Skip to content

Latest commit

 

History

History
61 lines (45 loc) · 1.56 KB

README.md

File metadata and controls

61 lines (45 loc) · 1.56 KB
Raw

lambda-calculus

Lambda calculus is the God's Programming language, so I wrote an interpreter for it. This interpreter is an extension to the original lambda caculus as described here.

Pre-requisites

  • cabal

Extensions

  • Number and Booleans can be encoded in pure lambda calculus but for convenience they have been made primitives.

  • General operators related to Int and Bool have been added as well.

Added Types:

  • Int, literals are constructors
  • Bool, true and false constructors

Added Operators

  • (+) :: Int -> Int -> Int
  • (-) :: Int -> Int -> Int
  • (*) :: Int -> Int -> Int
  • (/) :: Int -> Int -> Int
  • (and) :: Bool -> Bool -> Bool
  • (or) :: Bool -> Bool -> Bool
  • not :: Bool -> Bool
  • (>) :: a -> a -> Bool
  • (<) :: a -> a -> Bool
  • (=) :: a -> a -> Bool

Things you can do

We can define most all of the extensions, that I added to the language. In fact most modern functional languages compile down to some form of lambda calculus.

true := \x.\y.x -- true literal defined in pure lambda calculus
false := lambda x.lambda y. y

and := \p.\q.p q p
or := lambda p.lambda q.p p q

0 := \f.\x.x
1 := lambda f.lambda x.f x
2 := \f.\x. f ( f x )

REPL

You can try out the examples above in the repl. cabal new-run, will open the repl

λ (((\p.\q.p q p)\x.\y.x)\x.\y.y)
\y.y
λ (((\p.\q.p p q)\x.\y.x)\x.\y.y)
\y.x