# Some Lambda Calculus in Python:

# basic combinators:

I = lambda x: x
K = lambda x: lambda y: x
S = lambda x: lambda y: lambda z: x(z)(y(z))   # (x z)(y z)

# booleans and ifelse:

tr = K       # true
fl = K(I)    # false, K(I) = lambda x: lambda y: y

ifelse = lambda a,b,c: a(b)(c)

nott = lambda x: ifelse(x,fl,tr)
orr = lambda a,b: ifelse(a,tr,b)
andd = lambda a,b: ifelse(a,b,fl)

# pairs and linked lists

null = lambda x: x

pair = lambda x,y: lambda s: ifelse(s,x,y)
first = lambda p: p(tr)    # first element (head) of list
rest = lambda p: p(fl)     # second element of pair, tail of list

car = first                # classic names for head and tail (from lisp)
cdr = rest
cons = pair

l = pair(1,pair(3,pair(5,pair(7,null))))

print first(l)
print first(rest(l))

### problem: ifelse is call-by value, need call by name
ife = lambda(a,b,c): ifelse(a,b,c)(I)



### fixed point combinator
fix = lambda M: (lambda x: M(lambda y: x(x)(y)))(lambda x: M(lambda y: x(x)(y)))