10 ms·
How recursion got into Algol 60: a comedy of errors
- mjevans 11y agoI am quite thankful to those who did the right thing. However at the same time, this same process is used for evil quite often; as the US Congress clearly provides many examples.
- jessaustin 11y agoCommittee member F.L. Bauer registered his protest by characterizing the addition of recursion to the language as an "Amsterdam plot". Is "Amsterdam plot" an idiom, or simply a colorful expression that occurred to Bauer? I haven't seen this expression before, but TFA repeats it several times in stylized fashion so I thought maybe I was missing the intended meaning?
- bunderbunder 11y agoI'm guessing it's a reference to two of the conspirators (Dijkstra and van Wijngaarden) being Dutch.
- c3534l 11y agoThat doesn't answer whether or not "Amersterdam plot" was an existing idiom. I've never heard of it personally.
- bunderbunder 11y agoAh, gotcha. No, the use of a direct quotation implies that it's not a common idiom - if it were then that wouldn't be necessary.
- ilaksh 11y agoBut Lisp already had recursion, right? It was just Algol and the international standard that was held up. Similar to the situation with things like CoffeeScript vs. ES6 etc. What I think we need is a standard so flexible and meta that systems can evolve without waiting for society or standards to catch up. Which we have in Turing-complete languages. But we should standardize somehow on a very meta level.
- pekk 11y agoLots of things from Lisp never made it into mainstream programming (meaning things like Fortran, C, Java).
- davexunit 11y ago>What I think we need is a standard so flexible and meta that systems can evolve without waiting for society or standards to catch up. This is why we must demand macro systems in the languages we use. Building new languages is part of the programming process. Everyone should be able to do it, not just standards committees.
- Gibbon1 11y agoWinging off a comment above, I find recursion generally intuitive, occasionally useful, and really really boring. Offhand years ago I used a dialect of C that had no recursion so I can see both sides of this argument. On the one hand, there is a pain point when you don't have access to recursion. On the other, boy can a compiler that eschews recursion produce small and fast code. (Because without recursion the call graph is acyclic)
- anindyabd 11y agoI wouldn't call recursion boring. Quicksort in Haskell is probably my favorite two lines of code: quicksort [] = [] quicksort (x:rest) = quicksort [y | y <- rest, y <= x] ++ [x] ++ quicksort [y | y <- rest, y > x]
- nemesisrobot 11y agoIt's been discussed before, but that's not really quicksort though (since it's not in-place)[0] 0: http://stackoverflow.com/q/7717691/1235548 http://stackoverflow.com/q/7717691/1235548
- emmelaich 11y agoDo we know that for sure? I mean - could a sufficiently smart compiler actually create machine code which _did_ do it in-place?
- dragonwriter 11y agoShouldn't this be "how recursion got into Algol 60"? After all, part of the background is that McCarthy wanted it in Algol, coming off his success with Lisp, that had, in its earliest form, only recursion and no iteration. So recursion had already "got into programming" when this story of "How recursion got into programming" kicks off.
- mordocai 11y agoDid the post get updated after you left this comment? The post I read talks about lisp.
- dragonwriter 11y agoI was referring to the title, which suggests that it is the story of how recursion got into programming. But recursion being in Lisp is, in the story, part of the background -- its the story of how recursion got included in Algol 60, not how it got included in programming. That it was already included in programming -- in Lisp -- is part of the background and starting point of the story, and how that happened isn't part of the story.
- anindyabd 11y agoYeah, exactly what I was thinking when I was reading the piece.
- sytelus 11y agoOne can argue that many features of programming languages have existed in theory since days of Euclid and Archimedes. This article argues that ALGOL was the first attempt to "standardized" features of a programming language that was expected to be in wide spread usage. It was designed by committee of big name experts and the "comedy" part is that lot of these people considered recursion as unnecessary or even harmful. No one knows what would have happened if ALGOL indeed didn't supported recursion, became widespread and was considered as gold standard. How many years before someone would have broken the barrier and said experts were wrong and recursion is one of the most important part of language?
- dvt 11y agoAh recursion, my old nemesis. We meet again. Very interesting and informative article, but I'm with the SUBSET people on this one: > Do not write recursive procedures. Do not use procedures recursively. I've probably failed 90% of recursion "gotcha'" questions I've had during interviews. It's my uninformed opinion that recursion is uninteresting and unintuitive. This is why whenever I encounter it, I either ignore it or refactor it. I'm exaggerating, of course, but I really do hate it. There are some very interesting theoretical applications, however. The article briefly mentions Lambda Calculus (which I love) where I've always enjoyed playing with the divergent Omega combinator[1]: Ω = (λx. x x) (λx. x x) I'm may be entirely too stupid to appreciate the beautiful intricacies of recursive programming, but I do think that recursive programming can be susceptible to some unique bugs, such as exceeding stack/heap, that are very difficult to notice prima facia (more difficult than when the same is done via procedural code, at least). [1] http://www.seas.upenn.edu/~cis500/cis500-f06/lectures/0925-2x3.pdf http://www.seas.upenn.edu/~cis500/cis500-f06/lectures/0925-2...
- rblatz 11y agoI'm fairly sure Dijkstra didn't say that, since he was advocating for recursion to be added. It was one of the splinter Algol groups that added that sentence trying to remove it.
- baddox 11y agoI find recursion extremely intuitive, if not necessary, for pretty much any data structure with a bunch of things ("nodes") pointing to other things. That includes, most notably, linked lists and trees. I can probably work up recursive pseudocode for tree traversals pretty easily, despite not having studied computer science or doing it at work for several years, yet I find an iterative solution somewhat elusive and unnatural.
- joeblau 11y ago> In the late 1950s a committee was formed to design a universal, machine-independent programming language. I swear we still have not learned from our mistakes; Although now its platform-independent with the platforms being mobile, desktop, and web.
- pyre 11y agoWell, the machines got complex enough that we created operating systems to abstract them, and they became their own little sandboxes.
- bunderbunder 11y agoI'm not sure the dream was such a mistake. We now have that language, though it may not be quite what Algol's designers were hoping for. It's C.
- kazinator 11y ago> In fact, the first Lisp had no iteration, so that the only way to add all elements of a linear list was to write a recursively defined function. So that would be how recursion "got into programming". The comedy of errors is how recursion got into Algol, not into programming.
- rootedbox 11y agohttps://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664
- spdionis 11y agoI don't understand what's weird and special about recursion other than the ways it can be used to easily solve some problems. I would find it very unintuitive that in a language I couldn't write a function that calls itself. That feels like an obvious thing (if we ignore all the implementation details). When I first started programming I used recursion without knowing that it's called like that and I didn't expect it to be called in any special way at all.
- bunderbunder 11y agoOne big practical complaint is that recursion makes it difficult to reason about the run-time characteristics of code. There's some truth to this - I'm personally no stranger to refactoring recursive functions that have proven susceptible to stack overflows into iterative implementations. I think even the most die-hard functional programming fans among us secretly know that this is a problem. It's why virtually every functional language implements tail call optimization, and why one of the earliest things that's taught to new students of functional programming is how to ensure that functions use tail recursion whenever possible. Sometimes we even go through some pretty impressive contortions because of this. Consider the case of continuation passing style. The other is that a lot of people find recursion hard to understand. Others seem to naturally think in terms of recursion and think iteration is a headache. I'm not sure the two camps ever see eye to eye. It might be a brain wiring thing. Though perhaps practice rewires your brain - I wouldn't be surprised if making someone spend a decade writing mostly imperative code causes them to become more comfortable with iteration, and making someone spend a decade writing mostly declarative code causes them to become more comfortable with recursion.
- Swizec 11y ago> I wouldn't be surprised if making someone spend a decade writing mostly imperative code causes them to become more comfortable with iteration, and making someone spend a decade writing mostly declarative code causes them to become more comfortable with recursion. I have spent a decade doing a mix of both. It really really really depends on the problem at hand what's easier to understand Have to traverse a tree? Recursion. Have to make a big thing out of small things? Recursion. Have to add +1 to a bunch of numbers? Loop.
- sytelus 11y agoFunny side story is that Hoare couldn't publish algorithm for QuickSort until he learned ALGOL was ready to do recursion. QuickSort is one of the algorithms that is very difficult to do without having a concept of recursion. Another one is various tree traversals. What are the other algorithms that would be impractical without recursion? PS: Using stack to simulate recursion doesn't count :).
- munificent 11y ago> What are the other algorithms that would be impractical without recursion? Interestingly, writing a compiler. Since expressions nest, it's very hard to write a compiler for them without a recursive function for compiling an expression.
- copperx 11y agoThe implementations of non-recursive Quicksort and tree traversal are not impractical, just a little bit longer. By the way, are recursive versions of sorting algorithms even shipped with standard libraries of popular languages?
- sytelus 11y agoYes, Java as well as .Net implementations used recursive QuickSort (I think Java recently switched to Timsort?). The implementation however used only one recursive call instead of two as in textbooks because second call is tail recursive and can be made iterative. This is however not done just to avoid recursion. With QuickSort you run risk of using up O(n) stack space in worse case. Making second call iterative allows to make sure recursion always occur on smaller partition thus guerenteeing O(lg n) space.
- CJefferson 11y agoCertainly std::sort and friends are recursive in all C++ implementations I've looked at. In C++ it's hard to make the efficient and non-recursive. You can have a fixed-sized buffer (limits depth), or call malloc for a buffer (a single call to malloc can be more expensive than just doing the sort on the stack, and in general the C++ standard library tries hard to avoid mallocing).
- kabdib 11y agoI've encountered knee-jerk negative reactions to recursion from most firmware engineers. Then one day I got one to laugh at this byte-saving routine to do some multiplications: X32: BSR X16 X16: BSR X8 X8: BSR X4 X4: BSR X2 X2: ADD A RET Recursion. In assembly language. We were six bytes shy of filling our code space, but we had gobs of stack, and I got about 60 bytes back from our stupid compiler with this. When my cow-orker saw it, he thought for a moment, smiled, said "You're one sick dude, you know that?" and we checked it in.
- mikeash 11y agoDear god. I don't know if we should give you a Nobel Prize or put you in prison. Probably both.
- kabdib 11y agoPretty much that reaction :-)
- quantumtremor 11y agoELI someone who knows mips?
- pbsd 11y agoBasically equivalent to this C code (assuming BSR = procedure call): int x2(int x) { return x + x; } int x4(int x) { return x2(x) + x2(x); } int x8(int x) { return x4(x) + x4(x); } int x16(int x) { return x8(x) + x8(x); } int x32(int x) { return x16(x) + x16(x); }
- bbcbasic 11y agoHmm. How is this recursion? Maybe I don't understand what the word recursion means, but I thought that you'd have to call yourself directly or indirectly.
- hello0 11y agogreat article
- jrapdx3 11y agoThe article was interesting and entertaining too. Good (and bad) committee outcomes happen as described, when one or a few individuals seize the initiative, setting out their ideas in a more or less finished form. Other committee members may feel blindsided but in the crunch there's insufficient time to produce alternatives. It's a lesson worth our attention. The story evoked a personal element, going back to when I was first learning programming in the 80's. Early on one of the serious hurdles I encountered was recursion. (Another was pointers and indirection.) After struggling to wrap my brain around the thing that kept calling itself, I ran across a book, "Thinking Recursively" by Eric S. Roberts, 1986, which was enormously helpful. I consider the book a classic. And it must be since it's still in print! I'd highly recommend it for anyone who finds recursion unintuitive. Way back then it wasn't intuitive to me either, but with the book as a guide in time it became as natural as breathing air.
- FullyFunctional 11y agoThis is a well known story. I do take issue with the arrogance of the author: "Of course we cannot blame the Bauer faction for not having the experience of later workers in the field." Oh _please_! The reality was the the common machines of the time didn't have todays fancy addressing modes. All memory addresses were global addresses. Thus, the _cost_ of making all memory access relative to a stack pointer was far from trivial. Of course, there was a work-around if you could forgo re-entrance (~ "thread-safety"): use static activation records, but saving it to the stack before the recursive call and restoring after. Still not exactly free.
- FullyFunctional 11y agoOops, that static activation records would probably not work with the Algol 60 parameter semantics so the original point stands: supporting recursion is really expensive on that breed of hardware.