Skip to content

A small normalizer for lambda calculus, implementing (almost) everything from scratch.

License

Notifications You must be signed in to change notification settings

phipsgabler/mini-lambda

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

19 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

No Maintenance Intended

Mini-Lambda

The initial purpose of this project was just to try setting up a real-world Haskell project with stack, cleanly written and tested.

It ended up in an interesting task of understanding and implementing a normalizer for the untyped lambda calculus.

Usage

There is a command-line interface to the normalizer, which can most easily be accessed via stack exec mini-lambda. Currently, this does only run the full reduction and prints the result. The syntax is defined as follows:

EXPR = VAR
  | "(" LAMBDA VAR "." EXPR ")"
  | "(" EXPR EXPR ")"
LAMBDA = "λ" | "\\"  (a single backspace)
VAR = (['!'..'\''] | ['*'..'-'] | ['/'..'['] | [']'..'~'])+

This means that every lambda and every application have to be fully parenthesized -- this might get improved in the future. For more details, see Parser.hs (the parser combinator used is self-written, just for fun, so there's poor error handling).

About

A small normalizer for lambda calculus, implementing (almost) everything from scratch.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published