jpyamamoto/lambdas

Interpreters for Lambda Calculus and extensions

Lambda Calculus Interpreters

Interpreters for several extensions of Lambda Calculus.

• Dynamic scope
• Locally nameless representation
• Bound & Free variables
• Definitions

Running

This project was built with Haskell 9.8.

stack build

To install in the PATH:

stack install

To run without installing:

stack run <interpreter>

JS

1. Install a version of GHC (>= 9.8) with the JS backend enabled. Official instructions: https://gitlab.haskell.org/ghc/ghc/-/wikis/javascript-backend/building.
2. Run cabal build.
3. The resulting JS code will be exported to: dist-newstyle/build/javascript-ghcjs/ghc-9.8.1/lambdas-0.1.0.0/x/browser/build/browser/browser.jsexe/.

Notes:

• This process is highly unstable due to the limited support of the JS backend. You may have to run cabal get <package> to download a package and adjust its dependencies, so they do not collide.
• Due to lack of support for Text by the GHC JS backend, at the moment we're limited to using the inefficient String datastructure.

Interpreters

Lambda Calculus:

• Pure: untyped
• Simply Typed (a la Church): typed
  • Naturals.
  • Booleans.
  • Operators.
  • Type checking.
  • Fixpoint recursion.
• System F.
  • Type definitions.