- Haskell-Cafe - Haskell.org

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

Re: Top Level TWI's again was Re: [Haskell] Re: Parameterized Show
by Graham Klyne 23 Nov '04

23 Nov '04

[Switching to Haskell-cafe] At 11:26 22/11/04 +0000, you wrote: >I would ask an alternative question - is it possible to live without >unsafePerformIO? I have never needed to use it! I have used it once, with reservations, but at the time I didn't have the time/energy to find a better solution. (The occasion of its use was accessing external entities within an XML parser; by making the assumption that the external entities do not change within any context in which results from a program are compared, I was able to satisfy the "proof obligation" of not causing or being sensitive to side effects.) The reason this was important to me is that I wanted to be able to use the parser from code that was not visibly in the IO monad. For me, treating Web data transformations as pure functions is one of the attractions of using Haskell. (Since doing that, I had an idea that I might be able to parameterize the entity processing code on some Monad, and use either an Identity monad or IO depending on the actual requirements. This way, I could keep pure XML processing out of the IO monad, but use IO when IO was needed.) In short: I think it's usually possible to avoid using unsafePerformIO, but I'd be reluctant to cede it altogether, if only for sometimes quick-and-dirty pragmatic reasons. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

8 15

Re: Global variables again
by Benjamin Franksen 23 Nov '04

23 Nov '04

[we should really keep this on haskell-cafe because such lengthy discussions are what the cafe is for] On Tuesday 23 November 2004 10:26, Adrian Hey wrote: > On Monday 22 Nov 2004 4:03 pm, Benjamin Franksen wrote: > > This is getting ridiculous. At least two workable alternatives have been > > presented: > > > > - C wrapper (especially if your library is doing FFI anyway) > > - OS named semaphores > > Neither of these alternatives is a workable general solution. Since the problem only appears in special situations, a general solution is not required, nor is it desirable (because of the danger of infection with the "global variable disease".) > There are several significant problems with both, but by far > the most significant problem (at least if you believe that top > level mutable state is evil) is that they both rely on the use > of top level mutable state. If this is evil it is surely just as > evil in C or OS supplied resources as it is in Haskell. The evil is in the world in the form of C libraries with hidden global variables and hardware with non-readable registers. What I am arguing for is to *contain* this disease by forcing a solution to happen outside of Haskell. What you are arguing for (i.e. a general solution *in* Haskell) amounts to (deliberately) *spreading* the disease. > The fact that one solution requires the use of a completely different > programming language And that is exactly the point: In order to do evil you have to go somewhere else, preferably to where the problem originally came from. If it originated in C, go fix it on the C level. If originates in the OS, go fix it on the OS level. As for broken hardware, you should use a OS level mechanism, so that multiple initialization is prevented OS wide and not only per program run. > and the other requires the use of a library which > could not be implemented in Haskell (not without using unsafePerformIO > anyway) must be telling us that there something that's just plain missing > from Haskell. Yes it's plain missing and for good reasons. There are many things plainly missing from Haskell besides global variables. > IMO this is not a very satisfactory situation for a language > that's advertised as "general purpose". "General purpose" doesn't mean that any programming idiom is supported. > > Further, as for "evidence or credible justification" for the my claim, > > you can gather it from the numerous real-life examples I gave, and which > > you chose to ignore or at least found not worthy of any comment. > > I have no idea what examples you're talking about. Did you post any code? No, I didn't post code. I already said it's annecdotal evidence. For instance, I was talking about using the ONC/RPC implementation on VxWorks, which is broken because they internally use thread-local mutual state. > If so, I must have missed it for some reason. Perhaps your're refering > to your elimination of unsafePerformIO from a library you were writing. I wasn't. > > Of course, > > these examples are only annecdotal but I think this is better than a > > completely artificial requirement (like your "oneShot"). > > Being able to avoid the use of top level mutable state sometimes (or even > quite often) is not proof that it's unnecessary, True. I have never claimed that, though. What I claimed is that in the cases where they are necessary, FFI is probably used anyway, so it *is* workable to use a foreign language wrapper. In order to convince me that this is wrong you could present a (real-world, no artificial requirements) example that does not require the use of FFI anyway. If you can do so (which I doubt) I might be willing to accept a compiler-supported standard library routine with a very long and very ugly name like warningBadStyleUseOnlyIfAbolutelyNecessary_performOnlyOnce: IO a -> IO a ;-) > especially when nobody > (other than yourself presumably) knows why you were using it in the first > place. Not I. And it was for convenience only, as I proved by completely eliminating them without making the code any more complicated. I never claimed that this proves anything, it was just a personal experience. BTW, the main reason they use global variable in C all the time is because it's just so damn convenient (at first) and *not* because there are problems otherwise unsolvable. (There are *very* few exceptions.) > However, the existance of just one real world example where it does > appear unavoidable is pretty convincing evidence to the contrary IMO. I agree that the alternatives are not a good *general* solution. I have been arguing that a general solution is not desirable. > > You have been asked more than once to present a *real-life* example to > > illustrate that > > > > (a) global variables are necessary (and not just convenient), > > (b) both above mentioned alternatives are indeed unworkable. > > I knew this would happen. I was asked to provide an example and I *did*. > I gave the simplest possible example I had of the more general problem, > and now this whole thread has consisted of either repeated denials of > the reality of even this simple problem (something you've just done again) > or protracted discussions over various half baked non-solutions to > this one particular problem (such as those you identify above) without > seeing the real underlying general problem. There is no underlying problem, apart from interfacing evil hardware or foreign libraries. At least I know of none. > > > You have yet to > > > explain how you propose to deal with stdout etc.. > > > > I see absolutely no reason why stdxxx must or should be top-level mutable > > objects. They can and should be treated in the same way as environment > > and command line arguments, i.e. > > > > getArgs :: IO [String] > > getEnv :: String -> IO String > > getStdin, getStdout, getStderr :: IO Handle > > > > Note that (just like environment and command line arguments) these > > handles may refer to completely different things on different program > > runs. > > Sure, Peter Simons suggested the same thing. I have no great objection, > but why do this? Strange. I told you the reason. You even cited it. What about reading it, too ;-? > I mean what extra safety does this buy you? Nobody claimed that global variables are unsafe in any strict sense. > Anybody can > still get at stdout and write anything they like to it. Sure they can. They have been warned, though... ;-) > The only difference is that instead of writing.. > > do ... > foo stdout > ... > > ..they now have to write.. > > do ... > stdout <- getStdout > foo stdout > ... > > I don't see why the former should be regarded as a source of great evil > which is somehow eliminated by the latter. To repeat myself once again: The latter version makes it clear to anyone looking at the code, that the stdout above (a) might refer to something different from other results of getStdout elsewhere in the program (e.g. stdout might have been closed or re-opened) (b) might refer to completely different things on different program runs (e.g. output of program is piped to some other process or even a socket). Ben -- Top level things with identity are evil. -- Lennart Augustsson

1 0

Haskell-cafe message-length restriction
by Graham Klyne 23 Nov '04

23 Nov '04

To the list Haskell-cafe admin... May I suggest that the maximum message length for postings to the haskell-cafe list without moderation be raised from its current 5K limit? It seems to me that a value of (say) 20K would reduce the moderator's workload without obviously allowing too many undesirables ... (though I allow the moderator surely knows more about what is thrown at the list that most of us don't see.) Just a thought. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Mutable and persistent values (was: Top Level TWI's again)
by Graham Klyne 23 Nov '04

23 Nov '04

[I'm moving my response to the Haskell-cafe mailing list, as it seems more appropriate for this kind of discussion.] Your question seems to touch on the old chestnut of how to reconcile pure functional programs with the inherently procedural aspects of I/O and state management. Most of the richness to which you refer is, to my mind, a fairly esoteric corner of Haskell with which I've had little cause to engage. I sense you may be coming from a perspective similar to mine of a couple of years ago, hence this response. Maybe what follows is already well known to you (some of it is basic stuff), so please accept my apologies if I'm retreading well-worn paths for you. The classical work (c. 1970's) on using functions to describe programs that update machine state models such programs as functions that take a state and return a new state, maybe returning some other values as well. This could get complicated to handle, and along the way functional structures based on monads were invoked to tidy up the housekeeping. (A paper by Simon Peyton-Jones and John Launchbury [1] about handling state in Haskell was useful for me.) Note the central role of higher order functions in dealing with this: a state-monad function represents a computation on some state, not the result of that state; the result of the computation is available only when the function is applied to some initial state. The do-notation is a syntactic sugar to make this easier to write, but (I think) it can sometimes obscure what is going on. Philip Wadler's paper "The Essence of Functional Programming" [3] nicely illustrates how monads can take care of various housekeeping chores. The IO monad can be viewed as a special case that allows a program to access and update state ("the real world") that exists outside the program. So, turning to your specific questions/concerns: >Also, ultimately, I want to be able to save my work and restart >the next day (say) picking up the tags where I left off. Your top-level program must be "in the IO monad" (or: is an expression that describes an IO monad value, which is a computation that interacts with the real world). Thus, it can access yesterdays work, and also your interactive inputs, and compute a new value that is today's work. The IO monad allows you to sequence the various interactions with persistent state and user dialogue, in a purely functional way. >I'm darned if I can see how to do this in a callback without a global >variables (and references from other callbacks, by the way). I would expect the callback function to accept an initial value of the "global" variable(s), and return its new value(s), leaving the calling site to ensure that the new value is used as required. (This interaction may be "hidden" in a monad (e.g. a state monad), and if the "callback" itself involves interaction with a user must use the IO monad.) > I want to use the old value of a tag to compute the new value, in a > callback, > > I want to access the tag from other callbacks, and > > I want to the value to a mutable list from within the callback. All of these are accommodated by adopting the accept-a-value-and-return-a-new-value perspective. The calling program that invokes the callbacks deals with ensuring that the callbacks have access to the appropriate results from other callbacks. It is my view that use a functional language effectively, it is necessary to think differently about its structure than one would for a conventional imperative program. Global values become parameters and return values; mutable values become input values and new (separate) return values. If you're used to writing imperative programs that do not use global state, but rather use parameters to pass values, the difference isn't always quite as great as might be imagined. For complex values, this sounds horribly inefficient, but because values are pure (not mutable), very high levels of sharing can (sometimes, with good design!) be extensively shared. Thus, a return value may well consist mostly of a copy of the input value, with differences, rather than actually being a complete new copy. (Chris Okasaki's book shows well how to design to obtain these benefits.) Also, because Haskell is lazy, complex structures passed between functions don't necessarily ever exist in their entirety. Sometimes, I think of a data structure as describing a computational traversal through some data, rathert than something that actually exists. (This leads to very elegant expression of things like Prolog search-and-backtrack algorithms.) So the main point of this posting is to say that I think that the "richness" of "implicit parameters, linear implicit parameters, unsafePerformIO, ..." to which you refer is a shoal of red herring, as far as your goals are concerned. I hope this helps. I've added below a couple of links to my web site to stuff that I accumulated while learning Haskell over the past couple of years. #g -- [1] Simon Peyton-Jones and John Launchbury, State in Haskell, linked from: http://research.microsoft.com/Users/simonpj/Papers/papers.html#monads, document at: http://research.microsoft.com/Users/simonpj/Papers/state-lasc.ps.gz, also at: http://www.cse.ogi.edu/~jl/Papers/stateThreads.ps. Introduces monads as a general technique for handling state, and then introduces a concept of "the world" as a state manipulated by IO. I found this to be one of the more illuminating introductions to Monads (which are central to Haskell I/O). [2] Chris Okasaki, "Purely Functional Data Structures", Cambridge University Press, 1998 [3] Philip Wadler, "The essence of functional programming", linked from http://homepages.inf.ed.ac.uk/wadler/topics/monads.html, paper at http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps . [4] http://www.ninebynine.org/Software/Learning-Haskell-Notes.html [5] http://ninebynine.org/Links.html#Programming-Haskell At 15:34 22/11/04 -0800, John Velman wrote: >On Mon, Nov 22, 2004 at 07:27:44PM +0100, Lennart Augustsson wrote: > > >[snip] > > I admit there are proper uses of global variables, but they are very > > rare. You have not convinced me you have one. > > > > -- Lennart > >It's with some trepidation I bring a problem as a total newbie, but I've >been obsessed with this and hung up on it ever since I decided a couple of >weeks ago to learn Haskell by using it. > >Some brief background: > >A while back I decided I wanted a simple 'concept mapping' program that >would work the way I work instead of the way someone else works. I >envisioned a GUI with a canvas and an entry box (TK/tcl). I type a >"concept name" into the entry box, and it shows up on the canvas (initially >in a slightly randomized position), in a box, with a unique sequenced >identifier. The identifier is also used as a canvas tag for the item. >Similar input for relations between concepts. I think that's enough >description for now. > >Initially, I started programming this with PerlTK, but that effort was >interrupted for a few weeks. When I got back to it, I decided to do it in >Python instead. But that effort also got interrupted for a few weeks. >Before I got back to it, I ran across some material on Haskell I've had in >my files for a few years, and decided that I'd use this as a vehicle to >actually learn Haskell. (This all sounds a bit unfocused, and it is: I'm >retired, sometimes describe myself as an ex mathematician or an ex-PhD >having spent years in the aerospace industry instead of academia. Anyway, >I have both the luxury and lack of focus of no deadlines, no pressure to >publish. I hope to use Haskell to further my main hobby of knowledge >representation.) > >In perl, my labels/tags were very easy: > >In the initialization code: > > my @taglist = (); > my $nextag = "a"; > >and in the callback for the entry box: > > push(@taglist,$nextag); > $nextag++; > >(With the starting tag of "a" this results in "a",...."z","aa","ab",...) > >Also, ultimately, I want to be able to save my work and restart >the next day (say) picking up the tags where I left off. > >I'm darned if I can see how to do this in a callback without a global >variables (and references from other callbacks, by the way). > >In looking for a method, I've discovered that Haskell is a lot richer than >I thought (or learned when I tinkered with it back in the late '90s ). >I've found out about (but don't know how to use properly) implicit >parameters, linear implicit parameters, unsafePerformIO, "safe and sound >implementation of polymorphic heap with references and updates (Oleg >Kiselyov, (http://www.haskell.org/pipermail/haskell/2003-June/011939.html) >implicit configurations, phantom types, ... > >I've also found warnings against many of these. I'm inclined to try the >unsafePerformIO route as being the simplest, and most commonly used, even >though perhaps the least haskell-ish. I like implicit configurations, but >couldn't begin to say I understand them yet, and it's a bit heavy for a >novice. > >In a nutshell: > > I want to use the old value of a tag to compute the new value, in a > callback, > > I want to access the tag from other callbacks, and > > I want to the value to a mutable list from within the callback. > >I'd certainly be interested in doing without global variables, and would >appreciate any advice. > >(By the way, I'm using Linux, and so far it looks like HTk is my choice for >the GUI interface.) > >Best, > >John Velman >_______________________________________________ >Haskell mailing list >Haskell(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

foldlWhile
by Serge D. Mechveliani 22 Nov '04

22 Nov '04

Is such a function familia to the Haskell users? foldlWhile :: (a -> b -> a) -> (a -> Bool) -> a -> [b] -> a foldlWhile f p a bs = case (bs, p a) of ([], _ ) -> a (_, False) -> a (b:bs', _ ) -> foldlWhile f p (f a b) bs' foldl does not seem to cover this. Example. Sum the list while the sum is less than bound: boundSum :: Integer -> [Integer] -> Integer boundSum b = foldlWhile (+) (< b) 0 Example: boundSum 100 $ map (^2) [1 ..] Is this reasonable? More `generic' variant: foldlWhileJust :: (a -> b -> Maybe a) -> a -> [b] -> a foldlWhileJust f a bs = case bs of [] -> a b:bs' -> case f a b of Just a' -> foldlWhileJust f a' bs' _ -> a Please, copy the replies to mechvel(a)botik.ru ----------------- Serge Mechveliani mechvel(a)botik.ru

3 2