a small Lisp implementation in javascript

lisp.js

// Data Representation
function isAtom(x) { return typeof x !== 'object' || x === null; }
function isList(x) { return Array.isArray(x); }

// Parser (Converting Text to Data)
function parse(input) {
    // Better tokenization that handles multi-line input
    let tokens = input.replace(/\(/g, ' ( ')
                      .replace(/\)/g, ' ) ')
                      .replace(/\n/g, ' ')          // normalize newlines
                      .replace(/\s+/g, ' ')         // normalize whitespace
                      .trim()
                      .split(' ')
                      .filter(t => t.length > 0);   // remove empty tokens
    
    function parseExpr(tokens) {
        if (tokens.length === 0) {
            throw new Error("Unexpected end of input");
        }
        
        let token = tokens.shift();
        if (token === '(') {
            let expr = [];
            while (tokens.length > 0 && tokens[0] !== ')') {
                expr.push(parseExpr(tokens));
            }
            if (tokens.length === 0) {
                throw new Error("Missing closing parenthesis");
            }
            tokens.shift(); // consume ')'
            return expr;
        } else if (token === ')') {
            throw new Error("Unexpected closing parenthesis");
        } else {
            return isNaN(token) ? token : Number(token);
        }
    }
    return parseExpr(tokens);
}

// Core Operations
function atom(x) { return isAtom(x); }
function eq(x, y) { 
    // Handle empty lists specially
    if (Array.isArray(x) && Array.isArray(y)) {
        return x.length === 0 && y.length === 0;
    }
    return x === y; 
}
function car(list) { return list[0]; }
function cdr(list) { return list.slice(1); }
function cons(element, list) { return [element, ...list]; }

// The Evaluator (Where Magic Happens)
function evaluate(expr, env = {}) {
    // Atoms: look up in environment or return value
    if (isAtom(expr)) {
        return (typeof expr === 'string' && expr in env) ? env[expr] : expr;
    }
    
    // Lists: function calls
    if (isList(expr) && expr.length > 0) {
        let [fn, ...args] = expr;
        
        // Special forms (don't evaluate arguments automatically)
        if (fn === 'quote') return args[0];
        if (fn === 'cond') return evalCond(args, env);
        if (fn === 'lambda') return { type: 'lambda', params: args[0], body: args[1], env };
        if (fn === 'define') { 
            env[args[0]] = evaluate(args[1], env); 
            return env[args[0]]; 
        }
        
        // Primitives
        if (fn === 'atom') return atom(evaluate(args[0], env));
        if (fn === 'eq') return eq(evaluate(args[0], env), evaluate(args[1], env));
        if (fn === 'car') return car(evaluate(args[0], env));
        if (fn === 'cdr') return cdr(evaluate(args[0], env));
        if (fn === 'cons') return cons(evaluate(args[0], env), evaluate(args[1], env));
        
        // Arithmetic (practical additions)
        if (fn === '+') return args.reduce((sum, arg) => sum + evaluate(arg, env), 0);
        if (fn === '*') return args.reduce((prod, arg) => prod * evaluate(arg, env), 1);
        if (fn === '-') {
            if (args.length === 1) return -evaluate(args[0], env);
            let values = args.map(arg => evaluate(arg, env));
            return values.reduce((a, b) => a - b);
        }
        if (fn === '/') {
            let values = args.map(arg => evaluate(arg, env));
            return values.reduce((a, b) => a / b);
        }
        
        // Boolean operations (practical additions)
        if (fn === 'and') return args.every(arg => evaluate(arg, env));
        if (fn === 'or') return args.some(arg => evaluate(arg, env));
        if (fn === 'not') return !evaluate(args[0], env);
        
        // Function calls
        let func = evaluate(fn, env);
        if (func?.type === 'lambda') {
            let newEnv = { ...func.env };
            func.params.forEach((param, i) => newEnv[param] = evaluate(args[i], env));
            return evaluate(func.body, newEnv);
        }
    }
    throw new Error(`Cannot evaluate: ${JSON.stringify(expr)}`);
}

function evalCond(clauses, env) {
    for (let [condition, result] of clauses) {
        if (evaluate(condition, env)) return evaluate(result, env);
    }
    throw new Error("No cond clause was true");
}

// Testing Our Lisp
let env = {};

// Basic operations
evaluate(parse("(+ 1 2 3)"), env);                       // 6
evaluate(parse("(car (quote (1 2 3)))"), env);           // 1
evaluate(parse("(cons 1 (quote (2 3)))"), env);          // [1, 2, 3]

// Boolean operations
evaluate(parse("(and true true false)"), env);           // false
evaluate(parse("(or false true)"), env);                 // true
evaluate(parse("(not false)"), env);                     // true

// Define and call functions
evaluate(parse("(define double (lambda (x) (* x 2)))"), env);
evaluate(parse("(double 5)"), env);                      // 10

// Recursion works!
evaluate(parse(`
    (define factorial (lambda (n)
        (cond
            ((eq n 0) 1)
            (true (* n (factorial (- n 1)))))))
`), env);
evaluate(parse("(factorial 5)"), env);                   // 120

// Building complexity from simple parts
evaluate(parse("(define square (lambda (x) (* x x)))"), env);
evaluate(parse("(define sum-squares (lambda (x y) (+ (square x) (square y))))"), env);
evaluate(parse("(sum-squares 3 4)"), env);               // 25

// Higher-level data structures and operations
evaluate(parse(`
    (define assoc (lambda (key alist)
        (cond
            ((eq alist (quote ())) (quote ()))
            ((eq (car (car alist)) key) (car alist))
            (true (assoc key (cdr alist))))))
`), env);

evaluate(parse(`
    (define map (lambda (func list)
        (cond
            ((eq list (quote ())) (quote ()))
            (true (cons (func (car list)) 
                       (map func (cdr list)))))))
`), env);

// Using our higher-level functions
evaluate(parse(`
    (define phonebook (quote 
        ((alice 555-1234) 
         (bob 555-5678) 
         (charlie 555-9012))))
`), env);
evaluate(parse("(assoc bob phonebook)"), env);           // ["bob", "555-5678"]

evaluate(parse("(map square (quote (1 2 3 4)))"), env);  // [1, 4, 9, 16]
evaluate(parse("(map double (quote (10 20 30)))"), env); // [20, 40, 60]