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))))))

forgive

It's one thing to intone in a dull monotony: "Forgive those who trespass against us," where repetition drains the blood out of a revolutionary and crazy idea. It's quite another thing to try to put the spirit of forgiveness into real action. Serious forgiveness seems to me something superhuman, and I'm finding it hard to do.

Early Monday, right around 1am, I got taken by a pair of con artists who pretended they needed to make an emergency call outside. I let them use my cell, and when they handed the phone back, I didn't realize they'd yanked the battery and the SIM chip inside.

Still, I did get the physical phone back, and there wasn't really much damage, except one night of uneasy sleep and an afternoon buying cellphone components. I should say that I forgive the people who did this to me. A part of me tries doing so, but another part feels that it's a baldfaced lie, and I catch myself wanting something bad, something karmic to happen to the thieves.

But I think about it some more. Frankly, I got off easy: it could have been a lot more perilous, because the two thieves could have gone after much more than my cellphone. The guy had me in a bear hug at one point, pretending to be thankful. I couldn't get out of his grip. He could have squeezed me more tightly, and then I would have been in real trouble. So I am thankful and lucky not to have been crushed in this encounter.

If something this insignificant raises my ire, how hard it must be to forgive when people truly hurt each other! It just makes me wonder.

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.

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.