hashcollision

Migration

2011-05-08T21:17:00.000-07:00

I'll be moving this blog to http://blog.hashcollision.org.

shimmer

2010-04-17T19:16:00.000-07:00

One of my favorite companies is trying to kill my active area of research and personal interest. When Apple engages to hurt children, when they enforce a discriminatory and irrational policy, then they've crossed a terrible line. I've listened to the counterarguments, but I can only conclude that what they're doing here is morally wrong.

The iPhone has lost its shimmer for me. Time for a new phone.

quilty

2008-07-22T17:46:00.000-07:00

I wonder if Nabokov would laugh.

I need to stop doing things that make me feel guilty.

decentralize

2008-06-01T13:34:00.000-07:00

I've been using git for my source code control, and I'm happy I switched to it. I found out recently that my hosting service was burning; apparently something electrical exploded, knocking out a few of webfaction's servers.

I noticed the problem only when I was trying to push my changes upstream from my machine back to the mothership.

Long pause, no motion.

No problem. I canceled the push, and just continued to work and commit changes to my local machine.

I remember back at my previous workplace how the knockout of our main svn server meant we got to take the day off because we couldn't get any work done. Of course, I'm not telling the whole story. Not only was that server knocked out, but the whole building in general: we had a power outtage for a few hours. So that somewhat undercuts the story a little; decentralizing our source code server still wouldn't have saved us on that day.

happy birthday

2008-01-10T20:29:00.001-08:00

I didn't realize that Don Knuth's birthday was today. Happy birthday Professor Knuth!

zelda

2007-11-25T14:04:00.000-08:00

I held my sword in front, and approached the village cautiously. I would have to slaughter the terrible Yook monster disguised in one of the hapless villagers's homes. I pushed the doors open, ready to hack and slash. To my shock, all of the villagers looked exactly the same!

And each had something to say about the other Anouki:

* FoFo said that Gumo was honest.
* Kumu said Mazo or Aroo was lying.
* Dobo said Mazo was honest.
* Gumo said Fofo or Aroo was lying.
* Aroo said Kumu was lying.
* Mazo said that he and Dobo were honest.

How dastardly! Only the Yook would lie to me. And I couldn't just kill them all and let God sort them out. I had to think about this. So I did what anyone in this circumstance would do: I pulled out Alloy.


abstract sig Boolean {}
one sig True, False extends Boolean {}

abstract sig Anouki {
    truthful: Boolean
}

one sig Fofo, Kumu, Dobo, Gumo, Aroo, Mazo extends Anouki {}

pred whoTellsTruth {
   Fofo.truthful = True implies Gumo.truthful=True
   Kumu.truthful = True implies ((Mazo.truthful=False) or 
                                                          (Aroo.truthful=False))
   Dobo.truthful = True implies Mazo.truthful=True
   Gumo.truthful = True implies ((Fofo.truthful=False) or
                                                          (Aroo.truthful=False))
   Aroo.truthful = True implies (Kumu.truthful=False)
   Mazo.truthful = True implies (Mazo.truthful=True and 
                                                         Dobo.truthful=True)
}

pred onlyOneIsLying {
    one a: Anouki | a.truthful=False
}

run {
    whoTellsTruth
    onlyOneIsLying
}

Ah ha! But as I was about to raise my gleaming blade against the trembling liar, doubt came to my mind: what if there were two of them out there? Or three, or four? I thought: perhaps I should plan this out more carefully before executing my righteous justice. And maybe I should rewrite the model a little more to make it more general: who knows how many villages of liars I might run across?


/* Anouki can be friendly or antagonistic to other Anouki */
sig Anouki {
   supports: set Anouki,
   denies: set Anouki
} {
   /* and it's nonsensical to be both supportive and antagonistic of
      the same Anouki. */
   no (supports & denies)
}

/* A village consists of folks who tell the truth, and symmetrically,
   those who lie.  And we will categorically make every Anouki a
   truthteller or a liar. */
one sig Village {
   truthtellers: set Anouki,
   liars: set Anouki
} {
   no truthtellers & liars
   Anouki = truthtellers + liars
}

fact truthiness {
   all a : Village.truthtellers {
      all a' : a.supports | a' in Village.truthtellers
      all a': a.denies | a' not in Village.truthtellers
   }
}

/* Here's what everyone says about each other */
pred hearsay {
   some disj fofo, kumu, dobo, gumo, aroo, mazo : Anouki {
      fofo.supports = gumo
      fofo.denies = none
      kumu.supports = none
      kumu.denies = mazo or kumu.denies = aroo
      dobo.supports = mazo
      dobo.denies = none
      gumo.supports = none
      gumo.denies = fofo or gumo.denies = aroo
      aroo.supports = none
      aroo.denies = kumu
      mazo.supports = mazo + dobo
      mazo.denies = none
      fofo + kumu +dobo + gumo + aroo + mazo = Anouki
   }
}

pred oneLiar {
    hearsay and #Village.liars = 1
}

pred twoLiars {
   hearsay and #Village.liars = 2
}

run oneLiar for 6
run twoLiars for 6

Hours passed as I played out different scenarios. By this time, the Yook had already run away, but I had a model I was happy with.

consistency

2007-10-02T05:59:00.000-07:00

There's so much work that I have to do, and I've realized that one of my personal failings is not necessarily the understanding of hard stuff. Rather, it's getting the easy stuff even started.

It's a main point of Better: performance isn't about the shiny tools: it is more about the "gruntwork". It's the mundane task of being consistent, of staying on target, with which I struggle and flounder about like a floppy fish. My failure to do better isn't for lack of technical tools or skills: what I'm missing is consistency. Adults should have the firmness of mind to do something even if there are no immediate results. But my mind is still mushy and squishy. It has the consistency of oatmeal.

lists 1

2007-06-01T20:24:00.000-07:00

One of my research topics may involve Alloy in its role as a language for developing software. The problem is, I don't know Alloy quite well enough to use it in anger yet. That's something I must fix.

I need a nice, simple TODO list-keeping application, and so I'll try modeling it with Alloy. I'll try to verbalize my thinking in real-time, just to show that software isn't written in a vacuum, but is revised and re-revised.

These are the sort of things I'd want in a TODO list manager:

I should be able to make Items, and going the other way, deleting should be a snap.

I should be able to assign items to Tags.

I should be able to easily share my TODO lists with other people.

It's the last requirement that seems interesting to me; I'm not quite sure what I mean by this yet, but it involves some kind of security thing that I'll think about more in a moment. But let me first start modeling the relationships between the items in my imaginary system.


module lists
sig Person {
    tags: set Tag,
    items: set Item
}
sig Tag {}
sig Public, Private extends Tag {}
sig Item {
    tags: set Tag
}
run {}

I'm thinking of a design like delicious: a Person manages their TODO Items by tagging them. I'll keep two special tags called Public and Private, which I'll plan to use to restrict views by other people. Maybe it's premature to think about this...

Oh, I do want to say that the tags that are associated with a person are the ones used in that person's items: at the moment, my software model leaves that unconstrained. Let me fix that and revise the definition of a Person.


sig Person {
    tags: set Tag,
    items: set Item
} {
    tags = items.tags
}

At this point, I can ask Alloy: what would a possible situation of my model look like, by executing and showing a model. Here's one sample visualization that the tool's giving me.

Ok, but I haven't yet done anything about privacy yet; I need to model the items that a person might be looking at the moment. Let me extend a Person to also include the items that they're currently looking at, and also assign an "owner" to each Item.


module lists
sig Person {
    tags: set Tag,
    items: set Item,
    viewing: set Item
} {
    tags = items.tags
}
sig Tag {}
sig Public, Private extends Tag {}
sig Item {
    tags: set Tag,
    owner: one Person
}
run {}

Ok, so Items know who own them, so I should be able to write an expression capturing a notion of privacy. It might not be completely right, but let me see what things look like.


pred respectsPrivacy(p : Person) {
    all i : p.viewing | permit[p, i]
}
pred permit(p : Person, i : Item) {
    p = i.owner || Public in i.tags
}

Cool. Hmm, when I visualize this, though, the diagram's a little cluttered. And on second thought, I don't really need to have a Person keep track of their items's tags explicitely: that's easily computable as a function.


sig Person {
    items: set Item,
    viewing: set Item
}
// Returns the tags used by a Person
fun personalTags(p : Person) : set Tag {
    p.items.tags
}

Ok, let me visualize again, with a more interesting scenario.


pred show {
    all p : Person | respectsPrivacy[p]
    #Person > 1
    some p : Person | some i : Item {
        permit[p, i] && i.owner != p
    }
}
run show

Wait a minute, the diagram doesn't look right at all. Why does Person0 see Item0: she doesn't own it. Ooooh... I didn't tell my design that a Person's items must be owned by them. Ooops. I want to prevent panhandling.

Actually, let me just simplify the model so that this issue doesn't even happen. Just as I treated the personal tags as a function, I'll just make a personalItems function to compute whenever I need it.


// Returns a set of the items owned by this person.
fun personalItems(p : Person) : set Item {
    { i : Item | i.owner = p }
}

Here's my revised model so far.


module lists

sig Person {
    viewing: set Item
} 

// Returns a set of the items owned by this person.
fun personalItems(p : Person) : set Item {
    { i : Item | i.owner = p }
}

// Returns the tags used by a Person
fun personalTags(p : Person) : set Tag {
    p.personalItems.tags
}

sig Tag {}
sig Public, Private extends Tag {}

sig Item {
    tags: set Tag,
    owner: one Person
}

pred respectsPrivacy(p : Person) {
    all i : p.viewing | permit[p, i]
}

pred permit(p : Person, i : Item) {
    p = i.owner || Public in i.tags
}

pred show {
    all p : Person | respectsPrivacy[p]
    #Person > 1
    some p : Person | some i : Item {
        permit[p, i] && i.owner != p
    }
}

assert privateReallyMeansPrivate {
    all i : Item | all p : Person {
        (Private in i.tags && permit[p, i]) implies (i.owner = p)
    }
}

run show
check privateReallyMeansPrivate

I also added an assertion making sure that "private" really means private. There are plenty of counterexamples! It fails because my definition for permit() currently only cares about Public at the moment, and it's very easy for an Item to get tagged both with the Public and Private tag at once.

This is pretty cool stuff! To be able to talk about this software's design even without touching a single hashtable or SQL statement is really nice, and I'm already hitting core issues like handling privacy. But since the post is getting a bit long, I'll stop for now and continue this when I get back to Massachusetts tomorrow.

powers of two

2007-05-30T21:06:00.001-07:00

Knuth Check
Originally uploaded by dyoo

One of my friends complained that I didn't put any interesting images on my blog. So I promised him I'd post something with an image on it. I thought this photo would bring a smile to his face.

Gotta love powers of two.

turing

2007-05-15T21:41:00.000-07:00

The thing that struck me about the Turing Test, when I heard about it, was the crazy thought: how do I know that other people are anything like me? If we can't even judge faithfully between ourselves, how can we judge between humans and computers? For I can do nothing but observe reactions, the effect of my actions on others. I can't read people's minds: they could, for all I know, run entirely different mental software. Everyone is, in some sense, a black box.

The act of empathy, then, is a little presumptuous and magical: I trust that we can share an understanding with each other, with the assumption that because I share a similar hardware architecture with you, that there's a very strong chance that I share the same kinds of thoughts and values too. I think that's why we put so much emphasis on physical bodies. If someone looks different, I may fear them: they don't look like me, and so they might be thinking in an entirely different way. We all know the dilemma of the Turing Test deep in our bones, and we cheat a little (or a lot) by using irrelevant physical similarities in our judgements of one another.

I suppose I could be silly and wry and conclude that this is why women are mysterious and terrifying to me.

But I think that there's something there that deserves more serious thinking.

aliasing renaming

2007-05-09T11:43:00.000-07:00

People are often particular about naming. Names still hold special power: we may rationalize that names don't matter, but there's something hardcoded in human beings about choosing the right name for a thing. It's a hard thing to fight.

Programmers are people too, and programmers also keep concerns (sometimes too much) about the right name for a thing. As a concrete example, the word lambda scares off a few people since it's a foreign word. We might like to be brief and be able to say:


    (def (make-adder x)
      (fn (y) (+ x y)))

where def and fn are really meant to behave like define and lambda, respectively. One nice thing about Scheme is that it's plastic enough to absorb a trivial change like this. Here's a small library for aliasing identifiers:


(module alias mzscheme
  ;; Practice writing macros that themselves generate macros.  
  
  (provide alias)
  
  ;; (alias old-keyword new-keyword)   SYNTAX
  ;; Creates a new syntax for new-keyword; any occurrence of new-keyword
  ;; is replaced with the old-keyword.
  (define-syntax (alias stx-1)
    (syntax-case stx-1 ()
      [(_1 orig new)
       (syntax/loc stx-1
         (define-syntax (new stx-2)
           (syntax-case stx-2 ()
             [_2
              (identifier? stx-2)
              (syntax/loc stx-2
                orig)]
             [(_2 e (... ...))
              (syntax/loc stx-2
                (orig e (... ...)))])))])))

Once we have a tool like this, then we can test it out:


(module test-alias mzscheme
  (require "alias.ss")
  (alias lambda fn)
  (alias define def)
  
  (def (make-adder x)
    (fn (y) (+ x y))))

That being said, the above example is a silly thing to do. Even in competent hands, this is easy to abuse; in the wrong hands, one can end up with something that belongs to an obfuscation contest.


> (alias alias a)
> (a define d)
> (a if i)
> (d (f x) (i (= x 0) 1 (* x (f (- x 1)))))
> (f 3)
6

Communication between people means that we "come to terms", and the inherent abuse here is to turn the language into something that no one else can read. In PLT Scheme's case, the above is especially bad because there's already an established mechanism for controlled renaming of identifiers as part of PLT Scheme's module system.


(module test-alias mzscheme
  (require (rename mzscheme fn lambda)
           (rename mzscheme def define))
  
  (def (make-adder x) (fn (y) (+ x y))))

Still, I thought the macro definition was cute (even if it's silly), and it's one of the more direct applications of a "macro-generating macro" that I've seen. But maybe this is all just syntax, futzing with words, distracting us from the real work on nailing down the semantics of our thoughts.

logical

2007-05-02T13:05:00.000-07:00

I didn't get this so strongly before, but there's a correspondence between the language and structures of first-order logic, and the signatures and units of PLT Scheme (as well as the signatures and structures of ML). I guess the analogy is something like: "language::signature as structure::unit."

As a concrete example, a first-order language might just have equality (=), and a 2-arity P relation. Once we have a language, we can start writing statements in that language. Here are two statements using the language:

for all x, y, z: P(x, y) and P(x, z) implies y = z

for all x: there exists y: P(x, y)

These two sentences, taken together, are trying to say "P must be a relation that represents a total function". These sentences don't have a true or false value without being evaluated in the context of some structure. A structure tells us what domain of thingies (the universe) we're iterating over when we say "for all" or "there exists", and also provides a concrete definition for the relations of the language.

There are some structures that might satisfy this, and other structures that don't. Structures that satisfy the sentences we care about are called "models". One example of such a model for those two sentences might be the natural numbers (0, 1, 2, ...), where the interpretation of P is:

P(x, y) if and only if y = square(x)

But an example of a similar structure that wouldn't fit the above conditions would be natural numbers under a P that's not a function relation, like:

P(x, y) if and only if x < y

and so we'd say that this structure isn't a model of those sentences.

Programmers have an intuitive idea about this: it's similar to the distinction between "interface" and "implementation": the language provides the interface, and the structures provide implementations for that language. And when we have an interface, we usually have some implicit idea of how that interface should behave; if we have an interface called Stack, we have an expectation about what it should do. We can make those assumptions explicit by writing contracts or predicates with that interface: the things that satisfy our expectations are good implementations.

Again, to make this concrete, when we're programming with signatures and units, we first have to specify the things we're going to be fiddling with. For example, a signature like:


  ;; A function^ model consists of a universe of elements,
  ;; and a 2-place predicate P between elements.
  (define-signature function^ (universe
                               P))

gives us a language for talking and using units that implement this signature. For example, to build a unit where P is the squaring relation, we can do this:


  (define-unit squaring@
    (import)
    (export function^)
    (define universe (list 0 1 2 3 4 '>4))
    (define (P x y)
      (cond 
        [(equal? x '>4)
         (equal? y '>4)]
        [(> (* x x) 4)
         (equal? y '>4)]
        [else
         (equal? y (* x x))])))

(I'm defining the P function a bit peculiarly since I want the universe of elements to be finite.)

But again, not all implementations of the function^ signature will do the right thing. Here's a structure that doesn't satisfy the intent of the function^ signature.


  (define-unit less-than@
    (import)
    (export function^)
    (define universe '(1 2 3))
    (define (P x y)
      (< x y)))

How do we capture intent? We want to be able to catch implementations that don't do what we expect, and one way is to write code to exercise the units. Here's one example:


  ;; function-model?: function@ -> boolean
  ;; Checks to see if the given unit satisfies what we
  ;; expect out of functions, that their domain is total
  ;; and that each element of the domain maps to
  ;; just one element of the range.
  ;;
  ;; In first-order logic:
  ;;    (for all x, y, z: P(x, y) and P(x, z) implies y = z)
  ;;    and
  ;;    (for all x: there exists y: P(x, y))
  (define (function-model? model@)
    (local ((define-unit-binding a-model@
              model@ (import) (export function^))
            
            (define-unit function-tester@
              (import function^)
              (export)
              (and (for-all* (lambda (x y z)
                               (implies? (and (P x y) (P x z))
                                         (equal? y z)))
                             universe universe universe)
                   (for-all* (lambda (x)
                               (exists? (lambda (y) (P x y))
                                        universe))
                             universe))))
      (invoke-unit
       (compound-unit/infer
        (import)
        (export)
        (link a-model@ function-tester@)))))

(There are a few definitions I've left out here; see logic-practice.ss for the other definitions.)

Once we have this, we can now check to see if squaring@ and less-than@ satisfy the function-model? predicate.


> (function-model? squaring@)
#t
> (function-model? less-than@)
#f

spring

2007-04-30T22:20:00.000-07:00

It finally feels like spring has arrived here in Worcester. The flowers are blooming from the trees, in great white poofy and pink blossoms. After my first winter here on the East Coast, it feels glorious to stand outside and just soak in the sun.

This semester is finally over. I still feel a little unsatisifed with my performance in Dan's logic class; the simplest things trip me up. Ever time I do a logic session, I come out feeling mentally pummeled. Brain squish just like grape! But not because the material's necessarily difficult, but just that I come in with so much mental confusion.

For example, I got confused with the concepts of Skolem Hull and the Herbrand universe, which are different concepts. The Skolem Hull submodel only contains points that are interpretations of all the nameable elements of a language. A Herbrand universe, on the other hand, is a set containing only the nameable terms themselves. A hash collision.

We talked about models that include "junk" (elements that can't be named by terms) and "confusion" (named terms that go to the same element). It's funny, though, how the terms of logic are adopted by other subcultures, things like "compactness" and the "no junk, no confusion" properties, and in ways that are totally different from the definitions in mathematical logic.

I should probably spend a few more days in the sun and try to weed out the junk and confusion in myself, the ill-formed and redundant thoughts.

function of the day: fold

2007-04-20T08:13:00.000-07:00

The fold function does very much what the name implies: it's meant to fold ingredients into a big mixing bowl, of course. Here's a definition:


;; fold: (ingredient bowl -> bowl) bowl (listof ingredient) -> bowl
;; Folds in a list of ingredients into a bowl with a folding-action.
(define (fold folding-action a-bowl ingredients)
  (cond
    [(empty? ingredients) a-bowl]
    [else
     (local ((define mixed-bowl (folding-action
                                 (first ingredients)
                                 a-bowl)))
       (fold folding-action mixed-bowl (rest ingredients)))]))

FOLD here adds an ingredient at a time, using the folding-action to mix in every ingredient thoroughly into our large bowl. Once we have this incorporating function, we can roll up our sleeves and whisk some pancake batter:


;; make-pancake-batter: -> string
;; Example of FOLD to make pancake batter.
(define (make-pancake-batter)
  (local ((define (whisk an-ingredient a-bowl)
            (string-append a-bowl an-ingredient))
          
          (define pancake-ingredients '("flour" "sugar" "eggs" "milk"))
          
          (define empty-bowl ""))
    (fold whisk empty-bowl pancake-ingredients)))

Oh! I forgot the baking powder, so those pancakes will be a little stiff. Oh well.

Of course, we might even want to whisk in a slightly different way:


  (local
      ((define (whisk an-ingredient a-bowl)
         (cond [(string=? an-ingredient "eggs")
                (string-append a-bowl "egg-white-only")]
               [else
                (string-append a-bowl an-ingredient)])))
    (fold whisk "" '("flour" "eggs" "cabbage")))

Now we've got the basics of an okonomiyaki, I suppose.

We might even be silly enough to mix things that aren't even food!


> (fold + 0 '(1 2 3 4 5))
15

but this seems like a boring example compared to whisking.

Folding is popular, but for some reason it goes by different names by different programming camps. Python programmers call it REDUCE, and Ruby programmers call it INJECT. I don't know about these names, though: I think they sound a little bit aggressive for my taste. As for me, I like the homeliness of "fold": it reminds me of the kitchen.

death and taxes

2007-04-17T20:55:00.000-07:00

I can't help feeling haunted about the deaths in yesterday's shooting. The shooting itself makes no sense to me.

I can appreciate that people are trying to find meaning in the murderer's actions, trying to blame video games, or psychotic drugs, or jealousy, or divine retribution. It can't all be random, can it?

I suppose there's a story about the murderer that remains to be told, the motives and the exposure of lurid, petty details. Still, he is meaningless to me.

I do see clear meaning in the actions of people like Liviu Librescu. How gloriously different are the saints. I'd rather think about Professor Librescu and the others like him, who faced death with courage, teaching one final lesson: "Love is stronger than death." Another one of those lessons that I'm trying to believe.

stick a fork() in it

2007-04-15T16:23:00.001-07:00

Sometimes I really really dislike C for its low-levelness.

Here's one concrete example why. Predict the output of the following program:


#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>

int main(int argc, char** argv) {
  printf("hello world\n");
  if (fork() == 0) {
    printf("child\n");
  } else {
    printf("parent\n");
  }
  return 0;
}

with the following:


dyoo@dyoo-desktop:~/work/net-2$ gcc -Wall test-fork.c
dyoo@dyoo-desktop:~/work/net-2$ ./a.out
[predict your output here #1]
dyoo@dyoo-desktop:~/work/net-2$ ./a.out | cat
[predict your output here #2]

Yes; I was surprised too, but #1 and #2 can produce different output.

At least, this is what I see:


dyoo@dyoo-desktop:~/work/net-2$ ./a.out
hello world
child
parent
dyoo@dyoo-desktop:~/work/net-2$ ./a.out | cat
hello world
child
hello world
parent

The bug here is the interaction between the low-level fork() and the way that buffered output works in C. In the second case, since I'm piping through cat, there's more output buffering going on. The first printf() is buffered and not immediately printed but rather stored somewhere. The fork() duplicates the process. So when both the child and parent processes close, they flush their respective buffers... and we see this unusual output.

Some man pages do talk about this, like the one from SGI IRIX. Linux's man pages, not so much. Ah well.

cyberdyne

2007-04-12T21:39:00.000-07:00

I went to the NEPLS conference at Tufts University on Wednesday. It was a lot of fun; I got to hear programming language theory talks and meet with other people interested in the same sort of crazy things that pull my attention. I did like Dave's talk: the idea of collapsing idempotent type checks to preserve space seemed perfectly reasonable. I wonder if any of that will trickle back into PLT's contract system.

The last presentation, on Spatial Computing, was especially fascinating. At a first glance, it seemed ridiculous, and the scope of the project so breathtakingly absurd. I clamped my hands over my mouth to muffle my giggles. But as the speaker presented more and more, the whimsical thought came into to me: maybe this is how Skynet begins.

I hope that I too will someday build something that brings both laughter and pondering thoughts. And I'll also keep in mind to try avoiding the development of systems that might lead to the creation of bloodthirsty androids.

birthday

2007-03-30T14:47:00.000-07:00

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

2007-03-29T20:28:00.000-07:00

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

2007-03-01T18:56:00.000-08:00

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

2007-02-08T22:49:00.000-08:00

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

2007-02-01T18:03:00.000-08:00

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

2007-02-01T10:45:00.000-08:00

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

2007-01-14T19:07:00.000-08:00

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

2006-12-28T17:54:00.000-08:00

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

2006-12-25T00:46:00.000-08:00

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

2006-12-17T00:20:00.000-08:00

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

2006-12-07T11:27:00.000-08:00

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

2006-12-05T22:01:00.000-08:00

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

2006-11-18T19:05:00.000-08:00

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

2006-11-02T10:22:00.000-08:00

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

2006-10-27T22:01:00.000-07:00

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

2006-10-16T11:49:00.000-07:00

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

2006-10-08T21:00:00.000-07:00

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

2006-09-18T20:19:00.000-07:00

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

2006-08-23T18:56:00.000-07:00

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

2006-08-15T12:36:00.000-07:00

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!

2006-06-28T19:08:00.000-07:00

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

2006-06-20T16:21:00.000-07:00

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

2006-06-15T22:27:00.000-07:00

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

2006-06-01T23:05:00.000-07:00

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

2006-05-24T11:29:00.000-07:00

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

2006-05-16T20:25:00.000-07:00

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

2006-04-25T13:21:00.000-07:00

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

2006-04-19T00:06:00.000-07:00

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

2006-02-05T15:22:00.001-08:00

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

2006-01-14T01:25:00.000-08:00

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.

starting with dtrace

2005-11-24T22:16:00.000-08:00

Notes about setting up dtrace user on a Solaris 10 system: by default, it appears that normal users don't have enough privileges to access dtrace. These privileges are:

* dtrace_user
* dtrace_proc
* dtrace_kernel

and these are described in the privileges(5) man page.

So how do we add these privileges to a user account? According to http://forum.sun.com/thread.jspa?threadID=22787&messageID=73761, it's a matter of editing /etc/user_attr with a set of default privileges.

One hacker's treasure is another hacker's junk

2005-11-18T16:55:00.000-08:00

Sun's patch 120289 recently change gnome-terminal's behavior on page up and page down keys. Some people are very happy about this:

http://ptribble.blogspot.com/2005/09/yay-gnome-terminal-fixed.html

Unfortunately, I'm not. *grin*

I do understand why the change was made --- usability matters! --- but for me, the existing behavior was perfectly usable and right: I want those keys to be sent to the terminal. I use those keys all the time in pine, and they don't work anymore.

I'm now trying to figure out how to work with gconf-editor to preserve the old behavior but haven't figured out where things need to change yet. Oh well.

Emacs keystroke of the day

2005-11-16T00:46:00.000-08:00

I learned two new Emacs keystrokes that will make Scheme coding that much less painful:

C-M-f: forward-sexp
C-M-b: backward-sexp

Testing, testing

2005-10-25T15:13:00.000-07:00

(define greeting (lambda () (printf "hello world!~%")))
(greeting)