1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
import {
BUILTIN_Add,
BUILTIN_Arr,
BUILTIN_Eq,
BUILTIN_Mul,
BUILTIN_Sub,
BUILTIN_ToString,
SBUILTIN_Call,
SBUILTIN_IfElse,
SBUILTIN_Map,
} from "../builtin";
import { ToString } from "../util";
import {
ASTNode,
EmptyStackFrame,
MergeStackFrames,
NodeType,
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,
Callstack extends readonly string[]
> = GetEvaluatedChildren<
Node,
Frame,
Callstack
> extends infer Args extends readonly any[]
? Node["name"] extends "call"
? SBUILTIN_Call<Node, Frame, Callstack>
: Node["name"] extends "map"
? SBUILTIN_Map<Node, Frame, Callstack>
: Node["name"] extends "?"
? SBUILTIN_IfElse<Node, Frame, Callstack>
: Node["name"] extends "tostring"
? BUILTIN_ToString<Args>
: Node["name"] extends "arr"
? 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>
: SENTINEL_NO_BUILTIN
: never;
export type EvalError<T extends string> = `Eval error: ${T}`;
export type FindInStack<
Frame extends StackFrame,
NameToFind
> = NameToFind extends keyof Frame["bindings"]
? 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 HandleBind<
Node extends ASTNode,
Frame extends StackFrame,
Callstack extends readonly string[]
> = Node["children"] extends [
infer Name extends ASTNode,
infer Value extends ASTNode
]
? _Evaluate<Value, Frame, [...Callstack, "bind"]> extends infer U
? U extends FnPrim
? readonly [U, Frame, Name["name"]]
: 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>
: EvalError<"Invalid args for function call">;
export type MapZip<
Args extends readonly ASTNode[],
Values extends readonly any[]
> = {
[Idx in Exclude<
keyof Args,
keyof any[]
> as Args[Idx] extends infer Node extends ASTNode
? Node["name"]
: never]: Idx extends keyof Values ? Values[Idx] : never;
};
export type CallFn<
Fn,
Values extends readonly any[],
Frame extends StackFrame,
Callstack extends readonly string[]
> = Fn extends readonly [
infer Prim extends FnPrim,
infer CapturedFrame extends StackFrame,
infer Name extends ASTNode["name"]
]
? _Evaluate<
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>>>,
[...Callstack, "call"]
>
: Fn;
export type _Evaluate<
Node extends ASTNode,
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,
Callstack extends readonly string[]
> = Node["children"] extends infer Children extends readonly ASTNode[]
? {
[Idx in keyof Children]: Children[Idx] extends ASTNode
? _Evaluate<Children[Idx], Frame, Callstack>
: never;
}
: never;
export type Evaluate<Node extends ASTNode> = _Evaluate<
Node,
EmptyStackFrame,
[]
>;
|
