Lambda calculus interpreter in ZIG (no deps)

dependencies: zig 0.17

Compiling and running tests for various targets

Nothing project specific, this is just what zig can do. more of a reminder for myself:

If you have wasmtime installed, you can run zig build test -fwasmtime -Doptimize=ReleaseFast -Dtarget=wasm32-wasi-musl

If you have qemu you can try the weird archs: zig build run -fwasmtime -Doptimize=ReleaseFast -Dtarget=wasm32-wasi-musl

Both run and test and bare build should work!

Library Usage

Check "normal" test and main for sample usage:

var p = Parser{ .src = "((λx.(λk.k)x)y)", .alloc = std.testing.allocator };

const parsed = try p.parse();
defer {
    parsed.deinit(std.testing.allocator);
}
const reduced: *AST = try parsed.normal(std.testing.allocator);
defer {
    reduced.deinit(std.testing.allocator);
    std.testing.allocator.destroy(reduced);
}

const str = try std.fmt.allocPrint(std.testing.allocator, "{f}", .{reduced.*});
defer std.testing.allocator.free(str);

Make a parser with a string and allocator of your liking, call parse().

Several parsers available:

Parser

Parses bare lambda expression and provides AST type with .eval, subst and normal methods. All AST methods work make copies and do not mutate anything. Sometimes they do useless temporary allocations. All AST methods returning a pointer expect you to .deinit() and free the pointer manually.

EnvParser

Parses bare lambdas and <ident> = <bare lambda> and saves it in and env. Provides a .resolve() method to substitute all free variables found with an expr with definitions from the env, if possible.

Cli

git clone <this repo> && cd <this repo>
zig build run

Type in your lambda expression and see how it's parsed + result.

Type:help for help message.

λ :help
Commands:
  :help => prints this message
  :env => prints environtment
  :load <path> => loads .lambda file
λ id = \x.x
id = (λx.x) -> (λx.x)

λ :env
id: (λx.x)

λ :load src/stdlib.lambda
Loaded 24 definitions
λ :env
not: (λp.((p (λx.(λy.y))) (λx.(λy.x))))
3: (λf.(λx.(f (f (f x)))))
0: (λf.(λx.x))
4: (λf.(λx.(f (f (f (f x))))))
1: (λf.(λx.(f x)))
pred: (λn.(λf.(λx.(((n (λr.(λi.(i (r f))))) (λf.x)) (λx.x)))))
or: (λp.(λq.((p p) q)))
add: (λm.(λn.(λf.(λx.((m f) ((n f) x))))))
id: (λx.x)
and: (λp.(λq.((p q) p)))
mul: (λm.(λn.(λf.(λx.((m (n f)) x)))))
2: (λf.(λx.(f (f x))))
if: (λb.(λtrue.(λfalse.((b true) false))))
false: (λx.(λy.y))
minus: (λm.(λn.((n (λn.(λf.(λx.(((n (λr.(λi.(i (r f))))) (λf.x)) (λx.x)))))) m)))
leq: (λm.(λn.((((n (λn.(λf.(λx.(((n (λr.(λi.(i (r f))))) (λf.x)) (λx.x)))))) m) (λx.(λx.(λy.y)))) (λx.(λy.x)))))
5: (λf.(λx.(f (f (f (f (f x)))))))
test: (λc.((c TRUE) FALSE))
<...>

TODO:

• Evaluate with env
• Proper CLI (show env, display steps, etc)
• Feature parity with haskell version
• Polish debug features (set debug callback for library users, not logging)