Let’s go write a Lisp ‐ part two

This is the second part of an attempt to write a Lisp‐like language as a meta‐circular evaluator in JavaScript. So far we’ve got it taking in a string and executing functions, but not much else. Here’s part one.

Variables

‘That’s all well and good’, I hear you cry, ‘but what about variables? How am I supposed to get any work done without being able to store things?’

OK, so I guess we can add variables.

First of all we’ll need somewhere to store them. Remember that object that we put all our functions into? Let’s rename that global. For convenience we’ll create a lispDefine function that stores things in it.

Finally we’ll create a lookup function for retrieving the values. We can use this in lispEval to do a look‐up for all symbols.

/* Environment object. */
const global = {}

/* A helper function for defining lisp variables. */
function lispDefine(env, name, value) {
  if (typeof name === "string") {
    env[Symbol.for(name)] = value
  }
  else if (typeof name === "symbol") {
    env[name] = value
  }
  else {
    throw "DEFINE: Unexpected type '" + typeof name
      + "' for '" + name + "'!"
  }
}

function lookupVariable(env, name) {
  if (env.hasOwnProperty(name)) {
    return env[name]
  }
  else {
    throw "LOOKUP: Unknown variable '" + Symbol.keyFor(name) + "'!"
  }
}

lispDefine(global, 'display', function(...args) {
  console.log(args.join(' '))
})

lispDefine(global, '+', function(...args) {
  return args.reduce((a, b) => a + b, 0)
})

lispDefine(global, '=', function(...args) {
  return args.reduce((carry, x) => carry & (args[0] === x), true)
})

function lispEval(item) {
  if (typeof item === "symbol") {
    return lookupVariable(global, item)
  }
  else if (Array.isArray(item)) {
    /* Check if the function is an "if". */
    if (item[0] === Symbol.for('if')) {
      lispIf(item.slice(1))
    }
    /* Or a "define". */
    else if (item[0] === Symbol.for('define')) {
      lispDefine(global, item[1], lispEval(item[2]))
    }
    else {
      /* We must always eval the function name element of the array as
       * we have no guarantee it's a function. */
      const f = lispEval(item[0])

      try {
        return lispApply(f, item.slice(1))
      }
      catch(err) {
        throw err + "\nEVAL: Calling '" + JSON.stringify(item[0]) + "'"
      }
    }
  }
  else {
    return item
  }
}

lispEval(parser(lexer('(define cows "moo 🐄")')))
lispEval(parser(lexer('(display cows)')))

moo 🐄

Functions

So far so good, but we have to write our functions in JavaScript, which is OK, I guess, but not very exciting. Let’s make a lambda function.

One thing we need to bear in mind is that we need to look up variables, which could be either local to the function or global. To save us having to do two look‐ups (local and global) for each variable we’ll build a data structure containing the local variables, and the global environment object. Then we can modify lookupVariable to check each in turn. (More recursion!)

/* Make a new environment object. */
function newEnvironment(parent) {
  const e = {}
  e.parent = parent
  return e
}

/* A helper function for defining lisp variables. */
function lispDefine(env, name, value) {
  if (typeof name === "string") {
    env[Symbol.for(name)] = value
  }
  else if (typeof name === "symbol") {
    env[name] = value
  }
  else {
    throw "DEFINE: Unexpected type '" + typeof name
          + "' for '" + name + "'!"
  }
}

function lookupVariable(env, name) {
  if (env.hasOwnProperty(name)) {
    return env[name]
  }
  else if (env.parent !== null) {
    /* Look it up in the parent environment. */
    return lookupVariable(env.parent, name)
  }
  else {
    throw "LOOKUP: Unknown variable '" + Symbol.keyFor(name) + "'!"
  }
}

const global = newEnvironment(null)

We’ll use a closure to contain the lisp code within a JavaScript function. This means we don’t have to differentiate between JavaScript and lisp functions within lispApply because they’re all just JavaScript functions!

function lambda(env, argnames, body) {
  return function(...args) {
    /* We need to build up a stack frame for this function where we
     * store local variables, eg. the arguments. */
    const localEnv = newEnvironment(env)

    /* For each arg, a, define a variable named argnames[i]. */
    args.forEach((a, i) => lispDefine(localEnv, argnames[i], a))

    /* And eval each expression in the body with our new environment.
     *
     * TODO: add a begin function and use it here. */
    return body.reduce((c, s) => lispEval(localEnv, s), null)
  }
}

Add environment handling to our other functions.

function lispIf(env, args) {
  /* Test argument 0 and evaluate argument 1 or 2 as appropriate. */
  if (lispEval(env, args[0])) {
    return lispEval(env, args[1])
  }
  // else
  return lispEval(env, args[2])
}

function lispApply(env, f, args) {
  if (typeof f !== "function") {
    throw "APPLY: Unknown function!"
  }

  const a = args.map((a) => lispEval(env, a))
  return f.apply(null, a)
}

And finally add environment handling to lispEval too, and because lambda is another special form we add it to lispEval. The arguments shouldn’t be evaluated, otherwise the function would be evaluated when we declare it instead of when we call it.

function lispEval(env, item) {
  if (typeof item === "symbol") {
    return lookupVariable(env, item)
  }
  else if (Array.isArray(item)) {
    /* Check if the function is an "if". */
    if (item[0] === Symbol.for('if')) {
      return lispIf(env, item.slice(1))
    }
    /* Or a "define". */
    else if (item[0] === Symbol.for('define')) {
      lispDefine(env, item[1], lispEval(env, item[2]))
    }
    /* Or "lambda"... */
    else if (item[0] === Symbol.for('lambda')) {
      return lambda(env, item[1], item.slice(2))
    }
    /* Or "quote". (Return the argument unmodified.) */
    else if (item[0] === Symbol.for('quote')) {
      return item[1]
    }
    else {
      try {
        return lispApply(env, lispEval(env, item[0]), item.slice(1))
      }
      catch(err) {
        throw err + "\nEVAL: Calling '" + JSON.stringify(item[0]) + "'"
      }
    }
  }
  else {
    return item
  }
}

lispEval(global, parser(lexer('(define cows (lambda (x) (display "cows" x "moo 🐄")))')))
lispEval(global, parser(lexer('(cows "go")')))

cows go moo 🐄

Looks good. Let’s try something more complex.

const sexp = `
  (define fib (lambda (n)
    (define iter (lambda (a b count)
                   (if (= n count)
                       (+ a b)
                       (iter b (+ a b) (+ count 1)))))
    (iter 1 1 3)))
`

lispEval(global, parser(lexer(sexp)))
lispEval(global, parser(lexer('(display "The 12th Fibonacci number is:" (fib 12))')))

The 12th Fibonacci number is 144. Let’s see what we get…

The 12th Fibonacci number is: 144

Wooo!

It may not be immediately obvious, but our lisp has lexical scope and you can use closures. This is because we’re passing lambda the environment of the calling function and it’s stored within the JavaScript closure that lambda creates, just like the program code itself.

REPL(ish)

I’ve hacked together a rather dodgy REPL.

I’ve added some more functions:

Arithmetic: +, -, *, /, , >, <, >, <=, %
Boolean arithmetic: and, or, not
Array handling: first, rest, push, pop, shift, unshift, array-ref, concat
Strings: split (no need for join as you can use ’+’ for that)
Flow control: map, reduce
Others: null (returns null, shockingly), get-js-context (you can use this to get JavaScript functions)

The complete code is here, and you can try it out below.