LCI is an interpreter for the lambda calculus. It supports many advanced features such as recursion, user-defined operators and multiple evaluation strategies, all based on the pure calculus. It is free software licenced under the GNU General Public Licence (GPL).
LCI can run in a browser via WebAssembly. Try the demo!
LCI can be considered a small (but powerfull) functional progamming language based on the pure lambda-calculus. Its features include:
- Aliases of lambda terms (that is named functions).
- Integers
- An arbitrary encoding can be used by defining
0, Succ, Pred, IsZero. - Church encoding is used by default in
.lcirc. - Scott encoding is also available (uncomment to use it)
- An arbitrary encoding can be used by defining
- Recursion. Self-references of aliases are expanded during execution. LCI can also automatically convert recursive terms to non-recursive ones using a fixed point combinator.
- User-defined operators. The user can declare a new
operator with a certain precedence and associativity and define it in lambda
calculus. Many common operators (eg. integer, logic and list operations) are
pre-defined in
.lcircand are available by default. - List syntax.
[a,b,c]is parsed asa:b:c:Nil(:andNilare defined in.lcirc). - Let syntax.
let x = M in Nis parsed as(\x.N) M. - Multiple evaluation strategies. Call-by-name and call-by-value can coexist in the same program.
- Human-readable display of terms: for example church numerals are
displayed as numbers and lists using the
[a,b,c]notation. - Tracing of execution.
- File interpretation as well as interactive usage.
- A library of pre-defined functions (
.lcirc).
All features are implemented in the pure lambda calculus.
To demonstrate them, there is an implementation of the N-Queens problem
(queens.lci) in a way that reminds of Haskell syntax.
The latest version is available here. To install extract the archive, cd to that directory and run:
cmake -B build
cd build && make
sudo make install
This will install the lci executable in /usr/local/bin and .lcirc, queens.lci in
/usr/local/share/lci. You can install then in a different location by passing
-DCMAKE_INSTALL_PREFIX=<dir> to cmake.
Install Homebrew and run:
brew install lci
Windows binaries are
available here.
Simply extract and run the lci executable.
The browser version can be built with emscripten.
You first need to build make_dparser with a normal build, then build
again with emcmake. The build is created under build/html/dist.
mkdir build && cd build
cmake ..
make make_dparser
rm CMakeCache.txt
emcmake cmake ..
emmake make
If you have found a bug please report it. Also feel free to send pull requests, or suggest features.
LCI's documentation covers most of the program's features and related lambda-calculus concepts.