[Lightning] Tail calls - a better way

[Francis McCabe]

Could not help butting in here.

Paulo suggests the ‘classic’ way of implementing tail calls - by ‘sliding’ the 
new activation over the old one.

It turns out that there is a strictly faster way of implementing tail call 
optimization: garbage collecting the evaluation stack.

The idea would be to continue processing tail calls in the identical way to 
regular calls - but, when a GC is required (by stack overflow for example) the 
evaluation stack can be garbage collected of junk frames.

In terms of support required, it would have to be similar to other GC support 
schemes; except that there would have to be standard ways of walking the stack 
- something that is useful for other applications (like debugging).

Frank McCabe


> On Jan 9, 2015, at 1:55 PM, address@hidden wrote:
> 
> Send Lightning mailing list submissions to
>       address@hidden
> 
> To subscribe or unsubscribe via the World Wide Web, visit
>       https://lists.gnu.org/mailman/listinfo/lightning
> or, via email, send a message with subject or body 'help' to
>       address@hidden
> 
> You can reach the person managing the list at
>       address@hidden
> 
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Lightning digest..."
> 
> 
> Today's Topics:
> 
>   1. Are tail calls possible in GNU lightning? (Marc Nieper-Wi?kirchen)
>   2. Re: Are tail calls possible in GNU lightning?
>      (Paulo C?sar Pereira de Andrade)
>   3. Re: Are tail calls possible in GNU lightning?
>      (Marc Nieper-Wi?kirchen)
>   4. Re: Are tail calls possible in GNU lightning?
>      (Marc Nieper-Wi?kirchen)
> 
> 
> ----------------------------------------------------------------------
> 
> Message: 1
> Date: Fri, 9 Jan 2015 19:33:49 +0100
> From: Marc Nieper-Wi?kirchen <address@hidden>
> To: address@hidden
> Subject: [Lightning] Are tail calls possible in GNU lightning?
> Message-ID:
>       <address@hidden>
> Content-Type: text/plain; charset="utf-8"
> 
> Hi,
> 
> I haven't found any information whether tail calls are possible in GNU
> lightning while remaining portability. In case they are, would they also
> portably work across code that was generated by different calls to
> jit_emit()?
> 
> Best,
> 
> Marc
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: 
> <http://lists.gnu.org/archive/html/lightning/attachments/20150109/c87e2166/attachment.html>
> 
> ------------------------------
> 
> Message: 2
> Date: Fri, 9 Jan 2015 18:19:55 -0200
> From: Paulo C?sar Pereira de Andrade
>       <address@hidden>
> To: Marc Nieper-Wi?kirchen <address@hidden>
> Cc: lightning <address@hidden>
> Subject: Re: [Lightning] Are tail calls possible in GNU lightning?
> Message-ID:
>       <address@hidden>
> Content-Type: text/plain; charset=UTF-8
> 
> 2015-01-09 16:33 GMT-02:00 Marc Nieper-Wi?kirchen <address@hidden>:
>> Hi,
> 
>  Hi,
> 
>> I haven't found any information whether tail calls are possible in GNU
>> lightning while remaining portability. In case they are, would they also
>> portably work across code that was generated by different calls to
>> jit_emit()?
> 
>  It is not supported, but is on my non official TODO list. Note that
> if one is implementing a high level language, most likely is also
> using a "virtual stack" in the heap, and there anything can be done,
> for example, all language specific function calls could be jumps.
> 
>  Implementation using the "real" stack would be somewhat like this:
> 
> 1. Calculate stack depth of current function based on calls to jit_arg,
>    jit_arg_f and jit_arg_d, just for the sake of asserting will not corrupt
>    the stack, but must trust the programmer that the function
>    was called that way
> 2. Instead of "jit_prepare", would have something like "jit_tail"
> 3. After the above, jit_pusharg* would replace arguments  in the
>   current stack frame
> 4. Since it used the hypothetical "jit_tail" to prepare to call,
>   when jit_finish*() would be called, it would be replaced by
>   jit_jmp*(), or, could require an explicit jit_jmp* call
> 
>  This should not be too difficult to implement, and can be done
> in a reasonably portable way.
> 
>  Should be easier to implement than other 2 TODOs I have, that
> are support for varargs jit functions, not just calling varargs functions,
> and jit_allocar, that is, allocating variable stack space at run time,
> not just fixed size defined at jit generation.
> 
>  Do you have some more information about where, and why you
> need it?
> 
>  I am holding lightning 2.0.6 release to fix any remaining issues
> of using it to generate jit for GNU Smalltalk...
> 
>> Best,
>> 
>> Marc
> 
> Thanks,
> Paulo
> 
> 
> 
> ------------------------------
> 
> Message: 3
> Date: Fri, 9 Jan 2015 22:14:02 +0100
> From: Marc Nieper-Wi?kirchen <address@hidden>
> To: Paulo C?sar Pereira de Andrade
>       <address@hidden>
> Cc: lightning <address@hidden>
> Subject: Re: [Lightning] Are tail calls possible in GNU lightning?
> Message-ID:
>       <address@hidden>
> Content-Type: text/plain; charset="utf-8"
> 
> Dear Paulo,
> 
> thank you very much for your quick reply.
> 
> I am thinking of using GNU lightning to implement a small virtual machine
> that is able to JIT-compile a programming language like Scheme which needs
> guaranteed tail-calls (and where the existence call/cc forces continuation
> passing style).
> 
> In fact, the VM implementation will have a virtual stack and all internal
> calls will in fact be jumps as you suggested. Thus, so far I could
> implement everything in one large function, and everything would be fine.
> 
> However, the VM should also support a kind of eval, which should trigger
> JIT-compilation on the fly. In this case, GNU lightning shall be called
> from the already running compiled code. GNU lightning will produce a second
> function at a new address, which I want to tail-call from my already
> running function. Thus I need to know whether there is a portable way to
> dynamically jump into this second function.
> 
> (Don't hesitate to ask in case my explanation didn't help you.)
> 
> Best,
> 
> Marc
> 
> 2015-01-09 21:19 GMT+01:00 Paulo C?sar Pereira de Andrade <
> address@hidden>:
> 
>> 2015-01-09 16:33 GMT-02:00 Marc Nieper-Wi?kirchen <
>> address@hidden>:
>>> Hi,
>> 
>>  Hi,
>> 
>>> I haven't found any information whether tail calls are possible in GNU
>>> lightning while remaining portability. In case they are, would they also
>>> portably work across code that was generated by different calls to
>>> jit_emit()?
>> 
>>  It is not supported, but is on my non official TODO list. Note that
>> if one is implementing a high level language, most likely is also
>> using a "virtual stack" in the heap, and there anything can be done,
>> for example, all language specific function calls could be jumps.
>> 
>>  Implementation using the "real" stack would be somewhat like this:
>> 
>> 1. Calculate stack depth of current function based on calls to jit_arg,
>>    jit_arg_f and jit_arg_d, just for the sake of asserting will not
>> corrupt
>>    the stack, but must trust the programmer that the function
>>    was called that way
>> 2. Instead of "jit_prepare", would have something like "jit_tail"
>> 3. After the above, jit_pusharg* would replace arguments  in the
>>   current stack frame
>> 4. Since it used the hypothetical "jit_tail" to prepare to call,
>>   when jit_finish*() would be called, it would be replaced by
>>   jit_jmp*(), or, could require an explicit jit_jmp* call
>> 
>>  This should not be too difficult to implement, and can be done
>> in a reasonably portable way.
>> 
>>  Should be easier to implement than other 2 TODOs I have, that
>> are support for varargs jit functions, not just calling varargs functions,
>> and jit_allocar, that is, allocating variable stack space at run time,
>> not just fixed size defined at jit generation.
>> 
>>  Do you have some more information about where, and why you
>> need it?
>> 
>>  I am holding lightning 2.0.6 release to fix any remaining issues
>> of using it to generate jit for GNU Smalltalk...
>> 
>>> Best,
>>> 
>>> Marc
>> 
>> Thanks,
>> Paulo
>> 
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: 
> <http://lists.gnu.org/archive/html/lightning/attachments/20150109/e4b53705/attachment.html>
> 
> ------------------------------
> 
> Message: 4
> Date: Fri, 9 Jan 2015 22:55:33 +0100
> From: Marc Nieper-Wi?kirchen <address@hidden>
> To: Paulo C?sar Pereira de Andrade
>       <address@hidden>
> Cc: lightning <address@hidden>
> Subject: Re: [Lightning] Are tail calls possible in GNU lightning?
> Message-ID:
>       <address@hidden>
> Content-Type: text/plain; charset="utf-8"
> 
> P.S.: I have written a small example program that demonstrates what I want
> to achieve:
> 
> #include <stdio.h>
> #include <lightning.h>
> 
> static jit_state_t *_jit;
> 
> jit_node_t *compile() {
>  jit_state_t *_jit;
>  _jit = jit_new_state();
>  jit_prolog();
>  jit_node_t *label = jit_indirect();
>  jit_reti(42);
>  jit_emit();
>  jit_clear_state();
>  return jit_address(label);
> }
> 
> int main(int argc, char* argv[]) {
> 
>  int (*code)();
> 
>  jit_node_t *jump, *label, *ref;
> 
>  init_jit(argv[0]);
>  _jit = jit_new_state();
> 
>  jit_prolog();
>  jit_prepare();
>  jit_finishi(compile);
>  jit_retval(JIT_R0);
>  jit_jmpr(JIT_R0);
> 
>  code = jit_emit();
>  jit_clear_state();
> 
>  printf("Result: %d\n", code());
> 
>  jit_destroy_state();
>  finish_jit();
> 
>  return 0;
> }
> 
> I can run this program successfully on my x86_64 GNU/Linux. But does it
> work portably?
> 
> Marc
> 
> 2015-01-09 22:14 GMT+01:00 Marc Nieper-Wi?kirchen <address@hidden
>> :
> 
>> Dear Paulo,
>> 
>> thank you very much for your quick reply.
>> 
>> I am thinking of using GNU lightning to implement a small virtual machine
>> that is able to JIT-compile a programming language like Scheme which needs
>> guaranteed tail-calls (and where the existence call/cc forces continuation
>> passing style).
>> 
>> In fact, the VM implementation will have a virtual stack and all internal
>> calls will in fact be jumps as you suggested. Thus, so far I could
>> implement everything in one large function, and everything would be fine.
>> 
>> However, the VM should also support a kind of eval, which should trigger
>> JIT-compilation on the fly. In this case, GNU lightning shall be called
>> from the already running compiled code. GNU lightning will produce a second
>> function at a new address, which I want to tail-call from my already
>> running function. Thus I need to know whether there is a portable way to
>> dynamically jump into this second function.
>> 
>> (Don't hesitate to ask in case my explanation didn't help you.)
>> 
>> Best,
>> 
>> Marc
>> 
>> 2015-01-09 21:19 GMT+01:00 Paulo C?sar Pereira de Andrade <
>> address@hidden>:
>> 
>>> 2015-01-09 16:33 GMT-02:00 Marc Nieper-Wi?kirchen <
>>> address@hidden>:
>>>> Hi,
>>> 
>>>  Hi,
>>> 
>>>> I haven't found any information whether tail calls are possible in GNU
>>>> lightning while remaining portability. In case they are, would they also
>>>> portably work across code that was generated by different calls to
>>>> jit_emit()?
>>> 
>>>  It is not supported, but is on my non official TODO list. Note that
>>> if one is implementing a high level language, most likely is also
>>> using a "virtual stack" in the heap, and there anything can be done,
>>> for example, all language specific function calls could be jumps.
>>> 
>>>  Implementation using the "real" stack would be somewhat like this:
>>> 
>>> 1. Calculate stack depth of current function based on calls to jit_arg,
>>>    jit_arg_f and jit_arg_d, just for the sake of asserting will not
>>> corrupt
>>>    the stack, but must trust the programmer that the function
>>>    was called that way
>>> 2. Instead of "jit_prepare", would have something like "jit_tail"
>>> 3. After the above, jit_pusharg* would replace arguments  in the
>>>   current stack frame
>>> 4. Since it used the hypothetical "jit_tail" to prepare to call,
>>>   when jit_finish*() would be called, it would be replaced by
>>>   jit_jmp*(), or, could require an explicit jit_jmp* call
>>> 
>>>  This should not be too difficult to implement, and can be done
>>> in a reasonably portable way.
>>> 
>>>  Should be easier to implement than other 2 TODOs I have, that
>>> are support for varargs jit functions, not just calling varargs functions,
>>> and jit_allocar, that is, allocating variable stack space at run time,
>>> not just fixed size defined at jit generation.
>>> 
>>>  Do you have some more information about where, and why you
>>> need it?
>>> 
>>>  I am holding lightning 2.0.6 release to fix any remaining issues
>>> of using it to generate jit for GNU Smalltalk...
>>> 
>>>> Best,
>>>> 
>>>> Marc
>>> 
>>> Thanks,
>>> Paulo
>>> 
>> 
>> 
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: 
> <http://lists.gnu.org/archive/html/lightning/attachments/20150109/dfcafc91/attachment.html>
> 
> ------------------------------
> 
> _______________________________________________
> Lightning mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/lightning
> 
> 
> End of Lightning Digest, Vol 74, Issue 3
> ****************************************