implement recursion properly with closures

4 files changed, 116 insertions, 108 deletions

diff --git a/src/lang/ts-lang/builtin/builtin.ts b/src/lang/ts-lang/builtin/builtin.ts
index 8532072..cdd8991 100644
--- a/src/lang/ts-lang/builtin/builtin.ts
+++ b/src/lang/ts-lang/builtin/builtin.ts
@@ -50,18 +50,3 @@ export type BUILTIN_Eq<Args extends readonly any[]> = Args extends
   | readonly boolean[]
   ? ArrayEqual<Args>
   : FnError<`Can only check equality of numbers or string or boolean, but got ${ToString<Args>}`>;
-
-export type BUILTIN_IfElse<Args extends readonly any[]> = Args extends [
-  infer A,
-  infer B,
-  infer C,
-  infer D
-]
-  ? FnError<`Invalid args for "if": ${ToString<Args>}`>
-  : Args extends [infer Cond, infer TrueVal, infer FalseVal]
-  ? Cond extends true
-    ? TrueVal
-    : Cond extends false
-    ? FalseVal
-    : FnError<`Condition value ${ToString<Cond>} is not a boolean`>
-  : FnError<`Invalid args for "if": ${ToString<Args>}`>;
diff --git a/src/lang/ts-lang/builtin/sbuiltin.ts b/src/lang/ts-lang/builtin/sbuiltin.ts
index f873666..c92fd6a 100644
--- a/src/lang/ts-lang/builtin/sbuiltin.ts
+++ b/src/lang/ts-lang/builtin/sbuiltin.ts
@@ -1,27 +1,63 @@
+import { FnError } from ".";
 import { ASTNode, StackFrame } from "../core/common";
-import { CallFn, FnPrim, GetEvaluatedChildren, EvalError } from "../core/eval";
+import {
+  CallFn,
+  FnPrim,
+  GetEvaluatedChildren,
+  EvalError,
+  _Evaluate,
+} from "../core/eval";
 import { ExtractNumber, ToString } from "../util";
 
 export type SBUILTIN_Call<
   Node extends ASTNode,
-  Frame extends StackFrame
-> = GetEvaluatedChildren<Node, Frame> extends [
+  Frame extends StackFrame,
+  Callstack extends readonly string[]
+> = GetEvaluatedChildren<Node, Frame, Callstack> extends [
   infer Fn,
   ...infer Values extends readonly any[]
 ]
-  ? CallFn<Fn, Values, Frame>
+  ? CallFn<Fn, Values, Frame, Callstack>
   : EvalError<`Invalid params for function call: ${ToString<
-      GetEvaluatedChildren<Node, Frame>
+      GetEvaluatedChildren<Node, Frame, Callstack>
     >}`>;
 
 export type SBUILTIN_Map<
   Node extends ASTNode,
-  Frame extends StackFrame
-> = GetEvaluatedChildren<Node, Frame> extends [
+  Frame extends StackFrame,
+  Callstack extends readonly string[]
+> = GetEvaluatedChildren<Node, Frame, Callstack> extends [
   infer Arr extends readonly any[],
   infer Fn extends FnPrim
 ]
-  ? { [Idx in keyof Arr]: CallFn<Fn, [Arr[Idx], ExtractNumber<Idx>], Frame> }
+  ? {
+      [Idx in keyof Arr]: CallFn<
+        Fn,
+        [Arr[Idx], ExtractNumber<Idx>],
+        Frame,
+        Callstack
+      >;
+    }
   : EvalError<`Invalid params for map: ${ToString<
-      GetEvaluatedChildren<Node, Frame>
+      GetEvaluatedChildren<Node, Frame, Callstack>
     >}`>;
+
+export type SBUILTIN_IfElse<
+  Node extends ASTNode,
+  Frame extends StackFrame,
+  Callstack extends readonly string[]
+> = Node["children"] extends infer Children extends readonly ASTNode[]
+  ? Children extends [infer A, infer B, infer C, infer D]
+    ? FnError<`Invalid args for "if": ${ToString<Children>}`>
+    : Children extends [
+        infer Cond extends ASTNode,
+        infer TrueVal extends ASTNode,
+        infer FalseVal extends ASTNode
+      ]
+    ? _Evaluate<Cond, Frame, Callstack> extends true
+      ? _Evaluate<TrueVal, Frame, Callstack>
+      : _Evaluate<Cond, Frame, Callstack> extends false
+      ? _Evaluate<FalseVal, Frame, Callstack>
+      : FnError<`Condition value ${ToString<Cond>} is not a boolean`>
+    : FnError<`Invalid args for "if": ${ToString<Children>}`>
+  : never;
diff --git a/src/lang/ts-lang/core/common.ts b/src/lang/ts-lang/core/common.ts
index 95a9ad3..0287eec 100644
--- a/src/lang/ts-lang/core/common.ts
+++ b/src/lang/ts-lang/core/common.ts
@@ -50,11 +50,11 @@ export type ParserCtx = {
   stack: readonly ASTNode[];
 };
 
-export type StackFrame<
+export interface StackFrame<
   Bindings extends Record<ASTNode["name"], any> = Record<ASTNode["name"], any>
-> = {
+> {
   bindings: Bindings;
-};
+}
 
 export type EmptyStackFrame = StackFrame<{}>;
 
diff --git a/src/lang/ts-lang/core/eval.ts b/src/lang/ts-lang/core/eval.ts
index 511ada9..cc503a5 100644
--- a/src/lang/ts-lang/core/eval.ts
+++ b/src/lang/ts-lang/core/eval.ts
@@ -2,14 +2,14 @@ import {
   BUILTIN_Add,
   BUILTIN_Arr,
   BUILTIN_Eq,
-  BUILTIN_IfElse,
   BUILTIN_Mul,
   BUILTIN_Sub,
   BUILTIN_ToString,
   SBUILTIN_Call,
+  SBUILTIN_IfElse,
   SBUILTIN_Map,
 } from "../builtin";
-import { NumberToArray, ToString } from "../util";
+import { ToString } from "../util";
 import {
   ASTNode,
   EmptyStackFrame,
@@ -18,15 +18,24 @@ import {
   StackFrame,
 } from "./common";
 
+export type RECURSION_DEPTH_LIMIT = 7;
+
 export type SENTINEL_NO_BUILTIN = "__NO_BUILTIN__";
 export type MapBuiltins<
   Node extends ASTNode,
-  Frame extends StackFrame
-> = GetEvaluatedChildren<Node, Frame> extends infer Args extends readonly any[]
+  Frame extends StackFrame,
+  Callstack extends readonly string[]
+> = GetEvaluatedChildren<
+  Node,
+  Frame,
+  Callstack
+> extends infer Args extends readonly any[]
   ? Node["name"] extends "call"
-    ? SBUILTIN_Call<Node, Frame>
+    ? SBUILTIN_Call<Node, Frame, Callstack>
     : Node["name"] extends "map"
-    ? SBUILTIN_Map<Node, Frame>
+    ? SBUILTIN_Map<Node, Frame, Callstack>
+    : Node["name"] extends "?"
+    ? SBUILTIN_IfElse<Node, Frame, Callstack>
     : Node["name"] extends "tostring"
     ? BUILTIN_ToString<Args>
     : Node["name"] extends "arr"
@@ -39,8 +48,6 @@ export type MapBuiltins<
     ? BUILTIN_Mul<Args>
     : Node["name"] extends "eq"
     ? BUILTIN_Eq<Args>
-    : Node["name"] extends "?"
-    ? BUILTIN_IfElse<Args>
     : SENTINEL_NO_BUILTIN
   : never;
 
@@ -60,58 +67,17 @@ export type FnPrim<
   Fn extends ASTNode = ASTNode
 > = { args: Args; fn: Fn };
 
-export type NamedFnPrim<
-  Args extends readonly ASTNode[],
-  Fn extends ASTNode,
-  Name extends string,
-  CapturedFrame extends StackFrame
-> = { args: Args; fn: Fn; name: Name; frame: CapturedFrame };
-
-type BuildDeepBinding<
-  FnPrim extends NamedFnPrim<any, any, any, any>,
-  Depth extends readonly any[] = [any, any, any, any, any, any, any]
-> = Depth extends []
-  ? FnPrim
-  : BuildDeepBinding<
-      NamedFnPrim<
-        FnPrim["args"],
-        FnPrim["fn"],
-        FnPrim["name"],
-        MergeStackFrames<
-          FnPrim["frame"],
-          StackFrame<{
-            [K in FnPrim["name"]]: NamedFnPrim<
-              FnPrim["args"],
-              FnPrim["fn"],
-              FnPrim["name"],
-              FnPrim["frame"]
-            >;
-          }>
-        >
-      >,
-      Depth extends [infer Head, ...infer Tail] ? Tail : []
-    >;
-
 export type HandleBind<
   Node extends ASTNode,
-  Frame extends StackFrame
+  Frame extends StackFrame,
+  Callstack extends readonly string[]
 > = Node["children"] extends [
   infer Name extends ASTNode,
   infer Value extends ASTNode
 ]
-  ? _Evaluate<Value, Frame> extends infer U
+  ? _Evaluate<Value, Frame, [...Callstack, "bind"]> extends infer U
     ? U extends FnPrim
-      ? NamedFnPrim<
-          U["args"],
-          U["fn"],
-          Name["name"],
-          Frame
-        > extends infer NamedFn
-        ? NamedFn extends NamedFnPrim<infer A, infer F, infer N, any>
-          ? // RECURSION DEPTH LIMIT = 5
-            BuildDeepBinding<NamedFn, NumberToArray<5>>
-          : never
-        : never
+      ? readonly [U, Frame, Name["name"]]
       : U
     : never
   : never;
@@ -141,48 +107,69 @@ export type MapZip<
 export type CallFn<
   Fn,
   Values extends readonly any[],
-  Frame extends StackFrame
-> = Fn extends NamedFnPrim<
-  infer Args,
-  infer FnBody,
-  infer Name,
-  infer CapturedFrame
->
+  Frame extends StackFrame,
+  Callstack extends readonly string[]
+> = Fn extends readonly [
+  infer Prim extends FnPrim,
+  infer CapturedFrame extends StackFrame,
+  infer Name extends ASTNode["name"]
+]
   ? _Evaluate<
-      FnBody,
-      MergeStackFrames<CapturedFrame, StackFrame<MapZip<Args, Values>>>
+      Prim["fn"],
+      MergeStackFrames<
+        CapturedFrame,
+        MergeStackFrames<
+          StackFrame<{ [K in Name]: Fn }>,
+          StackFrame<MapZip<Prim["args"], Values>>
+        >
+      >,
+      [...Callstack, "call"]
     >
   : Fn extends FnPrim<infer Args, infer FnBody>
-  ? _Evaluate<FnBody, MergeStackFrames<Frame, StackFrame<MapZip<Args, Values>>>>
+  ? _Evaluate<
+      FnBody,
+      MergeStackFrames<Frame, StackFrame<MapZip<Args, Values>>>,
+      [...Callstack, "call"]
+    >
   : Fn;
 
 export type _Evaluate<
   Node extends ASTNode,
-  Frame extends StackFrame
-> = Node["type"] extends NodeType.INT
-  ? Node["value"]
-  : Node["type"] extends NodeType.EXT
-  ? // special builtins
-    Node["name"] extends "bind"
-    ? HandleBind<Node, Frame>
-    : Node["name"] extends "fn"
-    ? HandleFn<Node, Frame>
-    : MapBuiltins<Node, Frame> extends infer BI
-    ? BI extends SENTINEL_NO_BUILTIN
-      ? FindInStack<Frame, Node["name"]>
-      : BI
-    : never
-  : EvalError<`Unhandled node type ${Node["type"]}`>;
+  Frame extends StackFrame,
+  Callstack extends readonly string[]
+> = Callstack extends infer C extends readonly any[]
+  ? C["length"] extends RECURSION_DEPTH_LIMIT
+    ? EvalError<`Too deep: ${ToString<Callstack>}`>
+    : Node["type"] extends NodeType.INT
+    ? Node["value"]
+    : Node["type"] extends NodeType.EXT
+    ? // special builtins
+      Node["name"] extends "bind"
+      ? HandleBind<Node, Frame, Callstack>
+      : Node["name"] extends "fn"
+      ? HandleFn<Node, Frame>
+      : MapBuiltins<Node, Frame, Callstack> extends infer BI
+      ? BI extends SENTINEL_NO_BUILTIN
+        ? FindInStack<Frame, Node["name"]>
+        : BI
+      : never
+    : EvalError<`Unhandled node type ${Node["type"]}`>
+  : never;
 
 export type GetEvaluatedChildren<
   Node extends ASTNode,
-  Frame extends StackFrame
+  Frame extends StackFrame,
+  Callstack extends readonly string[]
 > = Node["children"] extends infer Children extends readonly ASTNode[]
   ? {
       [Idx in keyof Children]: Children[Idx] extends ASTNode
-        ? _Evaluate<Children[Idx], Frame>
+        ? _Evaluate<Children[Idx], Frame, Callstack>
         : never;
     }
   : never;
 
-export type Evaluate<Node extends ASTNode> = _Evaluate<Node, EmptyStackFrame>;
+export type Evaluate<Node extends ASTNode> = _Evaluate<
+  Node,
+  EmptyStackFrame,
+  []
+>;