A simple implementation of untyped lambda calculus using Normalization by Evaluation (NbE) in Haskell.
We use De Bruijn indices for terms and De Bruijn levels for values. In combination with NbE, this completely avoids the need for term reindexing, manual substitution, alpha equivalence, and alpha conversion. Inspired by elaboration-zoo/01-eval-closures-debruijn (I've cleaned it up and removed everything except pure NbE).
- The NbE implementation:
src/Lib.hs. - The unit tests:
test/Spec.hs.
Type stack test in the root project directory to execute the tests.