2005 Workshop on Scheme and Functional Programming

Tallinn, Estonia
24 September, 2005

Part of ICFP 2005

Program & Papers

Type Classes Without Types
Ronald Garcia and Andrew Lumsdaine

Data-directed programs consist of collections of generic functions, functions whose underlying implementation differs depending on properties of their arguments. Scheme~s flexibility lends itself to developing generic functions, but the language has some shortcomings in this regard. In particular, it lacks both facilities for con- veniently extending generic functions while preserving the flexibility of ad-hoc overloading techniques and constructs for group- ing related generic functions into coherent interfaces. This paper describes and discusses a mechanism, inspired by Haskell type classes, for implementing generic functions in Scheme that directly addresses the aforementioned concerns. Certain properties of Scheme, namely dynamic typing and an emphasis on block structure, have guided the design toward an end that balances structure and flexibility. We describe the system, demonstrate its function, and argue that it implements an interesting approach to polymorphism and, more specifically, overloading.

PDF for the paper; code; test suite

Eager Comprehensions in Scheme: The design of SRFI-42
Sebastian Egner

This article is about a certain style of programming iterative pro- grams. It is based on a concept we have named "eager comprehension," which is a convenient and efficient alternative to tail recursion, do-loops, and lazy list comprehensions (aka "ZF expressions"). Eager comprehensions are syntactic forms that encapsulate the details of an accumulation process (counting elements, creating a list, etc.). Within these forms, expressions called generators hide the details of enumerating basic sequences (running through a list, through a range of integers, etc.). By combining these elements in a clearly structured and well-defined way, a concise and powerful notation for writing loops emerges.

Of course, this style of programming is not new - it is implicitly present in any form of loop-macro already - and so we discuss several concrete designs that aim for the same goal. Surprisingly, however, none of these designs has had much impact on Scheme, despite the fact that their common floor plan has been around for decades. A particularly clean new design, SRFI 42, on the other hand has already made some friends in the first few years of its existence. Explaining the design and implementation of SRFI 42 constitutes the main part of this article.

PDF for the paper; SRFI 42

Abstraction and Performance from Explicit Monadic Reflection
Jonathan Sobel, Erik Hilsdale, R. Kent Dybvig, Daniel P. Friedman

Most of the existing literature about monadic programming focuses on theory but does not address issues of software engineering. Using monadic parsing as a running example, we demonstrate monadic programs written in a typical style, recognize how they violate abstraction boundaries, and recover clean abstraction crossings through monadic reflection. Once monadic reflection is made explicit, it is possible to construct a grammar for monadic programming that is independent of domain-specific operations. This grammar, in turn, enables the redefinition of the monadic operators as macros that eliminate at expansion time the overhead imposed by functional representations. The results are very efficient monadic programs; for parsing, the output code is competitive with good hand-crafted parsers.

PDF for the paper

An Operational Semantics for R5RS Scheme
Jacob Matthews and Robert Bruce Findler

This paper presents an operational semantics for the core of Scheme. Our specification improves over the existing R5RS denotational specification in four ways. First, it is more complete, since it contains eval, quote, and dynamic-wind. Second, it models multiple values in a way that does not require changes to unrelated parts of the language. Third, it provides a more faithful model of Scheme~s undefined order of evaluation. Finally, it is executable, because it is encoded as a program in PLT Redex, a domain-specific language for writing operational semantics. The executable specification allows others to experiment with our specification and allows us to build a specification test suite, which improves our confidence that our system is a faithful model of Scheme.

In addition to contributing a specification of Scheme, this paper presents several novel modeling techniques for Felleisen Hieb-style rewriting semantics that we discovered while developing our R5RS Scheme semantics. All are applicable to a wider range of problems than the specific uses we have for them, and the fact that they combine seamlessly in our full R5RS model shows that they scale to real languages.

PDF for the paper; source code for the semantics

Commander S - The shell as a browser
Martin Gasbichler and Eric Knauel

Commander S is a new approach to interactive Unix shells based on interpretation of command output and cursor-oriented terminal programs. The user can easily refer to the output of previous commands when composing new command lines or use interactive viewers to further explore the command results. Commander S is extensible by plug-ins for parsing command output and for viewing command results interactively. The included job control avoids garbling of the terminal by informing the user in a separate widget and running background processes in separate terminals. Commander S is also an interactive front-end to scsh, the Scheme Shell, and it closely integrates Scheme evaluation with command execution. The paper also shows how Commander S employs techniques from object-oriented programming, concurrent programming, and functional programming techniques.

PDF for the paper; Command S web page

Ubiquitous Mails
Erick Gallesio and Manuel Serrano

Bimap is a tool for synchronizing IMAP servers. It enables two or more IMAP mirrored servers to be modified independently and later on, synchronized. Bimap is versatile so, in addition to synchronizing emails, it can be used for filtering and classifying emails. For the sake of the example, the paper shows automatic emails classification and white-listing programmed with Bimap.

Bimap is implemented in Scheme. The most important parts of its implementation are presented in this paper with the intended goal to demonstrate that Scheme is suited for programming tasks that are usually devoted to scripting languages such as Perl or Python. With additional libraries, Scheme enables compact and efficient implementation of this distributed networked application because the main computations that require efficiency are executed in compiled code and only the user configurations are executed in interpreted code.

PDF for the paper

Implementing a Bibliography Processor in Scheme
Jean-Michel Hufflen

We report an experience of implementing the MlBibTeX bibliography processor, a re-implementation of BibTeX with particular focus on multilingual features. First we describe the behaviour of this software and explain why we chose Scheme to implement the first public version. Then we give the broad outlines of our implementation and show how we took as much advantage as possible of the main features of Scheme. We also explain what we really missed and suggest some ways to improve these points.

PDF for the paper; MlBibTeX web page

The Marriage of MrMathematica and MzScheme
Chongkai Zhu

In this paper, I argue that the programming languages provided in current mainstream CASes are not suitable for general purpose programming. To address this problem, I developed MrMathematica. MrMathematica is a connection between Mathematica and PLT-Scheme, which provides the ability to call Mathematica from MzScheme. The two languages share some common ground, but are mostly complementary to each other. MrMathematica enhances Mathematica, and it helps to introduce Scheme to more people (CAS users).

PDF for the paper; MrMathematica web page

ACT Parameterization Framework
Alan Pavicic and Niksa Bosnic

ACT is a generic parameterization framework used in the development of applications for modeling and parameterization of internal combustion engines. It is developed in Guile. Its two main parts are Ilm core of object model built on top of Goops, and Bee editor environment providing UI. The core object model supports generic persistence of any object to database, type guardians for different slots, nameservices and object repositories. It also supports addins, additional modules which can change the behavior of the entire system as well as any of its parts (e.g. undo/redo functionality, dependencies between objects, event notification, ...). The editor environment for editing Ilm objects includes a library of basic editors, simple composite editors and generic editors. A grading system can be used to dynamically decide which registered editor class is the most appropriate for editing a particular object. Every Bee editor is an Ilm object itself. High level XML descriptions of data models and editors can be compiled to Scheme code defining Ilm classes and Bee editors.

PDF for the paper

Javascript to Scheme Compilation
Florian Loitsch

This paper presents Jsigloo, a Bigloo frontend compiling Javascript to Scheme. Javascript and Scheme share many features: both are dynamically typed, they feature closures and allow for functions as first class citizens. Despite their similarities it is not always easy to map Javascript constructs to efficient Scheme code, and in this paper we discuss the non-obvious transformations that needed special attention.

Even though optimizations were supposed to be done by Bigloo the chosen Javascript-Scheme mapping made several analyses ineffective and some optimizations are hence implemented in Jsigloo. We illustrate the opportunities Bigloo missed and show how the additional optimizations improve the situation.

PDF for the paper