November 2007 - Haskell-Cafe

Leopard: ghc 6.8.1 and the case of the missing _environ
by Joel Reymont 04 Dec '07

04 Dec '07

Symptoms: You build 6.8.1 from source on Leopard (x86 in my case) and then junior:ghc-6.8.1 joelr$ ghci GHCi, version 6.8.1: http://www.haskell.org/ghc/ :? for help ghc-6.8.1: /usr/local/lib/ghc-6.8.1/lib/base-3.0.0.0/HSbase-3.0.0.0.o: unknown symbol `_environ' Loading package base ... linking ... ghc-6.8.1: unable to load package `base' Problem: ghc binaries are being stripped upon installation which eliminates _environ, e.g. junior:tmp joelr$ nm x|grep environ 00002ff0 T ___hscore_environ 0004d004 D _environ junior:tmp joelr$ strip x junior:tmp joelr$ nm x|grep environ Solution: Need to make sure install-sh does _not_ use the -s option. Haven't found out where this needs to be done yet. A temporary workaround is to ask Manuel for the pre-built binaries. Thanks, Joel -- http://wagerlabs.com

2 1

A tale of three shootout entries
by Sterling Clover 03 Dec '07

03 Dec '07

In some spare time over the holidays I cooked up three shootout entries, for Fasta, the Meteor Contest, and Reverse Complement. I should probably have tossed them to haskell-cafe before submission, for review and ideas, but they're up now. In any case, all three were great learning experiences, but could use some other eyes and ideas to be the best that they can. First up is the meteor-contest entry. http://shootout.alioth.debian.org/gp4/benchmark.php? test=meteor&lang=ghc&id=5 This is the clear win of the bunch, with significantly improved time thanks to its translation of the better algorithm from Clean. However, it's still missing something. Nearly all its time is spent in a tight loop in the solveCell function near the end of the code. I tried unboxing this, but failed because it spends the bulk of its time applying a bitwise and between the recursively passed value and a piece of data retrieved from the masksAtCell data structure which is of type :: Array (Row,Col) (Array Color [Mask]). (Note that Mask, Color, Row and Col are all type synonyms for Int that I added for readability). As each Mask is stored in this list, the masks can't easily be unboxed -- some sort of custom data structure built using the FFI seems in order here. If anyone wants to tackle this, I think it could be a big win for performance. Next is reverse-complement. http://shootout.alioth.debian.org/gp4/benchmark.php? test=revcomp&lang=ghc&id=3 This *would* be a big win except I dimly doubled memory usage from the previous entry due to filtering newlines explicitly -- which does, one should note, provide a large performance gain. The solution here seems the most obvious -- roll the newline stripping into the destructive modifications performed in the revcomp function, as the winning C++ entry does. I'll probably get around to this eventually, but if someone else wants to try to implement this or any other performance improvements, please jump right in. Additionally, there might be some other tricks to reducing its memory usage that escape me at the moment (noting, of course, that using a strict bytestring, as we should, its unavoidable that we consume the entire contents of the input at once... I think?) Finally, there's fasta. http://shootout.alioth.debian.org/gp4/benchmark.php? test=fasta&lang=ghc&id=2 This one really depresses me. It outperforms the previous version by roughly 20% on my machine (PPC) but underperforms by roughly the same amount on the shootout box. If you compare it to dons previous version, the "optimizations" I attempted should be pretty obvious. First, I precompute the partial sums for the frequency tables and alter the choose function accordingly. This is a pretty basic measure that all the better entries seem to do. Next, I unboxed the random function, which yielded big speedups However, given that we use an unfoldN, as we should, I couldn't very well pass it a function that returned something of kind #, (especially as Maybe, which unfoldN uses, is of kind *->*). Thus, I hid the unrolled loop in a lazy list of floats that is passed instead of a random seed. I suspect that for some reason I don't understand relating to differences in processors, GHC's internal handling of floating point math, or who knows what, this somehow is the source of the slowdown. If someone with an Intel Pentium 4 machine comparable to that of the shootout box wants to take a look at this code and see why it underperforms, I'd be much obliged. It really seems to me that GHC's fasta performance is far below where it should be (4x slower than Java!) , and I'd like to get its numbers up somehow. Thanks, Sterl p.s. It looks like they've depreciated chameneos in favor of a new version, chameneos-redux. As this was one of the places Haskell really rocked the competition, it would probably be worth updating the Haskell entry for the new benchmark. Also, the n-bodies benchmark seems like another that could be much improved.

8 18

Optimizing cellular automata evaluation (round 2)
by Justin Bailey 03 Dec '07

03 Dec '07

I posted awhile back asking for help improving my cellular automata program. I am competing with a C program which evolves CAs using a fairly simple genetic algorithm. The algorithm involves evaluating 100 rules on 100 CAs, 100 times. In C this takes about 1 second. In my Haskell version, it takes about 20 minutes. That's an improvement from my first attempts, which took 7 hours. All the time is spent in the function that evaluates one iteration of a given CA. It examines each cell and its neighbors and, based on the values found, updates the cell to be white or black. Here is the code, followed by an explanation of what it's doing. I'm looking for any suggestions on making this faster. Prettier helps too but not at the expense of speed. http://hpaste.org/4151#a0 I represent the automata as an array of integers, where each bit represents a cell. Automata 'wrap' around, so marching through the array and determing the value of all neighbors is tricky around the edges. My goal was to minimize conditionals as much as possible and to avoid any "modulo" arithmetic. I wanted to use straightforward array access. My implemention uses three functions: fill, fillS and fillE. Each evalutaion of fill will determine the new values for cells represented by the current array element. fill handles two conditions - when the array element being examined is the last element or when it is not. It calls fillS with appropriate arguments, the results of which become the value for the integer in the current array position. fillS then handles two conditions - when the "neighborhood" of the bit being examined crosses to the "next" array element and when it does not. When the "neighborhood" crosses to the next array element, fillE is called. fillE finishes determining the values for the remaining cells in the integer and returns, ending the current evaluation. There are some other details in the code (for example firstRule) which could be made faster and/or cleaner, but their contribution is far outweighed by the fill function. If there is one thing I'm happy about, its the memory performance of this code. It runs in a constant 7 - 10MB of memory, even when I'm doing 100 generations with 100 rules and 100 CAs. Each CA is evaluated for 250 steps, which means every generation does 2.5M steps. That kind of memory usage is pretty sweet. Thanks in advance to those willing to take the time to look at this code! Justin

7 8

doing builds using cygwin on Windows ....help
by Galchin Vasili 03 Dec '07

03 Dec '07

Hello, I have suceeded in doing a build on top of cygwin. However, after editing some of the cygwin "bashrc" files, teh darcs path and haddock path still don't show up when I do a "echo $PATH". I am now reading http://cygwin.com/cygwin-ug-net/setup-env.html. "The PATH environment variable is used by Cygwin applications as a list of directories to search for executable files to run. This environment variable is converted from Windows format (e.g. C:\WinNT\system32;C:\WinNT) to UNIX format (e.g., /WinNT/system32:/WinNT) when a Cygwin process first starts. Set it so that it contains at least the x:\cygwin\bin directory where " x:\cygwin is the "root" of your cygwin installation if you wish to use cygwin tools outside of bash. " .. however, I don't see in which file PATH can be set. Any help? I really want to get my Haskell build environment set up and cranking away. Kind regards, Vasya

2 1

Re: Haskell-Cafe Digest, Vol 51, Issue 180
by manu 02 Dec '07

02 Dec '07

>> >> I'm trying to build diverse packages from Hackage with ghc 6.8.1, >> they usually fail to build because of missing language extensions. >> >> Sometimes I am unable to determine the proper name of the extension >> missing in .cabal >> I tend to slap {- #OPTIONS -fglasgow-exts #-} at the top of the >> troublesome file. >> It works, but out of curiosity, what is the downside of such an >> approach ? (bigger executables ?) > > Can you list which packages failed to build out of the box? > > -- Don > Well I'd say none of the packages I've tried, build out of the box, that include : haskelldb haskelldb-hdbc haskelldb-hdbc-sqlite3 HDBC HDBC-sqlite3 Agreed some of these compile right after tweeking the build-depends: and extensions: lines in the .cabal file (apart from the pesky PatternSignatures which require a LANGUAGE pragma in the source file) haskelldb-hdbc-sqlite3 is the one that I couldn't get past... I didn't bother with hsql-mysql-1.7 since Duncan Coutts mentioned it required significant work (and I cannot do much) Manu

6 6

fast Array operations: foldl, drop
by Henning Thielemann 02 Dec '07

02 Dec '07

I thought operations like "foldl'" and "drop" must be very fast on arrays (especially UArray) with appropriate pointer tricks, I mean pointer incrementing instead of indexing for "foldl'" and a pointer into the array for "drop". Is it planned to add such functions? Ok, if "foldl f x . elems" and "listArray (i,sufficientlyBig) . drop n . elems" are fused to high speed code, then these functions do not need to materialize in the API.

8 11

Categories list in French (off-topic?)
by Maurício 01 Dec '07

01 Dec '07

Hi, I'm learning about categories using Saunders Mac Lane book. I'm also learning French. Do you guys know of a nice French mailing list, or forum, where people discuss about categories (and where beginners are accepted)? Sorry to ask that in a Haskell list, but you guys are the ones I know with interest in category theory. Thanks, Maurício

3 3

Design of a Physics Interface
by Luke Palmer 01 Dec '07

01 Dec '07

I'm currently working on idioms for game programming using FRP. After going through several representations of physics as arrows[1] I decided that physics objects must not be implemented as arrows, because introducing new arrows in the middle of a computation[2] leads to ugly pain. So far the best approach I have is to represent the physics world as a single object World, with a function > integrate :: TimeStep -> World -> World But I can't figure out a good way to represent bodies in this world. I considered: > newBody :: (Position,Velocity) -> World -> (Body,World) Where Body is an ADT with an internal representation of an Integer or something. The problem with this is that (1) there is no way to guarantee that a Body actually exists in a World (which is a minor but still annoying issue), and (2) that there's a possibility that you could make a Body in one world and use it in another and there would be no way to detect the error. (2) could be solved using an internal representation of Data.Unique, but (1) still remains a problem. And as long as the function > deleteBody :: Body -> World -> World exists, it will always remain a problem. Are there any clever idioms I can use for this interface or implementation? Is there a way to store the data for bodies along with the Body object instead of with the world in a way that the relationships between them respect different generations of the World (through integrate)? Any other ideas? Thanks, Luke [1] Once as SF () (Position,Velocity), and again as SF PhysIn PhysOut where PhysIn = (Impulse,Momentum) and PhysOut = (Position,Velocity). [2] Using the arrow joinSF :: SF (Event (SF [a] a)) [a], and other similar style functions taking streams of SF events...

4 4

cabal-install
by Ben Franksen 30 Nov '07

30 Nov '07

Just thought I install the latest version (0.4.0) from hackage and test it. Build and install went fine, but then it gets strange: ben@sarun: .../haskell/cabal-install-0.4.0 > sudo runhaskell Setup.lhs install Installing: /usr/local/bin ben@sarun: .../haskell/cabal-install-0.4.0 > rehash ben@sarun: .../haskell/cabal-install-0.4.0 > cabal --help Usage: cabal [GLOBAL FLAGS] or: cabal COMMAND [FLAGS] [...etc...] Commands: fetch Downloads packages for later installation or study. install Installs a list of packages. update Updates list of known packages clean Removes downloaded files list List available packages on the server. info Emit some info ben@sarun: .../haskell/cabal-install-0.4.0 > cd .. ben@sarun: .../software/haskell > cabal info Config file /home/ben/.cabal/config not found. Writing default configuration to /home/ben/.cabal/config. cabal: dist/Conftest.c: openFile: does not exist (No such file or directory) When later I tried the 'install' command, it reminds me to 'cabal update' first, which I do (no response, so probably worked), however next 'cabal install' gives the same funny answer about a missing dist/Conftest.c. Schade. Cheers Ben

4 9

Rigid type-var unification failure in existentials used with parametrically polymorphic functions
by Pablo Nogueira 30 Nov '07

30 Nov '07

A question about existential quantification: Given the existential type: data Box = forall a. B a in other words: -- data Box = B (exists a.a) -- B :: (exists a.a) -> Box I cannot type-check the function: mapBox :: forall a b. (a -> b) -> Box -> Box -- :: forall a b. (a -> b) -> (exists a.a) -> (exists a.a) mapBox f (B x) = B (f x) Nor can I type check: mapBox :: forall a. (a -> a) -> Box -> Box -- :: forall a. (a -> a) -> (exists a.a) -> (exists a.a) mapBox f (B x) = B (f x) The compiler tells me that in both functions, when it encounters the expression |B (f x)|, it cannot unify the universally quantified |a| (which generates a rigid type var) with the existentially quatified |a| (which generates a different rigid type var) -- or so I interpret the error message. However, at first sight |f| is polymorphic so it could be applied to any value, included the value hidden in |Box|. Of course, this works: mapBox :: (forall a b. a -> b) -> Box -> Box mapBox f (B x) = B (f x) Because it's a tautology: given a proof of a -> b for any a or b I can prove Box -> Box. However the only value of type forall a b. a -> b is bottom. This also type-checks: mapBox :: (forall a. a -> a) -> Box -> Box mapBox f (B x) = B (f x) When trying to give an explanation about why one works and the other doesn't, I see that, logically, we have: forall a. P(a) => Q implies (forall a. P(a)) => Q when a does not occur in Q. The proof in our scenario is trivial: p :: (forall a. (a -> a) -> (Box -> Box)) -> (forall a. a -> a) -> Box -> Box p mapBox f b = mapBox f b However, the converse is not true. Yet, could somebody tell me the logical reason for the type-checking error? In other words, how does the unification failure translate logically. Should the first mapBox actually type-check? Isn't the code for mapBox :: forall a. (a -> a) -> Box -> Box encoding the proof: Assume forall a. a -> a Assume exists a.a unpack the existential, x :: a = T for some T apply f to x, we get (f x) :: a pack into existential, B (f x) :: exists a.a Discharge first assumption Discharge second assumption The error must be in step 3. Sorry if this is obvious, it's not to me right now.

3 4