- Haskell-Cafe - Haskell.org

RE: [Haskell-cafe] Joels Time Leak
by Simon Peyton-Jones 29 Dec '05

29 Dec '05

Thanks for looking, Adrian, It'd be great if someone was able to find out more about what's going on here. Bandwidth at GHC HQ is always tight, so the more precisely someone can pinpoint what's happening, the faster we can fix it. Joel has done a lot by making a repro case. Maybe others can help to narrow it down? Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | Adrian Hey | Sent: 29 December 2005 13:03 | To: haskell-cafe(a)haskell.org | Subject: [Haskell-cafe] Joels Time Leak | | Hello, | | I haven't followed everything that's happened on the Binary IO | thread, but has anybody else actually tried Joels code? .. | | http://wagerlabs.com/timeleak.tgz | | I can reproduce the problem (ghc/Linux), but can't explain it. It | seems very strange that friggin about with an otherwise irrelevant | (AFAICT) MVar fixes the problem. | | Regards | -- | Adrian Hey | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

4 4

Haskell Speed
by Daniel Carrera 29 Dec '05

29 Dec '05

Hi all, I'm taking a look at the "Computer Language Shootout Benchmarks". http://shootout.alioth.debian.org/ It looks like Haskell doesn't do very well. It seems to be near the bottom of the pile in most tests. Is this due to the inherent design of Haskell or is it merely the fact that GHC is young and hasn't had as much time to optimize as other compilers? For example, another very slow language is Ruby. In Ruby's case, there is a design factor that will always make it slow. I wonder if Haskell is in a smilar situation. Yes yes, I know that a high level language trades CPU time by programmer time. I'm still interested in the CPU time question though :) Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

15 30

Haskell vs OCaml
by Daniel Carrera 29 Dec '05

29 Dec '05

Hi all, Okay, I've been studying Haskell for a few days and I think I have a feel for the language. I completted a course, and wrote a Revers Polish Notation calculator. Now that I sort of understand Haskell, I was hoping someone could give me an opinion on OCaml from a Haskell POV. Both are functional and have fairly clear syntax. OCaml is supposed to be very fast, and Haskell perhaps is not. Besides that, what else could you say about them? What would make someone prefer one over the other? Any thoughts, opinions and comments would be most appreciated. Thanks! Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

11 20

strange stack overflow with Data.Map
by David Roundy 29 Dec '05

29 Dec '05

Hi all, I've got a problem that I'm seeing using either Data.Map or Data.IntMap. > module Main where > import Data.List > import qualified Data.IntMap as Map > stats elems = foldl add_elem Map.empty elems > add_elem m x = Map.insertWith (+) x 1 m > main = print $ stats $ take 1000000 $ repeat 1 This program has a space leak and runs out of stack space. I'm guessing that I'm being bit here by an unnatural amount of laziness in Map.insertWith, but I can't see how to fix this. :( I'm sure it's something elementary... I tried defining add_elem m x = let m' = Map.insertWith (+) x 1 m Just num = Map.lookup x m' in seq num m' to force the (+) to be evaluated strictly, but that didn't help. -- David Roundy http://www.darcs.net

7 8

Re: [Haskell-cafe] GHC for Windows - no installer
by Paul Moore 29 Dec '05

29 Dec '05

On 12/29/05, Simon Peyton-Jones <simonpj(a)microsoft.com> wrote: > Yes, it should work > http://www.haskell.org/ghc/docs/latest/html/users_guide/sec-install-wind > ows.html Thanks. Sorry I missed that link, and thanks for the pointer. Paul.

1 0

How to read this syntax?
by David F. Place 29 Dec '05

29 Dec '05

Hi, I am trying to read _Arrows, Robots, and Functional Reactive Programming_ by Hudak, et al. http://www.haskell.org/yampa/AFPLectureNotes.pdf In section 2.1 there are a number of equations of the form: g’ :: SF A C g’ = arr g = arr f1 >>> arr f2 and i’ :: SF (A,C) (B,D) i’ = arr i = arr (f1 . fst) &&& arr (f2 . snd) = (arr fst >>> arr f1) &&& (arr snd >>> arr f2) I can't find any reference to the syntax where the function left hand side is just "space." I'd greatly appreciate any insight. -------------------------------- David F. Place mailto:d@vidplace.com

2 1

Re: [Haskell-cafe] strange stack overflow with Data.Map
by David Roundy 29 Dec '05

29 Dec '05

On Thu, Dec 29, 2005 at 04:24:02PM +0100, Jean-Philippe Bernardy wrote: > On 12/29/05, David Roundy <droundy(a)abridgegame.org> wrote: > > On Thu, Dec 29, 2005 at 01:42:29PM +0100, Christian Maeder wrote: > > > David Roundy wrote: > > > >>stats elems = foldl add_elem Map.empty elems > > > >>add_elem m x = Map.insertWith (+) x 1 m > > > > > > > >>main = print $ stats $ take 1000000 $ repeat 1 > > > > > > > >This program has a space leak and runs out of stack space. I'm guessing > > > >that I'm being bit here by an unnatural amount of laziness in > > > >Map.insertWith, but I can't see how to fix this. :( I'm sure it's > > > >something elementary... > > > try: > > > > > > stats = foldl' add_elem Map.empty > > > add_elem m x = myinsertWith (+) x 1 m > > > > > > myinsertWith f k v m = > > > case Map.lookup k m of > > > Nothing -> Map.insert k v m > > > Just w -> let r = f v w in r `seq` Map.insert k r m > > > > Thanks, that does it! I had tried something like that, but without the > > foldl', and had tried foldl', but without the myinsertWith. The reason I > > didn't spend much time using this implementation is that for large maps, it > > will take twice as long as Map.insertWith, so I assumed (incorrectly) that > > Map.insertWith should be written so that it behaves in a non-leaky manner. > > I'm not sure I understand this ... Do you say that the leaky program > is faster than the non-leaky one ? No, what I mean is that Map.insertWith only traverses the Map once, while myinsertWith has to traverse it twice, so for a large map, each call to myinsertWith will take twice as long as Map.insertWith. Or to put it a different way, if myinsertWith were part of the Map module, it could be twice as fast. > > Should the Map modules have an additional Map.insertWith' that behaves > > strictly, or might it be the case that you always want strict behavior when > > using insertWith? > > IMO, there is always a possibility for needing the lazy version. I > also have to say that making a strict version for each "...With" does > not fill my heart with joy. :) Such cases call for cheapness analysis, > or optimistic evaluation, or some other kind of solution implemented > at the compiler level, IMHO. I agree, there is a possibility for wanting the lazy version. If you only want to provite one insertWith, I suppose you'd want to figure out whether the lazy or strict version is more commonly needed (or "safer"), and make people wanting the other version implement it themselves. In my opinion, the strict version seems nicer, largely because HNF is cheap for most "large" computations I do, so strictness wouldn't cost much. On the subject of excessive functions, what are the uses of insertWithKey? It seems like anything you do with insertWithKey you could just as efficiently do with insertWith... it seems pretty trivial to write insertWithKey f k x = insertWith (f k) k x There may be a use to all the WithKey variants, but I'd much rather have strict varients... -- David Roundy http://www.darcs.net

1 0

GHC for Windows - no installer
by Paul Moore 29 Dec '05

29 Dec '05

I'd like to have GHC available to me, but some of the PCs I work on are extremely tight on space, or "locked down" in such a way that I can't install GHC on them. To get around this, I was considering copying GHC from my development PC onto a pen drive, and then using that (setting PATH when I needed access to GHC). My question is, will this work? Can the Windows install of GHC be copied around, or does it rely on registry entries or other system configuration in such a way that it has to be "properly" installed? Thanks, Paul.

1 0

RE: GHC optimization issue
by Simon Peyton-Jones 29 Dec '05

29 Dec '05

I did look into this a little. There are several things going on * GHC doesn't really expect you to use INLINE and SPECIALISE together. INLINE says to inline a copy of the function at every call site, which is the best possible form of specialisation, so SPECIALISE is a bit redundant if you are happy to do that. (Incidentally, INLINE is ignored for recursive functions, whereas SPECIALISE works fine.) * If you have both INLINE and SPECIALISE, GHC makes a specialised copy of the function, and the specialised copy takes precedence. So a call at the specialised type turns into a call to the specialised function. (A call at any other type would not use the specialisation, and so the un-specialised function would be inlined.) Moreover, the specialised copies are themselves not marked INLINE. * GHC's HEAD in CVS (i.e 6.5) has a new feature {#- SPECIALISE INLINE f :: <type> #-} which tells GHC to specialise f and inline the specialised copy (only). Ordinary, un-specialised calls will not be inlined. * When you delete the pragmas, GHC uses a size-based heuristic to decide when to inline a function at a call site. Oddly, this heuristic decides (just) to inline the un-specialised function, but when it's specialised GHC thinks it's bigger and doesn't inline it. You can increase the threshold for inlining with -funfolding-use-threshold=20, say. http://www.haskell.org/ghc/docs/latest/html/users_guide/options-optimise .html#options-f This really is a bit odd, but I don't want to fiddle with GHC's inlining heuristics without doing lots of benchmark runs etc. Actually, it'd be quite an easy thing for others to try fiddling with, and I bet there are performance gains to be had. Simon | -----Original Message----- | From: Joel Reymont [mailto:joelr1@gmail.com] | Sent: 22 December 2005 14:09 | To: Haskell-Cafe Cafe | Cc: Simon Peyton-Jones; Simon Marlow | Subject: GHC optimization issue | | Folks, | | I have been trying to improve my byte swapping routines as part of my | effort to speed up serialization. I then tried to look at the core | output from GHC to see what it was converting my code into. Brandon | (skew on #haskell) helped me code a TH version but then I went with a | regular CPP version instead. | | The point of contention is that the logical approach to optimization | does not produce expected results. The only difference between the | following two core outputs is the presence or absence of specialize | and inline pragmas. The code is the same. | | The version without pragmas inlines foo1 into | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) | of ww1_a2eo { __DEFAULT -> | case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of | ww_a2f4 { __DEFAULT -> | GHC.Word.W16# (GHC.Prim.narrow16Word# | (GHC.Prim.plusWord# ww1_a2eo ww_a2f4)) | } | } | | Whereas the version _with_ pragmas produces a function call: | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 Swap1.$w$sswap16 __word 3855 | of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | | Is there a reasonable explanation? | | Both versions compiled thusly: ghc --make Foo.hs -O -ddump-simpl > foo | | Swap: | | {-# OPTIONS_GHC -fglasgow-exts -cpp #-} | module Swap1 | ( | swap16 | ) | where | | import Data.Word | import Data.Int | import Data.Bits | | #define BIG_ENDIAN 1 | | {-# SPECIALIZE swap16 :: Word16 -> Word16 #-} | {-# SPECIALIZE swap16 :: Int16 -> Int16 #-} | {-# INLINE swap16 #-} | | swap16 :: Bits a => a -> a | #ifdef BIG_ENDIAN | swap16 v = (v `shiftR` 8) + ((v .&. 0xFF) `shiftL` 8) | #else | swap16 v = v | #endif | | Foo: | | module Main where | | import Data.Word | import Swap1 | | foo1 :: Word16 | foo1 = swap16 0x0f0f | | main = putStrLn $ show foo1 | | Core output for the version WITH pragmas, see the version w/o pragmas | way below | | ==================== Tidy Core Rules ==================== | "SPEC Swap1.swap16" __forall {$dBits_X1Co :: {Data.Bits.Bits | GHC.Int.Int16}} | Swap1.swap16 @ GHC.Int.Int16 $dBits_X1Co | = Swap1.$sswap16 ; | "SPEC Swap1.swap16" __forall {$dBits_X1Cv :: {Data.Bits.Bits | GHC.Word.Word16}} | Swap1.swap16 @ GHC.Word.Word16 $dBits_X1Cv | = Swap1.$sswap161 ; | | | ==================== Tidy Core ==================== | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 Swap1.$w$sswap16 __word 3855 | of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | | ==================== Tidy Core ==================== | Swap1.$w$sswap16 :: GHC.Prim.Word# -> GHC.Prim.Word# | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.$w$sswap16 = \ (ww_s1I5 :: GHC.Prim.Word#) -> | case GHC.Prim.Word# GHC.Word.$wshift3 ww_s1I5 | (-8) of ww1_a1Gx { __DEFAULT -> | case GHC.Prim.Word# GHC.Word.$wshift3 | (GHC.Prim.and# ww_s1I5 __word 255) 8 | of ww11_a1Hd { __DEFAULT -> | GHC.Prim.narrow16Word# (GHC.Prim.plusWord# | ww1_a1Gx ww11_a1Hd) | } | } | | Swap1.$w$sswap161 :: GHC.Prim.Int# -> GHC.Prim.Int# | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.$w$sswap161 = \ (ww_s1HV :: GHC.Prim.Int#) -> | case GHC.Prim.Int# GHC.Int.$wshift2 ww_s1HV | (-8) of ww1_a1Fk { __DEFAULT -> | case GHC.Prim.Int# GHC.Int.$wshift2 | (GHC.Prim.word2Int# | (GHC.Prim.and# (GHC.Prim.int2Word# ww_s1HV) __word 255)) | 8 | of ww11_a1G5 { __DEFAULT -> | GHC.Prim.narrow16Int# (GHC.Prim.+# ww1_a1Fk | ww11_a1G5) | } | } | | Swap1.$sswap16 :: GHC.Int.Int16 -> GHC.Int.Int16 | [GlobalId] | [Arity 1 | Worker Swap1.$w$sswap161 | NoCafRefs | Str: DmdType U(L)m] | Swap1.$sswap16 = __inline_me (\ (w_s1HT :: GHC.Int.Int16) -> | case GHC.Int.Int16 w_s1HT of w1_X1I5 | { GHC.Int.I16# ww_s1HV -> | case GHC.Int.Int16 Swap1.$w$sswap161 | ww_s1HV of ww1_s1I0 { __DEFAULT -> | GHC.Int.I16# ww1_s1I0 | } | }) | | Swap1.$sswap161 :: GHC.Word.Word16 -> GHC.Word.Word16 | [GlobalId] | [Arity 1 | Worker Swap1.$w$sswap16 | NoCafRefs | Str: DmdType U(L)m] | Swap1.$sswap161 = __inline_me (\ (w_s1I3 :: GHC.Word.Word16) -> | case GHC.Word.Word16 w_s1I3 of | w1_X1Ih { GHC.Word.W16# ww_s1I5 -> | case GHC.Word.Word16 Swap1.$w | $sswap16 ww_s1I5 of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | }) | | Swap1.swap16 :: forall a_a1aQ. (Data.Bits.Bits a_a1aQ) => a_a1aQ -> | a_a1aQ | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.swap16 = __inline_me (\ (@ a_a1dB) | ($dBits_a1ip :: {Data.Bits.Bits | a_a1dB}) -> | let { | $dNum_s1BO :: {GHC.Num.Num a_a1dB} | [Str: DmdType {a1ip->U | (SAAAAAAAAAAAAAAAAA)}] | $dNum_s1BO = Data.Bits.$p1Bits @ | a_a1dB $dBits_a1ip } in | let { | lit_s1BN :: a_a1dB | [Str: DmdType {a1ip->U | (SAAAAAAAAAAAAAAAAA) s1BO->U(AAAAAAAAS)}] | lit_s1BN = GHC.Num.fromInteger @ | a_a1dB $dNum_s1BO (GHC.Num.S# 255) | } in | \ (v_a1aW :: a_a1dB) -> | GHC.Num.+ | @ a_a1dB | $dNum_s1BO | (Data.Bits.shiftR @ a_a1dB | $dBits_a1ip v_a1aW (GHC.Base.I# 8)) | (Data.Bits.shiftL | @ a_a1dB | $dBits_a1ip | (Data.Bits..&. @ a_a1dB | $dBits_a1ip v_a1aW lit_s1BN) | (GHC.Base.I# 8))) | | | Core output without pragmas: | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) | of ww1_a2eo { __DEFAULT -> | case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of | ww_a2f4 { __DEFAULT -> | GHC.Word.W16# (GHC.Prim.narrow16Word# | (GHC.Prim.plusWord# ww1_a2eo ww_a2f4)) | } | } | | --- | Swap1.swap16 :: forall a_a1aQ. (Data.Bits.Bits a_a1aQ) => a_a1aQ -> | a_a1aQ | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.swap16 = \ (@ a_a1dB) ($dBits_a1ip :: {Data.Bits.Bits a_a1dB}) -> | let { | $dNum_s1BK :: {GHC.Num.Num a_a1dB} | [Str: DmdType] | $dNum_s1BK = case {GHC.Num.Num a_a1dB} $dBits_a1ip | of tpl_B1 { Data.Bits.:DBits tpl1_B2 | tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba | tpl10_Bb tpl11_Bc tpl12_Bd tpl13_Be tpl14_Bf tpl15_Bg tpl16_Bh | tpl17_Bi tpl18_Bj -> | tpl1_B2 | } } in | let { | lit_s1BM :: a_a1dB | [Str: DmdType] | lit_s1BM = case a_a1dB $dNum_s1BK | of tpl_B1 { GHC.Num.:DNum tpl1_B2 | tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba -> | tpl9_Ba Swap1.lvl1 | } | } in | \ (v_a1aW :: a_a1dB) -> | tpl3_B4 | (case a_a1dB $dBits_a1ip | of tpl10_Xy { Data.Bits.:DBits tpl11_XB | tpl12_XD tpl13_XF tpl14_XH tpl15_XJ tpl16_XL tpl17_XN tpl18_XP | tpl19_XR tpl20_Bb tpl21_Bc tpl22_Bd tpl23_Be tpl24_Bf tpl25_Bg | tpl26_Bh tpl27_Bi tpl28_Bj -> | tpl26_Bh v_a1aW Swap1.lvl | }) | (case a_a1dB $dBits_a1ip | of tpl10_Xy { Data.Bits.:DBits tpl11_XB | tpl12_XD tpl13_XF tpl14_XH tpl15_XJ tpl16_XL tpl17_XN tpl18_XP | tpl19_XR tpl20_Bb tpl21_Bc tpl22_Bd tpl23_Be tpl24_Bf tpl25_Bg | tpl26_Bh tpl27_Bi tpl28_Bj -> | tpl25_Bg (tpl12_XD v_a1aW lit_s1BM) Swap1.lvl | }) | | -- | http://wagerlabs.com/ | | | |

1 0

RE: Erlang vs. Haskell (was Re: [Haskell-cafe] binary IO)
by Simon Peyton-Jones 29 Dec '05

29 Dec '05

| Using Haskell for this networking app forced me to focus on all the | issues _but_ the business logic. Type constraints, binary IO and | serialization, minimizing memory use and fighting laziness, timers, | tweaking concurrency and setting up message channels, you name it. That's a disappointing result. Mostly I think Haskell lets you precisely focus on the logic of your program, because lots else is taken care of behind the scenes. You found precisely the reverse. It'd be interesting to understand which of these issues are - language issues - library issues - compiler/run-time issues My (ill-informed) hypothesis is that better libraries would have solved much of your problems. A good example is a fast, generic serialisation library. If you felt able (sometime) to distil your experience under headings like the above, only more concretely and precisely, I think it might help to motivate Haskellers to start solving them. Simon

1 0

RE: [Haskell-cafe] Re: Haskell Speed
by Branimir Maksimovic 28 Dec '05

28 Dec '05

>From: Isaac Gouy <igouy(a)yahoo.com> >To: haskell-cafe(a)haskell.org >Subject: [Haskell-cafe] Re: Haskell Speed >Date: Tue, 27 Dec 2005 20:12:01 -0800 (PST) > >Branimir Maksimovic wrote: > > Of course, first example uses [String] instead of >Data.HashTable > > as other languages do. Imagine C program does not >use > > hash,rather list, how it will perform:) > >And the author comments his program >-- This is a purely functional solution to the >problem. >-- An alternative which keeps a mutable table of >occurences would >-- be faster. > Yes, I saw that but that does not qualifies for benchmark with hash tables. I mean program is ok, but this is aplles to oranges. >We'll be happy to also show a Haskell program that >uses Data.HashTable - first, someone needs to >contribute that program. Ok , i've attached hash table version. As I'm Haskell newbie I suppose there is someone which can do much better. > > > > I didn't look further after that. > >Ideal - you may criticize without the risk that others >will criticize what you do. Attachment follows, you can cricize my poor Haskell skills as much you want :) This version si actually D program trnslated to Haskell + file parsing code from original Haskell program. Now wou can compare no matter how slow it is :) Greetings, Bane. _________________________________________________________________ Don't just search. Find. Check out the new MSN Search! http://search.msn.click-url.com/go/onm00200636ave/direct/01/

1 0

Shared/Exclusive Locks
by John Goerzen 28 Dec '05

28 Dec '05

Hello, I have the need for a locking object that can provide shared and exclusive locks in much the same manner as the POSIX flock() function. A thread that acquires an exclusive lock has a guarantee that no other thread holds any locks. A thread that acquires a shared lock has a guarantee that no other thread holds an exclusive lock, though any number of other threads hold shared locks. My intuition tells me that this could be implemented in terms of an MVar somehow. (At least, I've used MVars for simple locks for quite some time.) But I can't quite figure out how. Any ideas? Thanks, -- John

4 6

NewBinary on Ptrs
by Pupeno 28 Dec '05

28 Dec '05

Hello, After trying my own code and reading the whole thread I started to understand NewBinary. I'm going to give it a try. My question now is how to turn a Ptr into a BinHandle to use NewBinary on it, or is there another way to do it ? Thanks. -- Pupeno <pupeno(a)pupeno.com> (http://pupeno.com)

2 1

RE: [Haskell-cafe] Haskell vs. Erlang for heavy-duty network apps
by Simon Peyton-Jones 28 Dec '05

28 Dec '05

I've already said to Joel (off-list) how valuable I think his experience of using Haskell for a new kind of real application is. I see no reason in principle why Haskell shouldn't work just fine for his kind of application. But he's pushing hard on parts of the system (both run-time-system and libraries) that have not been as thoroughly exercised as (say) list processing. Quite a few people on the mailing list have helped a lot. My sense is (though I have not followed all the twists and turns) that Joel's experience has exposed immaturity in many of the networking libraries. I hope that people on this list may feel motivated to help improve them. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Joel | Reymont | Sent: 25 December 2005 13:35 | To: Tomasz Zielonka | Cc: haskell-cafe(a)haskell.org; Peter Simons; Bulat Ziganshin | Subject: Re: [Haskell-cafe] Haskell vs. Erlang for heavy-duty network apps | | | On Dec 25, 2005, at 1:14 PM, Tomasz Zielonka wrote: | | > I think your work will be very important and valuable for the | > community. | > You've shown were Haskell could be better, and I believe it will catch | > up eventually, either by improvements in GHC, in libraries or simply | > in documentation. | | Thank you Tomasz! I think eventually will come sooner than you | think :-). | | On my TODO list for the next few weeks: | | 1) Set up a Haskell vs. Erlang heavily-multithreaded serialization | shootout | 2) Work Simon M. to make sure Haskell is on par and try to hack GHC | to add whatever is needed | 3) Add profiling support for STM to GHC (including retainer profiling) | 4) Adapt the Zipper FileServer OS to #1. See if single-threading with | delimited continuations is better than multi-threading with unbound | threads. | 5) If #4 is a yes then investigate why | | And of course I will blog about the whole thing as I go along. | | Thanks, Joel | | -- | http://wagerlabs.com/ | | | | | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Re: Haskell Speed
by Isaac Gouy 28 Dec '05

28 Dec '05

Branimir Maksimovic wrote: > Of course, first example uses [String] instead of Data.HashTable > as other languages do. Imagine C program does not use > hash,rather list, how it will perform:) And the author comments his program -- This is a purely functional solution to the problem. -- An alternative which keeps a mutable table of occurences would -- be faster. We'll be happy to also show a Haskell program that uses Data.HashTable - first, someone needs to contribute that program. > I didn't look further after that. Ideal - you may criticize without the risk that others will criticize what you do. __________________________________ Yahoo! for Good - Make a difference this year. http://brand.yahoo.com/cybergivingweek2005/

1 0

Re: Haskell Speed
by Isaac Gouy 28 Dec '05

28 Dec '05

Jared Updike wrote: > What that means is the results are completely subject to > (1) how good the submission for that tests was Contribute faster more-elegant programs http://shootout.alioth.debian.org/gp4/faq.php#contribute >(2) the choice of tests in the first place Suggest better tests http://shootout.alioth.debian.org/gp4/faq.php#newbench > (3) startup times for loading the binaries into memory (GHC > makes big binaries that are arguably much faster if you do > things in "daemon" mode, for example). Is that just speculation? (Erlang is an application server starting-up and that really is noticeable.) -snip- > it is pretty much a game created to make C win---it already > wins! Which C do you mean - gcc, Intel C, Tiny C? And, no! It is not a game created to make C win (although it is a game). And, no! C does not already win all the games - astonishingly it doesn't even "win" the basic loop and array test nsieve. __________________________________________ Yahoo! DSL Something to write home about. Just $16.99/mo. or less. dsl.yahoo.com

1 0

Re: Haskell Speed
by Isaac Gouy 28 Dec '05

28 Dec '05

Simon Marlow wrote: > Also, I would like to draw your attention to the fact that GHC > wipes the floor with nearly everyone in the concurrency > benchmark SmartEiffel is so much faster that I'm still trying to figure out if it's doing something different :-) Be interesting to see GHC on the other concurrency benchmark... http://shootout.alioth.debian.org/benchmark.php?test=chameneos&lang=all > Seriously, it's very difficult to draw any meaningful > conclusions from these benchmarks. Is it any easier to draw meaningful conclusions about the relative performance of programming languages from some other benchmarks? __________________________________________ Yahoo! DSL Something to write home about. Just $16.99/mo. or less. dsl.yahoo.com

1 0

Database mailing list?
by John Goerzen 28 Dec '05

28 Dec '05

Greetings, It seems there are a lot of people working on database-related things in Haskell. HaskellDB, wxHaskell, HDBC, HSQL, etc. I'm wondering if it would make sense to have a haskell-db mailing list to help coordinate efforts? (Or even just to help manage development on these projects without cluttering more general lists) -- John

1 0

Tutorial uploaded
by Daniel Carrera 28 Dec '05

28 Dec '05

Hi all, I've finished a first draft of what I call "First steps in Haskell". It's intended to be the very first thing a new user sees when they decide to try out Haskell. http://www.haskell.org/hawiki/FirstSteps?action=show It's a bit longer than I'd like, but I don't inmediately see anything I can take out without losing something valuable (given the purpose of this document). Thoughts and comments? Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

27 82

Re: [Haskell-cafe] Proper way to write this
by Donn Cave 27 Dec '05

27 Dec '05

Quoth Pupeno <pupeno(a)pupeno.com>: | I have this piece of code: What do you think about this? may_ = maybe (return ()) (\ _ -> f) stopDaytimeServer dts = do may_ (killServer (ss dts)) (streamPort dts) may_ (killServer (ds dts)) (dgramPort dts) | PS: I have a worse case: I don't think it will be too much worse. I would not try to combine the struct updates, in the "both" case -- it doesn't buy you anything, and pulls you into duplication you don't want. Donn Cave, donn(a)drizzle.com | stopDaytimeServer dts = | case dts of | DaytimeServer {streamPort = Just _, dgramPort = Just _} -> do | killServer (ss dts) | killServer (ds dts) | DaytimeServer {streamPort = Just _, dgramPort = Nothing} -> do | killServer (ss dts) | DaytimeServer {streamPort = Nothing, dgramPort = Just _} -> do | killServer (ds dts) | -- | Having a 'DaytimeServer', run it according to its specifications. | runDaytimeServer :: DaytimeServer -> IO DaytimeServer | runDaytimeServer dts = | case dts of | DaytimeServer {streamPort = Just _, dgramPort = Just _} -> do | ss <- runDgramDaytimeServer dts | ds <- runStreamDaytimeServer dts | return dts{ss = ss, ds = ds} | DaytimeServer {streamPort = Just _, dgramPort = Nothing} -> do | ss <- runStreamDaytimeServer dts | return dts{ss = ss} | DaytimeServer {streamPort = Nothing, dgramPort = Just _} -> do | ds <- runDgramDaytimeServer dts | return dts{ds = ds}

4 3

Re[2]: [Haskell-cafe] binary IO
by Bulat Ziganshin 27 Dec '05

27 Dec '05

Hello Pupeno, Tuesday, December 27, 2005, 6:03:50 PM, you wrote: >> you must use `openBitAligned` to open bit-aligned stream over Handle, >> and use `flushBits` at the end of writing. there is much more >> features, ask me about what you need P> Well, it seems I am seeing a bit of light here :) P> I have a couple of questions: P> - Is it possible to serialize from and to a Ptr ? Because TCP gives me a P> Handle, but UDP just gives me a Ptr with the packet and I'll turn the TCP P> into a Ptr as well. reading: h <- openMemory ptr size bh <- openBitAligned h a <- get bh b <- get bh .... -- you don't need to close/flush/free resources at the end writing: h <- createMemoryStream 64 -- replace 64 with initial buffer size you need -- the buffer will be extended if more data -- will be written bh <- openBitAligned h put_ bh a put_ bh b ... flushBits bh but currently there is no way to get data from this buffer :) just see structure of SimpleMemoryStream (created by createMemoryStream) and extract these data yourself - something like: copyMemToHandle mem handle = do let (Mem buf' pos' end') = mem buf <- readPtr buf' pos <- readPtr pos' hPutBuf handle buf (pos-:buf) P> - Is it possible to serialize from and to a Ptr ? Because TCP gives me a P> Handle, but UDP just gives me a Ptr with the packet and I'll turn the TCP P> into a Ptr as well. btw, you don't need to "convert" anything, my library works with Handle and memory buffers in the same way. so just parse data directly from the original source P> - Is it possible to specify the endiannes ? I need to read everything as P> big-endian. my library works in network format which is what you used in ptrToWord16BE. if you need another format - you can either define and use new low-level functions: getWord16LE h = do w1 <- vGetByte h w2 <- vGetByte h return $! ((w2 `shiftL` 8) .|. w1) or define these functions and use them in defining instances of Binary class: instance Binary Word16 where put_ = putWord16LE get = getWord16LE instance Binary Word32 where put_ = putWord32LE get = getWord32LE .... and then just read Word16/Word32/... types. the second solution needs to edit Binary.hs -- Best regards, Bulat mailto:bulatz@HotPOP.com

1 0

binary IO
by Dominic Steinitz 27 Dec '05

27 Dec '05

It might also be worth looking at the networking code in House given the intended application is parsing network packets. See http://www.cse.ogi.edu/~hallgren/House/kernel/pfe.cgi?Net.PacketParsing, for example. Dominic.

1 0

Re: [Haskell-cafe] Re: Haskell Speed
by Branimir Maksimovic 26 Dec '05

26 Dec '05

Paul Moore wrote: > On 25 Dec 2005 12:24:38 +0100, Peter Simons <simons(a)cryp.to> wrote: > >>Paul Moore writes: >> >> > It would be interesting to see standalone code for wcIOB >> > (where you're allowed to assume that any helpers you >> > need, like your block IO library, are available from the >> > standard library). This would help in comparing the >> > "obviousness" of the two approaches. >> >>A simple version of the program -- which doesn't need any >>3rd party modules to compile -- is attached below. My guess >>is that this approach to I/O is quite obvious, too, if you >>have experience with system programming in C. > > > Hmm, I can't honestly believe that you feel that your code is as > "obvious" as the original. I'm not unfamiliar with monads and state, > and I know C well, but it took me a significant amount of time to > decipher your code (even knowing what it was intended to do), whereas > I knew what the original was doing instantly. > > >>IMHO, the main point of the example in the article is that >> >> wc :: String -> (Int, Int, Int) >> wc file = ( length (lines file) >> , length (words file) >> , length file >> ) >> >>is a crapy word-counting algorithm. > > > Dunno. It's certainly not a bad (executable!) definition of the > problem. My point is that Haskell allows me to write *very* clear > "executable pseudocode", but that code is not a good starting point > for writing production-quality code. this program counts two times length of lists of strings formed by lines, and words and third time counts again length of file. This is not just word counting program, it creates two additional lists, which are not used anywhere but to count :) While it is certainly expressive, in terms of programing is pointless. No one would write such a code for word counting. Here is what I would write in Haskell, same logic as in C++ (i don;t know standard lib ): module Main where import IO import Char main = do s <- hGetContents stdin putStrLn $ show $ wc s wc :: String -> (Int , Int , Int) wc strs = wc' strs (0,0,0) where wc' [] res = res wc' (s:str) (lns, wrds, lngth ) | s == '\n' = wc' str (lns+1,wrds, lngth+1) | isAlpha s = wc'' str (lns, wrds+1,lngth+1) | otherwise = wc' str (lns,wrds, lngth+1) wc'' [] res = res wc'' (s:str) (lns,wrds,lngth) = if isAlphaNum s then wc'' str (lns,wrds,lngth+1) else wc' str (lns,wrds, lngth+1) Greetings, Bane.

4 4

Functions with side-effects?
by Daniel Carrera 26 Dec '05

26 Dec '05

Hi all, I'm a Haskell newbie and I don't really understand how Haskell deals with functions that really must have side-effects. Like a rand() function or getLine(). I know this has something to do with monads, but I don't really understand monads yet. Is there someone who might explain this in newbie terms? I don't need to understand the whole thing, I don't need a rand() function right this minute. I just want to understand how Haskell separates purely functional code from non-functional code (I understand that a rand() function is inevitably not functional code, right?) Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

10 17

Re: [Haskell-cafe] Proper way to write this
by Donn Cave 26 Dec '05

26 Dec '05

Quoth Pupeno <pupeno(a)pupeno.com>: | On Monday 26 December 2005 02:41, Donn Cave wrote: |> I don't think it will be too much worse. I would not try to |> combine the struct updates, in the "both" case -- it doesn't buy |> you anything, and pulls you into duplication you don't want. | What about this | | runDaytimeServer :: DaytimeServer -> IO DaytimeServer | runDaytimeServer dts = do | dts' <- runStreamDaytimeServer dts | dts' <- runDgramDaytimeServer dts' | return dts' | | ? | | I moved the structure update of dts into run_DaytimeServer. Right, that's what I was thinking. Donn Cave, donn(a)drizzle.com

1 0

Proper way to write this
by Pupeno 26 Dec '05

26 Dec '05

I have this piece of code: stopDaytimeServer dts = case dts of DaytimeServer {streamPort = Just _, dgramPort = Just _} -> do killServer (ss dts) killServer (ds dts) DaytimeServer {streamPort = Just _, dgramPort = Nothing} -> do killServer (ss dts) DaytimeServer {streamPort = Nothing, dgramPort = Just _} -> do killServer (ds dts) and I don't like it. I don't like the code repeting. It'd look good with Lips' "when": (define stop-daytime-serve dts (when (stream dts) (kill-server (ss dts))) (when (dgram dts) (kill-server (ds dts)))) Is there a better way to write that on Haskell ? Thanks. -- Pupeno <pupeno(a)pupeno.com> (http://pupeno.com) PS: I have a worse case: -- | Having a 'DaytimeServer', run it according to its specifications. runDaytimeServer :: DaytimeServer -> IO DaytimeServer runDaytimeServer dts = case dts of DaytimeServer {streamPort = Just _, dgramPort = Just _} -> do ss <- runDgramDaytimeServer dts ds <- runStreamDaytimeServer dts return dts{ss = ss, ds = ds} DaytimeServer {streamPort = Just _, dgramPort = Nothing} -> do ss <- runStreamDaytimeServer dts return dts{ss = ss} DaytimeServer {streamPort = Nothing, dgramPort = Just _} -> do ds <- runDgramDaytimeServer dts return dts{ds = ds}

2 1

StringMap
by Christian Maeder 25 Dec '05

25 Dec '05

Hi, could I ask you for efficient StringMap implementations, i.e. based on tries or hash keys? It's mainly for the sake of interest. In the (not too distant) future I'd like to see a library module Data.MapString along the lines of Data.Map and Data.IntMap. So it would be nice (but no requirement) if your implementation could be easily compared to (or exchanged with) the "Data.Map String" instance. (I also still lack a comparison and correctness test infrastructure.) Cheers and Merry Xmas Christian

3 2

kinds question
by David Roundy 25 Dec '05

25 Dec '05

Hello all, I have a question about how to create the right kind to declare lists to be a class. I have a class Foo class Foo f where foo :: f a -> Foo and I want to define that a list of Foos is also a Foo, but can't see how to do it. I imagine something like instance Foo f => Foo [f] where foo xs = map foo xs but of course [f] isn't a valid type. I can define newtype LL f a = LL [f a] instance Foo f => Foo (LL f) where foo (LL xs) = LL (map foo xs) but then I haven't defined anything regarding an actual list. When I try type LL f a = [f a] instance Foo f => Foo (LL f) where foo xs = map foo xs I am informed that LL should have two arguments. Any suggestions? Am I overlooking something obvious? -- David Roundy http://www.darcs.net

2 3

Re: [Haskell-cafe] Haskell vs OCaml
by Donn Cave 24 Dec '05

24 Dec '05

Quoth Tomasz Zielonka <tomasz.zielonka(a)gmail.com>: ... | There are many differences (Haskell on the left): Might also mention foreign (C) function interface (FFI.) ocaml's is I would say average, but ghc's is outstanding, really a different level of support altogether. With regard to the syntax - aside from esthetic questions or awkward notations, there are some practical problems with Objective CAML's common syntax, having to do with optional block delimiters and ";" as a statement concatenator. Sometimes you need to add what seems like gratuitous delimiters to compensate for the kind of unintuitive interpretation. There's a revised syntax that eliminates this problem among other things, but little apparent interest from the community (which figures - they wouldn't be using Objective CAML if this was a high priority for them.) ocaml is nice work, though - very portable compiler that produces native code, and that has helped promote FP in general even if the language isn't all that rigorously functional (mutable strings!?) It seems like it might do very well if it were adopted by basically a new community that would insist on the revised syntax and would make serious use of the OO side of the language, which is kind of interesting. Donn Cave, donn(a)drizzle.com

1 0

zigzag data structure
by Brian McQueen 23 Dec '05

23 Dec '05

I'm curious what this user community would come up with in order to implement the curious zigzag data structure. If you haven't heard anything about it, its a simple but peculiar idea, by the guy who dreamed up the Xanadu project: http://xanadu.com/zigzag/. Conceptually it is "cells" with some sort of value, where each cell has any number of connections to any other cell, but the connections are conceptually labeled/grouped as though they were dimensions. So a cell with the value "Brian McQueen" would have a link to "dorky guy" in the Description dimension, and a link to "519 S. Frances" in the Street Address dimension. Obviously most people would have links in those same dimensions passing through their own name's cell. My cell might have a pointer to "Hector" in the Hero dimension while a conceited man might have a link right back to itself in that same Hero direction. So the structure is very flexible. There are interesting examples on the web site of a Day Planner type of an app where each day has a time line and each time has appointments and the appointments have attendees and they all have personal contact information ... But its all logically linked. I imagine it would be something like this in C-like code: struct cell { value; ptr_to_links }; struct link { { dimension; ptr_to_destination; ptr_to_link; }; struct dimension { name; id; } ; As I write this I realise that I don't remember much, if any, discussion in this group about data structures. I may be starting with a non-functional way of thinking. BTW I'm mostly still at the reading Haskell and fiddling with ghci phase. Brian McQueen

4 5

RE: [Haskell-cafe] Haskell Speed
by Simon Marlow 23 Dec '05

23 Dec '05

On 23 December 2005 19:15, Daniel Carrera wrote: > Hi all, > > I'm taking a look at the "Computer Language Shootout Benchmarks". > > http://shootout.alioth.debian.org/ > > It looks like Haskell doesn't do very well. It seems to be near the > bottom of the pile in most tests. Is this due to the inherent design > of Haskell or is it merely the fact that GHC is young and hasn't had > as much time to optimize as other compilers? GHC? young? We celebrated GHC's 10th birthday a couple of years ago :-) Also, I would like to draw your attention to the fact that GHC wipes the floor with nearly everyone in the concurrency benchmark: http://shootout.alioth.debian.org/benchmark.php?test=message&lang=all Seriously, it's very difficult to draw any meaningful conclusions from these benchmarks. Cheers, Simon

3 2

RE: [Haskell-cafe] Haskell Speed
by Simon Marlow 23 Dec '05

23 Dec '05

On 23 December 2005 20:07, Jeremy Shaw wrote: > Another possible factor is known deficiencies in current IO library > used by most haskell compilers. It is my understanding that the > current IO library was not implemented with speed and efficiency as a > top priority. If someone took the time to optimize/rewrite the current > library code, it might be possible to greatly increase the overall > speed of IO intensive haskell programs with out any changes to the > compilers or language. Not really - the IO library is pretty reasonable, but representing strings as [Char] is holding us back in many of these "benchmarks" significantly. Using the new packed string library will help, though. Cheers, Simon

1 0

Continuations
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, My current setup involves threads that block on a MVar/TMVar until they read an event from it and then proceed. I would like to convert these threads into continuations whereby a continuation is saved when an event is requested and I can call that continuation when an even arrives. I had done this in Lisp before like this: (defun/cc receive (game) (let/cc k ;; save continuation (setf (continuation game) k) ;; TODO: start a timer here )) (defun/cc ask-for-blind (game amount context) (let ((posted nil) (seat nil) (active (car context)) (small-blind-p (= (small-blind$ game) amount))) (while (and (not posted) (car active)) (setf seat (pop active)) ;; skip people who are waiting ;; for the big blind if small blind ;; is being posted. (unless (and (waiting-for-bb-p seat) small-blind-p) (setf (state seat) 'sitting-out) (setf (current game) seat) (send (player seat) 'blind amount) (let* ((cmd (receive game)) <------- note the call to receive here (action (first cmd)) (bet (second cmd)) (inplay$ (inplay$ (player seat)))) ... How would this translate into Haskell and the Cont monad? Alternatively, I would appreciate an example that requests, say, two Ints by saving a continuation each time and returns the sum. Thanks, Joel -- http://wagerlabs.com/

2 4

Optimization help needed
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, These functions together can be taking 15-20% of my processing time. I'm trying to optimize the hell out of them. Would it be less expensive to convert each of them into a foreign function? Is there a way to optimize them further within Haskell? appU_wstr is particularly expensive and deals with reversing the words in a unicode string received little-endian. Thanks, Joel P.S appP_wstr :: Ptr Word8 -> Int -> String -> IO Int appP_wstr ptr ix [] = pickle short ptr ix 0 appP_wstr ptr ix a = do ix1 <- foldM (\ix' c -> pickle endianW16 ptr ix' $ word c) ix a pickle short ptr ix1 0 where word c = fromIntegral $ ord c appU_wstr :: Ptr Word8 -> Int -> IO (String, Int) appU_wstr ptr ix = do (a, ix1) <- unpickle endianW16 ptr ix appU_wstr' ix1 a [] where appU_wstr' ix 0 acc = return $!! (reverse acc, ix) appU_wstr' ix x acc = do (a, ix1) <- unpickle endianW16 ptr ix appU_wstr' ix1 a ((chr $ fromIntegral x):acc) {-# SPECIALIZE swap16 :: Word16 -> Word16 #-} {-# SPECIALIZE swap16 :: Int16 -> Int16 #-} swap16 :: Bits a => a -> a #ifdef BIG_ENDIAN swap16 v = (v `shiftR` 8) .|. (v `shiftL` 8) #else swap16 v = v #endif {-# SPECIALIZE swap32 :: Word32 -> Word32 #-} {-# SPECIALIZE swap32 :: Int32 -> Int32 #-} swap32 :: Bits a => a -> a #ifdef BIG_ENDIAN swap32 v = ( v `shiftR` 24) .|. ((v .&. 0x000000FF) `shiftL` 24) .|. ((v .&. 0x0000FF00) `shiftL` 8) .|. ((v .&. 0x00FF0000) `shiftR` 8) #else swap32 v = v #endif {-# SPECIALIZE swap64 :: Word64 -> Word64 #-} {-# SPECIALIZE swap64 :: Int64 -> Int64 #-} swap64 :: Bits a => a -> a #ifdef BIG_ENDIAN swap64 v = ( v `shiftR` 56) .|. ((v .&. 0x00000000000000FF) `shiftL` 56) .|. ((v .&. 0x00FF000000000000) `shiftR` 40) .|. ((v .&. 0x000000000000FF00) `shiftL` 40) .|. ((v .&. 0x0000FF0000000000) `shiftR` 24) .|. ((v .&. 0x0000000000FF0000) `shiftL` 24) .|. ((v .&. 0x000000FF00000000) `shiftR` 8) .|. ((v .&. 0x00000000FF000000) `shiftL` 8) #else swap64 v = v #endif -- http://wagerlabs.com/

2 2

exuberant-ctags, haskell, vim, tlist plugin
by Marc Weber 23 Dec '05

23 Dec '05

Hi. I'm a happy vim user and enjoyed using the Tlist plugin which shows only the methods and classes described in a file.. But it uses exuberant-ctags to "parse" the files which doesn't support haskell, yet. Has anyone already added haskell support? Is someone else interested? Other solutions perhaps another editor? Here are some screenshots of the tlist plugin for vim: http://www.geocities.com/yegappan/taglist/screenshots.html Marc

4 5

Re: [Haskell-cafe] Substring replacements
by Daniel Fischer 23 Dec '05

23 Dec '05

Hello Bulat, I'm not sure what your point is, let's try to enlighten me. Am Mittwoch, 21. Dezember 2005 16:30 schrieben Sie: > Hello Daniel, > > Wednesday, December 21, 2005, 5:20:18 PM, you wrote: > > DF> ordinarily, on my computer, your version of straightforward is 10-15% > faster DF> than KMP (search-patterns are now supplied on the command line > -- which has DF> no big impact; > > of course. the search pattern can be compiled into the search > algorithm just at the time of program execution. just for example, if > you have code > > main = do [x] <- getArgs > y <- return $ map (\n -> fac $ read x) [1..10^6] > > then `fac $ read x` will be computed just one time. in this time, if > your perform many searches with the same pattern - compiler must > initialize array just one time and use it for all searches > Errrh, what here? If I want to replace each occurence of a pattern within a String, of course I want the arrays built only once, destroying and rebuilding them would be deliberate stupidity, that can't be your point, certainly. And also if we interactively search and replace, as in an editor, we'd hold on to the arrays until we get the message 'no more of that, next pattern'. > > DF> searched string is " able sea..."; all compiled with -O2; > DF> NOINLINE makes no difference -- at least with optimisations on -- > > why? i think that is the right way to check speed of optimized program > without pre-compiling search pattern to search/replace algorithm at > runtime ? What has NOINLINE to do with precompiling the search pattern? BTW, I think, the KMP-algorithm is too large to be inlined anyway (maybe, if we explicitly asked for it), so I wouldn't expect any NOINLINE-effect in the first place. And about RunTimeCompilation, I don't quite understand the Wiki-page, what I imagined might be the point there is that, if I know the search pattern before, I might import the general algorithm, write a function searchReplacePattern = searchReplace "pattern" and the arrays might then be built at compile-time and included in the object code -- but I've no idea whether compilers are clever enough to do that (I believe it should be possible to write compilers which would do that, but is it worth the trouble -- or is that sort of optimisation easy and routinely done?) -- but why that would be called RunTimeCompilation, I cannot imagine. So then, the thing that might make a difference, would be not to give the search pattern at compile-time, which I did. Of course, since we search a long String, the time needed to build the arrays is minute in relation to the time needed to traverse the String, but in the more realistic situation of a shorter String (50 kB instead of 48 MB), it would be significant. > > DF> ; without optimisations, KMP suffers far worse than straightforward). > > this test is meaningless Well, it's not really a test for the algorithm, but for ghc's optimiser and I've forgotten the exact numbers, but KMP compiled without optimisation is much much, much slower than with -O2, so the optimiser does a really great job. > > >> KMP is O(m) while straightforward is O(m*n). > > DF> Where m is the length of the input and n is the length of the > searched-for DF> pattern, I think? > DF> But these are worst-case complexities, I believe, ordinarily, > straightforward DF> will be O(m), too. > > and have longer init time (and take more space), so on typical > searches it will be worser than trivial algorithm I believe you've misread here. I'm saying that while the worst case complexity for the straighforward (or trivial) algorithm is O(n*m) -- as witnessed by my test, which was deliberately designed to be baaaaad for that --, usually, in most real situations, that will have O(m) complexity, too. And I -- like you -- believe that for typical searches the straightforward algorithm will be faster (at least with a clever implementation, like yours). Cheers, Daniel P.S.: I'd really appreciate another attempt at explaining RunTimeCompilation to me (might well be an URL of a paper or something).

1 0

W3C discussion: Principle of Least Power
by Graham Klyne 23 Dec '05

23 Dec '05

There's a possibly-interesting thread running on the W3C TAG mailing list [2] about the "Principle of Least Power" [1], in which Haskell gets a mention. The debate gets kind-of interesting around discussion of analyzability of language expressions vs expressibility, with passing reference to Turing completeness. Intuitively, I've felt that expressions in a pure functional language are easier to analyze than expressions in (say) C or Java, despite them all being fully Turing complete (so no difference in expressive power there). Can it truly be said that it's easier to analyze a functional expression than a C program? What could that actually mean? I feel the discussion is (so far) missing a trick, but I'm not sure what it is. #g -- [1] http://lists.w3.org/Archives/Public/www-tag/2005Dec/0101.html http://lists.w3.org/Archives/Public/www-tag/2005Dec/0113.html http://lists.w3.org/Archives/Public/www-tag/2005Dec/0115.html (etc.) [2] http://web3.w3.org/2001/tag/ http://lists.w3.org/Archives/Public/www-tag/ -- Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

Substring replacements
by Branimir Maksimovic 23 Dec '05

23 Dec '05

I've finally performed test on amd64 and result is a same as on intel. KMP always wins. So KMP is best suited for non indexed strings and I guess should be used in library as prefered search/replace method. This test favors straightforward search. [bmaxa@devel64 myhaskell]$ time ./KMP Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m10.783s user 0m10.769s sys 0m0.016s [bmaxa@devel64 myhaskell]$ time ./straightforward Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m11.769s user 0m11.741s sys 0m0.028s [bmaxa@devel64 myhaskell]$ uname -a Linux devel64.office.kom 2.6.14-skas3-v8.2 #2 Fri Nov 11 21:19:36 CET 2005 x86_64 x86_64 x86_64 GNU/Linux Greetings, Bane. _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

3 8

Vectors in Haskell
by Jeff.Harper＠handheld.com 23 Dec '05

23 Dec '05

Dear Haskell, Most of the time we get along well. But, I'm growing weary of the arguments, fights, and nitpicking when I try to implement new mathematical types and overload your operators. I don't know how to cooperate with your type systems. At moments like this, I think about getting back together with C++. I love you. But, I also love implementing complex numbers, vectors, matrices, and quaternions, and Galois fields. C++ is not nearly as elegant and beautiful as you. But, C++ doesn't complain when I try to do this. Isn't there some way we can work things out so I can implement these types with you? Seriously, I'm trying to implement a vector. I'm starting with vector addition: {- This code is works with Glasgow, ghci, with these options: -fglasgow-exts -fallow-undecidable-instances -fno-monomorphism-restriction -fallow-incoherent-instances -} data Vector a = Vector [a] deriving Show class Add a b c | a b -> c where (.+) :: a -> b -> c instance Add Int Int Int where (.+) x y = x + y instance Add Int Double Double where (.+) x y = (fromIntegral x) + y instance Add Double Int Double where (.+) x y = x + (fromIntegral y) instance Add Double Double Double where (.+) x y = x + y instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) where (.+) (Vector x) (Vector y) = Vector (zipWith (.+) x y) vi1 = Vector [(1::Int)..3] vi2 = Vector [(10::Int),15,2] vd1 = Vector [(1::Double)..3] vd2 = Vector [(10::Double),15,2] test1 = vi1 .+ vi2 test2 = vi1 .+ vd2 test3 = vd1 .+ vi2 test4 = vd1 .+ vd2 v1 = Vector [1,2,3] v2 = Vector [10,15,2] However, it is necessary to explicitly nail down the type of the Vector. v1 and v2 are more general. *Main> :t v1 v1 :: forall a. (Num a) => Vector a *Main> :t v2 v2 :: forall a. (Num a) => Vector a *Main> test2 I'd like for .+ to work with v1 and v2. So, I can use things like Vector [1,2,3] in expressions, instead of Vector[(1::Int),2,3]. However, v1 and v2 do not work with .+ in the code I produced above. Does anyone have any ideas how to make this work? I hoped defining .+ more generally for instances of Num would make my vector addition code work with v1 and v2. My failed attempt involved making the following changes . . . -- I added this instance (Num d) => Add d d d where (.+) x y = x + y -- instance Add Int Int Int where -- (.+) x y = x + y instance Add Int Double Double where (.+) x y = (fromIntegral x) + y instance Add Double Int Double where (.+) x y = x + (fromIntegral y) -- instance Add Double Double Double where -- (.+) x y = x + y When I make these changes and compile, I get the following error messages on the declaration of test1 and test4. . . Vector2.hs:38:12: Overlapping instances for Add (Vector Int) (Vector Int) (Vector Int) arising from use of `.+' at Vector2.hs:38:12-13 Matching instances: Vector2.hs:31:0: instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) Vector2.hs:15:0: instance (Num d) => Add d d d In the definition of `test1': test1 = vi1 .+ vi2 Vector2.hs:41:12: Overlapping instances for Add (Vector Double) (Vector Double) (Vector Double) arising from use of `.+' at Vector2.hs:41:12-13 Matching instances: Vector2.hs:31:0: instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) Vector2.hs:15:0: instance (Num d) => Add d d d In the definition of `test4': test4 = vd1 .+ vd2 I interpret this as saying that the compiler doesn't know if the .+ in "test1 = vi1 .+ vi2" should match the Vector instance or the Num instance. I could understand this if Vector was an instance of class Num. However, this is not the case. I figure either Glasgow has a bug or I don't really understand the error message. I'd be grateful for any suggestions or pointers to information on how to implement vectors (or other mathematical types) so they seamlessly and intuitively work with types, classes and operators already built into Haskell. Or, if someone could point to a more intermediate level book on working with the Haskell type system, that would be great.

6 5

Arrows and pickler combinators
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, I'm trying to monadify the pickler code. sequ below positively looks like >>= but you can't really join both pickle and unpickle into a single monad. I would like to keep the ops together, though, as this allows me a single specification for both pickling and unpickling. Cale suggested that PU is really an arrow in that it supports both input and output. I could not find an example of such an arrow, though. I thought that it could be a "dual arrow" but then could not find a description for one. I would appreciate your suggestions! The original paper is at http:// research.microsoft.com/ ~akenn/fun/picklercombinators.pdf Thanks, Joel P.S. data PU a = PU { appP :: Ptr Word8 -> Int -> a -> IO Int, appU :: Ptr Word8 -> Int -> IO (a, Int), appS :: a -> IO Int } pickle :: PU a -> Ptr Word8 -> Int -> a -> IO Int pickle p ptr ix value = appP p ptr ix value unpickle :: PU a -> Ptr Word8 -> Int -> IO (a, Int) unpickle p ptr ix = appU p ptr ix sizeup :: PU a -> a -> IO Int sizeup p value = appS p value lift :: a -> PU a lift x = PU (\_ ix _ -> return ix) (\_ ix -> return (x, ix)) (\_ -> return 0) sequ :: (b -> a) -> PU a -> (a -> PU b) -> PU b sequ f pa k = PU (\ptr ix b -> do let a = f b pb = k a ix1 <- appP pa ptr ix a appP pb ptr ix1 b) (\ptr ix -> do (a, ix1) <- appU pa ptr ix let pb = k a appU pb ptr ix1) (\b -> do let a = f b pb = k a sz1 <- appS pa a sz2 <- appS pb b return $ sz1 + sz2) pair :: PU a -> PU b -> PU (a,b) pair pa pb = sequ fst pa (\ a -> sequ snd pb (\ b -> lift $! (a, b))) -- http://wagerlabs.com/

3 4

Arrows for invertible programming: Notation question
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, I have been looking at the code for the "Arrows for invertible programming" paper (http://www.cs.ru.nl/A.vanWeelden/bi-arrows/) and I have a question about syntax. ghci surely does not like it. What does this mean and how do I make it compile? mapl{|a, b|arr|} :: (mapl{|a, b|arr|}, ArrowChoice arr, BiArrow arr) => arr a b Thanks, Joel -- http://wagerlabs.com/

3 4

Battling time leaks
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, It looks like I successfully squashed my time leaks and moving my serialization to Ptr Word8 got me as close to the metal as possible. I'm still getting wierd results, though, and they look like a time leak. ORANGE ALERT: 0s, 6s, SrvServerInfo ORANGE ALERT: 0s, 8s, SrvServerInfo ORANGE ALERT: 0s, 9s, SrvServerInfo ORANGE ALERT: 0s, 9s, SrvServerInfo ORANGE ALERT: 0s, 7s, SrvServerInfo unstuff :: Ptr Word8 -> Int -> IO Command unstuff ptr ix = do TOD time1 _ <- getClockTime (kind, ix1) <- unpickle puCmdType ptr ix TOD time2 _ <- getClockTime (cmd', _) <- unpickle (puCommand kind) ptr ix1 TOD time3 _ <- getClockTime when (time3 - time1 > 3) $ -- fail here with the messages above I would like to know where the time is going but how do I troubleshoot something like this? My understanding is that regular profiling will give me the total time spent by cost-center so if I add cost-center annotations it will not give me the average time per run. Come to think about it, the profiling report gives me the # of entries and the total time so I can get the average. Any other suggestions on how to figure out what is going on here? Thanks, Joel -- http://wagerlabs.com/

2 4

Encapsulation in Haskell
by Creighton Hogg 23 Dec '05

23 Dec '05

Hi guys, So one of the big things in object oriented programming is encapsulation, and I'm wondering how to do it properly in Haskell. How do you define new data types but minimize the dependence of external packages on the exact nature of the data definition?

5 4

Type inference for infinite structures
by Matt Collins 23 Dec '05

23 Dec '05

Hi everyone, I'm relatively new to Haskell and was a bit troubled by the problem of assigning a type to infinite structures. To give a clear example, suppose we have data Nat = Zero | Succ Nat omega = Succ omega What type then does omega have? According to GHCi, omega :: Nat. But surely this can only be the case if we already have that omega :: Nat (on the right hand side of the equation)? I can see that the type assignment is valid, but is it necessarily the case? Does it not, somehow, sidestep the inductive base case of the definition of a Nat? Thanks, Matt

2 2

Statements spanning multiple lines?
by Daniel Carrera 22 Dec '05

22 Dec '05

Hi all, How do I write a statement that spans multiple lines? I have this function: pythagoras n = [(a,b,c) | a <-[1..n], b <-[1..n], c <-[1..n], a <= b, b < c, a*a + b*b == c*c] This should all be in one line. I know some ways to make the line shorter, like defining local functions and using 'filter'. But the code would be clearer if I could just make this one statement span several lines. Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

4 6

RE: GHC optimization issue
by Simon Peyton-Jones 22 Dec '05

22 Dec '05

(Brief because I'm at home.) Use INLINE (alone) to include swap at its call sites. (That gives perfect per-call-site specialisation.) Use SPECIALISE (alone) to make a specialised copy of swap, which is then not duplicated at each call site, but instead is called. No need to use them both. The fact that GHC inlines the (big) unspecialised version and not the (apparently smaller) specialised version, is something we should look into. Simon | -----Original Message----- | From: Joel Reymont [mailto:joelr1@gmail.com] | Sent: 22 December 2005 14:09 | To: Haskell-Cafe Cafe | Cc: Simon Peyton-Jones; Simon Marlow | Subject: GHC optimization issue | | Folks, | | I have been trying to improve my byte swapping routines as part of my | effort to speed up serialization. I then tried to look at the core | output from GHC to see what it was converting my code into. Brandon | (skew on #haskell) helped me code a TH version but then I went with a | regular CPP version instead. | | The point of contention is that the logical approach to optimization | does not produce expected results. The only difference between the | following two core outputs is the presence or absence of specialize | and inline pragmas. The code is the same. | | The version without pragmas inlines foo1 into | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) | of ww1_a2eo { __DEFAULT -> | case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of | ww_a2f4 { __DEFAULT -> | GHC.Word.W16# (GHC.Prim.narrow16Word# | (GHC.Prim.plusWord# ww1_a2eo ww_a2f4)) | } | } | | Whereas the version _with_ pragmas produces a function call: | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 Swap1.$w$sswap16 __word 3855 | of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | | Is there a reasonable explanation? | | Both versions compiled thusly: ghc --make Foo.hs -O -ddump-simpl > foo | | Swap: | | {-# OPTIONS_GHC -fglasgow-exts -cpp #-} | module Swap1 | ( | swap16 | ) | where | | import Data.Word | import Data.Int | import Data.Bits | | #define BIG_ENDIAN 1 | | {-# SPECIALIZE swap16 :: Word16 -> Word16 #-} | {-# SPECIALIZE swap16 :: Int16 -> Int16 #-} | {-# INLINE swap16 #-} | | swap16 :: Bits a => a -> a | #ifdef BIG_ENDIAN | swap16 v = (v `shiftR` 8) + ((v .&. 0xFF) `shiftL` 8) | #else | swap16 v = v | #endif | | Foo: | | module Main where | | import Data.Word | import Swap1 | | foo1 :: Word16 | foo1 = swap16 0x0f0f | | main = putStrLn $ show foo1 | | Core output for the version WITH pragmas, see the version w/o pragmas | way below | | ==================== Tidy Core Rules ==================== | "SPEC Swap1.swap16" __forall {$dBits_X1Co :: {Data.Bits.Bits | GHC.Int.Int16}} | Swap1.swap16 @ GHC.Int.Int16 $dBits_X1Co | = Swap1.$sswap16 ; | "SPEC Swap1.swap16" __forall {$dBits_X1Cv :: {Data.Bits.Bits | GHC.Word.Word16}} | Swap1.swap16 @ GHC.Word.Word16 $dBits_X1Cv | = Swap1.$sswap161 ; | | | ==================== Tidy Core ==================== | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 Swap1.$w$sswap16 __word 3855 | of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | | ==================== Tidy Core ==================== | Swap1.$w$sswap16 :: GHC.Prim.Word# -> GHC.Prim.Word# | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.$w$sswap16 = \ (ww_s1I5 :: GHC.Prim.Word#) -> | case GHC.Prim.Word# GHC.Word.$wshift3 ww_s1I5 | (-8) of ww1_a1Gx { __DEFAULT -> | case GHC.Prim.Word# GHC.Word.$wshift3 | (GHC.Prim.and# ww_s1I5 __word 255) 8 | of ww11_a1Hd { __DEFAULT -> | GHC.Prim.narrow16Word# (GHC.Prim.plusWord# | ww1_a1Gx ww11_a1Hd) | } | } | | Swap1.$w$sswap161 :: GHC.Prim.Int# -> GHC.Prim.Int# | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.$w$sswap161 = \ (ww_s1HV :: GHC.Prim.Int#) -> | case GHC.Prim.Int# GHC.Int.$wshift2 ww_s1HV | (-8) of ww1_a1Fk { __DEFAULT -> | case GHC.Prim.Int# GHC.Int.$wshift2 | (GHC.Prim.word2Int# | (GHC.Prim.and# (GHC.Prim.int2Word# ww_s1HV) __word 255)) | 8 | of ww11_a1G5 { __DEFAULT -> | GHC.Prim.narrow16Int# (GHC.Prim.+# ww1_a1Fk | ww11_a1G5) | } | } | | Swap1.$sswap16 :: GHC.Int.Int16 -> GHC.Int.Int16 | [GlobalId] | [Arity 1 | Worker Swap1.$w$sswap161 | NoCafRefs | Str: DmdType U(L)m] | Swap1.$sswap16 = __inline_me (\ (w_s1HT :: GHC.Int.Int16) -> | case GHC.Int.Int16 w_s1HT of w1_X1I5 | { GHC.Int.I16# ww_s1HV -> | case GHC.Int.Int16 Swap1.$w$sswap161 | ww_s1HV of ww1_s1I0 { __DEFAULT -> | GHC.Int.I16# ww1_s1I0 | } | }) | | Swap1.$sswap161 :: GHC.Word.Word16 -> GHC.Word.Word16 | [GlobalId] | [Arity 1 | Worker Swap1.$w$sswap16 | NoCafRefs | Str: DmdType U(L)m] | Swap1.$sswap161 = __inline_me (\ (w_s1I3 :: GHC.Word.Word16) -> | case GHC.Word.Word16 w_s1I3 of | w1_X1Ih { GHC.Word.W16# ww_s1I5 -> | case GHC.Word.Word16 Swap1.$w | $sswap16 ww_s1I5 of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | }) | | Swap1.swap16 :: forall a_a1aQ. (Data.Bits.Bits a_a1aQ) => a_a1aQ -> | a_a1aQ | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.swap16 = __inline_me (\ (@ a_a1dB) | ($dBits_a1ip :: {Data.Bits.Bits | a_a1dB}) -> | let { | $dNum_s1BO :: {GHC.Num.Num a_a1dB} | [Str: DmdType {a1ip->U | (SAAAAAAAAAAAAAAAAA)}] | $dNum_s1BO = Data.Bits.$p1Bits @ | a_a1dB $dBits_a1ip } in | let { | lit_s1BN :: a_a1dB | [Str: DmdType {a1ip->U | (SAAAAAAAAAAAAAAAAA) s1BO->U(AAAAAAAAS)}] | lit_s1BN = GHC.Num.fromInteger @ | a_a1dB $dNum_s1BO (GHC.Num.S# 255) | } in | \ (v_a1aW :: a_a1dB) -> | GHC.Num.+ | @ a_a1dB | $dNum_s1BO | (Data.Bits.shiftR @ a_a1dB | $dBits_a1ip v_a1aW (GHC.Base.I# 8)) | (Data.Bits.shiftL | @ a_a1dB | $dBits_a1ip | (Data.Bits..&. @ a_a1dB | $dBits_a1ip v_a1aW lit_s1BN) | (GHC.Base.I# 8))) | | | Core output without pragmas: | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) | of ww1_a2eo { __DEFAULT -> | case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of | ww_a2f4 { __DEFAULT -> | GHC.Word.W16# (GHC.Prim.narrow16Word# | (GHC.Prim.plusWord# ww1_a2eo ww_a2f4)) | } | } | | --- | Swap1.swap16 :: forall a_a1aQ. (Data.Bits.Bits a_a1aQ) => a_a1aQ -> | a_a1aQ | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.swap16 = \ (@ a_a1dB) ($dBits_a1ip :: {Data.Bits.Bits a_a1dB}) -> | let { | $dNum_s1BK :: {GHC.Num.Num a_a1dB} | [Str: DmdType] | $dNum_s1BK = case {GHC.Num.Num a_a1dB} $dBits_a1ip | of tpl_B1 { Data.Bits.:DBits tpl1_B2 | tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba | tpl10_Bb tpl11_Bc tpl12_Bd tpl13_Be tpl14_Bf tpl15_Bg tpl16_Bh | tpl17_Bi tpl18_Bj -> | tpl1_B2 | } } in | let { | lit_s1BM :: a_a1dB | [Str: DmdType] | lit_s1BM = case a_a1dB $dNum_s1BK | of tpl_B1 { GHC.Num.:DNum tpl1_B2 | tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba -> | tpl9_Ba Swap1.lvl1 | } | } in | \ (v_a1aW :: a_a1dB) -> | tpl3_B4 | (case a_a1dB $dBits_a1ip | of tpl10_Xy { Data.Bits.:DBits tpl11_XB | tpl12_XD tpl13_XF tpl14_XH tpl15_XJ tpl16_XL tpl17_XN tpl18_XP | tpl19_XR tpl20_Bb tpl21_Bc tpl22_Bd tpl23_Be tpl24_Bf tpl25_Bg | tpl26_Bh tpl27_Bi tpl28_Bj -> | tpl26_Bh v_a1aW Swap1.lvl | }) | (case a_a1dB $dBits_a1ip | of tpl10_Xy { Data.Bits.:DBits tpl11_XB | tpl12_XD tpl13_XF tpl14_XH tpl15_XJ tpl16_XL tpl17_XN tpl18_XP | tpl19_XR tpl20_Bb tpl21_Bc tpl22_Bd tpl23_Be tpl24_Bf tpl25_Bg | tpl26_Bh tpl27_Bi tpl28_Bj -> | tpl25_Bg (tpl12_XD v_a1aW lit_s1BM) Swap1.lvl | }) | | -- | http://wagerlabs.com/ | | | |

2 1

ANN: HDBC 0.6.0
by John Goerzen 22 Dec '05

22 Dec '05

Hello, Version 0.6.0 of HDBC and the Sqlite3 bindings are now available. New features since Tuesday's 0.5.0 announcement include: * New type system for marshalling different Haskell types back and forth * New support for querying meta-information about the server * Much improved documentation * Fix for a race condition in the Sqlite3 binding * New fetchAllRows function that returns a lazy list of result rows (think hGetContents for database queries) I will shortly begin work on a PostgreSQL binding. Also, I plan to write a MissingH interface module. The main idea of that is to provide a SQL backend for the MissingH AnyDBM interface (which uses *dbm databases for persistent hashes). Combined with Sqlite, this provides a very interesting and easy to use persistent hash interface. -- John

1 0

FAQ: Why no interactive definitions?
by Greg Woodhouse 22 Dec '05

22 Dec '05

In neither GHCi nor Hugs (so far as I know) is it possible to interactively enter definitions. coming from Scheme, this was a bit of a surprise, as I'm used to being able to enter, say (define mysquare (lambda (x) (* x x))) Is this just a matter of the feature not being implemented, or is there a deeper reason for this? === Gregory Woodhouse <gregory.woodhouse(a)sbcglobal.net> "Interaction is the mind-body problem of computing." --Philip L. Wadler

3 2

Re: GHC Optimization Issue
by Brandon Moore 22 Dec '05

22 Dec '05

I think what's happening here is that the rewrite rule SPECIALIZE is producing turns the call to swap16 into a call to the specialized verision before any inlining happens[1], and then the specialized version can't be inlined[2]. Manually writing out a copy of swap16 at type Word16 -> Word16, marking it INLINE and setting up a rewite rule for specialization gives you the more efficient code: changing the definition to swap16 to this: swap16 :: Bits a => a -> a swap16 v = (v `shiftR` 8) + ((v .&. 0xFF) `shiftL` 8) {- # RULES "swap16/Word16" forall (v :: Int16) . swap16 v = swap16Word16 v #-} {- # INLINE swap16Word16 #-} swap16Word16 :: Word16 -> Word16 swap16Word16 v = (v `shiftR` 8) + ((v .&. 0xFF) `shiftL` 8) gives this Core for foo: Main.foo :: GHC.Word.Word16 [GlobalId] [Str: DmdType] Main.foo = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) of ww1 { __DEFAULT -> case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of ww { __DEFAULT -> GHC.Word.W16# (GHC.Prim.narrow16Word# (GHC.Prim.plusWord# ww1 ww)) } } and for swapWord16: Swap.swap16Word16 :: GHC.Word.Word16 -> GHC.Word.Word16 [GlobalId] [Arity 1 NoCafRefs Str: DmdType U(L)m] Swap.swap16Word16 = __inline_me (\ (v :: GHC.Word.Word16) -> GHC.Word.+2 (GHC.Word.$dmshiftR2 v (GHC.Base.I# 8)) (GHC.Word.shift2 (GHC.Word..&.2 v Swap.lit) (GHC.Base.I# 8))) Removing the INLINE directive for swap16Word16 leaves this code for foo, with a call to the worker function for swap16Word16: Main.foo :: GHC.Word.Word16 [GlobalId] [Str: DmdType] Main.foo = case GHC.Word.Word16 Swap.$wswap16Word16 __word 3855 of ww1 { __DEFAULT -> GHC.Word.W16# ww1 } and these definitions for swap16Word16: Swap.$wswap16Word16 :: GHC.Prim.Word# -> GHC.Prim.Word# [GlobalId] [Arity 1 NoCafRefs Str: DmdType L] Swap.$wswap16Word16 = \ (ww :: GHC.Prim.Word#) -> case GHC.Prim.Word# GHC.Word.$wshift3 ww (-8) of ww1 { __DEFAULT -> case GHC.Prim.Word# GHC.Word.$wshift3 (GHC.Prim.and# ww __word 255) 8 of ww11 { __DEFAULT -> GHC.Prim.narrow16Word# (GHC.Prim.plusWord# ww1 ww11) } } Swap.swap16Word16 :: GHC.Word.Word16 -> GHC.Word.Word16 [GlobalId] [Arity 1 Worker Swap.$wswap16Word16 NoCafRefs Str: DmdType U(L)m] Swap.swap16Word16 = __inline_me (\ (w :: GHC.Word.Word16) -> case GHC.Word.Word16 w of w1 { GHC.Word.W16# ww -> case GHC.Word.Word16 Swap.$wswap16Word16 ww of ww1 { __DEFAULT -> GHC.Word.W16# ww1 } }) It looks like marking the function INLINE supresses the worker/wrapper split, and when there is not INLINE and the function get split, only the wrapper is eligible for inlining. Brandon Moore [1] (section 10.7.2 of the 6.4.1 User's guide says "In the earlier phases of compilation, GHC inlines nothing that appears on the LHS of a rule, because once you have substituted for something you can't match against it (given the simple minded matching).") [2] Maybe because the worker isn't annotation with __inline_me in the Core? Maybe from the aside in 7.10.5 about and INLINE pragma preventing any inlining in the RHS of the thing marked inline?

1 0

Re: [Haskell-cafe] Functions with side-effects?
by Wolfgang Jeltsch 22 Dec '05

22 Dec '05

Am Donnerstag, 22. Dezember 2005 03:32 schrieb Gregory Woodhouse: > [...] > If this analogy is at all valid, then I wonder if the IO monad, at > least, doesn't represent something of a blurring of the traditional > distinction between applications and operating system functionality. An application can modify local state, e.g., a C variable. Purely functional code cannot do this. > Incidentally, devices do not necessarily correspond to hardware and > you can write drivers to do all sorts of interesting things if you > are so inclined -- just as monads are not limited in their use to I/O. The IO monad is not just about I/O but also about modifiable variables. Most other monads only deal with purely functional stuff. For example, a list has nothing to do with modifiable variables and I/O at all. > > We have a "evaluation machine" and a "execution machine". The former > > evaluates expressions, the latter executes I/O actions. > > This is where I'm a bit fuzzy. "Actions" make think of something like > a finite automaton, where the action would be (possibly) consuming an > input token and changing state. "Actions" makes me think of things like I/O and modifying variables in contrast to calculations which don't really "act". Of course, an I/O action, for example, modifies a state, namely the state of the outside world. > > When the program is started, the execution machine wants to execute the > > actions from the "main to do list". In order to be able to do so, it asks > > the evaluation machine to start evaluating main. For each entry on the to > > do list, main is evaluated as far as it's necessary to provide the > > execution machine with the entry. Of course, evaluating main may result > > in evaluating other expressions. > > I imagine this is somewhat analogous to a C statement like > > c = getchar(); > > Evaluation is "blocked" (and the process becomes not runnable) until > such a time as getchar() returns a value. If there is no buffered > input, a system call will be required, and control will pass to the > driver for the appropriate device. When control returns to the > calling process it can, of course, go on until it again > (transparently) blocks, waiting for input or other actions. I meant it the other way round. The execution machine does something like the following: while (actionsRemaining()) { nextAction = getNextAction(); executeAction(nextAction); } getNextAction() will force the evaluation machine to evaluate as much of main as is needed to provide the execution machine with the next action. > > The point is that the evaluation machine does never execute any I/O > > actions while the execution machine is unable to do any evaluation but > > needs to be feeded by the evaluation machine. > > Is this a reasonable analogy? I think so. :-) > [...] Best wishes, Wolfgang

1 0