Thursday, January 05, 2006

More on Type Checking

Christmas was spent mostly researching methods of type checking, and trying to get a good handle on what I'm going to do. After much looking, I now have apparently three options:
  • Write a standard type checker based on the W algorithm.
  • Write one based on Olaf's compositional method.
  • Attempt to refine Neil's idea for coming up with simple rules to be fed to a solver.

I don't like the first option - it's been done before, it'll give us no advantage over any other compiler, and it's boring. Olaf's method seems to have two major advantages - clear code with an easy to understand algorithm, excellent error messages/debugging. Meanwhile Neil's method seems to be the black horse - we don't know what we'll get out of it. From the first attempt at it, it appears that clear code will be one of the advantages, but speed may be lacking.

I think I'm probably going to go with Olaf's method first - that way we get excellent error messages guaranteed (one of my primary aims). However, I do think there's genuine scope in Neil's solver method, and I think a second experimental type checker may be written later, as I think it has much greater scope for being able to deal with really really complex type extensions.

So that's my thoughts for the moment. I need to speak to Olaf about a few details of his checker, and then I'll get writing.



Blogger Neil Mitchell said...

For those of you who don't know what Neil typing is, see here.

1:38 PM  
Blogger Neil Mitchell said...

Another thing to mention about "Neil typing" - I suspect I could implement it in lighting time in C, thanks to Union Find, unfortunately doing this in Haskell seems like a mini-nightmare :)

2:20 PM  
Blogger Tom Davie said...

Not a mini adventure? *boom boom tish*


2:38 PM  
Anonymous Peter Firefly Lund said...

Can it provide suggested fixes for type errors? They don't have to be correct, they just have to be small changes to the program that will make it typecheck.

Put that in an IDE and let the user choose easily and rapidly between a few suggestions (with easy undo) and I think complains about type errors will be much fewer.

7:33 AM  

Post a Comment

<< Home