Lambda Calculus (for geeks)#

If you are into maths, you may enjoy \(\lambda\)-calculus. It’s a calculus where all the elements are functions. It is also equivalent to a Von-Neumann-Machine and allows you, in principle, to perform any computation. In this chapter we will look at some Church encodings, which are \(\lambda\)-function representations of boolean algebra, numbers, data storage, etc.

Let`s start with something simple: booleans

Church Encoding: Booleans#

import ison

dicData = {
    "__globals__": {
        "eval": "$L{$!{%0, true, false}}",
        "true": "$L{%0%~1}",
        "false": "$L{%~0%1}",
    },
    "x": "${eval, ${true}}",
    "y": "${eval, ${false}}",
}

dicResult = ison.run.Run(xData=dicData)
print(ison.run.ToString(dicResult))

{
    "x": "true",
    "y": "false"
}

Boolean AND#

All elements here are functions. Boolean true is represented by a \(\lambda\)-function selecting the first value of two given arguments, and false is represented by a function selecting the second element. The function eval allows us to print the resultant effect of a construction with lambda functions. Any function that selects the first element, representes true, and if it selects the second element it represents false.

We can use this basic setup to define boolean and,

import ison

dicData = {
    "__func_globals__": {
        # Evaluation function
        "eval": "$L{$bool{$!{%0, true, false}}}",
        # Definition of 'true'
        "T": "$L{%0%~1}",
        # Definition of 'false'
        "F": "$L{%~0%1}",
        # The 'AND' function
        # The '$!{}' explicitly evaluates a lambda function
        "and": "$L{$!{$!{%0, %1}, %0}}",
    },
    "result": "${eval, ${and, ${T}, ${F}} }",
}

dicResult = ison.run.Run(xData=dicData)
print(ison.run.ToString(dicResult))

{
    "result": false
}

We can also define a whole dictionary as a lambda function. Executing this function processes all elements of the dictionary as lambda functions.

import ison

dicData = {
    "__func_globals__": {
        # Evaluation function
        "eval": "$L{$bool{$!{%0, true, false}}}",
        # Define a dictionary that will be used a lambda function.
        "eval_all_bi": { "__lambda__": {},
            "T %0 T": "${eval, $!{${%0}, ${T}, ${T}}}",
            "T %0 F": "${eval, $!{${%0}, ${T}, ${F}}}",
            "F %0 T": "${eval, $!{${%0}, ${F}, ${T}}}",
            "F %0 F": "${eval, $!{${%0}, ${F}, ${F}}}",
        },
        # Definition of 'true'
        "T": "$L{%0%~1}",
        # Definition of 'false'
        "F": "$L{%~0%1}",
        # The 'AND' function
        # The '$!{}' explicitly evaluates a lambda function
        "and": "$L{$!{$!{%0, %1}, %0}}",
    },
    # This calls the eval_all_bi dictionary lambda function
    # with the 'and' function as argument.
    "result": "${eval_all_bi, and}",
}

dicResult = ison.run.Run(xData=dicData)
print(ison.run.ToString(dicResult))

{
    "result": {
        "T and T": true,
        "T and F": false,
        "F and T": false,
        "F and F": false
    }
}

Boolean OR#

import ison

dicData = {
    "__func_globals__": {
        # Evaluation function
        "eval": "$L{$bool{$!{%0, true, false}}}",
        # Define a dictionary that will be used a lambda function.
        "eval_all_bi": { "__lambda__": {},
            "T %0 T": "${eval, $!{${%0}, ${T}, ${T}}}",
            "T %0 F": "${eval, $!{${%0}, ${T}, ${F}}}",
            "F %0 T": "${eval, $!{${%0}, ${F}, ${T}}}",
            "F %0 F": "${eval, $!{${%0}, ${F}, ${F}}}",
        },
        # Definition of 'true'
        "T": "$L{%0%~1}",
        # Definition of 'false'
        "F": "$L{%~0%1}",
        # The 'AND' function
        # The '$!{}' explicitly evaluates a lambda function
        "or": "$L{$!{$!{%0, %0}, %1}}",
    },
    # This calls the eval_all_bi dictionary lambda function
    # with the 'and' function as argument.
    "result": "${eval_all_bi, or}",
}

dicResult = ison.run.Run(xData=dicData)
print(ison.run.ToString(dicResult))

{
    "result": {
        "T or T": true,
        "T or F": true,
        "F or T": true,
        "F or F": false
    }
}

Boolean NOT#

import ison

dicData = {
    "__func_globals__": {
        # Evaluation function
        "eval": "$L{$bool{$!{%0, true, false}}}",
        # Define a dictionary that will be used a lambda function.
        "def_eval_all_uni": { "__lambda__": {},
            "%0 T": "${eval, $!{${%0}, ${T}}}",
            "%0 F": "${eval, $!{${%0}, ${F}}}",
        },
        # Definition of 'true'
        "T": "$L{%0%~1}",
        # Definition of 'false'
        "F": "$L{%~0%1}",
        # The 'NOT' function
        # The '$!{}' explicitly evaluates a lambda function
        "not": "$L{$!{$!{%0, %2}, %1}}",
    },
    # This calls the eval_all_bi dictionary lambda function
    # with the 'and' function as argument.
    "result": "${def_eval_all_uni, not}",
}

dicResult = ison.run.Run(xData=dicData)
print(ison.run.ToString(dicResult))

{
    "result": {
        "not T": false,
        "not F": true
    }
}

Church Encoding: Numerals#

The functional representation of numerals basically encodes how often a function is applied. To show the result here, we define the function f as incrementing an integer by one.

import ison

dicData = {
    "__globals__": {
        # evaluation function to see the effect
        "apply": "$L{%0+1}",
        "zero": "$L{%~0%1}",  # same as FALSE
        # The successor operator
        "succ": "$L{$!{%1, $!{$!{%0, %1}, %2}}}",
        # 1 is the succesor of 0
        "one": "${succ, ${zero}}",
        # 2 is the succesor of 0
        "two": "${succ, ${one}}",
    },
    "result": {
        # This shows the lambda function result
        "func-one": "${succ, ${zero}}",
        "func-two": "${succ, ${one}}",
        # The successor of 2 function applied to
        # the 'apply' function starting at 0
        "result": "${succ, ${two}, ${apply}, 0}",
        # This demonstrates the effect of applying the
        # apply function twice
        "x": "${apply, ${apply, 0}}",
    },
}

dicResult = ison.run.Run(xData=dicData)
print(ison.run.ToString(dicResult))

{
    "result": {
        "func-one": "$L{$!{%0, $!{$!{$L{%~0%1}, %0}, %1}}}",
        "func-two": "$L{$!{%0, $!{$!{$L{$!{%0, $!{$!{$L{%~0%1}, %0}, %1}}}, %0}, %1}}}",
        "result": "0+1+1+1",
        "x": "0+1+1"
    }
}

import ison

dicData = {
    "__globals__": {
        # apply function implements integer addition
        "apply": "$L{$sum{%0, 1}}",
        # The eval function applies the apply function
        "eval": "$L{$!{%0, ${apply}, 0}}",
        "zero": "$L{%~0%1}",  # same as FALSE
        "succ": "$L{$!{%1, $!{$!{%0, %1}, %2}}}",
        "plus": "$L{$!{$!{%0, %2}, $!{$!{%1, %2}, %3}}}",
        "one": "${succ, ${zero}}",
        "two": "${succ, ${one}}",
    },
    "result": {
        "succ 0": "${eval, ${one}}",
        "succ 1": "${eval, ${two}}",
        "2 + 2": "${eval, ${plus, ${two}, ${two}}}",
    },
}

dicResult = ison.run.Run(xData=dicData)
print(ison.run.ToString(dicResult))

{
    "result": {
        "succ 0": 1,
        "succ 1": 2,
        "2 + 2": 4
    }
}

Church Encoding: Data Structures#

import ison

dicData = {
    "__globals__": {
        "pair": "$L{$!{$!{%2, %0}, %1}}",
        "first": "$L{$!{%0, $L{%0%~1}}}",
        "second": "$L{$!{%0, $L{%~0%1}}}",
        "data": "${pair, 1, 2}",
    },
    "result": {
        "first": "${first, ${data}}",
        "second": "${second, ${data}}",
    },
}

dicResult = ison.run.Run(xData=dicData)
print(ison.run.ToString(dicResult))

{
    "result": {
        "first": "1",
        "second": "2"
    }
}

Lambda Calculus (for geeks)

Contents