Return Zero

This post is a continuation of LISPy-JSON Part 1, Part 2, Part-3, Part-4, Part-5 and Part-6, you should read these prior to reading the current post.

We already have the capability of defining and calling functions, but we do not have the ability to resolve functions and variables defined in the parent or grand parent scope. We will limit ourselves here to resolving functions so as to keep the state as immutable as possible, but if you prefer this can be easily modifed to resolve variables in the upper scope with minor changes.

Let us first define an input program with function that might need recursion. Fibonacci is a common recursive algorithm and hence we will define that in out LISPy-JSON syntax.

let program = [
  {
    fn: {
      'fibonacci': [['n'], [
        { 
          if: { '<=': [{ val: 'n' }, 1] },
          then: [{ val: 'n' }],
          else: [{
            '+': [
              { 'fibonacci': [{ '-': [{ val: 'n' }, 1] }] },
              { 'fibonacci': [{ '-': [{ val: 'n' }, 2] }] },
            ]
          }]
        }
      ]]
    }
  },
  {
    print: { fibonacci: [6] }
  }
]

We add two new operators, one of which is used in our fibonacci function,

We then modify the fnExec function,

we use a new resolveVarName function to resolve the function name instead of just trying to read it from the state.vars map. We also attach the function to its own local state so that we don’t have to resolve many levels up during a recursive call. We also ensure the arguments are evaluated so that we can also pass in complex expression rather than just plain values.

resolveVarName is defined below,

let resolveVarName = (varName, currentState) => {
  if (typeof currentState.vars[varName] !== 'undefined') {
    return currentState.vars[varName];
  } else {
    if (currentState.parent != null) {
      return resolveVarName(varName, currentState.parent);
    } else {
      throw new Error(`could not find: ${varName}`);
    }
  }

}

We basically try and see if the function is defined in the current state, if not we try the parent level and so on till we reach the top most level which has the parent as null.

The entire interpreter code is given below,

let program = [
  {
    fn: {
      'fibonacci': [['n'], [
        { 
          if: { '<=': [{ val: 'n' }, 1] },
          then: [{ val: 'n' }],
          else: [{
            '+': [
              { 'fibonacci': [{ '-': [{ val: 'n' }, 1] }] },
              { 'fibonacci': [{ '-': [{ val: 'n' }, 2] }] },
            ]
          }]
        }
      ]]
    }
  },
  {
    print: { fibonacci: [6] }
  }
]

let builtins = {
  print: (text) => { console.log(text) }
}

let binaryOperators = {
  '+': (a, b) => { return a + b },
  '-': (a, b) => { return a - b },
  '*': (a, b) => { return a * b },
  '>': (a, b) => { return a > b },
  '>=': (a, b) => { return a >= b },
  '<=': (a, b) => { return a <= b },
  '<': (a, b) => { return a < b },
  '==': (a, b) => { return a == b },
  '||': (a, b) => { return a || b },
  '&&': (a, b) => { return a && b },
}

interpret = (program, state) => {
  let returnValue;
  for (let stmt of program) {
    returnValue = exec(stmt, state)
  }
  return returnValue;
};

varDefinition = (defObj, state) => {
  let variable = Object.keys(defObj)[0];
  state.vars[variable] = exec(defObj[variable], state)
}

varValue = (varKey, state) => { return state.vars[varKey] }

let ifStatement = (stmt, key, state) => {
  let condition = stmt[key]
  if (exec(condition, state)) {
    let thenStatements = stmt['then']
    return interpret(thenStatements, state)
  } else {
    let elseStatements = stmt['else'];
    if (typeof elseStatements !== 'undefined') {
      return interpret(elseStatements, state)
    }
  }
}

let fnStatement = (stmt, key, state) => {
  let fnDefinition = stmt[key];
  let fnName = Object.keys(fnDefinition)[0];
  let fnArgs = fnDefinition[fnName][0];
  let fnBody = fnDefinition[fnName][1];
  state.vars[fnName] = { args: fnArgs, body: fnBody }
}

let resolveVarName = (varName, currentState) => {
  if (typeof currentState.vars[varName] !== 'undefined') {
    return currentState.vars[varName];
  } else {
    if (currentState.parent != null) {
      return resolveVarName(varName, currentState.parent);
    } else {
      throw new Error(`could not find: ${varName}`);
    }
  }

}

let fnExec = (stmt, key, state) => {
  let fnName = key;
  let fnArgs = stmt[fnName];
  let fn = resolveVarName(fnName, state); //find in current or parent states
  let newState = { vars: {}, parent: state };
  newState.vars[fnName] = fn; //attach current function defn to its own local state
  for (let [index, argName] of fn.args.entries()) {
    newState.vars[argName] = exec(fnArgs[index],state);
  }
  return interpret(fn.body, newState);
}

exec = (stmt, state) => {

  if (typeof stmt === 'number' || typeof stmt === 'string') {
    return stmt;
  }

  let key = Object.keys(stmt)[0]
  if (typeof builtins[key] === 'function') {
    builtins[key](exec(stmt[key], state), state)
  } else if (typeof binaryOperators[key] === 'function') {
    let firstArgument = stmt[key][0];
    let secondArgument = stmt[key][1];
    return binaryOperators[key](exec(firstArgument, state), exec(secondArgument, state))
  } else if (key === 'def') {
    let firstArgument = stmt[key]
    return varDefinition(firstArgument, state)
  } else if (key === 'val') {
    let firstArgument = stmt[key]
    return varValue(firstArgument, state)
  } else if (key === 'if') {
    return ifStatement(stmt, key, state)
  } else if (key === 'fn') {
    return fnStatement(stmt, key, state)
  } else {
    if (typeof state.vars[key] !== 'undefined') {
      return fnExec(stmt, key, state)
    }
    console.error('unknown instruction: ' + key)
  }

}

interpret(program, { vars: {}, parent: null })

$ interpret.js     
8

The diff against the previous version is here: https://github.com/avierr/LISPy-JSON-interpreter/commit/abea98bc03a6c3b319cfeaa70aecd0e724463efd

You might have noticed this, If we remove all the braces and quotes and some symbols from the input program, it almost resembles a modern programming language,

fn fibonacci n
  if  <= n 1
    then
      n
    else
      + fibonacci - n 1,
        fibonacci - n 2

What we essentially do is convert the above program to our JSON like structure or an AST(Abstract syntax tree) and use our interpreter to evaluate the AST.

If you remove the input JSON, the program is around 110 lines which is extremely tiny for a Turing complete interpreter and I hope this would have made it easy to grasp and learn the underlying concepts.

Side note: With a few minor adjustments you should be able to pass functions as arguments too. Implementing a for or while loop should be easy as well if you don’t like to use recursion everywhere.

Closing Thoughts

After a series of 7 long posts, we have at last implemented the final parts required to complete our interpreter. We have thus far implemented function definition, function calling, variables and state, and if-else branching. Now, we have a simple but a working programming language.