LambdaCalculus 1.0.0lambda
InstallPackage LambdaCalculus Version 1.0.0lambda
dotnet add package LambdaCalculus version 1.0.0lambda
<PackageReference Include="LambdaCalculus" Version="1.0.0lambda" />
paket add LambdaCalculus version 1.0.0lambda
#r "nuget: LambdaCalculus, 1.0.0lambda"
// Install LambdaCalculus as a Cake Addin
#addin nuget:?package=LambdaCalculus&version=1.0.0lambda&prerelease
// Install LambdaCalculus as a Cake Tool
#tool nuget:?package=LambdaCalculus&version=1.0.0lambda&prerelease
λ calculus in F#
Fun library for lambda calculus made purely in F#. It has a web app made for demonstration.
Syntax of λcalculus
Rules:
 Variables are singlecharacter lowercase Latin letters.
 Lambda starts with
\
, then is followed by 1 or more variable, then a dot (.
), then expression. Until wrapped with parentheses, the body of a lambda has a lower priority than()
(e. g.\x.(x)(y)
is the same as(\x.x)(y)
).  Associativity is leftsided:
xyz
is(xy)z
.  A nested lambda can be shortcuted:
\x.\y.\z.xyz
is the same as\xyz.xyz
.  Symbol
λ
can be used instead of\
, but is not essential.
Examples:
x
 an expression of one free variable xxy
y
applied tox
\x.x
 an identity\x.xx
 a lambda which returns its only parameter applied to itself(\x.x)y
y
applied to identity (will returny
after beta reduction)(\x.xx)(\x.xx)
 simple example of betairreducible expression
Library API
Expression is defined as following:
type Expression =
 Variable of char
 Lambda of Head : Variable * Body : Expression
 Applied of Lambda : Expression * Argument : Expression
in LambdaCalculus.Atoms
.
In the same module LambdaCalculus.Atoms
there are
betaReduce
orβReduce
:Expression > Expression
performs betareduction, that is, simplification of an expression (starting from bottom, replaces parameters of lambdas in their bodies with the applied expressions)alphaEqual
orαEqual
:Expression > Expression > Expression
compares two expressions up to lambdas parameter namessubstitute
:char > Expression > Expression > Expression
replaces the given variable with a given expression. In case of conflicts between it and a local variable in a lambda, it will alphaconvert the lambda's parameter to a new name.
In the module LambdaCalculus.Parsing
there is parse
which takes a string as an argument, and returns a Result
of
Expression
and string
.
Fun facts
The library is made in pure functional programming. Even the parser has no exceptions, early returns, forloops. The logic is implemented with recursion, pattern matching, and computation expressions.

net5.0
 FSharp.Core (>= 5.0.0)
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.
Version  Downloads  Last updated 

1.0.0lambda  46  8/14/2021 
First release