How recursion got into programming: a comedy of errors
vanemden.wordpress.com
vanemden.wordpress.com
For instance, on a PDP-8 (released some years after ALGOL) the calling convention was that the return address was written to the word of memory before the called function. This was simple, but pretty much precludes recursive calls.
These days we take for granted that the CPU will provide some sort of stack pointer that gets automatically managed by a CALL/RET instruction pair. Before that was provided in hardware, the compiler would have to do that itself. So if you decided to support recursion, you'd end up requiring a stack and adding a small cost to every function call.
Once you decide to have a stack, allowing recursion is a freebee so of course you'd include it.
It does, actually:
> And this is what they wanted to remove because they wanted static allocation of procedure activation records.
A stack frame is a dynamically allocated procedure activation record, but we no longer call them that because it's seen as absurd that they would be statically allocated.
It's true that it's not possible to make a Turing-complete language for which it's possible to statically determine the amount of memory arbitrary programs on arbitrary inputs will use. But typically a language has other means of supporting dynamic memory allocation than simply via frame allocation for functions; e.g., via built-in operations to manipulate lists of arbitrary length.
So, if you wanted to only allow recursion via tail-calls, you easily could, and if you wanted to furthermore go ahead and prevent all dynamic memory allocation, you could as well, but you would necessarily be giving up Turing-completeness.
To be fair, we're talking about a language designed in 1959, where a compiler had to run in 4KB of memory or so. At that point you're barely optimizing anything, just doing the simplest transformation you can.
Doing tail-call elimination isn't quite as simple as just doing a "JMP" instead of a "CALL" since you also need to replace the currently in-use activation record. Consider the C fragment:
int f(int a, int b)
{
if (a > b)
return f(b, a);
// ...
}
These problems certainly aren't insurmountable, but if it takes a few hundred instructions you've already blown a lot of your budget on one little feature. You could see why a language designer in 1959 would want to leave it out.
Even in a classic Turing machine I interpret the tape as a single pre-allocated array (of infinite size).
When talking about Turing-complete programming languages, a relaxed definition with finite-size memory is assumed, and to me it seems that it's just hair splitting whether program hits that limit via malloc() call or by advancing a pointer in an internal fixed-size array. Dynamic memory allocation is just a name for a bunch of bookkeeping done on a fixed-size memory.
In practice asm.js programs are not allowed to dynamically allocate any memory from the browser: a fixed-size array is created before the asm.js program starts. From the point of the VM programs are just shuffling bytes within a fixed-size array, and yet, we can run "Turing-complete" programs in asm.js.
"dynamic memory allocation" may not have been the right term to use to denote moving beyond finite state machines, for an audience which wants to consider a Turing machine as having statically allocated infinite memory. But it makes sense if you think of a Turing machine's memory as only storing enough data for the portion of the tape which has already been accessed, and allocating new memory as new tape regions are needed.
It's true that the actual machine sitting on your desk only has a fixed finite memory. In that sense, without a peripheral unbounded store, it's not properly Turing complete.
It's also true that we often find it convenient to analyze it as Turing complete anyway, but this abstraction basically goes hand-in-hand with abstracting away its memory limitations. I don't see any point in pretending you can be Turing complete using only programs with a statically given memory bound (which amounts to a logarithmic bound on the number of states in a corresponding finite state machine); if we're going to pretend, let's pretend the memory is effectively infinite as well.
>>we often find it convenient to analyze it as Turing complete anyway
It's convenient, because the proofs will still be true even if memory sizes grow by 500x. Turing machines clearly don't have a real, material existence, similarly to real numbers (assuming that all actual numbers are finite). Real numbers can be considered as modeling integers that are arbitrarily large.
Not really; most risc architectures still manage the stack via the compiler rather than instruction. About the closest you get is a jump-and-store-link-register instruction.
Little Schemer is without a doubt one of the best books I have ever read on the subject of recursion, and what is interesting because they never really go into a formal definition of what recursion is, as most texts on computer science try to. Instead they show the reader time and time again what recursion is, while providing a great series of rules (commandments) on how to get the most out of recursion, particually in a tail-recursive language like Scheme. http://www.amazon.com/The-Little-Schemer-4th-Edition/product...
You can read more about The Little Lisper here: http://thelittlelisper.blogspot.com.au/2010/06/little-lisper...
Or you can read about working through it in Clojure here: http://juliangamble.com/blog/2012/07/20/the-little-schemer-i...
Now, go cons a cake onto your mouth!
Also Friedman and Byrd did show up to a few clojure talks and seemed, from the online videos, to be highly entertaining - I remember their using miniKanren to automatically generate scheme programs that evaluated to 6 being particularly fun.
The machine I learned assembler on would rewrite the instruction at the start of a function with a jump instruction to return to the caller. You returned from the function by jumping back to its beginning. Recursion wasn't an option!
http://www.computermuseum.li/Testpage/IBM-1401.htm
"It came with 4,096 characters of memory [6-bit (plus 1 parity bit] CORE memory, constructed from little donut shaped metal rings strung on a wire mesh."
The core memory is explained in the same book which deanmen linked (thanks deanmen!)
There are strategies to prove various things about recursive calls. See Ada/Spark's explanation for Rule 17.2 in [1].
I'm not familiar with Coq and Agda, but I believe they allow recursive calls if they can prove termination, though "termination" may be different than "using too much stack".
[1] http://www.spark-2014.org/entries/detail/misra-c-2012-vs-spa...
You can annotate the program in ways to make the compiler see that a parameter is actually getting smaller.
If the algorithm is tail-recursive, this will use constant stack space and memory, just like tail-call optimisation. If the algorithm's not tail-recursive, it will use constant stack space but large (potentially exponential) amounts of memory.
There's no way around this. The only solution is to come up with a different algorithm (eg. using an accumulator).
However, we are talking about the automotive and aerospace industry so recursion overhead is often a deal breaker even if there are no other issues.
This isn't true at all. You can replace all recursion with loops, sure, but you're going to have to simulate a stack (i.e. use extra memory) to convert complex recursive functions to loops.
Then can one argue that loops vs. recursion is mostly a matter of style and loops just as good as recursion since the compiler will optimize them that way anyway ?
Recursive constructs are can be not tail recursive (and usually are with new starter developers) and many languages ignore it anyway (meaning even code that can be unpacked from function calls into a loop are not so the stack is still used).
Because humans also screw recursion all the time.
;;; power set = power {set-X} as sub (+.) {X U sub}
(define (power set)
(if (null? set)
'(())
(let ((sub (power (cdr set)))
(augment (lambda (subset) (cons (car set) subset))))
(append (map augment sub) sub))))
Recursion had no place in mainstream programming at the time, nor did lambda calculus. Only two years before, I had sat in a coffee-room discussion of what it would mean for a subroutine to call itself. Questions raised but unanswered were whether recursive instances deserved to be deemed the "same" subroutine, and, if you could do it, what good would it be? It turned out you could do it: I programmed it for the IBM 704. Given the challenge, the now standard stack solution arose inexorably. But the question of what it was good for remained.
In the course of the lecture John introduced the usual basic list functions like copy, append and reverse (quadratic and linear), as well as tree manipulation. He went on to higher-level functions, demonstrating maplis and lambda. By the end of the hour he had put together a powerful little toolkit of functions which he used in his finale: symbolic differentiation of univariate expressions.
There it was—functional programming ex nihilo. McCarthy acknowledged IPL V and recursive function theory, but the elegant and practical face he put upon these antecedents was a work of genius. Nobody would ever again wonder what good it was to allow functions to call themselves. And it was all so clear one could go home and build it oneself without any instruction book. - Doug McIlroy
ps: there's a post on Recursion in early languages https://news.ycombinator.com/item?id=8073361 that mentions McCarthy indirect influence on the ALGOL comitee, but nothing else.
In time, this lead to an appreciation of recursion in terms of dynamic programming and code clarity. But I still believe that the best way to teach recursion is through appealing to students' lazy tendencies.
> Ritchie relaxed the definition-before-use rule by allowing
> redundant declarations of procedure headings. At the
> expense of a redundant advance declaration the programmer
> can define mutually recursive procedures in C.
I imagine John McCarthy and the others who wanted recursion just sitting back and smiling, recognizing that that there was no need to press - it was just a matter of time.
When people talk of "Tail Call Optimization" (TCO) they are talking about a way to recurse without leaving things on the stack (tail-call meaning that the recuse call is the last thing in the function so the state of the function doesn't need pushed on the stack, it can be discarded.
Coincidentally, I had a stack overflow while working on some trees a few months ago, it ate all my ram within about 2 seconds. Although my stack was sizeable, my program was blind and unaware of the stack limit.
So, thanks to that, we can define map the clear and easy way:
(define (map f l)
(if (pair? l)
(cons (f (car l))
(map f (cdr l)))
'()))
(define (map f l)
(let lp ((l l) (out '()))
(if (pair? l)
(lp (cdr l) (cons (f (car l)) out))
(reverse out))))
That said, it is a nice way to reduce the chance or delay the occurrence of hitting the stack limit (whether it's on the heap or an explicit stack that's still what's happening).
Is TCO used in C++? I've only ever seen it mentioned in reference to Scheme and Haskell. It's a compiler optimization, so it would be transparent to the programmer, right?
That is an implementation detail. It doesn't matter if it is does at compiler or whatever runtime is targeted.
This is called lowering in compiler design speak.
Closures? Can't be optimized. Polymorphic method? Can't be optimized (even if every implementation is tail recursive).
This is more than an implementation detail, it actively influences the way you write your code.
And Scala -doesn't- optimize A calls B calls A etc cases. It requires the developer to explicitly make use of scala.util.control.TailCalls. See http://www.scala-lang.org/api/2.11.2/index.html#scala.util.c... and associated white paper.
What Scala gives you is that if A calls A (calls A calls A), and is tail recursive, and A can not be overridden, it will optimize it.
[0] "The Joy of Clojure," Fogus and Houser
As far as I know, F# is the only reasonably popular .NET language to emit the tail. prefix, though[3].
[1] http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-j...
[2] http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11...
[3] http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-c...
There are much more compilers out there than those three.
Example: https://github.com/skriticos/tac_workflow/blob/9890e66d60851...
Something like:
int recurse(int foo) {
int bar;
printf("%d\n", foo);
bar = recurse(foo + 1);
printf("%d\n", bar); //this is just to avoid bar being optimized away
return bar;
}
It is big, yes, but, in writing robust code, you have to anticipate and handle a stack overflow cleanly. How do you do this?
In principle, you have that problem with almost any language that uses the system stack to pass arguments when it makes a function call. It just happens to be easier to trigger it if you use a recursive algorithm, because it’s unlikely that you would write a program with 200,000 distinct functions each of which just called the next in a chain until something fell over.
In practice, recursive algorithms are often used to walk recursive data structures and often have logarithmic complexity in the size of the data structure. Even structures that fill the memory of a supercomputer probably aren’t going to need more than a few hundred levels of recursion in that scenario, while the available stack space is probably several orders of magnitude larger. So to be blunt, unless you really are talking about something where failure really isn’t an option (safety critical systems and the like), you probably just treat this as the same kind of catastrophic failure that running out of system memory would be, and use some OS-level support to abort as gracefully as you can if the sky falls.
If you really are working in a more constrained environment — safety-critical code, say, or perhaps an embedded system with relatively little memory — then it might be the case that you simply avoid the recursion altogether unless you’re using a language that guarantees tail recursion will be dealt with robustly. Some coding standards forbid the use of dynamically allocated memory for much the same reason, and you just have to use different tools to solve those problems if you’re working with such constraints.
You use sigaltstack and catch SIGSEGV.
It's probably easier to handle if you hit a soft limit rather than the heap. Then you raise the limit, set a flag to make your functions unwind and reduce the limit again.
In the JVM and the .NET VM, you can't handle it cleanly.
On Linux (and probably on other OSs) it's not easy to detect that the system is out heap memory because of lazy memory allocation policies.
Physical memory is not allocated when you call malloc() but when you first read or write the corresponding memory page.
Because of this, malloc() does not necessarily return NULL even if there isn't enough memory available on the system at the time you called malloc(). But if the system is still out of memory when your first access the allocated memory, your program will crash with a segfault.
So in absence of extra precaution, using heap memory isn't any safer than using stack memory.
A better fix is to add a work queue or stack.
Stack limits may or may not be a concern, depending on the application. In the case of directories, if you've got them nested 10k+ deep you've got other problems.
My understanding was that without recursion the lambda calculus is not Turing-complete. Is that correct?
It should also be noted that recursion is a close relative of induction, an indispensable tool that is not without its own problematic history.