7 ms·
How Recursion Got into Programming (2014)
- chadlavi 6y agoit did it by getting into programming
- gumby 6y agoIt was hard for a moment to get my head around the idea of static activation records. That makes “procedure call” simply into a goto. I guess I tend to write assembly code this way though. Ironic that almost 20 years later the idea of dynamic activation had been so well absorbed that it was possible to write an influential paper all about how procedure call (and lambda) could be considered a goto (via tail recursion)!
- Stratoscope 6y agoYes, imagine that a function looks like this in memory: +-----------------+ | return address | +-----------------+ | executable code | +-----------------+ The way you call a function is to store your desired return address in the first slot, and jump to the code in the second slot. The function jumps to the saved return address when it's done. We did it this way for years. Now given that mindset, how could you even contemplate recursion? Where would you put all the return addresses?
- mark-r 6y agoThat's the way the Control Data Cybers worked, except that it wasn't just a return address - it was a complete jump instruction. You needed to start your function with a no-op of the correct length, and it was overwritten by the caller. Then to return from your function you simply jumped back to the beginning.
- zozbot234 6y agoNice. Basically, the caller uses self-modifying code to set up the correct continuation ("self-modifying code" and "continuation" being somewhat closely-related concepts, after all), and then has the callee jump to it. Makes a lot of sense.
- Sniffnoy 6y agoWhat's a little confusing here is that they talk about "static allocation" vs "dynamic allocation"; but these days, use of the stack is referred to as static allocation! Even if it's not as fully static as the old way. The shift in terminology makes the old debate opaque for the modern reader, and without your comment (and some similar ones) I wouldn't have known what was going on.
- gumby 6y agoI have never seen that usage — in what community is it common? Thanks!
- dang 6y agoDiscussed at the time: https://news.ycombinator.com/item?id=8073361 https://news.ycombinator.com/item?id=8073361 also 2015: https://news.ycombinator.com/item?id=10131664 https://news.ycombinator.com/item?id=10131664
- woliveirajr 6y agoThere's some discussion here: https://news.ycombinator.com/item?id=23061881 https://news.ycombinator.com/item?id=23061881
- bArray 6y agoHow Recursion Got into Programming (2014) https://vanemden.wordpress.com/2014/06/18/how-recursion-got-into-programming-a-comedy-of-errors-3/ https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
- ookdatnog 6y agoI took a History of CS course in college, where this controversy was discussed. The way I understood it, the two camps approached the question of what ALGOL should be slightly differently. One camp (against recursion) was trying to design a language that would be productive for programming in the (then) here and now, with the machines they had at the time; in other words, the language is molded after the machine. Since efficiently implementing recursion wasn't well understood at the time, adding it to the language was a no-go for them. The Dijkstra side of the argument was that the language should be designed to be as elegant as possible, without much concern for the limitations of the machines of the day. The idea was that, once a broadly accepted programming language was designed, computer designs would follow to support it. I think both are valid viewpoints (especially in context), although with perfect hindsight Dijkstra et al seem to have been the more prescient side.
- mtreis86 6y agoTuring's paper in 1939 describes a machine whose operation is recursive.
- tuyiown 6y agoWell, the infinite memory tape was quite a concern for actual programming
- bregma 6y agoVery poorly worded title, but I guess it's more click-baity than "A History of the Personal Politics Involved with the Promotion of Alternative High-level Computer Programming Language Designs Among European and American Academics in the 1950s and 1960s". Maybe a little too dry?
- _bxg1 6y agoIt's strange to me that recursion wouldn't just naturally fall out of any language design that has a call stack. Even if you forbid the current procedure from calling itself, it could achieve the same thing by having two functions call each other.
- ken 6y agoAs the other comments here said, languages at the time did not generally have call stacks. It'd probably be more accurate to say that languages like Algol got call stacks because they were needed in order to implement recursion.
- gowld 6y agoIt's more accurate to say that recursion got into recursion.