not using garbage collector in Scheme/Lisp implementation
garbage-collection, lisp, scheme
Solution
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.
Problem
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?