- Haskell-Cafe - Haskell.org

Typeclass problem
by Mark T.B. Carroll 29 Jul '04

29 Jul '04

I have a little programme that doesn't compile: module Example where class (Show c, Ord c, Bounded c) => MyClass c showThings :: MyClass c => c -> (String, String) showThings x = let foo = maxBound :: c in (show x, show foo) If I change that second-to-last line to, let foo = max x maxBound then it compiles. However, it's clearly silly to use "max" just to make the type of the maxBound be the same type as the x. (I'm assuming that the Ord and the Bounded instances of the type are sensibly consistent.) What should I be writing if I want foo to be the maxBound applied to the type that x is? -- Mark

2 2

why is Prelude.^ so convoluted?
by blaetterrascheln＠web.de 29 Jul '04

29 Jul '04

{- (^) :: (Num a, Integral b) => a -> b -> a x ^ 0 = 1 x ^ n | n > 0 = f x (n-1) x where f _ 0 y = y f x n y = g x n where g x n | even n = g (x*x) (n`quot`2) | otherwise = f x (n-1) (x*y) _ ^ _ = error "Prelude.^: negative exponent" -} -- Is (^) :: (Num a, Integral b) => a -> b -> a x ^ 0 = 1 x ^ n = if even n then y*y else y*y*x where y = x ^ (n `quot` 2) _ ^ _ = error "negative exponent" -- not good enough? ________________________________________________________________ Verschicken Sie romantische, coole und witzige Bilder per SMS! Jetzt neu bei WEB.DE FreeMail: http://freemail.web.de/?mc=021193

1 0

not getting most general type - is this a bug in hugs?
by blaetterrascheln＠web.de 29 Jul '04

29 Jul '04

$ cat x.hs rep0 :: Num a => [a] rep0 = repeat 0 rep0' = repeat 0 $ hugs x.hs ... Main> :t rep0 rep0 :: Num a => [a] Main> :t repeat 0 repeat 0 :: Num a => [a] Main> :t rep0' rep0' :: [Integer] -- WHAT?? Main> :version -- Hugs Version Nov 2002 ________________________________________________________________ Verschicken Sie romantische, coole und witzige Bilder per SMS! Jetzt neu bei WEB.DE FreeMail: http://freemail.web.de/?mc=021193

2 1

What versions do I need to compile the fptools?
by Ron de Bruijn 29 Jul '04

29 Jul '04

I want to compile all of the fptools. This is what I did: I got all files via CVS. And I did autoreconf ./configure make But with the make step gcc crashes with an internal error on Syntax.hi. I already filled in a bug report (not the most clear of them). I especially installed an "old" version of gcc (3.3.3)(I had gcc 3.4.1-2) to be able to compile the C Macro's correctly. For the Haskell compilation I used ghc-6.2.1. I think there is somewhere somebody that can compile it, but I need the *exact* versions of the software needed to do it. Is there anyone that *can* compile all of the fptools successfully? Regards, Ron __________________________________ Do you Yahoo!? New and Improved Yahoo! Mail - Send 10MB messages! http://promotions.yahoo.com/new_mail

1 0

Re: [Haskell-cafe] optimising for vector units
by MR K P SCHUPKE 28 Jul '04

28 Jul '04

Erm, when I said no overhead I meant there is no overhead to choosing an instruction from a different thread compared to choosing an instruction from the same thread... Obviously the overall scheduling overhead will increase. >The real killer, of course, is memory latency. The cache resources >required to hold pending work can't be used to hold heap data I would have thought cache thrashing caused by two CPUs accessing the same address repeatedly would be the real killer... Of course this is not so much of a problem with hyper-threading where both 'virtual' CPUs access the same cache. >* All your functions must be strict in their arguments, I don't see that I am making that assumption. Obviously parts of the program that are in the IO monad are strict, so we start with the demand for a value required strictly by an IO function. This value will be the result of a function, so we take the graph representing the function, and carry on as suggested. This is definitely lazy as parameters not affecting the result will never be evaluated. I appreciate there are some unanswered hard questions, but most of these are to do with efficiency - not whether it is possible... Having an inefiicient implementation now rather than nothing might just be what is needed to get people looking at the efficiency issues. Thanks for the references by the way - although I am quite familiar with the Monsoon architecture - and the Pentium architecture (which since PPro has been internaly dataflow... SuperScalar is really a dataflow computer emulating a traditional processor, and interpreting its instructions) Keean./

1 0

Re: [Haskell-cafe] optimising for vector units
by MR K P SCHUPKE 28 Jul '04

28 Jul '04

>That was me. I think you're underestimating the cost of starting >threads even in this very lightweight world. Maybe... Perhaps haskell could be made to resemble dataflow instructions more... If when a computation completes we insert the result directly into the data structure which represents function, we can infact pick any function for execution with _no_ overhead. (In a true dataflow system any instruction from any thread can be executed with no overhead) The point it at any time we have N functions ready for execution (a function is ready for execution when all its arguments are ready)... we can pick and execute any (or all of these if enough execution units are ready) of these. The suggestion I guess is to only use instructions that get their arguments from main memory. This way any instruction can be sequenced with no overhead on any CPU. With modern on-die core-speed caches this can be almost as fast a registers (with good cache access patterns) ... Note that I am only suggesting interleaving instructions at the function level, so registers can be used within functions... of course as things get more and more parallel we may see hardware with no registers, just pipelined high speed cache access. (The hardware may well use registers to pre-fetch cache values, but that can be made transparent to the software)... Hardware manufacturers have hit the limit for pure sequential execution speed, so more parallelism is the only way forward (see Intels revised roadmap, they abandoned the pentium 4 and 5 and have focused on an updated _low_power_ pentium 3M, and are planning multi core versions for more speed). C and other imperitive languages focus toom much on the how and not the what to be easy to use in such multi-cpu environments... A language with abstracts and hides the parallelism could well take off in a big way. Keean.

2 1

Another STG optimization
by 7253146＠informatica.alumnos.uma.es 27 Jul '04

27 Jul '04

Hi. Thanks for the very useful replies to my recent question! I am still exploring some updating techniques for my pet STG machine. This time I am turning over an idea about closures returning primitive (unboxed) values. These ones, regardless other updating considerations, obviously cannot be updated directly, because the results are not closures. However, I think we could use a special closure for updating in these cases, with a single field holding the primitive result, which, when entered, should simply return its stored primitive value. operationals of my trick: -"someclosure", a zero-arg-closure which eventually returns a primitive value, is entered. -Before starting its evaluation, an update frame is pushed on the stack. -eventually, evaluation is done and a primitive value is returned. -a continuation is popped from the stack and entered, which turns to be actually the previously pushed update frame. -the update frame overwrites the closure to be updated with the a special closure, which holds the result value and, when entered, returns it. I think the same effects can be achieved using boxed values wherever commoning up the evaluation is required, but I think it may be slower (and it may use more heap space). And, of course, this trick only makes sense if the compiler front-end builds lots of zero-arg-closures which returns primitive values as result of large computations involving not many boxed values (which could capture, when updated, many intermediate steps of the computation). does someone knows if some similar trick has been implemented? (I have tried to read the GHC RTS (and some others), but it is too hard to understand!). Perhaps this trick is not useful? Or not possible due to some reason? Thanks in advance, Jose David --------------------------------------------- Este mensaje lo ha enviado un Alumno de la Universidad de Malaga. http://www.alumnos.uma.es/

1 0

Another STG optimization
by 7253146＠informatica.alumnos.uma.es 27 Jul '04

27 Jul '04

Hi. Thanks for the very useful replies to my recent question! I am still exploring some updating techniques for my pet STG machine. This time I am turning over an idea about closures returning primitive (unboxed) values. These ones, regardless other updating considerations, obviously cannot be updated directly, because the results are not closures. However, I think we could use a special closure for updating in these cases, with a single field holding the primitive result, which, when entered, should simply return its stored primitive value. operationals of my trick: -"someclosure", a zero-arg-closure which eventually returns a primitive value, is entered. -Before starting its evaluation, an update frame is pushed on the stack. -eventually, evaluation is done and a primitive value is returned. -a continuation is popped from the stack and entered, which turns to be actually the previously pushed update frame. -the update frame overwrites the closure to be updated with the a special closure, which holds the result value and, when entered, returns it. I think the same effects can be achieved using boxed values wherever commoning up the evaluation is required, but I think it may be slower (and it may use more heap space). And, of course, this trick only makes sense if the compiler front-end builds lots of zero-arg-closures which returns primitive values as result of large computations involving not many boxed values (which could capture, when updated, many intermediate steps of the computation). does someone knows if some similar trick has been implemented? (I have tried to read the GHC RTS (and some others), but it is too hard to understand!). Perhaps this trick is not useful? Or not possible due to some reason? Thanks in advance, Jose David --------------------------------------------- Este mensaje lo ha enviado un Alumno de la Universidad de Malaga. http://www.alumnos.uma.es/

1 0

Existential type within a record ... bad?
by Scott West 27 Jul '04

27 Jul '04

Hello all, Just got an interesting error, which I can't really understand (but that DOES happen a lot...). Trying to work with existention types, record types, and wrapping the whole thing up in a nice IORef for my uses: data ETable = forall a. EditableTable a => ETable a data GuiRecord = GuiRecord {gtable :: ETable, moz :: MozEmbed, pos :: Position, ent :: Entry} type GuiState = IORef (GuiRecord) Generates the following error: Couldn't match `* -> Type bx' against `*' In the type synonym declaration for `GuiState' Anyone have any ideas?? Thanks in advance! Regards, Scott

1 0

Re: [Haskell-cafe] optimising for vector units
by Jon Cast 27 Jul '04

27 Jul '04

MR K P SCHUPKE <k.schupke(a)imperial.ac.uk> wrote: > As far as I understand it haskells lazy evaluation resembles dataflow > computation - IE values are computed on demand. > > This problem has already been solved for hardware, you end up with > what is termed a super-scalar architecture. > > Instructions read from memory fill a re-order buffer. As computations > complete value slots in the reorder buffer are filled with the result > values. When an instruction has all its values it can be executed, and > will be assigned to the next available execution unit. > > I am not too sure of the internal architecture of GHC, but I can > imagine that funtions waiting to be run will have slots for arguments, > that will be filled in when values become available. No. A function may not use all of its arguments, so there's no point in evaluating all arguments---you have to find out which ones are actually needed. Terminology note: GHC uses the STG language internally. In STG, evaluation is always triggered by a case expression, which evaluates precisely one expression (not necessarily an argument of anything, either!). > The whole point is that a function with three parameters can spark > three threads This is actually a bad idea: the point of non-strict languages and lazy evaluation is to allow lots of values which are (a) unused and (b) expensive to evaluate. If you evaluate everything (even in parallel), there's a lot of wasted work if the programmer is making optimal use of the non-strictness of the language. Furthermore, if de-forestation fails anywhere, you've likely got another problem. Consider the following program: > n `choose` m = product $ take m $ [n, n-1..] Which translates (after some optimisation) to STG equivalent to: > downFrom n = let n1 = (-) n 1 > in let xn1 = downFrom n1 > in let xn2 = n:xn1 > in xn2 > choose n m = let xn1 = downFrom n > in let xn2 = take m xn1 > in product xn2 Now, (:) cannot `spark' a thread to evaluate xn1 in downFrom, because that would end up sparking infinitely many threads---which may be possible, but nothing you've said suggests that it is. > to calculate each parameter without worrying about the side affects of > each function. No locking is necessary because you only spark one > thread for each argument. This is true for tree reduction, but not for graph reduction. Consider, e.g., the fact that the call to product in choose and the recursive call to downFrom walk down (and hence evaluate) the same list. Since the cons cells making up this list are evaluated by two different functions, some sort of locking is indeed necessary to ensure that you don't end up with two threads for each of the (infinitely many) cons cells in the list. > I suspect I haven't fully understood the difficaulty in doing this, > care to enlighten me? Certainly. See above. Jon Cast

3 2