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/js-lang/builtin/builtin.ts | 17 +--- src/lang/js-lang/builtin/sbuiltin.ts | 19 ++++- src/lang/js-lang/core/eval.ts | 45 ++++++++--- src/lang/ks-lang/index.ts | 24 ++++-- 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 ++++++++++++++++------------------- 8 files changed, 189 insertions(+), 140 deletions(-) (limited to 'src') diff --git a/src/lang/js-lang/builtin/builtin.ts b/src/lang/js-lang/builtin/builtin.ts index ed279f6..bc40794 100644 --- a/src/lang/js-lang/builtin/builtin.ts +++ b/src/lang/js-lang/builtin/builtin.ts @@ -61,10 +61,12 @@ export const V_BUILTIN_Eq: BUILTIN = (args) => { } if (last === firstLast) { + last = arg; continue; } if (arg === last) { + last = arg; continue; } @@ -74,20 +76,6 @@ export const V_BUILTIN_Eq: BUILTIN = (args) => { return true; }; -export const V_BUILTIN_IfElse: BUILTIN = (args) => { - if (args.length !== 3) { - throw new Error(`Invalid args for "if": ${JSON.stringify(args)}`); - } - - const [cond, trueVal, falseVal] = args; - - if (typeof cond !== "boolean") { - throw new Error(`Condition value ${JSON.stringify(cond)} is not a boolean`); - } - - return cond ? trueVal : falseVal; -}; - export const nameToBUILTIN: Record = { arr: V_BUILTIN_Arr, tostring: V_BUILTIN_ToString, @@ -95,5 +83,4 @@ export const nameToBUILTIN: Record = { sub: V_BUILTIN_Sub, mul: V_BUILTIN_Mul, eq: V_BUILTIN_Eq, - "?": V_BUILTIN_IfElse, }; diff --git a/src/lang/js-lang/builtin/sbuiltin.ts b/src/lang/js-lang/builtin/sbuiltin.ts index e5bc6ab..663c2f9 100644 --- a/src/lang/js-lang/builtin/sbuiltin.ts +++ b/src/lang/js-lang/builtin/sbuiltin.ts @@ -1,4 +1,4 @@ -import { callFn, getEvaluatedChildren } from "../core/eval"; +import { _evaluate, callFn, getEvaluatedChildren } from "../core/eval"; import { ASTNode, FnPrim, StackFrame } from "../../ts-lang"; type SBUILTIN = (node: ASTNode, frame: StackFrame) => any; @@ -40,7 +40,24 @@ export const V_SBUILTIN_Map: SBUILTIN = (node, frame) => { return values.map((v, i) => callFn(fn, [v, i], frame)); }; +export const V_SBUILTIN_IfElse: SBUILTIN = (node, frame) => { + const children = node.children; + + if (children.length !== 3) { + throw new Error(`Invalid args for "if": ${JSON.stringify(children)}`); + } + + const cond = _evaluate(children[0], frame); + + if (typeof cond !== "boolean") { + throw new Error(`Condition value ${JSON.stringify(cond)} is not a boolean`); + } + + return cond ? _evaluate(children[1], frame) : _evaluate(children[2], frame); +}; + export const nameToSBUILTIN: Record = { call: V_SBUILTIN_Call, map: V_SBUILTIN_Map, + "?": V_SBUILTIN_IfElse, }; diff --git a/src/lang/js-lang/core/eval.ts b/src/lang/js-lang/core/eval.ts index 60a2059..1a9e292 100644 --- a/src/lang/js-lang/core/eval.ts +++ b/src/lang/js-lang/core/eval.ts @@ -6,6 +6,7 @@ import { NodeType, FnPrim, SENTINEL_NO_BUILTIN, + NamedFnPrim, } from "../../ts-lang"; import { nameToBUILTIN, nameToSBUILTIN, V_SBUILTIN_Map } from "../builtin"; @@ -27,11 +28,24 @@ const findInStack = (frame: StackFrame, nameToFind: string) => { return frame.bindings[nameToFind]; } - if (!frame.parent) { - throw new Error(`Can't find name ${nameToFind} on the stack`); + throw new Error(`Can't find name ${nameToFind} on the stack`); +}; + +const handleBind = (node: ASTNode, frame: StackFrame) => { + const inner = _evaluate(node.children[1], frame); + + if (inner.fn) { + const named: NamedFnPrim = { + args: inner.args, + fn: inner.fn, + name: node.children[0].name, + frame, + }; + + return named; } - return findInStack(frame.parent, nameToFind); + return inner; }; const handleFn = (node: ASTNode): FnPrim => { @@ -46,13 +60,22 @@ const handleFn = (node: ASTNode): FnPrim => { const mapZip = (args: ASTNode[], values: any[]) => Object.fromEntries(args.map(({ name }, i) => [name, values[i]])); -export const callFn = (fn: FnPrim, values: any[], frame: StackFrame) => - _evaluate(fn.fn, { - bindings: mapZip(fn.args as ASTNode[], values), - parent: frame, +export const callFn = (fn: FnPrim, values: any[], frame: StackFrame) => { + if ((fn as NamedFnPrim).frame) { + return _evaluate(fn.fn, { + bindings: { + ...mapZip(fn.args as ASTNode[], values), + ...frame.bindings, + ...(fn as NamedFnPrim).frame.bindings, + }, + }); + } + return _evaluate(fn.fn, { + bindings: { ...mapZip(fn.args as ASTNode[], values), ...frame.bindings }, }); +}; -export const _evaluate = (node: ASTNode, frame: StackFrame) => { +export const _evaluate = (node: ASTNode, frame: StackFrame): any => { if (node.type === NodeType.INT) { return node.value; } @@ -62,6 +85,10 @@ export const _evaluate = (node: ASTNode, frame: StackFrame) => { return handleFn(node); } + if (node.name === "bind") { + return handleBind(node, frame); + } + const builtinResult = mapBuiltins(node, frame); if (builtinResult !== V_SENTINEL_NO_BUILTIN) { return builtinResult; @@ -76,7 +103,7 @@ export const _evaluate = (node: ASTNode, frame: StackFrame) => { export const getEvaluatedChildren = (node: ASTNode, frame: StackFrame) => node.children.map((child) => _evaluate(child, frame)); -export const emptyStackFrame: EmptyStackFrame = { bindings: {}, parent: null }; +export const emptyStackFrame: EmptyStackFrame = { bindings: {} }; export const evaluate = ( node: Node diff --git a/src/lang/ks-lang/index.ts b/src/lang/ks-lang/index.ts index e5a78b9..772c9c9 100644 --- a/src/lang/ks-lang/index.ts +++ b/src/lang/ks-lang/index.ts @@ -23,13 +23,23 @@ export const createFn = () => ( program: Program - ): Evaluate>> extends [infer ProgramFn extends FnPrim] - ? TransformArgs extends ArgsConstraint - ? ( - ...args: Args - ) => CallFn - : EvalError<`Program's args do not extend args constraint`> - : EvalError<"Cannot create a function from a program that does not eval to a function"> => { + ): Evaluate>> extends infer E + ? E extends [infer ProgramFn extends FnPrim] + ? TransformArgs extends ArgsConstraint + ? ( + ...args: Args + ) => CallFn + : EvalError<`Program's args do not extend args constraint`> + : E extends readonly [ + readonly [infer Prim extends FnPrim, infer StackFrame, infer Name] + ] + ? TransformArgs extends ArgsConstraint + ? ( + ...args: Args + ) => CallFn + : EvalError<`Program's args do not extend args constraint`> + : EvalError<"Cannot create a function from a program that does not eval to a function"> + : never => { const [programFn] = evaluate(parse(lex(program))) as Array; if (!programFn.fn) { throw new Error( 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