通过与 Jira 对比,让您更全面了解 PingCode

  • 首页
  • 需求与产品管理
  • 项目管理
  • 测试与缺陷管理
  • 知识管理
  • 效能度量
        • 更多产品

          客户为中心的产品管理工具

          专业的软件研发项目管理工具

          简单易用的团队知识库管理

          可量化的研发效能度量工具

          测试用例维护与计划执行

          以团队为中心的协作沟通

          研发工作流自动化工具

          账号认证与安全管理工具

          Why PingCode
          为什么选择 PingCode ?

          6000+企业信赖之选,为研发团队降本增效

        • 行业解决方案
          先进制造(即将上线)
        • 解决方案1
        • 解决方案2
  • Jira替代方案

25人以下免费

目录

程序为什么要编译为语法树而不是语法列表或语法图

三种都有用。而且数据结构的本质区别,决定了这三种数据结构的适用范围。树相比起图,每个节点都至多有一个父节点。这导致,图可以很简单的表示sharing:当一个节点有多个父节点的时候,就被重复使用了。

一、程序为什么要编译为语法树而不是语法列表或语法图

三种都有用。而且数据结构的本质区别,决定了这三种数据结构的适用范围。树相比起图,每个节点都至多有一个父节点。这导致,图可以很简单的表示sharing:当一个节点有多个父节点的时候,就被重复使用了。

更严重的是,这是指数上的性能差异。想一想要把8个a加起来,树跟图差多少就知道了。

为了修复这个问题,我们可以给树引入变量跟let expression。但是要注意:这只是把图内在的性质(sharing)用一套糟糕的语言表达出来。对于图来说,简简单单的‘查找后续’,就变成了‘查找变量名’跟‘用变量名找后续’这个繁复的操作,而且这时候还额外引入了alpha equivalent,unbounded/shadowed variable等,本来不是问题的问题。这些问题可以通过诸如Fresh ML,Higher Order Abstract Syntax,Bound,De Bruijn Index等方法解决,也可以直接‘向Graph靠拢’:<A Graph-Based Higher-Order Intermediate Representation>里面就直接用指针来代表abstraction跟variable。

列表相比起树,每个节点都至多有一个子节点。

这导致,列表除了长度,没有任何结构,于是你无法表示任何‘数据跟操作间的关联’。

比如上面的程序,你用列表写,大概可以用一个stack based language,也就是说forth这样的。

这时候,程序是

a a + a a + +

当我们运行这个程序的时候,我们有一个stack。

当我们执行a的时候,我们把a的值push上stack。

当我们执行+的时候,我们在stack上pop两个值,相加,push回去。

要注意 – 你无法给这个‘程序’加任何括号:列表并不支持这种结构。

当然,结构的损失,也导致了一些优化的‘不可能性’:你无法并行执行这个程序,因为你无法在这个程序中找到一段子程序。

所以,你会在很多linear language(比如assembly, structured logging, skia DSL)里面看到,save/restore, call/return, begin/end等东东。归根到底,这些其实就是试图给列表加入嵌套结构。换句话说,这其实写作列表,读作树。

从图 -> 树 -> 列表这条路走下去,越右边复杂度越低,能表示的东东越小。

但是,反过来说,越左边的东东,越‘无序’,更难操控。

图最大的问题是没有scope,而这代表难以控制副作用范围。

lambda x. read() + x

vs

let a = read() in lambda x. a + x

这两个程序,一个副作用在外面,一个在里面,但是注意 – 这两个程序如果用图表示,后果是一样的。一个解决方法当然是重新引入let expression跟variable,defeating the purpose of the graph,而sea of nodes通过引入region跟control edge解决。如果你想一想,control edge其实就是一个unique backpointer,指定了一个parent,重新把scope变成树状的。

这也是为什么,在数据库跟深度学习里面,IR往往是一个图:这时候,所有操作都是(或者接近是)purely functional的,就没有副作用带来的副作用。

树的问题是,‘值’跟‘值的表式’含糊不分。

比如说,假设我们有以下这个program:

a = read()

a2 = a + a

a4 = a2 + a2

a8 = a4 + a4

我们可以试图把这个program stage下来,写下以下这个metaprogram:

a = Call(“read”, [])

a2 = Plus(a, a)

a4 = Plus(a2, a2)

a8 = Plus(a4, a4)

要注意,这时候,这个程序会执行read()8次,然后把八个结果相加!

这是因为,在本来的program,a2是一个‘值’,就是一个整数,而在metaprogram,a2是那个值的‘表示’,变成了一个ast,后续操作只是不停的引用这个ast而已。

解决方法,就是引入一个叫做letlist的辅助结构:对于所有操作,我都生成一个名字,然后把(名字,操作)放进letlist,并且后续只用这个名字引用这个值,而在退出当前scope的时候,利用letlist生成对应的let expression。这样,被引用的,永远只是name,而复制这些name不会造成任何问题。

同样的问题不止在staging中会出现,也会在编译器中出现。比如在strength reduction中,我们希望把2 * x优化成x + x,而这时候,x会被复制一次(考虑下x是read()的时候会怎么样)。解决方法也是一样的:我们还是对程序的所有操作赋予一个名字,而且只容许通过名字访问。(这可以通过对程序跑一遍staged definitional interpreter on letlist得到),而这,就是大名鼎鼎的ANF。已知接近的,CPS跟call by push value也是通过‘禁止构造复杂表达式,一切只能由名字访问’来控制evaluation跟effect的。

要注意,letlist是一个列表。再直白一点:在一个没有任何scope的程序上跑ANF,就会得到3地址码!归根到底,值跟表示的不匹配,就是因为一个简单的值,会由一个复杂的数据结构表示。换句话说,这是因为树可以嵌套。禁止掉嵌套以后,我们就得出一个更线性,更接近列表的表示法。

除了以上描述的光谱跟tradeoff,在现实中,编译器往往会采用多个IR。

比如说,你可以想象一个编译器,前端先parse上AST再进行一些desugar,中端用sea of nodes或者thorin等处理,然后后端会上一个peephole superoptimizer over ASM,这时候,树,列表,图都齐了。

延伸阅读:

二、什么是最小生成树

在给定一张无向图,如果在它的子图中,任意两个顶点都是互相连通,并且是一个树结构,那么这棵树叫做生成树。当连接顶点之间的图有权重时,权重之和最小的树结构为最小生成树!

在实际中,这种算法的应用非常广泛,比如我们需要在n个城市铺设电缆,则需要n-1条通信线路,那么我们如何铺设可以使得电缆最短呢?最小生成树就是为了解决这个问题而诞生的!

相关文章