A Knowledge-Based Approach to Using Efficiency Estimation in Program Synthesis

A KNOWLEDGE-BASED APPROACH TO USING EFFICIENCY ESTIMATION IN PROGRAM SYNTHESIS

Elaine Kant' Artificial Intelligence Laboratory Stanford University Stanford, California 94305

This paper describes a system for using efficiency knowledge in program synthesis. The system, called LIBRA, uses a combination of knowledge-based rules and algebraic cost estimates to compare potential program Implementations. Efficiency· knowledge is used to control the selection of algorithm and data structure implementations and the 11pplicalion of optimizing transformations. Prototypes of programming constructs and of cost estimation techniques are used to simplify the efficiency analysis process and to assist in the acquisition of efficiency knowledge associated with new coding knowledge. LIBRA has been used to guide the selection of implementations for several proarams that classify, retrieve information, sort, and generate prime numbers.

I . INTRODUCTION

Efficiency consider111ions often Impose conflicting demands on a program synthesis system. On the one hand, a synthesis system must produce an eff1cient target language program; on the other, II must produce that lergel code In a reasonable amount of lime and without running out of storage. This paper discusses a system that lakes 1 middle ground between the extremes of 1) construct ing ell possible programs lh11l meet the specification and picking the most efficient, 11nd 2) using default Implementations. The system, called LIBRA, uses a knowledge base of efficiency rules to guide the construction of relatively efficient target l11nguage programs In 1 reason11ble amount of lime. LIBRA works from a more abstract specification and considers a wider range of target-language Implementations than optimizing compilers. Many choices must be made, end making a good decision depends on a global view of the program. The target programs are not guaranteed to be optimal but the efficiency knowledge is designed to allow the flexibitily of trading off target-program efficiency for speed and compactneiS In the synthesis process.

The b11slc par11digm Is heuristic se11rch through a set of more and more complete program descriptions. Estimates of the elCecullon costs of program implementations are used as evaluation functions in the search. Symbolic, algebraic program analysis Is used to estimate the execution costs. Knowledge about the lime and storage costs of data structures 11nd operations is used to choose combinations of algorithms and data representations and to control the application of optimizing transformations. Rules about plausible Implementations are used to prune the search tree. LIBRA has been been used to guide the construction of several variants of programs that retrieve Information, sort, cl11ssify, 11nd gener11le prime numbers.

2. BACKGROUND

LIBRA is 11n extension of an interactive program synthesis system that generales implementations In a target language by a series of transformations and refinements of program descriptions, called coding rules. The knowledge base of coding rules was developed by Barstow [ ll The knowledge base allows programs In the area of symbolic processing to be specified in terms of constructs Including sets, mappings, set operellons, and enumeration. The knowledge in both the coding rules and efficiency rules permits the construction of programs using lists, arr11ys, hash t11bles, properly lists, and several enumeration, sorting, 11nd se11rching constructs. The target programs are written In a subset of INTERLISP.

' This research was supported in pert by a Fannie and John Hertz Foundation Fellowship, in part by a National Science Foundat ion Fellowship, In p11rt by Systems Control, Inc., under the Defense Advanced Reseerch Projects Agency Order 3687, Contract N00014-79-C-0127, and in part by the Stanford Artificial Intelligence Laboratory under the Defense Advanced Reseatch Projects Agency Order 249<1, Contract MDA 903-76-C-0206.

Most of the rules 11re not specific to the target language. For example, there are 5 or 10 rules that gradually refine a set into 11 hash table, and then a few language specific rules for refini~g the h11sh table into LISP. Although the general parad1gm IS refinement from abstract to more delailed!rogram descriptions, transformations such as combining nesle blocks of code or nested loops are also allowed. LIBRA decides whether or not to apply such a lr11nsformation ju~t as it decides which of . several refinements to appiy 1 by looking at the global execut1on cost estimates or by applying heuristics.

LIBRA 11nd the coding rules function together both as the synthesis phase of the ~SI program s.ynlhesis system [2) an? . as an independent synthesiS system. F1gure 1 shows a s1mphf1ed view of the synthesis phase and its relation to the rest of PSI. The other modules of the PSI system allow the description of programs by English dialogue or by elCamples or traces, and tr ansi ate the specification into a complete high-level language description. A specification in this high level language can also be given directly to the synthesis phase.

3. PREVIEW

LIBRA chooses from among applicable refinements in the knowledge b11se of coding rules through additional sets of rules that can be easily modified. For elCample, rules about planning, derived from previous analyses of how to make parllcular implement Ill ion detisions, reduce the . effort of explicitly constructing .and compar ing alternat ive implementations. Related decisions are grouped to reduce the size of the search space and to make cost lradeoffs more obvious. Rules about scheduling and resource allocation set priorities lhat reflect the importance of a coding decision and the effort expended in making the choice.

When ~ppropri~te, ~lternate implementations are explicitly con5trucled and compared analytically. The comparisons use global cost estimates to reflect the interdependence of decisions. The cost estimations c~n be made at any stage of the refinement process, ~lthough estimates of more completely relined programs are generally more accurate. LIEIRA computes upper and lower bounds on the estimated execution cost and uses them lor pruning program implementations with branch and bound. These bounds ~re also useful in identifying parts of the program that might lead to bottlenecks. Refinement resources are then concentrated on those parts of the program.

Since the knowledge-based is modular, it l1cilitates the acquisition of new programming knowledge. The same prototypes of programming constructs and of cost estimation procedures that simplify the efficiency analysis process are also quite useful in adding the efficiency information to match the coding knowledge th21t is in the system. A semi-automated process lor 1ddina new efficiency information has been developed.

The locus of this article is on the overall efficiency framework and on the knowledge-based aspects of LIBRA. More details on the 11nalysis procedures and on other topics only covered briefly here can be found in (3).

4. THE PROBLEM

The question addressed here Is how to select an efficient implement~tion for a high-level program specification, given · set of rules for constructing the possible implementations. It is assumed thai there may be a very large number of possible implementations 11nd that it is not possible to construct and comp11re all possibilities explicitly. The design goal was to produce a system lh:\: would lufomBfie~lly select implementations and that would be competible with the refinement paredigm for program synthesis.

The following example illustrates the type of problem that LIBRA solves. The problem Is to synthesize · aood implementetion of · simple database retrieval progr1m.

The program first inputs a database of news stories. It then loops, accepting a keyword command 1nd printing a list of all stones in the database that contain that keyword, 11lphabetized by story name. The special keyword "xyzzy" causes the program to terminate.

As part of the program specification, the user may specify information such as the estimated number of times a keyword command will be given, the expected number of stories tn the database, and the average number of keywords per story. Some variations of this example are developed further in later sections.

4.1 Implementation issue·

Given ~ high level progr~m description, there are sever1l types of implementation issues to be considered:

• -- choosin& data structure representation·
• -- implementin~: hi~:h level operations
• -- applyin~: optimizina transformations

Some of the major difficulties in resolving these issues arise from the need to consider:

• -- lime and space trade-off·
• -- dependencies amonJ decisions
• -- efficiency of tercel procram vercue efficiency of synthesis

Thu-., in the program described above, a representation for the d;~t <~ba -:;e mu-:;1 be chosen, and 11 method lor finding the stories a~!;Ocialed with the keyword must be cho!.en. If there is the an opportunity to apply a transformation such u combining two loops, it must be determined whether that transformation will actually improve the performance of the target program.

Often there is no ide01l representation that minimizes both space and lime. In the news retrieval example, the dalabese can be represented as a mapping from stories to sets of keywords. Unless the d;~labase is relatively small, it will take quite some lime to search lor 1111 the stories containing the given keyword and to sort th~l list. Another possibility is to use ~n additional representation of mappings from keywords to a sorted list of stories containing tl'i·l keyword. If keyword searches are requested frequently, this would improve the running speed, but at the expense of additional storage space.

When more than one data structure is involved, it may not be possible to m~ke implementation decisions independently. Given most cost functions, there will be cross-product terms involving the space from one representation and the lime from an operation on 1molher. For example, this could happen if the cost function were the product of I) execution lime of a statement, 2) number execulion·s, ~nd 3) total storage in use, summed over all statements in the program. The!".e cross-product terms make it impossible to analyze the cosh of the decisions independently. The best implementation choice 11lso depends on the relative frequency of the retrieval oper~lions and the sizes of the data structures.

4.2 Some subproblems

Some sublasks of this general problem of finding an efficient implementation Include codifying the eff iciency knowledge needed to:

1. symbolicelly estimate and compare execution costa One way to choose a good implemenhlion is to make several alternative refinements, estimate the costs of the resulting program implementations, and choose the best one.
2. store and epply previous efficiency analysis result· To avoid excessive analysis, it is helpful to be able to exploit the results of previous analyses. So there should be a mechanism for adding rules such as:

"In refining a set that has more than 30 elements and that is used only to lest membership and add and delete elements, the hash-table representation is a good choice."

"In relining a sequentially represented set in which clements 11re frequently inserted and deleted, use · linked list rather than an 11rrey." (This avoids shifting.)

3) concentrate effort on important parts of the procnm The synthesis system should determine whether the represent a lion of the dal abase has a greater effect on the global program CO!".I than the choice of alphabetizing technique, 1nd should use that information to focus synthesis resources.

4.3 Related research

Only some of the types of efficiency knowledge described in the previous section have been codified for machine use. The prim11ry research has been in data-structure selection systems. Some verific<~tion and theorem proving systems can prove facts about the execution performance of programs, but they do not u~e this inform;~tion to guide program synthesis. The use of efficiency knowledge in program synthesis has not been addressed by debugging or an~logy approaches.

The d<~la-slruclure selection systems all use cost estimation for cotnparison of implementations. Low (4) uses numerical cost eslim11les to choose data structures from among a library of implementations. To lind branching probabilities, the system inserts sll1tement counts Into 11 ddaull implementation that ts run on sample data. Set sizes at different points in the program are determined by queryin& the U5er. Morgenstern's system, a part of PROTOSYSTEM-1. [5J, uses estimates of file input/output and sorting costs to choose file system organizat ions and order the flow of processing operations 1n management information system.

These systems include heuristics for avoiding complete search, but the heuristics are not always expressed explicitly. Low's system h~s a buill-in rule for avoiding multiple representations by forcing all d;~la structures to have the same representation throughout the program and by constraining all data structures lh11l are arguments to 1 common operation to share 1n idenliul representation. Rovner (6] extended Low's work to the selection of t'ssocit'tive data structures and also allowed the selection of redundant representations. Heuristics about when to consider redund11nt representations and about other cost-tradeoff assumptions were carefully noted in the description of the system, but were not expressed as independent rules in the system implementation.

Several different search strategies have been tested. Low and Rovner use hill climbing among the estimated costs of the target prop,r ams to choose an implement at ion. Mor~enstern uses 1 dynamic programming algorithm sP.ecifically tatlored to choose structures for large files. Wegbretl [7] gives some examples of the use of performance analysis to drive a program transformation process. LIBRA represents its resource­ mAnAgement strategy In rules. One of the rules, which suggests consideration of the hip,h potential irnP.act decisions first, is similar to the techniques used by Wegbrett and Morgenstern.

Several other approaches to the problem of data structure selection have been tt'ken. The SETL project (8] uses a more traditional optimizing compiler approach to choose set representations based on a small set of alternatives. The systems described in [9J and [I OJ attempt to match modelling structures with the users needs. An unsolved problem in this approach is how to combine several modelling structures into one representation.

5. A FRAMEWORK FOR EFFICIENCY ESTIMATION

LIORA was· designed lo explore the feasibility of combining analytic and knowledge-based approaches to efficiency estimation. The basic idea in the framework is heuristic search throup,h a tree of partially implemented program descriptions. Efficiency rules from LIBRA are u~ed to control lhe search and to add efficiency-analysis information to the program description. Coding rules from Barstow's knowledge base are used to refine the program description into a more concrete description.

The root node of the search tree is the initial program spec.ificalion and the leaf nodes are target language programs. Each of the intermediate nodes is a partially implemented version of the ent ire program. The order in which refinements are considered affects the subtree that is constructed. The focus of attention for refinement may be limited to a particular part of the program, but compMisons between nodes are based on global execution costs. The tree of partial program implementations, each with an agenda of synthesis tasks, serves as a workspace for recording the slate of the search (see Figure 2 below).

A somewhat. simplified description of the sP.arch strategy is: pick a. program ·.mplementation to work on, pick a refinement task wtlhm that Implementation, pick a codina rule to 1chieve that task, and finAlly apply the (Oding rule and any associated efficiency rules.

Search-resource-m8nagemenl rules choose 1 program implementation and then a part of that program to work on. These rules assign priorities to tasks to ensure that the tasks are carried out within the limits of the resources.

When refining a part of a program, all relevant coding rules are retrieved and tested for applic11bilily. Plausible-implemenl1lion rules 11re used to help decide which coding rule to apply. These rules conl11in precomputed analyses and are used to restrict the possible codin~ rules to those that seem reasonable in the given program situalton, thus pruning the search tree.

Sometimes several coding rules seem plausible. Separate pr?p,ram descriptions are set up and refined, then compared usmg the cost estimates determined by cost-analysis rules. Search-resource-management and plausible-implementation rules may call on the cost-analysis rules for syn1bolic execution cost estimates to compare different implementations and identify polenli11l bottlenecks in the target program execution.

5.1 Assicninc priorities to dedcions

Since all implementations c11nnot be considered in equal detail, the quality of the decisions depends on the order in which they Arc considered and the depth to which the consequences are explored before making a commitment. The search-resource· management rules use scheduling and resource allocation tc balance the final pro~ram performance with the cost of choosing and constructing the Implementations.

Task-ordering rules determine the ordering for attempting different refinement tasks. Ordering principles include expanding complex programming constructs, such as "SUBSET" early to expose choices, and postponing choices of refinement rules and low level coding det11ils until the major decisions have been made.

Choice-ordering rules find an order for considering the decisions thAI must be lfntde. One of these rules suggests alloc1ling the most resources to the decisions that are likely to lead to bottlenecks and making those decisions first. Section 5.3 describes how these higl! potential imp1cl decisions are idenlif.ied. LIBRA makes an adjustment to the potential impact of a decoston to reflect the accuracy of cost estimates for the current level of program development and the expected (Ost of completing the ref inement process. Wilhout this, a highly refined implementation might be abandoned in favor of a very abslrtcl description with a slightly better optimistic estimate lhel is probably not achievable.

5.2 Applyinc plausible·implementalion rules

The plausible-implementation rules in LIBRA describe the situations under which data structure implementations are appropriate, when different sorting operations are plausible, and when to consider using more than one represenl11lion for a dale structure. This knowledge is used lo compare implementations without the expense of explicit construction and evaluat ion of execution costs of all alternatives.

The plAusible-implementation rules are structured condilion­ aclion rules. The condition of a rule about data structures, for example, states all the critical uses of a data structure that make lhe rule relevant. Efficiency information such as the size of a data structure and the number of executions of a statement may be used in the rule condition. The rule action can set a Boole11n combination of constraints for a set of program parts requiring that they be refined (or not refined) to a particular programming construct. A three valued logic (satisfied, impossible, possible) is used to check constraints.

5.3 Eslimalin& execution costs

LIBRA includes 11 knowledge base of rules for estimating the execution cost of 11 program description 111 any sl11ge of the refinement process and with varying degrees of accuracy. The user is expected to provide some basic information about the program, and then LIBRA keeps the analysis updated for the rest of the refinement process. For example, in the NEWS frogram, the b11sic information needed is the expected number o stories/ thr average number of keywords per story, and the number o times the main loop in the program will be executed for a given database. LIBRA then makes 11n111ysis transformations in parallel with refinements so that more 11ccurate cost estimates can be 11ssociated with succeeding nodes in the tree. Some analysis rules are associated with particular coding transformations. Many rules, such as those lor analyzing Boolean combinations, are llssocil·led with coding constructs rather than transformations. Information about parameters such as data structure sizes, statement running limes and execution frequencies, and data .structure usage information is maintained.

The lop-down, incremental analysis allows programs to be analyzed that would be difficult to analyze automatically if only the target program were presented. An advantage of combining the stepwise refinement with this sort of analysis is that classes of implementations can be compared by considering the cost estimates lor intermediate program descriptions rather than explicitly expanding the· tree and comparing the target lantzuage programs.

Estimating execution costs is not an exact science. LIBRA attacks the problem by using both upper and lower bounds on the ueculion cost. The upper bound, or achiev11ble estimate, is calculated by Introducing a standard implementation lor each of the programming constructs used and by assuming that standard implementation choices are made for the rest of the refinement process. The lower bound, or optimistic cost estimate is based on 11 lower bound for implementations known to the program, not a theoretical lower bound. Global optimistic cost estimates are estimated by assuming optimistic costs lor each of the constructs in the program and by assuming that no representation conflicts occur.

The importance of a decision is me~sured by its potential impact. This is achievable bound cost estimate and the execution cost estimated when optimistic cost estimates are used lor ail parts of the program involved in the decision.

A general model of program constructs and specific models for each construct are used to organize the cost estimation process. Also, a standard cost-computation process allows sharing of subroutines between estimation strategies lor making quick estimates and lor performing more detailed (and usually more expensive) analysis.

6. AN EXAMPLE

This section will consider the implementation of a retrieval program in more detail. The problem to be implemented, called NEWS, Is:

Read in a database of news stories. The DATABASE is a mapping from stories to sets of KEYWORDS. Repeatedly accept a keyword and prints out a list of the names of the stories in the database that contain that keyword. When the special command "xyzzy" is given instead of a keyword, then hall.

LIBRA has directed the implementation of several versions o1 NEWS. Under different assumptions about the size of the database or the cost function to be used, different implementations are selected. Fip,ure 3 below shows the tree of implementations that is generated and searched under certain a~r.umptions 11bout d11la strutlure sizes and branch probabilities. The major choices to be made in implementing NEWS are choosing representations lor the DATABASE mapping and lor the KEYWORDS set.

6.1 Alternate implementation paths

A 'number of ways to implement NEWS are possible with the current set of coding rules. One refinement path, node G in the search tree of Figure 3, is followed through in more detail in the following sections. II involves represent ing DATABASE internally as a hash table of stories, with each story in turn having a hash table of keywords. The cost funct ion used in this case is the product of running time and number of pages in use. LIBRA chooses a hash-table representation lor KEYWORDS because there are many keywords lor each story. The l ime to convert the set of keywords into 11 hash table is balanced by the lime savings from the membership lest, which is laster as a hash- table look-up than as a search through the list of keywords (lor large keyword sets). The DATABASE representation decision is simi lar. Both choices are reinforced by the fact that the main loop is executed many limes before exiling with "xyzzy."

Under other assumptions, a p;~lh through node B is taken and a linked-list representation is selecled. If the loop is executed only a lew limes or if the number of keywords associated with a story is small, then the lime required to convert the database from the list of pairs (<story, keywords>) representation to a hash-table representation is not outweighed by the last h~sh-l;~ble look-up operations. II space is a critical lacior in the cost lunclion 1 another path through B is taken in which the or iginal representation of a list of pairs is preserved. This avoids using any additional space, but at a cosl in lime.

A different tree than the one pictured in Figure 3 may also be searched. Suppose there are only a few keywords per story, ma11y stories, and a cost function dominated by runni ng lime. Then the representation of the DATABASE mappi n~ is a more critical decision than the KEYWORDS set represenlal1on, because the lime for the membership lest would not differ greatly lor thE' different represent at ions. If fewer resources are available lor synthesis than in the examples described above, then some of the less reliable plausible-implementation rules are used. For example, nodes F and H are not considered when a plausible­ implemenlation rule that prefers hash-table representat ions to property-list entries is applied.

The implementations that LIBRA chooses in this case are about the best possible with the current set of coding rules. People can do better on the NEWS eMample by using representations outside the scope of the coding rules. However, for any given set of coding rules, allowing people to make the decisions would not produce better Implementations.

6.2 Initial refinement· in NEWS

The following sections show more details of the path leading to node G. By questioning the user, LIBRA determines that the expected number of stories in the database is 80, the 8Verage number of keywords per story is 100, the expected number of iterations of the loop is 300, and the probability that the command is a keyword of the average story I$ .OJ.

LIBRA first ulls on the coding rules to make refinements that do not. involve any decisions. For example, the input DATABASE is refmed to the standard input format for mappin~s, a list of pairs <story, keywords>, and the set of KEYWORDS 1s refined into a linked list. LIBRA applies plausible-implementation rules to decide whether to consider multiple representations for the KEYWORDS set and the DATABASE m11pping.

During refinement, a "lor-all" statement enumerating the domain of OAT ABASE is created. It is refined into an explicit enumeration of the items of domain, since only one coding rule is applicable. To decide how to refine the enumeration, more information about the representation of the domain is needed. LIBRA does not con5ider all possible representation of the domain set explicitly; the choice is made by the application of plausible­ Implementation rules. For example, two of the efficiency rules about sets are:

If the only uses of a set A are for enumerations over thai set, and if B is another representation for A thai is easily enumerable, then use the same representation for A as for B.

If all u5es of a set are for enumerations, or as pointers to positions in set, or as tests of the stale of the enumerations, and if the target language is LISP, then ·P.'ine the set into a linked list.

These rules determine thai domain set, which is used only for enumeration and is not an alternate representation of some other set, should be refined into a linked list. a linked-list should be u~ed. Therefore constraints on the domain set are established, and il is refined into a sequence, and then into a list (rather than an array) with the choices between applicable coding rules resolved by the constraints.

Some of the details of constructing the domain list and the enumeration of the domain ~~re postponed by search-resource­ management rules because LIBRA predicts that no decisions will be involved t~nd the cost estimate for thai part of the progran1 will not change significantly. Other choices that arise and cannot be re5olvcd by plausible-implementation rules are also postponed until other useful refinements are finished.

6.3 ldenlifyin1 the most important decision

All of the ch;mges above lake place in node A of Figure 3. During this refinement, several choices are po5tponed. These choices Are I) how to refine the DATABASE mapping used inside the for-all, t~nd 2) how to refine the KE·YWORDS set within that m.-pping. What is the effect of uch of the two choices to btt m11cfe in this example?

The internt~l representation of DATABASE, <DB I), is used for retrieving the map v<~lue (keyword sets) of stories once per ~tory per command. Possible implementations for mappings range from a linked-list form<~l that ma~.e retrieval linear in the number of stories to 115soti11tive structures thai have nearly constant retrieval lime.

The keyword sets in DB I (KEYWORDS 1 ), are used in a "member(command, KEYWORDS)" test. This test is ewecuted one for each story for each iteration of the loop. Possible implementations give membership tests with limes ranging from linear in the number of keywords to nearly constant.

Since the number of keywords is greater thAn the number of stories, the keyword representation has the largest cost differential and IS more likely to be a bottleneck in the final program if care is not taken in the representation choice. According to the choice-ordering rule about making high potential impact decisions first, the next step is to look at the possible refinements of KEYWORDS!.

Decision-making resources are assigned. Currently the resources measured are the CPU lime used in carrying out the refinements and the number of nodes used in the refinement trees. The resources needed to complete a program implementation without making choices ere &stimated l'lnd subtracted from the total available resources. Decision-making resources from the remainder are assigned in proportion to the estimated importance of the decision. Then, separate program descriptions are set up (actually they share some substructure) in which each of the alternate coding rules are applied. in this decision, the applicable rules allow either refining the keyword set into an explicit set, leading to search node B, or into an explicit mapping, leading to search node C.

6.4 EKplorin1two Implementation· for KEYWORDS I

LII::IRA's go11l is to refine the alternatives (D and C) enough so that the compl'lrison among implementations will be informative. The resources previously assigned give upper limits on the lime tnd space to be spent on gelling a more accurate estimate of the progr11m cost of the implemenll'ltion being explored. Each program description also has a "purpose" to be fulfilled, which servEs 11s a lest of whether the task has been achieved and is used to set some of the task and choice-ordering strategies. There is also a set of program parts thai is to be the focus of attention of processing. In this case, the KEYWORDS! dal1 structure and the representation conversion and the membership lest are included in the focus set.

In the first program description, search node 9, the explicit-set rule is applied and refinement proceeds until all relevant tasks are satisfied -- the resources allowed for writing the program are generous in this example. AI the conclusion, the keyword set for each story has been refined, after the application of several coding rules 1 into a LISP list, and the membership operelion has been refinea into a list search.

Refinement of search node C, the progrAm description in which the explicit-mapping rule was applied, also halls because ali relevant tasks have been accomplished. Here the keyword set is refined to a mapping and membership tested by seeing if there is mapping for the given key. There is also a representation conversion since the keyword set is represented as a list in the input.

LIBRA then computes optimistic and achievable bounds on the co~t of the whole program for each pro~ram description. In the linked-list implementation, B, the optim1slic estimate is 18000 millisecond-pages, and the achievable bound is 48000. The optimistic and achievable cost estimates for the mapping representation, C, are 1000 11nd 110000 respectively. Branch and bound is applied to eliminate any implementations with optimistic estimates worse than the achievable estimate of some other implementation. Neither implementation is eliminated in this case, though later In the refinement of NEWS this technique will be fruitful. Node C has the best optimistic estimate and is chosen for further refinement.

6.5 Refinin~ the rest of NEWS

The remaining decisions are choosing a refinement for the explicit m<~pping of KEYWORDS! and choosing a refinement for OBI. The dat<~basc decision is chosen by the potential impact method. Three program descriptions 11re set up to consider the three applic<~ble refinement rules -- one to consider refining the m<~pping to a list of pairs (search node 0), one to consider a stored mapping (node E), and one to consider a distributed m;~pping (node F). The relevant parts of the program, those related to the OBI decision, are then refined in each program de5cripllon. For enmplc, the stored m<~pping is refined to a hash table. The resulting program descripliOM 11re then compared with each other and with other program descriptions that have been temporarily abandoned, such as the search node B. As Figure 3 thows, nodes B and D c~~n be eliminated from further consideration because even their lower bounds ere worse than achievAble bound on node E. The most promisina implement·lion, se11rch node E, is then chosen and refinement continues.

The final decision to be made is how to represent the KEYWORDS! set, which has been refined into a mapping. As in the refinement of node C, there are three applicable coding rules. However, there Is an applicable plausible-implementation rule about mappings that eliminates one of the possibilities.

If a mapping has already been refined from · set, then do not refine it into a set of pairs.

Thus, only two coding rules are considered. These rules are both tested, in search nodes G and H. The stored mapping, leading to the hash table representation in node G proves to be the best choice. AI this point, the cost estimate is precise enou~h to eliminate all the other possibilities. Thus, the best possibility is the implementation of both the keyword set and the mapping OBI as hash tables. As refinement continues, several other choices of coding rules are presented, but they are all resolved by plllusible-implementation rules. The decisions made include choosing to recompute rather than store values that are easy to compute. The program description is finally refined into a LISP program.

7. KNOWLEDGE ACQUISITION AIDS

LIBRA lndudes mechanisms to assist in the ·cqulsillon of new programming constructs, Including the additions that are made to efficiency knowledge when new coding knowledge Is added. When new high-level constructs are added, such as new types of sorts, or trees, new efficiency knowledge is needed to 1nalyze these constructs, their subparts, running limes, and other efficiency properties. LIBRA's prototypes of programming constructs are consulted by acquisition-aid routines when new constructs are added. Some of the necessary information can be deduced automatically, and the user is asked specific: questions to obtain the rest.

Estimates of running lime and space usage depend on the target languAge and target computer. LIBRA provides · semi-automatic procedure for deriving cost estimation functions from the set of functions for the target language constructs. This procedure can be used in to update efficiency rules when new coding rules are added. Currently only limes estimating functions are derived, but 11 .simil11r process could be used to check the accuracy of the plausible-implemenl11lion rules in the system when new codina knowledge is added.

8. CONClUSIONS AND FUTURE DIRECTIONS

The use of efficiency estimation in program synthesis is a new but promising field. The issue of data-structure selection has been studied In some detail, but not the issue of estimating the effects of applying high level program transform11lions. LIORA provides a framework in which both data-structure and alGOrithm selection can be tre~ted. The heuristics that suggest orderings for considering refinement tasks and decisions and lh11t suggest plausible implementations and when to consider multiple implement ~lions are expressed explicitly II!; rules. A start has been m~de on symbolic algorithm 11n11lysis, and incremental analysis is used to make the anAlysis process tractable. One of the r,oals in LIBRA is to break up the programming process into man~tge~tble chunks in order to learn more about the sequences of implementation choices avail~tble, how the choices interact, and when and how the choices should be made.

To extend LIBRA to complete automatic programmina system, additionAl research would be needed. For example, to write more complex progr11ms such as compilers or oper11ting systems, more coding and efficiency rules about constructs such ~~ bit-pack.ing, machine interrupts, and multiprocessing would need to be added to the system. However, the efficiency tee hniques described here should be sufficient to control combinatorial explosion.

Higher level optimizations, extended symbolic analysis and comp11rison c11pabililies, and more domain ~vpNi ise are some feasible extensions to LIBRA. Another pos~ i bi lity is to automate the checking of conditions in the heurist ic rules by doing a complete search through the current set of coding rules. Autom11tic generation of heur i stic~ based on analysis of symbolic cost estimates would be another important addition. Adding an inference process to both the coding and efficiency estimation process would also be useful, though not as str·ighlforward.

More powerful symbolic comparison techniques are also P�~sible. For enmple, the range of values for which one imj')lemenlation dominates another (ci·N2 over c2·N) could be determined. The user would then only have to say whether N was within a particular range, rather than giving a definite value. Another use of symbolic costs is in proposing alternate solutions, each with the conditions that make that solution the best choice. If, for example, the cost for primitive operations such as multiply are given as ranges, the system could produce the solution "implementation X is best if the target machine has a very fast multiply, but implementat ion Y is best if multiplication lakes about the same lime as addition."

LIBRA has demonstrated the feasibility of the approach described here, but has by no means exhausted the reseerch topics In efficiency estimation for program synthesis.