A stack-based untyped lambda calculus evaluator. Includes booleans and integers as primitive terms (not Church-encoded), as well as a conditional construct.
This is a weekend hobby project for practicing C hacking and some components of compiler implementation. More testing is needed to verify correctness. A useful "front-end" would be a parser for text files to speed-up test writing.
The algorithm deployed here uses a standard AST encoding for C, with tagged unions and pointers to structs for child nodes. Redexes are pushed on the stack, and pushed again if they contain further redexes. Reduction steps are done in-place, so there is some structure sharing that reduces work duplication. I have to analyze more closely, but I believe this is still sub-optimal in the sense of Lamping 1990.