Re: Compile to C difficulties

George Neuner <gneuner2@comcast.net>
12 Sep 2006 18:59:21 -0400

          From comp.compilers

Related articles
Compile to C difficulties chpowell2002@yahoo.com (Charlie) (2006-09-08)
Re: Compile to C difficulties tmk@netvision.net.il (Michael Tiomkin) (2006-09-08)
Re: Compile to C difficulties pjb@informatimago.com (Pascal Bourguignon) (2006-09-08)
Re: Compile to C difficulties gneuner2@comcast.net (George Neuner) (2006-09-09)
Re: Compile to C difficulties chpowell2002@yahoo.com (Charlie) (2006-09-11)
Re: Compile to C difficulties gneuner2@comcast.net (George Neuner) (2006-09-12)
Re: Compile to C difficulties chpowell2002@yahoo.com (Charlie) (2006-09-16)
Re: Compile to C difficulties kym@ukato.freeshell.org (russell kym horsell) (2006-09-18)
| List of all articles for this month |

From: George Neuner <gneuner2@comcast.net>
Newsgroups: comp.compilers
Date: 12 Sep 2006 18:59:21 -0400
Organization: Compilers Central
References: 06-09-02606-09-031 06-09-055
Keywords: code
Posted-Date: 12 Sep 2006 18:59:21 EDT

On 11 Sep 2006 23:59:44 -0400, "Charlie" <chpowell2002@yahoo.com>
wrote:


>The Core of the entire project is a high level semantic specification,
>with recursion used throughout. Removing recursion,( or more properly
>induction), is not a real possibility, although in isolated cases I
>have done so by evoking generated code in C while loops. Translating
>to a language other than C, say to Mercury, would be a better option
>if it comes to that. Hovever Mercury itself is translated to C.


IIRC, Mercury generates CPS code. That is one option for handling
unbounded recursion (see below).




>I am not actually manipulating the CPU stack pointer,
>( I would not Know how to do that in semi portable C )


See setjmp/longjmp. setjmp records the CPU's state in a structure
called a jumpbuf. longjmp takes the jumpbuf structure and (re)sets
the CPU to the state indicated by it.


setjmp/longjmp are standard library functions, but the jumpbuf
structure is architecture and OS specific and frequently not
documented very well. You may have to do some detective work to
figure out which fields to modify for your purpose.






>I am reading it and testing it, something roughly like
>
> PROCEDURE(yy Input1, yy Inupt2, yy * Output3 )
> int abc; void * sp=&abc; ....
> if( sp>LIMIT){ MY_STACK[SP+1]=Input1; ... ;
>Module_A(PROCEDURE_NUMBER);
> *Output3=MY_STACK[SP+3]; return ;
> }
> else { Regular procedure code }
>
>
>where Module_A is a single procedure with a switch on PROCEDURE_NUMBER
>to a goto to begining of Procedure Code, evoking other procedures
>within the module with gotos, setting a procedure occurance return
>number on the MY_STACK, used by an even larger switch with a case for
>each procedure occurance. Inside the Module Procedure variable passing
>occurs on MY_STACK. Procedures in other modules,
>and C procedures are evoked normally. Assuming no recursion between
>procedures in different modules, recursion in contained.


If I understand correctly, you've rewritten the DSL recursion in the
form a threaded interpreter using an auxiliary data structure, and now
use the real stack mostly for support functions.


While that certainly solves your stack overflow problem, I would bet
it is a *lot* slower than directly executing the original recursive
solution would have been (assuming you could). It probably also uses
more total memory even though it uses less stack.




If you can't eliminate the recursion, generating CPS might be the best
solution. In CPS code a function call never returns, so the stack
just keeps growing. You check the stack size before calling a
function and when it gets too large, you copy the current call frame
to the bottom of the stack and change the stack pointer ... thus
freeing all the garbage on the stack at once.




George


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.