Browse Prior Art Database

FUNCTIONAL COMBINATION

IP.com Disclosure Number: IPCOM000148916D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2007-Mar-30

Publishing Venue

Software Patent Institute

Related People

Friedman, Daniel P.: AUTHOR [+3]

Abstract

Daniel P. Friedman David S. W i s e

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 20% of the total text.

Page 1 of 16

FUNCTIONAL COMBINATION
Daniel P. Friedman

David S. W i s e

Computer Science Department

   Indiana University
Bloomington, Indiana 47401

TECHNICAL REPORT No, 27 FUNCT I

ONAL COMB INATI ON

 DANIEL PI FRIEDMAN DAVID S, WISE REVISED DECEMBER, 1976

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

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

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

Page 2 of 16

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

Page 3 of 16

Functional Combination*

Daniel P. Friedrnan
David S. Wise

Computer Science Department
Indiana University
Bloomington, Indiana 47401

Abstract - The algebraic functional operation of combination is introduced as a programming tool. It has a practical semantic interpretation in building functions which return several re- sults, especially when such functions are directly recursive. Example functions are given whose invocations build multiple results from single recursions, including a new algorithm for batch-probing binary search trees from an unordered list of keys which returns an ordered list of hits.

Keywords and Phrases - recursive procedures, lists, multiple- valued function, LISP, batch-probing, binary trees.

CR Categories - 4.22, 4.12, 3.74.

*Research reported herein was supported (in part) by the National Science Foundation under grant no. DCR75-06678 and no. ~cS75-08145.

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

Page 4 of 16

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

Page 5 of 16

Introduction
This note advances the concept of functional combination as

an important tool for (side-effect free) applicative programming. We have presented the idea elsewhere [ 2 , 31 more completely, imbed-

ded with other recent results in applic!ative, particularly pure

LISP, programming. Moreover, the idea itself is not new [l, 71

although it has not, to our knowledge, been imbedded in a practical programming language.

    The problem we address is that of writing a recursive function which returns more than one result. Using the classic factorial recursion as a model, one may observe that recursive functions often contribute something t o the answer on each recursion; in factorial it's another factor. We would like t o write similar functions
which return several such results, each with a contribution from every level of the recurrence.

    There are three classic solutions for specifying multiple-valued recursive procedures, none of which meet our demands for style.

The first is not even permissible in applicative programming since
it requires an assignment to a global (or COMMON) variable or to a parameter called by reference. Additional results may be extracted from recursive functions by communicating them t o the calling envi- ronment in channels independent of the Punctions' results, but that is not po...