- Haskell-Cafe - Haskell.org

ACIO versus Execution Contexts
by George Russell 01 Dec '04

01 Dec '04

I think it would be nice to summarise the current state of play. This really needs to be a WiKi. Ian's ACIO proposal http://www.haskell.org//pipermail/haskell-cafe/2004-November/007680.html seems in fact to achieve much the same as the proposal I originally posted to http://www.haskell.org//pipermail/haskell/2004-November/014894.html and which Benjamin Franksen has explained and simplified here http://www.haskell.org//pipermail/haskell-cafe/2004-November/007691.html You can in fact do much the same with both. With Haskell 98, Data.Dynamic and ACIO and, if your implementation has concurrency at all, thread identifiers, I can implement execution contexts. On the other hand ACIO allows you to create variables with top-level declarations such as x <- newIORef 0 which can then be accessed in a pure way. With Execution Contexts you cannot do this; you would instead need a function getX :: IO (IORef Int) which would get the global variable x. In practice I don't think this distinction very important, since there's not much you could do with x except using the IO monad. Disadvantages of execution contexts ----------------------------------- 1. You are only allowed one value of each type in an execution context. Thus it is dangerous to try to use a global value of type (IORef Int); people would have to be advised to create a special newtype for each value. 2. They are likely to be less efficient than just allowing <- declarations at top level. Certainly they are in my implementation. The vast majority of this inefficiency can be eliminated by using hash tables, but you can't escape doing at least one hash-table lookup each time you want to access a global value. The bare minimum then would be one division by a constant followed by an indirection. 3. In a concurrent system, you also need forkIO to be modified, so that you can work out which execution context applies to you. Disadvantages of ACIO --------------------- 1. The ACIO proposal preserves one bad feature of unsafePerformIO, namely that you only have one "execution context". You cannot for example run two copies of the same program simultaneously, since they will clobber each other's global variables. 2. I don't know exactly how ACIO is to be implemented, but it looks as if at the least it requires an extension to the Haskell syntax. 3. I think that if the ACIO proposal were implemented, it would in any case be a good idea to implement execution contexts or something like them on top of it, so that people can create initialisation actions which do other things than the very strict subset allowed as ACIO actions. Questions --------- 1. Is there anything people would like to do with ACIO for which execution contexts would not be practical? 2. Which if either of the proposals would the gods responsible for implementing Haskell compilers favour?

6 9

RE: [Haskell-cafe] ACIO versus Execution Contexts
by Simon Peyton-Jones 01 Dec '04

01 Dec '04

| I think it would be nice to summarise the current state of play. This really | needs to be a WiKi. Thanks for the summary, George. | 2. Which if either of the proposals would the gods responsible for implementing | Haskell compilers favour? Rather than remain completely silent on this topic let me say that (a) I'm totally snowed under at the moment, at least partly with GHC stuff (Template Haskell, GADTs etc); (b) there has been so much traffic on this global variable topic that I've stopped reading it carefully. This isn't because I think it's unimportant or boring, but rather because I'm hoping that someone will eventually emit a summary that really does boil out the main issues, so that everyone else can benefit from the fruits of your (plural) labours. The idea would be that everyone else can just read the summary without reading the thread. A Wiki would be good. (c) I have the impression that there's still quite a bit of active discussion; convergence is not achieved (d) I'm not averse to changing GHC in some way, but big changes (e.g top level <-) would need a jolly persuasive argument and solid consensus. Smaller changes (e.g. a robust promise about top-level newMVars) are easier of course. (e) FWIW, as Simon has remarked, we're busy eliminating top-level global MVars from GHC. The really persuasive use I know for them is to implement semantically-pure but implementationally impure things like memo tables. Simon

2 1

not possible with monad transformers ?
by Pavel Zolnikov 01 Dec '04

01 Dec '04

Hi, I have been playing with Maybe and Output monad transformers and realized that I cannot make the following work nicely: > foo a b = do > output "before" > r <- (liftM2(+)) a b > when r == Nothing $ output "error" > return r As soon as computation produces Nothing, I am loosing ability to do any output. I think what I need is not wrapping one monad into another with transformer; I need some sort of monad combiner: > newtype MC m1 m2 = MC (m1 a, m2 b) So I could execute both of monads ‘in parallel’. But I have no idea how to express this or even if this is doable at all. Any comments? Thanks, Pavel. P.S. Here is summary of what I tried with transformers so far: Let’s say I have following monad transformers: > newtype MaybeMonadT m a = MMT (m a) > newtype OuptutMonadT m o a = OMT (m a, o) And I am trying to use following monads: > type M1 a = MaybeMonadT OutputM a > type M2 a = OuptutMonadT Maybe String a Now, they both won’t quite work in the following example: > foo a b = do > output "before" > r <- (liftM2(+)) a b > when r == Nothing $ output "error" > return r In case of M1, as soon as I get Nothing in r, computation will stop and return without any output gathered. In case of M2, as soon as I get Nothing in r, computation will stop and return only with output gathered so far. That is > output "error" will never be called.

7 11

Re: [Haskell-cafe] Equality of functions
by oleg＠pobox.com 01 Dec '04

01 Dec '04

Jules Bean wrote: > From the point of view of a programmer, that's all there is to it: > there is no way of proving two functions are the same except by > exhaustively checking every input. That is too pessimistic, I'm afraid. There is also an intensional equality. Granted, it can be sound but never, in general, complete (although it can be total). That is, if the comparison function returns True, then the arguments truly denote the same, identically the same function. If the answer is False, well, we don't know. The arguments may still denote the same function. Here's one example of intensional comparison: > import Foreign > > comp a b = > do > pa <- newStablePtr a > pb <- newStablePtr b > let res = pa == pb > freeStablePtr pa > freeStablePtr pb > return res *FD> comp id id >>= print True *FD> comp undefined id >>= print False *FD> comp undefined undefined >>= print True This function lives in the IO monad, where it should stay because it destroys free theorems. It is quite equivalent to Scheme's eq? predicate. For some -- wide -- classes of functions, it is possible to define a pure functional intensional comparison. For example, a recent message http://www.haskell.org/pipermail/haskell/2004-November/014939.html demonstrated the reconstruction of (even compiled) numerical functions. So, one can define intensional equality of two numeric functions as structural equality of their reconstructed representations. Alas, this comparison function can't be total: bottom is beyond comparison.

2 1

Equality of functions
by Adam Zachary Wyner 01 Dec '04

01 Dec '04

Hi All, After some weeks of experimenting and digging around, I understand that functions cannot be compared for equality. Thanks to Bjorn Lisper for pointing this out. I basically understand (?) the underlying mathematical issue, which is that functions in general may have infinite domains and ranges. For example, a function f, which gives the successor of an integer, x + 1, could not be compared to a function g, which gives the predecessor of an integer which has 2 added, (x + 2) - 1, even though these two functions give exactly the same result on all arguments, because we would have to compare them on all possible values for x. Question -- is this all there is to the issue, or is there something more? Apologies in advance for not understanding the math better here. Question -- though Haskell, as a lazy language, does not otherwise have problems with infinite lists, why does it here? Question -- is there some way around this problem? It is very handy to be able to have a variable over functions and then compare the value to a designated function. This would let me say things like: when variableFunctionX == functionA then.... otherwise etc... One possible (dirty?) solution I thought up is to use the record types of Hugs to correlate the function with a name of type String: type FunctionNameFunction = Rec (functionName :: String, functionFunction :: WhateverFunction) Then, whenever one needs to use the function, one uses the value of functionFunction, but whenever one needs to evaluate for identity, one uses the value of functionName, using just string identity. Of course, this makes lots of things less 'pretty' (to apply a function to an argument, one has to first 'pull out' the function from the record), but it addresses a general problem. One would also have to keep careful track of which functionNames correlate with with functionFunctions. Other suggestions? Cheers, Adam

6 6

Re: ACIO versus Execution Contexts
by George Russell 30 Nov '04

30 Nov '04

Adrian Hey wrote (snipped): > I've been looking at your global variables library. Thanks. > In particular, the purpose of top level <- bindings IMO is *not* to > provide "global variables" (though they could be abused this way). > If you consider the example.. > > userInit <- oneShot realInit > > ..the top level MVar created is not global. It doesn't even scope over > an entire module, it's buried in a closure. This kind of use would be > pretty typical I think. Even when you do have top level IORefs (or > more complex mutable data structures) scoping over an entire module, > generally they won't be exported by that module. Instead access is > strictly limited to a few carefully defined IO actions, and these > are exported. I think you must mean by "global variable" something different to what I mean by "global variable". It is precisely such uses as you describe above which I would anticipate being supported by the Execution Contexts proposal. Of course good structured programming would hide a module's use of execution contexts or top-level variables. > Also, we don't want different threads to have their own versions of > these. There seems to have been some confusion on this point, so I should make it clear that by default, with my proposal, threads *do*not* each have their own versions of the variables. This only happens if you explicitly create a new execution context and run an action within it; that action, and the threads it forks off, will then use the new execution context. > They are for use in situations where you need to represent > state associated with a genuinely unique resource (eg top level > stateful C library or hardware IO device). In my experience this is only true quite rarely. I think Keean and Lennart have already said most of what I have to say here.

3 2

[Fwd: Re: [Haskell-cafe] Re: ACIO versus Execution Contexts]
by Lennart Augustsson 30 Nov '04

30 Nov '04

1 0

RE: Efficient or predictable Ord for Typeable
by Simon Peyton-Jones 30 Nov '04

30 Nov '04

The trouble is that *any* "function" can now deliver unpredictable results. Can I rely on the fact that foo :: Int -> Int will always give the same answer given the same input. Not any more. I think the strongest argument here is that it's like a more benign version of unsafePerformIO, whose existence also threatens foo's predictability. | -----Original Message----- | From: George Russell [mailto:ger@informatik.uni-bremen.de] | Sent: 30 November 2004 09:55 | To: haskell-cafe(a)haskell.org; Simon Peyton-Jones; John Meacham | Subject: Efficient or predictable Ord for Typeable | | Simon PJ wrote (snipped): | > This unfortunate observabilty of an ordering (or hash value) that is | > needed only for efficient finite maps, is very annoying. I wish I knew | > a way round it. As it is we can pick | > a) expose Ord/Hash, but have unpredictable results | > b) not have Ord/Hash, but have inefficient maps | | In this case there is a simple solution. Simply define | | newtype FastUnpredictableInstances a = FastUnpredictableInstances a | | and define the fast Ord and Hash only for FastUnpredictableInstances. | People who manage to type all that then have no grounds to grumble | if they get bitten. For something as basic as implementing execution | contexts, FastUnpredictableInstances is acceptable.

4 4

RE: [Haskell-cafe] Re: [Haskell] Re: Global Variables and IOinitializers
by Simon Peyton-Jones 30 Nov '04

30 Nov '04

| > In fact GHC at least *already* generates a unique integer for each | > TypeRep. A good idea, since it means comparisons can be done in unit | > time. Thus indexing can be done trivially using this integer as a | > hash function. | | Yes, I have seen this in the code, too. The Ord and Typeable instances | should be trivial. Take care here. There is no guarantee that the unique number generated will be the same in each run. So if you have Ord Typeable, this program may give unpredictable results: main = print (typeOf True < typeOf 'x') This unfortunate observabilty of an ordering (or hash value) that is needed only for efficient finite maps, is very annoying. I wish I knew a way round it. As it is we can pick a) expose Ord/Hash, but have unpredictable results b) not have Ord/Hash, but have inefficient maps Simon

4 3

Efficient or predictable Ord for Typeable
by George Russell 30 Nov '04

30 Nov '04

Simon PJ wrote (snipped): > This unfortunate observabilty of an ordering (or hash value) that is > needed only for efficient finite maps, is very annoying. I wish I knew > a way round it. As it is we can pick > a) expose Ord/Hash, but have unpredictable results > b) not have Ord/Hash, but have inefficient maps In this case there is a simple solution. Simply define newtype FastUnpredictableInstances a = FastUnpredictableInstances a and define the fast Ord and Hash only for FastUnpredictableInstances. People who manage to type all that then have no grounds to grumble if they get bitten. For something as basic as implementing execution contexts, FastUnpredictableInstances is acceptable.

1 0