From d8a969e231135978c4dd1fa67559101f506ad6f3 Mon Sep 17 00:00:00 2001 From: Kai Stevenson Date: Wed, 5 Nov 2025 01:20:07 -0800 Subject: recursion works for types with depth limit 5 --- src/lang/js-lang/builtin/builtin.ts | 45 ++++++++++++++ src/lang/ts-lang/builtin/builtin.ts | 19 ++++++ src/lang/ts-lang/builtin/sbuiltin.ts | 2 +- src/lang/ts-lang/core/common.ts | 18 +++--- src/lang/ts-lang/core/eval.ts | 113 ++++++++++++++++++++++++++++++----- src/lang/ts-lang/util/number.ts | 12 ++++ src/lang/ts-lang/util/utils.ts | 14 +++++ test/test.ts | 11 +++- 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 = { 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 = ? AddNumbers : FnError<`Cannot add operands ${ToString}`>; +export type BUILTIN_Sub = Args extends [ + infer A, + infer B, + infer C +] + ? FnError<`Can only sub [number, number], but got ${ToString}`> + : Args extends [infer M extends number, infer N extends number] + ? SubNumbers + : FnError<`Can only sub [number, number], but got ${ToString}`>; + export type BUILTIN_Mul = Args extends [ infer A, infer B, @@ -32,6 +44,13 @@ export type BUILTIN_Mul = Args extends [ ? Multiply : FnError<`Can only multiply [number, number], but got ${ToString}`>; +export type BUILTIN_Eq = Args extends + | readonly number[] + | readonly string[] + | readonly boolean[] + ? ArrayEqual + : FnError<`Can only check equality of numbers or string or boolean, but got ${ToString}`>; + export type BUILTIN_IfElse = 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 extends [ - infer Fn extends FnPrim, + infer Fn, ...infer Values extends readonly any[] ] ? CallFn 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 = Record, - Parent extends StackFrame | null = any + Bindings extends Record = Record > = { 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; + 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 : Node["name"] extends "add" ? BUILTIN_Add + : Node["name"] extends "sub" + ? BUILTIN_Sub : Node["name"] extends "mul" ? BUILTIN_Mul + : Node["name"] extends "eq" + ? BUILTIN_Eq : Node["name"] extends "?" ? BUILTIN_IfElse : 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}" on the stack`> - : FindInStack; + ? Frame["bindings"][NameToFind] extends never + ? EvalError<`Can't find name "${ToString}" on the stack`> + : Frame["bindings"][NameToFind] + : EvalError<`Can't find name "${ToString}" on the stack`>; export type FnPrim< Args extends readonly ASTNode[] = readonly ASTNode[], Fn extends ASTNode = ASTNode > = { args: Args; fn: Fn }; -export type HandleFn = 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, + 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 extends infer U + ? U extends FnPrim + ? NamedFnPrim< + U["args"], + U["fn"], + Name["name"], + Frame + > extends infer NamedFn + ? NamedFn extends NamedFnPrim + ? // RECURSION DEPTH LIMIT = 5 + BuildDeepBinding> + : 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 - : // 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, Frame>>; +> = Fn extends NamedFnPrim< + infer Args, + infer FnBody, + infer Name, + infer CapturedFrame +> + ? _Evaluate< + FnBody, + MergeStackFrames>> + > + : Fn extends FnPrim + ? _Evaluate>>> + : 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 + ? // special builtins + Node["name"] extends "bind" + ? HandleBind + : Node["name"] extends "fn" + ? HandleFn : MapBuiltins extends infer BI ? BI extends SENTINEL_NO_BUILTIN ? FindInStack 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 = ? 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 = SubNumbersInternal< + NumberToArray, + NumberToArray +> 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 [ : 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 + : Head extends Last + ? Last extends Head + ? ArrayEqual + : 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)); -- cgit v1.2.3-70-g09d2