I read Dijkstra's goto considered harmful in college, circa 1970. I was a young programmer at the time, and it made me think and reconsider how and why big programs were often hard to understand.
Years later, in grad school, my research was on program verification. Dijkstra was a big influence on the field. I attended a lecture at UT Austin that he gave before moving to the US.
Dijkstra's approach to proving the correctness of programs is hard to apply in practice. Like a geometry proof, there are ways in which a proof of correctness can have mistakes that aren't obvious. Here's an example, prove that a sorting algorithm works. If the specification is that the output must be in sorted order, a proven program can still fail to sort correctly. The specification has an error, the output must not only be in sorted order, it must ensure that all of the input elements make it somewhere to the output. But this isn't good enough. A sort proven to meet this specification might leave out some duplicate values. Requiring that the output be the same length as the input still isn't good enough, multiple copies of one element might hide missing duplicate input values for another element. The specification requires that the output be a sorted permutation of the input.
Sorting is a well understood problem, but real verification must deal with the strange mathematics implemented by computers. The mathematical theories that we are accustomed to from school assume infinite precision and no overflow, real life hardware doesn't act this way.
All of this makes program verification hard, and my hope is that AI programming assistants will someday aid in the construction of meaningful specifications and work with the programmer to verify the correctness of programs or determine their safe operating boundaries. Progress has been slow, and the tools are still impractical for use by most programmers on most programs.
Program verification is a fool's errand and Dijkstra would have been the first to tell you this. The correct approach is program construction following derivation rules that do not admit error. You don't need to verify a program produced from a specification this way anymore than you need to prove a proof by construction. It baffles me that to this day the distinction defies comprehension for so many in our field.
Bugs can still occur of course, but if one restricts oneself to valid manipulations the bugs will be found in the specification and reflected in the code. It's not a magic bullet, and that's one of the reasons TLA+ was invented, it helps with complexity on the specification side. However a method like the one Dijkstra shows in the referenced paper can be used to faithfully implement the TLA+ checked specification.
Take a look at Frama-C or Ada Spark sometime; they apply the predicate transformer semantics style to code and do pretty well. But yeah, incomplete specifications are always fun.
This is such a great and actually important comment. I’ve been obsessed with program correctness / verification for a while now. It just seems like the holy grail that we can’t fully attain yet. But you keep bumping into certain walls, and the fact that correctness can only be relative to a given specification is a profoundly huge wall.
There’s no checking to see if your specification is under-specified.
Given what I've seen of AI today (works reasonably well at the best of times, but is sensitive to unusual cases and can produce totally nonsensical results otherwise; and nearly impossible to actually debug), I remain highly skeptical.
Within the context of theorem-proving, that's not as significant a problem -- you still have a verification of the proof at the end. The value of AI is that it could potentially replace human intuition for how to construct the proof. Humans don't always get this right either. It may take the AI many attempts to get the program right, but you'll know at the end that it is correct.
It is remarkable how much he contravened modern academic norms: no work to bring in external funding, relatively few papers, very little collaboration, almost no PhD students. It's not an exaggeration to say that a young researcher with these characteristics today would likely get fired from any high-ranked American research university before even coming up for tenure review. Perhaps our modern academic metrics of merit are missing something?
Oh, yes. I’m very proud of not having a Ph.D. I think the Ph.D. system is an abomination. It was invented as a system for educating German professors in the 19th century, and it works well under those conditions. It’s good for a very small number of people who are going to spend their lives being professors. But it has become now a kind of union card that you have to have in order to have a job, whether it’s being a professor or other things, and it’s quite inappropriate for that. It forces people to waste years and years of their lives sort of pretending to do research for which they’re not at all well-suited. In the end, they have this piece of paper which says they’re qualified, but it really doesn’t mean anything.
I don't get it. Isn't it well-known that PhD makes only sense for people who want career in research? In this case, why "wasting years and years" doing research would be a waste of time?
My wife is an organic chemist by education and for every R&D job she applied to, there were tens to hundreds of applicants with PhDs. Having "only" a Master's degree, she had no chance. Pretty much all her college friends went to do a PhD, just so they could get a job.
Is there something wrong in this? Better qualified candidates were preferred for a research job. Of course, if you argue that the job didn't actually require PhD-level knowledge/experience, then the problem is in oversaturated job market of the field, not in the PhD system.
I've worked at a software company that received significant local government funding predicated on certain goals. One of those was hire X number of PhD graduates from the two local universities at a (relatively large) minimum salary. This then means the universities could say that a PhD from their various disciplines practically guarantees you a well paid job.
Unfortunately there was a huge gap in what was expected of these people and what they could actually do. Save but a few they were pretty awful employees for the job. Not necessarily their fault, but it's one example of the gamification of the system.
In chemistry "then", and I assume still "now", a MS is viewed as a "failed to complete the PhD" degree unless it comes from a smaller school lacking a PhD program. Or, "wanted to go to Med or Law school and didn't get in". When hiring, BS/MS chemists are seen as a pair-of-hands/technicians. There's a noticeable rank difference in how they enter Pharma - BS/MS with several promotions end up where PhD's walk in the door. Is this right or fair? Probably not, but PhD's are seen as somebody who can work (more) independently than a technician. Ironically, a significant fraction of the lab work is done by the BS/MS as PhD's graduate out of the lab if they learn medchem properly. So the best lab hands have the lowest status to outsiders.
It might be different in Process Chemistry, which is where the best lab work is work. Perhaps those who have the magic in scaling up a reaction into production are like those who can debug anything? I've never worked with those groups or with the Analytical chemists in Development.
Disclaimer: I have a PhD, but never wished to go into academia due to the politics. And yeah, it's a union card.
> In chemistry "then", and I assume still "now", a MS is viewed as a "failed to complete the PhD" degree unless it comes from a smaller school lacking a PhD program.
I don't know which country GGP (or his wife) is from, and you might well be correct about your assessment, but there are some countries where master's degrees are viewed differently than in the U.S.
Where I live and did my degree (Northern Europe), it's commonplace to do a master's rather than just a bachelor's degree. In fact, in many fields the master's used to be considered the basic "undergrad" degree here. A bachelor's degree existed, but in many fields you'd have been considered to have dropped out of completing a master's if you only had bachelor's. That might be slowly changing, with a higher emphasis given to bachelor's level degrees, but the sentiment probably still remains.
You asked "Isn't it well-known that PhD makes only sense for people who want career in research?" and I answered with a counterexample. There are many places where a PhD makes sense for a career in industry.
And if you think an oversaturated job market pushing people into doing PhD's they don't need for the actual job isn't a problem for "the PhD system" then I call you short sighted.
Opened his Wikipedia page out of curiosity and what do you know, some climate change denier decided that his ideas about CO2 level and their effects on climate deserve to be in the opening section.
Perhaps. I can't really speak to his career before he came to UT Austin in 1984, he was already very famous (Bjarne Stroustroup at Texas A&M/Columbia or Brian Kernighan at Princeton famous); if I remember, his chair was created for him as a full professor and without many of the usual duties of a professor. (One of his stipulations was that he not be made Chairman of the department.)
According to the article, as a young researcher, he was
* A "programmer" (something like a research assistant, perhaps?) at the Mathematisch Centrum (Mathematical Centre) in Amsterdam.
* Professor in the mathematics department of the Eindhoven University of Technology from 1962-1973. (As I understand, the "external funding" thing is less of a problem in mathematics. Also, I have no idea how tenure works there.)
* Finally, research fellow at the Burroughs Corporation.
It's true, he didn't have many direct PhD students (two?!), but his collaborations were many. (I don't know if the Tuesday Morning Group at UT is still active,[1] but it was rather well known and its members produced a great deal of what is now "theoretical computer science".)
If you're trying to compare Dijkstra to J. Random Young Researcher, J's gonna have a hard time any way you look at it.
[1] UT no longer requires automata theory or formal logic for CS undergraduates. They're dead to me.
> Professor in the mathematics department of the Eindhoven University of Technology from 1962-1973. (As I understand, the "external funding" thing is less of a problem in mathematics. Also, I have no idea how tenure works there.)
Back then, i think full professors were appointed by the Queen. (Certainly so for Beatrix, but he became a prof before her inauguration)
Being appointed by the Queen made it really difficult to fire you - one of the reasons (I was told) they stopped this practice.
Moreover, back then research funding worked very different from how it works now in .nl. Actually, I have some idea of how finding worked from the mid-90s on... but I've read that prior to early 80s, in .nl, most PhD students were part-time and not employed by the university.
Not sure how accurate that is. Irrespective of its accuracy, it's clear that academic life had changed drastically since then. (In .nl at least)
> Being appointed by the Queen made it really difficult to fire you
Monarchies today being at that awkward stage where they wield enough protection to prevent somebody from being fired but no longer enough power to get them beheaded…
> I don't know if the Tuesday Morning Group at UT is still active,[...] but it was rather well known and its members produced a great deal of what is now "theoretical computer science".)
> It's not an exaggeration to say that a young researcher with these characteristics today would likely get fired from any high-ranked American research university before even coming up for tenure review.
He wouldn't even get in an university to get the chance to be fired. And that's not specific to the US, it applies to nearly all developed or developing countries.
That person wouldn't be able to get much past a PhD, even as a student.
You’re right. The right of passage for most US computer science PhD programs is publications in the “right” journals and conferences. If you don’t publish you will rarely get past your thesis proposal. I think there are very few, very select professors in the US that prohibit publishing prior to graduating. But their count is likely in the single digits.
Also, by some miracle you manage to graduate by minimal publishing or no publications you will find all doors to getting research funding shut. This means that you are basically unemployable as a tenure track professor (universities prefer their newly minted assistant professors to come with funding).
The best teachers I’ve had published little or nothing: they were teachers first, but researchers who also taught. It’s a shame the modern colleges and universities don’t make this really possible anymore.
People used to say of my alma mater that the teaching was decent but the facilities were amazing.
There was a feel on campus that the people who were really going to 'make it' were only putting in B- or C+ work and spending the rest of their time working on side projects. There were very few days in a given year when more than half of the computer labs were full at the same time, and with Unix boxes you can always remote in to the flavor of machine you need.
You don't need much research budget if you already have access to time on equipment. I'd be curious to know if Dijkstra had access to a similar embarrassment of riches.
> I'd be curious to know if Dijkstra had access to a similar embarrassment of riches.
Dijkstra spent a good chunk of the latter part of his career at the University of Texas in Austin. There was plenty of access to facilities there, but that wasn't really what his research was about. He wrote longhand (scans here: https://www.cs.utexas.edu/users/EWD/) and didn't really use much technology directly in his work.
This makes sense, because after all, Dijkstra is responsible for this famous quote: "Computer science is no more about computers than astronomy is about telescopes".
This is the difference between computer science and software engineering.
And the vast majority of people who graduate with a CS degree are going to work as software engineers, not as computer scientists. They are therefore being mis-educated to the degree that their CS program agrees with Dijkstra's philosophy. (Which doesn't mean that Dijkstra is wrong about CS. It just means that a CS degree shouldn't be the passport to a career in software engineering, or even a job as a grunt programmer.)
Having a good understanding of theoretical CS and its fundamentals makes programming a relatively trivial activity. I don't think a CS degree miseducates you at all, as long as you actually internalize the CS you learn.
Yes, this is why computer science students from schools like Stanford, Carnegie Mellon, MIT (well, it's an engineering school, anyway), and UT Austin (EWD's stomping grounds) are almost completely unemployable in the software-related industries. All of the employers learned pretty quickly that they were all grossly incompetent.
First, even UT Austin doesn't run their CS program as EWD would have wanted. See his comments when they switched to Java.
Second, I suspect (but cannot prove) that this problem is why computer science grads need a couple of years of close supervision on the job before you can trust them with anything.
I suspect (but cannot prove) that this problem is why computer science grads need a couple of years of close supervision
There's more to it than that, a lot of which has more to do with learning how companies are structured and how people communicate in the corporate world. Among other things, college students have been trained to tackle any assignment with the assumption that the information they have been given is accurate and comprehensive, and the professor would prefer to hear nothing from them until the assignment is turned in as complete as possible right before the deadline.
If you want to educate people to be immediately productive in a corporate environment, that's not what college is for anyway.
They need supervision because they haven't been apprentices gaining practical experience yet. College (especially the sciences) is not about apprenticeships. If you just want "grunt programmer[s]", we need proper apprenticeships and trade schools. Like electronic technicians and plumbers go through.
> College (especially the sciences) is not about apprenticeships.
It is and it isn't. Most degree programs don't require it, and some don't integrate it as a for-credit option, but most (including in the sciences) do open opportunities for them, and lots of students take advantage of that opportunity and are more employable because of it.
Some folks say the science education system is similar to the Medieval Guild systems: apprentices (grad students), journeymen (postdocs) and various levels of master craftsmen (professors). These are intended as ranks not genders, so s/men/people/g if desired.
Academia (not just, or even especially, in the sciences) is a guild system on those lines, but if you are looking for employment outside of academia, things are a bit different even if you need to go through some part of the academic path for the career entry you are aiming for.
Interestingly, Eindhoven University of Technology did use (more-or-less) Dijkstra's approach throughout the 90s. Sure, there were some odd bits, but the core of the curriculum was Dijkstra style.
Nice strawman. Oh, wait, no it isn't. It's a really cheap strawman. But in the end, it's just a strawman.
But it is my position that a graduate of a proper software engineering degree would take less initial supervision than a graduate of a CS degree.
Why? Because they would have already seen ambiguous requirements, and would have an idea of what to do. They would have already seen a multi-hundred-thousand-line code base, and would be more likely to have some idea how to navigate in one. They would have some idea of what production-level code looks like, and how to go about achieving that level of completeness. And so on.
> Yes, this is why computer science students from schools like ... UT Austin (EWD's stomping grounds) are almost completely unemployable in the software-related industries.
UTCS 1997 here. I've been employed in software-related industries continually since graduation, and I can honestly say my UTCS degree has been nothing but helpful in that regard.
BTW, the personal website listed in your profile is down. You might want to look into that.
What's more confusing is that Software Engineering, Computer Engineering and Computer science overlap quite a bit, but are distinct fields.
Furthermore, there really is two kinds of CS departments: the ones that were spun out of a Math department and those that emerged out of an Electrical Engineering one.
The European tradition is that if you are not admitted to the guild you must not work in the field without supervision. Nothing wrong with that, tbh. You get something out of it, too, your sponsor is invested in your success.
Famously, Dijkstra did not have a computer for most of his time there. He either typed his work on a manual typewriter (early in his career) or wrote it longhand in his elegant Dijkstra font (https://news.ycombinator.com/item?id=7796919). His secretary would print out his emails for him to read and respond to.
Eventually, he got a Macintosh (IIRC, Cynthia Matuszek (https://www.csee.umbc.edu/~cmat/) was the one who set it up for him. (Hi!))
Hamilton Richards (maintainer at the time of the EWDs on the site) was my analysis of programs professor at UT. I had arrived there in 2003 as a freshman, the reverence and impact of Djistrka was incredibly palpable.
I remember some of my classmates were turned off by how theoretical some of the core courses were. A lot of people saw it as less practical. Also the height of Java's OO take over of CS programs, it was definitely a mix of classes. Although the theory courses tended to either care less about language choice or focused on Haskell.
That reminds me of the anecdote where one of Google’s hiring committees realized that they wouldn’t have gotten hired had they been judged by their own standards. It makes you wonder how much talent gets filtered out when we apply very stringent metrics to grade candidates.
I can't find it but I saw a presentation (I think from someone at Etsy) where the presenter described being on an interview panel that failed all of the candidates in a batch, only to find out that they had been given their own packets to review.
Working at a smaller company, I knew a few people in the hiring committee that had unreasonable standards. We used to tease them that they wouldn't pass their own standards when they were hired. Fortunately we didn't need unanimous approval of candidates.
Moishe Lettvin - What I Learned Doing 250 Interviews at Google. It is on Etsy Eng channel
Youtube url with the relevant time frame https://youtu.be/r8RxkpUvxK0?t=532
For many years many, if not most, of my fellow physicians have remarked that it's doubtful we would be admitted today to medical school. (me: UCLA Medical School, class of 1974)
That said, I don't know about self-mockery. A good line from the linked lecture transcript:
> The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague.
He seems to be addressing the issue of inflated egos influencing people to be "real programmers". For example, do you use a simple GUI interface? -- HA! I can type an arcane string into a command line with my TOES! Clearly, I art teh superior to thou. Which is stupid, because a proper GUI that shows the full scope of the API is awesome, while memorizing arcane strings is a silly practice. But, some folks let feelings of intellectual superiority cloud their judgement and beliefs, which Dijkstra was speaking out against.
He repeats this theme several times, with the overall lecture being a tad repetitive and redundant as it states the same thing over and over in a repetitive series of repetitions, but for a specific example:
> Finally, although the subject is not a pleasant one, I must mention PL/1, a programming language for which the defining documentation is of a frightening size and complexity. Using PL/1 must be like flying a plane with 7000 buttons, switches and handles to manipulate in the cockpit. I absolutely fail to see how we can keep our growing programs firmly within our intellectual grip when by its sheer baroqueness the programming language —our basic tool, mind you!— already escapes our intellectual control. And if I have to describe the influence PL/1 can have on its users, the closest metaphor that comes to my mind is that of a drug.
In short, Dijkstra strongly advocates intellectual minimalism. The "humility" he advocates is fortitude against ego-driven peacockery in decision-making; taking the simplest possible approach, that's the easiest to do, even when doing so doesn't show off one's intellect.
Dijkstra strongly advocates not making a mess of things. He then elaborates this means the primary challenge the programmer faces is keeping his programs intellectually manageable, which among other things means not burying himself in needless complexity.
That is good stuff (well he was Dijkstra). I think we've all seen such hubris play out. When you want to prove that you are intellectually superior you will demonstrate that you can master the most difficult tools (say category theory?) without understanding that your real goal should be to find simple solutions to difficult problems.
A simple solution does not look like much because it is so simple, but it can take a genius to come up with it. Whereas complicated solutions are easier to come by and do demonstrate your intellectual skills.
Bear in mind though that spending hours upon hours to find a simple solution to a hard problem will tank your professional career. Why? Because your manager will look at your simple solution that you took such pains to derive and then ask why it took you so long to produce such a small amount of such obvious code.
That is the case no doubt in most organizations. And I can see their point if it works it works even if it may be very difficult to maintain it. But that should be a conscious decision, not a point of pride how complicated the code is to understand.
Just because a person can write code that only they can understand does not mean they are more intelligent than others, nor that the quality of such code would be "good". :-)
Although I’ve seen numerous examples of hubris by creating accidental complexity, I actually think category theory is an exercise in minimalism. But the realization only happens when understanding the complexity of ‘normal’ imperative and object oriented programming.
The problem with category theory, as I see it, happens due to a mismatch with our mode of creating. We tend to converge in our solutions from chaos to order. Formal systems don’t provide space to be chaotic in. We need to be right the first time.
We need languages and IDEs that will help us find abstractions. Static analysis saying: “this thing here is like all those other things if only you see it like so. Perhaps you want to structure it like those other things as well?”
One of my past career pet peeves was not being able to work in the same team with some people I was really excited to work daily with. I almost joined the research group, passed interviews, got accepted, but eventually everything got stalled because some "credentials" weren't there.
It would be very funny to watch foremost experts in relatively new fields being denied because they don't have phd students. I somehow doubt this is the case, though.
I wish seeing the name Dijkstra didn't immediately remind me of his oft-quoted BASIC comment:
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
The problem is it's quoted regardless of how much the BASIC dialect being discussed resembles the one he was talking about [1]. There are lots of good BASIC languages out there running all kinds of useful software that are dismissed out of hand by a subset of developers simply from that comment.
In my opinion, The Proper Way To Teach Computer Science was the one area where Dijkstra made his most detrimental contribution, by promoting a particular school of instruction based on strong opinions with weak to no empirical underpinnings.
In _Coders at Work_, Knuth offers a counter-argument that I find compelling:
> Seibel: It seems a lot of the people I've talked to had direct access to a machine when they were starting out. Yet Dijkstra has a paper I'm sure you're familiar with, where he basically says we shouldn't let computer-science science students touch a machine for the first few years of their training; they should spend all their time manipulating symbols.
> Knuth: But that's not the way he learned either. He said a lot of really great things and inspirational things, but he's not always right. Neither am I, but my take on it is this: Take a scientist in any field. The scientist gets older and says, "Oh, yes, some of the things that I've been doing have a really great payoff and other things, I'm not using anymore. I'm not going to have my students waste time on the stuff that doesn't make giant steps. I'm not going to talk about low-level stuff at all. These theoretical concepts are really so powerful-that's the whole story. Forget about how I got to this point." I think that's a fundamental error made by scientists in every field. They don't realize that when you're learning something you've got to see something at all levels. You've got to see the floor before you build the ceiling. That all goes into the brain and gets shoved down to the point where the older people forget that they needed it.
> Peter Seibel. _Coders at Work_
It is clear from the reading the EWDs that Dijkstra considered actually doing something with Computers detrimental to the practice of Computer Science as he conceived it, but the kind of Computer Science he practiced past 1975 or so was not particularly useful to Computer Engineering, because it refused to engage with it, and, as the article points out, it was not even particularly good math, because it refused to engage properly with that field as well.
Because at the time he wrote it there wasn't a good standard or sufficiently common one that had the properties he wanted to use for exploring algorithms. See MMIX for something closer to a modern architecture than the original MIX.
And there are a lot of people that dismiss his comment and the rest of his writings by ignoring what BASIC meant at the time of writing. Visual BASIC certainly wouldn't have been his favorite language, but had the features that BASIC at the time lacked and that he disliked it for (when you start digging into it: lack of recursion, non-reentrant functions, massive use of global variables, preference for goto versus structured control flow).
My first language was actually GWBASIC on an ancient hand-me-down computer, followed by QBASIC. When I saw that quote as a teenager I was terrified that I had killed my career before it had even started.
I've since become quite proficient in C, Ruby, Java, Kotlin, HTML, JS, shell scripting, and many many other languages and environments. So IMO there is very little modern merit to the idea that exposure to BASIC (or any other mocked language) is "mentally mutilat[ing]".
BASIC only ruins you if you have no intellectual curiosity. BASIC was my first language and with each new language I’ve learned since I’ve always been excited at the new possibilities and paradigms it opened up.
At university my formal methods lecturer once said, presumably in jest, "no software developer should be allowed to use an actual computer until they are 40 years old."
I wear it as a badge of honor, since I first learned programming in BASIC -- the good old line numbered variety -- on a mainframe. Then again I've never claimed that I'm not mentally mutilated.
Or at least who thought he carried computer science on his shoulders.
He made significant, important contributions. He wasn't the only one. Hoare, Backus, McCarthy... there were a lot of people who made important, fundamental contributions.
Structured programming caught on. Proofs did not, for reasons that would have offended Dijkstra - they took time, and it was actually more valuable (both socially and financially) to produce mostly-working software quickly than to produce proven-correct software slowly.
But he never would have accepted that the real world was that way. He insisted that his approach was correct. As Backus said of him, "This guy’s arrogance takes your breath away."
So: Important contributions? Absolutely. More than anyone else's? Perhaps. Carried computer science on his shoulders? No, but he probably thought he did.
Well, static types and analysis are in fashion now, and always moving on the direction of more powerful proof systems.
He was very likely too much ahead of his time on that. Decades after him we still don't have good enough tech to do the kinds of proof he expected... And yes, maybe too arrogant to realize that it's not the entire world that is dumb, but it's a core piece of the system that is missing.
On the other hand, he did work to improve proof systems, so who knows what he really thought?
> ALGOL 60 included a series of novel features, such as recursion, which was supported in a much more complex manner than logicians had ever envisaged...Recursive procedures in ALGOL 60 are much more complex than in Lisp.
Can anyone explain how this "much more complex" recursion works?
Early LISP implementations used dynamic scope. This means that non-local references in a function search for the variable's binding in the call chain: if A calls B then when B uses nonlocal variable x it refers to the x in A, not necessarily the x that belongs in the lexical parent of B as seen in the source code.
(Unlike C, Algol/Pascal/LISP can all define functions inside of other functions. These nested function definitions introduce lexical non-local scopes.)
Dynamic scoping is easier to implement than lexical scoping. With lexical scoping, the run-time must incorporate some mechanism to find the stack frame of a lexical parent (as seen in the program's source code) to access a nonlocal variable's value. In dynamic scoping the run-time can just follow the stack frame order (starting at the top) to find a nonlocal variable's binding.
Early LISP used dynamic scope. Scheme had lexical scope from the beginning. Common Lisp had both mechanisms and programs can use both.
The implementation of recursion also has to address proper access to nonlocal variables in functions that are values themselves and are passed as arguments to other functions. Do these functions access the nonlocal variables based on their call location or their lexical location in the source code? These problems with functions as arguments are known as the upward and downward funarg problems. Knuth wrote the man-boy program to test Algol 60 implementations in these areas.
Another complication for implementors of Algol 60 was parameter passing by-name, which is neither by-value nor by-reference. I don't recall any other well known language that has subsequently made that non-intuitive (to me) choice. I believe that Algol 68 abandoned call by-name, but it's been 25 years since I looked at the Algol 68 standard.
Which reminds me of The Funarg Problem Explained by Joseph Weizenbaum https://www.computerhistory.org/collections/catalog/10272070.... I used its "diagrams" to understand the closure mechanism (definition vs invocation environments) during the course of a Scheme class in 1996.
In C++ you can pass a no-arguments lambda with local bindings that approximates pass-by-name.
If actually evaluating the expression is something expensive and its result might not be needed, it can be the right thing. But whoever designs the function interface has to anticipate that possibility.
I may be fuzzy on this, it's been a long time. But isn't by-name a special case of passing a function? (And then referencing the parameter in the called procedure invokes the function.)
Yes, that's how "Jensen's Device" is used to implement call-by-name. However, note that the expression passed to an Algol 60 function by name causes the expression to be evaluated in the context of the function being called. Each time the formal parameter appears in the called function the expression passed to that parameter is re-evaluated.
I think this refers to making the implementation efficient.
They wanted performance on par with existing languages that didn’t allow recursion, and could simply assign fixed addresses to all function arguments and local variables.
Lisp didn’t have that. It allocated environments left and right. That meant that a function call allocated memory and potentially could trigger garbage collection.
The major improvement was to use a runtime stack. That was fairly novel. Earlier compilers used a stack at compile time to make it possible that those fixed addresses for arguments and locals could be shared between functions that didn’t call each other, directly or indirectly, but that stack didn’t exist at runtime.
And yes, the idea of a stack seems trivial nowadays, but it wasn’t at the time. Quite a few CPUs didn’t even have “jump to subroutine” or “return from subroutine” instructions.
Algol’s “call by name” feature also may have complicated this, but I don’t see how that’s more difficult than passing lambdas as arguments.
I'm not sure that's fair. If you have objects that escape downwards (so X calls Y, y creates some item i, i gets returned to X) then you can't have a stack. i may be overwritten at the next call of anything else, as the stack grows over it.
I guess they do escape analysis and where items are provably local, stack allocate them. If not, plonk them on the heap.
A call frame is an object like any other, so they go on the heap. This allows you to create closures.
“Dijkstra’s quest to generalize led him to use the well-known concept of a stack (i.e., a continuous portion of computer memory) as a run-time object, rather than a mere compile-time object as was the case in Samelson and Bauer’s ALCOR compiler.”
So, I agree with you it can’t have been as simple als I implied.
I doubt they would have plonked anything on the heap, though, because languages of the time didn’t have a heap (FORTRAN certainly didn’t), and the language Samuelson and Baur wrote didn’t even allow functions to call other functions.
In 1972 the Nova 1200 Jump-to-Subroutine wrote the Program Counter contents above the subroutine address and thus Subroutine-Return was a short jump via that address. It was possible at compile-time to check if this mechanism was enough. Otherwise the subroutine call was three words, because it was possible to make one word Pushs and Pops in that advanced architecture.
I did a quick search and according to this article [1], dijkstra's implementation was not restricted compared to other implementations at the time :
It is Dijkstra's generalizing style which stands out when a comparison is made with the work of his contemporaries. Rutishauser, for example, had limited the order of his procedure activations in his run-time system [59], while Dijkstra had no such restriction. Floyd's work [60, p.42-43] relied on three specialized “yo-yo” lists (i.e., stacks) instead of one general stack. Likewise, the MAD translator [61, p.28] used several specialized tables. Also, and most importantly, the ALCOR compilers were severely restricted in that they could not handle several ALGOL60 language constructs, including the recursive procedure (cf. Section ). Finally, though the Irons-Feurzeig system [54] did implement recursive-procedure activations and by means of one general run-time stack, it was, in the interest of efficiency, sophisticated in its run-time capabilities and, hence, unlike the run-time system of Dijkstra and Zonneveld .
The answers to this question are extremely interesting and show how much work has been done to get where we are today, a position I took for granted and never really understood until now (even in name: 'yo-yo list', for heaven's sake!)
It's a bit like parsing, these days we either reach for a technique (eg. recursive descent) or an implementation of a tool (such as flex/bison) and never think there was a time before these where people had to struggle conceptually with these things.
Well, the whole comment you link doesn't really deny that Dijkstra could be arrogant and dismissive, it just goes on to say essentially that he was a lovable old coot and that they listened to him only as much as they wanted; "Dijkstra was much more funny than annoying for anyone who had any sense of self. The two biggest problems in our not-quite-a-field were those who listened to him too carefully and those who didn't listen to him carefully enough."
I read it more like people back then weren't so sensitive and didn't even take that kind of straight talk as arrogance and dismissiveness.
But then maybe Alan Kay will show up and clarify.
I'm just old enough to remember when corporate culture was like this too. It used to be OK to say when people were wrong or get mad when programming errors lit the building on fire. That started to become NOT OK in the past 15 years. A lot of older engineers really had to to work hard to adapt because it's so frustrating today when people make careless mistakes over and over again and no one can say a word without being accused of not being a team player or something.
People were more likely to admit their own mistakes then too. In that environment it was better to come clean then try to hide a mistake even when coming forward can solve the problem faster.
We've overcorrected this stuff.. correcting it helps make the field more inclusive but at some point after we're diverse and inclusive we need to walk some of this behavior back a bit.
"Back then" was the 60s (whose decade really ran from about 1963 to 1973).
A good quote from Dave Evans (to faculty members who complained about a genius faculty member who could be abrasive): "We don't care if they're prima donnas as long as they can sing".
As I've mentioned in a few other places, including this forum, most people found Edsger to be funny. He obviously enjoyed wielding English for comments, biting, snide, and otherwise. He loved to project snide arrogance in his particular highly developed style.
A good friend of his was Bob Barton -- I think even more of a genius -- and perhaps even more idiosyncratic, pointed and neurotic. Barton was kind of on-stage most of the time, and had truly eloquent extemporaneous opinions.
But so what? Listen to Dave Evans, and then listen to what great and interesting people have to say.
One of the definitions for these people is that whether they are right or wrong, or whether you agree with them or not, what they say is so interesting that it absolutely demands to be thought about.
You can't beat that kind of help for your own thinking processes.
Part of the reason may be the advent of online. It is much easier to offend people online than in person for several reasons:
1. You do the offending in public
2. You can not get and give immediate feedback
on how what you're saying affects your counter-part
3. What you say is carved in stone
One fun item I'm lucky enough to own is a core memory stack from Dijkstra's Electrologica computer, ca.1958 or so -- very low density obviously. This machine is where the first working Algol compiler was written.
If your opinion of Dijkstra is mostly negative and the result of reading others' opinions or selective readings of his EWDs (some of which are incredibly negative in tone), it would behoove you to read his EWDs. Just go through the archive and grab random ones based on title, then later do a more systematic reading of them.
I spent a year reading all of the English language ones and it has made me a MUCH better programmer. I can't recommend them highly enough. Also his book A Discipline of Programming was seminal for me.
That's the archive, talked about in the linked article. Letters (mostly) that he wrote and sent out to people. Today we'd consider their content and length equivalent to a technical blog. Some were much longer, though.
A well written portrait of a truly great and original "Scientist" in the true sense of the term.
I have always wondered why his approach of constructing correctness proof along with the implementation never really caught on. I think it was what allowed him to come up with his novel algorithms. Have we lost something of the real essence of logical thinking here? Perhaps the paper mentioned in the article; Social Processes and Proofs of Theorems and Programs which he was vehemently against, will give me the other side of the argument.
Probably because the cost associated with constructing such proofs for the vast majority of modern software use cases (like showing ads on 8 different browsers) is too high (cheaper to just hire QA teams), and most programmers are not simultaneously software engineers, computer scientists, and mathematicians.
> cost associated with constructing such proofs ... is too high
People assume this is true because it has been repeated endlessly. I think it is an issue of granularity. For example; both Dijkstra's GCL and Hoare's Triples (fine granularity) vs. Meyer's DbC (coarse granularity) can be expressed using Assertions to build Preconditions/Postconditions/Invariants as "correctness proof" throughout a real-world software system. But their systematic usage is never taught nor enforced; we have to learn it by trial and error.
> For example; both Dijkstra's GCL and Hoare's Triples (fine granularity) vs. Meyer's DbC (coarse granularity) can be expressed using Assertions to build Preconditions/Postconditions/Invariants as "correctness proof" throughout a real-world software system
The average dev at an average company will read this and not understand 90% of your sentence. Again, the vast majority of devs are not computer scientists nor mathematicians.
They are good at what they do, which is building what their bosses ask for using whatever web framework they specialize in.
I think you are giving too little credit to the "average programmer's" intelligence. He/She is after all a self-learning, problem solving biological machine :-)
An organisation that treats its programmers as morons will soon have programmers that are willing and able to act like morons only. -- Bjarne Stroustrup
We all were "average programmers" at one time and didn't know better. But at some point some of us came to know(from whatever source) of a "better and correct way" of doing things and then realized that this should have been taught from the beginning. It is not enough to just teach people the syntax of a language and let them loose on the World; we have to be taught "discipline" and how to use it "correctly". In the context of this thread, that was exactly what Dijkstra strongly advocated for (see my other reply to you listing some paragraphs from EWD288).
References (Wikipedia is a good starting point though sometimes overly complicates simple ideas):
Addendum to my previous reply from the end of EWD288 - "Concern for Correctness as a Guiding Principle for Program Composition";
My thesis is, that a helpful programming methodology should be closely tied to correctness concerns. I am perfectly willing to admit that I myself may be the most complete victim of my own propaganda, but that will not prevent me from preaching my gospel, which is as follows. When correctness concerns come as an afterthought and correctness proofs have to be given once the program is already completed, the programmer can indeed expect severe troubles. If, however, he adheres to the discipline to produce the correctness proofs as he programs along, he will produce program and proof with less effort than programming alone would have taken.
The framework of this contribution does not allow the inclusion of a worked-out example. Instead I shall try to sketch how the hand-in-hand construction of a program and its correctness proof guides the programming process.
I found what I regard as the quintessence of this methodology in the summer of 1968, when my attitude towards flowcharts changed radically. Up till that moment, I had regarded a flowchart as something incomplete, as a plan, as a (half-pictorial, but that is not essential) representation of my intentions, something that as a description would only make sense if all further details, down to the bottom, had indeed been supplied. But it was then that I saw that such a sketch of a program still to be made, could be regarded as an abstract version of the final program, or even, that it could be regarded as "the program", be it for a —in all probability hypothetical— machine with the proper repertoire of primitive actions operating on variables of the proper types. If such a machine were available, the "rough sketch" would solve the problem; usually it is not available, and actions and data types assumed have to be further detailed in the next levels of refinement. It is the function of these next levels to build the machine that has been assumed to be available at the top level, i.e. at the highest level of abstraction. This most abstract version is now no longer a draft of the final program, it is an essential part of the total program; its correctness is independent of the lower level refinements and can be established beforehand. To give this correctness proof before proceding with the lower level refinements serves many purposes. It establishes the correctness of the top level. Fine, but what is more important is that we do this by applying well-established theorems applicable to well-known sequencing clauses, and as a result it becomes most natural to avoid clever constructions like the plague. But the most important consequence is that the proof for one level ensures that the interface between itself and the lower levels has been given completely, as far as is relevant for that level; and also, by fixing in the interface only what the correctness proof really needs, the interface can be kept free from overspecification.
Finally, a word or two about a wide-spread superstition, viz. that correctness proofs can only be given if you know exactly what your program has to do, that in real life it is often not completely known what the program has to do and that, therefore, in real life correctness proofs are impractical. The fallacy in this argument is to be found in the confusion between "exact" and "complete": although the program requirements may still be "incomplete", a certain number of broad characteristics will be "exactly" known. The abstract program can see to it that these broad specifications are exactly met, while more detailed aspects of the problem specification are catered for in the lower levels. In the step-wise approach it is suggested that even in the case of a well-defined task, certain aspects of the given problem statement are ignored at the beginning. This means that the programmer does not regard the given task as an isolated thing to be done, but is invited to view the task as a member of a whole family; he is invited to make the suitable generalizations of the given problem statement. By successively adding more detail in the lower levels he eventually pins his program down to a solution for the given problem.
My only beef against Dijkstra is that I applied for a fairly crappy job I was eminently qualified for in terms of experience and someone told me to code Dijkstra's shunting yard algorithm on a whiteboard (well not in so many words, but that was the solution). It's a good algorithm but way beyond the scope of what you should ask in a whiteboard interview. I didn't get the job.
I get the sense that Dijkstra would've agreed with you and perhaps had harsh words for that interview process.
Sometimes these interview stories sound like selecting a professor of mathematics by picking the one who can calculate the square-root-of-2 to 12 digits in their head the fastest.
When I watched it I was both studying Computer Science and learning Dutch, so it was twice as interesting. The version I linked provides English subtitles.
This is a really nice article on Dijkstra, both more detailed about his contributions and more balanced about his limitations — many articles about him are too hagiographic to my taste.
The older I get the harder it is to time-slot things, but I can think of a few things where much of the interesting work happened in the last ten years (similar to how a lot of pivotal work on GC algorithms happened in the late 90's).
Most of the good work on escape analysis started around ~2010
Rust got us rolling on borrow semantics (I have a feeling the '20s will be remembered as the the golden age)
I'm sure there's a thing or two in or around LLVM that would rank, but I'm not paying close enough attention.
Would you say there are real CS advances when it comes to LZ family compression algorithms and containers? Wasn't LZ well known prior to the past 10 years? And is there any kind of fundamental or theoretical advancement in containers, or is this an example of a new(er) type of implementation?
Zip was an ahead-of-time compression algorithm until HTTP 1.1, and so the draw was storage and transmission bandwidth, but the deciding factor was decompression time and space complexity.
Now we've been using it for online compression so long, and bandwidth is a secondary concern. Eventually someone had to take the other constraints seriously. We made LZO and friends but the results weren't that exciting, and I think a lot of people wandered off for another 10 years to work on other things, until bandwidth became a bigger concern for producers than consumers.
For containers, I'd love to talk to some mainframe OS designers about how much of containers and The Cloud are merely democratizing techniques that were proven out on big iron 30 years ago. I suspect the answer is "a lot".
> similar to how a lot of pivotal work on GC algorithms happened in the late 90's
Speaking of which, there's been great progress in low-pause garbage collection over the last few years, although it could be said that Azul was doing it a while back.
Some would say the GC advances in the 90's were a renaissance, but I think I'd agree we are in the middle or tail end of a second one.
Many of those 90's GC algorithms complained of a lack of a cheap instruction for write barriers, and some were specifically about amortizing write barriers by using coarser grained ones. Azul's pivot to software only solutions came on the shoulders of Intel's VT instruction set, which allows, among other things, for nesting of virtual memory. The Azul JVM essentially behaves as a VM.
[ETA] and some of the other GCs now leverage the vast open space of 64 bit addressing to alias memory addresses to give references 2 or 3 flavors, and use that to coordinate parallel GC activities.
Has to be GAN and related ML developments. They're opening up problem spaces where progress had been largely stalled for decades. I don't think they'll be the ultimate solution in this problem space, but I do think they're an important stepping stone.
The crown has to go to machine learning and neural network advancements. This builds on the increase in data and processing capacity, but it's still an amazing advancement over a mere 10 years. One may argue that the actual CS has been around for longer but I don't think that's giving enough credit to recent advancements.
To me -- a casual novice -- it sounds like a lot of recent CS work results in things like CAP Theorem/consensus, NLP/AI models, AGI, practical tools for verification/formal methods.
I don't think we've made much progress towards AGI, but having reliable approaches to object recognition in images is fairly new, as is putting enough of that sort of thing together to make a self driving car.
Real-time ray tracing is finally here, in large part because of much better denoising technology. Similarly many types of stimulation are becoming vastly cheaper and more capable thanks to the use of machine learning. Image synthesis made huge leaps thanks to the invention of GANs in 2013.
As an aside, I took a History of Logic course from Krzysztof Apt (https://inference-review.com/author/krzysztof-apt/) while I was an undergrad and he was briefly at UT Austin. He is an excellent teacher and a very nice man.
(He loaned me a copy of a book on Frege's logic during the course---it had been signed and given to him by the person who let him stay on their floor when he first came to the US.)
Why not? The LotR was published in 1954, and won't enter the public domain for another 25 years or so... Copyright is a wonderful thing like that, surviving the death of the creator by another human lifetime.
I have wondered what Dijkstra would have said about that most (from my limited view) verification advances nowadays focus on functional programming (dependant types and so forth). I get the feeling he wasn't too fond of functional programming.
Or maybe he even was able to comment on it, I am not sure how far the field had moved while he was still with us. I have searched for it but could find any comment from him on the subject.
Alan Kay on Dijkstra, (1997 OOPSLA keynote): 'I don't know how many of you have ever met Dijkstra, but you probably know that arrogance in computer science is measured in nano-Dijkstras.'
Backus literally inspired functional programming with his Turing acceptance and Dijkstra attacked him for it. Dijkstra attacked the paper that inspired Haskell and everything else that currently exists in FP. He tried to destroy it. He should be a footnote in history.
Functional programming already existed in a few forms by the 1977 Turing Award lecture. ML was around since 1973, which defined the ML family (Ocaml, SML, F#) and influenced Haskell and others. The Lisp family of languages had been around since 1958. Some parts of the lecture can be seen as related to languages in the APL family (originated in 1965). These developments influenced the lecture itself.
To gain context into Dijkstra's response, it may be worth reading it [0]. Here's the conclusion of his response:
> In short, the article is a progress report on a valid research effort but suffers badly from aggressive overselling of its significance, long before convincing results have been reached. This is the more regrettable as it has been published by way of Turing Award Lecture.
Regarding "He tried to destroy it." Dijkstra is known, and often criticized by others, for his hyperbole. Perhaps instead of imitating this heavily criticized aspect of his, you could tone down your rhetoric and actually create an argument rather than try to dismiss someone (and all their work) for one thing you disagree with.
I will agree, Backus' ideas have panned out in many ways. Not having read his lecture in quite a while I can't comment on whether or not, in 1977, he was overselling the idea at the time, especially as I'm not familiar with the state of the art in research at the time (having been born 5 years later, and CS concepts not being taught in chronological order).
Regardless, your original comment made two absurd claims:
1. Dijkstra attacked the paper that inspired Haskell and everything else that currently exists in FP. He tried to destroy it. [emphasis added]
Which is what my quote of Dijkstra's actual statements was meant to rebut. He did not try to destroy it. He criticized it, and some of his criticism may have been wrong then, and I'd say is wrong now (with greater understanding of the ideas Backus was presenting), but he did not try to destroy it.
2. He should be a footnote in history.
Another absurd position. Because of one response (and if you wanted to you can probably find a number of others) exaggerated beyond reason ("He tried to destroy it."), you want to dismiss some 50 years of work.
His hopes for functional programming machines seems like overselling his dream of abandoning von Neumann atleast. Arcane Lisp-machines was actually made as a comparison. I don't get the feeling Backus meant that a "FP system" should be an abstraction ontop of a von Neumann machine/language.
I wouldn’t say he tried to destroy functional programming. If you read his response he pretty clearly says that he just thinks that FP as a solution to all problems is “overselling” the solution.
And I 100% agree. Thinking that functional programming solves all problems is a fundamental misunderstanding of computation.
The first thing that opened my eyes to the overselling of FP as a panacea was reading Leslie Lamport’s work, specifically Computation and State Machines: https://lamport.azurewebsites.net/pubs/state-machine.pdf. Specifically, in Section 3: Programs as State Machines, he demonstrates how the same algorithm for computing factorials can be implemented via mutation or recursion.
With TLA+, Lamport also showed that mutation and state can be reasoned about mathematically, contrary to the central claim of functional programming purists.
The point is simple: functional programming doesn’t in any way _inherently_ help with correctly implementing programs. The fact that FP is currently in vogue is simply another example of how humans don’t require any evidence of anything at all before following a belief system blindly.
FP does prevent certain classes of mistakes from happening, i.e. unintentional bugs due to mutation creating implicit state machines. But preventing bugs and aiding in correctness aren’t exactly the same thing.
Lamport is a giant and one of the greatest living computing scientists. He's also getting more and more Dijkstra-like. I say that with full admiration.
By "attacked" you probably meant "criticised"? Criticising something is not only a perfectly normal activity, it's a necessary one and is an important part of the scientific method.
> Dijkstra attacked the paper that inspired Haskell..
While Dijkstra's criticism probably does deserve to be called an "attack", the resulting exchange between him and Backus was highly thought-provoking and entertaining.
I have multiple CS and CE degrees, and learned his proofs, but industry is pretty antithetical to his approach and most CS pretty irrelevant. I am not sure he has that much real influence.
Not that I don't wish it were otherwise. I love the beauty of mathematics and do wish software were more elegant.
I genuinely wonder what gave you this impression. Dijkstra made seminal contributions to at least three subfields of computer science: algorithms (his optimal shortest path algorithm), programming languages (ALGOL -with others, but still- and his "goto considered harmful" paper), and concurrency theory (semaphores), just to state the most well-known ones...
I think he is actually underrated. I'd have liked to be introduced to his proof notations during some formal courses on my CS formation, which was never mentioned.
Think of Dijkstra as Sherlock Holmes thought of himself; viz.
My dear Watson,” said he, “I cannot agree with those who rank modesty among the virtues. To the logician all things should be seen exactly as they are, and to underestimate one’s self is as much a departure from truth as to exaggerate one’s own powers.
I Northern European/Germanic trait in general. As a Norwegian living in the Netherlands I found Dutch people very easy to relate to but I know many of my other fellow foreigner had major problems with their direct communication.
But you see the same with Linus Thorvalds. His tone offends a lot of people in particular Americans.
But as a fellow Nordic I think the passive aggressiveness often observed in America or fake politeness more difficult to deal with.
Of course Dijkstra and Linus are quite different personalities but both suffer from an English speaking majority thinking their concepts of proper etiquette is universal.
do you know of any media that has good depictions of this kind of culture? Ideally as part of the show, rather than a one-off foreigner in an American show. As an American this is how I sometimes wish our culture was like, but at the same time I realize I can't even imagine the reality of it since our culture can be rather extremely towards the opposite end of the spectrum
Thing is any local media wont display it "in your face" like an America show would do it, it is just part of the environment. Paraphrasing Borges, "How do you identify an actual desert people literary work? it's the one which does not mention camels"
This reminds me one thing I find irritating about SF in general and SF movies in particular. They hardly portrait technology use in an organic way. Do you want to see a great SF movie? Watch a current normal movie with 1990s eyes. People will text, call her friends, use Uber, buy on Amazon but nothing self conscious " See? See how cool is what I am doing!?"
That sounds like just what I'd be interested in watching. Any suggestions?
That's a good example. I often do the reverse: watching 90s or older movies with modern eyes. It can be incredibly refreshing to watch older movies that have a slower and more relatable vibe.
Regretfully I dont know any Dutch tv show. Your best bet are Nordic detective shows, they seem to produce a lot for some reason. Even Broadchurch, which is British, is good at portraying that kind of "I wont bite my tongue" person.
Interesting, reminds me of the German "Tatort" which has been running for millennia. I'll definitely check out Broadchurch and see if I can find something for Nordic shows too. Thanks!
Years later, in grad school, my research was on program verification. Dijkstra was a big influence on the field. I attended a lecture at UT Austin that he gave before moving to the US.
Dijkstra's approach to proving the correctness of programs is hard to apply in practice. Like a geometry proof, there are ways in which a proof of correctness can have mistakes that aren't obvious. Here's an example, prove that a sorting algorithm works. If the specification is that the output must be in sorted order, a proven program can still fail to sort correctly. The specification has an error, the output must not only be in sorted order, it must ensure that all of the input elements make it somewhere to the output. But this isn't good enough. A sort proven to meet this specification might leave out some duplicate values. Requiring that the output be the same length as the input still isn't good enough, multiple copies of one element might hide missing duplicate input values for another element. The specification requires that the output be a sorted permutation of the input.
Sorting is a well understood problem, but real verification must deal with the strange mathematics implemented by computers. The mathematical theories that we are accustomed to from school assume infinite precision and no overflow, real life hardware doesn't act this way.
All of this makes program verification hard, and my hope is that AI programming assistants will someday aid in the construction of meaningful specifications and work with the programmer to verify the correctness of programs or determine their safe operating boundaries. Progress has been slow, and the tools are still impractical for use by most programmers on most programs.