I've always been amazed by lambda calculus (the way it was tought to me at the university). A while ago (actually more than ten years, it turns out) I attempted to implement some pure lambda calculus in Python.

I've updated the code a bit and I'm reposting it here. It still amazes me you can actually perform arithmetic with only lambda, arguments and '=', and only that.

# based on http://perl.plover.com/lambda/jfp/lambda-church.pl
#
# requires python 2.1 (perhaps 2.0)
#
# CHANGES:
#
# 8 jan 2002: changed to_int to a more obscure lambda statement
# 17 december 2012: restored from web.archive.org, updated, reposted

from __future__ import nested_scopes

true = lambda x: lambda y: x
false = lambda x: lambda y: y
if_then_else = lambda a: lambda b: lambda c: (a)(b)(c)


# pair = cons? cons = if_then_else
pair = lambda a: lambda b: lambda c: (c)(a)(b)

# head = true, tail = false?

head = (lambda x: x)(true)
tail = (lambda x: x)(false)

first = head
second = tail

zero = lambda f: lambda x: x
succ = lambda n: lambda f: lambda x: f(n(f)(x))

n0 = zero
n1 = succ(n0)
n2 = succ(n1)
n3 = succ(n2)
n4 = succ(n3)
n5 = succ(n4)

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

if_then_else(is_zero(n0))(1)(2)
if_then_else(is_zero(n1))(1)(2)

add = lambda m,n: lambda f: lambda x: (m(f))(n(f)(x))

mul = lambda m,n: lambda f: m(n(f))
pred = lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda u: x)(lambda u: u)

fac = lambda n: n(lambda c: lambda q:
q(succ(c(true)))(mul(c(true), c(false)))
)(lambda q: succ(zero))(false)


# up until here all we ave used is lambda. No operators, literal numbers,
# and so on. Only lambda, arguments and '='.
#
# however, the representation on my computer for n5 is
# <function <lambda> at 0x2f1bcf8> which has no meaning to 
# a human programmer of course.
#
# This is why we need a  bridge between the pure lambda world and the
# programmer readable python world: convert a numeral to an actual 
# integer.
# Use it to test the lambda functions

to_int = lambda n: n(lambda x:x+1)(0)

print to_int(if_then_else(true)(n1)(n2))
print to_int(if_then_else(false)(n1)(n2))

print to_int(n3)

print to_int(add(n1,n1))
print to_int(add(n1,n2))
print to_int(add(n3,n2))
print to_int(add(n3,succ(n2)))

print to_int(fac(n5))
print to_int(mul(n4,n5))