31 the eval-apply metacircular evaluator for Lisp implemented in JavaScript

_readme.txt

This gist contains the implmentation of a eval-apply metacircular evaluator for Lisp.

Brief introduction on the following files:

test.js       - where you play with the evaluator
index.js      - where the global environment is set and the AST is constructed and evaulated
env.js        - the data structure for environment used in evaluation
parse.js      - tokenizing and parsing Lisp code
eval.js       - where the eval / apply mechanisms are implemented
primitives.js - where some primitive values and procedures of Lisp language are implemented

env.js

class Frame {
  constructor(bindings) {
    this.bindings = bindings || {}
  }
  set(name, value) {
    this.bindings[name] = value
  }
  get(name) {
    return this.bindings[name]
  }
}

class Env {
  constructor(env, frame) {
    this.frame = frame || new Frame()
    this.parent = env
    this.get = function get(name) {
      var result = this.frame.get(name)
      if (result !== undefined) {
        return result
      } else {
        if (this.parent) {
          return get.call(this.parent, name)
        } else {
          throw `Unbound variable ${name}`
        }
      }
    }
    this.set = function set(name, value) {
      var result = this.frame.get(name)
      if (result !== undefined) {
        this.frame.set(name, value)
      } else {
        if (this.parent) {
          return set.call(this.parent, name, value)
        } else {
          throw `Cannot set undefined variable ${name}`
        }
      }
    }
    this.define = (name, value) => {
      this.frame.set(name, value)
    }
    this.extend = (names, values) => {
      var frame = new Frame()
      for (var i = 0; i < names.length; i++) {
        var name = names[i]
        var value = values[i]
        frame.set(name, value)
      }
      var newEnv = new Env(this, frame)
      return newEnv
    }
  }
}

module.exports = { Env, Frame }

eval.js

class ASTNode {
  constructor(proc, args) {
    this.proc = proc
    this.args = args
  }
}

class Proc {
  constructor(params, body, env) {
    this.params = params
    this.body = body
    this.env = env
  }
}

var _eval = (ast, env) => {
  if (isNumber(ast)) {
    return evalNumber(ast)
  } else if (isString(ast)) {
    return evalString(ast)
  } else if (isVariable(ast)) {
    return lookUp(ast, env)
  } else if (isDefine(ast)) {
    return evalDefine(ast, env)
  } else if (isSet(ast)) {
    return evalSet(ast, env)
  } else if (isBegin(ast)) {
    return evalBegin(ast, env)
  } else if (isSequence(ast)) {
    return evalSequence(ast, env)
  } else if (isIf(ast)) {
    return evalIf(ast, env)
  } else if (isCond(ast)) {
    return _eval(condToIf(ast), env)
  } else if (isLambda(ast)) {
    return makeProcedure(ast, env)
  } else if (isProcedure(ast)) {
    var proc = _eval(ast.proc, env)
    var args = ast.args.map((arg) => {
      return _eval(arg, env)
    })
    return apply(proc, args)
  } else {
    throw 'Unknown expression'
  }
}

var apply = (proc, args) => {
  if (isPrimitive(proc)) {
    return applyPrimitive(proc, args)
  } else {
    var { params, body, env } = proc
    var newEnv = env.extend(params, args)
    return _eval(body, newEnv) 
  }
}

var isProcedure = (ast) => {
  return ast && ast.constructor && ast.constructor.name == 'ASTNode'
}

var isPrimitive = (ast) => {
  return ast && ast.constructor && ast.constructor.name == 'PrimitiveProc'
}

var applyPrimitive = (proc, args) => {
  var impl = proc.impl
  return impl.apply(null, args)
}

var isNumber = (ast) => {
  return /^[0-9.]+$/.test(ast) && ast.split('.').length <= 2
}

var isString = (ast) => {
  return ast[0] == '`'
}

var evalNumber = (ast) => {
  if (ast.split('.').length == 2) {
    return parseFloat(ast)
  } else {
     return parseInt(ast)
  }
}

var evalString = (ast) => {
  return ast.slice(1)
}

var isVariable = (ast) => {
  return typeof ast == 'string' && ast[0] != '`'
}

var lookUp = (ast, env) => {
  return env.get(ast)
}

var isDefine = (ast) => {
  return ast.proc == 'define'
}

var evalDefine = (ast, env) => {
  var name = ast.args[0]
  if (isProcedure(name)) {
    ast = defineProcToDefine(ast)
    name = ast.args[0]
  }
  var value = _eval(ast.args[1], env)
  env.define(name, value)
}

var defineProcToDefine = (ast) => {
  var procName = ast.args[0].proc
  var procParams = ast.args[0].args
  var procBody = ast.args.slice(1)

  var firstParam = procParams.shift()
  var paramNode = new ASTNode(firstParam, procParams)
  var lambdaNode = new ASTNode('lambda', [paramNode, procBody])
  return new ASTNode('define', [procName, lambdaNode])
}

var isSet = (ast) => {
  return ast.proc == 'set!'
}

var evalSet = (ast, env) => {
  var name = ast.args[0]
  var value = _eval(ast.args[1], env)
  env.set(name, value)
}

var isBegin = (ast) => {
  return ast.proc == 'begin'
}

var isSequence = (ast) => {
  return Array.isArray(ast)
}

var evalBegin = (ast, env) => {
  var sequence = ast.args
  return evalSequence(sequence)
}

var evalSequence = (sequence, env) => {
  var output
  sequence.forEach((ast) => {
    output = _eval(ast, env)
  })
  return output
}

var isIf = (ast) => {
  return ast.proc == 'if'
}

var evalIf = (ast, env) => {
  var predicate = ast.args[0]
  var thenBranch = ast.args[1]
  var elseBranch = ast.args[2]

  if (_eval(predicate, env)) {
    return _eval(thenBranch, env)
  } else {
    return _eval(elseBranch, env)
  }
}

var isCond = (ast) => {
  return ast.proc == 'cond'
}

var condToIf = (ast) => {
  var clauses = ast.args

  var predicates = clauses.map((clause) => clause.proc)
  var actions = clauses.map((clause) => clause.args)

  return _condToIf(predicates, actions)
}


var _condToIf = (predicates, actions) => {
  if (predicates.length != 0 && predicates.length == actions.length) {
    var pred = predicates.shift()
    var action = actions.shift()
    if (pred == 'else') {
      return action
    } else {
      return new ASTNode('if', [pred, action, _condToIf(predicates, actions)])
    }
  }
}

var isLambda = (ast) => {
  return ast.proc == 'lambda'
}

var astToArr = (ast) => {
  var arr = [ast.proc]
  arr = arr.concat(ast.args)
  return arr
}

var makeProcedure = (ast, env) => {
  var params = astToArr(ast.args[0])
  var body = ast.args[1]
  return new Proc(params, body, env)
}

module.exports = { _eval, ASTNode }

index.js

var { Env } = require('./env')
var { PRIMITIVES, PrimitiveProc, theEmptyList } = require('./primitives')
var lisp_parse = require('./parse')
var {_eval } = require('./eval')

var setupGlobalEnv = () => {
  var globalEnv = new Env(null)
  for (var method in PRIMITIVES) {
    var implementation = PRIMITIVES[method]
    globalEnv.define(method, new PrimitiveProc(method, implementation))
  }

  globalEnv.define('true', true)
  globalEnv.define('false', true)
  globalEnv.define('the-empty-list', theEmptyList)
  return globalEnv
}

var lisp_eval = (code) => {
  var globalEnv = setupGlobalEnv()
  var ast = lisp_parse(code)
  var output = _eval(ast, globalEnv)
  return output
}

module.exports = lisp_eval

parse.js

var { ASTNode } = require('./eval')

var lisp_beautify = (code) => {
  return code
  .replace(/\n/g, ' ') // replace line-breaks with spaces
  .replace(/\(/g, ' ( ') // append one space into each side of a left parenthesis
  .replace(/\)/g, ' ) ') // append one space into each side of a right parenthesis
  .replace(/\s{2,}/g, ' ') // shrink any space sequences longer than 2 into a single space
  .replace(/^\s/, '') // remove space on the head of the source code
  .replace(/\s$/, '') // remove space on the tail of the source code
}

var lisp_tokenize = (code) => {
  return code.split(' ')
}

var lisp_parse = (code) => {
  code = lisp_beautify(code)
  var tokens = lisp_tokenize(code)
  var ast = []
  while (tokens.length > 0) {
    ast.push(_parse(tokens))
  }
  return ast
}

var _parse = (tokens) => {
  if (tokens.length == 0) {
    throw 'Unexpected EOF'
  }
  var token = tokens.shift()
  if (token == '(') {
    var stack = []
    while (tokens[0] != ')') {
      stack.push(_parse(tokens))
    }
    tokens.shift()
    var proc = stack.shift()
    return new ASTNode(proc, stack)
  } else if (token == ')') {
    throw 'Unexpected )'
  } else {
    return token
  }
}

module.exports = lisp_parse

primitives.js

class PrimitiveProc {
  constructor(name, impl) {
    this.name = name
    this.impl = impl
  }
}

var cons = (a, b) => (m) => m(a, b)
var car = (pair) => pair((a, b) => a)
var cdr = (pair) => pair((a, b) => b)
var theEmptyList = cons(null, null)
var isListNull = (pair) => pair == null
var list = (...args) => {
  if (args.length == 0) {
    return theEmptyList
  } else {
    var head = args.shift()
    var tail = args
    return cons(head, list.apply(null, tail))
  }
}

var PRIMITIVES = {
  '+': (a, b) => a + b,
  '-': (a, b) => a - b,
  '*': (a, b) => a * b,
  '/': (a, b) => a / b,
  '>': (a, b) => a > b,
  '<': (a, b) => a < b,
  '=': (a, b) => a == b,
  'and': (a, b) => a && b,
  'or': (a, b) => a || b,
  'not': (a) => !a,
  'display': (a) => console.log(a),
  'cons': cons,
  'car': car,
  'cdr': cdr,
  'list': list,
  'null?': isListNull
}

module.exports = {
  PRIMITIVES,
  theEmptyList,
  PrimitiveProc
}

test.js

var lisp_eval = require('./index')

var code = `
(define (factorial n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))))
(factorial 6)
`
var result = lisp_eval(code)
console.log(result)