From Newsgroup: comp.lang.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.

(load "even-odd.tl")

nil

(pprof (even 20000))

** computation exceeded stack limit
** during evaluation at even-odd.tl:5 of form (pred x)

(pprof (even 2000))

malloc bytes: 0
gc heap bytes: 96048
total: 96048
milliseconds: 2
t

(compile-file "even-odd")

t

(pprof (even 20000))

malloc bytes: 0
gc heap bytes: 0
total: 0
milliseconds: 3
t

(pprof (even 200000))

malloc bytes: 0
gc heap bytes: 0
total: 0
milliseconds: 33
t

(pprof (even 2000000))

malloc bytes: 0
gc heap bytes: 0
total: 0
milliseconds: 336
t

(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
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.lang.lisp

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

Hmm... the fact that it still blows up the stack when interpreted means
that code isn't free to use tail-recursion instead of "plain old
iteration", tho.

Don't get me wrong, I like TCO, but it's better when it's not just an optimization but is part of the semantic of the language so code can
actually *rely* on it.

In ELisp we don't have TCO pretty much anywhere EfOU, except for the very special case of `named-let` and only for those recursive calls which are syntactically visible within the body of the loop (the TCO is applied
during macro-expansion). The only upside is that the TCO applies also
when the code is interpreted.


Stefan
--- Synchronet 3.21a-Linux NewsLink 1.2