My take on the church of lambda

lambda.py

"""

My take on the Church of Lambda. I've tweaked and added a few thing to
make life more enjoyable

author: Christopher O'Brien  <siege@preoccupied.net>

inspiration from http://doos.m3r.nl/~ivo/lambda.txt

"""



# TODO:
# implement NUL and cons cells
# implement number comparison and bitfield comparison



#
# Pairs


# let's start off with something simple, like a pair of values
# and a way to select between them

# use as pair(a)(b)
# access using my_pair(first) or my_pair(second)

pair = lambda a: lambda b: lambda which: (which)(a)(b)

first = lambda x: lambda y: x

second = lambda x: lambda y: y


print "testing out pair"
z = pair(111)(222)
print [z(first), z(second)]



#
# lists

# we could probably build a cons cell, but I haven't figured out a
# clean way to represent and check for NUL yet. I'll figure it out at
# some point, and then I'll write a LISP in this



#
# booleans


true = first
false = second

# just for debugging purposes. Converts one of our booleans into a
# Python boolean
to_bool = lambda b: b(True)(False)


# this is totally useless
if_then_else = lambda condition: lambda a: lambda b: condition(a)(b)


# I can't name these similarly to the existing and,or,not operators, so
# I just stuck a "b" in front

bnot = lambda a: a(false)(true)

band = lambda a: lambda b: a(b)(a)

bor = lambda a: lambda b: a(a)(b)

bnor = lambda a: lambda b: bnot(bor(a)(b))

bxor = lambda a: lambda b: a(bnot(b))(b)

beq = lambda a: lambda b: a(b)(bnot(b))


print "testing out band"
print "true and true ->", to_bool(band(true)(true))
print "false and true ->", to_bool(band(false)(true))

print "testing out bor"
print "false or true ->", to_bool(bor(false)(true))
print "false or false ->", to_bool(bor(false)(false))

print "testing out if_then_else"
print "if true then 111 else 222 ->", if_then_else(true)(111)(222)
print "if false then 111 else 222 ->", if_then_else(false)(111)(222)

print "screw if_then_else"
print "true? 444: 555 ->", true(444)(555)
print "false? 444: 555 ->", false(444)(555)



#
# Church-like numbers


zero = false

is_zero = lambda n: n(lambda x: false)(true)

non_zero = lambda n: n(lambda x: true)(false)

# effectively adds one to the value
incr = lambda n: lambda f: lambda x: f(n(f)(x))

# effectively subtracts one from the value. This took me forever to
# figure out, but then seemed very obvious afterwards. I need to look
# up how math people decrement these things, I'm sure they've got a
# better way
decr = lambda n: (n(lambda x: pair(true)(x(first)(incr(x(second)))(zero)))
                  (pair(false)(zero)))(second)


# adds two values together
add = lambda n1: lambda n2: lambda f: lambda x: n1(f)(n2(f)(x))


# multiplies two values together
mult = lambda n1: lambda n2: n1(lambda x: add(x)(n2))(zero)


# duplicates a number
dup = lambda n: n(incr)(zero)


n0 = zero
n1 = incr(n0)
n2 = incr(n1)
n3 = incr(n2)
n4 = add(n2)(n2)
n5 = add(n3)(n2)

n9 = add(n5)(n4)
n8 = decr(n9)
n7 = decr(n8)

n6 = mult(n2)(n3)

n10 = add(n6)(n4)


# just for debugging. Converts one of our numbers into a Python integer
to_int = lambda n: n(lambda x: x+1)(0)


print "testing numbers"
print [to_int(n) for n in (n0, n1, n2, n3, n4, n5, n6, n7, n8, n9, n10)]



#
# numbers and pairs


# given a list (nested pairs) and a number, we can get the nth item
# from the list
nth_pair = lambda p: lambda n: n(lambda x: x(second))(p)(first)



#
# bitfields


# let's get freaking crazy! Let's begin to emulate 4bit integers as
# nested pairs of true/false, and let's write basic arithmatic
# functions for them. Soon we'll be able to represent negative and
# floating point values


bu_add = lambda a: lambda b: lambda c: \
         bxor(bxor(a)(b))(c)

bu_add_carryp = lambda a: lambda b: lambda c: \
                a(bor)(band)(b)(c)

bu_add_carry = lambda ac: lambda a: lambda b: lambda c: \
               (pair(bu_add(a(first))(b(first))(c)) \
                (ac(a(second))(b(second)) \
                 (bu_add_carryp(a(first))(b(first))(c))))

uint0_add_carry = bu_add_carry(lambda a: lambda b: lambda c: c)

uint1_add_carry = bu_add_carry(uint0_add_carry)

uint2_add_carry = bu_add_carry(uint1_add_carry)

uint3_add_carry = bu_add_carry(uint2_add_carry)

uint4_add_carry = bu_add_carry(uint3_add_carry)

uint4_add = lambda a: lambda b: uint4_add_carry(a)(b)(false)


# 4bit zero
uint4_0 = pair(false)(pair(false)(pair(false)(pair(false)(false))))

# 4bit 1
uint4_1 = uint4_add_carry(uint4_0)(uint4_0)(true)

uint4_2 = uint4_add(uint4_1)(uint4_1)
uint4_3 = uint4_add(uint4_2)(uint4_1)
uint4_4 = uint4_add(uint4_2)(uint4_2)
uint4_5 = uint4_add(uint4_4)(uint4_1)
uint4_6 = uint4_add(uint4_4)(uint4_2)
uint4_7 = uint4_add(uint4_4)(uint4_3)
uint4_8 = uint4_add(uint4_4)(uint4_4)
uint4_9 = uint4_add(uint4_5)(uint4_4)
uint4_a = uint4_add(uint4_5)(uint4_5)
uint4_b = uint4_add(uint4_a)(uint4_1)
uint4_c = uint4_add(uint4_a)(uint4_2)
uint4_d = uint4_add(uint4_a)(uint4_3)
uint4_e = uint4_add(uint4_a)(uint4_4)
uint4_f = uint4_add(uint4_e)(uint4_1)


# there's a snake in my garden
uint4_to_bools = lambda u: [to_bool(nth_pair(u)(i)) for i in (n0,n1,n2,n3)]

# CHEATING! REWRITE THIS STAT
def uint4_to_int(u):
    ret = 0
    ret += (0,1)[to_bool(nth_pair(u)(n0))]
    ret += (0,2)[to_bool(nth_pair(u)(n1))]
    ret += (0,4)[to_bool(nth_pair(u)(n2))]
    ret += (0,8)[to_bool(nth_pair(u)(n3))]
    return ret


# test out some of our bitfield math
print 0, uint4_to_int(uint4_0)
print 1, uint4_to_int(uint4_1)
print 2, uint4_to_int(uint4_2)
print 3, uint4_to_int(uint4_3)
print 4, uint4_to_int(uint4_4)
print 5, uint4_to_int(uint4_5)
print 6, uint4_to_int(uint4_6)
print 7, uint4_to_int(uint4_7)
print 8, uint4_to_int(uint4_8)
print 9, uint4_to_int(uint4_9)
print 'a', uint4_to_int(uint4_a)
print 'b', uint4_to_int(uint4_b)
print 'c', uint4_to_int(uint4_c)
print 'd', uint4_to_int(uint4_d)
print 'e', uint4_to_int(uint4_e)
print 'f', uint4_to_int(uint4_f)
print 'overflow', uint4_to_int(uint4_add(uint4_f)(uint4_1))


bu_sub = lambda a: lambda b: lambda c: \
         a(b)(bnot(b))(c)(bnot(c))


bu_sub_carryp = lambda a: lambda b: lambda c: \
                c(bor)(band)(b)(bnot(a))


bu_sub_carry = lambda sc: lambda a: lambda b: lambda c: \
               (pair(bu_sub(a(first))(b(first))(c))
                (sc(a(second))(b(second)) \
                 (bu_sub_carryp(a(first))(b(first))(c))))


uint0_sub_carry = bu_sub_carry(lambda a: lambda b: lambda c: c)

uint1_sub_carry = bu_sub_carry(uint0_sub_carry)

uint2_sub_carry = bu_sub_carry(uint1_sub_carry)

uint3_sub_carry = bu_sub_carry(uint2_sub_carry)

uint4_sub_carry = bu_sub_carry(uint3_sub_carry)

uint4_sub = lambda a: lambda b: uint4_sub_carry(a)(b)(false)


print "1 - 0:", uint4_to_int(uint4_sub(uint4_1)(uint4_0))
print "2 - 1:", uint4_to_int(uint4_sub(uint4_2)(uint4_1))
print "3 - 1:", uint4_to_int(uint4_sub(uint4_3)(uint4_1))
print "6 - 2:", uint4_to_int(uint4_sub(uint4_6)(uint4_2))
print "8 - 1:", uint4_to_int(uint4_sub(uint4_8)(uint4_1))
print "8 - 2:", uint4_to_int(uint4_sub(uint4_8)(uint4_2))
print "8 - 3:", uint4_to_int(uint4_sub(uint4_8)(uint4_3))
print "f - 1:", uint4_to_int(uint4_sub(uint4_f)(uint4_1))
print "2 - 2:", uint4_to_int(uint4_sub(uint4_2)(uint4_2))
print "0 - 1:", uint4_to_int(uint4_sub(uint4_0)(uint4_1))
print "8 - 7:", uint4_to_int(uint4_sub(uint4_8)(uint4_7))



#
# The end.

output

testing out pair
[111, 222]
testing out band
true and true -> True
false and true -> False
testing out bor
false or true -> True
false or false -> False
testing out if_then_else
if true then 111 else 222 -> 111
if false then 111 else 222 -> 222
screw if_then_else
true? 444: 555 -> 444
false? 444: 555 -> 555
testing numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
a 10
b 11
c 12
d 13
e 14
f 15
overflow 0
1 - 0: 1
2 - 1: 1
3 - 1: 2
6 - 2: 4
8 - 1: 7
8 - 2: 6
8 - 3: 5
f - 1: 14
2 - 2: 0
0 - 1: 15
8 - 7: 1

Originally from my google code page, now a gist

The original moved to a gist too! https://gist.github.com/vivekhaldar/2438498