Recoding Lisp programs in C

[Smith]

	One of the problems of using malloc() and free() is that you may not 
be quite sure when you can free something. Having written a farily large Lisp
interpreter I was faced with this problem in just about every procedure. "What
is now free and what must I keep?" The answer is not easy because in a program
which is highly recursive, ie lots of procedures each of which can call a large
subset of the rest, it is very hard, if not impossible to know that item 'x'
is now free. My response to the question "why not recode in C?" is that reliable
garbage collection is hard and you are going to have to write it if the
program is fairily complex. One interesting aspect of 'mark and gather' garbage
collection in a recursive environment is that you have to mark all references
made by local variables in activated procedures. This means that you must run
down a stack of pointers to local variables and mark recursively all lists that
they refer to. For simple programs the cost of constructing this mark stack
is quite high and it has to be done for just about every recursive function.
This means that simple programs (where you know you are not going to run out
of memory doing one 'evaluation') are probably more effecient when written in C.

			Peter Ashwood-Smith
			Human Computing Resources,
			Toronto Ontario.