Tail call optimization

[julianhyde]

Implement tail call optimization. This would be a guarantee that functions that end with a function call would not use stack space.

Currently the following expression runs out of stack:

let
  fun resum (m, n) =
    if m = 0 then
      n
    else
      resum (m - 1, n + 1)
in
  resum (1000, 0)
end;

If you change 1000 to 500 it succeeds. With this feature, it would succeed for any positive int value.

The algorithm to solve the N queens problem (#148) only works for N <= 7 (which is rather unfortunate, considering that a chess board has N = 8). Solving this would require tail call optimization when the last expression in the function is a call to a continuation function value.

[abhillman]

Do you have any tentative thoughts on how to approach? e.g. one thought is that during the compile phase, could tag RecValDecls as being tail calls and use that property in the interpreter.

[julianhyde]

I don't have many thoughts on this.

Your approach sounds promising. I was hoping to avoid widespread changes to the intermediate form (especially ones that might be broken by other rewrites) if possible, but it might be necessary.

An evaluation strategy might be a trampoline (an interpreter instruction that returns either a value or a new environment and a new instruction). Or change the entire interpreter mode of operation so that each operation is called with a stack state and returns having created a new stack state (rather than taking an environment and returning a value as at present). How to choose between those? It will depend on what fraction of instructions need to be executed in a mode where they replace themselves on the stack, and I don't know whether that fraction is 10% or 90%.

Note that we already have two evaluation strategies: interface Applicable vs interface Code. If it simplifies things, we could consider getting rid of one or both of those.

[julianhyde]

I've started work in https://github.com/julianhyde/morel/tree/151-tail-call. The idea is to use a stack of values. A new method Code.eval(Stack) reads values off of the stack, replacing Code.eval(EvalEnv) which reads values from an environment (usually a map). If there are parameters, you need to push them onto the stack first.