编译器很难
我经常听说编写编译器很困难，并且与编写其他类型的软件有所不同。一些近期的经验使我对为什么会这样有深刻的认识，并证明了这很有趣！
我最近完成了ShipReq的新功能的工作。我花了大约2个月的时间进行开发，最终成为我一生中编写过的最困难的代码。我已经进行了数十年的编码，从事过许多不同的项目，并且从事的工作非常庞大组织；我是根据上下文告诉您的。当我说这是我编写过的最困难的代码时，它经历了很多竞争。并发系统通常以非常困难而著称，我在OO时代从头开始设计并编写了一个大型并发项目，包括编写所有调度和并发原语，以及自己管理所有线程安全性（这些时间是不同的）。我发现这件工作要困难得多。
我在ShipReq About页面上说ShipReq就像一个编译器。我最近完成的最大功能是迄今为止最类似于编译器的功能，令我惊讶的是，正是该属性使它如此难以置信地难以理解。基本上，当您有大量需求/问题/设计文档/其他内容时，此功能增加了自动功能，可以根据它们之间的关系和相关字段填充某些字段，从而使用户不必自己手动编辑或维护它，这既繁琐例如，如果有人提出了一个需要修复一些开发任务的错误，则可以设置他们的项目，以便当所有这些开发标记都标记为“完成”时，错误本身会自动变为“准备就绪”。测试”。此功能不具备“完成”或“测试”的知识，但允许用户定义所需的任何状态和规则。这听起来似乎与编写编译器无关。（可能不会甚至没有声音。）需求，错误报告，项目文档似乎也与代码无关，但是却有惊人的相似之处。让我们来看看…
ShipReq中几乎所有数据关系都是多对多/ DAG.ShipReq中的某些视图将数据显示为平面列表，但实际上，很少将任何内容存储为平面列表，并且几乎总是有一种查看方式与图形或树相同的数据。
如果您斜视一下，源代码也是如此：包具有多个类/对象，具有多个方法/字段/内部类，具有多个具有多个子句的语句等，在声明方面，它更像是-多对多比多对多，但它仍然是一个很大的DAG。当我们开始考虑诸如import和调用其他方法的方法之类的关系时，它也变得多对多，并得到一个循环图。
其次，ShipReq中的这一新功能非常易于用户配置，这是ShipReq的主要目标，避免硬编码隐式假设并找到适当且可配置的抽象，显然让用户一直需要重新配置所有内容将是一个沉重的负担，因此我们提供了-configure具有最佳实践的完整设置，用户可以（可选）使用它们，并且可以不受限制地进行重新配置以最好地满足他们的需求，从编码的角度来看，这意味着我们在编译时不了解自动化规则。代码需要在运行时理解和应用所有规则，并且需要能够识别和处理使不变式无效的数据和逻辑组合。这听起来似乎没什么大不了，但是在复杂的系统中有许多不变量，并且不变量不会在其直接域边界处停止-它们会传播所有相关图，并与其他不变量一起构成各种复杂程度的变量。
例如，您可能在10个隔离的域中有10个简单不变式，但是当它们全部组合在一起时，要考虑的状态数将达到10,000,000,000，并且在您认为非法（即错误）的状态中，将会有非常大的百分比。
这也就像编写编译器一样。例如，Java编译器不会对您的类的隐私级别进行硬编码。就像ShipReq可能有一个用于配置的UI页面一样，在Java中，您具有修饰符关键字，例如public class与private class不同。从编写编译器的角度来看，这些是具有运行时规则的运行时值当考虑诸如final和abstract之类的其他关键字时，我们开始了解关于组合爆炸的含义.Java编译器在运行时必须确保所有可能的组合均有效。例如，它将拒绝以下代码：
最后的公共类{public abstract void doSomething（）; //不允许在最终类中使用抽象方法}
想象您正在编写自己的Java编译器，完全由您考虑这些非法组合，然后编写代码来捕获它们，我认为我们所有人都认为理所当然，例如将方法标记为私有，然后知道不可能在外部调用，但实际上并不是完全不可能。您实际上是在正确的地方依赖某人的if语句。就像我的ShipReq示例一样，它是在运行时进行所有价值检查的，并不能保证所有功能的交互方式。与最终和抽象功能进行交互的类/方法隐私功能在心理上足够容易，但是每个功能都具有与其他功能进行不良交互的能力，并且识别这些组合并不总是那么容易。
我最近在Scala上看到了PR，这恰好说明了这一点。private和seal关键字一直存在于Scala中，直到最近才有人意识到私有类已被有效密封.Scala已经存在16年了！具有数百个功能，手动考虑每种可能的组合似乎并不可行。100个功能会产生4950个唯一对。不过，配对并没有什么特别的，有些问题可能只有在三个特定功能相交时才能体现出来。对于100个功能，有：
在可能的100个功能中，有10个功能之间的交互不好的可能性不大。要手动考虑也是不可能的。
类型安全性是我一直依赖的支柱。当您认为类型安全性时，虽然这只是一个开始，但请不要想起Java的类型系统，这并不是我真正的意思。我的意思是，更多的语言是Scala和Haskell之类的语言的类型系统，它们会考虑诸如存在和依赖类型等特征。 Java和Typescript之类的类型系统很棒！他们增加价值！但是，使用更先进的类型系统可以使您的安全数量级提高一个或两个以上，并且当您学习如何充分利用它们时，这将非常有益。
不幸的是，类型安全性在开发重要功能时对我没有太大帮助。例如，您拥有一个数据位置，无法接受一组值。在编译时，每个运行时值都是可以接受的，因为始终存在允许每个可能值合法的配置，就像具有String类型的'Name'字段，然后是一个运行时规则规定该名称的第一个字母一样。 （不切实际，但这是我要强调的概念。）配置可能是firstNameLetter：选项[Char]。在这种情况下，您必须将名称字段设置为可容纳所有可能性的名称，例如name：String。创建一个对名称证明进行编码以使其遵守规则的类型可能很棘手，但这仅是该名称的派生（名称：String，firstNameLetter：选项[Char]）。除非名称和配置以及可以原子方式修改为单个复合值，否则您仍需要在这样的派生之前将两个值独立存储。名称限制的首字母是一个玩具示例，但它演示了以下事实：您在一个位置具有运行时配置，在另一个位置具有运行时数据，并且在编译时没有类型安全性来强制执行正确的事情在运行时发生。
编译器有同样的问题。它们维护着庞大的运行时数据存储库，这完全取决于编译器作者是否可以应用所有规则，根据其他仅运行时条件等将数据移入和移出范围等。与我们的编译器用户不同，它们没有不能依赖（大部分）类型系统。它们是独立的，只能使用类型安全性来保护其非常复杂的域的底层。
这是流程出错的必要部分，因此需要向用户提供有意义的反馈。
检测总是错误的更改，并阻止用户进行这些更改。这些是错误。
检测出错误的数据/配置，相应地修改派生，并以完全可理解的方式将其呈现给用户。这些是警告。
收集所有必要的信息，以向用户确切解释派生数据的产生方式，原因和来源。自动填充/修改用户数据是一回事，但我相信用户应该能够检查和理解诸如执行了哪些步骤，以及哪些数据是因素。这就是出处。听起来并不难，但在实践中，实施起来却极具挑战性。
在运行时检测非法数据和数据组合，并向用户解释。这些都是错误。
检测可以接受或潜在错误的数据，进行处理（可能通过忽略该语句或以某种方式修改生成的代码），最后将其标记给用户。这些是警告。
一些编译器通常会在编译错误中计算出结果并呈现出来。一些编译器的错误消息会运行10到30行，因为它们提供了大量有关上下文和计算的信息。这是一种出处。
与上面的观点类似，这些都是专门人员编写的if条件（不是字面意义）的四倍，在非常重要的位置收集各种运行时数据，并进行大量的条件数据转换，以便能够简明地解释更大的基础数据集。
缓慢的编译器使大众感到沮丧。每隔两年左右，Scala的编译速度将大大提高，并且将继续如此，但是慢速的不良声誉仍然在很多人的脑海中持续存在。我认为Rust社区正在开始积累这一点。 Go的支持者自豪地宣布超快编译速度是该语言的主要卖点之一。编写编译器时，速度非常重要。
我编写的功能具有相同的要求。每次用户更改时，都有可能需要全面重新计算！每次更改发生的任何事情都必须快速。
大约9年以来，我一直是FP（函数式编程）的坚定支持者，但是为此，我不得不使用大量的变量和可变性。FP的妙处在于，您可以将可变代码封装在不可变的代码中以及参考透明的方式，使得工作的“原子”本身就是FP，尽管引擎盖下有很多可变性。这正是我所做的，而且我能够吃蛋糕：代码超快且整个“编译”步骤都是原子性的和纯净的，这意味着我不会牺牲FP。不变的结果，但我只是碰巧使用了很多可变性来达到那个不变的结果。这是Scala的绝妙特性，顺便说一下，它是多范式的性质。 （只有一种语言）会认为您在Haskell中可以达到相同的速度，但是我不确定该语句的准确性，也不确定该语句的实现方式。代码是否会做同样的事情，但是使用IORef或StateT堆栈使用更多样板？Haskell的优化效率如此之高，以至于更直接的FP方法足够快吗？我实际上不知道，但是非常有趣的发现。我想看一下Haskell编译器的内部结构将是一个非常出色的见解的宝库。但是我离题了。
除了Haskell之外，编写快速编译器意味着具有很多可变状态。突变状态很难以指数方式推理和保持正确。眼泪汪汪，这是我要达到闪电般的性能所必须达到的目标（这是经过许多非常有策略的缓存之后），据我所知，它几乎存在于所有编译器中。
我们讨论了很多困难，但是有什么解决方案？到底如何确保具有这种复杂性的代码真正起作用？这是我的方法。
首先，要做的是使您的测试，尤其是测试数据表示形式，尽可能易于读写。
最终案例类结果（帐户：Set [Account]）最终案例类Account（id：Long，名称：String，角色：Set [Role]，别名：Set [String]）密封的特征Role对象Role {case对象Admin扩展Role案例对象用户扩展角色案例对象离线扩展角色}
val结果= doStuff（…）val帐户=结果.accounts .toVector .sortBy（_ .id）assertEqual（accounts .length，3）assertEqual（accounts（0），Account（2，＆＃34; David＆＃34;，设置（角色.Admin，角色.User），设置（＆＃34; Baz＆＃34;，＆＃34; Bazza＆＃34;，＆＃34; Dave＆＃34;，＆＃34; Davo＆＃34;）） ）assertEqual（帐户（1），帐户（7，＆＃34; Bob＆＃34;，设置（角色.User），设置.empty）））assertEqual（帐户（2），帐户（13，＆＃34; John＆＃ 34;，Set（角色.User，Role .Offline），Set（＆＃34; Jono＆＃34;，＆＃34; Johnny＆＃34;）））
您一次只能获得一部分故障。也许“ 4不是3”，或者当您有多个帐户时，一个帐户可能会失败
如果缺少“ Davo”，则很难从结果中准确说明帐户出了什么问题，对于更大的数据更是如此
如果更改数据结构，则必须更改每个测试。想象一下在编写第51个测试用例时，您需要将Set [Role]更改为一个名为Roles的新类。这50个测试包含需要手动更新的“谁知道多少次数”的情况。
而是要宠爱自己和您的团队。花一两个小时对自己好一点。您将要编写许多测试，因此请尽可能轻松地做到以下几点：
在上面的示例中，我们将编写一个通过执行以下操作将Result转换为String的函数：
将Set [Role]表示为Admin，User和Offline的auo标志；就像在Linux中如何拥有rwx权限
另外，如果您的测试库不能很好地处理多行字符串，请找到一个能很好处理的字符串。理想情况下，当两个多行字符串不匹配时，您希望看到彩色的并排比较。
def assertResult（实际：结果，期望：字符串）：单位= assertEqual（formatForTests（实际），期望.trim）val结果= doStuff（…）def Expect =＆＃34;＆＃34;＆＃34;＃2）大卫[au-] |别名： -巴兹| -Bazza | -戴夫| -达沃| |＃7）鲍勃[-u-] | |＃13）约翰[-uo] |别名： -Jono | -约翰尼＆＃34;＆＃34;＆＃34; .stripMarginassertResult（结果，期望值）
现在进行单元测试，编写所有您通常会执行的测试，如果需要的话，请付出相似的努力以尽可能轻松地生成测试输入。为您能想到的每一个有问题的数据组合编写一个测试。添加注释，说明组合为什么会出现问题，因为这种组合并不总是很明显。
一旦您通过所有的痛苦和痛苦使所有的单元测试都通过了，就该进行下一步了：属性测试。
如果您不知道什么是“性能测试”，请进行搜索，因为它是一种宝贵的工具。它可以改变生活。
考虑一下结果数据应该满足的所有属性（即不变式）。我发现，像编译器一样的代码考虑属性比通常的常规代码要容易得多，这可能是因为该领域非常重视数据和数据关系。
别名绝不能与另一个用户的名字相同（也许代码应将其过滤掉）
如果您要处理的是图表而不是列表，那么通常是每个节点应遵循的属性（相对于其子节点或父节点）。
确保您的属性测试库能够重现其测试。每次发现故障时，提取数据并将其添加为单元测试。我的OSS Nyaya库具有一个称为Bug-hunt的功能，可以让我告诉它“嘿，从种子x开始在m个线程上运行n个测试，每个种子一个测试。”当我在使用上述ShipReq功能时，它发现了很多问题，通常是在30秒内，直到最终运行了一两个小时而没有发现我不能保证我的代码中仍然没有疯狂的错误，但是通过所有的单元测试以及数小时的系统测试，我至少可以放心，它在数学上是不可能的。这是您将付出的最大努力。
您也可以付出不合理的努力，如果愿意的话，可以走得更远！您可以尝试编写正式的，可机器验证的证明。获得验证的证明后，您可以保证自己的逻辑在所有情况下都可以正常工作，而不会出现任何意外错误（假设您正确实施了经过验证的逻辑）。尽管这是我们所有人都希望得到的结果，但它几乎不可行，因为它可能需要花费多年的时间才能完成。
Scala就是一个有趣的例子，它已经存在了很多年了，并且多年来社区中遇到了许多错误。如今，由于编译器错误的不断努力，它很少遇到编译器错误。即将到来的Scala 3的最令人振奋的事情之一是，经过多位博士生近10年的工作，Scala语言的基础已得到正式证明。甚至还不是全部的语言。例如，更高种类的类型和子类型之间的交互仍然是一个开放的研究问题。任何试图同时包含这两个功能的语言都将面临这样的问题：我们永远不会真正知道是否还有任何剩余的错误，并且在得到证明之前，我们只会知道添加到语言测试套件中的所有内容都可以正常工作。我喜欢Scala拥有所谓的“社区构建”，它可以编译和测试数百个（或大约）最流行的OSS Scala库和框架。这是捕捉回归的好方法。但是我现在真的离题了。关键是：形式证明=非常困难。
我还要提到的是，您可以使用TLA +来获得证明，但花费的精力要少得多。您基本上可以构建一个非常抽象的状态机，它将通过测试所有可能的组合来蛮力地证明它。在非常特殊的情况下，这真是天赐良机无论边缘情况多么罕见，TLA +都会找到它;通常在几秒钟之内。我将其与ShipReq结合使用，以确保最终的一致性之类的事情，并确保用户永远不会看到过时的数据。您可能要花几天时间并最终保证您的逻辑在所有可能的情况下都适用。虽然在验证类似编译器的代码，但我还没有尝试过，您可能不得不坐下来思考如何以一种兼容且有效的方式对逻辑建模非常非常困难。状态空间可能会可能确实可行，这取决于您在做什么，因此我至少建议考虑一下。
我还有其他遗漏吗？很抱歉，如果我提出的解决方案有点过时了。如果您能想到我真的很想知道的其他解决方案，请在Reddit或HackerNews评论中让我和其他读者知道！ 我之所以想写此书，有几个原因。我听说编译器作者说写一个co ......
