Tail recursion through universal invariants
type: Item
instance of: scholarly article
title: Tail recursion through universal invariants
zbMATH Open document ID: 0779.68057
DOI: 10.1016/0304-3975(93)90059-3
published in: Theoretical Computer Science
publication date: 1994-01-23T00:00:00Z
review text: Although initial algebra semantics are a powerful denotational tool, they yield programs based on primitive recursion. Tail-recursion is only derived by further, post hoc optimisation. As an alternative to the usual initial list objects, this paper introduces the convergent list objects. The two semantics are shown to be equivalent, but the latter yields tail-recursive programs directly and systematically. The unfolding of a tail-recursive program yields a loop or endomorphism, whose iteration is captured by its categorical colimit, or universal invariant. If the loop converges (roughly speaking, its universal invariant is its fixed object) then this invariant is the semantics of the original program. A list candidate is a convergent list object if all the necessary loops converge.
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 417340
zbMATH Keywords: recursion
zbMATH Keywords: convergent list objects
zbMATH Keywords: loop
zbMATH Keywords: universal invariant
author: Barry Jay
reviewed by: Barry Jay
MaRDI profile type: Publication
full work available at URL: 0304-3975(93)90059-3
OpenAlex ID: W2029006139
cites work: *-Autonomous categories and linear logic
cites work: Q3682648
cites work: Q3767474
cites work: List-arithmetic distributive categories: Locoi
cites work: Q3137150
cites work: Q3999206
cites work: Coalgebras and cartesian categories
cites work: A note on natural numbers objects in monoidal categories
cites work: Q3978976
cites work: Q4282576
cites work: An imperative language based on distributive categories II
cites work: Q3934579
cites work: Q3138542
cites work: Q4100671
cites work: Monads on symmetric monoidal closed categories
cites work: A fixpoint theorem for complete categories
cites work: Q4206923
cites work: Q3727946
cites work: Adjointness in Foundations
cites work: Metric spaces, generalized logic, and closed categories
cites work: Q4367604
cites work: Q5639839
cites work: Q3946206
cites work: Q3202991
cites work: Categorical fixed point semantics
cites work: Monoidal categories with natural numbers object
cites work: Cartesian categories with natural numbers object
cites work: Categories of partial maps
cites work: Q3827993
cites work: The Category-Theoretic Solution of Recursive Domain Equations
cites work: Data types in distributive categories
description: scientific article; zbMATH DE number 417340