RE: #ifdef considered harmful (was: DData)
On 19 April 2004 15:06, Jan-Willem Maessen - Sun Labs East wrote:
The real problem, of course, isn't the data structures at all---GHC does an excellent job with these (though the "UNPACK" pragma is a revelation). The actual problem is function arguments. GHC can't do worker-wrapper unless a function is strict. Often we end up with something like this:
I'm not sure I'd characterise that as "the real problem" - in a lot of the cases I've come across, the UNPACK pragma has been exactly what I needed. In a few critical functions where I found that arguments weren't strict enough, I've had to add seqs to help the compiler.
data Tree a = Branch !Int a (Tree a) (Tree a)
lookfor :: Int -> Tree a -> Maybe a lookfor Leaf key = Nothing lookfor (Branch k v l r) key | key==k = Just v | key < k = lookfor l key | otherwise = lookfor r key
Here we don't use "key" in the first clause, so GHC isn't allowed to unbox. Most of the uses of Int# that I've seen in library code have been workarounds to this problem. In this case, being able to write
lookfor :: FastInt -> Tree a -> Maybe a
might give us some hope of getting the compiler to generate the unboxed code we might want, yet still afford us the opportunity to use boxed types if that's not possible.
We could do this today without changing the language or the compilers. The library would have to be carefully coded...
I'm not clear on exactly what the FastInt type means. I think I asked Alastair the same question recently - is FastInt an unlifted type? Can I store it in a polymorphic data structure or pass it to a polymorphic function? If FastInt is Int# in GHC, and we want it to be portable, then we have to introduce unlifted types & kinds in Hugs and nhc98 too. Declaring instances of classes for unlifted types isn't possible, so you can't have instane Num Int#, for example. I think you need polymorphic kinds for that. Cheers, Simon
I'm not clear on exactly what the FastInt type means. I think I asked Alastair the same question recently - is FastInt an unlifted type?
Yes, it should be unlifted. Being unboxed as well would be nice but I'd sacrifice that for any other benefits like polymorphism and overloading.
Can I store it in a polymorphic data structure or pass it to a polymorphic function?
That would be highly desirable. I think it can be done using some kind of 'separate but equal' type system where we have two kinds of type variable: '*' for lazy types and '#' for strict types. So, for example, there would be two versions of 'id': id_* :: forall a::*. a -> a id_# :: forall a::#. a -> a My main question is how is a typechecker to infer kinds? Does it apply a default rule of '*' unless otherwise noted? What syntax does the programmer use to override that default? This would be a bit tedious because not only would be need to write strict and lazy versions of '+' (say) but we'd also have to define two separate Num-like classes: one for types of kind * and one for types of kind #. It would be really nice to have a single version of 'id' and a single definition of 'Num' but that would be hard to achieve because a piece of code like this: foo x = [bar (id (x + 1))] has a very different evaluation order depending on whether x is strict or lazy. I think we can implement it by passing round a dictionary that contains either 'seq' (for #) or '\ x y -> y' (for *) but that's not very appealing.
If FastInt is Int# in GHC, and we want it to be portable, then we have to introduce unlifted types & kinds in Hugs and nhc98 too.
Yes, I was proposing that Hugs and NHC be extended with unlifted types of some form.
Declaring instances of classes for unlifted types isn't possible, so you can't have instane Num Int#, for example. I think you need polymorphic kinds for that.
Yes, that was the conclusion I was slowly coming to above. -- Alastair Reid
participants (2)
-
Alastair Reid -
Simon Marlow