Please see this ever modifying page which seeks to demonstrate in a poorly organized, yet humorous manner, what the hell I’m trying to accomplish with this primitive recursive state machine stuff.
And as an added bonus – the great “Recursive Functions” book by Rozsa Peters contains the following remarkable note that has nothing to do with the mathematics, but a lot to do with how mathematicians think.
Ok, “the present conditions” were kind of dramatic.
At least 1,000 Soviet tanks are reported to have entered Budapest and troops deployed throughout the country are battling with Hungarian forces for strategic positions.
The Soviet air force has bombed part of the Hungarian capital, Budapest, and Russian troops have poured into the city in a massive dawn offensive.
I mentioned the phobia against mere experimentation recently, but now I have some more fascinating glimpses into “peer review”. I have some theoretical work I’m trying to finish up and get published somewhere so someone smart can do something with it. It may be junk or not – that’s why we have “peer review” in science. So I send a paper to LATA as something of a first effort. The reviews were negative. Pravda, well Pravda said: it stinks. Oh wait, that was a Tom Lehrer lyric. Have I mentioned how happy I am to have found a way of earning a living outside of Academia? In any case, here’s the most annoying of the three reviews:
OVERALL RATING: -2 (reject)
The authors discuss well-known methods for specifying Moore machines.
The referee did not find anything new in this paper.
The general direction of this research seems useful.
Certainly a fair comment and one that is pertinent except for one glaring omission – the citation. Perhaps the paper does repeat material that is well known to the expert reviewer and not the poor author. So where is the “for example, Perrin’s 1995 survey describes the same methods” ? Without a citation, the review has a strong flavor of humbug. But it’s not just the reviewer who comes into question here. The proceedings editor received this review and did not ask for clarification. If I had not seen similar responses to papers written by other people, perhaps I’d be less skeptical. But I have been in the position of a conference editor where I asked reviewers for citations – and most of the time, the reviewer was not able to substantiate. Why? Because if the reviewer can substantiate, if she or he really thinks that the paper covers known material, the natural inclination is to point to the known material. Of course, I complained to the conference program committee chairs and got this response.
PS: At conferences, there is usually no discussion on acceptance /
non-acceptance with the authors.
I’m not sure about “usually”, but often there is discussion. For example
In author response, also called rebuttal, reviewers enter their reviews, authors read the reviews, enter a response, and then reviewers make their final decisions. The purpose is to provide authors a forum to correct and directly address issues raised in the reviews.”Improving Publication Quality by Reducing Bias with Double-Blind Reviewing and Author Response” Kathryn S McKinley, The University of Texas at Austin ACM SIGPLAN Notices, 43(8):5–9, August 2008.
See, that is known as a “citation”. I made a statement and then made a reference to backing material so that the reader could look it up. Was that so hard? Going back to the problem with articles on experimental systems, reviewers who find the data unsurprising should be required to point to the literature that provide the same information. “It’s well known” without backup is offensive to the whole scientific process. If it is well known, then point to where it is explained. If not, then be silent.
I gotta add that this is far from the worst quality review I ever received. The all time star, included something like this: “The author fails to understand that while in a set {a,b} [something], if the ordering is different and the set is {b,a} then ...”. But I’m just starting to send out papers again, there’s hope that something even more amusing will appear.
EURYI applications were first submitted to the relevant national research councils, who could nominate a specific number of candidates. This selection cut the proportion of women from one-quarter to one-fifth. Each national research council oversaw a drop in the number of selected women. In Spain, where nearly a third of the applicants were women, not one was nominated. The all-male Spanish list emerged with the highest success rate in the later European rounds, nearly three times the average. From 133 national nominees, European evaluation committees created a shortlist of 67, causing the largest drop in the proportion of women: 9.90+/-.5% of men applying made the European short list , but only 4.7+/-1.4% of women did. [cite]
Here’s Edsger Dijkstra discussing the birth of the use of axiomatics in computer science – the start of “formal methods” research. What’s striking is the assumed choice between “axiomatic” and “mechanistic” as if there was no other way. In a later note he writes:
And now we are back at our old dilemma. Either we take by definition all properties of the model as relevant, or we specify in one way or another which of its properties are the relevant ones. In the first case we have failed to introduce in the name of “divide et impera” an interface that would allow us to divide and rule and the study of how we could build upon the (only implicitly defined) interface seems bound to deteriorate into a study of the model itself; in the second case we are again close to the axiomatic method….
[…]
Or, to put it in another way: if the traditional automata theory tends to make us insensitive to the role interfaces could and should play in coping with complex designs, should it then (continue to) occupy a central position in computing science curricula?
And I’m struck by the idea that seems utterly wrong to me, that one either uses the methods of formal logic OR one is stuck without any ability to abstract or underspecify
The reason mathematics has advanced so much was not because of the Euclidean axioms-lemma-theorem straitjacket, but in spite of it. Luckily, when we actually discover mathematics, we do it the Babylonian way, empirically and algorithmically. It is only when it is time to present it, that we put on the stifling Greek formal attire.
I always had the impression that the entire group of “process algebra” people didn’t know much about automata, but this is surprising.
But meanwhile I got somehow interested, and I don’t know how, in concurrency. I remember that, without linking it to verification particularly, I wondered about interacting automata. I had an idea that automata theory was inadequate, because it hadn’t said what it was for two automata to interact with each other. Except for the Krohn-Rhodes Representation Theorem, which said something about feeding the output of one automata into another. But there wasn’t interaction between the automata. (cite)
I don’t want to read too much into this, but Krohn-Rhodes theory provides an algebraic result about efforts to simplify state machines by “dividing” them into simpler machines connected in a cascade (with information flowing one way). It has nothing to do with networks of communicating automata, a subject that was not particularly of interest during the early 1960s when the minimization of state machines was a focus for research. In fact, it is not unusual to find in papers of that period a definition of very general automata products in which the machines “interact”, followed by a definition of the special case of “loop free products” which were seen as critical in an age where reducing a design from 100 flip flops to 70 flip flops was a tough and important engineering task. The “network” case where there is arbitrary communication between machines was apparently seen as obvious.
He [Perlis] published a very obnoxious paper arguing against a mathematical approach to programming cite
The paper by De Millo, Lipton and Perlis starts as follows:
Many people have argued that computer programming should strive to become more like mathematics. Maybe so, but not in the way they seem to think. The aim of program verification, an attempt to make programming more mathematics-like, is to increase dramatically one’s confidence in the correct functioning of a piece of software, and the device that verifiers use to achieve this goal is a long chain of formal, deductive logic. In mathematics, the aim is to increase one’s confidence in the correctness of a theorem, and it’s true that one of the devices mathematicians could in theory use to achieve this goal is a long chain of formal logic. But in fact they don’t. What they use is a proof, a very different animal. Nor does the proof settle the matter; contrary to what its name suggests, a proof is only one step in the direction of confidence. We believe that, in the end, it is a social process that determines whether mathematicians feel confident about a theorem–and we believe that, because no comparable social process can take place among program verifiers, program verification is bound to fail.
To me, the problem with Dijkstra is that he was so sharp and such a good writer that he was able to make persuasive cases out of obviously wrong ideas. Dijkstra wanted to be a scientist in the model of theoretical physics, not an engineer. I’m pretty confident that Dijkstra was wrong: programming is engineering – in fact, physics is not as far from engineering as some people would like to believe. I’m not a huge fan of the engineering discipline as it exists in the USA. It has all sorts of negative aspects – including those Dijkstra railed against. But the vision of a programmer as, not a mathematician, but a formal logician flying far above the grubby compromises and trade-offs of mere engineering in a platonic bubble of pure reasoning is wrongheaded.
Dijkstra published some criticism of the Demillo paper at the time and in their response the authors stated something that, as far as I know, remains true
We must begin by refusing to concede that our confidence in a piece of real software has ever been increased by a proof of its correctness
When I was in graduate school (a long time ago), a famous formal methods scholar came for a talk and explained to us that formal methods were needed if we were ever going to develop fault tolerant software. I pointed out that, for example, the Tandem Software worked pretty well in practice. “It cannot”, retorted the famous scholar.
So there.
Here’s Edsger Dijkstra discussing the birth of the use of axiomatics in computer science – the start of “formal methods” research. What’s striking is the assumed choice between “axiomatic” and “mechanistic” as if there was no other way. In a later note he writes:
And now we are back at our old dilemma. Either we take by definition all properties of the model as relevant, or we specify in one way or another which of its properties are the relevant ones. In the first case we have failed to introduce in the name of “divide et impera” an interface that would allow us to divide and rule and the study of how we could build upon the (only implicitly defined) interface seems bound to deteriorate into a study of the model itself; in the second case we are again close to the axiomatic method….
[…]
Or, to put it in another way: if the traditional automata theory tends to make us insensitive to the role interfaces could and should play in coping with complex designs, should it then (continue to) occupy a central position in computing science curricula?
And I’m struck by the idea that seems utterly wrong to me, that one either uses the methods of formal logic OR one is stuck without any ability to abstract or underspecify, And it’s also interesting to see this impoverished view of automata theory that underpins so much of the formal methods literature.
The reason mathematics has advanced so much was not because of the Euclidean axioms-lemma-theorem straitjacket, but in spite of it. Luckily, when we actually discover mathematics, we do it the Babylonian way, empirically and algorithmically. It is only when it is time to present it, that we put on the stifling Greek formal attire.
(links and dates fixed March 15 2015 – thanks to Luu and pm90 at news.y.combinator for digging this up)
October 2008: It’s somewhat funny and somewhat sad to read this thread on the old USENET. Starting out with Andy Tanenbaum’s proposed list of accepted truths (most of which I thought wrong at the time)
GENERALLY ACCEPTED AS TRUE BY RESEARCHERS IN DISTRIBUTED SYSTEMS
– The client-server paradigm is a good one
– Microkernels are the way to go
– UNIX can be successfully run as an application program
– RPC is a good idea to base your system on
– Atomic group communication (broadcast) is highly useful
– Caching at the file server is definitely worth doing
– File server replication is an idea whose time has come
– Message passing is too primitive for application programmers to use
– Synchronous (blocking) communication is easier to use than asynchronous
– New languages are needed for writing distributed/parallel applications
– Distributed shared memory in one form or another is a convenient model
and then Rob Pike’s refutation entitled “Andy Tanenbaum hasn’t learned anything”. A key point that comes up later in the discussion is Tanenbaum’s (incorrect) assertion that a “factor of two” performance loss is nothing to worry about. The date of the discussion is interesting, because in a few years the Linux Tsunami washed away most of the landscape of this discussion. As for my contribution it is very disturbing to see that I have not learned much about those topics in the last 1416 23 years. (updated again in 2015)
It is clear that Rob Pike was right on many more issues than AST, but that seemed clear at the time too.
The implementers of Plan 9 are baffled by Andy Tanenbaum’s recent posting.
We suspect we are not representative of the mainline view, but we disagree
at some level with most of the “GENERALLY ACCEPTED” truths Andy claims.
Point by point:
– The client-server paradigm is a good one
Too vague to be a statement. “Good” is undefined.
– Microkernels are the way to go
False unless your only goal is to get papers published.
Plan 9’s kernel is a fraction of the size of any microkernel we know and offers more functionality and comparable or often better performance.
– UNIX can be successfully run as an application program
`Run’ perhaps, `successfully’ no. Name a product that succeeds by running UNIX as an application.
– RPC is a good idea to base your system on
Depends on what you mean by RPC. If you predefine the complete set of RPC’s, then yes. If you make RPC a paradigm and expect every application to build its own (c.f. stub compilers), you lose all the discipline you need to make the system comprehensive.
– Atomic group communication (broadcast) is highly useful
Perhaps. We’ve never used it or felt the need for it.
– Caching at the file server is definitely worth doing
True, but caching anywhere is worthwhile. This statement is like saying ‘good algorithms are worth using.’
– File server replication is an idea whose time has come
Perhaps. Simple hardware solutions like disk mirroring solve a lot of the reliability problems much more easily. Also, at least in a stable world, keeping your file server up is a better way to solve the problem.
– Message passing is too primitive for application programmers to use
False.
– Synchronous (blocking) communication is easier to use than asynchronous
They solve different problems. It’s pointless to make the distinction based on ease of use. Make the distinction based on which you need.
– New languages are needed for writing distributed/parallel applications
`Needed’, no. `Helpful’, perhaps. The jury’s still out.
– Distributed shared memory in one form or another is a convenient model
Convenient for whom? This one baffles us: distributed shared memory is a lousy model for building systems, yet everyone seems to be doing it. (Try to find a PhD this year on a different topic.)
How about the “CONTROVERSIAL” points? We should weigh in there, too:
– Client caching is a good idea in a system where there are many more nodes than users, and users do not have a “home” machine (e.g., hypercubes)
What?
– Atomic transactions are worth the overhead
Worth the overhead to whom?
– Causal ordering for group communication is good enough
We don’t use group communication, so we don’t know.
– Threads should be managed by the kernel, not in user space
Better: have a decent process model and avoid this process/thread dichotomy.
Rob Pike
Dave Presotto
Ken Thompson
Phil Winterbottom
Distributed shared memory – an idea that never made any sense to me.
[edited to reflect the passage of time][ and again to add the Pike/Presott/Thompson/Winterbottom text]
This old note by Spolsky explains why the shift to java-only in computer science classes is harmful and reminds me of two events in my old career as an academic. One was when a student came by my office to explain to me, in the most condescending manner, how the linked-list exercise I had given in class could have been done much more easily using the new operator instead of all that obsolete pointer stuff that I had learned back in the ice-ages (we had to chisel those pointers out of glaciers with flint spears and punch cards). The second event was during the only perq I ever got for being a “department chairman” (the worst job I ever had, and that includes a couple of horrible days planting tree saplings on a devastated hillside in Arkansas ). The perq was a visit to the CS department chairs meeting in Snowmass one summer. It was quite beautiful out there and I even went to a meeting or two for forms sake. At one meeting, there was a discussion about the drop in the number of women going into
Anita Borg
computer science – the field started out not so bad and converged on the terrible engineering norm somewhere in the 1980s. Some poor sap stood up, and channeling Larry Summers in advance, suggested that reducing all that hard math content might be a good thing to do because, implicitly, girls aren’t so good in math. I was sitting near a professor from MIT and would have bet money that she was going vault out of her chair and hammer the speaker to the ground, but sadly enough she didn’t and perhaps the lack of a salutory example cost Dr. Summers his job later on. And the moral of these three different points, ahem, is that a variety of forces have lead to the watering down of the general computer science degree and none of it accomplishes any of the purposes the watering down was supposed to accomplish, but it has made life easier for CS professors who are just going through the motions.
because it hadn’t said what it was for two automata to interact with each other. Except for the Krohn-Rhodes Representation Theorem, which said something about feeding the output of one automata into another. But there wasn’t interaction between the automata. (
