解释器模式举例-TypeScript 类型体操天花板，用类型运算写一个 Lisp 解释器
解释器模式举例-TypeScript 类型体操天花板，用类型运算写一个 Lisp 解释器
把 的泛型当做函数声明和调用，可以类比 的函数声明：
type Func = A, B
// ↑ ↑ ↑ ↑ ↑ ↑ ↑
// 函数名 参数名 参数类型 参数名 参数类型 默认值 函数体
type Test = Func // => [10, 'world']
function Func(A: number, B: string = 'hello') { return [A, B] }
const Test = Func(10, 'world') // => [10, 'world']没有高阶函数不影响表达能力
把 类型当成一门纯函数式编程语言其实不算准确，比如 类型就缺少一个标志性的能力「First-Class-」，在表现上就是没有高阶函数，但是这并不影响他的表达能力。具体的不展开讲了，可以看一下面这个回答，如果我们把一个环境（闭包）当成参数传递给函数解释器模式举例，那意味着并不需要高阶函数一样能实现闭包的效果。
(, , {\color{red}{}}) \ Return + {\color{red}{'}}
模式匹配
我们都知道 后面可以接一个 infer 用来提取变量，一般我们会把跟 的解构拿来做类比，事实上这个能力叫做模式匹配，他会先做我们上面说的集合的运算，之后结果能匹配才会将里面的结构拆解出来。我们在这里介绍几个常见的技巧：
用于拆出来数组和字符串第一个元素的匹配，常用语递归一个数组里面的每一个元素：
// 递归处理数组常用的匹配
type Test0 = [0, 1, 2] extends [infer Head, ...infer Tail]
? { head: Head, tail: Tail }
: never;
// 递归处理字符串常用的匹配
type Test1 = `abcdefg` extends `${infer Head}${infer Tail}`
? { head: Head, tail: Tail }
: never;通过构造一个新结构一次性匹配多个变量：
type Func = A, B extends 1, 2
? 'match 1 2'
: 'not match';通过构造一个带类型的新结构来避免 infer 变量的类型丢失：
type OnlyNumber = N;
type Tmp = { a: A };
type Test0 = { a: 10 } extends Tmp // infer A 只能是 number 类型
? OnlyNumber // 不报错
: never;递归与尾递归
我在上面的小节里面讲了一些基本的语法和技巧，但是问题来了。循环去哪儿了？这里要提出一个「反常识」的概念了：
递归和循环等价！所以在纯函数式编程语言里面往往用递归代替循环。
并且可以得到以下推论：
普通递归
不做赘述解释器模式举例，用下面两个例子为例为例演示用 类型实现递归运算：
// 遍历数组
type ArrayStuct = [Head, ...Tail];
type Join
= Arr extends [] ? ''
: Arr extends ArrayStuct ? Head
: Arr extends ArrayStuct ? `${Head}${Sp}${Join}`
: never;
type Test = Join
// => type Test = "foo,bar,hello" // 遍历树
type NodeType = string | NodeType[];
type NodeArrayStruct = [Head, ...Tail]
type NodeArrayToString
= NodeArray extends NodeArrayStruct ? NodeToString
: NodeArray extends NodeArrayStruct ? `${NodeToString}, ${NodeArrayToString}`
: '';
type NodeToString
= Node extends string ? Node
: Node extends NodeType[] ? `(${NodeArrayToString})`
: '';
type Test = NodeToString
// => type Test = "(123, (456, 789), (1112))"尾递归 & 尾递归转循环 & 通用递归转循环
在纯函数式编程语言里面，由于没有只能用递归代替循环，但是就会遇到一个非常尴尬的问题「爆栈」，所以函数式编程用尾递归（尾调用）的方式解决了这个问题。
在 类型运算里面函数栈只有 50 层，几乎做不了任何复杂的运算，但是 在 4.5-beta 版里已经支持了类型运算的尾递归优化，用尾递归的方式来写递归极限可以达到 1000 层，远超原来的 50 层。
这一小节展开来讲非常耗时，大家可以通过我的另外两篇文章来补充关于递归的知识：
循环转尾递归
在尾递归章节的文章里面已经讨论过了，递归和循环实际上是等价的，并且已经讨论过如何将递归/尾递归转换成循环。既然等价，那也一定有办法将循环转换成尾递归。
说白了循环是什么？无非就是一个一段代码不断执行罢了，同上面的高阶函数小结我们给循环一个定义：
\begin{} () \ & ' \ Test() \ & True | False\ Loop(Test,, ) \ & if (Test()) \ & then \ Loop(Test, , ()) \ & else \ \end{}
我们把上面定义用代码实现一下就可以得到一个通用的将循环函数转成尾递归的方法，比如我们要将下面循环转成尾递归：
function join(arr) {
const l = arr.length;
let i = 0
let result = ''
while (i test(env)
? loop(test, process, process(env))
: env
function join(arr) {
const env = {
arr,
l: arr.length,
i: 0,
result: '',
}
const newEnv = loop(
env => env.i < env.l, // Test
env => { // Process
const newEnv = {...env}
newEnv.result += newEnv.arr[newEnv.i]
if (newEnv.i != newEnv.l - 1) {
newEnv.result += ','
}
newEnv.i++
return newEnv
},
env // Env
)
return newEnv.result用上面的方法，可以把任何的循环转换成尾递归形式，但是因为 类型不支持高阶函数，所以只能耦合 Loop / 和 Test，并且简化 ，比如如下用类型实现的尾递归版本 Join例子，就没有明确的 Loop / / Test 和 的定义，但其实都耦合在函数里面：
/ 遍历数组
type ArrayStuct = [Word, ...Tail];
type Join
= Arr extends [] ? Result
: Arr extends ArrayStuct ? `${Result}${Word}`
: Arr extends ArrayStuct ? Join
: never;
type Test = Join
// => type Test = "foo,bar,hello" 尾递归遍历树
如何用尾递归遍历树这种数据结构？组合一下上两节的知识就行了：
递归遍历树 --(通用递归转循环)--> 循环遍历树 循环遍历树 --(循环转尾递归)--> 尾递归遍历树
这里再强调一下重点，在用循环遍历一个树的时候，需要记录两个维度的信息才能明确我现在遍历的位置，以及下一步需要遍历的位置：
纵向（下图绿色所示）：表示我遍历的深度，一般用栈表示。 横向（下图红色所示）：表示我遍历到第几个子节点，这个有很多方法只要能标记哪些子节点已经遍历过了，那些未遍历即可。
这里给一个简单的运算加减表达式树的例子，虽然这个例子有更简单的解法（详见前缀式表达式运算），这里给了一个在栈上保留了更多上下文的更为通用的实现方式：
type OperatorType = '+' | '-';
type NodeType = number | OpNodeType;
type OpNodeType = [OperatorType, NodeType, NodeType];
type UnitOpNode
= OpNode;
type OpNode
= [Op, Left, Right];
type FrameType = NodeType;
type StackType = FrameType[];
type PushStack = [Frame, ...Stack];
type Eval
= Stack extends PushStack ? (
[Top, TailStack] extends [number, []] ? Top // 返回结果
: Top extends UnitOpNode ? Eval
: Top extends UnitOpNode ? Eval
: Top extends number ? Eval
: Top extends OpNode ? Eval
: Top extends OpNode ? Eval
: never
)
: never;
type Return
= Stack extends PushStack ? (
Top extends OpNode ? PushStack
: Top extends OpNode ? PushStack
: never
)
: never;
type Test = Eval
// => Test = 4在线体验：
实现 Lisp 解释器
基础知识补充完了以后我们开始实现解释器，开始着手实现解释。
基本加减乘除运算
类型并不能直接对数值进行运算，连最简单的 1 + 1 都无法运算，这个问题曾困扰广大体操运动员很久，直到有一天我们发现了数组可以通过 'length' 取出数值，既然我们不能直接操作数值，但是我们通过操作数组来代替操作数值并且求值，我们提出想法后我们的某个聪明过人的同事就把他实现了出来，加减乘除如下所示：
// 基本运算
export type NArray = N extends N ? (number extends N ? T[] : _NArray) : never
type _NArray = R['length'] extends N ? R : _NArray
type NArrayNumber = NArray
// 加法
export type Add = [...NArrayNumber, ...NArrayNumber]['length']
// 减法
export type Subtract =
NArrayNumber extends [...x: NArrayNumber, ...rest: infer R] ? R['length'] : unknown
// 主要用于辅助推导乘除法; 否则会因为 Subtract 返回类型为 number | unknown 报错
type _Subtract =
NArrayNumber extends [...x: NArrayNumber, ...rest: infer R] ? R['length'] : -1
// 乘法
type _Multiply =
N extends 0 ? res['length'] : _Multiply
export type Multiply = _Multiply
// 除法
type _DivideBy =
M extends 0 ? res["length"] : _Subtract extends -1 ? unknown : _DivideBy
export type DividedBy = N extends 0 ? unknown : _DivideBy;词法分析
词法分析过程也比较简单，我挑选 Lisp 的语法进行实现，就是因为 Lisp S 表达式非常容易解析，解析的过程非常简单，核心代码如下，整体逻辑就是一种类型一种类型的 Token 逐个尝试，直到试到能被解析的为止，并进行下一步：
type Tokenize
= Input extends '' ? TokenResult
: ParseSpace extends TokenResult ? Tokenize
: ParseIdentifier extends TokenResult ? Tokenize
: ParseNumber extends TokenResult ? Tokenize
: ParsePair extends TokenResult ? Tokenize
: ParseSymbol extends TokenResult ? Tokenize
: TokenError的实现都是从头一个一个字符尝试，匹配的技巧字匹配模式小结讲过，尝试到不能解析的位置为止，比如以 为例：
type ParseIdentifier
= Input extends `${infer Char}${infer Next}` ? (
Char extends AlphaChars ? _ParseIdentifierBody
: TokenError
)
: TokenError
;
type _ParseIdentifierBody
= Input extends `${infer Char}${infer Next}` ? (
Char extends AlphaChars | NumberChars ? _ParseIdentifierBody
: TokenResult
)
: TokenResult
;经过这个过程，最后将一串字符串转换成一串 Token 数组：
语法分析
语法分析部分核心代码如下所示，核心过程就是：
如果遇到 ( 符号入栈如果遇到 ) 符号出栈，讲栈顶一整个数组当成一个项加入新的栈顶的数组 如果遇到其他符号，直接将符号加入栈顶的数组
type NodeType = TokenType | NodeType[];
type _SafeTokens = Safe;
type _SafeToken = Safe;
type NodeStackType = NodeType[][];
type NodeStackPush = [...Stack, Top];
type NodeStackPopResult = { stack: Stack, top: Top };
type NodeStackPop
= Stack extends [...infer Tail, infer Top] ? NodeStackPopResult
: ErrorResult;
type ParseError = ErrorResult;
type _Parse
= Tokens extends [infer Token, ...infer Next] ? (
Token extends '(' ? _Parse
: NodeStackPop extends NodeStackPopResult ? (
Token extends ')' ? (
NodeStackPop extends NodeStackPopResult
? _Parse
: ParseError
)
: _Parse
)
: ParseError
)
: Stack;本文共 1686 个字数,平均阅读时长 ≈ 5分钟
腾讯云开发者
