% slides.tex             Gordon S. Novak Jr.                 26 Jul 00

% Copyright (c) 2000 by Gordon S. Novak Jr.

\documentstyle[12pt]{article}
\pagestyle{plain}
\setlength{\oddsidemargin}{0 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{9.0 in}
\setlength{\parskip}{0.15 in}
\setlength{\parindent}{0 in}
\setlength{\topmargin}{-0.4in}
\setlength{\unitlength}{1in}
\hyphenpenalty=9990

\begin{document}           % End of preamble and beginning of text.

\sloppy
\LARGE


\begin{center}  {\bf Interactions of Abstractions in Programming} \\
\vspace*{1in}
Gordon S. Novak Jr. \\
Department of Computer Sciences \\
University of Texas at Austin \\
\vspace*{1in}
{\tt novak@cs.utexas.edu} \\
{\tt http://www.cs.utexas.edu/users/novak} \\
\vspace*{1in}
\today
 \end{center}


\pagebreak

\begin{center}  {\bf Nature of Programming} \end{center}
\vspace*{.1in}
\begin{itemize}
\item Computer programs are composed of instances of data and
procedural abstractions.

\item Programs should be built by reuse and composition of abstract
components.
   \begin{itemize}
   \item Reuse seldom occurs in practice.

   \item Existing techniques for reuse are ineffective.
   \end{itemize}

\item Existing software components are:
   \begin{itemize}
   \item not abstract enough

   \item not sufficiently parameterizable.
   \end{itemize}

\item We need to understand:
   \begin{itemize}
   \item what the abstractions of programming are

   \item how to create programs by composition of abstract components

   \item how to make programming by composition easy and effective.
   \end{itemize}
\end{itemize}


\pagebreak

\begin{center}  {\bf Outline} \end{center}
\vspace*{.1in}
\begin{itemize}
\item Analyze a simple program to identify its components:
   \begin{itemize}
   \item There are many components.

   \item The components interact strongly.
   \end{itemize}

\item The program can be constructed from independent abstract components
using {\em views}.
   \begin{itemize}
   \item The good news: It works and generates efficient code.

   \item The bad news: The specs are very complex.

   \item The hope: Constraint propagation and inference can fill in
         many of the details.
   \end{itemize}

\item Work on deriving programs from minimal specifications

\item Related work
\end{itemize}


\pagebreak

\begin{center}  {\bf A Simple Program} \end{center}
\vspace*{.1in}
\begin{quotation}
Given as input a list of sublists, each of which has the format
{\tt (key n)}, sum the {\tt n} for each {\tt key}.
\end{quotation}
\begin{verbatim}
(alsum '((a 3) (b 2) (c 1) (a 5) (c 7)))

     =  ((C 8) (B 2) (A 8))
\end{verbatim}

\begin{tabbing}
(defun alsum (lst) \\
\ \  (let ({\tt (alist nil)} entry) \\
\ \ \ \=(dolist ({\em item} (identity lst)) \\
\> \ \ \=(setq entry \\
\>\> \ \   (or \={\tt (assoc} {\em (car item)} {\tt alist)} \\
\>\>\>           (progn \={\tt (push (list} {\em (car item)} {\bf 0} {\tt)}
 {\tt alist)} \\
\>\>\>\>         {\tt (assoc} {\em (car item)} {\tt alist)}))) \\
\>\>{\tt (}{\bf incf (cadr entry)} {\em (cadr item)} {\tt ) )} \\
\>{\tt alist})) \\
\end{tabbing}

Different fonts are used for code associated with different abstract
components.  Clearly, code of the components is thoroughly mixed
together in this program.


\pagebreak

\begin{center}  {\bf Program Components} \end{center}
\vspace*{.1in}
This small program combines five abstract procedural components:
\begin{itemize}
\item Iterate-Accumulate: Iterate through a sequence of items,
accumulating some aspect of the items.

\item Find-Update: Find an item in an indexing structure using its key
value, then update the record with information from the item.

\item {\tt dolist}: An iterator for linked lists in Lisp.

\item Alist: Association list, a kind of indexing structure.

\item Adder: A kind of accumulator.
\end{itemize}

In addition, there are several interfaces of {\em glue code}: how
to get the sequence from the input, how to get the key from the item,
what aspect of the item to accumulate.


\pagebreak

\begin{center}  {\bf Substitution Test} \end{center}
\vspace*{.1in}
A {\em substitution test} is useful to determine whether a decomposition
of a program into components is correct:
\begin{quotation}
Can the program be modified by a substituting a different component
for an existing one, without changing the other components?
\end{quotation}

In this example, we could produce different but related programs by
substitution of components:
\begin{itemize}
\item If the input were an array rather than a linked list, a different
iterator would be used.

\item A different indexing structure could be used, e.g. an AVL tree rather
than an Alist.

\item The product of the integers could be accumulated rather than
their sum.

\item By changing the glue code, we could change the key and accumulated
value, e.g. to accumulate symbols associated with each numeric value.
\end{itemize}


\pagebreak

\begin{center}  {\bf Abstract Software Components} \end{center}
\vspace*{.1in}
We claim that effectively reusable software components must be abstract.
Otherwise:
\begin{itemize}
\item Each decision that is hard-coded into a component becomes a
requirement on the use of that component.

\item There will be a combinatoric number of components based on
combinations of decisions.

\item It will be hard to find the right component among the many
available.

\item Learning the requirements of a component becomes a burden on the user.

\item Conforming to the requirements reduces the benefit of reuse.
\end{itemize}

Instead, there should be {\em only one} abstract version of each component,
which should serve for all uses.


\pagebreak

\begin{center}  {\bf Abstract Procedure: Iterate-Accumulate} \end{center}
\vspace*{.1in}
The top-level program is a generic procedure, Iterate-Accumulate:
\begin{verbatim}
(gldefun itacc (input:anything acc:anything)
  (let (seq item iter)
    (acc := (a (typeof acc)))
    (send acc initialize)
    (seq := (send input sequence))
    (iter := (send seq make-iterator))
    (while (not (send iter done))
      (item := (send iter next))
      (acc := (send acc update item)) )
    acc))
\end{verbatim}

When this procedure is specialized, wrapper types for the particular
arguments will replace the argument types.


\pagebreak

\begin{center}  {\bf Find-Update} \end{center}
\vspace*{.1in}

The accumulation is another generic procedure, Find-Update:
\begin{verbatim}
(gldefun findupd (coll:anything item:anything)
  (let (entry)
    (entry := (send coll find (send item key)))
    (if (null entry)
        (coll := (send coll insert
                            (send item key)))
        (entry := (send coll find
                             (send item key))))
    (send entry update item)
    coll ))
\end{verbatim}


\pagebreak

\begin{center}  {\bf Abstract Components with State} \end{center}
\vspace*{.1in}
\begin{verbatim}
(alist (listof (cons (key anything)
                     (rest anything)))
  msg ((initialize (nil))
       (find   (glambda (self key)
                 (assoc key self)))
       (insert (glambda (self key)
                 (cons
                   (send (a (typeof (first self))
                            with key = key)
                         initialize)
                   self)))) )
\end{verbatim}

\begin{verbatim}
(adder (sum number)
  prop ((initial-value (0)) )
  msg  ((init   ((sum := (initial-value self))))
        (update (glambda (self (item number))
                  ((sum self) _+ item)))
        (final  (sum))))
\end{verbatim}

Each of these expresses the functionality of the abstract component
cleanly.


\pagebreak

\begin{center}  {\bf Specializing Components} \end{center}
\vspace*{.1in}
The GLISP compiler can specialize a generic procedure through views.

\begin{center}
\setlength{\unitlength}{1pt}
\begin{picture}(340,150)(0,0)
 \thicklines \large
 \put(0,100){\framebox(80,50){\shortstack{Concrete\\ \\Type}}}
 \put(0,0){\framebox(80,50){\shortstack{View\\ \\Type}}}
 \put(130,0){\framebox(80,50){\shortstack{GLISP\\ \\Compiler}}}
 \put(130,100){\framebox(80,50){\shortstack{Generic\\ \\Procedure}}}
 \put(260,0){\framebox(80,50){\shortstack{Specialized\\ \\Procedure}}}
 \put(40,100){\vector(0,-1){48}} \put(81,25){\vector(1,0){48}}
 \put(211,25){\vector(1,0){48}} \put(170,100){\vector(0,-1){48}}
\end{picture}
\addtolength{\unitlength}{.5\unitlength}
\end{center}
\LARGE

A {\em view type}:
\begin{itemize}
\item wraps a concrete type (without adding any data)

\item has an abstract type as a superclass, inheriting its methods

\item defines data or procedures needed by the abstract type in terms
of the concrete type.
\end{itemize}


\pagebreak

\begin{center}  {\bf Compilation through Views} \end{center}
\vspace*{.1in}
Compilation of a generic procedure through views produces a specialized
version of the generic:
\begin{itemize}
\item Code expansion through views is recursive at compile time:
abstractions can be nested.

\item Code from views can be compiled in-line.

\item Partial evaluation optimizes the code produced.
\end{itemize}

The use of views has a low cost (often zero) after compilation.
A view can be considered a zero-weight wrapper that makes a data
type look like an abstract type.


\pagebreak

\begin{center}  {\bf Example of View} \end{center}

\begin{verbatim}
(circle anything
  prop  ((area  (pi * radius ^ 2))) )

(pizza (list (size symbol)
             (toppings (listof symbol)))
  views ((circle circle pizza-as-circle)))

(pizza-as-circle (p pizza)
  prop  ((diameter  ((if ((size p) = 'large)
                         then 18
                         else 12)))
         (radius    (diameter / 2)))
  supers (circle))
\end{verbatim}

\begin{verbatim}
(gldefun t1 (pz:pizza)
  (area (circle pz)))

result type: REAL
(LAMBDA (PZ)
  (IF (EQ (CAR PZ) 'LARGE)
      254.46900
      113.09733))
\end{verbatim}


\pagebreak

\begin{center}  {\bf Parameterization of Components} \end{center}
\vspace*{.1in}
View types are used to parameterize abstract components, in several ways:
\begin{itemize}
\item View types wrap concrete types for the application, and cause
derived values to be wrapped as well.
\begin{verbatim}
(myinputv (z myinput)
  prop ((sequence (z) result myalseq)))
\end{verbatim}

\item View types include {\em glue code}:
\begin{verbatim}
(myalrec (z myinputitem)
  prop ((accdata ((price z)))
        (key     ((name z)))) )
\end{verbatim}

\item View types invoke generic procedures by including abstract
superclasses:
\begin{verbatim}
(myview1 (z123 myaldata)
  prop   ((sum ((data z123))))
  supers (adder))
\end{verbatim}
An application could have multiple {\tt adder}s associated with the
same record.
\end{itemize}


\pagebreak

\begin{center}  {\bf Combined View Type} \end{center}
\vspace*{.1in}
The type that accumulates data for each key value is more complex
and includes components from several sources:
\begin{itemize}
\item The data structure includes data from independent sources:
   \begin{itemize}
   \item structural data (e.g. pointers) from the indexing method used

   \item key data whose type is the type of the key used 

   \item accumulator data specified by each accumulator.
   \end{itemize}

\item The methods {\tt initialize} and {\tt update} distribute
themselves over the accumulators.
\end{itemize}

\begin{verbatim}
(myaldata (list (key symbol) (data integer))
  msg  ((initialize
                ((send (view1 self) init)
                 self))
        (update (glambda (self item)
                 (send (view1 self) update
                       (send item accdata)))))
  views ((view1 adder myview1)) )
\end{verbatim}


\pagebreak

\begin{center}  {\bf Synthesized Program} \end{center}
\vspace*{.1in}
Using two given types and seven (handwritten) view types, the compiler
combines the five generic components to produce an application program:
\begin{verbatim}
(LAMBDA (INPUT ACC)
  (LET (ITEM ITER)
    (SETQ ACC (LIST))
    (SETQ ITER INPUT)
    (WHILE ITER (SETQ ITEM (POP ITER))
      (SETQ ACC
        (LET (ENTRY)
          (SETQ ENTRY (ASSOC (CAR ITEM) ACC))
          (UNLESS ENTRY
            (PUSH
              (LET ((SELF (LIST (CAR ITEM)
                                0)))
                (SETF (CADR SELF) 0)  SELF)
              ACC)
            (SETQ ENTRY
                  (ASSOC (CAR ITEM) ACC)))
          (INCF (CADR ENTRY) (CADR ITEM))
          ACC)))
    ACC))
\end{verbatim}



\pagebreak

\begin{center}  {\bf Recap} \end{center}
\vspace*{.1in}
\begin{itemize}
\item We have identified the abstract components in a small
application program.

\item The components are clear and satisfy the substitution test.

\item Even a small program has many abstract components!

\item The application can be mechanically synthesized from the
components using view types.

\item Unfortunately, the view types are complex, reflecting complex
relationships of components.
\end{itemize}


\pagebreak

\begin{center}  {\bf Automation using Constraints} \end{center}
\vspace*{.1in}
Our goal is to automate the production of view types from simpler
specifications.  The user should select a few components and
interfaces; the rest of the spec should be inferred.
\begin{itemize}
\item When data is passed from one component to another, the types
are equal.

\item A type mismatch is usually a need for type conversion; a
default method may be defined.

\item Some components have typical implementations, e.g. a typical
way to accumulate integers is to add them.

\item Components parameterize each other.  For example, if an {\tt adder}
is made part of an {\tt alist}, it will add its {\tt sum} variable
to the {\tt alist} record.
\end{itemize}


\pagebreak

\begin{center}  {\bf Constraint Propagation} \end{center}
\vspace*{.1in}
We envision a process similar to MOLGEN or Waltz filtering:
\begin{itemize}
\item Decisions made in one component will be propagated to connected
components, allowing them to infer other decisions.

\item Inferences must be retractable: the programmer can override
them.  Reason maintenance will retract derived decisions when needed.

\item A graphical interface will show specification status of the
developing program.
\end{itemize}


\pagebreak

\begin{center}  {\bf Example} \end{center}
\vspace*{.1in}
In one system we have implemented, the user can select a program
framework (e.g. Iterate-Accumulate) and make specifications.
Suppose the user specifies that the input to Iterate-Accumulate
is of type {\tt (arrayof integer)}:
\begin{itemize}
\item The input type matches the abstract type of the Iterator,
{\tt (sequence anything)}, so it is is inferred to be the
input to the Iterator.

\item The Iterator can now infer its item type as {\tt integer}.

\item The input to the Accumulator will thus be {\tt integer}.

\item Since a typical way to accumulate integers is to add them,
the accumulator can specialize itself to an Adder.
\end{itemize}



\pagebreak

\begin{center}  {\bf Minimal Specification} \end{center}

A minimal specification, Iterate-Accumulate on {\tt (arrayof integer)},
is enough to generate a complete program:
\begin{verbatim}
result type: INTEGER
(LAMBDA (IFA)
  (LET (ACC)
    (SETQ ACC 0)
    (LET (ITEM)
      (DOTIMES (INDX (ARRAY-TOTAL-SIZE IFA))
        (SETQ ITEM (AREF IFA INDX))
        (INCF ACC ITEM)))
    ACC))
\end{verbatim}

The programmer can obtain a different program by saying more.


\pagebreak

\begin{center}  {\bf Conclusions} \end{center}
\vspace*{.1in}
\begin{itemize}
\item Greater abstraction is needed to make software construction
by composition of components really work.

\item Automation is needed to make it easy to specify programs
by composition:
   \begin{itemize}
   \item minimize programmer input

   \item minimize programmer learning
   \end{itemize}
\end{itemize}


\pagebreak

\begin{center}  {\bf Related Work} \end{center}
\vspace*{.1in}
\begin{itemize}
\item SPECWARE$^{TM}$ [Srinivas96]: composition of types by
finding the colimit of the descriptions.

\item KIDS [Smith90]: transforms logic specs into programs for
combinatoric search problems.

\item Lowry87: knowledge of generic designs as parameterized theories.

\item Aspect-Oriented Programming [Kiczales97]: {\em aspect weaver}
combines program fragments from separate aspects of a design at
{\em join points}.

\item Programmer's Apprentice [Rich90]: synthesize programs from
{\em clich\'{e}s}.

\item Batory93: construction of software systems from layers of
plug-compatible components.

\item Krueger92 and Mili95 survey software reuse.
\end{itemize}


\end{document}


\pagebreak

\begin{center}  {\bf } \end{center}
\vspace*{.1in}
\begin{itemize}
\item 

\item 

\item 

\item 
\end{itemize}

\begin{verbatim}
\end{verbatim}