RacketCon

I’m still recovering from the week of Program By Design, followed immediately with RacketCon. My feet are meant for walking, not standing.

The weekend was fun, though. I got to show that Whalesong, my Racket to JavaScript compiler, is starting to do interesting things. Although I didn’t tell anyone explicitly, I was dogfooding Whalesong: my entire slideshow was itself a World program that I had compiled with Whalesong itself.

Unfortunately, I was so nervous during the beginning of the talk, that I rushed my example about a slideshow being itself a world program into incoherence. I’ll have to watch myself when the videos come out, grimace, and hope to do better next time. I think folks got a kick out of the JQuery example.

Other items to note:

  • The second day unfortunately suffered from a lack of air conditioning.
  • Jay McCarthy showed a kick-butt example of game programs written with World. My ears are still ringing with the thump of the video game music.
  • Marco Morazan showed how to teach A* to first-year undergrads. Awesome.
  • Matthew Flatt talked about the history and future of Racket. He brought his magic 8-ball with him.

Ok, better get back to work and get Whalesong ready…

F*dging up a Racket

(A small history behind the guide at http://hashcollision.org/brainfudge)

I was listening to Randal Schwartz give an interview to Matthew Flatt on FLOSS Weekly a few weeks ago. It was really cool to listen to Matthew, who consistently gave so much credit to the PLT team during the interview. At one point, the conversation turned toward the idea that Racket could support multiple languages. Randal asked, with excitement, whether that meant Racket could potentially do Perl 6. I was hoping that Matthew would respond with a “Dear God No!” kind of horror, but he took it in calm stride, of course, and said that people were welcome to try it if they had time.

That stuck with me. I wanted to do my part in helping to make such dreams/nightmares into reality. I definitely didn’t have the time to do it myself, not without getting severely schooled by my advisors. But I still wanted to help. Maybe I could write a guide to help other hackers get started. Hopefully, I’d get in less trouble that way.

So I wanted to write an extended example of how to add a new language to Racket. It needed to cover the entire gauntlet, from setting up the PLaneT development links, to writing the semantics and parser, to finally delivering a self-contained package on PLaneT. And I needed to use a non-parenthetical language.

Sometimes it’s hard to get across the idea that Racket supports multiple programming languages. The traditional examples that people see, such as programs written in Beginner Student Language:

#lang htdp/bsl ; Any key inflates the balloon
(require 2htdp/image) (require 2htdp/universe)
(define (balloon b) (circle b "solid" "red"))
(define (blow-up b k) (+ b 5))
(define (deflate b) (max (- b 1) 1))
  (big-bang 50 (on-key blow-up) (on-tick deflate)
               (to-draw balloon 200 200))


just aren’t convincing to people, precisely because it looks just like Scheme, with all those silly parentheses, defines, and all.

But something like this:

#lang planet dyoo/bf
++++++[>++++++++++++<-]>.
>++++++++++[>++++++++++<-]>+.
+++++++..+++.>++++[>+++++++++++<-]>.
<+++[>----<-]>.<<<<<+++[>+++++<-]>.
>>.+++.------.--------.>>+.


… now there’s something deliciously perverse and screwed up about this! The choice was clear: the language had to be brainf*ck.

I spent an afternoon getting the code ready. For days, though, my brain was full of the document. Writing is hard! I wanted to keep the number of concepts down as much as possible. There were two dangers I tried to avoid:

  1. Losing velocity. A person needed to be able to read it in one sitting, or else they might give up too easily.
  2. Narrowing the target audience. I want to make it accessible to professional programmers with some familiarity with a programming language like Scheme. But they shouldn’t be Racket experts.

After some struggle, I finished the first nine chapters of the tutorial. I posted it up, and tried getting it on /r/programming. Although I failed miserably at getting upvotes, thankfully, more Reddit-savvy folks posted a compelling headline, and people started looking at the tutorial. Hurrah! Mission accomplished!

… except that some people were getting caught up by the fact that the implementation was slow. Drats. I went back and saw that I had messed up a small part of the implementation. I fixed it, but then saw that I had no choice: I had to extend the tutorial to show what I needed to do to fix the performance issues. A small matter of writing again, right?

There are moments in one’s life where certain actions seem preordained and inevitable. I had just gone and re-watched an anime, episode 10 to be precise, which involved a time loop and all sorts of pain, sadness, and suffering. The optimization section, Section 10, felt very much like the same thing: I needed to go back, fix things, and keep fixing things until the implementation performed reasonably well.

That section ended up being slightly longer than the first half of the document, and as long to write. The upside was that the tutorial felt much more complete after the writing was done. The downside was I didn’t get anything else done during the week. A conservation of hope and despair, I suppose.

aliasing renaming

People are often particular about naming. Names still hold special power: we may rationalize that names don’t matter, but there’s something hardcoded in human beings about choosing the right name for a thing. It’s a hard thing to fight.

Programmers are people too, and programmers also keep concerns (sometimes too much) about the right name for a thing. As a concrete example, the word lambda scares off a few people since it’s a foreign word. We might like to be brief and be able to say:


(def (make-adder x)
(fn (y) (+ x y)))

where def and fn are really meant to behave like define and lambda, respectively. One nice thing about Scheme is that it’s plastic enough to absorb a trivial change like this. Here’s a small library for aliasing identifiers:


(module alias mzscheme
;; Practice writing macros that themselves generate macros.

(provide alias)

;; (alias old-keyword new-keyword) SYNTAX
;; Creates a new syntax for new-keyword; any occurrence of new-keyword
;; is replaced with the old-keyword.
(define-syntax (alias stx-1)
(syntax-case stx-1 ()
[(_1 orig new)
(syntax/loc stx-1
(define-syntax (new stx-2)
(syntax-case stx-2 ()
[_2
(identifier? stx-2)
(syntax/loc stx-2
orig)]
[(_2 e (... ...))
(syntax/loc stx-2
(orig e (... ...)))])))])))

Once we have a tool like this, then we can test it out:


(module test-alias mzscheme
(require "alias.ss")
(alias lambda fn)
(alias define def)

(def (make-adder x)
(fn (y) (+ x y))))

That being said, the above example is a silly thing to do. Even in competent hands, this is easy to abuse; in the wrong hands, one can end up with something that belongs to an obfuscation contest.


> (alias alias a)
> (a define d)
> (a if i)
> (d (f x) (i (= x 0) 1 (* x (f (- x 1)))))
> (f 3)
6

Communication between people means that we “come to terms”, and the inherent abuse here is to turn the language into something that no one else can read. In PLT Scheme’s case, the above is especially bad because there’s already an established mechanism for controlled renaming of identifiers as part of PLT Scheme’s module system.


(module test-alias mzscheme
(require (rename mzscheme fn lambda)
(rename mzscheme def define))

(def (make-adder x) (fn (y) (+ x y))))

Still, I thought the macro definition was cute (even if it’s silly), and it’s one of the more direct applications of a “macro-generating macro” that I’ve seen. But maybe this is all just syntax, futzing with words, distracting us from the real work on nailing down the semantics of our thoughts.

logical

I didn’t get this so strongly before, but there’s a correspondence between the language and structures of first-order logic, and the signatures and units of PLT Scheme (as well as the signatures and structures of ML). I guess the analogy is something like: “language::signature as structure::unit.”

As a concrete example, a first-order language might just have equality (=), and a 2-arity P relation. Once we have a language, we can start writing statements in that language. Here are two statements using the language:

  • for all x, y, z: P(x, y) and P(x, z) implies y = z
  • for all x: there exists y: P(x, y)

These two sentences, taken together, are trying to say “P must be a relation that represents a total function”. These sentences don’t have a true or false value without being evaluated in the context of some structure. A structure tells us what domain of thingies (the universe) we’re iterating over when we say “for all” or “there exists”, and also provides a concrete definition for the relations of the language.

There are some structures that might satisfy this, and other structures that don’t. Structures that satisfy the sentences we care about are called “models”. One example of such a model for those two sentences might be the natural numbers (0, 1, 2, …), where the interpretation of P is:

P(x, y) if and only if y = square(x)

But an example of a similar structure that wouldn’t fit the above conditions would be natural numbers under a P that’s not a function relation, like:

P(x, y) if and only if x < y

and so we’d say that this structure isn’t a model of those sentences.

Programmers have an intuitive idea about this: it’s similar to the distinction between “interface” and “implementation”: the language provides the interface, and the structures provide implementations for that language. And when we have an interface, we usually have some implicit idea of how that interface should behave; if we have an interface called Stack, we have an expectation about what it should do. We can make those assumptions explicit by writing contracts or predicates with that interface: the things that satisfy our expectations are good implementations.

Again, to make this concrete, when we’re programming with signatures and units, we first have to specify the things we’re going to be fiddling with. For example, a signature like:


;; A function^ model consists of a universe of elements,
;; and a 2-place predicate P between elements.
(define-signature function^ (universe
P))

gives us a language for talking and using units that implement this signature. For example, to build a unit where P is the squaring relation, we can do this:


(define-unit squaring@
(import)
(export function^)
(define universe (list 0 1 2 3 4 '>4))
(define (P x y)
(cond
[(equal? x '>4)
(equal? y '>4)]
[(> (* x x) 4)
(equal? y '>4)]
[else
(equal? y (* x x))])))

(I’m defining the P function a bit peculiarly since I want the universe of elements to be finite.)

But again, not all implementations of the function^ signature will do the right thing. Here’s a structure that doesn’t satisfy the intent of the function^ signature.


(define-unit less-than@
(import)
(export function^)
(define universe '(1 2 3))
(define (P x y)
(< x y)))

How do we capture intent? We want to be able to catch implementations that don’t do what we expect, and one way is to write code to exercise the units. Here’s one example:


;; function-model?: function@ -> boolean
;; Checks to see if the given unit satisfies what we
;; expect out of functions, that their domain is total
;; and that each element of the domain maps to
;; just one element of the range.
;;
;; In first-order logic:
;; (for all x, y, z: P(x, y) and P(x, z) implies y = z)
;; and
;; (for all x: there exists y: P(x, y))
(define (function-model? model@)
(local ((define-unit-binding a-model@
model@ (import) (export function^))

(define-unit function-tester@
(import function^)
(export)
(and (for-all* (lambda (x y z)
(implies? (and (P x y) (P x z))
(equal? y z)))
universe universe universe)
(for-all* (lambda (x)
(exists? (lambda (y) (P x y))
universe))
universe))))
(invoke-unit
(compound-unit/infer
(import)
(export)
(link a-model@ function-tester@)))))

(There are a few definitions I’ve left out here; see logic-practice.ss for the other definitions.)

Once we have this, we can now check to see if squaring@ and less-than@ satisfy the function-model? predicate.


> (function-model? squaring@)
#t
> (function-model? less-than@)
#f

function of the day: fold

The fold function does very much what the name implies: it’s meant to fold ingredients into a big mixing bowl, of course. Here’s a definition:


;; fold: (ingredient bowl -> bowl) bowl (listof ingredient) -> bowl
;; Folds in a list of ingredients into a bowl with a folding-action.
(define (fold folding-action a-bowl ingredients)
(cond
[(empty? ingredients) a-bowl]
[else
(local ((define mixed-bowl (folding-action
(first ingredients)
a-bowl)))
(fold folding-action mixed-bowl (rest ingredients)))]))

FOLD here adds an ingredient at a time, using the folding-action to mix in every ingredient thoroughly into our large bowl. Once we have this incorporating function, we can roll up our sleeves and whisk some pancake batter:


;; make-pancake-batter: -> string
;; Example of FOLD to make pancake batter.
(define (make-pancake-batter)
(local ((define (whisk an-ingredient a-bowl)
(string-append a-bowl an-ingredient))

(define pancake-ingredients '("flour" "sugar" "eggs" "milk"))

(define empty-bowl ""))
(fold whisk empty-bowl pancake-ingredients)))

Oh! I forgot the baking powder, so those pancakes will be a little stiff. Oh well.

Of course, we might even want to whisk in a slightly different way:


(local
((define (whisk an-ingredient a-bowl)
(cond [(string=? an-ingredient "eggs")
(string-append a-bowl "egg-white-only")]
[else
(string-append a-bowl an-ingredient)])))
(fold whisk "" '("flour" "eggs" "cabbage")))

Now we’ve got the basics of an okonomiyaki, I suppose.

We might even be silly enough to mix things that aren’t even food!


> (fold + 0 '(1 2 3 4 5))
15

but this seems like a boring example compared to whisking.

Folding is popular, but for some reason it goes by different names by different programming camps. Python programmers call it REDUCE, and Ruby programmers call it INJECT. I don’t know about these names, though: I think they sound a little bit aggressive for my taste. As for me, I like the homeliness of “fold”: it reminds me of the kitchen.

birthday

I felt a little silly today, and just learned about SRFI 42 (Eager Comprehensions), so I thought I might play with it on a trivial example.


(module happy-birthday-song mzscheme
(require (lib "etc.ss")
(lib "42.ss" "srfi"))

(provide sing)

;; sing: string -> void
;; Prints out the popular happy birthday stanza.
(define (sing person)
(local ((define (trailer i)
(cond [(= i 2)
(format "dear ~a" person)]
[else
"to you"])))
(do-ec (: i 4)
(begin
(display "Happy birthday ")
(display (trailer i))
(newline))))))

crazed

I think I came out a bit raving during Thursday’s Coding Dojo; I did a quick-and-dirty derivation of the brute-force countdown program for last afternoon’s session, and I only had an hour to work with. Not only that, but I had to try to explain what I was doing while coding things up, and that almost inevitably gets me into trouble. And I needed to write unit tests too. And make unintentional mistakes to justify those unit tests. I’ll show one of those mistakes at the end of this post.

Actually, it was really exciting! But my body felt so totally exhausted at the end of it. Much of it is performance, exaggerations and all. My stage persona is one that’s, well, a bit crazed. I’m not exactly sure what the audience thought about it. I hope folks thought was worth it and that the content was useful.

The function where I made a mistake was this: we were writing a function to see if any number expression was reused. One way to check for this condition is to do a depth-first traversal across the expression, watching to see if any number appears twice.

Here’s a variation of what I did:


(require (lib "plt-match.ss"))

;; Data structures, of course, for our expressions:
(define-struct num (n))
(define-struct comb (left op right))

;; is-legal?: expr -> boolean
;; Returns true if no num is reused more than once in the expression
;; or its subexpressions.
(define (is-legal? expr)
(define ht (make-hash-table))

(define (seen-already? expr)
(hash-table-get ht expr #f))

(define (mark-as-seen! expr)
(hash-table-put! ht expr #t))

(let loop ([expr expr])
(match expr
[(struct num (n))
(cond
[(seen-already? n) #f]
[else
(mark-as-seen! expr)
#t])]
[(struct comb (l o r))
(and (loop l) (loop r))])))

Thankfully, I also wrote a test case.


(require (planet "test.ss" ("schematics" "schemeunit.plt"))
(planet "text-ui.ss" ("schematics" "schemeunit.plt")))

(define simple-test-suite
(test-suite
"testing"
(test-true "check simple case"
(is-legal? (make-num 3)))
(let ([n1 (make-num 4)])
(test-false "check false"
(is-legal? (make-comb n1 + n1))))))

(test/text-ui simple-test-suite)

And the test case quickly showed that I screwed up somewhere.


Welcome to DrScheme, version 369.6-svn24jan2007 [3m].
Language: Pretty Big (includes MrEd and Advanced Student).
testing > check false
check false has a FAILURE
name: check-false
location: struct:object:...ascheme/diva-link.ss:124:4>:39:5
params: (#t)
1 success(es) 1 failure(s) 0 error(s) 2 test(s) run

Oh no! Terror! But thankfully, I figured out I had made a type error: the hash-table should always hold expressions, and to my chagrin, I stuffed the primitive number into it instead. Easy to fix.


(define (is-legal? expr)
(define ht (make-hash-table))

(define (seen-already? expr)
(hash-table-get ht expr #f))

(define (mark-as-seen! expr)
(hash-table-put! ht expr #t))

(let loop ([expr expr])
(match expr
[(struct num (n))
(cond
[(seen-already? expr) #f]
[else
(mark-as-seen! expr)
#t])]
[(struct comb (l o r))
(and (loop l) (loop r))])))

And hesitantly pressed Run on my tests.


Welcome to DrScheme, version 369.6-svn24jan2007 [3m].
Language: Pretty Big (includes MrEd and Advanced Student).
2 success(es) 0 failure(s) 0 error(s) 2 test(s) run

Hurrah.

In all, it was a fun day.

countdown

Recently, I’ve been going to a Coding Dojo to practice my programming chops. One of the problems presented so far has been the Countdown program from RubyQuiz. I thought I might give it a shot, and cooked up a solution in Scheme, and it wasn’t too bad.

I’ll try to give an write-up on how one might attack the problem starting from scratch, and rather than just give a perfect solution, I’ll go at this iteratively. (And make accidental mistakes along the way!)

The idea behind the countdown problem is that we are doing exhaustive “brute-force” search for all arithmetic expressions. For example, if we limit ourselves to the numbers 3, 4, and 5, and the only operations are addition and multiplication, here’s a conceptual trace of what expressions we’ll be brutishly looking at:

3
4
5

That the first phase. Then we take pairs of numbers here, and build new expressions:

3 + 4
3 + 5
4 + 5
3 * 4
3 * 5
4 * 5

Ok, now we take pairs again, combining stuff from previous phases and the phase we just generated:

3 + (4 + 5)
3 + (4 * 5)
4 + (3 + 5)
4 + (3 * 5)
5 + (3 + 4)
5 + (3 * 5)
3 * (4 + 5)
3 * (4 * 5)
4 * (3 + 5)
4 * (3 * 5)
5 * (3 + 4)
5 * (3 * 5)

Whew! Even with three numbers, this gets a bit long.

I should be more formal for a moment. By an expression, I mean either a number, or something that involves two smaller expressions and a number. In Backus-Naur Form, that’s:


expression = number
| expression op expression

Let’s create a data definition in Scheme for this.


(module countdown mzscheme
(provide (all-defined))
;; An expression is either a
;; (make-num n)
;; where n is a number, or
;; (make-comb l o r)
;; where l and r are expressions, and op is an operator.
(define-struct num (n))
(define-struct comb (left op right)))

Ok, we have our expression data definition. We should also make a quick-and-dirty helper function to help us visually read expressions; let’s call this expression->string:


(module countdown mzscheme
(require (lib "plt-match.ss"))

;; [data definition omitted]

;; expression->string: expression -> string
;; Makes a nice human-readable expression.
(define (expression->string an-expr)
(define (operator->string an-op)
(cond
[(eq? an-op +) "+"]
[(eq? an-op *) "*"]))

(match an-expr
[(struct num (n)) (format "~a" n)]
[(struct comb (l o r))
(format "(~a ~a ~a)"
(expression->string l)
(operator->string o)
(expression->string r))]))

Ok, now that we’ve got this, let’s exercise the code.


> (expression->string (make-comb (make-num 3) + (make-num 4)))
"(3 + 4)"

Good. But I’m feeling guilty; we should really make this a unit test. Let’s pull in SchemeUnit, the unit testing framework for Scheme.


(module countdown mzscheme
(require ;; [other packages omitted]
(planet "test.ss" ("schematics" "schemeunit.plt" 2))
(planet "text-ui.ss" ("schematics" "schemeunit.plt" 2)))

;; [code omitted]

(define countdown-tests
(test-suite
"tests for countdown"
(test-equal?
"expression->string simple test"
(expression->string (make-comb (make-num 3) + (make-num 4)))
"(3 + 4)")))

(test/text-ui countdown-tests))

If we run this module, we see:


1 success(es) 0 failure(s) 0 error(s) 1 test(s) run
>

Very good.

Now let’s see if we can build new expressions from old ones. The idea is that, if we have an existing collection of expressions, we want to pair two of them up together and do something with them. We might do this naively:


;; for-each-pairs: (X X -> void) (listof x) -> void
;; Calls f on distinct ordered pairs in the collection.
(define (for-each-pairs f collection)
(let outer-loop ([i 0])
(when (< i (length collection))
(let inner-loop ([j (add1 i)])
(when (< j (length collection))
(f (list-ref collection i) (list-ref collection j))
(inner-loop (add1 j))))
(outer-loop (add1 i)))))

Does this work?


> (for-each-pairs (lambda (x y) (printf "~a ~a~n" x y)) '(red blue green))
red blue
red green
blue green

Looks reasonable. Of course, now we want to use this to collect up all the pairs and build an addition and a multiplication from x and y. Let’s call this build-next-generation. Oh, let’s write our unit test first:


(test-equal?
"build-next-generation simple"
(map expression->string
(build-next-generation (list (make-num 3)
(make-num 4))))
(list "(3 + 4)" "(3 * 4)"))

Ok, let’s roll up our sleeves and do it.


;; build-next-generation: (listof expression) -> (listof expression)
;; Constructs new expressions from pairs of old ones.
(define (build-next-generation expressions)
(define next-gen '())

(define (collect! an-expr)
(set! next-gen (cons an-expr next-gen)))

(define (visit-pair e1 e2)
(collect! (make-comb e1 + e2))
(collect! (make-comb e1 * e2)))

(for-each-pairs visit-pair expressions)
(reverse! next-gen)
next-gen)

Ok, should work. On every pair, we combine two expressions, and collect them. We do a reverse! to put things in the order expected by the test case. (Although that might be a little silly.) Let’s rerun our unit tests.


tests for countdown > build-next-generation simple
build-next-generation simple has a FAILURE
name: check-equal?
location: #:67:5
params: (("(3 * 4)") ("(3 + 4)" "(3 * 4)"))
actual: ("(3 * 4)")
expected: ("(3 + 4)" "(3 * 4)")
1 success(es) 1 failure(s) 0 error(s) 2 test(s) run

What?! Yes, there’s something wrong here.

It turns out that I’ve misused reverse! here: I should just take the result of reverse! and return it directly.


(define (build-next-generation expressions)
(define next-gen '())

(define (collect! an-expr)
(set! next-gen (cons an-expr next-gen)))

(define (visit-pair e1 e2)
(collect! (make-comb e1 + e2))
(collect! (make-comb e1 * e2)))

(for-each-pairs visit-pair expressions)
(reverse! next-gen))

Hurrah for unit tests. But maybe we shouldn’t do the reverse after all. Let me just fix up the test case to expect the paired expressions in a different order. Since I’ve made so many changes, let’s show what the code looks like now:


(module countdown mzscheme
(provide (all-defined))
(require (lib "plt-match.ss")
(planet "test.ss" ("schematics" "schemeunit.plt" 2))
(planet "text-ui.ss" ("schematics" "schemeunit.plt" 2)))

;; An expression is either a
;; (make-num n)
;; where n is a number, or
;; (make-comb l o r)
;; where l and r are expressions, and op is an operator.
(define-struct num (n))
(define-struct comb (left op right))


;; expression->string: expression -> string
;; Makes a nice human-readable expression.
(define (expression->string an-expr)
(define (operator->string an-op)
(cond
[(eq? an-op +) "+"]
[(eq? an-op *) "*"]))

(match an-expr
[(struct num (n)) (format "~a" n)]
[(struct comb (l o r))
(format "(~a ~a ~a)"
(expression->string l)
(operator->string o)
(expression->string r))]))

;; for-each-pairs: (X X -> void) (listof x) -> void
;; Calls f on distinct ordered pairs in the collection.
(define (for-each-pairs f collection)
(let outer-loop ([i 0])
(when (< i (length collection))
(let inner-loop ([j (add1 i)])
(when (< j (length collection))
(f (list-ref collection i) (list-ref collection j))
(inner-loop (add1 j))))
(outer-loop (add1 i)))))


;; build-next-generation: (listof expression) -> (listof expression)
;; Constructs new expressions from pairs of old ones.
(define (build-next-generation expressions)
(define next-gen '())

(define (collect! an-expr)
(set! next-gen (cons an-expr next-gen)))

(define (visit-pair e1 e2)
(collect! (make-comb e1 + e2))
(collect! (make-comb e1 * e2)))

(for-each-pairs visit-pair expressions)
next-gen)


(define countdown-tests
(test-suite
"tests for countdown"
(test-equal?
"expression->string simple test"
(expression->string (make-comb (make-num 3) + (make-num 4)))
"(3 + 4)")
(test-equal?
"build-next-generation simple"
(map expression->string
(build-next-generation (list (make-num 3)
(make-num 4))))
(list "(3 * 4)" "(3 + 4)"))))

(test/text-ui countdown-tests))

Ok! Does this do what we’ll need for brute-forcing the countdown problem?


> (define expressions (list (make-num 3)
(make-num 4)
(make-num 5)))
> (define generation-1 (append expressions (build-next-generation expressions)))
> (define generation-2 (append generation-1 (build-next-generation generation-1)))
> (map expression->string generation-2)
("3"
"4"
"5"
"(4 * 5)"
"(4 + 5)"
"(3 * 5)"
"(3 + 5)"
"(3 * 4)"
"(3 + 4)"
"((3 * 4) * (3 + 4))"
"((3 * 4) + (3 + 4))"
"((3 + 5) * (3 + 4))"
;; ... a LOT of output omitted
"(3 * (4 * 5))"
"(3 + (4 * 5))"
"(3 * 5)"
"(3 + 5)"
"(3 * 4)"
"(3 + 4)")

It’s a beginning. It’s not quite right, but it’s getting there. Since this post is getting long, I’ll split this up with another blog post later.

debugging test-case

I thought it might be useful to do a stream-of-consciousness post about what a programmer does when he or she sees a bug and wants to fix it.

The bug in question is in DrScheme, and it’s triggered whenever one goes to the Special menu and runs an “Insert Test Case”. From that point on, the resulting program is uncompilable, with the following error message:


require: broken compiled code (phase 0, defn-phase 0): cannot find module |,/Users/dyoo/local/plt/collects/test-suite/private/test-case| in: test-case

The first thing I wanted to do was isolate the problem: what code is responsible? I knew the functionality in question had something to do with “Insert Test Case”, so let’s start there.


mithril:~ dyoo$ cd local/plt/collects/
mithril:~/local/plt/collects dyoo$ cd string-constants/
mithril:~/local/plt/collects/string-constants dyoo$ grep 'Insert Test Case' *
english-string-constants.ss: (test-case-insert "Insert Test Case")
portuguese-string-constants.ss: (test-case-insert "Insert Test Case")

I had some previous knowledge that the menus in DrScheme were all internationalized, so I could start by searching through the string-constants directory to start my search. Whatever code uses test-case-insert is probably related, so we should start searching for occurrences of that now.


mithril:~/local/plt/collects/string-constants dyoo$ cd ..
mithril:~/local/plt/collects dyoo$ grep -r test-case-insert *

A bunch of output spews out, but I’ll ignore anything dealing with string constants; if I do that, I see that there’s a particular collection called test-suite, and that sounds promising.

Next thing to do: let’s see if anyone else has already tried looking at this, by searching http://bugs.plt-scheme.org. Yup, there appear to be a few. Bugs 7001, 7317, and 7373 seem to be the same bug. Ok, time to read those bugs reports thoroughly just to make sure I understand what other people have said about this.

Ok, it looks like Robby mentioned a workaround: if the user enters:


(require (lib "test-case.ss" "test-suite" "private"))

then things should work out. Yup, I can verify that this works. But that seems really odd to have to do this!

I’ll start to look at test-suite and see what the overall flow of the program is.

[will fill in as soon as I finish doing a review]

[hours pass…]

Well, I traced the issue down to how the snips make external requirements that can’t always be met, especially in modularized code. I posted a question about it in the PLT list, and then, a few days later, they were obliterated altogether.
So, in summary: the code I studied is no longer relevant. It happens.

heresy

Every so often, a fey mood takes me, and I write a program that probably shouldn’t see the light of day. I’ve done so with a PLT package called infix. It’s a package for writing infix expressions in PLT Scheme, but it does some other funky stuff. For example:


(module test mzscheme
(require (planet "infix.ss" ("dyoo" "infix.plt" 1 0)))

(infix printf("hello, this is a test: ~a ~a~n",
list(3, 4),
5))

(define (in-order a b c)
(infix printf("in-order(~a, ~a, ~a): ~a~n",
a, b, c, a <= b <= c))) (infix in-order(1, 2, 3)) (infix in-order(1, 3, 2)))

I had a very good laugh with Guillaume when I showed this to him. You have to be a Schemer to appreciate how very wrong this is.

This technique is a proof-of-concept that shows just how programmable the PLT Scheme syntax system can be. It wouldn't be much more work to embed a different programming language syntax in here, as long as it's compatible with s-expressions. The source code for this can be found here.