Higher-Order and Symbolic Computation, 18(3/4)

This issue presents selected papers from the first three ACM SIGPLAN Workshops on Scheme and Functional Programming (Felleisen, 2000; Serrano, 2001; Shivers, 2002). The articles cover various aspects of analysis, implementation, and application of Scheme. All of the articles were subjected to the usual process of journal reviewing.

"Selectors make set-based analysis too hard" examines the problem of program analysis for the Scheme construct case-lambda, which combines binding and pattern-matching to implement a function having a sum-of-products input type. The paper argues that the analysis of this construct currently implemented in the MrSpidey static debugger propagates too much information and thus often signals errors that cannot occur at runtime. To address the problem, the paper extends the set-based analysis found in MrSpidey to obtain more accurate results, but finds that the resulting analysis is too expensive, due to the use of selectors. A set-based analysis using techniques from closure analysis is then proposed that has better performance in practice. A preliminary version of this work was presented at the 2001 Scheme Workshop.

"BIT: A very compact Scheme system for microcontrollers" presents the design of a Scheme system for use in an embedded system with tight memory and real-time constraints. The paper proposes various strategies for the implementation of Scheme language features such as symbols, continuations, and garbage collection, and assesses the appropriateness of these strategies for use in an embedded context. Experience with using BIT on several microcontrollers is reported. A preliminary version of this work was presented at the 2000 Scheme Workshop, with the title "BIT: A very compact Scheme system for embedded applications."

"Fixing letrec: A faithful yet efficient implementation of Scheme's recursive binding construct" proposes an efficient implementation of letrec that addresses all of the cases and verication requirements described by the Revised^5 Report on Scheme. Key to this implementation is the classication of letrec bindings into those that are not used, those that bind a variable to a simple expression, those that bind a variable to a lambda abstraction, and others. A left-to-right variant of letrec is also proposed, and implemented using a similar strategy. Extensive performance results are provided. A preliminary version of this work was presented at Scheme Workshop 2002, with the title "Robust and effective transformation of letrec."

"Integrating user-level threads with processes in scsh" investigates the problems that arise when making the POSIX API available in a system that provides user-level threads. The main difficulty in this setting is that the POSIX API manipulates processes, which may contain multiple threads. The paper describes design structures and implementation techniques that map information obtained from the POSIX API to individual threads, thus for example allowing each thread to maintain an independent view of the current directory. A preliminary version of this work was presented at the 2002 Scheme Workshop, with the title "Processes vs. user-level threads in scsh."

"Implementing Metcast in Scheme" describes the use of Scheme in developing a weather-information server used by the United States Navy. The paper describes features of Scheme that were helpful in designing the server as well as new features added to Scheme to ease the implementation and meet performance requirements. A preliminary version of this work was presented at the 2000 Scheme Workshop.

"A variadic extension of Curry's fixed-point combinator" shows how to convert a specication of a variadic multiple fixed-point operator into a Scheme program that systematically represents the required sequences of values as lists. The result is naturally expressible in Scheme and is shown to be more efficient than a previously constructed variadic multiple fixed-point operator. A preliminary version of this work was presented at the 2002 Scheme Workshop.

References

Felleisen, M. (ed.): 2000, 'ACM SIGPLAN Workshop on Scheme and Functional Programming', Technical Report 00-368, Rice University. Montreal, Canada.

Serrano, M. (ed.): 2001, 'ACM SIGPLAN Workshop on Scheme and Functional Programming'. Firenze, Italy.

Shivers, O. (ed.): 2002, 'ACM SIGPLAN Workshop on Scheme and Functional Programming', Technical report GIT-CC-02-28, College of Computing, Georgia Institute of Technology. Pittsburgh, Pennsylvania.