Final Program for 2010 Workshop on Scheme and Functional Programming

Eager parsing and user interaction with call/cc

Olin Shivers

Many s-expressions have the pleasant property of being syntactically self-terminating: we know when we come to the right parenthesis at the end of a list that the list is complete. Old (but advanced) Lisp systems such as Maclisp and the Lisp Machine exploited this fact by interleaving the parser and the interactive "rubout" handler: a call to the reader completes as soon as the parser has consumed a complete s-expression without the user needing to input a following separator character. Yet the user is also able to correct erroneous, incomplete input by "backing up" with the delete key and re-entering corrected text.

Implementing such an input facility turns out to be a task for which Scheme has just the right tools: call/cc and other higher-order control operators. I will show how to use these operators to implement a reader that is eager, yet interactively permits correction. Although the parsing and error-correction functionality is interleaved, the code is not. The implementation is quite modular: the reader is a standard, off-the-shelf recursive-descent parser, written with no concern for error correction; the error-correction code works with any parser that needs no more than one character of lookahead.

The talk will show the development of real code, giving a demonstration of how Scheme's sophisticated control operators are put to work in a real systems-programming context.

Functional Data Structures for Typed Racket

Hari Prashanth KR and Sam Tobin-Hochstadt

Scheme provides excellent language support for programming in a functional style, but little in the way of library support. In this paper, we present a comprehensive library of functional data structures, drawing from several sources. We have implemented the library in Typed Scheme, a typed variant of PLT Scheme, allowing us to maintain the type invariants of the original definitions.

Implementing User-level Value-weak Hashtables

Aaron Hsu

Value weak hashtables retain only weak references to the values associated with either a strongly or weakly referenced key. Value-weak hashtables automatically remove entries with invalid weak references, which occurs when the collector reclaims a weakly referenced value. Value-weak hashtables provide a convenient way to automatically manage secondary information that does not need to exist once the primary object no longer exists. However, most Scheme implementations do not provide value-weak hashtables by default in their base library. Key-weak hashtables are more common. This paper presents an user- level technique for implementing value-weak hashtables that relies on features commonly found or that could be implemented in most implementations. This makes value- weak hashtables a practical reality for most Scheme users without requiring additional work on the implementation code itself. Programmers may, therefore, utilize value-weak hashtables in code that targets a wider range of implementations.

Pushdown Control-Flow Analysis of Higher-Order Programs

Christopher Earl, Matthew Might, and David Van Horn

We present push-down control-flow analysis, a novel method for analyzing higher-order control-flow. As its name suggests, push-down control-flow analysis replaces the finite-state machine underlying classical CFAs with a push-down system. The infinite state-space afforded by a push-down system makes it both more precise and more powerful than classical control-flow analysis. The push-down stack adds extra precision by perfectly matching returns to call sites. We discover push-down control-flow analysis as an abstract interpretation of a CESK machine with an unbounded stack. To prove computability, we transform the abstracted CESK machine into a push-down automaton (PDA), and then reduce control-flow analysis to deciding the non-emptiness of a language derived from the PDA's language. From there, we refine the algorithm, dropping its time-complexity from doubly exponential, to best-case exponential, to worst-case exponential, to polynomial. In the end, we are left with an efficient, polyvariant framework for control-flow analysis that can compute push-down generalizations of the classical finite-state control-flow analysis, e.g. push-down 0CFA, push-down k-CFA and push-down poly/CFA.

Measuring the Effectiveness of Error Messages Designed for Novice Programmers

Guillaume Marceau, Kathi Fisler, and Shriram Krishnamurthi

Good error messages are critical for novice programmers. Many projects attempt to rewrite expert-level error messages in terms suitable for novices. DrScheme's language levels provide a powerful alternative through which error messages are customized to pedagogically-inspired language subsets. Despite this, many novices still struggle to work effectively with DrScheme's error messages. To better understand why, we have begun using human-factors research methods to explore the effectiveness of DrScheme's error messages. Unlike existing work in this area, we study messages at a fine-grained level by analyzing the edits students make in response to various classes of errors. Our results point to several shortcomings in DrScheme's current treatment of errors; many of these should apply to other languages. This paper describes our methodology, presents initial findings, and recommends new approaches to presenting errors to novices.

JazzScheme: Evolution of a Lisp-Based Development System

Guillaume Cartier and Louis-Julien Guillemette

This article introduces JazzScheme, a development system based on extending the Scheme programming language and the Gambit system. JazzScheme includes a module system, hygienic macros, object-oriented programming, a full featured cross-platform application framework, a sophisticated programmable IDE and a build system that creates executable binaries for Mac OS X, Windows and Linux. JazzScheme has been used for more than 10 years to develop commercial software.

The Design of a Functional Image Library

Ian Barland, Robert Findler, and Matthew Flatt

We report on experience implementing a functional image library designed for use in an introductory programming course. Designing the library revealed subtle aspects of image manipulation, and led to some interesting design decisions. Our new library improves on the earlier Racket library by adding rotation and having a significantly faster implementation of equal?.

Enabling cross-library optimization and compile-time error checking in the presence of procedural macros

Andrew Keep and R. Kent Dybvig

Libraries and top-level programs are the basic units of portable code in the language defined by the Revised 6 Report on Scheme. As such, they are naturally treated as compilation units, with source optimization and certain forms of compile-time error checking occurring within but not across library and program boundaries. This paper describes a library-group form that can be used to turn a group of libraries and optionally a top-level program into a single compilation unit, allowing whole programs to be constructed from groups of independent pieces and enabling cross-library optimization and compile-time error checking. The paper also describes the implementation, which is challenging partly because of the need to support the use of one library's run-time exports when another library in the same group is compiled. The implementation does so without expanding any library in the group more than once, since doing so is expensive in some cases and, more importantly, semantically unsound in general. While described in the context of Scheme, the techniques presented in this paper are applicable to any language that supports both procedural macros and libraries, and might be adaptable to dependently typed languages or template meta-programming languages that provide full compile-time access to the source language.

Guiding Requirements for the Ongoing Scheme Standardization Process

Mario Latendresse

The Scheme standardization process has produced several Scheme revisions, the most recent one being R6RS. The R7RS standardization process is underway with an amended charter. The new charter has introduced two language levels, Small Scheme and Large Scheme, succinctly described as "lightweight" and "heavyweight", respectively. We analyze this new charter and propose some mod- ifications to it that we believe would help the standardization of Scheme, and in particular steer it towards greater use by the software developer community. We suggest that the Steering Committee establishes guiding requirements for the two Scheme levels. We discuss some examples of concrete guiding requirements to include in the standardization process for maintenance and debugging. We also discuss the need for an additional general principle for Small Scheme and suggest that, besides the general principle of a small language specification, the notion of efficiency of execution is also at the core of Small Scheme.

Contracts in Racket

Robert Findler

Adding contracts to a full-fledged implementation of a programming language reveals a number of subtle issues that studying small, focused calculi cannot. In particular, our experience with Racket alerted us to issues with proper blame assignment, interference between the contracts and the program, and how supporting contracts for advanced programming-language constructs leads to new, interesting challenges.

In this talk I will report on contracts in Racket, showing how these issues came up and how we resolved them. The talk will be structured around a number of real-world examples, showing how Racket responds to a series of increasingly complex interactions between modules with contracts. The talk draws on work and experience from several PLT institutions, including Northwestern, Northeastern, Utah, Brown, and BYU.