def ref(items, n):
    return (head(items) if n == 0
            else ref(tail(items), n - 1))
# 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 map(fun, items):
    return (None if is_none(items)
            else pair(fun(head(items)),
                      map(fun, tail(items))))
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 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.3.3
def is_amb(component):
    return is_tagged_list(component, "application") and is_name(function_expression(component)) and symbol_of_name(function_expression(component)) == "amb"
def amb_choices(component):
    return arg_expressions(component)
def analyze_name(component):
    return lambda env, succeed, fail: (succeed(lookup_symbol_value(symbol_of_name(component), env), fail))
def analyze_lambda_expression(component):
    params = lambda_parameter_symbols(component)
    bfun = analyze(lambda_body(component))
    return lambda env, succeed, fail: (succeed(make_function(params, bfun, env), fail))
def analyze_sequence(stmts):
    def sequentially(a, b):
        return lambda env, succeed, fail: (a(env, lambda a_value, fail2: (succeed(a_value, fail2) if is_return_value(a_value) else b(env, succeed, fail2)), fail))
    def loop(first_fun, rest_funs):
        return first_fun if is_none(rest_funs) else loop(sequentially(first_fun, head(rest_funs)), tail(rest_funs))
    funs = map(analyze, stmts)
    return lambda env: (None) if is_none(funs) else loop(head(funs), tail(funs))
def analyze_declaration(component):
    symbol = declaration_symbol(component)
    vfun = analyze(declaration_value_expression(component))
    def the_declaration(env, succeed, fail):
        def success(val, fail2):
            assign_symbol_value(symbol, val, env)
            return succeed(None, fail2)
        return vfun(env, success, fail)
    return the_declaration
def analyze_assignment(component):
    symbol = assignment_symbol(component)
    vfun = analyze(assignment_value_expression(component))
    def the_assignment(env, succeed, fail):
        def success(val, fail2):              # *1*
            old_value = lookup_symbol_value(symbol, env)
            assign_symbol_value(symbol, val, env)
            def restore():                    # *2*
                assign_symbol_value(symbol, old_value, env)
                return fail2()
            return succeed(val, restore)
        return vfun(env, success, fail)
    return the_assignment
def analyze_conditional(component):
    pfun = analyze(conditional_predicate(component))
    cfun = analyze(conditional_consequent(component))
    afun = analyze(conditional_alternative(component))
    return lambda env, succeed, fail: (pfun(env, lambda pred_value, fail2: (cfun(env, succeed, fail2) if is_truthy(pred_value) else afun(env, succeed, fail2)), fail))
def accumulate(op, initial, sequence):
    return (initial if is_none(sequence)
            else op(head(sequence),
                    accumulate(op, initial, tail(sequence))))
def scan_out_bindings(component):
    if is_sequence(component):
        return accumulate(append,
                          None,
                          map(scan_out_bindings,
                              sequence_statements(component)))
    elif is_conditional(component):
        return append(scan_out_bindings(conditional_consequent),
                      scan_out_bindings(conditional_alternative)),
    elif is_assignment(component):
        return llist(assignment_symbol(component))
    elif is_assignment(component):
        return llist(assignment_symbol(component))
    else None
def llist_of_unassigned(symbols):
    return map(lambda symbol: "*unassigned*", symbols)
def analyze_block(component):
    body = block_body(component)
    locals = scan_out_declarations(body)
    unassigneds = list_of_unassigned(locals)
    bfun = analyze(body)
    return lambda env, succeed, fail: (bfun(extend_environment(locals, unassigneds, env), succeed, fail))
def analyze_return_statement(component):
    rfun = analyze(return_expression(component))
    return lambda env, succeed, fail: (rfun(env, lambda val, fail2: (succeed(make_return_value(val), fail2)), fail))
def get_args(afuns, env, succeed, fail):
    return succeed(None, fail) if is_none(afuns) else head(afuns)(env, lambda arg, fail2: (get_args(tail(afuns), env, lambda args, fail3: (succeed(pair(arg, args), fail3)), fail2)), fail)
def execute_application(fun, args, succeed, fail):
    return succeed(apply_primitive_function(fun, args), fail) if is_primitive_function(fun) else function_body(fun)(extend_environment(function_parameters(fun), args, function_environment(fun)), lambda body_result, fail2: (succeed(return_value_content(body_result) if is_return_value(body_result) else None, fail2)), fail) if is_compound_function(fun) else error("unknown function type - execute_application", fun)
def analyze_application(component):
    ffun = analyze(function_expression(component))
    afuns = map(analyze, arg_expressions(component))
    return lambda env, succeed, fail: (ffun(env, lambda fun, fail2: (get_args(afuns, env, lambda args, fail3: (execute_application(fun, args, succeed, fail3)), fail2)), fail))
def analyze_amb(component):
    cfuns = map(analyze, amb_choices(component))
    def _lambda_1(env, succeed, fail):
        def try_next(choices):
            return fail() if is_none(choices) else head(choices)(env, succeed, lambda : (try_next(tail(choices))))
        return try_next(cfuns)
    return _lambda_1
def analyze(component):
    return analyze_literal(component) if is_literal(component) else analyze_name(component) if is_name(component) else analyze_amb(component) if is_amb(component) else analyze_application(component) if is_application(component) else analyze(operator_combination_to_application(component)) if is_operator_combination(component) else analyze_conditional(component) if is_conditional(component) else analyze_lambda_expression(component) if is_lambda_expression(component) else analyze_sequence(sequence_statements(component)) if is_sequence(component) else analyze_block(component) if is_block(component) else analyze_return_statement(component) if is_return_statement(component) else analyze(function_decl_to_constant_decl(component)) if is_function_definition(component) else analyze_declaration(component) if is_declaration(component) else analyze_assignment(component) if is_assignment(component) else error("unknown syntax -- analyze", component)
def ambeval(component, env, succeed, fail):
    return analyze(component)(env, succeed, fail)
def first_solution(input):
    return ambeval(parse("{ " + input + " }"), the_global_environment, lambda val, next_alternative: (val), lambda : (None))
def reverse(items):
    def reverse_iter(items, result):
        return (result if is_none(items)
                else reverse_iter(tail(items),
                                  pair(head(items), result)))
    return reverse_iter(items, None)
def all_solutions(input):
    solutions = None
    def internal_loop(input, retry):
        if input == "retry":
            return retry()
        else:
            def on_success(val, next_alternative):
                nonlocal solutions
                solutions = pair(val, solutions)
                return internal_loop("retry", next_alternative)
            return ambeval(parse("{ " + input + " }"),
                       the_global_environment,
                       on_success,
                       lambda: None)
    def internal_error():
        print("// internal error")
    internal_loop(input, internal_error)
    return reverse(solutions)
def member(item, x):
    return (None if is_none(x)
            else x if item == head(x)
            else member(item, tail(x)))
full_parser = "                                                \
function require(p) {                                                \
    return ! p ? amb() : 'Satisfied require';                        \
}                                                                    \
function member(item, x) {                                           \
    return is_null(x)                                                \
        ? null                                                       \
        : item === head(x)                                           \
          ? x                                                        \
          : member(item, tail(x));                                   \
}                                                                    \
let unparsed = null;                                                 \
function parse_word(word_list) {                                     \
    require(! is_null(unparsed));                                    \
    require(! is_null(member(head(unparsed), tail(word_list))));     \
    const found_word = head(unparsed);                               \
    unparsed = tail(unparsed);                                       \
    return list(head(word_list), found_word);                        \
}                                                                    \
const prepositions = list('prep', 'for', 'to',  'in', 'by', 'with'); \
function parse_prepositional_phrase() {                              \
    return list('prep-phrase',                                       \
                parse_word(prepositions),                            \
                parse_noun_phrase());                                \
}                                                                    \
const nouns = list('noun', 'student', 'professor', 'cat', 'class');  \
const verbs = list('verb', 'studies', 'lectures', 'eats', 'sleeps'); \
                                                                     \
const articles = list('article', 'the', 'a');                        \
function parse_simple_noun_phrase() {                                \
    return list('simple-noun-phrase',                                \
                parse_word(articles),                                \
                parse_word(nouns));                                  \
}                                                                    \
function parse_noun_phrase() {                                       \
    function maybe_extend(noun_phrase) {                             \
        return amb(noun_phrase,                                      \
                   maybe_extend(list('noun-phrase',                  \
                                 noun_phrase,                        \
                                 parse_prepositional_phrase())));    \
    }                                                                \
    return maybe_extend(parse_simple_noun_phrase());                 \
}                                                                    \
function parse_sentence() {                                          \
    return list('sentence',                                          \
                parse_noun_phrase(),                                 \
                parse_verb_phrase());                                \
}                                                                    \
function parse_verb_phrase() {                                       \
    function maybe_extend(verb_phrase) {                             \
        return amb(verb_phrase,                                      \
                   maybe_extend(list('verb-phrase',                  \
                                 verb_phrase,                        \
                                 parse_prepositional_phrase())));    \
    }		                                                     \
    return maybe_extend(parse_word(verbs));                          \
}                                                                    \
function parse_input(input) {                                        \
    unparsed = input;                                                \
    const sent = parse_sentence();                                   \
    require(is_null(unparsed));                                      \
    return sent;                                                     \
}                                                                    "
def analyze_literal(component):
    return lambda env, succeed, fail: (succeed(literal_value(component), fail))

ref(ref(ref(ref(ref(all_solutions(full_parser + 
"                                                                   \
parse_input(list('the', 'student', 'with', 'the', 'cat',            \
'sleeps', 'in', 'the', 'class'));                                   "),
                                             0),
                                    2),
                           2),
                  2),
         1)
