This post is a continuation of LISPy-JSON Part 1, Part 2, Part-3, Part-4 and Part-5 you should read these prior to reading the current post.
To implement functions, the first thing we would need is to design a syntax for our function declaration. Functions usually have three things, a function name, a list of arguments and the function body. The keyword ‘fn’ is used to denote that any declaration within is a function.
Let us go ahead and define a function that returns the max of two numeric inputs, the function arguments and the body for max can be described in a JSON like format as shown below,
let program = [
{
fn: {
'max': [['a', 'b'], [
{
if: { '>': [{ val: 'a' }, { val: 'b' }] },
then: [{ val: 'a' }],
else: [{ val: 'b' }]
}
]]
}
},
{
print: { max: [3, 5] }
}
]
Side note: If you remember our if-else statements can do a return so you do not need a return keyword.
Calling a custom function is the same as calling any other function like print, def or val.
Functions have their own local scope which is isolated from the global or parent scope, so instead of starting the interpreter with an {} empty state we define a map with two keys:
vars: to hold values and reference to custom functions.
parent: reference to parent state.
We then modify the def and val function, so that we can use the vars key instead of writing directly to the state object.
The exec function is then modified to support function definition using fn keyword by calling the fnStatement function, and we further modify it to try and call a custom function using fnExec if we don’t find it in any of the in built functions or operators,
The functions fnStatement is implemented as follows:
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 }
}
We first exctract the function name and the function body. The name and body are then assigned to the state.vars map using the function name as the key.
We then define the fnExec function,
let fnExec = (stmt, key, state) => {
let fnName = key;
let fnArgs = stmt[fnName];
let fn = state.vars[fnName];
let newState = { vars: {}, parent: state };
for (let [index, argName] of fn.args.entries()) {
newState.vars[argName] = fnArgs[index];
}
return interpret(fn.body, newState);
}
The fnExec basically takes the given function name and uses it as the key to fetch the function name and body that were defined in the FnStatement function.
Thne, we create a newState map variable which has a vars map which is empty and parent pointing to the state which the fnExec currently has as the argument.
newState.vars are then loaded with the variable names and their values by looping through the argument list. Then we call the interpret function passing in the function body and the newState which now holds all arguments as variables.
The entire program is given below,
let program = [
{
fn: {
'max': [['a', 'b'], [
{
if: { '>': [{ val: 'a' }, { val: 'b' }] },
then: [{ val: 'a' }],
else: [{ val: 'b' }]
}
]]
}
},
{
print: { max: [3, 5] }
}
]
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 },
}
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 fnExec = (stmt, key, state) => {
let fnName = key;
let fnArgs = stmt[fnName];
let fn = state.vars[fnName];
let newState = { vars: {}, parent: state };
for (let [index, argName] of fn.args.entries()) {
newState.vars[argName] = fnArgs[index];
}
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 })
$ node interpret.js
5The diff against the previous version can be seen here: https://github.com/avierr/LISPy-JSON-interpreter/commit/86e72a85a404a4d82231459895568710633f3701
In the next post, we will add support for recursive functions in our interpreter.
Tags: interpreter javascript