A Linear Spine Calculus

From MaRDI portal





The linear \(\lambda\)-calculus \(\lambda^{\to \multimap \& \top}\) is an interesting system which has unrestricted as well as linear contexts and unrestricted and linear versions of the ``\(\ldots\) is a term of type \(\ldots\) relation. It also has pairing operators and an ``additive unit \(\top\). \(\lambda^{\to \multimap \& \top}\) is used in systems for symbolic computation, such as theorem provers, and logic programming languages. The extra features however make implementation much less efficient than for \(\lambda^{\to }\). The authors introduce the spine calculus \(S^{\to \multimap \& \top}\) and show that there are sound and complete translations of this to and from \(\lambda^{\to \multimap \& \top}\). The spine calculus allows more efficient implementation of critical procedures such as unification. The typable fragment of the spine calculus is shown to be strongly normalizing and has unique \(\beta \eta\)-normal forms.




Cited in
(24)


Describes a project that uses

Uses Software






This page was built for publication: A Linear Spine Calculus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4444935)