- Haskell-prime - Haskell.org

preemptive vs cooperative: attempt at formalization
by John Meacham 13 Apr '06

13 Apr '06

I'd like to be a bit more formal when it comes to the distinction between cooperative and preemptive implementations of concurrency, here is a first attempt. 1. termination, In a concurrent implementation, a thread performing an infinite loop with no IO or interaction with the outside world can potentially stall switching to another thread forever, in FP, we usually denote an infinite loop by _|_. so I think the first difference would be: [Rule 1] * in a cooperative implementation of threading, any thread with value _|_ may cause the whole program to have value _|_. In a preemtive one, this is not true. I am using _|_ in the stronger sense of non-termination, not including things like exceptions which should have a well defined behavior. 2. fairness Assuming no thread has value _|_ now, what can both models guarentee when it comes to fairness? both can guarentee every runnable thread will eventually run with a round-robin type scheduler. both can fairly allocate CPU time at the limit, if a thread is taking too much CPU in either model, it can be allocated less timeslices in the future. the same scheduling algorithms work for both with minor modifications. the thing that pre-emptive implementations can do that cooperative ones cannot is provide latency fairness. as in, the time before a given thread is scheduled once it becomes runnable can be bound independently of what other threads are doing. so perhaps the following [Rule 2] * A cooperative system cannot necessarily guarentee or provide for latency requirements when it comes to scheduling a thread once it becomes runnable. A pre-emptive system can provide such guarentees (discounting foreign nonconcurrent calls) I think these two rules are enough to distinguish when you can say you meet the pre-emptive option without delving into implementation details. What do y'all think? John -- John Meacham - ⑆repetae.net⑆john⑈

6 16

On Unicode
by Mr Noone 13 Apr '06

13 Apr '06

I write to you because of this: "Revert to US-ASCII, Latin-1 or implementation-defined character sets." (from http://hackage.haskell.org/trac/haskell-prime/wiki/UnicodeInHaskellSource) The benefits of being allowed to used Unicode in sourcecode include: - Being able to define operators and identifiers exactly matching the standard definitions in a domain such as mathematics have been proven over many years in tools like Mathematica. Using shortcuts and palettes with such symbols and operators in whatever editor makes entry easy. - Allow non-english students to focus on logic rather that on translating concepts into English. While students may have a rudimentary grasp of English, special terminology may be unknown to them. - Interoperate with Microsoft .Net and by extension Novell Mono where identifiers etc are allowed to be Unicode. (I'm not familiar with Sun Java but the same seem to be the case there). - While using English can be of benefit for international projects, there are many tasks where this is not a factor such as adhoc research calculations, in teaching and projects where all the programmers are non-English. Using Unicode does not prevent specific projects from choosing to restrict themselves to only ASCII characters, the reverse is not true. Typical arguments against Unicode are: - English is 'better'. This seems to be propagated by people who only understand English and who has never been exposed to other cultures and thus feel threatened when confronted with something they do not understand. However it is generally better to be allowed to think and write in one's native tongue. - It is not portable. This can be solved by standardization as discussed elsewhere in the wiki article. - It may result in obfuscated code. True if misused, however using ASCII does not prevent anyone from obfuscating by naming variables a1, a2, a3, ... or whatever else. Common sense makes this claim null and void. Naming a variable correctly in one's own language is preferable to an incorrect translation attempt into English. - It takes up more space. True but hardly relevant except in degenerate cases because of the ever increasing availability of memory. Even resource constrained embedded devices such as Windows CE exclusively support Unicode. - It is not common practice. Practically all leading user applications provide multi-language versions, some Office products even has multi-language scripting built-in. I can recall when it was common practice to use punch cards with their 80 characters per line restriction, it is my understanding that Haskell is leading edge rather than legacy entrenched. It is sad to see that most Haskell compilers and interpreters does not implement the Haskell language with regard to Unicode (perhaps except JHC but I haven't succeeded in getting it to compile on Windows yet - my own fault no doubt). It is even more sad to see that this affects applications such as Pivotal, which would be a truly wonderful teaching and research aid with Unicode support and user-provided translations into major languages. My experience is from South-East Asia where written languages are markedly different from English and European languages. The alfabets are different, for example in Khmer there is no space between words, spaces are used somewhat like commas in English, even the symbol for full stop "." is different. The symbols for numbers are different (though English numbers are widely understood) and in Thailand the official calendar is Thai-Buddhist (current year 2549) not Christian. These aspects are supported in Microsoft .Net language applications consequently Microsoft .Net is being widely taught here now! I understand the situation to be much the same in Arabic countries and then there is China and Japan... Personally I would like to see things taken one step further by having compilers support translation tables for keywords, system defined function names, and even external user defined identifiers, so automatic translation of source code would be possible, but that would propably be outside the scope of Haskell'. As for myself I will continue to use Mathematica where I can define my operators and symbols exactly like they are in the literature which I consider to be in the spirit of the literate programming style. I do understand that all this does not really matter if Haskell is only a research language for new programming language concepts. But I hope this is enough of argumentation to make it understandable that while it is easier to implement a compiler in ASCII only there are benefits to using Unicode for non-English speakers also when programming. Best regards, freegoldbar __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

1 0

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

13 Apr '06

| Any function that is not defineable in (pure) Haskell should be viewed | with utmost suspicion. The seq function is one of these. At least | seq has simple denotational semantics, which can't be said for deepSeq. | | I say, put deepSeq in a type class (which is what I've done when I need | it). The whole *point* is that deepSeq is (dynamically) idempotent: deepSeq (deepSeq x) = deepSeq x. Its denotational behaviour is perfectly definable in Haskell, but its operational behaviour is not. That is both attractive (because it means you feel less anxious about wasting work with deepSeq) and repellent (because it constrains the implementation, as John points out). Whether it should be in a class is a rather separate discussion. In a way we already sold out when we allowed seq to escape from the type-class world. Perhaps deepSeq is worse (because it traverses data structures) but not obviously. Simon

4 3

The goals of the concurrency standard?
by oleg＠pobox.com 12 Apr '06

12 Apr '06

John Meacham wrote > [Rule 1] > * in a cooperative implementation of threading, any thread with value > _|_ may cause the whole program to have value _|_. In a preemtive one, > this is not true. > would the simple qualifier > 'if there exists another runnable thread' > solve the issues? if there exists another runnable thread of at least the same priority. I am afraid I must ask for the clarification of the goals of this discrimination between pre-emptive and cooperative scheduling -- which leads me to further questions. One one hand, I understand the motivation: providing guidance to the end programmer. In a cooperative thread system, the programmer just can't write code imagining the current thread is the only one. If the thread is to compute the Nth Mersenne prime, it would effectively hang the whole system. So, the user must specifically insert calls to yield -- which means that the whole code has to be converted into a monadic style, because yield is most certainly a monadic operation _and_ because we must be sure that computations before yield are indeed finished, rather than snowball up to the very end. So, we have to re-write pure functional code (like the Mersenne prime computation) into a monadic one, and thus explicitly serialize it. That negates one of the significant benefits of Haskell -- no longer code looks like a specification or mathematical notation. If we're forced to write everything in the A-normal form, we might as well use a better language for that, like SML. In a preemptive thread system, we can indeed program a thread as if it were the only thread in the system -- and the scheduler would do the rest. Problem solved? Only if threads do not interact, which is not likely. At least they have to write something, and so contend for the access to stdout (assuming multi-line output). A thread running a long computation while holding a critical resource can just as well hang the whole system, pre-emptive scheduler notwithstanding. Lazy evaluation of Haskell makes this problem quite subtle: do r <- return (mersenne' 44) acquire'lock putStrLn "Great success" print r release'lock One may think that the long computation occurs in the "r <- ..." line. Alas, it may just as well occur in the "print r" line, when the digits of the number are really required to print. So, we will be running a long computation while holding a lock. This isn't much better than the situation with the cooperative scheduling, is it? It appears that just pre-emptiveness does not guarantee us much. We need to add, for example, hyper-strict evaluation -- or, effectively, give up on the lazy evaluation because otherwise we can never be certain about the length of the computation -- and without that information, we can never be certain if our locking strategy is fair. The latter has nothing to do with pre-emptiveness. There seems to be another, Erlang way. The programmer must have an impression that threads do not share absolutely anything, and must communicate exclusively via message passing. Incidentally, how this message passing implemented on a shared memory multi-processor is another matter entirely: Erlang is quite good at taking advantage of shared memory while giving the user impression of complete isolation. Message passing in Erlang is quite advanced: a thread may snoop the message queue looking for a specific message. The user may code a process as if no other processes exist. Erlang's scheduler does the right thing (I think it pre-empts based on the number of reductions; the scheduler may take the size of the message queue into account). The example above becomes do r <- return (mersenne' 45) send "Great success" send $ show r send "print it now" the output thread won't write anything until it catches the sight of "print it now" message in its message queue. In a sense, this strategy isn't quite different from STM. There is a price to pay however: absolutely no IORefs, no MVars etc. All system calls must be converted to a message-passing style. The latter isn't a huge problem: Erlang has managed. But for us, that entails the re-design of FFI, IO, and the banishment of IORefs and MVars...

3 8

postponing discussion on exceptions and deepSeq
by isaac jones 12 Apr '06

12 Apr '06

I'd like to ask the list to postpone discussion on exceptions and deepSeq until a later iteration. While these are two topics that are of deep importance to me, I would prefer to focus on the other two topics at hand until they are solved. That is, concurrency, and the class system. I'm still postponing opening up another topic since I find that the class system isn't being as enthusiastically discussed as I had hoped. Let's all focus our energies on these topics, I promise that the others won't be forgotten. Ross has asked for use cases for functional dependencies and so far has only two replies. Surely there are those on this list who have use of functional dependencies? peace, isaac -- isaac jones <ijones(a)galois.com>

4 3

RE: limitations of newtype-derivings (fixed)
by Simon Peyton-Jones 12 Apr '06

12 Apr '06

I like this idea. Needs fleshing out though. | * you can only newtype derive the last argument to a MPTC. | * you cannot co-derive an instance for multiple newtype renamings. | | it seems that both these can be solved when combined with the other | proposed extension, allowing deriving clauses to be separate from data | definitions. | | basically, we would allow deriving anywhere. | | > deriving (Show Foo) I'm all for that. A modest but useful gain. All we need is the syntax, and that is something that Haskell Prime might usefully define. | > newtype Id = Id Int | > data Term = ... | > newtype Subst = Subst (IM.IntMap Term) | | ideally, we'd like an MapLike instance, but we'd have to tediously write | it ourselves. if we allow the supergeneralized newtype deriving, we can do: | | > deriving(MapLike Id Term Subst) Now things aren't so clear. You are assuming that we have an instance instance MapLike Int a (IntMap a) But suppose we also had an explicit instance decl for instance MapLike Int Term Subst which we might. Which would the 'deriving' base its instance on? We might also have an explicit instance instance MapLike Id a (IntMap a) Now it's even less obvious which to use. What if the newtype was buried more deeply. Can we say deriving( C (Foo Id) ) if we happen to have an instance for C (Foo Int) around already? Here the newtype isn't at the "top level" of the class argument. GHC's newtype-deriving mechanism is very precise: it unwraps exactly one layer of exactly one newtype. It's attractive to go further, as you describe, but it'd need to be tightly specified. (And of course, that increases the complexity of the overall language.) Simon

3 2

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

11 Apr '06

Jan-Willem - thanks for your thoughts on this, it's greatly appreciated. On 31 March 2006 18:49, Jan-Willem Maessen wrote: > John - > > You are, in effect, proposing a memory model for MVars and IORefs. > The high-level model for programmers is "In order to communicate data > between threads, you *must* use an MVar, and never an IORef." > > But the devil is in the details. I'd like to strongly urge *against* > adopting the extremely loose model you have proposed. The following > things seem particularly important: > > * reads and writes to IORefs should be atomic, meaning either a > complete update is observed or no change is observed. In the absence > of this guarantee, misuse of IORefs can cause programs to crash in > unrepeatable ways. If the machine doesn't make this easy, the > implementor ought to sweat a little so that Haskell programmers don't > have to sweat at all. > > * I assume forkIO constitutes a sequence point. I suspect throwTo et > al ought to as well. > > * I would urge that atomicModifyIORef constitute a sequence point---I > suspect it loses a great deal of its utility otherwise. > > Now, on to more difficult issues... Consider the following example > (untested): > > data RefList a = Nil | Cons a (IORef (RefList a)) > > cons :: a -> RefList a -> IO (RefList a) > cons x xs = do > a <- newIORef xs > return (Cons x a) > > hd :: RefList a -> a > hd (Cons a _) = a > > tl :: RefList a -> IO (RefList a) > tl (Cons a t) = readIORef a > > setTl :: RefList a -> RefList a -> IO () > setTl (Cons a t) t' = writeIORef t t' > > main = do a <- cons 'a' Nil > forkIO $ do > c <- cons 'c' Nil > b <- cons 'b' Nil > setTl b c > setTl a b > at <- tl a > case at of > Nil -> return () > Cons _ _ -> do > putChar (hd at) > att <- tl at > > This program is, by your informal model, buggy. The question is > this: how badly wrong is it? > Let's say at happens to read b. Is (hd at) well defined? That's > assuming very strong consistency from the memory system already. How > about the IORef in at? Is that fully allocated, and properly > initialized? Again, if it is, that implies some pretty strong > consistency from the memory system. > > Now, what about att? By your argument, it may or may not be c. We > can ask the same questions about its contents assuming it happens to > be c. > > People have talked a lot about weakly-ordered NUMA machines for more > than a decade, and they're always just a couple of years away. In > practical terms, non-atomic NUMA memory models tend to be so hard to > program that these machines have never found any traction---you need > to throw away all of your software, including your OS, and start > afresh with programmers that are vastly more skilled than the ones > who wrote the stuff you've already got. > > My feeling is that the purely-functional portion of the Haskell > language already makes pretty stringent demands of memory > consistency. This is true - in GHC we are required to add a memory barrier to thunk update on architectures that don't have strong memory ordering, just to ensure that when you follow the pointer in an indirection you can actually see the value at the end of the pointer. Since x86 & x86_64 can implement strong memory ordering without (seemingly) too much overhead, surely adding the barrier instruction for other architectures shouldn't impose too much of a penalty, at least in theory? > In light of those demands, and the fact that mutable > state is used in pretty tightly-controlled ways, it's worth > considering much stronger memory models than the one you propose. > I'd even go so far as to say "IORefs and IOArrays are sequentially > consistent". Certainly possible; again on x86 & x86_64 it's a no-op, on other architectures it means adding a barrier to writeIORef. In GHC we're already doing a write barrier (of the generational GC kind, not the microprocessor kind) in writeIORef anyway. > The only argument against this behavior is their use in > the internals of arrays, file I/O, the FFI, etc., etc. (though really > it's all about IOUArrays in the latter cases) where we might > conceivably pay a bundle in performance. > > Another possibility is an algebraic model based on commuting IO > actions. That approach is a particular bias of mine, having tangled > with these issues extensively in the past. It'd go something like > this: * Any data written to an IORef can safely be read by another > thread; we cannot observe > partially-written objects. > * readIORef commutes with readIORef. > * newIORef commutes with newIORef. > * writeIORef and newIORef commute with writeIORef or readIORef to > a different IORef. > * Nothing commutes with readMVar, writeMVar, or atomicModifyIORef. > * Nothing before a forkIO can be commuted to after forkIO. Does this model mean anything to the runtime, or would it just affect compile-time optimisations? I imagine that, since the runtime still has to use barriers to prevent partially-written objects from being visible to other threads, in effect the runtime would end up providing full serialisation anyway. But my tiny brain hasn't quite the capacity to think this through completely right now, I'm hoping someone else has. > I think it's a Good Idea to choose a model that is conceptually > simple now, at the cost of imposing a few constraints on > implementors, rather than a complex specification which permits > maximum implementation flexibility but is utterly opaque. I don't have a strong opinion, since as I said earlier the constraints aren't that onerous in practice. However, I don't completely understand why the more flexible model would be "complex" and "opaque". Isn't it just a case of specifying certain interactions as resulting in undefined behaviour? Or do you think it's too hard to specify exactly which interactions are undefined? Cheers, Simon

2 1

RE: Signals + minimal proposal (was Re: asynchronous exceptions)
by Simon Marlow 11 Apr '06

11 Apr '06

On 07 April 2006 23:37, John Meacham wrote: > I think we might be thinking of different things. here is a complete > implementation of exit. > > exitMVar :: MVar () -- starts full > exitMVar = .. > > handlerMVar :: MVar [IO ()] -- starts with [] > handlerMVar = ... > > onExit :: IO () -> IO () > onExit action = modifyMVar handlerMVar (action:) > > exitWith status = do > takeMVar exitMVar -- winner takes all > let handleLoop = do > hs <- swapMVar handlerMVar [] > sequence_ hs > if null hs then return () else handleLoop > handleLoop > exitWith_ status > > exitWith_ calls the underlying 'exit' routine of the operating system > immediatly. no waiting. Suppose I want to do some action with a temporary file: bracket newTempFile (\f -> removeTempFile f) (\f -> doSomethingWith f) Under your scheme, this code doesn't get to remove its temporary file on exit, unless I explicitly add an exit handler that throws an exception to the current thread. I think code like the above should just work. Furthermore, I think it should be an invariant that a thread is never discarded or killed, only sent an exception. Otherwise, how else can I acquire a resource and guarantee to release it when either an exception is raised, the program exits, or the computation completes? According to your definition of exitWith above, I can't both raise an exception *and* exit in the same thread. If I register an onExit handler that throws an exception to the current thread, things go wrong if the current thread also calls exitWith. Also, you couldn't call exitWith while holding an MVar, if the handlers need access to the same MVar. You didn't show WithTemporaryExitHandler, which complicates things quite a bit. Also, your implementation has a race condition - a thread might add another exit handler after the swapMVar. I think we can probably agree on one thing: exitWith should raise an exception: exitWith e = throw (ExitException e) This isn't inconsistent with your proposal, and I think it's unambiguously better. The top-level exception handler catches ExitException and performs the required steps (running handlers, calling exit_). As you said, you need a top-level exception handler anyway, this is just a small change to your proposal, moving the exit actions to the top-level exception handler. Now additionally I believe that, if the system is about to simply stop, every thread should be sent an exception and be given a chance to clean up before the system stops. If this is the case, then: - withTemporaryExitHandler is unnecessary (catch suffices) - bracket and finally "just work" - it is safe to call exitWith while holding resources such as MVars - the programmer doesn't have to distinguish cleanup actions that should happen on exit from others - library programmers can rely on exceptions being delivered and don't have to additionally install exit handlers It's the right default: if a programmer decides not to handle the exception, then nothing goes wrong. > advantages of this set up. > > 1. base case requires no concurrency or exceptions Haskell already has exceptions (in the IO monad), and people are using them to manage resources. We shouldn't introduce another way to clean up. Also, in the single-threaded case my proposal makes sense too. > 2. abstract threads possible, if you don't let your ThreadId escape, > there is no way to get an exception you don't bring upon yourself. Well, there's StackOVerflow and HeapOverflow, and imprecise exceptions are hard to plan for too. All IO monad code should be prepared for exceptions, IMO. > 3. simple rules. expressable in pure haskell. > 4. can quit immediatly on a SIGINT since the exitWith routine runs on > whatever thread called exit, rather than throwing responsibility back > to the other threads which might be stuck in a foreign call. (unless > you explicitly ask it to) Don't understand this one - it certainly doesn't help with SIGINT in GHC. > 5. you don't have to worry about 'PleaseExit' if you don't want to. See (2). Also, the exit exception can be treated in the same way as all other unexpected exceptions (just clean up and re-throw). > 6. modularity modularity. now that concurrency is part of the > standard, we will likely see a lot of libraries using concurrency > internally for little things that it wants to keep abstract, or > concurrent programs composed with each other. having a global 'throw > something to all threads on the system' doesn't feel right. It's having a global exit that doesn't feel right. But since exit is something that is happening to all the threads in the system, they should all be told about it. > 7. subsumes the exitWith throws exceptions everywhere policy. > > John Cheers, Simon

4 3

RE: Exceptions
by Simon Marlow 11 Apr '06

11 Apr '06

On 11 April 2006 13:54, John Meacham wrote: > On Tue, Apr 11, 2006 at 01:43:18PM +0100, Simon Marlow wrote: >> yes, when I say "one throw" I was referring to the argument type, not >> the return type. We should still have ioError - although it would >> probably be better named throwIO: > > Ah, I see what you mean now. > > would it be possible to use Typeable1 to just catch 'ArithException a' > for any Typeable a? It seems like it should be, but I have not used > Typeable1 much. I tried it briefly and couldn't get it to work, but I'm no expert on the SYB stuff. You might need an Exception1 class to go with Typeable1, and that would be fairly ugly. Cheers, Simon

1 0

RE: Exceptions
by Simon Marlow 11 Apr '06

11 Apr '06

On 11 April 2006 13:35, John Meacham wrote: > On Tue, Apr 11, 2006 at 01:24:07PM +0100, Simon Marlow wrote: >> Attached is another variant of the extensible exceptions idea, it >> improves on the previous designs in a couple of ways: there's only >> one catch & throw, regardless of what type you're throwing or >> catching. There is an extensible hierarchy of exceptions, and you >> can catch and re-throw subclasses of exceptions. > > I made the catch and throw separate so the decision as to whether to > include imprecice exceptions and extensible extensions can be made > independently. > > that and > > throw x /= ioError x > > ioError x >> return () -> IO _|_ (only _|_ when IO action executed) > throw x >> return () -> _|_ > > ioError x `seq` () -> () > throw x `seq` () -> _|_ yes, when I say "one throw" I was referring to the argument type, not the return type. We should still have ioError - although it would probably be better named throwIO: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Excep tion.html#v%3AthrowIO (the docs for throwIO also mention the strictness property you described above) Cheers, Simon

2 1