- Glasgow-haskell-users

instance inference
by Ross Paterson 12 Dec '05

12 Dec '05

I'm puzzled that the following is accepted. Is some sort of greatest fixed point computation used for instances? {-# OPTIONS_GHC -fglasgow-exts #-} module M where class C a b where c :: a -> b -> Bool instance C b b => C (Maybe a) b where c x y = c y y f :: Maybe a -> Bool f x = c x x

1 0

RE: recommended build system
by Simon Marlow 10 Dec '05

10 Dec '05

The nightly binary snapshots for x86/Linux are currently hard-wired to use gcc-3.4.3, because I occasionally change gcc versions to make sure things are still working. I'll change it back to gcc. To workaround it you can add '-pgmc gcc' to the command line. Cheers, Simon On 09 December 2005 03:26, Frederik Eaton wrote: > Does this depend on a certain version of gcc? > > $ ghc -M --make Matrix.hs -o matrix > Chasing modules from: Matrix.hs > [1 of 2] Compiling Fu.Prepose ( Fu/Prepose.hs, Fu/Prepose.o ) > ghc-6.5.20051207: could not execute: gcc-3.4.3 > > I'm wondering why it is trying to execute something which isn't in my > path... > > Frederik > > On Mon, Dec 05, 2005 at 10:51:19AM -0000, Simon Peyton-Jones wrote: >> Simon fixed this recently. The GHC HEAD build will not re-link with >> --make if none of the object files have changed. >> >> Simon >> >>> -----Original Message----- >>> From: glasgow-haskell-users-bounces(a)haskell.org >>> [mailto:glasgow-haskell-users- bounces(a)haskell.org] On Behalf Of >>> Frederik Eaton >>> Sent: 04 December 2005 00:46 >>> To: glasgow-haskell-users(a)haskell.org >>> Subject: recommended build system >>> >>> Hi all, >>> >>> I'm looking for a build system for my projects which will correctly >>> handle all of ghc's dependencies. I.e. every time I ask it to >>> rebuild an output file, it will only do the minimum amount of >>> compilation necessary. This is important to me because "ghc --make" >>> and cabal currently (AFAICT) will always relink an executable even >>> when it is not necessary to do so; thus if I have a project with a >>> bunch of libraries and executables, the cost of making a small >>> modification and recompiling is very high, and it becomes hard to >>> maintain focus on my projects after the initial design phase. I've >>> just been playing around with GNU coreutils and was impressed with >>> how well the build system works, and how fast the recompilation >>> goes. >>> >>> Anyway, the system that darcs uses seems to work pretty well, >>> should I copy that, or do people recommend other alternatives? >>> >>> Frederik >>> _______________________________________________ >>> Glasgow-haskell-users mailing list >>> Glasgow-haskell-users(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users >> _______________________________________________ >> Glasgow-haskell-users mailing list >> Glasgow-haskell-users(a)haskell.org >> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users >> > _______________________________________________ > Glasgow-haskell-users mailing list > Glasgow-haskell-users(a)haskell.org > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

2 2

RE: Optimizations for mutable structures?
by Simon Marlow 09 Dec '05

09 Dec '05

On 07 December 2005 16:38, Malcolm Wallace wrote: > "Simon Marlow" <simonmar(a)microsoft.com> writes: > >> I should have said that if 'acts' blocks, then the transformation is >> invalid. > > Well that is exactly what I was assuming when I said that the > transformation is invalid. In the general case, for some arbitrary > actions between the write and the read (excluding another write of > course), there is no guarantee that the IORef remains unmodified. This is an analysis that's performed all the time in C compilers, it's quite straightforward to do a good approximation. One simple algorithm is: a store can be forwarded to a matching read as long as there are no intervening writes that may alias, or function calls. C does this and C has threads, so what's the difference? > If you want to restrict the intermediate actions to be non-blocking, > such that another thread cannot run, then that is an extra (and > significant) proof obligation. > > And AFAICS your non-blocking argument only applies to co-operative > scheduling. If pre-emption is permitted (e.g. interrupt-handling), > then all bets are off, because an arbitrary thread could write to > the IORef at any moment. No, that is exactly what I disagree with. Faced with non-derministic semantics, the compiler does *not* have to preserve all possible outcomes. In other words, it does not have to assume that an IORef can be modified between any two arbitrary instructions. If we had to assume this, then indeed all bets would be off, and C compilers would be very much more restricted in what optimisations they could perform. I don't know how I can explain this a different way - it seems pretty obvious to me, but I'm probably not explaining it well :-/ You cut the example from my message - did you agree with the conclusion? Or the conclusion I made from Ian's example? Cheers, Simon

7 7

RE: recommended build system
by Simon Marlow 09 Dec '05

09 Dec '05

This doesn't affect the source snapshots, only the Linux/x86 binaries. I think there are more people using the sources and the Linux/x86_64 binaries. Cheers, Simon On 09 December 2005 10:26, Frederik Eaton wrote: > Would I be the only user of the nightly binary snapshots? > > Frederik > > On Fri, Dec 09, 2005 at 09:23:16AM -0000, Simon Marlow wrote: >> The nightly binary snapshots for x86/Linux are currently hard-wired >> to use gcc-3.4.3, because I occasionally change gcc versions to make >> sure things are still working. I'll change it back to gcc. To >> workaround it you can add '-pgmc gcc' to the command line. >> >> Cheers, >> Simon >> >> On 09 December 2005 03:26, Frederik Eaton wrote: >> >>> Does this depend on a certain version of gcc? >>> >>> $ ghc -M --make Matrix.hs -o matrix >>> Chasing modules from: Matrix.hs >>> [1 of 2] Compiling Fu.Prepose ( Fu/Prepose.hs, Fu/Prepose.o ) >>> ghc-6.5.20051207: could not execute: gcc-3.4.3 >>> >>> I'm wondering why it is trying to execute something which isn't in >>> my path... >>> >>> Frederik >>> >>> On Mon, Dec 05, 2005 at 10:51:19AM -0000, Simon Peyton-Jones wrote: >>>> Simon fixed this recently. The GHC HEAD build will not re-link >>>> with --make if none of the object files have changed. >>>> >>>> Simon >>>> >>>>> -----Original Message----- >>>>> From: glasgow-haskell-users-bounces(a)haskell.org >>>>> [mailto:glasgow-haskell-users- bounces(a)haskell.org] On Behalf Of >>>>> Frederik Eaton Sent: 04 December 2005 00:46 >>>>> To: glasgow-haskell-users(a)haskell.org >>>>> Subject: recommended build system >>>>> >>>>> Hi all, >>>>> >>>>> I'm looking for a build system for my projects which will >>>>> correctly handle all of ghc's dependencies. I.e. every time I ask >>>>> it to rebuild an output file, it will only do the minimum amount >>>>> of compilation necessary. This is important to me because "ghc >>>>> --make" and cabal currently (AFAICT) will always relink an >>>>> executable even when it is not necessary to do so; thus if I have >>>>> a project with a bunch of libraries and executables, the cost of >>>>> making a small modification and recompiling is very high, and it >>>>> becomes hard to maintain focus on my projects after the initial >>>>> design phase. I've just been playing around with GNU coreutils >>>>> and was impressed with how well the build system works, and how >>>>> fast the recompilation goes. >>>>> >>>>> Anyway, the system that darcs uses seems to work pretty well, >>>>> should I copy that, or do people recommend other alternatives? >>>>> >>>>> Frederik >>>>> _______________________________________________ >>>>> Glasgow-haskell-users mailing list >>>>> Glasgow-haskell-users(a)haskell.org >>>>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users >>>> _______________________________________________ >>>> Glasgow-haskell-users mailing list >>>> Glasgow-haskell-users(a)haskell.org >>>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users >>>> >>> _______________________________________________ >>> Glasgow-haskell-users mailing list >>> Glasgow-haskell-users(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

1 0

RE: recommended build system
by Simon Peyton-Jones 09 Dec '05

09 Dec '05

Simon fixed this recently. The GHC HEAD build will not re-link with --make if none of the object files have changed. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces(a)haskell.org [mailto:glasgow-haskell-users- | bounces(a)haskell.org] On Behalf Of Frederik Eaton | Sent: 04 December 2005 00:46 | To: glasgow-haskell-users(a)haskell.org | Subject: recommended build system | | Hi all, | | I'm looking for a build system for my projects which will correctly | handle all of ghc's dependencies. I.e. every time I ask it to rebuild | an output file, it will only do the minimum amount of compilation | necessary. This is important to me because "ghc --make" and cabal | currently (AFAICT) will always relink an executable even when it is | not necessary to do so; thus if I have a project with a bunch of | libraries and executables, the cost of making a small modification and | recompiling is very high, and it becomes hard to maintain focus on my | projects after the initial design phase. I've just been playing around | with GNU coreutils and was impressed with how well the build system | works, and how fast the recompilation goes. | | Anyway, the system that darcs uses seems to work pretty well, should I | copy that, or do people recommend other alternatives? | | Frederik | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users(a)haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

2 2

RE: ghc --make and make
by Simon Marlow 09 Dec '05

09 Dec '05

On 04 December 2005 00:51, John Meacham wrote: > I was thinking it would be nice if ghc --make could touch the output > file with the timestamp of the most recently modified source file. > > As it is, if you edit a file in between when ghc --make starts and it > finishes (a substantial amount of time in some cases) then 'make' will > not realize the dependencies have changed. Hmm, I'm not sure about this. I see the problem: you have a Makefile rule that looks like this: myprog : Main.hs Foo.hs Bar.hs ... $(GHC) -o $@ --make Main.hs and while building myprog, you edit Foo.hs after it has been compiled, with the result that myprog has a later modification date than Foo.hs so won't be recompiled. However, touching myprog to match the date of Foo.hs when it was compiled doesn't seem right - the date on the executable would be earlier than the object files, which might not cause problems with the Makefile rule above, but would likely lead to problems with different Makefile setups. Perhaps the date on an object file should be set to the same as the source file? And the date on the .hi file? The easiest thing to do is not to try to use make dependencies with --make, just run ghc --make every time. It doesn't link if linking isn't required any more. Cheers, Simon

2 1

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 08 December 2005 11:52, Claus Reinke wrote: > is every MVar access is a synchronisation point (in terms of memory > update propagation between threads, not just in terms of thread > interaction)? Yes, it is. On a multiprocessor every MVar operation performs a full memory barrier internally. Incedentally, GHC hasn't actually supported multiprocessors until very recently, and it's still only in CVS and very experimental. Cheers, Simon

1 0

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 07 December 2005 19:57, Claus Reinke wrote: > there seem to be two issues here - can we agree on that at least? > > 1) scheduling non-sequential programs on sequential processors > > i wasn't arguing that the scheduler should realise all possible > interleavings at once. the issue i was referring to is known as > "fairness" in concurrent systems literature. as with referential > transparency, various non-equivalent definitions are in use, > but one informal description might be something like: > > if, for a given experiment, some event is possible according to > the semantics, it should happen eventually if the experiment is > repeated often enough. > > see, eg, > http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-fairn ess Yes, good point. Regarding fairness, I've been working with the assumption that we don't need to preserve (certain kinds of) fairness properties when performing optimisations, whereas you and others want to preserve all fairness. Why don't I care about preserving fairness? Well you said it - it's not practical to implement. And since the implementation already doesn't guarantee strong fairness (or whatever it's called), it doesn't do any harm to weaken the fairness that we do provide, because programmers can't rely on strong fairness anyway. In practical terms, you won't notice the difference. Furthermore, I'd go so far as to say that a program that relies on the kind of fairness we've been talking about (arbitrary interleaving) for correctness or termination, is broken. We ceratinly *do* care about some kind of fairness. The property that we try to maintain is something like this: If a thread is unblocked according to the semantics, then the implementation ensures that it runs after a finite time. I'm not familiar with the fairness literature, perhaps this property is known? You may well call our implementation incomplete because it doesn't implement full fairness. I don't think that's useful though; I'd much rather characterise exactly what fairness property we can and do implement, and use that for reasoning with. [snip] > 2) compiler optimisation validity in sequential and non-sequential > environments > > the original motivation of this thread - are sequential > transformations still valid in a non-sequential setting? > > in general, the answer is no, to the surprise/annoyance of many many > compiler implementors who want their valuable optimisations to work > even when their sequential language acquires threads. I don't think this applies in our setting. The reason we have IORef and {M,T}Vars, and not just a single mutable reference type, is that {M,T}Vars provide strong consistency guarantees when used to communicate between threads, whereas IORefs do not. Hence, IORefs can be implemented with much fewer restrictions. If you share IORefs between threads and run on a multiprocessor, you are at the mercy of both sequential optimisations and your architecture's memory consistency guarantees. In other words, don't do it. Use communication primitives that have strong properties in a multi-threaded setting. > i'd really, really prefer concurrent haskell not to go down a route > in which demands of simpler implementation leads to subtle problems > in reasoning about programs. If you think any of this impacts your ability to reason about programs, please elaborate - I don't think it does. Cheers, Simon

4 3

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 08 December 2005 09:40, Simon Marlow wrote: > If you share IORefs between threads and run on a multiprocessor, you > are at the mercy of both sequential optimisations and your > architecture's memory consistency guarantees. In other words, don't > do it. Use communication primitives that have strong properties in a > multi-threaded setting. I realised this paragraph is a bit stronger than I meant. Of course it's fine to share IORefs between threads as long as you use a proper communication primitive to synchronise access to the IORef. eg. using one MVar to lock on a bunch of IORefs is perfectly fine (this is how GHC's IO library is implemented). Cheers, Simon

2 1

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 07 December 2005 15:21, Claus Reinke wrote: >> (assuming 'acts' doesn't modify 'r'). > > this remark is the problem. > >> No, Jan's transformation is correct even in a multithreaded setting. >> It might eliminate some possible outcomes from a non-deterministic >> program, but that's ok. There's no requirement that all >> interleavings according to the semantics have to be implemented. .. > > not implementing traces promised as possible by the semantics is not > a good idea, imho, as programmers have some control over the set of > traces themselves. It's unreasonable to expect an implementation to provide *all* transitions specified by the semantics. How could you tell, for one thing? For example, what if the compiler doesn't allow a context switch between two adjacent operations: writeIORef r e x <- readIORef r this is a good example, in fact, because GHC will quite possibly compile this code into a single basic block that doesn't allow a context switch between the two statements. However, the semantics certainly allows a context switch between these two operations. Is GHC wrong? No way! So how do you specify which transitions an implementation must provide? Perhaps there's a good formulation, but I don't know what it is. > in this case, acts could implement the synchronisation with another > thread working on r, ie., even if acts does not modify r itself, it > might reliably cause another thread to modify r before acts can end. > if such synchronisations depend on traces you have eliminated, the > code > would just block (without apparent reason), whereas in this case, r > will have a value after acts that shouldn't have been possible, due > to the explicit synchronisation code (again, happy debugging) .. I should have said that if 'acts' blocks, then the transformation is invalid. When I say "acts doesn't modify r", I mean to include all ways of modifying r, including synchronising with another thread, or calling an unknown function. > of course, you could try to infer non-sequential interference with r > resulting from act, but that is what Malcolm pointed out - you have > to take the full semantics into account when doing such > transformations (btw, java originally made a mess of this- hope that > has been fixed by now). I don't think so. Malcolm asserted that the transformation was invalid in a multi-threaded implementation; I disagree - it's just as valid in a multi-threaded implementation as a single-threaded one. You don't have to preserve non-deterministic interactions with other threads, because they're non-deterministic! Cheers, Simon

5 4