Lisp implemented in JavaScript

lisp.js

/*

This is an implementation of a Lisp in JavaScript. It does not provide
a full suite of the built-in functions one might expect, but it
does represent a solid basis for a more complete implementation.

I prototyped this interpreter because I want to expose a scripting
language to users of a project I'm working on and Lisp seemed like a
good choice.

To try out this example, open a web console and write, for example:

// Print "hello world" to the console
lisp.evaluate(`(print "hello world")`);

// Define a function for listing the elements of a Collatz sequence
lisp.evaluate(`
    (define collatz (function [:n]
        (extend [n] (while (!= 1 n)
            (define n (if (modulo n 2)
                (+ 1 (* 3 n))
                (/ n 2)
            ))
        ))
    ))
`);

// Display the Collatz sequence of the number 5
lisp.evaluate(`(print (collatz 5))`);

An expression is anything contained within balanced parentheses ().
An expression contains zero or more elements.
Expressions may themselves contain expressions as elements.
The elements within an expression are separated by whitespace and/or commas.
The null expression "()" evaluates the same as the null literal "null".
The first element of a not-empty expression shall always be a function.
All expressions other than the null expression evaluate to the result of invoking
the first element as a function, using the remaining elements as parameters.

Expressions contained within balanced brackets [] define lists.
This is a shortcut such that "[...]" means the same thing as "(list ...)".

Whenever a source string is passed to lispContext.evaluate() it is wrapped
inside an expression like (do <expressions>).

*/

function SyntaxError(line, message){
    if(line){
        const error = new Error(`Syntax error on line ${line}: ${message}`);
        error.line = line;
        return error;
    }else{
        return new Error(`Syntax error: ${message}`);
    }
}

function isWhiteSpace(char){
    return char === " " || char === "\t" || char === ",";
}

function isDigit(char){
    return (
        char === "0" || char === "1" ||
        char === "2" || char === "3" ||
        char === "4" || char === "5" ||
        char === "6" || char === "7" ||
        char === "8" || char === "9"
    );
}

function parseSymbol(symbol, lineNumber){
    // TODO: Better handling of malformed literals
    if(symbol === "null"){
        return {
            type: "null",
            value: null,
        };
    }else if(symbol === "true"){
        return {
            type: "boolean",
            value: true,
        };
    }else if(symbol === "false"){
        return {
            type: "boolean",
            value: false,
        };
    }else if(
        isDigit(symbol[0]) || symbol[0] === "+" || symbol[0] === "-"
    ){
        if(symbol === "+" || symbol === "-"){
            return {
                type: "identifier",
                value: symbol,
            };
        }else{
            return {
                type: "number",
                value: parseFloat(symbol),
            };
        }
    }else if(symbol[0] === "."){
        return {
            type: "number",
            value: parseFloat(symbol),
        };
    }else if(symbol.startsWith("0x")){
        return {
            type: "integer",
            value: parseInt(symbol.slice(2), 16),
        };
    }else if(symbol[0] === "\""){
        return {
            type: "string",
            value: symbol.slice(1, -1),
        };
    }else if(symbol[0] === "'"){
        return {
            type: "character",
            value: symbol.slice(1, -1),
        };
    }else if(symbol[0] === ":"){
        return {
            type: "keyword",
            value: symbol.slice(1),
        };
    }else{
        return {
            type: "identifier",
            value: symbol,
        };
    }
}

function wrapValue(value){
    let type = undefined;
    if(value instanceof Function){
        type = "function";
    }else if(typeof(value) === "number"){
        type = "number";
    }else if(value === true || value === false){
        type = "boolean";
    }else if(value === null || value === undefined){
        type = "null";
        value = null;
    }else if(typeof(value) === "string"){
        type = "string";
    }else if(value instanceof Array){
        type = "list";
        value = value.map(i => wrapValue(i));
    }else{
        type = "map";
        const newValue = {};
        for(const key in value){
            newValue[key] = wrapValue(value[key]);
        }
        value = newValue;
    }
    return {
        type: type,
        value: value,
    };
}

function parseSyntaxTree(source){
    let lineNumber = 1;
    let currentNode = [];
    let nodeStack = [currentNode];
    let currentSymbolBegin = 0;
    let currentSymbolLineNumber = 1;
    let escapeSequence = false;
    let inDoubleQuote = false;
    let endOfLineComment = false;
    let blockComment = false;
    function terminateSymbol(i){
        if(currentSymbolBegin !== i){
            const symbol = source.slice(currentSymbolBegin, i);
            currentNode.push(parseSymbol(symbol, currentSymbolLineNumber));
        }
    }
    for(let i = 0; i < source.length; i++){
        const char = source[i];
        if(inDoubleQuote){
            if(char === "\"" && !escapeSequence){
                inDoubleQuote = false;
            }else if(char === "\\"){
                escapeSequence = !escapeSequence;
            }else{
                escapeSequence = false;
                if(char === "\n"){
                    lineNumber++;
                }
            }
        }else if(endOfLineComment){
            if(char === "\n"){
                lineNumber++;
                currentSymbolBegin = i + 1;
                endOfLineComment = false;
            }
        }else if(blockComment){
            if(char === "\n"){
                lineNumber++;
            }else if(char === "/" && source[i - 1] === "*"){
                currentSymbolBegin = i + 1;
                blockComment = false;
            }
        }else if(char === "\n"){
            terminateSymbol(i);
            currentSymbolBegin = i + 1;
            lineNumber++;
        }else if(char === "\""){
            inDoubleQuote = true;
        }else if(char === "/" && source[i + 1] === "/"){
            terminateSymbol(i);
            endOfLineComment = true;
        }else if(char === "/" && source[i + 1] === "*"){
            terminateSymbol(i);
            blockComment = true;
        }else if(char === "(" || char === "["){
            // TODO: Better validation of mixed open/close parens
            currentNode = char === "[" ? [{type: "identifier", value: "list"}] : [];
            currentNode.lineNumber = lineNumber;
            nodeStack[nodeStack.length - 1].push(currentNode);
            nodeStack.push(currentNode);
            currentSymbolBegin = i + 1;
        }else if(char === ")" || char === "]"){
            terminateSymbol(i);
            currentSymbolBegin = i + 1;
            nodeStack.pop();
            currentNode = nodeStack[nodeStack.length - 1];
            if(!currentNode){
                throw SyntaxError(lineNumber, "Unbalanced parens.");
            }
        }else if(isWhiteSpace(char)){
            terminateSymbol(i);
            currentSymbolBegin = i + 1;
            currentSymbolLineNumber = lineNumber;
        }
    }
    if(nodeStack.length !== 1){
        throw SyntaxError(currentNode.lineNumber, "Unterminated expression.");
    }
    if(nodeStack[0].length === 1){
        return nodeStack[0][0];
    }else{
        nodeStack[0].unshift({type: "identifier", value: "do"});
        return nodeStack[0];
    }
}

class lispContext{
    constructor(register, scope, parent){
        this.parent = parent;
        this.scope = scope || {};
        if(register){
            for(const name in register){
                this.register(name, register[name]);
            }
        }
    }
    register(name, value){
        this.define(name, wrapValue(value));
    }
    define(name, value){
        this.scope[name] = value;
    }
    compile(source){
        return parseSyntaxTree(source);
    }
    identify(identifier){
        let context = this;
        while(context){
            if(identifier in context.scope){
                return context.scope[identifier];
            }
            context = context.parent;
        }
        return undefined;
    }
    evaluate(expression){
        if(typeof(expression) === "string"){
            expression = this.compile(expression);
        }
        if(!expression){
            throw new Error("Undefined expression.");
        }else if(expression.type === "identifier"){
            const identity = this.identify(expression.value);
            if(identity === undefined){
                console.log(`Undeclared identifier "${expression.value}".`);
                return {
                    type: "null",
                    value: null,
                };
            }
            return identity;
        }else if(expression.type !== undefined){ //"expression"){
            return expression;
        }else if(expression.length === 0){
            return {
                type: "null",
                value: null,
            };
        }else{
            let func;
            if(expression[0].type === "identifier"){
                func = this.identify(expression[0].value);
                if(func === undefined && expression.length > 1){
                    func = this.identify(
                        this.evaluate(expression[1]).type + ":" + expression[0].value
                    );
                }
                if(func === undefined){
                    console.log(`Undeclared identifier "${expression[0].value}".`);
                    return {
                        type: "null",
                        value: null,
                    };
                }
            }else{
                func = this.evaluate(expression[0]);
            }
            if(func.type !== "function"){
                console.log("Malformed expression.");
                return {
                    type: "null",
                    value: null,
                };
            }else{
                return func.value(this, ...expression);
            }
        }
    }
}

function begin(){
    window.lisp = new lispContext({
        "do": function(context, func, ...args){
            let result = {
                type: null,
                value: "null",
            };
            for(const expression of args){
                result = context.evaluate(expression);
            }
            return result;
        },
        "when": function(context, func, condition, ...expressions){
            let result = {
                type: null,
                value: "null",
            };
            if(context.evaluate(condition)){
                for(const expression of expressions){
                    result = context.evaluate(expression);
                }
            }
            return result;
        },
        "if": function(context, func, condition, trueBody, falseBody){
            if(context.evaluate(condition).value){
                return context.evaluate(trueBody);
            }else{
                return context.evaluate(falseBody);
            }
        },
        "while": function(context, func, condition, whileBody){
            const list = [];
            while(context.evaluate(condition).value){
                list.push(context.evaluate(whileBody));
            }
            return {
                type: "list",
                value: list,
            };
        },
        "list": function(context, func, ...elements){
            return {
                type: "list",
                value: elements.map(i => context.evaluate(i)),
            };
        },
        "list:length": function(context, func, listExp){
            return context.evaluate(listExp).value.length;
        },
        "list:push": function(context, func, listExp, ...elements){
            const list = context.evaluate(listExp);
            for(const element of elements){
                list.value.push(context.evaluate(element));
            }
            return list;
        },
        "list:pop": function(context, func, listExp){
            const list = context.evaluate(listExp);
            return list.value.pop();
        },
        "list:extend": function(context, func, listExp, extendExp){
            const list = context.evaluate(listExp);
            const extend = context.evaluate(extendExp);
            for(const element of extend.value){
                list.value.push(context.evaluate(element));
            }
            return list;
        },
        "list:foreach": function(context, func, listExp, callbackExp){
            const list = context.evaluate(listExp);
            const callback = context.evaluate(callbackExp);
            if(list.type === "list"){
                for(const item of list){
                    callback.value(context.evaluate(item));
                }
            }
            return list;
        },
        "map": function(context, func, ...pairs){
            const map = {};
            for(let i = 0; i < pairs.length; i++){
                const key = context.evaluate(pairs[i]);
                const value = context.evaluate(pairs[i + 1]);
                map[key.value] = value;
            }
            return {
                type: "map",
                value: map,
            };
        },
        "map:length": function(context, func, mapExp){
            let length = 0;
            for(const key in context.evaluate(mapExp).value){
                length++;
            }
            return length;
        },
        "map:keys": function(context, func, mapExp){
            const map = context.evaluate(mapExp);
            const keys = [];
            for(const key in map){
                keys.push({
                    type: "keyword",
                    value: map.value,
                });
            }
            return {
                type: "list",
                value: keys,
            };
        },
        "map:values": function(context, func, mapExp){
            const map = context.evaluate(mapExp);
            const values = [];
            for(const key in map){
                values.push(map[key]);
            }
            return {
                type: "list",
                value: values,
            };
        },
        "object": function(context, func, objectType, objectValue){
            return {
                type: objectType.value,
                value: context.evaluate(objectValue).value,
            };
        },
        "print": function(context, func, ...args){
            const evalArgs = args.map(e => context.evaluate(e));
            console.log(...evalArgs);
            if(args.length === 0){
                return {
                    type: null,
                    value: "null",
                };
            }else{
                return evalArgs[evalArgs.length - 1];
            }
        },
        "define": function(context, func, identifier, assignTo){
            const assigned = context.evaluate(assignTo);
            context.define(identifier.value, assigned);
            return assigned;
        },
        "function": function(context, func, argsList, funcBody){
            const argNames = context.evaluate(argsList);
            const definedFunc = function(newContext, func, ...args){
                const argsScope = {};
                for(let i = 0; i < argNames.value.length; i++){
                    const argName = argNames.value[i].value;
                    argsScope[argName] = context.evaluate(args[i]);
                }
                const restOfArgs = [];
                for(let j = argNames.value.length; j < args.length; j++){
                    restOfArgs.push(context.evaluate(args[i]));
                }
                argsScope["@"] = {
                    type: "list",
                    value: restOfArgs,
                };
                const funcContext = new lispContext(undefined, argsScope, context);
                return funcContext.evaluate(funcBody);
            };
            return {
                type: "function",
                value: definedFunc,
            };;
        },
        "typeof": function(context, func, value){
            return {
                type: "identifier",
                value: context.evaluate(value).type,
            };
        },
        "==": function(context, func, ...args){
            if(args.length > 1){
                const first = context.evaluate(args[0]);
                for(let i = 1; i < args.length; i++){
                    const n = context.evaluate(arg);
                    if(n.value !== first.value) return {
                        type: "boolean",
                        value: false,
                    };
                }
            }
            return {
                type: "boolean",
                value: true,
            };
        },
        "!=": function(context, func, a, b){
            return {
                type: "boolean",
                value: context.evaluate(a).value !== context.evaluate(b).value,
            };
        },
        "+": function(context, func, ...args){
            let sum = 0;
            for(const arg of args){
                const n = context.evaluate(arg);
                sum += n.value;
            }
            return {
                type: "number",
                value: sum,
            };
        },
        "*": function(context, func, ...args){
            let product = 1;
            for(const arg of args){
                const n = context.evaluate(arg);
                product *= n.value;
            }
            return {
                type: "number",
                value: product,
            };
        },
        "/": function(context, func, a, b){
            return {
                type: "number",
                value: context.evaluate(a).value / context.evaluate(b).value,
            };
        },
        "modulo": function(context, func, a, b){
            return {
                type: "number",
                value: context.evaluate(a).value % context.evaluate(b).value,
            };
        }
    });
}

window.onload = begin;