I’m trying to write (for the fun of it) a Lambda Calculus interpreter. So far, I can
Add, Mult, and do Exponentiation using Church numbers.
Module Program
' Define node types using classes for Lambda Calculus expressions
MustInherit Class Node
Public MustOverride Overrides Function ToString() As String
End Class
Class Lambda
Inherits Node
Public Property Parameter As String
Public Property Body As Node
Public Sub New(param As String, body As Node)
Me.Parameter = param
Me.Body = body
End Sub
Public Overrides Function ToString() As String
Return $"λ{Parameter}.{Body}"
End Function
End Class
Class Apply
Inherits Node
Public Property FunctionPart As Node
Public Property ArgumentPart As Node
Public Sub New(func As Node, arg As Node)
Me.FunctionPart = func
Me.ArgumentPart = arg
End Sub
Public Overrides Function ToString() As String
Return $"({FunctionPart} {ArgumentPart})"
End Function
End Class
Class Var
Inherits Node
Public Property Name As String
Public Sub New(name As String)
Me.Name = name
End Sub
Public Overrides Function ToString() As String
Return Name
End Function
End Class
' Function to generate a fresh variable name to avoid clashes
Function FreshVariable(base As String, avoid As HashSet(Of String)) As String
Dim newVar = base
Dim counter = 1
While avoid.Contains(newVar)
newVar = base & counter
counter += 1
End While
avoid.Add(newVar)
Return newVar
End Function
' Function to rename a bound variable (Alpha Conversion)
Function Rename(body As Node, oldName As String, newName As String) As Node
Select Case True
Case TypeOf body Is Var
Dim var = CType(body, Var)
If var.Name = oldName Then
Return New Var(newName)
Else
Return var
End If
Case TypeOf body Is Lambda
Dim lambda = CType(body, Lambda)
If lambda.Parameter = oldName Then
' No need to rename inside the lambda if it's the same parameter
Return New Lambda(lambda.Parameter, lambda.Body)
Else
Dim newBody = Rename(lambda.Body, oldName, newName)
Return New Lambda(lambda.Parameter, newBody)
End If
Case TypeOf body Is Apply
Dim apply = CType(body, Apply)
Dim newFunc = Rename(apply.FunctionPart, oldName, newName)
Dim newArg = Rename(apply.ArgumentPart, oldName, newName)
Return New Apply(newFunc, newArg)
Case Else
Return body
End Select
End Function
' Function to detect free variables in a lambda expression
Function FreeVariables(expr As Node) As HashSet(Of String)
Dim freeVars As New HashSet(Of String)
Select Case True
Case TypeOf expr Is Var
freeVars.Add(CType(expr, Var).Name)
Case TypeOf expr Is Lambda
Dim lambda = CType(expr, Lambda)
Dim bodyFreeVars = FreeVariables(lambda.Body)
bodyFreeVars.Remove(lambda.Parameter)
freeVars.UnionWith(bodyFreeVars)
Case TypeOf expr Is Apply
Dim apply = CType(expr, Apply)
freeVars.UnionWith(FreeVariables(apply.FunctionPart))
freeVars.UnionWith(FreeVariables(apply.ArgumentPart))
End Select
Return freeVars
End Function
' Function to substitute a variable in a lambda expression with alpha conversion
Function Substitute(body As Node, parameter As String, argument As Node, avoid As HashSet(Of String)) As Node
Select Case True
Case TypeOf body Is Var
Dim var = CType(body, Var)
If var.Name = parameter Then
Return argument
Else
Return var
End If
Case TypeOf body Is Lambda
Dim lambda = CType(body, Lambda)
If lambda.Parameter = parameter Then
' No substitution needed if parameter is shadowed
Return lambda
Else
' Check for variable name clashes and perform alpha conversion
If FreeVariables(argument).Contains(lambda.Parameter) Then
Dim newParam = FreshVariable(lambda.Parameter, avoid)
Dim newBody = Rename(lambda.Body, lambda.Parameter, newParam)
lambda = New Lambda(newParam, newBody)
End If
' Substitute in the body of the lambda
Dim substitutedBody = Substitute(lambda.Body, parameter, argument, avoid)
Return New Lambda(lambda.Parameter, substitutedBody)
End If
Case TypeOf body Is Apply
Dim apply = CType(body, Apply)
' Substitute in both function and argument parts
Dim newFunc = Substitute(apply.FunctionPart, parameter, argument, avoid)
Dim newArg = Substitute(apply.ArgumentPart, parameter, argument, avoid)
Return New Apply(newFunc, newArg)
Case Else
Return body
End Select
End Function
' Function to reduce a lambda expression with cycle detection and alpha conversion
Function Reduce(node As Node, debug As Boolean, sharedNodes As Dictionary(Of Node, Node), visitedNodes As HashSet(Of String), recursionCount As Dictionary(Of String, Integer), Optional depth As Integer = 0) As Node
If debug Then
Console.WriteLine($"[Reduce] Reducing: {node}")
End If
' Define a maximum depth to prevent excessive recursion
Dim maxDepth As Integer = 100
Dim maxRecursion As Integer = 20
If depth > maxDepth Then
If debug Then
Console.WriteLine("[Reduce] Max recursion depth reached, returning 'Infinite loop or recursion'.")
End If
Return New Var("Infinite loop or recursion")
End If
' If node is shared, return the already computed result
If sharedNodes.ContainsKey(node) Then
Return sharedNodes(node)
End If
' Check for infinite recursion using visited nodes
Dim nodeId As String = node.ToString()
If visitedNodes.Contains(nodeId) Then
If Not recursionCount.ContainsKey(nodeId) Then
recursionCount(nodeId) = 0
End If
recursionCount(nodeId) += 1
If recursionCount(nodeId) > maxRecursion Then
If debug Then
Console.WriteLine("[Reduce] Infinite recursion detected, returning 'Infinite loop or recursion'.")
End If
Return New Var("Infinite loop or recursion")
End If
Else
visitedNodes.Add(nodeId)
End If
' Handle different types of nodes
Select Case True
Case TypeOf node Is Apply
Dim apply = CType(node, Apply)
Dim func = Reduce(apply.FunctionPart, debug, sharedNodes, visitedNodes, recursionCount, depth + 1)
If func.ToString() = "Infinite loop or recursion" Then
Return func
End If
Dim arg = Reduce(apply.ArgumentPart, debug, sharedNodes, visitedNodes, recursionCount, depth + 1)
If arg.ToString() = "Infinite loop or recursion" Then
Return arg
End If
If TypeOf func Is Lambda Then
Dim lambda = CType(func, Lambda)
' Prepare avoid set for alpha conversion
Dim avoid As New HashSet(Of String)(FreeVariables(arg))
avoid.UnionWith(FreeVariables(lambda.Body))
avoid.Add(lambda.Parameter)
Dim reducedBody = Substitute(lambda.Body, lambda.Parameter, arg, avoid)
If reducedBody.ToString() = "Infinite loop or recursion" Then
Return New Var("Infinite loop or recursion")
End If
visitedNodes.Remove(nodeId)
sharedNodes(node) = reducedBody
Return Reduce(reducedBody, debug, sharedNodes, visitedNodes, recursionCount, depth + 1)
Else
' Handling deferred application for self-application and other cases
If TypeOf func Is Var AndAlso func.ToString() = arg.ToString() Then
Return New Apply(func, arg)
End If
sharedNodes(node) = New Apply(func, arg)
visitedNodes.Remove(nodeId)
Return sharedNodes(node)
End If
Case TypeOf node Is Lambda
Dim lambda = CType(node, Lambda)
Dim reducedBody = Reduce(lambda.Body, debug, sharedNodes, visitedNodes, recursionCount, depth + 1)
If reducedBody.ToString() = "Infinite loop or recursion" Then
Return New Var("Infinite loop or recursion")
End If
sharedNodes(node) = New Lambda(lambda.Parameter, reducedBody)
visitedNodes.Remove(nodeId)
Return sharedNodes(node)
Case Else
sharedNodes(node) = node
visitedNodes.Remove(nodeId)
Return node
End Select
End Function
' Function to convert a Church numeral to an integer
Function ChurchNumeralToInteger(churchNumeral As Node) As Integer
Dim current As Node = churchNumeral
' We expect the structure λf.λx.(f (f ... (f x)...)) where the number of applications of 'f' to 'x' is the numeral value.
If TypeOf current Is Lambda Then
current = CType(current, Lambda).Body
If TypeOf current Is Lambda Then
current = CType(current, Lambda).Body
Dim count As Integer = 0
While TypeOf current Is Apply
count += 1
current = CType(current, Apply).ArgumentPart
End While
Return count
End If
End If
Return 0 ' Not a valid Church numeral if it doesn't match the expected structure
End Function
' Function to create a Church numeral for a given integer
Function ChurchNumeral(n As Integer) As Node
Dim zero As New Lambda("f", New Lambda("x", New Var("x")))
Dim succ As New Lambda("n", New Lambda("f", New Lambda("x", New Apply(New Var("f"), New Apply(New Apply(New Var("n"), New Var("f")), New Var("x"))))))
Dim numeral As Node = zero
For i As Integer = 1 To n
numeral = New Apply(succ, numeral)
Next
Return numeral
End Function
' Function to add two Church numerals
Function ChurchAddition() As Node
Return New Lambda("m", New Lambda("n", New Lambda("f", New Lambda("x", New Apply(New Apply(New Var("m"), New Var("f")), New Apply(New Apply(New Var("n"), New Var("f")), New Var("x")))))))
End Function
' Function to multiply two Church numerals
Function ChurchMultiplication() As Node
Return New Lambda("m", New Lambda("n", New Lambda("f", New Apply(New Var("m"), New Apply(New Var("n"), New Var("f"))))))
End Function
' Function to exponentiate two Church numerals
Function ChurchExponentiation() As Node
Return New Lambda("m", New Lambda("n", New Apply(New Var("n"), New Var("m"))))
End Function
' Test case class
Class TestCase
Public Property Expression As Node
Public Property Expected As String
Public Property IsChurchTest As Boolean
Public Sub New(expression As Node, expected As String, Optional isChurchTest As Boolean = False)
Me.Expression = expression
Me.Expected = expected
Me.IsChurchTest = isChurchTest
End Sub
End Class
' Main function to run the test cases
Sub Main()
' Toggle this to enable or disable debug printing
Dim debug As Boolean = False
Dim testCases = New List(Of TestCase) From {
New TestCase(New Apply(New Apply(ChurchAddition(), ChurchNumeral(2)), ChurchNumeral(3)), "5", True),
New TestCase(New Apply(New Apply(ChurchAddition(), ChurchNumeral(0)), ChurchNumeral(4)), "4", True),
New TestCase(New Apply(New Apply(ChurchAddition(), ChurchNumeral(5)), ChurchNumeral(0)), "5", True),
New TestCase(New Apply(New Apply(ChurchMultiplication(), ChurchNumeral(2)), ChurchNumeral(3)), "6", True),
New TestCase(New Apply(New Apply(ChurchMultiplication(), ChurchNumeral(4)), ChurchNumeral(0)), "0", True),
New TestCase(New Apply(New Apply(ChurchMultiplication(), ChurchNumeral(0)), ChurchNumeral(5)), "0", True),
New TestCase(New Apply(New Apply(ChurchExponentiation(), ChurchNumeral(2)), ChurchNumeral(3)), "8", True), ' 2^3 = 8
New TestCase(New Apply(New Apply(ChurchExponentiation(), ChurchNumeral(3)), ChurchNumeral(2)), "9", True), ' 3^2 = 9
New TestCase(New Apply(New Apply(ChurchExponentiation(), ChurchNumeral(5)), ChurchNumeral(0)), "0", True), ' 5^0 = 1
New TestCase(New Apply(New Apply(ChurchExponentiation(), ChurchNumeral(0)), ChurchNumeral(3)), "0", True) ' 0^3 = 0
}
Console.OutputEncoding = System.Text.Encoding.UTF8
Dim sharedNodes As New Dictionary(Of Node, Node)()
Dim passedCount As Integer = 0
Dim failedCount As Integer = 0
For Each testCase In testCases
Try
Dim visitedNodes As New HashSet(Of String)()
Dim recursionCount As New Dictionary(Of String, Integer)()
Dim result = Reduce(testCase.Expression, debug, sharedNodes, visitedNodes, recursionCount)
Dim actual As String
If testCase.IsChurchTest Then
Dim actualInt = ChurchNumeralToInteger(result)
Dim expectedInt = Integer.Parse(testCase.Expected)
Dim pass As Boolean = (actualInt = expectedInt)
If pass Then
passedCount += 1
Console.WriteLine($"Church Test Case {passedCount + failedCount}: Evaluating Expression: {testCase.Expression}")
Console.WriteLine($"Expression: {testCase.Expression}, Expected: {expectedInt}, Actual: {actualInt}, Pass: True")
Else
failedCount += 1
Console.WriteLine($"Church Test Case {passedCount + failedCount}: Evaluating Expression: {testCase.Expression}")
Console.WriteLine($"Expression: {testCase.Expression}, Expected: {expectedInt}, Actual: {actualInt}, Pass: False")
End If
Else
actual = result.ToString()
Dim expected As String = testCase.Expected
Dim pass As Boolean = (actual = expected)
If pass Then
passedCount += 1
Else
failedCount += 1
End If
Console.WriteLine($"Test Case {passedCount + failedCount}: Evaluating Expression: {testCase.Expression}")
Console.WriteLine($"Expression: {testCase.Expression}, Expected: {expected}, Actual: {actual}, Pass: {pass}")
End If
Console.WriteLine("--------------------------------------------------")
Catch ex As Exception
Console.WriteLine($"Test Case {passedCount + failedCount}: Evaluating Expression: {testCase.Expression}")
Console.WriteLine($"Exception occurred: {ex.Message}")
Console.WriteLine("--------------------------------------------------")
failedCount += 1
End Try
Next
End Sub
End Module
Now I’m trying to implement recursion in the interpreter using Y combinators. I have not been successful doing that at all. I believe the problem is in the evaluation function as it never resolves correctly and generates the correct Church numbers. Could somebody take a look at this and give me some suggestions regarding the evaluation?
using System;
namespace LambdaCalculus
{
abstract record Node
{
public abstract override string ToString();
}
record Lambda(string Parameter, Node Body) : Node
{
public override string ToString() => $"λ{Parameter}.{Body}";
}
record Apply(Node FunctionPart, Node ArgumentPart) : Node
{
public override string ToString() => $"({FunctionPart} {ArgumentPart})";
}
record Var(string Name) : Node
{
public override string ToString() => Name;
}
class Program
{
static void Main(string[] args)
{
bool debug = true;
Node Y = YCombinator();
Node Sum = new Apply(Y, SumLambda());
var sumTestCases = new List<TestCase>
{
new TestCase(new Apply(Sum, ChurchNumeral(0)), "0", true),
new TestCase(new Apply(Sum, ChurchNumeral(1)), "1", true),
new TestCase(new Apply(Sum, ChurchNumeral(2)), "3", true),
new TestCase(new Apply(Sum, ChurchNumeral(3)), "6", true),
new TestCase(new Apply(Sum, ChurchNumeral(10)), "55", true)
};
Console.WriteLine("nTesting sum function:");
RunTestCases(sumTestCases, debug);
}
static bool IsValue(Node node)
{
return node is Lambda;
}
static Node Evaluate(Node node, bool debug = false, int maxDepth = 100, Dictionary<Node, Node> memo = null)
{
Stack<(Node, int)> evalStack = new Stack<(Node, int)>();
evalStack.Push((node, 0));
memo ??= new Dictionary<Node, Node>();
while (evalStack.Count > 0)
{
(node, int depth) = evalStack.Pop();
if (debug)
{
Console.WriteLine($"Evaluating: {node} at depth {depth}");
}
if (depth > maxDepth)
{
if (debug)
{
Console.WriteLine($"Max recursion depth {maxDepth} exceeded, returning 'Infinite loop or recursion'.");
}
return new Var("Infinite loop or recursion");
}
if (memo.TryGetValue(node, out var memoizedResult))
{
if (debug)
{
Console.WriteLine($"Returning memoized result for {node}: {memoizedResult}");
}
return memoizedResult;
}
if (node is Apply apply)
{
if (IsValue(apply.FunctionPart) && IsValue(apply.ArgumentPart))
{
Node result = Substitute(apply.ArgumentPart, apply.FunctionPart as Lambda);
if (debug)
{
Console.WriteLine($"After substitution: {result}");
}
evalStack.Push((result, depth + 1));
}
else
{
// Push the components back for further evaluation
if (!IsValue(apply.FunctionPart))
{
evalStack.Push((apply, depth));
evalStack.Push((apply.FunctionPart, depth + 1));
}
else if (!IsValue(apply.ArgumentPart))
{
evalStack.Push((apply, depth));
evalStack.Push((apply.ArgumentPart, depth + 1));
}
}
}
else if (IsValue(node))
{
if (debug)
{
Console.WriteLine($"Reached a value: {node}");
}
memo[node] = node;
return node;
}
else
{
if (debug)
{
Console.WriteLine($"Non-application and non-lambda value encountered: {node}");
}
memo[node] = node;
return node;
}
}
return node; // Final evaluated result
}
static Node Substitute(Node value, Lambda lambda)
{
return Substitute(value, lambda.Parameter, lambda.Body);
}
static Node Substitute(Node value, string parameter, Node body)
{
if (value == null) throw new ArgumentNullException(nameof(value));
if (parameter == null) throw new ArgumentNullException(nameof(parameter));
if (body == null) throw new ArgumentNullException(nameof(body));
if (value is Lambda)
{
// Prevent infinite loops with recursive functions
if (body is Var v && v.Name == parameter)
{
return value;
}
}
if (body is Var var)
{
if (var.Name == parameter)
{
return value;
}
return var;
}
else if (body is Apply apply)
{
var newFunc = Substitute(value, parameter, apply.FunctionPart);
var newArg = Substitute(value, parameter, apply.ArgumentPart);
return new Apply(newFunc, newArg);
}
else if (body is Lambda innerLambda)
{
if (innerLambda.Parameter == parameter)
{
return new Lambda(innerLambda.Parameter, innerLambda.Body); // No substitution
}
else
{
return new Lambda(innerLambda.Parameter, Substitute(value, parameter, innerLambda.Body));
}
}
else
{
throw new InvalidOperationException("Unknown node type");
}
}
static Node YCombinator()
{
return new Lambda("f", new Apply(new Lambda("x", new Apply(new Var("f"), new Apply(new Var("x"), new Var("x")))), new Lambda("x", new Apply(new Var("f"), new Apply(new Var("x"), new Var("x"))))));
}
static Node SumLambda()
{
Node zero = ChurchNumeral(0);
Node succ = new Lambda("n", new Lambda("f", new Lambda("x", new Apply(new Var("f"), new Apply(new Apply(new Var("n"), new Var("f")), new Var("x"))))));
Node add = new Lambda("m", new Lambda("n", new Lambda("f", new Lambda("x", new Apply(new Apply(new Var("m"), new Var("f")), new Apply(new Apply(new Var("n"), new Var("f")), new Var("x")))))));
return new Lambda("f", new Lambda("n",
new Apply(
new Apply(
new Apply(IsZero(), new Var("n")),
zero
),
new Apply(
new Apply(add, new Var("n")),
new Apply(new Var("f"), new Apply(succ, new Var("n")))
)
)
));
}
static Node IsZero()
{
return new Lambda("n", new Apply(new Apply(new Var("n"), new Lambda("x", ChurchFalse())), ChurchTrue()));
}
static Node ChurchTrue()
{
return new Lambda("t", new Lambda("f", new Var("t")));
}
static Node ChurchFalse()
{
return new Lambda("t", new Lambda("f", new Var("f")));
}
static Node ChurchNumeral(int n)
{
Node zero = new Lambda("f", new Lambda("x", new Var("x")));
Node succ = new Lambda("n", new Lambda("f", new Lambda("x", new Apply(new Var("f"), new Apply(new Apply(new Var("n"), new Var("f")), new Var("x"))))));
Node result = zero;
for (int i = 0; i < n; i++)
{
result = new Apply(succ, result);
}
return result;
}
static void RunTestCases(List<TestCase> testCases, bool debug)
{
int passedCount = 0;
int failedCount = 0;
foreach (var testCase in testCases)
{
try
{
var memo = new Dictionary<Node, Node>();
Node result = Evaluate(testCase.Expression, debug, 100, memo);
string actual;
if (testCase.IsChurchTest)
{
int actualInt = ChurchNumeralToInteger(result);
int expectedInt = int.Parse(testCase.Expected);
bool pass = (actualInt == expectedInt);
if (pass)
{
passedCount++;
Console.WriteLine($"Church Test Case {passedCount + failedCount + 1}: Evaluating Expression: {testCase.Expression}");
Console.WriteLine($"Final Reduced Form: {result}");
Console.WriteLine($"Expression: {testCase.Expression}, Expected: {expectedInt}, Actual: {actualInt}, Pass: True");
}
else
{
failedCount++;
Console.WriteLine($"Church Test Case {passedCount + failedCount + 1}: Evaluating Expression: {testCase.Expression}");
Console.WriteLine($"Final Reduced Form: {result}");
Console.WriteLine($"Expression: {testCase.Expression}, Expected: {expectedInt}, Actual: {actualInt}, Pass: False");
}
}
else
{
actual = result.ToString();
string expected = testCase.Expected;
bool pass = (actual == expected);
if (pass)
{
passedCount++;
}
else
{
failedCount++;
}
Console.WriteLine($"Test Case {passedCount + failedCount + 1}: Evaluating Expression: {testCase.Expression}");
Console.WriteLine($"Final Reduced Form: {result}");
Console.WriteLine($"Expression: {testCase.Expression}, Expected: {expected}, Actual: {actual}, Pass: {pass}");
}
Console.WriteLine("--------------------------------------------------");
}
catch (Exception ex)
{
Console.WriteLine($"Test Case {passedCount + failedCount + 1}: Evaluating Expression: {testCase.Expression}");
Console.WriteLine($"Exception occurred: {ex.Message}");
Console.WriteLine("--------------------------------------------------");
failedCount++;
}
}
Console.WriteLine($"Total Test Cases Passed: {passedCount}");
Console.WriteLine($"Total Test Cases Failed: {failedCount}");
}
static int ChurchNumeralToInteger(Node numeral)
{
if (numeral is Lambda outerLambda && outerLambda.Body is Lambda innerLambda)
{
string param = innerLambda.Parameter;
Node body = innerLambda.Body;
int count = 0;
while (body is Apply apply && apply.FunctionPart is Var var && var.Name == param)
{
count++;
body = apply.ArgumentPart;
}
return count;
}
throw new ArgumentException("Not a valid Church numeral");
}
record TestCase(Node Expression, string Expected, bool IsChurchTest = false);
}
}