Towards Increased Productivity of Algorithm Implementation in Scaled Up Applications

Robert Paige

ONR Grant N00014-97-1-0128

                                    | Project Objectives:
                                    | Increasing Productivity of Large Scale,
                                    | Labor Intensive, High Performance
                                    | Systems

Scientific Approach:                | Recent Results:
1.  Design statically typed         | 1.  An initial design of Low SETL, a
variants of SETL as specification   | low level, statically typed variant of
languages.  The type system allows  | SETL2 was used to speedup the linear
errors to be detected at compile    | expected time fragment of Willard's RCS
time, helps to model complex data   | query language to linear worst case time.
structures, and supports            | 2.  Low SETL was extended with disjoint
computational transparency.         | disjoint unions, user types, recursive 
2.  Transform these specification   | types and subtypes.   The formal
languages into C using partial      | semantics of a batch read method
evaluation, data structure          | for the new Low SETL was developed.
selection, finite differencing, and | An algorithm implemented in the old
chaotic iteration iteration.        | Low SETL was developed to convert
                                    | input in string form into efficient
                                    | data structures for a variable list with
                                    | any signature from our type system in
                                    | linear time in the length of the string.
                                    | 3.  An initial solution to the hidden
                                    | copy problem for SETL2 was discovered, 
                                    | and was used to implement a new SETL2 
                                    | backend.  This result solves a difficult,
                                    | important problem that has plagued SETL
                                    | compilers for 20 years.