Skip to content

Instantly share code, notes, and snippets.

@obriencj

obriencj/lambda.py

Last active Jan 4, 2016
Embed
What would you like to do?
My take on the church of lambda
"""
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.
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
@obriencj

This comment has been minimized.

Copy link
Owner Author

@obriencj obriencj commented Jan 25, 2014

Originally from my google code page, now a gist

@obriencj

This comment has been minimized.

Copy link
Owner Author

@obriencj obriencj commented Jan 25, 2014

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.