Lisp Interpreter written in JavaScript

Question

I had a task to reduce my Lisp Interpreter from 400 lines to 120 lines. I was able to bring it down to 255 lines without including newline after every function. I'm not able to figure out where I can reduce the lines of code. I wanted a different perspective to my code probably a repeating pattern which i'm not able to find. What all improvements can I push to my code?

GitHub

Input file

var input = require('fs').readFileSync('newexample.txt', 'utf-8') const ENV = {} let mat, regexp = /^[0-9]+/, output const spaceParser = (input) => (mat = input.match(/^[\s\t\n]+/)) ? [mat[0], input.slice(mat[0].length)] : null const identifierParser = (input) => (mat = input.match(/^[a-z]+[0-9]*[a-z]*/i)) ? [mat[0], input.slice(mat[0].length)] : null const numberParser = (input) => (mat = regexp.exec(input)) ? [parseInt(mat[0]), input.slice(mat[0].length)] : null const stringParser = (data) => { if (data[0] === '"') { data = data.substring(1, data.length) let i = data.search('"') return ([data.substring(0, i), data.slice(i + 1)]) } return null } const add = input => input.reduce((accum, value) => (ENV[value]) ? accum + ENV[value] : accum + value, 0) const sub = input => input.reduce((accum, value) => (ENV[value]) ? accum - ENV[value] : accum - value) const mul = input => input.reduce((accum, value) => (ENV[value]) ? accum * ENV[value] : accum * value, 1) const div = input => input.reduce((accum, value) => (ENV[value]) ? accum / ENV[value] : accum / value) const greaterThan = (a, b) => a > b const lessThan = (a, b) => a < b const greaterThanEqualTo = (a, b) => a >= b const lessThanEqualTo = (a, b) => a <= b const EqualTo = (a, b) => a === b const notNumber = (a) => !a const maxNumber = (a, b) => a > b ? a : b const minNumber = (a, b) => a < b ? a : b const listCall = (a) => { return { type: 'list', args: a } } const listCar = (a) => a[0].shift() const listCdr = (a) => { a[0].shift() return a[0] } const listCons = (a) => { a[1].unshift(a[0]) return a[1] } const isListLisp = (a) => !!(Array.isArray(a)) const defineLisp = (a, b) => { ENV[a] = b } const printLisp = (a) => (ENV[a]) ? console.log(ENV[a]) : a const ifLisp = (a, b, c) => a ? b : c const plusParser = (data) => data.startsWith('+') ? [add, data.slice(1)] : null const minusParser = (data) => data.startsWith('-') ? [sub, data.slice(1)] : null const mulParser = (data) => data.startsWith('*') ? [mul, data.slice(1)] : null const divParser = (data) => data.startsWith('/') ? [div, data.slice(1)] : null const greaterThanParser = (data) => data.startsWith('>') ? [greaterThan, data.slice(1)] : null const lessThanParser = (data) => data.startsWith('<') ? [lessThan, data.slice(1)] : null const greaterThanEqualToParser = (data) => data.startsWith('>=') ? [greaterThanEqualTo, data.slice(2)] : null const lessThanEqualToParser = (data) => data.startsWith('<=') ? [lessThanEqualTo, data.slice(2)] : null const equalToParser = (data) => data.startsWith('==') ? [EqualTo, data.slice(2)] : null const maxParser = (data) => data.startsWith('max') ? [maxNumber, data.slice(3)] : null const minParser = (data) => data.startsWith('min') ? [minNumber, data.slice(3)] : null const notParser = (data) => data.startsWith('not') ? [notNumber, data.slice(3)] : null const listParser = (data) => data.startsWith('list') ? [listCall, data.slice(4)] : null const carList = (data) => data.startsWith('car') ? [listCar, data.slice(3)] : null const cdrList = (data) => data.startsWith('cdr') ? [listCdr, data.slice(3)] : null const consList = (data) => data.startsWith('cons') ? [listCons, data.slice(4)] : null const isListIden = (data) => data.startsWith('isList') ? [isListLisp, data.slice(6)] : null const defineSlicerParser = (data) => data.startsWith('define') ? [defineLisp, data.slice(6)] : null const ifSlicerParser = (data) => data.startsWith('if') ? [ifLisp, data.slice(2)] : null const printSlicerParser = (data) => data.startsWith('print') ? [printLisp, data.slice(5)] : null const lambdaSlicerParser = (data) => data.startsWith('lambda') ? ['lambda', data.slice(6)] : null const openBracket = (input) => (input.startsWith('(')) ? ['(', input.slice(1)] : null const closeBracket = (input) => (input.startsWith(')')) ? [')', input.slice(1)] : null const parserFactory = (...parsers) => (input) => { for (let parser of parsers) { let output = parser(input) if (output !== null) return output } return null } const allParser = (...parsers) => (input) => { let result = [] for (let parser of parsers) { let output = parser(input) if (output === null) return null result.push(output[0]) input = output[1] } return [result, input] } const operatorFinder = (input) => parserFactory(plusParser, minusParser, mulParser, divParser, greaterThanEqualToParser, lessThanEqualToParser, equalToParser, greaterThanParser, lessThanParser, maxParser, minParser, notParser, listParser, carList, cdrList, consList, isListIden)(input) const operatorParser = (input) => { let count = 1 if (!input.startsWith('(')) return null input = input.slice(1) if (input.startsWith('>') || input.startsWith('>=') || input.startsWith('<') || input.startsWith('<=') || input.startsWith('==') || input.startsWith('max') || input.startsWith('min')) { count++ } let output = operatorFinder(input) if (output === null) return null // For Operator Operand1 Operand2 let result = [], vid = '', args = 'args' result.push(output[0]) while (output[0] !== ')') { output = spaceParser(output[1]) output = expressionParser(output[1]) if (ENV[output[0]]) { (ENV[output[0]].args) ? result.push(ENV[output[0]].args) : result.push(ENV[output[0]]) } else { result.push(output[0]) } output = (vid = closeBracket(output[1])) ? vid : output } if (output[0] === ')') { if (output[1] === '') { return [evaluate(result, count)] } else { return [evaluate(result, count), output[1]] } } } const evaluate = (input, count) => { let operation = input.shift() if (count > 1) return operation(...input) else return operation(input) } const expressionParser = (input) => parserFactory(numberParser, stringParser, lambdaParser, identifierParser, operatorParser)(input) const lambdaArgumentsParser = (input) => { let result = [], output input = openBracket(input) input = input[1] while (!input.startsWith(')')) { input = identifierParser(input) result.push(input[0]) input = (output = spaceParser(input[1])) ? output[1] : input[1] } input = closeBracket(input) return [result, input[1]] } const lambdaBodyParser = (input) => { let count = 0, k = 0, output = '' do { if (input[k] === '(') count++ if (input[k] === ')') count-- output += input[k] k++ } while (count !== 0) input = input.slice(k) return [output, input] } const defineLambda = (input) => { let obj = {}, count = 3 let output = allParser(openBracket, lambdaSlicerParser, spaceParser, lambdaArgumentsParser, spaceParser, lambdaBodyParser, closeBracket)(input) if (output === null) return null let [[, Type, , Args, , Body], rest] = output obj.type = Type, obj.args = Args, obj.body = Body return [obj, rest, count] } const checker = (output) => { if ((output[0] === 'list') || (output[0] === 'max') || (output[0] === 'min') || (output[0] === 'car') || (output[0] === 'cdr') || (output[0] === 'cons') || (output[0] === 'isList')) { return null } } const lambdaParser = (input) => { if (!input.startsWith('(')) return null input = input.slice(1) let output = identifierParser(input) let type = 'type' if ((output === null) || (checker(output) === null) || (ENV[output[0]].type === undefined)) return null let key = output[0], arr = [] while (!output[1].startsWith(')')) { output = spaceParser(output[1]) if (numberParser(output[1])) { output = numberParser(output[1]) arr.push(output[0]) } if (identifierParser(output[1])) { output = identifierParser(output[1]) if (ENV[output[0]] !== undefined) { output[0] = ENV[output[0]] arr.push(output[0]) } } if (output[1].startsWith('(')) { output = lambdaParser(output[1]) arr.push(output[0][0]) } } let value = output[0], args = 'args', body = 'body', env = {} for (let i = 0; i < arr.length; i++) { env[ENV[key].args[i]] = arr[i] } env[body] = ENV[key].body for (let i = 0; i < arr.length; i++) { env[body] = env[body].replace(ENV[key].args[i], env[ENV[key].args[i]]) } env[body] = env[body].replace(ENV[key].args[0], value) env[body] = env[body].replace(ENV[key].args[0], value) output = (vid = closeBracket(output[1])) ? vid : output if (output[0] === ')') { return [operatorParser(env[body]), output[1]] } } const defineParser = (input) => { let arr = [], count = 1 let output = allParser(openBracket, defineSlicerParser, spaceParser, identifierParser, spaceParser)(input) if (output === null) return null let [[ , defineFunc, , iden], rest] = output input = rest output = defineLambda(input) if (output === null) output = expressionParser(input) let [val1, val2] = output arr.push(defineFunc, iden, val1) count += 3 evaluate(arr, count) input = closeBracket(val2) return input[1] } const printParser = (input) => { let arr = [], count = 1 let output = allParser(openBracket, printSlicerParser, spaceParser, expressionParser, closeBracket)(input) if (output === null) return null let [[, printFunc, , exp], rest] = output arr.push(printFunc) ENV[exp] ? arr.push(ENV[exp]) : arr.push(exp) console.log('Evaluate to ' + evaluate(arr, count)) if (rest === null) { return null } return rest } const ifParser = (input) => { let arr = [], count = 0 let output = allParser(openBracket, ifSlicerParser, spaceParser, expressionParser, spaceParser, expressionParser, spaceParser, expressionParser, closeBracket)(input) if (output === null) return null let [[, ifFun, , test, , conseq, , alt], rest] = output arr.push(ifFun, test, conseq, alt) console.log('Evaluate to ' + evaluate(arr, count + 3)) return rest } const statementParser = (input) => parserFactory(defineParser, printParser, ifParser)(input) const programParser = (input) => { while (input !== '' && input !== null) { let spaceParsed = '' input = (spaceParsed = spaceParser(input)) ? spaceParsed[1] : input input = statementParser(input) } return ENV } console.log((output = programParser(input)) ? output : 'Error') 

Answer 1

Expectations

Lisp is well-known for it's REPL, so I'd expect to see at least the following 3 functions in any Lisp interpreter: read, evaluate and print.

• read takes a string and returns a form (a number, string, symbol, list, and so on). For example: read("(+ 4 5)") should return a list that contains the symbol + and the numbers 4 and 5.
• evaluate takes a form and evaluates it. Some forms, such as numbers and strings, simply evaluate to themselves. Symbols evaluate to whatever they're bound to. Lists are evaluated as function calls, unless their first item is a special operator - in that case it's a special form, which has its own evaluation rules.
• print takes a form and returns a textual representation of it.

Main problems

Your code contains a lot of parsing functions. It's almost as if everything is a parser. There are a few standard functions hidden in-between (add, sub, and so on), and there's an evaluate function as well, but that appears to handle function application, not general evaluation of forms.

• Organize your code into separate parts. Those comment headers are helpful, but not enough. You may also want to hide most of those functions, as they're internal and shouldn't be part of the public interface of your Lisp interpreter. Currently there are no clear 'entry points' in your code.
• Make a clear separation between parsing and evaluation code. Several parse functions appear to do both parsing and evaluation, which is inflexible and makes them harder to reuse. Classes and functions should have a single responsibility.
• You've got lots of special-case parsing functions. Every operator and standard function has a matching parser function. Why? In Lisp, + and - are just symbols that are bound to standard 'add' and 'subtract' functions. The same goes for special forms: for the parser, they're just symbols. You only need a single symbol-parsing function.
• You've got a parserFactory function that calls several parser functions in a row, until one of them returns a non-null result. I think this has the following problems:
  • It's more difficult to determine control flow.
  • It causes more work to be done than necessary, because each parse function needs to do some work before it finds out whether the input is valid or not.
  • It requires more code, because each parse function needs additional checks.
  • It's also more error-prone, because a failure in any parse function can cause problems. For example, (print (if (== 1 1) 4 5)) fails due to a check in lambdaParser - even though there's no lambda in that input at all.
• An interpreter is usually stateful - it needs to store things in memory. You're using a global ENV variable for that. That means that you can have only one interpreter at the same time. If your interpreter is a 'class', other code could instantiate it and have as many or as few independent interpreters as needed.
• It looks like your code doesn't actually work very well. For example, it chokes on the sample code by ending up in an infinite loop.

These points alone should be sufficient for a major overhaul. Addressing them will likely also reduce the amount of code. That may well be the reason why you were told to do this in less code: to force you to come up with a better approach. Having less code is beneficial, but shouldn't be a goal all by itself.

Other issues

• Most function names here are nouns. Verbs would be more appropriate. parseExpression(input) looks more natural than expressionParser(input).
• Use clear and descriptive names. spaceParser doesn't parse spaces, it skips spaces, so skipSpaces would be a better name. Your evaluate function performs function application, so it's better named as apply or applyFunction.
• Javascript isn't statically typed, which can make it easier to work with, but it also makes code less self-documenting. You may want to document that those parse functions return a [value, rest-of-input] array.
• Returning the rest of the input as a string requires a lot of strings to be created. This may cause performance issues for large inputs.
• You're working on a Lisp interpreter, so use Lisp terminology (and use it correctly): symbols, forms, special forms, function application, evaluation, and so on. Using different terms or using them with a different meaning makes your code much harder to understand.
• Putting if/else bodies on the same line makes code less readable. It may reduce the number of code lines, but it doesn't reduce the overall amount of code.

There is probably more that can be said about this, but I'll stop here.

EDIT: Inspired by Konijn, I've written down how I would approach this.

Recommendations

Here's what I would do:

First, come up with a way to store your Lisp programs in memory. The easiest way is probably to just use Javascript booleans, numbers, strings and lists, and a few classes for symbols and functions defined in Lisp. Once you've got that worked out, you know what read should return, and what evaluate and print should work with.

---

To implement read, a few helper functions for parsing lists, symbols, strings and numbers (and perhaps other things) will be useful. These functions should be easy to test in isolation:

• parseString('"hello world"') should return the (Javascript) string 'hello world'
• parseNumber('14.5') should return the (Javascript) number 14.5
• parseSymbol('is-empty?') should return the result of new LispSymbol('is-empty?')
• parseList('(+ 4 (* 2 5))') should return the equivalent of [new LispSymbol('+'), 4, [new LispSymbol('*'), 2, 5]].
• A general parseForm function that inspects its input and calls one of the above functions should also be useful. Not only as an entry point, but parseList can also use it to parse its elements (which makes it recursive, and capable of parsing nested lists and lists with arbitrary content).

Don't forget to come up with a good error-handling strategy.

---

Implementing print should be fairly straight-forward. Just check the type of the given Lisp form, and return a string representation of it:

• print(4) ->4
• print('hello') ->"hello"
• print([4, [5, 6]]) ->'(4 (5 6))
• print(new LispSymbol('my-variable')) ->'my-variable
• print(new LispFunction('add', ...)) ->#<function:add>

and so on.

---

evaluate is where the real work happens. As with print, it needs to check the type of the given Lisp form, and handle each type accordingly:

• Primitives like booleans, numbers, strings and functions evaluate to themselves, so they can be returned directly.
• Symbols evaluate to the result of a lookup in the current execution context.
• Lists are either function applications or special forms:
  • If the first element is a special syntax symbol (a keyword, if you will) then special rules apply (depending on the keyword). You typically end up with a separate evaluation function for each special form - usually a dozen or two, depending on how complete you want your Lisp to be.
  • For function applications, the first element of the list must evaluate to a function, and the rest of the elements are then evaluated and used as arguments for the function call. You'll probably have to handle standard functions (such as +, -, and so on) and Lisp functions (the result of a define) separately, because the former are Javascript functions under the hood, and the latter are LispFunction objects whose function bodies must be evaluated. You could wrap those standard functions in NativeFunction objects and give both the same interface to simplify things.
  • Or they're macro calls. Macros are functions that return code, and they're usually expanded after reading and before evaluation. What requires a compiler extension in other languages can often be done with macros in Lisp.

---

I've probably overlooked a few things, and there are of course many more details to figure out, depending on how simple or complex you want your interpreter to be. Feel free to ask for another code review once you've improved your code.