Programmed Learning

As I was listening to Guy Steele from a talk he gave at Dan Friedman’s 60th birthday, I was a little shocked when Guy voiced the relationship between B.F. Skinner’s Programmed Learning method and the style of the conversation used in the Little Schemer.
I didn’t really think of it that way, and now I’m trying to sort out why I have a negative feeling about Programmed Learning and positive feelings about The Little Schemer.

What both seem to do right is quick iteration: rather than lecture (which bores me to tears), they instruct with a running conversation, Socratic style. I think what’s different, at least in the examples that Guy gave, was the degree of difficulty in the questions. In the examples with Skinner, the respondent answer in one-word sound bites, and there’s a feeling of rote memorization and little thinking. In contrast, in the Little Schemer, the questions require a lot more out of the student. The stepping stones are spaced widely.

So there are two ideas I’m picking out of this: just as in Agile development, I should be aiming toward iterative learning. At the same time, even though the iterations are fairly regular, the goals in each iteration shouldn’t be trivial, but have some real substance behind it.

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.

latex


So I visited Amazon today to buy an egg timer. I was amused to see the following from Amazon’s computerized recommendation system. The items were supposedly based on my prior purchases. I’ve put a screenshot of it here, just in case anyone else gets a chuckle out of it.

new year

I came in last night from California back into Worcester. I opened my apartment door, half-expecting a nest of mice to scatter. If there were any, I didn’t see them. I fell blissfully asleep. I’ve been sleeping too much lately. Classes start tomorrow, so I suppose that will be remedied.

I’m about to fall asleep again, but before that happens, let me mention DivaScheme 2.1.

Here’s hoping this New Year is a good one!

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.

christmas

Merry Christmas to my family and friends! What I have been gifted with is much more than I expected or deserved. I’m thankful for everyone’s support and love.
I don’t have anything really programming-related to say (because my brain’s fried from debugging DivaScheme).

May your holidays be peaceful and without the need of an exception handler.

the moon

I woke up early on Saturday to catch the airport shuttle. It was one of those hours of the night when everything was still and dark, one of those magic weird moments.

I could see a crescent moon above me, like a sharp scythe. But have I really seen a scythe in real life? The only scythe I know is the one held by a Grim Reaper, and that’s clearly fantastical. I have no practical experience with them. So what else would be a good analogy from my own experience?

The moon looked like a large left parenthesis. As soon as that thought floated in my head, I knew. I was doomed.

Anyway, it’s nice to be in California again.

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.