Towards Increased Productivity of Algorithm Implementation in Scaled Up Applications

Table of Contents:

  1. Principal Investigator.
  2. Productivity Measures.
  3. Summary of Objectives and Approach.
  4. Detailed Summary of Technical Progress.
  5. Transitions and DOD Interactions.
  6. Software and Hardware Prototypes.
  7. List of Publications.
  8. Invited and Contributed Presentations.
  9. Honors, Prizes or Awards Received.
  10. Project Personnel Promotions.
  11. Project Staff.
  12. URLs.
  13. Keywords.
  14. Business Office.
  15. Expenditures.
  16. Students.
  17. Book Plans.
  18. Sabbatical Plans.
  19. Related Research.
  20. History.

Principal Investigator.

Productivity Measures.

Summary of Objectives and Approach.

  1. Our objective is to improve programming productivity of complex, labor intensive, large scale, high performance systems. The approach combines partial evaluation with program transformations developed by the principal investigator over the last ten years under ONR funding.
  2. We propose a new software development technology that allows specifications to be written in three different languages, Low SETL (a statically typed, pointerless, variant of SETL2 restricted to low level element-at-a-time operations ), High SETL (Low SETL augmented with set comprehension, quantification, and other high level features), and SQ2+ (a functional subset of High SETL augmented with least and greatest fixed points). Specifications in SQ2+ and High SETL are compiled into Low SETL; Low SETL systems of systems are partially evaluated into a single, seamless, Low SETL system without major interfaces. Low SETL is subsequently transformed into high performance C.

Detailed Summary of Technical Progress.

  1. During the grant reporting period, we made continued progress with the design of Low SETL. The type system for an earlier version of Low SETL was developed with type judgments specifically to guarantee real-time simulation of assocative access on a RAM. This new system was then used to guarantee runtime speedup of the linear time fragment of Willard's RCS query language from linear expected to linear worst case time (Goyal and Paige, Proc. IFIP TC2 Working Conf. on Algorithmic Languages and Calculi,1997).
  2. The type system was further augmented with disjoint unions, user defined types, and recursive types and subtypes. We then developed the formal semantics of a batch read method for Low SETL together with an efficient algorithm written in Low SETL itself. The algorithm converts input in string form into efficient data structures for a variable list with any signature in the new type system in linear time in the length of the input string (Paige and Zhe, POPL 97).
  3. An off-line partial evaluator for a low level subset of dynamically typed SETL2 has been built with a finite, uniform, congruent division and polyvariant specialization based on the method for flowchart languages found in (Jones 1993). It includes interprocedural analysis for control flow, dataflow, and live variables, which is used for various optimizations including procedure unfolding during specialization. So far the partial evaluator has been used successfully to implement the First Futamura Projection on several interesting examples, including an interpreter for a simple imperative language. Minor modification is underway to implement the Second Futamura Projection, which is critical for automatic transformation of the APTS interpreter into a compiler.
  4. During the past year we made a surprising discovery of a solution to the hidden copy problem, which is the major source of inefficiency inherited by two generations of SETL compilers. This problem has to do with implementing assignments and parameter passing of large objects according to copy/value semantics. The strategy of SETL1 (Schwartz et.al. 1986) and SETL2 (Snyder 1990) is to implement lazy copies. That is, assignment of large objects (e.g. sets and tuples with arbitrary depth of nesting) or incorporation of a large object into another large object is implemented by only copying pointers. Since a large object may be shared under this strategy, it must be first copied whenever it is updated in order to avoid any side effect. With this approach hidden copies can potentially degrade program performance from O(f(n)) expected time to O(f(n)^2 ) actual time. In (Cai and Paige 1993) we observed 30,000-fold slowdowns in SETL2 performance due to unnecessary hidden copies.

    During the 1970's Schwartz developed an interesting but complicated value flow analysis for SETL1 in order to detect when hidden copies could be avoided, and update operations could be performed in place. The difficulty of the analysis seems to stem, in large part, from the fact that SETL1 did not implement reference counts, so that the analysis had to prove that an r-value was unshared. It was never implemented, and a completely different naive approach that was eventually used proved to be unsatisfactory.

    In SETL2 dynamic reference counts of all pointers to each tuple or set value are maintained. If a value has a reference count greater than 1, then that value is shared, and cannot be updated unless it is first copied. For example, in order to perform element addition S with:= a (which adds element a to set S) in place, the r-value of S must have a reference count of 1 and the l-values of S and a must be different. Otherwise, a hidden copy of the r-value of S must be made, and the update is performed on the copy. Unfortunately, the backend of Snyder's SETL2 compiler introduces so many compiler-generated temporary variables (which don't get garbage collected until the end of scope) that practically all data is shared at runtime.

    We are currently working on a good solution to the hidden copy problem for both Low SETL and SETL2 using dynamic reference counts. Such a solution would also shed light on related problems in the object oriented and functional programming communities. Our approach is to solve this problem indirectly by introducing operations that decrement reference counts of dead l-values dynamically. We have made good progress in solving the problem for SETL2, and a rudimentary, but effective, very local optimizer has been completed. A more global solution is planned for the coming year.

Transitions and DOD Interactions.

Software and Hardware Prototypes.

List of Publications.

  1. Chang, C. and Paige, R., "From Regular Expressions to DFA's Using Compressed NFA's," Theoretical Computer Science, vol. 178(1-2), May, 1997, pp. 1-36.
  2. Paige, R., "Future Directions in Program Transformations," http://www.acm.org/surveys/1996/PaigeFuture/, ACM Computing Surveys, 28A(4), Dec. 1996.
  3. Goyal, D. and Paige, R., "The Formal Reconstruction and Improvement Of The Linear Time Fragment Of Willard's Relational Calculus Subset," in Algorithmic Languages and Calculi, Richard Bird and L.G.L.T. Meertens (Eds.), pp. 382 - 414, Chapman \& Hall, London, 1997. Short form appeared in IFIP TC2 Working Conf. on Algorithmic Languages and Calculi, Feb. 1997.
  4. Paige, R. and Yang, Z., "High Level Reading and Data Structure Compilation," Proc. 24th POPL, Jan. 1997, pp. 456 - 469.

Invited and Contributed Presentations.

  1. Using Qualitative Methods in Programming Languages To Solve Quantitative Problems in Algorithms and Complexity, Atlantique Workshop, ENS, Paris, France, Jan. 1997.
  2. High Level Reading And Data Structure Compilation, 24th POPL, Paris, France, Jan. 1997.
  3. The Formal Reconstruction nd Improvement of the Linear Time Fragment of Willard's Relational Calculus Subset, TC2 Conf., Strasbourg, France, Feb. 1997.
  4. The Formal Reconstruction nd Improvement of the Linear Time Fragment of Willard's Relational Calculus Subset, Seminar, SUNY at Albany, Apr. 1997.
  5. The Formal Reconstruction nd Improvement of the Linear Time Fragment of Willard's Relational Calculus Subset, Seminar, DIKU at the U. of Copenhagen, Denmark, Aug. 1997.
  6. The Formal Reconstruction nd Improvement of the Linear Time Fragment of Willard's Relational Calculus Subset, Seminar, U. of Aarhus, Denmark, Aug. 1997.

Honors, Prizes or Awards Received.

Project Personnel Promotions.

Project Staff.

  1. Name: Dr Robert Paige

URLs.

  1. EOYL FY97
  2. QUAD FY97
  3. EOYL FY96
  4. QUAD FY96

Keywords.

  1. Transformations
  2. Program Development
  3. Productivity
  4. Algorithm Derivation

Business Office.

Expenditures.

  1. FY97: 95%

Current and Former Students.

Book Plans.

  1. Topic: Program Transformations

Sabbatical Plans.

  1. Person: Robert A. Paige

Related Research.

  1. Semantics-Based Program Analysis and Manipulation
  2. IFIP Working Group 2.1---Algorithmic Languages and Calculi

History.

  1. I've heard from Ed Clarke and others that my bisimulation algorithm with Tarjan is being used widely in verification systems; e.g. the Aldebaran verification tool by J.C. Fernandez.
  2. I believe that several other algorithms developed under present and past ONR funding will be used widely in research and even commercial systems. Bruce Watson, the Chief Architect at Ribbit Software Systems Inc. told me that there's been a lot of interest in implementing my algorithms with Chang to turn regular expressions into DFA's. Researchers at Rice with industrial connections have also told me about their plans to implement several of my multiset discrimination-based algorithms with Cai including fast iterated strength reduction as part of an optimizing compiler.

-------------------------------------------------------------