LambdaCraft is a Common Lisp DSL for building untyped lambda calculus terms in a macro-based style. It is inspired by Ben Rudiak-Gould's Scheme program Lazier, a compiler from lambda terms written in Scheme to Lazy K.
LambdaCraft is used to build LambdaLisp, a Lisp interpreter written in untyped lambda calculus. It can be used to write large programs in the following lambda-calculus-based languages:
LambdaCraft can also be used to build general-purpose generic lambda terms for educational purposes as well. Many output formats shown in the supported output formats section are supported.
(load "./lambdacraft.cl")
(defrec-lazy fact (n)
(if (<= n 0)
1
(* n (fact (- n 1)))))
(format t (compile-to-plaintext-lambda-lazy fact))will print
(λx.(λy.(x (y y)) λy.(x (y y))) λx.λy.((((((λz.λa.a λy.λa.λb.(((y λc.λd.(d (c a))) λc.b) λc.c)) y) λz.λz.λb.b) λz.λa.z) λz.λa.(z a)) λz.λa.((y ((x ((λz.λa.(z a) y.λz.λa.(((y λe.λf.(f (e z))) λe.a) λe.e)) y)) z)) a)))
Which is a lambda calculus term that takes a Church-encoded number and returns its factorial.
Here, defrec-lazy is a LambdaCraft macro that uses the Y combinator for self-recursion.
The source code is available as example.cl.
LambdaCraft supports the following lambda-calculus-based and SKI-combinator-based languages:
These languages accept a lambda calculus term or a SKI combinator calculus term as a program. Using a stream-based I/O with strings encoded in the Mogensen-Scott encoding, these languages are able to handle lambda terms as a function that takes a string and outputs a string, where each string represents the standard input and output.
examples/*.cl are sample scripts for these languages, which compiles to a program that prints the letter A and exits.
The outputs of examples/*.cl can be run on each language as:
sbcl --script ./examples/blc.cl | asc2bin | tromp # Binary Lambda Calculus
sbcl --script ./examples/ulamb.cl | asc2bin | clamb -u # Universal Lambda
lazyk <(sbcl --script ./examples/lazyk.cl) -u # Lazy KInstructions for building the interpreters for these languages are described in detail in my other project, LambdaLisp.
LambdaCraft can compile lambda terms into the following formats:
| Format | Example | API |
|---|---|---|
| Plaintext lambda notation | \x.x |
compile-to-plaintext-lambda-lazy |
| Binary lambda calculus notation | 0010 |
compile-to-blc-lazy |
| SKI combinator calculus term in Unlambda notation | ``skk |
compile-to-ski-lazy |
| SKI combinator calculus term | ((SK)K) |
compile-to-ski-parens-lazy |
| Plaintext lambda compatible with https://github.com/tromp/AIT | (\x.x) |
compile-to-lam-lazy |
| Lisp S-expression | (lambda (x) x) |
compile-to-lisp-lazy |
| Lisp S-expression, pretty-printed | (lambda (x) x) |
compile-to-lisp-pretty-lazy |
| JavaScript function | function (x) { return x; } |
compile-to-js-lazy |
| JavaScript function in arrow notation | (x) => x |
compile-to-js-arrow-lazy |
| Python lambda | lambda x: x |
compile-to-python-lazy |
LambdaCraft is written in Common Lisp. It should run in any Common Lisp interpreter of your choice. I particularly use SBCL (Steel Bank Common Lisp), which is installable by:
sudo apt install sbclor on a Mac with:
brew install sbclLambdaCraft can then be used by simply including the program as a header, and running the source as a Common Lisp program. For example, example.cl can be run as:
sbcl --script example.clwhich will print the factorial function defined in the script.
LambdaCraft also runs on LambdaLisp as well, since it is written as a Common-Lisp-LambdaLisp polyglot program. Practically, running it on Common Lisp is faster.
The test runs make test, which does the following:
- Runs ./examples/ulamb.cl with SBCL, and saves the output as
a.ulamb - Builds clamb, a Universal Lambda interpreter written by Kunihiko Sakamoto (@irori)
- Runs
a.ulambonclamband confirms that it prints the letterA