Browse Prior Art Database

AN ENVIRONMENT FOR MULTIPLE-VALUED RECURSIVE PROCEDURES

IP.com Disclosure Number: IPCOM000148912D
Original Publication Date: 1975-Oct-31
Included in the Prior Art Database: 2007-Mar-30
Document File: 22 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Friedman, Daniel P.: AUTHOR [+3]

Abstract

Daniel P. Frledman David S. Wise Computer Science Department Indiana University Bloomington, Indiana 47401 Research reported herein was supported (in part) by the National Science Foundation under grant no. DCR~~-06678and 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-valuedprocedure which recurses dihectly on itself. "Listsf' of functions, 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

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 22

AN ENVIRONMENT FOR MULTIPLE-VALUED RECURSIVE PROCEDURES

Daniel P. Frledman

David S. Wise

Computer Science Department
Indiana University

Bloomington, Indiana 47401

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

Science Foundation under grant no. DCR~~-06678
and no. MCS75-08145.

To be presented at the 2nd Symposium on Programming (Paris, 1976).

-

[This page contains 1 picture or other non-text object]

Page 2 of 22

[This page contains 1 picture or other non-text object]

Page 3 of 22

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-valuedprocedure which recurses dihectly on itself. "Listsf'
of functions, 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
enhanced recursive language. Several examples of purely recursive
code illustrate its power, including one on coroutining and one on
batch searching.

INTRODUCTION

    The importance of functions (procedures) in programming has been
demonstrated by several languages which depend solely on function or
macro 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 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 those 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 functions can be used
to rebind elements of that structure to individu...