[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: native compilation units

From: Lynn Winebarger
Subject: Re: native compilation units
Date: Mon, 20 Jun 2022 08:34:41 -0400

On Sun, Jun 19, 2022 at 9:39 PM Lynn Winebarger <owinebar@gmail.com> wrote:
On Sun, Jun 19, 2022 at 7:02 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:

Proper tail recursion elimination would require changing the *normal*
function call protocol.  I suspect you're thinking of a smaller-scale
version of it specifically tailored to self-recursion, kind of like
what `named-let` provides.  Note that such ad-hoc TCO tends to hit the same
semantic issues as the -O3 optimization of the native compiler.
E.g. in code like the following:

    (defun vc-foo-register (file)
      (when (some-hint-is-true)
        (load "vc-foo")
        (vc-foo-register file)))

the final call to `vc-foo-register` is in tail position but is not
a self call because loading `vc-foo` is expected to redefine
`vc-foo-register` with the real implementation.

I'm only talking about the steps that are required to allow the compiler to 
produce code that implements proper tail recursion.
With the abstract machine currently implemented by the byte-code VM,
the "call[n]" instructions will always be needed to call out according to
the C calling conventions.
The call[-absolute/relative] or [goto-absolute] instructions I suggested
*would be* used in the "normal" function-call protocol in place of the current
funcall dispatch, at least to functions defined in lisp.  
This is necessary but not sufficient for proper tail recursion.
To actually get proper tail recursion requires the compiler to use the instructions
for implementing the appropriate function call protocol, especially if
"goto-absolute" is the instruction provided for changing the PC register.
Other instructions would have to be issued to manage the stack frame
explicitly if that were the route taken.  Or,  a more CISCish call-absolute
type of instruction could be used that would perform that stack frame
management implicitly.
EIther way, it's the compiler that has to determine whether a return
instruction following a control transfer can be safely eliminated or not.
If the "goto-absolute" instruction were used, the compiler would
have to decide whether the address following the "goto-absolute"
should be pushed in a new frame, or if it can be "pre-emptively
garbage collected"  at compile time because it's a tail call.

For the record, my point of reference for a classic implementation of efficient
lexical closures and proper tail recursion is Clinger's TwoBit compiler for
Larceny Scheme, and the associated "MacScheme" abstract machine:
https://www.larcenists.org/twobit.html.   That system is implemented
in several variants.  Each has a well-defined mapping of the state of the
MacScheme machine state to the actual machine state for compiled code.
That system does not have the constraint of having a byte-code interpreter
and native-code implementation co-existing, but if they do coexist and 
are expected to be able to call each other with the "normal" (lisp, not C)
calling conventions, defining the abstract machine state that has to be 
maintained between calls would be a key step.
If calling between byte-code and native-code is expected to have the same 
overhead as calling between lisp and C, then I suppose that's not necessary.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]