aliasing renaming

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

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

function of the day: fold

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.

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

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.

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.

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.

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.