Recursion bug in Mosh Scheme
Oh, great. In my first day of working with Mosh Scheme, on pretty elementary stuff, I find a bug.
Here's the simplified example that I sent in as part of the bug report. I want to write a procedure that tests whether a given binary tree of integers contains only even integers. I'm using the empty list to model the empty binary tree, and three-elements lists (root, left subtree, right subtree) to model non-empty ones. So here's the definition:
(define (buggy tree)
(letrec ((recurrer
(lambda (subtree)
(or (null? subtree)
(and (even? (car subtree))
(recurrer (cadr subtree))
(recurrer (caddr subtree)))))))
(recurrer tree)))
And here's a simple test case, giving the wrong answer.
> (buggy '(92 () (103 () ()))) #t
I was particularly puzzled to discover that the error disappears if you use any of the following three variations instead:
(define (ok0 tree)
(or (null? tree)
(and (even? (car tree))
(ok0 (cadr tree))
(ok0 (caddr tree)))))
(define ok1
(letrec ((recurrer (lambda (tree)
(or (null? tree)
(and (even? (car tree))
(recurrer (cadr tree))
(recurrer (caddr tree)))))))
recurrer))
(define (ok2 tree)
(letrec ((recurrer
(lambda (subtree)
(let ((result (or (null? subtree)
(and (even? (car subtree))
(recurrer (cadr subtree))
(recurrer (caddr subtree))))))
result))))
(recurrer tree)))
The explanation should be interesting.
Running a top-level R6RS program under Mosh Scheme
With the setup described in my early post on Larceny, I was able to run the same top-level program under Mosh Scheme with the shell command
mosh --loadpath=. top-level-greeter.ss
The --loadpath option is superfluous if the names of the
libraries are relative to the current working directory, as in this example.
Mosh Scheme doesn't have either of the bugs (in rational
arithmetic and in the
syntax-case system) that I've encountered in Ikarus
Scheme.
Like PLT Racket and Larceny, Mosh Scheme confirms that the tests for the code I've written for Algorithms for functional programming pass.
Another bug in Ikarus Scheme?
I've run into another problem that seems to be a bug in Ikarus Scheme, this
one in the processing of syntax definitions. This is supposed to be one of
Ikarus's strong points -- the implementer published a paper on the portable
syntax-case system that he developed for Ikarus -- so I was
surprised to encounter this difficulty.
I'm using syntax-case to automate the implementation of
"tuple" data types -- fixed-length lists in which each position is supposed
to hold values of a specified type. The idea is that I want to be able to
write something like
(define-tuple star (name string? string=?)
(magnitude number? =)
(distance number? =)
(spectral-class symbol? symbol=?))
and have it expand into a sequence of definitions: a constructor, a selector for each field, a "disaggregator" that returns the components as separate values, a classification predicate, and an equality predicate, thus:
(begin
(define (make-star name magnitude distance spectral-class)
(list name magnitude distance spectral-class))
(define (star-name star)
(list-ref star 0))
(define (star-magnitude star)
(list-ref star 1))
(define (star-distance star)
(list-ref star 2))
(define (star-spectral-class star)
(list-ref star 3))
(define (destar star)
(apply values star))
(define (star? something)
(and (list? something)
(= (length something) 4)
(string? (list-ref star 0))
(number? (list-ref star 1))
(number? (list-ref star 2))
(symbol? (list-ref star 3))))
(define (star=? left right)
(and (string=? (list-ref left 0) (list-ref right 0))
(= (list-ref left 1) (list-ref right 1))
(= (list-ref left 2) (list-ref right 2))
(symbol=? (list-ref left 3) (list-ref right 3)))))
Here's my definition of the define-tuple syntax:
(define-syntax define-tuple
(letrec ((as-string
(lambda (x)
(cond ((identifier? x)
(as-string (syntax->datum x)))
((symbol? x)
(symbol->string x))
((string? x) x))))
(construct-id
(lambda (context . parts)
(datum->syntax context
(string->symbol
(apply string-append
(map as-string parts))))))
(iota
(lambda (n)
(let loop ((count n) (so-far '()))
(if (zero? count)
so-far
(let ((next (- count 1)))
(loop next (cons next so-far))))))))
(lambda (input-form)
(syntax-case input-form ()
((_ type-name (field-name classification equality) ...)
(with-syntax ((constructor-name
(construct-id #'type-name "make-" #'type-name))
((selector-name ...)
(map (lambda (fn)
(construct-id #'type-name
#'type-name
"-"
fn))
#'(field-name ...)))
(field-count
(datum->syntax #'type-name
(length #'(field-name ...))))
((field-index ...)
(iota (length #'(field-name ...))))
(disaggregator-name
(construct-id #'type-name "de" #'type-name))
(classification-predicate-name
(construct-id #'type-name #'type-name "?"))
(equality-predicate-name
(construct-id #'type-name #'type-name "=?")))
#'(begin
(define (constructor-name field-name ...)
(list field-name ...))
(define (selector-name type-name)
(list-ref type-name field-index)) ...
(define (disaggregator-name type-name)
(apply values type-name))
(define (classification-predicate-name something)
(and (list? something)
(= (length something) field-count)
(classification
(list-ref something field-index)) ...))
(define (equality-predicate-name left right)
(and (equality (list-ref left field-index)
(list-ref right field-index))
...)))))))))
Ikarus accepts this syntax definition without complaining, but hangs
when it encounters any use of define-tuple, as if it can't
complete the expansion process. Neither PLT Racket nor Larceny has this
problem.
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.