Thursday, February 08, 2007

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.

3 comments:

Raoul Duke said...

hi Danny, Slenk here - doesn't PLT have some kind of type inference/checker tool these days? I forget.

Danny Yoo said...

Hey, good to see you again!

There's a Typed Scheme language now, but I haven't played around with it too much yet.

Raoul Duke said...

Funny. I think I really like type inference, so I'm sad Typed Scheme doesn't do that. But on the other hand, I've read recently in various places that when you run into the usual typing heck in O'Caml or Haskell, the trick is to add explicit type signatures to your functions, and that it helps narrow down what/where on earth the actual error is.

on the other hand, i've already come across one person saying the opposite, that *removing* them helps. i give up ;-) - somebody needs to write an interactive debugger for the type checkers...