Saturday, December 17, 2005

YHC and types

So it appears by some weird twist of fate that I'm going to be writing YHC's type checker, and it appears that over christmas is when I'm going to be starting on this task.

Yhc of course currently uses the nhc98 type checker. This, while it works well, could do with some improvement. My two personal bugbears with it are:
  • Type Errors
  • Lack of any extensions

If we use this program as an example:
main = print $ "a" == 5
yhc currently produces this type error:
yhcc: The class Prelude.Num has no instance for the type Prelude.[].
Possible sources for the problem are: 1:23
When type checking declarations at: 1:1-1:23

Okay, so from this we can get two pieces of information:
First, the type system thinks that lists are not numbers, quite reasonably.
Second, where the error came from.

Ghc produces this error:
No instance for (Num [Char])
arising from the literal `5' at jam.hs:1:22
Probable fix: add an instance declaration for (Num [Char])
In the second argument of `(==)', namely `5'
In the second argument of `($)', namely `"a" == 5'
In the definition of `main': main = print $ ("a" == 5)

This also tells us where the error is, and that it doesn't think lists are numbers. However it also provides quite a lot more information that is very useful for finding and fixing the bug:
  • It tells us the error in our own language - Haskell. If we were to write an instance for (Num [Char]), that's exactly what we would start by typing!
  • It tells us more information than is necessary - in order for there to be a type error all that mattered was we tried to match a number against a list, but the additional information that it was a list of characters gives added context, and makes it much easier for us to work out where the problem is.
  • It suggests a fix. Okay, in this case it's suggested what's probably a bad fix - we probably don't want strings to be numbers, but in many cases, this is exactly what would be needed
  • It tells us in more human terms where the error is. A human is not good at counting line and column numbers, they are good at looking for patterns like "it's in the comparison"

Okay, so type errors fall a long way short of ghcs, but even ghc's error messages are not yet good enough, as Olaf Chitil points out [1].

Secondly, you may have noted in all the posts we have made, that we intend to implement at least a few extensions to Haskell 98/06 (currently on the list are Multi parameter type classes, and all the jazz that goes with that). This means I need to understand how the type checker works in every detail, and know exactly where it needs extending in order to make things work. To get to this state, would take almost as long as it would for me to write a type checker that I understood in much more detail, and as such, my proposal is that I'm going to completely rip out the type checker, and replace it with something new and shiny.

My plan is to write a very compositional type checker as described by Olaf in his paper, and hopefully get the following benefits:
  • Good error messages!
  • Modularity - if the type checker is compositional, it should be easy to add new rules and extensions, and to enable and disable them
  • Understandability - Simple Haskell that just plugs together is good Haskell!
  • Having had a quick chat with Olaf about it - Speed. Hopefully, this should be a pretty quick type checker

So, I'm off to visit the pain monster for a bit to make sure I fully understand what I'm doing.

See you some other time.


author = {Olaf Chitil},
title = {Compositional Explanation of Types and Algorithmic Debugging of Type Errors},
month = {September},
year = {2001},
pages = {193--204},
keywords = {Hindley Milner type system},
note = {},
url = {},
publication_type = {inproceedings},
submission_id = {15958_1077221965},
booktitle = {Proceedings of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP'01) },
address = {Firenze, Italy},
publisher = {ACM},
refereed = {yes},


Blogger Neil Mitchell said...

My pet annoyance is that in Hugs:

(\x -> (case x of {[] -> 'x'; _ -> "x"}) :: String) []

The error message is that "x" should be a Char, because it doesn't use the type annotation other than as a check at the end. I don't know what nhc does, but Yhc should definately pay attention to this!

All in all, this would rock!

2:03 PM  

Post a Comment

<< Home