Browse by author
Lookup NU author(s): Dr Christopher Holt
Within a domain of functions such as the lambda calculus, every application of a function to an argument can be associated with a time interval. Time is a length attribute, since the time of a vertical composition is bounded by the sum of the times of its components, while the time of a horizontal composition is bounded by the maximum of the times of its components (assuming sufficient resources). These bounds can be reduced by optimization, e.g. for constant functions and alternative selection (defined as a first-past-the-post filter). The composition of applications into structures leads more naturally to lattices than the trees of conventional functional programming; lattices conform to the single argument and result format of monadic functions, and can be associated with single time attributes. The state transformation approach of imperative programming can be viewed as horizontal decomposition of a lattice, while processes can be viewed as vertical decomposition into paths linked by communications. The observation of execution of a program is defined as the introduction of an extra path that has access to information about the applications it goes through. The observer's path may introduce additional ordering into the program; thus an omniscient observer yields a total order. The history of an evaluation consists of those applications that have generated results; when these are viewed as open sets, a topology is induced that is between To and T2. The topological notions of nestedness and sobriety have computational significance, capturing the distinction between the set of possible histories and any given history, and the difference between allowing finite vs. infinite branching.
Author(s): Holt CM
Publication type: Report
Publication status: Published
Series Title: Computing Laboratory Technical Report Series
Year: 1989
Pages: 24
Print publication date: 01/11/1989
Source Publication Date: November 1989
Report Number: 299
Institution: Computing Laboratory, University of Newcastle upon Tyne
Place Published: Newcastle upon Tyne
URL: http://www.cs.ncl.ac.uk/publications/trs/papers/299.pdf
