Next: About this document ...
Software Reuse by Specialization of Generic Procedures through Views
Gordon S. Novak Jr.
Department of Computer Sciences
University of Texas at Austin
Austin, Texas 78712
September 20, 2001
Challenge: Make Programming Easier
The progress of computing is limited by the difficulty, delay, and expense
of programming. A grand challenge of computer science is to
enable programming by composition of large-scale components.
- Reuse generic algorithms rather than rewriting
- Adapt generic procedures for the application
- Raise the level of programming:
- from coding of details
- to module integration
- Reduce the detail that must be specified explicitly
- Software must be customized for the application
- Correct and efficient code must be produced
- Must reduce human cost:
- Reduce input
- Reduce learning
- Combine components (procedures and data) that
are not designed to fit together a priori.
- Specialization of generic procedures
- Views describe how concrete types correspond to abstract types
- User interfaces make it easy to create views
- VIEWAS: data structure views
- MKV: mathematical views
- Language translation: one system and one set of generics delivers code
in Lisp, C, C++, Java, Pascal.
- Automatic Programming Server synthesizes code for user over Web
- VIP: construction of scientific programs from diagrams
- Program Frameworks: collections of data structures and procedures
- Future work: Automated assistance to instantiate frameworks
- Constraint propagation
- Expert systems
GLISP Language and Compiler
- GLISP (Generic Lisp) is a typed Lisp
- Goal: code independent of data representation
- Single form of access to properties:
whether property is stored or computed.
- Can store back through a computed property by algebraic inversion:
( x * 2 := y )
or by a procedure.
- Methods and inheritance as in OOP
- In-line expansion or specialization of methods
- Expansion is recursive at compile time:
- An operation expands to sub-operations on the implementation
- Large code expansion is possible
- Types inferred and propagated during expansion
- Partial evaluation and pattern-based optimization:
- eliminates message sending at runtime
- optimizes code
- Loops use iterator macros
- A view makes a concrete type appear as an abstract type;
it encapsulates a concrete type and adapts it for use with a generic procedure.
- A view has:
- concrete type as its stored form
- abstract type as a superclass
- methods that translate from the concrete type to basis variables of
the abstract type
- cf. Wrapper or Adapter class in OOP [Gamma]
- Application objects may have many views.
For example, an airplane is:
- a machine
- a financial asset
- a location in space
A Simple View
(gldefun t1 (pz:pizza)
(area (circle pz)))
(LAMBDA (PZ) (* 0.78539816 (EXPT (CADR PZ) 2)))
Computation as Simulation
A useful view is to think of all computation as
cf.: Isomorphism of semigroups 1
Given two semigroups
and from which:
, an invertible function
is said to be an
isomorphism between G1 and G2 if, for every aand b in S,
Views as Isomorphisms
Requirements of Views
- An abstract type is defined as an abstract record containing a set of
- Generic procedures are written in terms of the basis variables.
- A view type emulates the abstract record using the
concrete record as storage:
- storage property: after a value is stored into a basis
variable, a read of the basis variable returns the same value.
- independence property: storing into one basis variable does
not change the values of others.
- A store into a basis variable may require updating several concrete
- Slight inaccuracy in emulation may be allowed (e.g., floating point
round-off error in representing (x, y) using
- Views may be complex: an example line-segment view is
67 lines of code.
- Views may be error-prone if written by hand: storage and
independence properties must be maintained.
- Difficulty of coding view types detracts from benefit of reuse.
- Automated assistance for making views is needed.
Data Structure Views: VIEWAS
The VIEWAS system makes a view of a concrete type as a data structure
type, such as a linked-list or avl-tree.
- VIEWAS makes correspondences between abstract and concrete records
- Values, e.g. field to sort on
- Choices, e.g. sort-direction
- Groups of fields, e.g. contents is everything except the
- Type filtering and propagation of choices reduce input from user;
simple views can be made automatically.
Example: Sorted Linked List
(part (name string)
(next (^ part)))
- The link pointer is inferred to be the next field:
the only possibility allowed by type filtering.
- The sort-value is selected as name by the user.
- The sort-direction is selected as ascending.
The user only needs to make two choices from menus; then any
procedure defined for sorted-linked-list can be specialized
for the user's data.
Standard data structure templates can easily be instantiated with
a given contents.
Views by Graphical Correspondences
Views can be specified by graphical correspondences between user data
and a diagram of an abstract object.
Example: View a Christmas tree as a cone.
>(mkv 'cone 'xmas-tree)
(gldefun tg (x:xmas-tree) (side-area (cone x)))
(* (FIFTH X)
(SQRT (+ (EXPT (FIFTH X) 2)
(EXPT (CADDR X) 2))))))
Mathematical Views: MKV
- User makes correspondences between a diagram of the abstract type
and a menu of fields and computed properties of the concrete type.
- Buttons on the diagram correspond to variables of the abstract type
- Equations associated with abstract type are solved by symbolic algebra
- A button is removed from diagram when solved; this prevents inconsistent
- Symbolic algebra is used to make a view that maintains storage and
- An instance of concrete type can be created from a set of basis
- Data translation is possible through views as a common abstract type:
A line segment could be represented in many ways:
The figure presents variable buttons to allow nearly any representation
to be specified easily.
- two end points
- one end point, length, theta
- one end point, slope, delta-x
Example of Line Segment View
(mkv 'line-segment 'ls1)
(gldefun tb (l:ls1 p:consv)
(leftof-distance (line-segment l) p))
result type: REAL
(LAMBDA (L P)
(- (* (COS (CADDDR L))
(- (CDR P) (CADR L)))
(* (SIN (CADDDR L))
(- (CAR P)
(- (FIFTH L)
(* (CADDR L) (COS (CADDDR L))))))))
Line Segment Data Conversion
(mkv 'line-segment 'ls2)
(gleqns-transfer-by-view 'ls2 'ls1)
(LET ((VAR-LS1-VIEW VAR-LS1))
(- (FIFTH VAR-LS1-VIEW)
(* (CADDR VAR-LS1-VIEW)
(COS (CADDDR VAR-LS1-VIEW))))
(- 1.570796 (CADDDR VAR-LS1-VIEW))
(+ (CADR VAR-LS1-VIEW)
(* (CADDR VAR-LS1-VIEW)
(SIN (CADDDR VAR-LS1-VIEW)))))))
Advantages of Graphical Correspondences
Programming by Graphical Correspondences
Related techniques make it possible to write scientific programs and
solve physics problems.
- The initial diagram consists of boxes that represent input data
and an output box.
- Physical laws and geometric models may be selected by menu and
added to the picture.
- Connections may be made between diagram buttons and data.
- A program is generated from the diagram by symbolic data flow:
- Initially, input data and constants are defined.
- When a data item becomes defined, its value is propagated into
boxes to which it is connected.
- When a value is propagated into a box, equations associated with
the box are examined to see whether they can be solved for other variables.
- Code is generated as a side-effect of the data flow.
- Units of measurement are converted automatically.
Calculation of the Mass of the Sun
result type: (UNITS REAL KILOGRAM)
(LAMBDA () 1.9660057055546021E30)
Aircraft Position from Radar Data
'((TIME-DIFF (UNITS INTEGER (* 100 NANOSECOND)))
(AIRCRAFT-ALTITUDE (UNITS INTEGER (* 10 FOOT)))
(RADAR-ALTITUDE (UNITS INTEGER (* 10 FOOT)))
(RADAR-ANGLE (UNITS INTEGER (/ (* 2 PI RADIANS)
Aircraft Position Program
(LAMBDA (TIME-DIFF: (UNITS INTEGER (* 100 NANOSECOND))
AIRCRAFT-ALTITUDE: (UNITS INTEGER (* 10 FOOT))
RADAR-ALTITUDE: (UNITS INTEGER (* 10 FOOT))
RADAR-ANGLE: (UNITS INTEGER (/ (* 2 PI RADIANS)
(LET (OUT7 OUTPUT D3 OUT8 X5 Y3 X6 RELPOS:UTM-CVECTOR)
(OUT7 := (- AIRCRAFT-ALTITUDE RADAR-ALTITUDE))
(D3 := (* '(Q 2.997925E8 (/ M S)) TIME-DIFF))
(OUT8 := (/ D3 2))
(X5 := (SQRT (- (EXPT OUT8 2) (EXPT OUT7 2))))
(Y3 := (* X5 (SIN RADAR-ANGLE)))
(X6 := (* X5 (COS RADAR-ANGLE)))
(RELPOS := (A UTM-CVECTOR NORTH Y3 EAST X6))
(OUTPUT := (+ RELPOS RADAR-UTM))
Aircraft Position Program in C
CUTM *tqc (time_diff, aircraft_altitude, radar_altitude,
long time_diff, aircraft_altitude, radar_altitude,
float d3, out8, x5, y3, x6;
CUTM *relpos, *glvar4796;
out7 = aircraft_altitude - radar_altitude;
d3 = 2.997925E8 * time_diff;
out8 = d3 / 2;
x5 = sqrt(square(out8) - 9.2903039999999988E14
y3 = x5 * sin(0.0015339807878856412 * radar_angle);
x6 = x5 * cos(0.0015339807878856412 * radar_angle);
relpos = (CUTM*) malloc(sizeof(CUTM));
relpos->north = 1.0000000000000001E-7 * y3;
relpos->east = 1.0000000000000001E-7 * x6;
glvar4796 = (CUTM*) malloc(sizeof(CUTM));
glvar4796->east = relpos->east + radar_utm->east;
glvar4796->north = relpos->north + radar_utm->north;
output = glvar4796;
Specialized procedures can be delivered in several languages:
Lisp, C, C++, Java, Pascal.
- Lisp is equivalent to abstract syntax trees used by compilers
- Data structures in other languages can be specified to GLISP
- Simulated data structures in Lisp can be used for rapid prototyping
- Program transformation:
- Transform Lisp features, e.g. returning a value from if statement
- Patterns transform Lisp idioms to target idioms
- Syntactic transformation: names, types, patterns
- Printing program produces formatted, readable code.
Automatic Programming Server
The Automatic Programming Server operates over the Web and writes
specialized procedures for the user.
- User describes concrete data types
- User makes views showing how concrete types correspond to
abstract types known to the system
- User selects desired procedures
- Procedures are specialized, translated to target language,
and delivered as a source code file.
- Data conversion programs can also be generated.
- Example: avl-tree: 200 lines of generated code in less
than a minute of user time.
Automatic Programming Server
A program framework is a large-scale generic program whose
components are other generics and data structures.
A framework can be instantiated by plugging in
appropriate procedural and data components.
Example: Key Word in Context (KWIC) index program.
This framework has parameters:
- Input data record. This will contain a title, and may contain
other information that will be printed.
- Noise word dictionaries. There may be a general noise word
dictionary and a domain-specific one.
- Data structures for storing instances of key words. These will be
specializations of abstract data structures, e.g. an avl-tree of symbols
with a linked list of occurrences.
- Method for printing the output.
Programming by Combining Components
Hypothesis: Although there is much detail in a program, there
are many fewer significant decisions to be made. Most details can be
derived from these decisions or defaulted.
- The title record will contain a subset of the fields of the
- Only the fields that will eventually be printed need to be stored.
- A standard dictionary of noise words will usually be adequate.
- The entry storage can be defaulted to an avl-tree containing
- A word entry will contain a string and a pointer to a linked list of
- Each occurrence will have a pointer to a title record and a column
Constraints from various parts of the program can be propagated to
specialize the data structures needed. Given the data structures and
views, the program components can be specialized.
Graphical program specifications as used in VIP could be adapted for
specification of larger programs using frameworks.
- A framework gives a large-scale structure with program and
data components to be filled in.
- Connection of two components may constrain both.
- Constraint propagation through the network can
maintain consistency and avoid redundant specification.
- Constraint violations can be treated not as errors, but as
subproblems to be solved, e.g. by converting data to the needed form.
- The system can make defaults using rules, or offer intelligent
choices of components (both data and programs).
Constraint propagation and symbolic inference can fill in details
based on major decisions by the user.
- Browne, Werth, Newton et al.: CODE/ROPE system generates code for
parallel structuring of programs.
- Batory et al.: GENESIS system allows creation of a database
system from components.
- Kant et al., Scicomp: Synapse system generates code
for numerical simulation of differential equations.
- Smith et al., Kestrel Institute: KIDS system generates code
by correctness-preserving transformations from a formal specification.
- Waldinger and Manna: generate a program by constructive proof from
a formal specification using deductive tableaux.
- Setliff: generation of wire-routing programs.
- Goguen: uses views specified as isomorphisms in OBJ.
- Gries: transforms used to transform code into application form.
- Object-oriented programming: reuse of generic procedures.
Views are powerful.
- Views enable:
- Specialization of generic algorithms
- Data translation
- Graphical interfaces
- A single view provides
access to all of the generic procedures associated with the view
(28 procedures for linked-list).
- Views are easily created with smart interfaces.
- Reuse of carefully written generic algorithms can provide
improved program quality and performance.
- Views allow easier modification of programs and data.
These techniques may achieve the grand challenge of making
programming much easier by reuse of components.
Simple Example Framework
The Iterate-Add framework is an abstraction of a large number of
programs. Specifying the type of the input as (listof integer)
allows the whole framework to be instantiated by propagation of facts
result type: INTEGER
(LET (ITEM4 ACC5)
(SETQ ACC5 0)
(DOLIST (ITEM4 SEQ3) (INCF ACC5 ITEM4))
Next: About this document ...
Gordon Shaw Novak