Scheme front end for egcs.

[tc at gauss dot muc dot de (Matthias Hoelzl tc)]

I am currently trying to find out whether it would be possible for
me to write a Scheme front end to the gcc/egcs compiler.  

Right now I have figured out how to set up the Makefiles, etc. to add
a new front end to egcs, and I have built a simple compiler that
handles arithmetic functions in Scheme syntax.  But I am unsure how to
deal with some important topics for compiling Scheme:

Scheme requires functions to be properly tail recursive and many
programs rely on this.  Therefore the Scheme equivalent to the
following program

int
main(int argc, char** argv)
{
  a(0);
  return 0;
}

void
a(int i)
{
  if ( i < 100 )
    b(i + 1);
  else
    b(0);
}

void
b(int i)
{
  a(i + 1);
}

should loop indefinitely (instead of overflowing the stack).  However,
unless I am missing something, implementing proper tail recursion is
rather difficult with the current calling convention.  It seems that
support for tail calls might best be implemented by adding some
extensions to the back end; on the other hand complicating the back
end to add support for one not very widely used language might not be
such a good idea.  Robert Strandh has already discussed this topic
with RMS and they reached the conclusion that one of the following
calling conventions should be implemented in addition to the existing
one (quoted from Robert's email):

>	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. 

To which I'll add

3. Have a different stack for Scheme->Scheme calls, generate
   tree/rtl instructions to manage this stack directly in the 
   front end and use the "C-stack" only to call non-Scheme functions.  
   This would also ease the handling of first-class continuations, but 
   seems rather inelegant otherwise.  Would the back end be able to
   do register allocation, etc. for Scheme code that basically looks
   like one enormous function?

Personally I would prefer option 1, but I would be interested in your
opinions.  How would different calling conventions be reflected in the
tree language?

Scheme has first-class continuation which require some manipulations
of the stack.  Is there a portable way to find the base of the stack,
to walk the stack and to copy parts of the stack to/from the heap?


Regards,

  Matthias