Deductive Programming Synthesis
Abstract
Some of the most efficient numerical algorithms rely on a binary- search strategy; according to this strategy, the interval in which the desired output is sought is divided roughly in half at each iteration. This technique is so useful that some authors have proposed that a general binary-search paradigm or schema be built into program synthesis systems and then specialized as required for particular applications. It is certainly valuable to store such schemata if they are of general application and difficult to discover. This approach, however, leaves open the question of how schemata are discovered in the first place. We have found that the concept of binary search appears quite naturally and easily in the derivations of some numerical programs. The concept arises as the result of a single resolution step, between a goal and itself, using our deductive-synthesis techniques. Keywords: Computer programming; Algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1989
- Accession Number
- ADA206451
Entities
People
- Zohar Manna
Organizations
- Stanford University