recursion works for types with depth limit 5

8 files changed, 208 insertions, 26 deletions

diff --git a/src/lang/js-lang/builtin/builtin.ts b/src/lang/js-lang/builtin/builtin.ts
index d54c439..ed279f6 100644
--- a/src/lang/js-lang/builtin/builtin.ts
+++ b/src/lang/js-lang/builtin/builtin.ts
@@ -17,6 +17,22 @@ export const V_BUILTIN_Add: BUILTIN = (args) => {
   throw new Error(`Cannot add operands ${JSON.stringify(args, undefined, 2)}`);
 };
 
+export const V_BUILTIN_Sub: BUILTIN = (args) => {
+  if (args.length !== 2) {
+    throw new Error(
+      `Can only sub [number, number], but got ${JSON.stringify(args)}`
+    );
+  }
+
+  if (isNaN(args[0]) || isNaN(args[1])) {
+    throw new Error(
+      `Can only sub [number, number], but got ${JSON.stringify(args)}`
+    );
+  }
+
+  return args[0] - args[1];
+};
+
 export const V_BUILTIN_Mul: BUILTIN = (args) => {
   if (args.every((arg) => typeof arg === "number") && args.length === 2) {
     return args.reduce((acc, cur) => acc * cur, 1);
@@ -31,6 +47,33 @@ export const V_BUILTIN_Mul: BUILTIN = (args) => {
   );
 };
 
+export const V_BUILTIN_Eq: BUILTIN = (args) => {
+  const firstLast = {};
+  let last = firstLast;
+
+  for (const arg of args) {
+    if (!["number", "string", "boolean"].includes(typeof arg)) {
+      throw new Error(
+        `Can only check equality of numbers or string or boolean, but got ${JSON.stringify(
+          args
+        )}`
+      );
+    }
+
+    if (last === firstLast) {
+      continue;
+    }
+
+    if (arg === last) {
+      continue;
+    }
+
+    return false;
+  }
+
+  return true;
+};
+
 export const V_BUILTIN_IfElse: BUILTIN = (args) => {
   if (args.length !== 3) {
     throw new Error(`Invalid args for "if": ${JSON.stringify(args)}`);
@@ -49,6 +92,8 @@ export const nameToBUILTIN: Record<string, BUILTIN> = {
   arr: V_BUILTIN_Arr,
   tostring: V_BUILTIN_ToString,
   add: V_BUILTIN_Add,
+  sub: V_BUILTIN_Sub,
   mul: V_BUILTIN_Mul,
+  eq: V_BUILTIN_Eq,
   "?": V_BUILTIN_IfElse,
 };
diff --git a/src/lang/ts-lang/builtin/builtin.ts b/src/lang/ts-lang/builtin/builtin.ts
index ed6b0a3..8532072 100644
--- a/src/lang/ts-lang/builtin/builtin.ts
+++ b/src/lang/ts-lang/builtin/builtin.ts
@@ -2,7 +2,9 @@ import { FnError } from ".";
 import {
   AddNumbers,
   AddStrings,
+  ArrayEqual,
   Multiply,
+  SubNumbers,
   ToString,
   UnarrayIfOnlyHead,
 } from "../util";
@@ -22,6 +24,16 @@ export type BUILTIN_Add<Args extends readonly any[]> =
     ? AddNumbers<Args>
     : FnError<`Cannot add operands ${ToString<Args>}`>;
 
+export type BUILTIN_Sub<Args extends readonly any[]> = Args extends [
+  infer A,
+  infer B,
+  infer C
+]
+  ? FnError<`Can only sub [number, number], but got ${ToString<Args>}`>
+  : Args extends [infer M extends number, infer N extends number]
+  ? SubNumbers<M, N>
+  : FnError<`Can only sub [number, number], but got ${ToString<Args>}`>;
+
 export type BUILTIN_Mul<Args extends readonly any[]> = Args extends [
   infer A,
   infer B,
@@ -32,6 +44,13 @@ export type BUILTIN_Mul<Args extends readonly any[]> = Args extends [
   ? Multiply<M, N>
   : FnError<`Can only multiply [number, number], but got ${ToString<Args>}`>;
 
+export type BUILTIN_Eq<Args extends readonly any[]> = Args extends
+  | readonly number[]
+  | readonly string[]
+  | 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,
diff --git a/src/lang/ts-lang/builtin/sbuiltin.ts b/src/lang/ts-lang/builtin/sbuiltin.ts
index 01f197e..f873666 100644
--- a/src/lang/ts-lang/builtin/sbuiltin.ts
+++ b/src/lang/ts-lang/builtin/sbuiltin.ts
@@ -6,7 +6,7 @@ export type SBUILTIN_Call<
   Node extends ASTNode,
   Frame extends StackFrame
 > = GetEvaluatedChildren<Node, Frame> extends [
-  infer Fn extends FnPrim,
+  infer Fn,
   ...infer Values extends readonly any[]
 ]
   ? CallFn<Fn, Values, Frame>
diff --git a/src/lang/ts-lang/core/common.ts b/src/lang/ts-lang/core/common.ts
index fa5cb7c..95a9ad3 100644
--- a/src/lang/ts-lang/core/common.ts
+++ b/src/lang/ts-lang/core/common.ts
@@ -51,16 +51,20 @@ export type ParserCtx = {
 };
 
 export type StackFrame<
-  Bindings extends Record<ASTNode["name"], any> = Record<ASTNode["name"], any>,
-  Parent extends StackFrame | null = any
+  Bindings extends Record<ASTNode["name"], any> = Record<ASTNode["name"], any>
 > = {
   bindings: Bindings;
-  parent: Parent;
 };
 
-export type EmptyStackFrame = StackFrame<{}, null>;
+export type EmptyStackFrame = StackFrame<{}>;
 
-export type WithPushedBindings<
+export type MergeStackFrames<
   OldFrame extends StackFrame,
-  Bindings extends StackFrame["bindings"]
-> = StackFrame<Bindings, OldFrame>;
+  NewFrame extends StackFrame
+> = StackFrame<{
+  [K in
+    | keyof OldFrame["bindings"]
+    | keyof NewFrame["bindings"]]: K extends keyof NewFrame["bindings"]
+    ? NewFrame["bindings"][K]
+    : OldFrame["bindings"][K];
+}>;
diff --git a/src/lang/ts-lang/core/eval.ts b/src/lang/ts-lang/core/eval.ts
index b2fecaa..511ada9 100644
--- a/src/lang/ts-lang/core/eval.ts
+++ b/src/lang/ts-lang/core/eval.ts
@@ -1,14 +1,22 @@
 import {
   BUILTIN_Add,
   BUILTIN_Arr,
+  BUILTIN_Eq,
   BUILTIN_IfElse,
   BUILTIN_Mul,
+  BUILTIN_Sub,
   BUILTIN_ToString,
   SBUILTIN_Call,
   SBUILTIN_Map,
 } from "../builtin";
-import { ToString } from "../util";
-import { ASTNode, EmptyStackFrame, NodeType, StackFrame } from "./common";
+import { NumberToArray, ToString } from "../util";
+import {
+  ASTNode,
+  EmptyStackFrame,
+  MergeStackFrames,
+  NodeType,
+  StackFrame,
+} from "./common";
 
 export type SENTINEL_NO_BUILTIN = "__NO_BUILTIN__";
 export type MapBuiltins<
@@ -25,8 +33,12 @@ export type MapBuiltins<
     ? BUILTIN_Arr<Args>
     : Node["name"] extends "add"
     ? BUILTIN_Add<Args>
+    : Node["name"] extends "sub"
+    ? BUILTIN_Sub<Args>
     : Node["name"] extends "mul"
     ? BUILTIN_Mul<Args>
+    : Node["name"] extends "eq"
+    ? BUILTIN_Eq<Args>
     : Node["name"] extends "?"
     ? BUILTIN_IfElse<Args>
     : SENTINEL_NO_BUILTIN
@@ -38,25 +50,82 @@ export type FindInStack<
   Frame extends StackFrame,
   NameToFind
 > = NameToFind extends keyof Frame["bindings"]
-  ? Frame["bindings"][NameToFind]
-  : Frame["parent"] extends null
-  ? EvalError<`Can't find name "${ToString<NameToFind>}" on the stack`>
-  : FindInStack<Frame["parent"], NameToFind>;
+  ? Frame["bindings"][NameToFind] extends never
+    ? EvalError<`Can't find name "${ToString<NameToFind>}" on the stack`>
+    : Frame["bindings"][NameToFind]
+  : EvalError<`Can't find name "${ToString<NameToFind>}" on the stack`>;
 
 export type FnPrim<
   Args extends readonly ASTNode[] = readonly ASTNode[],
   Fn extends ASTNode = ASTNode
 > = { args: Args; fn: Fn };
 
-export type HandleFn<Node extends ASTNode> = Node["children"] extends [
+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
+> = Node["children"] extends [
+  infer Name extends ASTNode,
+  infer Value extends ASTNode
+]
+  ? _Evaluate<Value, Frame> 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
+      : U
+    : never
+  : never;
+
+export type HandleFn<
+  Node extends ASTNode,
+  Frame extends StackFrame
+> = Node["children"] extends [
   ...infer Args extends ASTNode[],
   infer Fn extends ASTNode
 ]
   ? FnPrim<Args, Fn>
-  : // error?
-    never;
+  : EvalError<"Invalid args for function call">;
 
-// any[] was propertykey
 export type MapZip<
   Args extends readonly ASTNode[],
   Values extends readonly any[]
@@ -70,10 +139,22 @@ export type MapZip<
 };
 
 export type CallFn<
-  Fn extends FnPrim,
+  Fn,
   Values extends readonly any[],
   Frame extends StackFrame
-> = _Evaluate<Fn["fn"], StackFrame<MapZip<Fn["args"], Values>, Frame>>;
+> = Fn extends NamedFnPrim<
+  infer Args,
+  infer FnBody,
+  infer Name,
+  infer CapturedFrame
+>
+  ? _Evaluate<
+      FnBody,
+      MergeStackFrames<CapturedFrame, StackFrame<MapZip<Args, Values>>>
+    >
+  : Fn extends FnPrim<infer Args, infer FnBody>
+  ? _Evaluate<FnBody, MergeStackFrames<Frame, StackFrame<MapZip<Args, Values>>>>
+  : Fn;
 
 export type _Evaluate<
   Node extends ASTNode,
@@ -81,9 +162,11 @@ export type _Evaluate<
 > = Node["type"] extends NodeType.INT
   ? Node["value"]
   : Node["type"] extends NodeType.EXT
-  ? // special builtin
-    Node["name"] extends "fn"
-    ? HandleFn<Node>
+  ? // 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"]>
diff --git a/src/lang/ts-lang/util/number.ts b/src/lang/ts-lang/util/number.ts
index 6e4e360..2fa6d85 100644
--- a/src/lang/ts-lang/util/number.ts
+++ b/src/lang/ts-lang/util/number.ts
@@ -20,6 +20,18 @@ export type AddNumbers<Numbers extends readonly number[]> =
     ? T["length"]
     : never;
 
+export type SubNumbersInternal<
+  MS extends readonly unknown[],
+  NS extends readonly unknown[]
+> = MS extends readonly [...NS, ...infer Tail] ? Tail : never;
+
+export type SubNumbers<M extends number, N extends number> = SubNumbersInternal<
+  NumberToArray<M>,
+  NumberToArray<N>
+> extends infer T extends readonly any[]
+  ? T["length"]
+  : never;
+
 export type MultiplyInner<
   N extends number,
   MS extends readonly any[],
diff --git a/src/lang/ts-lang/util/utils.ts b/src/lang/ts-lang/util/utils.ts
index ac36ca1..d6d46f7 100644
--- a/src/lang/ts-lang/util/utils.ts
+++ b/src/lang/ts-lang/util/utils.ts
@@ -6,3 +6,17 @@ export type UnarrayIfOnlyHead<T extends readonly any[]> = T extends [
   : T extends [infer Head]
   ? Head
   : T;
+
+type ARR_EQUAL_SENTINEL = { __arrEq: true };
+export type ArrayEqual<
+  T extends readonly any[],
+  Last = ARR_EQUAL_SENTINEL
+> = T extends [infer Head, ...infer Tail]
+  ? Last extends ARR_EQUAL_SENTINEL
+    ? ArrayEqual<Tail, Head>
+    : Head extends Last
+    ? Last extends Head
+      ? ArrayEqual<Tail, Head>
+      : false
+    : false
+  : true;
diff --git a/test/test.ts b/test/test.ts
index 672fb4e..5e884ab 100644
--- a/test/test.ts
+++ b/test/test.ts
@@ -1,4 +1,4 @@
-import { createFn } from "../src";
+import { _Evaluate, createFn } from "../src";
 
 const KS_boolToBin = "fn(b, ?(b, 1, 0))";
 
@@ -6,5 +6,10 @@ const boolArrToBinaryArr = createFn<[boolean[]]>()(
   `fn(boolArr, map(boolArr, ${KS_boolToBin}))`
 );
 
-const result = boolArrToBinaryArr([true, false, true]);
-console.log(result);
+const factorial = createFn<[number]>()(
+  `bind(fac,fn(n,?(eq(n, 1),n,mul(n,call(fac,sub(n,1))))))`
+);
+
+const res = factorial(6);
+
+// console.log(factorial(2));