Browse Prior Art Database

AN ENVIRONMENT FOR MULTIPLE-VALUED RECURSIVE PROCEDURES

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

Publishing Venue

Software Patent Institute

Related People

Daniel P. Friedman: AUTHOR [+4]

Abstract

'A problem with existing language provisions for programming procedures which return multiple results is the facility with which such results are passed along as arguments to other functions. We define the functional operation of combination which provides a method of using such multiple results conveniently, say, for writing a multi-valued procedure which recurses dixectty on itself. "Lists offunctions, called combinators, take lists of arguments and the length of the result is determined by the shortest of the combinator or its arguments. Notation is presented for constructing lists which are arbitrary repetitions of a single element so that one parameter can be "spread" across a combinator, or a single function can be spread into a combinator across lists as arguments. Finally, the provision of a functional application notation is introduced and shown to be a very important adjunct to the other features of our enhan ced recursive language. Several examples of purely recursive code illustrate its power, including one on coroutining and one on batch searching.

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

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN ENVIRONMENT FOR MULTIPLE-VALUED RECURSIVE PROCEDURES

Daniel P. Friedman David S. Wise

Computer Science Department Indiana University

Bloomington, Indiana 47401

TECHNICAL REPORT No. 40

AN ENVIRONMENT FOR MULTIPLE-VALUED RECURSIVE PROCEDURES

DANIEL P. FRIEDMAN DAVID S. WIESE

OCTOBER, 1975

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

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

To be presented at the 2nd Symposium on Programming (Paris, 1976). AN ENVIRONMENT FOR MULTIPLE-VALUED RECURSIVE PROCEDURES DANIEL P. FRIEDMAN DAVID S. WISE INDIANA UNIVERSITY

ABSTRACT

'A problem with existing language provisions for programming procedures which return multiple results is the facility with which such results are passed along as arguments to other functions. We define the functional operation of combination which provides a method of using such multiple results conveniently, say, for writing a multi-valued procedure which recurses dixectty on itself. "Lists offunctions, called combinators, take lists of arguments and the length of the result is determined by the shortest of the combinator or its arguments. Notation is presented for constructing lists which are arbitrary repetitions of a single element so that one parameter can be "spread" across a combinator, or a single function can be spread into a combinator across lists as arguments. Finally, the provision of a functional application notation is introduced and shown to be a very important adjunct to the other features of our enhan ced recursive language. Several examples of purely recursive code illustrate its power, including one on coroutining and one on batch searching.

INTRODUCTION

The importance offunctions (procedures) in programming has been demonstrated by several languages which depend solely on function or mac ro invocation to control computations. The central theme of this paper is enhancement of the standard treatment of functions. This enhancement not only facilitates multiple results from functions (i.e. multi-dimensioned range), as in LISP or APL, but also provides for the use of such a multiple-value as an argument to

Indiana University Page 1 Dec 31, 1975

Page 2 of 14

AN ENVIRONMENT FOR MULTIPLE-VALUED RECURSIVE PROCEDURES

other functions without requiring its explicit decomposition. The value of a function which returns- - a multiple result may,.be pictured as a fixe~ length vector in algebraic languages or as a list in list processing languages. If the language under consideration depends on function invocation for program control, then t-hose vectors or lists must be allowed as arguments, as well as results, for functional composition. When the multiple result of one function is to be an argument to the next, treatment of the formal parameter which represents the multiple result as a data structure of several results becomes necessary. Extra assignments or nested...