Archives
-
Lambda Calculus via C# (23) Y Combinator, And Divide
p is the fixed point of function F if and only if:
-
Lambda Calculus via C# (22) Iota Combinator and Jot Combinators
Iota is an esoteric programming language with minimum elements but still Turing-complete. Iota's universal combinator is:
-
Lambda Calculus via C# (21) SKI Combinator Calculus
The previous part shows SKI calculus is untyped and strongly typed C# implementation does not work. So here comes the SKI in untyped C#:
-
Lambda Calculus via C# (20) Combinators
As mentioned in a fundamental part, combinator is a special kind of lambda expression without free variables. So combinatory logic (introduced by Moses Schönfinkel and Haskell Curry) can be viewed as a variant of lambda calculus.
-
Lambda Calculus via C# (19) Church Encoding, And More
So far a ton has been encoded. Here is a summary.
-
Lambda Calculus via C# (18) Encoding Signed Number
In lambda calculus, a signed number (integer) can be represented by a Church pair (2-tuple) of Church numerals (natural numbers):
-
Lambda Calculus via C# (17) Encoding Church List with Fold (Aggregate) Function
A third way to encode Church list, is to use fold function (also called aggregate in C#/.NET):
-
Lambda Calculus via C# (16) Encoding Church List with 2 Church Pairs as a Node
Previous part encoded Church list with one Church pair (2-tuple) as a list node. An alternative way is to use 2 tuples as a node, one wrapping the other.
-
Lambda Calculus via C# (15) Encoding Church List with Church Pair, And Null
This part will demonstrate how to use lambda expressions to encode another data structure - list (Church list in lambda calculus or LinkedList<T> in .NET).
-
Lambda Calculus via C# (14) Church Pair (2-Tuple) and Church Numeral Decrease
In the Church numeral arithmetic part, the Decrease was defined as:
-
Lambda Calculus via C# (13) Encoding Church Pairs (2-Tuples) and Generic Church Booleans
Church pair is the Church encoding of the pair type, aka 2-tuple. Unlike the Tuple<T1, T2> class in .NET, in lambda calculus Church pair will be represented by lambda expression. To avoid 2 naming systems, here in all the code, Church pair will be called tuple.
-
Lambda Calculus via C# (12) Church Numeral Comparison Operators
With the predicates defined in previous part, operators can be defined in _Numeral class. Once again, class does not exist in lambda calculus, but C# class provides a place to define operators, which greatly improve the readability.
-
Lambda Calculus via C# (11) Predicates, And Divide
A predicate is a function that returns a Boolean value. In Church encoding of lambda calculus, a predicate is a lambda expression that returns a Church Boolean.
-
Lambda Calculus via C# (10) Church Numeral Arithmetic Operators
Another benefits of introducing (cheating with) _Numeral class into lambda calculus is - it provides a place to define custom operators.
-
Lambda Calculus via C# (9) Wrapping Church Numerals And Arithmetic
In previous part, the Decrease function was a Func<Numeral<Func<Func<T, T>, T>>, Numeral<T>>:
-
Lambda Calculus via C# (8) Church Numeral Arithmetic
The previous part defined Church numerals in lambda calculus and implemented 0, 1, 2, 3 in 2 different ways. By observing the definition and code, there are some patterns when the Church numeral increases from 0 to 3.
-
Lambda Calculus via C# (7) Encoding Church Numerals
Previous parts showed that Boolean values, Boolean logic, and if logic can all be encoded by lambda expressions. This and next few articles will focus on natural numbers. Signed number will be encoded after introducing Church pairs (2-tuples).
-
Lambda Calculus via C# (6) If Logic, And Reduction Strategies
The if logic is already built in Church Booleans.
-
Lambda Calculus via C# (5) Boolean Logic
After defining Boolean values True and False with functions, now the Boolean logics can be encoded, by functions too.
-
Lambda Calculus via C# (4) Encoding Church Booleans
After clarifying the concepts and terms, a lot of implementation coding starts from this part.
-
Lambda Calculus via C# (3) Fundamentals - Function composition
It may not be the best place to discuss function composition in the lambda calculus series. However, function composition will be used a lot in later articles, so here is a brief introduction.
-
Lambda Calculus via C# (2) Fundamentals - Lambda Expression, Variables, Reductions
The C# lambda expression has been discussed in detail. This post will explain lambda expression and other concepts in lambda calculus.
-
Lambda Calculus via C# (1) Fundamentals - Closure, Currying and Partial Application
C# lambda expression is discussed in detail used everywhere in the LINQ via C# series. This post and the following few posts will focus on functions and disregard lambda expression for expression tree. These articles will be a deeper dive about lambda expression and lambda calculus - how it comes, what it does, and why it matters. And - functions and anonymous functions will always be the only primitive.