... until the collector arrives ...

This "blog" is really just a scratchpad of mine. There is not much of general interest here. Most of the content is scribbled down "live" as I discover things I want to remember. I rarely go back to correct mistakes in older entries. You have been warned :)

2008-05-31

Y-Combinator Explained Using Javascript

We take recursion for granted in most languages.  Consider the factorial function, in Javascript:

function f(n) {
    return (n < 2) ? 1 : n * f(n-1)
}

This implementation relies on the fact that the name f being defined is the same as the f in the definition.  If you think for a minute about how a compiler would arrange this, you are likely to come up with an imperative solution.  For example, the compiler might leave a placeholder for f in the compiled definition and then update it to point to itself once the body has been compiled.

Systems like the lambda calculus, being purely functional, do not admit of such imperative solutions.  So how do you express recursion functionally?

One answer is a technical trick called the Y-combinator.  Let's start by writing a variation of the factorial function:

function f(r) {
    return function(n) {
        return (n < 2) ? 1 : n * r(n-1)
    }
}

Instead of taking an integer and returning an integer, this new f takes a function and returns a function.  The returned function can compute the factorial of an integer -- provided r was bound to a suitable function that ensures the requisite recursion.

What is the proper argument for r?  How about f?

f(f)(10)

It looks promising, but it won't work.  Look again at the definition of f.  r must accept an integer as its argument, but we have passed f which expects a function.  This is trickier than it looks.  What we need is something like:

f(f(f(f(f(f(...))))))(10)

Enter the Y-combinator. It is used like this:

Y(f)(n)

which evaluates to:

f(Y(f))(n)

that is:

f(f(f(f(f(f(...))))))(n)

That's easy to say.  But has does one write this mythical function Y?  I can't answer that, but Alonzo Church could.  Here's the definition he somehow puzzled out, in lambda notation:

λf . (λg . f (g g)) (λg . f (g g))

Applying Y to f, the evaluation sequence is as follows:

(λf . (λg . f (g g)) (λg . f (g g))) f

(λg . f (g g)) (λg . f (g g))

f ((λg . f (g g)) (λg . f (g g)))

f (f ((λg . f (g g)) (λg . f (g g))))

f (f (f ((λg . f (g g)) (λg . f (g g)))))

f (f (f (f ((λg . f (g g)) (λg . f (g g))))))

...

This has the desired property.  Here is Y expressed in Javascript, along with the almost-recursive definition of f and a test case:

function Y(f) {
   return function(g) { return function(n) { return f(g(g))(n) }}(
     function(g) { return function(n) { return f(g(g))(n) }}
   )
}

function f(r) {
   return function(n) { return n < 2 ? 1 : r(n-1) * n } }

alert(Y(f)(10))

Nifty, huh?  For those who want to play along in Scheme:

(define Y
   (lambda (f)
     ((lambda (g)
        (lambda (n)
          ((f (g g)) n) ))
      (lambda (g)
        (lambda (n)
          ((f (g g)) n) )))))

(define f
   (lambda (r)
     (lambda (n)
       (if (< n 2) 1 (* n (r (- n 1)))) )))

((Y f) 10)

2008-05-26

Equinox HttpContextManager Bug

There is a bug in the Eclipse Equinox implementation of HttpContextManager (version 1.0.0.v20070608).  It throws an array out-of-bounds exception on line 91:

for (int j = 0; j < resourceMappingElements.length; j++) {
    IConfigurationElement resourceMappingElement = resourceMappingElements[i];

i is the wrong index variable.  It should be j.

This code will only work when there is only one context with no more than one resource mapping.

2008-05-23

eXist Redux

The eXist XML database system has come a long way.  It now supports full XQuery and lots of HTTP interfaces.  It provides two out three layers in the so-called XRX stack (REST and XQuery).  Now how about a browser that does XForms to complete the stack?

Google Visualization API

Another Google service:  Google Visualization API.

The Third Manifesto

The Third Manifesto is Darwen and Date's latest take on the relational model.  It attempts to eliminate the OO/relational impedence mismatch by fully supporting the relational model (in contrast, say, to the limited support in SQL).

2008-05-08

Google Chart API

Google provides a nifty service for generating charts, the Google Chart API.  You can get charts like this...

... just by crafting up a special URL:

http://chart.apis.google.com/chart?chs=200x100&cht=lxy&chtt=A Google Chart&chd=t:10,20,40,60,80,100|99,50,15,125,300,43

2008-05-02

Hibernate Tuple Query Debugging

If you are using a Hibernate HQL query like select new MyClass(...) and Hibernate cannot find an appropriate constructor, the exception message does not tell you  the types of arguments for which it was looking.  You can find out by setting a breakpoint in org.hibernate.util.ReflectHelper#getConstructor(...).

Hibernate cannot find tuple classes that are inner classes.

2008-05-01

Broken Hibernate Tools for Eclipse

The Hibernate Tools 3.2.1.GA running in Eclipse 3.3.2 have problems.

The worst is that when you run your second HQL query, the IDE hangs.  You can avoid the hang if you remember to close the previous result set pane first.

Also, the Hibernate Entity Diagram view is completely missing.

Blog Archive