BibTeX entry:

@inproceedings{HerLe2001a,
  author={Christoph A. Herrmann and Christian Lengauer},
  title= {A Transformational Approach which Combines Size
          Inference and Program Optimization},
  editor={Walid Taha},
  series={Lecture Notes in Computer Science 2196},
  pages ={199--218},
  booktitle={Semantics, Applications, and Implementation of Program 
             Generation (SAIG'01)},
  year=2001,
  publisher={Springer-Verlag}
 }

Abstract:

We propose a calculus for the analysis of list lengths in functional programs. In contrast to common type-based approaches, it is based on the syntactical structure of the program. To our knowledge, no other approach provides such a detailed analysis of nested lists. The analysis of lists is preceded by a program transformation which makes sizes explicit as program values and eliminates the chain of cons operations. This permits alternative implementations of lists, e.g., by functions or arrays. The technique is being implemented in an experimental parallelizing compiler for the functional language HDC. We believe that analysis and parallelization work best if higher-order functions are used to compose the program from functional building blocks, so-called skeletons, instead of using unrestrained recursion. Skeletons, e.g., data-parallel combinators come with a theory of sizes and parallelization.

Paper itself:

Authors:

Cross links:

Christoph Herrmann