Contents tagged with Lambda Calculus
-
Lambda Calculus via C# (8) Undecidability of Equivalence
All the previous parts demonstrated what lambda calculus can do – defining functions to model the computing, applying functions to execute the computing, implementing recursion, encoding data types and data structures, etc. Lambda calculus is a powerful tool, and it is Turing complete. This part discuss some interesting problem that cannot be done with lambda calculus – asserting whether 2 lambda expressions are equivalent.
-
Lambda Calculus via C# (7) Fixed Point Combinator and Recursion
p is the fixed point (aka invariant point) of function f if and only if:
-
Lambda Calculus via C# (6) Combinatory Logic
In lambda calculus, the primitive is function, which can have free variables and bound variables. Combinatory logic was introduced by Moses Schönfinkel and Haskell Curry in 1920s. It is equivalent variant lambda calculus, with combinator as primitive. A combinator can be viewed as an expression with no free variables in its body.
-
Lambda Calculus via C# (5) List
In lambda calculus and Church encoding, there are various ways to represent a list with anonymous functions.
-
Lambda Calculus via C# (4) Tuple and Signed Numeral
Besides modeling values like Boolean and numeral, anonymous function can also model data structures. In Church encoding, Church pair is an approach to use functions to represent a tuple of 2 items.
-
Lambda Calculus via C# (3) Numeral, Arithmetic and Predicate
Anonymous functions can also model numerals and their arithmetic. In Church encoding, a natural number n is represented by a function that calls a given function for n times. This representation is called Church Numeral.
-
Lambda Calculus via C# (2) Church Encoding: Boolean and Logic
Lambda calculus is a formal system for function definition and function application, so in lambda calculus, the only primitive is anonymous function. Anonymous function is actually very powerful. With an approach called Church encoding. data and operation can be modeled by higher-order anonymous functions and their application. Church encoding is named after Alonzo Church, who first discovered this approach. This part discusses Church Boolean - modeling Boolean values and logic operators with functions.
-
Lambda Calculus via C# (1) Fundamentals
Lambda calculus (aka λ-calculus) is a theoretical framework to describe function definition, function application, function recursion, and uses functions and function application to express computation. It is a mathematics formal system, but can also be viewed as a smallest programming language that can express and evaluate any computable function. As an universal model of computation, lambda calculus is important in programming language theory, and especially it is the foundation of functional programming. The knowledge of lambda calculus greatly helps understanding functional programming, LINQ, C# and other functional languages.