diff options
| -rw-r--r-- | src/lang/builtin/index.ts | 5 | ||||
| -rw-r--r-- | src/lang/core/eval.ts | 128 | ||||
| -rw-r--r-- | src/lang/core/parser.ts | 59 |
3 files changed, 118 insertions, 74 deletions
diff --git a/src/lang/builtin/index.ts b/src/lang/builtin/index.ts index 373f54a..7728455 100644 --- a/src/lang/builtin/index.ts +++ b/src/lang/builtin/index.ts @@ -1,3 +1,4 @@ +import { FnPrim } from "../core/eval"; import { AddNumbers, AddStrings, @@ -32,3 +33,7 @@ export type BUILTIN_Mul<Args extends readonly any[]> = Args extends [ : Args extends [infer M extends number, infer N extends number] ? Multiply<M, N> : FnError<`Can only multiply [number, number], but got ${ToString<Args>}`>; + +export type BUILTIN_Call<Args extends readonly any[]> = Args extends [infer Fn extends FnPrim, ...infer Valuex extends readonly any[]] = + +export type BUILTIN_Map<Args extends readonly any[]>
\ No newline at end of file diff --git a/src/lang/core/eval.ts b/src/lang/core/eval.ts index 6a25a6c..61eb63a 100644 --- a/src/lang/core/eval.ts +++ b/src/lang/core/eval.ts @@ -4,39 +4,125 @@ import { BUILTIN_Mul, BUILTIN_ToString, } from "../builtin"; +import { ToString } from "../util"; import { ASTNode, NodeType } from "./common"; import { Lex } from "./lexer"; import { Parse } from "./parser"; +export type GetEvaluatedChildren< + Node extends ASTNode, + Frame extends StackFrame +> = Node["children"] extends infer Children extends readonly ASTNode[] + ? { + [Idx in keyof Children]: Children[Idx] extends ASTNode + ? Evaluate<Children[Idx], Frame> + : never; + } + : never; + export type SENTINEL_NO_BUILTIN = "__NO_BUILTIN__"; -export type MapBuiltins<Node extends ASTNode> = - Node["children"] extends infer Children extends readonly ASTNode[] - ? { - [Idx in keyof Children]: Children[Idx] extends ASTNode - ? Evaluate<Children[Idx]> - : never; - } extends infer Args extends readonly any[] - ? Node["name"] extends "tostring" - ? BUILTIN_ToString<Args> - : Node["name"] extends "arr" - ? BUILTIN_Arr<Args> - : Node["name"] extends "add" - ? BUILTIN_Add<Args> - : Node["name"] extends "mul" - ? BUILTIN_Mul<Args> - : SENTINEL_NO_BUILTIN - : never - : never; +export type MapBuiltins< + Node extends ASTNode, + Frame extends StackFrame +> = GetEvaluatedChildren<Node, Frame> extends infer Args extends readonly any[] + ? Node["name"] extends "tostring" + ? BUILTIN_ToString<Args> + : Node["name"] extends "arr" + ? BUILTIN_Arr<Args> + : Node["name"] extends "add" + ? BUILTIN_Add<Args> + : Node["name"] extends "mul" + ? BUILTIN_Mul<Args> + : SENTINEL_NO_BUILTIN + : never; export type EvalError<T extends string> = `Eval error: ${T}`; -export type Evaluate<Node extends ASTNode> = Node["type"] extends NodeType.INT +export type StackFrame< + Bindings extends Record<ASTNode["name"], any> = Record<ASTNode["name"], any>, + Parent extends StackFrame | null = any +> = { + bindings: Bindings; + parent: Parent; +}; + +export type EmptyStackFrame = StackFrame<{}, null>; + +export type WithPushedBindings< + OldFrame extends StackFrame, + Bindings extends StackFrame["bindings"] +> = StackFrame<Bindings, OldFrame>; + +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<NameToFind>}" on the stack`> + : FindInStack<Frame["parent"], NameToFind>; + +export type MapOnStack< + Node extends ASTNode, + Frame extends StackFrame +> = FindInStack<Frame, Node["name"]>; + +export type FnPrim< + Args extends readonly ASTNode[] = readonly ASTNode[], + Fn extends ASTNode = any +> = { args: Args; fn: Fn }; + +// Can support multiple args, just need to make the last arg be the fn +export type HandleFn<Node extends ASTNode> = Node["children"] extends [ + infer Arg extends ASTNode, + infer Fn extends ASTNode +] + ? FnPrim<[Arg], Fn> + : never; + +type MapZip<T extends readonly ASTNode[], U extends readonly PropertyKey[]> = { + [Idx in Exclude< + keyof T, + keyof any[] + > as T[Idx] extends infer Node extends ASTNode + ? Node["name"] + : never]: Idx extends keyof U ? U[Idx] : never; +}; + +export type CallFn< + Fn extends FnPrim, + Values extends readonly any[], + Frame extends StackFrame +> = Evaluate<Fn["fn"], StackFrame<MapZip<Fn["args"], Values>, Frame>>; + +export type Evaluate< + Node extends ASTNode, + Frame extends StackFrame = EmptyStackFrame +> = Node["type"] extends NodeType.INT ? Node["value"] : Node["type"] extends NodeType.EXT - ? MapBuiltins<Node> + ? // special builtin + Node["name"] extends "call" + ? GetEvaluatedChildren<Node, Frame> extends [ + infer Fn extends FnPrim, + ...infer Values extends readonly any[] + ] + ? CallFn<Fn, Values, Frame> + : EvalError<`Invalid params for function call: ${ToString< + GetEvaluatedChildren<Node, Frame> + >}`> + : // special builtin + Node["name"] extends "fn" + ? HandleFn<Node> + : MapBuiltins<Node, Frame> extends infer BI + ? BI extends SENTINEL_NO_BUILTIN + ? MapOnStack<Node, Frame> + : BI + : never : EvalError<`Unhandled node type ${Node["type"]}`>; -const input = `` as const; +// const input = `map(arr(1,2,3), fn(n, add(n, 1)))` as const; +const input = `call(fn(a, add(a, 5)), 12)` as const; const lex_result = null as unknown as Lex<typeof input>; const parse_result = null as unknown as Parse<typeof lex_result>; const eval_result = null as unknown as Evaluate<typeof parse_result>; diff --git a/src/lang/core/parser.ts b/src/lang/core/parser.ts index 79218e9..2b481fd 100644 --- a/src/lang/core/parser.ts +++ b/src/lang/core/parser.ts @@ -8,51 +8,6 @@ import { } from "./common"; import { Lex } from "./lexer"; -/* -start -if no 'lastName' -then: - expect nextToken to be a name - lastName = nextToken - goto start - -else: - if nextToken is name - then: - // we already have a lastName - mutate last element of stack to push lastName as child - lastName = nextToken - goto start - - else: - //nextToken is openParen or close paren - if nextToken is closeParen - then: - set last element of stack as child of prev element on stack - pop stack - // [stack[last - 1].children.push(stack.pop) - goto start - else if nextToken is openParen: - push lastName onto stack - goto start - - -finally: - // only one element remains on the stack - return stack[0] - - - CALL ( param, CALL2 ( param2 ) ) - - param2 ret call2 param ret call - - | call - |-- param - |-- | call2 - |-- param2 - - */ - export type Error<T extends string> = ASTNode< NodeType.PARSER_ERROR, "Error", @@ -131,9 +86,9 @@ export type _Parse<Ctx extends ParserCtx> = Ctx["remainingTokens"] extends [ ] ? Ctx["lastToken"] extends Token ? Head["type"] extends TokenType.NAME - ? // we already have a lastName - // mutate last element of stack to push lastName as child - // lastName = nextToken + ? // we already have a lastToken + // mutate last element of stack to push lastToken as child + // lastToken = nextToken // goto start _Parse<{ lastToken: Head; @@ -145,7 +100,7 @@ export type _Parse<Ctx extends ParserCtx> = Ctx["remainingTokens"] extends [ }> : //nextToken is openParen or close paren Head["type"] extends TokenType.CLOSE_PAREN - ? // handle lastName + ? // handle lastToken // set last element of stack as child of prev element on stack // pop stack // [stack[last - 1].children.push(stack.pop) @@ -167,7 +122,7 @@ export type _Parse<Ctx extends ParserCtx> = Ctx["remainingTokens"] extends [ >; }> : Head["type"] extends TokenType.OPEN_PAREN - ? // push lastName onto stack + ? // push lastToken onto stack // goto start _Parse<{ lastToken: null; @@ -177,7 +132,7 @@ export type _Parse<Ctx extends ParserCtx> = Ctx["remainingTokens"] extends [ : Ctx & Error<`Was not expecting ${Head["type"]}`> : // expect nextToken to be a name or close paren Head["type"] extends TokenType.NAME - ? // lastName = nextToken + ? // lastToken = nextToken // goto start _Parse<{ lastToken: Head; @@ -216,5 +171,3 @@ export type Parse<Raw extends readonly Token[]> = _Parse<{ remainingTokens: Raw; stack: [ASTNode<NodeType.EXT, "arr", null, []>]; }>; - -const test_result = null as unknown as Parse<Lex<`test(135)`>>; |