A Lambda Calculus to LLVM IR compiler
- run
pipx install git+https://github.com/Ferdi265/lambda-compiler
to install - run
pipx install --editable .
for a development install
pipx
is a modern replacement for installing CLI applications with pip
directly, since pip
now by default forbids installing applications outside a
virtualenv on most distros. You can use pip
as well, but pipx
is
recommended.
- a few example programs are found in the
examples/
subdirectory - you can create a new project by running
lambda-mkmake myproject
in a new folder
Compilation is done in five steps:
- collect GNU Make dependency information for a Lambda crate (
lambda-lang2deps
) - collect a whole Lambda crate into one file, resolve names and macros (
lambda-lang2hlir
) - compile Lambda calculus expressions to simple returns, tail calls, and calls, with explicit captures (
lambda-hlir2mlir
) - translate the resulting intermediate language to LLVM IR (
lambda-mlir2llir
) and generate a main function (lambda-mlir2main
) - compile the resulting LLVM IR together with the runtime and external IO routines into a program (
clang
)
Lambda is an eagerly evaluated lambda calculus.
- Function Application:
func arg1 arg2
is equivalent to(func(arg1))(arg2)
in Python - Lambda Construction:
func arg -> body
is equivalent tofunc(lambda arg: body)
in Python - Parentheses can be used to adjust precedence:
func arg -> body arg2
is equivalent tofunc(lambda arg: body(arg2))
in Pythonfunc (arg -> body) arg2
is equivalent to(func(lambda arg: body))(arg2)
in Python
- Macros are prefixed by
!
and expand to regular calls to functions defined instd.lambda
:!"string"
expands to a call to(std::list_n ...)
constructing a list of numbers representing the UTF-8 bytes of the string!42
expands to a call to(std::dec2 ...)
or(std::dec3 ...)
to construct a number object. Number literals greater than 999 are currently not supported.
A Lambda program is a list of definitions that can only refer to previous definitions (not to themselves). This means one has to use a fixed point combinator such as the y combinator to create recursive functions.
true = a -> b -> a;
false = a -> b -> b;
not = a -> a false true;