ftp.umcs.maine.edu/2015-02-07.ftp.umcs.maine.edu.tar/ftp.umcs.maine.edu/pub/WISR/wisr6/proceedings/ascii/baxter2.ascii

Text File | 1993-10-19 | 23KB | 550 lines

                                              Practical  Issues  in


               Building  Knowledge-Based  Code  Synthesis  Systems



                                                        Ira Baxter



                              Schlumberger Laboratory for Computer Science

                                             Austin, Texas, 78720 USA

                                                 Tel:  [phone]

                                                 Fax: [phone]

                                        Email: [e-mail]



                                                         Abstract


           We present some issues and lessons on building a practical "generativereuse" system.  We
       discuss the cost of building a useful system, and the tensions between prototyping and production
       systems, often induced by scale demands.


       Keywords: Synthesis, transformation, generative, knowledge-based systems


       Workshop Goals:  Exchange  ideas  on  capture  and  mechanized  reuse  of  design  knowledge.
       Particular interest in learning about other work related to knowledge acquisition for program
       generation.


       Working Groups: reuse and formal methods, reusable component certification, domain anal-
       ysis/engineering



1      Author's Background



Much  of  the  work  in  reuse  is  focused  on  code  reuse.  In  contrast, much  of  my  work  is  related
to reuse of design and analysis information in a formal context,  in an effort to enhance software
maintenance.


The Draco tool [1] reused composable components resulting from domain analysis. The experience
of the Advanced Software Engineering group at UC Irvine with Draco led to ideas about porting
software by partial domain analysis, comp onent abstraction, and re-implementation [2 ].


Work on Design Maintenance Systems (DMS) [3 ] defined how to generate and capture a complete
design rationale for a transformationally-derived program interms of specified p erformance predi-
cates. The design rationale was reused (and revised) to control the modification of the synthesized
program according to formal maintenance deltas, representing desired specification changes. Co de
intended  for  reuse  often  needs  to  be  modified, but  few  concrete  methods  for  carrying  out  that
modification have been studied. The DMS strategies can be viewed asan explicit prescription for
how to modify code in a particular reuse instance.



                                                         Baxter- 1


My current work is on developing infrastructure needed by the Sinapse system to generate efficient
parallel programs. This work shows the value of both declarative capture of potential parallelism in
abstract components [4], and the utility of conventional compiler optimizations such as paralleliza-
tion detection and common subexpression elimination on abstract domains rather than low-level
(i.e., Fortran) synthesizedco de.



2      Position



Building  knowledge-based  tools  to  aid  generative  reuse is  a  difficult  process.   Both  theory  and
practical  issues  must  be  addressed.  Many  of  the  theoretical  issues are  already  addressed  in  the
literature: domain analysis and evolution [5], transformational development [6], etc.


This position paper discusses a number of practical issues, using our exp erience developing Sinapse
as  examples.   A good  software  engineering  process  ought  to  identify  and  address  these  issues.
However, since building generative reuse systems is not yet a common SE task, we decided to risk
stating the obvious for would-be reusers of our experience.



2.1     Issues



We will discuss the following issues:



    fflConstruction costs


    fflScaling up for real synthesized codes


    fflAd hoc knowledge vs.  algorithms


    fflCoding vs.  specifying optimization tasks


    fflKnowledge acquisition tools vs. knowledge capture


    fflLeveraging the synthesis tools


    fflTesting system robustness



We first sketch Sinapse to provide necessary background.



2.2     Sinapse Overview



The  Schlumberger  Laboratory  for  Computer  Science  has  develop ed a  system  called  Sinapse  [7 ]
[8 ] [9 ] to synthesize mathematical modeling programs for restricted application domains.  These
are primarily wave propagation problems, typically used to validate seismic or geophysical models.
Sinapse accepts a 20-50 line specification which defines a set of partial differential equations (PDEs)
to be solved, either directly by stating the equations, or indirectly by use of domain-specific termi-
nology. Sinapse produces complete C, (sequential) Fortran, or (data parallel) Connection Machine
Fortran programs that solvethe PDEs in a particular geophysical context by using finite differ-
encing methods, including the necessary input and output code. Resulting programs are 500-1500
lines in size.


                                                         Baxter- 2


Sinapse  is  a  knowledge-based  synthesis  system,  containing  knowledge  about  the  wave  propaga-
tion  problem  domain, knowledge  of  abstract  algorithms  for  solution  techniques  for  problems  in
that domain, parallelization methods for those codes, general programming knowledge, and control
knowledge to sequence the synthesis process. The domain knowledge is used to cho ose abstract so-
lutions by classifying domain-specific specifications. These solutions are transformationally refined
into a production code. The system stores synthesis sequencing knowledge as a set of hierarchical,
nonlinear plans. Abstract algorithms are stored in a mixed form consisting of abstract syntax trees
(ASTs) with procedural attachments. Decisions about branches in the design space are handled by
built-in system constraints, heuristics and defaults; because we always exp ect the system to have
limited knowledge, the software engineer operating Sinapse can override any heuristic decision. Re-
finements consist of tree-to-tree rewrite rules coupled withexecution of the procedural attachments.
The refinement process is reminiscent of Draco's repeated refine-to-domain, optimize-within-domain
method. Optimizers based on conventional compiler technology concepts were implemented to allow
optimizations in abstract domains; this allows Sinapse to detect common subexpressions and con-
trol parallelism by analyzing the set of PDEs rather than expecting a Fortran compiler to discover
these in the final output.



3      Construction Costs



The development of a production-quality synthesis system, even when limited to addressing restricted
domains, and reusing existing tools, can easily consume 15-20 person-years.


Sinapse today consists of 37,000 lines of code (LOC) built on top of the commercialMathematica
[10 ] system. It was developed at the cost of 12 person-years, spread over 4 elapsed years. We intend
to reach a production system that can be reliably used by physicists and engineers this year.


To provide the barest indication of where the effort goes,  weinclude a system breakdown as an
LOC percentage of subsystem vs. total system:



  5%   Textual User Interface


  9%   Graphical User Interface


  5%   Synthesis control


 25%   Domain-specific synthesis knowledge


  5%   Local optimizer:  type inference, simplification


 16%   Conversion of ASTs to target languages: C, Fortran, CM Fortran, Lisp


 27%   Global optimizer:  parallelization, code motion, CSE


  4%   Computation partial order management (used by optimizer)


  4%   Utilities/debugging tools



We caution the reader not to interpret these percentages as effort, because the tasks had differing
complexities, and considerable activity occurred outside of coding.


It should come as no surprise that much of the effort went into domain-specific knowledge acquisi-
tion. It may be more of a surprise that significant effort went intodomain-independent optimizing
technology.


                                                         Baxter- 3


4      Scaling  up  for  Realistic Co des



One must design synthesis systems for performance with scale.  We address how prototyping and
knowledge interact with scale.



4.1     Prototyping vs.  Production



Well-intentioned reuse of existing tools may make scaling more difficult.


As a system starts to show promise of utility, ambitions turn from small demos to practical codes,
and scale difficulties begin to show up. An initially attractive system foundation may have other
properties which exact a relatively large cost in comparisonto the exp ected b enefits.  One must
consider these benefits carefully; engineering for scale may require payinghigher costs during the
early stages of development.


As an example, we built Sinapse on top of a symb olicmathematical system, Mathematica (MMa),
because it had several attractive properties from a prototyping p oint of view.  It provided a sin-
gle program development environment which contained considerable built-in knowledge useful for
manipulating symbolic (algebraic and differential) equations,a procedural programming language,
and a transformation system for free.  It promised p ortability of the result because MMa ran on
several  platforms, and  it  was  interactive, which  eased  debugging  by  making  inspection  simpler.
Early versions of Sinapse benefited because the availability of these mechanisms made it easier to
prototype parts of the system, thereby selling the system concept via small demos.


Growing sophistication caused Sinapse's internal algorithm form to become more specialized.  It
became progressively more difficult to keep a form compatiblewith that of the underlying MMa
system. Eventually, we gave up direct compatibility, opting for conversion to MMa's form when we
needed MMa's mathematical knowledge, and then converting the result back to the Sinapse form.
Happily the number of conversions per run have turned out to be infrequent. Obviously, we wish to
(re)use the knowledge in a symbolic algebra system;the need for our own representations hints that
staying within the environment definedby such a tool is not necessarily required. Ideally, we'd like
to have a way of compiling symbolic manipulation knowledge stored in a knowledge-representation
language such as KIF [11 ] into a form compatible with our desired representations. This is itself a
program synthesis problem we don't knowhow to solve.


The MMa tree-to-tree rewrite system works well onsmall trees representing "typical" size math-
ematical formulas.  Unfortunately,  MMa's built-in control strategies work slowly on large sets of
transformations (100's of rules) on large ASTs (10K tree no des) which are typical of the size of the
codes we synthesize. Further, MMa is an interpreter without any corresponding compiler, costing
us an additional runtime factor of 10x. Synthesis times without optimization run to 30 minutes on
a Sparc 2 and can be much longer with the optimizations. This has made building and testing the
Sinapse system components relatively painful. If one insists on using ASTs, a tree-to-tree transfor-
mation system engine is cheap to replicate compared to the investment in a synthesis system; we
would recommend instead looking into more efficient pro duction system tools like OPS5 [12 ].


Even the choice of ASTs is called intoquestion by scale.  Most "purist"" transformation systems,
MMa  being  no  exception, operate  by  manipulation  of  ASTs.  However,  serious  optimization  of
refined code requires that dataflow analysis be performed; ASTsare a p oor choice for this.  The lion's
share of the cost in the optimizer is the need to recompute the data flow analysis information after
an optimization has been made. An approach we are pursuing is the use of compiler representations


                                                         Baxter- 4


such as Static Single Assignment form [13 ], in which the data flow has been made explicit,  and
optimizations directly transform the dataflows, keeping them up to date.  An ideal solution would
be to treat the data flow analysis problem as a problem in incremental re-computation,  and use
finite difference methods (unfortunately, this term is common to both PDE solving and program
synthesis but doesn't mean the same thing) to keep dataflows current [14 ].


Many  difficulties  can  be  traced  to  the  tension  between  prototyping  and  production.   Synthesis
systems are controversial enough so that the need to prototype them early can predispose evolutionary
descendents to later scale troubles.  For conventional SE tasks, we know that prototypes are a po or
foundation  for  production  code; for  knowledge-based  systems,  evidence that  a  prototype  works
should similarly not be treated as evidence that the prototype can be easily extended to a pro duction
code by mere incremental addition of knowledge.



4.2     Ad Hoc Knowledge vs.  Algorithms



Special  cases  may  sometimes  be  more  easily  handled  algorithmical ly.  Knowledge-based  methods
should be reserved for cases where the algorithms fail because of intractability or lack of information.
System designers should be prepared to pay the price of installing the appropriate algorithms when
scaling up.


Sinapse uses some simple methods to effect certain kinds of optimizations. To ensure that reason-
ably high-performance code is generated, a kind of knowledge-based code motion is used to move
initialization code for refined components out of loops. Other special mechanisms were installed to
allow results of computations in generated programs to be stored and reused at later points.  These
mechanisms have the advantage of being easy to define and install, which is attractive for small
examples.


Both  of  these  mechanisms  are  subsumed  by  conventional  compiler  optimization  techniques  that
couple code motion with common subexpression elimination.  The knowledge-based versions are
somewhat fragile, and KB encoders of algorithms had to think carefully about how to use them.
The compiler methods simply work without thought; this makes the system more robust,  and it
makes KB augmentation faster because less has to be explicitly encoded.


There will still be cases where compiler methods fail because the cost of inference is simply too
high. In these cases, knowledge can play a useful role.



5      Coding  vs.  Specifying  Optimization  tasks



Since many synthesis systems will have unique internal representations, there should be a way to
manufacture conventional optimizers easily.


Program specification is about defining what a program will do. Since, given a specification,one can
simply try enumerate-and-test, program synthesis is onlyab out optimization.  For scale purposes,
conventional optimizers seem necessary, but building them by hand is expensive. Much of the code
in an optimizer consists of routines that interpret how information flows across various syntactic
constructs.


While this can be encoded by hand, we found that as Sinapse's internal form evolved and grew in
complexity,the optimizer had to evolve in lock step. We often wished that we could instead specify


                                                         Baxter- 5


something like the denotational semantics [15],  and "compile" that into practical optimizers.  In
essence, we need an optimizer generator. Basic research is needed to accomplish this task.


Another possibility is for the synthesis community to agree on a widely usable internal form. This
would allow tools to be made generically available.  We believe this avenue is unlikely because a
long search for UNCOL has largely been unsuccessful, and we expect that the utility of internal
forms will come from their domain specificity.



6      Knowledge Acquisition  Tools  vs.  Knowledge  Capture



System designers must choose between capturing knowledge themselves and defining knowledge ac-
quisition tools.  Experts often havelittle patience for unfamiliar detail.  Failure to get them directly
involved in knowledge capture can limit the rate at which a system's ability grows.


Much of Sinapse's knowledge is coded in MMa notation for defining trees or as MMa procedures.
This required that encoders know MMa well, and made it difficult to prevent some low-level imple-
mentation details of Sinapse from leaking into thecomp onents.  Attempts to get wave propagation
experts, who  were  expert  parallel  machine  programmers, directly  involved  in  the  knowledge  en-
coding task were not very successful because of the high cost of learning the system.  The system
designers have had to substitute for the experts when encoding the knowledge, making the designers
a bottleneck in the acquisition process.


Getting the experts involved requires that they be taught basic principles of knowledge represen-
tation and domain analysis.  The system designers should spend their energy building knowledge
acquisition tools, to allowing the experts to easily find out what the system already knows, and
revise that knowledge, using notational schemes which are familiar [16 ], [17 ].



7      Leveraging the  Synthesis  Tools



We should try for an "avalanche" technology, in which the tools can be used to enhance themselves.
Much of a synthesis tool is focused around generation and optimization of mundane code.  It would
be ideal if such mechanisms could be used to help generate more of the synthesizer code.


Much of the Sinapse system was built byconventional coding methods. Considerable leverage might
have been obtained if we could have used such synthesis tools to build part of Sinapse itself. As an
example, data flow analyzers on arbitrary internalforms might have been built in this fashion.



8      Testing  System  Robustness



A system must have a methodology for testing and configuration management to ensure robustness.


We  successfully  used  some  conventional  SE  practices  to  help  ensure  the  robustness  of  Sinapse.
Modules of the optimizer were tested dynamically on each system load during development. RCS,
a source-code control tool, was augmented with a number of procedures to ensure that the base
system had always been regression-tested, and that differences in test results from previous runs



                                                         Baxter- 6


had been validated by team members.  These methods ensured that thedevelopers were always
working with trusted components.



9      Conclusion



We have presented some issues that must be faced by designers of generative reuse systems. Gener-
ative systems appear to cost a lot to build; theremust be considerable payoff to justify building one.
The classic tensions between the need to prototype cheaply to sell a system concept and the need
to design for scale will probably appear as repeated development. Algorithmic methods should be
used where known, and augmented with knowledge-based methods where they fail.  Generation of
optimized code requires the construction of complex optimizers; abstract syntax trees seem to b e
a weak representation for this purpose, and we have few tools to help us build even conventional
optimizer mechanisms.


Most of these issues are related to effects of scaling up, which cannot be avoided for most practical
systems.



References



  [1] J. Neighbors, "The Draco Approach to Constructing Software from Reusable Components,"
      IEEE Transactions on Software Engineering, vol. SE-10, Sept. 1984.


  [2] G. Arango, I. Baxter, P. Freeman, and C. Pidgeon, "TMM: Software Maintenance by Trans-
      formation," IEEE Software, vol. 3, pp. 27-39, May 1986.


  [3] I. D. Baxter, "Design Maintenance Systems," Communications of the ACM, vol. 35, pp. 73-89,
      Apr. 1992.


  [4] I. D. Baxter and E. Kant, "Using Domain-Specific, Abstract Parallelism," in Proceedings of
      Parallel-Code Generation Workshop atICLP91, IEEE Computer Society, Oct. 1991.


  [5] G. Arango, Domain Engineering for Software Reuse.  PhD thesis,Department of Information
      and Computer Science, University of California at Irvine, July 1988.  ICS-RTP-88-27.


  [6] H. A. Partsch, Specification and Transformation of Programs.  Springer-Verlag, 1990.  ISBN
      52356-1.


  [7] E. Kant, F. Daube, W. MacGregor, and J. Wald, "Automated Synthesis of Finite Difference
      Programs," inSymbolic Computations and Their Impact on Mechanics,PVP-Volume 205, New
      York, NY: The American Society of Mechanical Engineers 1990, 1990.  ISBN 0-791800598-0.


  [8] E.  Kant,  F.  Daube,  W.  MacGregor,  and  J.  Wald,  "Scientific  Programming  by  Automated
      Synthesis," in Automating Software Design (M. Lowry and R. McCartney, eds.), AAAI Press,
      1991.


  [9] E. Kant, "Synthesis of Mathematical Modeling Software," IEEE Software, vol. 10, pp. 30-41,
      May 1993.


[10]  S.  Wolfram,  Mathematica:   A  System  for  Doing  Mathematics  by  Computer.    Reading,
      Massachusetts:   Addison-Wesley  Publishing  Company,  Inc.,  1988.    ISBN 0-201-19334-5,
      QA76.95.W651988.


                                                         Baxter- 7


[11]  M.  R.  Geneserth  and  R.  E.  Fikes, "Knowledge  Interchange  Format  Version  3.0  Reference
      Manual," Tech. Rep. Logic Group Report Logic-92-1, Computer Science Department, Stanford
      University, June 1992.


[12]  L. Brownston, R. Farrell, E. Kant, and N. Martin, Programming Expert Systems in OPS5:  An
      Introduction to Rule-based Programming.  Addison-Wesley, 1985.  ISBN 0-201-10647-7.


[13]  R. Cytron, J. Ferrante, B. Rosen,M. Wegman, and K. Zadeck, "Efficiently computing static
      single assignment form and the control dependence graph," ACM Trans. Programming Lan-
      guages and Systems, vol. 13, pp. 451-490, Oct. 1991.


[14]  D. R. Smith, "KIDS: A Semi-Automatic Program Development System," tech. rep., Kestrel
      Institute, Palo Alto, California 94304, Oct. 1989.


[15]  F. G. Pagan, Formal Specification of Programming Languages:  A Panoramic Primer. Engle-
      wood Cliffs, New Jersey 07632: Prentice-Hall, Inc., 1981. ISBN 0-13-329052-2.


[16]  S. Marcus, "SALT: A Knowledge Acquistion Tool for Propose-and-Revise Systems," in Au-
      tomating  Knowledge  Acquisition  for Expert  Systems  (S.  Marcus,  ed.),  pp. 81-123,  Boston:
      Kluwer Academic Publishers, 1988.


[17]  J. Boose and B. Gaines, The Foundations of Knowledge Acquisition, Vol. 4. New York: Aca-
      demic Press, 1990.



10       Biography



Ira D. Baxter is a research scientist with the Schlumberger Laboratory for Computer Science in
Austin, Texas, working on tools to helpengineers generate scientific modeling programs for parallel
computers. He received a Ph.D. in Computer Science from the University of California at Irvine in
1990.  A previous life included 20 years of system software design for mini- and micro-computers.
His interests include program synthesis/transformation, software engineering, and pizza.



                                                         Baxter- 8