Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!rpi!image.soe.clarkson.edu!jk0
From: jk0@image.soe.clarkson.edu (Jason Coughlin)
Newsgroups: comp.lang.scheme
Subject: Re: (none)
Message-ID: <1990Feb5.194739.3018@sun.soe.clarkson.edu>
Date: 5 Feb 90 19:47:39 GMT
References: <9002051741.AA03862@heike.informatik.uni-dortmund.de>
Sender: jk0@sun.soe.clarkson.edu (Jason Coughlin)
Organization: Clarkson University, Potsdam, NY
Lines: 90
To: muenx@heike.informatik.uni-dortmund.de

muenx@heike.informatik.uni-dortmund.de (Holger Muenx):
>   Although there are some implementations for the Amiga or at least simple
>   to port to the Amiga I decided to write my own scheme.
> 

	I could give you source to a beginning of scheme so that you
wouldn't have to implement the WHOLE thing.  I am writing a scheme -- and
the interpreter is almost completely finished (I'm acutally working onthe
compiler right now).  The source is not public domain but it is freely
distributable -- of course, I'd like your improvements to be freely
distributable too [your problem in the first case!], but we could work
this out.

>   At first, it is possible to implement scheme that tail recursions (means
>   recursions of iterative nature, needing only a constant amount of memory)
>   really work without allocating new memory during every recursive application.
>   In Abelson + Sussman it is said it is possible and I think in MIT-Scheme it
>   is done.
> 
	Correct, the stack doesn't grow by 1 cons node.  I have a compile
time option that lets you see this (the stack really doesn't grow at all).

>   Here you cannot immedeatly see if (dummy ...) is the last evaluated
>   expression. In some way you have to analyze the meaning of the procedure.
>   To my opinion it is not enough to test additional in special forms like 'if'
>   or 'cond' if the application is the last evaluated expression in this form
>   because after the 'if' or 'cond' clause there can be other expressions to be
>   evaluated.
> 
	You're thinking on too high a level -- human level.  it isn't
implemented this way.

>   But HOW can it be done? I think the problem is to determine in every
>   application of a compound procedure if it is the last command which is evaluated
>   in a procedure. For example, the following is obviously tail recursive:
> 
>        (define (dummy x)
>           (print x)
>           (dummy (1+ x)))
> 

	first of all, this is equivalent to (and the interp probably sees it
like this):

	(define dummy
		(lambda (x) 
			(print x)
			(dummy (+ 1 x))
		)
	)

	lambda is a special form that returns a closure.  a closure is
code and it's associated env (remember static scope -- things are evaled
in the env in which they're defined).  it probably looks like this:
(*CLOSURE* parms body env) where *CLOSURE* is just a symbol and env is
the CURRENT env.

	Ok, the interpreter is a stack based machine.  To evaluate the
closure (NOT LAMBDA, you've got to separate the eval of LAMBDA and what
it returns [a closure]).  On entering the closure (that's what dummy is)
Since it's static scope, you:
	(1) push the current env on the stack (so you can return to it
	when you're done with the closure)
	(2) restore the env from the closure (static scope, evaluate something
	in the environment in which it is DEFINED )
	(3) bind args to parms over this new environment
	(4) evaluate code in closure (by pushing the body of the closure
	on the stack)
	(5) restore environment that you pushed on the stack

that handles one evaluation. 

if your language doesn't handle tail recursion, then it does this ad
nauseum.  at each invokation of the closure, it pushes the current
environment so your stack has ALL of these environments on it -- the
tail recurision comes in because when you're done, you have to step back
through ALL of those environments.  to handle tail recursion, change
step 1. 

	(1) if there is an environemnt on the stack, skip to step 2.  if
	not, push the current env

	this way, there is only 1 env on the stack during any directly
recursive call.  viola, no tail recursion (you immediately pop back to
the original environment because that's the only one on the stack). 
-- 
Jason Coughlin ( jk0@sun.soe.clarkson.edu , jk0@clutx )
"Every jumbled pile of person has a thinking part that wonders what the
part that isn't thinking isn't thinking of." - They Might Be Giants