Embedding by Unembedding
Embedding by Unembedding
复制标题
通过取消嵌入进行嵌入
DOI：
10.1145/3607830
复制
发表时间：
2023
影响因子：
--
通讯作者：
Matsuda K
中科院分区：
文献类型：
--
作者：
Matsuda K
< jats: p>嵌入是一种语言开发技术，它将对象语言实现为宿主语言中的库。这种方法有许多优点，包括轻量级和继承宿主语言特性的能力。一个值得注意的例子是HOAS技术，它使用高阶函数来表示具有绑定器的抽象语法树。尽管HOAS很受欢迎，但它也有其局限性。我们观察到，HOAS的斗争与语义域，不能自然地表示为功能，特别是当开放的表达式涉及。这方面的突出例子包括增量计算和可逆/双向语言。在本文中，我们针点HOAS所面临的挑战，主机和对象语言功能的语义域之间的不匹配，并提出了一个解决方案。该解决方案是基于unembedding技术< jats: italic>，从最终无标记表示转换为具有强正确性保证的de Bruijn索引项。我们表明，这种方法是能够扩展HOAS的适用性，同时保持其优雅。我们提供了一个通用的策略，通过Unembedding嵌入，然后证明其有效性与增量计算和双向变换领域的两个实质性的案例研究。由此产生的嵌入式实现在功能上可以与相应领域中最先进的语言实现相媲美。
< jats: p> Embedding is a language development technique that implements the object language as a library in a host language. There are many advantages of the approach, including being lightweight and the ability to inherit features of the host language. A notable example is the technique of HOAS, which makes crucial use of higher-order functions to represent abstract syntax trees with binders. Despite its popularity, HOAS has its limitations. We observe that HOAS struggles with semantic domains that cannot be naturally expressed as functions, particularly when open expressions are involved. Prominent examples of this include incremental computation and reversible/bidirectional languages. In this paper, we pin-point the challenge faced by HOAS as a mismatch between the semantic domain of host and object language functions, and propose a solution. The solution is based on the technique of< jats: italic> unembedding, which converts from the finally-tagless representation to de Bruijn-indexed terms with strong correctness guarantees. We show that this approach is able to extend the applicability of HOAS while preserving its elegance. We provide a generic strategy for Embedding by Unembedding, and then demonstrate its effectiveness with two substantial case studies in the domains of incremental computation and bidirectional transformations. The resulting embedded implementations are comparable in features to the state-of-the-art language implementations in the respective areas.
登录
查看更多内容
微分 Lambda 演算
DOI：
--
发表时间：
2003
期刊：
影响因子：
--
作者：
T. Ehrhard;L. Regnier
通讯作者：
L. Regnier
优化纯函数式 GPU 程序
DOI：
10.1145/2500365.2500595
发表时间：
2013
期刊：
Proceedings of the 18th ACM SIGPLAN international conference on Functional programming
影响因子：
--
作者：
T. L. McDonell
通讯作者：
T. L. McDonell
同上
DOI：
--
发表时间：
--
期刊：
Journal of the Royal Asiatic Society of Great Britain & Ireland
影响因子：
--
作者：
Fahad R. Dogar;Amar Phanishayee;Himabindu Pucha;Olatunji Ruwase;D. Andersen
通讯作者：
D. Andersen
封闭数据库视图的基于顺序的更新理论
影响因子：
1.2
作者：
S. Hegner
通讯作者：
S. Hegner
DOI：
10.1007/978-3-030-45231-5_17
发表时间：
2020-04-17
期刊：
Foundations of Software Science and Computation Structures
影响因子：
--
作者：
Huot M;Staton S;Vákár M
通讯作者：
Vákár M