Compiler Proof of Referential Transparency

Programs in languages with mutation can make optimizations that Haskell programs can't, at least not without compiler magic, unsafePerformIO, or wrapping return types in the IO monad. Simple examples that spring to mind are memoization and splay trees. Here, operations that should have no semantic effects (calling a fib function or doing a find on a splay map) do have actual effects. It would be nice if Haskell programmers could write these optimizations and prove them safe with the type system, then use these functions as if they were referentially transparent.

My idea for this a few months ago was to use quotient types, since quotient types equate two actually different things that are functionally the same under some view. A Fibonacci function with a memoization table up to 100 looks the same to a caller as one with no memoized values at all, so they are equal under some quotient.

Other things came up, and I put off this idea for a while, and I have now seen a really cool way for Haskell programmers to deal with local effects. Ben Lippmeier's talk at the SAPLING June 2007 meeting (talk summary) explains region and effect inference for Haskell-like languages without sacrificing referential transparency or having to use the IO monad. This insight wouldn't solve the splay tree issue, because reading a splay tree does modify data that is not local to the reading function, though that modification should be opaque to clients.

I can't wait to see the full paper(s) and the implementation. Until I can, I'll have to settle for the slides from an earlier talk with more motivation.

Quotient Types for Information Hiding

Imagine you're writing a datatype for representing sets. You want to hide the internal representation of sets from clients, but you also want to allow clients to perform any operations as efficiently as if the internal representation were exposed. This is not easy, and it's why Data.Set has 36 functions, when all that are really needed to ensure the meaning of a set ("These elements are distinct") are toList and fromList. Of course, writing member :: Ord a => a -> Set a -> Bool as

member x y = Data.List.elem x (toList y)

is just awful, but the price we pay for efficient member is having to open up the module and break the abstraction if one of the 34 other functions doesn't do exactly what we want. In addition to this pain, there's some danger: functions like mapMonotonic are not really safe, and cannot be made so.

The papers I've been reading about quotient types:

• Bart Jacobs' Quotients in Simple Type Theory
• Aleksey Nogin's Quotient Types: A Modular Approach. (mirror 1, mirror 2)

We could alleviate all of this mess with quotient types. Quotient types allow modules to expose their internals with no danger of breaking abstractions. The quotients are the same as the mathematical quotients in abstract algebra, where they are used frequently. Back on the type theory side, the elimination rule for typing quotients depends not just on types, but on terms, and so requires a type system with dependent types. That's a shame, since dependent types are so tricky to typecheck. It would be great if there were some form of lightweight quotient types that didn't require the full power of dependent types.

The break-the-abstraction vs. lose-efficiency-&-safety issue reminds me of the difference between GADTs and lightweight static capabilities: GADTs are verbose, but they allow the client to safely and efficently operate on datatypes in ways that aren't covered by the library.