Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

TECHNIQUES FOR THE AUTOMATIC SELECTION OF DATA STRUCTURES

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

Publishing Venue

Software Patent Institute

Related People

James Low: AUTHOR [+4]

Abstract

to our methods and an overview of the selection system. The second contains a discussion of__our recent cork on auto- matic of associative data structures. An appendix contains detailed examples of this work.

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

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

TECHNIQUES FOR THE AUTOMATIC SELECTION OF DATA STRUCTURES

James Low and Paul Rovner Computer Science Department The University of Rochester

TR4 w TECHNIQUES FOR THE AUTOMATIC SEl_ECTIO's OF DATA STRUCTURES

James Low and Paul Rorer Computer Science Department University of Rochester Rochester, New York 14627

We are a71 aware of the development- o f in- creasingly sophisticated, elaborate, and expensive computer programsprograms, particularly in the fields of artificial intelligence, data base canagei-:en t, and intelligent systems. The teed for techniques to deal with such complexity has renewed interest in programming language research. Recent work on. structured programming, intelligent com.pilers, automatic program generation and verification, and high-Ieve7.optimization has resulted. .

A pattern of approach similar to that of ear= tier research on programming languages is emerging. The work di vi des naturally into tyro parts: the search for good linguistic-tools for expressing algorithms and data, and .the Bevel opmen t of prac-tical methods for 'translating these to working computer programs. Our emphasis in this paper is in the latter. t _.

For programs that are inherently complex and expensive, the intelligent choice o f i np7 ez=n ta- tion-1eve7 representations for high-'level data is a central problem. This paper contains a dis- cession of several powerfu7 techniques for automating such intelligent choices for a given program. Flow analysis, execution monitoring, and interactive sessions about tie characteristics of the problem are' are*considered. Built-in knowl- edge for a collection of data structures is assumed.. For each data structure, this includes rules about its applicability and formulas for its memory space and execution time requires:=nts as functions of the properties of the data and the operations of the program.' _2_

The context for the discussion is an ex-' perimental system [Low74, Rovner76j- which chooses data structures and algorithms for sets, lists, and associations in the ALGOL-60 based programs- ming language SAIL [VanLehn73J. (A brief des- cription of SAIL is contained in Appendix I_) Similar abstract data structures are to be found m other experimental prograr.~irg lan- I uages, including QA4 Derksen721, 14ICRO-PLAf;i:EP Sussman70, 8aumgart72~, SETL [Schvrartz7S E , tVI,BCAP Morris731 , VERS2 [Earley73] and CON't-111VER ussman72, McDermott72~ .

This caper i s organized i n taro parts. The first comprises an introduction to our methods and an overview of the selection system. The second contains a discussion of__our recent cork on auto- matic of associative data structures. An appendix contains detailed examples of this work.

System Overview .

The selection system is based on the premise that there are many different ways of representing -the sets,' lists, and triples of a user's program. A fixed library of such representations is bui...