LambdaCalculus 1.0.0-lambda

.NET 5.0 This package targets .NET 5.0. The package is compatible with this framework or higher.
This is a prerelease version of LambdaCalculus. 
dotnet add package LambdaCalculus --version 1.0.0-lambda
                    


                    

                
NuGet\Install-Package LambdaCalculus -Version 1.0.0-lambda
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package. 
<PackageReference Include="LambdaCalculus" Version="1.0.0-lambda" />
For projects that support PackageReference, copy this XML node into the project file to reference the package. 
<PackageVersion Include="LambdaCalculus" Version="1.0.0-lambda" />
                    


                            Directory.Packages.props
                        

                    

                
<PackageReference Include="LambdaCalculus" />
                    


                            Project file
For projects that support Central Package Management (CPM), copy this XML node into the solution Directory.Packages.props file to version the package. 
paket add LambdaCalculus --version 1.0.0-lambda
                    


                    

                
#r "nuget: LambdaCalculus, 1.0.0-lambda"
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package. 
#:package LambdaCalculus@1.0.0-lambda
#:package directive can be used in C# file-based apps starting in .NET 10 preview 4. Copy this into a .cs file before any lines of code to reference the package. 
#addin nuget:?package=LambdaCalculus&version=1.0.0-lambda&prerelease
                    


                            Install as a Cake Addin
                        

                    

                
#tool nuget:?package=LambdaCalculus&version=1.0.0-lambda&prerelease
                    


                            Install as a Cake Tool

λ 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 single-character lower-case 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 left-sided: 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 x
  • xy - y applied to x
  • \x.x - an identity
  • \x.xx - a lambda which returns its only parameter applied to itself
  • (\x.x)y - y applied to identity (will return y after beta reduction)
  • (\x.xx)(\x.xx) - simple example of beta-irreducible 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 beta-reduction, 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 names
  • substitute: 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 alpha-convert 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, for-loops. The logic is implemented with recursion, pattern matching, and computation expressions.

Product Compatible and additional computed target framework versions.
.NET net5.0 is compatible.  net5.0-windows was computed.  net6.0 was computed.  net6.0-android was computed.  net6.0-ios was computed.  net6.0-maccatalyst was computed.  net6.0-macos was computed.  net6.0-tvos was computed.  net6.0-windows was computed.  net7.0 was computed.  net7.0-android was computed.  net7.0-ios was computed.  net7.0-maccatalyst was computed.  net7.0-macos was computed.  net7.0-tvos was computed.  net7.0-windows was computed.  net8.0 was computed.  net8.0-android was computed.  net8.0-browser was computed.  net8.0-ios was computed.  net8.0-maccatalyst was computed.  net8.0-macos was computed.  net8.0-tvos was computed.  net8.0-windows was computed.  net9.0 was computed.  net9.0-android was computed.  net9.0-browser was computed.  net9.0-ios was computed.  net9.0-maccatalyst was computed.  net9.0-macos was computed.  net9.0-tvos was computed.  net9.0-windows was computed.  net10.0 was computed.  net10.0-android was computed.  net10.0-browser was computed.  net10.0-ios was computed.  net10.0-maccatalyst was computed.  net10.0-macos was computed.  net10.0-tvos was computed.  net10.0-windows was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.

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.0-lambda 333 8/14/2021

First release