March 2006 - Haskell-prime

RE: MPTCs and functional dependencies
by Simon Peyton-Jones 10 Apr '06

10 Apr '06

My current take, FWIW. * MPTCs are very useful. They came along very rapidly (well before H98). I think we must put them in H' * But MPTCs are hamstrung without FDs or ATs * FDs and ATs are of the same order of technical difficulty, as Martin says * ATs are (I believe) a bit weaker from the expressiveness point of view (zip example), but are (I believe) nicer to program with. * BUT we have way more experience with actually programming with FDs. ATs fail the "well-established" test by a mile. * Largely due to Martin's work, we now have a much better handle on just what restrictions on FDs make type inference tractable. So I believe there is a solid MPTC+FD story that we could embody in H'. * Medium term, I think ATs may *at the programming-language level* displace FDs, because they are nicer to program with. But that's just my opinion, and we don't have enough experience to know one way or the other. Tentative conclusion: H' should have MPTC + FDs, but not ATs. Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Ross Paterson | Sent: 02 February 2006 11:25 | To: haskell-prime(a)haskell.org | Subject: MPTCs and functional dependencies | | On Thu, Feb 02, 2006 at 11:38:07AM +0100, John Hughes wrote: | > The problem with Haskell 98 is that it *lacks* features which | > have become absolutely essential to Haskell programmers today. Those | > features are what really *need* discussion and energy spent on them. | > | > [...] | > | > Multi-parameter classes with functional dependencies | > - used everywhere... for example in monad transformers... so | > *must* be included this time | > - omitted from Haskell 98 because "the right design" wasn't clear | > - it's still unclear! Functional dependencies *in some form* | > are essential, but associated types and datatypes look nicer | > in many ways! | > - is it too late, in practice, to replace fundeps by something | > else? How will we know? If we are to standardize on associated | > types instead, we need a major effort to *make sure* all | > important applications of fundeps can be represented. How will | > we organize that? | | I agree that MPTCs are much less useful (though not completely useless) | without something like FDs or associated types. But the specification | of FDs is far from clear: the system described in Mark's paper is quite | a bit weaker than what is implemented by GHC and (more shakily) by Hugs. | It seems that associated types aren't ready yet, but I don't think FDs | are either, accustomed as people are to them. | | I have another worry about MPTCs. They require require relaxations on | the form of instances (FlexibleInstances on the wiki), which in turn | require relaxations on contexts and thus deferred context reduction (see | FlexibleContexts). The result is that missing instances get reported | later than they do now. MPTCs are very useful and probably necessary, | but there is a cost. | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

6 6

FFI, safe vs unsafe
by Wolfgang Thaller 07 Apr '06

07 Apr '06

Hi everyone, Before adding non-concurrent, reentrant calls to the language standard, please take some time to think about what that means. If you have forkIO'ed multiple threads, things start to interact in strange ways. I think this is a can of worms we don't want to open. (Or open again. It's still open in GHC's non-threaded RTS, and the worms are crawling all over the place there). So I'm going to ask a few questions about the semantics of non- concurrent reentrant calls, and if people can provide answers that don't scare me, I'll concede that they have a place in the language standard. 1.) Assume thread A and B are running. Thread A makes a non- concurrent, reentrant call to Foreign Lands. The foreign function calls a foreign-exported Haskell function 'foo'. While 'foo' is executing, does thread B resume running? 2.) Assume the same situation as in 1, and assume that the answer to 1 is yes. While 'foo' is running, (Haskell) thread B makes a non- concurrent, reentrant foreign call. The foreign function calls back to the foreign-exported Haskell function 'bar'. Because the answer to 1 was yes, 'foo' will resume executing concurrently with 'bar'. If 'foo' finishes executing before 'bar' does, what will happen? 3.) Same situation as in 1. When 'foo' is called, it forks (using forkIO) a Haskell thread C. How many threads are running now? 4.) Should there be any guarantee about (Haskell) threads not making any progress while another (Haskell) thread is executing a non- concurrent call? Two more questions, not related to semantics: 5.) Assume that Haskell Programmer A writes a Haskell library that uses some foreign code with callbacks, like for example, the GLU Tesselator (comes with OpenGL), or, as a toy example, the C Standard Library's qsort function. Should Programmer A specify "concurrent reentrant" on his foreign import? Programmer B will say "please don't", as he wants to use a Haskell implementation which doesn't support "concurrent reentrant". Programmer C will say "please do", as he wants his application's GUI to stay responsive while the library code is executing. So what should the poor library programmer A do? 6.) Why do people consider it too hard to do interthread messaging for handling a "foreign export" from arbitrary OS threads, when they already agree to spend the same effort on interthread messaging for handling a "foreign import concurrent"? Are there any problems that I am not aware of? If I am wrong and we should indeed provide non-concurrent reentrant calls in a concurrent Haskell system, then I think there should be satisfying answers to the above questions... Cheers, Wolfgang

5 13

deeqSeq proposal
by Andy Gill 06 Apr '06

06 Apr '06

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

3 2

RE: important news: refocusing discussion
by Simon Marlow 05 Apr '06

05 Apr '06

On 24 March 2006 12:28, Ross Paterson wrote: > On Fri, Mar 24, 2006 at 11:30:57AM -0000, Simon Marlow wrote: >> So I believe the issue is mainly one of perspective. Until I wrote >> this email I hadn't thought of (4) and my preference was for (2), >> but now I quite like the idea of (4). We would include concurrency >> in Haskell', but provide a separate addendum that specifies how >> imlementations that don't provide concurrency should behave. One >> advantage of (4) over (3) is that we can unambiguously claim that >> Haskell' has concurrencey. > > And we can unambiguously state that there is only one Haskell' > implementation (though a second is on the way). > > Sure, concurrency is essential to many applications, and should be > precisely specified. But it is also irrelevant to a lot of uses of > Haskell (except for ensuring that one's libraries are also usable on > concurrent implementations, as JohnM said). A specification of the > language without concurrency would be at least as valuable (having > more implementations). Perspective, as you say -- most people agree > we need both -- but I think you're a bit too negative about the > smaller variant. This is just a difference of opinion, and probably won't be easily resolved. It comes down to whether you think Haskell' should be a language that is wide enough to include such applications as a web server, or whether it has to stop short of including concurrency because it's too hard to implement (and it's not always hard - the YHC guys managed it in a matter of days, but I do realise it would be hard in Hugs). I think it would be a mistake to relegate concurrency to an addendum; it is a central feature of the language, and in fact is one area where Haskell (strictly speaking GHC) is really beginning to demonstrate significant advantages over other languages. We should make the most of it. Cheers, Simon

7 7

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

05 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

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

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

02 Apr '06

On 28 March 2006 15:26, Malcolm Wallace wrote: > "Simon Marlow" <simonmar(a)microsoft.com> wrote: > >> Ok, I'll try to nail down what we should require in terms of fairness >> (which is the same as pre-emption). > > The terms are not entirely synonymous. > > Pre-emption means that (1) threads have priority levels, and (2) that > a higher priority thread can steal the processor from a > currently-running lower priority thread, and (3) it can do so > "immediately" it needs to, without waiting for some "safe" > synchronisation point. > > By those criteria, none of the current Haskell implementations are > pre-emptive, because no API assigns priorities to threads. So let's > not use the term pre-emption; instead let's agree to talk only about > fairness, since that is the real topic here. Ok, I won't argue this point. It depends which definition you read - I'm using the term preemption to mean that threads can be preempted by the execution engine. I won't use the term any more to avoid confusion. > As I see it, all current (and likely future) implementations of > concurrency in Haskell use co-operative scheduling. The only > differences are in the granularity and positioning of the 'yield' > calls. > > * For Hugs, yield is inserted at certain I/O actions. > * For ghc, yield is inserted after some count of allocations. > * For yhc, yield is inserted after some count of bytecode > instructions. That list is a useful implementation reference, but I think it misses the point. It's much more useful to reserve the term "cooperative" for when the burden is on the programmer to insert context-switch points, as is the case in Hugs. This is a significant difference from the programmer's point of view, whereas the difference in imlementation between GHC and YHC is to a very close approximation invisible. Let's stick to fairness. These are the requirements I think the standard should include: No runnable process will be indefinitely delayed. No thread can be blocked indefinitely on an MVar unless another thread holds the MVar indefinitely. Suitably annotated foreign calls run concurrently with other Haskell threads. That does preclude a cooperative implementation, and for good reasons. Manuel made the point that if a cooperative implementation is admitted by the standard, that makes it much harder to write portable concurrent code. Code written using GHC wouldn't neceessarily run properly on a cooperative implementation, despite the fact that both implementations would be conforming. I think Haskell' should avoid this pitfall. Cheers, Simon

4 3

Re: Concurrency
by John Meacham 01 Apr '06

01 Apr '06

On Fri, Mar 31, 2006 at 10:21:16AM -0600, John Goerzen wrote: > On Fri, Mar 31, 2006 at 04:41:06AM -0800, John Meacham wrote: > > optional preemption - ability to preempt pure code, fairness guarentees, > > interleaved evaluation operators (merge, nmerge) > > Under the "what is provided" section, did you intend that to apply to > all compilers, even ones that don't implement threading? the point is that all compilers will implement threading now and provide everything in that section. rather than having all of concurrency being an option, we have found a way to get a good portion of concurrency guarenteed to be supportable on all systems without any compromises in run-time for the non-concurrent case or restricting the range of future implementation techniques. > If so, we should specify what exception is raised if, say, forkIO is > called on such a system. We should also make it clear that > single-threaded implementations are required of things such as MVars. > Finally, we should add a function that indicates the level of threading > support on the running system. routines that are guarenteed to fail becaues they arn't supported should not exist, haskell tries hard to catch so many errors at compile time, it would seem odd to delegate the error of missing a whole subsystem to run-time :) John -- John Meacham - ⑆repetae.net⑆john⑈

2 3

RE: MVar semantics: proposal
by Simon Marlow 01 Apr '06

01 Apr '06

Sequence points... yes, all seems reasonable to me. On 31 March 2006 00:50, John Meacham wrote: > 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. Slightly less overhead than an MVar, because you only need one lock/release to implement atomicModifyIORef, but two lock/release combinations are involved in an update of an MVar. atomicModifyIORef would be a sequence point, BTW. Semantically, think of it as having a hidden MVar attached to the IORef: withMVar m $ \_ -> do x <- readIORef r let (x',y) = f x writeIORef r x' return y as long as you have some way to enforce exclusion with respect to other atomicModifyIORef operations on a given IORef, you can implement it like this. > atomicModifyIORef also cannot (easily) be implemented on > implementations > that use update-in-place rather than indirections for thunk updates. I don't follow you - how would that make it harder? Cheers, Simon

3 2