In this paper we present two type inference systems for detecting useless-code in higher-order typed functional programs. Type inference can be performed in an efficient and complete way, by reducing it to the solution of a system of constraints. We also give a useless-code elimination algorithm which is based on a combined use of these type inference systems. The main application of the technique is the optimization of programs extracted from proofs in logical frameworks, but it could be used as well in the elimination of useless-code determined by program transformations.

We propose a parallel specialized language that ensures portable and cost-predictable implementations on parallel computers. The language is basically a first-order, recursion-less, strict functional language equipped with a collection of higher-order functions or skeletons. These skeletons apply on (nested) vectors and can be grouped into four classes: computation, reorganization, communication and mask skeletons. The compilation process is described as a series of transformations and analyses leading to SPMD-like functional programs which can be directly translated into real parallel code. The language restrictions enforce a programming discipline whose benefit is to allow a static, symbolic and accurate cost analysis. The parallel cost takes into account both load balancing and communications, and can be statically evaluated even when the actual size of vectors or the number of processors are unknown. It is used to automatically select the best data distribution among a set of standard distributions. Interestingly, this work can be seen as a cross-fertilization between techniques developed within the FORTRAN parallelization, skeleton and functional programming communities.

This paper introduces a sequence of λ-expressions modeling the binary expansion of integers. We derive expressions computing the test for zero, the successor function, and the predecessor function, thereby showing the sequence to be an adequate numeral system, i.e. one in which all recursive functions are lambda-definable. These functions can be computed efficiently; To this end, we introduce a notion of complexity that is independent of the order of evaluation.

Program generation has the prospect of being an integral part of a wide range of software development processes. Recent studies investigate different aspects of program generation systems, including their semantics, their applications, and their implementation. Existing theories and systems address both high-level (source) language and low-level (machine) language generation. A number of programming languages now support program generation and manipulation, with different goals, implementation techniques, and targeted at different applications. In this context, a PLI workshop dedicated to this theme (SAIG'00) was held in Montreal in September 2000. Following on from this workshop, a special issue of the Journal of Functional Programming will be devoted to the same theme.

Full-length, archival-quality submissions are solicited on topics including both theoretical and practical models and tools for building program generation systems, Examples include:

[bull ] Semantics, type systems, and implementations for multi-stage languages.

[bull ] Run-time specialization systems, e.g. compilers, operating systems.

[bull ] High-level program generation (applications, foundations, environments).

[bull ] Symbolic computation, linking and explicit substitution, in-lining and macros.

Reports on applications of these techniques to real-world problems are especially encouraged, as are submissions that relate ideas and concepts from several of these topics, or bridge the gap between theory and practice.

Contributors to SAIG'00 are encouraged to submit, but submission is open to everyone. Papers will be reviewed as regular JFP submissions, and acceptance in the special issue will be based on relevance to the theme. The special issue also welcomes high-quality survey and position papers that would benefit a wide audience. Accepted papers exceeding the space restrictions will be published as regular JFP papers.

Submissions should be sent to the guest editor (address below), with a copy to Nasreen Ahmad ([email protected]). Submitted articles should be sent in postscript format, preferably gzipped and uuencoded. In addition, please send, as plain text, title, abstract, and contact information. The submission deadline is 1st February 2001. For other submission details, please consult an issue of the Journal of Functional Programming or see the Journal's web page at http://www.dcs.gla.ac.uk/jfp/.