Future work on interpreter

[brprice]

Description

There is some future work we could do on the new interpreter #1187. This (WIP) FR is to record some ideas.

Dependencies

None

Spec

We rely heavily on laziness and the Haskell runtime, and we work entirely in the Expr AST. This means we cannot make expressions spine-strict with our current interpreter. One reason we made this choice was an attempt to be able to return a sensible result if we time-out (this hope did not pan out). Since the implementation choice requires us to evaluate under lambdas, and we don't actually want to do that all the time (e.g. if a student asks to evaluate the function map for instance, we don't want to unroll recursive occurrences), it may pay off to change strategy.

We could investigate a more traditional interpreter or compile-to-closures, representing the interpretation of a (syntactic) lambda as a Haskell lambda or a closure (pair of environment and syntactic body). Another approach of interest is normalization by evaluation. Perhaps a smaller change to enable a sensible partial result after a timeout would be to investigate a CPS style.

Implementation details

Unknown as yet, but we should think about whether (and how) the implemented strategy will evaluate under lambdas, and whether it can sensibly have a deterministic (non time-based) timeout (and if so whether it can return partially evaluated results). Another decision needed is whether to require exact agreement with the small-step reduction semantics (NBE returns eta-long results, which small-step may not).

Not in spec

Discussion

Future work

This may unlock making the Expr type stricter.