Circular programs and self‐referential structures

L Allison - Software: Practice and Experience, 1989 - Wiley Online Library
Software: Practice and Experience, 1989Wiley Online Library
A circular program creates a data structure whose computation depends upon itself or refers
to itself. The technique is used to implement the classic data structures circular and doubly‐
linked lists, threaded trees and queues, in a functional programming language. These
structures are normally thought to require updateable variables found in imperative
languages. For example, a functional program to perform the breadth‐first traversal of a tree
is given. Some of the examples result in circular data structures when evaluated. Some …
Abstract
A circular program creates a data structure whose computation depends upon itself or refers to itself. The technique is used to implement the classic data structures circular and doubly‐linked lists, threaded trees and queues, in a functional programming language. These structures are normally thought to require updateable variables found in imperative languages. For example, a functional program to perform the breadth‐first traversal of a tree is given. Some of the examples result in circular data structures when evaluated. Some examples are particularly space‐efficient by avoiding the creation of intermediate temporary structures which would otherwise later become garbage. Lastly, the technique can be applied in an imperative language to give an elegant program.
Wiley Online Library