Browse Prior Art Database

MULTIPLE-VALUED RECURSIVE PROCEDURES

IP.com Disclosure Number: IPCOM000128021D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 13 page(s) / 39K

Publishing Venue

Software Patent Institute

Related People

Daniel P. Friedman: AUTHOR [+4]

Abstract

The. importance o.f functions (procedures) in programming has been'demonstrated by several languages which depend on function or macro invocation alone to control computations. The central theme of this paper is an enhancement of the standard treatment of functions. It not only provides multiple results from func-tions, as in LISP or APL, but also provides for use of such values, as arguments to functions without requiring their explicit decomposition. The value of a function which returns a multiple result may be structured as a vector in algebraic languages, or as a list in list processing languages. If the language under considera-tion depends on function inv ocation for program control, then those structures must be allowed as arguments, as well as re-sults, in order to allow functional composition. When the multi-ple result of one function is an argument to the next, convenient access into the structure holding several results is required. Extra assignments or nested functions may be used to rebind ele-ments of that structure to individual variables suitable for easy access by the next function, but such intervening overhead is confusing. The programmer bothered with unnecessary rebindings is morelikely to make mistakes., the reader of such a program is more likely to be confused; the compiler of such a program will likely generate less efficient code than would be possible if a standard access protocol were available. The immediate need for such a protocol arose from an ongoing project aimed at the development of a practical translator of 11stylized recursions" 151 into stackless iterations. Early in that project the decision to restrict the source language to the purer forms of recursion frustrated attempts at providing legal function definitions which could be translated to code similar to that'for common iterative programs which yield several re-sults. The strong equivalence between simple linear recursions and a FORTRAN style DO-loop 13,141 suggests that some stylized recursive code is just as simply related to a DO-loop which accumulates two disjoint results instead of one. The preimage of such an iteration under the translation being considered can be written with the tool of "functional combination" as intro-duced below. Functional combination is a scheme for weaving a new function from notionally parallel invocations of extant functions so that ,the structures of the parameters and of the results for the new function are determined by a fixed arrangement of those structures for the original functions. It is a version of the Cartesian pro-duct of functions in common use by algebraists [151 which is modi-fied to make the parameter-structure more similar t,o the structure of the result. It is this change which makes it a 'comfortable tool for expressing functions in a programming language.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

MULTIPLE-VALUED RECURSIVE PROCEDURES

Daniel P. Friedman David S. Wise

Computer Science Department Indiana University Bloomington, Indiana TECHNICAL REPORT NO@ 27

MULTIPLE-VALUED RECURSIVE PROCEDURES

DANIEL P. FRIEDMAN DAVID S. WISE

REVISED FEBRUARY, 1976

Research reported herein was supported (in part) by the National

Science Foundation under grant no. DCR75-o6678 and no. MCS75-08145.

Introduction

The. importance o.f functions (procedures) in programming has been'demonstrated by several languages which depend on function or macro invocation alone to control computations. The central theme of this paper is an enhancement of the standard treatment of functions. It not only provides multiple results from func-tions, as in LISP or APL, but also provides for use of such values, as arguments to functions without requiring their explicit decomposition.

The value of a function which returns a multiple result may be structured as a vector in algebraic languages, or as a list in list processing languages. If the language under considera-tion depends on function inv ocation for program control, then those structures must be allowed as arguments, as well as re-sults, in order to allow functional composition. When the multi-ple result of one function is an argument to the next, convenient access into the structure holding several results is required. Extra assignments or nested functions may be used to rebind ele- ments of that structure to individual variables suitable for easy access by the next function, but such intervening overhead is confusing. The programmer bothered with unnecessary rebindings is morelikely to make mistakes., the reader of such a program is more likely to be confused; the compiler of such a program will likely generate less efficient code than would be possible if a standard access protocol were available. The immediate need for such a protocol arose from an ongoing project aimed at the development of a practical translator of 11stylized recursions" 151 into stackless iterations. Early in that project the decision to restrict the source language to the purer forms of recursion frustrated attempts at providing legal function definitions which could be translated to code similar to that'for common iterative programs which yield several re-sults. The strong equivalence between simple linear recursions and a FORTRAN style DO-loop 13,141 suggests that some stylized recursive code is just as simply related to a DO-loop which accumulates two disjoint results instead of one. The preimage of such an iteration under the translation being considered can be written with the tool of "functional combination" as intro- duced below.

Functional combination is a scheme for weaving a new function from notionally parallel invocations of extant functions so that

Indiana University Page 1 Dec 31, 1976

Page 2 of 13

MULTIPLE-VALUED RECURSIVE PROCEDURES

,the structures of the par...