Multiplicative-inverse bug in Ikarus Scheme
In testing the examples from chapter 1 of AFP, I turned up a bug in
the Ikarus Scheme processor (version 0.0.3). One of my examples computes
the multiplicative inverse of -3/8, using the expression
(/ -3/8). The test code, then, was essentially
(= (/ -3/8) -8/3)
The test failed -- Ikarus Scheme returns #f as the value of
the equality test. I tried a few interactions to try to get some idea
of what was going on, but I found the results mystifying:
> (/ -3/8) 8/-3
This isn't exactly wrong, but the form of the number is not what I expecteed, since 8/-3 is not a valid R6RS literal. Ikarus Scheme accepts such literals as input, but appears to normalize them:
> 8/-3 -8/3
It looks like the one-argument / procedure is internally
generating a rational value with a negative denominator and not normalizing
the result:
> (rational? (/ -3/8)) #t > (numerator (/ -3/8)) 8 > (denominator (/ -3/8)) -3
Then the = predicate gets the wrong answer because it
somehow relies the precondition that denominators are positive. It's not
that the = predicate can't deal with signed values:
> (= -8/3 8/-3) #t > (= -8/-3 16/6) #t
Other procedures deal correctly with the negative-denominator rational:
> (< 8/-3 (/ -3/8)) #f > (> 8/-3 (/ -3/8)) #f > (<= 8/-3 (/ -3/8)) #t > (>= 8/-3 (/ -3/8)) #t > (- 8/-3 (/ -3/8)) 0
The two-argument form of the / procedure gives the correct
answer:
> (/ 1 -3/8) -8/3 > (= (/ -3/8) (/ 1 -3/8)) #f > (- (/ -3/8) (/ 1 -3/8)) 0
I looked over the list of bugs fixed in version 0.0.4 and didn't find this one, so I filed a bug report on the LaunchPad site for Ikarus Scheme.
Testing equality for exact rationals seems pretty straightforward -- you multiply the numerator of each one by the denominator of the other and determine whether the resulting integers are equal. But this should work even without the precondition that denominators be positive. I wonder what alternative approach the author of Ikarus Scheme used -- I must be missing something.
Binding
This morning I realized that I've been using the term ‘bind’ inconsistently when describing the association of an identifier and a value: Usually I have written of “binding the identifier to the value,” but about a third of the time I've swapped the direct object with the object of the preposition, “binding the value to the identifier.” I'm obsessive enough that this really bothers me -- binding isn't a symmetrical relation, so it makes no sense to waffle back and forth between these two ways of construing it.
After some thought, I concluded that the nominalization ‘parameter binding’ and the frequency and importance of the technical term ‘bound variable’ strongly favor the former construction, so I'm going through and changing the passages in which I used the latter one instead.
I'm not quite sure why this issue bothers me so much, but the recent history of ‘substitute’ may have heightened my sensibilities. Technical writers now frequently use ‘substitute’ as if its syntax were the same as the syntax of ‘replace’, writing “substituting A with B” when they should be writing “substituting B for A.” It can be difficult for a reader to be sure about whether A or B ends up in the result of the substitution. I don't want something similar to happen to ‘bind’.
RSS feed launched
At the suggestion of two members of my Google+ circles (Nicholas E. May and Lowell Vaughn), I've added an RSS feed to this blog. Thanks for the suggestion!
Algorithms for functional programming: the language variant
I started reworking my existing draft to take advantage of the new resources of R6RS. By creating a library that imports from (rnrs base (6)), (rnrs lists (6)), the SRFI libraries, and so on, and exports just the procedures that I want to have available in Algorithms for functional programming, I can easily define a variant of Scheme customized for this particular purpose. It can even be purely functional.
Running a top-level R6RS program under PLT Racket
With the setup described in my previous post on Larceny, I could find no way to run the same top-level program under PLT Racket. That language processor requires all libraries to be contained in “collections,” i.e., directories.
Accordingly, I created a subdirectory called greeting, moved greeting.sls into it, and revised the import clause of the top-level greeter to read
(import (greeting greeting))
I also revised the library name at the beginning of greeting.sls to read
(greeting greeting (0 0))
In both cases, the idea was to identify the contents of the greeting.sls file as a library called greeting within a collection also called greeting.
I discovered that, because of the diversity of language variants that the PLT Racket processor accepts and distinguishes, R6RS library modules must begin with the comment
#!r6rs
in order to be recognized.
With these changes, I found that the command
plt-r6rs ++path . top-level-greeter.ss
executed the program.
I confirmed that the Larceny and Ikarus Scheme command lines that I worked out continued to work under the new arrangement of files:
ikarus --r6rs-script top-level-greeter.ss larceny -r6rs -path . -program top-level-greeter.ss
Running a top-level R6RS program under Ikarus Scheme
With the setup described in my previous post on Larceny, I was able to run the same top-level program under Ikarus Scheme with the shell command
ikarus --r6rs-script top-level-greeter.ss
Ikarus Scheme presupposes that the names of the libraries are relative to the current working directory.
Running a top-level R6RS program under Larceny
One way in which I'll frequently be using the Scheme language processors that I've installed is to run a top-level Scheme program that imports libraries that I create as well as standard R6RS libraries. The mechanics of this process vary from one language processor to another. Indeed, the author of the Larceny user manual notes that “[t]he R6RS standard does not specify any way for a top-level program to define its own libraries.” As a result, R6RS language processors that permit this are obliged to extend the standard, so one would expect to find differences.
I created a directory called /home/stone/Projects/AFP/r6rs-testing and placed in it two files. One, greeting.sls, defines an R6RS library; apart from comments, it contains
(library (greeting (0 0))
(export hello)
(import (rnrs base (6))
(rnrs io simple (6)))
(define hello
(lambda ()
(display "Hello, world!")
(newline))))
The other file, top-level-greeter.ss, imports the greeting library and invokes its procedure:
(import (greeting)) (hello)
If the current working directory is the one containing these two files, the shell command
larceny -r6rs -path . -program top-level-greeter.ss
runs the top-level greeter. The -path command-line option takes a colon-separated list of directories in which Larceny is to search for libraries.
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.
Setting up this blog
This blog runs on under BlazeBlogger, which I chose because it's quite simple to configure and use, supports the very limited range of operations that I need, and is available as a Debian package. I had previously installed it on the local-area network (MathLAN) that I administer at Grinnell with the command
/usr/bin/aptitude install blazeblogger
issued as root.
To set up the blog, as an ordinary user of MathLAN, I created two directories, one for the editable versions of the blog posts and BlazeBlogger's internal configuration files and one for the visible version of the blog that BlazeBlogger builds:
mkdir -p blogs/afp mkdir public_html/afp-blog
Then the command
blaze-init -b blogs/afp
populated the editing-and-configuration directory, and
blaze-config -b blogs/afp
enabled me to edit a number of configuration options,
blaze-add -t "Algorithms for functional programming: the premise" -b blogs/afp
enabled me to write up the initial post and save it to the editing-and-configuration directory, and
blaze-make -d public_html/afp-blogs -b blogs/afp
built the visible Web pages and published them.
Actually, there was a problem with the last of these commands. In blaze-config, I had changed the lang option from the default value of en_GB to en_US, which implicitly directs BlazeBlogger to find and use a file containing American English versions of several words and phrases that it uses in building the Web pages (the names of the months of the year, etc.). For some reason, the Debian package for BlazeBlogger does not include this file. However, I was able to find a copy of it at http://blaze.blackened.cz/files/lang/en_US. I placed a copy of this file at blogs/afp/.blaze/lang/en_US and re-ran the blaze-make command, and this time it succeeded.
I ran the command
chmod -R go+rX blogs/afp public_html/afp-blog
to make sure that all of BlazeBlogger's files were world-readable.
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.