- Haskell-Cafe - Haskell.org

Re: Yet another IO initializer: Effectful declarations and an ACIO monad
by George Russell 26 Nov '04

26 Nov '04

Ian Stark wrote (snipped): > Way back in this thread, Koen Claessen mentioned the idea of a commutative > version of the IO monad for handling things with identity. That doesn't quite > do it, but I have a refinement that might. The thing is to focus on IO > computations that are: > > a) central -- their effect commutes with every other IO action > b) affine -- their effect is not directly observable, and can be discarded. Unfortunately I have a number of examples where I use global variables with initialisation actions which cannot conceivably be proven to be central & affine by the compiler. For example, where I want to call up an external program (such as wish) which I will later use for doing graphics. The Haskell libraries would run into a similar problem when they tried to open stdin/stdout/stderr. Or indeed when they tried to implement RandomGen, which I presume is going to want to get at the system clock to seed the random number generator. My guess is that if we were to have top-level <- actions where the actions were restricted to those certified to be ACIO, it would not be very long before GHC would implement an unsafeForceACIO function ...

3 4

[Haskell] Lexically scoped type variables
by Martin Sulzmann 26 Nov '04

26 Nov '04

Hi, let me answer your questions by comparing what's implemented in Chameleon. (For details see http://www.comp.nus.edu.sg/~sulzmann/chameleon/download/haskell.html#scoped) > ---- QUESTION 1 ----- > > In short, I'm considering adopting the Mondrian/Chameleon rule for GHC. > There are two variations > > 1a) In the example, 'a' is only brought into scope in the > right hand side if there's an explicit 'forall' written by > the programmer > 1b) It's brought into scope even if the forall is implicit; e.g. > f :: a -> a > f x = (x::a) > > I'm inclined to (1a). Coments? > Currently, Chameleon goes for 1b), i.e. foralls are implicit. I agree that 1a) might help the programmer to immediately see which variables are bound by the outer scope. > > ----- QUESTION 2 ------ > > [...] > > The alternatives I can see are > > 2a) Make an arbitrary choice of (A) or (B); GHC currently chooses (B) > 2b) Decide that the scoped type variables arising from pattern > bindings scope only over the right hand side, not over > the body of the let > 2b) Get rid of result type signatures altogether; instead, > use choice (1a) or (1b), and use a separate type signature > instead. > > Opinions? > Chameleon goes for 2c) A Chameleon speciality is that we can write f ::: a->a f x = True f ::: a->a states that f has type a->a for some a. ::: follows the same scoping rules as :: Then, the following statement let f (x::[a],ys) = <rhs> in <body> (I assume that x::[a] states here that x has type [a] for some a) can be encoded as let f ::: ([a],b)->c f (x::[a],ys) = <rhs> in <body> The main motivation behind Chameleon's lexically scoped annotations was to allow for programs such as class Eval a b where eval::a->b f :: Eval a (b,c) => a->b f x = let g :: (b,c) g = eval x in fst g As Josef pointed out, there are also examples where it might be useful that some inner annotations refer to variable a from the outer annotation. Martin

1 0

Re: Global Variables and IO initializers
by George Russell 26 Nov '04

26 Nov '04

Marcin wrote (snipped): > I think global variables are a lot less evil if they behave as if they > were dynamically scoped, like Lisp special variables. > > That is, there is a construct which gives the variable a new mutable > binding visible in the given IO action. It's used more often than > assignment. Assignment is still available though. I agree entirely. The fact that declaring global variables using unsafePerformIO introduces an artificial notion of "global" and forces it on every part of the program is a major disadvantage which we haven't heard enough about in this discussion. It prevents you doing all sorts of things. It's bad for parallelism. It prevents you running two independent copies of a (main) action. It prevents you writing a Haskell controller which runs over Haskell actions as subprograms.

1 0

[Haskell] Re: Global Variables and IO initializers
by George Russell 25 Nov '04

25 Nov '04

> This is funny. When I got no immediate reaction from you, I started > implementing it myself. I ended up with something similar. It has less > features but is also a lot simpler. This is the interface: > > initGlobal :: Typeable a => a -> IO () > getGlobal :: Typeable a => IO a Your implementation is probably much simpler than mine because you don't implement withEmptyDict. I'm really quite keen about withEmptyDict, because one of the MAJOR conceptual problems I have with unsafePerformIO global variables is that you only get one universe, corresponding to the Haskell program. There shouldn't really be a single "the Haskell program" anyway; imagine something like GHC or an operating system written in Haskell which run sub-systems which require their own global variables. Or imagine a program split between lots of processors where, for efficiency reasons, you don't want everyone to have to refer to the same set of global variables.o > Storing (TypeRep,Dynamic) pairs is redundant, since Dynamics already > contain their own TypeRep (that is how they are made to work). It is, but I'm not sure if it can be avoided without using stuff not in the standard libraries. > I also use a list for the dictionary; and I share your view about > TypeRep badly needing an Ord instance (probably trivial to provide > but I could be wrong). Even better would be a hashable integer. TypeRep actually is implemented internally on GHC using a hashcons'd unique integer, so exposing it should be trivial ...

3 2

Interview with David Roundy on darcs and Haskell
by Josef Svenningsson 25 Nov '04

25 Nov '04

Hi all, At osdir there is a nice interview with David Roundy about darcs, the revision control system written in Haskell. He has a few comments about Haskell as well. Read it here: http://osdir.com/Article2571.phtml This was also covered on /. (which is where I found it). /Josef

1 0

Yet another IO initializer: Effectful declarations and an ACIO monad
by Ian.Stark＠ed.ac.uk 25 Nov '04

25 Nov '04

Way back in this thread, Koen Claessen mentioned the idea of a commutative version of the IO monad for handling things with identity. That doesn't quite do it, but I have a refinement that might. The thing is to focus on IO computations that are: a) central -- their effect commutes with every other IO action b) affine -- their effect is not directly observable, and can be discarded. Thus an element u of (IO a) is affine central if for all v::IO b and w::IO c, do { x <- u; v } = v (affine) do { x <- u; y <-v; w } = do { y <- v; x <- u; w } (central) where '=' is observational equivalence. For example, we would expect newMVar x :: IO (MVar a) to be affine central; similarly newIORef, and newStdGen for random number generators. If we define an ACIO monad for affine central IO expression, then we can safely use these in toplevel declarations: declare x <- u -- x::a, u::ACIO a declare count <- newIORef 0 -- count :: IORef Int declare flag <- newMVar True -- flag :: MVar Bool The semantics of such declarations would be to gather them all to the start of a program, whose meaning is now do { declarations; main } Because all declarations are ACIO: they can appear anywhere in the source; be executed at any point between the start of the program and the use of their value; and if there is no such use, need never be executed at all. In any event, the right-hand side of each declaration will be evaluated, and perform its side-effect, at most once. The declared values (x, count, flag) are pure values and do not have IO types. However, almost all their uses (bumping the counter, reading the flag) will live in the IO monad. Like stdIn and stdOut. Also, just because these declarations are toplevel doesn't mean they are globally visible: they are lexically scoped within standard module namespaces. I conjecture that when used "safely" the {-# NOINLINE #-} unsafePerformIO idiom is in fact being applied to IO expressions that are affine central; which means they could be put in ACIO and used as declarations instead. -- Ian Stark http://www.ed.ac.uk/~stark LFCS, School of Informatics, The University of Edinburgh, Scotland

2 2

RE: [Haskell] Lexically scoped type variables
by Josef Svenningsson 25 Nov '04

25 Nov '04

Let me just begin by sharing my experience with scoped type variables. I've found them very useful in a project were I was to generalize a substantial code base. Many of the functions had local definitions whose type were simply not expressible without scoped type variables. During this work I found an interesting interplay between multi parameter type classes and scoped type variables. An example would look something like this: f :: C a b c => a -> b f a = .... let g = ... The important thing to note is that the type variable c in f's signature occurs neither in the argument nor the result type of f. Hence c is not bindable by lexically scoped type variables. But suppose c is part of g's type. Then we still have no way of expressing g's type! This thing has bitten me and so I welcome the change you're planning. As for your questions I would prefer 1b although I don't think it is a big deal. For your second question I would go for 2c (which you've called 2b :). That's because I don't use result type signatures. Other people will surely disagree. Cheers, /Josef > -----Original Message----- > From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On > Behalf Of Simon Peyton-Jones > Sent: den 25 november 2004 11:44 > To: haskell(a)haskell.org > Subject: [Haskell] Lexically scoped type variables > > | This is a great example, thanks for posting it. However, I feel like > | the real problem in this example is the lexically-scoped type > | variables declared with your function f. > > Paul's message gives me an excuse to consult the Haskell list about the > design of lexically scoped type variables. I have a two particular > questions I'd like your advice about. (This is nothing to do with > monomorphism restriction, or Lennart's original puzzle.) > > I'm sending this message to the main Haskell list, to maximise > readership, but I suggest that > > you reply to haskell-cafe(a)haskell.org > > Thereby to avoid spamming the main Haskell list, which is meant to be > low-bandwidth. I believe I've set the reply-to field of this message to > achieve this goal. [Perhaps others can do the same?!] > > Simon > > ---- Background ---- > > First, for background you might want to glance at "Lexically scoped type > variables", an unpublished paper available at > http://research.microsoft.com/%7Esimonpj/papers/scoped-tyvars > I don't want to take time in this message to discuss why we want scoped > type variables; I'll just take it for granted here. > > One design choice discussed in the paper, and implemented in GHC, is > that we can bring new lexically-scoped type variables into scope by > mentioning them in a pattern type signature: > f (x::a) = .... > Here 'a' is a name for the type of x, and 'a' scopes over f's body, and > can be mentioned in type signatures in f's body. Sometimes one wants to > name types in the result* of f, rather than it its *arguments*. For > example > head (xs::[a]) :: a = ... > Here, the ":: a" before the "=" gives the type of head's result. If a > result type signature binds a type variable, that type variable scopes > over the right hand side of the definition. > > In GHC, it's not necessary for the type that 'a' names to be a type > variable; it could be Int, for example: > f (x::a) = x + (1::Int) > Already this embodies several design choices. For example, we know that > 'a' is a *binding* for 'a' because there is no 'a' already in scope, > otherwise it'd be an *occurrence* of 'a'. (An alternative would be to > mark binding sites somehow.) Also once could require that 'a' names a > type variable rather than an arbitrary type. But for this message I > want to take GHC's design as given. > > ---- QUESTION 1 ----- > > In GHC at present, a separate type signature introduces no scoping. For > example: > f :: forall a. a -> a > f x = (x::a) > would be rejected, because the type signature for 'f' does not make > anything scope over the right-hand side, so (x::a) means (x::forall > a.a), which is ill typed. > > An obvious alternative, taken up by (among others) Mondrian and > Chamaeleon, is to say that > > the top-level quantified variables of a separate type signature > scope over the right hand side of the binding > > In the above example, then, the 'a' bound by the 'forall' would scope > over the right hand side of 'f'. > > I've argued against this in the past, because the construct (forall a. > <type>) patently scopes 'a' only over <type>. But my resolve is > weakening. It's just too convenient! Furthermore, it binds a *rigid* > type variable (i.e. 'a' really must name a type variable) and that's > important for GADTs... which strengthens the case. > > In short, I'm considering adopting the Mondrian/Chameleon rule for GHC. > There are two variations > > 1a) In the example, 'a' is only brought into scope in the > right hand side if there's an explicit 'forall' written by > the programmer > 1b) It's brought into scope even if the forall is implicit; e.g. > f :: a -> a > f x = (x::a) > > I'm inclined to (1a). Coments? > > > ----- QUESTION 2 ------ > > Question 2 concerns degenerate bindings. First, consider pattern > bindings. For example: > let > (x::[a], y) = <rhs> > in <body> > The LHS of the let-binding is a pair, so it's called a pattern binding. > What should the scope of 'a' be? GHC's current story is that "it is the > same as the scope of term variables bound in the same pattern", so just > as 'x' scopes over both <rhs> and <body>, so does 'a'. And that in turn > means that we can't generalise over 'a', so 'x' is monomorphic. > > An alternative would be to say that type variables bound in a pattern > binding scope only over the right-hand side. > > ---- The degenerate case: variable bindings ---- > > Now the nasty case > > let > f :: a -> a = \x -> x > in (f True, f 'c') > > Is the binding for 'f' > (A) a (degenerate) function binding no arguments, but with a > result signature? > or (B) a (degenerate) pattern binding with pattern (var::type)? > > If we consider it to be (A) then arguably 'a' scopes only over the > right-hand side, and f gets the polymorphic type (forall a. a-> a). > > If we consider it to be (B) then currently 'a' scopes over the right > hand side and the body of the let, so 'f' has to be monomorphic, with > type ty->ty for some ty; and no ty will do, so the program is rejected. > > The trouble is that the binding is patently *both* (A) and (B). This > gives no difficulty in Haskell 98, because there's no difference in > treatment; but GHC's current rules for scoped type variables do > distinguish the two. > > The alternatives I can see are > > 2a) Make an arbitrary choice of (A) or (B); GHC currently chooses (B) > 2b) Decide that the scoped type variables arising from pattern > bindings scope only over the right hand side, not over > the body of the let > 2b) Get rid of result type signatures altogether; instead, > use choice (1a) or (1b), and use a separate type signature > instead. > > Opinions? > > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell

1 0

Re: Global Variables and IO initializers
by Benjamin Franksen 25 Nov '04

25 Nov '04

[encouraging everybody to reply on haskell-cafe] On Tuesday 23 November 2004 12:02, you wrote: > Thanks to the encouraging post > > http://www.haskell.org//pipermail/haskell/2004-November/014748.html > > from Benjamin Franksen, I have implemented > my proposal which allows the user to define new global variables without > unsafePerformIO, NOINLINE and other such horrors. This is funny. When I got no immediate reaction from you, I started implementing it myself. I ended up with something similar. It has less features but is also a lot simpler. This is the interface: initGlobal :: Typeable a => a -> IO () getGlobal :: Typeable a => IO a Some remarks: o The separation into two modules is only historical. o I use an MVar internally, not an IORef; since it is not exposed, no indefinite blocking can occur. It's just a mutex around the dictionary. o Storing (TypeRep,Dynamic) pairs is redundant, since Dynamics already contain their own TypeRep (that is how they are made to work). o Both our implementations use unsafePerformIO in an unsafe manner, which is why the NOINLINE flag is used. o I also use a list for the dictionary; and I share your view about TypeRep badly needing an Ord instance (probably trivial to provide but I could be wrong). *************** On a related note, there was some discussion recently about which IO actions should be considered as 'harmless' so that they are allowed for the proposed top-level '<-' bindings, and how to characterize them in an elegant way. Here is yet another solution: The only things allowed at top-level (other than pure values) will be unique labels (such as provided by Data.Unique). Then we take all the newXXX actions out of whatever monad they live in and provide them as pure functions that take a Unique as additional argument: newXXX :: Unique -> a -> XXX a This might be a bit tricky to do efficiently. Anyway, a Haskell program could then create top-level Unique labels instead of top-level XXX vars: myGlobalVarLabel <- unique myGlobalMVar = newMVar myGlobalVarLabel "initial content" The concrete syntax could be made even simpler (and clearer), i.e. without the '<-' operator: unique myGlobalVarLabel Advantages: o No question of what is in SafeIO and what is not. o No question of when top-level IO actions are performed. *************** Now what about combining the two aproaches? The point here is that in Haskell we can easily create new unique labels at the top-level without resorting to any kind of unsafe operations: data Uniq1 = Uniq1 data Uniq2 = Uniq2 ... Only these have not the same but different types. So we need a way to map them to a single type in such a way that their uniqueness is preserved. We already have such a tool and it is called "deriving Typeable": unique = typeOf type Unique = TypeRep data Uniq1 = Uniq1 deriving Typeable data Uniq2 = Uniq2 deriving Typeable Our unique labels can now simply be defined as label1 = unique Uniq1 label2 = unique Uniq2 and our global variables as global1 = functionalNewMVar label1 True global2 = functionalNewMVar label1 (117::Int) I think this is most elegant, although there remains the questions of an efficient implementation of functionalNewXXX. Ben

3 4

Re: [Haskell] Top Level TWI's again
by Benjamin Franksen 24 Nov '04

24 Nov '04

[for the third time moving this discussion to cafe] On Tuesday 23 November 2004 20:20, Aaron Denney wrote: > [...about std file handles...] > They're wrappers around the integers 0, 1, and 2. The handles could > have been implemented to be the same, at each invocation. (I expect > they are in most implementations). If we had to make them ourselves, > they could be done as: > > stdin = makeHandle 0 > stdout = makeHandle 1 > stderr = makeHandle 2 > > in absolutely pure Haskell, only the things that manipulate them need > be in the IO monad. If they were simple wrappers around the integers, you'd be right and I couldn't rightfully object to them being top-level values. I don't like it but I have to admit that (although hypothetical) this invalidates the argument I gave against them being top-level things ;-( My only rescue is to shift the blame on the OS. Indeed it is quite debatable whether the raw file descriptor API is a good one. Does it make sense that you can, e.g. swap stdin and stdout? It doesn't seem right to me that file descriptors are reused at all. I think file handles should be completely abstract. Also I would rather have separate types for Input, Output, and RandomAccess Streams, although they might of course share some methods via type classes. I am currently taking a look at Simon Marlow's new_io library that seems to do just that (and a lot more). > >> Keeping them outside the IO monad, and only accessing them inside -- > >> i.e. the current situation -- would be fine. > > > > I beg to differ. Note, I do not claim they are unsafe. > > If it's not unsafe, and it makes for simpler (hence easier to > understand, create, debug, and modify) in what sense is it not fine? I don't buy the "easier to understand, create, debug, and modify" part if it comes to global variables. Not everything that makes things simpler at first, is also good for long-term maintenance, and global variables have accumulated quite a bad reputation in this regard. > >> They're not mutable in any sense. > > > > Well, a variable in C is not mutable in exactly the same sense: It always > > refers (="points") to the same piece of memory, whatever value was > > written to it. Where does that lead us? > > A slightly different sense, but I won't quibble much. Assume a completely type-safe version of C, if that makes it clearer. > It would lead us to being able to have TWIs, only readable or writeable > in the IO Monad. Many people don't think that would be such a bad > thing. But because of the semantics we expect from IORefs, we can't > get them without destroying other properties we want. > > a = unsafePerformIO $ newIORef Nothing > > Respecting referential integrity would give us the wrong semantics. > Adding labels would force the compiler to keep two differently labeled > things seperate, Hmm. That sounds as if the global variables problem is equivalent to the problem of unique name supplies: With global variables (let's say top-level MVars) we can easily implement a unique name supply. And with a unique name supply we could (in principle, at least) define newMVar and newIORef as pure functions taking some unique label as an argument. (QED) I have just taken a closer look at 'linear implicit parameters' because they are supposed to be good for unique name supplies. It seems they are even worse than the 'normal' implicit parameters. Considering the above argument this doesn't surprise me much. That means we are back to using the IO Monad to create unique labels, so all this doesn't gain us anything, at least not on the practical level. > In contrast with IO Handles, there the OS does all the work. If > "makeHandle" were exposed to us, It really wouldn't matter whether > > handle1 and stdout > > handle1 = makeHandle 1 > stdout = makeHandle 1 > > were beta-reduced or not. Either way, the OS naturally handles how we > refer to stdout. I see the difference and I agree. However, you can already do this using the Posix package: makeHandle :: Int -> System.Posix.Fd makeHandle = fromIntegral but note that handleToFd :: Handle -> IO Fd fdToHandle :: Fd -> IO Handle are both in the IO Monad. BTW, the man page for stdin etc. says: "Note that mixing use of FILEs and raw file descriptors can produce unexpected results and should generally be avoided." > (One caveat here -- buffering implemented by the compiler & runtime > would make a difference.) I think this is done neither by compiler nor RTS but by a low-level library. Anyway, it seems to make a difference, as witnessed by the above signatures. Ben

2 1

Problem with overlapping class instances
by Graham Klyne 23 Nov '04

23 Nov '04

Once again, the Haskell class system is proving rather subtle for me. On this occasion, I'm getting an overlapping class instance error which I think should be fully disambiguated by the supplied class context. The code below (end of message) is a .lhs file that reproduces the problem in Hugs, with external dependencies from my working codebase stripped out. It should be possible to simply load it (or this whole email) to get the same error: [[ Reading file "D:\Cvs\DEV\HaskellDL\spike-overlap-conceptexpr.lhs": ERROR "D:\Cvs\DEV\HaskellDL\spike-overlap-conceptexpr.lhs":30 - Overlapping inst ances for class "ConceptExpr" *** This instance : ConceptExpr (a b) *** Overlaps with : ConceptExpr AtomicConcept *** Common instance : ConceptExpr [Char] ]] The line referred to as "this instance" is: instance (ConceptWrapper cw c, ConceptExpr c) => ConceptExpr (cw c) where The reported overlapping instance is [Char], which I take to be derived from the type constructor [] applied to type Char, this yielding a form that matches (cw c). But the instance ConceptExpr (cw c) is declared to be dependent on the context ConceptWrapper cw c, which has *not* been declared for the type constructor []. GHCi with -fglasgow-exts is no more informative. What am I missing here? #g -- [Source code follows] spike-overlap-ConceptExpr.lhs ----------------------------- > type AtomicConcepts a = [(AtomicConcept,[a] )] > type AtomicRoles a = [(AtomicRole ,[(a,a)])] > > type TInterpretation a = ([a],AtomicConcepts a,AtomicRoles a) > class (Eq c, Show c) => ConceptExpr c where > iConcept :: Ord a => TInterpretation a -> c -> [a] ... > type AtomicConcept = String -- named atomic concept Declare AtomicConcept and AtomicRole as instances of ConceptExpr and RoleExpr (AtomicRole is used by AL, and including AtomicConcept here for completeness). > instance ConceptExpr AtomicConcept where > iConcept = undefined ... To allow a common expression to support multiple description logics, we first define a wrapper class for DLConcept and DLRole: > class ConceptExpr c => ConceptWrapper cw c | cw -> c where > wrapConcept :: c -> cw c -> cw c > getConcept :: cw c -> c Using this, a ConceptWrapper can be defined to be an instance of ConceptExpr: This is line 30: > instance (ConceptWrapper cw c, ConceptExpr c) => ConceptExpr (cw c) where > iConcept = iConcept . getConcept Error message: Reading file "D:\Cvs\DEV\HaskellDL\spike-overlap-conceptexpr.lhs": ERROR "D:\Cvs\DEV\HaskellDL\spike-overlap-conceptexpr.lhs":30 - Overlapping inst ances for class "ConceptExpr" *** This instance : ConceptExpr (a b) *** Overlaps with : ConceptExpr AtomicConcept *** Common instance : ConceptExpr [Char] ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

3 6