We introduce a linear infinitary -calculus, called ℓ, in which two exponential modalities are available, the first one being the usual, finitary one, the other being the only construct interpreted coinductively. The obtained calculus embeds the infinitary applicative -calculus and is universal for computations over infinite strings. What is particularly interesting about ℓΔ, is that the refinement induced by linear logic allows to restrict both modalities so as to get calculi which are terminating inductively and productive coinductively. We exemplify this idea by analysing a fragment of ℓ built around the principles of SLL and 4LL. Interestingly, it enjoys confluence, contrarily to what happens in ordinary infinitary -calculi.
Dal Lago, U. (2016). Infinitary Lambda Calculi from a Linear Perspective. IEEE [10.1145/2933575.2934505].
Infinitary Lambda Calculi from a Linear Perspective
DAL LAGO, UGO
2016
Abstract
We introduce a linear infinitary -calculus, called ℓ, in which two exponential modalities are available, the first one being the usual, finitary one, the other being the only construct interpreted coinductively. The obtained calculus embeds the infinitary applicative -calculus and is universal for computations over infinite strings. What is particularly interesting about ℓΔ, is that the refinement induced by linear logic allows to restrict both modalities so as to get calculi which are terminating inductively and productive coinductively. We exemplify this idea by analysing a fragment of ℓ built around the principles of SLL and 4LL. Interestingly, it enjoys confluence, contrarily to what happens in ordinary infinitary -calculi.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.