lambda.py

# Most of this was adapted from
# http://matt.might.net/articles/compiling-up-to-lambda-calculus/

# Python's lambda expressions are turing-complete. To show this, we will
# implement the "Lambda calculus" which is another way of saying "We're so manly
# we don't even NEED if statements!" The lambda calculus was invented in the
# 1930s, and it can solve any computable problem just by using anonymous
# functions that each take one argument and return one value, function
# application, and variable references. No jumps or GO TO's needed.


# Start out with void. The value of this doesn't matter, we just need the fact
# that it exists.
VOID = "bacon"

# How to represent true and false? Simple: given two expressions, true evaluates
# the first one and false evaluates the second.
TRUE  = lambda t: lambda f: t()
FALSE = lambda t: lambda f: f()

# From here, we can build some sort of if statement. The condition will be TRUE
# or FALSE, so if we pass the 'branches' to the condition, the condition  will
# pick the right one.
IF = lambda condition: lambda true_branch: lambda false_branch: (
    condition(lambda: true_branch)(lambda: false_branch))

# Now we can say things like
# print IF(TRUE) (lambda: 25) (lambda: 26) ()
# and 25 would pop up!

# Here is part of the foreign function interface.
def boolify(church_boolean):
    "Takes one of those funky booleans and converts it into a normal Python boolean"
    return church_boolean(lambda: True)(lambda: False)

# Here's a few more boolean primitives.
AND = lambda a: lambda b: IF (a) (b) (FALSE)
OR  = lambda a: lambda b: IF (a) (TRUE) (b)

# So now we need a way of representing numbers. "Church numerals" can do this.
# It's easy: we encode a digit N as a function that invokes another function N
# times.

# Hard to see? Take a look:
# some_church_numeral (function) (end)
# This will call function some_church_numeral-many times and return end.

# To see this,
# def foo(x):
#     print "Foo!"
#     return x
# print "%s is good" % some_church_numeral (foo) (bacon)
# will output "Foo!" some_church_numeral times followed by "bacon is good"

# Here's some more foreign interface. We'll never refer to it within the raw
# program.
def num_to_church(n):
    "Convert a positive python integer into a Church numeral"
    if n==0:
        return lambda a: lambda b: b
    else:
        prev = num_to_church(n-1)
        return lambda f: lambda z: f(prev(f)(z))
def church_to_num(church_numeral):
    "Convert a Church numeral into a python integer"
    return church_numeral(lambda n: n + 1)(0)

# Here's a bit of arithmetic, copied straight out of the textbook. Don't ask me
# how it works.
IS_ZERO = lambda n: n(lambda _: FALSE)(TRUE)
SUM = lambda n: lambda m: lambda f: lambda z: m(f)((n(f))(z))
MUL = lambda n: lambda m: lambda f: lambda z: m(n(f))(z)
PRED = lambda n: lambda f: lambda z: (
        n(lambda g: lambda h: h(g(f)))(lambda u: z)(lambda u: u))
SUB = lambda n: lambda m: m(PRED)(n)
IS_EQUAL = lambda a: lambda b: AND(IS_ZERO(SUB(a)(b)))(IS_ZERO(SUB(b)(a)))


# Now we can code factorial like this:
ONE = num_to_church(1)
FACT = lambda n: (IF(IS_ZERO(n))
                    (lambda _: ONE)
                    (lambda _: (MUL(n)
                                   (FACT(SUB(n)(ONE)))))
                 (VOID))

FIVE = num_to_church(5)
print "The factorial of 5 is %d" % church_to_num(FACT(FIVE))
# => The factorial of 5 is 120

# There are ways of building complete data structures. It's easy to build linked
# lists, and from there you can get trees, tables, and so on.

amazing examples @gcr ! thank you so much for writing them.

do you mind if i use a snippet from this code (with reference to it) in a card game i am making for my daughter?

the game card will look like this (the dice symbol means you have to roll 20 sided dice and get its value at that place):

(you can check the other cards at https://punkjazz.org/programming-time/easy.html)

also do you want me to link just to the gist file or to your github?

PS: i will print 300 decks and donate them to schools.

thanks in advance

go for it!

go for it!

Thanks!
I am embarrassed to say I already printed the decks and donated most of them, I am really sorry for not waiting for your ack, but I got too excited to print, I would love to send you few decks as a thank you, the print turned out really nice, you can see it at https://punkjazz.org/programming-time/ , email me at jackdoe@fastmail.com if you want

Thanks again for making those great examples!