April 2006 - Haskell-prime

RE: Specification of newtype deriving
by Simon Peyton-Jones 03 Apr '06

03 Apr '06

| By the way, the description in the GHC User's Guide 7.4.12.2: | | newtype T v1...vn = T' (S t1...tk vk+1...vn) deriving (c1...cm) | | is too restrictive in requiring that S must be a type constructor of | the same arity as T, forbidding things like | | newtype Wrap m a = Wrap (m a) deriving (Monad, Eq) | | It should be | | newtype T v1...vn = T' (t vk+1...vn) deriving (c1...cm) | | with vk+1...vn not free in the type expression t. It should also | mention that T may not be recursive, unless all the classes are | those derivable by the existing mechanism. (There is some | awkwardness in the overlap between the two mechanisms.) Good point. It turned out that the HEAD already implemented this, but because I hadn't thought of this case, I'd missed a test in the eta-ok test. So there was a lurking bug. I've fixed the documentation as you suggest too. Thanks for pointing this out Simon

1 0

terminating instances
by Ross Paterson 03 Apr '06

03 Apr '06

GHC 6.4 has rather conservative constraints on instances to guarantee termination. GHC 6.5 has more liberal constraints; see http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/FlexibleInsta… Unfortunately instances generated by newtype-deriving need not satisfy either of these constraints (but the newtypes are required to be non-recursive). I can't construct a problem example for the 6.4 rules (but nor is there an obvious termination ordering). However the following is non-terminating (caught by the depth limit) for GHC 6.5: class C a where foo :: a -> Bool -- instance C (f (Maybe a) a a) => C (Bar f a) newtype Bar f a = Bar (f (Maybe a) a a) deriving C instance C (Bar (,,) a) => C (a,b,c) where foo (a,b,c) = foo (Bar (Just a,a,a)) f = foo ('a', 'b', 'c')

1 0

RE: Concurrency
by Simon Marlow 03 Apr '06

03 Apr '06

On 31 March 2006 13:41, John Meacham wrote: > I have tried to summarize the current thinking into a proposal on the > wiki. > > http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/Concurrenc y > > I split it into 3 parts. > > the standard - all haskell' compilers must implement > > optional preemption - ability to preempt pure code, fairness > guarentees, interleaved evaluation operators (merge, nmerge) > > optional OS threads - bound threads, SMP, reentrant concurrent FFI > calls supported. > > comment or modify it at will. Great. Apart from my misgivings about allowing cooperative scheduling at all, here's a few comments on the proposal: - I wouldn't include threadWaitRead, threadWaitWrite, or threadDelay at all. These can all be implemented using FFI, so don't belong in the concurrency library. Their presence is largely historical. - yield bothers me a little. If it weren't for cooperative systems, yield would be semantically a no-op, because the no-starvation guarantee means you never need it for correctness. I think it's ok, just a bit unsettling. - In the optional OS threads section it says "allows multiple haskell threads to run at once" - actually you can provide all that without allowing multiple haskell threads to run at once, eg. ghc-6.4.1 with -threaded. I'll modify it. Cheers, Simon

1 0

state threads
by John Meacham 03 Apr '06

03 Apr '06

In case anyone was wondering what this state-threads thing I keep talking about is, here is a sample implementation (in C) as well as a lot of documentation and FAQs that apply to haskell as well. http://state-threads.sourceforge.net/ it should be noted that the chief disadvantage of state threads in C is not an issue for haskell (requiring an alternate IO library) A form of state threads can be implemented in pure haskell using the Poor Man's Concurrency monad described here: http://citeseer.ist.psu.edu/claessen99functional.html assuming you have the ability to use an 'epoll' or 'select' mechanism. However, this is probably not a suitable implementation method for high performance haskell implementations and does not address foreign concurrent calls. John -- John Meacham - ⑆repetae.net⑆john⑈

1 0

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

01 Apr '06

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

4 3

FD improvement, variable quantification & generalised propagation
by Claus Reinke 01 Apr '06

01 Apr '06

I've had some interesting off-list discussion with Tom Schrijvers (one of the guys responsible for the K.U.Leuven CHR System, which is provided, eg., in SWI Prolog). particularly interesting was the difference in perspective (logic vs functional programming). I'd like to share two items from that discussion (haven't thought either of them through yet, but hope they both provide useful food for thought to those of you interested in the type class problem). 1. I didn't have to explain to him that FDs may lead to variable instantiation, but I did have to explain why without FDs, there is no variable instantiation, and why we even think about FD consistency without automatically implying unification (improvement). the main difference here seems to be that he was thinking of all variables as existentially quantified, whereas type variables are mostly universally quantified, so far. I hadn't given that much thought before, because FDs are meant to determine their range types, and there isn't much difference between universal and existential quantification if there is only one possible variable value, eg: (forall a in {Char}. T a) vs (exists a in {Char}. T a) but perhaps some of the interpretation disagreements we have with FDs could be mitigated if we interpreted FDs differently, depending on whether the range type variables are universally or existentially quantified. given some 'class C a b | a -> b', we could try something like: - forall a b. C a b => T a b: no improvement for b, the FD is used only for checking consistency - forall a. exists b. C a b => T a b improvement & consistency check for b 2. he suggested that the whole problem may be an instance of generalised propagation: Generalised Constraint Propagation Over the CLP Scheme, by Thierry Le Provost and Mark Wallace. Journal of Logic Programming 16, July 1993. Also [ECRC-92-1] http://eclipse.crosscoreop.com:8080/eclipse/reports/ecrc_genprop.ps.gz I agree that this might be a useful framework in which to discuss further developments (variable instantiation is a lot more limited in our context, but we think about why and how to change that; we need to reason in an open world, but at least theoretically, we can collect all instances; we don't have multiple solutions, but we do sometimes need to look at instances before knowing all variable instantiations, leaving us with multiple possible matches, so approximation may be a useful alternative to full search for us, rather than just the optimisation it is in the logic case). any thoughts?-) cheers, claus

1 0