PE2013 Q5

pe2013_q5.js

// Question 5
 
function is_tagged_object(stmt,the_tag) {
    return is_object(stmt) &&
        stmt.tag === the_tag;
}
 
function is_self_evaluating(stmt) {
    return is_number(stmt) ||
        is_string(stmt) ||
        is_boolean(stmt);
}
 
function is_empty_list_statement(stmt) {
    return is_tagged_object(stmt,"empty_list");
}
 
function evaluate_empty_list_statement(stmt,env) {
    return [];
}
 
function is_variable(stmt) {
    return is_tagged_object(stmt,"variable");
}
 
function variable_name(stmt) {
    return stmt.name;
}
 
function enclosing_environment(env) {
    return tail(env);
}
function first_frame(env) {
    return head(env);
}
var the_empty_environment = [];
function is_empty_environment(env) {
    return is_empty_list(env);
}
function enclose_by(frame,env) {
    return pair(frame,env);
}
 
function lookup_variable_value(variable,env) {
    function env_loop(env) {
        if (is_empty_environment(env)) {
            error("Unbound variable: " + variable);
        } else if (has_binding_in_frame(variable,first_frame(env))) {
            return first_frame(env)[variable];
        } else {
            return env_loop(enclosing_environment(env));
        }
    }
    var val = env_loop(env);
    return val;
}
 
function is_var_definition(stmt) {
    return is_tagged_object(stmt,"var_definition");
}
function var_definition_variable(stmt) {
    return stmt.variable;
}
function var_definition_value(stmt) {
    return stmt.value;
}
 
function make_frame(variables,values) {
    if (is_empty_list(variables) && is_empty_list(values)) {
        return {};
    } else {
        var frame = make_frame(tail(variables),tail(values));
        frame[head(variables)] = head(values);
        return frame;
    }
}
 
function add_binding_to_frame(variable,value,frame) {
    frame[variable] = value;
    return undefined;
}
function has_binding_in_frame(variable,frame) {
    return has_own_property(frame, variable);
}
 
function define_variable(variable,value,env) {
    var frame = first_frame(env);
    return add_binding_to_frame(variable,value,frame);
}
 
function evaluate_var_definition(stmt,env) {
    define_variable(var_definition_variable(stmt),
                    evaluate(var_definition_value(stmt),env),
                    env);
    return undefined;
}
 
function is_if_statement(stmt) {
    return is_tagged_object(stmt,"if");
}
 
function if_predicate(stmt) {
    return stmt.predicate;
}
 
function if_consequent(stmt) {
    return stmt.consequent;
}
 
function if_alternative(stmt) {
    return stmt.alternative;
}
 
function is_true(x) {
    return x === true;
}
 
function is_false(x) {
    return x === false;
}
 
function evaluate_if_statement(stmt,env) {
    if (is_true(evaluate(if_predicate(stmt),env))) {
        return evaluate(if_consequent(stmt),env);
    } else {
        return evaluate(if_alternative(stmt),env);
    }
}
 
function is_function_definition(stmt) {
    return is_tagged_object(stmt,"function_definition");
}
 
function function_definition_parameters(stmt) {
    return stmt.parameters;
}
 
function function_definition_body(stmt) {
    return stmt.body;
}
 
function evaluate_function_definition(stmt,env) {
    return make_function_value(
        function_definition_parameters(stmt),
        function_definition_body(stmt),
        env);
}
function make_function_value(parameters,body,env) {
    return { tag: "function_value",
             parameters: parameters,
             body: body,
             environment: env };
}
 
function is_compound_function_value(f) {
    return is_tagged_object(f,"function_value");
}
 
function function_value_parameters(value) {
    return value.parameters;
}
 
function function_value_body(value) {
    return value.body;
}
 
function function_value_environment(value) {
    return value.environment;
}
 
function function_value_name(value) {
    return value.name;
}
 
function is_sequence(stmt) {
    return is_list(stmt);
}
 
function is_last_statement(stmts) {
    return is_empty_list(tail(stmts));
}
 
function first_statement(stmts) {
    return head(stmts);
}
function rest_statements(stmts) {
    return tail(stmts);
}
 
function evaluate_sequence(stmts,env) {
    if (is_last_statement(stmts)) {
        return evaluate(first_statement(stmts),env);
    } else {
        var first_stmt_value = 
            evaluate(first_statement(stmts),env);
        if (is_return_value(first_stmt_value)) {
            return first_stmt_value;
        } else {
            return evaluate_sequence(
            rest_statements(stmts),env);
        }
    }
}
 
function is_application(stmt) {
    return is_tagged_object(stmt,"application");
}
function operator(stmt) {
    return stmt.operator;
}
function operands(stmt) {
    return stmt.operands;
}
function no_operands(ops) {
    return is_empty_list(ops);
}
function first_operand(ops) {
    return head(ops);
}
function rest_operands(ops) {
    return tail(ops);
}
 
function is_primitive_function(fun) {
    return is_tagged_object(fun,"primitive");
}
function primitive_implementation(fun) {
    return fun;
}
 
function apply_primitive_function(fun,argument_list) {
    return apply_in_underlying_javascript(primitive_implementation(fun),
                                          argument_list);
}
 
function extend_environment(vars,vals,base_env) {
    var var_length = length(vars);
    var val_length = length(vals);
    if (var_length === val_length) {
        var new_frame = make_frame(vars,vals);
        return enclose_by(new_frame,base_env);
    } else if (var_length < val_length) {
        error("Too many arguments supplied: " + JSON.stringify(vars) +
              JSON.stringify(vals));
    } else {
        error("Too few arguments supplied: " + JSON.stringify(vars) +
              JSON.stringify(vals));
    }
}
 
function is_return_statement(stmt) {
    return is_tagged_object(stmt,"return_statement");
}
function return_statement_expression(stmt) {
    return stmt.expression;
}
 
function make_return_value(content) {
    return { tag: "return_value", content: content };
}
function is_return_value(value) {
    return is_tagged_object(value,"return_value");
}
function return_value_content(value) {
    return value.content;
}
 
function drop(n, xs) {
    if (is_empty_list(xs)) {
        return [];
    }else if (n === 0) {
        return xs;
    } else {
        return drop(n - 1, tail(xs));
    }
}// Drops the first n elements of a list xs
    // and returns whatever comes after
 
function take(n, xs) {
    // Returns the first n elements of a list xs
    // empty list base case, check if n > number of arguments in the list
    if (n === 0) {
        return [];
    } else {
        return pair(head(xs), take(n - 1, tail(xs)));
    }
}
 
function apply(fun,args) {
    if (is_primitive_function(fun)) {
        return apply_primitive_function(fun,args);
    } else if (is_compound_function_value(fun)) {
        if (length(function_value_parameters(fun)) === length(args)) {
            var env = extend_environment(function_value_parameters(fun),
                                         args,
                                         function_value_environment(fun));
            var result = evaluate(function_value_body(fun), env);
            if (is_return_value(result)) {
                return return_value_content(result);
            } else {
                return undefined;
            }
        } else {
            // error('Incorrect number of arguments supplied for function');
            if (length(function_value_parameters(fun)) > length(args)) {
                var new_parameters = drop(length(args),
                                          function_value_parameters(fun));
                var new_env = extend_environment(
                                take(length(args),
                                     function_value_parameters(fun)),
                                args,
                                function_value_environment(fun));
                return make_function_value(new_parameters,
                                           function_value_body(fun),
                                           new_env);
            } else {
                error('Incorrect number of arguments supplied for function');
            }
        } 
    } else {
        error("Unknown function type for application");
    }
}
 
function list_of_values(exps,env) {
    if (no_operands(exps)) {
        return [];
    } else {
        return pair(evaluate(first_operand(exps),env),
                    list_of_values(rest_operands(exps),env));
    }
}
 
var primitive_functions = 
    list(
        //Builtin functions
        pair("alert", alert),
        pair("prompt", prompt),
        pair("parseInt", parseInt),
 
        //List library functions
        pair("pair", pair),
        pair("head", head),
        pair("tail", tail),
        pair("list", list),
        pair("length", length),
        pair("map", map),
        pair("is_empty_list", is_empty_list),
 
        //Intepreter functions
        pair("parse", parse),
        pair("error", error),
 
        //Primitive functions
        pair("+", function(x,y) { return x + y; }),
        pair("-", function(x,y) { return x - y; }),
        pair("*", function(x,y) { return x * y; }),
        pair("/", function(x,y) { return x / y; }),
        pair("%", function(x,y) { return x % y; }),
        pair("===", function(x,y) { return x === y; }),
        pair("!==", function(x,y) { return x !== y; }),
        pair("<", function(x,y) { return x < y; }),
        pair(">", function(x,y) { return x > y; }),
        pair("<=", function(x,y) { return x <= y; }),
        pair(">=", function(x,y) { return x >= y; }),
        pair("!", function(x) { return ! x; })
    );
 
function primitive_function_names() {
    return map(function(x) { return head(x); },
               primitive_functions);
}
 
function primitive_function_objects() {
    return map(function(f) { return tail(f); },
               primitive_functions);
}
 
function evaluate(stmt,env) {
    if (is_self_evaluating(stmt)) {
        return stmt;
    } else if (is_empty_list_statement(stmt)) {
        return evaluate_empty_list_statement(stmt,env);
    } else if (is_variable(stmt)) {
        return lookup_variable_value(variable_name(stmt),env);
    } else if (is_var_definition(stmt)) {
        return evaluate_var_definition(stmt,env);
    } else if (is_if_statement(stmt)) {
        return evaluate_if_statement(stmt,env);
    } else if (is_function_definition(stmt)) {
        return evaluate_function_definition(stmt,env);
    } else if (is_sequence(stmt)) {
        return evaluate_sequence(stmt,env);
    } else if (is_application(stmt)) {
        return apply(
            evaluate(operator(stmt),env),
            list_of_values(operands(stmt),env));
    } else if (is_return_statement(stmt)) {
        return make_return_value(
            evaluate(return_statement_expression(stmt),
                     env));
    } else {
        error("Unknown expression type ");
    }
}
 
function evaluate_toplevel(stmt,env) {
    var value = evaluate(stmt,env);
    if (is_return_value(value)) {
        error("return not allowed outside of function definition");
    } else {
        return value;
    }
}
 
function setup_environment() {
    var initial_env = extend_environment(primitive_function_names(),
                                         primitive_function_objects(),
                                         the_empty_environment);
    return initial_env;
}
 
var the_global_environment = setup_environment();
 
function driver_loop() {
    var program_string = read("Enter your program here: ");
    var program_syntax = parse(program_string);
    if (is_tagged_object(program_syntax,"exit")) {
        return "interpreter completed";
    } else {
        var output = evaluate_toplevel(
            program_syntax, the_global_environment);
        write(output);
        return driver_loop();
    }
}
 
function parse_and_evaluate(string) {
    return evaluate_toplevel(parse(string),
                             the_global_environment);
}
 
function display_object(object) {
    display(JSON.stringify(object));
}
 
 
 
///////////////////////////////////
 
assert(
    function() {
        var res = parse_and_evaluate("
        function add(x, y) {
            return x + y;
        }
        var add5 = add(5);
        add5(3);");
        return res === 8;
    },
    "Q5T1",
    []
);
 
assert(
    function() {
        var res = parse_and_evaluate("
        function f(x,y,v,w) {
            return x * v + (y - w);
        }
        var g = f(2, 3);
        g(7, 5);");
        return res === 12;
    },
    "Q5T2",
    []
);