Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu!bloom-beacon!dont-send-mail-to-path-lines From: max@nic.gac.EDU (Max Hailperin) Newsgroups: comp.lang.scheme Subject: stack/heap continuation allocation Message-ID: <9105031337.AA02153@Kolmogorov.gac.edu> Date: 3 May 91 13:37:59 GMT References: <@altdorf.ai.mit.edu,@mc.lcs.mit.edu:scheme-request@mc.lcs.mit.edu> Sender: daemon@athena.mit.edu (Mr Background) Reply-To: Max Hailperin Organization: The Internet Lines: 34 Scott Layson Burson suggests in Scheme Digest V3 #205 an implementation of call/cc which would convert the stack to heap and then allow further stack growth (and contraction) in the region on top of that. Several parties responded that the idea sounded familiar, but had some difficulty coming up with a concrete citation. The idea sounded familiar to me, and I have the good fortune to put my hand onat least one of the places it was published: MIT AI Memo No. 559 (EE&CS Integrated Circuit Memo No. 80-6), January 1980, "The SCHEME-79 Chip," by Jack Holloway, Guy Lewis Steele Jr., Gerald Jay Sussman, and Alan Bell, p. 24. The relevant quotation is: "Richard Stallman has observed that one can make stack out of list nodes, as we do, but by allocating it from a separate region, the stack will usually be a linear sequence of cells. Thus, if we can be sure that there are no pointers to the current region, pops can be done by just moving the stack pointer as in a traditional machine. If, however, the control environment is to be retained, we cannot just deallocate linearly, but rather we must defer to the garbage collector as usual. Since it is only the construcdtion of retained control environments which makes the stack non-linear, and since these retained control environments are only constructed at known times by either the user or the interrupt system, it is possible to know just which control environments are to be retained. Stallman suggests having a movable base register which points to the base of the linear (not retained) portion of the stack. When the stack is retained, the base register is just moved up to the stack pointer. When the stack is popped, it may be deallocated unless the pointer is below the base register. Assuming that such retained control environments are rare by comparison to the usual uses of the stack, one can usually treat most of the stack as a linear array, gettin most of the efficiency of normal stack operations on conventional machines."