Towards Increased Productivity of Algorithm Implementation

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. Multimedia URL.
  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 long term objective is to dramatically improve the programming productivity of algorithm implementation and labor-intensive software. Our approach is based on very high level transformational and compiler technology with a generic (as opposed to domain specific) problem domain, an automatic (as opposed to interactive) software development methodology, and the production of high performance (as opposed to prototype) code.
  2. During the grant reporting period, the emphasis has been on demonstrating how qualitative methods in theoretical programming language can be used to solve quantitative problems in algorithms and complexity. The point of this activity was to confirm the practical utility of methods used in our compiler technology by showing their effectiveness in helping to solve difficult theoretical problems. This study also helps to unify the computer science discipline and to elevate the importance of programming languages by showing novel links between languages and algorithms. We know how algorithms can be adapted to solve problems in programming languages and compilers. However, links in the other direction are rare.

Detailed Summary of Technical Progress.

  1. During the grant period there were four results in which qualitative methods in theoretical languages were used to solve difficult quantitative problems in algorithms and complexity. The first showed how types can facilitate algorithm design by modeling complex data structures. The result was a new improved DFA minimization algorithm [Keller and Paige,CPAM 96] that uses O(n) space and O(n + m + m log n) time, where n is the number of NFA states and m is the number of transitions.
  2. The second showed how the fundamental semantic method of Rule Induction could be used in algorithm design and analysis. The result was a new improved Regular Expression-to-NFA transformation [Chang and Paige, Theoretical Computer Science, in press 1997]. That is, we turn regular expressions of r symbols and s occurrences of alphabet symbols into a compressed form of NFA in time O(r) and auxiliary space O(s). The best previous solution due to Chang and Paige ran in the same time bound but with O(r) auxiliary space. Our application of rule induction made use of a nonstandard context free grammar for the regular expressions.
  3. The third result showed how well typedness of programs written for a set theoretic model of computation guarantees program speedup from time in the expected sense to time in the worst case. A set theoretic model of computation assumes that associative access operations such as membership testing, set element addition and deletion, and finite map application can be performed in unit time. It was used in the 1970's by Hunt, Szymanski, Ullman, Fong, Paige, Schwartz, Willard, and others. Nowadays, it is commonly used in the compiler, database, and AI communities. In our case, programs written in a statically typed variant of SETL with O(f(n)) running time on a set-based model of computation (in which hashing unit space data is assumed to take unit expected time) are shown to be simulated on a pointer RAM in real time. This general speedup result was used to improve the complete linear time fragment of Willard's Relational Calculus Subset (RCS) [Willard, JCSS, 1996] from linear expected time to linear worst case time [Goyal and Paige, Proc. IFIP TC 2 Conf. on Algorithmic Languages and Calculi, Feb. 1997].
  4. The last result demonstrated the importance of a formal semantic specification for a type-directed high level batch reading method to the development of an efficient algorithm. More specifically, we developed a linear time algorithm to convert external input in string form into efficient data structures for a variable list with any signature in our type system [Paige and Yang, POPL, Jan. 1997]. This result serves to unify input complexity with algorithmic complexity for a pointer RAM model of computation.

Transitions and DOD Interactions.

  1. Your_text_for_this_item_goes_here....

Software and Hardware Prototypes.

  1. Prototype Name: Your_prototype_name_goes_here

List of Publications.

  1. Keller, J. P. and Paige, R., "Program Derivation With Verified Transformations - A Case Study," Communications of Pure and Applied Mathematics, Vol 48, No. 9-10, pp. 1053-1113, 1996.
  2. Paige, R., "Future Directions in Program Transformations," ACM Computing Surveys, 28A(4), Dec. 1996.
  3. Chang, C. and Paige, R., "From Regular Expressions to DFA's Using Compressed NFA's," in press, Theoretical Computer Science, to appear vol 178(1-2), 1997.
  4. Paige, R. and Yang, Z., "High Level Reading and Data Structure Compilation," Proc. 24th POPL, Jan. 1997, pp. 456 - 469.
  5. Goyal, D. and Paige, R., "The Formal Reconstruction and Improvement Of The Linear Time Fragment Of Willard's Relational Calculus Subset," to appear IFIP TC2 Working Conf. on Algorithmic Languages and Calculi, Feb. 1997.

Invited and Contributed Presentations.

  1. Invited paper on future directions in program transformations for the ACM Workshop on Strategic Directions in Computer Science, MIT, June 1996.

Honors, Prizes or Awards Received.

  1. Your_text_for_this_item_goes_here....

Project Personnel Promotions.

  1. Your_text_for_this_item_goes_here...

Project Staff.

  1. Name: Dr Robert Paige

Multimedia URL.

  1. EOYL FY96
  2. QUAD FY96
  3. EOYL FY95
  4. Research Project

Keywords.

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

Business Office

Expenditures

  1. Est. FY97: 100%
  2. FY96: 100%
  3. FY95: 90%
  4. FY94: 98%

Current and Former Students

  1. Name: [Mr|Ms|Dr] Student_name_goes_here

Book Plans

  1. Topic: Your_book_topic_goes_here

Sabbatical Plans

  1. Person: Your_name_or_name_of_person_on_contract_goes_here

Related Research

  1. Semantics-Based Program Analysis and Manipulation
  2. IFIP Working Group 2.1---Algorithmic Languages and Calculi
  3. BRICS (Basic Research in Computer Science, U. of Aarhus

History