////////////////////////////////////////////////////////////////
// Expressions

// An Exp is one of
// - new Var(Name)
// - new Num(Number)
// - new Lam(String, Exp)
// - new App(Exp, Exp)
// And Name = String.

function Var(name) { this.name = name }
function Num(val)  { this.val = val }

function Lam(variable, body) {
  this.variable = variable;
  this.body = body }

function App(left, right) {
  this.left = left;
  this.right = right }

function isVar(exp) { return exp instanceof Var }
function isNum(exp) { return exp instanceof Num }
function isLam(exp) { return exp instanceof Lam }
function isApp(exp) { return exp instanceof App }

////////////////////////////////////////////////////////////////
// Values

// A Val is one of
// - makeClosure(Lam, Env)
// - Number

////////////////////////////////////////////////////////////////
// Evaluation

// evaluate : Exp Env -> Val
// Evaluate the given expression in the given environment, 
// which must close the expression.
function evaluate(exp, env) {
  return isVar(exp) ? lookup(exp, env) :
         isNum(exp) ? exp.val :
         isLam(exp) ? makeClosure(exp, env) :
         isApp(exp) ? (function () {
                        var fun = evaluate(exp.left, env);
                        var arg = evaluate(exp.right, env);
                        return fun(arg) })() :
         undefined }

// makeClosure : Lam Env -> (Val -> Val)
function makeClosure(lam, env) {
  return function (v) {
    return evaluate(lam.body, extend(env, lam.variable, v))}}

////////////////////////////////////////////////////////////////
// Environments

// A {Listof T} is one of
// - [], the empty array
// - [T, {Listof T}]
// And Env = {Listof [Name, Val]}

// lookup : Var Env -> Val
// Produces the binding of the given variable
// in the given environment.
function lookup(variable, env) {
  return variable.name === first(first(env))
       ? rest(first(env))
       : lookup(variable, rest(env))}

// extend : Env Name Val -> Env
// Produces an extended environment
// with the given name bound to the given value.
function extend(env, name, value) {
  return [[name, value], env]}

function first(p) { return p[0] }
function rest(p)  { return p[1] }

////////////////////////////////////////////////////////////////
// S-Expressions

// An S-Exp is one of
// - Name
// - Number
// - ["fun", Name, S-Exp]
// - [S-Exp, S-Exp]

// parse : S-Exp -> Exp
function parse(sexp) {
  return isString(sexp) ? new Var(sexp) :
         isNumber(sexp) ? new Num(sexp) :
         sexp[0] === "fun" ? new Lam(sexp[1], parse(sexp[2])) :
         new App(parse(sexp[0]), parse(sexp[1]))}

function isString(sexp) { return typeof sexp === "string" }
function isNumber(sexp) { return typeof sexp === "number" }

////////////////////////////////////////////////////////////////
// Examples

parse(5) 
//=> 
new Num(5)

parse("x") 
//=> 
new Var("x")

parse(["fun", "x", "x"]) 
//=> 
new Lam("x", parse("x"))

parse(["add1", 4]) 
//=>
new App(parse("add1"), parse(4))

evaluate(parse(3), [])
//=>
3

evaluate(parse(["fun", "x", "x"]), [])
//=> 
makeClosure(parse(["fun", "x", "x"]),[])

evaluate(parse([[["fun", "x", ["fun", "y", "x"]], 3], 7]), [])
//=> 
3

var initial_env = [["add1", (function (n) {return n+1})], []]

evaluate(
  parse([["fun", "d", [[[[["d", "d"], "d"], "d"], "add1"], 0]],
         ["fun", "f", ["fun", "x", ["f", ["f", "x"]]]]]),
  initial_env)
//=>
65536