Lambda Calculus System
Last edited: July 31, 2023 - 1 minute read
Description
Content
The code used in this post can be found here: http://github.com/Fraguinha/Lambda.
Lambda Calculus
At it’s core, Lambda Calculus is composed of three elements: variables
, abstractions
, and applications
.
Variables are
placeholders that represent an unknown value or lambda term
. They are typicallyrepresented by a single lowercase letter
.Abstractions are
expressions that define a function
. They consist of alambda, followed by a variable, followed by a dot, followed by a lambda term
. e.g.:λx.x
is anabstraction
thatdefines a function
thattakes x
andreturns x
.Applications are
expressions that apply a function to an argument
. They consist oftwo lambda terms separated by a space
. Theleft term
is thefunction to be applied
, and theright term
is theargument to which the function will be applied
. e.g.:(λx.x) y
is anapplication
thatapplies the function λx.x
to theargument y
.
Playground
Syntax
x
or x'
λx.M
or \x.M
M N
where M
and N
are lambda terms
This interpreter supports sintatic sugar like:
λxyz.M
instead of λx.(λy.(λz.M))
and
M N O
instead of ((M N) O)
Terms can be defined in this way:
Y=λf.(λx.f(xx))(λx.f(xx))
or
S=λxyz.xz(yz); K=λxy.x; I=λx.x
or even
TRUE=λxy.x
Statements are separated by semicolons