summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lang/js-lang/builtin/builtin.ts17
-rw-r--r--src/lang/js-lang/builtin/sbuiltin.ts19
-rw-r--r--src/lang/js-lang/core/eval.ts45
-rw-r--r--src/lang/ks-lang/index.ts24
-rw-r--r--src/lang/ts-lang/builtin/builtin.ts15
-rw-r--r--src/lang/ts-lang/builtin/sbuiltin.ts54
-rw-r--r--src/lang/ts-lang/core/common.ts6
-rw-r--r--src/lang/ts-lang/core/eval.ts149
-rw-r--r--test/test.ts8
9 files changed, 195 insertions, 142 deletions
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<string, BUILTIN> = {
arr: V_BUILTIN_Arr,
tostring: V_BUILTIN_ToString,
@@ -95,5 +83,4 @@ export const nameToBUILTIN: Record<string, BUILTIN> = {
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<string, SBUILTIN> = {
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<any, any, any, any> = {
+ 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<any, any, any, any>).frame) {
+ return _evaluate(fn.fn, {
+ bindings: {
+ ...mapZip(fn.args as ASTNode[], values),
+ ...frame.bindings,
+ ...(fn as NamedFnPrim<any, any, any, any>).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 = <const Node extends ASTNode>(
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 =
<ArgsConstraint extends any[]>() =>
<Program extends string>(
program: Program
- ): Evaluate<Parse<Lex<Program>>> extends [infer ProgramFn extends FnPrim]
- ? TransformArgs<ProgramFn["args"]> extends ArgsConstraint
- ? <const Args extends ArgsConstraint>(
- ...args: Args
- ) => CallFn<ProgramFn, Args, EmptyStackFrame>
- : 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<Parse<Lex<Program>>> extends infer E
+ ? E extends [infer ProgramFn extends FnPrim]
+ ? TransformArgs<ProgramFn["args"]> extends ArgsConstraint
+ ? <const Args extends ArgsConstraint>(
+ ...args: Args
+ ) => CallFn<ProgramFn, Args, EmptyStackFrame, []>
+ : EvalError<`Program's args do not extend args constraint`>
+ : E extends readonly [
+ readonly [infer Prim extends FnPrim, infer StackFrame, infer Name]
+ ]
+ ? TransformArgs<Prim["args"]> extends ArgsConstraint
+ ? <const Args extends ArgsConstraint>(
+ ...args: Args
+ ) => CallFn<E[0], Args, EmptyStackFrame, []>
+ : 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<FnPrim>;
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 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,
+ []
+>;
diff --git a/test/test.ts b/test/test.ts
index 5e884ab..4b281b1 100644
--- a/test/test.ts
+++ b/test/test.ts
@@ -1,4 +1,4 @@
-import { _Evaluate, createFn } from "../src";
+import { _Evaluate, createFn, evaluate, lex, parse } from "../src";
const KS_boolToBin = "fn(b, ?(b, 1, 0))";
@@ -11,5 +11,9 @@ const factorial = createFn<[number]>()(
);
const res = factorial(6);
+console.log(res);
-// console.log(factorial(2));
+const closureTest = createFn<[number]>()(`fn(n, call(fn(m, add(m,n)), n))`);
+
+const res2 = closureTest(5);
+console.log(res2);
generated by cgit v1.2.3-70-g09d2 (git 2.51.2) at 2025-11-08 08:55:26 +0000