# chapter=4 
def map(fun, items):
    return (None if is_none(items)
            else pair(fun(head(items)),
                      map(fun, tail(items))))
# In Source, most functions have a fixed number of arguments.
# (The function llist is the only exception, to this so far.)
# The function apply_in_underlying_javascript allows us to
# apply any given function fun to all elements of the argument
# linked list args, as if they were separate arguments
def apply(fun, args):
    return apply_in_underlying_javascript(fun, args)
def apply_generic(op, args):
    type_tags = map(type_tag, args)
    fun = get(op, type_tags)
    return (apply_in_underlying_javascript(fun, map(contents, args))
            if not is_none(fun)
            else error("no method for these types -- apply_generic",
                       llist(op, type_tags)))
def add(x, y): return apply_generic("add", llist(x, y))

def sub(x, y): return apply_generic("sub", llist(x, y))

def mul(x, y): return apply_generic("mul", llist(x, y))

def div(x, y): return apply_generic("div", llist(x, y))
# operation_table, put and get
# from chapter 3 (section 3.3.3)
def assoc(key, records):
    return (None
            if is_none(records)
            else head(records)
            if key == head(head(records))
            else assoc(key, tail(records)))
def make_table():
    local_table = llist("*table*")
    def lookup(key_1, key_2):
        subtable = assoc(key_1, tail(local_table))
        if is_none(subtable):
            return None
        else:
            record = assoc(key_2, tail(subtable))
            return (None
                    if is_none(record)
                    else tail(record))
    def insert(key_1, key_2, value):
        subtable = assoc(key_1, tail(local_table))
        if is_none(subtable):
            set_tail(local_table,
                     pair(llist(key_1, pair(key_2, value)),
                          tail(local_table)))
        else:
            record = assoc(key_2, tail(subtable))
            if is_none(record):
                set_tail(subtable,
                         pair(pair(key_2, value), tail(subtable)))
            else:
                set_tail(record, value)
    def dispatch(m):
        return (lookup if m == "lookup"
                else insert if m == "insert"
                else error("unknown operation -- table", m))
    return dispatch
operation_table = make_table()
get = operation_table("lookup")
put = operation_table("insert")
def attach_tag(type_tag, contents):
    return pair(type_tag, contents)
def type_tag(datum):
    return (head(datum)
            if is_pair(datum)
            else error("bad tagged datum -- type_tag", datum))
def contents(datum):
    return (tail(datum)
            if is_pair(datum)
            else error("bad tagged datum -- contents", datum))
def install_python_number_package():
    def tag(x):
        return attach_tag("python_number", x)
    put("add", llist("python_number", "python_number"),
        lambda x, y: tag(x + y))
    put("sub", llist("python_number", "python_number"),
        lambda x, y: tag(x - y))
    put("mul", llist("python_number", "python_number"),
        lambda x, y: tag(x * y))
    put("div", llist("python_number", "python_number"),
        lambda x, y: tag(x / y))
    put("make", "python_number",
        lambda x: tag(x))
    return "done"
print(install_python_number_package())
def make_python_number(n):
    return get("make", "python_number")(n)
def is_variable(x): return is_string(x)
def is_same_variable(v1, v2):
    return is_variable(v1) and is_variable(v2) and v1 == v2
def install_python_number_is_equal_to_zero():
    put("is_equal_to_zero", llist("python_number"),
        lambda x: x == 0)
    return "done"
install_python_number_is_equal_to_zero()

def is_equal_to_zero(x):
    return apply_generic("is_equal_to_zero", llist(x))

def install_polynomial_package():

    # internal functions

    # representation of poly
    def make_poly(variable, term_list):
        return pair(variable, term_list)
    def variable(p): return head(p)
    def term_list(p): return tail(p)

    # representation of terms and term lists
    def adjoin_term(term, term_list):
        return (term_list
                if is_equal_to_zero(coeff(term))
                else pair(term, term_list))
    the_empty_termlist = None
    def first_term(term_list):
        return head(term_list)
    def rest_terms(term_list):
        return tail(term_list)
    def is_empty_termlist(term_list):
        return is_none(term_list)
    def make_term(order, coeff):
        return llist(order, coeff)
    def order(term):
        return head(term)
    def coeff(term):
        return head(tail(term))

    def add_poly(p1, p2):
        return (make_poly(variable(p1),
                          add_terms(term_list(p1),
                                    term_list(p2)))
                if is_same_variable(variable(p1), variable(p2))
                else error("polys not in same var -- add_poly",
                           llist(p1, p2)))

    def add_terms(L1, L2):
        if is_empty_termlist(L1):
          return L2
        elif is_empty_termlist(L2):
          return L1
        else:
            t1 = first_term(L1)
            t2 = first_term(L2)
            return (adjoin_term(t1, add_terms(rest_terms(L1), L2))
                    if order(t1) > order(t2)
                    else adjoin_term(t2, add_terms(L1, rest_terms(L2)))
                    if order(t1) < order(t2)
                    else adjoin_term(make_term(order(t1),
                                               add(coeff(t1),
                                                   coeff(t2))),
                                     add_terms(rest_terms(L1),
                                               rest_terms(L2))))

    def mul_poly(p1, p2):
        return (make_poly(variable(p1),
                          mul_terms(term_list(p1),
                                    term_list(p2)))
                if is_same_variable(variable(p1), variable(p2))
                else error("polys not in same var -- mul_poly",
                           llist(p1, p2)))

    def mul_terms(L1, L2):
        return (the_empty_termlist
                if is_empty_termlist(L1)
                else add_terms(mul_term_by_all_terms(
                                      first_term(L1), L2),
                               mul_terms(rest_terms(L1), L2)))
    def mul_term_by_all_terms(t1, L):
        if is_empty_termlist(L):
            return the_empty_termlist
        else:
            t2 = first_term(L)
            return adjoin_term(
                       make_term(order(t1) + order(t2),
                                 mul(coeff(t1), coeff(t2))),
                       mul_term_by_all_terms(t1, rest_terms(L)))

    # interface to rest of the system
    def tag(p):
        return attach_tag("polynomial", p)
    put("add", llist("polynomial", "polynomial"),
        lambda p1, p2: tag(add_poly(p1, p2)))
    put("mul", llist("polynomial", "polynomial"),
        lambda p1, p2: tag(mul_poly(p1, p2)))
    put("make", "polynomial",
        lambda variable, terms:
            tag(make_poly(variable, terms)))
    return "done"
print(install_polynomial_package())
def make_polynomial(variable, terms):
    return get("make", "polynomial")(variable, terms)
p1 = make_polynomial("x",
                     llist(llist(2, make_python_number(4)),
                           llist(1, make_python_number(3)),
                           llist(0, make_python_number(7))))
p2 = make_polynomial("x",
                     llist(llist(2, make_python_number(5)),
                           llist(1, make_python_number(2)),
                           llist(0, make_python_number(10))))

print(head(tail(tail(tail(mul(p1, p2))))))

