inter-function tail calls working in TXR Lisp.

Where a tree-interpreted even/odd test case blows the stack,
the compiled one runs. Demo below.

It's not exactly a trampoline implementation but something along those lines.
The function which executes a VM function, vm_execute_closure was modified to
contain a loop.

A cross-function tail call is indicated by a prefix instruction called tail.
This goes in front of one of four instructions: call, apply, gcall and gapply.
When vm_execute encounters tail, it returns an indication to the caller,
vm_execute_closure.

vm_execute_closure examines the following instruction and determines which
function is being called, and with how many arguments.

Next, it has to determine whether the arguments will fit into a previously used
argument space. If not, it has to call alloca() to get more stack space for the
arguments. The arguments are exctracted from the call/apply/gcall/gappy
instruction and placed into the argument storage.

The argument storage is then (if necessary) moved into the high address end of
the stack area.

Then the argument and function variable are reassigned, and the loop turns
around to the top of vm_execute_closure, which will process the new function.
If the function's frame size will fit into the existing stack space (minus
argument area at the top), that will be used, otherwise alloca will be called
to allocate the difference required.

The frame is allocated and initialized, and vm_execute called to run the
new function which replaced the previous one.

It resembles chained execution of programs in a bootstrapping sequence,
including the bit about having to relocate something to "himmem"
to get it out of the way for the next program.

$ cat even-odd.tl
(defun even (x)
  (cond
    ((zerop x) t)
    ((minusp x) (even (- x)))
    (t (odd (pred x)))))

(defun odd (x)
  (cond
    ((zerop x) nil)
    ((minusp x) (odd (- x)))
    (t (even (pred x)))))
$ ./txr
This is the TXR Lisp interactive listener of TXR 301.
Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
TXR Labs engaged in gain-of-function experiments as far back as 2009.
1> (load "even-odd.tl")
nil
2> (pprof (even 20000))
** computation exceeded stack limit
** during evaluation at even-odd.tl:5 of form (pred x)
2> (pprof (even 2000))
malloc bytes:             0
gc heap bytes:        96048
total:                96048
milliseconds:             2
t
3> (compile-file "even-odd")
t
4> (pprof (even 20000))
malloc bytes:             0
gc heap bytes:            0
total:                    0
milliseconds:             3
t
5> (pprof (even 200000))
malloc bytes:             0
gc heap bytes:            0
total:                    0
milliseconds:            33
t
6> (pprof (even 2000000))
malloc bytes:             0
gc heap bytes:            0
total:                    0
milliseconds:           336
t
7> (pprof (even 20000000))
malloc bytes:             0
gc heap bytes:            0
total:                    0
milliseconds:          3845
t


--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca