Lambda calculus is a special language that understands how functions work. Think of functions as little black-box machines that take an input and give an output. The lambda calculus, uses "lambda expressions" to create these functions. Every lambda expression has two parts: the input and the output, written as follows:
λ(input).output.
Thus a simple function that adds 2 to any number looks like this:
λx.x + 2
The λx defines the input called "x," and the "x + 2" is the output. So if the number 3 is the input, the black-box will add 2 to give 5 as the output. Now, it gets interesting because using lambda calculus, black-box functions can also take functions as input. For example a function that doubles any number is expressed as:
λy.y * 2
If we give this function the number 4 as input, it will multiply it by 2 and give us 8 as the output. But can you also combine functions. For example a new function that takes a number, doubles it, and then adds 2 is expressed as:
(λx.λy.y * 2) (x + 2)
The (x + 2) part is the input for the function that doubles, and the whole expression becomes a new function that can be resolved by a more complex Lambda expression. So if the input to this combined function is the number 5 as input, it first adds 2, which gives us 7, and then doubles it, giving us 14 as the final output.
Given this understanding as the basic idea of lambda calculus as a language of functions helps to understand how things are combined and transformed by a digital computer. It may seem complicated, but it is actually so simple and powerful it solves many problems in computer science and mathematics. For example, given another lambda expression, say, λy. y * 3 one can multiply by 3, and get the answer and combine this with the first lambda expression, to create the expression:
(λx. x + 2)((λy. y * 3) 4).
What happens is the lambda expression λy. y * 3 and put the number 4 into it. So the box will do 4 * 3 and give us 12. Then, we take that 12 and put it into the lambda expression λx. x + 2. The box will do 12 + 2 and give us 14 as the final answer. Thus the lambda calculus can express complex scientific expressions to perform calculations and solve any computational problem. In this case the simple black-box is extended functionally to follow instructions and give the answers wanted, just like a computer.
Think of a program to calculate the volume of any sphere. The volume of a sphere is calculated using the radius of the sphere (r) in the formula:
(4/3) * π * r^3
One can can this lambda function by the name "volume_of_sphere" that is represented by an immutable token resolved by the lambda expression for the volume of a sphere would be:
volume_of_sphere = λr. ((4/3) * 3.14159 * r^3)
Here, λr indicates that the function takes in a parameter called "r", representing the radius and the parameter π is another tokens resolved by the namespace as the value 3.14159 to calculate the volume of any sphere using the given radius 'r'. To use this lambda expression, one inputs a specific value for "r" to the function named "volume_of_sphere." To find the volume of a sphere with a radius of 5 units, you would computer the lambda expression written like this: volume_of_sphere(5). The result is the volume of the sphere with a radius of 5 units.
Consider another case chosen by Ada Lovelace as the first program ever written documented in about 1840. Ada's function, the Bernoulli series is a sequence of numbers named after the Swiss mathematician Jakob Bernoulli. It is defined using a recursive formula. Ada used Charles Babbage's functional machine code proposed for his Thinking Machine, as Ada called it. She programmed mathematically a lambda expression to generate the nth term of the Bernoulli series. It can be called "bernoulli_series" as follows:
bernoulli_series = λn. if (n = 0) then 1 else (-1/(n+1)) * (∑i=0 to n-1 ((n choose i) * bernoulli_series(i)))
This lambda expression works as follows:
- λn indicates that the function takes in a parameter called "n", representing the index of the term in the Bernoulli series.
- The "if" statement checks if n is equal to 0. If it is, then the value 1 is returned since the first term of the Bernoulli series is always 1.
- If n is not 0, then the lambda expression calculates the nth term using the recursive formula. It calculates the sum (∑) from i=0 to n-1 of ((n choose i) * bernoulli_series(i)), where "choose" represents the binomial coefficient, which calculates the number of ways to choose i elements from a set of n elements.
- The term (-1/(n+1)) multiplies the sum by a factor (-1/(n+1)).
To use this lambda expression, the program inputs a specific value for "n" when applying the lambda function. For example, to find the 5th term of the Bernoulli series, the program would apply the lambda expression like this: bernoulli_series(5). The returned result would be the 5th term of the Bernoulli series.
A binary computer cannot execute a Lambda Calculus expression because the concept of immutable symbolic names does not exist. For example the value 3.14159 cannot be represented by a local token or the global name π and the more complex programmed functions are likewise obscured by static shared addressing. The important point is that functional programs use unique names instead of unreliable details like shared storage memory locations.
So to implement the functional expression above; bernoulli_series(5) or volume_of_sphere(5) requires the name to be translated by a namespace table into the correct memory location. Now as the memory layout changes over time the name always remains unchanged. Furthermore the table can dynamically intercept and perhaps block and reference for any desired computational reason like memory compaction, garbage collection or invalid access rights including all other malware and security reasons.
Functional programs use names or local tokens instead of binary addresses to transfer control from one step in a calculation to another. A named function can execute sequentially within a name based context just like Alan Turing first proposed as Alonzo Church's doctoral student at Princeton University just prior to WWII. If each paper tape represents a self contained function accessed by a unique name defined by a namespace table the simple Turing Machine becomes the engine of functional programming as the Lambda in the Lambda Calculus.
Immutable names replace virtual memory using a equivalent indirection step by driven by a Namespace Table assembled from the names objects in an application namespace that replaces the page table and all the dangerous mechanisms of a privileged, centralized operating system. The superuser evaporates replaced by program controlled namespace addressing and universally safe machine code.
Comments