Lambda - Lambda Calculus System
Last edited: October 17, 2022 - 2 minutes read
Description
Content
The code used in this post can be found here: Lambda.
Lambda Calculus
At it’s core, Lambda Calculus
is composed of three elements: variables
, abstractions
, and applications
.
Variables
areplaceholders
that represent anunknown value
or alambda term
. They are typically represented by a singlelowercase letter
.Abstractions
are expressions thatdefine a function
. They consist of alambda
, followed by avariable
, followed by adot
, followed by alambda term
. i.e.:λx.x
is anabstraction
that defines afunction
thattakes x
andreturns x
.Applications
are expressions thatapply
afunction
to anargument
. 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. i.e.:(λ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