next up previous
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




http://www.cs.utexas.edu/users/novak
novak@cs.utexas.edu


(512) 471-9569










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.

Technical Challenges


Our Approach


GLISP Language and Compiler


Views



\begin{picture}(300,120)(0,0)
\thicklines {\Large
\put(0,80){\line(1,0){40}}
...
...{\makebox(0,0){Generic}}
\put(215,22){\makebox(0,0){Procedure}} }
\end{picture}

A Simple View



\begin{picture}(320,240)(0,0)
{\large {\tt
\thicklines
\put(0 ,0){\framebox ...
... view type}}
\put(180,230){\makebox(0,0)[l]{\em abstract type}} }
\end{picture}




(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
simulation. cf.: Isomorphism of semigroups 1

Given two semigroups $ G_{1} = [S, \circ] $ and
$ G_{2} = [T, \ast] $, an invertible function
$ \varphi : S \rightarrow T $ is said to be an isomorphism between G1 and G2 if, for every aand b in S,

$ \varphi (a \circ b) = \varphi (a) \ast \varphi (b) $
from which: $ a \circ b = \varphi ^{-1} ( \varphi (a) \ast \varphi (b) ) $





\begin{picture}(520,220)
\put(140,10){\makebox(0,0){$ a \circ b $ }}
\put(140,10...
...put(180,140){\vector(-1,-1){30}}
\put(380,140){\vector(-1,-1){30}}
\end{picture}

Views as Isomorphisms



\begin{picture}(350,150)
\put(20,10){\makebox(0,0){\shortstack{Concrete\\ Result...
...}
\put(400,110){\vector(0,-1){20}}
\put(400,50){\vector(0,-1){23}}
\end{picture}






\begin{picture}(350,150)
\put(20,10){\makebox(0,0){$ area $ }}
\put(20,130){\mak...
...}
\put(400,110){\vector(0,-1){25}}
\put(400,55){\vector(0,-1){30}}
\end{picture}

Requirements of Views


Making Views


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.

Example: Sorted Linked List


(part (name string)
      (size integer)
      (next (^ part)))

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)))

(LAMBDA (X)
  (* 3.1415926535897931
     (* (FIFTH X)
        (SQRT (+ (EXPT (FIFTH X) 2)
                 (EXPT (CADDR X) 2))))))

Mathematical Views: MKV



\begin{picture}(200,50)(0,0)
\put(25,25){\circle{20}}
\put(100,25){\circle{20}...
...or(-1,0){55}}
\put(38,28){ {\em view}}
\put(114,28){ {\em view}}
\end{picture}

Line Segment


A line segment could be represented in many ways:

The figure presents variable buttons to allow nearly any representation to be specified easily.

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)

(LAMBDA (VAR-LS1)
  (LET ((VAR-LS1-VIEW VAR-LS1))
    (LIST 'LS2
          (- (FIFTH VAR-LS1-VIEW)
             (* (CADDR VAR-LS1-VIEW)
                (COS (CADDDR VAR-LS1-VIEW))))
          (FIFTH 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.

Calculation of the Mass of the Sun

result type: (UNITS REAL KILOGRAM)

(LAMBDA () 1.9660057055546021E30)

Aircraft Position from Radar Data
(vip
  '((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)
                                         4096)))
    (RADAR-UTM         UTM-VECTOR))

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)
                                        4096))
         RADAR-UTM:UTM-CVECTOR)
  (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))
    OUTPUT))

Aircraft Position Program in C
CUTM  *tqc (time_diff, aircraft_altitude, radar_altitude,
            radar_angle, radar_utm)
  long time_diff, aircraft_altitude, radar_altitude,
       radar_angle;
  CUTM  *radar_utm;
  {
    long out7;
    CUTM  *output;
    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
                             * lsquare(out7));
    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;
    return output;
  }

Language Translation


Specialized procedures can be delivered in several languages: Lisp, C, C++, Java, Pascal.

Automatic Programming Server


The Automatic Programming Server operates over the Web and writes specialized procedures for the user.

Automatic Programming Server


Program Framework


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:

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.

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.

Future Work


Graphical program specifications as used in VIP could be adapted for specification of larger programs using frameworks.

Constraint propagation and symbolic inference can fill in details based on major decisions by the user.

Related Work

Summary


Views are powerful.

These techniques may achieve the grand challenge of making programming much easier by reuse of components.

Constraint Propagation



  
Figure 1: Simple Example Framework
\begin{figure}
\begin{center}
\addtolength{\unitlength}{-.5\unitlength} %
\begin...
...nd{picture}\end{center}\addtolength{\unitlength}{+1.0\unitlength} %
\end{figure}

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 via rules.

result type: INTEGER
(LAMBDA (SEQ3)
  (LET (ITEM4 ACC5)
    (SETQ ACC5 0)
    (DOLIST (ITEM4 SEQ3) (INCF ACC5 ITEM4))
    ACC5))



 
next up previous
Next: About this document ...
Gordon Shaw Novak
2001-09-20