Memory management

[hhefesto]

Original Issue: sfultong/stand-in-language#25

I thought a bit about how memory management in SIL could work, so let’s use this issue to track ideas.

1. The first option would be to use garbage collection. Integrating a conservative garbage collector (e.g. Boehm GC) with LLVM seems doable. However, integrating a precise garbage collector (or even writing a simple one from scratch) is probably a lot of work (and I’m not really familiar with that).
2. There is some cool work called ASAP: As Static As Possible memory management which basically boils down to doing as much static memory management as you can infer using various static analyses and generating code to handle the rest at runtime. In terms of complexity, this is definitely non-trivial but I would say it is far less work than getting precise garbage collection right. However, it’s worth pointing out that this is fairly new research and I’ve only read part of the thesis and not attempted to implement anything yet.
3. Try to stick somewhat close to the current approach but try to improve it in various ways. This ties in with get cabal repl working #7. Having thought about get cabal repl working #7 for a bit, I haven’t come up with a way to calculate the size that would be significantly cheaper than just executing the code. That makes me somewhat pessimistic about going down that route since at runtime that would not be useful and at compile time you might as well perform constant folding. You have definitely thought more about this so if you have some idea on how this would be beneficial, let me know!

Personally, I think the two most promising options are the following:

1. A conservative garbage collector which has the advantage of being the simplest option to implement and I think conservative garbage collection would also work reasonably well for our usecase.
2. Going down the ASAP route. This would definitely be the most interesting option from a research perspective while having the advantage of probably still being simpler than precise garbage collection.

[hhefesto]

Answer by @sfultong

I'm fine with the conservative garbage collector for now.

However, let's remember that I do want space complexity calculation down the line, so eventually I'll want something that works well with that.

For sfultong/stand-in-language#7 I'm actually ok with a situation where the calculation is almost as expensive as simply executing the grammar.