potential optimization: look for fully applied lambdas and substitute them all at once

[mhuesch]

motivation

our interpreter currently creates unnecessary closures.
this may or may not be a big deal.
I'd say it seems likely that other issues are more pressing than interpreter performance.

since this is semi-fresh in my mind, I'm recording my thoughts here in case we want to investigate this in the future.

core issue

currently if we have ((lam [x y] (+ x y)) 1 2), we will create 2 closures.
we'll interpret the first lambda to get a VClosure.
then we'll interpret the application of the lambda, do a substitution with 1 for x into the body, then get out another VClosure.
then we will interpret that body with 2 substituted for y, and be done.
so we will do 2 packaging-up-s of closures, and 2 substitutive interpretations.
in this case, no closure is actually needed to evaluate the arguments or the closure body (since 1, 2, and (+ x y) have no free variables - x & y are bound by the lambda).

this seems like a waste, when we could just substitute both at once, and not package up either closure.
IIRC, this is a safe optimization, but I can't remember the name for it...

I think they key is determining whether the arguments to the function applications have any free variables.
and perhaps also determining what variables are returned...

next action

• try to find this optimization, perhaps in a textbook about interpreters. seems much easier to find it than to try to reinvent the optimization.

potential approach to testing

generate well-typed Exprs (see #13).
evaluate them to Values, using the unoptimized interpreter and the optimized interpreter.
assert that both versions produce the same output.
derive equality on Value (possible??) in order to decide equality.
this should be doable given the current definition of Value, which would be a strong form of equality (I forget all the names for different equality-s, but this is a very literal form, where we would ideally just derive Eq).

after demonstrating equivalence, using 2 modules, replace the unoptimized module with the optimized one.
OR, hide the optimization behind some feature flag / optimization level.

[mhuesch]

additional links which might be useful for tracking down this concept:

https://users.cs.northwestern.edu/~robby/courses/322-2013-spring/
https://www.elsevier.com/books/engineering-a-compiler/cooper/978-0-12-088478-0
https://www.cs.princeton.edu/~appel/modern/ml/

the first is the page for a compilers course I took in undergrad.
it was based on the two books linked after it.
I am not sure if we performed the optimization I'm describing in this issue (it was perhaps optional? hard to implement in a compiler than an interpreter I think. I likely didn't implement it, because of the time constraints of the class).

[mhuesch]

migrated to neighbour-hoods/rep_lang#20.