# functions from SICP Python 4.1.1
def evaluate(component, env):
  if is_literal(component):
    return literal_value(component)
  elif is_name(component):
    return lookup_symbol_value(symbol_of_name(component), env)
  elif is_application(component):
    return apply(evaluate(function_expression(component), env),
                          llist_of_values(arg_expressions(component),
                                          env))
  elif is_operator_combination(component):
    return evaluate(operator_combination_to_application(component),
                    env)
  elif is_conditional(component):
    return eval_conditional(component, env)
  elif is_lambda_expression(component):
    return make_function(lambda_parameter_symbols(component),
                         make_return_statement(lambda_body(component)),
                         env)
  elif is_sequence(component):
    return eval_sequence(sequence_statements(component), env)
  elif is_return_statement(component):
    return eval_return_statement(component, env)
  elif is_function_definition(component):
    return evaluate(function_def_to_assignment(component), env)
  elif is_assignment(component):
    return eval_assignment(component, env)
  else:	return error("unknown syntax -- evaluate", component)
def apply(fun, arguments):
    if is_primitive_function(fun):
        return apply_primitive_function(fun, arguments)
    elif is_compound_function(fun):
        body = function_body(fun)
        locals = local_variables(body)
	unassigneds = llist_of_unassigned(locals)
        result = evaluate(body,
                          extend_environment(
                              append(function_parameters(fun),
			             locals),
                              append(arguments,
			             unassigneds),
                              function_environment(fun)))
        return (return_value_content(result)
                if is_return_value(result)
                else None)
    else:
        return error("unknown function type -- apply", fun)
def map(fun, items):
    return (None if is_none(items)
            else pair(fun(head(items)),
                      map(fun, tail(items))))
def llist_of_values(exps, env):
    return map(lambda arg: evaluate(arg, env), exps)
def eval_conditional(component, env):
    if is_truthy(evaluate(conditional_predicate(component), env)):
        return (evaluate(conditional_consequent(component), env)            
    else: return evaluate(conditional_alternative(component), env))
def eval_sequence(stmts, env):
    for_each(lambda stmt: evaluate(stmt, env), stmts)	    
    return None
def eval_return_statement(component, env):
    return make_return_value(evaluate(return_expression(component),
                                      env))
def eval_assignment(component, env):
    value = evaluate(assignment_value_expression(component), env)
    assign_symbol_value(assignment_symbol(component), value, env)
    return value
def eval_declaration(component, env):
    assign_symbol_value(
        declaration_symbol(component),
        evaluate(declaration_value_expression(component), env),
        env)
    return None

# functions from SICP JS 4.1.2
def is_tagged_list(component, the_tag):
    return is_pair(component) and head(component) == the_tag
def is_literal(component):
    return is_tagged_list(component, "literal")
def literal_value(component):
    return head(tail(component))
def make_literal(value):
    return llist("literal", value)
def is_name(component):
    return is_tagged_list(component, "name")
def make_name(symbol):
    return llist("name", symbol)
def symbol_of_name(component):
    return head(tail(component))
def is_assignment(component):
    return is_tagged_list(component, "assignment")
def assignment_symbol(component):
    return head(tail(head(tail(component))))
def assignment_value_expression(component):
    return head(tail(tail(component)))
def is_declaration(component):
    return is_tagged_list(component, "constant_declaration") or is_tagged_list(component, "variable_declaration") or is_tagged_list(component, "function_definition")
def is_lambda_expression(component):
    return is_tagged_list(component, "lambda_expression")
def lambda_parameter_symbols(component):
    return map(symbol_of_name, head(tail(component)))
def lambda_body(component):
    return head(tail(tail(component)))
def make_lambda_expression(parameters, body):
    return llist("lambda_expression", parameters, body)
def ref(items, n):
    return (head(items) if n == 0
            else ref(tail(items), n - 1))
def is_function_definition(component):
    return is_tagged_list(component, "function_definition")
def function_definition_name(component):
    return ref(component, 1)
def function_definition_parameters(component):
    return ref(component, 2)
def function_definition_body(component):
    return ref(component, 3)
def function_decl_to_constant_decl(component):
    return make_constant_declaration( function_definition_name(component), make_lambda_expression( function_definition_parameters(component), function_definition_body(component)))
def is_return_statement(component):
    return is_tagged_list(component, "return_statement")
def return_expression(component):
    return head(tail(component))
def is_conditional(component):
    return is_tagged_list(component, "conditional_expression") or is_tagged_list(component, "conditional_statement")
def conditional_predicate(component):
    return ref(component, 1)
def conditional_consequent(component):
    return ref(component, 2)
def conditional_alternative(component):
    return ref(component, 3)
def is_sequence(stmt):
    return is_tagged_list(stmt, "sequence")
def sequence_statements(stmt):
    return head(tail(stmt))
def first_statement(stmts):
    return head(stmts)
def rest_statements(stmts):
    return tail(stmts)
def is_empty_sequence(stmts):
    return is_none(stmts)
def is_last_statement(stmts):
    return is_none(tail(stmts))
def is_block(component):
    return is_tagged_list(component, "block")
def block_body(component):
    return head(tail(component))
def make_block(statement):
    return llist("block", statement)
def is_operator_combination(component):
    return is_unary_operator_combination(component) or is_binary_operator_combination(component)
def is_unary_operator_combination(component):
    return is_tagged_list(component, "unary_operator_combination")
def is_binary_operator_combination(component):
    return is_tagged_list(component, "binary_operator_combination")
def operator_symbol(component):
    return ref(component, 1)
def first_operand(component):
    return ref(component, 2)
def second_operand(component):
    return ref(component, 3)
def make_application(function_expression, argument_expressions):
    return llist("application", function_expression, argument_expressions)
def operator_combination_to_application(component):
    operator = operator_symbol(component)
    return make_application(make_name(operator), llist(first_operand(component))) if is_unary_operator_combination(component) else make_application(make_name(operator), llist(first_operand(component), second_operand(component)))
def is_application(component):
    return is_tagged_list(component, "application")
def function_expression(component):
    return head(tail(component))
def arg_expressions(component):
    return head(tail(tail(component)))

# functions from SICP JS 4.1.3
def is_truthy(x):
    return x if is_boolean(x) else error("boolean expected, received", x)
def is_falsy(x):
    return not is_truthy(x)
def make_function(parameters, body, env):
    return llist("compound_function", parameters, body, env)
def is_compound_function(f):
    return is_tagged_list(f, "compound_function")
def function_parameters(f):
    return ref(f, 1)

def function_body(f):
    return ref(f, 2)

def function_environment(f):
    return ref(f, 3)
def make_return_value(content):
    return llist("return_value", content)
def is_return_value(value):
    return is_tagged_list(value, "return_value")
def return_value_content(value):
    return head(tail(value))
def enclosing_environment(env):
    return tail(env)

def first_frame(env):
    return head(env)

the_empty_environment = None
def make_frame(symbols, values):
    return pair(symbols, values)

def frame_symbols(frame):
    return head(frame)

def frame_values(frame):
    return tail(frame)
def length(items):
    return (0 if is_none(items)
            else 1 + length(tail(items)))
def extend_environment(symbols, vals, base_env):
    return pair(make_frame(symbols, vals), base_env) if length(symbols) == length(vals) else error("too many arguments supplied: " + stringify(symbols) + ", " + stringify(vals)) if length(symbols) < length(vals) else error("too few arguments supplied: " + stringify(symbols) + ", " + stringify(vals))
def lookup_symbol_value(symbol, env):
    def env_loop(env):
        def scan(symbols, vals):
            return env_loop(enclosing_environment(env)) if is_none(symbols) else head(vals) if symbol == head(symbols) else scan(tail(symbols), tail(vals))
        if env == the_empty_environment:
            error("unbound name", symbol)
        else:
            frame = first_frame(env)
            return scan(frame_symbols(frame), frame_values(frame))
    return env_loop(env)
def assign_symbol_value(symbol, val, env):
    def env_loop(env):
        def scan(symbols, vals):
            return env_loop(enclosing_environment(env)) if is_none(symbols) else set_head(vals, val) if symbol == head(symbols) else scan(tail(symbols), tail(vals))
        if env == the_empty_environment:
            error("unbound name -- assignment", symbol)
        else:
            frame = first_frame(env)
            return scan(frame_symbols(frame), frame_values(frame))
    return env_loop(env)

# functions from SICP JS 4.1.4
def is_primitive_function(fun):
    return is_tagged_list(fun, "primitive")

def primitive_implementation(fun):
    return head(tail(fun))
primitive_functions = llist(llist("head", head), llist("tail", tail), llist("pair", pair), llist("list", list), llist("is_null", is_none), llist("display", print), llist("error", error), llist("math_abs", abs), llist("+", lambda x, y: (x + y)), llist("-", lambda x, y: (x - y)), llist("-unary", lambda x: (- x)), llist("*", lambda x, y: (x * y)), llist("/", lambda x, y: (x / y)), llist("%", lambda x, y: (x % y)), llist("===", lambda x, y: (x == y)), llist("!==", lambda x, y: (x != y)), llist("<", lambda x, y: (x < y)), llist("<=", lambda x, y: (x <= y)), llist(">", lambda x, y: (x > y)), llist(">=", lambda x, y: (x >= y)), llist("!", lambda x: ( not x)))
primitive_function_symbols = map(head, primitive_functions)
primitive_function_objects = map(lambda fun: (llist("primitive", head(tail(fun)))), primitive_functions)
primitive_constants = llist(llist("undefined", None), llist("Infinity", math_inf), llist("math_PI", math_pi), llist("math_E", math_e), llist("NaN", math_nan))
primitive_constant_symbols = map(lambda c: (head(c)), primitive_constants)
primitive_constant_values = map(lambda c: (head(tail(c))), primitive_constants)
def apply_primitive_function(fun, arglist):
    return apply_in_underlying_javascript(primitive_implementation(fun), arglist)
def append(list1, list2):
    return (list2 if is_none(list1)
            else pair(head(list1), append(tail(list1), list2)))
def setup_environment():
    return extend_environment(append(primitive_function_symbols, primitive_constant_symbols), append(primitive_function_objects, primitive_constant_values), the_empty_environment)
the_global_environment = setup_environment()

# functions from SICP JS 4.4.4
def type(exp):
    return head(exp) if is_pair(exp) else error("unknown expression type", exp)
def contents(exp):
    return tail(exp) if is_pair(exp) else error("unknown expression contents", exp)
def is_assertion(exp):
    return type(exp) == "assert"
def assertion_body(exp):
    return head(contents(exp))
# 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 make_binding(variable, value):
    return pair(variable, value)
def binding_variable(binding):
    return head(binding)
def binding_value(binding):
    return tail(binding)
def binding_in_frame(variable, frame):
    return assoc(variable, frame)
def extend(variable, value, frame):
    return pair(make_binding(variable, value), frame)
def instantiate_term(term, frame):
    if is_variable(term):
        binding = binding_in_frame(term, frame)
        return term if is_none(binding) else instantiate_term(binding_value(binding), frame)
    elif is_pair(term):
        return pair(instantiate_term(head(term), frame), instantiate_term(tail(term), frame))
    else:
        return term
def convert(term):
    return term if is_variable(term) else make_application(make_name("pair"), llist(convert(head(term)), convert(tail(term)))) if is_pair(term) else make_literal(term)
def instantiate_expression(expression, frame):
    return convert(instantiate_term(expression, frame)) if is_variable(expression) else pair(instantiate_expression(head(expression), frame), instantiate_expression(tail(expression), frame)) if is_pair(expression) else expression
def stream_append_delayed(s1, delayed_s2):
    return delayed_s2() if is_none(s1) else pair(head(s1), lambda : (stream_append_delayed(stream_tail(s1), delayed_s2)))
def interleave_delayed(s1, delayed_s2):
    return delayed_s2() if is_none(s1) else pair(head(s1), lambda : (interleave_delayed(delayed_s2(), lambda : (stream_tail(s1)))))
def stream_flatmap(fun, s):
    return flatten_stream(stream_map(fun, s))
def flatten_stream(stream):
    return None if is_none(stream) else interleave_delayed(head(stream), lambda : (flatten_stream(stream_tail(stream))))
def extend_if_consistent(variable, data, frame):
    binding = binding_in_frame(variable, frame)
    return extend(variable, data, frame) if is_none(binding) else pattern_match(binding_value(binding), data, frame)
def pattern_match(pattern, data, frame):
    return "failed" if frame == "failed" else frame if pattern == data else extend_if_consistent(pattern, data, frame) if is_variable(pattern) else pattern_match(tail(pattern), tail(data), pattern_match(head(pattern), head(data), frame)) if is_pair(pattern) and is_pair(data) else "failed"
def singleton_stream(x):
    return pair(x, lambda : (None))
def check_an_assertion(assertion, query_pat, query_frame):
    match_result = pattern_match(query_pat, assertion, query_frame)
    return None if match_result == "failed" else singleton_stream(match_result)
def get_stream(key1, key2):
    s = get(key1, key2)
    return None if is_none(s) else s
def index_key_of(pattern):
    return head(pattern)
def fetch_assertions(pattern, frame):
    return get_indexed_assertions(pattern)
def get_indexed_assertions(pattern):
    return get_stream(index_key_of(pattern), "assertion-stream")
def find_assertions(pattern, frame):
    return stream_flatmap(lambda datum: (check_an_assertion(datum, pattern, frame)), fetch_assertions(pattern, frame))
rule_counter = 0
def new_rule_application_id():
    rule_counter = rule_counter + 1
    return rule_counter
def make_new_variable(variable, rule_application_id):
    return make_name(symbol_of_name(variable) + "_" + stringify(rule_application_id))
def rename_variables_in(rule):
    rule_application_id = new_rule_application_id()
    def tree_walk(exp):
        return make_new_variable(exp, rule_application_id) if is_variable(exp) else pair(tree_walk(head(exp)), tree_walk(tail(exp))) if is_pair(exp) else exp
    return tree_walk(rule)
def depends_on(expression, variable, frame):
    def tree_walk(e):
        if is_variable(e):
            if variable == e:
                return True
            else:
                b = binding_in_frame(e, frame)
                return False if is_none(b) else tree_walk(binding_value(b))
        else:
            return tree_walk(head(e)) or tree_walk(tail(e)) if is_pair(e) else False
    return tree_walk(expression)
def extend_if_possible(variable, value, frame):
    binding = binding_in_frame(variable, frame)
    if  not  is_none(binding):
        return unify_match(binding_value(binding), value, frame)
    elif is_variable(value):
        binding = binding_in_frame(value, frame)
        return unify_match(variable, binding_value(binding), frame) if not is_none(binding) else extend(variable, value, frame)
    elif depends_on(value, variable, frame):
        return "failed"
    else:
        return extend(variable, value, frame)
def unify_match(p1, p2, frame):
    return "failed" if frame == "failed" else frame if p1 == p2 else extend_if_possible(p1, p2, frame) if is_variable(p1) else extend_if_possible(p2, p1, frame) if is_variable(p2) else unify_match(tail(p1), tail(p2), unify_match(head(p1), head(p2), frame)) if is_pair(p1) and is_pair(p2) else "failed"
def is_rule(assertion):
    return is_tagged_list(assertion, "rule")
def conclusion(rule):
    return head(tail(rule))

def rule_body(rule):
    return llist("always_true") if is_none(tail(tail(rule))) else head(tail(tail(rule)))
def apply_a_rule(rule, query_pattern, query_frame):
    clean_rule = rename_variables_in(rule)
    unify_result = unify_match(query_pattern, conclusion(clean_rule), query_frame)
    return None if unify_result == "failed" else evaluate_query(rule_body(clean_rule), singleton_stream(unify_result))
def fetch_rules(pattern, frame):
    return get_indexed_rules(pattern)
def get_indexed_rules(pattern):
    return get_stream(index_key_of(pattern), "rule-stream")
def apply_rules(pattern, frame):
    return stream_flatmap(lambda rule: (apply_a_rule(rule, pattern, frame)), fetch_rules(pattern, frame))
def simple_query(query_pattern, frame_stream):
    return stream_flatmap(lambda frame: (stream_append_delayed(find_assertions(query_pattern, frame), lambda : (apply_rules(query_pattern, frame)))), frame_stream)
def evaluate_query(query, frame_stream):
    qfun = get(type(query), "evaluate_query")
    return simple_query(query, frame_stream) if is_none(qfun) else qfun(contents(query), frame_stream)
def store_assertion_in_index(assertion):
    key = index_key_of(assertion)
    current_assertion_stream = get_stream(key, "assertion-stream")
    put(key, "assertion-stream", pair(assertion, lambda : (current_assertion_stream)))
def store_rule_in_index(rule):
    pattern = conclusion(rule)
    key = index_key_of(pattern)
    current_rule_stream = get_stream(key, "rule-stream")
    put(key, "rule-stream", pair(rule, lambda : (current_rule_stream)))
def add_rule_or_assertion(assertion):
    return add_rule(assertion) if is_rule(assertion) else add_assertion(assertion)
def add_assertion(assertion):
    store_assertion_in_index(assertion)
    return "ok"
def add_rule(rule):
    store_rule_in_index(rule)
    return "ok"
def is_empty_conjunction(exps):
    return is_none(exps)

def first_conjunct(exps):
    return head(exps)

def rest_conjuncts(exps):
    return tail(exps)
def is_empty_disjunction(exps):
    return is_none(exps)

def first_disjunct(exps):
    return head(exps)

def rest_disjuncts(exps):
    return tail(exps)
def negated_query(exps):
    return head(exps)
def javascript_predicate_expression(exps):
    return head(exps)
def conjoin(conjuncts, frame_stream):
    return frame_stream if is_empty_conjunction(conjuncts) else conjoin(rest_conjuncts(conjuncts), evaluate_query(first_conjunct(conjuncts), frame_stream))
put("and", "evaluate_query", conjoin)
def disjoin(disjuncts, frame_stream):
    return None if is_empty_disjunction(disjuncts) else interleave_delayed(evaluate_query(first_disjunct(disjuncts), frame_stream), lambda : (disjoin(rest_disjuncts(disjuncts), frame_stream)))
put("or", "evaluate_query", disjoin)
def negate(exps, frame_stream):
    return stream_flatmap(lambda frame: (singleton_stream(frame) if is_none(evaluate_query(negated_query(exps), singleton_stream(frame))) else None), frame_stream)
put("not", "evaluate_query", negate)
def javascript_predicate(exps, frame_stream):
    return stream_flatmap(lambda frame: (singleton_stream(frame) if evaluate(instantiate_expression(javascript_predicate_expression(exps), frame), the_global_environment) else None), frame_stream)
put("javascript_predicate", "evaluate_query", javascript_predicate)
def stream_tail(stream):
    return tail(stream)()
def stream_ref(s, n):
    return (head(s)
            if n == 0
            else stream_ref(stream_tail(s), n - 1))

def stream_map(f, s):
    return (None
            if is_none(s)
            else pair(f(head(s)),
                      lambda: stream_map(f, stream_tail(s))))

def stream_for_each(fun, s):
    if is_none(s):
        return True
    else:
        fun(head(s))
        return stream_for_each(fun, stream_tail(s))
max_display = 9
def display_stream(s):
    def display_stream_iter(st, n):
        if is_none(st):
            pass
        elif n == 0:
            display("", "...")
        else:
            display(head(st))
            display_stream_iter(stream_tail(st), n - 1)
    display_stream_iter(s, max_display)
def always_true(ignore, frame_stream):
    return frame_stream
put("always_true", "evaluate_query", always_true)
is_variable = is_name
def convert_to_query_syntax(exp):
    if is_application(exp):
        function_symbol = symbol_of_name(function_expression(exp))
        if function_symbol == "javascript_predicate":
            return pair(function_symbol, arg_expressions(exp))
        else:
            processed_args = map(convert_to_query_syntax, arg_expressions(exp))
            return pair(head(processed_args), head(tail(processed_args))) if function_symbol == "pair" else processed_args if function_symbol == "list" else pair(function_symbol, processed_args)
    elif is_variable(exp):
        return exp
    else:
        return literal_value(exp)
def is_list_construction(exp):
    return (is_literal(exp) and is_none(literal_value(exp))) or (is_application(exp) and is_name(function_expression(exp)) and symbol_of_name(function_expression(exp)) == "pair" and is_list_construction(head(tail(arg_expressions(exp)))))
def element_expressions(list_constr):
    return None if is_literal(list_constr) else pair(head(arg_expressions(list_constr)), element_expressions(head(tail(arg_expressions(list_constr)))))
def accumulate(op, initial, sequence):
    return (initial if is_none(sequence)
            else op(head(sequence),
                    accumulate(op, initial, tail(sequence))))
def comma_separated(strings):
    return accumulate(lambda s, acc: (s + ("" if acc == "" else ", " + acc)), "", strings)
def has_char(x, c):
    found = False
    i = 0
    while char_at(x, i) != None:
        found = found or char_at(x, i) == c
        i = i + 1
    return found
def better_stringify(x):
    return "'" + x + "'" if is_string(x) and not has_char(x, "'") else stringify(x)
def unparse(exp):
    return better_stringify(literal_value(exp)) if is_literal(exp) else symbol_of_name(exp) if is_name(exp) else unparse(make_application(make_name("list"), element_expressions(exp))) if is_list_construction(exp) else symbol_of_name(function_expression(exp)) + "(" + comma_separated(map(unparse, arg_expressions(exp))) + ")" if is_application(exp) and is_name(function_expression(exp)) else "(" + unparse(first_operand(exp)) + " " + operator_symbol(exp) + " " + unparse(second_operand(exp)) + ")" if is_binary_operator_combination(exp) else error("unknown syntax -- unparse", exp)
def user_read(prompt_string):
    return prompt(prompt_string)
input_prompt = "Query input:"
def query_driver_loop():
    input = user_read(input_prompt)
    if is_none(input):
        print("--- evaluator terminated ---")
    else:
        exp = parse(input + ";")
        q = convert_to_query_syntax(exp)
        print("---- driver loop input -----")
        print(unparse(exp))
        if is_assertion(q):
            add_rule_or_assertion(assertion_body(q))
            print("Assertion added to data base.")
        else:
            print("", "------ query results -------")
            display_stream(stream_map(lambda frame: (unparse(instantiate_expression(exp, frame))), evaluate_query(q, singleton_stream(None))))
        return query_driver_loop()
def process_query(input):
    if is_none(input):
        print("--- evaluator terminated ---")
    else:
        exp = parse(input + ";")
        q = convert_to_query_syntax(exp)
        if is_assertion(q):
            add_rule_or_assertion(assertion_body(q))
        else:
            print("", "------ query results -------")
            display_stream(stream_map(lambda frame: (unparse(instantiate_expression(exp, frame))), evaluate_query(q, singleton_stream(None))))
def first_answer(input):
    exp = parse(input + ";")
    q = convert_to_query_syntax(exp)
    frames = evaluate_query(q, singleton_stream(None))
    return "no matching data" if is_none(frames) else unparse(instantiate_expression(exp, head(frames)))
process_query("""assert(
rule(append_to_form(null, $y, $y)))""")
process_query("""assert(
rule(append_to_form(pair($u, $v), $y, pair($u, $z)),
     append_to_form($v, $y, $z)))""")
process_query("""assert(
rule(append_to_form(null, $y, $y)))""")
process_query("""assert(
rule(append_to_form(pair($u, $v), $y, pair($u, $z)),
     append_to_form($v, $y, $z)))""")
process_query("""append_to_form($x, $y, list("a", "b", "c", "d"))""")
