intercaetera · March 15, 2025 21:18 · Mar 15, 2025
diff --git a/lisp.js b/lisp.js
@@ -0,0 +1,98 @@
+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))