May 2008 - Haskell-Cafe

GHC predictability
by Jeff Polakow 15 May '08

15 May '08

Hello, One frequent criticism of Haskell (and by extension GHC) is that it has unpredictable performance and memory consumption. I personally do not find this to be the case. I suspect that most programmer confusion is rooted in shaky knowledge of lazy evaluation; and I have been able to fix, with relative ease, the various performance problems I've run into. However I am not doing any sort of performance critical computing (I care about minutes or seconds, but not about milliseconds). I would like to know what others think about this. Is GHC predictable? Is a thorough knowledge of lazy evaluation good enough to write efficient (whatever that means to you) code? Or is intimate knowledge of GHC's innards necessary? thanks, Jeff PS I am conflating Haskell and GHC because I use GHC (with its extensions) and it produces (to my knowledge) the fastest code. --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

29 59

Re: [Haskell] Re: [Haskell-cafe] ANN: Haddock version 2.1.0
by David Waern 15 May '08

15 May '08

2008/5/2 Simon Marlow <marlowsd(a)gmail.com>: > David Waern wrote: > > > No it doesn't, but it's on the TODO list. It needs a fix in GHC. > > > > By the way, I'm going to experiment with doing the parsing of comments > > on the Haddock side instead of in GHC. > > If that works out, we won't have to fix these things in GHC anymore. > > > > Sounds great - along the lines that we discussed on cvs-ghc a while back? Yes, something along the lines of separately parsing the comments and recording their source locations, and then trying to match them with the source locations of the AST nodes. I don't think there are any lexical rules for where Haddock comments can exist, so it should work. David

7 15

FFI: newbie linking problem
by Olivier Boudry 15 May '08

15 May '08

Hi all, I'm trying to call the following C function. RFC_RC _stdcall RfcUTF8ToSAPUC(const RFC_BYTE *utf8, unsigned utf8Length, SAP_UC *sapuc, unsigned *sapucSize, unsigned *resultLength, RFC_ERROR_INFO *info) I wrote a foreign import for this function: foreign import ccall unsafe "sapnwrfc.h RfcUTF8ToSAPUC" f_RfcUTF8ToSAPUC :: RfcBytePtr -> CUInt -> SapUCPtr -> Ptr CUInt -> Ptr CUInt -> RfcErrorInfoPtr -> IO RfcRetCodeType But when compiling I keep getting this error: C:\Temp\Haskell\HSAP>ghc --make -LC:/Temp/nwrfcsdk/lib -lsapnwrfc SAP/Types.hs Test.hs [1 of 2] Compiling SAP.Types ( SAP/Types.hs, SAP/Types.o ) Linking Test.exe ... SAP/Types.o(.text+0x91c):fake: undefined reference to `RfcUTF8ToSAPUC@24' collect2: ld returned 1 exit status I ran nm.exe on the sapnwrfc.lib to see the exports and got this list: SAPNWRFC.dll: 00000000 I .idata$4 00000000 I .idata$5 00000000 I .idata$6 00000000 T .text 00000000 T _RfcUTF8ToSAPUC@24 U __IMPORT_DESCRIPTOR_SAPNWRFC 00000000 I __imp__RfcUTF8ToSAPUC@24 It looks like RfcUTF8ToSAPUC@24 exists. I tried prepending a _ but it doesn't change anything. GHC tries to link directly to the .dll file and not to the .lib file. Is this a problem? Should I convert the .lib to a .a and link the .a? Is there a way to list the exports directly from the dll file? Thanks, Olivier.

2 3

saner shootout programs
by J C 15 May '08

15 May '08

I don't know Haskell very well, but even I can tell, looking at, for example, the N-body benchmark, that the Haskell code is probably not type-safe, and the tricks used in it would not be usable in a larger program (see below). The task is essentially a pure computation: take a list of bodies having mass, position and velocity; apply Newton laws at discrete intervals for a large number of times; return new positions and velocities. I could write a C++ procedure that performs this task and have some piece of mind regarding its type correctness, exception safety and functional purity: side effects would be local to the procedure, arguments passed as const or by value, the result returned by value, no type casts or new/delete operators used. On the other hand, the Haskell code makes assumptions about the size of double-precision floats (obviously not type-safe). Further, the simulation is not a pure function. It is often argued that one only needs these dirty tricks in the most time-consuming functions. However, if using imperative programming in these "inner loop" procedures places them in IO monad, the "outer loops" (the rest of the program - procedures that call it) will have to go there as well. This makes me doubt the Haskell approach to functional programming. If anyone has a version of the N-body benchmark, where the simulation is a type-safe pure function, I would very much like to see and time it.

6 15

Monad for HOAS?
by Edsko de Vries 15 May '08

15 May '08

Hi, Suppose we have some data structure that uses HOAS; typically, a DSL with explicit sharing. For example: > data Expr = One | Add Expr Expr | Let Expr (Expr -> Expr) When I use such a data structure, I find myself writing expressions such as > Let foo $ \a -> > Let bar $ \b -> > Add a b It seems to me that there should be a monad here somewhere, so that I can write this approximately like do a <- foo b <- bar return (Add a b) or something along those lines. It is however not at all clear to me what this monad should look like. I have experimented with adding a type parameter to Expr, something like > data Expr a = One > | Add (Expr a) (Expr a) > | Let (Expr a) (Expr a -> Expr a) > | Place a which has the additional benefit of supporting catamorphisms; I have also experimented with defining various variations on > Let a b = Let a (a -> b) and making Let an instance of Monad rather than Expr; but none of my experiments wered satisfactory. Am I missing something obvious, or is there a good reason this cannot be done? Thanks, Edsko

4 6

Re: Richer (than ascii) notation for haskell source?
by Patrick Surry 15 May '08

15 May '08

Lots of folk have suggested writing code with Unicode symbols, but that doesn't really get me where I'm thinking of. Back in the day, I spent many happy hours writing math(s) in amstex style, peppered with latex backslash references/macros for greek symbols, set operators as well as character attributes like underline, bold, goth, italic and so on. With the magic of (la)tex and dvips you get a rich intuitive representation of your equations - where you can 'see' types by character attributes (bold vectors, gothic sets or whatever) and have easily readable operators, functions, etc. Similarly to display alternative pattern cases as a display equation? So maybe what I really want is to essentially write my source in (la)tex and be able to both compile and render to dvi at the same time? I suppose word's crazy equation editor or mathml is another option but it makes the source itself either less portable or less readable? I think Knuth talks about literate programming as this ability to intermingle 'beautified' human-readable representation along with code, and it seems like Haskell is close to delivering that. (Tho I think "literate Haskell" is not the same thing.) Perhaps a pipe dream tho. Patrick ________________________________________________________________________ DISCLAIMER: This e-mail is intended only for the addressee named above. As this e-mail may contain confidential or privileged information, if you are not the named addressee, you are not authorised to retain, read, copy or disseminate this message or any part of it. If you received this email in error, please notify the sender and delete the message from your computer.

2 1

RE: Richer (than ascii) notation for haskell source?
by Patrick Surry 15 May '08

15 May '08

Sorry, missed a mail digest: LyX and lhs2tex sound more like what I mean. Patrick -----Original Message----- From: Patrick Surry Sent: Wednesday, May 14, 2008 10:24 PM To: 'haskell-cafe(a)haskell.org' Subject: Re: Richer (than ascii) notation for haskell source? Lots of folk have suggested writing code with Unicode symbols, but that doesn't really get me where I'm thinking of. Back in the day, I spent many happy hours writing math(s) in amstex style, peppered with latex backslash references/macros for greek symbols, set operators as well as character attributes like underline, bold, goth, italic and so on. With the magic of (la)tex and dvips you get a rich intuitive representation of your equations - where you can 'see' types by character attributes (bold vectors, gothic sets or whatever) and have easily readable operators, functions, etc. Similarly to display alternative pattern cases as a display equation? So maybe what I really want is to essentially write my source in (la)tex and be able to both compile and render to dvi at the same time? I suppose word's crazy equation editor or mathml is another option but it makes the source itself either less portable or less readable? I think Knuth talks about literate programming as this ability to intermingle 'beautified' human-readable representation along with code, and it seems like Haskell is close to delivering that. (Tho I think "literate Haskell" is not the same thing.) Perhaps a pipe dream tho. Patrick ________________________________________________________________________ DISCLAIMER: This e-mail is intended only for the addressee named above. As this e-mail may contain confidential or privileged information, if you are not the named addressee, you are not authorised to retain, read, copy or disseminate this message or any part of it. If you received this email in error, please notify the sender and delete the message from your computer.

1 0

Re: GHC predictability
by Don Stewart 15 May '08

15 May '08

> I offer up the following example: > > mean xs = sum xs / length xs > > Now try, say, "mean [1.. 1e9]", and watch GHC eat several GB of RAM. (!!) But you know why, don't you? > sat down and spent the best part of a day writing an MD5 > implementation. Eventually I got it so that all the test vectors work > right. (Stupid little-endian nonsense... mutter mutter...) When I tried > it on a file containing more than 1 MB of data... ooooohhhh dear... Did you use Data.Binary or the other libraries for efficient access to gigabytes of data? > Of course, the first step in any serious attempt at performance improvement > is to actually profile the code to figure out where the time > is being spent. Well, actually, for our 'mean()' case, it means just using the right structures. Arrays for example: import Data.Array.Vector import Text.Printf mean :: UArr Double -> Double mean arr = b / fromIntegral a where k (n :*: s) a = n+1 :*: s+a a :*: b = foldlU k (0 :*: 0) arr :: (Int :*: Double) main = printf "%f\n" . mean $ enumFromToFracU 1 1e9 For example, $ time ./A 5.00000000067109e8 ./A 3.53s user 0.00s system 99% cpu 3.532 total Try allocating an array of doubles in C, and getting similar results. (The compiler is optimising this to: Main_zdszdwfold_info: leaq 32(%r12), %rax cmpq %r15, %rax movq %rax, %r12 ja .L10 movsd .LC0(%rip), %xmm0 ucomisd %xmm5, %xmm0 jae .L12 movq %rsi, (%rax) movq $base_GHCziFloat_Dzh_con_info, -24(%rax) movsd %xmm6, -16(%rax) movq $base_GHCziBase_Izh_con_info, -8(%rax) leaq -7(%rax), %rbx leaq -23(%rax), %rsi jmp *(%rbp) .L12: movapd %xmm6, %xmm0 addq $1, %rsi subq $32, %r12 addsd %xmm5, %xmm0 addsd .LC2(%rip), %xmm5 movapd %xmm0, %xmm6 jmp Main_zdszdwfold_info Note even any garbage collection. This should be pretty much the same performance-wise as unoptimised C. > almost any nontrivial program you write > spends 60% or more of its time doing GC rather than actual work. Ok, you're doing something very wrong. GC time is typically less than 15% of the running time of typical work programs I hack on. I bet you're using lists inappropriately? > I find it completely impossibly to write code that doesn't crawl along at a > snail's pace. Even when I manage to make it faster, I usually have no clue > why. I think there is a problem that few people are taking the time to understand the compilation model of Haskell, while they've had the C runtime behaviour drilled into their brains since college. Until you sit down and understand what your Haskell code means, it will be very hard to reason about optimisations, unfortunately. GHC does what it does well, and its predictable. As long as you understand the operations your trying to make predictions about. I suggest installing ghc-core, and looking at how your code is compiled. Try many examples, and have a good knowledge of the STG paper. -- Don

8 12

Monad vs ArrowChoice
by Ronald Guida 14 May '08

14 May '08

I have read that Monad is stronger than Idiom because Monad lets me use the results of a computation to choose between the side effects of alternative future computations, while Idiom does not have this feature. Arrow does not have this feature either. ArrowChoice has the feature that the sum type, Either, can be used to choose between alternative computations, including their side effects. I know that Monad is supposed to be stronger than ArrowChoice, but I have to ask, what exactly can Monad do that ArrowChoice can't do? Let me set up an example to illustrate where I'm coming from. > import Control.Monad.Writer > import Control.Applicative > import Control.Arrow hiding (pure) The missileControl function accepts a flag to determine whether missiles actually get launched, and it returns the number of casualties. > missileControl :: Bool -> IO Integer > missileControl b = do > showFlag b > casualties <- if b > then launchMissiles > else doNotLaunch > return casualties > showFlag :: Bool -> IO Bool > showFlag b = (putStrLn $ "Launch flag = " ++ show b) >> return b > launchMissiles :: IO Integer > launchMissiles = do > putStrLn "Missiles have been launched." > putStrLn "Casualties = 6,700,000,000." > return 6700000000 > doNotLaunch :: IO Integer > doNotLaunch = putStrLn "Missiles not launched." >> return 0 If I try to use an Idiom, or even an Arrow, instead of a Monad, then I don't get to choose between the alternative side effects, and the results will be similar to this: > missileControl' :: Bool -> IO Integer > missileControl' b = do > showFlag b > casualties <- launchMissiles > casualties' <- doNotLaunch > if b > then return casualties > else return casualties' If I use ArrowChoice, then I can do this: > missileControl2 :: Bool -> IO Integer > missileControl2 b = runKleisli a b > where a = (Kleisli $ showFlag) >>> (arr boolToEither) >>> > ((Kleisli $ const launchMissiles) ||| > (Kleisli $ const doNotLaunch)) > boolToEither :: Bool -> Either () () > boolToEither True = Left () > boolToEither False = Right () GHCi> missileControl2 True Launch flag = True Missiles have been launched. Casualties = 6,700,000,000. 6700000000 GHCi> missileControl2 False Launch flag = False Missiles not launched. 0

2 1

Copy on read
by Andrew Coppin 14 May '08

14 May '08

I just had a random idea, which I thought I'd share with you all. I've heard about systems that do "copy on write". That is, all users share a single copy of some structure, until somebody tries to write on it. At that moment they get a personal copy to modify so they don't upset everybody else. This way, you don't have to go to all the expense of copying a potentially large structure unless it's actually necessary to do so. Then I started thinking about Clean's "uniqueness typing". If I'm understanding this correctly, it lets you do things like mutate data in-place without requiring a monad. The restriction is that the compiler has to be satisfied, at compile-time, that you will never try to access the old data you just overwrote. Although I once held more optimistic beliefs, as far as I can tell no current, real-world Haskell implementation ever mutates the fields of algebraic data types in-place. (Ignoring for a moment the issue of overwriting a thunk with it's result.) This strikes me as rather pessimistic. I was thinking... If Haskell had uniqueness typing, maybe the compiler could be made to infer when values are used in a unique way. And maybe if the compiler can detect data being used in a unique way, it could code for in-place updates instead of copying, and thereby gain a performance advantage. I don't know how viable this would be - the thing that immediately jumps out at me is that in practice there might be comparatively few places where you can *guarantee* the transformation is safe, and so it might not get applied very much. And considering all this would likely take a fair bit of work on the compiler, that wouldn't be a great payoff. Still, the idea of the compiler transparently rewriting your pure functional code to efficient mutable updates (when safe) is very appealing for performance reasons. Thoughts, people? [I'd be surprised if I'm the first person ever to have this idea...]

6 7