Ordinals in Python

import time
timeout_in_sec = 3

"""
The functions numterms, add, deepfund, fund, ack, trans, u and
beautify take their natural number inputs as normal Python
integers, and their ordinal inputs in the format
<ord> = <ord> + <ord>
      | <num>w^(<ord>)
      | <num>w
      | <num>
with the usual ordinal addition rules. The notation only
covers the harmless ordinals.
"""

def numterms(alpha):
    """
    Returns the number of terms in alpha.
    """
    return len(p(alpha))

def add(*alphas):
    """
    Calculates alpha + beta with the usual non-commutative
    ordinal addition.
    """
    return up(p("+".join(alphas)))

def deepfund(alpha, n):
    """
    Calculates alpha((n)) given an ordinal alpha and a
    natural number n.
    """
    return up(timeout(deepfund_, (p(alpha),n),
                      td=timeout_in_sec))

def fund(alpha, n):
    """
    Calculates alpha(n) given an ordinal alpha and a natural
    number n.
    """
    return up(timeout(fund_, (p(alpha),n), td=timeout_in_sec))

def ack(alpha, n):
    """
    Calculates f_alpha given an ordinal alpha.
    """
    return up(timeout(timeout(ack_, (p(alpha),),
                              td=timeout_in_sec),
                      (n,),
                      td=timeout_in_sec))

def trans(n, alpha, m):
    """
    Calculates T_{n, alpha} as a generator, given an ordinal
    alpha and a natural number n.
    """
    t = timeout(trans_, (n, p(alpha)), td=timeout_in_sec)
    v = 0
    for i in range(m-n+1):
        v = t.next()
    return up(v)

def u(n, alpha):
    """
    Calculates U(n, alpha) given an ordinal alpha and a natural
    number n.
    """
    return up(timeout(u_, (n, p(alpha)), td=timeout_in_sec))

def beautify(o):
    """
    Fixes the representation of an ordinal.
    """
    return up(p(o)) # nalle

class ParseError(Exception):
    def __init__(self, value):
        self.value = value
    def __str__(self):
        return repr(self.value)

def p(o):
    if isinstance(o, int): return o
    else:
        o = "".join(filter(lambda a:a!=" ", o))
        try:
            parsed = p_(o,0)[0]
        except ParseError, e:
            return "Parse error near " + str(e.value) + \
                   " in ordinal input."
        except:
            return "Unknown parse error in ordinal input."
    return fix_(parsed)

def up(o):
    if isinstance(o,str):return o
    o = fix_(o)
    if isinstance(o, int):return str(o)
    def m(t):
        if isinstance(t, int):return str(t)
        elif t[1]==1:
            r="w"
        else:
            r="w^("+up(t[1])+")"
        if t[0]==1:return r
        return str(t[0])+r
    return " + ".join(map(m,o))

def p_(string,i):
    v = []
    while True:
        j=i
        while j < len(string) and string[j].isdigit():
            j+=1
        intstring = string[i:j]
        if intstring == "":
            coef = None
        else:
            coef = int(intstring)
        i=j
        if i == len(string) or string[i] == ")":
            if coef == None: return v, i+1
            v.append(coef)
            return v, i+1
        elif string[i:i+3] == "w^(":
            exp, i = p_(string, i+3)
            if coef == None: coef = 1
            v.append((coef, exp))
        elif string[i]=="w":
            i+=1
            if coef == None: coef = 1
            v.append((coef, 1))
        elif string[i]=="+":
            i+=1
        else:
            raise ParseError(i)
        if i < len(string) and string[i] == "+":
            i+=1

def timeout(func, args=(), td=None,
            default="Sorry, I ran out of time."):
    import threading
    class InterruptableThread(threading.Thread):
        def __init__(self):
            threading.Thread.__init__(self)
            self.result = default
        def run(self):
            try:
                self.result = func(*args)
            except:
                self.result = punchline
    it = InterruptableThread()
    it.start()
    if td == None:
        it.join()
    else:
        it.join(td)
    return it.result

def limit_(alpha):
    if isinstance(alpha, int):
        return False
    lastv = alpha[-1][1]
    return lastv != 0

def ord_cmp_(alpha, beta):
    alpha, beta = fix_(alpha), fix_(beta)
    # base cases
    if isinstance(alpha, int):
        if isinstance(beta, int):
            return alpha - beta
        return -1
    if isinstance(beta, int):
        return 1
    c = ord_cmp_(alpha[0][1], beta[0][1])
    if c == 0:
        coefc = alpha[0][0] - beta[0][0]
        if coefc == 0:
            return ord_cmp_(alpha[1:], beta[1:])
        return coefc
    return c

def fix_(alpha):
    if isinstance(alpha, int):
        return alpha
    if len(alpha) == 0:
        return 0
    def intfix_(a):
        if isinstance(a, int):return (a,0)
        return a
    def unintfix_(a):
        if isinstance(a, int):a
        elif a[1]==0:return a[0]
        return a
    alpha = list(map(intfix_, alpha))
    if len(alpha) == 1 and fix_(alpha[0][1]) == 0:
        return alpha[0][0]
    alpha = list(map(lambda(c,e):(c,fix_(e)),alpha))
    i = 1
    while i < len(alpha):
        if i == 0:
            i+=1
            continue
        c = ord_cmp_(alpha[i-1][1], alpha[i][1])
        if c < 0:
            alpha = alpha[0:i-1] + \
                    [(alpha[i][0], alpha[i][1])] + \
                    alpha[i+1:]
            i -= 1
        elif c == 0:
            alpha = alpha[0:i-1] + \
                    [(alpha[i-1][0] + alpha[i][0],
                      alpha[i][1])] + alpha[i+1:]
        elif c > 0:
            i += 1
    return list(map(unintfix_,alpha))

def prec_(alpha):
    assert not limit_(alpha) and alpha != 0 and \
           alpha != [(0,0)]
    if isinstance(alpha, int):
        return alpha - 1
    beta = alpha[:]
    if beta[-1][0] == 1:
        return fix_(beta[:-1])
    beta[-1] = (beta[-1][0]-1,beta[-1][1])
    return beta

def fund_(alpha,n):
    if not limit_(alpha):
        return alpha
    beta = alpha[:-1]
    lastc, lastv = alpha[-1]
    if lastc > 1:
        beta = beta + [(lastc-1,lastv)]
    if limit_(lastv):
        return beta + [(1,fund_(lastv,n))]
    else:
        return beta + [(n,prec_(lastv))]

def power_(f,n):
    def pow_f_n(m):
        k=m
        for i in xrange(n):
            k=f(k)
        return k
    return pow_f_n

def deepfund_(alpha,n):
    beta=alpha
    while limit_(beta):
        beta=fund_(beta,n)
    return beta

def ack_(alpha):
    if alpha == 1 or alpha == [(1,0)]:
        return lambda n: n*2
    if not limit_(alpha):
        return lambda n: power_(ack_(prec_(alpha)),n)(n)
    return lambda n: ack_(fund_(alpha,n))(n)

def trans_(n,alpha):
    beta = alpha
    m=n
    while True:
        yield beta
        if beta!=0 and beta!=[(0,0)]:
            beta = prec_(deepfund_(beta,m))
        m+=1

def u_(n,alpha):
    g=trans_(n,alpha)
    m=n
    while True:
        beta=g.next()
        if beta==0 or beta==[(0,0)]:
            return m
        m+=1

punchline = "I need a bigger universe to compute this."