Lisp in JS

lisp.js

const symbols = [
    // special forms
    'lambda', 'when', 'rec', 'define',
    // standard library
    'inc', 'dec', 'add', 'mul', 'eq', 'head', 'tail', 'cons', 'list', 'isNil',
    // variables
    'a', 'b', 'c', 'k', 'l', 'm', 'n', 'x', 'y', 'z',
    'as', 'xs',
    'fn', 'double', 'map',
]

const createSymbol = name => {
    globalThis[name] = Symbol(name)
}

symbols.forEach(createSymbol)

const defaultEnv = a => {
    if (a === inc) return x => x + 1
    if (a === dec) return x => x - 1
    if (a === add) return (x, y) => x + y
    if (a === mul) return (x, y) => x * y
    if (a === eq) return (x, y) => x === y
    if (a === head) return ([x]) => x
    if (a === tail) return ([_x, ...xs]) => xs
    if (a === cons) return (x, xs) => ([x, ...xs])
    if (a === list) return (...xs) => xs
    if (a === isNil) return x => Array.isArray(x) && x.length === 0

    throw new Error(`unbound symbol: ${a.toString()}`)
}

const evaluate = (expr, env = defaultEnv) => {
    if (['number', 'boolean', 'function', 'string'].includes(typeof expr)) return expr
    if (typeof expr === 'symbol') return env(expr)
    if (expr[0] === lambda) return evalLambda(expr, env)
    if (expr[0] === when) return evalWhen(expr, env)
    if (expr[0] === define) return evalDefine(expr, env)
    return apply(expr, env)
}

const evalLambda = ([_lambda, params, body], env) => {
    const fn = (...args) => {
        const newEnv = b => {
            const index = params.indexOf(b)
            if (index !== -1) return args[index]
            if (b === rec) return fn
            return env(b)
        }
        return evaluate(body, newEnv)
    }

    return fn
}

const evalWhen = ([_when, cond, then, otherwise], env) => {
    if (evaluate(cond, env)) {
        return evaluate(then, env)
    } else {
        return evaluate(otherwise, env)
    }
}

const evalDefine = ([_define, definitions, body], env) => {
    const newEnv = definitions.reduce((env, [symbol, definition]) => {
        return b => {
            if (b === symbol) return evaluate(definition, env)
            return env(b)
        }
    }, env)

    return evaluate(body, newEnv)
}

const apply = ([operator, ...operands], env) => {
    const fn = evaluate(operator, env)
    if (typeof fn !== 'function') {
        console.log(operator)
        throw new Error(`not a function, ${operator.toString()}`)
    }
    const args = operands.map(operand => evaluate(operand, env))
    return fn(...args)
}

const program = 
    [define, [
        [double, [lambda, [a], [mul, a, 2]]],
        [xs, [list, 1, 2, 3, 4, 5]],
        [map, [lambda, [fn, as],
            [when, [isNil, as],
                [list],
                [cons, [fn, [head, as]], [rec, fn, [tail, as]]]
            ]]]
    ], 
        [map, double, xs]]


console.log(evaluate(program))