Program Calculation Properties of Continuous Algebras

Share/Save/Bookmark

Fokkinga, Maarten M. and Meijer, Erik (1991) Program Calculation Properties of Continuous Algebras. [Report]

[img]
Preview
PDF
334Kb
Abstract:Defining data types as initial algebras, or dually as final co-algebras, is beneficial, if not indispensible, for an algebraic calculus for program construction, in view of the nice equational properties that then become available. It is not hard to render finite lists as an initial algebra and, dually, infinite lists as a final co-algebra. However, this would mean that there are two distinct data types for lists, and then a program that is applicable to both finite and infinite lists is not possible, and arbitrary recursive definitions are not allowed. We prove the existence of algebras that are both initial in one category of algebras and final in the closely related category of co-algebras, and for which arbitrary (continuous) fixed point definitions ("recursion") do have a solution. Thus there is a single data type that comprises both the finite and the infinite lists. The price to be paid, however, is that partiality (of functions and values) is unavoidable.
We derive, for any such data type, various laws that are useful for an algebraic calculus of programs.
Item Type:Report
Copyright:© 1991 CWI
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66626
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page