the informal ramblings of a formal language researcher

Saturday, March 26, 2005

"Well-going programs can be typed"

Here is one of the stranger papers I've seen since the Forsythe one:

Well-going programs can be typed

The abstract:

Our idiomatically objectionable title is a pun on Milner's ``well-typed programs do not go wrong' --- because we provide a completeness result for type-checking rather than a soundness result.

We show that the well-behaved functions of untyped PCF are already expressible in typed PCF: any equivalence class of the partial logical equivalence generated from the flat natural numbers in the model given by PCF's operational semantics is inhabited by a well-typed term.


Its got Scott's $D_{\infty}$, PCF, Retractions, PERs, Logical Relations, . . .

And yet the paper itself is 50% tricks with Haskell type classes and GHC extensions.

I think the title is extremely misleading, at least based on my interpretation of the abstract. I thought the title meant: "if your untyped PCF program is well-behaved, then there is some way to add type annotations to yield a well-typed program (presumably with the same behavior)." But abstract semes to really be saying that if you have a well-behaved function, then there is some well-typed function with extensionally equivalent behavior; note the lack of constraint on the form of the typed program text and its relation to the untyped text.

test

My first post. Woot.

Catching up on West Wing. This one has Castro. Lots of Cuban-sounding music in the background. Its kind of like watching The Godfather Part II

Followers