February 2007 - Haskell-Cafe

Saving the AST generated by Template Haskell
by Alfonso Acosta 22 Feb '07

22 Feb '07

Hi all, I'm using Template Haskell to design a small subset of a Hardware Description DSEL (Domain Specific Embedded Language). My language supports higher order as the user can supply small functions as arguments. I chose to parse them with TH because it allows me to use plain Haskell for the function syntax (instead of reinventing the wheel) but mostly because gives parsing for free. The AST of the functions must be kept by the embedded compiler so that it can be later translated to a target language by one of the potential backends of the embedded compiler. The problem is ... how to store that AST? Let me show an example ---- import Language.Haskell.TH.Syntax -- sample function from the DSLE library hdMapSY :: (HDPrimType a, HDPrimType b) => HDFun (a -> b) -> HDSignal a -> HDSignal b -- We keep the function's AST (to make program transformations in the backends) newtype HDPrimFun = HDPrimFun [Dec] deriving Show -- Type safety layer, we keep the function to make sure TH checks the type (and possible further simulations) data HDFun a = HDFun [Dec] a deriving Show -- Helper constructor function, which suffers from the Saving-the-AST problem -- mkMetaAST currently returns a phony value mkHDFun :: Q [Dec] -> Q Exp mkHDFun qd = do dx <- qd metaASTnm <- newName "metaAST" let funnm = getFunName dx metaAST = mkMetaAST dx metaASTdec = ValD (VarP metaASTnm) (NormalB metaAST) [] return $ LetE (metaASTdec:dx) (AppE (AppE (ConE $ mkName "HDFun") (AppE (ConE $ mkName "HDPrimFun") (VarE metaASTnm))) (VarE funnm)) where getFunName :: [Dec] -> Name getFunName [FunD nm _] = nm getFunName _ = error "mkHDFun: toy example, just and exactly one dec!" -- This function should create an AST expression from the AST -- but it would be a big pain to code mkMetaAST :: [Dec] -> Exp mkMetaAST _ = AppE (ConE (mkName "LitE")) (LitE (StringL "big pain to code!")) --- An example program coded in the DSLE could could be something like .. myCircuit :: HDSignal Int -> HDSignal Int myCircuit = hdMapSY ($mkHDFun [d| f input = input+1 |]) So the question is .. How can mkHDfun save the AST of "f input = input+1" (for which it needs to create and return a metaAST) without the effort of having to create boiler plate code for the whole TH library types? Did anyone do something similar before? I workaround would be saving the String of the AST with show, but Dec nor Exp belong to the Read class, :S Thanks in advance, Alfonso Acosta

2 3

Fwd: [Haskell-cafe] Newbie: generating a truth table
by Peter Berry 22 Feb '07

22 Feb '07

Sigh, I seem to have done a reply to sender. Reposting to the list. On 06/02/07, phiroc(a)free.fr <phiroc(a)free.fr> wrote: > Hello, > > I would like to create a Haskell function that generates a truth table, for > all Boolean values, say, using the following "and" function : > > and :: Bool -> Bool -> Bool > and a b = a && b A fairly old thread, but I had an interesting idea: > combos :: (Enum a, Enum b) => a -> b -> (a -> b -> c) -> [(a, b, c)] > combos min1 min2 op = [(x, y, x `op` y) | x <- [min1..], > y <- [min2..]] Then: *Main> combos False (&&) [(False,False,False),(False,True,False),(True,False,False),(True,True,True)] In the case of Bool and a few others, you can use a slightly nicer one: > bCombos :: (Enum a, Bounded a, Enum b, Bounded b) => > (a -> b -> c) -> [(a, b, c)] > bCombos op = [(x, y, x `op` y) | x <- [minBound..maxBound], > y <- [minBound..maxBound]] And: *Main> bCombos (&&) [(False,False,False),(False,True,False),(True,False,False),(True,True,True)] The secret of these is of course in the Enum and Bounded type classes, which define, respectively, * enumFrom and enumFromTo (which have syntactic sugar in [foo..] and [foo..bar] respectively), and * minBound and maxBound. You can do the same with any instance of these classes. -- Peter Berry <pwberry(a)gmail.com> Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html

5 4

Multiparameter class error
by Alfonso Acosta 21 Feb '07

21 Feb '07

Hi, I'm a newbie to multiparameter classes and I'm getting this error from GHC when compiling the following class definition: Could not deduce (Synchronous s f11) from the context (Synchronous s f1) arising from use of `delaySY' Possible fix: add (Synchronous s f11) to the class or instance method `sourceSY' In the expression: delaySY s0 s In the definition of `o': o = delaySY s0 s In the definition of `sourceSY': sourceSY f s0 = o where o = delaySY s0 s s = mapSY f \begin{code} class Synchronous s f1 where mapSY :: f1 a b -> s a -> s b delaySY :: a -> s a -> s a sourceSY :: f1 a a -> a -> s a sourceSY f s0 = o where o = delaySY s0 s s = mapSY f o \end{code} Can anyone explain a bit further than GHC what am I doing wrong? Thanks, Alfonso Acosta

2 2

Implementation of scaled integers
by Stefan Heinzmann 21 Feb '07

21 Feb '07

Hi all, is there a library for Haskell that implements scaled integers, i.e. integers with a fixed scale factor so that the scale factor does not need to be stored, but is part of the type? In particular it would be useful (i.e. for signal processing) to have numbers based on Int scaled such that they fall into the range [-1.0 .. 1.0). Or other scale factors which are powers of 2. Addition and subtraction would then map to the ordinary operations for Int, while Multiplication and Division would have to apply the scale factor to correct the result of normal Int operations (which would be a shift operation). If it doesn't exist yet, have you got ideas how to implement that for maximum efficiency? Cheers Stefan

6 7

nobench: now with hbc support (!)
by dons＠cse.unsw.edu.au 21 Feb '07

21 Feb '07

Just a quick note. I've tweaked the benchmarks some more, adding support for Lennart's hbc compiler. (Go hbc!). Also, we have nice html output (thanks to Text.XHtml!). http://www.cse.unsw.edu.au/~dons/nobench/results.html Pretty :-) Remaining tasks left are to port the rest of the 'real' category from nofib, and implement output diffing (note the nhc winning entries, due to erroneous output), and add nhc's bytestring support. The particular errors are logged here, http://www.cse.unsw.edu.au/~dons/nobench/bench.results -- Don

1 0

Call for testers: using Cabal to build RPMs
by Bryan O'Sullivan 21 Feb '07

21 Feb '07

I've got a branch of Cabal that adds a new command, "rpm", that lets you build an RPM package with a single invocation: runhaskell Setup.*hs rpm I've tested this pretty extensively with GHC 6.6, and I'm quite happy with it, but if there are other users of RPM-based distros out there, I'd appreciate it if you could kick the tyres a bit. Once it's in solid shape, I hope to plug this capability into Hackage so that there will automatically be fresh RPM packages available for Linux distributions such as Fedora. See the brief writeup here: http://www.serpentine.com/blog/2007/02/20/haskell-cabal-now-with-extra-crun… Cheers, <b

1 0

Haskell School of Expression
by Andrew Wagner 21 Feb '07

21 Feb '07

Has anyone worked through HSOE lately? I'm wondering if I'm going to be able to work through the examples that use their graphic library, under gtk2hs on fedora. Is there a workaround for this?

2 1

Re: Genuine Eratosthenes sieve [Was: Optimization fun]
by Melissa O'Neill 20 Feb '07

20 Feb '07

Sorry, I'm a little late to this thread, but the topic of > sieve [] = [] > sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0] (as posted by Rafael Almeida) is somewhat dear to my heart, as I wrote a paper about it last summer and sent it in to JFP. Still waiting for a reply though. Let's go back to the beginning with the classic complaint and the excuses... Creighton Hogg wrote: > So a friend and I were thinking about making code faster in > Haskell, and I was wondering if there was a way to improve the > following method of generating the list of all prime numbers. It > takes about 13 seconds to run, meanwhile my friend's C version took > 0.1. Here come the excuses, like this one from apfelmus, > While Haskell makes it possible to express very complicated > algorithms in simple and elegant ways, you have to expect to pay a > constant factor (roughly 2x-10x) when competing against the same > algorithm in low-level C. and this one from Nicolas Frisby, > I have yet to need my Haskell to perform well Matthew Brecknell came up with something much faster, namely > primes :: [Int] > primes = 2 : filter isPrime [3,5..] where > f x p r = x < p*p || mod x p /= 0 && r > isPrime x = foldr (f x) True primes FWIW, another way to write this code (without needing to think about how "fold bails early") is primes = 2: [x | x <−[3,5..], all (\p −> x `mod` p > 0) (factorsToTry x)] where factorsToTry x = takeWhile (\p −> p*p <= x) primes Both of these algorithms best the "sieve" we began with and run quickly, but as you can see (possibly more clearly from my rephrasing), this algorithm is not actually the Sieve of Eratosthenes -- it's actually a classic naive primes algorithm which checks a number for primality by trying to divide it by every prime up to its square root. But that's okay, because our initial algorithm ISN'T THE REAL SIEVE EITHER. Markus Fischmann hits the nail on the head when he says > The characteristics of a sieve is, that it uses the already found > primes to generate a list of non-primes that is then removed from a > list of candiates for primeness. But then we get distracted by a discussion about avoiding division. It's true that the real sieve avoids division, but it is NOT true that every algorithm that avoids division is the sieve. The thread ends with this algorithm from Yitzchak Gale: > -- Delete the elements of the first list from the second list, > -- where both lists are assumed sorted and without repetition. > deleteOrd :: Ord a => [a] -> [a] -> [a] > deleteOrd xs@(x:xs') ys@(y:ys') > | x > y = y : deleteOrd xs ys' > | x < y = deleteOrd xs' ys > | otherwise = deleteOrd xs' ys' > deleteOrd _ ys = ys > > sieve (x:xs) = x : sieve (deleteOrd [x+x,x+x+x..] xs) > sieve _ = [] > > primes = sieve [2..] Which seems reasonable, until you realize that every prime p we come up with is still "considered" by k deleteOrd filters, where k is the number of primes that preceeded it. So, let's recap: the original algorithm is beautiful and simple, but it is NOT the actual Sieve of Eratosthenes, NOT because it uses modulus, but because fundamentally, at the highest level, it is a different algorithm. At the risk of beating a dead horse, let's see why it's not the real sieve. What makes the sieve an efficient algorithm are the details of *what* gets "crossed off", *when*, and *how many times*. Suppose that we are finding the first 100 primes (i.e., 2 through 541), and have just discovered that 17 is prime. We will begin crossing off at 289 (i.e., 17 * 17) and cross off the multiples 289, 306, 323, ... , 510, 527, making fifteen crossings off in total. Notice that we cross off 306 (17 * 18), even though it is a multiple of both 2 and 3 and has thus already been crossed off twice. (The starting point of 17 * 17 is a pleasing, but actually *minor*, optimization for the *genuine* sieve.) The algorithm is efficient because each composite number, c, gets crossed off f times, where f is the number of unique factors of c less than sqrt(c). The average value for f increases slowly, being less than 3 for the first 10^12 composites, and less than 4 for the first 10^34. None of the algorithms we've discussed correspond to the above algorithm. It is not merely that they don't perform "optimizations", such as starting at the square of the prime, or that some of then use a divisibility check rather than using a simple increment. Rather, at a fundamental level, they all work differently than the real sieve. Following our earlier example, after finding that 17 is prime, the "phony" algorithm will check to see if 19 is divisible by 17 (in the case of Yitzchak's algorithm, divisibility is checked by comparing against 17*2), followed by 23, 29, 31, ... , 523, 527, checking a total of ninety-nine numbers for divisibility by 17. In fact, even if it did (somehow) begin at 289, it would examine all forty-five numbers that are not multiples of the primes prior to 17 (289, 293, 307, ... , 523, 527). It is also worth realizing that the set of numbers examined by the phony algorithm is not a superset of the ones examined by the real sieve (as we saw, the real algorithm crossed off 306, which the phony algorithm skips). In general, the speed of the phony algorithm depends on the number of primes that are *not* factors of each composite, whereas the speed of the real algorithm depends on the number of (unique) primes that *are*. Hopefully at this point I've piqued your interest. Maybe you're wondering what our original sieve algorithm is, if it isn't the real sieve and the mod issue is just a red herring...? Maybe you're wondering what the the real sieve looks like, coded in Haskell. Or maybe you're still not convinced about any of it. If so, I invite you to read a draft of my JFP paper, available at: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf Best Regards, Melissa.

5 7

return?
by Vikrant 20 Feb '07

20 Feb '07

Hi, I am writing a recursive function which does some IO operation. I encounter situation in which my function has to end recursion by doing "nothing" and otherwise keep calling same function with some different parameters. I did not find anything equivalent to "pass" or "return" statement in Haskell. Presently I have got a workaround. I am doing it by putting a dummy print as described below. can anybody help me in this? e.g f some_params = if some_condition then do putStr "Hacky way to do nothing!" else do perform_some_IO f some_other_params == Vikrant

3 2

trouble installing ghc 6.6: xargs: /usr/bin/ar: terminated by signal 11
by tphyahoo 20 Feb '07

20 Feb '07

I'm having trouble installing ghc 6.6. On ubuntu, virtual server (user mode linux). Something seems to be killing the process, no idea why. Anyone seen this? I looked around with ps to see if anything looked suspicious. I do have a lot of screens open, but I don't see why that should matter. There is no instance of haskell or gnci running. after running configure with no problem..... ~$ cd ghc-6.6/ ~/ghc-6.6$ sudo make &>makeOut Password: ~/ghc-6.6$ tail -n8 makeOut (echo Control/Concurrent_stub.o System/CPUTime_hsc.o System/Time_hsc.o ; /usr/bin/find Control/Applicative_split Control/Arrow_split Control/Concurrent_split Control/Concurrent/Chan_split ...long mess... Text/PrettyPrint/HughesPJ_split Text/Printf_split Text/Read_split Text/Read/Lex_split Text/Show_split Text/Show/Functions_split -name '*.o' -print) | xargs /usr/bin/ar q libHSbase.a /usr/bin/ar: creating libHSbase.a xargs: /usr/bin/ar: terminated by signal 11 make[2]: *** [libHSbase.a] Error 125 make[2]: *** Deleting file `libHSbase.a' make[1]: *** [all] Error 1 make[1]: Leaving directory `/home/thartman/ghc-6.6/libraries' make: *** [stage1] Error 2 ~/ghc-6.6$ -- View this message in context: http://www.nabble.com/trouble-installing-ghc-6.6%3A-xargs%3A--usr-bin-ar%3A… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

7 7