Let’s go write a Lisp ‐ part one

function lexer(input) {
  let pos = 0

  /* A couple of functions to help us grab the characters. */
  function next() {
    if (pos < input.length) {
      return input.charAt(pos++)
    }
    return null
  }

  function rewind() {
    pos--
  }

  /* Return a string.
   *
   * Strings are special because they can contain pretty much anything
   * except a double quote, so we can't break them on spaces. */
  function string() {
    let token = next()
    let c

    while ((c = next()) != null) {
      if (c == '"') {
        return token + c
      }
      // else
      token = token + c
    }

    /* If we get this far then the string wasn't terminated. I'll let
     * it slide this time. */
    return token
  }

  /* I've called this symbol, but it's actually anything that's not a
   * string or a bracket. */
  function symbol() {
    let token = ""
    let c

    while ((c = next()) != null) {
      /* Check that the character isn't whitespace or a closing
       * bracket. */
      if (/[\s\)]/.test(c)) {
        /* This character isn’t part of the token, so wind it back
         * into the input. */
        rewind()
        return token
      }
      // else
      token = token + c
    }

    /* Again, if we get here we've reached the end of the input. */
    return token
  }

  /* This is the main function. */
  return function() {
    let c

    while ((c = next()) != null) {
      if (/\s/.test(c)) {
        /* Whitespace, we don't care about this, so skip back to the
         * start of the loop. */
        continue
      }

      if (c == '"') {
        // It's a string!
        rewind()
        return string()
      }

      /* If it's a bracket, just return it as-is. */
      if (c == '(' || c == ')') {
        return c
      }

      /* It must be a symbol of some sort. We need to rewind otherwise
       * the first character will get lost. */
      rewind()
      return symbol()
    }

    // End of input.
    return null;
  }
}

const testInput = `(this is (a test) "We must have spaces and ()"
                   (brackets))`
const o = []
let t

/* Initialize the lexer. */
const l = lexer(testInput)

while ((t = l()) != null) {
  o.push(t)
}

console.log(o)

[
  '(',
  'this',
  'is',
  '(',
  'a',
  'test',
  ')',
  '"We must have spaces and ()"',
  '(',
  'brackets',
  ')',
  ')'
]

/* Pass in a tokenizer function. */
function parser(nextToken) {
  function string(token) {
    /* Strip the quotes off. */
    return token.replace(/^"|"$/g, '')
  }

  function symbol(token) {
    return Symbol.for(token)
  }

  function number(token) {
    return parseInt(token, 10)
  }

  function list() {
    let val
    const list = []

    /* Parse each item in the list and put the result into the
     * array. */
    while ((val = parser(nextToken)) != null) {
      list.push(val)
    }

    return list
  }

  const t = nextToken()

  /* If the token is null we’ve reached the end of input. */
  if (t === null) {
    return null
  }

  const first = t.charAt(0)

  if (first == '(') {
    /* It's a list! */
    return list()
  }
  else if (first == ')') {
    /* End of the current list, so return null. */
    return null
  }
  else if (/\d/.test(first)) {
    /* Congratulations, it's a number! */
    return number(t) 
  }
  else if (first == '"') {
    /* And a string. */
    return string(t)
  }
  // else
  return symbol(t)
}

const input = `(testing (the) (parser "is a") lot of (fun))
               (honest guv 😉)`

let l = lexer(input)
let r

while ((r = parser(l)) != null) {
  console.log(r)
}

[
  Symbol(testing),
  [ Symbol(the) ],
  [ Symbol(parser), 'is a' ],
  Symbol(lot),
  Symbol(of),
  [ Symbol(fun) ]
]
[ Symbol(honest), Symbol(guv), Symbol(😉) ]

const functions = {
  'display': function(...args) {
    console.log(args.join(' '))
  },
  '+': function(...args) {
    return args.reduce((a, b) => a + b, 0)
  },
  '=': function(...args) {
    return args.reduce((carry, x) => carry & (args[0] === x), true)
  },
  'if': function(pred, arg1, arg2) {
    if (pred) {
      return arg1
    }
    // else
    return arg2
  }
}