Browse Prior Art Database

Automatic Compilation of Logical Specifications into Efficient Programs

IP.com Disclosure Number: IPCOM000128666D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 10 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

Donald Cohen: AUTHOR [+3]

Abstract

We describe an automatic programmer, or "compiler" which accepts as input a predicate calculus specification of a set to generate or a condition to teat, along with a description of the underlying representation of the data. This compiler searches a space of possible algorithms for the one that is expected to be most efficient. We describe the knowledge that is and is not available to this compiler, and its corresponding capabilities and limitations. This compiler is now regularly used to produce large programs.

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

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Automatic Compilation of Logical Specifications into Efficient Programs

Donald Cohen

ISI Research Report ISIIRS-86-175 November 1986 University of Southern California Reprinted from the AAAI-86, Proceedings of the 5th National Conference on Artificiallntelligence, held August 11-15, 1986 in Philadelphia, PA. INFORMATION SCIENCES INSTITUTE 2131822-1511

4676 Admiralty Way/Marina del Rey/California 90292-6695 This research is supported by the Defense Advanced Research Projects Agency under Contract No. MDA903 81 C 0335_ Views and conclusions contained in this report are the authors' and should not be interpreted as representing the official opinion or policy of DARPA,the U.S. Government, or any person or agency connected with them.

ISl Reprint Series This report is one in a series of reprints of articles and papers written by ISI research staff and published in professional journals and conference proceedings. For a complete list of ISI reports, write to

Document Distribution USC/Information Sciences Institute

4676 Admiralty Way Marina del Rey, CA 90292-6695 USA Automatic Compilation of Logical Specifications into Efficient Programs Donald Cohenf U.S.C. Information Sciences institute

4876 Admiralty Way Marina del Rey, Ca. 80282

Abstract

We describe an automatic programmer, or "compiler" which accepts as input a predicate calculus specification of a set to generate or a condition to teat, along with a description of the underlying representation of the data. This compiler searches a space of possible algorithms for the one that is expected to be most efficient. We describe the knowledge that is and is not available to this compiler, and its corresponding capabilities and limitations. This compiler is now regularly used to produce large programs.

1. Introduction

This work is motivated by a desire to help programmers do their job better, I.e., more easily and quickly create and modify programs that are more efficient, correct and understandable. Our approach follows the weft-travelled route of supplying a "higher level language" which allows a programmer to say more of what he wants the machine to do and less of the details of how h (s to be done. This leads to programs that are shorter, easier to understand and modify, and contain fewer bugs. However, higher level languages tend to degrade efficiency, since their compilers fail to make many optimizations that a human might make. In fact, some optimizations cannot even be expressed to the higher level language. Our higher level language, nPs, is an extension of lisp in which programs can be written with much less commitment to particular algorithms or data representations. This is a benefit to the degree (which we believe is quite large) that programmers spend their effort dealing with these issues. One way to avoid thinking

University of Southern California Page 1 Dec 31, 1986

Page 2 of 10

Automatic Compilation of Logical...