Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    An Iterator Construct for the Refinement Calculus

    4th Irish Workshop on Formal Methods

    Maynooth, Ireland. 5th-6th July 2000


    S. King & C. Morgan


    This paper concerns the introduction of an iterator into the refinement calculus. The construct is based on concepts from functional programming, and the work gives an interesting example of cross-fertilisation between the functional and imperative programming worlds.

    Specifically, the iterator construct it..ti uses the idea of a catamorphism - the unique homomorphism from an initial algebra.

    The datatype for which the iterator is to be defined is considered as an initial algebra of an appropriate functor.

    The it..ti construct is formally defined as a recursive procedure, and it is shown that, if the value to be obtained by an iteration can be expressed as a catamorphism, then the it..ti construct provides a very natural implementation.

    Examples are given to show typical uses of the new construct.


    PDF filePDF Version of this Paper (165kb)