Abstract Heresies

A bit more challenging

2012-01-19T09:11:00.000-08:00

In my previous post, I gave the puzzle of taking a pattern and generating code that matches it. The tricky part was making sure that the pattern is completely traversed at compile time. If the object to be tested matches the pattern, the pattern variables and their values were to be returned in an alist.

It would be better, however, to generate code where the pattern variables become bindings of Scheme variables. Instead of generating code that stuffs the values into an alist, like this code does at the highlighted points:

(make-matcher '((? one) and (? two))) =>

(lambda (object)
  (and (pair? object)
       (let ((left-submatch
              ((lambda (object) (list (cons 'one object))) (car object)))
             (right-submatch
              ((lambda (object)
                 (and (pair? object)
                      (let ((left-submatch
                             ((lambda (object)
                                (and (eqv? object 'and)
                                     '()))
                              (car object)))
                            (right-submatch
                             ((lambda (object)
                                (and (pair? object)
                                     (let ((left-submatch
                                            ((lambda (object)
                                               (list (cons 'two object)))
                                             (car object)))
                                           (right-submatch
                                            ((lambda (object)
                                               (and (eqv? object '())
                                                    '()))
                                             (cdr object))))
                                       (and left-submatch
                                            right-submatch
                                            (append left-submatch
                                                    right-submatch)))))
                              (cdr object))))
                        (and left-submatch
                             right-submatch
                             (append left-submatch right-submatch)))))
               (cdr object))))
         (and left-submatch
              right-submatch
              (append left-submatch right-submatch)))))

We'd generate something more like this:

(make-matcher '((? one) and (? two)) <user code goes here>) =>

(lambda (object)
  (and (pair? object)
       (let ((one (car object))
             (tail1 (cdr object)))
         (and (pair? tail1)
              (eq? (car tail1) 'and)
              (let ((tail2 (cdr tail1)))
                (and (pair? tail2)
                     (let ((two (car tail2)))
                       (and (null? (cdr tail2))
                            <user code goes here>))))))))

This is more challenging for two reasons. First, we need to ensure that the pattern variable names become bound in a scope that encloses the user's code so that free references to pattern variables are correctly captured. In addition, we need to ensure that other “helper” bindings, like tail1 and tail2 do not capture free references by accident. (That is to say, watch your macro hygiene.) Second, you have to be sure that subpattern bindings are visible to the entire body of the user code. This will throw a monkey wrench into the simple recursive solution.

Slightly trickier

2012-01-15T11:38:00.000-08:00

In my previous post, I gave a small pattern matching problem. It is easily solved by recursively descending the pattern and the object to match. This is analogous to interpreting the pattern because you walk the pattern each time you want to try to match an object.

If the pattern is constant, though, you can walk the pattern once and generate code that can match against an object much more quickly:

(define my-matcher
  (eval (make-matcher '(a (? var1) (nested (c (? var2)))))
        user-initial-environment))

(my-matcher '(a b (nested (c d)))) => ((var1 . b) (var2 . d))

I'd rate this as an intermediate puzzle. It isn't very different from the previous one, but you have to pay more attention to the phase of evaluation. As a hint, here are a pair of possible matchers:

(make-matcher '((? car) . (? cdr))) =>

(lambda (object)
  (and (pair? object)
       (let ((p1 ((lambda (object) (list (cons 'car object))) (car object)))
             (p2 ((lambda (object) (list (cons 'cdr object))) (cdr object))))
         (and p1
              p2
              (append p1 p2)))))

(make-matcher '((? one) and (? two))) =>

(lambda (object)
  (and (pair? object)
       (let ((left-submatch
              ((lambda (object) (list (cons 'one object))) (car object)))
             (right-submatch
              ((lambda (object)
                 (and (pair? object)
                      (let ((left-submatch
                             ((lambda (object)
                                (and (eqv? object 'and)
                                     '()))
                              (car object)))
                            (right-submatch
                             ((lambda (object)
                                (and (pair? object)
                                     (let ((left-submatch
                                            ((lambda (object)
                                               (list (cons 'two object)))
                                             (car object)))
                                           (right-submatch
                                            ((lambda (object)
                                               (and (eqv? object '())
                                                    '()))
                                             (cdr object))))
                                       (and left-submatch
                                            right-submatch
                                            (append left-submatch
                                                    right-submatch)))))
                              (cdr object))))
                        (and left-submatch
                             right-submatch
                             (append left-submatch right-submatch)))))
               (cdr object))))
         (and left-submatch
              right-submatch
              (append left-submatch right-submatch)))))

Astute readers will notice that this latter matcher is doing more work than necessary. If the match against part of the pattern fails, it still attempts to match the rest of the pattern. It only notices just before assembling the final result. Also, using append to assemble the sub-matches is a terrible waste.

A small puzzle

2012-01-13T08:53:00.000-08:00

Here's a quick little puzzle that isn't too hard.

A pattern is:

A symbol, number, boolean, or null (an atom).

A pattern variable, which is a two element list where the first element is the symbol ? and the second is a symbolic (a symbol) name.

;;   Examples:
;;     (pattern-variable? '(? foo))                      => #t
;;     (pattern-variable? '(? another-pattern-variable)) => #t
;;
;;     (pattern-variable? '(not a (pattern variable)))   => #f
;;     (pattern-variable? '(?))                          => #f
;;     (pattern-variable? '(foo ?))                      => #f
;;     (pattern-variable? '(? foo . bar))                => #f
;;     (pattern-variable? '(? foo quux))                 => #f

(define (pattern-variable? thing)
  (and (pair? thing)
       (eq? (car thing) '?)
       (pair? (cdr thing))
       (symbol? (cadr thing))
       (null? (cddr thing))))

A pair (a cons) of two patterns.

Write a program that given a pattern and some list structure (an object composed of pairs, numbers, symbols, nulls, etc.) returns an association list (an alist) of the pattern variable names and the associated matching elements, or #F if the pattern does not match.

;;  Examples:
;;   (pmatch '(foo (? pvar1) (? pvar2) bar) '(foo 33 #f bar))
;;      => ((pvar2 . #f) (pvar1 . 33))
;;
;;   (pmatch '(foo (? pvar) bar) '(quux 33 bar))
;;      => #f
;;
;;   (pmatch '(a (? var1) (nested (c (? var2)))) '(a b (nested (c d))))
;;      => ((var2 . d) (var1 . b))
;;
;;  Edge cases:
;;
;;   (pmatch '(a b c) '(a b c))
;;      => '()
;;
;;   (pmatch '(foo (? pvar1) (? pvar2) bar) '(foo 33 (xyzzy #f) bar))
;;      => ((pvar2 xyzzy #f) (pvar1 . 33))
;;
;;   (pmatch '(foo . (? pvar)) '(foo bar baz))
;;      => ((pvar bar baz))
;;
;;   (pmatch '((? ?) quux) '(foo quux))
;;      => ((? . foo))
;;
;;   (pmatch '(? ?) '(foo quux))
;;      => ((? foo quux))
;;
;;   (pmatch '(? ? ?) '(foo quux))
;;      => #f

Please be careful and obfuscate your solution if you want to post it.

2011-11-23T12:21:00.000-08:00

Imagine that we have a boatload of memory and we're nowhere near the limit. Suppose, too, that we allocate memory simply by bumping the free pointer. If you think about it, you can see that the age of the most recently allocated objects is simply the distance between the object's location and the current value of the free pointer. Little's Law tells us that mean age of a heap allocated object is equal to the mean size of the reachable heap, so it must be the case that the mean distance from the reachable objects to the free pointer is also equal to the mean size of the heap (blah, blah, satisfy boundary conditions, blah, in the limit, etc.)

A few weeks ago, someone asked about the improvement in locality that one may get from the garbage collector. The vast majority of objects don't survive even a single garbage collection, so the vast majority of objects are layed out in memory exactly where they were consed and cannot benefit from any improvement in locality. This is not to say that there is no effect at all, but that the effect doesn't apply to the vast majority of objects.

Someone also asked what the GC pauses were. With a large heap (131072 blocks), the total time for MIT/GNU Scheme compiling itself was 167.7 seconds runtime, 1.06 second GC time. This comes out to about 22 milliseconds per GC.

Little's Law and the weak generational hypothesis

2011-11-18T18:05:00.000-08:00

Theorem: The mean lifetime of a heap allocated object is equal to the mean amount of reachable storage.
Proof: This is Little's Law with λ=1.

This turns out to be a pretty handy theorem. Here's an example.

In a prior post, I mentioned that a prerequisite for effective garbage collection is that the amount of reachable storage must at all times be less than the amount of memory available for the heap. We apply Little's Law and get this: The mean lifetime of a heap allocated object must be less than the time it takes to exhaust the heap.

That naturally follows: in order for garbage collection to “work”, we need something to become garbage before we completely run out of memory. But Little's Law allows us to make a much stronger statement. The mean lifetime of all objects (where lifetime is measured in subsequent allocations), is, by Little's Law, equal to the mean size of reachable storage. The mean size of the reachable storage has to be less than the amount of memory available for the heap. Since the mean lifetime of an object must be small, and we have the occasional very long-lived object, it must be the case that the vast majority of objects have very short lifetimes. Or in other words,

Most allocated objects die young.

This statement is often called the weak generational hypothesis. It is usually presented as an empirical observation. By Little's Law, it is equivalent to saying that the size of the reachable objects is small, which is not a hypothesis, but a strong pre-condition of garbage collection.

Little's Law and Lisp

2011-11-16T18:28:00.000-08:00

We model the Lisp heap as a queuing system.

A “queuing system” consists of discrete objects we shall call “items” that “arrive” at some rate to the “system.” Within the system the items may form one or more queues and eventually receive “service” and exit.
-- Graves and Little in Building Intuition: Insights from Basic Operations Management Models and Principles, edited by D. Chhajed and T. J. Lowe, Springer Science+Business Media, LLC, New York, 2008

Our discrete objects are the objects returned by cons, make-vector, make-string, and the other primitive constructors. The heap is where these objects wait, and the objects “exit” the system when they become unreachable.
We can now apply Little's Law:

L=λW

We will assign λ, the average number of items arriving per unit time, to 1. In other words, we normalize time to be equal to the allocation rate. Little's Law simplifies to:

L/λ=W (when λ is 1)
L=W

We let L, average number of items in the queuing system, be the size of the heap in allocation units. W, the average waiting time in the system for an item, is therefore the mean lifetime of an object. Provided that we meet the necessary boundary conditions: The mean lifetime of a heap allocated object is equal to the mean size of the reachable heap.

We are measuring object lifetime in `allocations'. If desired, we could measure the allocation rate in units of time, and then we would get the object lifetime also in units of time. Instead, we are determining the average number of word allocations that occur before an object becomes unreachable.

The boundary conditions for Little's Law are quite lax. If the heap begins and ends empty we can satisfy them. The heap naturally starts empty, and when a program ends, we discard the heap, so we can pretend it is empty again. (This puts an upper limit on the lifetime of all objects.) As I noted in a previous post, the mean heap size for MIT/GNU Scheme compiling itself is about 300,000 words. Therefore, the mean object lifetime is 300,000 word allocations.

I will expand on this in the next post...

Little's Law

2011-11-15T16:22:00.000-08:00

In Chapter 5 of Building Intuition: Insights from Basic Operations Management Models and Principles, edited by D. Chhajed and T. J. Lowe, Springer Science+Business Media, LLC, New York, 2008, Steven Graves and John Little discuss Little's Law:

A “queuing system” consists of discrete objects we shall call “items” that “arrive” at some rate to the “system.” Within the system the items may form one or more queues and eventually receive “service” and exit.

Little's Law says that, under steady state conditions, the average number of items in a queuing system equals the average rate at which items arrive multiplied by the average time that an item spends in the system. Letting

L = average number of items in the queuing system,
W = average waiting time in the system for an item, and
λ = average number of items arriving per unit time, the law is

L=λW

Graves and Little give several examples, and I'll paraphrase one here.

Caroline is a wine buff. Her wine rack in the cellar holds 240 bottles. She seldom fills the rack to the top but sometimes after a good party the rack is empty. On average it seems to be about 2/3rds full. She buys, on average, about eight bottles per month. How long, on average, does a bottle languish in the cellar before being consumed?

Using Little's Law, we let L be the average number of bottles in the wine rack, 2/3×240=160. λ is the average number of items arriving per unit time, 12×8=96 bottles/year. Divide L by λ and we get W≅1.67 years per bottle.

(It seems to me that Little's Law is related to Stoke's Theorem. The size of the queue is the integral of the “flux” across the queue boundaries.)

more to come...

Another chart

2011-10-27T16:24:00.000-07:00

Here is a chart of the number of words in use after each garbage collection (for MIT/GNU Scheme compiling itself with a heap of 1935360 words):

This is the smallest heap that is big enough for the compilation to complete. The limiting factor seems to be the big spike on the left at about 0.9×10⁹. We obviously wouldn't want to run with the minimum size heap; 3935 garbage collections are needed and almost a third of the total time is spent in GC. But the more frequently you collect, the better resolution you get.

2011-10-26T08:20:00.000-07:00

Garbage collection gives us the illusion of nearly unlimited memory for temporary storage. To pull off this illusion, we must be able to satisfy every allocation request (at least up to the point where we throw up our hands and raise an “out of memory” condition). In other words, there must be free or unused memory available whenever we need some. Since the point of automatic memory management is to free the programmer from having to think about it, we expect to be able to allocate temporary storage at any time we wish during program execution.

A data structure can be considered “in use” if modifications to it can change the future behavior or result of a program. Since we cannot in general statically determine the future behavior, we compute the transitive closure of the data structures under the data access primitives. This is a superset of the data “in use”. That is, if you can't access the data, it cannot be “in use”.

In order for garbage collection to succeed as a storage management strategy, there must be at all times (anytime we want to allocate) some storage that is either unallocated or unreachable. The size of the heap must always exceed the size of the reachable data. Or we could say that the amount of reachable data must at all times be less than the size of the heap. (By ‘size of the heap’ I mean the total amount of storage both in use and free. For example, I could have a five megabyte heap, but only have 3 words in use.)

Any allocated data structure has but one of two ultimate fates: it remains reachable for the remainder of the run of the program or it becomes unreachable at some point (and we may re-use the storage). Assuming the heap starts empty, the size of reachable storage at any point in time is the difference between the total amount of all allocation and the total amount of all storage that has become unreachable up to that point. For example, if my program allocates sixty megabytes over its lifetime and it abandons fifty-nine megabytes, then the heap must contain the remaining megabyte.

We now consider the differential case, which is to say, the rates of allocation, collection, and heap growth or shrinkage. If the rate of allocation exceeds the rate of collection, the amount of storage in use in the heap must grow to meet the demand. Conversely, if the amount of reachable storage in the heap is decreasing, then we are abandoning storage at a faster rate than we are allocating it. But there are hard boundaries on the size of the heap. We can never have a negative amount of storage in use, and we have the requirement (see above) that the heap must be larger than the reachable storage at all times. The heap size is limited, so the rate of increase in reachable storage must be quite small over the long term if we are not to run out of heap.

The rate of storage allocation must be nearly equal to the rate of deallocation (or abandonment) almost all the time.

(This is only slightly different from the “steady-state” assumption that the rates are essentially equal. We're simply admitting the possibility that the reachable storage grows indefinitely and that the program would eventually crash if it doesn't finish first.)

2011-10-24T14:06:00.000-07:00

John McCarthy

1927 - 2011

Boring charts

2011-10-24T09:13:00.000-07:00

Here is a chart that shows the amount of free space remaining after each garbage collection (MIT/GNU Scheme compiling itself, heap size 1935360 words):

Compare that chart with this one which shows the amount of free space remaining after each GC with heaps of sizes 8388608, 16777216, 33554432, and 100663296 words. Note that the y axis is now displayed in log scale in order to get the wide variation in heap size on one chart.

As we move to larger and larger heap sizes, the proportion of memory that is freed after each GC increases. This makes sense because the program allocates memory in the same way regardless of how much heap is present (a program that adjusts its allocation profile in response to the heap size would look much, much different). When the heap is small, large allocations of temporary storage (like the one at about 8.5×10⁸) make a significant difference in the amount of free space, but when the heap is big, these differences virtually disappear.

It is almost disappointing that the detail is lost when we use larger heap sizes. The charts for the large heap sizes are essentially flat. At large heap sizes, the variations in temporary storage usage become insignificant. In other words, the number of garbage collections becomes less dependent upon the moment by moment allocation of the program being run and approaches the simple limit of the heap size divided by the total allocation.

Scheming and plotting

2011-10-21T11:43:00.000-07:00

Another interesting thing to plot is the amount of space that remains in use after the garbage collector runs. This is simply the total size of the heap minus the amount the collector frees (on average). For example, if we start MIT/GNU Scheme with --heap 4096, we'll get a heap of (* 4096 1024) = 4194304 words. With this size heap, the garbage collector will run 1589 times and recycle 6204751035 words, or 3904815 words per collection. This gives us (- 4194304 3904815) = 289489 words that are still in use (averaging over all 1589 collections, of course). If we do this calculation for various heap sizes and plot the results, we get this:

Adjusting for extra collections

2011-10-16T10:13:00.000-07:00

Here is a log-log plot of garbage collection counts as function of heap size. The green line is the predicted number of collections assuming that the product of the heap size and GC count is constant. The red points are actual GC counts for MIT/GNU Scheme compiling itself.

As you can see, the line matches pretty good in the middle, but not so much at the ends. It took me a while, but I figured out that the discrepancy at the lower right of the curve (where the heap size is very large and the number of collections quite small) can be attributed to a few extra garbage collections that are triggered for the purposes of compaction. If we take these into account, our graph looks more like this:

That takes care of the lower end, but it is the discrepancy at the upper end of the curve (smaller memory and more frequent GC) that is more interesting.

Dividing the total amount of memory used by the size of the heap gives us a pretty good estimate of the number of garbage collections provided that each garbage collection frees the entire heap. This is generally not the case in a real program. We should be dividing the total amount of memory used by the average of the amount of storage freed by the garbage collector. In this next chart, we adjust for both the extra collections and the space in use that cannot be collected.

In this chart, we can see the effect of not reclaiming 100% of the storage on each collection. When the heap size is small, the memory that survives garbage collection becomes a larger fraction of that heap. This causes the GC count to increase faster than it would if it could free all the storage. There is a vertical asymptote to the line. This is where the heap size is equal to the averaged amount of storage retained at each GC. Basically, when the heap is only a little larger than the amount of storage retained, you have to do a lot of extra collection. This next chart is simply a close-up of the previous chart showing the divergence better.

It is interesting to see that retaining a modest amount of storage (empirically, it is about 400K words) can have a noticeable effect even when the heap is tens of times larger. (Remember, the vertical scale is logarithmic, so differences that appear small are actually quite a bit larger.)

If it is possible to use a heap ten, twenty, fifty, or even a hundred times larger than the averaged amount of storage retained, then we'll be beyond the worst part of the curve and down in the linear region. Another way to state this is that you want the amount of storage retained at each GC to be only a few percent of the entire heap.

Demystified

2011-10-13T10:59:00.000-07:00

I discovered why the total amount of memory used does not seem approximately constant across the different heap sizes. I had forgotten to take into account that a garbage collection cycle can be run for reasons other than reclaiming storage. In particular, it can be run as part of a compaction phase that precedes dumping a binary object or moving an object out of the collected heap into “pure” storage. These are not particularly interesting operations; they contribute little to the total resource usage or total time. They just cause an overestimate of the amount of storage used in very large heaps. I could correct for this, but I'm far more interested in what happens on the other end of the curve when you have a relatively small heap. More to come.

Confusing

2011-10-06T08:23:00.000-07:00

I found some of the data in my GC timings to be a little confusing. I can understand how different runs of the compiler might have different space usages even when compiling the same thing (things like timestamps are going to change), but the variation is too large to explain away like this. I think the problem is that by instrumenting the code to measure the timings I have inadvertently changed the behavior of the code beyond simply collecting the data.

Some GC stats

2011-10-04T09:54:00.000-07:00

I invested some time making MIT/GNU Scheme compile itself with various sizes of heap. I did one set of runs with the variable compiler:preserve-data-structures? set to #f and another with it set to #t. The MIT/GNU Scheme compiler was written in a way that allows the garbage collector to reap the intermediate storage for the compiler after each phase of compilation. When compiler:preserve-data-structures? is set to #t, however, the intermediate data structures are retained until the next compilation. This should not change the total amount of storage used by the compiler, but it should have the effect of reducing the amount of storage recovered by a GC cycle. The number of GC cycles can be seen to be larger for the smaller heap sizes. When the heap is huge, the extra amount of storage in use has little effect on the GC count.

The Total Free column contains the sum of the memory freed after each GC totaled for the entire compilation.

Memory Size		Discard Data Structures		Preserve Data Structures
(blocks)	(words)	GC Count	Total Free	GC Count	Total Free
1890	1935360	3935	6213003931	-	-
1900	1945600	3882	6211940217	-	-
1920	1966080	3818	6213153480	-	-
2048	2097152	3502	6210260535	-	-
3072	3145728	2178	6205257571	-	-
4096	4194304	1589	6207697668	1626	6200942665
5000	5120000	1283	6206081325	1303	6198903924
6144	6291456	1033	6210675904	1043	6205324016
8192	8388608	766	6212253195	771	6207156928
16384	16777216	377	6222514645	379	6233468540
32768	33554432	188	6257358354	188	6244416384
40000	40960000	154	6266232939	154	6257300338
50000	51200000	124	6316240152	124	6311996423
65536	67108864	94	6283277196	94	6276744843
98304	100663296	63	6324424897	63	6320187112
131072	134217728	48	6430202774	48	6426705701
262144	268435456	25	6704242312	25	6702940561

Some of my thoughts about this (with graphs) in a bit. (It becomes very interesting when the data seriously disagrees with the math, but it is tedious to collect enough data to either support or refute the mathematical model.)

Knee surgery

2011-09-23T17:53:00.000-07:00

As an anonymous person pointed out, the knee in the curve is an illusion. Here is the same chart displayed with varying scales for the x and y axes:

You can see that the position of the “knee” depends upon the scale of the X and Y axes.

The whole chart is a problem. Not only does it show a knee, but the rest of the chart has the data all squished up along either the X or Y axis. It is going to be hard to compare different charts if they all look like this. I want the whole chart to be scale invariant.

(Can you guess where this is going?)

The curved line in the chart represents the solution to x × y = 6100000. This line appears to come pretty close to the actual garbage collection count when you use MIT/GNU Scheme to compile itself. Since the product is a constant, we have a hyperbolic curve. To transform this into something more reasonable, we want to take the logarithm of the curve in both the X and Y direction. This will change our line from x × y = constant to x + y = constant (because logarithms transform multiplication into addition).

This chart is certainly more interesting! First, notice how the measured garbage collection counts fall in almost a straight line. The curve that approximates the count is a straight line, and you can see that the actual garbage collection count deviates from this line slightly at the ends. Second, notice that the lines 10 × x, x, and x/10 become parallel. This is convenient, too. Finally, notice that the knee is gone. This sort of chart won't fool us with a fake knee.

Now that we have something of an interesting baseline, it would be instructive to plot other processes that generate garbage and see how they look. (upcoming post)

A bit of a problem

2011-09-23T13:59:00.000-07:00

Once again, here is a plot of the actual garbage collection counts as a function of heap size:

and we mention that we want to be “beyond the knee” in the curve. So where is that “knee”?

The green line is the plot of f(x) = 6100000/x, or, to put it another way, the plot of x × y = 6100000. The knee in the curve ought to be where x = y = √6100000 ≈ 2470. But look at the chart! Just by eyeballing it, we can see that 2470 is nowhere near what anyone would call the knee.

More on GC

2011-09-22T13:14:00.000-07:00

I had been thinking of improving the garbage collector in MIT/GNU Scheme. I carefully measured the current GC performance so I could quantify any improvements. This uncovered a bug (see earlier post), but it also uncovered something more interesting. Here is a plot of the number of garbage collections as a function of heap size for the problem of compiling all the Scheme code in MIT/GNU Scheme:

This graph looks an awful lot like the graph of minimal collections. In fact, if we plot the minimum number of garbage collections necessary for about 6100000 blocks, we get this:

That appears to be a really good fit. This isn't too surprising, because a GC that collects only when it is almost out of memory ought not to be doing much more work than the minimum necessary.

What makes this interesting is this: We can clearly see the “knee” of the curve, and we have enough memory to be “well beyond the knee” when we compile all of Scheme. This means that the total number of garbage collections will be quite low. If the garbage collector is fast enough, the total GC time will also be quite low. For example, when given 40000 blocks of memory, MIT/GNU Scheme will compile itself in about 3 minutes of which only 2.6 seconds total are spent in garbage collection. And as I noted previously, with sufficient memory, there need not be any garbage collection at all.

Notice that the details of the collector are unimportant. MIT/GNU Scheme uses a variation of the Minsky-Fenichel-Yochelson-Cheney-Arnborg algorithm, but it could just as easily use a mark-sweep collector. The point is that when you are only doing a few dozen collections, it doesn't matter much what algorithm you use because changing the algorithm will make little impact on the total run time. (Suppose I had the world's greatest garbage collector that just blows away the current one. Then I could reduce the total time from 182.6 seconds to exactly 180 seconds. This is less than a 5% improvement and not worth pursuing.) (A reference count GC, however, would be a problem because it traces garbage rather than live storage.)

So my original plan is pointless. There is no advantage to improving the garbage collector if it doesn't take more than a small amount of time, and it looks like you can achieve this by simply throwing memory at the process. So long as you have sufficient memory, you can make the cost of a collection be close to (or even equal to) zero.

At least it looks that way...

Thoughts about GC

2011-09-19T17:33:00.000-07:00

Suppose I have a program that, when run, allocates a total of 10 GiB (10×2³⁰ bytes). If it happens that I have more than 10 GiB of heap, then I don't need to worry about running out. If my heap is smaller than 10 GiB, I'm going to have a problem.

It is often possible to re-use storage by overwriting the previously written information. If the result computed by a program (including the side effects as part of the ‘result’) is completely invariant with respect to the value of a location in memory, then that memory location could be re-used. Depending upon the program and the runtime system, re-use can be the responsibility of the programmer, or there can be an automatic means of storage management (e.g. a garbage collector). Regardless of how re-usable storage is identified and made available to the program, we can use the pigeonhole principle to determine the minimum number of times that we must re-use some part of memory. For example, if my program uses 10×2³⁰ and I have 10×2³⁰−1 bytes of heap, then at least one byte somewhere will have to be re-used.

So let us suppose that our program which allocates 10 GiB is to be run with a 2 GiB heap and our runtime system provides a garbage collector so we don't have to manage our storage manually. Suppose further that our garbage collector is not continuous, but has some sort of identifiable ‘cycle’ during which it locates re-usable memory. On each cycle the garbage collector can reclaim at most 2 GiB, so we know the runtime system must perform a minimum of at least five garbage collection cycles. It may perform many, many more than five, but it cannot perform fewer because it would have to recycle more than 100% of the heap at some point.

Another way to state this is that the number of garbage collections times the size of the heap must be equal to or greater than the total amount of storage allocated by a program. Here is a graph that shows the minimum number of collections needed for a program that allocates 50 bytes of storage.

The discrete jumps in the graph are because we aren't considering partial allocations (less than 1 byte). When working with realistic heap sizes, we can approximate this graph by dividing the total allocation by the heap size. The green line in this chart plots 50/x.

More to come...

Measuring GC times

2011-08-30T13:13:00.000-07:00

MIT/GNU Scheme has a command line parameter, --heap, that allows one to specify the size of heap in 1024 word blocks. On a 32-bit machine, the heap size is limited because MIT/GNU Scheme stores the type tag in the upper bits of the word. On a 64-bit machine the word size is wider, so it is possible to specify extremely large heaps without worrying that the address will overflow into the type tag.

For kicks, I decided to vary the value of the heap size and see what effect that had on the task of MIT/GNU Scheme compiling itself.

Heap	GC Count	Cumulative GC Time in ms
6000	1056	25800
8192 (64 MiB)	764	19120
10000	623	17910
16384 (128 MiB)	377	10980
32768 (256 MiB)	188	7350
50000	124	5560
65536 (512 MiB)	94	5000
100000	63	4410
131072 (1 GiB)	48	3910
150000	42	4160
200000	32	3800
250000	26	3560
262144 (2 GiB)	25	3050
300000	22	3360
350000	19	3260
393216 (3 GiB)	18	2740

Collecting this data was tedious, so I spent a fair amount of time thinking about a model that could explain the results. At first glance, everything looks about right: the more memory, the fewer GCs and the less total time is spent garbage collecting. The problem is that the curve predicted by my model doesn't fit the empirical data at all. Of course this means that my model is either wrong or incomplete.

I have since figured out the problem, but I thought I'd let people puzzle over it themselves for a bit, first.

50 years ago — April 28, 1961

2011-04-28T09:42:00.000-07:00

This is an excerpt from the forth coming LISP 1.5 Programmer's Manual.

Provision is made in LISP 1.5 for allocating blocks of storage for data. The data may consist of list structure or data words. Arrays may have up to three indicies.

To declare an array, us the function array. Its argument is a list of arrays to be declared. Each one must be for list structure or non-list structure.

Suppose ALPHA is to be a 10 x 10 array of list structure and BETA a 5 x 5 x 5 array of non-list structure. The array function is
ARRAY ((
     (ALPHA (10,10) LIST)
     (BETA (5,5,5) NONLIST)    ))

To find the value of B_3,4,2: (BETA 3,4,2) or (BETA I J K) with a pair list.

To set ALPHA_3,4 to "YES": (ALPHA (QUOTE SET) (QUOTE YES) 3 4)

Array uses marginal indexing for maximum speed. The total number of words used by an array whose size is D₁ x D₂ x D₃ is 4 + D₁ + D₁D₂ + D₁D₂D₃. If the array is 2 dimensional, D₁ = 1. If the array is 1 dimensional, D₁ and D₂ = 1.

To save space, specify the dimensions in increasing order.

ALPHA (3,4,5) takes less words than ALPHA (5,3,4).

Compatability of LISP 1 and LISP 1.5.

EVALQUOTE has two arguments while APPLY has three. To change a LISP 1 program for LISP 1.5 simply eliminate the p-list if it is null. If the p-list is needed, then the function apply is available in LISP 1.5,

Arithmetic in LISP 1.5 is new, improved, and generally incompatible with LISP 1.

LISP 1.5 has many extra features. There [sic, these] are being written up for the new LISP 1 Programmer's Manual. Until it comes, check in Room 26-265.

— Michael Levin

Artificial Intelligence Project

RLE and MIT Computation Center Memo 24

Arithmetic in Lisp 1.5

Fun with scammers

2011-04-22T15:25:00.000-07:00

No Scheme or Lisp content today. I was amusing myself for a while with this email exchange. The strings of digits are courtesy www.random.org. I even found a site that creates fake Western Union receipts.

Hello,

I'm writing this with tears in my eyes,my family and I came down here to Edinburgh Scotland for a short vacation unfortunately we were mugged at the park of the hotel where we stayed,all cash,credit card and cell were all stolen from us but luckily for us we still have our passports with us.

We've been to the embassy and the Police here but they're not helping issues at all and our flight leaves in few hrs from now but we're having problems settling the hotel bills and the hotel manager won't let us leave until we settle the bills the amount needed now is just $2,700..I am so confused right now and thank God i wasn't injured because I complied immediately. Waiting to hear from you. Robert

I sent this message to Bob's other account:

I just got this message that supposedly came from you. It is plausible enough that your friends might fall for it! You should email your friends and assure them that you are OK and to NOT SEND MONEY
~jrm

Thanks for checking on me, well the message is from me and not a hoax. I'm presently stuck in UK and really in a bad situation.....I have been talking to the lazy embassy but it's taking them time process me help, and it's hard to get hold of a phone, that was why I had to send out email for help....I need a financial help with getting back home...all i need is $2,700.,but anything you could assist with now be helpful ..let me if can you have the money wire to me through western union

Thanks.

Robert

I'm glad to hear your email is ok, it would be terrible to be mugged and hacked. Where do you need it sent?
~jrm

Glad you replied back. I am full of panic now and the police only asked me to write a statement about the incident and directed me to the embassy,i have spoken to the Consulate here but they are not responding to the matter effectively,I really need your help to get myself out of this place. Well all i need now is just $2,700 but any amount you can afford will be appreciated, you can have it wired to my name via Western Union i'll have to show my passport as ID to pick it up here and i promise to pay you back as soon as i get back home.

Here's the info you need at western union location below

Name: Robert G

Address: 48 Princes Street, Edinburgh, Scotland

Kindly email me the transfer details as soon as you have it done.Please let me know if you are heading out to western union now.

Thanks

Robert

What's going on?

I was only able to wire $300 (I hit the limit on my ATM). I can send a lot more tomorrow, but will you have time to get it?
~jrm

Please Let me have the western union confirmation number # M.T.C.N, so i can be able to pick up the Money. I'm freaked out at the moment please keep me posted.

Robert.

Robert, did you receive the money? Are you still in trouble? Is there anything more I can do?

Thanks for your effort,Let me have the western union confirmation number # M.T.C.N. Awaiting for your reply.

Robert

I left him dangling on this one.

What's going on?

Robert .

My apologies, Robert, (I know you are in trouble, but I do have to sleep at times!) The MTCN is 2665592734

HOWEVER!!! IMPORTANT!!!!

I didn't want to broadcast that over email because it could be read by someone unscrupulous. So I added in your wife's birth date. Just subtract that out to get the real tracking number. I hope you can figure that out. Please let me know. If you want, I have an additional $500 I can send right away.

What's going on,I just got back from Western Union and i was told there was no record for the transaction,kindly check the receipt and get back to me with the correct confirmation #

Awaiting to reply.

Robert .

Trip number 1. I'm shocked it didn't work.

What?! Did you remember to subtract your wife's birth date from the number I gave you?

Omg!! I am full of panic now,Let me have the scanned receipt For Payment giving to you by the Western Union Agent.

Uh oh. I'm busted... maybe I can vamp a bit....

How can I do that? You know I don't have a scanner. I've got an idea! What's the phone number of the hotel that is giving you problems? I'll call the manager myself and put it on my credit card.

No reply. I was going to give up but it occurred to me to check for an on-line receipt generator (they have everything on line, don't they?) They do. I sent him a nice receipt.

Good news! I found a scanner. Please let me know if everything is ok.

Thanks for your help.. i just got the money but there seems to be a problem with the conversion rate, i noticed the money came out here in $300but all i need is $2,700 as i requested, don't know that the conversion is that low, please i will need your further assistance so i will be needing $2,400. Please let me know when you will be heading out to western union. Waiting to read from you.

Hmm, he read the receipt, but didn't make a Western Union run. I'll string him along a bit.

I'll have to go by the bank (again) to get an additional check. I should be able to do that after work, in a few hours. Hang in there! I'm very worried.

Ok,I will be waiting ,Do e-mail the full Western Union Transfer Details once you have it done.

Keep me posted.

Robert.

I'm trying to get the guy to go `off script'.

URGENT
Robert, I need to know if you want the money in US Dollars, GB Pounds, or Euros, and what the exchange rate is. Can you get back to me as soon as you can? I'm really sorry about this, hope you are surviving.

No reply. Better dangle some cash.

I sent some more money. Did you get it? Is everything all right?

OK...Can i have the full transfer details (MTCN) so i will be able to pick up the money. Waiting to read from you.

Thanks Robert.

The MTCN is 4677254413 Please let me know when you get it!

Are you there?

Robert, did you receive the money? Are you still in trouble? Is there anything more I can do?

Let me have the confirmation details # M.T.C.N. Awaiting for your urgent reply. Robert

Please do get back to me with the Western Union Control Number M.T.C.N# Please Keep me posted.

Robert

This guy just has a one-track mind. It seems impossible to get him `off script'.

Robert,
What is going on? Are you all right?

I just checked with Western Union and they say you haven't picked up either of the two wires that I sent! Are you having difficulty getting them?

The Western Union Control Number M.T.C.N # are these:
2665591653 --- amount $300
3207519347 --- amount $500

Please let me know if you have any problems retrieving the money.
~jrm

Are you kidding me or what,cause i was told at western union office the money you sent to me was not there. Please Let me know what's going on am freaked out here.

Robert.

Yes! Trip number 2. He's probably figured out I'm playing him, though. Let's goad him into one more trip. A bit of an insane rant to allay his suspicions and we'll sweeten the pot just a bit more...

I don't know what to say, Robert. Perhaps they have a different system in Edinburgh and the numbers don't match? Are you sure that you are telling them the right numbers and didn't get them mixed up?

I checked with Western Union, and the agent told me that the money was there and that you didn't pick it up. Why don't you go to the Royal Bank of Scotland? They are at 4 Princess Street, right around the corner from where you are staying. They should be able to straighten this out right away.

I'm surprised you suggest that I am kidding. Why would I be so cruel? I have $800 on the line, and I'm doing this for your benefit. I'm not the victim here, you are. Do you think I would wire you this kind of money and then make a joke about it? Do you think I get a kick out of imagining you walk back and forth to Western Union for no reason? This is a bad situation and you seem to think I'm making it worse! I'm not sure you are taking this as seriously as I am. Are you sure you didn't get injured?

I'm going to try this one more time, and I expect action on your part. I have wired an additional $200 dollars for a total of One Thousand ($1000) dollars. I really cannot afford any more, so I hope this is enough. The details are these:

Sender: Joseph Marshall
Receiver: Robert G, 48 Princess Street, Edinburgh Scotland
Amount: $1000.00 (One Thousand)
Money Transfer Control Number: 1822631749
Transfer Fee: 50.00
Number: 10341731365

And I am enclosing a receipt. Please be sure to get these details correct. I am awaiting to hear that you have collected the cash.
~jrm

The receipt was fake and I included a “security question”: Who's your daddy? I was sure this would tip my hand, but....

Robert, it has been 7 hours since I sent this. Did you get it?
~jrm

No i didn't,I will like to go back to western union and make this complain to them that all the confirmation number they give you was invalid ok..

YES! Three trips! Well, that's good enough for me.

Oops

2011-04-12T16:14:00.000-07:00

I made a mistake that has lead to a lot of confusion. It is a common mistake, so I have a lot of company. To assuage the trauma to my ego, I'll point out that no one who argued with me (or, for that matter, agreed with me) identified it. Allow me to explain it and correct myself.

The Church-Turing thesis is often stated as follows:

Anything that can be computed by some means can also be computed by a Turing machine.

And this is usually coupled with Rosser's observation that λ-calculus and recursion theory are equivalent formulations.

The problem is that phrasing, while not exactly incorrect, is not exactly right, either. It is vagueness disguised as definition. Because it is a definition, it is “correct, by definition”, but it is vague enough to admit interpretations that are absurd. Thus, if one isn't careful, one can deduce several absurdities that are “correct, by defintion”.

So what is the correct statement? The Church-Turing thesis is a statement about “effective calculability”. This is an intuitive concept which tries to generalize on the idea of an algorithm, or “plug and chug” math formulas, or “mechanistic” procedures like Newton's method. Many mathematicians have attempted to formalize the notion of “effective calculability”, among them Church and Turing, but also Gödel, Kleene, Rosser, and Post (and many others after them, but these are the big names). A correct statement of the Church-Turing thesis is more like this:

The formal terms “computable by a Turing machine” and “λ-definable” fully capture the intuitive notion of “effectively calculable”.

Naturally, the bulk of what a modern digital computer does is in fact an “effective calculation” and thus a Turing machine or λ-calculus is a very good model for what a computer can calculate. However, there are things a modern digital computer can do other than calculate. These activities fall outside the scope of the Church-Turing thesis and there is no reason to believe that they would be subject to the limitations of computability.

Does anybody really know what time it is?

— Robert Lamm of Chicago

A good example of a non-computable, yet common task that a digital computer performs is to determine the current time. There is no algorithm or calculation that you can perform that will yield the current time. You simply must check a clock. Even if you somehow know the elapsed time since some event, you nonetheless have to check a clock in order to determine the beginning of the ‘epoch’ (baseline time).

A whole set of non-computable quantities can be made available via reflection. Recall the definition of a Turing machine. The next state of a Turing machine is a function of the current state and the symbol on the tape under the head. It is not a function of, for example, the the size of the state transition table. This is not to say that these quantities are unknowable, but that they cannot be calculated without introspection (certainly bounds can calculated, and certainly any machine can be instrumented or even simulated, but consider this: any Turing machine can be augmented by any number of inaccessible states. There is no way to calculate the size of the state table without knowing the number of these states.) Also note, that there is nothing magic about these quantities, you can calculate to your heart's content with them after you obtain them. It is obtaining them in the first place that involves something other than computation.

My mistake is this: I didn't specifically and explicitly state when I was referring to the informal “effective calculation” and the superset that is the informal “computing” that one can do on a modern digital computer. In other words, I applied the Church-Turing thesis to too broad a class.

Given that, I'll rephrase my Exercise 1 and see how people react:

Exercise 1: Write a program for a class of universal Turing machines that, when run, calculates whether the machine it is on is imposing additional space complexity.

When I phrase it that way, it sort of sounds obvious that there are going to be problems.

On the other hand, this is a far more satisfying rewording than

Write a portable program that is non-portable.

Too much exercise

2011-04-08T09:53:00.000-07:00

I've spent the past few days thinking about how to answer the exercises in my previous post. I think I finally came up with a good analogy. (Bear with me.)

These days, it is not uncommon to run programs on virtual hardware. Programs like VMWare or Virtual Box provide nearly undetectable emulation of an x86 PC. In fact, modern x86 CPUs actually emulate the x86 instruction set through hardware accelerated interpretation or jit compiling. Although it can be tricky to emulate the entire body of computer hardware and peripherals that might go into a PC, it is straightforward to emulate the bare bones PC hardware with close to perfect fidelity, even down to the CPUID.

So could one write a portable x86 program — one that can run without modification on a real PC with real hardware or on a real PC with virtual hardware (like a Transmeta CPU) or on completely virtual hardware — that can reliably and predictably detect whether it is being “run directly” or “just being emulated”? The entire raison d'être of virtualization rests on the fact that, given enough effort, you can fool all of the programs all of the time. (Bugs notwithstanding.)

So let's reconsider Exercise 1: Write a program that returns 1 if run on any tail-recursive implementation of a language, but returns 0 if run on any non tail-recursive implementation of that same language.

Restate this as: Write a portable x86 program — one that can run without modification on a real PC with real hardware or on a real PC with virtual hardware (like a Transmeta CPU) or on completely virtual hardware — that can NOT ONLY reliably and predictably detect whether it is being “run directly” or “just being emulated”, BUT FURTHERMORE can reliably and predictably detect whether the underlying execution mechanism is “recursive” or “iterative”?

I assert that this question is barely worth thinking about (unless you work at VMWare) and that the answer could hardly be anything but “No.”

Exercise 1a (extra credit): Write a program that crashes or doesn't return if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language.

If a program cannot detect whether or not it is being emulated, perhaps it can “half” detect. If it could reliably crash the emulator, then you could at least demonstrate that some sort of emulation is being done even if you couldn't perform a conditional branch in this situation. Suppose the program were being emulated. Suppose further that the emulator is recursive (for whatever reason). One could, in theory, crash the emulator via a stack overflow or out-of-memory error (maybe that emulator is recursive, but it uses heap-allocated stack frames). Alas, this isn't what we asked for. We are looking for a program that can reliably crash an iterative emulator. We're out of luck.

Exercise 1b, essay (extra extra credit): Discuss the implications of your answers to exercises 1 and 1a to the semantics of the programs (woah, my apologies, programs don't have semantics, languages do. Pretend I wrote “languages”). In particular, briefly outline what changes to the various semantic models — denotational, operational, and/or axiomatic — take place upon introducing tail recursion.

The implication is this: the semantics of a programming language are logically independent of the implementation of the language. (If they were not, virtual machines would be impossible.)

Exercise 2: What trivial change can Louis make to his code for smaller that will disable tail recursion?

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      (let ((answer
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate))))
        answer)))

There is no need for a flag to enable or disable tail recursion. Tail recursion only “works” when the caller does nothing to the return value but immediately return it itself. A LET expression is syntactic sugar:

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      ((lambda (answer) answer)
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate)))))

You can now see that the value of the conditional expression is not immediately returned, but rather passed as an argument to a (rather trivial) lambda expression. (Yes, a smart compiler could notice that the lambda expression is simply the identity function in this case. If that is a problem, simply make sure that the function you use to disable the tail recursion is late-bound so that the compiler cannot prove that it can be elided.)

Exercise 3: What trivial change can Louis make to his code for smaller that will enable tail recursion on all but the initial call to smaller?

(define (smallest list predicate)
  ;; Returns the smallest element of list.

  (define (smallest list predicate)
    (if (null? list)
        #f
        (if (predicate (car list) (cadr list))
            (smallest (cons (car list) (cddr list)) predicate)
            (smallest (cdr list) predicate))))
  (let ((answer (smallest list predicate)))
    answer))

Again, we don't need special flags to have fine control over tail recursion.

Exercise 4: Implement disable-tail-recursion as a macro.

;;; For example:
(define-syntax disable-tail-recursion
  (syntax-rules ()
    ((disable-tail-recursion form)
     (let ((answer form)) answer))))

You could be more sophisticated and invoke a late-bound function, but this is, frankly, overkill. You hardly need macros, special forms, flags, decorations, etc. to control tail recursion. This is especially true if all you want is a pretty stack trace for debugging. Tail recursion is as easy to turn on and off as a printf.

Exercises

2011-04-01T11:11:00.000-07:00

Apparently I was not as clear with my questions as I thought I was. I've edited the questions to make them more precise. The additional text is in this alternative color.

Exercise 1: Write a program that returns 1 if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language. The goal is not to find a program and language implementation pair that exhibit the behavior, but to design a program that can correctly infer whether on not any supplied language implementation supports tail recursion by examining its own behavior.

Exercise 1a (extra credit): Write a program that crashes or doesn't return if run on a any tail-recursive implementation of a language, but returns 0 if run on a any non tail-recursive implementation of that same language. The goal is not to find a program and language implementation pair that exhibit the behavior, but to design a program that can correctly infer that any supplied implementation does not support tail recursion (this is a weaker condition because we do not require that the program correctly infer support of tail recursion, but only lack of support).

Exercise 1b, essay (extra extra credit): Discuss the implications of your answers to exercises 1 and 1a to the semantics of the programs. In particular, briefly outline what changes to the various semantic models — denotational, operational, and/or axiomatic — take place upon introducing tail recursion.

Louis Reasoner wrote this program to sort numbers:

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      (if (predicate (car list) (cadr list))
          (smallest (cons (car list) (cddr list)) predicate)
          (smallest (cdr list) predicate))))

(define (louis-sort list predicate)
  (do ((remainder list (cdr remainder))
       (answer '() (append answer (cons (smallest remainder predicate) '()))))
      ((null? remainder) answer)))

(define test-list
  (do ((i 0 (+ i 1))
       (answer '() (cons i answer)))
      ((>= i 100) answer)))

He complains “I am unable to debug this because smallest tail calls itself and leaves no trace on the stack. Look!

1 ]=> (louis-sort test-list <)

;The object (), passed as an argument to safe-car, is not a pair.
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

2 error> (debug)

There are 9 subproblems on the stack.

Subproblem level: 0 (this is the lowest subproblem level)
Expression (from stack):
    (predicate (car list) ###)
 subproblem being executed (marked by ###):
    (cadr list)
Environment created by the procedure: SMALLEST

 applied to: ((0) #[arity-dispatched-procedure 39])
The execution history for this subproblem contains 1 reduction.
You are now in the debugger.  Type q to quit, ? for commands.

3 debug> H
H
SL#  Procedure-name          Expression

0    smallest                (predicate (car list) (cadr list))
1    smallest                (if (predicate (car list) (cadr list)) (smalle ...
2    do-loop                 (cons (smallest remainder predicate) (quote ()))
3    do-loop                 (append answer (cons (smallest remainder predi ...
4    do-loop                 (do-loop (cdr remainder) (append answer (cons  ...
5    %repl-eval              (let ((value (hook/repl-eval s-expression envi ...
6    %repl-eval/write        (hook/repl-write (%repl-eval s-expression envi ...
7    do-loop                 (begin (if (queue-empty? queue) (let ((environ ...
8    loop                    (loop (bind-abort-restart cmdl (lambda () (der ...

“I was expecting to see pending stack frames as the program recursively called smaller, but since they are all tail-recursive calls, I don't have a way of knowing how deep it went. I wish I could selectively enable or disable tail recursion for this one call...”

Exercise 2: What trivial change can Louis make to his code for smaller that will disable tail recursion?

Louis again has a problem. “I have a stack trace, but, but, well, just LOOK at it!

1 ]=> (louis-sort test-list <)

;The object (), passed as an argument to safe-car, is not a pair.
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

2 error> (debug)

There are more than 50 subproblems on the stack.

Subproblem level: 0 (this is the lowest subproblem level)
Expression (from stack):
    (predicate (car list) ###)
 subproblem being executed (marked by ###):
    (cadr list)
Environment created by the procedure: SMALLEST

 applied to: ((0) #[arity-dispatched-procedure 39])
The execution history for this subproblem contains 1 reduction.
You are now in the debugger.  Type q to quit, ? for commands.

3 debug> H
H
SL#  Procedure-name          Expression

0    smallest                (predicate (car list) (cadr list))
1    smallest                (if (predicate (car list) (cadr list)) (smalle ...
2    smallest                (let ((answer (if (predicate (car list) (cadr  ...
3    smallest                (let ((answer (if (predicate (car list) (cadr  ...
4    smallest                (let ((answer (if (predicate (car list) (cadr  ...
5    smallest                (let ((answer (if (predicate (car list) (cadr  ...
6    smallest                (let ((answer (if (predicate (car list) (cadr  ...
7    smallest                (let ((answer (if (predicate (car list) (cadr  ...
8    smallest                (let ((answer (if (predicate (car list) (cadr  ...
9    smallest                (let ((answer (if (predicate (car list) (cadr  ...
10   smallest                (let ((answer (if (predicate (car list) (cadr  ...
11   smallest                (let ((answer (if (predicate (car list) (cadr  ...
12   smallest                (let ((answer (if (predicate (car list) (cadr  ...
13   smallest                (let ((answer (if (predicate (car list) (cadr  ...
14   smallest                (let ((answer (if (predicate (car list) (cadr  ...
15   smallest                (let ((answer (if (predicate (car list) (cadr  ...
16   smallest                (let ((answer (if (predicate (car list) (cadr  ...
17   smallest                (let ((answer (if (predicate (car list) (cadr  ...
18   smallest                (let ((answer (if (predicate (car list) (cadr  ...
19   smallest                (let ((answer (if (predicate (car list) (cadr  ...
20   smallest                (let ((answer (if (predicate (car list) (cadr  ...
21   smallest                (let ((answer (if (predicate (car list) (cadr  ...
22   smallest                (let ((answer (if (predicate (car list) (cadr  ...
23   smallest                (let ((answer (if (predicate (car list) (cadr  ...
24   smallest                (let ((answer (if (predicate (car list) (cadr  ...
25   smallest                (let ((answer (if (predicate (car list) (cadr  ...
26   smallest                (let ((answer (if (predicate (car list) (cadr  ...
27   smallest                (let ((answer (if (predicate (car list) (cadr  ...
28   smallest                (let ((answer (if (predicate (car list) (cadr  ...
29   smallest                (let ((answer (if (predicate (car list) (cadr  ...
30   smallest                (let ((answer (if (predicate (car list) (cadr  ...
31   smallest                (let ((answer (if (predicate (car list) (cadr  ...
32   smallest                (let ((answer (if (predicate (car list) (cadr  ...
33   smallest                (let ((answer (if (predicate (car list) (cadr  ...
34   smallest                (let ((answer (if (predicate (car list) (cadr  ...
35   smallest                (let ((answer (if (predicate (car list) (cadr  ...
36   smallest                (let ((answer (if (predicate (car list) (cadr  ...
37   smallest                (let ((answer (if (predicate (car list) (cadr  ...
38   smallest                (let ((answer (if (predicate (car list) (cadr  ...
39   smallest                (let ((answer (if (predicate (car list) (cadr  ...
40   smallest                (let ((answer (if (predicate (car list) (cadr  ...
41   smallest                (let ((answer (if (predicate (car list) (cadr  ...
42   smallest                (let ((answer (if (predicate (car list) (cadr  ...
43   smallest                (let ((answer (if (predicate (car list) (cadr  ...
44   smallest                (let ((answer (if (predicate (car list) (cadr  ...
45   smallest                (let ((answer (if (predicate (car list) (cadr  ...
46   smallest                (let ((answer (if (predicate (car list) (cadr  ...
47   smallest                (let ((answer (if (predicate (car list) (cadr  ...
48   smallest                (let ((answer (if (predicate (car list) (cadr  ...
49   smallest                (let ((answer (if (predicate (car list) (cadr  ...
50   smallest                (let ((answer (if (predicate (car list) (cadr  ...
51   smallest                (let ((answer (if (predicate (car list) (cadr  ...
52   smallest                (let ((answer (if (predicate (car list) (cadr  ...
53   smallest                (let ((answer (if (predicate (car list) (cadr  ...
54   smallest                (let ((answer (if (predicate (car list) (cadr  ...
55   smallest                (let ((answer (if (predicate (car list) (cadr  ...
56   smallest                (let ((answer (if (predicate (car list) (cadr  ...
57   smallest                (let ((answer (if (predicate (car list) (cadr  ...
58   smallest                (let ((answer (if (predicate (car list) (cadr  ...
59   smallest                (let ((answer (if (predicate (car list) (cadr  ...
60   smallest                (let ((answer (if (predicate (car list) (cadr  ...
61   smallest                (let ((answer (if (predicate (car list) (cadr  ...
62   smallest                (let ((answer (if (predicate (car list) (cadr  ...
63   smallest                (let ((answer (if (predicate (car list) (cadr  ...
64   smallest                (let ((answer (if (predicate (car list) (cadr  ...
65   smallest                (let ((answer (if (predicate (car list) (cadr  ...
66   smallest                (let ((answer (if (predicate (car list) (cadr  ...
67   smallest                (let ((answer (if (predicate (car list) (cadr  ...
68   smallest                (let ((answer (if (predicate (car list) (cadr  ...
69   smallest                (let ((answer (if (predicate (car list) (cadr  ...
70   smallest                (let ((answer (if (predicate (car list) (cadr  ...
71   smallest                (let ((answer (if (predicate (car list) (cadr  ...
72   smallest                (let ((answer (if (predicate (car list) (cadr  ...
73   smallest                (let ((answer (if (predicate (car list) (cadr  ...
74   smallest                (let ((answer (if (predicate (car list) (cadr  ...
75   smallest                (let ((answer (if (predicate (car list) (cadr  ...
76   smallest                (let ((answer (if (predicate (car list) (cadr  ...
77   smallest                (let ((answer (if (predicate (car list) (cadr  ...
78   smallest                (let ((answer (if (predicate (car list) (cadr  ...
79   smallest                (let ((answer (if (predicate (car list) (cadr  ...
80   smallest                (let ((answer (if (predicate (car list) (cadr  ...
81   smallest                (let ((answer (if (predicate (car list) (cadr  ...
82   smallest                (let ((answer (if (predicate (car list) (cadr  ...
83   smallest                (let ((answer (if (predicate (car list) (cadr  ...
84   smallest                (let ((answer (if (predicate (car list) (cadr  ...
85   smallest                (let ((answer (if (predicate (car list) (cadr  ...
86   smallest                (let ((answer (if (predicate (car list) (cadr  ...
87   smallest                (let ((answer (if (predicate (car list) (cadr  ...
88   smallest                (let ((answer (if (predicate (car list) (cadr  ...
89   smallest                (let ((answer (if (predicate (car list) (cadr  ...
90   smallest                (let ((answer (if (predicate (car list) (cadr  ...
91   smallest                (let ((answer (if (predicate (car list) (cadr  ...
92   smallest                (let ((answer (if (predicate (car list) (cadr  ...
93   smallest                (let ((answer (if (predicate (car list) (cadr  ...
94   smallest                (let ((answer (if (predicate (car list) (cadr  ...
95   smallest                (let ((answer (if (predicate (car list) (cadr  ...
96   smallest                (let ((answer (if (predicate (car list) (cadr  ...
97   smallest                (let ((answer (if (predicate (car list) (cadr  ...
98   smallest                (let ((answer (if (predicate (car list) (cadr  ...
99   smallest                (let ((answer (if (predicate (car list) (cadr  ...
100  smallest                (let ((answer (if (predicate (car list) (cadr  ...
101  smallest                (let ((answer (if (predicate (car list) (cadr  ...
102  do-loop                 (cons (smallest remainder predicate) (quote ()))
103  do-loop                 (append answer (cons (smallest remainder predi ...
104  do-loop                 (do-loop (cdr remainder) (append answer (cons  ...
105  %repl-eval              (let ((value (hook/repl-eval s-expression envi ...
106  %repl-eval/write        (hook/repl-write (%repl-eval s-expression envi ...
107  do-loop                 (begin (if (queue-empty? queue) (let ((environ ...
108  loop                    (loop (bind-abort-restart cmdl (lambda () (der ...

“I wish I could start eliminating the tail call from the second call onwards...

Exercise 3: What trivial change can Louis make to his code for smaller that will enable tail recursion on all but the initial call to smaller? (Hint, the bold text in the following backtrace shows how this differs from the first backtrace.)

1 ]=> (louis-sort test-list <)

;The object (), passed as an argument to safe-car, is not a pair.
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

2 error> (debug)

There are 10 subproblems on the stack.

Subproblem level: 0 (this is the lowest subproblem level)
Expression (from stack):
    (predicate (car list) ###)
 subproblem being executed (marked by ###):
    (cadr list)
Environment created by the procedure: SMALLEST

 applied to: ((0) #[arity-dispatched-procedure 39])
The execution history for this subproblem contains 1 reduction.
You are now in the debugger.  Type q to quit, ? for commands.

3 debug> H
H
SL#  Procedure-name          Expression

0    smallest                (predicate (car list) (cadr list))
1    smallest                (if (predicate (car list) (cadr list)) (smalle ...
2    smallest                (let ((answer (smallest list predicate))) answer)
3    do-loop                 (cons (smallest remainder predicate) (quote ()))
4    do-loop                 (append answer (cons (smallest remainder predi ...
5    do-loop                 (do-loop (cdr remainder) (append answer (cons  ...
6    %repl-eval              (let ((value (hook/repl-eval s-expression envi ...
7    %repl-eval/write        (hook/repl-write (%repl-eval s-expression envi ...
8    do-loop                 (begin (if (queue-empty? queue) (let ((environ ...
9    loop                    (loop (bind-abort-restart cmdl (lambda () (der ...

Louis seems to have gotten his wish and is currently making progress despite the existence of tail recursion. Cy D. Fect, however, is unimpressed. He complains “Sure, it is trivial to disable tail recursion whenever you desire, but I don't like guessing whether the compiler is going to emit a tail call, and I'd simply rather not learn. I'd prefer some sort of declaration or decoration so I can explicitly tell the compiler to not emit a tail call. Something like this:

(define (smallest list predicate)
  ;; Returns the smallest element of list.
  (if (null? list)
      #f
      (if (predicate (car list) (cadr list))
          ;; This branch should leave a backtrace - CDF
          (disable-tail-recursion 
             (smallest (cons (car list) (cddr list)) predicate))
          (smallest (cdr list) predicate))))

Exercise 4: Implement disable-tail-recursion as a macro.

Homework: Fix Louis's code.

Tail recursion and debugging

2011-03-30T13:06:00.000-07:00

java.lang.NullPointerException
        at java.io.FilterInputStream.close(FilterInputStream.java:172)
        at sun.net.www.protocol.jar.JarURLConnection$JarURLInputStream.close(JarURLConnection.java:108)
        at com.alba.vware.ResourceServlet.doGet(ResourceServlet.java:396)
        at javax.servlet.http.HttpServlet.service(HttpServlet.java:617)
        at javax.servlet.http.HttpServlet.service(HttpServlet.java:717)
        at com.alba.vware.ServletDefinition.doService(ServletDefinition.java:261)
        at com.alba.vware.ServletDefinition.service(ServletDefinition.java:175)
        at com.alba.vware.ManagedServletPipeline.service(ManagedServletPipeline.java:91)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:62)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
[Continued on next page]

When a tail recursion is eliminated, there's no stack frame left to use to print a traceback when something goes wrong later.

— Guido van Rossum

[Continued from previous page]
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
[Continued on next page]

The elimination of stack frames doesn't do anything for the algorithmic complexity of the code, but it does make debugging harder.

— Guido van Rossum

[Continued from previous page]
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
[Continued on next page]

My issue with this optimization is that you lose debugging information.

— Ian Bicking

[Continued from previous page]
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
[Continued on next page]

Tail recursion can be easily inlined, however it is my understanding that the Java creators specifically chose not to implement this, as it makes resultant code hard to debug (if not impossible).

— Andrew Monkhouse

[Continued from previous page]
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
[Continued on next page]

This will confuse users who inadvertently wrote something recursive (the recursion isn't obvious in the stack trace printed), and makes debugging hard.

— Guido van Rossum

[Continued from previous page]
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
[Continued on next page]

I am a big fan of being able to get stack backtraces when I have a problem to debug. But tail call recursion silently throws away stack frames. You get great performance benefits from doing so, but I'd like an option when debugging to get at the information that has been thrown away.

— btilly

[Continued from previous page]
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
[Continued on next page]

I'm uninterested in optimizing tail recursion.

— Guido van Rossum

[Continued from previous page]
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.FilterDefinition.doFilter(FilterDefinition.java:167)
        at com.alba.vware.FilterChainInvoke.doFilter(FilterChainInvoke.java:58)
        at com.alba.vware.ManagedFilterPipeline.dispatch(ManagedFilterPipeline.java:118)
        at com.alba.vware.Filter.doFilter(Filter.java:113)
        at com.alba.vware.FilteredServlet$Chain.doFilter(FilteredServlet.java:176)
        at com.alba.vware.FilteredServlet.service(FilteredServlet.java:145)
        at com.alba.vware.HttpConnection.runServletFromWithinSpan(HttpConnection.java:933)
        at com.alba.vware.HttpConnection.access$000(HttpConnection.java:71)
        at com.alba.vware.HttpConnection$1.runServletFromWithinSpan(HttpConnection.java:854)
        at com.alba.vware.TraceHelper$TraceableServletRunnable$2.run(TraceHelper.java:467)
        at com.alba.vware.LocalTraceSpanRunnable.run(LocalTraceSpanRunnable.java:56)
        at com.alba.vware.LocalTraceSpanBuilder.run(LocalTraceSpanBuilder.java:518)
        at com.alba.vware.TraceHelper$TraceableServletRunnable.beginNewTrace(TraceHelper.java:411)
        at com.alba.vware.TraceHelper$TraceableServletRunnable.runWithTracingEnabled(TraceHelper.java:377)
        at com.alba.vware.TraceHelper$TraceableServletRunnable.run(TraceHelper.java:339)
        at com.alba.vware.HttpConnection.runServlet(HttpConnection.java:850)
        at com.alba.vware.HttpConnection.run(HttpConnection.java:815)
        at com.alba.vware.DispatchQueue$WorkerThread.run(DispatchQueue.java:379)

The default value for thread stack size is 128K for 32-bit server and 256K for 64-bit server.

— Java manual

Erf

2011-03-23T15:25:00.000-07:00

I found a polynomial approximation to Erf:

(define (polynomial-erf z)
  ;; Numerical Recipies 6.2
  ;; fractional error < 1.2e-7
  (let* ((t (/ 1.0 (+ 1.0 (* .5 (abs z)))))
         (ans (- 1.0 (* t
                        (exp (+ (- (* z z))
                                (+ -1.26551223
                                   (* t (+ 1.00002368
                                   (* t (+ .37409196
                                   (* t (+ .09678418
                                   (* t (+ -.18628806 
                                   (* t (+ .27886807 
                                   (* t (+ -1.13520398
                                   (* t (+ 1.48851587
                                   (* t (+ -.82215223 
                                   (* t .17087277))))))))))))))))))))))))
    (if (>= z 0) ans (- ans))))

For kicks I plotted the difference between my Taylor series expansion and the polynomial approximation. (Since the polynomial approximation probably started life as the Taylor series, I wasn't expecting much enlightenment.) My Taylor series version has a tunable tolerance, though, so I dialed it up beyond the 1.2e-7 tolerance that the polynomial approximation claims. I got this graph:

So what are we seeing? First, my Taylor series version does a pretty good job for small values, but when we get to about Erf(1.5) or so, you can see the beginnings of a ‘square wave’ artifact. The discrete jumps are caused by adding more terms to the expansion. Down at the low end we see a smooth wiggly curve. This is the error from the polynomial approximation. Since both the polynomial and Taylor series are approximations, we cannot quantitatively determine how much error comes from each approximation, but we have a rough idea about what is going on.

Continued Fractions

2011-03-23T11:39:00.000-07:00

How did I end up back at continued fractions? I was doing more thinking about my polling problem, and I wanted to plot some cumulative log-normal distributions. That involves computing the ‘error function’. There are libraries for computing this, but I didn't find anything I could immediately use, so I wrote a truly simple-minded version that just expands the Taylor series:

(define (erf z tolerance)

  (define (erf-taylor terms)
    (* (/ 2 (sqrt pi))
       (sum 0 terms
            (lambda (n)
              (/ (* (expt -1 n) (expt z (+ (* n 2) 1)))
                 (* (factorial n) (+ (* n 2) 1)))))))

  (define (iter approx terms)
    (let ((new-approx (erf-taylor terms)))
      (if (and (> new-approx -1.0)
               (< new-approx 1.0)
               (< (abs (- new-approx approx)) tolerance))
          new-approx
          (iter new-approx (+ terms 1)))))
  (iter 0.0 1))

This was good enough to get a curve plotted, but it is a terrible way to compute Erf. Since Erf is such an important function in statistics, I thought that I should put a little more effort into it, so I looked around and found “Computation of the error function erf in arbitrary precision with correct rounding” by Chevillard and Ravol. This paper seriously goes to town. Their goal is to return the floating point number closest to the actual value of Erf according to the rounding rules. It isn't enough to simply calculate Erf using floats, you have to keep careful track of where rounding errors can happen and go out of your way to minimize them. This is probably more work than it is worth for me, but I assume that Chevillard and Ravol have already done the really hard analysis.

Chevillard and Ravol considered an approach using continued fractions. They dismissed it as being too slow for practical computation. They're correct. But it just so happens that I wrote a continued fraction library for Scheme, so although the technique is slow, using a continued fraction approximation is the easiest path to validating the faster computations.

Unfortunately, my continued fraction library is too limited to deal with non-integer coefficients, so I have to fix that first.

A couple of puzzles

2011-03-18T08:15:00.000-07:00

Write a program that finds the smallest element in a list.
Write a program that, given a predicate, finds an extremum from a list. That is, if the predicate is <, the smallest is returned, if the predicate is >, the largest is returned.
```
(define (longer? a b) (> (string-length a) (string-length b)))
```
Given longer? it would find the longest string in a list.

C.A.R. “Tony” Hoare proposed a selection algorithm to find the kth order statistic in a collection of elements. The obvious solution is this:

(define (list-select predicate list index)
  (list-ref (sort list predicate) index))

;; Examples:
;;
;; Find the smallest element:
;;   (list-select < list 0)
;;
;; Find the second longest string:
;;   (lsit-select longer? list 1)

The “obvious” solution is O(n log n), but one can do better.

And from left field

2011-03-10T09:41:00.000-08:00

Blogger is kind enough to report a few statistics about people who visit this blog. One of the stats is “Search Keywords”, which I interpret to mean “What people typed in to Google that directed them here”. Here are a few:

continuation passing style no stack
how to not write factorial functions
lisp vs c++
first class environment

These aren't weird. This one is:

stairsteps in hair

I'm baffled.

Pretty charts

2011-03-09T14:38:00.000-08:00

I have collected some empirical data concerning the polling problem. If we sort the successful polls by time and plot the ordinal fraction against time we get this:

If we plot on a logarithmic scale, it looks like this:

This looks suspiciously familiar. My gut feeling was that there was a log-normal distribution somewhere around here. If we try fitting a cumulative log-normal distribution to the data, we get this:

(μ = 4.3, σ = 1.6)

That is a very good fit for the range of interest.

Last night I had an ‘Aha!’ moment. We can look at the distribution as the probability that a result will be ready when we poll (that's not the ‘Aha!’). But we can pretend that we made all the RPCs at exactly the same time. If we had, then this chart shows the fraction of RPCs that finish as a function of time (not a big ‘Aha!’, but I'll take it). So if we were to poll at 2 seconds, we'd find about 20% of the RPCs have completed, but if we wait until about 4.5 seconds we'd find 90% have completed.

What if we polled at 2 seconds and 4.5 seconds? Well, the 20% that completed before the poll at 2 seconds will be serviced right after that poll, but any that become ready between 2 and 4.5 seconds will have to wait until the later poll. That will be 90 - 20 = 70%. That is to say, the efficacy of the poll — the marginal increase in likelihood of getting a response — is proportional to the vertical difference in the graph divided by the time since the last poll. Or, to put it yet another way, the polling frequency should be proportional to the derivative of the distribution. Aha!

An empirical measurement of the derivative would have a lot of noise. Fortunately, we noticed that the cumulative distribution is closely modeled by a cumulative log-normal curve. Cumulative means integral. The derivative is therefore simply a log-normal curve centered at the median time (about 3 seconds). (Is this an ‘Aha!’, or a ‘D'oh!’ moment?)

I think I have enough of an understanding of this problem to write some code.

More about that puzzle

2011-03-08T09:58:00.000-08:00

In the previous post I described a puzzle. I based the puzzle on a real-world problem: I'm invoking a service with an RPC and the defined interface requires that I poll for the answer. (I dislike polling, but I'm stuck with it.) I have been told vaguely that the answer usually arrives ‘within a few seconds,’ but that ‘sometimes it takes longer.’ (This is what passes for documentation. I can't blame the implementors too much, actually; they themselves are interfacing with a sucky third-party API. On the other hand, had they provided a better abstraction, then I wouldn't need to.)

So given this API, I decided to model it to try to understand it better. Casting the problem as a betting challenge helps because I can reduce the abstract cost and benefit to a simple number that I want to maximize. We can compare different strategies and different assumptions by comparing the “payoff”.

It makes sense to look at the trivial and degenerate strategies first as they are the simplest. The easiest strategy is to not do anything. That seems to be a non-starter here, but it rules out any strategy that loses money in the long run. (You'd be surprised at how often people think that doing something simply must be better than doing nothing. As Ira Gershwin penned, “It ain't necessarily so.”)

The next simplest strategy is to wait until you are sure the answer is available and poll exactly once. So how long is that? I asked the implementors of the API if there were any point at which we absolutely knew that the answer was available. They said there was no a priori time limit on getting an answer, but that they've never seen one take more than a few days. That's discouraging because it seems to rule out any sort of guaranteed “real-time” interaction. But since ‘most of the time’ it takes only ‘a few seconds’, it might be worthwhile to partition the problem into fast and slow responses and optimize the fast case.

The third simplest strategy is poll as rapidly as possible until the answer is ready. This will minimize the amount of time we spend in anticipation of a result, but the cost associated with polling may be too expensive (and remember, it costs nothing to do nothing).

Finally, there may be an optimal way to schedule the polling. Consider the case if we knew for certain that 97% of the time the answer comes back in exactly 2 seconds and that the other 3% of the time it took exactly 115 seconds. Obviously we'd poll exactly twice: once at just after two seconds, once again just after 115. Of course this is unlikely to be the case, but a bi-modal distribution of response times is not unusual in and of itself.

We can now characterize something about the solution: if an optimal strategy exists, it depends on several factors:

The cost of polling.
The benefit of getting a ‘timely’ answer.
The distribution of response times.

At this point I suspect that the distribution can be modeled as the sum of a handful of time-shifted log-normal distributions, but that is just a gut feeling.

A puzzle and challenge

2011-03-03T17:35:00.000-08:00

Imagine you have a black box that can play a betting game. On the top of the box is a button, two LEDs (red and green), and a slot in which you can insert a 25 cent piece.

You start the game by pressing the button. This resets the box to the initial state.

If the box is in the initial state, whenever you insert a 25 cent piece, the red LED will light (nothing else happens and you lose your money). While the box is in the initial state, you may insert as many 25 cent pieces as you wish (and they each will be happily devoured).

The box will remain in the initial state for somewhere between 1 millisecond and 10 seconds, at which point it silently changes to the final state.

In the final state, if you insert a 25 cent piece, the green LED will light, your 25 cent piece will be returned and the game is over. However, you may be awarded a bonus. The bonus starts at one dollar the instant the box changes to the final state, but the bonus is reduced by one cent every 10 milliseconds after the state change.

Once in the final state, the box remains there until the button is pressed to start the next round.

The challenge: develop and implement a strategy that maximizes your return.

Fifty Years Ago

2011-03-01T12:26:00.000-08:00

*
*      EVALQ   A SUCCESSOR TO THE APPLY OPERATOR, THE GRAND NEW
*              (AS OF 1 MARCH 1961) THE EVALQUOTE OPERATOR.
*

A universal Turing machine is an abstract ‘machine’ that can simulate any other Turing machine.
A universal function is the mathematical analogue of a universal Turing machine. A universal function is a computable function that can be parameterized to compute any other computable function. The fact that universal functions exist (by the utm theorem) means that one can write an interpreter. (Alternatively, an interpreter for a Turing complete language can be easily shown to be a universal function.)
In Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (there is no Part II), McCarthy states:

There is an S-function apply with the property that if f is an S-expression for an S-function f′ and args is a list of arguments of the form (arg₁,...,arg_n), where arg₁,...,arg_n are arbitrary S-expressions, then apply[f;args] and f′[arg₁,...,arg_n] are defined for the same values of arg₁,...,arg_n, and are equal when defined.

This is not a vacuous statement. It says (more precisely), suppose there is a mathematical partial function f′ which is computable for some arguments. Then, there is a program (called f), which will compute exactly the same answers as the abstract mathematical partial function f′. Furthermore, the LISP program apply, when given the program f and some particular arguments, computes the exact same thing as if the function f′ were directly called on the arguments. In other words, LISP I's apply operator is universal.

By March 1 1961 it was realized that although apply is universal, it is not necessarily primitive. The user version of apply is trivially defined as:

(defun quote-args (arglist)
  (map 'list (lambda (arg) (cons 'quote arg)) arglist))

(defun lisp1-apply (f arglist)
  (eval (cons f (quote-args arglist))))

This is the origin of the evalquote operator.

In February 1961, Dan Edwards recoded OVERLORD (the original batch-mode ‘REPL’) to use EVALQUOTE rather than APPLY for top-level execution.

EVALQUOTE — Reads pairs of LISP statements (atoms or atomic symbols) and considers the first as a function and the second as a list of quoted arguments for the function. Pairs are read in until a card with the atomic symbol STOP is encountered or a READ error is found. The pairs are then evaluated one at a time and the results printed.

— Lisp 1.5 Programmer's Manual

Here is a LISP program from about this time:

DEFINE ((
(MEMBER (LAMBDA (A X) (COND ((NULL X) F)
     ((EQ A (CAR X)) T) (T (MEMBER A (CDR X))) )))
(UNION (LAMBDA (X Y) (COND ((NULL X) Y) ((MEMBER
     (CAR X) Y) (UNION (CDR X) Y)) (T (CONS (CAR X)
     (UNION (CDR X) Y))) )))
(INTERSECTION (LAMBDA (X Y) (COND ((NULL X) NIL)
     ((MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECTION
     (CDR X) Y))) (T (INTERSECTION (CDR X) Y)) )))
))
INTERSECTION ((A1 A2 A3) (A1 A3 A5))
UNION ((X Y Z) (U V W X))

The commas have disappeared, the main loop now uses the two-argument EVALQUOTE rather than the three-argument APPLY, and some rudimentary indentation is present.

No stack? No problem.

2011-02-28T15:32:00.000-08:00

“We have no badges. In fact, we don't need badges. I don't have to show you any stinking badges...”
— The Treasure of the Sierra Madre, B. Travern

I really blew it with that last post. Mea maxima culpa.

The IBM 704 didn't have a stack.
This was not unusual at the time. Most computer languages at the time had no need of a stack at all. Algol, however, was a different story. Friedrich L. (Fritz) Bauer had, a few years earlier, invented the stack in order to support recursive descent evaluation of expressions. This appeared to be the best way to support the recursion and block structure that ALGOL required. As Alan Perlis notes:

It was ALGOL 60 that really pointed a finger at, focused on the absolute necessity of learning how to define, control and manipulate stacks. ALGOL 60 would have been impossible to adequately process in a reasonable way without the concept of stacks. Though we had stacks before, only in ALGOL 60 did stacks come to take a central place in the design of processors.
—Alan J. Perlis, Transcripts of Presentation

Not having a stack can make it a bit of a challenge to program, but Steve “Slug” Russell invented a different technique. The assembly code of LISP I was written in continuation-passing style. (Russell did not name this technique; the phrase “continuation-passing style” seems to have been coined by Sussman and Steele in 1975.)

When a program is converted to continuation-passing style, all control transfer can be expressed with jump and indirect jump operations. This does not eliminate the need for temporary storage — any piece of re-entrant or recursive code will need to save and restore values in use as it calls subroutines — but it allows you to separate the control flow from the temporary storage management.

Closed subroutines in LISP are given a standard calling sequence. The arguments of the subroutines are placed in order in the AC, the MQ, and locations called ARG3 and ARG4.

After the arguments have been provided, the subroutine is entered by a TSX SUBR, 4 where SUBR is the location of the first instruction of the subroutine. The subroutine ends with its value in the AC and the instruction TRA 1,4 which returns control to the instruction after the TSX that set IR4. Note that any other program can be executed between this TSX and the TRA 1,4 so long as the contents of IR4 are restored to the value set by the TSX before the TRA is executed. A subroutine restores all index registers it uses to the value they had on entering the subroutine.
— S. Russell, Artificial Intelligence Project — RLE and MIT Computation Center, Writing and Debugging Programs — Memo 6

We can see this in the LISP 1.5 assembly code:

       REM
       REM APPEND(L1,L2)=
       REM (L1=0 YIELDS L2,1 YIELDS CONS(CAR(L1),APPEND(CDR(L1),L2))
A      HED
APPEND TNZ APNP1
       XCA
       TRA 1,4       ** Invoke continuation (return)

 APNP1 SXD AS1,4     ** Store continuation in memory
       TSX $SAVE,4   ** Call SAVE subroutine
       TXL     $END2,,CWR1+2      SAVE 2 ITEMS
       PDX 0,4
       CLA 0,4
       STO CWR1
       ANA DECM
       TSX APPEND,4  ** Recursive call to APPEND
       XCA
       LXA CWR1,4
       PXD 0,4
       TSX UNSAVE,4  ** Call UNSAVE to restore temps
       LXD AS1,4     ** Restore continuation to register
       TRA $CONS     ** Tail call CONS

Where did the stack go?

2011-02-24T12:33:00.000-08:00

[This post doesn't describe things the way I'd like to. Please see the subsequent post.]

The IBM 704 didn't have a stack.

This was not unusual at the time. Although stacks were known about for years before, low-level languages did not make much use of them. Early FORTRAN certainly didn't need a stack, so IBM didn't bother with a hardware implementation.

Not having a stack does make it a bit of a challenge to program. For example, when you call a subroutine, where does the return address go?

The IBM 704 had an instruction TSX (Transfer and Set Index) that was designed for subroutine linkage. TSX would do two things. First, it loaded a register with the two's-complement value of the program counter. (The IBM 704 was much better at subtraction than addition. The two's complement of the program counter made it easier to dispatch because subtracting a two's complement number gives the same result as adding the uncomplemented number.) Second, it loaded the program counter with the subroutine address. Loading the program counter would cause an unconditional jump to the subroutine.

There was obviously a data path from the instruction register to the program counter — that's how the target address got from the instruction stream to the program counter. Likewise, there was a data path from the program counter to the register set. However, there doesn't appear to be a data path from the register set back in the other direction. So we can use the TSX instruction to call a subroutine, but once there we need to do a nasty trick to get back. That trick is to end the subroutine with an unconditional jump (opcode TRA). When we enter the subroutine, we expect the return address to be in one of the registers (by convention, LISP used register 4). The first thing the subroutine does is to save the return address in the target field of the TRA instruction. This modifies the code so that the unconditional jump at the end takes us back to where the subroutine is called.

But what if the subroutine needs to be re-entrant?

Ultimately, you need a stack (or a heap). There are several options for implementing one. The obvious idea of allocating a block of memory and keeping a pointer to the top of stack was not obviously the best idea. Without dedicated hardware, operations like push and pop become quite expensive. You have to fetch the stack pointer from memory, perform an addition or subtraction, do an indirect memory reference, and write the new stack pointer back to memory. (And if you thought the x86 didn't have enough registers, the IBM 704 had only 3 index registers.)

Another method is to use a linked list as a stack. This is not obviously a bad idea. Once the linked list is created at program initialization time, pushing and popping can be done via pointer chasing. This avoids having to use the ALU for adding and subtracting the stack pointer. Furthermore, you didn't have to guess how much stack space to reserve. with only 32,000 words of memory, you didn't want to waste any on unused stack reserve. For these reasons, both IPL and LISP I used a ‘push-down list’ to implement re-entrant subroutines.

A harder puzzle

2011-02-23T14:31:00.000-08:00

Suppose I have a procedure that needs to make temporary use of some expensive resource. The usual way to code this up is something like this:

(defun foo (x)
  (let ((resource nil))   ; or #f or whatever
    (unwind-protect
        (progn (setq resource (obtain-resource pool))
               (compute x resource))
      (if (not (null resource))
          (return-resource pool resource)))))

There are two problems with this. The first is a minor race condition where the resource can be lost if an asynchronous interrupt is taken right after obtain-resource returns but just before the value is assigned to the variable. We'll ignore that problem for now. The bigger problem is that we cannot easily spot the separation between the parts of foo concerned with resource management and the parts needed for computing the return value.

What we want to do is abstract out the resource management:

(defun foo (x)
  (call-with-resource resource-pool
    (lambda (resource)
      (compute x resource))))

(defun call-with-resource (pool receiver)
  (let ((resource nil))
    (unwind-protect
        (progn (setq resource (obtain-resource pool))
               (funcall receiver resource))
      (if (not (null resource))
          (return-resource pool resource)))))

(One could use macros here, too.)

Now we can see that foo just supplies an additional argument to a call to compute. As an additional bonus, we have a simple idiom that correctly encapsulates the acquisition and release of our resource. Other code that has the ‘boilerplate’ needed to manage the resource can be simplified to use our wrapper. It is less likely that resources are dropped by accidentally copying the boilerplate incorrectly. This sort of wrapper code is frequently found in Lisp or Scheme.

The puzzle is “How do you do this in Java?” To be more specific, suppose I have this code:

class Foo {
    ...
    public Answer method1 (int x) throws BadRequest {
        Resource resource = null;
        try {
            resource = pool.obtainResource();
            return computeAnswer (x, resource);
        } finally {
            if (resource != null)
                pool.returnResource(resource);
        }
    }

    private Answer computeAnswer (int x, Resource r) throws BadRequest {
        ....
    }
}

class Bar {
   ...
   public void method2 (Boolean flag, String name) throws NoSuchEntry {
        ExpensiveObject resource = null;
        try {
            resource = expensiveObjectPool.obtainResource();
            if (flag)
               resource.addName(name);
            doSomething(resource); 
        } finally {
            if (resource != null)
                expensiveObjectPool.returnResource(resource);
        }
    }

    private void doSomething (ExpensiveObject expo) throws NoSuchEntry {
        ....
    }      
}

and I want to write something more like this:

class Foo {
    ...
    public Answer method1 (int x) throws BadRequest {
        // WRAPPER CODE HERE
        return computeAnswer(x, resource);
        // POSSIBLE WRAPPER EPILOGUE
    }
 
    private Answer computeAnswer (int x, Resource r) throws BadRequest {
        ....
    }
}

class Bar {
   ...
   public void method2 (Boolean flag, String name) throws NoSuchEntry {
        // WRAPPER CODE HERE;
            if (flag)
               resource.addName(name);
            doSomething(resource); 
        // POSSIBLE WRAPPER EPILOGUE HERE
    }

    private void doSomething (ExpensiveObject expo) throws NoSuchEntry {
        ....
    }      
}

Where the wrapper and possible epilogue (if needed) are some relatively simple, easy to use constructs like a method call or inner class declaration or whatever.

An easy puzzle

2011-02-23T12:07:00.000-08:00

Suppose I have some code like this:

(defun foo (x)
  (wrapper-macro
    (bar 42 x)))

Where wrapper-macro simply prints ‘Normal exit’ or ‘Throw’ as control returns from bar through foo. (If bar returns normally, all the return values are returned from foo after wrapper-macro prints. If bar exits via a throw, then the throw continues after wrapper-macro prints.)

The challenge: Implement wrapper-macro.

(If you wish, imagine that wrapper-macro simply expands to this:

(defun foo (x)
  (wrapper-function
    (lambda ()
      (bar 42 x))))

and the challenge is to implement wrapper-function.)

An early LISP program (circa Feb. 1960)

2011-02-18T07:47:00.000-08:00

       TST M948-371-P. FOX-EXERCISE 1
DEFINE
(((COLLAPSE,(LAMBDA,(L),(COND,
   ((ATOM,L), (CONS,L,NIL))
   ((NULL,(CDR,L)),
      (COND,((ATOM,(CAR,L)),L),(T,(COLLAPSE,(CAR,L)))))
   (T,(APPEND,(COLLAPSE,(CAR,L)),(COLLAPSE,(CDR,L))))
))))) ()
COLLAPSE ((((A,B),((C))),((D,(E,F)),(G),((H))))) ()
COLLAPSE ((A,(B,(C,(D,(E))),F,(G,(H,J))))) ()
COLLAPSE ((((((A),B),C),D),E)) ()
   STOP))))))))))STOP
        FIN M948-371-P. FOX-EXERCISE 1

Notes:

This example and the quotes below were taken from the LISP I manual by Phyllis Fox. The output from the program contains these two lines:
APPLY OPERATOR AS OF SEPTEMBER 1, 1959
THE TIME IS NOW 2/16 1139.5
so we can date the sample run.
Each line above was punched on a separate card.
The TST (or SET) card indicates the beginning of the program. The FIN card indicates the end.
This is followed by triplets of the form <function>, <argument-list>, <environment>. Instead of read, eval, print, the main loop is more like read, read, read, apply, print.
The STOP card has lots of extra close parens in order to keep the reader from consuming the entire card deck if the programmer didn't correctly close all the parens.

The read program reads until it finds the correct number of final parenthesis.

S-expressions were originally supposed to have commas between the elements. The LISP I manual explains: “The commas in writing S-expressions may be omitted. This is an accident.” The author of the reader took a shortcut and treated whitespace as commas. “The current version of the read program interprets a blank (space) as a comma, so that no blanks are allowed within atomic symbols.”
“LISP II will be able to handle both integers and floating point numbers, but in LISP I integers are not allowed. ... Numbers are brought into a LISP program by being defined within S-expressions, and they must always be quoted. For example, the following expression is correct, (SUM,(QUOTE,0.6),X)”
“Values of compiled functions are computed about 60 times faster than the S-expressions for the functions could be interpreted... After a function has been compiled, it can be used as if it had been defined, but of course it will run much faster than it would have as an interpreted expression.”

Observations on the Feeling of the Ugly and Insignificant

2011-02-17T10:32:00.000-08:00

vsm001 said...
I neglected to add my biggest objection to Louis's project, the lack of a strictly (or lazily) functional subset.

Louis told me he is planning on writing a book about interpreter implementation. I have offered to write prolegomena for any future meta-circularity, but Louis doesn't seem too keen on the idea.

Anyway...
vsm001 went directly to the meta-point of many of my posts: This is no way to go about designing a language.

BUT, I wanted to explore a particular issue in the design space of languages, not whether we should be in the space in the first place. In particular, let us assume some plausible rationale for inventing a language and then ask the questions that vsm001 raised.

vsm001 asked,
What are the characteristics of problems that Reason is well-suited to solve?

I'll rephrase this. What are the characteristics of problems that would be better solved by a language that has two complementary ‘modes’ of operation as opposed to a language in which a single mode suffices? In other words, neither of the two modes of Reason taken separately is quite powerful enough to be Turing complete, you really need both of them; under what situations would this provide an advantage over using a single, Turing complete mode?

Critique of Reason

2011-02-15T12:02:00.000-08:00

A language will not succeed without a good name. I have recently invented a very good name and now I am looking for a suitable language.
— Donald Knuth

Louis Reasoner is developing a new computer language. I'm letting him write this post.

“I have already done the most important part: the name of my language is Reason.

“The second most important thing is to come up with a trope. This will enable me to defend my language decisions with a pithy reply and call it a design philosophy. My trope is ‘reasonableness’. Reason will adhere to the philosophy of reasonableness. Anything in my language is, by definition, reasonable. Anything omitted is naturally unreasonable. Here is some more design philosophy:

Small is more reasonable than big.
Fast is more reasonable than slow.
Useful is more reasonable than useless.
Good is more reasonable than bad.
etc., etc., etc....

I'll generate more later.

“After the name and the self-styled philosophy, the next important thing is the syntax. The syntax of Reason is complicated, but reasonable. Bear with me. Although it might be a bit difficult to explain, it is, after sufficient practice, natural to use.

“Reason borrows heavily from Lisp and Scheme. Most of the programming in Reason is done in ‘Lisp’ mode. Lisp mode is exactly what you think it would be: you write programs just like you would in Lisp, but with a few modifications to make things more reasonable.

Prefix notation for everything by default, with these exceptions:
- Infix notation for arithmetic. — Let's just capitulate on this one. Operator precedence will be fleshed out later.
- Excess parenthesis are ignored where it is unambiguous. You can pretty much always add parenthesis to make something clearer or to override operator precedence.
- Function calls have the operator on the outside of the parenthesis. Not only is this more natural, it avoids weird interactions with operator precedence. Arguments are separated by commas.
- Postfix notation for post-increment and post-decrement. — I just like these.
No ‘special’ forms. We get rid of
- define — Lisp code tends to creep towards the right margin. Removing internal definitions makes the code ‘flatter’ and therefore easier to read. (Besides, it's hard to efficiently compile internal definitions.)
- begin — No good reason to include it.
- cond — Too many parenthesis.
- let — Again, too many parenthesis.
- lambda — This is just too advanced. Mere mortals can define a named procedure like anyone else would.
- letrec — As if lambda wasn't confusing enough! Who comes up with this stuff?
- quote — Too confusing. Actually, I wanted to leave quote in, but with infix and postfix in the mix I couldn't figure out where the quotation ended. I decided to punt.
Assignment is allowed. This is technically a ‘special form’, but it is so useful that I had to leave it in.

“Lisp mode is distinguished by its use of nesting as the primary means of combination. In fact, sequential combinations are disallowed. Lisp mode constructs are created compositionally from other Lisp mode constructs or primitives. Lisp mode is where most of the primitive procedures of the language are available.

“In order to radically simplify Lisp mode I had to introduce ‘Program’ mode. Program mode is more imperative than Lisp mode, so I tried to reduce the functionality and power of Program mode so that people would favor Lisp mode. Program mode has these features:

Special forms — Flow control, variable declaration and binding, conditionals, etc. are available in Program mode.
No artificially rigid syntax — Program mode is not really infix, prefix, or postfix. Each construct defines its own syntax. This improves readability for the built-in special forms. For example, the if construct can have a traditional else clause rather than just having two or three subconstructs like in Lisp.
No user-defined special forms — The user doesn't have to memorize any additional special forms beyond the built-in ones.
No arbitrary nesting — In Program mode, you can only nest a construct if the enclosing construct permits it. There is nesting, it is just controlled.
Concatenation for a means of combination — Lisp mode is obviously recursively evaluated. This isn't needed in Program mode because arbitrary nesting is disallowed. Instead, user constructs in Program mode are built by concatenation of Program mode primitives.
Easy switching to Lisp mode — You can always concatenate a Lisp mode construct with a Program mode construct. Originally, I didn't want to do this, but I ended up duplicating a lot of the Lisp mode functionality. By allowing the programmer to switch to Lisp mode pretty much whenever he wants, I avoided having to duplicate a lot of code.

“When you write a procedure in Reason, you start in Program mode. As I mentioned, you can switch to Lisp mode whenever you feel like it, but there is no way to switch back (this isn't strictly true, you can mimic the ability to switch back by use of a function call. The function body starts in Program mode.) You can define a procedure in either Program mode or Lisp mode. That is, you can explicitly mark a procedure as available in Program mode only or in Lisp mode only. Of course since you can always switch to Lisp mode, it makes no discernible difference if you define a procedure as Lisp mode only; you can use it in Program mode. But if you define a procedure in Program mode only, you simply cannot use it from Lisp mode. (It will be visible, you just can't call it.)

“I could go on for hours about how variables are looked up, but I don't want to bore everyone. I would like some feedback about my ideas so far, though.

How about it? Would any readers care to critique the design of Reason?

I whine too much.

2011-02-14T14:32:00.000-08:00

Mea culpa.

   ...
   for (Foo foo : permute(fooList)) {
        operateOnFoo (foo);
    }
   ...

  private static final Random rng = new Random();

  private static <E> List<E> permute (List<E> list) {
    List<E> answer = Lists.newArrayList (list);
    Collections.shuffle (answer, rng);
    return answer;
  }

More about shuffle.

2011-02-08T17:42:00.000-08:00

In my last post, I asked why
public static void shuffle(List<?> list) was given a ‘B’ grade. A few readers didn't see the problem, so I thought I'd clarify.

I was writing code to perform some operations on the elements of a collection. Multiple copies of the code will be running. I want to avoid having each copy being synchronized with the others, so it makes sense to iterate over the list elements in a non-deterministic order. This will not prevent multiple instances of the code from occasionally ‘colliding’ on a single object, but it will make this case the exception rather than the rule.

I originally wrote the code using a Set<Foo> rather than a List<Foo> because there is no natural ordering of Foo objects. The code looked like this:

    for (Foo foo : fooSet) {
        operateOnFoo (foo);
    }

where fooSet was an instance variable declared as Set<Foo>.

A Set is an unordered abstraction. Obviously, an iterator on a Set will return the objects is some order, but abstractly, there is no meaningful way to ‘change’ the order of the Set itself. A List, on the other hand, is an ordered abstraction that imposes a external order on the elements. (An array imposes the additional unnecessary constraints of compactedness on the indexes and random access.) Changing the instance variable from Set<Foo> to a List<Foo> was trivial.

The problem is now to ‘iterate pseudorandomly’. Pseudorandom iteration is not an uncommon operation, so I assumed there was a way to do it. Pseudorandom iteration is not common enough that a special iteration construct would be defined for it, so I assumed I would simply use a normal iterator and iterate over a permutation of the list. What immediately came to mind was something like:

    for (Foo foo : fooList.permute()) {
        operateOnFoo (foo);
    }

That doesn't work.

So Java doesn't provide a ‘permute’ method on a list. I vaguely recalled that Java had something called ‘shuffle’ rather than ‘permute’. However, the List class doesn't have a ‘shuffle’ method either. None of the methods on a List will permute it. That is strange because permuting a list is a fairly common operation.

I was sure that I had seen ‘shuffle’ somewhere, so I hauled out grep to search for some code that called it. I found some and chased down the documentation. The shuffle method is a static method in the Collections class. This means that I have to use a different syntax:

    for (Foo foo : Collections.shuffle(fooList)) {
        operateOnFoo (foo);
    }

That doesn't work.

The shuffle method mutates its argument but does not return a value. This means I cannot simply call the method as an expression, but I have to hoist the call to the nearest ‘Command’ level:

    Collections.shuffle(fooList);
    for (Foo foo : fooList) {
        operateOnFoo (foo);
    }

That works, but now I have to revisit my original design: is it OK to directly shuffle the fooList, or should I copy it first? Fortunately, I don't need a copy.

To recap, what I wanted to write was this:

    for (Foo foo : fooList.permute()) {
        operateOnFoo (foo);
    }

what I had to write was this:

    Collections.shuffle(fooList);
    for (Foo foo : fooList) {
        operateOnFoo (foo);
    }

By making shuffle ‘return’ void, the author has relegated the method to command contexts only. I happened to want to use it in an expression context.

I'm sure a lot of readers are wondering “So what?” It is in fact a trivial point, and now that I've discovered how to permute a list I doubt I'll encounter this particular problem in the future. But the point is that Java distinguishes between commands and expressions. You are prohibited from using a command where an expression is called for. However, you are permitted to use an expression where a command is called for. The programmer has to keep track of which things are commands because they require a command context. The programmer doesn't have to remember which things are expressions because they can be used in either context. By making shuffle a command, the author has added yet another item to my mental “remember these aren't expressions” list. If shuffle returned the shuffled list, I wouldn't have to think about it at all.

Arcane Sentiment noted that “ Java uses the return type as a way of declaring that the operation has side effects... ”. I guess I'm weird because I use the return type to declare the type of object that will be returned.

What's wrong with this?

2011-02-04T12:16:00.000-08:00

The java.util.Collections library has this method:
public static void shuffle(List<?> list)

Were this homework, I'd give it a solid ‘B’. Readers are encouraged to suggest improvements.

Replies to comments

2011-01-31T10:44:00.000-08:00

steck said...
Haskell type classes give a consistent interface to different kinds of numbers (among other things). Would that do here?

It would solve the problems with the built-in number hierarchy. Does Haskell allow you to add user defined subtypes to the built-in number types?

Jevon said...
Are you saying that we shouldn't develop using design patterns? No, there's nothing wrong with the pattern per se. I'm saying that if we have programming concept that is important enough and ubiquitous enough that we can identify it and name it (for example, “The Factory Pattern” or “Singletons”), then there should be a way of abstracting it so that the pattern is replaced by something much more lightweight, or, if possible, nothing at all.

You can't argue against Factory objects using Factorial as an example. That's like arguing against using Windows when you're using Notepad as an example.
Notepad might be an effective example for certain types of arguments. Factorial obviously shouldn't be encapsulated and turned into a first-class object, it's absurd. But the language does require that it be encapsulated in some kind of object, nonetheless.

Michael said...
Java is verbose, way too verbose in areas that should be concise.
True, but I'm not necessarily complaining about the verbosity. I'm complaining that there is no reasonable way to avoid, eliminate, or abbreviate the verbosity.

Hardware Critic said...
His point is that Java has created a culture where developers over-generalize (violating the en vogue You Ain't Gonna Need It principle) and create frameworks rather than customized solutions. You turned it on its side and asked "why should developers ever have to do this junk" and made it a criticism of the Java language.
Just so.

But in doing so, you take code decorated with "don't do this" and then point to it as an example of Java's failings.
You say "but what about the 1% of people who need all that extra nonsense?", but remember Mr. Woody's point is that developers should create bespoke solutions providing only the power necessary to solve the problem at hand rather than large general frameworks.

I don't think we are contradicting each other. Let's take the “Singleton” pattern as an example. Mr. Woody and I both agree that a Singleton would be an unnecessary complication to the factorial class, but we disagree on why. If you look at the Wikipedia article on singletons, you'll see that there are three examples of how to write singletons in Java:

// Examples taken from Wikipedia
public class Singleton {
 
    private static final Singleton INSTANCE = new Singleton();
 
    // Private constructor prevents instantiation from other classes
    private Singleton() {
    }
 
    public static Singleton getInstance() {
        return INSTANCE;
    }
 
}

// Solution suggested by Bill Pugh
public class Singleton {
 
   // Private constructor prevents instantiation from other classes
   private Singleton() {
   }
 
   /**
    * SingletonHolder is loaded on the first execution of Singleton.getInstance() 
    * or the first access to SingletonHolder.INSTANCE, not before.
    */
   private static class SingletonHolder { 
     public static final Singleton INSTANCE = new Singleton();
   }
 
   public static Singleton getInstance() {
     return SingletonHolder.INSTANCE;
   }
 
 }

// Modern way suggested by Joshua Bloch
 public enum Singleton {
   INSTANCE;
 }

All three are missing my point. They say, “The correct way to use singletons is to write your code like this.” What they ought to say is “The correct way for an implementation of singletons to behave is as if your code were written like this.”

A programmer who decides to use singletons (correctly or incorrectly) ought to be able to write something like:

public singleton FactorialUtil
{
    public static int factorial(int n)
    {
        if (n == 0) return 1;
        return n * factorial(n-1);
    }
}

Yes, it is stupid to do this for something like the factorial program, but it clearly states my (poorly considered) intention, was trivial to do, trivial to undo, and best of all, theoretically allows me to change the implementation of singletons from “traditional” to “Pugh style” without having to look at all the places singletons are used.

I'd have to post a much larger program and then spend time arguing the merits of singletons if I had to give a “real world” example.

Your point that Java requires significant boilerplate in order to say what needs to be said is valid, if not particularly novel. Even so, using code which was written in an intentionally convoluted way to criticize Java's convolution is like using the winner of the Obfuscated C Code contest to demonstrate that C is difficult to read.
It is hard to make concise arguments against convolution without needlessly convoluting a concise piece of code. A situation like this in real life usually involves a truly huge pile of awful code which makes the blog post far too large and contains many additional problems that hide the point I'm trying to make.

Jason Wilson said... The Development Chaos Theory article is largely concerned with factories. Factories are used all the time in Scheme and nobody ever complains because both the use and definitions are easy and natural:

USE:
((*factorial-function-factory*) 5)

POSSIBLE DEF:
(fluid-let (*factorial-function-factory*
(lambda (n) ....))

How *factorial-function-factory* got defined should not matter to the code depending on it. It's there. I promise. (Guice gives absolutely no more guarantees that it's defined and it is the best in class dynamic variable err, dependency injection framework for Java).

The Development Chaos Theory article is of course ridiculous for treating fact as a function that needs to be so abstracted, but without dynamic variables, this really is a necessary pattern in Java in many real world cases.
Exactly. There's just one refinement I'd suggest. (let ((factorial (make-instance <factorial-function>))) (factorial 5)) Object frameworks like CLOS provide a ‘universal factory’ generic function. And I'd suggest this definition of


<factorial-function>

(defclass <factorial-function> () (:metaclass singleton))

The definition of the singleton metaclass would contain code analagous to Bill Pugh's implementation.

But this doesn't answer Mr. Woody's objection that this is completely unnecessary. In that case, I suggest this alternative definition of


<factorial-function>

;; Unnecessary
;; (defclass  <factorial-function> () (:metaclass singleton))

(defmethod make-instance ((class (eql (find-class '<factorial-function>))) &rest initargs)
    #'factorial)

I have overloaded make-instance in this one case to not even instantiate an object but to return the factorial procedure as a natural singleton.

HowWhy (not) to write Factorial in Java.

2011-01-28T15:04:00.000-08:00

In “Development Chaos Theory”, William Woody laments the habits of bad Java programmers. I blame the language.

Before I start ranting, let me first say that I agree completely with Mr. Woody. If you haven't read his article, I suggest you do now.

Let's follow the example.

/** 
 * @author wwoody
 */
public static int factorial(int n)
{
    if (n == 0) return 1;
    return n * factorial(n-1);
}

This is presented as a typical way someone might write this in Java. I might have written it slightly differently:

public static int factorial(int n)
{
    return (n == 0) ? 1 : n * factorial (n - 1);
}

There is only a subtle difference between these. return, in its fully general form, is a non-local exit. It returns out of the enclosing method instead of out of the enclosing form. The difference becomes obvious if you attempt to manually inline the factorial method.

public static foo (int x)
{
    int y = (x == 0) ? 1 : x * factorial (x - 1);
    ...etc.
}

public static bar (int x)
{
    int y = if (x == 0) return 1;
            return n * factorial(n-1);
    ...etc.
}

Either way appears to be acceptable Java to me.

There should already be warning bells ringing. I have to admit that I didn't hear them the first time I looked at this code, though. I'm so inured to this crap that I missed a glaring problem.

Simplicio: Why do these methods have type declarations?
Salviati: Java doesn't do type inference.

Simplicio: Ok, that's lame, but why not just declare everything to be Object?
Salviati: Objects are too general. The * method doesn't work on them.

Simplicio: Of course! We want the most general type that supplies ==, *, and - operations. So let's use Number.
Salviati: Hold your horses, cowboy. Arithmetic doesn't work on Numbers.

Simplicio: What? Whyever not?!
Salviati: Arithmetic only works on byte, double, float, int, long, and short.

Simplicio: factorial should work on any of these. Why do I have to pick one?
Salviati: The semantics of these types aren't compatible. They behave quite differently at the very ends of their ranges. There is no way to unify them under a superclass and still preserve the subclass semantics.

Simplicio: umm... whatever. What about that static thingy?
Salviati: That doesn't matter. You aren't using any objects.

Simplicio: If it doesn't matter, why do I have to specify it?
Salviati: It would matter if you were using objects. It tells the compiler that free identifiers should have class scope. By specifying static, you're indicating that you want lexical scope.

Simplicio: But that doesn't matter because I'm not using any objects.
Salviati: Right.

Simplicio: If it doesn't matter, why do I have to specify it?

Then Mr. Woody wraps the method in a utility class:

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        if (n == 0) return 1;
        return n * factorial(n-1);
    }
}

and suggests an iterative implementation

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        int ret = 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}

Simplicio: Ummm....
Salviati: You don't want to know. In this case, we're not really using the class, but you'll want it later to avoid namespace conflicts.

Simplicio: I guess... Isn't namespace management is more of a configuration control issue than a datatype issue? Wouldn't I want these to be orthogonal issues?
Salviati: They can be handled orthogonally, but that requires some serious hacking. Right now all you want is a simple factorial problem, so just use the default.

Simplicio: What default?
Salviati: Just pick a name. Remember, though, the class name should be the same as the file name.

Simplicio: If it is the default, why do I have to do anything?

Mr. Woody now suggests that BigInteger is the right return type. We'll fix the code:

public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        if (n == 0) return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorial(n-1));
    }
}

alternatively...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

What we're seeing here is already serious problem. Changing the range of the output is a trivial change, yet it requires large changes to the code. Here we have the original code and the modified code with the changes highlighted.

// before changes...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static int factorial(int n)
    {
        int ret = 1;
        for (int i = 1; i <= n; ++i) ret *= i;
        return ret;
    }
}
// after changes...
/** 
 * @author wwoody
 */
public class FactorialUtil
{
    public static BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

Sometimes, when you are building a big system, you want to transparently install a far-reaching package. This doesn't happen often, but it happens more often than you might think. Take, for example, the scmutils library. This library augments the standard generic arithmetic in MIT Scheme so that the usual arithmetic operators can handle vectors, matrices, and functions in addition to integers, rationals and reals. No changes need to be made to the code that calls the arithmetic methods. This makes life a lot easier for developers who will not have to remember whether to use the built-in arithmetic or to switch to the extended package.

Mr. Woody now points out that one might want to memoize the answers.

/** 
 * @author wwoody
 */
public class FactorialUtil
{
    static HashMap cache = new HashMap();

    public static BigInteger factorial(int n)
    {
        BigInteger ret;

        if (n == 0) return BigInteger.ONE;
        if (null != (ret = cache.get(n))) return ret;
        ret = BigInteger.valueOf(n).multiply(factorial(n-1));
        cache.put(n, ret);
        return ret;
    }
}

To quote, “easy enough.”

Except it isn't. Memoization is a general technique that has nothing to do with the factorial program. Yet it isn't abstracted out of the problem. Tom White wrote an article on how to use Dynamic Proxy Classes to perform this abstraction. The code is a bit convoluted, but that doesn't matter because when all is said and done, we can just memoize that call to factorial.

That's the theory, anyway. It turns out that you'll need to build an interface to the factorial class and then memoize that:

/** 
 * @author wwoody
 */
public interface FactorialAlgorithm 
{
  public BigInteger factorial(final int n);
}

/** 
 * @author wwoody
 */
public class FactorialUtil implements FactorialAlgorithm
{
    public BigInteger factorial(int n)
    {
        BigInteger ret = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
        return ret;
    }
}

FactorialAlgorithm originalFactorial = new FactorialUtil();
FactorialAlgorithm memoizedFactorial =
   (FactorialProgram) Memoizer.memoize(new FactorialUtil());

That's better, but there's still a problem. All the places in the code where you used to call FactorialUtil.factorial(n) now need to change to use the interface instead: memoizedFactorial.factorial(n). And every caller has to have access to an instance of the dynamic proxy class at runtime.

Let's continue. Mr. Woody points out that we want to select which version of factorial to use at runtime. After all, we don't even need the BigInteger version if the actual data only contains single digit numbers. To do this, he suggests a factory class that can examine configuration data and instantiate the appropriate implementation. I won't bore you with the details.

Mr. Woody then asserts:

Sure, there are circumstances where a pluggable architecture would be desirable or even necessary—but that comes up so rarely it’s not even funny. About 99% of the time I see code like this, it’s completely and utterly useless. It’s obscuring the purpose of the code—replacing a two or three line utility (max!) with dozens or even hundreds of lines of self-important masturbatory Java bullshit. Sure, it may make you feel good—but it makes an ugly mess of it that future developers will have to clean up, or more likely just avoid like the plague.

Again, I want to stress that I agree with Mr. Woody and I'm not attempting to argue against him. And here I'd like to interject and raise a point. What about the rare situations? About 1% of the time you really do want a pluggable architecture, and code like this is not completely useless. The problem is that you still need “dozens or even hundreds of lines of self-important masturbatory (but necessary) Java bullshit.” Since there is a need for a pluggable architecture, you can be sure that future developers won't be trying to clean it up. Unfortunately, that leaves “avoid like the plague” as our option.

Mr. Woody says:

The biggest complaint I have with many Java developers is that they develop a whole bunch of really bad habits. Specifications are unclear, or they think someday the code may need to be extended into a different direction. So they write a whole bunch of overblown architectural nonsense, sight unseen, thinking that the additional crap someday will help out and make things easier.

But how does this differ from the case where the additional crap really does make things easier? The code doesn't change simply because it becomes more useful. It is still a whole bunch of overblown architectural nonsense. The only difference is that you are forced to use this crap because it is the only way to get things done when the simple solution is insufficient.

My complaint with Java is that it tends to exacerbate a bad situation. Small conceptual changes to code, like changing an int to a BigInteger, end up being large textual changes. Larger conceptual changes, like adding a Factory object or a dynamically pluggable implementation, cannot be abstracted out. This leads to big piles of additional crap that have to be replicated all over the place. The language is unfriendly to change and modern software development is all about managing changes to the body of code.

A day in the life

2011-01-28T11:00:00.000-08:00

I seem to have a career as a professional software engineer. Don't get me wrong, I love doing it, but somehow my avocation became my vocation. C'est la guerre.

Last night I was thinking about what my job really entails and it is a bit different from what I usually think and tell people. The exciting part is taking a poorly formed concept, refining it to a very detailed and well-formed formal concept, translating the ideas to software, and making a tool or service that people can use. There is a tedious part, too. Frankly, I don't find it too monotonous because it involves a lot of puzzle solving and finding creative solutions, but it is necessary work that doesn't seem logically necessary, and that tends to dampen my enthusiasm for doing it.

I spend a lot of time just “plumbing”. There is a lot of infrastructure where I work. In all the projects I've worked on, the vast majority of the code has already been written. So the very first phase of software development is identifying the infrastructure subcomponents that the project should depend upon. This is pretty easy to do. Any basic project will always have these components:

A web server front-end with the following properties:
- Automated load balancing.
- Automated failover.
- High availability.
- Resistance against DOS attacks.
Persistent storage or a database with these properties:
- Geographically separate replicas.
- Regular backups.
- Tools for manual editing and revision of stored data.
Software attendants to keep it running ‘unattended’.

My current project involves selling things (like all businesses need to do on occasion). There is infrastructure to handle purchases, refunds, deal with fraud, etc. We'll also need some more infrastructure to handle user authorization and authentication. And I didn't mention the infrastructure needed to deliver the purchased items. When it all comes down to it, there isn't a whole lot of logic involved in the project itself. Almost all the functionality comes from the underlying infrastructure. Our team spends a lot of time plugging it together. That doesn't mean that it is easy or that it doesn't involve any creativity.

I've found on most projects I work on that there is always some piece of software that I intend to use but I have only very vague ideas about how it might work. My task might be to hook it up.

Of course I spend several days thoroughly reading and understanding the copious documentation.

This is what I really do: I know that the end user is going to be sitting in front of his web browser and at some point click on something. This will eventually trigger a method call that performs the requested operation. Let's assume the user wants to buy something and that the mouse click the user made was the last one before the purchase (the one that asks “Ok to charge your credit card?”). What can I deduce?

There ought to be a method that ultimately handles the ‘purchase’.
Since buying something must be a very common operation, I expect there to be some easy way to charge the user's credit card.
1. I first look for the ‘quick start’ guide or the FAQ.
2. If I can't find an answer there, I look at the table of contents of the detailed documentation.
3. A lot of the time there isn't any documentation or if there is, I can't find it. The end result is the same. If there is no documentation, then I think whether there are similar projects that might want to use the same infrastructure in the same way. I'll eventually find some code that actually works.
4. Now comes a trick. I sketch out in my head a few possible protocol designs. There should be a way, given a user and an item, to “begin” the process of purchasing. There should be a way to determine if the process has completed. There should be a way to determine the outcome of the process. Each of these mechanisms should exist as separate calls because we might have to re-do any part of the process if the computer crashes during the purchase. But since the usual case will involve rapid turnaround and no crashes, there should be an abstraction that handles the entire process from end to end. I poke around in the docs and in the source code to see if these things exist.
5. Now I analyze what I've found and make a guess at the sophistication of the design and the programmer. If I see an API that involves continuation-passing style or a variant (Java callbacks are poor-man's CPS), then I expect a high level of sophistication from the API. I expect there to be a ‘standard’ way of purchasing something and I expect that all the edge cases are handled in a reasonable way. Why? Anyone that successfully uses a complex concept like continuation-passing style has most likely applied a lot of serious thought to the API.
6. On the other hand, if I see an API that involves a lot of methods that return void and must be called in the right order or they won't work, or an API with ambiguous methods like checkPurchase() and validatePurchase() (which one do I use?), or one where the arguments must be strings that will then be parsed to something that makes more sense, or APIs that throw only a single catch-all error (or just return null on success or maybe null on failure), then I expect that I'm going to have to think hard about all the edge cases myself and I'm going to have to wade through a lot of examples to determine the right ‘magic’ Why? People that write APIs like this aren't thinking. They code up the first solution that comes into their head and when they are done, they call it an API. It is likely that they either didn't think there were edge cases, or it didn't occur to them that they should abstract them away.
So I finally determine what methods need to be called. I look at the argument lists of the methods and I look at the arguments passed in to the servlet. These are generally isomorphic in some way, but it is typically the case that the servlet is being passed a string representation and the underlying method needs an object. If the API isn't completely idiotic, it will provide parsers and unparsers for the data that represent major concepts. So the servlet might get a string that represents a user and a string that represents what he wants to purchase. Now I have to figure out how to call the method.
1. If the API is well designed, there might even be a method that takes the strings directly from the servlet and does all the work including checking inventory and scheduling order fulfillment. This is the rare case.
2. If the API is pretty good, then I'll probably have to make the appropriate calls to parse the servlet arguments to actual data, handle errors, and validate the input. Then, with the parsed arguments in hand I can call the purchase method.
3. If the API is lame, then after the argument parsing I'll have to check the database to see if there is inventory and somehow reserve it. Then I'll run the purchase methods (which will not be unified into one abstraction, but consist of five methods that need to be called in the right order). Then I'll have to see if the purchase succeeded, and if not, return the reserved item to inventory, or if it did, arrange for the item to be delivered.

So how do I know how to use the API if it is undocumented? The simple answer is this: look for methods that have the same type signature as the objects that are at hand in the servlet. There probably won't be very many. Now look at the names of the methods and see if any make sense. The easyPurchase(User user, Item item) seems a lot more likely than the getReceipt(User user, Collection items). A really good API uses names that practically shout out their purpose.

Finally I try out the code and see if it works. If it does, I call it day. If not, then it is time to twiddle, tweak, and frob things. If the API is good, then I'll get informative error messages that tell me what I did wrong. Something along the lines of “Error: user id is an email address, did you forget to call parseUser()?” instantly tell me what I'm doing wrong. Something along the lines of “null pointer exception” followed by a stack trace filled with methods I never heard of before now tell me nothing whatsoever.

This is work. It isn't extremely difficult, but it does require practice, skill, and imagination. It also isn't really engineering. It is more like plumbing. Get this stuff here and put it over there, and you might need an adapter fitting.

A bit of history

2011-01-24T15:00:00.000-08:00

The computers of the 50s were very primitive machines. The IBM 704, for example, had 4096 words of ferrite core memory (later expandable up to 32768 words) with an access time of 17 milliseconds. The Central Processing Unit, which was not a monolithic silicon chip, but a cabinet full of vacuum tubes, could execute 40 thousand instructions per second (twenty-five microsecond basic execution cycle).

It cost $50,000 a month just to rent one. (That's more than $4 million a year in today's dollars). And this was one of the most advanced machines available at the time. These days, the level 1 cache control would put this kind of power to shame.

The computer languages at the time were bizarre to say the least. Of course no one at all had any experience programming, let alone designing languages to make programming easier. The conventional wisdom at the time was that ‘information processing’ required an approach that differed fundamentally from ‘numeric calculation,’ so people tried out all sorts of weird ideas. One idea was string processing. The COMIT language was one of the earliest string processing languages that was based around the idea of rewrite rules. It is sort of like sed on acid:

(8             PROGRAM TO BRING IN A NUMBER OF CONSTITUENTS AND PRINT OUT-
               ALL OF THE N FACTORIAL PERMUTATIONS OF THEM)
                       (PROBLEM SUGGESTED BY B. ULVESTAD)

INPUT                                $ = Q + 1 + N       //*RSA1              INPUT
*                                    N = QL + QR/.1                               *
NUMBER Q + $ + $1 +  QL +  $ + QR  + N = 1 + 2 + 4 + 3 + 5 + 7/.*6 + 6/.I1   NUMBER
*              Q + QL + $ + N + $ + QR = 3 + 2 + 6/.1 + 4 + 5                     *
PRINT                          $1 + QL = 2 + 1          //*WAB2               PRINT
*                 QL + $ + $1 + QR + N = 2 + Q + 3 + 1 + 5 + 4                    *
PERMUTE $1 + Q + $1 + $ + QL + $ + QR + N = 3 + 2 + 4 + 1 + 5 + 6 + 7 + 8/.D1     *
TEST               QL + $ + QR + $/.G0 = 1 + 3 + 2 + 4                       NUMBER
MOVE               $1 + Q + $ + QR + 1 = 2 + 1 + 3 + 5 + 4                  PERMUTE

Yngve, Victor H. 1958. “A programming language for mechanical translation.” Mechanical Translation 5 (1). 25-41

The information processing language, IPL, on the other hand is more like assembly code with linked list support:

            COMMENTS                TYPE  NAME  PQ  SYMB   LINK

Type-9 card                          9
                                     1
Type-2 cards define regions.         2     A                1
The B-Region consists of             2     B                1
 one cell, named "B0" or just "B".   2     I                1
                                     2     L                2
The R-region has 2 cells,            2     R                2
 named "R0" and "R1".                2     v                1
                                     2     (                1
                                     2     )                1
Type-1 cards are for comments.       1
                                     1
Type-5, Q=1 says "DATA FOLLOWS."     5           1

L1---(AI(A v B))                          LI        0
                                                    (
                                                    A
                                                    I
                                                    (
                                                    A
                                                    v
                                                    B
                                                    )
                                                    )        0

Type-5, Q=blank says "ROUTINES       5
 FOLLOW."                            1
                                     1
R1 prints the list L1.               1
                                     1
Q=3 says "TRACE THIS ROUTINE."            R1     13 L1
                                                    J151    0

P or Q = 0 can be left blank.

Type-5, SYMB=R1 says execute R1      5              R1

Correspondence between Hugh S. Kelley and Chuck Baker.

These languages differ from INTERCAL in that their designers were serious.

A notable exception was the language ALGOL.

begin integer i; real y; real array a[0:10];
   real procedure f(t); real t; value t;
     f := sqrt(abs(t)) + 5*t^3;
   for i := 0 step 1 until 10 do read(a[i]);
   for i := 10 step -1 until 0 do
     begin y := f(a[i]);
           if y > 400 then write(i, "TOO LARGE")
           else write(i,y);
     end
   end

(taken from Wikipedia article on the Trabb Pardo-Knuth algorithm)

ALGOL doesn't look unusual to the modern eye. That in itself is testimony to the fact that ALGOL was years ahead of its time. As you can imagine, though, it was well beyond the capability of most computers to compile and run an ALGOL program.

When McCarthy started the “Advice Taker” project, he proposed a new language LISP that would be based around the linked-list paradigm of IPL and the λ-calculus of Alonzo Church. One of the goals of the language was to deliberately move away from the Turing-inspired mechanistic model of computation (Turing machine) and towards a more mathematical way of programming based upon recursion. (Incidentally, ALGOL was designed to support recursion, but the very first ALGOL implementations punted because it was too complicated to support and users didn't know how to use it.)

Fifty Years Ago

2011-01-19T12:50:00.000-08:00

The character-reading functions make it possible to read characters one by one from data records. The choice of input medium is determined by sense switch 1, though at a future time mode-set facilities may be added so that input may be taken from any medium. This description will be given in terms of hollerith cards [sic] as input; the procedure for tape is completely analogous. However, the tape records must be 72 characters long.

Paul Abrahams, Artificial Intelligence Project
RLE and MIT Computation Center Memo 22a
Character-Handling Facilities in the LISP System

In the months following McCarthy's initial description of ‘A Symbol Manipulating Language’, Steve Russell translated McCarthy's eval into IBM 704 machine code and the first LISP was born. By 1961 the implementation of Lisp 1.5 was well under way and a number of new libraries were being written.

Hollerith cards were the main input medium in those days. They were a step up from punched paper tape, though. In fact, punched cards were pretty much the only input medium until online input became available.

Paul Abrahams, personal correspondence

Lisp had read, eval, and print, but the computer itself was shared by the MIT Community. You would submit your card deck for processing and come back some time later to get the printout. The REPL was run in batch mode.

Answers for Faré

2011-01-18T09:04:00.000-08:00

Faré said...
Problem is that indeed you need to do something about those slots without keyword initializers, slots that are computed from other slots (e.g. hash values), slots that are initialized from a counter (e.g. OID), slots that are actually plumbing from a larger structure (e.g. indexes back into other objects), etc.

You would think so, but it turns out you don't.

When an object is created for the very first time, you must have already written code to deal with slots without keyword initializers, slots computed from other slots, slots that are initialized from a counter, slots that are plumbing, etc. or you wouldn't have been able to create the object. When the object is re-instantiated from the persistent store, there is no reason you cannot simply perform those operations (mutatis mutandis) again.

But what if these operations are not idempotent? Actually, we already know they are not. Each time we call the constructor, we ought to be getting a brand new object, so we don't want the operations to be idempotent. But note that the object is constructed exactly once per ‘session’ — the constructor is never called twice without dropping all references to the constructed object in-between the calls. Therefore, it is not possible to ever observe two separate calls to the constructor. (By ‘observe’ I mean, “You cannot write an extensional program that returns 0 if exactly one call to the constructor occurs, but returns 1 otherwise.“)

Certainly one could, through reflection and other mechanisms write code that intensionally exposes the implementation, but one can always write code that deliberately breaks an abstraction barrier. Although it seems far too easy to break this abstraction barrier by something as mundane as computing a slot value from other slots, in practice it turns out that you won't want to. Again, this can be derived from an information-theoretic argument. At the point of invoking the constructor, the program has provided all the information necessary to correctly initialize the new instance. Any other information used is, by definition, ‘implicit’.

Let us assume, for a brief moment, that the implementation depends critically upon the implicit part of the initialization process. I simply argue that critical dependence upon implicit information is a serious bug, regardless of whether persistence is brought into the picture or not. If the implicit information is designed to be implicit, then the onus is upon the designer to hide the implicit dependency well enough that the client code need not be aware of it.

So let us assume the opposite: the implementation does not depend cricitally upon the implicit part of the initialization process. Well, if there is no critical implicit dependence, there are no bugs that occur because of a critical implicit dependence.

The approach still works, but is actually very low-level, and calls for a higher-level interface of some sort, lest your whole system keep a very low-level feel.

Not at all. In ChangeSafe, the abstraction of a versioned object is built directly upon the persistent object abstraction by layering yet another set of MOP customizations on the existing ones that implement persistence. There is no higher-level interface beyond the normal CLOS interface, yet there is very little code that needs to have explicit calls to the persistence API.

I doubt these arguments will persuade anyone, so I suggest trying to implement things this way and seeing for yourself.

And this reminds me of another thing. Earlier you asked why ‘pointer swizzling’ was performed on reading rather than upon loading of the persistent object. I mentioned a few reasons, but I forgot one really important one: it allows you to build persistent circular structure without needing mutable objects.

Some Bells and Whistles

2011-01-13T10:18:00.000-08:00

There are a few bells and whistles that I added to my persistent store. The first is multiple extents (that is, more than one persistent store open and participating in a transaction). This is fairly easy to add. The only tricky part is ensuring that a transaction that involves multiple extents either fully commits or aborts across all participating stores. The way I chose to implement this is by choosing a single particular persistent store to be the transaction master. The commit record in the transaction master is the one that holds the authoritative record of whether the entire transaction has committed.

The commit proceeds in two phases. In the first phase, each non-master store performs a ‘conditional commit’. This involves flushing the pending writes to the backing store and writing a special commit record that refers to the transaction master. Once each non-master store has written the special commit record, the commit record is written to the master store.

If nothing unusual happens, processing may continue as in the normal case. The interesting thing happens when the non-master store is first opened. If the most recent commit record in a store is a ‘conditional commit’, then it is necessary to check the transaction master to see if it committed. Typically, the relationship between the different stores is that there is one master and one or more ‘satellite’ stores. Therefore, it is likely that the transaction master is already open and within a transaction when the satellite store is opened, so the master commit record will be easily at hand. If not, then the code recursively opens the master store to determine if the conditional commit of the satellite is valid. This adds a little amount of bookkeeping to the commit code, but it isn't particularly complex.

Nested Transactions and Multi-version Concurrency Control (MVCC)

My original plan had been to avoid the complexities of nested transactions and MVCC. I designed this as a simple store, and I figured that a good number of applications would not need nested transactions. I discovered almost immediately that I was wrong. If nested transactions are disallowed and a procedure needs to start a transaction, it has to determine whether an existing transaction is in progress. If it is not, then the procedure needs to begin the transaction and ensure it is committed when it exits. On the other hand, if there is an existing transaction, the procedure should ‘join’ that transaction and let whoever started the transaction decide whether or not to commit. This isn't so bad if you can segregate your procedures into ‘top-level’ (ones that always start and commit a transaction) and ‘subroutines’ (ones that never start and commit a transaction, but expect there to be one in place before being called). Unfortunately, recursive procedures cannot be in both categories simultaneously. A possible workaround is to have duplicate code tailored for each use case, but then the programmer would have to remember which version to call under which circumstances, or we'd have to avoid using recursion. Since this is clearly unacceptable, I bit the bullet and implemented nested transactions.

With the current design, nested transactions turn out to be pretty simple. When a non-nested transactions starts, it gets a copy of the most recent object-map which it uses for OID resolution. When a nested transaction starts, it gets a copy of the current object-map from the immediately enclosing transaction. The nested transaction gets to see the intermediate state of the enclosing transaction. If the nested transaction commits, it does not write a commit record to the store. Instead, the object-map from the nested transaction is used as the object-map of the enclosing transaction when control is returned. Thus the enclosing transaction gets to see the state that the nested transaction committed. When the enclosing transaction commits, the object-map (which includes the nested transaction updates) is written to the store and committed.

If the enclosing transaction aborts, the nested transaction state is simply dropped on the floor and becomes inaccessible. The interesting question is how to handle the case where the nested transaction aborts. In this case, we return control to the enclosing transaction, but we discard the object-map from the nested transaction. The enclosing transaction therefore sees no effect at all from the nested transaction. The enclosing transaction has the opportunity to itself abort (in which case all the intermediate state is discarded), to commit (in which case only the effect of the enclosing transaction is made permanent), or to perhaps continue processing and begin more nested transactions.

In effect, nested transactions act like software transactional memory.

At this point, one can see how MVCC can be easily implemented. Each concurrent thread runs its own transactions with its own object-map. Since all OID resolution is performed against the object-map associated with the current (thread local) transaction, each concurrent transaction sees only its view of the persistent store. (This is a necessary condition, but it is not sufficient. We have to ensure that committed transactions can be given a serial order to preserve the isolation between transactions. We do this by recording in each transaction the OIDs of every persistent object read and written within the transaction. When the transaction attempts to commit, the set of reads and writes is compared against the set of objects read and written by any other parallel transaction that has committed since this one started. If there is an overlap, we abort. That is, we use optimistic locking.)

(This should answer Fare's question about why OID resolution is performed on each read rather than being done just once when the store is opened.)

These features involve adding a good chunk of bookkeeping code, but the code is straightforward, albeit tedious. Good testing code is vital to ensuring that this all works as it should.

Schema evolution finessed

2011-01-07T16:46:00.000-08:00

Schema evolution is the bête noire of the object-oriented database world. It is probably the most labor intensive and error prone activity that an end-user is likely to attempt. The root problem is that the metadata about persistent objects is implicitly replicated in several ways.

The big advantage of object-oriented databases is that they unify the query language with the ‘business logic’ language. You access and navigate persistent objects in the exact same way you access and navigate the ordinary data structures in the language. The obvious benefit is that the mechanisms of persistence and querying are hidden behind the object abstraction. But this means that the definition of the data structures are performing double duty. Data structure definitions are used by the compiler to generate the appropriate primitive operations in the code, but they also are needed by the database component to generate the persistent representation of objects. If the data definition changes, objects that conform to the old definition will no longer work.

Programmers generally expect that a recompile is all that is needed to change how a program handles data structures. But if the data definition is used by the database for object storage and retrieval then changing the data definition may change the persistent representation and make it impossible to retrieve data. (Or worse, it could silently retrieve the data incorrectly.)

It turns out that if persistent objects are immutable then there is a way to finesse the issue of schema evolution.

In CLOS, objects are created and initialized when the programmer invokes make-instance. There is a well-defined series of operations that take place and the resulting object is returned to the caller. The important thing here is the intent of the programmer. The arguments given to make-instance contain the specific information that the programmer has determined is needed to correctly initialize the object. The returned instance will depend on the argument values and any default values that are supplied in the class definition. From an information theoretic view, the argument list to make-instance and the resulting instance ought to contain the same information. So rather than attempting to persist the resulting instance, we instead persist the argument list to make-instance.

The immediate objection to this is that there is no way to know what on earth make-instance constructed! It could be the case that make-instance decides to return NIL. There could be a very complex initialization protocol that defaults certain slot values and computes other slot values from the initargs. This doesn't matter. The programmer is working at the abstraction level where the entire process is kicked off by the invocation of make-instance, and thus his intent is simply to create an instance of an object that is parameterized by the given initargs.

When we retrieve an object from the database, we don't attempt to retrieve the representation of the constructed object, we instead retrieve the arguments that were handed to make-instance and simply invoke make-instance again to re-create the object.

Now suppose that we have a database where we are modeling automobiles. Let us assume that we have already stored thousands of automobile instances and that each instance contains, say, the number of doors and the color of the automobile. At some point we decide that we no longer care about the number of doors, but we do want to know the make and model of the automobile. We change the definition of the automobile class in the program. When we invoke make-instance, we now have a different set of initargs. However, the legacy objects in the database are reconstructed by calling make-instance with the old argument lists. This is easily dealt with. The older argument lists will have initargs describing the number of doors and the color of the car. We arrange for make-instance to ignore any initargs that are unused, and we require the programmer to supply ‘reasonable defaults’ for initargs that are not supplied. Thus when retrieving an older object, the count of the number of doors will be ignored, and a default value will be supplied for the make and model.

Note that we no longer require a schema to describe the layout of objects in the database.

There are drawbacks to this strategy. First, we are making the assumption that all the relevant information for object creation is supplied in the call to make-instance. A perverse programmer can easily bypass this assumption. However, it doesn't seem unreasonable to require that programmers either use the object creation protocol in the intended manner, or to specifically arrange for auxiliary helper objects to be created that hold any missing relevant information. This is meant as a tool for programmers, not as a fool-proof system. (Incidentally, the full-blown system I wrote allows the programmer to declare certain slots as transient. This allows a programmer to cache information needed for the runtime without forcing the information to be persisted.) Second, we give up the ability to side effect persistent objects. (As I have noted in previous posts, we can mimic side effects reasonably easy.)

These disadvantages are minor compared to the difficulties of schema evolution.

I'm happy to answer questions about this.

EQL Specializers

2011-01-04T11:50:00.000-08:00

Pascal Costanza asked an interesting question: Why are EQL specializers convenient for smooth integration with object instantiation?

My original answer was simply that when you want to customize make-instance for a particular class of objects that you end up writing methods like this:

  (defmethod make-instance ((class (eql (find-class 'foo))) ...

This is doable without EQL specializers, but it would be kludgy.

While thinking about this some more, though, it occurred to me that EQL specializers are probably a necessary element for reflective programming.

When you reflectively program the object system, you operate at a meta-level where abstractions such as classes are reified as concrete instances of a meta-class. At the reflected level, object instances are no longer the data being manipulated. Instead, object classes are used to represent sets of instances, and the classes themselves are represented by instances of meta-class objects.

When you cross abstraction levels in this way, you need a set of level-shifting primitives. One of the most important of these is quotation. Quotation is level-shifting primitive that lifts (injects) an instance from beneath the abstraction level to the level itself.

In CLOS, EQL specializers are the quotation mechanism for method dispatch.

Side effects

2010-12-20T11:29:00.000-08:00

Before continuing on with transactions I want to describe how side effects are implemented. Objects in the persistent store are immutable, so we really cannot modify an existing object. We can, however, allocate a brand new object that differs from the old one only in that the ‘side-effected’ fields have different values from fields in the original object. We'll enter this new object in the object-map, but instead of assigning it a fresh OID, we'll re-use the OID from the original object as well.

The object-map, as you may recall, is also a pure functional object. Adding an entry does not mutate any part of the object-map but instead makes a new object-map that shares as much structure as possible with the old one. Any OID dereferencing that happens under the old object-map will continue to see the original object with its original contents. Dereferencing an OID under the new object-map will see the new version of the object with the ‘modified’ field. We mimic side effects by creating a whole new world where everything is identical to the original except for the thing that appears to change.

Normally, one would expect that creating a new world every time you wish to mutate an object would be prohibitively expensive. But since the objects and the object-map itself are immutable, we can re-use them freely. This makes it reasonably efficient. Creating a new world takes time proportional to the logarithm of the number of objects persistently stored. Even having a huge number of objects adds very little time and space overhead to simulate mutation.

You may think this is an awfully roundabout way to do something simple. After all, why not do the traditional thing of simply maintaining a snapshot of the current consistent state of the world and actually mutating it? This would require modifying the logging strategy slightly. A special mutation record would have to be written to the log to echo the mutation being performed in memory. If the machine crashes, the log could be read forward to re-do the mutations that were in progress at crash time. Alternatively, it could be read backwards to undo the mutations that ought to be undone if the transaction didn't commit.

The rationale for this roundabout solution is simplicity. It is hard to make transactions work correctly every single time given the fact that a hard failure can occur at any moment at all. Use Google to search for “transaction bug” and take a look at how easy it is to make subtle mistakes. By making it impossible to mutate existing persistent store records and indexes, we guarantee that bugs in the transaction layer simply cannot affect earlier, successful transactions. Cleanup and recovery of the persistent store remain as easy and trivial as before: we simply find the most recent valid commit record. There are no undo or redo logs to process. The transaction algorithm can be proven correct by inspection.

Once we have ‘mutation’, we'll need to ensure that we can maintain consistency when we use it. We want the persistent store to behave as if the mutations had some serial order to them. We augment each transaction object with some more bookkeeping information. Each transaction must record which objects it dereferences, allocates, and ‘mutates’ before it commits. We'll also add a transaction manager object which examines transactions before they are committed to determine if a serial ordering can still be computed. If there is a single thread performing transactions, then a serial ordering is virtually guaranteed. But if multiple concurrent threads run transactions in parallel, we have to make sure that each transaction runs in isolation from each other, and that the sets of locations read and written do not intersect with other transactions. If the transaction manager finds a conflict, it aborts one of the transactions.

Again, we note that this implementation can easily handle conflicts because it is very simple. Aborting a transaction is easier than committing it. You simply discard the transaction and you don't write a commit record for it. Allowing transaction to proceed and only checking for conflicts at commit time is an ‘optimistic’ strategy. In many situations an ‘optimistic’ concurrency strategy can perform better than a ‘pessimistic’ one. With a slight change it is easy to go to a ‘pessimistic’ model. In a pessimistic model, conflicting transactions are detected when a field is mutated. If the mutated field has been read within another transaction, then the other transaction may be working with stale data if it commits before this one. A pessimitic model is slightly simpler to understand because you check the validity of each operation just before performing it. However, an optimistic model performs very well if concurrent changes to the exact same objects do not often occur.

While trying to bring this code back to life I encountered two bugs in MIT/GNU Scheme. The first was a bug in a rare corner case of structure definition. The second was caused by the fact that the floating point layout changed between the 32 and 64 bit releases. I've fixed these, but I have a more interesting problem.

The MIT Scheme object system, SOS, is derived from many of the ideas in Tiny CLOS. It is missing, however, a fully functional MOP. In addition, method dispatch is done only on the types of arguments. This makes it tricky to do ‘EQL specializers’. EQL specializers are necessary to smoothly integrate object instantiation. You can work around this limitation in some ways, but it would be much better if the implementation had this as a built-in feature.

Transactions, part I

2010-12-17T09:42:00.000-08:00

Faré has persuaded me to post actual working and tested code. It seems that enough has changed since I switched computers and the code that was working is working no longer. (The problem has nothing to do with my code — a shared library referred to by Scheme seems to have moved and Scheme came crashing down.) I'll get things working and show the live code. Until then, we'll have to make do with illustrative code fragments.

Given the index structure I described over the past two days, you can easily see that we have solved the problem of internal and external references. We use OIDs as a sort of ‘pointer’, and we modify the access mechanisms to hide the redirection. An analagous modification to make-instance gives us aggregate objects by initializing the instance slots with the appropriate OIDs.

The next thing to deal with is transactions. These are very easy to implement using this design. We have provided no mechanism to rewrite any data in the backing store; it is opened in append-only mode. When we augment the object-map to associate new OIDs with new objects, we construct new object-map nodes and append them to the backing store, but we do not modify any existing object-map nodes. If we were to ignore the new object-map and re-use the old one, we would not be able to access the new objects. The entire object graph would appear to us as if time had stopped at the point when the old object-map was created. This is the key to implementing transactions.

When we begin a transaction, we create a transaction object and copy the most recent object-map root node to it. As we create objects we update the transaction object with augmented object-map. If the transaction fails, we simply discard it. The next transaction is initialized with either the new object-map (if the prior transaction committed) or the old object-map (if the prior transaction aborted). There is no need to ‘undo’ anything because persistent objects cannot be mutated.

When the computer shuts down (either by a crash or planned outage) and is restarted, we use the information in the backing store to restore the state of the program. We need to find the most recent, but valid, root of the object-map. Since we cannot plan crashes, we might find objects and object-map nodes at the tail of the backing store that were written by a transaction that was in progress when the crash happened. We want to ignore these because they represent intermediate state. The trick is this: when a transaction commits we append a special ‘commit record’ to the backing store. The commit record will contain the location (within the store) where the root node of the object-map is stored. When the process restarts, it scans the backing store to find the latest valid commit record and it initializes from there. Any objects that were allocated after that commit record are simply ignored.

If transactions usually commit and the computer rarely crashes, then the most recent commit record will usually be the very last record in the backing store. If the computer crashes a lot, or if transactions are usually aborted, then it is likely that the backing store would accumulate abandoned objects. One could develop a way of reclaiming that storage.

Here is an actual commit record:

((:commit-record-starts)
 (:record-format 0.4)
 (:timestamp 3331389370)
 (:object-map-offset 5971200)
 (:previous-record-offset 5970432)
 (:reason "Update user context.")
 (:commit-record-ends))

The commit record has start and end markers so we can identify incomplete commit records. The object-map is at location 5971200 in the backing store, and the previous commit record is at location 5970432. (For extra safety, the commit record should contain a CRC or hash of the object-map. It should probably contain a CRC or hash of itself in order to make it self-validating. Or you can punt.)

The :reason is just a string. It is not used for anything, but it is extremely important nonetheless. The :reason gives us an audit trail in the event of a catastrophic failure. This is part of the “belt and suspenders” safety mechanism. The backing store may kept for a long time, perhaps even many years. Although we will protect the data with multiple mechanisms to reduce the probability of simultaneous failures, our last line of defense is to manually inspect the backing store records. The :reason field will make this much easier.

Ok, now for some code to illustrate. The actual code has a number of bells and whistles, and I'll show them later, but it is best to start with a stripped down version.

(defconstant *transaction-dispositions*
  '(:running :committing :aborting :committed :aborted))

;; running = transaction should commit upon return,
;;           but abort if a throw occurs
;;
;; aborting = transaction is still running, but it must abort upon exit
;; committing = transaction is still running, but it must commit
;;              upon exit, even if throwing
;;
;; aborted = transaction is over, it aborted
;; committed = transaction is over, it committed
(deftype transaction-disposition () `(member ,@*transaction-dispositions*))

(eval-when (:load-toplevel :compile-toplevel :execute)
  (defvar *current-transaction*)
  (setf (documentation '*current-transaction* 'variable)
        "The current transaction.  Not bound if we are not in a transaction."))

;;; Transactions
(defclass transaction ()
  ((disposition :accessor transaction/disposition
                :initform :running
                :type transaction-disposition)
   (reason      :accessor transaction/reason
                :initarg :reason
                :initform "Unknown"
                :type string)
   (object-map :accessor transaction/object-map
               :initarg  :object-map)))

The code for running a transaction is conceptually simple, but the bells and whistles obscure the simplicity. I'll present a stripped-down version first and then show the full version in a later post.

(defun call-with-transaction (pstore reason receiver)
  (let ((transaction   nil)
        (normal-return nil)
        (abort-reason  "Non-local exit from call-with-transaction."))
      (unwind-protect
          (progn
            ;; This is the only place that transactions are created.
            (setq transaction
                  (make-instance
                   :object-map (persistent-store/object-map pstore)
                   :reason reason))
            (multiple-value-prog1
                (let ((*current-transaction* transaction))
                   (funcall receiver transaction)))
              (setq normal-return t)))

        ;; If the transaction is null, we never even got started.
        (unless (null transaction)
          (ecase (transaction/disposition transaction)
             ;; If we return normally and no one decided to commit
             ;; or abort before now, we commit.
            (:running (if normal-return
                          (transaction/do-commit transaction)
                          (progn
                            (setf (transaction/reason transaction) abort-reason)
                            (transaction/do-abort  transaction))))
            (:committing (transaction/do-commit transaction))
            (:aborting   (transaction/do-abort  transaction))))))

;; Aborting is simple.
(defun transaction/do-abort (transaction)
  "Perform the necessary work to abort the transaction."
  (assert (or (eq (transaction/disposition transaction) :aborting)
              (eq (transaction/disposition transaction) :running)))
  (setf (transaction/disposition transaction) :aborted))

;; Committing is simple, too.  Just write a commit record.
(defun transaction/do-commit (transaction)
  "Perform the necessary work to commit the transaction."
  (assert (or (eq (transaction/disposition transaction) :committing)
              (eq (transaction/disposition transaction) :running)))
   (let* ((object-map (transaction/object-map transaction))
          (pstore (object-map/pstore object-map)))
     (persistent-store/commit pstore
         :object-map object-map
         :reason (transaction/reason transaction))
     (setf (transaction/disposition transaction) :committed)))

More persistence

2010-12-15T12:31:00.000-08:00

In my last post, I described how to map OIDs to persistent objects by means of a functional, weight-balanced, binary tree. In this post, I will describe how to implement aggregate objects. I'm going to start with a high-level view and drill down to the details. I'm afraid at this point I'm going to switch to Common Lisp and CLOS. Don't worry, though, if you just pretend that defclass is a synonym for define-structure, you won't be far off.

Here's a simple CLOS class definition:

(defclass test-class ()
  ((name :initarg :name
         :initform 'zippy)))

Objects of class test-class have a single field which is called name. This class definition adds a method to make-instance that works as follows:

  ;; make an instance where the name is the symbol GRIFFY 
  (defvar test-instance-1 (make-instance 'test-class :name 'griffy))

  ;; alternatively, use the default name of ZIPPY
  (defvar test-instance-2 (make-instance 'test-class))

In addition, we can use slot-value to extract the name:

  (slot-value test-instance-1 'name)
  => GRIFFY

  (slot-value test-instance-2 'name)
  => ZIPPY

And that's that. (And you thought CLOS was complicated.)

A persistent class is defined as follows:

(defclass test-class ()
  ((name :initarg :name
         :initform 'zippy))
  (:metaclass persistent-standard-class)
  (:schema-version 0))

The :metaclass specifier tells CLOS that we want instances to be persistent. The :schema-version is a bit of magic that protects against the unlikely, but possible nasty case that over time a class definition might evolve where a slot name is accidentally re-used. In such a case, the code will need to disambiguate which class definition was intended and it can use the :schema-version. You can safely ignore this by following this simple rule: If you ever modify the slots in a persistent class, you should increment the :schema-version.

So what is different? On the surface, practically nothing changes. The calls to make-instance and slot-value work just as before. There are four changes that happen ‘under the covers’

The object returned by make-instance will be a persistent object.
Two additional slots are allocated. The first contains the OID of the instance itself, the second contains the persistent store where the instance was allocated.
The name slot in the object will contain the OID of the persistent name rather than a Lisp object. make-instance is modified to extract the OIDs of its arguments to initialize this slot.
slot-value must be modified to dereference the OID that is actually in the slot.

These modifications are easily made using the CLOS MOP.

We use the meta-object protocol to override slot-value-using-class as follows:

(defmethod clos:slot-value-using-class ((class persistent-standard-class)
                                        (object persistent-standard-object)
                                        slot)
   (persistent-object/find 
     (persistent-standard-object/pstore object)
     (call-next-method)))

The call to call-next-method invokes the underlying mechanism for reading a slot value. But we're not storing the actual slot value in the slot, we are storing the OID of the actual slot value, so call-next-method will return that OID. We look up the returned OID in the persistent store to get the value. (In order to support multiple persistent stores, we need to know which store contains the value. We require that all subfields of an object be allocated in the same persistent store as the containing object.)

The modifications to make-instance are more complex. We actually don't modify make-instance directly, but instead we modify clos:shared-initialize (which is invoked by make-instance as part of the instance allocation protocol).

;; Override the primary shared-instance method
;; in order to deal with persistent slots.
(defmethod clos:shared-initialize ((instance persistent-standard-object) slot-names
                                   &rest initargs
                                   &key persistent-store oid
                                   &allow-other-keys)
    ;; We have to wrap the initargs and initforms
    ;; in persistent-objects and create an initializer
    ;; for this object.
    (let* ((class (class-of instance))

           (init-plist (compute-persistent-slot-initargs class
                                                         (or persistent-store  *default-persistent-store*)
                                                         initargs))

           (oid (persistent-object/save
                     (make-initializer class
                                       (class-schema-version class)
                                       init-plist)
                     (or persistent-store  *default-persistent-store*)
                     oid)))

      (apply #'call-next-method instance slot-names (nconc init-plist initargs))
      (setf (persistent-standard-object/oid instance) oid)
      instance))

(defun compute-persistent-slot-initargs (class persistent-store initargs)
  "Scan over the persistent effective slots in CLASS,
   determine the value to be assigned to each slot, either
   from the initargs or from the initfunction, then
   using the persistent-initarg as a key, construct a
   plist for use in the persistent initializer and in
   the inner call to shared-initialize."
  (let ((result nil))
    (iterate (((slot-initargs slot-initfunction slot-persistent-initarg)
               (map-fn '(values t t symbol)
                       #'effective-slot-initialization-info
                       (scan-class-persistent-effective-slots class))))
      (let ((initial-value (slot-initial-value initargs slot-initargs slot-initfunction
                                               (clos::slot-unbound-value))))
        (unless (eq initial-value (clos::slot-unbound-value))
          (push slot-persistent-initarg result)
          (push (slot-value->persistent-node persistent-store initial-value) result))))
    (nreverse result)))

In compute-persistent-slot-initargs, you can see the call to slot-value->persistent-node that extracts the OID from the initarg. In shared-initialize, the call to persistent-object/save writes an initialization record to the store and then allocates and initializes the transient, in-memory version of the object.

These are the essential changes to the MOP to implement the basic persistence mechanism.

More details to come in the next post.

Oh yeah, about that persistent store....

2010-12-14T14:04:00.000-08:00

In April of last year I was describing a simple persistent object store. I never finished. Mea culpa. I was thinking about it again and I realize why. The next step in the implementation is a really big one. We're going to solve five unrelated problems in one fell swoop:

Transactions — we will add the ability to roll-back partially completed operations.
Aggregate objects — up to now, we only allow primitive objects to be persisted. We will add the mechanism to allow aggregate structures to be stored and retrieved.
Side effects — the backing store is opened in append mode, so mutation of existing objects is not possible. Since we only allow primitive immutable objects to be stored, this is not an issue. Once we have aggregate objects, however, we will want to simulate the ability to side-effect these objects. The transaction system will have to know how to undo these effects if the transaction aborts.
Schema migration — Persistent objects live a long time. Over time, it is usually the case that we will want to change what fields are contained in an aggregate object. Removing a field is easy, but adding or renaming an existing field can be tricky because legacy objects will be missing the field. Furthermore, if the aggregate object model is rich (for example, if it supports inheritance), some changes to the model might require making extensive changes to the existing persistent objects.
Internal and external references — up to now, an object cannot refer to another object. There is also no way to refer to a particular persistent object other than by directly using it. For example, although we could store two different strings in the persistent store, and we can recover both, we cannot identify which one is ‘first’ and which one is ‘second’.

I haven't figured a way to truly separate these five different features, so this post is going to be a long and complex one.

We need to introduce object identifiers (OIDs). An OID is an integer that refers to a unique persistent object. Every persistent object in a particular persistent store is given a different OID (we do not require that OIDs are universally unique).

At this point, let me illustrate the code.

(define-structure (object-map-entry
                   (type list)
                   (conc-name object-map-entry/)
                   (constructor %make-object-map-entry
                                (object-id address cached-value)))
  (object-id #f read-only #t)
  (address #f read-only #t)

  ;; *** A slot holding the cached value greatly improves
  ;;     performance!
  (cached-value #f read-only #t)
  )

Each object-map-entry associates an object-id with an address. The address is the location within the backing store where the object has been serialized. The cached-value not only speeds up object retrieval, it ensures that every dereference of an OID yields the same EQ? result. Extrinsic identity — the existence of a universal ‘identically equal’ predicate — is a key assumption of Lisp, so it is important to avoid violating this assumption.

We will be maintaining a data structure that maps OIDs to objects. This data structure will itself need to be persistent. Over time, we expect the ratio of new objects to old objects to decrease, so a data structure that supports incremental update will be much more efficient than one that requires wholesale replacement. A weight-balanced binary tree is one way of implementing this map.

A tree has two kinds of nodes: leaf nodes, which hold a single object-map-entry, and branch nodes, which hold sub-trees in addition to an object-map-entry. Object lookup requires descending into the tree to find the object-map-entry with the correct OID.

(define (persistent-tree/descend object-id current-tree best-tree)
  (cond ((null? current-tree) best-tree)
        ((< object-id 
               (object-map-entry/object-id (persistent-tree/object-map-entry current-tree)))
         (persistent-tree/descend object-id 
                                  (persistent-tree/left-child current-tree) best-tree))
        (else
         (persistent-tree/descend object-id
                                  (persistent-tree/right-child current-tree) current-tree))))

(define (persistent-tree/find-entry root object-id)
  (let ((best-tree (persistent-tree/descend object-id root '())))
    (if (null? best-tree)
        #f
        (let ((entry (persistent-tree/object-map-entry best-tree)))
          (if (< (object-map-entry/object-id entry) object-id)
              #f
              entry)))))

Adding an entry to the OID tree is much more complex. Binary trees work best when they are balanced, so when we add a node to the tree we may want to rebalance the tree. This may require creation of new internal nodes of the tree. In addition, we want our tree to be persistent, so any new nodes must be written to the backing store. However, we want the tree to be efficient — adding a node and rebalancing the tree should not require too much computation and disk traffic.
This particular implementation uses a `functional binary tree'. Updates to the tree do not modify existing data structures. Instead, new nodes are allocated and as much of the existing tree as possible is re-used. (See Stephen Adams `Implementing Sets Efficiently in a Functional Language' http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.1134 for the details on the algorithms.) Here is the code:

(define-structure (persistent-tree
                   (conc-name persistent-tree/)
                   (constructor make-persistent-tree (left-child-address
                                                      right-child-address
                                                      %weight
                                                      %address
                                                      left-child
                                                      right-child
                                                      object-map-entry)))

  ;; Address of left child of the tree.
  ;; This field is persistent.
  (left-child-address #f read-only #t)

  ;; Address of right child of the tree.
  ;; This field is persistent.
  (right-child-address #f read-only #t)

  ;; Weight of this tree.
  ;; This field is persistent.
  (%weight #f read-only #t)

  ;; Where the persistent version is in the durable store.
  ;; This field is transient and reconstructed upon deserialization.
  (%address #f read-only #t)

  ;; Cached left child.
  ;; A transient copy of the deserialized left child.
  (left-child #f read-only #t)

  ;; Cached right child.
  ;; A transient copy of the deserialized right child.
  (right-child #f read-only #t)

  ;; The object map entry stored at the root of this tree.
  (object-map-entry #f read-only #t))

(define (persistent-tree/make-leaf durable-store entry)
  (let* ((weight 1)
         ;; Serialize the persistent information from the
         ;; object-map-entry.  (the object-id and the address).
         (address (primitive-serialize-leaf durable-store (object-map-entry/address entry))))
    (make-persistent-tree 0 0 weight address '() '() entry)))

(define (primitive-serialize-leaf durable-store entry-address)
  (write-leaf-record! 
   durable-store
   (lambda (oport)
     ;; store the delta because it is likely to be a small number.
     (write entry-address oport))))

(define (persistent-tree/make-branch durable-store left-child right-child entry)
  (if (and (null? left-child)
           (null? right-child))
      (persistent-tree/make-leaf durable-store entry)
      (let* ((weight (+ 1
                        (persistent-tree/weight left-child)
                        (persistent-tree/weight right-child)))
             (left-child-address (persistent-tree/address left-child))
             (right-child-address (persistent-tree/address right-child))
             ;; Serialize the addresses of the
             ;; left and right child, and the persistent information 
             ;; from the object-map-entry (the object-id and the address).
             (address 
              (primitive-serialize-branch durable-store
                                          left-child-address
                                          right-child-address
                                          (object-map-entry/address entry))))
        (make-persistent-tree left-child-address
                              right-child-address
                              weight
                              address
                              left-child
                              right-child
                              entry))))

(define (primitive-serialize-branch durable-store
                                    left-child-address
                                    right-child-address
                                    entry-address)
  (write-branch-record!
   durable-store
   (lambda (output-port)
     (write left-child-address output-port)
     (write-char #\space output-port)
     (write right-child-address output-port)
     (write-char #\space output-port)
     (write entry-address output-port))))

(define (persistent-tree/add durable-store root new-entry)
  (if (null? root)
      (persistent-tree/make-leaf durable-store new-entry)
      (let ((root-entry (persistent-tree/object-map-entry root))
            (left-child (persistent-tree/left-child root))
            (right-child (persistent-tree/right-child root)))
        (cond ((< (object-map-entry/object-id new-entry)
                  (object-map-entry/object-id root-entry))
               (persistent-tree/t-join 
                durable-store 
                (persistent-tree/add durable-store left-child new-entry)
                right-child
                root-entry))
              ((< (object-map-entry/object-id root-entry)
                  (object-map-entry/object-id new-entry))
               (persistent-tree/t-join
                durable-store 
                left-child
                (persistent-tree/add durable-store right-child new-entry)
                root-entry))
              (else
               (persistent-tree/make-branch durable-store 
                                            left-child right-child
                                            new-entry))))))

(define (persistent-tree/t-join durable-store left-child right-child entry)
  (let ((l.n (persistent-tree/weight left-child))
        (r.n (persistent-tree/weight right-child)))
    (cond ((< (+ l.n r.n) 2)
           (persistent-tree/make-branch durable-store left-child right-child entry))

          ((> r.n (* 5 l.n))
           (persistent-tree/l-join durable-store left-child right-child entry))

          ((> l.n (* 5 r.n))
           (persistent-tree/r-join durable-store left-child right-child entry))

          (else
           (persistent-tree/make-branch durable-store left-child right-child entry)))))

(define (persistent-tree/l-join durable-store left-child right-child entry)
  (if (< (persistent-tree/weight (persistent-tree/left-child right-child))
         (persistent-tree/weight (persistent-tree/right-child right-child)))
      (persistent-tree/single-l durable-store left-child right-child entry)
      (persistent-tree/double-l durable-store left-child right-child entry)))

(define (persistent-tree/single-l durable-store x r entry)
  (persistent-tree/make-branch 
   durable-store 
   (persistent-tree/make-branch durable-store 
                                x (persistent-tree/left-child r) entry)
   (persistent-tree/right-child r)
   (persistent-tree/object-map-entry r)))

(define (persistent-tree/double-l durable-store x r entry)
  (let ((r.l (persistent-tree/left-child r)))
    (persistent-tree/make-branch 
     durable-store
     (persistent-tree/make-branch durable-store
                                  x
                                  (persistent-tree/left-child  r.l)
                                  entry)
     (persistent-tree/make-branch durable-store
                                  (persistent-tree/right-child r.l)
                                  (persistent-tree/right-child r)
                                  (persistent-tree/object-map-entry r))
     (persistent-tree/object-map-entry r.l))))

(define (persistent-tree/r-join durable-store left-child right-child entry)
  (if (< (persistent-tree/weight (persistent-tree/right-child left-child))
         (persistent-tree/weight (persistent-tree/left-child left-child)))
      (persistent-tree/single-r durable-store left-child right-child entry)
      (persistent-tree/double-r durable-store left-child right-child entry)))

(define (persistent-tree/single-r durable-store l z entry)
  (persistent-tree/make-branch
   durable-store
   (persistent-tree/left-child l)
   (persistent-tree/make-branch durable-store
                                (persistent-tree/right-child l)
                                z
                                entry)
   (persistent-tree/object-map-entry l)))

(define (persistent-tree/double-r durable-store l z entry)
  (let ((l.r (persistent-tree/right-child  l)))
    (persistent-tree/make-branch 
     durable-store
     (persistent-tree/make-branch durable-store
                                  (persistent-tree/left-child  l)
                                  (persistent-tree/left-child  l.r)
                                  (persistent-tree/object-map-entry l))
     (persistent-tree/make-branch durable-store
                                  (persistent-tree/right-child l.r)
                                  z
                                  entry)
     (persistent-tree/object-map-entry l.r))))

In the next post, I will describe how we use this structure to implement transactions, simulate side-effects, and turn schema migration into a non-issue.

No ILC for me

2010-10-18T12:23:00.000-07:00

Alas, I'm unable to attend ILC 2010.

For your amusement...

2010-09-02T10:16:00.000-07:00

Some computer Tom Swifties:

“I thought I would free up more memory on the second pass,” Tom recollected.
“You should always check the pre-conditions,” Tom asserted.
“Did you use SSL?” Tom asked cryptically.
“If one of those is smaller, put it first,” Tom ordered weakly.
“Command continuations discard values,” Tom said expressionlessly.
“That isn't null or a cons cell,” Tom said listlessly.
“Does this return an answer?” Tom asked haltingly.
“This program implicitly depends upon time,” Tom stated.
“Maybe it's in Reverse Polish Notation,” Tom put forth.

INTERNATIONAL LISP CONFERENCE 2010 - HIGHLIGHTS and CALL for PAPERS

2010-08-20T08:53:00.000-07:00

With the usual apologies to those who receive multiple copies of this...

 INTERNATIONAL LISP CONFERENCE 2010 - HIGHLIGHTS and CALL for PAPERS 

Important Dates:
~~~~~~~~~~~~~~~~

 * Deadline for all submissions (FIRM): September 6, 2010
 * Early registration: September 16, 2010
 * Author notification: September 20, 2010
 * Final paper due (in electronic form): October 5, 2010
 * Conference: October 19-21, 2010


Invited Speakers:
~~~~~~~~~~~~~~~~~

We are proud to announce that, for the 2010 edition, we will have the
following invited talks:

 * Lawrence Hunter
     Building a Mind for Life

 * Jans Aasman
     AllegroGraph and the Linked Open Data Cloud

 * Marc Feeley
     Gambit Scheme: Inside Out

 * Peter Seibel
     Common Lisp Standardization: The Good, the Bad, and the Ugly

 * Don Syme
     F#: Taking Succinct, Efficient, Typed Functional Programming 
     into the Mainstream

 * Lowel Hawkinson
     Lisp for Breakthrough Products

More information about speakers and talks is available at
http://www.international-lisp-conference.org/2010/speakers


Registration:
~~~~~~~~~~~~~

Rates for Early Registration (before or on September 16, 2010)

ALU member
 & ACM member      $355
 & ACM non member  $390
 & Student         $150

ALU Individual Sponsors
 & ACM member      $280
 & ACM non-member  $315
 & Student         n/a

non-member of ALU
 & ACM member      $430
 & ACM non-member  $465
 & Student         $165

Rates for Late Registration (after September 16, 2010 & Onsite)

ALU member
 & ACM member      $440
 & ACM non member  $485
 & Student         $185

ALU Individual Sponsors
 & ACM member      $365
 & ACM non-member  $410
 & Student         n/a

non-member of ALU
 & ACM member      $515
 & ACM non-member  $560
 & Student         $200

Due to colocation, registration must be done using ILC/SPLASH'10
unified registration forms available at http://splashcon.org/

Please note that the registration page (page 3) has the option "SPLASH
(OOPSLA/Onward!)" selected by default.  If you are only planning to
attend ILC, don't forget to deselect that option.


Travel and Accommodation:
~~~~~~~~~~~~~~~~~~~~~~~~~

SouthWest Airlines offers low fares into Reno but requires booking
online at www.southwest.com

John Ascuaga's Nugget offers reduced rates for ILC participants.
Please, visit http://splashcon.org/ to obtain the group code.


Scope:
~~~~~~

Lisp is one of the greatest ideas from computer science and a major
influence for almost all programming languages and for all
sufficiently complex software applications.

The International Lisp Conference is a forum for the discussion of
Lisp and, in particular, the design, implementation and application of
any of the Lisp dialects.  We encourage everyone interested in Lisp to
participate.

We invite high quality submissions in all areas involving Lisp
dialects and any other languages in the Lisp family, including, but
not limited to, ACL2, AutoLisp, Clojure, Common Lisp, ECMAScript,
Dylan, Emacs Lisp, ISLISP, Racket, Scheme, etc.

Topics may include any and all combinations of Lisp and:

 * Language design and implementation
 * Language critique
 * Language integration, inter-operation and deployment
 * Applications (especially commercial)
 * 'Pearls' (of wisdom)
 * Experience reports and case studies
 * Reflection, meta-object protocols, meta-programming
 * Domain-specific languages
 * Programming paradigms and environments
 * Parallel and distributed computing
 * Software evolution
 * Theorem proving
 * Scientific computing
 * Data mining
 * Semantic web

We also encourage submissions about known ideas as long as they are
presented in a new setting and/or in a highly elegant way.

Authors concerned about the appropriateness of a topic may communicate
by electronic mail with the program chair prior to submission.

Accepted papers will be published in the ACM Digital Library (PENDING).

Papers must be written in English and submitted electronically at
http://www.easychair.org/conferences?conf=ilc2010 in PDF or WORD
format.  Final submissions must not exceed 15 pages and need to use
the ACM format, for which templates can be found at:
http://www.acm.org/sigs/pubs/proceed/template.html.

Each paper should explain its contributions in both general and
technical terms, identifying what has been accomplished, explaining
why it is significant, and comparing it with previous work. Authors
should strive to make their papers understandable to a broad audience.
Each paper will be judged according to its significance, novelty,
correctness, clarity, and elegance.

The official language of the conference is English.  Some further
information is available at the conference web site, with more details
added later.  See: http://www.international-lisp-conference.org/

Technical Program:
~~~~~~~~~~~~~~~~~~

Original submissions in all areas related to the conference themes are
invited for the following categories.

 * Papers: Technical papers of up to 15 pages that describe original
   results or explain known ideas in new and elegant ways.

 * Demonstrations: Abstracts of up to 4 pages for demonstrations of
   tools, libraries, and applications.

 * Tutorials: Abstracts of up to 4 pages for in-depth presentations
   about topics of special interest for at least 90 minutes and up to
   180 minutes.

 * Workshops: Abstracts of up to 4 pages for groups of people who
   intend to work on a focused topic for half a day.

 * Panel discussions: Abstracts of up to 4 pages for discussions about
   current themes. Panel discussion proposals must mention panel
   members who are willing to partake in a discussion.

 * Lightning talks: Abstracts of up to one page for talks to last for
   no more than 5 minutes.

Depending on the technical content, each submitted paper will be
classified by the program committee as either a technical paper or as
an experience paper; and authors will be informed about this
classification.  Note that all interesting submissions are considered
valuable contributions to the success of the ILC series of
conferences.  As in past ILC's since 2007, accepted papers in both
categories will be presented at the conference, included in the
proceedings, and submitted to the ACM digital library.


Organizing Committee:
~~~~~~~~~~~~~~~~~~~~~

 * General Chair:
   JonL White - The Ginger IceCream Factory of Palo Alto, ALU

 * Program Chair:
   Antonio Leitao - Instituto Superior Tecnico/INESC-ID

 * Conference Treasurer:
   Duane Rettig - Franz, Inc., ALU Director

 * Publicity Chair:
   Daniel Herring - ALU Director

 * ALU Treasurer:
   Rusty Johnson - TASC, Inc., ALU Director


Program Committee:
~~~~~~~~~~~~~~~~~~

 * Antonio Leitao - Instituto Superior Tecnico/INESC-ID, Portugal
 * Alex Fukunaga - University of Tokyo, Japan
 * Charlotte Herzeel - Vrije Universiteit Brussel, Belgium
 * Christophe Rhodes - Goldsmiths College, University of London, UK
 * Didier Verna - EPITA Research and Development Laboratory, France
 * Duane Rettig - Franz, Inc., USA
 * Giuseppe Attardi - University of Pisa, Italy
 * Jeff Shrager - Symbolic Systems Program, Stanford University, USA
 * Joe Marshall - Google, Inc., USA
 * Julian Padget - University of Bath, UK
 * Keith Corbett - Clozure Associates, USA
 * Kent Pitman - PTC, USA
 * Manuel Serrano - INRIA Sophia Antipolis, France
 * Marc Feeley - University of Montreal, Canada
 * Marie Beurton-Aimar University of Bordeaux 1, France
 * Mark Stickel - SRI International, USA
 * Matthias Felleisen - Northeastern University, USA
 * Scott McKay - ITA Software, USA


Contacts:
~~~~~~~~~

 * Questions: ilc10-organizing-committee at alu.org

 * Program Chair: ilc2010 at easychair.org

For more information, see http://www.international-lisp-conference.org/

P ≠ NP (part 2 correction)

2010-08-18T09:41:00.000-07:00

In the previous post I said that one example of an NP problem is “Check if two computer programs always produce the same output.” jkff commented:

The "check if two computer programs always produce the same output" is not NP. It's simply undecidable and cannot be solved in any amount of time.

I blew it and oversimplified the statement. At Wikipedia, they have a list of commonly known NP-complete problems and on that list is “Inequivalence of simple functions.” I seriously mangled the meaning because I was daydreaming about assembly code. What I should have done is put some restrictions on what sort of computer program I meant.

First, we have to restrict ourselves to programs that we can prove will always return an answer within a given amount of time. A computer program that does not have any loops, backward jumps (gotos), subroutine calls, or exceptions should simply run from from start to finish. Second, we do not allow the program to save any state between runs; the output must be a pure function of the input. Furthermore, we restrict the input to a finite set (for example, integers that expressible in a single 32-bit word). Now suppose we have two such programs. To prove they are not equivalent, we need to find a 32-bit integer input that makes each program give a different answer. By trial and error we will eventually find such an input or exhaustively show that there is none. However, if someone were to claim that a particular input produced different output, then it is easy to check by simply trying it out.

P ≠ NP (part 2)

2010-08-17T12:02:00.000-07:00

As I mentioned in my last post, P and NP are commonly encountered complexity classes. Knowing what complexity class a problem is in can give us some idea of how difficult it may be to solve the problem. So what's the difference between P and NP? I don't want to get into the technical definition of P and NP, so I'm going to make broad generalizations that aren't technically rigorous, but will give you a feel for the difference.

Problems in class P are generally considered “tractable” by computer scientists. By this we mean that a computer can probably solve such a problem efficiently and relatively quickly. Recall that the complexity classes relate the ‘number of pieces’ to the difficulty. If you can solve a particular problem in P, then a similiar problem with a ‘larger number of pieces’ is likely within your grasp (and if not, it is usually a question of upgrading to a better computer). Problems in class P are the ‘meat and potatoes’ of computer programs.

Before I discuss NP, let me introduce the complexity class EXPTIME. EXPTIME is where you find some really hard problems, like computer chess or Go. It is true that there are computers that can play chess really well, but if we were to modify the rules of chess to add a couple of new pieces and make the board 9x9 instead of 8x8, it would greatly increase the difficulty of the game. Problems in EXPTIME are generally considered “intractable”. By this we mean that a computer will have a hard time solving such a problem efficiently and quickly. And if you are able to solve a particular problem in EXPTIME, then a similar problem with just ‘a few more pieces’ is likely beyond your grasp, no matter how fancy a computer you might buy. Problems in class EXPTIME take a lot of time and money to solve.

So what about NP? Problems in NP are quite curious. They seem to be very difficult to solve, much like EXPTIME problems, but they have the unusual property that it is very easy to check if a solution is correct. Let me illustrate: if I showed you a chess position and claimed that it was a good position for white, you'd have to do a lot of work to verify whether my claim was true. In fact, it would have to be about the same amount of work it took me to come up with the position in the first place. On the other hand, if I were to show you a jigsaw puzzle and claim that I had finished it, you could tell at a glance whether my claim were true. Problems in NP seem to be much harder to solve than problems in P, but as easy to verify as problems in P. That is a little weird.

Problems in NP are often encountered in computer programs, and many of these kind of problems, although very difficult to solve, have approximations that are relatively easy. In some cases, when a perfect solution is not needed, one that is ‘good enough’ will be a lot easier to compute. Another weird thing is that a lot of problems in NP don't sound at all like they'd be hard to solve. Here are some examples:

Take a group of people and divide them into two subgroups such that both subgroups have exactly the same amount of change in their pockets. (No, you aren't allowed to move the change around.)
Find the shortest path that visits all the major landmarks in a city.
Check if two computer programs always produce the same output. Whoops! I blew this one. Check the next posting.

There is one final bit of weirdness. It is easy to prove that EXPTIME problems are much harder to solve that P problems, but no one has proven that NP problems are harder than P problems. (or that they aren't harder than P problems!) This isn't for lack of trying. Many smart people have worked on a proof for some time. There's a million dollar prize for the first person to prove this one way or the other. Recently, Vinay Deolalikar of HP Labs claimed that he has a proof. Unfortunately, other experts in the field have pointed out flaws in the proof that may invalidate it.

P ≠ NP (part 1)

2010-08-13T14:22:00.000-07:00

I'm sure most people who read this blog know a bit about what this means, but I want to try to explain it in a way my mom could understand. I won't go into excruciating detail, and I'll probably gloss over interesting points.

Let's start with an analogy. Suppose you go to the store to buy a present for your nephew. He likes jigsaw puzzles, so you want to get him one. He's going to be twelve years old, so you need to find one that has the appropriate challenge. A simple one with four pieces might be great for a two year-old, but your nephew would find that boring. A big one with ten thousand pieces is probably too much for him. You know he just finished one with five hundred pieces, so you pick one with six hundred pieces because it won't be too easy, but not too frustrating. What you are doing is estimating the complexity of the puzzle.

When you get to the store you find that they are sold out of jigsaw puzzles. They have a variety of other puzzles, though. They have a Rubik's cube, a Sudoku book, some cryptograms, a Tower of Hanoi, etc. They have models you can put together as well. But these things aren't jigsaw puzzles. You can't estimate the complexity the same way. A model with five hundred pieces would be quite a bit more difficult to assemble than a jigsaw puzzle with the same number of pieces.

Perhaps you look at the age ratings for the various puzzles. The eight-piece Tower of Hanoi puzzle is rated for ages ten and up, so maybe a twelve piece? The standard 3x3x3 Rubik's cube is rated for ages eight and up, but would the 4x4x4 be too hard or too easy? What about the 5x5x5?

The kind of rating system you use to describe the difficulty of a puzzle is analogous to the “complexity class” of a problem. The complexity class roughly describes how hard a problem will be to solve, and more importantly, how much harder ‘big’ problems are compared to the ‘small’ ones. Here's what I mean: if I take a jigsaw puzzle, any jigsaw puzzle, and double the number of pieces in it, I'll make it roughly twice as hard (more or less). If I take a cryptogram and double the number of words in it, I'll actually make it a lot easier. If I take the Tower of Hanoi and double the number of discs, I'll make it incredibly harder, maybe even impossible. These puzzles are in different complexity classes.

As it turns out, a lot of puzzles are in the same complexity class as the jigsaw puzzle: the difficulty is reasonably proportional to the number of pieces. Adding a piece or two doesn't change things that much, and it is easy to figure out how long it will take to solve if you've done a few of them. A lot of puzzles are more like the Tower of Hanoi. Adding a single piece will double the amount of time it takes to solve them.

P and NP are complexity classes for problems you might want to solve on a computer. There are all sorts of rating systems, but everyone is familiar with the MPAA movie ratings. There are all sorts of complexity classes, but most computer scientists are familiar with P and NP.

I'll pause here because the analogy is wearing thin. The main point is that “P ≠ NP” is a statement about complexity classes. In particular, it talks about two of the most popular complexity classes and that is part of the reason it is interesting.

Rambling

2010-08-12T10:00:00.000-07:00

Writing a blog is hard. I need practice so I'm going to ramble a bit.

First, I'm very pleased that Blogger has improved their comment spam detection. Every time I made a post I'd have to come back a day or two later and remove a bunch of pointless comment spam.

Second, I told my daughter that someone claims to have a proof that P ≠ NP. She replied “Well, now we know that N doesn't equal 1.”

I read through the proof and I confess that I don't get it. On the other hand, I think I want to get it, so I'll have to learn some interesting things.

Here's another thing I don't get.

`` E8 is any of several closely related exceptional simple Lie groups and Lie algebras of dimension 248''

``a simple Lie group is a connected non-abelian Lie group G which does not have nontrivial connected normal subgroups.''

``a Lie group is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure.''

``a non-abelian group is a group (G, * ) in which there are at least two elements a and b of G such that a * b ≠ b * a.''

``a connected space is a topological space which cannot be represented as the union of two or more disjoint nonempty open subsets''

Happy 80th Birthday to Neil Armstrong

2010-08-05T10:07:00.000-07:00

Neil Armstrong turns 80 years old today!

My definition

2010-08-03T11:10:00.000-07:00

Here's my definition:

A computer program is a description of a process which is formal enough to be carried out by a machine.

Most of the other definitions describe a program as a ‘set of instructions’. Some of the definitions suggest that these instructions should be organized in some way, perhaps as a (linear) list. These instructions ‘make the computer do things’, ‘bring about a certain result’, ‘cause the computer to behave in a predetermined manner’, or ‘alter the contents of memory’. But these definitions have an explicit or implicit assumption: a sequential, imperative mode of thought.

Look at this Prolog code:

append(c(H,T), B, c(H,TB)) <= append(T, B, TB).
append(nil, B, B).

This code describes relationship of appending lists, but it doesn't specify how to accomplish the appending. Is the first clause an ‘instruction’ to build a list, or to take one apart? Are the clauses to be run in any particular order? Is there a deterministic ‘answer’?

What is a ‘computer program’?

2010-08-02T15:53:00.000-07:00

This seems like a simple enough question.

Here's what the web says. A computer program is

a set of statements or instructions to be used directly or indirectly in a computer in order to bring about a certain result
what makes the computer do things
a set of instructions written in a programming language
an algorithm written in a language that a computer can understand
simply a long list of code written in another language
a set of instructions for altering the contents of various words in the computer's memory
a carefully thought out, step-by-step, set of instructions prepared by a programmer
an organized list of instructions that, when executed, causes the computer to behave in a predetermined manner
is a procedure (or algorithm) for performing some computation
a bunch of instructions run by a computer, just like a storybook is just a whole bunch of sentences read by the reader

Does anyone have any better definitions?

Crazy person thinks ``Lisp sucks''

2010-07-13T12:18:00.000-07:00

In this post, a person going by the initials CC declares:

There's a good reason almost no software has been written in lisp. Lisp sucks. Not just lisp, but the whole way the logic is arranged as nested things. The simplest problem becomes a mind-bending puzzle.

Instead of easy to understand:
if (a equals b) { 
  c = not d; 
} else { 
  c = d + b; 
}
You have this nested inner to outer logic where if is a function.
c = if(equals(a,b), not(d), plus(d,b)) 
The first is definitely more readible [sic] and it reads like we think of the logic. No one thinks of if as a function that takes three arguments, and forcing you to work that way just makes you crazy.

I suppose it is futile to argue with an admittedly crazy person, but perhaps being forced to work with conditionals has made me crazy as well. A closer translation of the original code would be this:

(if (equals a b)
    (setq c (not d))
    (setq c (+ d b)))

If these sorts of differences are a ``mind-bending puzzle'', perhaps the author should consider a career in the housekeeping or food-service industries.

Dr Scheme name change

2010-06-24T12:31:00.000-07:00

I put together a page that compares the various names of Dr. Scheme by how often people search for them in Google.

Buoyancy

2010-06-11T08:45:00.000-07:00

Steve suggested: For this to work like you want, Java style, you'd have to add a Class member to the Box class, to represent the type of Box at runtime.

Like this:

public final class Box<E> {

  private final Class<E> type;
  private final E value;

  public Box (Class<E> type, E value) {
    this.type = checkNotNull(type, "type");
    this.value = value;
  }

  public E getValue() {
    return value;
  }

  public boolean isType (Class<?> specific) {
    return specific == this.type;
  }

  @SuppressWarnings("unchecked")
  public <X> Box<X> asType (Class<X> specific) {
    if (isType(specific)) {
      return (Box) this;
    } else {
      throw new ClassCastException();
    }
  }
}

You could then write a static generic filter taking an Iterable of generic Boxes and a Class object to filter by, and returning an Iterable of the correct type fairly simply.

Sort of like this (assuming appropriate definitions of map and filter):

// The essential code is in a bold green face.

public <X> Iterable<Box<X>> boxesOfType (final Class<X> type,
                                         Iterable<Box<?>> boxes) {
  return
      map (
          filter (
              boxes,
              new Predicate<Box<?>> () {
                @Override
                public boolean apply (Box<?> box) {
                  return box.isType(type);
                }
              }),
          new Function<Box<?>, Box<X>> () {
            @Override
            public Box<X> apply (Box<?> box) {
              return box.asType(type);
            }
          });
}

Dunno if that floats your boat, tho.

It definitely floats my boat (thanks, Steve) in that I can now, in a typesafe manner, take a bunch of heterogeneous boxes and select and downcast them to a subset of homogeneous boxes.

I'll discuss the leaks in the boat in the next post.

Addendum

mquander offered a C# solution to the same problem:

internal interface IBox { }
 
public class Box<T> : IBox
{
    public T Value;
}
 
public static class BoxManipulators
{
    public static int MinimumIntegerInBox(IEnumerable<IBox> boxes)
    {
        return boxes.OfType<Box<int>>().Min(x => x.Value);
    }
}

An Illustrative Problem (Part II) correction

2010-06-10T10:43:00.000-07:00

Blogger really munged Mike's code, so here is the relevant part correctly formatted:

public static int minimumIntegerInBox(Collection<Box<?>> boxes) {
  Iterable<Box<?>> intBoxes = filter(boxes,
      new Function<Box<?>, Boolean>() {
        @Override
        public Boolean of(Box<?> domainItem) {
          return domainItem.get() instanceof Integer;
        }
      });
  Iterable<Integer> ints = map(
      intBoxes,
      new Function<Box<?>, Integer>() {
        @Override
        public Integer of(Box<?> domainItem) {
          return Integer.class.cast(domainItem.get());
        }
      });
  return minimumElement(ints);
}

public static int minimumElement(Iterable<Integer> items) {
  return best(
      new Function<Pair<Integer, Integer>, Boolean>() {
        @Override
        public Boolean of(Pair<Integer, Integer> domainItem) {
          return domainItem.second() < domainItem.first();
        }
      },
      items);
}

This is similar to what I started with, but I didn't like this solution for two reasons.

The test for whether the Box<?> is a Box<Integer> relies on extracting the contents of the Box and testing to see if it is an integer. In other words, rather than relying on the type of the container, we explicitly look at the contents of the container. This is an important distinction, but it might be hard to see it in this context. Just because the box happens to contain an integer at this point doesn't mean that it is a Box<Integer>. It could be a Box<Number> or a Box<Object> that currently has an integer in it, but could just as well have some non-integer in it. Conversely, it could be a Box<Integer> that happens to have a null in it. For the purposes of finding the minimum element, a null would be an issue, but if the task were to “fill all the Box<Integer> with zero,” then this method of testing the box type would miss the Box<Integer> with null.
The type of intBoxes is wrong. It really ought to be Iterable<Box<Integer>>.

Anyone care to offer a fix?

An illustrative problem (part II)

2010-06-09T10:39:00.000-07:00

Mike Coffin took the bait. (Thanks, Mike!) Unfortunately, pasting code into the blog comments is a very poorly supported feature. Blogs about Python must be interesting. I'll recopy some of Mike's code here.

Mike said: While I prefer this:

int minimumIntegerInBox (Collection<Box> boxes) {
    int result = Integer.MAX_VALUE;
    for (Box box : boxes) {
        if (box.get() instanceof Integer) {
            result = Math.min (result, Integer.class.cast (box.get()));
        }
    }
    return result;
}

that would be cheating.

It isn't cheating, but it isn't answering the question I posed, either. It's more or less the obvious thing to do in Java or Lisp. But conceptually it is pretty primitive. I don't care about the machinery involved in traversing a list (the looping construct). I want to take a binary operation like Math.min and make it n-ary.

Mike gave a very complete solution, but I'm only going to reformat the relevant part:

public static int minimumIntegerInBox(Collection<Box> boxes) {
    Iterable<Box> intBoxes = 
        filter (boxes,
                new Function<Box, Boolean>() {
                    @Override
                    public Boolean of(Box domainItem) {
                        return domainItem.get() instanceof Integer;
                    }
                });

    Iterable ints = 
        map (intBoxes,
             new Function<Box, Integer>() {
                 @Override
                 public Integer of(Box domainItem) {
                     return Integer.class.cast(domainItem.get());
                 }
             });

    return minimumElement(ints);
}

public static int minimumElement(Iterable items) {
    return best(
        new Function<Pair, Boolean>() {
            @Override
            public Boolean of(Pair domainItem) {
                return domainItem.second() < domainItem.first();
            }
        },
        items);
}

That's a lot closer to what I had in mind, but these are untyped Boxes. I want to use parameterized Boxes.

An illustrative problem.

2010-06-08T13:01:00.000-07:00

I'm working on a fairly simple problem and I think it illustrates something interesting. Here is the problem statement:

A `box' is an object that has a name and can hold another object of a particular type (that is, there are boxes for integers, boxes for strings, boxes for floats, etc.) You are given an unordered collection of various boxes and must find the smallest integer among the subset of boxes that contain integers.

To make it a tiny bit more challenging, we won't just write an ad-hoc loop. We'll use map, filter, and fold-left. Since fold-left is a bit scary, I'll write that part:

(define (best better? list)
  (fold-left (lambda (best-so-far candidate)
               (if (or (null? best-so-far)
                       (better? candidate best-so-far))
                   candidate
                 best-so-far))
             '()
             list))

(define (minimum-element list)
  (best < list))

So assuming that *box-list* is a variable containing our list of boxes, Exercise 1 is to write a program in Scheme or Lisp using map, filter, and minimum-element that finds the smallest integer (fixnum) in the boxes.

Too easy? Let's make it a bit trickier: Code up the identical solution in Java.

Assume that Box is a generic (that is, parameterized) type, so Box<Integer> would contain an Integer and Box<String> contains a String, etc. The variable BoxList would be declared as Collection<Box<?>>, so we want a method with this signature: int minimumIntegerInBox (Collection<Box<?>> boxes)

I don't think it can be done without getting at least one Unchecked conversion warning, but a cleverly placed @SuppressWarnings("unchecked") will permit you to downcast a Box<?> to a specific type, and then everything else should type check.

International Lisp Conference 2010 - Call for Papers

2010-06-07T15:52:00.000-07:00

***********************************************************************
*                                                                     *
*                  International Lisp Conference 2010                 *
*                         October 19-21, 2010                         *
*                    John Ascuaga's Nugget (Casino)                   *
*              Reno/Sparks, Nevada, USA (near Lake Tahoe)             *
*                                                                     *
*           Collocated with SPLASH 2010 (OOPSLA & DLS & more)         *
*               see also http://splashcon.org as well as              *
*          http://www.dynamic-languages-symposium.org/dls-10/         *
*                                                                     *
*              In association with ACM SIGPLAN (PENDING)              *
*                                                                     *
*********************************************************************** 


The Association of Lisp Users is pleased to announce that the 2010
International Lisp Conference will be held in Reno, Nevada, in
collocation with SPLASH 2010.  The scope includes all areas related to
the Lisp family of programming languages.

Accepted papers will be published in the ACM Digital Library (PENDING).

Extended Abstracts and Papers must be written in English and submitted
electronically at http://www.easychair.org/conferences?conf=ilc2010 in
PDF or WORD format. If an Extended Abstract is submitted, it must be 
between 2 and 4 pages, with full paper to follow before final deadline.

Final submissions must not exceed 15 pages and need to use the ACM 
format, for which templates which can be found at:
    http://www.acm.org/sigs/pubs/proceed/template.html.


Important Dates:
****************

* Deadline for Abstract Submission      August      1, 2010
* Deadline for Paper Submission         September   6, 2010
* Author notification                   September  20, 2010
* Final paper due (in electronic form)  October     5, 2010
* Conference                            October 19-21, 2010


Scope:
******

Lisp is one of the greatest ideas from computer science and a major
influence for almost all programming languages and for all
sufficiently complex software applications.

The International Lisp Conference is a forum for the discussion of
Lisp and, in particular, the design, implementation and application of
any of the Lisp dialects.  We encourage everyone interested in Lisp to
participate.

We invite high quality submissions in all areas involving Lisp
dialects and any other languages in the Lisp family, including, but
not limited to, ACL2, AutoLisp, Clojure, Common Lisp, ECMAScript,
Dylan, Emacs Lisp, ISLISP, Racket, Scheme, etc.

Topics may include any and all combinations of Lisp and:

* Language design and implementation
* Language critique
* Language integration, inter-operation and deployment
* Applications (especially commercial)
* 'Pearls' (of wisdom)
* Experience reports and case studies
* Reflection, meta-object protocols, meta-programming
* Domain-specific languages
* Programming paradigms and environments
* Parallel and distributed computing
* Software evolution
* Theorem proving
* Scientific computing
* Data mining
* Semantic web

We also encourage submissions about known ideas as long as they are
presented in a new setting and/or in a highly elegant way.

Authors concerned about the appropriateness of a topic may communicate
by electronic mail with the program chair prior to submission.

Each paper should explain its contributions in both general and
technical terms, identifying what has been accomplished, explaining
why it is significant, and comparing it with previous work. Authors
should strive to make their papers understandable to a broad audience.
Each paper will be judged according to its significance, novelty,
correctness, clarity, and elegance.

The official language of the conference is English.  Some further
information is available at the conference web site, with more details
added later.  See: http://www.international-lisp-conference.org

Technical Program:
******************

Original submissions in all areas related to the conference themes are
invited for the following categories.

* Papers: Technical papers of up to 15 pages that describe original
   results or explain known ideas in new and elegant ways, or extended
   abstracts of 4 pages soon followed by the corresponding full paper.

* Demonstrations: Abstracts of up to 4 pages for demonstrations of
   tools, libraries, and applications.

* Tutorials: Abstracts of up to 4 pages for in-depth presentations
   about topics of special interest for at least 90 minutes and up to
   180 minutes. 

* Workshops: Abstracts of up to 4 pages for groups of people who
   intend to work on a focused topic for half a day.

* Panel discussions: Abstracts of up to 4 pages for discussions about
   current themes. Panel discussion proposals must mention panel
   members who are willing to partake in a discussion.

* Lightning talks: Abstracts of up to one page for talks to last for
   no more than 5 minutes.

Depending on the technical content, each submitted paper will be
classified by the program committee as either a technical paper or as
an experience paper; and authors will be informed about this
classification.  Note that all interesting submissions are considered
valuable contributions to the success of the ILC series of
conferences.  As in past ILC's since 2007, accepted papers in both
categories will be presented at the conference, included in the
proceedings, and submitted to the ACM digital library.


Organizing Committee:
*********************

* General Chair:
   JonL White          The Ginger IceCream Factory of Palo Alto, ALU

* Program Chair:
   Antonio Leitao      Instituto Superior Tecnico/INESC-ID

* Conference Treasurer:
   Duane Rettig        Franz, Inc., ALU Director

* Publicity Chair:
   Daniel Herring      ALU Director

* ALU Treasurer:
   Rusty Johnson       TASC, Inc., ALU Director


Program Committee:
******************

* Antonio Leitao      Instituto Superior Tecnico/INESC-ID, Portugal
* Alex Fukunaga       University of Tokyo, Japan
* Charlotte Herzeel   Vrije Universiteit Brussel, Belgium
* Christophe Rhodes   Goldsmiths College, University of London, UK
* Didier Verna        EPITA Research and Development Laboratory, France
* Duane Rettig        Franz, Inc., USA
* Giuseppe Attardi    University of Pisa, Italy
* Jeff Shrager        Symbolic Systems Program, Stanford University, USA
* Joe Marshall        Google, Inc., USA
* Julian Padget       University of Bath, UK
* Keith Corbet        Clozure Associates, USA
* Kent Pitman         PTC, USA
* Manuel Serrano      INRIA Sophia Antipolis, France
* Marc Feeley         University of  Montreal, Canada
* Marie Beurton-Aimar University of Bordeaux 1, France
* Mark Stickel        SRI International, USA
* Matthias Felleisen  Northeastern University, USA
* Scott McKay         ITA Software, USA


Contacts:
*********

* Questions:         ilc10-organizing-committee at alu.org

* Program Chair:     ilc2010 at easychair.org

For more information, see http://www.international-lisp-conference.org

It was quiet..... too quiet.....

2010-06-04T09:52:00.000-07:00

Things seemed a bit quiet here until I looked at some older posts and discovered comments I hadn't seen before. It seems that gmail had gotten into its head that forwarded posts were spam. Wonderful. My apologies for not responding to people.

Choose and perish

2010-06-04T09:37:00.000-07:00

I chose ok...

(I had to retouch the buttons because the camera overexposed them.)

2010-05-26T09:53:00.000-07:00

I have two collections and I need to see if one of them is a representation of the other. Since each kind of object has an Id, the two sets of Ids should match, but since collections are unordered, you can't just do a pairwise match.

The solution is to use the containsAll method to see if each collection contains all the elements of the other one. In Scheme this is trivial:

(let ((foo-ids (map foo-id (get-foos)))
      (bar-ids (map bar-id (get-bars))))
  (and (contains-all foo-ids bar-ids)
       (contains-all bar-ids foo-ids)))

in Java, not so easy:

Collection<Id> fooIds =
    Collections2.transform(getFoos(),
                           new Function<Foo, Id> () {
                             @Override
                             public Id apply (Foo foo) {
                               return foo.getId();
                             }
                           });
Collection<Id> barIds =
    Collections2.transform(getBars(),
                           new Function<Bar, Id> () {
                             @Override
                             public Id apply (Bar bar) {
                               return bar.getId();
                             }
                           });
return fooIds.containsAll(barIds) &&
       barIds.containsAll(fooIds);

I know that this is not Java's forte, but this isn't some obscure stratified monadic combinator, it's just map for heaven's sake! If future maintainers of this code can't handle map, maybe they should consider a career in the fast food industry.

Pathetic

2010-05-25T16:26:00.000-07:00

Collection expectedIds =
    Collections2.transform(fooCollection,
                           new Function () {
                             @Override
                             public Id apply (Foo foo) {
                               return foo.getId();
                             }
                          });

Looking forward to ILC 2010

2010-05-25T09:12:00.000-07:00

Daniel Herring sends this announcement:

The ALU is pleased to announce that the International Lisp Conference 2010 (ILC-2010) will be held mid October in Reno, Nevada.
ILC-2010 will be colocated with OOPSLA/SPLASH.
Colocated conferences allow people to explore other sessions; but the ILC itself will be the same independent, lisp-intensive event you've grown to love.
More announcements, including the ILC conference website and call for papers, will appear in the coming weeks.
Sincerely,
p.p. Daniel Herring
ALU Board of Directors

I'm planning on being there. Anybody want to write a paper?

Doing it wrong

2010-05-11T12:17:00.000-07:00

I'm hacking some Java code and I'm going to do a query and return some objects. Since I have no need to mutate the collection, I decide to use an immutable list. To make a long story short, I did this:

import com.foo.bar.ImmutableList;

final ImmutableList.Builder<Object> intermediateCollection = ImmutableList.builder();
    ...
    if (fromObjectClass.isInstance(object))
       intermediateCollection.add(object);
    ...
    query (intermediateCollection.build())

This is bad enough, but we'll let it slide.

It turns out that the query method wants to mutate the collection. (This is obnoxious. When I borrow something I try to leave it in the same condition as when I got it. I don't go mutating it and I expect my libraries to extend the same courtesy.) I guess I don't care all that much — I can simply make the collection mutable.

So why can't I just delete the `Immutable' prefix?

// Now it is named `Lists' with an `s'
import com.foo.bar.Lists;

// Now I have to specify the implementation technique.
// Why isn't it a List.builder?
  final List<Object> intermediateCollection = Lists.newArrayList();

// Why isn't there build that is a no-op?
   query (intermediateCollection)

This is simply wrong.

2010-05-06T12:26:00.000-07:00

Not too many takers on that batch of questions. Oh well.

Anyone care to take a stab at how these notions of equality relate to procedural abstraction?

Pondering

2010-05-05T09:18:00.000-07:00

What does it mean to say that two programs are ‘the same’?

What does it mean to say that two programs are ‘equivalent’?

What is the difference between intensional and extensional equivalence?

What is ‘observational equivalence’?

C++ vs. Lisp

2010-05-04T08:36:00.000-07:00

Yes, a provocative title.

In this blog post, Mr. Ebhakt decides to compare C++ and Lisp. (Go ahead and read it, I'll wait...)

Wow! It seems the original article was written by Brandon Corfman. My apologies to Mr. Corfman. Shame on you, Ebhakt.

I had to laugh. First he is disappointed that it took him eight hours to find a solution (Norvig did it in two), and his initial attempt took 220 lines of code (Norvig did it in 45). One source of conciseness was because Lisp function calls return useful values while C++ function calls typically cause side effects. Thus the Lisp expression

(format t "~a:~ {  ~a}~%" num (reverse words))

could make use of the return value from reverse whereas the C++ version

words.reverse(); 
cout << num << ":"; 
for (list::const_iterator i = words.begin(); i != words.end(); ++i) 
    cout << *i; 
cout << "\n";

could not.

Mr. Ebhakt also noted that ‘most of the complexity of the STL arises from its explicit use of iterators.’ Henry Baker pointed out in 1992 that iterators are “Signs of Weakness in Object-Oriented Languages”.

Armed with this knowledge, Mr. Corfman “decided to rewrite all of the STL’s algorithms to accept containers instead of iterators” and “also make the algorithms (where possible) return copies of containers instead of iterators”. Furthermore, he decided “to build another layer of utility functions on top of the STL to perform common tasks such as tokenizing strings, looking up values in containers, reading from files” etc. The end result? “The new line count is 79 lines.”

I wont bother quoting Philip Greenspun at this point.

Mr. Corfman sums it all up: ‘C++ isn’t all that bad.’

Of course it doesn't have garbage collection, macros, and closures, but it has ‘extensive library support’ (which he just spent hours throwing away and re-implementing) ‘and of course, its premier status’ which, with an additional two dollars will buy you a large coffee.

Mr. Corfman came so close to the mark and just missed it. Lisp isn't magic, it's at a sweet spot in the design space. Lisp doesn't do anything the other languages cannot, but it does what the other ones do not. It works that much harder for the programmer so the programmer can do other things (like program). Sure, a Ford Model-A isn't all that bad. It can get you where you're going and it is unsurpassed in popularity, but if you spend most of your waking hours behind the wheel, wouldn't you rather drive a Dusenberg?

After finding out that this was written by Brandon Corfman, I decided to see if his opinion had changed at all. On his Road to Lisp page, he says “Lisp still has the definite edge on the power curve. I think the clue for me is that I still find myself saying, ‘Why didn't they do this like Lisp?’”

Quasi-cranks

2010-05-03T17:55:00.000-07:00

Every now and then I run into ‘quasi-cranks’ in the computer industry. These people don't fit the mold of the standard crank. For instance, they often appear reasonably normal (although in this field, there is more than the usual amount of latitude for ‘normal’), they generally don't rant unless you specifically mention certain trigger words, and they seem to have successful computer careers. But when you start talking about technical details, you realize that these people are profoundly confused.

I often help people debug their code. Most of the time I can follow what they're thinking and how the code is structured. Every now and then, though, I'll come across someone that has some insane hairball of code. They'll point out the location where the error is raised and explain what the intended behavior is. (I don't know why they insist on telling me this. If the code behaved the way it was intended, there wouldn't be an error.) I listen patiently and then ask them what the code actually did, and then try to understand where the reasoning went wrong. It's at this point I get the first inklings of weirdness. I'll find out that what they want to do is fairly simple, but that the error is bizarre. For example, they'll say they want to look something up in a table, but the error message is something like Error: Variable reference to syntactic keyword.

Now this can go one of three ways. The best is when I ask them if they're doing something weird and they sheepishly admit “Yeah, I thought I could model this with a first-class environment... I guess I should use a hash table.” These people have a future in computers. They're exploring.

Second best is when they say “I'm using a first-class environment to hold my lookup table.” and when I suggest some more conventional mechanism they assert “No, I need to be able to call eval.” and it turns out they have some hair-brained idea that kinda sounds plausible, but won't work in practice. These people can make a living in computers, but they need a structured environment.

Then there are the third type of people. When you look at the hairball of code you see a bunch of things that make no sense at all: continuations that are captured, but not bound to a variable, spurious data structure copying, strange and unexpected variable names, checks for errors that cannot logically occur, etc. If you ask them what they are doing, they'll say something like “I have to eval the current continuation on the stack.” or “That forces the oldspace to swap.” If you try to encourage them to try a standard approach they explain “Look, this code pushes a binding on the continuation and I need to find a way to remove it. The error message is because the garbage collector is evaluating the wrong binding. If I could remove the binding here, then the collector will see the correct binding here.”

The first couple of times I ran into people like this I tried to nudge them in the right direction. It doesn't work. People like this are profoundly confused. I'm not sure what they are doing. They think they are programming, but the logic is unrelated to any model of programming I am familiar with. I'll usually feign ignorance and suggest some debugging tool or something. (Sometimes they'll come back with a ‘solution’ to their bug: “Oh yeah, it was easy, I just pushed a second null on the continuation.”)

You can tell these quasi-cranks from the way they use computer jargon and terminology. They “misunderstand or fail to use standard notation and terminology,” and “ignore fine distinctions which are essential to correctly understand mainstream belief.” (as per the Wikipedia article). But it astounds me that some of these people seem to have careers as programmers despite their confusion.

Importance of terminology

2010-04-30T09:14:00.000-07:00

An upcoming study of first-year computer science students has an interesting observation about terminology. It seems that their understanding of the computer science vocabulary is much worse than one would expect. You cannot blame the teachers because I'm sure they were unaware of the problem. You cannot blame the students for being `dumb' because nearly all of them could identify a `function body'. Yet fewer than one in three could tell you what is meant by a `defined name' or a `predicate'. Really! The results surprised me, but in thinking about it, I have a couple of personal anecdotes that highlight the problem.

Every year or so there used to be a heated debate on one or more usenet groups (remember usenet?) between the static and dynamic type factions. (I won't argue either side.) One year, however, I encountered someone who challenged me about my viewpoint. He said that he knew many people who held a similar viewpoint to mine, and he had a lot of respect for them. They weren't idiots. But he could not understand their rationale. His viewpoint made perfect logical sense to him, so how could another intelligent person disagree so violently? He didn't want to argue, he wanted to understand how anyone could find the alternative viewpoint to be as logical. (He assumed it must be so, or there wouldn't be so many respectable adherents to it.)

We discussed it back and forth for a while in a non-heated way and it dawned on me that the fundamental problem is simply one of terminology. `Static typers' and `dynamic typers' have completely different understandings of the word `type'. They cannot agree on the simplest things because they each think the other knows what he means by `type'.

For the sake of clarity, I'll lay out the definitions:

Type₁ — an equivalence class for data. Two objects are of the ‘same type’ if operations on one could be (or could have been) performed on the other with analagous results. For example, ‘integer’ is a type because objects like ‘3’ and ‘42’ can both be added, subtracted, multiplied, and divided.
Type₂ — a purely syntactic label that can be assigned to a code fragment. There are rules for assigning such labels to primitive fragments and rules for composing types as the code fragments are composed. Certain compositions are disallowed. A well-typed program has no disallowed compositions, and a type-checking program can verify this. By clever construction of the rules, certain useful runtime properties can be proven.

I think you can see that these two definitions have almost nothing to do with each other.

Once I understood this, I stopped using the word ‘type’ and started talking about ‘tags’ — manifest metadata attached to all objects in memory that describe what each object is. ‘Static typers’ understand the utility and benefit such things, they don't understand why anyone would want to forego compile-time ‘type checks’. They don't mean the annoying task of decorating every variable and procedure in the system with a ‘type specifier’, but rather having the compiler notice that your code said to vector-ref the result of a floating point divide and that most likely is not what you intended. Notwithstanding the contrarians who complain that maybe they did want to vector-ref a float, every Lisp hacker I know of appreciates getting early notification of these kind of errors (provided that false positives are very rare and it remains unnecessary to kowtow to the compiler).

Next anecdote later...

Persistent store: a new record type

2010-04-29T08:22:00.001-07:00

The object map allows us to abstract away the physical addresses where our objects are stored, but only if we can remember where we put it! We need another record type and things will get much more interesting.

A commit-record is a special record that we will write to the durable storage. The commit-record will contain (among other things) the physical address of the root of the object map. We'll require a little more functionality from the durable storage layer. When we first use a previously existing persistent store, we need to ask the durable storage layer to find the most recent valid and complete commit record. It can do this by starting at the newest record and reading backwards through earlier records until it finds one.

Since computers are unreliable, we have to take into account the possibility that the computer could crash in the middle of writing a commit record. When looking for the commit record on restart, we ignore any partially written commit records. When we're writing a commit record to the durable storage, we don't return control until we're sure that the record is durably saved and complete. If the computer crashes at any time before that last byte is written, we will recover using the previous valid commit record, and if it crashes at any time after that last byte is written we'll use this one.

There is an extra burder on the durable store to be able to find the most recent commit record, but we can take a different burden off the store. Instead of insisting that every record be durably written at the time we send it to the store, we can allow most of the records to be buffered until it is more convenient to write. We only insist that the buffers be flushed prior to writing the commit record. This makes a huge difference in the performance of the store.

There is a design decision to be made at this point. When we save durable objects, we can either send the object and the object-map records to the durable store immediattely, or we can defer sending them until we want to write the commit record. The eager strategy is more responsive when we are doing a lot of writes because we can start writing records while we're computing. The lazy strategy will reduce the total amount of traffic (every time we modify the object-map, we need to write new object-map records, if newer entries supersede records that haven't even been written, we can elide the write), but when we eventually do write the commit record, there will be a flurry of activity as we force the pending writes. This will cause a noticable pause at commit time.

There is another interesting design decision. In many cases, it is ok to lose a few seconds of work if the computer crashes. You wouldn't want to lose anything if you were logging financial transactions, but if you were checkpointing a text file, you might consider it ok if two or three of the most recently typed letters didn't get saved. When the computer restarted, you'd re-open the text file and find that what you were typing wasn't completely there, but was mostly there. You can re-enter the last couple of keystrokes. If this is acceptable — and it is for some applications and not for others — then it is not necessary for commit records to be immediately written to durable storage so long as they are written in a reasonably timely manner (within a second or two). The freedom to defer writing commit records like this will also improve performance quite a bit.

Exercise: Add commit records to your durable store and the ability to recover the most recent commit record when opening an existing store.

Open letter to the SEC

2010-04-27T13:46:00.000-07:00

To Whom it may concern:

In the document entitled

    SECURITIES AND EXCHANGE COMMISSION
    17 CFR Parts 200, 229, 230, 232, 239, 240, 243 and 249
    Release Nos. 33-9117; 34-61858; File No. S7-08-10
    RIN 3235-AK37 
    ASSET-BACKED SECURITIES

a number of changes to Item 601 of Regulation S-K, Rules 101, 201, 202 and 305 of Regulation S-T, a new Rule 314 of Regulation S-T and changes to Form 8-K are proposed. These changes are proposed to accommodate the filing of the ‘waterfall’ computer program. The document requests comments on this proposal.

Is it appropriate for us to require most ABS issuers to file the waterfall computer program?

As mentioned in the proposal, ABS issuers are currently required to submit an informal, ‘English language’ description of the waterfall. A computer program would be far more formal and less likely to be ambiguous or misinterpreted.

Is it appropriate to require issuers to submit the waterfall computer program in a single programming language, such as Python, to give investors the benefit of a standardized process? If so, is Python the best choice or are there other open source programming language alternatives (such as PERL) that would be better suited for these purposes?

The proposal goes to great lengths to justify the choice of Python as the language in which the waterfall program should be expressed. Unfortunately, every one of the justifications is either incorrect or irrelevant.

Python is an open source interpreted programming language. — Python is more accurately described as a family of programming languages with several implementations. The Python Software Foundation supports one particular implementation, but both Microsoft and Nokia offer alternative implementations. The Python Software Foundation provides an interpreter, but there are versions of Python that are fully compiled, byte-code compiled, or JIT compiled.
Open source means that the source code is available to all users.— This is true, but irrelevant. INTERCAL is an open source language, yet it is completely unsuitable for the purposes of writing a waterfall program. On the other hand, the Microsoft implementation of ECMAScript is proprietary, yet ECMAScript is certainly a language to consider for waterfall programs.
An interpreted language is a programming language that requires an interpreter in the target computer for program execution. — Interpretation is a technique for implementing a language. Few languages require an interpreter, and as noted above, compilers for Python exist.
Since Python is an interpreted language that does not need to be compiled prior to running it, executable code would not need to be published on EDGAR. We define executable code in Rule 11 of Regulation S-T [17 CFR 239.11] as instructions to a computer to carry out operations that use features beyond the viewer's, reader's, or Internet browser's native ability to interpret and display HTML, PDF, and static graphic files. Such code may be in binary (machine language) or in script form. Executable code includes disruptive code.— A Python program is most certainly ‘executable’ by the definition supplied.

The proposal appears to be suggesting that safety is an important desideratum. This includes the safety of the EDGAR system as well as the safety of the investors that would presumably use the waterfall program. The proposal concludes that a language that is executed by an interpreter would be inherently safer than a compiled language. This is false. There has been a considerable amount of research into computer safety, and it is clear that safety is very hard to achieve even if it is the highest priority in the design. Provable safety is not, and never has been, a goal of Python.

To conclude, I believe that a formal description of the waterfall algorithms written as a computer program may be quite beneficial to investors. The proposal, however, fails to enumerate the desiderata for the language such a program would be written in. The proposal makes a few erroneous assertions and then puts forward Python as a suggested language. While Python is a popular language, it was never intended to be used as a critical component of such an important part of the U.S. economy.

I suggest that Securities and Exchange Commission, if they intend to pursue the path of requiring a formal waterfall program to be provided, follow a formal process for finding or developing a suitable language. First, the requirements for such a language need to be specified. Second, these requirements should be compared against existing and proposed languages. Finally, one or more of the languages should be adopted and implemented.

Sincerely,
Joe Marshall

More on persistence

2010-04-27T11:32:00.000-07:00

I haven't forgotten about persistence, I've just been busy.

When I last blogged about it, I discussed the need for an object-map. The object-map maps logical object ids to the physical location that the durable store placed the object. We'll be putting a couple more kinds of things in the durable store, so at this point it is a good idea to add a record abstraction on top of the durable store. It is easier to show this than to describe it. Here are the actual contents of a test durable store:

;;; A persistent store.  Do not edit.
(object 1 929 <string> 1 "zip")
(leaf 1 38)
(object 1 269 <string> 1 "zero?")
(leaf 1 82)
(branch 1 116 0 38)
(object 1 387 <string> 1 "yield-current-thread")
(leaf 1 148)
(branch 1 0 197 82)
(leaf 1 38)
(leaf 1 82)
(branch 1 242 230 148)
(object 1 535 <string> 1 "xsubstring-move!")
(leaf 1 277)
(branch 1 322 0 38)
(branch 1 242 335 148)
(object 1 295 <string> 1 "xsubstring-find-previous-char-in-set")

A ‘record’ is simply a list. The first element is one of object, leaf, or branch. The second element is the version number of the record layout in case I decide to change how the record is represented. The remaining elements are the contents of the record. For a leaf, it is simply the address of the object that this leaf represents. For a branch, it is the addresses of the left and right child and the address of the object the branch represents. (This is using a functional binary tree as detailed in the code.) An object record has four additional components. First is the object-id. Second is the data tag of the object. Third is a version number of the serialization method for the object and finally the serialized representation of the object itself.

This is clearly not the most parsimonious representation, and it could be made much more robust by including record length information, checksums or CRCs, and by ensuring that user data (such as those strings) cannot spoof a record boundary, but this is demonstration code, not production code.

In the next installment, we add another record type.

The Education of JRM

2010-04-23T10:01:00.000-07:00

I learn so much from the Internet. Yesterday, someone posted a link to my post about Java. I got close to 3 orders of magnitude increase in traffic. Many people commiserated with me, and I thank them. Some, however, went the extra mile:

An ellipsis has three dots.

Mea culpa. I was sloppy. Fortunately, another reader defended me:

An ellipsis at the end of a sentence is three dots, followed by a period. He/she did it right.

Alas, if I did it right it was only by accident.

There should be a space between the ellipsis and the period. Putting four dots ala George Lucas is incorrect....

I'm flattered to be placed in such good company!

One reader pointed out that the problem might not lie in Java, but within me:

This is what reflection is for. If you can't solve this problem with reflection, then you don't really have reflection.

while others offered concrete advice:

Maybe you just need to learn to type faster.

and still others tactfully suggested I broaden my horizons:

ever code in C++? this isn't unique to Java, noob.

I thank you all for the advice and the spirit in which you offered it. I believe I'll reflect upon it this weekend — assuming I really have reflection. I will continue posting in the hope that I can be further edified.

Whenever I write code in Java....

2010-04-21T16:18:00.000-07:00

Whenever I write code in Java I feel like I'm filling out endless forms in triplicate.

“Ok, sir, I'll just need your type signature here, here, and ... here. Now will this be everything, or...”

‘Well, I might need to raise an exception.‘

The compiler purses its lips.“An exception? Hmmm... let's see.... Yes, I think we can do that... I have the form over here... Yes, here it is. Now I need you to list all the exceptions you expect to raise here. Oh, wait, you have other classes? We'll have to file an amendment to them. Just put the type signature here, here, ... yes, copy that list of exceptions....

2010-04-21T09:12:00.000-07:00

Student M overhears the argument between Students A and T. “What seems to be the problem?”

Student T explains, ‘We're at an impasse. I want to be able to change the semantics of the language...’

Student A says “... and I want the semantics to be stable.”

Student T says ‘It seems to me that if the program is a tool for solving a problem, then the language itself is just another tool. I should be able to make changes to the language if it helps solve the problem.’

Student A replies “And I have no problem with that in principle, but when I'm writing a program, I need to know what the language semantics are so I can have some idea about whether my program will work. If the semantics change after I write the program, I won't even know whether I have a program. Mangle the semantics all you want, but then tell me what they are and don't change them!”

Student T says ‘I'm not going to “mangle” the semantics. But I don't want to lock myself out of a solution for your convenience. I want to be able to take whatever baseline semantics we have and tweak them as appropriate, but I can't change the semantics before I write the program the changes them!’

Student A says “This is just impossible.”

Student M interrupts “Time out, everyone. Ok, now let me get this straight. You...” and he points to student A, “want the meaning of your code to be stable, and you...” (he points to student T) “ want to be able to tailor the semantics to suit you. That's simple! Why are you arguing?”

Students A and T look confused. ‘Simple?!’

Student M says, “Of course. You both agree that changing the language will change the semantics, and conversely changing the semantics changes the language...”

Students A and T nod.

Student M turns to student A “So you write your code in your language (let's call it L), and we'll be sure that L has stable, static semantics that never change.”

Student A says “That's what I'm talking about.”

Student T objects ‘Hold on! You're just completely ignoring me! What if I don't like the semantics?’

Student M turns to student T “I'm not done, yet. You want the freedom to morph language L into language L', which is very much like L, but with maybe a few changes...”

Student T interrupts ‘.. or a lot of changes. And not just L', I want L, L', L'', L''', whatever changes I think are necessary and whenever I think they are necessary.’

Student M continues “... or a lot of changes. I get you. Now here's the question: If I have a program in language L, but I have a machine that runs a different language — call it C — what do I do?”

Student T replies ‘Write an interpreter...’

Student A answers “ ... or a compiler.”

Student M says “Bingo! Problem solved. Simply use language L as the base language for an interpreter or compiler for programs in L' (or L'' or L''', etc.)”

Student A thinks for a moment then says “Works for me. If I need to understand code written in L', I can just compile it down to L.”

Student T looks dubious. ‘Wait a second. You're suggesting I write a compiler? What if I want several different language features to mix and match? I'm supposed to write compilers for each of them?!’

Student M shrugs “Well, you're the one that wants to change the language, you can't expect student A to write them. Besides, it isn't that much work.”

Student T protests ‘Not that much work? It's a compiler! Flow control, analysis, register allocation, code generation! I just want to tweak the language, not invent a whole new one from scratch!’

Student M counters “Who said you need to do all that? A compiler is simply a program that translates code from one language to another, right? If you can express the constructs of language L' (or L'' etc.) in terms of language L, then that's all you need to do. If you're really just tweaking the language, then your ‘compiler’ is mostly the identity function.“

‘And the parts that aren't?’

“Macros.”

Is student M's solution reasonable?

Another wacky idea

2010-04-15T09:12:00.000-07:00

Student T exclaims “I have a great idea!

“Sometimes I want to make a computer language that is very similar to an existing language with just a couple of exceptions. Wouldn't it be cool if we could just tweak the semantics of the existing language?”

Student A asks ‘What do you mean? What part of the semantics?‘

“Oh, I don't know... Anything!”

‘Anything? Anything at all?’

“Sure. Why limit ourselves?”

‘Like, say, adding or removing special forms?’

“Of course. Anything!”

‘How about changing from call-by-value to call-by-name?’

“That would be harder, but why not? Imagine you're running a program and you realize you need lazy evaluation for some part of it. Well, you just turn on lazy evaluation for that segment of code and turn it off again when it returns! Voila!”

‘What? While the code is running?’ Student A thinks for a moment and says, ‘So in essence you want the language semantics to be a function of time.’

Student T replies “No no no. I just want to be able to change them on the fly if I want.”

Student A says ’Yes, that's what I mean. At different times you could have different semantics.’

Student T says “Yes, but only if you change them.”

‘And how do I change them?’

“You just call a special primitive or something from your program.“

‘So if the language semantics can change over time, doesn't that imply that the meaning of a program can change over time as well?’

Is Student A right?

2010-04-14T08:11:00.000-07:00

Let me propose these thoughts: a “semantics” is a way of associating meaning with programs. A “formal semantics” uses well-known mathematical models in an attempt to be thorough, precise, and consistent. An “informal semantics” uses human language, analogies, and examples in an attempt to be more concise and easier to understand.

As a programmer, you need to have some idea of semantics in order to get anything done. Even something as simple as the expression x + 1 presupposes that the symbol + has something to do with addition, the symbol 1 names a literal number, and the symbol x names something that can be understood numerically. Your understanding doesn't have to be complete (how does that supposed addition handle overflow?), and it doesn't have to be correct (maybe x is a string and + performs concatenation), or even consistent, but you can't work with no understanding whatsoever.

Does that seem like a reasonable point of view?

2010-04-13T18:59:00.000-07:00

It's clear that you don't need to fully understand the formal semantics of a language in order to program in it. (There are a lot of languages for which the formal semantics haven't been specified.) How far could you get without knowing the informal semantics?

Student Z has another complaint

2010-04-12T17:51:00.000-07:00

Student Z raises his hand in class. He says “Ok, so I guess I see a reason to do something with code other than run it. But I still think there's too much academic wankery in this field. Look at all these discussions of meaning and semantics. Who cares? Your average hacker doesn't bother with semantics, he just wants to get the job done.”

Well, obviously I'm setting up Student Z as a straw man, but how important are the semantics of a language? Are they simply a curiosity for ‘language lawyers’ and mathematicians to worry about, or are they a tool that is used daily by programmers?

Improvements

2010-04-10T13:00:00.000-07:00

Of course the next day after you upload something you find bugs. If you go to http://code.google.com/p/jrm-code-project/source/browse/#svn/trunk/PStore you will find not only updated versions of the object-map and persistent tree code, but also a very primitive serializer and deserializer (using John Cowan's suggesting of read and write).