April 2006 - Haskell-prime

Re: Concurrency
by oleg＠pobox.com 05 Apr '06

05 Apr '06

It would be really great if the concurrency portion of Haskell' did not outlaw light-weight threads implemented via delimited continuations (similar to those in the ZFS system). Such threads are cooperative: a thread runs until it requests service from a `supervisor' (yield() being one of such requests). The advantage of these threads is that they are lightweight, that the scheduler becomes expressible in the Haskell itself (and so each application can have its own scheduler, with or without priorities, with or without sophisticated resource-aware scheduling), and such threads have a natural transactional semantics. In the ZFS project threads can only do IO that is explicitly provided for them, and nothing else. Or, to be more precise, threads are statically prevented from any IO; they must request IO from the supervisor, which then decides if to satisfy the request, and when. Due to the natural 'copy-on-write' semantics, transactional memory becomes trivial; exceptions require no roll-back because no global state is modified unless the explicit commit is requested. Incidentally, the cooperative nature of lightweight threads does not preclude preemption: because all processing occurs in a monad, we can just as well make a monad that issues yield() after a certain number of 'binds'. Still, it will be nice if yield() per se were available, so users could chose the strategy for themselves. Interacting with foreign calls is indeed a problem: it is imperative that foreign calls be non-blocking. ZFS had to implement select(2) binding to get the non-blocking network IO. Fortunately, asynchronous behavior is possible for *any* operating system call, under generous assumptions (which hold for Linix and BSD systems, among others): Lazy Asynchronous I/O for Event-Driven Servers http://www.usenix.org/events/usenix04/tech/general/elmeleegy.html >From the abstract: ``We compare the performance of web servers implemented using LAIO to the performance obtained with previous interfaces. For workloads with an appreciable amount of disk I/O, LAIO performs substantially better than the alternatives, because it avoids blocking entirely. In one such case, the peak throughput with LAIO is 24% higher than the next best alternative. For in-memory workloads it performs comparably.'' It does seem to be a general consensus that events are faster than threads, but more difficult to program [just because first-class delimited continuations are not available for all languages, IMHO]. Here's a summary of HotOS X presentation that touches on the topic: ** Making Events Less Slippery with eel Ryan Cunningham and Eddie Kohler, University of California, Los Angeles HotOS X: Tenth Workshop on Hot Topics in operating systems. Santa Fe, New Mexico, June 12-15, 2005. Cited from the summaries in USENIX ;login: v.30, N5, p.67, 2005. http://www.usenix.org/publications/login/2005-10/openpdfs/hotos05.pdf ''This talk continued the old debate concerning threads and events. Events are fast but difficult to program. The speaker described eel, a programming tool designed to simplify programming with events. [Basically, a GUI for losers. Should use better languages!] eel uses program analysis techniques to improve programmability while preserving the event model, and provides the libeel event library, visualization, and debugging tools. Programming events is hard because it is difficult to understand the flow of the program and difficult to debug. eel's visualization tools make it easy to visualize the control flow, and the debugger allows you to step through each program flow separately; you follow the callbacks related to the same connection, so each flow of related events appears sequential. The speaker concluded that events don't need to be hard to program. You can use simple tools to extract program control flow and to help with visualization, verification, and debugging. Margo Seltzer pointed out that while eel helps clarify the event- based program after it's written, it does not appear to help with the actual writing of the program. The speaker responded that by allowing the programmer to visualize newly written code, eel does make writing easier. Margo was not convinced that using events is worth all this trouble. The speaker said that using events is preferable because they are much faster. Pei Cao responded that based on her experience of designing large software projects people use both threads and events. Events are a pain, so people use them only when performance is absolutely critical, which does not happen very often.''

1 0

Re: FD improvement, variable quantification & generalised propagation
by oleg＠pobox.com 05 Apr '06

05 Apr '06

Claus Reinke wrote: > I hadn't given that much thought before, because FDs are meant > to determine their range types, and there isn't much difference > between universal and existential quantification if there is only > one possible variable value, eg: > > (forall a in {Char}. T a) vs (exists a in {Char}. T a) That is quite an interesting issue, and the one on which different Haskell implementations differ. Let us consider the following code > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > > module Foo where > > class C a b | a -> b, b -> a where > foo :: b -> Bool > > data E a = forall b. C a b => E b > data U a = U (forall b. C a b => b) We see that given the constraint "C a b", the type |a| unambiguously determines the type |b|, and vice versa. One may ask if the type |E a| provides any type abstraction over |b|, and if the type |U a| provides any generalization over |b|. Hugs (March 2005) and GHC 6.4.1 differ in their answers. > instance C a a where foo _ = True > > t1 () = E undefined > t1' = case t1 () of E x -> foo x > > t2 () = U undefined > t2' = case t2 () of U x -> foo x Hugs -98 accepts this code; both t1' and t2' evaluate to True. GHC accepts t1 but flags t1'. GHC does not accept even t2. If we have more specific instances, then Hugs too reject the program (alas, for a different reason: unresolved overloading). If we have more specific instances > instance C () () where foo _ = True > instance C [a] [a] where foo _ = False then t2 becomes acceptable to GHC. t1' and t2' still present the problem; the latter is due to the unresolved overloading, which we can fix > t2 () = U undefined > t2' = case t2 () of U x -> foo (tail x) and now this code works in GHC, and Hugs. In Hugs, even the following is accepted: > t1 () = E () > t1' () = case t1 () of E x -> foo x however the inferred type for t1' is Foo> :t t1' t1' :: C a ([b] -> Bool) => () -> Bool which I can't explain at all... The slight change in the class: > class C a b | a -> b, b -> a where > foo :: b -> a -> Bool (please note: only the signature of foo is changed; the constraints and FD remain the same) the more specific instances now work in Hugs > instance C () () where foo _ _ = True > instance C [a] [a] where foo _ _ = False > > t1 () = E () > t1' = case t1 () of E x -> foo x () > > t2 () = U undefined > t2' = case t2 () of U x -> foo x [] As before, GHC accepts both t2 and t2' (but not t1'). It would be really great if the writers of typeclass-based programs could expect consistent results... > he suggested that the whole problem may be an instance of > generalised propagation: > > Generalised Constraint Propagation Over the CLP Scheme, > by Thierry Le Provost and Mark Wallace. Journal of Logic > Programming 16, July 1993. Also [ECRC-92-1] > http://eclipse.crosscoreop.com:8080/eclipse/reports/ecrc_genprop.ps.gz Francois Pottier's ICFP'05 invited talk had essentially the same gist: constraint propagation. He considered different domain: GADT and related implication and disequality constraints (I think he mentioned that the results applied to FDs as well) http://para.inria.fr/~fpottier/slides/fpottier-2005-09-icfp.pdf

1 0

deriving Typeable
by oleg＠pobox.com 05 Apr '06

05 Apr '06

John Meacham wrote: > things like DeepSeq and Typeable will most likely have optimized > versions on various compilers which is why I'd like to see the > restriction that the only way to create instances for these two > classes is via the "deriving" mechanism of the compiler. Please make it so! Allowing users to create their own instances of Typeable is tantamount to allowing them to define the _total_ function unsafeCoerce :: (Typable a, Typeable b) => a -> b That function always succeeds; you don't want to trust its result in general though. If we add -fallow-incoherent-instances, then the Typeable constraint disappears and we obtain the total function of the type a->b. The fact these functions are expressible in Haskell at all is quite disconcerting.

1 0

RE: Concurrency
by Simon Marlow 04 Apr '06

04 Apr '06

On 31 March 2006 22:15, John Meacham wrote: > On Fri, Mar 31, 2006 at 04:21:26PM +0100, Simon Marlow wrote: >> Great. Apart from my misgivings about allowing cooperative >> scheduling at all, here's a few comments on the proposal: > > much much preferable to a standard that not everyone can implement. :) > >> - I wouldn't include threadWaitRead, threadWaitWrite, >> or threadDelay at all. These can all be implemented using >> FFI, so don't belong in the concurrency library. Their >> presence is largely historical. > > They all have special implementations on a 'epoll' based system. > threadDelay turns into the timeout parameter to select, waitread/write > turn into the basic building blocks of your epoll wait-list. We > definitly want these in the interface as primitves. Still not convinced. Most applications can use the standard IO library in a multithreaded program to get I/O multiplexing. The library might be implemented by using a clever epoll/kqueue/whatever interface underneath, but I don't see a reason to expose that as a standard library. And it's perfectly reasonable to implement concurrent IO without doing any clever epoll stuff: GHC on Windows does just that. IMHO, concurrency gives you a way to *avoid* needing an event interface in your language. > In particular, foregin concurrent calls will most likely be > implemented in _terms_ of threadWaitRead on cooperative systems. By all means, but that still doesn't mean that threadWaitRead needs to be in the standard. Cheers, Simon

2 1

RE: Re[2]: thread priorities?
by Simon Marlow 04 Apr '06

04 Apr '06

On 31 March 2006 10:24, Bulat Ziganshin wrote: > Hello Simon, > > Friday, March 31, 2006, 12:24:23 PM, you wrote: > >>> threadSetPriority :: ThreadID -> Int -> IO () > >> 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. > > it was requested by Joel Reymont, and he even give us information how > that is implemented in Erlang, together with hint to assign higher > priorities to consuming threads. Yes, but the Erlang implementation doesn't do anything about priority inversion. Also, I don't think Joel really wanted priorities, his problem could have been solved by using bounded channels. Cheers, Simon

3 2

RE: Re[2]: 'deriving Tree (Eq,Ord)'
by Simon Marlow 04 Apr '06

04 Apr '06

On 04 April 2006 14:35, Bulat Ziganshin wrote: > Hello Ross, > > Tuesday, April 4, 2006, 4:55:09 PM, you wrote: > >>> http://www.cse.unsw.edu.au/~dons/haskell-1990-2000/msg00727.html >> (Making 'deriving' a separate declaration instead of a clause) > >> Orphan instances are discouraged in the GHC libraries, so there might >> not be much support for adding a feature designed to permit orphan >> derived instances. > > sorry, i don't understand how them are discouraged? GHC can't support > this because of it's internal limits? i think you mean some other > thing but i can't understand you Discouraged in the sense of "it works fine, but we don't recommend it". Compilation times may be worse if you have orphan instances, because the compiler *always* has to read an interface file containing an orphan instance if it is in the transitive closure of imported modules. Cheers, Simon

1 0

Deriving for newtypes
by Bulat Ziganshin 04 Apr '06

04 Apr '06

Hello , as i see, it was some form of formal specification for subj: http://www.cse.unsw.edu.au/~dons/haskell-1990-2000/msg05468.html -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

3 2

RE: deeqSeq proposal
by Simon Peyton-Jones 03 Apr '06

03 Apr '06

Interesting idea. What would you expect to happen here? f x xs = let g y = x+y in map !! g xs Here I'm evaluating the function g hyperstrictly before the call to map. Does x, the free variable in g's function closure, get evaluated? >From an implementation point of view, you could imagine that hyperstrict evaluation would pull apart function closures, as well as data structures. But I'm not sure you could give that a sensible denotational semantics. Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Andy Gill | Sent: 30 March 2006 23:12 | To: haskell-prime(a)haskell.org | Cc: Laura McKinney | Subject: deeqSeq proposal | | For the reasons talked about in previous posts, I'd like to propose a | deepSeq | for Haskell'. | | - It provides a mechanism to allow an effective, systematic | tracking down of | a class of space leaks. | - It provides a mechanism to simply stomp on a class of space leaks. | - It avoids the user having to explicitly declare instances for a | homebrew deepSeq | for every type in your program. | - It has a declarative feel; this expression is hyper strict. | - Is a specification of strictness. | - It will open up various optimization opportunities, avoiding | building thunks. | (I dont talk about this more, but I'm happy to elaborate) | - It can have an efficient implementation, or a simple (slow) | implementation. | (The fast implementation one can be used to stomp space leaks, | the slow one can help find the same leaks.) | | What I would like to propose for Haskell' are four things: | | (Essential) Add a deepSeq function into Haskell' | | deepSeq :: a -> b -> b | | - Don't really care if its in a class or not; would prefer not for | the reasons John Hughes talked about. | - This would deepSeq all its children for regular constructors. | - deepSeq would not indirect into IO or MVar. | - functions would be evaluated to (W?)HNF. | - IO, ST are functions under the hood. | | (Easy) Add a $!! function, and a strict function | | f $!! a = a `deepSeq` f a | strict a = a `deepSeq` a | | (Nice) Add a !! notation, where we have ! in datatypes. | | data StrictList a = Cons (!!a) (!!StrictList a) | Nil | | (Perhaps) Add a way of making *all* the fields strict/hyperstrict. | | data !!StrictList a = .., | | We could also do this for ! | | -------------- | | Implementation: | | deepSeq (RAW_CONS <is_deep_seq'd_bit> ... fields ) = | if <is_deep_seq'd_bit> == True | then return /* hey, we've already deepSeq'd this */ | else set <is_deep_seq'd_bit> to True. | deepSeq (field_1) | ... | deepSeq (field_n) | deepSEQ (REF/MVAR...) = return | | So we only deepSeq any specific constructor once! Sorta like lazy | evaluation :-) | We'd need to catch exceptions, unset the is_deep_seq'd_bit, so that any | subsequent call of deepSeq would also have the option of raising the | exception. | | So, | | - How easy is this to add to the compilers? It looks pretty simple | to me, | and would provide huge bang-for-buck for Galois. | - Any alternatives to the key concern; stomping on space leaks. | (This proposal is orthogonal to the seq/Class discussion) | | Andy Gill | Galois | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

3 2

Concurrency
by John Meacham 03 Apr '06

03 Apr '06

I have tried to summarize the current thinking into a proposal on the wiki. http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/Concurrency I split it into 3 parts. the standard - all haskell' compilers must implement optional preemption - ability to preempt pure code, fairness guarentees, interleaved evaluation operators (merge, nmerge) optional OS threads - bound threads, SMP, reentrant concurrent FFI calls supported. comment or modify it at will. John -- John Meacham - ⑆repetae.net⑆john⑈

5 8

Re: Concurrency
by John Meacham 03 Apr '06

03 Apr '06

On Fri, Mar 31, 2006 at 04:21:26PM +0100, Simon Marlow wrote: > Great. Apart from my misgivings about allowing cooperative scheduling > at all, here's a few comments on the proposal: much much preferable to a standard that not everyone can implement. :) > - I wouldn't include threadWaitRead, threadWaitWrite, > or threadDelay at all. These can all be implemented using > FFI, so don't belong in the concurrency library. Their > presence is largely historical. They all have special implementations on a 'epoll' based system. threadDelay turns into the timeout parameter to select, waitread/write turn into the basic building blocks of your epoll wait-list. We definitly want these in the interface as primitves. In particular, foregin concurrent calls will most likely be implemented in _terms_ of threadWaitRead on cooperative systems. > - yield bothers me a little. If it weren't for cooperative > systems, yield would be semantically a no-op, because the > no-starvation guarantee means you never need it for > correctness. I think it's ok, just a bit unsettling. even pthreads provides it. <noise> I think you place a lot of faith in pre-emption. :) In my experience, it doesn't actually buy you a whole lot over state-threading in the non SMP case. everything would be different if we were thinking of different processes on the same computer, where you wouldn't want one buggy one interfering with others, but in general you consider a single program buggy or bug-free as a unit. </noise> In any case, IO multiplexing is 90% of the uses of threading anyway, (ginsu,yi,gui apps that don't do background processing, etc...) which cooperative threading is ideal for. not that there arn't itches that only preemptive threads can scratch too. > - In the optional OS threads section it says "allows multiple > haskell threads to run at once" - actually you can provide > all that without allowing multiple haskell threads to run > at once, eg. ghc-6.4.1 with -threaded. I'll modify it. okay. yeah, I just sort of outlined the options figuring we would fill in the details later. John -- John Meacham - ⑆repetae.net⑆john⑈

3 5