Recursion from Cyclic Sharing: Traced Monoidal Categories and Models of Cyclic Lambda Calculi
Recursion from Cyclic Sharing: Traced Monoidal Categories and Models of Cyclic Lambda Calculi
复制标题
循环共享的递归：循环 Lambda 演算的追踪幺半群范畴和模型
DOI：
10.1007/3-540-62688-3_37
复制
发表时间：
1997
影响因子：
--
通讯作者：
Masahito Hasegawa
中科院分区：
文献类型：
--
作者：
Masahito Hasegawa
循环共享（循环图重写）已被用作有效实现递归计算的实用技术。为了捕捉它的语义性质，我们介绍了分类模型lambda演算与循环共享（循环lambda图），使用的概念计算的Moggi/Power和罗宾逊和跟踪monoidal类Joyal，街和Verity。前者用于表示共享的概念，而后者用于循环数据结构。我们的新模型为理解从循环共享创建的递归提供了一个语义框架，其中包括从不动点创建的递归的传统模型作为特例。我们的循环lambda演算作为一个统一的语言，这种更广泛的递归计算模型。
Cyclic sharing (cyclic graph rewriting) has been used as a practical technique for implementing recursive computation efficiently. To capture its semantic nature, we introduce categorical models for lambda calculi with cyclic sharing (cyclic lambda graphs), using notions of computation by Moggi/Power and Robinson and traced monoidal categories by Joyal, Street and Verity. The former is used for representing the notion of sharing, whereas the latter for cyclic data structures. Our new models provide a semantic framework for understanding recursion created from cyclic sharing, which includes traditional models for recursion created from fixed points as special cases. Our cyclic lambda calculus serves as a uniform language for this wider range of models of recursive computation.