
Accession Number : ADA327435
Title : The Essence of Rum: A Theory of the Intensional and Extensional Aspects of LispType Computation,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Taylor, Carolyn L.
PDF Url : ADA327435
Report Date : AUG 1985
Pagination or Media Count : 250
Abstract : Rum is a theory of applicative, sideeffect free computations over an algebraic data structure. It goes beyond a theory of functions computed by programs, treating both intensional and extensional aspects of computation. Powerful programming tools such as streams, objectoriented programming, escape mechanisms, and coroutines can be represented. Intensional properties include the number of multiplications executed, the number of context switches, and the maximum stack depth required in a computation. Extensional properties include notions of equality for streams and coroutines and characterization of functionals implementing strategies for searching treestructured spaces. Precise definitions of informal concepts such as stream and coroutine are given and their mathematical theory is developed. Operations on programs treated include program transformations which introduce functional and control abstractions; a compiling morphism that provides a representation of control abstractions as functional abstractions; and operations that transform intensional properties to extensional properties. The goal is not only to account for programming practice in Lisp, but also to improve practice by providing mathematical tools for developing programs and building programming systems. Rum views computation as a process of generating computation structures  trees for contextindependent computations and sequences for contextdependent computations. The recursion theorem gives a fixedpoint function that computes computationally minimal fixed points. The context insensitivity theorem says that contextdependent computations are uniformly parameterized by the calling context and that computations in which context dependence is localized can be treated like contextindependent computations.
Descriptors : *COMPUTER PROGRAM VERIFICATION, *OBJECT ORIENTED PROGRAMMING, COMPUTATIONS, MATHEMATICAL PROGRAMMING, SUBROUTINES, COMPILERS, EXECUTIVE ROUTINES.
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE