- Haskell-prime - Haskell.org

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 30 Mar '06

30 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

Re: seq as a class method
by John Hughes 30 Mar '06

30 Mar '06

>it seems that there is not yet a ticket about putting seq into a type class >(again). > >In my opinion, having seq available for every type is a serious flaw. One >problem is that the law f = \x -> f x doesn't hold anymore since the equation >is false for f = _|_. There was also a discussion on one of the mailing >lists some time ago which revealed that the Monad instance for IO doesn't >satisfy the monad laws because of the availability of seq for IO, I think. > >In addition, the automatic definition of seq for every type can make >implementation details visible which were thought of as completely hidden. >For example, it might make a difference whether one uses data or newtype for >a one-alternative-one-field datatype, even if the data constructor is hidden. > >I therefore propose to declare a class like this: > > class Seq a where > seq :: a -> b -> b > > Oh please, no. This sounds like a good idea in principle, but it was a nightmare in practice. First, the implementation details and the difference between _|_ and const _|_ make a difference to space behaviour, and one needs a way to control that. Hiding the differences can make space leaks *impossible* to fix. Secondly, the need to insert and remove Seq contexts from type signatures during space debugging is a major overhead. In my practical experience such overheads made some desirable refactorings impossible to carry out in the time available for the project. Thirdly, the laws one loses are "nearly true" anyway, and that's very often enough. See "Fast and loose reasoning is morally correct", POPL 2006. We don't need to give up anything to make reasoning *as though* such laws held sound, in most cases. John

8 9

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

30 Mar '06

On 30 March 2006 12:44, Claus Reinke wrote: > so if we take that hypothetical example of foreign exporting GHC's > concurrency support, can we assume that the (IO a)s implemented in > foreign code will be given their own OS thread when using that > concurrency library? all of them, or only the non-atomic ones? I'm sorry, I completely fail to see what you're getting at with this line of discussion. Could you say in more detail how you expect to provide access to concurrency via the FFI? And what the point of it is? (it's not obvious how to foreign export forkIO, for example). > 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? Cheers, Simon

2 1

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

30 Mar '06

On 29 March 2006 17:34, Neil Mitchell wrote: >> context-switches happen only on specific events, which every >> thread will usually engage in, although it need not always do so: >> >> 1 only calls to yield >> 2 any calls to concurrency library api >> 3 any allocation > > The Yhc concurrency switches every n instructions, and therefore even > an "evil" thread cannot lock up the system. > > Of course, even with fully pre-emptive scheduling, you've still got > deadlocks... Neil, What does YHC do about in-progress thunk evaluations when a context switch happens? Does it use blackholing like GHC, or does it portentially duplicate the work, or something else? Cheers, Simon

3 2

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

30 Mar '06

On 30 March 2006 13:05, John Meacham wrote: > but the debugging/deterministic > benefits could be useful. you could be guarenteed to reproduce a given > sequence of context switches which could make finding concurrent > heisenbugs easier. Actually +RTS -C0 already gives deterministic concurrency in GHC. And you're right, it's essential for debugging. SMP has made my life somewhat more painful of late :-) > or something like concurrent 'hat' or another > debugger might find it easier to work in such a mode. > > In any case, what I think of when I think of 'writing a portable app' > is that from _the spec alone_ I can write something that I can expect > to work on any compliant system. This goal can be achieved to various > degrees. But if the specification says, 'the implementation might be > cooperative' and I write assuming that, then it pretty much will > definitly work anywhere perhaps with some spurious 'yields'. Absolutely, but a preemptive implementation has no way to tell you if you missed out a 'yield', and that essentially is the same as non-portabiliy. It doesn't matter that the spec told you you needed the yield, if the implementation you're using works fine without it, non-portable software will be the result. What's more, in some cases it isn't even possible to insert enough yields. It's entirely reasonable to have an application that runs some CPU-bound pure computation in one thread and a GUI in some other threads. This type of application can't be implemented if the standard guarantees nothing more than cooperative scheduling. Worse, no static property of the code tells you that. > however > if it says something to the effect of 'runnable threads will be > timeshared via some fair algorithm for some definition of fair' No, I'm suggesting the specific fairness guarantees mentioned earlier (and on the wiki page). > then > it doesn't help much writing portable apps since you would want to > test on the various compilers to see what their definiton of "fair" > is. Given those fairness guarantees, programmers will not need to care whether the implementation is using preemption based on allocation, or one based on reductions, or arbitrary inter-instruction preemption. Because it is hard to write a program that can tell the difference, especially if you stick to using proper synchronisation primitives, nobody will do it by accident. Contrast this with a standard that allows both cooperative and preemptive scheduling. It's much easier to write a program that can show the difference, and I'm worried that people will do it all the time, by accident. That's bad. > I thought yhc supported unboxed values, so a loop like > > count 0 = 0 > count n = count (n - 1) > > count 100000 > > could block the runtime (assuming it was properly unboxed by the > compiler) since it never calls back into it and is just a straight up > countdown loop? are we talking about the same compiler? YHC is fully interpreted, has no unboxed types, and AFAIK it is impossible to write any code that doesn't get preempted after a while. Cheers, Simon

2 1