The goals of the concurrency standard?
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... ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: The goals of the concurrency standard?
Fortunatly, I don't expect these issues to be much of a problem in practice. (though, they certainly are real issues) the vast majority of programs, haskell ones included, are either interactive or batch. an interactive program spends most of its time waiting for user input or external events, responding, and in general using very little CPU, this is the sort of app threads are ideal for, text editors, chat clients, window managers, etc... batch programs are things like compilers or meresenne prime calcalculators, that tend to accept input, run for a while, and produce output. however, these types of programs rarely need concurrency. not that all programs fall into those categories, one can write their GUI enabled meresenne prime calculator, and then they will have to worry about such things. but at least with the standard they can now say 'this requires the OS threading option' rather than 'this requires GHC'. in any case, the situation you describe has been the case in GHC for a long time and has not seemed to hurt the use of concurrency for writing a lot of useful apps. However, I am also of the mind that preemtiveness alone doesn't buy enough to make the runtime cost of locking worth it which is why I plan for jhc to be fully cooperative or fully OS threaded with no middle ground. but the situation is different in compilers such as nhc, where preemptiveness can be added relatively easily due to its run-time design and absolute speed was never a goal. In any case, the standard should admit a range of implementations. though, your erlang example reminds me of a truely horrid hack I did with jhc once when experimenting with concurrency models, link two instances of haskell programs together and have them communicate via the FFI while running in different OS threads :) John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: limitations of newtype-derivings (fixed)
On 4/11/06, Simon Peyton-Jones [EMAIL PROTECTED] wrote: | 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. Speaking of which, how about simply qualifying a body-less instance with deriving, like this: deriving instance Show Foo -- Cheers, Dinko ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: collecting requirements for FDs
Hello, I just moved the documentation (still accessible from the below wiki page) to here: http://users.skynet.be/jyp/html/collections/Data.Collections.html the source being: http://darcs.haskell.org/packages/collections/Data/Collections.hs And, since you asked for it, there is something I think would be nice to have. As you may have found out by reading the above documentation, I've been trying to put Sets and Maps into the same class-framework. (Or, to put differently, unify collections and associative collections). The result of this, as Jim said, is I get two range parameters: class Map m k a | m - k a where ... The value type for sets being (). instance Map IntSet Int () where ... This is all very well, except that it complexifies some type contexts, and is also a bit restrictive in some respects: intersectionWith must have type (a - a - a) - m - m - m, instead of (a - b - c) - m a - m b - m c, if Map was (partially) a constructor class. One way to reconcile both approaches would be to have both classes: class Map m k a | m - k a where ... class Map_ m k | m - k where ... In order to avoid redundancy though, I'd wish to relate the classes like this: class Map (m a) k a = Map_ m k | m - k where ... This is rejected by GHC, and I suspect every current haskell implementation. Before you ask, I haven't worked out the implications in terms of confluence. But I thought I might just as well express my wish. :) Cheers, JP. On 4/11/06, Jim Apple [EMAIL PROTECTED] wrote: On 4/10/06, Ross Paterson [EMAIL PROTECTED] wrote: What other libraries should Haskell' support, and what are their requirements? http://hackage.haskell.org/trac/ghc/wiki/CollectionClassFramework There are two range arguments here, IIUC. Jim ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
On 12 April 2006 08:41, John Meacham wrote: However, I am also of the mind that preemtiveness alone doesn't buy enough to make the runtime cost of locking worth it which is why I plan for jhc to be fully cooperative or fully OS threaded with no middle ground. but the situation is different in compilers such as nhc, where preemptiveness can be added relatively easily due to its run-time design and absolute speed was never a goal. In any case, the standard should admit a range of implementations. Couldn't pre-emption be implemented quite easily in JHC if you compiled to C--? And imprecise exceptions, for that matter. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
On 12 April 2006 07:46, [EMAIL PROTECTED] wrote: 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? In cases where this happens, and it *does* happen, the programmer has to insert explicit seq or deepSeq. It's not a huge problem, at least no worse than the need to use seq/deepSeq to control resource usage or exception leakage. The code inside a lock/unlock sequence is usually quite short, and we can enumerate the free variables quite easily. One example where this happened in GHC is in the definition of putStr itself: our first implementation of putStr took the Handle lock, and then proceeded to traverse the string argument, filling the Handle's buffer with the characters. Unfortunately traversing the string takes arbitrary time, and might even invoke further putStrs (inside unsafePerformIO), so we had to rethink. The easy way is to deepSeq the string first, but that means traversing the string twice, and we don't like to make putStr any less efficient than it already is. So currently putStr works by grabbing a buffer from the Handle, and filling this buffer without holding the Handle lock. When the buffer is full, it gets committed. The Handle keeps a list of free buffers to avoid having to allocate a new one for each putStr. One side-effect of this is that putStrs from multiple threads can be interleaved in strange ways. Fortunately STM helps a lot here, too. (which doesn't mean much for Haskell', but at least it means we have a solution without completely redesigning Haskell'). If a transaction takes a long time because it is busy evaluating free variables, that doesn't prevent other transactions from completing. All that happens is the long-running transaction will probably be aborted due to conflicts with other transactions, but the next time it runs it will probably complete because the work already done isn't discarded. Conclusion: the programmer doesn't have to think about it. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: preemptive vs cooperative: attempt at formalization
On 11 April 2006 22:24, John Meacham wrote: 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 don't know what it means for a thread to have value _|_. A thread is defined by its observable effects, threads don't have values. 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. What if one of the threads never yields in a cooperative system? Even if it isn't calculating _|_, if it's just endlessly doing some pointless IO? Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
On 12 April 2006 11:03, John Meacham wrote: On Wed, Apr 12, 2006 at 10:24:57AM +0100, Simon Marlow wrote: On 12 April 2006 08:41, John Meacham wrote: However, I am also of the mind that preemtiveness alone doesn't buy enough to make the runtime cost of locking worth it which is why I plan for jhc to be fully cooperative or fully OS threaded with no middle ground. but the situation is different in compilers such as nhc, where preemptiveness can be added relatively easily due to its run-time design and absolute speed was never a goal. In any case, the standard should admit a range of implementations. Couldn't pre-emption be implemented quite easily in JHC if you compiled to C--? And imprecise exceptions, for that matter. no, it doesn't really help, the main things C-- provides over C are continuations and the introspection into the stack needed for garbage collection. everything c-- continuations would be useful for I am already using longjmp and setjmp for for cooperative concurrency. mainly jumping between multiple C stacks (which are the same as haskell stacks). the issues facing a preemptive implemenentation are that there is no way to implement black-holing, multiple threads will happily waste time evaluating the same thunk, but worse, updates would have to be protected by some sort of mutex or lock. jhc updates nodes in place, meaning a single atomic write to an indirection can't be used, to avoid a context switch in the middle of an update, either locks need to be placed around it, or run-time checks need to be made at safe points (which is arguably not much different than cooperative scheduling). I'll argue that point :) GHC makes run-time checks at safe points and implements preemptive concurrency. Cooperative scheduling is when the *programmer* has to insert the safe points. The safe points don't even have to be very often: in GHC the context switch check is made after every 4k of allocation. Point taken about black holes. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: preemptive vs cooperative: attempt at formalization
On Wed, Apr 12, 2006 at 10:58:32AM +0100, Simon Marlow wrote: I don't know what it means for a thread to have value _|_. A thread is defined by its observable effects, threads don't have values. sure they do, the value is just usually discarded. cooperative implementations are just the ones that don't have that luxury. :) What if one of the threads never yields in a cooperative system? Even if it isn't calculating _|_, if it's just endlessly doing some pointless IO? All real IO would have to effectively be a potential yield point. This is in practice assumed of any state threading implementation, but perhaps we should make it part of the standard to be sure. by real IO I mean reading/writing file descriptors and other interaction with the real world and not just anything in the IO monad. I don't think we need to do anything like enumerate the yield points or anything (except the 'yield' function of course), meeting the progress guarentee ensures a liberal sprinkling of them throughout the standard libs, in particular on any file descriptor read or write. Of course, if the user really wanted to, they could cheat using something like mmaping a file into memory and writing to that in a tight loop, but hopefully any user doing something like that would be aware of the ramifications. (heck, it would probably lock up the old version of ghc too if the tight loop thread never needed to GC) John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: The goals of the concurrency standard?
On Wed, Apr 12, 2006 at 11:19:53AM +0100, Simon Marlow wrote: I'll argue that point :) GHC makes run-time checks at safe points and implements preemptive concurrency. Cooperative scheduling is when the *programmer* has to insert the safe points. the programmer of the standard libraries or low level FFI interfaces. not the end programmer. I would be highly surprised if anyone other than system or very low level library implementors ever actually needed to use an explicit 'yield'. certainly a whole lot less often than they have to add 'seq's and it is a lot more clear when they are needed :) The safe points don't even have to be very often: in GHC the context switch check is made after every 4k of allocation. indeed, which means GHC technically doesn't meet the preemptive requirements since a tight mathematical non-allocating loop can halt it. in order to do true preemption, you'd need to respond to SIGALRM or something like that, which can be quite tricky. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: preemptive vs cooperative: attempt at formalization
John Meacham [EMAIL PROTECTED] wrote: 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: By infinite loop, you mean both non-terminating, and non-productive. A non-terminating but productive pure computation (e.g. ones = 1:ones) is not necessarily a problem. Why? Because ultimately the demand that forces production of the infinite data structure must come from somewhere, and that somewhere must essentially be I/O. (The only alternative consumers are terminating pure (no problem), non-terminating productive pure (so look upward to its demand), or an unproductive non-terminating computation, which brings us full circle.) It is a curious artifact that in certain multi-threaded implementations, a non-terminating non-productive thread does not make the entire system unproductive, but I don't think this is a behaviour anyone would want to rely on. I would say such a program has a bug, and the threaded RTS is just masking it. Regards, Malcolm ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
On 12 April 2006 11:30, John Meacham wrote: On Wed, Apr 12, 2006 at 11:19:53AM +0100, Simon Marlow wrote: The safe points don't even have to be very often: in GHC the context switch check is made after every 4k of allocation. indeed, which means GHC technically doesn't meet the preemptive requirements since a tight mathematical non-allocating loop can halt it. in order to do true preemption, you'd need to respond to SIGALRM or something like that, which can be quite tricky. Not at all, we could make non-allocating loops bump the heap pointer and do heap checks, but we choose not to. It's just a bug that we don't do this, and it virtually never happens in practice. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: deeqSeq proposal
On Apr 11, 2006, at 5:37 PM, Lennart Augustsson wrote: Yes, I realize than dynamic idempotence is not the same as cycle detection. I still worry. :) I think expectance is in the eye of the beholder. The reason that (the pure subset of) pH was a proper implementation of Haskell was because we were not over-specifying the semantics originally. I would hate to do that now. Though, to be fair, an awful lot of Prelude code didn't work in pH unless it was re-written to vary slightly from the specification. So the assumption of laziness was more deeply embedded than the spec was willing to acknowledge. -Jan-Willem Maessen -- Lennart Simon Peyton-Jones wrote: | Well, my worry was partly about the suggested version of deepSeq that | would not diverge on circular structures (since circular structures | are just one way to implement infinite data structures). Dynamic idempotence is not the same as detecting circular structures. Deepseqing a circular structure should definitely diverge, as it would as if it was infinite. Idempotence changes the operational behaviour, but not the denotational behaviour. So that part of the worry is ok. But since the dynamic-idempotence operational behaviour is (as I understand the proposal) the whole point, it's true that the implementation would be constrained. In the same kind of way that we expect call-by-need rather than call-by-name. S ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: postponing discussion on exceptions and deepSeq
On Tue, Apr 11, 2006 at 09:54:12PM -0400, Robert Dockins wrote: An additional issue is the following instance declarations, which require undecidable instances under GHC: Eq (s a) = Eq (Rev s a) (Sequence s, Read (s a)) = Read (Rev s a) (Sequence s, Show (s a)) = Show (Rev s a) These are accepted by GHC 6.5, under a relaxed termination condition that is a candidate for Haskell': http://www.haskell.org/ghc/dist/current/docs/users_guide/type-extensions.html#instance-rules ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: collecting requirements for FDs
Dear all, Ross Peterson wrote: The favourite customer for FDs has been the monad transformer library. ... What other libraries should Haskell' support, and what are their requirements? Here are some classes from Yampa/earlier versions of FRP. I shouldn't think they're particularly demanding. Also, I'm not saying these classes could not be defined differently/better. They are just examples of what seems to me reasonable uses of FDs. - -- Minimal instance: zeroVector, (*^), (^+^), dot class Floating a = VectorSpace v a | v - a where zeroVector :: v (*^) :: a - v - v (^/) :: v - a - v negateVector :: v - v (^+^):: v - v - v (^-^):: v - v - v dot :: v - v - a norm :: v - a normalize:: v - v -- -- Minimal instance: origin, .+^, .^. class (Floating a, VectorSpace v a) = AffineSpace p v a | p - v, v - a where origin :: p (.+^):: p - v - p (.-^):: p - v - p (.-.):: p - p - v distance :: p - p - a -- From an old version of FRP: FRPCore.lhs: class MixSwitchable s a b | s a - b where FRPCore.lhs: class Switchable s i | s - i where FRPCore.lhs: class RunningIn a b i | a - i where FRPCore.lhs: class ImpAs a b | a - b where FRPTask.lhs: class RunningInTask a t i | a t - i where FRPTask.lhs: class Monad m = StateMonad s m | m - s where FRPTask.lhs: class Monad m = EnvMonad env m | m - env where FRPTask.lhs: class GTask t = MsgTask t m | t - m where FRPTask.lhs: class MsgTaskMap mt m nt n | mt - m, nt - n where /Henrik -- Henrik Nilsson School of Computer Science and Information Technology The University of Nottingham [EMAIL PROTECTED] This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
Simon Marlow wrote: I agree. So other suggestions? longrunning? mightblock or mayblock? I don't like *block, because the question of blocking is irrelevant to this issue. It's about whether the foreign call returns sooner or later, not about whether it spends the time until then blocked or runnning. Personally, I'm still in favour of inverting this. We are not in court here, so every foreign function is guilty until proven innocent. Every foreign function might be longrunning unless the programmer happens to know otherwise. So maybe... returnsquickly? As far as I can gather, there are two arguments *against* making longrunning/concurrent the default: 1) It's not needed often, and it might be inefficient. 2) There might be implementations that don't support it at all (I might have convinced John that everyone should support it though..). 3) There might be implementations where concurrent calls run on a different thread than nonconcurrent calls. Now I don't buy argument 1; For me the safety/expected behaviour/easy for beginners argument easily trumps the performance argument. ad 3). For implementations that don't support Bound Threads, John Meacham proposed saying that nonconcurrent calls are guaranteed to be executed on the main OS thread, but no guarantees where made about concurrent calls; that makes a lot of sense implementation-wise. However, this means that calls to the main loops for GLUT, Carbon and Cocoa (and maybe others) have to be annotated nonconcurrent/returnsquickly despite the fact that they return only after a long time, just to keep access to the right thread-local state. I see a big fat #ifdef heading our way. Cheers, Wolfgang ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: preemptive vs cooperative: attempt at formalization
Simon Marlow [EMAIL PROTECTED] wrote: By infinite loop, you mean both non-terminating, and non-productive. A non-terminating but productive pure computation (e.g. ones = 1:ones) is not necessarily a problem. That's slightly odd terminology. ones = 1:ones is definitely terminating. (length ones) is not, though. Well, the expression ones on its own is non-terminating. So if you say putStrLn (show ones), it doesn't just sit there doing nothing. This infinite computation produces an infinite output. So the fact that it is non-terminating is irrelevant. I may very well want a thread to do exactly that, and even with a cooperative scheduler this is perfectly OK. Other threads will still run just fine. The only time when other threads will *not* run under cooperative scheduling is when the non-terminating pure computation is *also* unproductive (like your length ones). Maybe you could expand on in what sense you mean non-terminating, and what productive means? I'm using productive to mean it generates a WHNF in finite time, even if the full normal form takes infinite time. Is there something we need to worry about here? No, I don't think so. John was attempting to formalise an observable difference between scheduling strategies, in much the manner that one sees the strictness of functions being defined. I am pointing out that the situation with threads is not analogous. f _|_ == _|_-- function is strict f _|_ /= _|_-- function is non-strict If you consider f to be the scheduler, and its arguments to be all available threads, then schedule threads | any (==_|_) threads == _|_ means we have a cooperative scheduler. The converse schedule threads | any (==_|_) threads =/= _|_ means we have a preemptive scheduler. The argument John was making is that this is a useful distinguishing point to tell whether your concurrent implementation is cooperative or preemptive. My argument is that, even if you can distinguish them in this way, it is not a useful distinction to make. Your program is simply wrong. If you have a sequential program whose value is _|_, your program is bad. If you execute it in parallel with other programs, that does not make it any less bad. One scheduler reveals the wrongness by hanging, another hides the wrongness by letting other things happen. So what? It would be perverse to say that the preemptive scheduler is semantically better in this situation. Regards, Malcolm ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FDs and confluence
On Mon, Apr 10, 2006 at 02:39:18PM +0100, Claus Reinke wrote: class B a b | a - b class C a b c | a - b instance B a b = C [a] b Bool Starting from a constraint set C [a] b Bool, C [a] c d, [...] CHR-alt: B a b = infer_B a b, memo_B a b. memo_B a b1, memo_B a b2 ==b1=b2. C a b c = infer_C a b c, memo_C a b c. memo_C a b1 c1, memo_C a b2 c2 == b1=b2. infer_C [a] b Bool = B a b. memo_C [a] b' c' == b'=b. OK, so you want to modify the usual instance reduction rule by recording functional dependencies from the head. That is, you get confluence by remembering all the choices you had along the way, so you can still take them later. My problem with this scheme is that it makes FDs an essential part of the semantics, rather than just a shortcut, as they are in the original system. With the old system, one can understand instances using a Herbrand model, determined by the instance declarations alone. If the instances respect FDs, types can be made more specific using improvement rules justified by that semantics. With your system, there's only the operational semantics. The logical semantics of the original CHR program and that of Claus with the memoization is really the same, I'm sure. The justifiable improvemetns are exactly the same. The main difference is that the memoization makes the rules confluent in more cases, i.e. the difference is in the operational semantics. For that matter the operational semantics of the confluent program would be considered to capture more completely the logical semantics and justifiable improvements. To understand types, programmers must operate the rewriting system. Not at all. The confluent program is really more intuitive, because more of the logically justifiable improvements are done. And the constraint store they must work with will be quite cluttered with all these memoized FDs. This is more of an implementation issue than a conceptual one, isn't it? I can think of a number of optimizations already to reduce the overhead. In the above example, the third argument is not involved in the FD, so does not have to be remembered, yielding: memo_C a b1, memo_C a b2 == b1=b2. Secondly, you only need to keep one of a number of identical copies. In CHR there is what's called a simpagation rule: memo_C a b1 \ memo_C a b2 = b1=b2. that removes the constraint after the backslash. Here it's valid because that constraint becomes identical to the first one. Moreover, very few people will actually have to look at the constraint store, I think. -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: [EMAIL PROTECTED] ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
On Wed, Apr 12, 2006 at 12:07:06PM -0400, Wolfgang Thaller wrote: 3) There might be implementations where concurrent calls run on a different thread than nonconcurrent calls. this is necessarily true for non-OS threaded implementations. there is no other way to wait for an arbitrary C call to end than to spawn a thread to run it in. This doesn't have to do with bound threads, to support those you just need to make sure the other thread you run concurrent calls on is always the same thread. it is the cost of setting up the mechanism to pass control to the other thread and wait for the response that is an issue. turning a single call instruction into several system calls, some memory mashing and a context switch or two. I object to the idea that concurrent calls are 'safer'. getting it wrong either way is a bug. it should fail in the most obvious way rather than the way that can remain hidden for a long time. in any case, blocking is a pretty well defined operation on operating systems, it is when the kernel can context switch you away waiting for a resource, which is the main use of concurrent calls. the ability to use them for long calculations in C is a sort of bonus, the actual main use is to ensure the progress guarentee, that if the OS is going to take away the CPU because one part of your program is waiting for something another part of your program can make progress. Which is why I'd prefer some term involving 'blocking' because that is the issue. blocking calls are exactly those you need to make concurrent in order to ensure the progress guarentee. sayng something like 'takesawhile' muddies things, what is a while? not that concurrent calls shouldn't be used for long C calculations, it is quite a nice if uncommonly needed perk, but I don't want the report to confuse matters by making a quantitative real matter, meeting the progress guarentee, with a qualitiative one does this take a while. I'd actually prefer it if there were no default and it had to be specified in neutral language because I think this is one of those things I want FFI library writers to think about. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: deeqSeq proposal
On Wed, Apr 12, 2006 at 09:21:10AM -0400, Jan-Willem Maessen wrote: Though, to be fair, an awful lot of Prelude code didn't work in pH unless it was re-written to vary slightly from the specification. So the assumption of laziness was more deeply embedded than the spec was willing to acknowledge. out of curiosity what sort of things had to be rewritten? I have been toying with the idea of relaxing sharing to help some optimizations and was curious what I was in for. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: preemptive vs cooperative: attempt at formalization
On Wed, Apr 12, 2006 at 05:50:40PM +0100, Malcolm Wallace wrote: The argument John was making is that this is a useful distinguishing point to tell whether your concurrent implementation is cooperative or preemptive. My argument is that, even if you can distinguish them in this way, it is not a useful distinction to make. Your program is simply wrong. If you have a sequential program whose value is _|_, your program is bad. If you execute it in parallel with other programs, that does not make it any less bad. One scheduler reveals the wrongness by hanging, another hides the wrongness by letting other things happen. So what? It would be perverse to say that the preemptive scheduler is semantically better in this situation. Oh, I didn't mean it was necessarily a useful quality to the end programmer, I was actually just trying to make the point you were making that such programs are incorrect and getting the non-termination case over with. So we can get to the fairness discussion without adding caveats like if no thread is in an infinite loop. But I didn't want to just say assuming your program is correct without giving some indication of what that actually means for a program to be correct. In any case, it is something we can point to and say this! this is a difference! whether it is a useful one or not. now for the contrived counter-example :) start two threads, one trying to prove goldbachs conjecture, the other trying to find a refutation. in a preemptive system this will terminate*, in a cooperative system it may not. John * insert goedel incompleteness caveat. -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
FD use cases (was Re: postponing discussion on exceptions and deepSeq)
isaac jones [EMAIL PROTECTED] wrote: 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? Personally, I have never used FDs, but I recall some discussion we had in the Hat tracing project about the possibility of using them to solve a problem we had. (In the end, I think we decided it was either too complex, or the particular FD use case was not supported by any compiler.) The idea was to drop from traced computations down to the original computations (unwrap), and lift them back up again (wrap), in order to run trusted code at the original speed. This class looks something like class Wrap a b | a - b, b - a where wrap :: a - R b unwrap :: R b - a Nothing too unusual I'm sure. But there are some subtleties to do with the way this class interacts with other classes. A sketch of these is given in a short memo, attached to the wiki under Use Cases at http://hackage.haskell.org/trac/haskell-prime/wiki/FunctionalDependencies The relevant section is 3.2. One interesting thing to note for the FD discussion is the need/possibility of defining the same multi-parameter class at several different kinds. Regards, Malcolm ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
On 4/12/06, Wolfgang Thaller [EMAIL PROTECTED] wrote: Personally, I'm still in favour of inverting this. We are not in court here, so every foreign function is guilty until proven innocent. Every foreign function might be longrunning unless the programmer happens to know otherwise. So maybe... returnsquickly? Hear, hear: fast - takes very little time to execute pure - side-effect free nocallback - does not call back into Haskell -- Taral [EMAIL PROTECTED] You can't prove anything. -- Gödel's Incompetence Theorem ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
On Wed, Apr 12, 2006 at 04:40:29PM -0500, Taral wrote: pure - side-effect free we don't really need pure because not having an IO type in the result implies pure. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
John Meacham [EMAIL PROTECTED] writes: I object to the idea that concurrent calls are 'safer'. getting it wrong either way is a bug. it should fail in the most obvious way rather than the way that can remain hidden for a long time. I wouldn't consider it a bug of an implementation if it makes a call behave like concurrent when it's specified as non-concurrent. If a library wants to make it a critical section, it should use a mutex (MVar). Or there should be another kind of foreign call which requires serialization of calls. But of which calls? it's rarely the case that it needs to be serialized with other calls to the same function only, and also rare that it must be serialized with everything else, so the granularity of the mutex must be explicit. It's fine to code the mutex explicitly if there is a kosher way to make it global. Non-concurrent calls which really blocks other thread should be treated only as an efficiency trick, as in implementations where the runtime is non-reentrant and dispatches threads running Haskell code internally, making such call without ensuring that other Haskell threads have other OS threads to run them is faster. OTOH in implementations which run Haskell threads truly in parallel, the natural default is to let C code behave concurrently. Ensuring that it is serialized would require extra work which is counter-productive. For functions like sqrt() the programmer wants to say that there is no need to make it concurrent, without also saying that it requires calls to be serialized. Which is why I'd prefer some term involving 'blocking' because that is the issue. blocking calls are exactly those you need to make concurrent in order to ensure the progress guarentee. What about getaddrinfo()? It doesn't synchronize with the rest of the program, it will eventually complete no matter whether other threads make progress, so making it concurrent is not necessary for correctness. It should be made concurrent nevertheless because it might take a long time. It does block; if it didn't block but needed the same time for an internal computation which doesn't go back to Haskell, it would still benefit from making the call concurrent. It is true that concurrent calls often coincide with blocking. It's simply the most common reason for a single non-calling-back function to take a long time, and one which can often be predicted statically (operations of extremely long integers might take a long time too, but it would be hard to differentiate them from the most which don't). The name 'concurrent' would be fine with me if the default is 'not necessarily concurrent'. If concurrent calls are the default, the name 'nonconcurrent' is not so good, because it would seem to imply some serialization which is not mandatory. -- __( Marcin Kowalczyk \__/ [EMAIL PROTECTED] ^^ http://qrnik.knm.org.pl/~qrczak/ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
On Thu, Apr 13, 2006 at 12:43:26AM +0200, Marcin 'Qrczak' Kowalczyk wrote: What about getaddrinfo()? It doesn't synchronize with the rest of the program, it will eventually complete no matter whether other threads make progress, so making it concurrent is not necessary for correctness. It should be made concurrent nevertheless because it might take a long time. It does block; if it didn't block but needed the same time for an internal computation which doesn't go back to Haskell, it would still benefit from making the call concurrent. getaddrinfo most definitly blocks so should be made concurrent, it uses sockets internally. The progress guarentee is meant to imply if something can effectivly use the CPU it will be given it if nothing else is using it not that it will just eventually complete. Performing a long calculation is progress whether in haskell or C, waiting on a file descriptor isn't. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
John Meacham wrote: This doesn't have to do with bound threads, [...] I brought it up because the implementation you are proposing fullfills the most important feature provided by bound threads, namely to be able to access the thread local state of the main OS thread (the one that runs C main ()), only for nonconcurrent calls, but not concurrent calls. This gives people a reason to specify some calls as nonconcurrent, even when they are actually expected to block, and it is desirable for other threads to continue running. This creates an implementation-specific link between the concurrent/ nonconcurrent question and support for OS-thread-local-state. I would probably end up writing different code for different Haskell implemlementations in this situation. Note that some predictable way of interacting with OS threads (and OS- thread local state) is necessary in order to be able to use some libraries at all, so not using OS threads *at all* might not be a feasible method of implementing a general-purpose programming language (or at least, not a feasible implementation method for general purpose implementations of general purpose programming languages). The whole point of having bound threads is to NOT require a 1:1 correspondence between OS threads and Haskell threads but still be able to interact with libraries that use OS-thread-local-state. They allow implementers to use OS threads just for *some* threads (i.e. just where necessary), while still having full efficiency and freedom of implementation for the other (non-bound) threads. There might be simpler schemes that can support libraries requiring OS-thread-local-state for the most common use cases, but there is a danger that it will interact with the concurrent/nonconcurrent issue in implementation-specific ways if we don't pay attention. I object to the idea that concurrent calls are 'safer'. getting it wrong either way is a bug. it should fail in the most obvious way rather than the way that can remain hidden for a long time. How can making a call concurrent rather than nonconcurrent ever be a bug? in any case, blocking is a pretty well defined operation on operating systems, it is when the kernel can context switch you away waiting for a resource, which is the main use of concurrent calls. the ability to use them for long calculations in C is a sort of bonus, the actual main use is to ensure the progress guarentee, I disagree with this. First, concurrent calls serve a real-world purpose for all interactive programs. GUI applications are soft realtime systems; if a GUI application stops processing events for more than 2 seconds (under regular system load), I consider it buggy. Second, although blocking is well-defined for kernel operations, the documented interface of most libraries does not include any guarantees on whether they will block the process or not; sometimes the difference might be entirely irrelevant; does it make a difference whether a drawing function in a library writes to video memory or sends an X request accross the network? Saying something takesawhile doesn't muddy things; it is a strictly weaker condition than whether something blocks. Calculations done by foreign calls are not a bonus, but an important use case for concurrent calls. Think of a library call that causes a multimedia library to recompress an entire video file; estimated time required is between a few seconds and a day. In a multithreaded program, this call needs to be concurrent. It is true that the program will still terminate even if the call is nonconcurrent, but in the real world, termination will probably occur by the user choosing to force quit an application that is not responding (also known as sending SIGTERM or even SIGKILL). Reducing the issue to the question whether a function blocks or not is just plain wrong. I'd actually prefer it if there were no default and it had to be specified in neutral language because I think this is one of those things I want FFI library writers to think about. But as I have been saying, the decision that FFI library writers have to make, or rather the only decision that they *can* make, is the simple decision of can I guarantee that this call will return to its caller (or reenter Haskell via a callback) before the rest of the program is negatively affected by a pause. If the function could block, the answer is a definite no, otherwise the question is inherently fuzzy. Unfortunately, I don't see a way of avoiding this fuzziness. The question can I provide a certain guarantee or not could be answered with no by default to flatten the learning curve a bit. My objection against having no default is not very strong, but I do object to specifying this in neutral language. This situation does not call for neutral language; rather, it has to be made clear that one of the options comes
Re: FFI, safe vs unsafe
On Wed, Apr 12, 2006 at 07:35:22PM -0400, Wolfgang Thaller wrote: John Meacham wrote: This doesn't have to do with bound threads, [...] I brought it up because the implementation you are proposing fullfills the most important feature provided by bound threads, namely to be able to access the thread local state of the main OS thread (the one that runs C main ()), only for nonconcurrent calls, but not concurrent calls. This gives people a reason to specify some calls as nonconcurrent, even when they are actually expected to block, and it is desirable for other threads to continue running. This creates an implementation-specific link between the concurrent/ nonconcurrent question and support for OS-thread-local-state. I would probably end up writing different code for different Haskell implemlementations in this situation. Oh, I made that proposal a while ago as a first draft, bound threads should be possible whether calls are concurrent or not, I am not positive I like the ghc semantics, but bound threads themselves pose not much more overhead than supporting concurrent in the first place (which is a fairly substantial overhead to begin with). but that doesn't matter to me if there isn't a performance impact in the case where they arn't used. However, in order to achieve that we would have to annotate the foreign functions with whether they use thread local state. it would pretty much be vital for implementing them efficiently on a non OS-threaded implemenation of the language. you need to perform a stack-pass-the-baton dance between threads to pass the haskell stack to the right OS thread which is a substantial overhead you can't pay just in case it might be running in a 'forkOS' created thread. Checking thread local state for _every_ foregin call is definitly not an option either. (but for specificially annotated ones it is fine.) ghc doesn't have this issue because it can have multiple haskell threads running at once on different OS threads, so it just needs to create one that doesn't jump between threads and let foreign calls proceed naturally. non-os threaded implementations have the opposite problem, they need to support a haskell thread that _can_ (and does) jump between OS threads. one pays the cost at thread creation time, the other pays the cost at foreign call time. the only way to reconcile these would be to annotate both. (which is perfectly fine by me if bound threads are needed, which I presume they are) Oddly enough, depending on the implementation it might actually be easier to just make every 'threadlocal' function fully concurrent. you have already paid the cost of dealing with OS threads. Calculations done by foreign calls are not a bonus, but an important use case for concurrent calls. Think of a library call that causes a multimedia library to recompress an entire video file; estimated time required is between a few seconds and a day. In a multithreaded program, this call needs to be concurrent. It is true that the program will still terminate even if the call is nonconcurrent, but in the real world, termination will probably occur by the user choosing to force quit an application that is not responding (also known as sending SIGTERM or even SIGKILL). they are a bonus in that you can't run concurrent computing haskell threads at the same time. you get free concurrent threads in other languages that you would not get if the libraries just happened to be implemented in haskell. However, if the libraries were implemented in haskell, you would still get concurrency on OS blocking events because the progress guarentee says so. The question can I provide a certain guarantee or not could be answered with no by default to flatten the learning curve a bit. My objection against having no default is not very strong, but I do object to specifying this in neutral language. This situation does not call for neutral language; rather, it has to be made clear that one of the options comes with a proof obligation and the other only with a performance penalty. you seem to be contradicting yourself, above you say a performance penalty is vitally important in the GUI case if a call takes too long, but here you call it 'just a performance penalty'. The overhead of concurrent calls is quite substantial. Who is to say whether a app that muddles along is better or worse than one that is generally snappy but has an occasional delay. Though, I am a fan of neutral language in general. you can't crash the system like you can with unsafePerformIO, FFI calls that take a while and arn't already wrapped by the standard libraries are relatively rare. no need for strong language. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
Simon Marlow wrote: 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? In cases where this happens, and it *does* happen, the programmer has to insert explicit seq or deepSeq. It's not a huge problem, at least no worse than the need to use seq/deepSeq to control resource usage or exception leakage. The code inside a lock/unlock sequence is usually quite short, and we can enumerate the free variables quite easily. My main trouble is foundational. The very need to use seq/deepSeq is quite disturbing: in the above example, we must use those constructions (and so, deepSeq must be standardized, if we take this route). Evaluation time (and divergence) is certainly an effect; when composing with another effect such as locking, we must be able to specify the exact sequence of those effects. Essentially, the need for seq/deepSeq seems to tell that non-strict evaluation is an inadequate computational model in the example at hand. Incidentally, the need to manually insert deepSeq isn't that much different from the need to insert safe points? In both cases, the programmer must be aware how much of the computation has already been done at (some) program points, and be able to control the amount of computation done. Strictly speaking, none of that is possible under non-strict evaluation. Fortunately STM helps a lot here, too. Yes, it does. The previous message pointed out that the STM model seems to be similar to the one used in Erlang. With STM, we can keep lazy evaluation and the programmer does not need to think of seq/deepSeq, etc. But there is a price to pay: we can't use FFI while in the STM monad, we can't use IORefs and we can't use MVars. Right? So, if the STM model is to become the default one (which would be a great thing), FFI and the whole IO will have to be re-designed, and IORefs and MVars removed from the language. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: FFI, safe vs unsafe
John Meacham wrote: However, in order to achieve that we would have to annotate the foreign functions with whether they use thread local state. I am not opposed to that; however, you might not like that here again, there would be the safe, possibly inefficient default choice, which means might access thread local data, and the possibly more efficient annotation that comes with a proof obligation, which says guaranteed not to access thread local data. The main counterargument is that some libraries, like OpenGL require many *fast* nonconcurrent, nonreentrant but tls-using calls (and, nost likely, one reentrant and possibly concurrent call for the GLUT main event loop). Using OpenGL would probably be infeasible from an implementation which requires a notls annotation to make foreign imports fast. it would pretty much be vital for implementing them efficiently on a non OS-threaded implemenation of the language. True, with the implementation plan you've outlined so far. Have you considered hybrid models where most threads are state threads (all running in one OS thread) and a few threads (=the bound threads) are OS threads which are prevented from actually executing in parallel by a few well-placed locks and condition variables? You could basically write an wrapper around the state threads and pthreads libraries, and you'd get the best of both worlds. I feel it wouldn't be that hard to implement, either. Oddly enough, depending on the implementation it might actually be easier to just make every 'threadlocal' function fully concurrent. you have already paid the cost of dealing with OS threads. Depending on the implementation, yes. This is the case for the inefficient implementation we recommended for interpreters like Hugs in our bound threads paper; there, the implementation might be constrained by the fact that Hugs implements cooperative threading in Haskell using continuation passing in the IO monad; the interpreter itself doesn't even really know about threads. For jhc, I fell that a hybrid implementation would be better. they are a bonus in that you can't run concurrent computing haskell threads at the same time. you get free concurrent threads in other languages that you would not get if the libraries just happened to be implemented in haskell. However, if the libraries were implemented in haskell, you would still get concurrency on OS blocking events because the progress guarentee says so. Hmm... it sounds like you've been assuming cooperative scheduling, while I've been assuming preemptive scheduling (at least GHC-style preemption, which only checks after x bytes of allocation). Maybe, in a cooperative system, it is a little bit of a bonus, although I'd still want it for practical reasons. I can make my Haskell computations call yield, but how do I make a foreign library (whose author will just say Let them use threads) cooperate? In a preemtive system, the ability to run a C computation in the background remains a normal use case, not a bonus. The question can I provide a certain guarantee or not could be answered with no by default to flatten the learning curve a bit. My objection against having no default is not very strong, but I do object to specifying this in neutral language. This situation does not call for neutral language; rather, it has to be made clear that one of the options comes with a proof obligation and the other only with a performance penalty. you seem to be contradicting yourself, above you say a performance penalty is vitally important in the GUI case if a call takes too long, [...] I am not. What I was talking about above was not performance, but responsiveness; it's somewhat related to fairness in scheduling. If a foreign call takes 10 microseconds instead of 10 nanoseconds, that is a performance penalty that will matter in some circumstances, and not in others (after all, people are writing real programs in Python...). If a GUI does not respond to events for more than two seconds, it is badly written. If the computer or the programming language implementation are just too slow (performance) to achieve a certain task in that time, the Right Thing To Do is to put up a progress bar and keep processing screen update events while doing it, or even do it entirely in the background. Of course, responsiveness is not an issue for non-interactive processes, but for GUIs it is very important. Who is to say whether a app that muddles along is better or worse than one that is generally snappy but has an occasional delay. I am ;-). Apart from that, I feel that is a false dichotomy, as even a factor 1000 slowdown in foreign calls is no excuse to make a GUI generally muddle along. Though, I am a fan of neutral language in general. you can't crash the system like you can with unsafePerformIO, FFI calls that take a while and arn't already wrapped by the standard libraries
Re: FFI, safe vs unsafe
On Wed, Apr 12, 2006 at 11:37:57PM -0400, Wolfgang Thaller wrote: John Meacham wrote: However, in order to achieve that we would have to annotate the foreign functions with whether they use thread local state. I am not opposed to that; however, you might not like that here again, there would be the safe, possibly inefficient default choice, which means might access thread local data, and the possibly more efficient annotation that comes with a proof obligation, which says guaranteed not to access thread local data. The main counterargument is that some libraries, like OpenGL require many *fast* nonconcurrent, nonreentrant but tls-using calls (and, nost likely, one reentrant and possibly concurrent call for the GLUT main event loop). Using OpenGL would probably be infeasible from an implementation which requires a notls annotation to make foreign imports fast. this is getting absurd, 95% of foreign imports are going to be nonreentrant, nonconcurrent, nonthreadlocalusing. Worrying about the minor inconvinience of the small chance someone might accidentally writing buggy code is silly when you have 'peek' and 'poke' and the ability to just deadlock right out there in the open. The FFI is inherently unsafe. We do not need to coddle the programer who is writing raw FFI code. _any_ time you use the FFI there are a large number of proof obligations you are commiting to that arn't necessarily apparent, why make these _very rare_ cases so visible. There is a reason they arn't named 'unsafePoke' and 'unsafePeek', the convinience of using the names poke and peek outweighs the unsafety concern becaues you are already using the FFI and already know everything is unsafe and you need to be careful. these problems can't even crash the runtime, way safer than a lot of the unannotated routines in the FFI. it would pretty much be vital for implementing them efficiently on a non OS-threaded implemenation of the language. True, with the implementation plan you've outlined so far. Have you considered hybrid models where most threads are state threads (all running in one OS thread) and a few threads (=the bound threads) are OS threads which are prevented from actually executing in parallel by a few well-placed locks and condition variables? You could basically write an wrapper around the state threads and pthreads libraries, and you'd get the best of both worlds. I feel it wouldn't be that hard to implement, either. well, I plan a hybrid model of some sort, simply because it is needed to support foreign concurrent calls. exactly where I will draw the line between them is still up in the air. but in any case, I really like explicit annotations on everything as we can't predict what future implementations might come about so we should play it safe in the standard. Oddly enough, depending on the implementation it might actually be easier to just make every 'threadlocal' function fully concurrent. you have already paid the cost of dealing with OS threads. Depending on the implementation, yes. This is the case for the inefficient implementation we recommended for interpreters like Hugs in our bound threads paper; there, the implementation might be constrained by the fact that Hugs implements cooperative threading in Haskell using continuation passing in the IO monad; the interpreter itself doesn't even really know about threads. For jhc, I fell that a hybrid implementation would be better. yeah, what I am planning is just providing a create new stack and jump to a different stack(longjmp) primitive, and everything else being implemented in haskell as a part of the standard libraries. (with liberal use of the FFI to call things like pthread_create and epoll) so actually fairly close to the hugs implementation in that it is mostly haskell based, but with some better primitives to work with. (from what I understand of how hugs works) you seem to be contradicting yourself, above you say a performance penalty is vitally important in the GUI case if a call takes too long, [...] I am not. What I was talking about above was not performance, but responsiveness; it's somewhat related to fairness in scheduling. If a foreign call takes 10 microseconds instead of 10 nanoseconds, that is a performance penalty that will matter in some circumstances, and not in others (after all, people are writing real programs in Python...). If a GUI does not respond to events for more than two seconds, it is badly written. If the computer or the programming language implementation are just too slow (performance) to achieve a certain task in that time, the Right Thing To Do is to put up a progress bar and keep processing screen update events while doing it, or even do it entirely in the background. Of course, responsiveness is not an issue for non-interactive processes, but for GUIs it is very important. at some point,
