# Some Lambda Calculus in Python:

I = lambda x:x
K = lambda x:lambda y:x  # not same lambda x,y:x  (not Curried)
S = lambda x:lambda y:lambda z:x(z)(y(z))  # x z (y z) in lambda calc notation

print S(K)(I)(3)  # should print 3  since SKI = I

# booleans and if-else

Tr = K
Fl = K(I)  # lambda x:lambda y:y

# cheat and make sure 3 args always passed:
If0 = lambda c,a,b: c(a)(b)
Negate = lambda a: If0(a,Fl,Tr)
Andd = lambda a,b: If0(a,b,Fl)
Orr = lambda a,b: If0(a,Tr,b)

# to simulate call-by-name, delay evaluation using dummy lambda term.
# most languages use "weak normalization": evaluate body of lambda term only
# when applied to a value.

Ifelse = lambda c,a,b:c(a)(b)()   # extra application to return result.

x = 2
#print If0(Tr,1,1/(x-2))  # uncomment at own risk
print Ifelse(Tr,lambda : 1, lambda : 1/(x-2))  # should print 1

# hints at how to implement call-by-name (pass pointer to code)

# data structures

Cons = lambda a,b:lambda s: If0(s,a,b)
Car = lambda p:p(Tr)
Cdr = lambda p:p(Fl)
NULL = I  # something to represent end of list

M = Cons(2,Cons(3,Cons(5,Cons(7,NULL))))  # list of primes
print Car(Cdr(Cdr(M)));  # should print 5


# Recursion:
# What combinator FIX with behavior: FIX(M) = M(FIX(M))
# Applicative Order a bit more complicated

FIX = lambda M:(lambda x:M(lambda y:x(x)(y)))(lambda x:M(lambda y:x(x)(y)))