Monday, December 26, 2005

Crazy Ideas

Having a small, clean, simple, production strength Haskell compiler lets a lot of people come up with Crazy ideas that just weren't feasible before. (alright, so Yhc certainly isn't production strength yet, but it could be without too much work...)

Some of the crazy ideas are listed at on the wiki, some others have been sent out in emails. Quite a lot aren't crazy at all, but would be really useful! Just a quick summary of some side projects/tools that are being developed, or have been thought of:
  • Haskell HBC -> Java bytecode
  • Javascript runtime for HBC files
  • Python runtime for HBC files
  • Playstation port (entirely speculation so far)
I also came up with a new crazy idea for Yhc, HsNub. Have you ever written a function, and later found out that it did the same as a function in the prelude? Take the Yhc code base, I recently eliminated the function second, which is equivalent to the Prelude function const. It would have been nice if something spotted this and gave out a warning. With a portable bytecode, this isn't that much work - two functions can be seen as equivalent if they are identical at the bytecode level. I intend to write this tool once I have a working bytecode library - I don't expect it to take more than an hour at most - thats the nice thing about having a relatively simple Haskell implementation!

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:
jam.hs:1:22:
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.

Bob

[1] http://www.cs.kent.ac.uk/pubs/2001/1811/content.pdf
@inproceedings{1811,
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 = {http://www.cs.kent.ac.uk/pubs/2001/1811},
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},
}

Sunday, December 11, 2005

Yhc Core

Some people might have seen or heard of GHC's Core language, there is a detailed account of it here. As part of my PhD I need to convert from full Haskell to a reduced Haskell-like language. How should I go about doing this? Well the obvious thing is to use a Haskell compiler to translate to a reduced language, then tweak this reduced language to my personal taste. A few months ago when I started this process, the options available to me were:
  • GHC - a massive monster, but with an emerging API, and somewhat complex Core
  • Hugs - C, yuk!
  • nhc98 - doesn't work on Windows
With a choice like that, I went for GHC and started doing some work. It turns out the GHC Core that I was getting had let's, so learning let floating seemed necessary. Also all the symbols are nastily mangled - GHCziBase.ZMZN is the Core way of saying []. Also there is no natural correspondance between the original and the new names, and multi-module stuff looked like it was going to be a problem as well - HsAllInOne seemed to do the business, but thats yet another layer of mangling on top of that, which makes it look revolting.

Well that was 3 months ago I think, and since then an extra compiler has emerged, Yhc! So I thought I'd fire off Yhc and see what i got. Amazingly, I just compiled with -lift and suddenly everything looked beautifully close to what i wanted. The syntax was horrible, but it looked very nice! From this initial observation, I've hacked around a bit to try and define an easily parseable Core language for Yhc, which external tools (i.e. mine) can work with. It's a bit different from GHC's, compare and contast:
{from1 :: GHCziBase.Int -> GHCziBase.ZMZN GHCziBase.Int =
\ (n::GHCziBase.Int) ->
GHCziBase.ZC @ GHCziBase.Int n
(from1
(%case (GHCziBase.Int) zddNum
%of (tpl::GHCziNum.ZCTNum GHCziBase.Int)
{GHCziNum.ZCDNum
(tpl1::GHCziBase.ZCTEq GHCziBase.Int)
(tpl2::GHCziShow.ZCTShow GHCziBase.Int)
(tpl3::GHCziBase.Int -> GHCziBase.Int -> GHCziBase.Int)
(tpl4::GHCziBase.Int -> GHCziBase.Int -> GHCziBase.Int)
(tpl5::GHCziBase.Int -> GHCziBase.Int -> GHCziBase.Int)
(tpl6::GHCziBase.Int -> GHCziBase.Int)
(tpl7::GHCziBase.Int -> GHCziBase.Int)
(tpl8::GHCziBase.Int -> GHCziBase.Int)
(tpl9::GHCziNum.Integer -> GHCziBase.Int) ->
tpl3 n lit}))};
vs:
Main.from v379 =
(Prelude.: v379 (Main.from (Prelude.Prelude.Num.Prelude.Int.+ v379 1)))
A couple of differences to note. Yhc has no types, GHC has lots. Yhc resembles Haskell, GHC doesn't. The names are much clearer in Yhc. Yhc has a nice property that if you just cat all the modules together, it works perfectly. Another difference not shown here is that Yhc knows exactly where Main.from is defined, and can even track down exactly where that constant 1 comes from. It doesn't display this information, but it could do.

It finally looks like I've got a way to make Yhc part of my Phd!

[Note: all this code isn't in the build, its only in my copy, but it didn't take more than about 2 hours. Hopefully it can get into the main Yhc sometime soon]

Thursday, December 08, 2005

GHC Survey

The GHC team did a huge survey of Haskell users, its online here

Its quite interesting to go down the points, and see which things that Haskell users want, but can't find in GHC, and Yhc might be able to provide in the future.

  • GHC is too slow, Yhc will be faster
  • Performance and size of generated code - we win on size, loose massively on performance
  • Most requested feature is a debugger, I think we can win there :)
  • Portability and difficulty of compiling GHC, we can do that easily
  • API and feature changes, we loose massively
  • Quality of error messages, lets not go into that, but we can hopefully do better
  • Better documentation, well library docs we steal from GHC (draw), compiler docs are a wiki so hopefully that will be better quicker
  • GHC is too complex, well yhc is certainly a lot simpler
Hopefully we can learn from the work of others to give people what they want!

Sunday, December 04, 2005

Another port

Another day, another port. Now Solaris is a supported platform by yhc, see http://www.haskell.org/hawiki/Yhc/Ports for all the platforms supported. The nice thing about the Solaris port is that it required no changes whatsoever, hopefully there are lots of other platforms outthere which just need a quick compile on.

Along with vaguely standard architectures, there are also a few more "weird" platforms people are aiming for - Plan 9 and PalmOS for example. One person mentioned that the tagline for Yhc should be "64-bit clean, ultra-portable, pure Haskell 98 Haskell compiler!"