From 490b9c94fba16f484be3bb58b8a4a4880b9396bc Mon Sep 17 00:00:00 2001 From: Kai Stevenson Date: Thu, 6 Nov 2025 00:18:26 -0800 Subject: implement recursion properly with closures --- src/lang/ts-lang/builtin/builtin.ts | 15 ---- src/lang/ts-lang/builtin/sbuiltin.ts | 54 ++++++++++--- src/lang/ts-lang/core/common.ts | 6 +- src/lang/ts-lang/core/eval.ts | 149 ++++++++++++++++------------------- 4 files changed, 116 insertions(+), 108 deletions(-) (limited to 'src/lang/ts-lang') 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 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, - infer C, - infer D -] - ? FnError<`Invalid args for "if": ${ToString}`> - : Args extends [infer Cond, infer TrueVal, infer FalseVal] - ? Cond extends true - ? TrueVal - : Cond extends false - ? FalseVal - : FnError<`Condition value ${ToString} is not a boolean`> - : FnError<`Invalid args for "if": ${ToString}`>; 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 extends [ + Frame extends StackFrame, + Callstack extends readonly string[] +> = GetEvaluatedChildren extends [ infer Fn, ...infer Values extends readonly any[] ] - ? CallFn + ? CallFn : EvalError<`Invalid params for function call: ${ToString< - GetEvaluatedChildren + GetEvaluatedChildren >}`>; export type SBUILTIN_Map< Node extends ASTNode, - Frame extends StackFrame -> = GetEvaluatedChildren extends [ + Frame extends StackFrame, + Callstack extends readonly string[] +> = GetEvaluatedChildren extends [ infer Arr extends readonly any[], infer Fn extends FnPrim ] - ? { [Idx in keyof Arr]: CallFn], Frame> } + ? { + [Idx in keyof Arr]: CallFn< + Fn, + [Arr[Idx], ExtractNumber], + Frame, + Callstack + >; + } : EvalError<`Invalid params for map: ${ToString< - GetEvaluatedChildren + GetEvaluatedChildren >}`>; + +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 extends [ + infer Cond extends ASTNode, + infer TrueVal extends ASTNode, + infer FalseVal extends ASTNode + ] + ? _Evaluate extends true + ? _Evaluate + : _Evaluate extends false + ? _Evaluate + : FnError<`Condition value ${ToString} is not a boolean`> + : FnError<`Invalid args for "if": ${ToString}`> + : 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 = Record -> = { +> { 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 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 + ? SBUILTIN_Call : Node["name"] extends "map" - ? SBUILTIN_Map + ? SBUILTIN_Map + : Node["name"] extends "?" + ? SBUILTIN_IfElse : Node["name"] extends "tostring" ? BUILTIN_ToString : Node["name"] extends "arr" @@ -39,8 +48,6 @@ export type MapBuiltins< ? BUILTIN_Mul : Node["name"] extends "eq" ? BUILTIN_Eq - : Node["name"] extends "?" - ? BUILTIN_IfElse : 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, - 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 extends infer U + ? _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 + ? 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>> + Prim["fn"], + MergeStackFrames< + CapturedFrame, + MergeStackFrames< + StackFrame<{ [K in Name]: Fn }>, + StackFrame> + > + >, + [...Callstack, "call"] > : Fn extends FnPrim - ? _Evaluate>>> + ? _Evaluate< + FnBody, + MergeStackFrames>>, + [...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["name"] extends "fn" - ? HandleFn - : MapBuiltins extends infer BI - ? BI extends SENTINEL_NO_BUILTIN - ? FindInStack - : 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}`> + : Node["type"] extends NodeType.INT + ? Node["value"] + : Node["type"] extends NodeType.EXT + ? // special builtins + Node["name"] extends "bind" + ? HandleBind + : Node["name"] extends "fn" + ? HandleFn + : MapBuiltins extends infer BI + ? BI extends SENTINEL_NO_BUILTIN + ? FindInStack + : 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 + ? _Evaluate : never; } : never; -export type Evaluate = _Evaluate; +export type Evaluate = _Evaluate< + Node, + EmptyStackFrame, + [] +>; -- cgit v1.2.3-70-g09d2