A dependently typed calculus with pattern matching and erasure inference
A dependently typed calculus with pattern matching and erasure inference
复制标题
具有模式匹配和擦除推理的依赖类型演算
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Matus Tejiscak
中科院分区：
文献类型：
--
作者：
Matus Tejiscak
依赖类型程序的某些部分构成其类型正确性的证据，一旦检查，就不需要执行了。这些部分很容易变得比剩余的运行时有用的计算大得多，这可能会导致正常的线性时间程序以指数时间运行，甚至更糟。我们不应该仅仅通过更准确地描述程序来使程序运行得更慢。当前依赖类型的系统不能令人满意地消除这种计算。通过通过类型性宇宙或无关性间接模拟擦除，他们强加了这些方法的局限性来进行擦除。于是，一些无用的计算就不能被删除，惯用的程序仍然是渐近次优的。在本文中，我们解释了为什么我们需要擦除，它不同于其他概念，如无关性，并提出了一个依赖类型演算模式匹配和擦除注释来建模它。我们证明，在类型良好的程序中，擦除是合理的，因为它与缩减互换。假设丘奇-罗瑟性质，擦除进一步保留了一般的可兑换。我们还给出了删除未注释或部分注释程序的删除推理算法，并证明了该算法的可靠性、完备性和相对于微积分的类型规则的最优性。最后，我们证明了这种擦除方法是有效的，因为它不仅可以恢复编译程序在运行时预期的渐近复杂性，而且可以缩短编译时间。
Some parts of dependently typed programs constitute evidence of their type-correctness and, once checked, are unnecessary for execution. These parts can easily become asymptotically larger than the remaining runtime-useful computation, which can cause normally linear-time programs run in exponential time, or worse. We should not make programs run slower by just describing them more precisely. Current dependently typed systems do not erase such computation satisfactorily. By modelling erasure indirectly through type universes or irrelevance, they impose the limitations of these means to erasure. Some useless computation then cannot be erased and idiomatic programs remain asymptotically sub-optimal. In this paper, we explain why we need erasure, that it is different from other concepts like irrelevance, and propose a dependently typed calculus with pattern matching with erasure annotations to model it. We show that erasure in well-typed programs is sound in that it commutes with reduction. Assuming the Church-Rosser property, erasure furthermore preserves convertibility in general. We also give an erasure inference algorithm for erasure-unannotated or partially annotated programs and prove it sound, complete, and optimal with respect to the typing rules of the calculus. Finally, we show that this erasure method is effective in that it can not only recover the expected asymptotic complexity in compiled programs at run time, but it can also shorten compilation times.
Haskell 中依赖类型的规范
影响因子：
--
作者：
Weirich, Stephanie;Voizard, Antoine;de Amorim, Pedro Henrique;Eisenberg, Richard A.
通讯作者：
Eisenberg, Richard A.