- Haskell-Cafe - Haskell.org

optimising for vector units
by Matthew Roberts 26 Jul '04

26 Jul '04

Hi, Does anybody know if any of the Haskell compilers are able to optimise for vector units (like MMX, SSE(2), 3D_Now! and AltiVec)? My investigations have revealed that c requires special programming constructs to make the most of these processor capabilites (i.e. the compiler is not able to work it out for itself). Is there any work on getting haskell compilers to work this kind of thing out? Cheers, Matt

3 2

Trouble with types
by Kari Pahula 23 Jul '04

23 Jul '04

I'm new to Haskell, as you can probably tell... I have the following data types: data Real a => Energy a = Energy a deriving (Eq, Ord, Show) data Real a => HeatC a = HeatC a deriving (Eq, Ord, Show) data Object h c = Object {energy :: (Energy h), heatc :: (HeatC c)} deriving (Eq, Show) data Real a => Temp a = Temp a deriving (Eq, Ord, Show) I'd like to make a function to calculate the temperature of an object. Physically this is the total heat times the heat capacity. I tried this with the following: temp :: (Real a) => Object (Energy a) (HeatC a) -> Temp a temp Object (Energy e) (HeatC c) = Temp e*c But this fails in hugs with: ERROR "temp.hs":22 - Constructor "Object" must have exactly 2 arguments in pattern What's the syntax to use here? Should I do this in some other way? Should I use newtype here instead of data?

4 4

Re: generalised algebraic data types, existential types, and phantom types
by Jim Apple 23 Jul '04

23 Jul '04

I tried to post this to gmane.comp.lang.haskell.general, but it never got there - it may belong here anyway. Abraham Egnor wrote: > Is there any closer approximation [of GADTs] possible? {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} data Term a = forall b . (EqType a b, EqType b Int) => Lit Int | forall b . (EqType a b, EqType b Int) => Inc (Term Int) | forall b . (EqType a b, EqType b Bool) => IsZ (Term Int) | If (Term Bool) (Term a) (Term a) | forall b . Fst (Term (a,b)) | forall b . Snd (Term (b,a)) | forall b c . (EqType a (b,c))=> Pair (Term b) (Term c) class EqType a b | a->b, b->a instance EqType a a Unfortunately, I can't seem to write an eval function: eval (Lit a) = a gives Inferred type is less polymorphic than expected Quantified type variable `b' is unified with `Int' When checking an existential match that binds The pattern(s) have type(s): Term Int The body has type: Int In the definition of `eval': eval (Lit x) = x Any ideas? Jim

2 1

Data.Set subset function?
by Graham Klyne 22 Jul '04

22 Jul '04

I don't see a subset function in Data.Set. What is the preferred way to define this? I currently have: a `subset` b = isEmptySet (a `minusSet` b) (Hmmm... does library style prefer `subset`, `subsetOf`, `isSubset`, `isSubsetOf` ?) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

RE: [Haskell-cafe] STG optimization
by Simon Marlow 21 Jul '04

21 Jul '04

On 20 July 2004 22:58, 7253146(a)informatica.alumnos.uma.es wrote: > So far so good. Nonetheless, some doubts have arisen when I have > started to try to add updating. In the paper, implementation for > "update in place" is extensively discussed, although it is said it > could greatly increase the memory space usage. ¿Has this risk been > measured? I think deforestation can minimize the risk; however, as > far as I know, deforestation is only applied to lists. Nowadays GHC doesn't do update-in-place. We removed update-in-place when we re-implemented the code generator and RTS back in version 4.00. There were two reasons: - update-in-place (and its friend, return-in-registers) turned out to be hugely complex when combined with all the other optimisations that GHC does. - we achieve much of the same benefit by adding unboxed tuples to the language and using the "Constructed Product Result" optimisation. CPR is now done by the strictness analyser. Nevertheless, for a while we still did update-in-place when the code genreator could statically determine that there was an update frame on the top of the stack when building a constructor application. But this could only be done when the constructor application contained no pointers - because otherwise the update-in-place code has to deal with the complexities of mutation in a generational garbage collector. But when combined with concurrency, even this kind of update-in-place is difficult, because it might be that another thread is waiting on the result of the thunk being evaluated, and the update code has to wake up that thread. So now, all updates go through one carefully optimised piece of code in the runtime. > But the STG paper ignores an optimization readyly available to me: > whenever a constructor is allocated (constructor's register > allocation aside, since the push/enter - eval/apply paper says GHC no > longer supports it), the STG machine (the one described by the paper) > takes heap space for it, although an update (indirection or copying) > is going to be done most of times. This leads to potentially bad heap > space usage and more garbage collections. > > I think update frames may be detected by the constructor allocation > code, so it could determine whether to allocate a new constructor or > build it over the closure to be updated. This could be achieved by > marking continuations and update frames in the stack, so constructor > allocation code could distinguish between them. This is inconvenient > because common continuations should remove the mark too, so I do not > like it. Yes you could do this. Don't forget to take into account the complications I mentioned above, though (much easier if you don't have generational collection and concurrency). Also you have to know whether the thunk is big enough to be updated with the constructor application. Cheers, Simon

1 0

Sets and Monads and comprehensions
by Graham Klyne 21 Jul '04

21 Jul '04

A few months ago, there was a discussion here about defining Set to be a Monad, starting with: [1] http://www.haskell.org/pipermail/haskell-cafe/2004-March/005988.html in response to which, SPJ pointed out that a Set cannot be a Monad: [2] http://www.haskell.org/pipermail/haskell-cafe/2004-March/005995.html I found myself treading a path which led me to asking the same question as [1]. Given the answer [2], I'd like to stand back a little and ask if there's another way to tackle my niggle: what I'm interested in is a set comprehension expression that is analogous to a list comprehension expression; e.g. in: [[ > import Data.Set > > type AtomicConcept = String -- named atomic concept > type AtomicRole = String -- named atomic role > > type AtomicConcepts a :: AtomicConcept -> (Set a) > type AtomicRoles a :: AtomicRole -> (Set (a,a)) > > type Interpretation a :: (Set a,AtomicConcepts a,AtomicRoles a) ... > iAL (idom,ic,ir) (ALAll r c) = mkSet [ a | (a,b) <- setToList (ir r) > , b `elementOf` ir c ] ]] is there a common or similar idiom to achieve the same effect without converting the set to a list and back? I did also find myself wondering if there was a role for unfold (or similar) here. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

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

21 Jul '04

Hi. I have been reading recently the STG machine paper by Simon Peyton-Jones. It is relatively easy to follow the explanation, though the formal description of operational semantics is hard to understand. In order to fully understand it, I have started to implement a C-based mini STG machine, implementing the obvious compilation schemes according to the STG paper. Of course, I have not implemented most of optimizations: environment management is very rudimentary, it has three stacks (pointer args, primitive args and continuations) for simplicity, etc. At the moment I have a beatiful tree-reduction STG machine. So far so good. Nonetheless, some doubts have arisen when I have started to try to add updating. In the paper, implementation for "update in place" is extensively discussed, although it is said it could greatly increase the memory space usage. ¿Has this risk been measured? I think deforestation can minimize the risk; however, as far as I know, deforestation is only applied to lists. But the STG paper ignores an optimization readyly available to me: whenever a constructor is allocated (constructor's register allocation aside, since the push/enter - eval/apply paper says GHC no longer supports it), the STG machine (the one described by the paper) takes heap space for it, although an update (indirection or copying) is going to be done most of times. This leads to potentially bad heap space usage and more garbage collections. I think update frames may be detected by the constructor allocation code, so it could determine whether to allocate a new constructor or build it over the closure to be updated. This could be achieved by marking continuations and update frames in the stack, so constructor allocation code could distinguish between them. This is inconvenient because common continuations should remove the mark too, so I do not like it. Another (my favourite) similar solution should be introduce a new stack only for update frames, but still pushing code labels for updating in the continuation stack (which could still be merged with the primitive args stack): this way, constructor's code can still simply jump to the next "continuation" (the update code should be responsible of popping the update stack), and constructor allocation code can simply test if the "continuation" on top of the stack is a real continuation, so it can safely take newly allocated heap space for the constructor, or it is an update (perhaps by testing for equality with the top of the update stack), so the code should test if the constructor closure can be overwritten over the closure to be updated. To ilustrate my thoughts: \begin{code} some_func <some_args> = let b = <some_expression> in SomeConstructor { b, some_stuff } some_other_func <some_other_args> = let a = some_func { some_other_stuff } in case a of <some_alternatives> \end{code} In the above piece of core STG language, when the "a" closure is entered and finally "SomeConstructor" must be allocated, the code of "some_func" should check if the continuation leads to an update (in this case, an update of "a") or an continuation. In this case it leads to an update, so then the code should check if the update closure ("a") is large enough, and, in that case, build the constructor closure over it. Maybe this technique is irrelevant for performance, too expensive to implement, or having a separated update stack is too inconvenient, or these effects are achieved by other ways? Thanks in advance Jose David --------------------------------------------- Este mensaje lo ha enviado un Alumno de la Universidad de Malaga. http://www.alumnos.uma.es/

2 1

Re: [Haskell-cafe] How do I include polymorphic function type signatures in a data element ?
by Crypt Master 20 Jul '04

20 Jul '04

*grin* its so obvious once you know the answer :-) Thx ----Original Message Follows---- On Tue, 20 Jul 2004, Crypt Master wrote: > Exmaple: > > <CODE> > type Fitness = Integer > data Population a = Population [(Fitness, a)] > deriving (Show) > > data GAParams = GAParams { randomNums :: [Integer] , > someFunc :: (Int->Int->(Population a))} > </CODE> Like for 'Population a' you have to specify a type parameter for 'GAParams', i.e. | v data GAParams a = GAParams { randomNums :: [Integer] , someFunc :: (Int->Int->(Population a))} _________________________________________________________________ Protect your PC - get McAfee.com VirusScan Online http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963

1 0

How do I include polymorphic function type signatures in a data element ?
by Crypt Master 20 Jul '04

20 Jul '04

Hi How do I include polymorphic function type signatures in a data element ? Exmaple: <CODE> type Fitness = Integer data Population a = Population [(Fitness, a)] deriving (Show) data GAParams = GAParams { randomNums :: [Integer] , someFunc :: (Int->Int->(Population a))} </CODE> This errors with parse input error on '}'. However something like this works fine: <CODE> data GAParams = GAParams { randomNums :: [Integer] , someFunc :: (Int->Int->GAParams) } /<CODE> I am just having issues with polymorphic types. Any ideas ? The context is included below in case it helps: <CODE> import Random type Fitness = Integer data Population a = Population [(Fitness, a)] deriving (Show) data GAParams = GAParams { randomNums :: [Integer] , someFunc :: (Int->Int->GAParams) } gaSolutionSpaceFrom :: Population a -> GAParams -> [Population a] gaSolutionSpaceFrom p gaParams = (evolvePopulation p gaParams) : gaSolutionSpaceFrom p newGAParams where (r,rs) = splitAt (length pl) (randomNums gaParams) Population pl = p newGAParams = (gaParams{randomNums=rs}) evolvePopulation :: Population a -> GAParams -> Population a evolvePopulation p gaParams = (mutate (cross (select p))) selectMatingPoolByRouletteWheel :: Population a -> GAParams -> Population a selectMatingPoolByRouletteWheel (Population popList) gaParams = (Population [ (rwSelect rw rnd) | rnd <- rndNums ]) where rw = createRW (Population popList) rndNums = (randomNums gaParams) rwSelect :: [(Fitness, a)] -> Fitness -> (Fitness, a) rwSelect [] _ = error "rwSelect random number outside roullete wheel range or list empty" rwSelect ((x,a):xs) z = if x <= z then rwSelect xs z else (x,a) createRW :: Population a -> [(Fitness, a)] createRW (Population xs) = (scanl1 f xs) where f (n,a) (m,b) = (n + m, a) select p = p cross p = p mutate p = p _________________________________________________________________ MSN 8 with e-mail virus protection service: 2 months FREE* http://join.msn.com/?page=features/virus

2 1

migrating from python
by paolo veronelli 14 Jul '04

14 Jul '04

I'm working on semantics and triples (RDF & co) Python code for inference in based totally on dictionaries (associative arrays ??),nested three or four times. The result is astonishing me:compact beautiful modular and extremely readable. I imagine that haskell way should be different but I'm in the dark. As the stream of triples coming from outside estabilishes the actions to be done for inference,the searching through keys (the words that form any triple) is the main job:every time I pick up a triple I have to enlarge the knowledge more or less "near" the resources represented by the words. And after I have produced (possibly) some new inferred triples surely I have to reswitch on some already read triples, matching a pattern. All these are very natural with dictionaries, so I'd like to figure out the haskell view. Thanks for your quiteness and answers Paolino -- ....lotta dura per la verdura

3 2