- Haskell-Cafe - Haskell.org

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

28 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 28 Jul '04

28 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 28 Jul '04

28 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 28 Jul '04

28 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

Beginner problems with 'triple' code
by Stu White 27 Jul '04

27 Jul '04

Hi I'm not especially experienced in using haskell, and I could use some help. As part of a project, I'm trying to construct a data type that can represent three values as a 'triple' (as opposed to a 'tuple'), and then make a function so that I can sort these values into ascending order. I'm having a few problems with the code that I have at the minute (I suspect its riddled with errors!) type Triple = Triple { entry 1 :: a; entry 2 :: a; entry 3 :: a; sortTriple :: Triple a -> Triple a; } deriving (Show, Eq) where sortTriple t@(Triple x y z) | (y<x) = sortTriple (Triple y x z) | (z<y) = sortTriple (Triple x z y) | otherwise = t Hope you guys can help me, sorry if this seems trivial - but I'm only a beginner! If you could explain/correct any errors I'd appreciate it, as I am trying to learn what to do and what not to do, not just arrive at a working program. Thanks S. Midley --------------------------------- ALL-NEW Yahoo! Messenger - all new features - even more fun!

4 3

Parsec Problem
by haskell＠alias.spaceandtime.org 27 Jul '04

27 Jul '04

Hello, I copied this example exactly from the page http://www.cs.uu.nl/people/daan/download/parsec/parsec.html -----begin----- module Parser where import Data.Char import Text.ParserCombinators.Parsec import Text.ParserCombinators.Parsec.Char import Text.ParserCombinators.Parsec.Token price = lexeme (do{ ds1 <- many1 digit ; char '.' ; ds2 <- count 2 digit ; return (convert 0 (ds1 ++ ds2)) }) <?> "price" where convert n [] = n convert n (d:ds) = convert (10*n + digitToInt d) ds -----end----- However attempting to compile it gives the error message Test.hs:8: Couldn't match `GenParser tok st a' against `CharParser st1 a1 -> CharParser st1 a1' Expected type: GenParser tok st a Inferred type: CharParser st1 a1 -> CharParser st1 a1 Probable cause: `lexeme' is applied to too few arguments in the call (lexeme (do ds1 <- many1 digit char '.' ds2 <- count 2 digit return (convert 0 (ds1 ++ ds2)))) In the first argument of `(<?>)', namely `lexeme (do ds1 <- many1 digit char '.' ds2 <- count 2 digit return (convert 0 (ds1 ++ ds2)))' I wish I knew what that meant. If someone could explain it and tell me what's wrong, I'd appreciate it. Thanks.

2 1

Ambiguous type variable
by Arjun Guha 27 Jul '04

27 Jul '04

Hi, I'm new to Haskell and am getting this error: AlphaBeta.hs:1: Ambiguous type variable `v' in the top-level constraint: `Ord v' arising from use of `maxValue' at AlphaBeta.hs:12 in the following code: module AlphaBeta where -- Game states are instances of MinimaxState class MinimaxState st where successors:: st -> [(action,st)] terminal:: st -> Bool utility:: (Ord v) => st -> v minimaxDecision state = filter (\(_,st) -> utility st == v) (successors state) where v = maxValue state maxValue:: (MinimaxState state, Ord v) => state -> v maxValue state = if terminal state then utility state else (foldl max x xs) where (x:xs) = map (minValue.snd) (successors state) minValue:: (MinimaxState state, Ord v) => state -> v minValue state = if terminal state then utility state else (foldl min x xs) where (x:xs) = map (maxValue.snd) (successors state) Any hints would be appreciated. -Arjun

4 4

RE: [Haskell-cafe] Parsec Problem
by Bayley, Alistair 27 Jul '04

27 Jul '04

> I copied this example exactly from the page > http://www.cs.uu.nl/people/daan/download/parsec/parsec.html > > price = lexeme (do{ ds1 <- many1 digit > ... > However attempting to compile it gives the error message > ... > I wish I knew what that meant. If someone could explain it > and tell me what's wrong, I'd appreciate it. The documentation for Parsec is a bit out-of-date; some things still work as described, and some things have changed. You'll have to browse the current libraries at the same time as reading the Parsec documentation to determine if a particular feature is still working as described, or if there's a newer (better?) way of doing the same thing. If you want to learn how to use the libraries, I recommend writing some very simple character/string parsers first, to see how the combinators work. Back to your parser... A lexeme parser (as described in the Parsec document) is one that consumes any trailing whitespace after the token has been read, so as to leave the next non-whitespace token ready on the input stream. The easiest way to fix the price parser is simply to add Text.ParserCombinators.Parsec.Char.spaces after the last digits have been read. price = do { ds1 <- many1 digit ; char '.' ; ds2 <- count 2 digit ; spaces -- eat trailing whitespace ; return (convert 0 (ds1 ++ ds2)) } <?> "price" where convert n [] = n convert n (d:ds) = convert (10*n + digitToInt d) ds (The lexeme function is now a record field accessor in Text.ParserCombinators.Parsec.Token. There is a data type called TokenParser, of which lexeme is one field. There's probably a way to write the price parser using TokenParser and the lexeme function/field, but I haven't figured this out yet.) Alistair. ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

1 0

Re: [Haskell-cafe] Parsec Problem
by J.Garrett.Morris＠Dartmouth.EDU 27 Jul '04

27 Jul '04

--- haskell(a)alias.spaceandtime.org wrote: I wish I knew what that meant. If someone could explain it and tell me what's wrong, I'd appreciate it. --- end of quote --- Lexeme is actually a selector function over the TokenParser record. In the previous section (also on lexical analysis), he included the code: module Main where import Parsec import qualified ParsecToken as P import ParsecLanguage( haskellStyle ) lexer :: TokenParser () lexer = makeTokenParser (haskellDef { reservedOpNames = ["*","/","+","-"] }) whiteSpace= P.whiteSpace lexer lexeme = P.lexeme lexer -- <-- here's lexeme symbol = P.symbol lexer natural = P.natural lexer parens = P.parens lexer semi = P.semi lexer identifier= P.identifier lexer reserved = P.reserved lexer reservedOp= P.reservedOp lexer Once you've done that, the sample code should work fine. /gXm

1 0

Type Theory? Relations
by haskell＠alias.spaceandtime.org 27 Jul '04

27 Jul '04

Hello, I have a question that may pertain to type theory. According to Enderton, one of the ways to define an ordered pair (a,b) is {{a},{a,b}}. A relation is defined as a set of ordered-pairs. A map, of course, is a single-valued relation. Given all that, suppose I have a "FiniteMap Int String" in Haskell. This is, according to the definitions above, a "Set (Int,String)". An element of that has type (Int,String), which contains {Int,String}. But that can't exist because a Set contains only elements of one type. What I'm getting at is that it seems that a Relation should be defined type Relation a = Set (a,a) rather than type Relation a b = Set (a,b) so that we don't have this problem. Thanks.

2 1