Call for update to database of transformation/synthesis projects

Transformation systems are tools whose purpose is generally to manipulate
programs and/or specifications, producing other programs or
specifications. Often, the purpose is to produce a low-level executable
program from a high-level specification; Martin Feather characterizes
these transformation tools as "compilation with advice."


This is the 2nd annual call for information on serious transformation
systems. The purpose of this call is collect a database describing such
systems, and to distribute this knowledge widely in an effort to foster
better communication. I will post the survey results to all respondants
and to suitable newsgroups.


The criteria I consider useful for deciding which projects match are
the following:
        a) The existence a specification language S. This can be anything
              that can be interpreted by a fixed predicate I(S,P),
              defining acceptable generated programs P for each instance of S.
              We include nonprocedural specifications (Logic, FSAs, BNF,
              domain-specific notations, etc.), abstract programs, and conventional
              programming languages as legitimate specification languages.
        b) A transformation, synthesis, or partial evaluation engine,
              applying rewrite rules explicitly or procedurally to a specification
              language instance to produce a program corresponding to that
              specification.
              Any control regime is acceptable, manual to fully automatic.
        c) The intent that the control regime, rule base or some other
              aspect of the system be augmented over time, by others than
              the maintainers of the system, for the purposes of generating
              different programs from the same specifications.
        d) Possession of a running implementation, or significant
              resources committed to obtaining an implementation
        e) Expectation that something larger than a toy program will
              be constructed, often in a language different
              of the specification langauge.


I view conventional compilers and application generators as outside this
realm, primarily by failing criterion c). However, I would rather err on
the side of including too much than too little, so if you are not sure,
please respond. As an example, I don't view VLSI synthesis as being
excluded; ignoring geometry, the problems seem much the same. I also view
design recovery and/or analysis systems that use the same kind of
mechanisms as interesting.


If you are a principal on a transformation project, I'd really like to
obtain a response! Last year's response was smaller than I expected,
excluding even the world's best known commercial system. If you are
not a principal, but know of a system that should be included, please
provide me a pointer, and I'll contact the principal directly.


Ideally, respondants will supply the following information, in the same
format, just to provide comparative information


System Name:
Problem Domain:
Specification Language:
Target languages:
Transformation process:
Control Regime:
Advice accepted:
Key focus:
Status 1993:
Biggest Difficulties:
Overview Publications:
Research Group:
Contact:
email:
phone:
Organization:
Address:


As an example, I have filled it in for our in-house project.
Any additional information or clarifications are welcome.


----------------------------------------------------------------------
System Name: Sinapse
Problem Domain: Numerical modeling codes
Specification Language: Partial Differential Equations,
                                                Schema slot fillers,
                                                Various atomic performance goals
Target languages: CM Fortran, Fortran77, C
Transformation process: Symbolic and procedural refinement of program schemas
Control Regime: Partially-ordered synthesis tasks with subtasks.
Advice accepted: Heuristics for making decisions in the refinement space.
Key focus: Generation of efficient supercomputer codes
                                                from mathematical specifications
Status 1993: Implemented, producing runnable 500-1000 line programs.
Biggest Difficulties: Defining complete specification language for
mathematical models. Acquisition of useful refinements.
Generation of efficient parallel code.
Absence of performance models.
Overview Publications: "Scientific Programming by Automated Synthesis",
                                                E. Kant, F. Daube, W. MacGregor, J. Wald,
                                                in Automating Software Design, M. Lowry and R.
McCartney, eds., AAAI Press, 1991
E. Kant, "Synthesis of Mathematical Modeling Software",
IEEE Software v10 #3, May 1993.
Research Group: Modeling and Simulation
Contact: Ira Baxter
email: baxter@slcs.slb.com
phone: 1-512-331-3714
Organization: Schlumberger Laboratory for Computer Science
Address: PO Box 200015
                                                Austin, Texas, 78720
----------------------------------------------------------------------


I also invite discussion of the criteria, and remarks on what
kinds of additional information should be collected.


Summary responses from last year are appended for your edification or
correction. None of them have the Advice: slot. Text in brackets
containing -ed is editorializing on my part, either guessing information
or remarking on something particularly interesting.


--------------------------------------------------------------------
Ira Baxter email: baxter@slcs.austin.slb.com ph: 1-512-331-3714
Schlumberger Laboratory for Computer Science
8311 North RR 620 [for snail mail, use PO Box 200015 instead]
Austin, Texas, 78720


******************************************************************************


System Name: ap5 (with others under development)
Specification Language: commonlisp + relational abstraction and rules
(we call these virtual and active databases)
Problem Domain: problems requiring complex data models
Target languages: commonlisp
Related work may try to provide relational
abstraction with other languages, e.g., C++.
Transformation process: There is a compiler for relational calculus
expressions and smaller compilers for other
idiomatic ways of specifying derived relations.
There is also a trigger compiler for active
database applications.
Advice: ap5 is extended by users providing
                                                descriptions of new representations
                                                for stored relations, and new derivational
                                                idioms for derived relations.
Status 1991: Implemented, megabytes of code using ap5
are in daily use.
Overview Publication: A 15 year perspective on automatic programming
IEEE Trans. on Software Engineering, Nov. 1985
(That's an extremely high level overview.)
Research Group: Software Sciences division of ISI
Contact: {balzer, donc, goldman, wile, ...} @isi.edu
email: see above
phone: 1-213(soon to be 310)-822-1511
Organization: Information Sciences Institute
(University of Southern California)
Address: 4676 Admiralty Way
                                                Marina del Rey, CA, 90292
******************************************************************************


System Name: ARIES
Specification Language: Reusable Gist + various graphical notations
Problem Domain: Numerical modeling codes, Air traffic control
Target languages: LISP, English
Transformation process: Symbolic and procedural refinement of program schemas
Status 1991: To be demonstrated at KBSE92.
Overview Publication: W.L. Johnson, M.S. Feather, and D.R. Harris.
                                                "Integrating domain knowledge, requirements,
                                                and specifications", Journal on System Integration,
                                                1991 (in press, I just don't know what issue)
Contact: Lewis Johnson
email: johnson@isi.edu
phone: 1-213-822-1511
Organization: USC/ Information Sciences Institute
Address: 4676 Admiralty Way, Marina del Rey, CA 90292-6695




******************************************************************************


System Name: BEHAVIOR
Specification Language: KMODEL (a ancestor of Model-K [W.Karbach, A. Voss
et al.] based on KADS methodology)
Problem Domain: model-based diagnosis
Target languages: Common LISP
Transformation process: evaluation of the specification (runnable
specification),
call of target language constructs from specification
Status 1991: Model-K was implemented, KMODEL is under development,
Overview Publication: Angi Voss, Werner Karbach, Uwe Drouven, Darius
Lorek and Ralf Schuckey: "Operationalization of a
synthetic problem"
ESPRIT Basic Research Project P 3178 REFLECT Task
I.2.1 Report, 1990
Thomas Hemmann, Hans Voss: "Preliminary Results on the
BEHAVIOR Specification Language KMODEL-0";
BEHAVIOR Memo 5-91; 1991
Research Group: Institute for Applied Information Technology, AI
Division
Contact: Thomas Hemmann, Hans Voss
email: hemmann@gmdzi.gmd.de, hvoss@gmdzi.gmd.de
phone: +49-2241-14-1
Organization: German National Research Center for Computer
Science (GMD)
Address: Institute F3, AI Div.
                                                PO Box 1240
                                                D-5205 Sankt Augustin
                                                Germany


Pointers to other projects: REFLECT (A. Voss, W. Karbach), FABEL (M. Linster);
both at GMD


******************************************************************************


System Name: CHIP [? ed]
Problem Domain: Compiling logic
Specification Language: First order logic
Target languages: Recursive logic Procedures
Transformation process:
Control Regime:
Advice accepted:
Key focus:
Status 1993:
Biggest Difficulties:
Overview Publications: K.K. Lau and S.D. Prestwich,
"Top-down Synthesis of Recursive Logic Procedures
from First-order Logic Specifications",
Proc. 7th Int. Conf. on Logic Programming,
MIT Press 1990 pp.667-684
K.K. Lau and S.D. Prestwich,
"Synthesis of a Family of Recursive Sorting Procedures",
1991 International Logic Programming Symposium.
Research Group:
Contact: Steven Prestwich
email: steven@ecrc.de
phone:
Organization:
Address:


[This system includes an automatic partial deduction system for full Prolog.]


You might also be interested in the LOPSTR 91 proceedings (Workshop on
Logic Program Synthesis and Transformation). If so, please email
Dr.K.K.Lau: kung-kiu@computer-science.manchester.ac.uk
***************************************************************************


System Name: CIP
Problem Domain: General [applied to building transformation systems]
Specification Language: CIP-L wide spectrum languge,
                                                algebraic specifications
Target languages: Pascal [? ed.]
Transformation process: Tree-to-tree transforms applied where directed
Control Regime: *Entirely* manual
Advice accepted: Where to apply transforms
Key focus: Clerical support of transformation process
Status 1993: Defunct [? ed.]
Biggest Difficulties:
Overview Publications: Fredrich Ludwig Bauer and Bernhard Moller and
Helmut Partsch and Peter Pepper,
"Formal Program Construction by Transformations--
Computer-Aided, Intuition-Guided Programming"
IEEE Transactions on Software Engineering,
15(2), February, 1989,
F. L. Bauer and H. Ehler and A. Horsch and B. Moller
and H. Partsch and O. Paukner and P. Pepper,
"The Munich Project CIP", Lecture Notes in
Computer Science 292,Springer-Verlag, 1987.
Research Group: CIP
Contact:
email:
phone:
Organization:
Address:


[LNCS 292 contains an amazingly readable, huge algebraic specification of
a version of a proposed version of the CIP system. This is pretty
convincing that large non-reactive systems can be specified this way. - ed].




****************************************************************************


System Name: Cleaver
Specification Language: pattern-based tree attributes and rewrite rules
Problem Domain: dynamic compilers
Target languages: Lisp, eventually C
Transformation process: transformation composition
Overview Publication: "Attributed Transformational Code Generation for
Dynamic Compilers"
J. Boyland, C. Farnum, S. L. Graham
International Workshop on Code Generation
Dagstuhl, FRG (May 1991).
(to appear in Springer, 1991)
Research Group Pan
Contact: John Boyland
email: boyland@sequoia.berkeley.edu
phone: 1-415-642-9542
Organization: Computer Science Division,
University of California, Berkeley
Address: Berkeley, CA 94720


Here is my doctoral research project. It builds upon [Dora],
the work of C. Farnum.


This work may not be what you want; in particular, the specification
language may seem too procedural for your system --- instead of using
rewrite rules to transform a specification, the rewrite rules are the
specification.


[There was discussion with Boyland over whether he had a transformation
system. Boyland's tool *produces* an optimizer, given a set of
transformations over an IL form. It accepts an attributed tree grammer
defining transformations as a specification of the optimizer to be
produced. The usual point of a transformation system is to *be* the
optimizer, if one thinks of a specification as simply a really inefficient
program. Boyland's tool apparantly optimizes the application of the
transforms specified in the ATG. -ed]


I see two ways to view the system:


CLEAVER is a specification language for dynamic compilers


CLEAVER is a transformation system for tree languages.


The first concept was what I was trying to say and the second is what you
at first understood. Since I don't use formal transformation methods to
transform transformations, it may be better, in fact, to view CLEAVER in the
second light.


attributes + transformations
--------- processed by CLEAVER (part I) into -----------
attribute grammar
--------- compiled (part II) into ------------------
dynamic compiler


source tree
---------- dynamically compiled
code tree


Charlie Farnum was using attributes and transformations to describe
optimization; I'm using them to describe (naive) compilation.
Dynamic compilation does about zero optimization.


Charlie's system differs in that
      1> attributes and transformations are compiled separately
      2> transformation is multi-stage and non-incremental
      3> it works.


******************************************************************************


System Name: Dora
Specification Language: Attribute patterns, tree rewrite rules
Problem Domain: Compilers
Target languages: Lisp
Transformation process: Construction of pattern-matching automata,
combination of separate specifications and rewrites.
Status 1991: Implemented for local use, 1990; currently rewriting
for robustness, hope to spread to other sites 1992.
Overview Publication: "Pattern-based Languages for Prototyping of
Compiler Optimizers", C. Farnum, UC Berkeley,
Tech Report #UCB/CSD 90/608, 1990.
Research Group: Programming languages
Contact: Charles Farnum
email: cfarnum@valhalla.cs.wright.edu
phone: 1-513-259-1346
Organization: Wright State University
Address: Department of Computer Science and Engineering
Dayton, OH 45435




Dora is a system for building prototype compilers. There are
special-purpose non-procedural languages in Dora. I would classify
the languages as being similar to attribute grammars, in so far as
`specification' vs `programming' goes.


The constructed compilers are definitely prototypes, not production,
in that they run quite slowly. We generate `real' programs in terms
of size --- e.g., we've generated a compiler optimizer that does all
of the UOPT optimizations (the suite used by the DECstation C
compiler). They are `fake' in terms of execution efficiency. The
intent is to make it easier to experiment with combining different
optimizations, or to build compilers while experimenting with new
languages.


As far as your explicit criteria list goes:


> a) A specification language (anything that can be interpreted as
> a predicate over acceptable generated programs, including
> abstract programs)
According to this one, any programming language is a specification language.
[Yes. -- ed.]


> b) A transformation or synthesis engine, applying rewrite rules
> explicitly or procedurally. Any control regime is acceptable.
Since we are generating compilers, this is done at execution time of
the specification. The compiler specifications are not rewritten
with rewrite rules [although, if one uses Dora to write a Lisp
optimizer, and apply it to the system itself, then... :-)]. (Or, if
you want to view the generated compiler as the system and the
programming language being implemented as the specification language,
then definitely yes.)


> c) The intent that the rule base be augmented over time,
> by others than the maintainers of the system.
Yes.


> d) Possession of a running implementation, or significant
> resources committed to obtaining an implementation
Yes, though it's not clear we have sufficient resources to make it
usable outside our environment.


> e) Expectation that something larger than a toy program will
> be constructed, often in a language different
> of the specification langauge.
Yes.


I've included the abstract from my dissertation (which is where the
system got started) below, it might help you decide.


Abstract:


Choosing an appropriate set of optimizations for a particular compiler is
a black art; the literature abounds with unimplemented optimization
algorithms. This dissertation describes the core tools used in Dora, an
environment for exploring the design space of optimizing compilers.


Dora uses a lambda-calculus based intermediate language schema to
represent programs at both high and low levels. Operators that are
appropriate to a particular language, machine, and/or code-level are
defined as necessary for a particular compiler, using a description
language that allows the implementor to state the important properties of
the operator with regard to optimization. ``Machine independent''
optimizations, such as moving code out of loops, are written to
interrogate this information, enabling a single specification to be
applicable to code at many levels for many source languages and target
machines.


The language schema and description languages provide the possibility of
writing optimizations in a context-independent manner, but the environment
must also give special support to ease this writing. Dora includes
attribution and transformation languages based on pattern matching. The
pattern language is grounded in the efficient automata-driven tradition,
but with important extensions for natural handling of variable-arity
operators and repetitive vertical constructs such as left-associated
addition trees. The attribute system uses the pattern matching system to
gain the descriptive advantages of an attribute grammar system (easy
access to local context and a declarative functional specification)
without inheriting the difficulties of a monolithic specification factored
by an often irrelevant abstract syntax. The transformation language uses
the pattern matching system for local context, while relying on the
attribute system for global analysis.


Dora has been used to implement a functional prototype of Frederick Chow's
optimizer UOPT. The example prototype demonstrates the support Dora
provides for building actual optimizers. It also makes possible
previously infeasible experiments, such as reordering the optimizations,
adding non bitvector-based optimizations to the suite, and applying UOPT
to languages in the LISP tradition.


******************************************************************************


System Name: ISTS (the Interactive Space-Time Scheduler)
Specification Language: Simple single assignment language with arithmetic
operators
Problem Domain: Static algorithms (basic blocks or equivalent in
imperative languages)
Target languages: Pseudo code for synchronous parallel straight-line
programs with annotations for placement of
processors (2-D integer coordinates)
Transformation process: Manual, interactive scheduling in 3-D space-time
through graphics interface
Status 1991: First prototype implemented, producing small
parallel straight-line programs
Overview Publication: Bj\"orn Lisper "The Interactive
Space-Time Scheduler", Microprocessing
and Microprogramming, vol 30 no 1-5,
pp. 109-116, Aug. 1990
Research Group: Distributed Systems Lab
Contact: Bj\"orn Lisper
email: bjornl@tds.kth.se
phone: 46-8-7907865, 46-8-7521547
Organization: Swedish Institute for Computer Science
Address: P.O. Box 1263, S-164 28 Kista, Sweden


***************************************************************************


System Name: [Kelsey Thesis]
Problem Domain: Compilation
Specification Language: Pascal/Basic; internal form is Lambda calculus variant
Target languages: Lambda calculus variant; MC68020
Transformation process: Source to source transformations
Control Regime: Remove any dependencies from intermediate language
semantics that target machine cannot implement
directly.
Advice accepted: ?
Key focus: Compilation using denotational semantics concepts
[? ed].
Status 1989: Operational.
Biggest Difficulties:
Overview Publications: Richard Kelsey, "Compilation by Program
Transformation", Phd Thesis, Yale University, 1989
YALEU/CSD/RR #702, May 1989.
Research Group:
Contact:
email:
phone:
Organization:
Address:


******************************************************************************


System Name: KIDS (Kestrel Interactive Development System)
Specification Language: First-order axiomatic theories, REFINE, REGROUP
Input and output conditions are attached to functions
Some higher-order constructs
Problem Domain: Variable
Restriction: no state
Target languages: REFINE
Transformation process: 1. Synthesis by building a theory morphism
from an algorithm theory (e.g.,
global search) to a problem theory (e.g.,
k-queens).
2. Synthesis mediated by a
"directed-inference" system. Typical case:
extend a partial theory morphism between
problem theory and algorithm theory to a
full morphism. Example: given a
decomposition operator, produce a spec for
the composition operator in a
divide-and-conquer theory.
3. Instantiation of program schemes associated
with each algorithm theory (i.e.,
incorporate canned implementation knowledge)
5. Simplification (context independent, e.g.,
"if true then ...", and context dependent,
e.g., simplify "if x > 0 then ..." under
the assumption "x in [1..10]").
Simplification rules derived from axioms in
the problem theory.
6. Optimization using standard transformation
techniques such as fold/unfold, finite
differencing, partial evaluation, loop fusion, etc.
7. Data structure selection and refinement
Status 1991: Implemented, producing small runnable programs
Examples: topological sort, costas arrays,
k-queens, max-sum-subsegment, binary-search
trees, several kinds of sorting algorithms,
cyclic-difference sets, scheduling
Overview Publication: KIDS: A Semiautomatic Program Development System,
Douglas R. Smith, IEEE TSE, Vol 16, No 9, 1990,
pp 1024-1043.
Research Group: Kestrel Institute
Contact: Maria Pryce
email: maria@kestrel.edu
Organization: Kestrel Institute
Address: 3260 Hillview Ave
Palo Alto, CA 94304
Phone: (415) 493-6871


***************************************************************************


System Name: Mural
Specification Language: generic, with particular instantiation for
                                                specification and refinement using VDM
Problem Domain: non-specific
Target languages: none as yet
Transformation process: Specifications and refinements ("reifications") are
translated to formal theories, including proof
obligations.
Control Regime:
Advice accepted:
Key focus: Emphasis on user-guided machine-assisted proof.
Status 1991: Implemented, used to develop a number of examples
                                                (eg topological sort algorithm).
Biggest Difficulties:
Overview Publications: "Mural: A Formal Development Support System"
                                                CB Jones, KD Jones, PA Lindsay, R Moore
                                                Springer-Verlag 1991
                                                "Reasoning about VDM Developments Using the VDM
                                                Support Tool in Mural"
                                                JC Bicarregui, B Ritchie,
                                                VDM'91 Proceedings
Contact: Richard Moore (MU) and Brian Ritchie (RAL)
email: richard@uk.ac.man.cs br@uk.ac.rl.inf
phone: +44 61 275 6273 +44 235 44 6147
Organization: Manchester University (PEVE Unit)
                                                and Rutherford Appleton Laboratory (Informatics Dept.)
Address: MU: Dept. of Computer Science,
                                                        Victoria University of Manchester,
                                                        Oxford Road, Manchester, UK.
                                                RAL: Chilton, Didcot, Oxon OX11 0QX, UK


You asked for information about systems that "may" fall into the category
of program transformation/synthesis. Here's one that might...
I apologise for the length of this posting, and hope its not too off-putting!
If you want to skim it, it ends with the "initial comparative information"
that you requested.


We (Manchester University and Rutherford Appleton Laboratory) have developed
(and continue to develop) a "formal development support system" called Mural.
The primary aim of the system is to support the construction of and reasoning
about formal specifications and refinements. This may or may not fit within
the area of program synthesis and/or transformation, and we've not used it
to develop any system "all the way" to a particular implementation language.


The central part of Mural is a hierarchically-structured theory store based
on a generic logical notation, and tools to support the construction of
proofs of results within those theories. As an example, one theory store has
been built containing theories of the logic and basic data types used in VDM.
A separate set of tools can be used to build VDM specifications and to
construct refinement (or reification) relationships between them; these are
then "translated" to produce new Mural theories (built on top of the "basic
VDM" theory store which include definitions and axioms corresponding to
definitions in the specification/reification together with proof obligations
which should be discharged in order to validate the design.


Let me try and see how I believe Mural fits with the criteria you list:


        a) A specification language (anything that can be interpreted as
              a predicate over acceptable generated programs, including
              abstract programs)


Mural is being used to construct and reason about both specifications and
refinements in VDM. I've also done a tiny amount on building a theory for
(user-guided) rewriting of Basic LOTOS behaviour expressions. The book
referred to below contains numerous examples of formal systems expressed in
Mural (lambda calculi, Hoare logic, as well as VDM).


        b) A transformation or synthesis engine, applying rewrite rules
              explicitly or procedurally. Any control regime is acceptable.


The emphasis is on user-constructed proof, with the machine helping the user
explore possible proof directions (for example, by finding the set of rules
that match a given part of a proof). There is a tactics language of a sort,
and this has been used to write tactics that allow user-directed rewriting
(ie repeatedly select a subterm and a rewrite rule to apply to it).
The only control regime is that a proof won't be considered complete until
you've correctly justified each step. You can tackle a proof in any manner
you like (forward from known (justified) lines, backward from goal lines, or
by adding "midway" lines as stepping-stones). Rules can be used in other
proofs (but not their own!) before they themselves are proven. Mural will
maintain all the dependencies, so the user can always find out what remains
to be done. There's no specific support for transformational refinement.
The refinement part of the VDM support tools concentrates on data refinement:
it handles data reification and operation modelling, but not operation
decomposition.


        c) The intent that the rule base be augmented over time,
              by others than the maintainers of the system.


A Mural theory store contains a hierarchy of individual theories. Each theory
contains a signature of declared expression and type constants, and binders
(egs universal and existential quantifiers, set comprehension, ...) These
may be defined either directly in terms of other constants, or by axiomatic
definitions. In addition to axioms, a theory can also contain derived rules,
which express properties that the designer believes should follow from the
axioms and definitions. These rules can have (possibly partial) proofs of
their validity. A theory inherits all the formal information from its parents
(hence the hierarchy). It is always possible to add new rules to a theory,
even if the theory is "closed" (which prevents users from changing its
signature or axioms); thus, if someone working with a particular VDM
specification decides that a result they require for some proof is best
generalised to a (hopefully derivable) result of set theory, then they can
add this result as a new rule to the appropriate theory, rather than adding it
as a "local" rule to the theory of the specification. This increases the
result's "reusability".


        d) Possession of a running implementation, or significant
              resources committed to obtaining an implementation


Mural is implemented in Smalltalk-80 (version 2.5: porting to version 4 is
seen as a serious problem, as Mural is about 80% user interface). The
"kernel" was initially specified in VDM.


        e) Expectation that something larger than a toy program will
              be constructed, often in a language different
              of the specification langauge.


This is where we fall down, to date anyway. Mural has been used primarily to
check abstract specifications, and (slightly) more concrete reifications of
them. To my knowledge, no-one has developed a serious piece of code from it
(only some serious specifications!) I could be wrong - I'm not completely
au fait with the commercial applications (Richard Moore may have more info
on this).


The commercial bit: Mural is available for industrial and academic use.
Interested industrial organisations are invited to contact Richard Moore
at the PEVE Unit of Manchester University (address below) for further details.
Rutherford Appleton Laboratory handle academic distribution and licencing;
contact Brian Ritchie at the address below for more details. (Roughly,
the academic licence insists that the recipient have the "right to use"
Objectworks for Smalltalk-80, version 2.5, and that Mural not be used for
financial gain. 100 pounds handling charge gets you a Smalltalk image of
Mural (with VDM theory store and tools) plus user documentation.)


******************************************************************************


System Name: Phideo (Esprit project 2260, also called SPRITE)
Specification Language: Silage, ELLA, and others
Problem Domain: VLSI architecture synthesis for bit-parallel,
micro programmed Digital signal processors.
Specifically for real-time video processing.
Target: custom chip.
Transformation process: Hardware, module allocation followed by scheduling.
Overview Publication: See EDAC'91, Lippens et.al.
Research Group: VLSI Design
Contact: Jos Huisken and others
email: sprite@prl.philips.nl
phone: +31-40-742824
Organization: Philips Research Laboratories, Eindhoven, Netherlands
Address: PO Box 80.000, WAY-41


******************************************************************************


System Name: PIER
Specification Language: Instantiate numerical operations from PIER
Knowledge base. User specifies Input/Ouput data
objects and execution styles for each operation.
Operations are composed in PIER modules and fit
into F77 templates. The templates are used for
representing program control flow and other fixed
programming structures.
Problem Domain: Finite Element Codes Target
Language: F77, Sequent Parallel Fortran and W2
(for Warp Systolic Computer).


Transformation Process: Procedural refinement based on execution styles for
each operation. Scheduling codes are automatically
generated after data dependence ananlysis of PIER
modules.
Status 1991: Implementation work is in progress.
A few simple (test) programs generated.
Overview Publications: (a) Sharma, N., "PIER: A Parallel Finite Element
Analysis Programming", (Outline for Doctoral
Dissertation-August
1991), Department of Math./CS., Kent State University,
Kent, OH 44240,
(b) Sharma, N., ``Generation of Finite Element
Programs for Multiprocessors'', presented at Fifth
SIAM Conference on Parallel Processing for
Scientific Computing, Houston, TX, March 1991.
(c) Sharma, N. and Wang, P. S., ``Generating Finite
Element Programs for Shared Memory Multiprocessor'',
ASME Winter Annual Meeting, Dallas, TX, November 1990.
Contact: Naveen Sharma, Research Assistant, Deptt. of Math/CS.,
Kent State Univ., Kent OH 44240.
Ph: 1-216-672-3319
Email:sharma@mcs.kent.edu
Organization: Institute of Computational Mathematics,
                                                Dept. of Math/CS., Kent State Univ., Kent OH 44240.


******************************************************************************


System Name: Piramid (Esprit project 97)
Specification Language: Silage
Problem Domain: VLSI architecture synthesis for bit-parallel,
micro programmed Digital signal processors.
Specifically in Audio Digital Signal Processing.
Target: custom chip.
Transformation process: Hardware, module allocation followed by scheduling.
Overview Publication: not by hand currently (I'm at home... :-)
Research Group: VLSI Design
Contact: Jos Huisken and others
email: huisken@prl.philips.nl piramid@prl.philips.nl
phone: +31-40-742824
Organization: Philips Research Laboratories, Eindhoven, Netherlands
Address: PO Box 80.000, WAY-41


******************************************************************************


System Name: Popart
Specification Language: Extended BNF + Transformationally expressed "syntax
                                                directed experts"
Problem Domain: Arbitrary language applications
Target languages: Lisp, Ada, C++
Transformation process: Symbolic and procedural refinement of language
sentences. Automatic invocation of sets of
transformations with declarative user guidance.
Metaprogramming language (Paddle) for ad hoc
transformational developments.
Status 1991: Implemented, used with multi-thousand line metaprograms.
Overview Publication: David S. Wile, "Program Development: Formal Explanations
                                                of Implementations," CACM, 1983 (26:11), pp. 902-911.
Research Group: Annotations + Metaprogramming
Contact: Dave Wile
email: wile@isi.edu
phone: 1-213-822-1511 x248
Organization: USC/Information Sciences Institute
Address: 4676 Admiralty Way
                                                Marina del Rey, CA 90292
Pointers: Lewis Johnson (johnson@isi.edu): KBRA project (user)
                                                Ramesh Patil (ramesh@isi.edu): knowledge base
translation
***************************************************************************


System Name: PROSPECTRA
Problem Domain: Compiling algebraic specifications
Specification Language: Algebraic specifications
Target languages: Functional programs
Transformation process:
Control Regime: Metaprograms specified algebraically.
Advice accepted:
Key focus: [Algebraic specification of everything. -ed.]
Status 1993: Defunct [? -ed]
Biggest Difficulties:
Overview Publications: Bernd Krieg-Bruckner, "The PROSPECTRA Methodology of
Program Development", in "IFIP/IFAC Working Conference
on Hardware and Software for Real Time Process
Control", Warsaw, 1988, North-Holland, 1-15.
B. Krieg-Bruckner,
"ESPRIT Project Report #390: Algebraic
Specification with Functionals in Program
Development by Transformation", in "Esprit 89:
Proceedings of the 6th Annual Esprit Conference",
Brussels, Belguim, Luwer Academic Publishers,
Dordrecht, The Netherlands, 1989.
Research Group: PROSPECTRA
Contact: Professor Bernd Krieg-Bruckner
email: bkb@informatik.uni-bremen.de
phone: +49-421-2183660 or 2183054 (fax)
Organization: Bremen University
Address: Bibliothekstrasse 1. D-2800 Bremen 33.


******************************************************************************


System Name: Program Transformation Notation (PTN)
Specification Language: Program Composition Notation (PCN)
Problem Domain: General purpose
Target languages: PCN
Transformation process: Procedural, SIMD-style refinement of programs
Status 1991: Implemented as part of PCN parallel programming system.
Producing large, multi-module runnable programs.
Overview Publication: "PTN: A Tutorial Introduction", Ian Foster,
Mathematics and Computer Science Division,
Argonne National Laboratory, Argonne IL 60439
Research Group: Mathematics and Computer Science Division
Contact: Ian Foster
email: foster@mcs.anl.gov
phone: 1-312-972-4619
Organization: Argonne National Laboratory
Address: 9700 South Cass Ave
                                                Argonne, IL 60439
******************************************************************************
System Name: PVC-M (For Process-Oriented Version & Configuration
Management System)
Specification Language: XDL (An Object-Oriented Extension to CCITT's SDL)
Problem Domain: Telecom Software, Software Configuration Management
Target languages: Currently C++. Considering BETA and other existing
SDL CASE tools
Transformation process: Translation of graphical/textual process descriptions
Status 1991: Actual transformation not yet implemented. A rudimen-
tary demo exists, though
Overview Publication: "A Process-Oriented Version and Configuration Management
Model for Communications Software" in Proceedings of
the 3rd Intl Workshop on Software Configuration
Management, pp 109-120, June 1991, ACM Notices
(by S.J. Ochuodho & A.W. Brown; ed. P. Feiler)


"XDL: An Object-Oriented Extension to SDL" in
Proceedings of the 5th International SDL Forum, Sept
1991 (to appear), pp 35-47, Elsevier (North Holland)
(by S.J. Ochuodho & A.W. Brown; eds. O. Faergemand
& R. Reed)
Research Group: Database & Information Systems
Contact: Shem J. Ochuodho
email: shem@minster.york.ac.uk
phone: +44 904 432746
Organization: Dept of Computer Science, University of York
Address: Heslington, York YO1 5DD, United Kingdom


You may also wish to contact Birger Moeller-Pedersen, email address
Birger_Mollerpedersenn_NORWEGIAN_COMP_CTR@eurokom.ie. They are doing
some work with OSDL, another Object-Oriented SDL variant.


******************************************************************************


System Name: Sabre/INRIA
Problem Domain: Database query optimization
Specification Language: [Relational Algebra? -ed]
Target languages: CM Fortran, Fortran77, C
Transformation process: Symbolic and procedural refinement of program schemas
Advice accepted: Heuristics for making decisions in the refinement
space.
Key focus: Generation of efficient supercomputer codes
                                                from mathematical specifications
Status 1993: Implemented, producing runnable 500-1000 line
programs.
Overview Publication: "Scientific Programming by Automated Synthesis",
                                                E. Kant, F. Daube, W. MacGregor, J. Wald,
                                                in Automating Software Design, M. Lowry and R.
McCartney, eds., AAAI Press, 1991
Research Group: Modeling and Simulation
Contact: Mikal Ziane
email: mikal@lolita.inria.fr
phone: 1-512-331-3714
Organization: BULL and INRIA ROCQUENCOURT
Address:


It seems that an extensible query optimizer for a database system may
match your requirements. Typical systems are Exodus and Starbust but there
are others. I can give you some references I you want. The specification
is for example a relationnal algebra program. Transformation rules are
often used. The goal being extensibility the support for new rules is a
major objective. Several prototypes already exists which support realistic
queries. This topics was very fashionable 3 years ago but is less now
because extensibility seems really very difficult. A rule-based approach
is not a sufficient anwer. I believe that a deep implementation of the
underlying concepts of optimization is necessary. "Deep" meaning that not
only a superficial and transient aspect of the concepts should be
implemented, but that as much knowledge as possible about a concept should
be supported. This is of course obvious for an AI person but this is
surprisingly almost never discussed by database people.


Our project (projet Sabre at INRIA) develops the physical optimizer
of the EDS ESPRIT II project. Another team develops the logical
optimizer. The logical optimizer is rule-based. The physical optimizer
is not rule-based because of efficiency reasons, but I am working on a
declarative language allowing to extend more easily the optimizer.
A first limited attempt against extensibility, was made at a software
engineering level. We wanted to see how far an object-oriented design
and implementation could help. The result is that we get the classical
software engineering advantages (which should not be neglected) but
the semantical barrier between an object oriented language such as C++
and a conceptual model of an optimizer is not much smaller than with
a language like C. Encapsulation is nice but inheritance was only moderaltely
useful. Also the complexity of the program becomes quickly a major problem.
Thus an independant declarative language compiled seems a better approach.


I was amazed to see that the number of projects working on AP in
the world in so small. I visited the Programmer's Apprentice project
and Dr Waters told me that the phrase "Automatic Programming"
was almost taboo. I hope it is slowly changing.


***************************************************************************


System Name: Similix
Specification Language: Recursive higher order function definitions
(concrete Scheme syntax)
Problem Domain: compiler generation (interpreter-to-compiler
transformation), or almost any Scheme program
Target languages: Scheme
Transformation process: Partial evaluation, guided by binding time
analysis
Status 1991: implemented, used to produce 1000-2000
line compiler for (full) functional
lazy language and smaller programs so far;
available via anonymous ftp
Overview Publications: Anders Bondorf, "Automatic Autoprojection
of Higher Order Recursive Equations",
ESOP '90, Springer LNCS 432, pp. 70-87.
Research Group: TOPPS -- Partial Evaluation (Neil Jones)
Contact: Anders Bondorf
email: anders@diku.dk
phone: +45-31 39 68 61
Organization: DIKU, University of Copenhagen
Address: Universitetsparken 1
DK-2100 Copenhagen East, Denmark


If you plan on including partial evaluation systems generally you can
take a look at the proceedings of the recent Partial Evaluation and
Semantics-Based Program Manipulation (PEPM) conference, which was
held at Yale in June of this year.
******************************************************************************
System Name: Sinapse
Problem Domain: Numerical modeling codes
Specification Language: Partial Differential Equations,
                                                Schema slot fillers,
                                                Various atomic performance goals
Target languages: CM Fortran, Fortran77, C
Transformation process: Symbolic and procedural refinement of program schemas
Control Regime: Partially-ordered synthesis tasks with subtasks.
Advice accepted: Heuristics for making decisions in the refinement
space.
Key focus: Generation of efficient supercomputer codes
                                                from mathematical specifications
Status 1993: Implemented, producing runnable 500-1000 line
programs.
Biggest Difficulties: Defining complete specification language for
mathematical models. Acquisition of useful
refinements.
Generation of efficient parallel code.
Overview Publications: "Scientific Programming by Automated Synthesis",
                                                E. Kant, F. Daube, W. MacGregor, J. Wald,
                                                in Automating Software Design, M. Lowry and R.
McCartney, eds., AAAI Press, 1991
E. Kant, "Synthesis of Mathematical Modeling
Software", IEEE Software v10 #3, May 1993.
Research Group: Modeling and Simulation
Contact: Ira Baxter
email: baxter@slcs.slb.com
phone: 1-512-331-3714
Organization: Schlumberger Laboratory for Computer Science
Address: PO Box 200015
                                                Austin, Texas, 78720
******************************************************************************


System Name: (Unnamed)
Specification Language: Not applicable, transforms source directly
                                                [This appears to mean Scheme. -ed].
Problem Domain: Tool-Assisted Global Program Restructuring as an
Aid to Maintenance
Target languages: Scheme and other LISP variants
Transformation process: Maintain semantic invariants in AST, CFG, and PDG
Status 1991: Prototyped, transforming 300 line programs
Overview Publication: W. G. Griswold, "Program Restructuring as an Aid to
Software Maintenance", Ph.D. Thesis, University of
Washington, Technical Report 91-08-04, August, 1991.
Research Group: (Unnamed)
Contact: William Griswold or David Notkin
email: wgg@cs.ucsd.edu, notkin@cs.washington.edu
phone: (619) 534-6116, (206) 685-3798
Organization: UC San Diego and Univ. of Washington
Address: UC San Diego
                                                Dept. of Computer Science and Engineering, 0114
La Jolla, CA 92093-0114


                                                Dept. of Computer Science and Engineering, FR-35
University of Washington
Seattle, WA 98195


David Notkin and I have a transformation system that automates the
non-subjective aspects of restructuring program source to improve program
structure for future changes. Although this is not derivational
programming, it is a powerful application of transformational techniques
to ease programming activities. We use the Control Flow Graph and Program
Dependence Graph as internal representations to help maintain the
necessary semantic invariants that allow error-free global restructuring.


******************************************************************************


System Name: [Wolff Thesis.]
Specification Language: Relational specifications. We define a problem by
means of fonctional constraints on input/output
behavior.
Target languages: functional language (lisp)
Status 1991: I haven't a system yet but I hope to develop a
little one the next year. I'll use KIDS (Kestrel
Interactive Development System). KIDS is a
semiautomatic Program Development System.
Research Group: PROGRAIS
Contact: Patricia Wolff
email: wolff@loria.crin.fr
phone: 83-91-23-89
Organization: CRIN (Centre de Recherche en Informatique de Nancy)
Address: BP 239- 54506 Vandoeuvre-le`s-Nancy
                                               France


Topic of my thesis:
Design a program from a formal specification by using
the following reasoning :"if you cannot directly
solve a problem, first try to solve another problem
(more general, more specialized or related problem)
which seems to be easier to solve".
In order to model this reasoning, I determine:
- some transformations modifying the initial
    specification in order to get a new problem (this
    transformation don't preserve the whole specification
    semantics but we want control the semantics
    modification)
- some transformations to design a correct program
    from a specification (in our case, from the new
    defined specification).
- some means (program transformations or program
    development modifications) to obtain a correct
    program for the initial specification from the first
    designed program.


[I believe Patricia is now at Kestrel Institute doing this work. -ed].


--
Ira Baxter email: baxter@slcs.austin.slb.com ph: 1-512-331-3714
Schlumberger Laboratory for Computer Science
8311 North RR 620 [for snail mail, use PO Box 200015 instead]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.