Current R6RS implementations
In developing and testing the algorithm implementations in Algorithms for functional programming, I propose to use Scheme language processors that implement the R6RS standard completely and correctly and are available as Debian packages, ideally packages that the Debian Project itself includes in the free stable distribution.
The list of R6RS implementations at http://www.r6rs.org/implementations.html identifies eight of them: Chez Scheme, Guile, Ikarus Scheme, IronScheme, Larceny, Mosh Scheme, PLT Racket, and Ypsilon.
A binary-only version of Chez Scheme (without the compiler) is available under an unfree license from the developer. The current version is 8.3.
Chez Scheme download site ... Chez Scheme version 8 user's guide ... The Scheme programming language, fourth edition
Guile is available as a Debian package (guile-1.8), but the version that Debian provides is older and does not implement R6RS. A newer version is available from the GNU Project as a tarball.
GNU Guile download site ... Guile reference manual (PDF version)
Ikarus Scheme is available as a Debian package (ikarus), but it is not a complete implementation of R6RS Scheme, and no one appears to be maintaining it. The developer's site (http://ikarus-scheme.org/) is currently out of service.
IronScheme is based on the Microsoft Dynamic Language Runtime and so cannot be expected to run in a GNU environment.
Larceny is available as a prebuilt binary for the Intel 32-bit architecture. The developer also provides source code, under the Lesser General Public License and an alternative license that appears to be unique to Larceny.
Larceny download site ... Larceny User Manual (PDF version)
Mosh Scheme is available as a tarball.
Mosh Scheme download site ... Mosh Scheme user manual
The Debian Project packages and distributes PLT Racket (version 5.1.1) for version squeeze in its squeeze-backports/main section. The package names are racket and racket-doc. If you already have the PLT Scheme packages installed, the Debian package manager will require you to remove them as you install PLT Racket.
Ypsilon is available as a tarball (version 0.9.6.update3). There appears to be no useful documentation for it.
I already had Ikarus Scheme on the desktop that I'll be working on this semester, and I installed the Debian packages for PLT Racket and the binaries for Larceny. For compatibility testing, I plan eventually to install Guile and Mosh Scheme as well.
Although it is possible to install Larceny in user space, I decided that it would be preferable to have set it up in /opt. As root on eunoia, I downloaded the tarball into /tmp and unpacked it into a new directory in /opt:
cd /tmp /usr/bin/wget http://www.larcenists.org/LarcenyReleases/larceny-0.97-bin-native-ia32-linux86.tar.gz cd /opt /bin/tar xvzf /tmp/larceny-0.97-bin-native-ia32-linux86.tar.gz
I then added the lines
if [ -d /opt/larceny-0.97-bin-native-ia32-linux86 ]
then
PATH=$PATH:/opt/larceny-0.97-bin-native-ia32-linux86
fi
to add Larceny's directory to the shell's search path.
Algorithms for functional programming: the premise
Algorithms for functional programming is a textbook on algorithms and data structures, presented in a purely functional style and exemplifying the functional programmer's approach to algorithm design and implementation.
The building blocks of programs created in this style are functions, in the mathematical sense of the word: well-defined formal entities that receive values as arguments and yield values as results. Functions have no internal state. Given the same arguments, therefore, a function always yields the same results, regardless of the context in which it is applied. This invariant behavior simplifies many algorithms and makes it easier to determine their preconditions and postconditions exactly, to prove their correctness, and to analyze their resource use.
A second characteristic of the functional programming style is the treatment of functions as values that can be transmitted as arguments to other functions, yielded as results by other functions, and constructed and invoked during program execution. Programming languages that support this style provide convenient and concise ways of expressing such operations.
Algorithms for functional programming uses Scheme as its implementation language. Scheme supports functions as values within its “procedure” type. (This type also includes entities that receive arguments and yield results, but do not qualify as pure functions because they have internal states, and their results can depend on those states as well as on the arguments that the procedure receives.)
Scheme is defined by a de facto standard, the Revised6 report on the algorithmic language Scheme. This standard defines a base language and a set of standard libraries that make it exceptionally easy to specify extensions, subsets, and variants that are tailored to specific projects. The language variant used in Algorithms for functional programming is designed to exclude many of Scheme's non-functional constructions and to supplement the Scheme base and standard library with additional operations that support the functional style.
Algorithms for functional programming currently exists as an incomplete draft, which I developed during previous leaves from my job as a teacher of computer science and system and network administrator at Grinnell College. Initially, this blog will follow the development of this draft into a finished book. After that, my intention is to announce here any supplements and extensions to the book, or other news related to it, and perhaps more generally to report and discuss discoveries and events in this field.