使用图形理解程序

您可能听说过编译器在解析程序时使用称为抽象语法树(AST)的数据结构，但很少有人知道通常在编译开始时就使用AST，而功能强大的编译器通常使用更高级类型的数据结构作为其中间表示，以优化您的程序并在编译的后期阶段将其转换为机器码。以我们在Shopify工作的Ruby的即时编译器TruffleRuby为例，这种数据结构被称为节点海图形。我想向您展示这种节点海图形数据结构是什么样子以及它是如何工作的，我认为出于以下几个原因，这样做是值得的。首先，我只是认为它是一个非常有趣和漂亮的数据结构，但也是一个实用的结构。为了通过我们行业的面试，学习数据结构和算法的压力很大，能展示一些我们在Shopify应用的非常实用的东西是很棒的。此外，节点海中的图形在视觉上对我非常有吸引力，我想与您分享它们。其次，对此数据结构略知一二可以让您深入了解程序的真正含义以及编译器如何理解它，因此我认为它可以增加您对程序如何运行的理解。在这一点上，我应该告诉您，我恐怕实际上要使用Java来展示我的示例，以便使它们更简单、更容易理解。这是因为与Ruby相比，Java具有更简单的语义-更简单的语言工作规则-以及更简单的图形。例如，如果您在Java中索引一个数组，那么简单的索引几乎就是它的全部功能。如果在Ruby中为数组编制索引，可能会有正索引、负索引、范围、转换、强制和更多-只是更复杂。但是不用担心，它都是超基本的Java代码，所以如果您来自Ruby或任何其他语言，都可以假装它是伪代码。阅读节点海GraphsLets通过显示一些代码和相应的节点海图直接进入。下面是一个Java方法。正如我所说的，它没有使用任何高级Java特性，所以如果您愿意，您可以假装它是伪代码。它使用简单的递归方法从称为斐波那契序列的数学序列中返回一个数字。以下是该程序的传统AST数据结构。它是一棵树，它直接映射到文本源代码，不添加和删除任何内容。要运行它，您需要沿着树中的一条路径，从顶部开始，按深度优先遍历它。抽象斐波纳契序列程序的语法树，下面是同一程序的节点海图。这是一个真正的数据结构转储，就像我们在前面展示的编译斐波纳契序列的Java方法时使用的数据结构一样，节点海图表是斐波纳契序列程序的节点海图表，这里有很多事情要做，但我会将其分解。我们有方框和箭头，所以它就像流程图一样。框是操作，箭头是操作之间的连接。一个操作只有在所有带箭头的操作都运行完之后才能运行。一个非常重要的概念是，有两种主要的箭头，它们非常不同。粗红色箭头显示控件在程序中的流动方式。绿色细箭头显示数据在程序中的流动方式。虚线的黑色箭头是元信息。有些人画了指向上方的绿色箭头，但在我们团队中，我们认为显示向下流动的数据会更简单。还有两种主要的操作框。方形的红色盒子做了一些事情；它们有副作用，或者在某种程度上是必须的。菱形绿色方框计算一些东西(它们是纯的，或无副作用的)，绿色表示安全执行，P(0)表示参数0，即第一个参数。C(2)表示常量值2。大多数其他节点应该可以从它们的标签中理解。每个节点都有一个便于参考的数字。要在您的头脑中运行程序，请从顶部的开始节点开始，然后向下向下移动红色粗箭头，指向底部的一个返回节点。如果您的正方形红色方框有一个箭头从椭圆形或菱形绿色方框指向它，那么您首先运行那个绿色方框，以及指向该绿色方框的任何其他绿色方框。我认为这种数据结构的一个主要特点是非常棒的。红色部分是必备程序，绿色部分是小功能程序。我们已经从单个Java程序中分离出这两个。他们是在重要的地方加入的，而不是在不重要的地方加入的。这将在稍后变得有用。我通过图表理解了我说的，我认为你可以使用这些图表了解一些关于你的程序的见解。这就是我所说的意思。当你用文本编写程序时，你是在用线性格式编写，这意味着很多东西实际上并不是