- Haskell-Cafe - Haskell.org

22 Aug '07

for sake of argument, suppose an enterprising haskell newbie wanted to code up concurrent b-trees (really b-link trees) in haskell. if i am understanding STM correctly, it will NOT help in any way with the implementation, because of the IO-intensive nature of the algorithms? so i will have to resort to the usual games with locks and latches? (using Ibrahim Jaluta, Seppo Sippu and Eljas Soisalon-Soininen. Concurrency control and recovery for balanced B-link trees. The VLDB Journal, Volume 14, Issue 2 (April 2005), Pages: 257 - 277, ISSN:1066-8888. as a source for b-tree algorithms.) take care, B

3 2

I'm stuck in my thought experiment
by Levi Stephen 22 Aug '07

22 Aug '07

Hi, Apologies for a long post that may not be totally clear. I was thinking through a problem and how the data might be represented in Haskell. I'm now stuck and frustrated. Now, I'm not even sure whether I'm on the right track (I might still be thinking too OO). Suggestions/ideas would be much appreciated. I was imagining a drag and drop web page designer. There are a bunch of Widgets (e.g., BlogWidget, TextWidget, MenuWidget, etc) that the user can place on the page. Along with these are layout/container widgets (e.g., ColumnLayoutWidget) that can contain other widgets. I'm looking at a data structure that would allow this to be represented in Haskell, so I'm keeping in mind that these won't be written in code, but generated on the fly somehow (e.g., from a database or file). So, my thoughts were along the lines of something like: class Widget a where render :: a -> Html -- A page has a title and a Widget. -- I know this isn't valid Haskell, but I'm not sure how to specify what I -- want here. (existential types?) data Page = Page String Widget data TextWidget = TextWidget String instance Widget TextWidget .... -- An example layout widget data ColumnLayoutWidget = ColumnLayoutWidget [Widget] instance Widget ColumnLayoutWidget ... etc... So, entire pages might be represented something like: Page "Main" (ColumnLayoutWidget [MenuWidget, TextWidget mainPageText]) Page "About" (ColumnLayoutWidget [MenuWidget, TextWidget aboutPageText]) Where I get stuck, is I want to extract layout information into a parent page. This would allow global changes such as adding a header image to the above pages to be done once only. So I want to be able to have something like: layout = Page "Main" (ColumnLayoutWidget [MenuWidget, ??? ]) mainPage = ChildPage layout [TextWidget mainPageText] aboutPage = ChildPage layout [TextWidget aboutPageText] So, each page is it's layout/parent page, with additional widgets inserted/added. The issue becomes, given a parent page and the customized content for the child page, what is the best way to insert the customized content at the right point? Might a tree like structure be useful? But, how do you work out where in the tree child content gets added? Store a traversal with each sub tree of child page content that basically says 'insert here'? It might be simple to have a PlaceHolderWidget. Then insertions of the child page content happens at each of those widgets. This just gets trickier if I start considering multiple extension points for child pages and what happens when the layout/parent page changes. This is why I'm thinking I may be going along a bad path here. Thanks, Levi lstephen.wordpress.com

3 5

Re: [Haskell-cafe] STM, IO and b-trees
by Thomas Conway 22 Aug '07

22 Aug '07

On 8/21/07, Ben <midfield(a)gmail.com> wrote: > some basic questions: you have limits on key and value size? fixed > page sizes per tree? I have chosen Yes and Yes respectively, though these are *choices*. Personally, I think fixed sized pages are fine. Handling unlimited sized keys is not hard, especially if you think they will be rare: you use a bit to flag an immediate key vs a remote key, and keep an overflow file for long keys. Another idea that I've had, though I have not had the opportunity to implement it is to use arithmetic coding on the keys. If you carve up the zero-to-one interval in sorted order, then the arithmetic coded bitstrings sort (lexicographically) in the same order as the uncompressed strings. From the top of my head, most *english* words can compress in this fashion with a 0 order model to about 2-3 bits per character. This doesn't eliminate a key length by itself, but it should increase the limit dramatically in practice. My implementation uses 64K pages, with a limit of 32K - 8 bytes on the size of an individual key. > on point 2: it sounds like you'r suggesting using STM after all. not > sure if i understand what you've said: something like type PagePtr t = TVar (Address, Maybe t) data Node = Node (PagePtr Node) [(Key,PagePtr Node)] | Leaf [(Key,Data)] > work with a page cache. do the various b-tree algorithms in STM > transactions on the cached pages. retry STM transactions when pages > aren't loaded. on successful STM transaction completion, write out the > dirty pages. Yes, except you might want to be clever about flushing dirty pages more lazily. My implementation isn't crash-proof (i.e. doesn't support crash recovery - the environment in which my code operated means that if something bad happens, I can rebuild from external data). > probably use the trick where the STM transaction returns > an IO action which you then perform. probably use ordinary page-level > locks to deal with concurrency on IO -- STM doesn't help. Maybe. See the SPJ video on STM. His basic point is that STM helps get rid of the stupid concurrency bugs, leaving just the "more interesting" ones for you to deal with. :-) Actually, using relaxed balance and making all the tree updates local, means that my btree code successfully supports a very high degree of concurrency. > as far as implementing the page cache: using a TVar Map would > essentially be creating a global lock on the entire cache. Exactly, which is why you want to push the TVars down. > so you > suggest using other implementations. your suggestion sounds like an > array with linear search, or probably something more sophisticated. i > would imagine a balanced binary tree where the nodes are TVars might > work nice, though rebalacing would touch a lot of nodes. (it does > seem strange haskell doesn't have more concurrent data structures.) Yes, I've chatted with Andrew Bromage about the need for Data.Map.Concurrent Data.Set.Concurrent etc. I have a concurrent hash table which works very nicely. Think class Hashable t where hash :: t -> Word64 type HashTable k v = TArray Word64 [(k,v)] Another alternative that others have suggested are Tries (radix trees). Something along the lines: type Trie v = .... insert :: [Bit] -> v -> Trie v -> STM () > on point 1: you're saying relaxed balance is better for STM-style > optimistic transactions? i'm using > > B-Trees with Relaxed Balance (1993) > Kim S. Larsen, Rolf Fagerberg > IPPS: 9th International Parallel Processing Symposium Yes. There's a tech report version which includes details of deletion which IIRC the one you mention does not. citeseer... google.... The reason I believe relaxed balance works particularly well with STM is that all the operations (insert, delete, rebalance) operate *locally*. That is, they only modify a single node or a couple of proximate nodes. In STM terms, this means a given operation only *writes* a couple of TVars close to where the operation took place. One of the cool things is that Larsen et al prove that as you progress up the tree the number of rebalancing operations drops geometrically. Effectively, this means you very rarely need to get a write-lock on the root (or top few nodes) of the tree, so randomly dispersed operations are unlikely to conflict with one another. Also, by separating the insert/delete bits from the rebalance bits, both are simpler to code, and you have fewer edge cases to think about. cheers, T -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

2 1

ANN: SF Bay Area Functional Programmers Group
by Keith Fahlgren 21 Aug '07

21 Aug '07

Hi All, I'd like to announce the formation of the Bay Area Functional Programmers group. This group is for anyone using or interested in functional programming and functional programming languages, particularly strongly typed languages such as Haskell, OCaml, SML, etc. The first meeting will be Thursday, September 13th at 7:30pm somewhere in San Francisco. Please join the mailing list at http://groups.google.com/group/bayfp and suggest a location. The initial meeting will be a casual pizza and beer get together, although going forward we'd like to also include speakers, reading and discussion of technical papers, and some hands on coding. Future announcements and the location of the first meeting will be posted to the BayFP mailing list. More information will be available on the website: http://bayfp.org/. Keith (+ Mike Wells)

1 0

"Tying the knot" with unknown keys
by David Ritchie MacIver 21 Aug '07

21 Aug '07

I was playing with some code for compiling regular expressions to finite state machines and I ran into the following problem. I've solved it, but I'm not terribly happy with my solution and was wondering if someone could come up with a better one. :-) Essentially I have data FSM = State { transitions :: (Map Char FSM) } and transitions' :: Regexp -> Map Char Regexp I want to lift this so that the Regexps become states of the finite state machine (while making sure I set up a loop in the data structure). Tying the knot is the traditional way of doing such things, but we couldn't figure out a way to make it work without the set of keys known in advance because of the strictness of Map in its keys (an association list was suggested, and that would probably work, but it seemed a bit ugly and would be fairly inefficient). In the end what I did was just work out the set of reachable regexps in advance and use a standard tying the knot trick, but it felt vaguely unsatisfactory (and does some repeat work which I felt should be unneccessary). Anyone have a more elegant suggestion? Regards, David

6 7

can't build haxml under ghc 6.7, says HughesPJ is hidden... but ghc-pkg doesn't say it's hidden...
by Thomas Hartman 21 Aug '07

21 Aug '07

Can I get some help building HaXml (from hackage) under ghc 6.7? I'm hoping to get HAppS running under 6.7, and use the new debugger to better understand what's going on under the hood. Eg, when I'm in the h function, I can take a look at the args and just see what types they are. (I am finding building an intuition from the documentation alone to be overwhelming. Too many types, too many instances... total confusion.) HaXMl is a dependendency for happs, that's why I need it. Anyway building haxml this is what I get. The subject of my message more or less summarizes my confusion. hartthoma@linuxpt:~/installs/HaXml-1.13.2>runghc Setup.hs build Setup.hs: Warning: The field "hs-source-dir" is deprecated, please use hs-source-dirs. Preprocessing library HaXml-1.13.2... Preprocessing executables for HaXml-1.13.2... Building HaXml-1.13.2... src/Text/XML/HaXml.hs:30:7: Could not find module `Text.PrettyPrint.HughesPJ': it is a member of package pretty-1.0, which is hidden hartthoma@linuxpt:~/installs/HaXml-1.13.2>ghc-pkg list /usr/local/lib/ghc-6.7.20070719/package.conf: Cabal-1.1.7, base-2.1, directory-1.0, filepath-1.0, ghc-6.7.20070719, haskell98-1.0, hpc-0.5, old-locale-1.0, old-time-1.0, pretty-1.0, process-1.0, random-1.0, readline-1.0, rts-1.0, template-haskell-0.1, unix-2.0 hartthoma@linuxpt:~/installs/HaXml-1.13.2>ghc-pkg list pretty-1.0 /usr/local/lib/ghc-6.7.20070719/package.conf: pretty-1.0 hartthoma@linuxpt:~/installs/HaXml-1.13.2>ghc --version The Glorious Glasgow Haskell Compilation System, version 6.7.20070719 hartthoma@linuxpt:~/installs/HaXml-1.13.2>ghc-pkg describe pretty-1.0 name: pretty version: 1.0 license: BSD3 copyright: maintainer: libraries(a)haskell.org stability: homepage: package-url: description: This package contains a pretty-printing library. category: author: exposed: True exposed-modules: Text.PrettyPrint Text.PrettyPrint.HughesPJ hidden-modules: import-dirs: $topdir/lib/pretty-1.0 library-dirs: $topdir/lib/pretty-1.0 hs-libraries: HSpretty-1.0 extra-libraries: extra-ghci-libraries: include-dirs: $topdir/lib/pretty-1.0/include includes: depends: base-2.1 hugs-options: cc-options: ld-options: framework-dirs: frameworks: haddock-interfaces: $topdir/share/ghc/doc/html/pretty/pretty.haddock haddock-html: $topdir/share/ghc/doc/html/pretty hartthoma@linuxpt:~/installs/HaXml-1.13.2> hartthoma@linuxpt:~/ProjectRepos/miscAdmin>ghc-pkg list /usr/local/lib/ghc-6.7.20070719/package.conf: Cabal-1.1.7, base-2.1, directory-1.0, filepath-1.0, ghc-6.7.20070719, haskell98-1.0, hpc-0.5, old-locale-1.0, old-time-1.0, pretty-1.0, process-1.0, random-1.0, readline-1.0, rts-1.0, template-haskell-0.1, unix-2.0 --- 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.

4 5

Re: [Haskell-cafe] How can I pass IOUArrays to FFI functions?
by Ryan Ingram 21 Aug '07

21 Aug '07

Thanks to everyone, especially Bulat Ziganshin. In http://haskell.org/haskellwiki/Modern_array_libraries there is enough information to do what I want. It specifically mentions that it's OK to pass ByteArray# and MutableByteArray# to an "unsafe foreign" procedure as long as that procedure doesn't save the pointer, and that worked for me. Here is what I ended up using, which worked great and the FFI usage for a couple of key functions sped up my code by a large factor: import Data.Array.Base import Data.Array.IO.Internals import GHC.Exts {-# INLINE unsafeByteArrayToPtr #-} unsafeByteArrayToPtr :: IOUArray Int Word32 -> Ptr Word32 unsafeByteArrayToPtr (IOUArray (STUArray _ _ array#)) = Ptr (unsafeCoerce# array#) Possibly a better thing to do would be to declare that the call takes a MutableByteArray# directly in the foreign import statement, which I believe would let me avoid using unsafeCoerce# at all, but this was good enough for my purposes. Afterwards I used -ddump-simpl to check on the generated Core for the foreign call and it looked good. -- ryan

4 8

is there a way to patch the build-depends line of a cabal file without breaking backwards compatibility?
by Thomas Hartman 21 Aug '07

21 Aug '07

cafe, is there a way to patch the build-depends line of a cabal file without breaking backwards compatibility? I just patched HDBC head to compile under ghc 6.7. Unfortunately it now won't compile in 6.6.1. is there a way for build-depends to detect which version of ghc you're on? also I seem to recall that -fglasgow-exts was deprecated under 6.7. is there a better way to beat back the error message below than this? thanks, thomas. { hunk ./Database/HDBC/Statement.hs 1 +{-# LANGUAGE TypeSynonymInstances #-} hunk ./Database/HDBC/Types.hs 1 +{-# OPTIONS_GHC -fglasgow-exts #-} +{- +-- without -fglasgow-exts you get: [_$_] +Database/HDBC/Types.hs:202:0: + Illegal polymorphic or qualified type: forall conn. + (IConnection conn) => + conn -> b + In the type signature for `withWConn': + withWConn :: forall b. + ConnWrapper -> (forall conn. (IConnection conn) => conn -> b) -> b +-} hunk ./HDBC.cabal 13 -Build-Depends: base, mtl + +Build-Depends: base, mtl, old-time, bytestring, containers +-- breaks backwards compability with ghc 6.6.1 + } --- 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.

3 4

How can I pass IOUArrays to FFI functions?
by Ryan Ingram 21 Aug '07

21 Aug '07

I have a C function of type void f ( HsWord32* p0, HsWord32* p1, HsWord32 size ); along with the FFI declaration: foreign import ccall unsafe f :: Ptr Word32 -> Ptr Word32 -> Word32 -> IO () In my Haskell code I have an unboxed IO array of Word32; IOUArray Int Word32. I want to pass the pointer to this array to f(). How can I get the pointer out of the array? Or, is there a better way to declare f() to do this? I'm open to using GHC hackery; using v6.6.1 right now. -- ryan

4 3

Diagnosing stack overflow
by Justin Bailey 20 Aug '07

20 Aug '07

I am trying to determine why my stack overflows in my medium sized program (it has several modules but maybe only 1000 LOC total). On Windows, at least, the ghcprof visualization tool doesn't work. Any suggestions besides an output trace? It may be the function below, which tries to determine if a list of strict bytestrings is longer than the count given. I have tried to make it strict but am not sure if it's too lazy. Any hints are appreciated. -- Determines if the length of the strings in the list is longer than the given -- count. If not, amount the list falls short is returned. Otherwise, -- -1 indicates the prefix list is at least that long. If the count is zero and -- the list is empty or just null strings, -1 is also returned. prefixesAtLeast :: Int -> [S.ByteString] -> Int prefixesAtLeast !0 !ss | null ss = 0 | all S.null ss = 0 | otherwise = -1 prefixesAtLeast !n !ss = prefixesAtLeast' n ss where prefixesAtLeast' !n ss | n < 0 = -1 | null ss = n | otherwise = let (!s : (!rest)) = ss in prefixesAtLeast' (n - (S.length s)) rest

5 10