drw@cullvax.UUCP (Dale Worley) (06/24/87)
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?
wagner@iaoobelix.UUCP (06/26/87)
Where is the closure object supposed to be located?? I reckon, the LISP system
will put it onto the heap (stack is impossible due to its unknown lifetime)...
Juergen Wagner, (USENET) ...seismo!unido!iaoobel!wagner
("Gandalf") Fraunhofer Institute IAO, Stuttgartshebs@utah-orion.UUCP (Stanley T. Shebs) (06/30/87)
In article <6900004@iaoobelix.UUCP> wagner@iaoobelix.UUCP writes: >Where is the closure object supposed to be located?? I reckon, the LISP system >will put it onto the heap (stack is impossible due to its unknown lifetime)... In general, a closure must be a distinct type of object that lives in the heap. It is normally a two-element structure, components are environment and the code proper. Of course, this can be extremely poor both space and time-wise, so there are optimizations. Environments can be shared or eliminated in special cases, and if the closure can be proved to have a bounded lifetime, as in the expression (mapcar #'(lambda (foo) (* foo foo)) '(1 2 3)) then they can be stack-allocated. See the Orbit paper in the 1986 Compiler Conf proceedings for some good discussion of closure analysis. >Juergen Wagner, (USENET) ...seismo!unido!iaoobel!wagner stan shebs shebs@cs.utah.edu