Small lambda calculus calculator without alpha conversion

abs.py

def var(name):
    return (0, name)

def abs(name, body):
    return (1, (name, body))

def app(callee, argument):
    return (2, (callee, argument))


def is_var(expr):
    return expr[0] == 0

def is_abs(expr):
    return expr[0] == 1

def is_app(expr):
    return expr[0] == 2


def unbox_expr(expr):
    return expr[1]


def match_expr(var_case, abs_case, app_case, expr):
    if is_var(expr):
        return var_case(unbox_expr(expr))

    elif is_abs(expr):
        (name, body) = unbox_expr(expr)
        return abs_case(name, body)

    elif is_app(expr):
        (callee, argument) = unbox_expr(expr)
        return app_case(callee, argument)


def to_string(expr):
    def var_case(name):
        return name

    def abs_case(name, body):
        return name + " -> " + to_string(body)

    def app_case(callee, argument):
        def bracket_abs(expr):
            if is_abs(expr):
                return "(" + to_string(expr) + ")"
            else:
                return to_string(expr)

        if is_app(argument):
            return bracket_abs(callee) + " (" + to_string(argument) + ")"
        else:
            return bracket_abs(callee) + " " + bracket_abs(argument)

    return match_expr(var_case, abs_case, app_case, expr)


def substitute(name, new, expr):
    def var_case(current):
        if current == name:
            return new
        else:
            return expr

    def abs_case(inner_name, body):
        if (name == inner_name):
            return expr
        else:
            return abs(inner_name, substitute(name, new, body))

    def app_case(callee, argument):
        return app(substitute(name, new, callee), substitute(name, new, argument))

    return match_expr(var_case, abs_case, app_case, expr)


# call by name
def weak_normalise(expr):
    if is_var(expr):
        return expr

    elif is_abs(expr):
        return expr

    elif is_app(expr):
        (callee, argument) = unbox_expr(expr)
        normalised_callee = weak_normalise(callee)

        if is_abs(normalised_callee):
            normalised_argument = weak_normalise(argument)
            (name, body) = unbox_expr(normalised_callee)
            return substitute(name, normalised_argument, body)
        else:
            return expr


expr = app(app(abs("x", var("x")), abs("y", var("y"))), var("z"))

print(to_string(expr))
print(to_string(weak_normalise(expr)))