Misc ideas & comments

[strandh@cs.utexas.edu]

> 1) As far as I can see there is no simple way to generate tail
> calls in the front end.  Gcc does some tail call elimination in the
> back end, but not enough to be satisfying for a Scheme compiler (as far
> as I can figure out it only optimizes self-tail-calls).

I discussed this with RMS and here is what we came up with.  He would
be willing to include modifications to GCC in order to support it as
target for Scheme.  Essentially, GCC would support declaring a
function to have a different calling convention.  All calls to the
function as well as the function itself must see the declaration.  For
the modified calling convention, I can see two possibilities.

	1. (the one I prefer, but RMS thinks is too complicated, I
	   think the other one is complicated as well)  The calling
	   convention for Scheme compatible functions would be
	   completely altered so that the arguments are allocated in
	   the callee's stack frame the difference between sp and fp
	   would determine argument count.

	2. (the one RMS prefers) An additional invisible argument is
	   supplied indicating the argument count (must be the first
	   argument) and the calling convention is altered so that the
	   caller does not remove the arguments after the call is
	   completed.  Tail calling involves tricky manipulation of
	   the stack frame such as growing or shrinking the area used
	   for arguments. 
           

> 2) The implementation of the stack handling needed to have efficient
> first class continuations seems very difficult to integrate with the
> gcc back end.  The possibilities that I see right now are a
> setjmp/longjmp based stack copying approach, suitable only to use
> continuations for error handling; or managing your own runtime stack,
> which would somewhat defeat the aim of using the gcc back end.  The
> cleanest approach would probably be to define some additional tree
> codes with corresponding implementation in the gcc back end.  However
> this would be a largish undertaking, and since I'm no proficient
> C-hacker I don't think that I can handle this without a lot of support
> from people more familiar with both C and the gcc back end.

How about using a stack cache and migrating the stack frames to the
heap whenever the cache overflows.  You get the advantage of using the
normal stack convention of GCC but call/cc only involves flushing the
cache. 

> 3) Would it be possible to compile Scheme function calls to be
> compatible with C calls so that it would be easy to interface to C?

You can either modify GCC or use the following trick that I used
successfully: 

	Add two more parameters to a Scheme compatible function, the
	argument count and the stack offset (which is the amount that
	the caller will add to sp after the call).  Tail calls pass a
	new argument count but the same stack offset.  A return first
	deallocates the stack frame and then subtracts the stack
	offset from sp so as to compensate for what the caller will do
	after the return.  It is stupid, but works. 
> I
> think that calling C from Scheme would not be a problem, 

Right, you just tell the Scheme compiler to generate C compatible
code. 

> but that it
> would be necessary to create stubs for Scheme functions that can be
> called from C because you cannot simply stack-allocate all parameters
> to a Scheme function.  

I don't see why you could not simply stack allocate all parameters to
a Scheme function.

> I will investigate these points some more and then ask the people on
> the egcs mailing list whether I am on the right track and whether they
> would be willing to help with such an undertaking, however I am a bit
> sceptical.  Answering my (undoubtedly many) question about the gcc
> back end would mean spending a lot of their time to help with a scheme
> front end to gcc and I suppose they are more interested in improving C
> and Fortran, since these are the languages they actually use
> themselves.  Furthermore I am not really certain whether I want to
> spend that many hours writing a compiler that nobody will be
> interested in anyway.  I'll keep you updated about the results of my
> inquiry and my future plans if you are interested.

Adding tail calls to GCC according to one of the two possibilities
above seems to be the best solution which could be used for Guile as
well as for any other Scheme or Lisp system.  


-- 
Robert Strandh

---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------