- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Generics Versus Parametric Polymorphism
by Bulat Ziganshin 11 Mar '09

11 Mar '09

Hello Mark, Wednesday, March 11, 2009, 9:11:42 AM, you wrote: > Just wondering if Generics and Parametric polymorphism are one and the same in Haskell. haskell Parametric polymorphism is the same type of thing as Java Generics :) haskell Generics provides ability to define procedures polymorphic by *any* data type with just a fixed number of definitions there are at least dozen of various tools/libraries supporting Generics in some way in haskell, so indeed we are interested to have at least one with guaranteed availability google for "scrap your boilerplate" paper for a description of one of the most popular Generics implementation -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

2 2

Re: [reactive] FRP + physics / status of hpysics
by Wolfgang Jeltsch 11 Mar '09

11 Mar '09

Am Freitag, 6. März 2009 14:34 schrieb Daniel Bünzli: > > without using recursive signal functions, > > If this is because there's this limitation in the frp system you use It is. > then better fix the system. The system is Grapefruit, by the way. And I’m its developer, by the way. :-) I have to say that it’s hard, if not impossible, to combine recursive signal definitions with other features, I want to have. The point of recursive definitions is that you want to turn recursive equations from your problem domain directly into Haskell definitions. This is nice from a user’s point of view but hard from a programmers point of view. Standard Haskell already shows that. While it is possible to define an infinite list of ones by ones = 1 : ones, it is not possible to do the same for sequences of type Seq. The above definition of ones relies very much on the structure of lists. Analogously, the ability to define signals recursively restricts the set of possible signal implementations seriously. Haskell’s recursive definitions are very general. They have to find fixpoints of arbitrary functions over arbitrary type. Therefore, their semantics are rather weak. They give you the least defined fixpoint. The consequence is that you get bottom if you use something like x = 0 * x although x = 0 might be what you prefered. What I want to say is that coming up with a signal implementation that allows Haskell recursion and has other advantages at the same time is a big challenge. There are three features, you might want from a signal implementation: 1. support for recursive signal definitions using Haskell equations 2. memoization (for avoiding time leaks, for example) 3. signals which may depend on external sources I tried hard to support 2 and 3 well in Grapefruit. Fran has 1 but has problems with 2 and 3. I don’t know whether Reactive has a solution for 2 in the context of recursive definitions, i.e., whether the space and time leak problems of Fran were solved. I think, it has at least problems with 3. For me, 2 and 3 are more important than 1. One reason is that 1 has other problems than being in conflict with 2 and 3. The result of a recursively defined signal depends on when sampling occurs. Since a recursive definition tends to result in accumulation of values, errors introduced by sampling may accumulate too. So you have to use clever approximation algorithms in addition. My new idea is to view the problem in a different way. Let’s take the problem where the position of a ball is the integral of the difference between the mouse position and the ball position. As far as I can see, the transformation of the mouse position signal into the ball position signal forms a linear system. So the ball position signal is the mouse position signal convoluted with another signal. If we would have a function that performes convolution, we could probably implement many problems using this function. Using convolution would let us get rid of the problems with accumulating errors. I suppose that most of the recursive definitions you would use in FRP are differential or integral equations. Let’s look at the equation for the ball-following-the-mouse example: ballPos = integral (mousePos - ballPos) ballPos can be represented in terms of mousePos as follows: ballPos = (exp . negate) * mousePos where * means convolution. We could provide a library which supports common stuff like distance-dependent acceleration, friction etc. Of course, you could say that now the programmer isn’t able anymore to enter his equations directly which isn’t nice. However, this situation is not different to other areas. For example, you cannot write x = 5 - x / 2 and expect x to be 10 / 3. Instead, you have to transform the equation first. > Soon or later it you'll want it elsewhere. A recursive reactive signal just > means that some of what your reactive program computed will be > usefull/necessary for the next step. You can do this with convolution, I think. By the way, continuous signals don’t have steps. These are just introduced by sampling. > You'll see that happen very quickly (e.g. any simple reactive state > machine). “State machine” sounds like a discrete problem. You can use accumulation over event sequences here (as, for example, provided by the scan function in FRP.Grapefruit.Signal.Discrete). By the way, the adress of the Grapefruit mailing list is grapefruit(a)projects.haskell.org, not grapefruit(a)haskell.org. Best wishes, Wolfgang

1 2

Re: [Haskell-cafe] Generics Versus Parametric Polymorphism
by Sean Leather 11 Mar '09

11 Mar '09

Hi Mark, > Just wondering if Generics and Parametric polymorphism are one and the same > in Haskell. > > I read (somewhere!) an article stating that generics might be included in > Haskell Prime but I thought that they’re already included as parametric > polymorphism. > To see the current status of Haskell Prime, visit the Trac page: http://hackage.haskell.org/trac/haskell-prime/ > Did I misread something? Or is generics in Haskell referring to something > completely different. > I'm not sure which article you read, but there is a lot of ambiguity in the term "generics." Depending on whom you talk to, it means a different thing. But I can give you some pointers to where you can learn about many of the possible interpretations. The following paper gives a useful vocabulary for describing the different types of "generics." Just by reading section 2 you can see how confusing it is when so many techniques are referred to as generic programming. For example, parametric polymorphism is an example of genericity by type here. In the Haskell world, (as Don said) it's not considered generics, but in Java (as Alp remarked), it's called generics. http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/dgp.pdf There's a comparison paper from 2003 that presents language support for generics in C++, ML, Haskell, Eiffel, Java, and C#. Things have changed a bit since then, but it's an interesting read. http://ece-www.colorado.edu/~siek/pubs/comparing_generic_programming03.pdf "Generics" in Haskell has come to be known as datatype-generic programming. In the past, it has been labeled polytypism, structural polymorphism, or typecase. This refers to the technique of writing functions or programs that work for many types and have knowledge about the structure of the type (mentioned by Bulat). Generic Haskell is a (non-standard) language extension to Haskell. It was used to explore the possibilities of datatype-generic programming (DGP) with Haskell. The following paper compares varying approaches of DGP to Generic Haskell. http://people.cs.uu.nl/johanj/publications/ComparingGP.pdf In the last few years, people have seen the power of Haskell's type system, and GHC has developed some interesting extensions to that type system. As a result of this and the difficulty with maintaining language extensions external to a compiler (e.g. Generic Haskell), libraries for DGP in Haskell have become much more common and powerful. The following article compares a large number of these libraries. http://www.cs.uu.nl/wiki/Alexey/ComparingLibrariesForGenericProgrammingInHa… Lastly, since I started working in this area over a year ago, I've been collecting references to published research. My citations are on CiteULike: http://www.citeulike.org/user/spl There are tags for "generics" and "datatype-generic" that give you a narrower view on the collection. http://www.citeulike.org/user/spl/tag/generics http://www.citeulike.org/user/spl/tag/datatype-generic Hope this helps to answer your questions. Regards, Sean

1 0

FRP + physics / status of hpysics
by Peter Verswyvelen 11 Mar '09

11 Mar '09

Regarding hpysics, did anybody did some experiments with this? The blog seems to be inactive since december 2008; has development ceased? Do alternatives exist? Maybe good wrappers (hopefully pure...) around existing engines? Integrating hpysics with Grapefruit might be a good topic for the Hackaton, trying to make a simple game (e.g. Pong or Breakout) without using recursive signal functions, but with correct collision response and better-than-Euler integration, all handled by the physics engine. Other FRP engines could be tried, but Grapefruit hacking is already a topic on the Hackaton, so it would combine efforts. It feels as if none of the current FRP engines can handle physics correctly, since a typical physics implementations requires "time backtracking", in the sense that when you want to advance the current simulation time by a timestep, collision events can happen during that time interval, and hence the FRP engine can only advance time until the earliest collision event. So to do physics *with* an FRP engine, the implementation and maybe even semantics of the FRP system might need to be changed. *Using* a physics engine as a blackbox inside an FRP system might make more sense. Thanks to Wolfgang Jeltsch and Christopher Lane Hinson for having a discussion with me that lead to this. Interestingly a similar discussion was help by other people in the Reactive mailing list at the same time :-) Cheers, Peter Verswyvelen

7 13

do nmergeIO or mergeIO preserve order?
by Anatoly Yakovenko 11 Mar '09

11 Mar '09

do nmergeIO or mergeIO preserve order? or not preserve order?

3 7

Re: [Haskell-cafe] Generics Versus Parametric Polymorphism
by Don Stewart 11 Mar '09

11 Mar '09

mark.spezzano: > Hi, > > Just wondering if Generics and Parametric polymorphism are one and the same in > Haskell. > > I read (somewhere!) an article stating that generics might be included in > Haskell Prime but I thought that they’re already included as parametric > polymorphism. > > Did I misread something? Or is generics in Haskell referring to something > completely different. Parametric polymorphism is kinda boring in Haskell -- since it's been there since the beginning. We tend to reserve the term "generics" for higher order, and fancier, polymorphism. These kinds of things: http://hackage.haskell.org/packages/archive/pkg-list.html#cat:generics -- Don

2 1

Generics Versus Parametric Polymorphism
by Mark Spezzano 11 Mar '09

11 Mar '09

Hi, Just wondering if Generics and Parametric polymorphism are one and the same in Haskell. I read (somewhere!) an article stating that generics might be included in Haskell Prime but I thought that they’re already included as parametric polymorphism. Did I misread something? Or is generics in Haskell referring to something completely different. Cheers, Mark Spezzano No virus found in this outgoing message. Checked by AVG. Version: 7.5.557 / Virus Database: 270.11.9/1993 - Release Date: 10/03/2009 7:19 AM

1 0

Re: [Haskell-cafe] Parallel programming (threads, cores, processors)
by Sterling Clover 11 Mar '09

11 Mar '09

On Mar 10, 2009, at 10:38 PM, Mark Spezzano wrote: > Hi, > > I’m an experienced software developer, but a bit of a newbie when > it comes to parallel processing in any language. > > Question 1: > > Is there any programmatic change in dealing with multiple threads > as opposed to multiple cores in most languages (specifically Haskell)? > > That is, to write multiple threads you normally “spin-off” a new > thread which runs in parallel along with other threads. Is Haskell > smart enough to do this by magic by itself, or would I need to tell > it explicitly : Run thread A whilst running thread B > > Also, what about multicore architectures? Do I have to tell the > language to spin off two separate programs to run on each core and > then somehow use some kind of communications to exchange data? > GHC's parallel runtime, which is what we're really talking about when we're talking about Haskell concurrency, operates roughly like this: Threads at the language level are "green" -- i.e. they are conceptually threads, and the runtime schedules them as it sees fit, but they aren't tied to any given core for execution. You can create (using the forkIO primitive) as many new threads as you like. If you then execute your program with runtime options (i.e. +RTS -N 2 for two cores) that specify how many actually operating system threads you want, the runtime will then map your set of green threads onto OS threads (and presumably cores) in what it thinks is an efficient manner. Communication between threads is via MVars, which are like one-item mailboxes, and are one concurrency primitive, or TVars, which are for Software Transactional Memory. > I also assume that, in theory it would be possible to have multiple > threads running on each core. Say, 3 threads spawned from program 1 > running on core 1 and 5 threads on program 2 running on core 2 > Generally, the runtime system moves threads between cores as it sees fit. However, you can tie threads to particular cores using other concurrency primitives (i.e. runInBoundThread). See the documentation for Control.Concurrent (http://www.haskell.org/ ghc/docs/latest/html/libraries/base/Control-Concurrent.html) and Control.Concurrent.STM (http://www.haskell.org/ghc/docs/latest/html/ libraries/stm/Control-Concurrent-STM.html) for more details. > Likewise I would suppose that it would be possible to have > multiprocessors, each potentially multicore, each core running > multiple threads. > Yep, see above, although I don't know of any way to distinguish between cores and processors as you're really just mapping to OS threads (i.e. capabilities) and relying on the OS to distribute these among cores and processors reasonably. > Question 2: > > In light of the above statement, is the programmatic change > DIFFERENT for dealing with each of > > a) Multithreading in Haskell versus > > b) Multicores in Haskell verus > > c) Multiprocessors in Haskell > Generally, you'll want to write concurrent Haskell code as an abstraction to think about things that are "naturally" concurrent -- i.e. which are best thought of as happening at the same time. At runtime, you specify how many OS capabilities you want to map onto. For algorithms where you want computations to happen in parallel, there's an entirely different set of operations, based around `par` (see Control.Parallel [http://www.haskell.org/ghc/docs/latest/html/ libraries/parallel/Control-Parallel.html] and Control.Parallel.Strategies). In neither case should you need, generally, to concern yourself with the details of threads vs. cores vs. processors. Cheers, Sterl.

1 0

Parallel programming (threads, cores, processors)
by Mark Spezzano 11 Mar '09

11 Mar '09

Hi, I’m an experienced software developer, but a bit of a newbie when it comes to parallel processing in any language. I’ve done some multithreading in Java and C++ on a single processor, single core architecture only. First, let me define some terms: Multithreading: this is multiple processes running on one processor and is the conventional way to do parallel programming Multicore: this is when we have two (or more) cores within the one CPU Multiprocessor: this is when we have multiple CPUs Question 1: Is there any programmatic change in dealing with multiple threads as opposed to multiple cores in most languages (specifically Haskell)? That is, to write multiple threads you normally “spin-off” a new thread which runs in parallel along with other threads. Is Haskell smart enough to do this by magic by itself, or would I need to tell it explicitly : Run thread A whilst running thread B Also, what about multicore architectures? Do I have to tell the language to spin off two separate programs to run on each core and then somehow use some kind of communications to exchange data? I also assume that, in theory it would be possible to have multiple threads running on each core. Say, 3 threads spawned from program 1 running on core 1 and 5 threads on program 2 running on core 2 Likewise I would suppose that it would be possible to have multiprocessors, each potentially multicore, each core running multiple threads. Question 2: In light of the above statement, is the programmatic change DIFFERENT for dealing with each of a) Multithreading in Haskell versus b) Multicores in Haskell verus c) Multiprocessors in Haskell References or info appreciated. Just curious. Mark No virus found in this outgoing message. Checked by AVG. Version: 7.5.557 / Virus Database: 270.11.9/1993 - Release Date: 10/03/2009 7:19 AM

1 0

Parallel programming in Haskell (threads, cores, processors)
by Mark Spezzano 11 Mar '09

11 Mar '09

Hi, I’m an experienced software developer, but a bit of a newbie when it comes to parallel processing in any language. I’ve done some multithreading in Java and C++ on a single processor, single core architecture only. First, let me define some terms: Multithreading: this is multiple processes running on one processor and is the conventional way to do parallel programming Multicore: this is when we have two (or more) cores within the one CPU Multiprocessor: this is when we have multiple CPUs Question 1: Is there any programmatic change in dealing with multiple threads as opposed to multiple cores in most languages (specifically Haskell)? That is, to write multiple threads you normally “spin-off” a new thread which runs in parallel along with other threads. Is Haskell smart enough to do this by magic by itself, or would I need to tell it explicitly : Run thread A whilst running thread B Also, what about multicore architectures? Do I have to tell the language to spin off two separate programs to run on each core and then somehow use some kind of communications to exchange data? I also assume that, in theory it would be possible to have multiple threads running on each core. Say, 3 threads spawned from program 1 running on core 1 and 5 threads on program 2 running on core 2 Likewise I would suppose that it would be possible to have multiprocessors, each potentially multicore, each core running multiple threads. Question 2: In light of the above statement, is the programmatic change DIFFERENT for dealing with each of a) Multithreading in Haskell versus b) Multicores in Haskell verus c) Multiprocessors in Haskell References or info appreciated. Just curious. Mark No virus found in this outgoing message. Checked by AVG. Version: 7.5.557 / Virus Database: 270.11.9/1993 - Release Date: 10/03/2009 7:19 AM

1 0