Tail recursion and debugging

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

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

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

• 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

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

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

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

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

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