Skip to content

Instantly share code, notes, and snippets.

@lqt0223
Last active July 8, 2022 02:04
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lqt0223/fc7f10bfb9147ace16ab006ccfe6d5e6 to your computer and use it in GitHub Desktop.
Save lqt0223/fc7f10bfb9147ace16ab006ccfe6d5e6 to your computer and use it in GitHub Desktop.
31 the eval-apply metacircular evaluator for Lisp implemented in JavaScript
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
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 }
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 }
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
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
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
}
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment