Browse Prior Art Database

RECURSIVE PROGRAMMING THROUGH TABLE LOOK-UP

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

Publishing Venue

Software Patent Institute

Related People

Daniel P. Friedman: AUTHOR [+5]

Abstract

The maintenance of arbitrarily large tables of previously computed values for functions on integer domains becomes practical 'when those tables are built using constructor functions which suspend evaluation of their arguments. Two styles of programming with such tables are presented. The first results from replacing recursive invocations within standard recursive function definitions with a reference into a table which is predefined to be all the possible results of the function. The second.,, more sophisticated, style requires that the table be defined strictly through a generation scheme. In either case the table may be available to the user as a data structure exclusive of the function definition with entries still being,manifested only when they are actually used. Keywords and Phrases - suspended evaluation, generation, streams, infinite lists, dynamic owns., LISP. CR Categories _' 4.13, 4.22, 5.7, 4.12 *Research reported herein was supported (in part) by the National Science Foundation under grant no. DCR75-06678 and no. MCS75-o8145-

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

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

RECURSIVE PROGRAMMING THROUGH TABLE LOOK-UP*

Daniel P. Friedman David S. Wise Mitchell Wand Computer Science Department Indiana University Bloomington, Indiana 47401

TECHNICAL REPORT No. 45

RECURSIVE PROGRAMMING THROUGH TABLE LoOK-UP DANIEL P. FRIEDMAN DAVID S. WISE MITCHELL WAND MARCH, 1976

*Research reported herein was supported (in part) by the National Science Foundation under grant no. DCR75-06678 and no. MCS75-o8145. Recursive Programming through Table Look- up*

Daniel P. Friedman David S. Wise Mitchell Wand

Computer Science Department Indiana Un'versity Bloomington, fndiana

Abstract

The maintenance of arbitrarily large tables of previously computed values for functions on integer domains becomes practical

'when those tables are built using constructor functions which suspend evaluation of their arguments. Two styles of programming with such tables are presented. The first results from replacing recursive invocations within standard recursive function definitions with a reference into a table which is predefined to be all the possible results of the function. The second.,, more sophisticated, style requires that the table be defined strictly through a generation scheme. In either case the table may be available to the user as a data structure exclusive of the function definition with entries still being,manifested only when they are actually used.

Keywords and Phrases - suspended evaluation, generation, streams, infinite lists, dynamic owns., LISP.

CR Categories _' 4.13, 4.22, 5.7, 4.12

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

Introduction

The goal of this paper is to demonstrate that standard recursive definitions may easily be transformed to permit the specification of a table of arbitrary size. The table, built with "suicidal suspensions" [Friedman and Wise 1976 only manifests itself for values which have been explicitly used; these values remain easily accessible for later reuse. The values which are computed from an algorithm expressed in "top-down" recursive code are computed through a'j~ottom-up computation sequence which is time-optimal for that algorithm in the sense of

Indiana University Page 1 Dec 31, 1976

Page 2 of 9

RECURSIVE PROGRAMMING THROUGH TABLE LOOK-UP

Berry 119751. Such tables may also be specified by generating functions based on an unconventional formulation of traditional recurrence relations requiring the concept of a suspended'structure.

'The technique of purely recursive expression was popularized by McCarthy [19601 in the fundamentals of the language LISP, referred to here as pure LISP and elsewhere as LISP 1.0. As this language became more popular, different researchers with varying needs added more and more "enhancements" to the language; I notable versions, like LISP 1.5, LISP 1.6, MACLISP, and

1NTER_LIS? found their way into-common use. In this...