- Glasgow-haskell-users

Quoting a quasi-quote
by Yitzchak Gale 27 Jul '11

27 Jul '11

It was pointed out by Ben Millwood on the Cafe that there is an undocumented way to escape the closing oxford bracket of a quasi-quote using a backslash: [s|This quasi-quote contains this, \|], an escaped closing oxford bracket.|] The backslash itself cannot be escaped in this way: [s|Also contains an escaped bracket \\|] |] Thus there is a fairly strong limitation on the contents of a quasi-quote: it can never end in a backslash. This behavior is not mentioned in the GHC docs. Is it a mistake, or is it meant to be a supported feature? This behavior is a bit surprising to me. Since the whole point of a quasi-quoter is to allow the user to define syntax, you would think that the syntax for the quasi-quote itself would be as quiet as possible and stay out of the way. People who need to be able to escape the closing bracket can easily define their own syntax to do so. In any case, if this is indeed a feature, it certainly should be documented. Thanks, Yitz

4 3

Understanding behavior of BlockedIndefinitelyOnMVar exception
by Brandon Simmons 26 Jul '11

26 Jul '11

I'm trying to really understand how the BlockedIndefinitelyOnMVar exception works in concurrent code as I would like to rely on it as a useful runtime signal in a concurrency library I'm working on. Here is some code illustrating a function restoring an abandoned lock in a single-threaded program and works as I would expect: -------- START CODE -------- module Main where import Control.Concurrent import Control.Exception -- This raises the exception only once and the lock is successfully restored: main1 = do lock <- newMVar () lockPrint "good1" lock badLockPrint "bad" lock -- exception is raised and lock is restored here: lockPrint "good2" lock -- no exception raised: lockPrint "good3" lock readMVar lock lockPrint :: String -> MVar () -> IO () lockPrint name v = do e <- try $ takeMVar v :: IO (Either BlockedIndefinitelyOnMVar ()) -- either print exception, or print name: either print (const $ putStrLn name) e `finally` putMVar v () -- perhaps simulates an operation that died before it could return a lock: badLockPrint :: String -> MVar () -> IO () badLockPrint s v = do takeMVar v putStrLn s -- Forgot to return the lock here!: -------- END CODE -------- Now here is a variation of 'main' that forks the operations: -------- START CODE -------- main0 = do lock <- newMVar () forkIO $ lockPrint "good1" lock threadDelay 1000000 forkIO $ badLockPrint "bad" lock -- these both raise blocked indefinitely exception threadDelay 1000000 forkIO $ lockPrint "good2" lock threadDelay 1000000 forkIO $ lockPrint "good3" lock threadDelay 1000000 -------- END CODE -------- What I think I've learned here is that the BlockedIndefinitelyOnMVar exception is raised in all the blocked threads "at once" as it were. That despite the fact that the handler code in 'lockPrint' restores the lock for successive threads. This would also seem to imply that putMVar's in an exception handler don't stop the runtime from raising the BlockedIndefinitelyOnMVar. But that doesn't really seem right. Can anyone comment on the two conclusions above? FWIW, this was an interesting related thread: http://comments.gmane.org/gmane.comp.lang.haskell.glasgow.user/18667 Thanks, Brandon Simmons http://coder.bsimmons.name

3 6

GHC 7.0.4 on Lion
by Luca Ciciriello 26 Jul '11

26 Jul '11

Hi All. I've installed on my Mac the new MacOS X 10.7 (Lion) with Xcode 4.1 Using ghc 7.0.4 (64-bit) on that system a get the following warnings in the linking phase: Linking hslint ... ld: warning: could not create compact unwind for _ffi_call_unix64: does not use RBP or RSP based frame ld: warning: PIE disabled. Absolute addressing (perhaps -mdynamic-no-pic) not allowed in code signed PIE, but used in ___gmpn_modexact_1c_odd from /Library/Frameworks/GHC.framework/Versions/7.0.4-x86_64/usr/lib/ghc-7.0.4/integer-gmp-0.2.0.3/libHSinteger-gmp-0.2.0.3.a(mode1o.o). To fix this warning, don't compile with -mdynamic-no-pic or link with -Wl,-no_pie Is this something to worrying about? Thanks in advance for any answer. Luca

3 3

Re: Superclass Cycle via Associated Type
by Edward Kmett 21 Jul '11

21 Jul '11

*Simon Peyton-Jones* simonpj at microsoft.com <glasgow-haskell-users%40haskell.org?Subject=Re%3A%20Superclass%20Cycle%20via%20Associated%20Type&In-Reply-To=%3C59543203684B2244980D7E4057D5FBC125661A72%40DB3EX14MBXC308.europe.corp.microsoft.com%3E> ------------------------------ You point is that the (C Int) dictionary has (C String) as a superclass, and > (C String) has (C Int) as a superclass. So the two instances are mutually > recursive, but that's ok. > That is not unreasonable. But it is dangerous. Consider > class C [a] => C a > Then any dictionary for (C a) would contain a dictionary for (C [a]) which > would contain a dictionary for C [[a]], and so on. Haskell is lazy so we > might even be able to build this infinite dictionary, but it *is* infinite. > It's a bit like the "recursive instance" stuff introduced in "Scrap your > boilerplate with class". > After 5 mins thought I can't see a reason why this could not be made to > work. But it'd take work to do. If you have a compelling application maybe > you can open a feature request ticket, describing it, and referring this > thread? > Has anyone else come across this? > Yes. This is actually an active problem for me in my 'algebra' package. We can define additive, additive abelian and multiplicative semigroups: class Additive m where (+) :: m -> m -> m class Additive m => Abelian m class Multiplicative m where (*) :: m -> m -> m then we can define semirings (in the semirings are semigroups with distributive laws sense): class (Additive m, Abelian m, Multiplicative m) => Semiring m then to define monoids, we enforce the fact that every additive monoid is a module over the naturals. class (Semiring r, Additive m) => LeftModule r m where (.*) :: r -> m -> m class LeftModule Natural m => Monoidal m where This makes it an obligation of anyone that provides a Monoidal instance to ensure that they also supply the LeftModule, side-stepping what would be a hugely overlapping instance, and ensuring we can rely on it. But we weren't able to exploit the fact that any Additive semigroup forms a module over N+, due to the cycle. Moreover, we also weren't able to encode that every semiring is a module over itself. If we could have superclass cycles, we could restate this all as class LeftModule Whole m => Additive m where (+) :: m -> m -> m class Additive m => Abelian m class (Semiring r, Additive m) => LeftModule r m where (.*) :: r -> m -> m class Multiplicative m where (*) :: m -> m -> m class LeftModule Natural m => Monoidal m where zero :: m class (Abelian m, Multiplicative m, LeftModule m m) => Semiring m class (LeftModule Integer m, Monoidal m) => Group m where recip :: m -> m class Multiplicative m => Unital m where one :: m class (Monoidal r, Unital r, Semiring r) => Rig r where fromNatural :: Natural -> r fromNatural n = n .* one class (Rig r, Group r) => Ring r where fromInteger :: Integer -> r fromInteger n = n .* one ... There are a number of typeclass cycles in there, but I can safely instantiate the whole mess without any overlapping instances and I already have to ball all of these classes up in the same 'Internals' module to avoid orphans instances anyways. Using the usual dodge of a newtype to provide Self module over any given semiring is particularly unsatisfying because the Natural and Integer multiplication become horrific, and I wind up having to multiply the code below this point in the hierarchy to deal with the 'self algebra' cases. =/ I've also run into the problem about once or twice a year when encoding other concepts that are usually more categorical in nature. I would love to be able to do this. -Edward Kmett

1 0

HEAD doesn't not build on OS X
by Johan Tibell 20 Jul '11

20 Jul '11

While trying to build head (from a maintainer-clean tree) I get the following error: echo "compiler_stage1_depfile_haskell_EXISTS = YES" >> compiler/stage1/build/.depend-v.haskell.tmp for dir in compiler/stage1/build/./ compiler/stage1/build/Llvm/ compiler/stage1/build/LlvmCodeGen/ compiler/stage1/build/PPC/ compiler/stage1/build/RegAlloc/ compiler/stage1/build/RegAlloc/Graph/ compiler/stage1/build/RegAlloc/Linear/ compiler/stage1/build/RegAlloc/Linear/PPC/ compiler/stage1/build/RegAlloc/Linear/SPARC/ compiler/stage1/build/RegAlloc/Linear/X86/ compiler/stage1/build/SPARC/ compiler/stage1/build/SPARC/CodeGen/ compiler/stage1/build/Vectorise/ compiler/stage1/build/Vectorise/Builtins/ compiler/stage1/build/Vectorise/Monad/ compiler/stage1/build/Vectorise/Type/ compiler/stage1/build/Vectorise/Utils/ compiler/stage1/build/X86/; do if test ! -d $dir; then mkdir -p $dir; fi done grep -v ' : [a-zA-Z]:/' compiler/stage1/build/.depend-v.haskell.tmp > compiler/stage1/build/.depend-v.haskell "/usr/sbin/dtrace" -Iincludes -Irts -Ilibffi/build/include -C -x cpppath=/usr/bin/gcc -h -o rts/dist/build/RtsProbes.h -s rts/RtsProbes.d . includes/HsFFI.h .. includes/ghcconfig.h ... includes/ghcautoconf.h ... includes/ghcplatform.h .. includes/stg/Types.h .. /usr/lib/gcc/i686-apple-darwin10/4.2.1/include/stdint.h .. /usr/lib/gcc/i686-apple-darwin10/4.2.1/include/float.h . includes/rts/EventLogFormat.h dtrace: failed to compile script rts/RtsProbes.d: line 71: parameter is already declared in probe input prototype: StgWord, parameter #6 make[1]: *** [rts/dist/build/RtsProbes.h] Error 1 make: *** [all] Error 2

2 4

memory statistics via an API ?
by Tim Docker 20 Jul '11

20 Jul '11

The "+RTS -s" runtime arguments give some useful details the memory usage of a program on exit. eg: 102,536 bytes allocated in the heap 2,620 bytes copied during GC 36,980 bytes maximum residency (1 sample(s)) 28,556 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) Is there any means of obtaining this information at runtime, via some API? It would be useful for monitoring a long running server process. Tim

2 1

Statically linking a small piece of C into every GHC generated binary
by Johan Tibell 19 Jul '11

19 Jul '11

Hi, I'm trying to add support for the POPCNT instruction, which exists on some modern CPUs (e.g. Nehalem). The idea is to add a popCnt# primop which would generate a POPCNT instruction when compiling with -msse4.2. If the user didn't specified -msse4.2, the primop should fall back to some other implementation of population count. A good fallback, in terms of both speed and memory usage, is this lookup-table based function: static char popcount_table_8[256] = { /*0*/ 0, /*1*/ 1, /*2*/ 1, /*3*/ 2, /*4*/ 1, /*5*/ 2, /*6*/ 2, /*7*/ 3, /*8*/ 1, /*9*/ 2, /*10*/ 2, /*11*/ 3, ... }; /* Table-driven popcount, with 8-bit tables */ /* 6 ops plus 4 casts and 4 lookups, 0 long immediates, 4 stages */ inline uint32_t popcount(uint32_t x) { return popcount_table_8[(uint8_t)x] + popcount_table_8[(uint8_t)(x >> 8)] + popcount_table_8[(uint8_t)(x >> 16)] + popcount_table_8[(uint8_t)(x >> 24)]; } (GCC and LLVM use the same fallback method.) It's important that the fallback is as good as it gets so that the user of the primop doesn't have to implement their own fallback (which is very complicated as the user would have to detect whether -msse4.2 is used or not!). This precludes non-table based solutions (as they're slower). I've implemented the primop but run into some difficulty: to use the above fallback I need the code to be statically linked into every binary. I'm not quite sure how to achieve that. GCC manages by having the above function definition in libc, which is always statically linked. I think LLVM uses a small statically linked compiler run-time library for the same purpose. How would one go about having a small C library linked into every Haskell binary? If we go ahead and implement more of these modern instructions we're likely to need more fallbacks (so this isn't needed by just POPCNT). Cheers, Johan

2 2

Package abi hash and interface file versions
by Joachim Breitner 18 Jul '11

18 Jul '11

Hi, in Debian, we use the ghc-pkg ABI hashes to find out what packages we need to rebuild when. So far, the system has worked great. But now something unfortunate happened: Yesterday, I upgraded ghc from 7.0.3 to 7.0.4. The ABI hash of base and other libraries changed only on amd64 and kfreebsd-amd64, while they stays unmodified on the other architectures. That by itself is interesting, but nothing to worry about, as I assumed that the hashes ensure that packages are rebuild where required. But now I see this build log: https://buildd.debian.org/status/fetch.php?pkg=haskell-mtlparse&ver=0.1.2-1… with the relevant line: Text/ParserCombinators/MTLParse/MTLParseCore.hs:69:1: Bad interface file: /usr/lib/haskell-packages/ghc/lib/mtl-2.0.1.0/ghc-7.0.3/Control/Monad/Trans.hi mismatched interface file versions (wanted "7004", got "7003") Obviously, the ghc version is encoded into the .hi file and checked before using it, including the minor patch level. But it seems that this bit of information is not included in the calculation of the interface hash! So although the ABI hash did not change between 7.0.3 and 7.0.4, the package is broken. I see two solutions for this problem: a) (preferred) The ghc version number is not encoded in the .hi file any more. Instead, a version counter is used that is manually incremented if there has been an incompatible change to the interface – after all, not every minor release of ghc changes this format. b) The interface file version should be included in the hash generation, so that a package built against the base package of 7.0.3 will clearly state that it does not work with the base package of 7.0.4 and needs to be rebuild. (Actually, b) should be the case even if a) is done). Thanks, Joachim -- Joachim "nomeata" Breitner Debian Developer nomeata(a)debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nomeata(a)joachim-breitner.de | http://people.debian.org/~nomeata

2 4

Deriving Typeable -- possible improvement
by Simon Peyton-Jones 14 Jul '11

14 Jul '11

| iterIO uses mkTyCon for the simple reason that ((Typeable t, Typeable | m) => Iter t m) is Typeable1 and there is no automatic way of deriving | Typeable1. This email is triggered by a thread on Haskell Cafe about changes to the Typeable class http://www.mail-archive.com/haskell-cafe@haskell.org/msg91830.html It proposes a modification to the way Typeable is derived; and concludes with a question. Simon David Mazieres and others comment that you can't derive Typeable for types like this: data T f = MkT (f Int) So he defines his own instance like this [C] instance Typable1 f => Typeable (T f) where typeOf = ... So why can't GHC do this? Well, here's what GHC does. Given a bog standard data type like Maybe data Maybe a = Nothing | Just a deriving( Typeable ) GHC generates this instance [A] instance Typeable1 Maybe where typeOf = ... Remember that Typeable1 takes a type *constructor*, of kind (*->*), as its argument. Now if we need (Typeable (Maybe Int)), GHC first uses an instance from the Typeable library: [B] instance (Typeable1 f, Typeable a) => Typeable (f a) where typeOf = ... And now it uses the (Typeable1 Maybe) instance [A]. So it's kind of cool... the applications are decomposed by [B], leaving the tycon to [A]. But this doesn't work for T above. We can't make (Typeable1 T) because T has kind ((*->*)->*), not (*->*) as Typeable1 requires. Hence David defining his own instance. GHC could do this too. Indeed it could do so for Maybe too, thus: instance Typeable a => Typeable (Maybe a) where typeOf = ... But then, alas, we could not get (Typeable (T Maybe)), because [C] needs Maybe to be in Typeable1. ========== PROPOSAL ============== So here is a compromise, which would at least do better than the current story: When deriving Typeable for a data type S of kind S :: k1 -> .. -> kn -> * -> ... -> * (where kn is not *, and there are M trailing * arguments), generate the instance instance (Typeable_x1 a1, ..., Typeable_xn an) => TypeableM (S a1 .. an) That is, knock off all the trailing * args, and then generate an instance for the remaining stub. ===================== EXAMPLE ============ Example from iterIO: newtype Iter (t :: *) (m :: *->*) (a :: *) = Iter { runIter :: Chunk t -> IterR t m a } deriving( Typeable ) This should generate instance (Typeable t, Typeable1 m) => Typeable1 (Iter t m) where we knock off the trailing (a :: *) argument. ================== QUESTION ================= This approach is not beautiful. It does not solve the underlying problem, which is a lack of kind polymorphism, but that is a battle for another day. Until that day, this alternative way of deriving Typeable would automate significantly more cases, I think. Of course, it also makes it more complicated to explain when "deriving Typeable" will succeed. Any opinions? Does anyone care? Simon

1 0

Fixing Performance Leaks at the Type Level
by Gershom Bazerman 12 Jul '11

12 Jul '11

This post is in literate Haskell. It describes how certain performance leaks are introduced in type level programming. These leaks do not affect program runtimes, but can cause compile times to grow drastically. They exist both with Functional Dependencies and Type Families, but are currently worse with the former, and have grown worse with the new constraint solver in GHC 7. It is intended both as a guide to those encountering these issues, and as a motivation for the GHC development team to address such issues as the constraint solver is developed and improved. > {-# OPTIONS_GHC -fcontext-stack=1000 #-} > {-# LANGUAGE FlexibleContexts, FlexibleInstances, FunctionalDependencies, MultiParamTypeClasses, OverlappingInstances, TypeSynonymInstances, TypeOperators, UndecidableInstances, TypeFamilies #-} > module TypePerformance where Our running example, for simplicity's sake, is a type-level map of a single function. For reference, here is the code for a simple value-level map of a single function. > vfoo = id > mapfoo (x : xs) = vfoo x : mapfoo xs > mapfoo [] = [] Because Haskell is a lazy language, this runs in O(n) time and constant stack. We now lift map to the type level, to operate over HLists. First, the basic HList types > infixr 3 :* > data x :* xs = x :* xs deriving Show > data HNil = HNil deriving Show Next, a large boring HList > -- Adds ten cells > addData x = i :* i :* d :* d :* s :* > i :* i :* d :* d :* s :* > x > where i = 1 :: Int > d = 1 :: Double > s = "" > > -- Has 70 cells. > sampleData = addData $ addData $ addData $ addData $ addData $ > addData $ addData $ > HNil Next, a simple polymorphic function to map > class Foo x y | x -> y > where foo :: x -> y > foo = undefined > instance Foo Int Double > instance Foo Double Int > instance Foo String String Now, our map > class HMapFoo1 as bs | as -> bs where > hMapFoo1 :: as -> bs > > instance (Foo a b, HMapFoo1 as bs) => HMapFoo1 (a :* as) (b :* bs) where > hMapFoo1 (x :* xs) = foo x :* hMapFoo1 xs > > instance HMapFoo1 HNil HNil where > hMapFoo1 _ = HNil If we enable the following line, compilation time is ~ 9 seconds. > testHMapFoo1 = hMapFoo1 sampleData Furthermore, playing with the size of sampleData, we see that the time spent in compilation is superlinear -- each additional cell costs a greater amount of time. This is because while Haskell is lazy at the value level, it is strict at the type level. Therefore, just as in a strict language, HMapFoo1's cost grows O(n^2) because even as we induct over the as, we build up a stack of bs. Just as in a strict language, the solution is to make hMapFoo tail recursive through introducing an accumulator. This also reverses the hlist, but never mind that. > class HMapFoo2 acc as bs | acc as -> bs where > hMapFoo2 :: acc -> as -> bs > > instance (Foo a b, HMapFoo2 (b :* bs) as res) => HMapFoo2 bs (a :* as) res where > hMapFoo2 acc (x :* xs) = hMapFoo2 (foo x :* acc) xs > > instance HMapFoo2 acc HNil acc where > hMapFoo2 acc _ = acc If we enable the following line, compilation time is a much more satisfying ~0.5s. > testHMapFoo2 = hMapFoo2 HNil sampleData But wait, there's trouble on the horizon! Consider the following version: > class HMapFoo3 acc as bs | acc as -> bs where > hMapFoo3 :: acc -> as -> bs > > instance (HMapFoo3 (b :* bs) as res, Foo a b) => HMapFoo3 bs (a :* as) res where > hMapFoo3 acc (x :* xs) = hMapFoo3 (foo x :* acc) xs > > instance HMapFoo3 acc HNil acc where > hMapFoo3 acc _ = acc The only difference between hMapFoo2 and hMapFoo3 is that the order of constraints on the inductive case has been reversed, with the recursive constraint first and the immediately checkable constraint second. Now, if we enable the following line, compilation time rockets to ~6s! > testHMapFoo3 = hMapFoo3 HNil sampleData Slowdowns such as those described here are not a purely hypothetical issue, but have caused real problems in production code. The example given above is fairly simple. The constraints used are minimal and easily checked. In real programs, the constraints are more difficult, increasing constant factors significantly. These constant factors, combined with unexpected algorithmic slowdowns due to the type inference engine, can lead (and have lead) to compilation times of HList-style code becoming deeply unwieldy-to-unusable, and can lead (and have lead) to this occuring only well after this code has been introduced and used on smaller cases without trouble. The constraint solver should certainly be smart enough to reduce the compile times of HMapFoo3 to those of HMapFoo2. In fact, with type families, the there is no difference (see below). Could the compiler be smart enough to do the same for HMapFoo1? I'm not sure. Certainly, it could at least knock down its own constant factors a bit, even if it can't improve the big-O performance there. ---- Appendix: Examples with Type Families As the below code demonstrates, the same issues demonstrated with Functional Dependencies also appear with Type Families, although less horribly, as their code-path seems more optimized in the current constraint solver: > class TFoo x where > type TFooFun x > tfoo :: x -> TFooFun x > tfoo = undefined > > instance TFoo Int where > type TFooFun Int = Double > instance TFoo Double where > type TFooFun Double = Int > instance TFoo String where > type TFooFun String = String > > class THMapFoo1 as where > type THMapFoo1Res as > thMapFoo1 :: as -> THMapFoo1Res as > > instance (TFoo a, THMapFoo1 as) => THMapFoo1 (a :* as) where > type THMapFoo1Res (a :* as) = TFooFun a :* THMapFoo1Res as > thMapFoo1 (x :* xs) = tfoo x :* thMapFoo1 xs > > instance THMapFoo1 HNil where > type THMapFoo1Res HNil = HNil > thMapFoo1 _ = HNil The following, when enabled, takes ~3.5s. This demonstrates that slowdown occurs with type families as well. > testTHMapFoo1 = thMapFoo1 sampleData > class THMapFoo2 acc as where > type THMapFoo2Res acc as > thMapFoo2 :: acc -> as -> THMapFoo2Res acc as > > instance (TFoo a, THMapFoo2 (TFooFun a :* acc) as) => THMapFoo2 acc (a :* as) where > type THMapFoo2Res acc (a :* as) = THMapFoo2Res (TFooFun a :* acc) as > thMapFoo2 acc (x :* xs) = thMapFoo2 (tfoo x :* acc) xs > > instance THMapFoo2 acc HNil where > type THMapFoo2Res acc HNil = acc > thMapFoo2 acc _ = acc The following, when enabled, takes ~0.6s. This demonstrates that the tail recursive transform fixes the slowdown with type families just as with fundeps. > testTHMapFoo2 = thMapFoo2 HNil sampleData > class THMapFoo3 acc as where > type THMapFoo3Res acc as > thMapFoo3 :: acc -> as -> THMapFoo3Res acc as > > instance (THMapFoo3 (TFooFun a :* acc) as, TFoo a) => THMapFoo3 acc (a :* as) where > type THMapFoo3Res acc (a :* as) = THMapFoo3Res (TFooFun a :* acc) as > thMapFoo3 acc (x :* xs) = thMapFoo3 (tfoo x :* acc) xs > > instance THMapFoo3 acc HNil where > type THMapFoo3Res acc HNil = acc > thMapFoo3 acc _ = acc The following, when enabled, also takes ~0.6s. This demonstrates that, unlike the fundep case, the order of type class constraints does not, in this instance, affect the performance of type families. > testTHMapFoo3 = thMapFoo3 HNil sampleData --Gershom

2 1