April 2006 - Haskell-Cafe

6.2.1 for glibc-2.4
by Paul A. Steckler 14 Apr '06

14 Apr '06

I need a Linux ghc 6.2.1 built with glibc-2.4. The existing 6.2.1 RPM, built with glibc-2.3, works mostly OK, but with some programs, the generated executables barf and die on startup. Any suggestions on how to create such a beast? I've tried using ghc 6.4.1, for which there's a Fedora 5 RPM, to build 6.2.1 from source, but all sorts of compile errors occur. On a Linux with glibc-2.3 installed, is there a way to have the ghc build use a different glibc? -- Paul -- Paul Steckler, PhD Tel: +1 503.626.6616 x156 Galois Connections, Inc. Fax: +1 503.350.0833 12725 SW Millikan Way, Beaverton, OR 97005 Email: steck(a)galois.com

1 0

AFP 2006: any news ?
by Alain Cremieux 14 Apr '06

14 Apr '06

Hi, Has anyone any news about an Advanced Functional Programming school, which was scheduled for 2006 ? Thanks, Alain

2 1

RuntimeLoader
by Tim Newsham 14 Apr '06

14 Apr '06

Hi, I'm about to start playing with HWS-WP (web server + plugins). It relies on RuntimeLoader: http://www.algorithm.com.au/wiki/hacking/haskell.ghc_runtime_loading I grabbed the example and built it (only one minor tweak to imports to get it to build) but it doesnt quite work: $ ./src/TextFilter ./plugins/Lower.o < README TextFilter: ./plugins/Lower.o: unknown symbol `__stginit_Char_' TextFilter: user error (resolveFunctions failed?False) There were also some warnings during building: Compiling RuntimeLoader ( ../runtime_loader/RuntimeLoader.hs, ./RuntimeLoader .o ) /tmp/ghc11951.hc: In function `s2Pj_ret': /tmp/ghc11951.hc:170: warning: implicit declaration of function `unloadObj' /tmp/ghc11951.hc: In function `s2JU_entry': [...] I assume this is because it is mucking with some ghc internals? Is anyone familiar with this package? Is there a more up-to-date version or alternative? Tim Newsham http://www.lava.net/~newsham/

3 2

Local Fundeps [was: Fundeps: I feel dumb]
by oleg＠pobox.com 13 Apr '06

13 Apr '06

Creighton Hogg posed the following problem. Given a rather straightforward matrix multiplication code > -- The elements and the size > data Vec a = Vec (Array Int a) Int deriving (Show,Eq) > type Matrix a = (Vec (Vec a)) > class MatrixProduct a b c | a b -> c where > (<*>) :: a -> b -> c > instance (Num a) => MatrixProduct a (Vec a) (Vec a) where > (<*>) num (Vec a s) = Vec (fmap (*num) a) s > vector n elms = Vec (array (0,n-1) $ zip [0..n-1] elms) n we'd like to get the following straightforward test to compile: > test = 10 <*> (vector 10 [0..9]) The trouble it doesn't: the function (<*>) has the type a->b->c so the type of the scalar doesn't have to be in any a priori relation with the type of the matrix (to permit efficient representations for particular sorts of matrices). Such a general type for (<*>) means that the test expression does not constrain "10" to be of the same numeric type as the type of matrix elements. So, the inferred type for test is test :: (Num a, Num b, MatrixProduct a (Vec b) c) => c The constraint must be resolved (top level, monomorphism restriction): but it can't because there is no instance MatrixProduct a (Vec b) c There is only more specialized instance, which doesn't match. The solution exists: change test so that the type of the scalar and the base type of the vector are the same: > test1 = (10::Int) <*> (vector 10 [0..9::Int]) > test2 = let n = 10 in n <*> (vector 10 [0..(9 `asTypeOf` n)]) or add the type annotations in other ways. But that is annoying. Creighton Hogg asked if there is another way? There is. Change the instances to > instance (Num a,Num b,TypeCast a b) => MatrixProduct a (Vec b) (Vec b) where > (<*>) num (Vec a s) = Vec (fmap (* (typeCast num)) a) s The difference is subtle but important: given such a general instance, trying to resolve "MatrixProduct a (Vec b) c" now succeeds. Instance selection is done only based on the types in the head; constraints are not taken into account. When the match succeeds, GHC commits to it and goes checking the constraints. One of the constraints, TypeCast a b, says that the type a must be the same as b. Because 'a' and 'b' were just type variables (could be instantiated), that constraint succeeds and we accomplished our task. Now the original test types and works. In short: given the instance "C a a" and the constraint "C a b", we see failure: "C a a" can't match "C a b". The type variables of the latter aren't instantiated: this is matching, not the full unification. The re-written instance "TypeCast a b => C a b", effectively describes the same set of types. Now, however, "C a b" matches that instance -- and, the TypeCast constraint forces "a" and "b" to be the same. These _local_, per-instance functional dependencies notably improve the power of instance selection: from mere matching to some type improvement (towards the full unification). The net result is fewer type annotations required from the user. One might consider that useful. The full code: {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module Foo where import Array data Vec a = Vec (Array Int a) Int deriving (Show,Eq) type Matrix a = (Vec (Vec a)) class MatrixProduct a b c | a b -> c where (<*>) :: a -> b -> c {- previously: instance (Num a) => MatrixProduct a (Vec a) (Vec a) where (<*>) num (Vec a s) = Vec (fmap (*num) a) s -} instance (Num a,Num b,TypeCast a b) => MatrixProduct a (Vec b) (Vec b) where (<*>) num (Vec a s) = Vec (fmap (* (typeCast num)) a) s vector n elms = Vec (array (0,n-1) $ zip [0..n-1] elms) n test = 10 <*> (vector 10 [0..9]) test1 = (10::Int) <*> (vector 10 [0..9::Int]) test2 = let n = 10 in n <*> (vector 10 [0..(9 `asTypeOf` n)]) class TypeCast a b | a -> b, b->a where typeCast :: a -> b class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' instance TypeCast'' () a a where typeCast'' _ x = x

1 0

#if and #endif
by ihope 13 Apr '06

13 Apr '06

I grabbed the source code to Haddock, but GHC doesn't like the #if's and the #endif's. What can I do with these?

1 0

Re: [Haskell-cafe] Re: coherence when overlapping?
by Martin Sulzmann 13 Apr '06

13 Apr '06

I believe that GHC's overlapping instance extensions effectively uses inequalities. Why do you think that 'inequalities' model 'best-fit'? instance C Int -- (1) instance C a -- (2) under a 'best-fit' instance reduction strategy we would resolve C a by using (2). 'best-fit' should be very easy to implement. Simply order instances (resulting CHRs) in an appropriate 'best-fit' order. In case of instance C Int instance a =!=Int | C a (2') we can't reduce C a (because we can't satisfy a=!=Int) Notice that (2') translates to rule C a | a =!=Int <==> True I think it's better to write a =!=Int not as part of the instance context but write it as a guard constraint. I don't think there's any issue for an implementation (either using 'best-fit' or explicit inequalities). The hard part is to establish inference properties such as completeness etc. Martin Tom Schrijvers writes: > On Thu, 13 Apr 2006, Martin Sulzmann wrote: > > > > > Coherence (roughly) means that the program's semantics is independent > > of the program's typing. > > > > In case of your example below, I could type the program > > either use the first or the second instance (assuming > > g has type Int->Int). That's clearly bound. > > > > Guard constraints enforce that instances are non-overlapping. > > > > instance C Int > > instance C a | a =!= Int > > > > The second instance can only fire if a is different from Int. > > > > Non-overlapping instances are necessary but not sufficient to > > obtain coherence. We also need that types/programs are unambiguous. > > Claus Reinke was discussing this with me some time ago. He called it the > best fit principle, which would in a way, as you illustrate above, allow > inequality constraints to the instance head. You could even write it like: > > instance (a /= Int) => C a > > as you would do with the superclass constraints... I wonder whether > explicit inequality constraints would be useful on their own in all the > places where type class and equality constraints are used (class and > instance declarations, GADTs, ...). Or maybe it opens a whole new can of > worms :) > > Tom > > -- > Tom Schrijvers > > Department of Computer Science > K.U. Leuven > Celestijnenlaan 200A > B-3001 Heverlee > Belgium > > tel: +32 16 327544 > e-mail: tom.schrijvers(a)cs.kuleuven.be

4 3

Re: Fundeps: I feel dumb
by oleg＠pobox.com 13 Apr '06

13 Apr '06

Creighton Hogg wrote: > No instance for (MatrixProduct a (Vec b) c) > arising from use of `<*>' at <interactive>:1:3-5 > Probable fix: add an instance declaration for (MatrixProduct a > (Vec b) c) > In the definition of `it': it = 10 <*> (vector 10 ([0 .. 9])) Let us look at the instance class MatrixProduct a b c | a b -> c where (<*>) :: a -> b -> c instance (Num a) => MatrixProduct a (Vec a) (Vec a) where it defines what happens when multiplying a vector of some numeric type 'a' by a value _of the same_ type. Let us now look at the error message: > (MatrixProduct a (Vec b) c) That is, when trying to compile your expression 10 <*> (vector 10 ([0 .. 9])) the typechecker went looking for (MatrixProduct a (Vec b) c) where the value and the vector have different numeric types. There is no instance for such a general case, hence the error. It is important to remember that the typechecker first infers the most general type for an expression, and then tries to resolve the constraints. In your expression, 10 <*> (vector 10 ([0 .. 9])) we see constants 10, 10, 0, 9. Each constant has the type Num a => a. Within the expression 0 .. 9, both 0 and 9 must be of the same type (because [n .. m] is an abbreviation for enumFromThen n m, and according to the type of the latter enumFromThen :: a -> a -> [a] both arguments must be of the same type). But there is nothing that says that the first occurrence of 10 must be of the same numeric type as the occurrence of 9. So, the most general type assignment will be (Num a => a) for 10, and (Num b => b) for 9. Solution: either choose a specific (non-polymorphic type) > test1 = (10::Int) <*> (vector 10 [0..9::Int]) Or tell the typechecker that those constants must be of the same type: > test2 = let n = 10 in n <*> (vector 10 [0..(9 `asTypeOf` n)])

2 1

Counting bits: Sanity Check
by David F. Place 13 Apr '06

13 Apr '06

Hi All, Since it seems that real applications need more than just union, intersection, difference and complement to be fast to make EnumSet useful, I've been looking into the less naive approaches to the other things. In particular, size seems to find itself in the inner loop. I've made a comparison of various approaches to bit counting. It seems I was too hasty to declare Bulat's suggestion of table lookup (table,table32) the winner. It seems Robert's suggestion of Kernighan's (kern) method is faster. I also implemented the method described in pages 187-188 of Software Optimization Guide for AMD Athlon™ 64 and Opteron™ Processors. (ones32) It's slower on my powerbook, but may be the winner on 64bit processors. Here are the results: [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 ones32 21 1.788u 0.136s 0:03.30 57.8% 0+0k 0+0io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table 21 2.404u 0.164s 0:04.96 51.6% 0+0k 0+1io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table32 21 2.067u 0.140s 0:04.27 51.5% 0+0k 0+0io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 kern 21 1.729u 0.137s 0:03.25 56.9% 0+0k 0+1io 0pf+0w If you'd like to give it a whirl on your fancy modern computers, here's the code: ghc -O3 -optc-O3 -o bits BitTwiddle.hs Of course, if I've done something lame-brained and skewed the results, please let me know. Cheers, David -------------------------------- David F. Place mailto:d@vidplace.com

4 6

The Marriage of Heaven and Hell: Type Classes and Bit-Twiddling
by David F. Place 13 Apr '06

13 Apr '06

Hi: Looking around further for a charming way to count bits, I found a method that is completely inscrutable might be very fast. http://graphics.stanford.edu/~seander/bithacks.html Counting bits set in 12, 24, or 32-bit words using 64-bit instructions I thought it would be neat to have size function constrained to members of Bounded that would automatically choose which method depending on the extent of the domain of the set. So, a small set could be computed by the very fast method and the compiler would be able to do the dispatch as part of constant folding. This is what I came up with. It works, but it seems kind of forced. I wonder if there is a better way. sizeB :: (Bounded a,Enum a) => a -> Set a -> Int sizeB e = case fromEnum $ maxBound `asTypeOf` e of x | x <= 12 -> \(Set w) -> fromIntegral $ c12 $ fromIntegral w x | x <= 24 -> \(Set w) -> fromIntegral $ c24 $ fromIntegral w x | x <= 32 -> \(Set w) -> fromIntegral $ c32 $ fromIntegral w _ -> \(Set w) -> bitcount 0 w c12 :: Word64 -> Word64 c12 v = (v * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f c24' :: Word64 -> Word64 c24' v = ((v .&. 0xfff) * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f c24 :: Word64 -> Word64 c24 v = (c24' v) + ((((v .&. 0xfff000) `shiftR` 12) * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f) c32 :: Word64 -> Word64 c32 v = (c24 v) + (((v `shiftR` 24) * 0x1001001001001 .&. 0x84210842108421) `rem` 0x1f) For example: data Test1 = Foo | Bar | Baaz | Quux deriving (Enum, Bounded) sizeTest1 :: (Set Test1) -> Int sizeTest1 = sizeB Foo Cheers, David -------------------------------- David F. Place mailto:d@vidplace.com

1 1

Re: coherence when overlapping?
by oleg＠pobox.com 13 Apr '06

13 Apr '06

It seems that the subject is a bit more complex, and one can force GHC to choose the less specific instance (if one confuses GHC well enough): see the example below. First of all, the inequality constraint is already achievable in Haskell now: "TypeEq t1 t2 False" is such a constraint. One can write polymorphic functions that distinguish if the argument a list (any list of something) or not, etc. One can write stronger invariants like records where labels are guaranteed to be unique. There are two problems: first there are several notions of type inequality, all of which are useful in different circumstances. http://www.haskell.org/pipermail/haskell-prime/2006-March/000936.html Second, how inequality interacts with functional dependencies -- and in general, with the type improvement. And here, many interesting things emerge. For example, the following code > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > {-# OPTIONS -fallow-overlapping-instances #-} > > module Foo1 where > > class C a b | a -> b where > f :: a -> b > > instance C Int Bool where > f x = True > > instance TypeCast Int b => C a b where > f x = typeCast (100::Int) > > class TypeCast a b | a -> b, b->a where typeCast :: a -> b > class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b > class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b > instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x > instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' > instance TypeCast'' () a a where typeCast'' _ x = x > > class D a b | a -> b where > g :: a -> b > > instance D Bool Bool where > g x = not x > > instance TypeCast a b => D a b where > g x = typeCast x > > test1 = f (42::Int) -- ==> True > test2 = f 'a' -- ==> 100 > > test3 = g (1::Int) -- ==> 1 > test4 = g True -- ==> False > > bar x = g (f x) `asTypeOf` x We see that test1 through test4 behave as expected. We can even define the function 'bar'. It's inferred type is *Foo1> :t bar bar :: (C a b, D b a) => a -> a The question becomes: is this a function? Can it be applied to anything at all? If we apply it to Int (thus instantiating the type a to Int), the type b is instantiated to Bool, and so (following the functional dependency for class D), the type a should be Bool (and it is already an Int). OTH, if we apply bar to anything but Int, then the type b should be Int, and so should the type a. Liar's paradox. And indeed, bar cannot be applied to anything because the constraints are contradictory. What is more interesting is the slight variation of that example: > class C a b | a -> b where > f :: a -> b > > instance C Int Int where > f x = 10+x > > instance TypeCast a b => C a b where > f x = typeCast x > > class D a b | a -> b where > g :: a -> b > > instance D Int Bool where > g x = True > > instance TypeCast Int b => D a b where > g x = typeCast (10::Int) > > test1 = f (42::Int) > test2 = f 'a' > > test3 = g (1::Int) > test4 = g True > > bar x = g (f x) `asTypeOf` x > > test5 = bar (1::Int) *Foo> :t bar bar :: (C a b, D b a) => a -> a If bar is applied to an Int, then the type b should be an Int, so the first instance of D ought to have been chosen, which gives the contradiction a = Bool. And yet it works (GHC 6.4.1). Test5 is accepted and even works *Foo> test5 10

2 1