Extra for http://nbviewer.ipython.org/5523724

parser.py

from collections import deque

def readArg(string):
    for i in range(len(string)):
        if string[i] == ")":
            return deque([string[:i]]), string[i+1:]
        if string[i] == "(":
            inner_result, rest = readArg(string[i+1:])
            other_results, return_rest = readArg(rest)
            other_results.extendleft(deque([inner_result, string[:i]]))
            return other_results, return_rest
    return deque([string]), ""

def filter_empty(lst):
    while True:
        try: 
            lst.remove("")
        except ValueError: 
            break
    for el in lst: 
        if isinstance(el, deque):
            filter_empty(el)
    return lst

to_tree = lambda s: filter_empty(readArg(s)[0])

def to_string(tree, i=0):
    if len(tree) == i: return ""
    tail = to_string(tree, i+1)
    if isinstance(tree[i], str):
        return tree[i] + tail
    return "(" + to_string(tree[i]) + ")" + tail

def replace_all(tree, what, _with, i=0):
    if isinstance(tree, str): return tree
    if len(tree) == i: return deque()
    tail = replace_all(tree, what, _with, i+1)
    if isinstance(tree[i], str) and tree[i] == what: 
        tail.appendleft(_with)
    elif isinstance(tree[i], deque):
        tail.appendleft(replace_all(tree[i], what, _with))
    else:
        tail.appendleft(tree[i])
    return tail

keys = []
replacements = {} 
def learn(name, meaning):
    name = name.strip()
    meaning = to_tree(meaning.strip())
    for key in keys:
        #print name, key
        #print to_string(meaning)
        #print
        meaning = replace_all(meaning, key, replacements[key])
    replacements[name] = meaning
    keys.append(name)
    return meaning


a = """
ZERO  = lambda f: lambda x: x

ONE   = lambda f: lambda x: f(x)

TWO   = lambda f: lambda x: f(f(x))

THREE = lambda f: lambda x: f(f(f(x)))

FOUR  = lambda f: lambda x: f(f(f(f(x))))

FIVE  = lambda f: lambda x: f(f(f(f(f(x)))))

TEN   = lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x))))))))))

INCREMENT = lambda num: lambda f: lambda x: f(num(f)(x))

DECREMENT = lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)

SIX = INCREMENT(FIVE)

PLUS     = lambda a: lambda b: a(INCREMENT)(b)

MINUS    = lambda a: lambda b: b(DECREMENT)(a)

MULTIPLY = lambda a: lambda b: a(PLUS(b))(ZERO)

POWER    = lambda a: lambda b: b(a)

NINE     = MULTIPLY(THREE)(THREE)

FIFTEEN  = MULTIPLY(FIVE)(THREE)

THIRTY   = MULTIPLY(SIX)(FIVE)

TRUE  = lambda a: lambda b: a

FALSE = lambda a: lambda b: b

IF = lambda boolean: boolean

AND = lambda a: lambda b: (IF(a)(b)(FALSE))

OR  = lambda a: lambda b: (IF(a)(TRUE)(b))

NOT = lambda a: (IF(a)(FALSE)(TRUE))

IS_ZERO = lambda num: num(lambda x: (FALSE))(TRUE)

LESS_THAN_EQUAL = lambda a: lambda b: (IS_ZERO(MINUS(a)(b)))

EQUAL = lambda a: lambda b: (AND(LESS_THAN_EQUAL(a)(b))(LESS_THAN_EQUAL(b)(a)))

PAIR  = lambda head: lambda tail: lambda f: f(head)(tail)

LEFT  = lambda pair: pair(TRUE)

RIGHT = lambda pair: pair(FALSE)

NIL  = PAIR(TRUE)(TRUE)

HEAD = lambda lst: (LEFT(RIGHT(lst)))

TAIL = lambda lst: (RIGHT(RIGHT(lst)))

PREPEND  = lambda el: lambda lst: (PAIR(FALSE)(PAIR(el)(lst)))

IS_EMPTY = LEFT

Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))

REDUCE = Y(lambda rec: lambda f: lambda init: lambda lst: (IF(IS_EMPTY(lst))(init)(lambda x: f(HEAD(lst))(rec(f)(init)(TAIL(lst)))(x))))

LENGTH = REDUCE(lambda _: (PLUS(ONE)))(ZERO)

SUM = REDUCE(PLUS)(ZERO)

RANGE = Y(lambda rec: lambda start: lambda end: (IF(LESS_THAN_EQUAL(end)(start))(NIL)(lambda x: (PREPEND(start)(rec(INCREMENT(start))(end)) )(x))))

MIN_LENGTH = lambda a: lambda b: (IF(OR(IS_EMPTY(b))(AND(NOT(IS_EMPTY(a)))(LESS_THAN_EQUAL(LENGTH(a))(LENGTH(b)))))(a)(b))

COIN_CHANGE = Y(lambda rec: lambda amount: lambda coins: lambda taken: (IF(EQUAL(amount)(SUM(taken)))(taken)(IF(IS_EMPTY(coins))(NIL)(lambda x: (MIN_LENGTH(rec(amount)(TAIL(coins))(PREPEND(HEAD(coins))(taken)))(rec(amount)(TAIL(coins))(taken)))(x)))))

MAP = lambda f: (REDUCE(lambda el: (PREPEND(f(el))))(NIL))

SQUARE = lambda num: MULTIPLY(num)(num)

FILTER = lambda pred: REDUCE(lambda el: lambda rest: (IF(pred(el)) (PREPEND(el)(rest)) (rest))(NIL))

MOD = Y(lambda rec: lambda a: lambda b: (IF(LESS_THAN_EQUAL(b)(a)) (lambda x: (rec(MINUS(a)(b))(b) )(x)) (a)))

IS_PRIME = lambda num: (IS_EMPTY(FILTER(lambda x: (IS_ZERO(MOD(num)(x)))) (RANGE(TWO)(num))))

PUSH = lambda el: (REDUCE(PREPEND)(PREPEND(el)(NIL)))

DIV = Y(lambda rec: lambda a: lambda b: (IF(LESS_THAN_EQUAL(b)(a)) (lambda x: (INCREMENT(rec(MINUS(a)(b))(b))(x))) (ZERO)))

TO_DIGITS = Y(lambda rec: lambda num: (IF(LESS_THAN_EQUAL(num)(NINE)) (PREPEND(num)(NIL)) (lambda x: (PUSH(MOD(num)(TEN)) (rec(DIV(num)(TEN)))(x)))))

F = TEN

I = ELEVEN 

ELEVEN = INCREMENT(TEN)

Z = TWELVE 

TWELVE = INCREMENT(ELEVEN)

B = THIRTEEN 

THIRTEEN = INCREMENT(TWELVE) 

U = FOURTEEN 

FOURTEEN = INCREMENT(THIRTEEN) 

FIFTEEN = MULTIPLY(THREE)(FIVE)

HUNDRED = POWER(TEN)(TWO)

ZZ = PREPEND(Z)(PREPEND(Z)(NIL))

FIZZ = PREPEND(F)(PREPEND(I)(ZZ))

BUZZ = PREPEND(B)(PREPEND(U)(ZZ))

FIZZBUZZ = PREPEND(F)(PREPEND(I)(PREPEND(Z)(PREPEND(Z)(BUZZ))))

_101 = INCREMENT(HUNDRED)

FB = lambda num: (IF(IS_ZERO(MOD(num)(FIFTEEN))) (FIZZBUZZ) (IF(IS_ZERO(MOD(num)(FIVE))) (BUZZ) (IF(IS_ZERO(MOD(num)(THREE))) (FIZZ) (TO_DIGITS(num)))))
"""
#FB = lambda num: (IF(IS_ZERO(MOD(num)(FIFTEEN))) (FIZZBUZZ) (IF(IS_ZERO(MOD(num)(FIVE))) (BUZZ) (IF(IS_ZERO(MOD(num)(THREE))) (FIZZ) (TO_DIGITS(num)))))

for x in a.split("\n\n"):
    try:
        a, b = x.split("=")
        learn(a.strip(), b)
    except Exception as e:
        print x.split("="), e

def l(x):
    result = to_string(learn("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", x))
    errors = [(x, result.count(x)) for x in replacements if x in result]
    print
    print result
    if errors:
        print "\n\nERROR: %s" % errors
#l("COIN_CHANGE(TEN)(RANGE(ONE)(SIX))(NIL)")
l("MAP(FB)(RANGE(ONE)(_101))")