Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!ll-xn!cullvax!drw
From: drw@cullvax.UUCP (Dale Worley)
Newsgroups: comp.lang.lisp
Subject: heapless evaluator
Message-ID: <1308@cullvax.UUCP>
Date: Tue, 23-Jun-87 18:19:39 EDT
Article-I.D.: cullvax.1308
Posted: Tue Jun 23 18:19:39 1987
Date-Received: Thu, 25-Jun-87 03:16:33 EDT
Organization: Cullinet Software, Westwood, MA, USA
Lines: 50

system@asuvax.UUCP (Marc Lesure) writes:
> Is anyone aware of any past/present attempt[s] to produce a heapless evaluator
> for a purely functional [side-effect free] language such as pure lisp, sasl,
> miranda, lucid, etc.?  Heapless => no dynamic data structures => no GC.
> For those who wonder about lists w/o a heap, recall the language GEDANKEN
> [Reynolds CACM 13,5/1970] and its functional data structures.  Lexical scoping
> and higher order functions [full funarg] are necessary features of such a
> language.  A desirable language attribute is call-by-need semantics.

I'm not really up on all this, but the following comments come to
mind:

If you are purely applicative, even in Lisp you can't create circular
data structures, and you can't modify existing data structures.  In
that case, you don't need GC at all -- a simple reference count system
works fine.  Also, you can duplicate any structure in whole or in part
in any other part of a distributed system safely.  Thus, you get the
advantages of no GC and distributability without having to use
functional data structures.

Consider a Gedanken-style "cons" function -- it takes two arguments A
and B and returns a function:

	f(x) = A	if x = 1
	       B	otherwise

we can write this

(defun cons (a b)
		; this lambda is executed when cons is called, and it
		; creates a function which is returned as the value of
		; cons
		(lambda (x) (if (= x 1)
				a
				b)))

The trouble here is that the references to "a" and "b" persist in the
body of the returned function after the termination of the invocation
in which their stack frame was created.  I.e., you have to save those
two values *somewhere*.  This place is usually called a "closure", and
it looks to me like it will act exactly as a usual cons cell would
have in Lisp.

Maybe I'm not getting the point...  Send more details.

Dale
-- 
Dale Worley	Cullinet Software		ARPA: cullvax!drw@eddie.mit.edu
UUCP: ...!seismo!harvard!mit-eddie!cullvax!drw
If you light a match, how much mass does it convert into energy?