Re: native compilation units

[Lynn Winebarger <owinebar@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 3323 bytes --]

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.

Lynn

[-- Attachment #2: Type: text/html, Size: 4713 bytes --]