a universal printer for Haskell?

Bernard James POPE bjpop@cs.mu.OZ.AU
Mon, 18 Feb 2002 22:11:55 +1100 (EST)

Hi all (warning long post),

Sorry to dredge up past discussions, but this has been burning in my mind
and I wanted to get further opinions.

I, and I assume many other Haskell programmers would from time to time like
a universal print mechanism, something that can turn an arbitrary value
into a String.

According to Wadler and others [1], this gives a language designer nightmares.
It certainly gives me headaches.

So I want:

   toString :: a -> String

We all know you can't do that in Haskell (without some fancy primitive), 
so maybe:

   toString :: ToString a => a -> String

(of course I've just asked for the Show class).

But the problem is not solved (drum roll please). Even first time programmers
know the pitfalls of trying to show the empty list:

   show [] ---> kapow!

But you ought to be able to print the empty list, 
without having to make some bogus type qualification (which 
is in general not a solution to the problem of printing arbitrary values).

Previous discussions [2], have considered passing bottom dictionaries for
variables like the 'a' in 'forall a . [a]', in cases where the
"a does not matter". The approach discussed was
converting such "don't matter" variables into an Empty type which is
magically an instance of every class, or at least the Show class. 
Arguments were raised against this
showing that it is quite hard to determine when such variables really
do not matter. Subtyping was also considered, but I don't see that
coming to Haskell in the short term.

What if only the compiler could instantiate the ToString class?
What I mean is, imagine the class ToString being avilable in every program,
but restricted so that the programmer could not make their own instances
of the class, only the compiler.

Lets generalise a bit.

We have a type:

   data Meta = MApp String [Meta]
             | MInt Int 
             | MChar Char
             | MFunction

and a class:

   class Reify a where
      reify :: a -> Meta


   toString :: Reify a => a -> String  
   toString x = metaToString $ reify x 
              metaToString x = ...  {- easy enough -}

The compiler is required to generate instances of Reify for all types
in the program (instances for built in types are hand-coded in a Standard
Library). Instances should be derived directly from the syntax of each
algebraic data type.

So for example:

   data List a = Nil | Cons a (List a)

The compiler derives:
   nilStr = "Nil"
   consStr = "Cons"

   instance (Reify a) => Reify (List a) where
      reify Nil = MApp nilStr []
      reify (Cons h t) = MApp consStr [reify h, reify t]
Deriving could be done ala Drift, but in the compiler itself.

Since it is impossible for the programmer to define their own
Reify instance, it should be possible to adopt the 'defaulting to Empty'
rule for "type variables that don't matter", as in:

   reify Nil ---> Mapp "Nil" []

and so:

   toString Nil ---> "Nil"

No matter which type of list Nil belongs to it always and only reifies
to the one representation. The problem with defaulting to Empty with Show
is that Show can be user-defined.

What about overloaded constants?

   class Boo a where
      constant :: a

   reify constant  ---> unresolved constraint '(Reify a, Boo a) => a'

We could make Reify a superclass of Boo:

   class (Reify a) => (Boo a) where ...

Does this mean we have to modify the Prelude?

   class Reify a => Num a

I'm not sure. If we take for granted that EVERY type in the program is
an instance of Reify, perhaps there is a way to modify the dictionary 
transformation to insert Reify dictionaries where needed, without 
having to modify the text of the Prelude and user classes and so on - as
if the superclass relationship was implicit in the program. Okay, so this
is very hazy.

The mechanism breaks abstraction boundaries, but when I am debugging my 
program and all I want to do is see what the data looks like, I don't care
much about the abstraction boundaries, I just want to print something
meaningful out. 

I can't print functions with this, except to get "Function". But I can live
with that.


[1] A Second Look at Overloading, Wadler, Odersky, Wehr.
[2] (see http://www.mail-archive.com/haskell%40haskell.org/msg09292.html)