not using garbage collector in Scheme/Lisp implementation

Question

For my class project, I have to implement a (simple) Scheme compiler.

At this point I am brainstorming how I'd implement various features.

Why typical Scheme implementations bother with a complicated GC? If the code is truly functional (no side-effects) then non currently executing function cannot hold on to allocated memory. Ever! (unless it's a leak!)

Therefore, why not just use the strategy most imperative languages follow, like C, ie stack allocations. Every time a new lexical context is entered (ie (define (foo ..) or (letrec ...), allocate variable storage on stack and then simply adjust stack pointer once the context is exited.

Since scheme doesnt have malloc() and allows allocation only of predefined types, a simple implementation could use a pooling or zone allocater, so the "stack" should never fragment.

I dont have to implement closures, but I think even those can be done in the same vein by copying binded values to a separate stack that's used for tracking closure states exclusively.

Thoughts?

Answer 1

Even without closures, aliasing is the hard part. Specifically, suppose a procedure creates a structured piece of data and then returns a part of it? How do you determine what parts to free? If you can solve this problem... well, you've just re-invented garbage collection.

For a somewhat different take on this, you might want to take a look at Rust (www.rust-lang.org), a systems-level language that allows programmers to avoid all GC by using regions and by requiring programmers to track ownership explicitly using different pointer types.

Answer 2

Functions that finish executing return objects to their caller. Those objects cannot be allocated in the stack frames of those functions.

So either you have to ban value returning (in which case, you have procedures which are not functional programming: and to do anything useful, those procedures will have to have side effects).

Or you have to make everything by value: when an object is returned, it is copied from the stack frame of the returning function (which is subsequently deallocated), into the stack frame of the caller.

By-value systems have performance and semantic limitations.