checkpointchurch-numerals

9 files changed, 190 insertions, 54 deletions

diff --git a/src/engine/TheAbstractionEngine.ts b/src/engine/TheAbstractionEngine.ts
index 63c6274..793de7d 100644
--- a/src/engine/TheAbstractionEngine.ts
+++ b/src/engine/TheAbstractionEngine.ts
@@ -38,7 +38,9 @@ export class TheAbstractionEngine {
     [
       new RadialObserve(),
       new Modal(),
-      new Level(isDev ? LevelNames.CarCadr : LevelNames.LevelSelection),
+      new Level(
+        isDev ? LevelNames.ChurchNumeralsOne : LevelNames.LevelSelection,
+      ),
       inputSystem,
       facingDirectionSystem,
       new Grid(
diff --git a/src/engine/entities/FunctionApplication.ts b/src/engine/entities/FunctionApplication.ts
index 4d5729f..f4201de 100644
--- a/src/engine/entities/FunctionApplication.ts
+++ b/src/engine/entities/FunctionApplication.ts
@@ -24,8 +24,9 @@ import { Game } from "..";
 import { Grid as GridSystem, SystemNames } from "../systems";
 import { colors, tryWrap } from "../utils";
 import {
-  InvalidLambdaTermError,
+  DebrujinIndex,
   SymbolTable,
+  Visitors,
   emitNamed,
   interpret,
 } from "../../interpreter";
@@ -41,16 +42,9 @@ const APPLICATION_RESULTS: Record<
 export class FunctionApplication extends Entity {
   private static spriteSpec = SPRITE_SPECS.get(Sprites.BUBBLE) as SpriteSpec;
 
-  private symbolTable: SymbolTable;
-
   constructor(gridPosition: Coord2D, lambdaTerm: string) {
     super(EntityNames.FunctionApplication);
 
-    this.symbolTable = new SymbolTable();
-    Object.keys(APPLICATION_RESULTS).forEach((key) => {
-      this.symbolTable.add(key);
-    });
-
     const dimension = {
       width: FunctionApplication.spriteSpec.width,
       height: FunctionApplication.spriteSpec.height,
@@ -151,7 +145,10 @@ export class FunctionApplication extends Entity {
     );
     const newCode = applicationTerm.code.replace("_INPUT", functionTerm.code);
 
-    const result = tryWrap(() => interpret(newCode, this.symbolTable, true));
+    const { symbolTable, visitors } = this.getVisitors(game);
+    const result = tryWrap(() =>
+      interpret(newCode, symbolTable, true, visitors),
+    );
     applicationTerm.last = result;
     if (result.error || !result.data) {
       console.error(result.error);
@@ -166,13 +163,6 @@ export class FunctionApplication extends Entity {
 
     let applicationResultingEntity: Entity | null = null; // this should be its own function
     const { data } = result;
-    if ("application" in data) {
-      // if we get an application that means we didn't interpret correctly.
-      // this should "not" happen and should be fatal.
-      throw new InvalidLambdaTermError(
-        "produced term should not be an application",
-      );
-    }
     if ("abstraction" in data) {
       const code = emitNamed(data);
       applicationResultingEntity = new FunctionBox(grid.gridPosition, code);
@@ -187,20 +177,100 @@ export class FunctionApplication extends Entity {
     }
 
     game.removeEntity(entity.id);
-    if (applicationResultingEntity) {
-      const grid = applicationResultingEntity.getComponent<Grid>(
+    if (!applicationResultingEntity) {
+      return;
+    }
+
+    applicationResultingEntity.getComponent<Grid>(
+      ComponentNames.Grid,
+    ).movingDirection = entityGrid.previousDirection;
+    game.addEntity(applicationResultingEntity);
+  }
+
+  private getVisitors(game: Game): {
+    visitors: Visitors;
+    symbolTable: SymbolTable;
+  } {
+    const directionKeywords = {
+      _LEFT: Direction.LEFT,
+      _RIGHT: Direction.RIGHT,
+      _DOWN: Direction.DOWN,
+      _UP: Direction.UP,
+    };
+    const entityKeywords = {
+      _KEY: (pos: Coord2D) => new Key(pos),
+    };
+
+    const visitors: Visitors = new Map();
+    visitors.set("_SPAWN", (_term) => {
+      const position = this.getComponent<Grid>(
         ComponentNames.Grid,
-      );
-      grid.movingDirection = entityGrid.previousDirection;
-      applicationResultingEntity.addComponent(grid);
+      ).gridPosition;
+      return {
+        abstraction: {
+          param: "_DIRECTION",
+          body: (direction) => {
+            const destinationDirection =
+              directionKeywords[
+                (direction as DebrujinIndex)
+                  .name! as keyof typeof directionKeywords
+              ];
+            const destination = game
+              .getSystem<GridSystem>(SystemNames.Grid)
+              .getNewGridPosition(position, destinationDirection);
+            return {
+              abstraction: {
+                param: "_ENTITY",
+                body: (entityType) => {
+                  const entityFactory =
+                    entityKeywords[
+                      (entityType as DebrujinIndex)
+                        .name! as keyof typeof entityKeywords
+                    ];
+                  const newEntity = entityFactory(destination);
+                  game.addEntity(newEntity);
+                  return {
+                    abstraction: {
+                      param: "_x",
+                      body: (_t) => {
+                        return {
+                          application: {
+                            left: {
+                              index: 1,
+                              name: "_SPAWN",
+                            },
+                            args: [direction, entityType],
+                          },
+                        };
+                      },
+                    },
+                  };
+                },
+              },
+            };
+          },
+        },
+      };
+    });
 
-      game.addEntity(applicationResultingEntity);
-    }
+    return {
+      visitors,
+      symbolTable: SymbolTable.from(
+        Array.from(visitors.keys())
+          .concat(Object.keys(APPLICATION_RESULTS))
+          .concat(Object.keys(directionKeywords))
+          .concat(Object.keys(entityKeywords))
+          .concat(["_x"]),
+      ),
+    };
+  }
 
-    SOUNDS.get(LambdaTransformSound.name)!.play();
+  private addParticles(game: Game, position: Coord2D) {
+    const gridSystem = game.getSystem<GridSystem>(SystemNames.Grid);
     const { dimension } = gridSystem;
+    SOUNDS.get(LambdaTransformSound.name)!.play();
     const particles = new Particles({
-      center: gridSystem.gridToScreenPosition(nextPosition),
+      center: gridSystem.gridToScreenPosition(position),
       spawnerDimensions: {
         width: dimension.width / 2,
         height: dimension.height / 2,
diff --git a/src/engine/levels/CarCadr.ts b/src/engine/levels/CarCadr.ts
index 10ff6d9..8875623 100644
--- a/src/engine/levels/CarCadr.ts
+++ b/src/engine/levels/CarCadr.ts
@@ -9,8 +9,6 @@ import {
   Player,
   Wall,
 } from "../entities";
-import { Piston } from "../entities/Piston";
-import { Direction } from "../interfaces";
 import { Grid, SystemNames } from "../systems";
 import { normalRandom } from "../utils";
 
diff --git a/src/engine/levels/ChurchNumeralsOne.ts b/src/engine/levels/ChurchNumeralsOne.ts
new file mode 100644
index 0000000..2dbb6b5
--- /dev/null
+++ b/src/engine/levels/ChurchNumeralsOne.ts
@@ -0,0 +1,45 @@
+import { FunctionApplication, Grass, LambdaFactory, Player } from "../entities";
+import { Game } from "../Game";
+import { Grid, SystemNames } from "../systems";
+import { normalRandom } from "../utils";
+import { Level } from "./Level";
+import { LevelNames } from "./LevelNames";
+
+export class ChurchNumeralsOne extends Level {
+  constructor() {
+    super(LevelNames.ChurchNumeralsOne);
+  }
+
+  public init(game: Game) {
+    const grid = game.getSystem<Grid>(SystemNames.Grid);
+    const dimensions = grid.getGridDimensions();
+
+    const grasses = Array.from({ length: dimensions.width })
+      .fill(0)
+      .map(() => {
+        // random grass
+        return new Grass({
+          x: Math.floor(
+            normalRandom(dimensions.width / 2, dimensions.width / 4, 1.5),
+          ),
+          y: Math.floor(
+            normalRandom(dimensions.height / 2, dimensions.height / 4, 1.5),
+          ),
+        });
+      });
+
+    [
+      ...grasses,
+      new LambdaFactory({ x: 1, y: 1 }, "(\\ (f) . (\\ (x) . (f f x)))", 1),
+      new FunctionApplication(
+        { x: 2, y: 2 },
+        "(_INPUT ((_SPAWN _RIGHT) _KEY))",
+      ),
+      new FunctionApplication(
+        { x: 3, y: 3 },
+        "(_INPUT _EMPTY)",
+      ),
+      new Player({ x: 0, y: 0 }),
+    ].forEach((e) => game.addEntity(e));
+  }
+}
diff --git a/src/engine/levels/LevelNames.ts b/src/engine/levels/LevelNames.ts
index 7f3c4f1..c8182ab 100644
--- a/src/engine/levels/LevelNames.ts
+++ b/src/engine/levels/LevelNames.ts
@@ -1,5 +1,6 @@
 export namespace LevelNames {
   export const Tutorial = "0";
   export const CarCadr = "1";
+  export const ChurchNumeralsOne = "2";
   export const LevelSelection = "LevelSelection";
 }
diff --git a/src/engine/levels/Tutorial.ts b/src/engine/levels/Tutorial.ts
index 97a6826..fc927da 100644
--- a/src/engine/levels/Tutorial.ts
+++ b/src/engine/levels/Tutorial.ts
@@ -36,6 +36,7 @@ export class Tutorial extends Level {
         });
       });
 
+    // TODO: new level which adds introductory syntax
     const entities = [
       ...grasses,
       new Sign(
@@ -51,7 +52,7 @@ export class Tutorial extends Level {
       new Wall({ x: 11, y: 10 }),
       new Curry({ x: 10, y: 10 }),
       new LockedDoor({ x: 9, y: 10 }),
-      new LambdaFactory({ x: 6, y: 3 }, "// TODO: Remove line\n(λ (x) . x)", 3),
+      new LambdaFactory({ x: 6, y: 3 }, "// TODO: Remove this comment\n(λ (x) . x)", 3),
       new FunctionApplication({ x: 6, y: 6 }, "(_INPUT _KEY)"),
       new Player({ x: 2, y: 2 }),
     ];
diff --git a/src/engine/levels/index.ts b/src/engine/levels/index.ts
index 216453c..f47000b 100644
--- a/src/engine/levels/index.ts
+++ b/src/engine/levels/index.ts
@@ -6,13 +6,16 @@ export * from "./CarCadr";
 
 import { LevelNames } from ".";
 import { CarCadr, LevelSelection, Tutorial, Level } from ".";
+import { ChurchNumeralsOne } from "./ChurchNumeralsOne";
 
 export const LEVELS: Level[] = [
   new LevelSelection(),
   new Tutorial(),
   new CarCadr(),
+  new ChurchNumeralsOne(),
 ];
 export const LEVEL_PROGRESSION: Record<string, string[]> = {
   [LevelNames.LevelSelection]: [LevelNames.Tutorial],
   [LevelNames.Tutorial]: [LevelNames.CarCadr],
+  [LevelNames.CarCadr]: [LevelNames.ChurchNumeralsOne],
 };
diff --git a/src/interpreter/SymbolTable.ts b/src/interpreter/SymbolTable.ts
index e2ff7e1..df88d8f 100644
--- a/src/interpreter/SymbolTable.ts
+++ b/src/interpreter/SymbolTable.ts
@@ -46,4 +46,10 @@ export class SymbolTable {
   public createChild(): SymbolTable {
     return new SymbolTable(this);
   }
+
+  public static from(collection: Array<string> | Set<string>): SymbolTable {
+    const table = new SymbolTable();
+    collection.forEach((symbol) => table.add(symbol));
+    return table;
+  }
 }
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;
 };