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.