- Haskell-Cafe - Haskell.org

LLVM back end
by Michael T. Richter 23 Nov '06

23 Nov '06

I've been eyeing LLVM[1] as interesting technology -- brief executive summary: a virtual machine suited as the back end of compiler output with optimised native code then coming from it as either JIT-based execution of the LLVM bytecode or as a further compilation step -- and couldn't help but immediately think of the possibility of one of the Haskell compiler projects providing an LLVM code generator. I think this would help in several areas: * it could make porting the compiler to other architectures -- including oddball ones that would be too small to otherwise support -- easier; * it could help remove the nigh-ubiquitous reliance upon GCC as a back-end (while I think that GCC is a pretty good piece of software, I'm not sure it's really suited to its current role as the "do-everything" back end); * it could leverage some of the really interesting work that's going on in optimisation technology by letting one VM's optimiser do the work for any number of languages; * it could improve interaction between source code written in multiple languages. Is this me opening up a Pandora's Box of ignorance here? Or is LLVM potentially interesting? (And were someone motivated into perhaps trying to make an LLVM back-end, where would one start to poke around in, say, the GHC codebase to even begin to implement this? And how insane would they be driven by the process?) [1]http://llvm.org -- Michael T. Richter Email: ttmrichter(a)gmail.com, mtr1966(a)hotpop.com MSN: ttmrichter(a)hotmail.com, mtr1966(a)hotmail.com; YIM: michael_richter_1966; AIM: YanJiahua1966; ICQ: 241960658; Jabber: mtr1966(a)jabber.cn "I have never seen the poor people being so familiar with their heads of state as they were with [Michele Duvalier]. It was a beautiful lesson for me. I've learned something from it." --Mother Theresa

2 2

Re: help with happy/alex
by Simon Marlow 23 Nov '06

23 Nov '06

robert bauer wrote: > Hi, > > I have a .y and .x file. The alex -g _.x gives me a .hs file and happy -g -a -c _.y gives me a .hs file. > I then use ghc -c alex.hs to get a a .o and a .hi file. This works great. > Unfortunately > ghc -c happy.y doesn't work -- it says that it the module name for the lexer doesn't match. I've attached the > .y and .x files. > > Also, I cannot figure out what I need to do in the parser to call the lexer and I don't know how to kick start the > parser -- I have no clue what to put in third, main.hs, module. > > Any help would be appreciated. You have a typo in the module name in TVScriptLexer.x. As for tying it together, I suggest taking a look at some of the examples, eg. http://darcs.haskell.org/alex/examples/tiny.y from the Alex distribution. Cheers, Simon

1 0

YCR2JS Programmers Guide Draft available
by Dimitry Golubovsky 23 Nov '06

23 Nov '06

Hi, I have finished typing in the draft of low-level programming guide for Yhc Core to Javascript converter. Everyone interested in future use of this tool is encouraged to read and review the Guide. Its purpose is to give some ideas about interaction of Haskell programs converted into Javascript with a web browser on the lowest possible level, without application frameworks and support libraries (just because these haven't been developed). Any feedback and ideas are appreciated. The document is located at: http://haskell.org/haskellwiki/Yhc/Javascript/Programmers_guide Thanks. -- Dimitry Golubovsky Anywhere on the Web

1 0

trivial ghc problem, help needed
by brad clawsie 22 Nov '06

22 Nov '06

i have a program tb.hs: --- module Main where import Network.URI (URI(..), URIAuth(..), parseURI) myFunc :: String -> Maybe URI myFunc u = parseURI u main = do { return () } --- when i attempt to build it with ghc, i get the following output: tb.o: In function `Main_myFunc_info': (.text+0x11): undefined reference to `networkzm2zi0_NetworkziURI_parseURI_closure' tb.o: In function `Main_myFunc_srt': (.rodata+0x0): undefined reference to `networkzm2zi0_NetworkziURI_parseURI_closure' collect2: ld returned 1 exit status any clue why? i would send this to the ghc list but i presume my issue is due to a trivial misunderstanding of the language thanks in advance

2 1

Articles on programming with (IO) exceptions in Haskell?
by Magnus Therning 22 Nov '06

22 Nov '06

I'm having problems finding a good introduction to exceptions. Yet Another Haskell Tutorial leaves it for chapter 10, which is empty. I'd prefer something that suits a noob. :-) /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus Software is not manufactured, it is something you write and publish. Keep Europe free from software patents, we do not want censorship by patent law on written works. `Time is an illusion. Lunchtime doubly so.' `Very deep,' said Arthur, `you should send that in to the "Reader's Digest". They've got a page for people like you.' -- Ford convincing Arthur to drink three pints in ten minutes at lunchtime.

4 3

Why are new releases of libraries required for every GHC release?
by DavidA 22 Nov '06

22 Nov '06

Some recent comments suggested that every time there is a new GHC release, there needs to be a new wxHaskell release (or insert name of other library here) to work with it. This seems to be true even for minor upgrades, like 6.4.1 -> 6.4.2. Why is this? Does GHC break binary compatibility at every release? Is this avoidable? This makes using Haskell unnecessarily hard compared to other platforms.

4 3

help with threadDelay
by Neil Davies 22 Nov '06

22 Nov '06

Hi, I'm using GHC 6.6 (debian/etch) - and having some fun with threadDelay. When compiled without the -threaded compiler argument it "behaves" as documented - waits at least the interval - for example: Tgt/Actual = 0.000000/0.036174s, diff = 0.036174s Tgt/Actual = 0.000001/0.049385s, diff = 0.049384s Tgt/Actual = 0.000005/0.049492s, diff = 0.049487s Tgt/Actual = 0.000025/0.049596s, diff = 0.049571s Tgt/Actual = 0.000125/0.049655s, diff = 0.04953s Tgt/Actual = 0.000625/0.04969s, diff = 0.049065s Tgt/Actual = 0.003125/0.049684s, diff = 0.046559s Tgt/Actual = 0.015625/0.04962s, diff = 0.033995s Tgt/Actual = 0.078125/0.099668s, diff = 0.021543s Tgt/Actual = 0.390625/0.399637s, diff = 0.009012s Tgt/Actual = 1.953125/1.999515s, diff = 0.04639s Tgt/Actual = 9.765625/9.799505s, diff = 0.03388s however when -threaded is used you get some interesting effects, including returning too early: Tgt/Actual = 0.000000/0.000093s, diff = 0.000093s Tgt/Actual = 0.000001/0.000031s, diff = 0.00003s Tgt/Actual = 0.000005/0.000029s, diff = 0.000024s Tgt/Actual = 0.000025/0.000028s, diff = 0.000003s Tgt/Actual = 0.000125/0.000034s, diff = -0.000091s Tgt/Actual = 0.000625/0.000035s, diff = -0.00059s Tgt/Actual = 0.003125/0.000029s, diff = -0.003096s Tgt/Actual = 0.015625/0.000028s, diff = -0.015597s Tgt/Actual = 0.078125/0.058525s, diff = -0.0196s Tgt/Actual = 0.390625/0.389669s, diff = -0.000956s Tgt/Actual = 1.953125/1.939513s, diff = -0.013612s Tgt/Actual = 9.765625/9.749573s, diff = -0.016052s The program I used to generate this is :- import Control.Concurrent import Data.Time import Text.Printf main = mapM_ delay (0 : take 11 (iterate (*5) 1)) delay n = do tS <- getCurrentTime threadDelay n tE <- getCurrentTime let n' = toRational n / 10^6 n'' = fromRational (n') :: Double obs = diffUTCTime tE tS printf "Tgt/Actual = %0.6f/%s, diff = %s\n" n'' (show obs) (show $ obs - fromRational n') return () Any suggestions? Neil

3 2

why are implicit types different?
by S. Alexander Jacobson 21 Nov '06

21 Nov '06

Why do g and g' have different types? g x y = let ?f = \x-> x in ?f x ++ (show (?f y)) g' x y = let f = \x-> x in f x ++ (show (f y)) Is there a way I can use implicit types and let g be as general as g'? -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

1 0

Friday Afternoon Play: The Burrows Wheeler Transformation
by Jón Fairbairn 21 Nov '06

21 Nov '06

So, it's Friday afternoon (well, here anyway), and presumably everyone is thinking of leaving for the weekend. Is anyone interested in playing a little game? I'm going to make the first move, and then just wait and see if anyone makes the next. I'm certainly not promising to make any further moves myself, but I'm not promising I won't, either. Below you'll see a naïve implementation of the Burrows Wheeler transformation and its inverse. That's my move. (And don't complain too much about style and such -- I'm half asleep.) Further moves are made by transforming the programme so that it becomes more efficient. The first target is not raw speed, but to adjust it until the computational complexity gets to be what it should be. I'm hoping for elegant moves here. After that, folk might start replacing the lists with more efficient datastructures and so on, but still /elegantly/. The object of the game isn't ultimate speed -- I've no particular wish to see a Haskell version that's as fast as a good C version, especially not if it ends up /looking/ like a C version. Really the objective is to think about Haskell programming -- and probably come up with some observations such as "there really ought to be a class of indexable structures, so that we don't have to change (!!) to (!) all over the place". And to have fun, anyhow... * * * Demonstration of the principle of the Burrows Wheeler transform. The implementations are simplistic (and have worse complexity than is possible). > module Burrows_Wheeler_Transform where > import List This is surely the wrong module to have to find (><) from: > import Data.Graph.Inductive.Query.Monad((><)) The forward transformation. Input a list, output the transformed list and possibly an int (Nothing if there were no elements in the input -- perhaps the result type should be Maybe (NonEmptyList t,Int)) > slow_bwt:: Ord t => [t] -> ([t], Maybe Int) This version works by computing a list of all the rotations of the input and sorting it. The transformation is then the last element of each line of the sorted rotations. Tag the data with an index so that it's possible to find where the original form of the unput ends up after sorting. This is essentially the specification of the transform coded up directly. > slow_bwt l > = (map fst tagged_bwt, index_of_original) > where tagged_bwt = map (last><id) > $ sort > $ rotations l`zip`[0..] > index_of_original = findIndex ((==0).snd) tagged_bwt that looks like worst case n²×log n to me (where n is the length of the string): if every element is the same, the n×log n comparisons the sort does will each look at every element, and that's really more than is necessary. The inverse transform. We should have that @ slow_inv_bwt . slow_bwt == id @ Observe that sorting the input gives the first column of the sorted rotations (and the input is the last). So after one sort we have X ... c Y ... b Z ... a . . . . . . . . . Since they are rotations, rotating each row of this gives pairs that belong to the original list: cX ... by ... aZ ... . . . . . . sorting these gives us the first two columns of the sorted rotations, and again we already know the last column, which can be rotated into the first and so on. > slow_inv_bwt ([],_) = [] > slow_inv_bwt (l,Just index_of_original) > = iterate catsort (replicate len []) After (length input) iterations we have the original sorted rotations, > !! len and we have the index of where the untransformed string is, so we can just pick it back out. > !! index_of_original > where catsort s = sort $ map (uncurry (:)) $ l `zip`s > len = length l This version does rather fewer sorts: > mark2_inv_bwt ([],_) = [] > mark2_inv_bwt (l,Just n) > = (transpose $ take (length l) $ iterate (permuteWith perm) l)!!(perm!!n) > where perm = map snd $ sort $ l `zip` [0..] Should I simply have left it out and hoped that it would turn up after a few moves? I'm not going to explain it, anyway. > rotations l = init $ zipWith (++) (tails l) (inits l) > permuteWith ns l = map (l!!) ns -- Jón Fairbairn Jon.Fairbairn(a)cl.cam.ac.uk

6 6

Newbie Haskell optimization question
by Slavomir Kaslev 21 Nov '06

21 Nov '06

Hello, I am new to Haskell and I am having fun with it writing L-system generator. I was very pleased with concise syntax. It's an order of magnitude better than any C++, Lisp, etc program I've ever written or read. Doing algorithmic optimizations on my generator I ended up with 4 different versions (you can see the other 3 in the file attached). The most optimal of them is: import qualified Data.Map type LSystemElement = (Char, [Int]) type LSystem = [LSystemElement] type LSystemRules = Data.Map.Map Char (LSystemElement -> LSystem) generate'' :: LSystemRules -> LSystem -> Int -> LSystem generate'' rules axiom steps = concatMap (iterate f axiom !!) (ind !! steps) where ind = [0] : [g x | x <- ind] where g [] = [] g [x] = [x, x + 1] g xs = xs ++ g (drop (length xs `div` 2) xs) f = concatMap $ \elem -> Data.Map.findWithDefault (\x -> [x]) (fst elem) rules elem -- Tests a (_, [x, y]) | y <= 2 = [('A', [x + 2, y + 2])] | otherwise = [('B', [2]), ('A', [x - 1, y - 1])] b (_, [x]) | x <= 2 = [('C', [])] | otherwise = [('B', [x - 1])] rules = Data.Map.fromList [('A', a), ('B', b)] axiom = [('A', [2, 2])] Now I am thinking of doing some language level optimizations. Can you give me any (random) directions? Any style recommendations are welcome as well. Cheers. -- Slavomir Kaslev

3 2