3个不稳定版本

使用旧的Rust 2015

0.2.1	2017年1月31日
0.2.0	2017年1月31日
0.1.0	2017年1月24日

#176 in 可视化

MIT 许可证

130KB
2K SLoC

TIMi - 模板实例化机解释器

一个可视化、用户友好的模板实例化机实现。旨在理解如何惰性评估编程语言。

创建定义使用define <name> [<param>]* = <expr>来创建新的超级组合子。 > define plus x y = x + y 将创建一个名为plus的函数，该函数接受两个参数x和y。要运行此函数，请调用 > plus 1 1 解释器选项和使用方法 >:步要逐步执行，请使用 >:step enabled stepping through execution >1 + 1 *** ITERATION: 1 Stack - 1 items ## top ## 0x21 -> ((+ 1) 1) H-Ap(0x1F $ 0x20) ## bottom ## Heap - 34 items 0x21 -> ((+ 1) 1) H-Ap(0x1F $ 0x20) Dump Empty Globals - 30 items None in Use ===///=== 1>> 注意，提示符已更改为>>。步骤命令 >>n（用于next）以进入下一步 >:nostep 要启用整个程序的连续执行，请使用 >:nostep 执行.tim文件解释器可以通过传递文件名作为命令行参数在单独的文件上调用。示例：独立文件创建一个名为 standalone.tim 的文件 #standalone.tim main = 1 使用以下命令运行 $ timi standalone.tim 这将打印出程序跟踪信息 *** ITERATION: 1 Stack - 1 items ## top ## 0x1E -> 1 H-Num(1) ## bottom ## Heap - 31 items 0x1E -> 1 H-Num(1) Dump Empty Globals - 30 items None in Use ===///=== === Final Value: 1 === 语言介绍该语言是一种小型、惰性求值的语言。惰性求值意味着直到需要值时才进行求值。顶层（超级组合子）顶层声明（也称为超级组合子）的形式为 <name> [args]* = <core expr> #####示例 K x y = x 多个顶层声明通过使用 ; 来分隔 I x = x; K x y = x; K1 x y = y 请注意，最后一个表达式后面没有 ; main值编写程序（不是在解释器中运行的表达式）时，执行从名为 main 的顶层函数（超级组合子）开始。表达式表达式可以是以下给定选项之一。注意，lambda 和 case 是缺失的，因为它们在这种机器的风格中难以实现。关于这一点在缺少 Lambda 和 Case 部分有更多讨论。 Let let <...bindings...> in <expr> Let 绑定可以是递归的，并且可以相互引用。 #####示例：简单的 let > let y = 10; x = 20 in x + y ... === Final Value: 30 === 示例：相互递归的 let # keep in mind that K x y = x > let x = K 10 y; y = K x x in x ... === Final Value: 10 === 尽管 x 和 y 是相互定义的，但它们并不直接引用对方。相反，它们作为某个较大函数的组件相互引用。这是允许的，因为可以“解析”x 和 y。因此，此示例将求值为 10。示例：由于严格的 let 绑定不允许的代码注意： Let 绑定是严格的，而不是惰性的，因此此代码将无法工作 > let y = x; x = y in 10 *** ITERATION: 1 step error: variable contains cyclic definition: y 在这里，甚至无法解析 y 和 x。因此，解释器将拒绝此代码。函数应用 function <args> 类似于 Haskell 的函数应用。参数 <args> 是原始值或变量。所有 n-元应用都由嵌套的 1-元应用表示。函数默认是柯里化的。 f x y z == (((f x) y) z) 数据声明 Pack{<tag>, <arity>} Pack 原始操作接受一个标记和参数数量。当使用时，它将 arity 个表达式打包成一个单一的对象，并用 tag 标记。示例 False = Pack{0, 0} True = Pack{1, 0} True 和 False 分别表示为标记为 1 和 0 的对象，它们具有 0 的参数数量。 MkPair = Pack{2, 2} my_tuple = MkPair 42 -42 MkPair 是一个用于创建元组的函数，它使用标记 2 并需要两个参数。现在 my_tuple 是一个数据节点，包含值 42 和 -42。注意：由于语言中没有 case 表达式，因此使用自定义标记不会非常有用。相反，List 和 Tuple 作为语言内建项创建，分别带有自定义解构函数 caseList 和 casePair。原始应用 <arg1> primop <arg2> 整数上的原始操作。支持以下操作 - Arithmetic - `+`: addition - `-`: subtraction - `*`: multiplication - `/`: integer division - Boolean, returning `True` (`Pack{1, 0}`) for truth and `False` (`Pack{0, 0}`) for falsehood: `<`, `<=`, `==`, `/=`, `>=`, `>` 原始字面量整数声明。 >3 布尔值 True = Pack{1, 0} False = Pack{0, 0} True 和 False 分别由带标签 1 和 0 的数据类型表示。元组元组是语言内置的，通过使用 MkPair 构建。 MkPair <left> <right> 使用 casePair 来对元组进行模式匹配。 casePair (MkPair a b) f = f a b 请注意，默认的 fst 和 snd 定义如下 K x y = x; K1 x y = y; fst t = casePair t K; snd t = casePair t K1; ** 列表列表是语言内置的，有两个构造函数： Nil 和 Cons Nil Cons <value> <list> 使用以下方式通过模式匹配来处理列表 caseList <nil-handler> <cons-handler> nil-handler 是一个值 cons-handler 是一个函数，它接受 2 个参数，即 Cons 单元中的值和列表的其余部分。 Cons 注释 # anything after a # till the end of the line is commented main = 1 # this is a comment as well 注释风格类似于 Python，其中 # 用于注释到行尾。没有多行注释。缺少Lambda和Case 情况 Case 需要我们有一些模式匹配/解构的概念，而这在这个机器中是不存在的。 Lambda 作为简化，语言假设所有 lambda 都已经被转换成顶层定义。这个过程称为 lambda lifting，并且 TIMi 假设所有 lambda 都已经被提升。运行时函数默认是柯里化的。因此，(f x y z) 实际上是 (((f x) y) z) 机器的组成部分运行时包含 4 个组件堆：地址到堆节点的映射栈：堆地址的栈转储：栈的栈，用于存储中间评估结果全局变量：名称到地址的映射机器在运行时使用的所有内容必须在机器开始执行之前分配到堆上。因此，我们需要一种将 CoreExpr 转换为 Heap 的方法。这个过程称为实例化。实例化示例：示例程序 1 + 1 考虑程序 1 + 1。机器的初始状态是 >1 + 1 *** ITERATION: 1 Stack - 1 items ## top ## 0x21 -> ((+ 1) 1) H-Ap(0x1F $ 0x20) ## bottom ## Heap - 34 items 0x21 -> ((+ 1) 1) H-Ap(0x1F $ 0x20) 0x1F -> (+ 1) H-Ap(0xE $ 0x1E) 0x1E -> 1 H-Num(1) 0xE -> + H-Primitive(+) 0x20 -> 1 H-Num(1) Dump Empty Globals - 30 items + -> 0xE 请注意，表达式 1 + 1 的每一部分都在堆上，符号 + 映射到其在 Globals 部分中的地址 0xE。整个表达式位于栈顶，等待评估。评估我们将通过解释如何评估 1+1 来解释代码的评估过程。评估示例： (((S K) K) 3) 考虑以下定义 S f g x = f x (g x) K x y = x (这些是 lambda 演算中的 S 和 K 组合子) 现在，让我们了解程序 S K K 3 的评估过程。 *** ITERATION: 1 Stack - 1 items ## top ## 0x21 -> (((S K) K) 3) H-Ap(0x1F $ 0x20) ## bottom ## ... ===///=== 最初，我们想要运行的字节码(((S K) K) 3)位于栈顶。 *** ITERATION: 2 Stack - 2 items ## top ## 0x1F -> ((S K) K) H-Ap(0x1E $ 0x1) 0x21 -> (((S K) K) 3) H-Ap(0x1F $ 0x20) ## bottom ## ... ===///=== 记住，所有应用总是柯里化的。也就是说，(((S K) K) 3)被视为(((S K) K)在3上的应用。函数应用((S K) K)的左侧被推入当前栈顶。这个过程一直持续到栈顶有一个超组合子。 *** ITERATION: 3 Stack - 3 items ## top ## 0x1E -> (S K) H-Ap(0x3 $ 0x1) 0x1F -> ((S K) K) H-Ap(0x1E $ 0x1) 0x21 -> (((S K) K) 3) H-Ap(0x1F $ 0x20) ## bottom ## ... ===///=== *** ITERATION: 4 Stack - 4 items ## top ## 0x3 -> S H-Supercombinator(S f g x = { ((f $ x) $ (g $ x)) }) 0x1E -> (S K) H-Ap(0x3 $ 0x1) 0x1F -> ((S K) K) H-Ap(0x1E $ 0x1) 0x21 -> (((S K) K) 3) H-Ap(0x1F $ 0x20) ## bottom ## Heap - 34 items 0x1F -> ((S K) K) H-Ap(0x1E $ 0x1) 0x1E -> (S K) H-Ap(0x3 $ 0x1) 0x1 -> K H-Supercombinator(K x y = { x }) 0x3 -> S H-Supercombinator(S f g x = { ((f $ x) $ (g $ x)) }) 0x20 -> 3 H-Num(3) 0x21 -> (((S K) K) 3) H-Ap(0x1F $ 0x20) ===///=== 看看当前的栈状态。应用的左侧参数不断推入栈中。这个过程一直持续到栈顶有一个超组合子。这个过程被称为函数调用的展开。实例化现在，一个超组合子（S）位于栈顶，我们需要通过传递参数来实际应用它。在这个阶段，“脊”被展开。栈顶的条目（S）被弹出以进行评估。由于S需要3个参数（f、g和x），因此另外弹出3个条目从弹出的元素中取出S的参数。在地址0x1E的1次应用（(S K)）的参数变为f 在地址0x1F的2次应用（(S K) K）的参数变为g 在地址0x21的3次应用（((S K) K ) 3)的参数变为3 所以，总结当前阶段 S：展开的超组合子 K：第一个参数，f K：第二个参数，g 3：第三个参数，x 接下来，在第5次迭代中，我们将超组合子的主体推入一个空栈，并替换变量。 *** ITERATION: 5 Stack - 1 items ## top ## 0x24 -> ((K 3) (K 3)) H-Ap(0x22 $ 0x23) ## bottom ## Heap - 37 items 0x24 -> ((K 3) (K 3)) H-Ap(0x22 $ 0x23) 0x1 -> K H-Supercombinator(K x y = { x }) 0x20 -> 3 H-Num(3) 0x23 -> (K 3) H-Ap(0x1 $ 0x20) 0x22 -> (K 3) H-Ap(0x1 $ 0x20) ... ===///=== 请注意，现在S的参数已经在堆上实例化了。这就是为什么它被称为“实例化机”的原因——它通过在堆上实例化参数来展开超组合子。 f（K）位于0x22 g（K）位于0x23 x（3）位于0x20 评估是如何提供惰性的？首先，我们将对评估过程做一些观察在超组合子展开过程中，只有被使用的变量会被实例化。参数不会进行评估，只是在函数体中进行替换。因此，我们可以这样表述：评估是从外部向内部进行的。这是因为应用展开的方式导致的。 *** ITERATION: 7 Stack - 3 items ## top ## 0x1 -> K H-Supercombinator(K x y = { x }) 0x22 -> (K 3) H-Ap(0x1 $ 0x20) 0x24 -> ((K 3) (K 3)) H-Ap(0x22 $ 0x23) ## bottom ## ((K 3) (K 3))首先进行评估。当K被展开时，其展开方式如下： *** ITERATION: 8 Stack - 1 items ## top ## 0x20 -> 3 H-Num(3) ## bottom ## 函数((K 3 (K 3))的第二个参数，即(K 3)根本就没有被评估过！3被替换为x，在K x y = x的函数体中。因此，通过从外部向内部进行评估，并且只替换函数体而不评估参数，我们实现了惰性求值。原语例如，+、-等在某种程度上是相似的——它们也遵循相同的执行尾部展开模型。 >1 + 1 *** ITERATION: 1 Stack - 1 items ## top ## 0x31 -> ((+ 1) 1) H-Ap(0x2F $ 0x30) ## bottom ## ===///=== *** ITERATION: 2 Stack - 2 items ## top ## 0x2F -> (+ 1) H-Ap(0xE $ 0x2E) 0x31 -> ((+ 1) 1) H-Ap(0x2F $ 0x30) ## bottom ## ===///=== *** ITERATION: 3 Stack - 3 items ## top ## 0xE -> + H-Primitive(+) 0x2F -> (+ 1) H-Ap(0xE $ 0x2E) 0x31 -> ((+ 1) 1) H-Ap(0x2F $ 0x30) ## bottom ## ===///=== *** ITERATION: 4 Stack - 1 items ## top ## 0x31 -> 2 H-Num(2) ## bottom ## ===///=== === FINAL: "2" === 计算类似(I 3) + 1这样的表达式并不简单，因为现在需要先评估I 3，然后才能评估+。关于此过程的详细说明请见“输出”部分。间接引用当我们实例化一个超组合子时，我们不会缓存应用的结果。函数应用通过重写应用节点的值为获得的结果来优化。这会缓存计算过程。这正是Indirection节点所做的事情——它们将堆地址重定向到另一个地址。我们将考虑以下示例，其中我们定义了x = I 3，其中I x = x。 >define x = I 3 >x *** ITERATION: 1 Stack - 1 items ## top ## 0x22 -> x H-Supercombinator(x = { (I $ n_3) }) ## bottom ## ... ===///=== *** ITERATION: 2 Stack - 1 items ## top ## 0x25 -> (I 3) H-Ap(0x0 $ 0x24) ## bottom ## ... ===///=== *** ITERATION: 3 Stack - 2 items ## top ## 0x0 -> I H-Supercombinator(I x = { x }) 0x25 -> (I 3) H-Ap(0x0 $ 0x24) ## bottom ## ... ===///=== *** ITERATION: 4 Stack - 1 items ## top ## 0x24 -> 3 H-Num(3) ## bottom ## ... ===///=== === FINAL: "3" === 现在我们已经运行了x一次，让我们再次运行它并查看其值。 >x *** ITERATION: 1 Stack - 1 items ## top ## 0x22 -> indirection(indirection(3)) H-Indirection(0x25) ## bottom ## Heap - 39 items 0x22 -> indirection(indirection(3)) H-Indirection(0x25) 0x25 -> indirection(3) H-Indirection(0x24) 0x24 -> 3 H-Num(3) ... ===///=== *** ITERATION: 2 Stack - 1 items ## top ## 0x25 -> indirection(3) H-Indirection(0x24) ## bottom ## ... ===///=== *** ITERATION: 3 Stack - 1 items ## top ## 0x24 -> 3 H-Num(3) ## bottom ## Heap - 39 items 0x24 -> 3 H-Num(3) ... ===///=== === FINAL: "3" === > 请注意，x的值现在已变为一个指向0x25的间接引用，之前它持有（即I 3）。 0x25是一个间接引用，它引用了I 3的值，即3（在0x24处）。这样，I 3的值没有进行评估。它被重定向到3。转储现在我们已经了解了函数应用的工作方式，我们想要了解诸如+、-等原语是如何工作的。让我们考虑以下示例代码 (I 1) + 3，其中 I x = x（恒等）。 >I 1 + 3 *** ITERATION: 1 Stack - 1 items ## top ## 0x2C -> ((+ (I 1)) 3) H-Ap(0x2A $ 0x2B) ... ===///=== *** ITERATION: 2 Stack - 2 items ## top ## 0x2A -> (+ (I 1)) H-Ap(0xE $ 0x29) 0x2C -> ((+ (I 1)) 3) H-Ap(0x2A $ 0x2B) ## bottom ## ... ===///=== *** ITERATION: 3 Stack - 3 items ## top ## 0xE -> + H-Primitive(+) 0x2A -> (+ (I 1)) H-Ap(0xE $ 0x29) 0x2C -> ((+ (I 1)) 3) H-Ap(0x2A $ 0x2B) ## bottom ## ... Dump Empty ===///=== 现在栈顶有 +，但左侧是一个需要执行的计算。因此，我们需要某种执行计算的方法。解决方案是将当前栈迁移到 Dump 中，并将 I 1 推送到栈顶并执行它。 *** ITERATION: 4 Stack - 1 items ## top ## 0x29 -> (I 1) H-Ap(0x0 $ 0x28) ## bottom ## Heap - 45 items 0x29 -> (I 1) H-Ap(0x0 $ 0x28) 0x2A -> (+ (I 1)) H-Ap(0xE $ 0x29) 0x0 -> I H-Supercombinator(I x = { x }) 0xE -> + H-Primitive(+) 0x28 -> 1 H-Num(1) 0x2B -> 3 H-Num(3) Dump ## top ## 0xE -> + H-Primitive(+) 0x2A -> (+ (I 1)) H-Ap(0xE $ 0x29) 0x2C -> ((+ (I 1)) 3) H-Ap(0x2A $ 0x2B) ## bottom ## --- ===///=== 注意，现在 I 1 在栈顶，而 Dump 包含了之前的栈内容。我们继续观察 I 1 的执行。 *** ITERATION: 5 Stack - 2 items ## top ## 0x0 -> I H-Supercombinator(I x = { x }) 0x29 -> (I 1) H-Ap(0x0 $ 0x28) ## bottom ## Dump ## top ## 0xE -> + H-Primitive(+) 0x2A -> (+ (I 1)) H-Ap(0xE $ 0x29) 0x2C -> ((+ (I 1)) 3) H-Ap(0x2A $ 0x2B) ## bottom ## ===///=== *** ITERATION: 6 Stack - 1 items ## top ## 0x28 -> 1 H-Num(1) ## bottom ## Dump ## top ## 0xE -> + H-Primitive(+) 0x2A -> (+ indirection(1)) H-Ap(0xE $ 0x29) 0x2C -> ((+ indirection(1)) 3) H-Ap(0x2A $ 0x2B) ## bottom ## ===///=== 注意，在迭代 6 中，I 1 在 0x2A 处的重写也导致栈发生变化。现在的栈内容是 0x2A -> (+ indirection(1)) H-Ap(0xE $ 0x29) 而迭代 5 时的栈内容是 0x2A -> (+ (I 1)) H-Ap(0xE $ 0x29) 这允许 + 执行在稍后“捡起”值 1。这种重写对于这个评估是必不可少的。它允许导出的栈获取 I 3 执行的结果。现在栈中只有一个元素 1。没有剩余的评估。因此，我们知道 (I 1) 的值是 1。我们在 Dump 中的其余计算，将其恢复。 *** ITERATION: 7 Stack - 3 items ## top ## 0xE -> + H-Primitive(+) 0x2A -> (+ indirection(1)) H-Ap(0xE $ 0x29) 0x2C -> ((+ indirection(1)) 3) H-Ap(0x2A $ 0x2B) ## bottom ## Dump ===///=== *** ITERATION: 8 Stack - 1 items ## top ## 0x2C -> ((+ 1) 3) H-Ap(0x2A $ 0x2B) ## bottom ## Dump Empty ===///=== 在迭代 7 时，栈内容是 0x2A -> (+ indirection(1)) H-Ap(0xE $ 0x29) 我们通过“短路”间接引用并替换为我们想要的值来消除间接引用。 *** ITERATION: 9 Stack - 2 items ## top ## 0x2A -> (+ 1) H-Ap(0xE $ 0x28) 0x2C -> ((+ 1) 3) H-Ap(0x2A $ 0x2B) ## bottom ## ===///=== *** ITERATION: 10 Stack - 3 items ## top ## 0xE -> + H-Primitive(+) 0x2A -> (+ 1) H-Ap(0xE $ 0x28) 0x2C -> ((+ 1) 3) H-Ap(0x2A $ 0x2B) ## bottom ## ===///=== *** ITERATION: 11 Stack - 1 items ## top ## 0x2C -> 4 H-Num(4) ## bottom ## Dump Empty ===///=== === FINAL: "4" === 现在我们有一个简单的表达式，评估过程如往常一样进行，以机器评估栈顶的 1 + 3 结束。路线图标记 1（模板实例化） let，letrec 模板更新（不要每次都天真地实例化）数值函数布尔值元组列表更友好的执行步骤界面设计决策 TIMi 是用 Rust 编写的，因为 Rust 是一种系统语言，因此它允许对内存、引用等有更多的控制，这让我很享受。 Rust 有不错的 readline 库、表格打印库，以及一个流畅的 stdlib 用于编写美观的代码学到的知识懒递归绑定与严格递归绑定的区别懒递归绑定会让你避开 let y = x; x = y in 10 而严格递归绑定将尝试实例化 x 和 y。 [..] 和 &[..] 的区别无 ref 切片与带 ref 切片区别在于第二个切片 [..] 维护了编译时所需的长度信息。参考实现函数式语言，教程非常感谢 quchen 的 STGi 实现，我从这份文档中借鉴了其文档风格。

依赖项 ~5.5MB ~84K SLoC ansi_term 0.9 prettytable-rs 0.6 rand 0.3 rustyline 1.0

3个不稳定版本

TIMi - 模板实例化机解释器

目录

快速入门

从cargo的二进制文件

从源代码构建

使用解释器

评估表达式

创建定义

解释器选项和使用方法

>:步

步骤命令

>:nostep

执行.tim文件

示例：独立文件

语言介绍

顶层（超级组合子）

main值

表达式

示例：相互递归的 let

示例：由于严格的 let 绑定不允许的代码

缺少Lambda和Case

情况

Lambda

运行时

机器的组成部分

实例化示例：示例程序 1 + 1

评估

评估示例： (((S K) K) 3)

实例化

评估是如何提供惰性的？

原语

间接引用

转储

路线图

设计决策

学到的知识

懒递归绑定与严格递归绑定的区别

[..] 和 &[..] 的区别

参考

依赖项

从`cargo`的二进制文件

`>:步`

`>:nostep`

执行`.tim`文件

`main`值

示例：相互递归的 `let`

示例：由于严格的 `let` 绑定不允许的代码

实例化示例：示例程序 `1 + 1`

评估示例： `(((S K) K) 3)`

`[..]` `和 &[..] 的区别`