Lambda calculus interpreter in ZIG (no deps)

dependencies: zig 0.16

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.

Compile with

const lambda_debug = true;

to emit debug logs during parsing.

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)