1 files changed, 35 insertions, 25 deletions

diff --git a/src/interpreter/interpreter.ts b/src/interpreter/interpreter.ts
index c79a2cf..6580a4f 100644
--- a/src/interpreter/interpreter.ts
+++ b/src/interpreter/interpreter.ts
@@ -11,6 +11,11 @@ export class InvalidLambdaTermError extends Error {}
 
 export class MaxRecursionDepthError extends Error {}
 
+export type Visitors = Map<
+  string,
+  (term: DebrujinifiedLambdaTerm) => DebrujinifiedLambdaTerm
+>;
+
 export type DebrujinAbstraction = {
   abstraction: {
     param: string;
@@ -28,6 +33,7 @@ export type DebrujinApplication = {
 export type DebrujinIndex = { name: string; index: number };
 
 export type DebrujinifiedLambdaTerm =
+  | ((t: DebrujinifiedLambdaTerm) => DebrujinifiedLambdaTerm)
   | DebrujinAbstraction
   | DebrujinApplication
   | DebrujinIndex;
@@ -76,6 +82,10 @@ export const substitute = (
   index: number,
   withTerm: DebrujinifiedLambdaTerm,
 ): DebrujinifiedLambdaTerm => {
+  if (typeof inTerm === "function") {
+    return inTerm(withTerm);
+  }
+
   if ("index" in inTerm) {
     if (inTerm.index > index) {
       return adjustIndices(inTerm, -1);
@@ -154,51 +164,45 @@ export const adjustIndices = (
 
 export const betaReduce = (
   term: DebrujinifiedLambdaTerm,
+  visitors: Visitors,
   maxDepth: number,
 ): DebrujinifiedLambdaTerm => {
   if (maxDepth === 0) {
     throw new MaxRecursionDepthError("max recursion depth identified");
   }
-  if ("index" in term) {
+  if (typeof term === "function") {
     return term;
   }
 
+  if ("index" in term) {
+    const replacement = visitors.get(term.name)?.apply(null, [term]);
+    return replacement ?? term;
+  }
+
   if ("abstraction" in term) {
     const { body, param } = term.abstraction;
 
     return {
       abstraction: {
-        body: betaReduce(body, maxDepth - 1),
+        body: betaReduce(body, visitors, maxDepth - 1),
         param,
       },
     };
   }
 
   if ("application" in term) {
-    const { left } = term.application;
-    const args = term.application.args.map((term) =>
-      betaReduce(term, maxDepth - 1),
+    const { left, args } = term.application;
+    const [reducedLeft, ...reducedArgs] = [left, ...args].map((term) =>
+      betaReduce(term, visitors, maxDepth - 1),
     );
-
-    return args.reduce((acc: DebrujinifiedLambdaTerm, x) => {
+    return reducedArgs.reduce((acc: DebrujinifiedLambdaTerm, x) => {
       if ("abstraction" in acc) {
         const { body } = acc.abstraction;
-        const newBody = substitute(body, 1, x);
-        return newBody;
+        const substituted = substitute(body, 1, x);
+        return substituted;
       }
-      if ("application" in acc) {
-        const {
-          application: { left, args },
-        } = acc;
-        return {
-          application: {
-            left,
-            args: [...args, x],
-          },
-        };
-      }
-      return { application: { left: acc, args: [x] } };
-    }, left);
+      return acc;
+    }, reducedLeft);
   }
 
   throw new InvalidLambdaTermError(
@@ -207,6 +211,10 @@ export const betaReduce = (
 };
 
 export const emitDebrujin = (term: DebrujinifiedLambdaTerm): string => {
+  if (typeof term === "function") {
+    return term.toString();
+  }
+
   if ("index" in term) {
     return term.index.toString();
   }
@@ -250,18 +258,20 @@ export const interpret = (
   term: string,
   symbolTable = new SymbolTable(),
   allowUnderscores = false, // in our world, underscores should be internal to the game.
-  maxDepth = 15,
+  visitors: Visitors = new Map(),
+  maxDepth = 20,
 ): DebrujinifiedLambdaTerm => {
   const ast = parse(term, allowUnderscores);
   const debrujined = debrujinify(ast, symbolTable);
 
   let prev = debrujined;
-  let next = betaReduce(prev, maxDepth);
+  let next = betaReduce(prev, visitors, maxDepth);
 
   while (emitDebrujin(prev) !== emitDebrujin(next)) {
     // alpha equivalence
     prev = next;
-    next = betaReduce(prev, maxDepth);
+    next = betaReduce(prev, visitors, maxDepth);
   }
+  console.log(next);
   return next;
 };