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.

falling snow

I saw a hint of snow by the window.

I thought for a moment that I had been seeing ash drifting in the air, but one step out into the frigid air convinced me. Snow! (Sad girl in snow?)

It's cold outside! It's not yet the kind of cold that makes one think of fairy tales and wolves, but it's slightly chilly now.

baking bread

I had the compulsion to bake bread for about a week, but having never done so before, I hesitated. Do I get a bread machine, or buy a few books, or...?

It turns out there is a very nice recipe for newbies like me. I tried it, and it didn't turn out half bad.

I suppose this is why almost everyone is forced to write a "hello world" program when they start off learning to program. If only "hello world" were more... sustaining.

how not to write xml

I came across Writing XML with Java the other day, and hoped that the authors wouldn't advocate building XML through plain string concatenations. Unfortunately, they had.

Here's what the author said to justify this:

Eventually we’ll take up some alternatives to the direct string approach such as DOM and JDOM that do allow you to automatically maintain well-formedness and sometimes even validity. However, for many simple cases, these are vast overkill. It can be much simpler to just write a few strings onto an output stream.

I disagree: maintaining well-formedness should be the computer's job, not ours, because it it mindless and very easy to get wrong if we do it by hand. Well-formedness is something I shouldn't have to worry about: it should be trivial to get this right.

The author also said:

Making sure the output is correct is simply one part of testing and debugging your code.

Yes, making sure we're outputting the right thing is part of a good test suite. But there are some kinds of bugs that just don't deserve to be out into the open. The most common error I've seen in HTML/XML generation is failing to properly quote and escape things. It's precisely because of this cavalier attitude toward generating structured data that we see such problems.

Here's the style of code they wrote (translation of Exercise 3.8):

  (define (simple)
    (printf "<?xml version=\"1.0\"?>~n")
    (printf "<mathml:math xmlns:mathml=\"http://www.w3.org/1998/Math/MathML\">~n")
    (let loop ([i 1]
               [low 1]
               [high 1])
      (when (<= i 10)
        (printf "<mathml:mrow>~n")
        (printf "     <mathml:mi>f(~a)</mathmi>~n" i)
        (printf "     <mathml:mo>=</mathml:mo>~n")
        (printf "     <mathml:mn>~a</mathml:mn>~n" low)
        (printf "</mathml:mrow>~n")
        (loop (add1 i) high (+ high low))))
    (printf "</mathml:math>~n"))

This style of building XML is simple, as the author notes, but it doesn't scale. As soon as we start dealing with XML documents that have interesting content, we suddenly have to start thinking about HTML injection issues, entity quotation, and keeping those darn tags balanced all the time.

Writing code that treats the XML as real structure is not much harder than the above:

  (require (lib "xml.ss" "xml")
           (lib "list.ss"))
  (define (simple-2)
    (define (make-row i low)
      `(mathml:mrow (mathml:mi ,(format "f(~a)" i))
                    (mathml:mo "=")
                    (mathml:mn ,(format "~a" low))))
    (define (make-rows)
      (let loop ([i 1]
                 [low 1]
                 [high 1])
        (cond
          [(<= i 10) (cons (make-row i low)
                           (loop (add1 i) high (+ high low)))]
          [else empty])))
    (printf "~a" (xexpr->string
                  `(mathml:math
                    ((xmlns:mathml "http://www.w3.org/1998/Math/MathML"))
                    ,@(make-rows)))))

The difference here is that all the niggling issues from the first example --- balancing tags, properly quoting values --- don't apply at all. The XML library takes care of this busywork, as it should. It's guaranteed to be well-formed.

Not everything has to be treated as a string. We shouldn't be afraid to play with structured data.

streaky

There's a peculiar behavior in human psychology where something that catches your attention ends up showing up everywhere. Knuth noticed it in his discussion on randomness. We are pattern matchers: we try to make sense of the world by looking at similarity, at streaks of continuity.

So I was amused to post this and that within the same week.

in summation...

In an earlier post, I wondered out how to get a closed form for my car debt. The program I wrote can be actually thought of as a recurrence relation:

   debt at the very beginning = initial debt at zero months

   debt(n) = monthly interest * (debt from last month - my monthly car payment)
             and where n has to be greater than 0.

But since that's a bit wordy, I'll use some shorter variable names when I'm talking about the debt I'm incurring at month n:

   d(n) = I * (d(n-1) - P)     for n > 0
        = I * d(n-1) - I*P     for n > 0

I didn't quite remember how to get a closed form for this formula at the time. Yesterday, though, as I was quaffing a coffee at Cape Cod, I flipped through Concrete Mathematics. There in the first few pages of the book was the technique I needed!

The core idea is to use a summation factor to make the function I'm solving for a little simpler. For the recurrence above,

   (1/I)^n

is a good summation factor. When I multiply my recurrence with it, I get:

   d(n)/(I^n) = d(n-1)/(I^(n-1)) - P/(I^(n-1))     for n > 0

The reason this is simpler is because I can consider a parallel formula:

   S(n) = d(n) / (I^n)

which I can use to restate the recurrence as:

   S(0) = d(0) / (I^0) = d(0)         (since anything to the zeroth power is 1)
   S(n) = S(n-1) - P/(I^(n-1))        for n > 0

And now S(n) is, structurally, simple enough to be treated as a straight summation rather than a wacky recurrence:

   S(n) = d(0) - sum across k from 1 to n of: P/(I^(k-1))

        = d(0) - P * sum across k from 0 to (n-1) of: (1/I)^k

        = d(0) - that horrendous sum

But it turns out that that horrendous sum is actually not bad at all. If we squint our eyes at it, it's a geometric sum, and those have a very nice closed form: it's the "first term - the first excluded term in the sum, divided by one minus the term ratio". That is, if I'm doing:

   a^0 + a^1 + a^2 + ... + a^n

I don't have to actually add up all those terms: I can just do:

   ((a^0) - a^(n+1)) / (1 - a)

So by applying the transformation on that geometric sum, I can get a closed form for S(n):

   S(n) = d(0) - P * sum across k from 0 to (n-1) of: (1/I)^k
        = d(0) - P*(1 - (1/I)^n)/(1 - 1/I)

But S(n) isn't what I was originally going after: I was going after d(n), so let me backpatch that fix in:

   S(n) = d(n) / (I^n), so
   d(n) = S(n) * I^n

That is, my car debt at any given month is going to be:

   d(n) = I^n * (d(0) - P*(1 - (1/I)^n)/(1 - 1/I))

Whew! Let's try that out:

(module car-payment-2 mzscheme
 ;; debt: number number number number -> number
 ;; Returns the amount of money owed after months pass,
 ;; given a particular monthly payment and apr rate.
 (define (debt months initial-debt monthly-payment apr)
  
   ;; closed-form: number number number number -> number
   ;; This is a closed form solution for the recurrence:
   ;;
   ;; d(n) = I * (d(n-1) - P)
   ;;
   ;; d(n) = I^n * (d(0) - P*(1 - (1/I)^n)/(1 - 1/I))
   (define (closed-solution n d0 P I)
     (let* ([I^n (expt I n)]
            [1/I (/ 1 I)]
            [1/I^n (/ 1 I^n)])
       (I^n . * .
            (d0 . - .
                ((P . * . (1 . - . 1/I^n))
                 . / .
                 (1 . - . 1/I))))))
  
   (let ([monthly-interest (+ 1 (/ apr 12))])
     (closed-solution months
                      initial-debt
                      monthly-payment
                      monthly-interest))))

and let's look at a few values:

> (debt 0 16300 327.93 0.0767)
16300
> (debt 1 16300 327.93 0.0767)
16074.158147416665
> (debt 2 16300 327.93 0.0767)
15846.872788992236
> (map (lambda (x) (debt x 16300 327.93 0.0767))
      (list 0 1 2 3 4 5 6 7 8 9 10))
(16300
16074.158147416665
15846.872788992236
15618.13469831854
15387.934590015295
15156.263119353142
14923.110881874338
14688.46841301098
14452.32618770081
14214.67462000053
13975.5040626967)
> (map (lambda (x) (debt x 16300 327.93 0.0767))
      (list 56 57 58 59 60))
(1150.9196104211048
828.2498856810436
503.5177636170277
176.71006207281036
-152.1864853637734)

I did a little fist-pump after I got this working. CS students are weird.

the guy in the second row

I've always wondered what was up with the
guy in the second row, the person in any class that seems to hold a personal conversation with the professor. God, those people were both impressive and annoying.

God has a sense of humor. To my horror, I've found that I've become one of those people.

Sometimes I wonder if it would have been better to go with the meek and shy persona in class. Oh well. Jay Parini wrote in The Art of Teaching that a successful teacher is a stage performer, that they have no choice but to adopt a persona to become a successful teacher. I suppose that goes for students as well.

(new car% [brand "toyota"] [type "corolla"])

The big thing that's happened this weekend was getting a car; I bought a 2007 Toyota Corolla. I still have some mixed feelings about this, but I think I'll need it to survive the winters here.

These machines cost a lot! I dropped by http://www.edmunds.com/apps/calc/CalculatorController. But it's a black box to me: I had no real idea how it was actually doing its calculation. So I tried to cook up the calculations from scratch:

(module car-payment mzscheme
  ;; Small toy code for calculating car stuff.
  (provide (all-defined))
  
  ;; debt: number number number number -> number
  ;; Returns the amount of money owed after months pass,
  ;; given a particular monthly payment and apr rate.
  (define (debt months current-debt monthly-payment apr)
    (let loop ([n months]
               [current-debt current-debt])
      (cond
        [(= n 0) current-debt]
        [else
         (let ([monthly-interest (/ apr 12)])
           (loop (sub1 n)
                 (* (+ 1 monthly-interest)
                    (- current-debt monthly-payment))))])))
  
  ;; months-till-debt-free: number number number -> number
  ;; Returns how many months have to pass before we're debt free.
  (define (months-till-debt-free initial-cost monthly-payment apr)
    (let loop ([n 0])
      (let ([new-debt (debt n initial-cost monthly-payment apr)])
        (cond
          [(<= new-debt 0) n]
          [else (loop (add1 n))])))))

Now I could verify for myself: how long would it be until I dig myself out of a big hole?

> (months-till-debt-free 16300 327.93 0.0767)
60

Oh. Ok, so at least it looks like the code is doing the same thing as the Edmunds calculator. That's good.

I should brush up on my recurrence relations, though, since I'm sure that there's a closed form for this calculation.

lights out

Some fragmented, disconnected thoughts:

My room light in Providence blew out two weeks ago. I jumped, but couldn't reach the ceiling. I told the landlady about it, but she said not to worry, since I would be moving out anyway.

A few days later Felix and I chatted about manga; he asked what the Japanese word for "light" was. "Hikari," I said with assurance. Felix raised his eyebrow, and countered that he was sure it was "Raito". We were confused. It turns out, though, that we were both right: "Raito" is the Engrish romanization for "light". I groaned.

I remember watching Guillaume standing on top of his patio, trying to catch the dying sunset in his digital camera. I came to visit his place again, and the lights were out; he had moved back to Montreal. I hope he's doing ok. My summer at Brown is over.

Four days ago, as I climbed the steps to my new apartment in Worcester, I saw a notice: "TO ALL TENANTS: THE POWER WILL BE OUT FOR TWO DAYS AS WE WILL BE REPLACING THE ELECTRICAL SYSTEM." Suddenly, the prospect of living on the tenth floor didn't seem so comfortable.

Yesterday, I flew back from Providence to LA to see my folks. As I entered the airport, I could hear sirens going off, and all the computer monitors were dead black. The electricity at the airport had blown, and everything was at a standstill. I sighed.

Looking back at the last few days, I notice that I've been leaving a trail of darkness in my wake.

in bed

I recently went to a Chinese buffet restaurant on Sunday, and my fortune cookie for that day had an unusual property of passive resistance:

If you think you're too small to be effective, you have never been in bed with a mosquito.

emacs / DrScheme keystroke of the day: kill!

C-M-k: kills the s-expression to the right of the cursor point. This is really useful in parenthetical languages like Scheme, since it further reduces the need to count parentheses.

But speaking of keystrokes, I should lay off typing for a little time; my wrists have been itching as of late, and I think I've been overdoing my keyboarding. I'm back in LA to attend Ken's wedding, so I should use this time to get away from the keyboard. But I'm typing at this very moment! But I can't write what I'm thinking without typing... Argh... C-c C-c C-c C-c...

reading papers: Exploring the Design of an Intentional Naming Scheme with an Automatic Constraint Analyzer

Notes to self on http://sdg.csail.mit.edu/pubs/2000/INS_ASE00.pdf. I'm revising this as I read more.

Shallow summary: the authors use Alloy, a model checker, to validate the design of the Intentional Naming System (INS); along the way, they show that INS has flaws in it. They use Alloy as a counterexample generator and as a tool to explore INS's design.

What questions does the paper ask?

* When does INS break?
* When does it work?
* Can we use the model to describe general properties for any intentional naming system?

Why is this novel?

* It's another data point showing that model checking can be used effectively in real world applications.
* It shows, in particular, that Alloy can handle the modeling of complex data structures. This is a new application of Alloy to a recursive algorithm (Lookup-Name) that has not been done before.

learning to play wisely

I just played another Go game with Guillaume. One of the problems I have is that when I see a ko that I can fight, I'll rush into it like a lemming.

It must be exhausting to play me sometimes.

I have to stop fighting just for the sake of fighting. Playing games is not all I'm doing for the summer. I am getting a Nintendo DS tomorrow, though. Hmmm...

In retrospect, I suppose I am playing too many games. The days here at Brown have been a lot of fun, but there is serious work I am trying to do. (Or am I trying to be serious about my work?) I've been fighting with PLT Scheme's module system; who knew that loading a module could be so frustrating sometimes?

The issue I've been seeing involves trying to erase lexical scope and inject modules through the blood-brain barrier that is PLT Scheme's evaluation REPL. DrScheme likes to fight back, and I find myself very exhausted and writing error prone code.

In fact, my lexical-scope-erasing macro code was flawed; here's the corrected code. So Schemers do write buggy code too.

If only it were easy to transfer my determination in playing into programming well.

learning to resign

I've been playing Go with Guillaume; it's a lot of fun, but occassionally I get boneheaded and just don't know when to resign. It's bad courtesy, and I should be better about it. There's a difference between optimism and denial, and I resolve to tell the difference better next time.

There's also a point when one is programming something difficult; sometimes I feel like I should resign and step back and see that my approach is altogether wrong. But there's the mythology of the heroic programmer --- that one last bug fix, and maybe-if-I-fiddle-with-this-it-will-work syndrome --- that I'm still enamored with.

This fault runs deep in me, and I will need to retrain myself to be less silly.

getting started in programming language theory

These are the two textbook resources I'm reading to get myself up to speed:

• Programming Languages: Application and Interpretation


• Programming Languages and Lambda Calculi

The second book, PLLC, is a very good book that appears to cover the same material as in Benjamin Pierce's Types and Programming Languages. (Why do all these textbooks have four-letter acronyms?)

nightmare

I wanted to post something entirely non-programming related. I had a nightmare last night; I dreamt of atomic bombs going off. It was bizarre; in my dream, I imagined that the ISS had been taken over by terrorists (or aliens; not quite sure who was responsible here). LA had been hit by bombs, the floor shuddered, and blackness. The scene shifted, and I stumbled into a dark bar. CNN played in the dim light. Were the talking heads even American? Whispers all around. And again, the lights went out, screams, and I heard a large thudding roar in the distance, with the earth shifting in protest. Much too close. I tried to close the ajar bar door. It didn't help, but it made me feel better.

It was as if I were an extra in a bad B-rated movie. I stirred and, half-waking, looked at my clock. 8:00am. Well, there's nothing else to do. The Apocalypse dream is, at least, more interesting than getting up. Might as well watch how this all ends. I went back to sleep to finish watching the nightmare of my dreams. I don't remember what happened afterwards.

I write this now so that my future self can laugh at me. What a strange time we live in.

Speaking of anxieties: I'm going here tomorrow. Not to say that this has anything to do with my nightmares.

macro-happy

I'm still a little too macro-happy these days. Hopefully this phase will pass.


I found a few good references on guidelines for macros:
http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/msg02079.html

I can't end this without not posting my little assert macro

  (define-syntax (assert stx)
    (syntax-case stx ()
      [(_ expr)
       (quasisyntax/loc stx
         (unless expr
           (error 'assert (format "~a lineno ~a: ~s failed" 
                                  #,(syntax-source stx)
                                  #,(syntax-line stx)
                                  (quote expr)))))]))

Reading and writing

I've been reading Richard Gabriel's book, "Writers' Workshops & the Work of Making Things". I'm really liking what I've read so far. It speaks a lot to what I think about collaborative learning --- what we do when we read and write each other's programs to give and share the gift of making.

In some sense, a mailing list like tutor@python.org tries to --- perhaps instinctively --- follow the writers' workshop environment. There is satisfying work in building communities that help each other; I would like to continue with it.

Besides reading, I'm continuing my study of PLT Scheme, and think that I can contribute to the documentation-for-mainstream-programmers-is-missing problem. I'll start by attacking classes, since that'll be the thing that Java programmers will reach first, and I'll probably try to tackle MrEd next.

Last: sometimes I'm too eager to jump into a question and write something that I think is helpful; I should watch out not to reveal too much, lest I do damage. The lessons that John Holt learned in How Children Fail should always be at the back of my mind.

opening the time capsule

I've been starting to browsing through old archives of the RnRS mailing list and it's a blast to see how the ideas behind Scheme have evolved.

For example, it was somewhat shocking (and amusing) to hear that call-with-current-continuation was deliberately named to make it hard for programmers to type and misuse!

Well, better continue reading; I've only read up to 1985, and there's a few more years of mail left to read...

learning to read papers: why calculating is better than scheming

I just finished reading Why calculating is better than scheming, and it's good stuff. But I get the feeling that I'll need to read a lot more papers to get up to date with programming languages.

One thing that bothers me occassionally is this: I don't think I know enough about programming language theory yet to talk with specialists about it. So there's an isolating feeling I get about reading early papers, because I think it's cool stuff, and yet it's probably so elementary that everyone else is so beyond it already.

But, despite all these being elementary, I still do want to write what I'm getting out of reading these papers, just in case I make conclusions that are absolutely wrong. If it's public, then there's still some chance that someone out there can correct me. *grin* So here goes...

A few of the critiques made in Wadler's paper are addressed in PLT Scheme. For example, pattern-matching does exist in a library. The sum Miranda code in the paper:

sum [] = 0
sum (x:xs) = x + sum xs

can be written in PLT Scheme as:

(require (lib "plt-match.ss"))
(define sum
  (match-lambda
   ((list) 0)
   ((list-rest x xs) (+ x (sum xs)))))

though this also brings up a point about syntax: the Miranda code does use an appealing syntax, whereas everything in Lisp is an s-expression. Syntax is also an issue, though I think Wadler discounts too much the role of macros in Lisp-like languages.

The points for a type discipline seem fair, and I suspect a proper use of MrFlow would catch the same kind of mistakes that a static type system would catch. (Though I don't know yet: I haven't played with MrFlow seriously.)


Wadler's term "free data types" goes over my head slightly. *grin* Concretely in terms of Scheme, I think he's trying to say that equal? only works on s-expressions, and that trying to do equal? on arbitrary compound data might not work because we're never sure what the choice of representation is.

Does PLT Scheme's structure and inspector support meet the requirements of free data type definition? It seems to me that:

;; a structure is either a Weight or a Mobile.
(define-struct Weight (n) (make-inspector))
(define-struct Mobile (left right) (make-inspector))

(define-struct Branch (length structure) (make-inspector))

could also be considered a way to define free data types, though I'm probably missing something subtle.

Anyway, better stop now and sleep.