Memleak in basic lambda usage

[Mai-Lapyst]

When using lambdas in a basic setting, they create rather big memleaks:

(define foo (lambda () ()))

or

(defun foo () ())

This makes it sadly impossible to embedd this library into larger, long-running applications like webservices without takeing up large amounts of memory very quickly.

---

Commit: e0f571b

Command: valgrind --tool=memcheck --leak-check=full --track-origins=yes --show-leak-kinds=all ./target/debug/rust_lisp '(define foo (lambda () ()))'

Valgrind output: https://gist.github.com/Mai-Lapyst/d8a560bf018b04bcf497255772ae8710

[Mai-Lapyst]

I've found a solution for this: https://github.com/Mai-Lapyst/rust_lisp/tree/test-fix-closure-memleaks

It's still a bit rough, but I dont get any compiler errors with it and valgrind dosn't complain when tested, even with more "complex" examples like the following:

(define counter
    (lambda (start)
        (let ((i start))
            (list
                (lambda () i)
                (lambda ()
                    (set i (+ i 1))
                    ()
                )
            )
        )
    )
)
(define my (counter 4))
((nth 0 my))
((nth 1 my))
((nth 0 my))

---

An complete and full explanation of what the changed code does and all can be found in a blogpost here, but I'll also repeat the core points here:

I've named this technique "Switchable references with strongchain elimination"; essentially it utilizes a custom referencetype that is allowed to be either a strong or a weak reference (Rc<RefCell<Env>> vs Weak<RefCell<Env>>).

When a closure is "born", it contains a weak reference to it's environment, as to be created, the environment(s) it captures need to be still alive. Once the env is about to be destroyed, we'll do a scan on all values that might be escaping (as for example return values from invoking a closure). Since the env is about to be destroyed, the reference to the env a closure form that env is switched to a strong one, so the env is kept alive.

While this gets rid of closures creating a cycle by themselv, if they're bound to an parent env again (like in the example above), it creates a chain again, only a buch longer one. To combat that problem, well do "strongchain elimination", which is just that we scan the value we're about to bound to a env to find any lambda which a strong reference to it's captured env and walk the chain until we're find the env that we're trying to bind the value onto; if we're found it, we're switching that reference to an weak one, as the value itself is now bound to that env anyway so it dosn't need to prevent it from being dropped.

As I said, this is a technique thats fairly new, so if you find any examples that prove it further (be it that it's working or not), I'm happy to hear from you so this can be further proven & extended.

Thank you for this amazing crate that enabled me to discover & refine this technique / idea!