March 2006 - Haskell-prime

RE: New syntax
by Simon Peyton-Jones 31 Mar '06

31 Mar '06

| > Template Haskell breaks expressions with $, | | It's very bad that with TH enabled you cannot write sections of the form ($ x) | anymore which are sometimes very handy. I'd prefer it if TH only sprang into action when you wrote $x or $(f x) That is, no space after the $. If you put spaces, you should get the H98 $. If anyone feels like fixing this, I think it'd be a good thing to do. S

2 1

RE: FFI, safe vs unsafe
by Simon Marlow 31 Mar '06

31 Mar '06

On 30 March 2006 21:40, Claus Reinke wrote: >> I updated the ForeignBlocking wiki page with what I believe is the >> current state of this proposal; see > > didn't I mention that "concurrent" may be inappropriate and > misleading, and that I think it is bad practice to rely on the > programmer annotating the dangerous cases, instead of the safe cases? > > wouldn't the safe approach be to assume that the foreign call may do > anything, unless the programmer explicitly tells you about what things > it won't do (thus taking responsibility). This is the way it is right now in GHC: the default is "safe", and safe means both reentrant and concurrent. This is for the reason you give: the default should be the safest, in some sense. However, John has argued, and I agree, that requiring the combination of concurrent and reentrant to be supported is too much, and furthermore is often unnecessary. So we can't have the default (unanotated) foreign call be something that isn't required by the standard. Hence, the proposal states that concurrent foreign calls have to be annotated as such, and it is the specific case of 'concurrent' alone, as opposed to 'concurrent nonreentrant' that is an extension. http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/ForeignBlo cking Cheers, Simon

2 1

RE: Pre-emptive or co-operative concurrency (was: Concurrency)
by Simon Marlow 31 Mar '06

31 Mar '06

On 30 March 2006 22:01, Claus Reinke wrote: >>> the point being: the FFI says something about how to integrate >>> foreign and Haskell memory management; should it also say something >>> about threadability of foreign code (wrt to scheduling, and wrt >>> thread-safety)? >> If Haskell' includes concurrency then of course it must say something >> about the behaviour of foreign calls with respect to concurrency (if >> that's what you mean by "threadability"). Is that what you're >> asking? > > yes. I'm all for Haskell' having both ffi and concurrency, but that > means that the feature interactions have to be investigated. I know > you made a start on that, so I was just pointing out some further > corners that may need looking into: > > - if foreign code is used in Haskell' scheduling, what properties of > the foreign code need to be specified, how does long-running > foreign code interact with the scheduler, and are the current > annotations sufficient for all that? > > - if Haskell' code involving concurrency is foreign exported, what > does that mean? does it work out of the box, or what are the > limitations? Rather than answer these directly, I'll point to this paper which addresses these questions and more: http://www.haskell.org/~simonmar/papers/conc-ffi.pdf GHC implements exactly what is in that paper. For Haskell', I expect we won't require all of it, some will be relegated to extensions. > I was looking for a practical example involving concurrency and ffi > in such a way as to expose some of the questions that need to be > answered. you're mentioning forkIO, so that's an example of such > questions: why shouldn't we be able to foreign export that? The (slightly glib) answer to this question is "because it doesn't have a legal FFI type". If you want to foreign export forkIO, you'll have to give me a version that I can foreign export. And that involves some important decisions: just where do you want to run the IO() action, on the server, or the client? If it's on the server, then how to I get the IO() in the first place? YOu must provide some more API functions to build a FunPtr(IO()), or something. (by server I mean the library proferring the forkIO API, by client I mean the client of this API). Cheers, Simon

1 0

MVar semantics: proposal
by John Meacham 31 Mar '06

31 Mar '06

Based on discussion, I'd like to offer up this concrete proposal when it comes to MVars, IORefs, and what we can guarentee when it comes to their interaction with concurrency. My wording can use some cleaning up but I want to get this out there while it is fresh in mind and before I forget the subtleties that led me to this formulation. its primary goals are * let us reason sanely about and provide the tools needed to write concurrent programs. * not break SMP scalability. programs we write now should work on systems of the future. some definitions action - a memory read/write either MVar or IORef that is theoretically observable by a different thread, not necessarily atomic or ordered. sequence point - exactly and only the actions putMVar and takeMVar in a given thread, for some sequence of actions before a sequence point, and some sequence of actions after it. another particular thread may observe those actions in an arbitrary order, at an arbitrary time in the future, except actions may not cross the sequence point boundry. for example thread 1 : A B SP C thread 2 may observe A B C or B A C, but not A C B. another formulation would be that if any action after the sequence point is observable, then all actions before it are guarenteed to be observable in the current thread. putMVar and takeMVar are atomic. this is the _one and only_ guarentee when it comes to different threads observing the same memory locations. in particular, IORefs cannot safely be used except in a single-threaded manner. This is a _pairwise guarentee_ between specific threads, for threads 1,2,and 3 where thread 1 is writing to memory. threads 2 and 3 may observe completly different orderings but each is independently subject to the sequence point constraint. You cannot reason about the observable behavior of a group of threads except insofar as what you can infer by applying this rule pairwise to the members of the group. sequence points are _not_ atomic global events. for the case above thread 1: A B SP C thread 2 might see A B C before thread 3 even sees A. however both are guarenteed to see A and B before they see C. just because one thread reaches and passes a sequence point, it does not mean any other thread has done so. how this relates to IORefs: IORefs do not introduce sequence points nor are operations on them guarenteed to be atomic. given the sequence point constraint above, the following rule is needed for safety IORefs must be used in a single threaded manner, when IORefs are protected by an MVar, the MVar _must_ be locked by the same thread that is using the IORefs. so no locking an MVar and then telling another thread to go ahead and modify some IORefs as the other thread may not have even observed the 'locking' sequence point yet. I believe this lets us sanely reason about concurrent accesses to memory and won't hamper SMP scalable implementations of haskell. notes: We should drop atomicModifyIORef since we have MVars, for architectures with only a test and set instruction and no atomic exchange, supporting atomicModifyIORef would entail the same overhead as MVars. atomicModifyIORef also cannot (easily) be implemented on implementations that use update-in-place rather than indirections for thunk updates. IORefs are not even guarenteed to be atomic. so, if thread 1 writes A then B to an IORef, thread 2 is not even guarenteed to see A or B when it reads it. it may see an intermediate value or even crash the system. if however thread 1 creates a sequence point after writing to the IORef and thread 2 waits for that sequence point to be visible (by say waiting on an MVar) then it may safely read the IORef. if you have not guessed, sequence points correspond exactly to where memory barriers need to be placed in the instruction stream or the much more expensive bus locks on architectures that don't support true memory barriers (cough. x86.). Using the weaker memory barrier semantics for sequence points is a concious decision as it is vital vital for reasonable SMP scaling and global atomic sequence points can be simulated when needed with MVars between an arbitrary number of threads by pairwise sequenceing them. (perhaps we can provide some library routines to make this easy if it turns out to be a common thing people want?) John -- John Meacham - ⑆repetae.net⑆john⑈

1 1

RE: thread priorities?
by Simon Marlow 31 Mar '06

31 Mar '06

On 31 March 2006 02:49, John Meacham wrote: > Thinking about it some. I think we will need some sort of very basic > thread priorities. > > honoring these priorities will be _manditory_ for cooperative > implementations but advisory for preemptive ones that meet the > fairness guarentees. priorities are sometimes needed in cooperative > systems to ensure certain things get run, but the fairness guarentees > of preemptive systems make them less important. Another reason to > make them advisory in preemptive implementations is because they > might be using OS level threads and hence not have their own > scheduler to tweak priorities in. > > I am thinking > > threadSetPriority :: ThreadID -> Int -> IO () > threadSetPriority = ... I'd rather not, if we can avoid it. The only rationale I'll offer is that we don't have it in GHC, and people manage to do a lot without priorities. Priorities come with a whole can of worms that I'd rather not deal with. Cheers, Simon

5 4

thread priorities?
by John Meacham 31 Mar '06

31 Mar '06

Thinking about it some. I think we will need some sort of very basic thread priorities. honoring these priorities will be _manditory_ for cooperative implementations but advisory for preemptive ones that meet the fairness guarentees. priorities are sometimes needed in cooperative systems to ensure certain things get run, but the fairness guarentees of preemptive systems make them less important. Another reason to make them advisory in preemptive implementations is because they might be using OS level threads and hence not have their own scheduler to tweak priorities in. I am thinking threadSetPriority :: ThreadID -> Int -> IO () threadSetPriority = ... with a small modification to the progress guarentee saying that when threads of different priorities are runnable, one of the threads of the highest priority will be running. we should also say something about priority inheritance via MVars... but perhaps this is too complicated for the spec and should be left up to the implementations (or just make it always advisory). let me know what y'all think. John -- John Meacham - ⑆repetae.net⑆john⑈

2 2

Specification of newtype deriving
by Twan van Laarhoven 31 Mar '06

31 Mar '06

The Trac page for 'Generalised deriving for newtype' remarks that it is 'difficult to specify without saying "the same representation"'. I assume that no one has tried yet, so I'll take a shot at it. Say we have a declaration of the form: > class C a where > x :: T a -- any type that can contain a > .. > > -- instance declaration, can also be more general > instance Ctx p => C (OldT p) where > x = .. > .. > > newtype NewT p = Constr (OldT p) > deriving C Where p can be any number of type variables and Ctx is a context depending on them. The instance for C NewT can be derived with the following algorithm. The new instance declaration will be: > instance Ctx b => C (NewT b) where > x = wrap_T (x :: T a) > .. Now the details of the wrap function depend on the type T. There are four cases: 1. If T is a type not containg a, i.e. > type T a = T' then define: > wrap_T x = x > unwrap_T x = x 2. If T is exactly the type a, possible applied to arguments: > type T a = a or > type T a = a b .. then define: > wrap_T x = Constr x > unwrap_T x = case x of (Constr x') -> x' 3. If T is a function type: > type T a = T1 a -> T2 a then define > wrap_T f = \arg -> wrap_T2 (f (unwrap_T1 arg)) > unwrap_T f = \arg -> unwrap_T2 (f (wrap_T1 arg)) 4. If T is an abstract data type: > data T a = C1 (T1 a) .. > | .. then define: > wrap_T x = case x of > (C1 x1 ..) -> C1 (wrap_T1 x1) .. > .. > unwrap_T x = case x of > (C1 x1 ..) -> C1 (unwrap_T1 x1) .. > .. With an alternative for each constructor of T. All these wrap/unwrap functions are specific for the type NewT and the definition x. The T in wrap_T should be read as a subscript where T is the actual type, and not as a value named "wrap_T". '..' stands for a repetition of the same principle. Here is also an example from the wiki page: > -- | Unique integer generator monad transformer. > newtype UniqT m a = UniqT (StateT Int m a) > deriving Monad The class is: > class Monad m where > (>>=) :: m a -> (a -> m b) -> m b > .. There is an instance: > instance Monad m => Monad (StateT s m) Now the newtype declaration desugars to (using wr_T for wrap_T and un_T for unwrap_T): > newtype UniqT m a = UniqT (StateT Int m a) > > instance Monad m => Monad (UniqT m a) where > (>>=) = w (>>= :: StateT Int m a) > where > wr_T f = \arg -> wr_T2 (f (un_T1 arg)) -- m a -> (a -> m b) -> m b > un_T1 x = case x of (UniqT x') -> x' -- m a > wr_T2 f = \arg -> wr_T4 (f (un_T3 arg)) -- (a -> m b) -> m b > un_T3 f = \arg -> un_T6 (f (wr_T5 arg)) -- a -> m b > wr_T4 x = UniqT x -- m b > wr_T5 x = x -- a > un_T6 x = case x of (UniqT x') -> x' -- m b Cleaning up leads to: > instance Monad m => Monad (UniqT m a) where > wr_T = \(UniqT a0) a2 -> UniqT > (a0 >>= ( \a3 -> case (a2 a3) of (UniqT x') -> x' )) Which is essentially the same as what the programmer would have written himself. Twan

2 1

RE: Re[2]: important news: refocusing discussion
by Simon Marlow 31 Mar '06

31 Mar '06

On 26 March 2006 03:44, Ross Paterson wrote: > On Sat, Mar 25, 2006 at 05:31:04PM -0800, isaac jones wrote: >> I have no idea if it would work, but one solution that Simon didn't >> mention in his enumeration (below) is that we could find a group of >> people willing to work hard to implement concurrency in Hugs, for >> example, under Ross's direction. > > I'm no expert on Hugs internals, and certainly not qualified to direct > such an effort, but I don't have great hopes for it. Apart from the > fact that Hugs is written in a legacy language and uses a quite a bit > of global state, it also makes heavy use of the C stack, and any > implementation that does that will have trouble, I think. Yes, I don't see an easy way to do it. You could have one OS thread per Haskell thread (let the OS manage the separate C stacks), a giant lock around the interpreter (to protect all the global state), and explicit yield() from time to time to simulate pre-emption. This isn't too bad, but you still have to implement GC somehow, and hence traverse all the live C stacks, and that sounds tricky to me. > I've been assuming that Haskell' was intended to encompass a wide > range of implementations. If that's the case, the key point is that > a Haskell' module that does not use concurrency, but is thread-safe, > ought to work with non-concurrent implementations too. > > To make that work, we'd need two interfaces: > * one for applications that make use of concurrency. This would be > unavailable on some implementations. > * one for thread-safe use of state. This would be available on all > implementations, and authors not requiring concurrency would be > encouraged to use it for maximum portability. Sure, I think this is a point on which we're all agreed. The portable interface could be Control.Concurrent.MVar, perhaps. Cheers, Simon

7 7

Pragmatic concurrency Re: [Haskell-cafe] multiple computations, same input
by Jon Fairbairn 31 Mar '06

31 Mar '06

On 2006-03-28 at 08:02+0200 Tomasz Zielonka wrote: > I wonder if it would be possible to remove the space-leak by running both > branches concurrently, and scheduling threads in a way that would > minimise the space-leak. I proposed this before > > http://www.haskell.org/pipermail/haskell-cafe/2005-December/013428.html > > I would like to hear opinions from some compiler gurus. This is something I've been thinking about on and off for a long time (probably since John Hughes mentioned the case of "average"). I even kept Tomasz's original message in my inbox until today in the hope that I'd get round to sending a response, but my flaky health gets in the way. So here, and I hope people will allow for the fact that I'm half asleep as I write this, is an attempt. There are some observations I'd like to make, and a proposal. Since the proposal relates (in a small way) to concurrency and is, I think worthwhile, I've cc'd this message to haskell-prime. 1) choosing the optimal reduction strategy is undecidable 2) we shouldn't (in general) attempt to do undecidable things automatically 3) Separation of concerns: Pragmatic decisions about evaluation order should be kept separate from the denotational aspect of the code. By this token, seq shouldn't be a function (because it isn't one), but a pragma. The fact that it's shorter to write seq a b than {-# SEQ a #-} b is a matter of syntax, so shouldn't rate highly in language design decisions. Perhaps we want a different syntax for this kind of pragma, but that's a side issue. So, to take Tomasz's example of wc, we want to be able to define it essentially this way: wc cs = (ll, ww, cc) where ll = lines cs ww = words cs cc = length cs but add [a] pragma[s] to the effect that evaluation should be input driven, and that ll, ww, and cc are to be given equal time. Something like {-# STEPPER cs; ROUND_ROBIN ll,ww,cc #-} (please do not take this as a suggestion of real syntax!). The way I would implement this is to add a new primitive, STEP, which is like seq except that it only evaluates its argument until it encounters another STEP. (It really isn't much different to seq). So after the compiler understood the pragma, it would replace wc with this (allowing the compiler to pretend step is a function): wc cs = (ll, ww, cc) where ll = lines cs' ww = words cs' cc = length cs' cs' = foldr (\a -> STEP ll . STEP ww . STEP cc . (a:)) [] cs Evaluation would start as normal (a wrinkle here is that the way I've written it, whichever element of the tuple is evaluated first gets two goes at the start, but that's a compiler detail). when it came to evaluating cs', it would be looking at a thunk something like STEP ll (STEP ww (STEP cc ('x': ...))) update the thunk to (STEP ww (STEP cc ('x': ...))) evaluate ll until (and if) it hits the thunk again, update it to (STEP cc ('x': ...)) evaluate ww until it hits the thunk, update it to 'x' : (STEP ...) evaluate cc, and so on. It seems to me that this wouldn't take much effort to implement, but it would provide a simple means of removing space leaks from a whole bunch of programmes without mangling the source code much. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk

2 2

RE: FFI, safe vs unsafe
by Simon Marlow 31 Mar '06

31 Mar '06

I updated the ForeignBlocking wiki page with what I believe is the current state of this proposal; see http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/ForeignBlo cking Cheers, Simon

3 4