Lambda Zero is a minimalist pure lazy functional programming language with:
- All the standard Lambda Calculus features (first class functions, closures, currying, recursion, nested function definitions, ...)
- Lazy evaluation (infinite data structures, increased modularity, ...)
- Algebraic data types (enumerations, tuples, lists, trees, records/structs, maybe/optional types, checked exceptions, monads, ...)
- Pattern matching (case expressions, tuple destructuring, ...)
- Automatic garbage collection
- Semantic whitespace
- Unicode support (UTF8)
- User-defined lexically-scoped operator syntax and semantics (even spaces)
- Uniform function call syntax (
f(x, y, z))
- Hindley-Milner static type inference (implemented in Lambda Zero)
- A self-interpreter
And the whole language can be interpreted with just over 2000 lines of C code!
main(input) ≔ "hello world"
n ! ≔ n ⦊ 0 ↦ 1; ↑ n′ ↦ n ⋅ n′ !
sort ≔  ↦ ; n ∷ ns ↦ sort(ns ¦ (≤ n)) ⧺ [n] ⧺ sort(ns ¦ (> n))
Infinite list of natural numbers
iterate(f, x) ≔ x ∷ iterate(f, f(x)) (…) ≔ iterate(↑) naturals ≔ 0 …
Infinite list of Fibonacci numbers
fibonaccis ≔ f(0, 1) where f(m, n) ≔ m ∷ f(n, m + n)
Infinite list of prime numbers
primes ≔ p(2 …) where p ≔  ↦ ; n ∷ ns ↦ n ∷ p(ns ¦ (% n ≠ 0))
The Lambda Calculus is incredibly elegant and can be a very powerful high-level programming language with just a few simple optimizations and syntactic sugars.
Lambda Zero allows you to program in the Lambda Calculus with just the minimal amount of added features to make it practical and readable. Lambda Zero combines the elegance of Haskell with the simplicity of LISP.
The primary use case of Lambda Zero is to bootstrap a future higher level language "Lambda One" i.e. Lambda Zero is a sublanguage of Lambda One and the Lambda One compiler is written entirely in Lambda Zero.
Lambda Zero is also a good way to learn about functional programming since it is much simpler than other languages like Haskell, but operates on the same foundation.
Lambda Zero is not a general purpose language; the interpreter is optimized for simplicity over performance and the language does not allow any I/O besides accepting stdio as a string and returning a string which is sent to stdout by the interpreter.
First we will describe the core language without syntactic sugars, which is very small. These are the only things you can do in the core language:
- Define a one-parameter function with the arrow operator:
(x -> body)
- Call a one-parameter function by putting a space between the function name
fand the argument
- Refer to the parameter of a function by name:
- Refer to an integer:
- Refer to a built-in operator:
For example, we can combine all of these to write a function that returns its argument plus one (just ignore the parentheses around the plus sign; they are to disable a syntactic sugar):
(x -> (((+) x) 1))
Note that you can construct a function that effectively takes two parameters by making a one-parameter function that returns a one-parameter function, so that it takes two function applications to get to the body. This is the concept of currying. For example, to make a function that adds two arguments:
(x -> (y -> (((+) x) y)))
The desugared language can be described by the grammar rules below (technically the desugared language is a sublanguage of expr because this grammar ignores some error cases):
natural = [0-9]+ builtin = '+' | '-' | '*' | '//' | '%' | '=' | '=/=' | '<' | '>' | '<=' | '>=' | 'up' | 'error' name = ("a token that is not a natural, builtin, delimiter, or arrow") expr = natural | builtin | name | (name -> expr) | (expr expr)
x, y, z be generic expressions,
f be a name expression, and
an operator name expression.
- Left associative spaces:
x y zdesugars to
((x y) z)
- Right associative newlines:
x \n y \n zdesguars to
(z (y z))
- Redundant Parentheses:
xis an operator (see Operator names sugar below)
- Definitions (Let expressions):
(f := x) ydesugars to
(f -> y) x
- Trailing definitions:
(x (f := y))desguars to
(x ((f := y) f))If there is nothing after a definition, it as treated as if the name of the definition follows the definition.
- Function definitions:
f x y := zdesugars to
f := x -> y -> z
- Recursive definitions: The right hand sise of a function definition can refer to the function name, in which case the Y combinator is used to convert the definition to a non-recursive one.
- Curried function application:
f(x, y)desugars to
f x y
- Infix operators:
x * ydesugars to
* x yWhen operators are chained like
x * y * zthere are precedence and associatvitiy rules that determine how it is parsed.
- Operator names:
(*)disables the infix operator sugar on
(* y)desguars to
x -> (x * y)and
(y *)desugars to
x -> (y * x)
- String literals:
"abc"desugars to a Church-encoded list of ascii character codes.
- Character literals:
'a'desugars to the ascii character code for
- List literals:
[x, y, z]desugars to the Church-encoded list of
- Tuple destructuring:
(a, b, c) := xdesugars to the equivalent of
a := first(x),
b := second(x), and
c := third(x). Tuples can also be used on the left side of
->and in parameters on the left side of function definitions. Destructuring is also recursive e.g.
((a, b), (c, d)) := x.
There is no I/O in the lambda zero language, but there is some basic I/O
support in the lambda zero interpreter. In other words, there is no
syntax in a lamda zero program that actually performs I/O itself, but there is a
main that the interpreter treats differently to allow I/O.
When the last function definition of a program defines the symbol
interpreter assumes that it is a function and passes it a string corresponding
stdin and then assumes that the return value of
main is a string and
prints it to
stdout. An error will occur if these assumptions aren't true.
A string is a linked list of integers in the range 0-255, where the linked list is constructed according to the standard Church encoding.
The input and output are both evaluated lazily, which allows for non-terminating output and interactive programs. See the samples below for examples of this.
That's the whole language! Take a look at the prelude for more examples.
Make sure gcc and bash are installed and run the
make script in the
cd to the bootstrap-interpreter directory.
For example, try this sample program that prints out an infinite list of prime numbers:
This sample program runs an interactive REPL that reverses each line entered:
run script prepends the prelude to the
passes the result to
Note that when using the
run script, line numbers in error messages will be
offset by the number of lines in the prelude.
Lambda Zero is in version 0.x, so breaking changes can be made in any commit.