Recursion from cyclic sharing:
traced monoidal categories and models of cyclic lambda calculi
Masahito Hasegawa
In
Proc. 3rd International Conference on Typed Lambda Calculi and Applications
(TLCA'97), Springer LNCS 1210 (1997) 196-213
Abstract
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 recently introduced 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, which are shown to be sound and complete for
the cyclic lambda calculi, 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 then serves as a uniform language
for this wider range of models of recursive computation.
Pointers to Related Work
-
Z. M. Ariola and S. Blom,
Cyclic lambda calculi.
In Proc. TACS'97, Springer LNCS 1281 (1997) 77-106.
- R.F. Blute, J.R.B. Cockett and
R. A. G. Seely,
Feedback for linearly distributive categories:
traces and fixpoints.
To appear in Journal of Pure and Applied Algebra.
- M. Hasegawa,
Models of Sharing Graphs
(A Categorical Semantics of Let and Letrec).
PhD thesis ECS-LFCS-97-360, University of Edinburgh (1997).
- A. Jeffrey,
Premonoidal categories and a graphical view of programs.
Manuscript (1998).
- A. Joyal, R. Street and D. Verity,
Traced monoidal categories.
Mathematical Proceedings of the Cambridge Philosophical Society
119(3) (1996) 447-468.
- E. Moggi,
Computational lambda-calculus and monads.
Technical report ECS-LFCS-88-66, University of Edinburgh (1988).
- E.P. Robinson and A.J. Power,
Premonoidal categories and notions of computation.
Mathematical Structures in Computer Science 7(5) (1997) 453-468.
Back to Hassei's
Research Page / Home Page