Skip to content

Instantly share code, notes, and snippets.

@nathanhleung
Last active May 14, 2022 13:23
Show Gist options
  • Save nathanhleung/9ee3e22e34f5b0075180 to your computer and use it in GitHub Desktop.
Save nathanhleung/9ee3e22e34f5b0075180 to your computer and use it in GitHub Desktop.
The Egg programming language (from Eloquent Javascript, Ch. 11)
// So that we can import this into CodePen!
"use strict";
function Egg() {
/**
* Removes whitespace from the beginning of the provided program
* @param program - The program to truncate whitespace from
*/
function truncateWhitespace(program) {
// Finds the first non-whitespace character
let firstChar = program.search(/\S/);
// If there is whitespace at the beginning, remove it
if (firstChar === -1) {
program = "";
} else {
program = program.slice(firstChar);
}
return program;
}
/**
* Parses an expression, which can be a string, number, or operator
* @param program - The program whose expressions are being parsed.
*/
function parseExpression(program) {
program = truncateWhitespace(program);
let expr, val, match;
// Match all characters between double quotes (that aren't double quotes)
match = /^"([^"]*)"/.exec(program);
if (match) {
// Get inner group (in parentheses), so match[1]
val = match[1];
expr = {
type: "string",
value: val
};
// Slice off quotes too, so match[0] (outer group)
return parseOperator(expr, program.slice(match[0].length));
}
match = /^\d+\b/.exec(program);
if (match) {
val = match[0];
expr = {
type: "number",
value: val
}
return parseOperator(expr, program.slice(match[0].length));
}
// If it's not a space/whitespace, parenthesis, comma, or double quote, it's an operator.
// We can't parse a word then a space then another word
match = /^[^\s(),"]+/.exec(program);
if (match) {
val = match[0];
expr = {
type: "word",
value: val
}
return parseOperator(expr, program.slice(match[0].length));
}
throw new SyntaxError("Unexpected syntax: " + program);
}
/**
* Parses any operators (i.e. function calls)
* @param expr - The expression (string, number, operator) that was parsed
* @param program - The program to parse
*/
function parseOperator(expr, program) {
program = truncateWhitespace(program);
// If the parsed expression wasn't a function call, then return the parsed program
if (program[0] !== "(") {
return {
expr: expr,
rest: program
};
}
// If the parsed expression was a function call
program = truncateWhitespace(program.slice(1));
expr = {
type: "apply",
operator: expr,
args: []
};
// Until we reach the end of the arguments
while (program[0] !== ")") {
// Parse the next characters of the program (the argument)
let arg = parseExpression(program);
expr.args.push(arg.expr);
// From above, if the expression is not a function call parseOperator returns a "rest" property with the rest of the program
program = truncateWhitespace(arg.rest);
// This means there is another argument
if (program[0] === ",") {
program = truncateWhitespace(program.slice(1));
} else if (program[0] !== ")") {
throw new SyntaxError("Expected ',' or ')'");
}
}
// If there is a clothing parenthesis, then move on.
return parseOperator(expr, program.slice(1));
}
/**
* Wrapper for parsing
* @param program - The program to parse
*/
function parse(program) {
let result = parseExpression(program);
if (truncateWhitespace(result.rest).length > 0) {
throw new SyntaxError("Unexpected text after program");
}
return result.expr;
}
/**
* Print parsed program
* @param program - The program to print
*/
function printProgram(program) {
console.log(JSON.stringify(parse(program), null, 2));
}
/**
* Evaluate
*/
function evaluate(expr, env) {
switch(expr.type) {
case "string":
return expr.value;
case "number":
// Make sure "number" gets turned into a Number!
return Number(expr.value);
case "word":
// Get the function/variable from the current context ("word")
if (expr.value in env) {
return env[expr.value];
} else {
throw new ReferenceError("Undefined variable: " + expr.value);
}
case "apply":
if (expr.operator.type == "word" && expr.operator.value in specialForms) {
return specialForms[expr.operator.value](expr.args, env);
}
// If the operator isn't in special forms then evaluate the operator ("word") itself
let operator = evaluate(expr.operator, env);
if (typeof operator !== "function") {
throw new TypeError("Applying a non-function");
}
return operator.apply(null, expr.args.map((arg) => {
return evaluate(arg, env);
}));
}
}
let specialForms = Object.create(null);
specialForms["if"] = (args, env) => {
if (args.length !== 3) {
throw new SyntaxError("Bad number of args to if");
}
if (evaluate(args[0], env) !== false) {
return evaluate(args[1], env);
} else {
return evaluate(args[2], env);
}
};
specialForms["while"] = (args, env) => {
if (args.length !== 2) {
throw new SyntaxError("Bad number of args to while");
}
while (evaluate(args[0], env) !== false) {
evaluate(args[1], env);
}
return false;
};
specialForms["do"] = (args, env) => {
let value = false;
args.forEach((arg) => {
value = evaluate(arg, env);
});
// Returns value produced by last arg
return value;
};
specialForms["define"] = (args, env) => {
if (args.length !== 2 || args[0].type !== "word") {
throw new SyntaxError("Bad use of define");
}
let value = evaluate(args[1], env);
env[args[0].value] = value;
return value;
};
specialForms["func"] = (args, env) => {
if (!args.length) {
throw new SyntaxError("Functions need a body");
}
// Get all args except for last, which is function body
let argNames = args.slice(0, args.length - 1).map((expr) => {
if (expr.type !== "word") {
throw new SyntaxError("Arg names must be a word")
}
return expr.value;
});
let body = args[args.length - 1];
return function() {
if (arguments.length !== argNames.length) {
throw new TypeError("Wrong number of arguments");
}
let localEnv = Object.create(env);
for (let i = 0; i < arguments.length; i++) {
localEnv[argNames[i]] = arguments[i];
}
return evaluate(body, localEnv);
};
}
specialForms["array"] = (args, env) => {
let arr = [];
args.forEach((arg) => {
arr.push(arg.value);
});
return arr;
}
let baseEnv = Object.create(null);
baseEnv["true"] = true;
baseEnv["false"] = false;
["+", "-", "/", "*", "%", "==", "!=", ">", "<", ">=", "<="].forEach((operator) => {
baseEnv[operator] = new Function("a", "b", "return a " + operator + " b;");
});
baseEnv["print"] = (value) => {
console.log(value);
return value;
};
baseEnv["length"] = (arg) => {
return arg.length;
};
baseEnv["elementAt"] = (arg, i) => {
return arg[i];
}
function interpret(program) {
let env = Object.create(baseEnv);
return evaluate(parse(program), env);
}
Object.defineProperty(this, "interpret", {
value: interpret
});
}
// Create a new Egg instance via new Egg();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment