Fuchsia is an untyped lambda calculus interpreter. Expressions are evaluated according to normal order reduction (outside-in). The core has no dependencies outside the standard library, though tests are implemented with RSpec.
To try the repl:
ruby fuchsia.rb
Fuchsia can also be run with an input file:
ruby fuchsia.rb FILE
Expressions in the input file should be newline-delimited.
Tests are implemented with RSpec. First, install dependencies:
bundle install --path .bundle
Then, run tests with:
bundle exec rspec
They include alpha-renaming, beta-reduction, eta-reduction, and various combinations.
The lexer/parser were hand-written according to the following grammar:
<expression> := <atom>
| <abstraction>
| <application>
| (<expression>)
<abstraction> := λ<atom>.<expr>
<application> := <expression> <expression>
<atom> := [a-z][a-zA-Z]*
To get rid of left recursion:
<expression> := <application>
| ε
<abstraction> := λ<atom>.<expr>
<application> := <atom> <expression>
| <abstraction> <expression>
| (<atom>) <expression>
| (<abstraction>) <expression>
<atom> := [a-z][a-zA-Z]*
Variable names can be arbitrarily long so long as they begin with a lowercase letter and otherwise only consist of alphabetic characters, so arbitrarily long expressions can be evaluated.
- Lecture slides, good except for a few errors.
- Assignment spec, basis for test-cases.
- A Tutorial Introduction to the Lambda Calculus
MIT, see LICENSE.