May 2007 - Haskell-Cafe

shared oneShot IO (was top-level state proposals)
by Claus Reinke 29 May '07

29 May '07

i thought the discussion had actually progressed a little further than might be obvious from http://www.haskell.org/haskellwiki/Top_level_mutable_state here is my summary of what i thought was the state of the discussion, followed by a hopefully simpler proposal. first, i'd like to distinguish between two aspects of the problem: (a) shared identifiers (b) shared initialisation by (a), i mean identifiers shared between several functions, referring to the same item, such as 'System.IO.stdin' referring to _the_ standard input handle. by (b), i mean initialisation code that needs to be run once before a set of functions may be used, such as 'Network.Socket.withSocketsDo'. second, note that neither (a) nor (b) represents a problem for non-IO code: let-binding takes care of (a) and (b). the problem arises when (a) and (b) are combined with IO-based code, in particular, if the shared identifiers of (a) stand for IO-based items, such as IO-based initialisation in (b). the source of trouble lies in the interaction of let-bindings with IO-based code. we know how to share descriptions of IO actions: let a = putStr "hi ho" -- 1 in a >> a we also know how share the results of IO actions: do r <- getLine -- 2 return (r,r) in (1), the action description is shared, but the action itself is executed, possibly repeatedly, after substitution, in (2), the action is executed before substitution and before continuation (through monadic bind), and its result is shared. what we do not know is how to share IO actions themselves in a demand-driven way, ie how to describe an IO action that is executed at most once, only on demand, with shared result. i thought this had become clear through Adrian's oneShot examples, but it seems to be mentioned only as a sideline on the Top_level_mutable_state page. if we had the ability to specify shared IO actions, this would directly address the issue of (a) in the case of IO-based things, and that IO-based (a) could then be used to make IO-based (b) more convenient. aside: even IO-based (b) is not in itself impossible, it is just inconvenient and error-prone. a module could provide an initialisation action and require that to be executed before any of its other actions may be called. this is inconvenient, especially if initialisation generates results that need to be passed to several other actions, and it is error-prone, because Haskell does not directly support protocol types (guaranteeing that initialisation is always called before any of the other actions, and is only called once). we can address the 'before' typing by having all other actions take a parameter of a type that can only be produced by the initialisation code, but we cannot guarantee that initialisation will be called at most once, without relying on the user, or on a solution to (a). the latter brings us back to the sharing of IO actions. that is exactly what "the unsafePerformIO hack" tries to achieve: myGlobalVar :: IORef Int {-# NOINLINE myGlobalVar #-} myGlobalVar = unsafePerformIO (newIORef 17) we specify an IO action ('newIORef'), we specify a shared name for it ('myGlobalVar'), with a monomorphic type ('IORef Int'), we specify that we do not want the action description to be substituted before execution ('NOINLINE', usually also '-fno-cse'), to avoid the repeated execution shown in (1) above, and we do _not_ specify that the action should be executed before continuation, as it would be in (2) above, by _not_ using monadic bind. what the 'unsafePerformIO' does is to ensure that the action is executed before substitution. taken together, we get a by-need sharing of IO action execution similar to by-need sharing of expression evaluation. the aspects that make this a somewhat brittle and unsafe 'hack' are the use of a pragma to ensure semantics, the use of the 'unsafePerformIO' hook to extend the evaluator, the type that is no longer IO-based (it is 'IORef Int', not 'IO (IORef Int)'), and the implicit constraint to a monomorphic type. quite a complex interaction of features. it is great that these features allow us to experiment with possibilities not originally planned for in language or evaluator. but now that experimentation has settled down to a common pattern of using these extension hooks for a particular class of problems, it seems sensible to integrate that pattern into the language and evaluator proper, addressing the safety issues at the same time. which is what all this discussion has been about. among the approaches suggested, we have seen first-class modules (do the initialisation on import or export, then pass the result to the whole module, rather than to each function in it), top-level "mdo" (collect commuting IO actions, and execute them at a sensible point in time out-of-line), and type-based indexing (use types as shared identifiers). i like first-class modules, but they would be a rather substantial change to Haskell; i almost like the top-level 'mdo', but only if it can be made to behave exactly as a non-top-level 'mdo', something current proposals don't seem to achieve, because it would again require rather substantial changes; i think that type-based indexing is just another workaround, rather than a solution (in particular, types as globally shared identifiers have their own issues; cf the first-class labels proposal for Haskell': http://hackage.haskell.org/trac/haskell-prime/ticket/92 ). the most pragmatic approach seems to be the top-level 'mdo', but it would still be a substantial change in language and implementation, and it introduces a difference between top-level and non-top-level 'mdo' which would complicate the language. but if i'm not mistaken, none of that is necessary - the whole 'mdo' aspect was introduced only as an after-the-fact justification of a special syntax for addressing the shared-IO issue. and the complications arise because that special syntax really has a new semantics, and top-level bindings do not really behave like the 'let . = . ' and '<-' in an 'mdo', even if the former might be translated into the latter. ---------- proposal: introduce support for shared-on-demand IO actions if i try to remove all that 'mdo'-related justification, and focus on the shared-IO issue of the proposal, i end up with something like this (which is implied, but somewhat hidden in Top_level_mutable_state): -- library mkOnceIO :: IO a -> IO (IO a) mkOnceIO io = do mv <- newEmptyMVar demand <- newEmptyMVar forkIO (takeMVar demand >> io >>= putMVar mv) return (tryPutMVar demand () >> readMVar mv) -- usage, desugared {-# OPTIONS_GHC -fno-cse #-} {-# NOINLINE myGlobalVar #-} myGlobalVar :: IO (IORef Int) myGlobalVar = unsafePerformIO (mkOnceIO (newIORef 42)) main = do gv <- myGlobalVar doSomeThing gv and the syntax extension would be something like -- usage, sugared myGlobalVar <= newIORef 42 main = do gv <- myGlobalVar doSomeThing gv where '<=' compares to the existing '<-' and '=' as follows: '<=' vs '=': the binding is shared, but involves an IO action, and shares the IO action itself, not just its description '<=' vs '<-': the binding is monomorphic and involves the result of an IO action, but that action itself wrapped in IO, and is only executed on demand, at most once apart from the IO type, there is nothing global about this, '<=' could be used to specify oneShot actions whereever an IO action is defined. in particular, one could define initialisation actions in a module and import them: module MyIOBase(mkStdIn) where mkStdIn <= initialiseStdIn -- shared IO action, run at most once module MyIO where import MyIOBase(mkStdIn) getLine = do stdin <- mkStdIn hGetLine stdin module Main where import MyIO(getLine) main = getLine >>= ... since the oneShot actions are wrapped in IO, this extension does not allow IO action to be executed in pure code, and possible points of execution are clearly specified in the code, which is safer, but slightly more inconvenient than 'the unsafePerformIO hack', and simpler than the toplevel '<-' plus 'ACIO monad' proposal. since the proposal could be implemented by a local transformation, it should also be easier to realise. okay, now: are there any holes in this proposal?-) claus

2 2

data PLZ a
by dons＠cse.unsw.edu.au 29 May '07

29 May '07

We got the names wrong! data PLZ a = AWSUM_THX a | O_NOES String instance Monad PLZ where return = AWSUM_THX fail = O_NOES O_NOES s >>= _ = O_NOES s AWSUM_THX x >>= f = f x Thanks to mauke on #haskell. -- Don

4 4

Mysterious monads
by Andrew Coppin 29 May '07

29 May '07

Take a look at the following: data Writer o v = Writer [o] v instance Monad (Writer o) where return v = Writer [] v (Writer os v) >>= f = let (Writer os' v') = f v in Writer (os ++ os') v' write :: o -> Writer o () write o = Writer [o] () writes :: [o] -> Writer o () writes os = Writer os () By this code, I define a new monad where I can "write" stuff into a big list. (Although I notice this is going to get slower and slower as the list grows...) For example, test = do write 1 write 2 write 3 yields "Writer [1,2,3] ()". Now, how do I implement the following? data Reader i v = Reader [i] v instance Monad (Reader i) where return = ??? (>>=) = ??? read :: Reader o o such that a Reader is created with an initial list, and the read function fetches 1 element out of that list. That is, the expression "x <- read" will take the head element of the list and put it into x, keeping the tail to be read later. (Oh yeah - and apparently that clashes with Prelude.read. Oh well!) I can't figure out how to implement this... The closest I managed was to make a Reader object also contain a function that tells (>>=) what to do to the Reader object you're binding against... But that seems to be horribly buggy. Any thoughs?

6 12

Re: [Haskell-cafe] Cute code [was: The C Equiv of != in Haskell miscommunication thread]
by Roberto Zunino 29 May '07

29 May '07

(re-joining the list -- I forgot to "reply all") Vincent Kraeutler wrote: > Roberto Zunino wrote: >>Vincent Kraeutler wrote: >>>i see that the definition of fix (from Control.Monad.Fix) could not be >>>any simpler: >>> >>>>fix f = let x = f x in x >> >>I actually consider >> >>fix f = f (fix f) >> >>to be simpler. Alas, it breaks sharing... > > ;-) > sharing? > v. The two functions fix1 f = let x = f x in x fix2 f = f (fix2 f) have the same semantics. However I believe many implementations run them with different performance. Consider y = fix1 (2:) This would be expanded to y = let x = 2:x in x A typical implementation would then represent the infinite list using (roughly) a circular pointer-list, i.e. x = cons(2, pointer-to-x) . So, the tail of the list is shared with the list itself, causing a constant space to be allocated for the list, even if a large portion of the list is demanded as in (take 1000000 y). On the contrary, y = fix2 (2:) would be y = 2 : fix2 (2:) and, unless some optimization magic kicks in, the representation for y is not a circular list. Each time a new list element is demanded, a new cons cell will be allocated. Running (take 1000 y) would then "waste" space for 1000 copies of 2. This is because the tail is not shared. Zun.

1 0

Slower with ByteStrings?
by Jason Dagit 29 May '07

29 May '07

Hello, We recently had a challenge as follows: Given a word, find all the words in the dictionary which can be made from the letters of that word. A letter can be used at most as many times as it appears in the input word. So, "letter" can only match words with 0, 1, or 2 t's in them. I opted for simplicity in my implementation including hard coding the input word and using /usr/share/dict/words as the dictionary: -- Begin Words.hs module Main where import List -- I was lazy and borrowed perms from the Haskell wiki -- but I wrote everything else perms [] = [[]] perms xs = [ x : ps | x <- xs, ps <- perms (xs\\[x]) ] -- creates permutations of all lengths then cleans up duplicates and gets rid of the -- empty list, this is probably the least efficient way possible allPerms x = drop 1 $ sort $ nub $ concatMap inits $ perms x main = do wordList <- readFile "/usr/share/dict/words" let words = lines wordList mapM_ print $ filter (`elem` words) $ allPerms "ubuntu" -- End Words.hs Next I decided to try it with byte stings: -- Begin ByteStringWords.hs module Main where import List -- import qualified Data.ByteString.Char8 as C import qualified Data.ByteString.Lazy.Char8 as C -- I was lazy and borrowed perms from the Haskell wiki -- but I wrote everything else perms [] = [[]] perms xs = [ x : ps | x <- xs, ps <- perms (xs\\[x]) ] -- creates permutations of all lengths then cleans up duplicates and gets rid of the -- empty list, this is probably the least efficient way possible allPerms x = drop 1 $ sort $ nub $ concatMap inits $ perms x main = do wordList <- C.readFile "/usr/share/dict/words" let words = C.lines wordList mapM_ print $ filter (`elem` words) $ map C.pack $ allPerms "ubuntu" -- End ByteStringWords.hs I don't think the overhead to compute the permutations matters here as the input to the permutations calculation is so small. Any ideas why the byte string version is slower? (Strict bytestrings appear to be about 2 seconds slower and lazy bytestrings appear to be about 1 second slower). I think, given my simple algorithm that means that (==) for ByteStrings is slower than (==) for String. Is this possible? I think the program might be spending more time cleaning up after execution with the ByteString versions as it seems to "stall" after printing the last match. Thanks, Jason

6 8

Cabal can't install in home directory
by Grzegorz 29 May '07

29 May '07

Hi, It seems that if GHC is installed non-user-writable directory, and you want to install a package in the home directory (using "runghc Setup configure --prefix=$HOME") this isn't possible: when running "runghc Setup install" you get an error like this: Unable to rename "/usr/lib/ghc-6.6.1/package.conf" to "/usr/lib/ghc-6.6.1/package.conf.old" Saving old package config file... ghc-pkg.bin: /usr/lib/ghc-6.6.1/package.conf: renameFile: permission denied (Permission denied) Shouldn't that be fixed? Best, -- Grzegorz

2 2

Yet another top-level state proposal
by Judah Jacobson 29 May '07

29 May '07

Hi all, Given the recent discussion about adding top-level mutable state to Haskell, I thought it might be a good time to throw my own proposal into the ring. If enough people think it's worth considering, I can add it to the wiki page. (http://www.haskell.org/haskellwiki/Top_level_mutable_state) In contrast to recent proposals, this one requires no extra syntax or use of unsafe functions by the programmer. Any nonstandard "magic" that might occur is kept within the compiler internals. Furthermore, top-level initializations are only executed when needed; merely importing a module does not cause any additional actions to be run at startup. The core idea, similar to that of "type-based execution contexts" on the above wiki page, is to associate each top-level action with its own type. For example, the current way to declare a source for unique integers is: ------------------------------------------------ {-# NOINLINE uniqueRef #-} uniqueRef :: IORef Integer uniqueRef = unsafePerformIO $ newIORef 0 uniqueInt :: IO Integer uniqueInt = do n <- readIORef uniqueRef writeIORef uniqueRef (n+1) return n ------------------------------------------------ Under this proposal, we would write instead: ------------------------------------------------ newtype UniqueRef = UniqueRef (IORef Integer) deriving OnceIO instance OnceInit UniqueRef where onceInit = liftM UniqueRef (newIORef 0) uniqueInt :: IO Integer uniqueInt = do UniqueRef uniqueRef <- runOnceIO n <- readIORef uniqueRef writeIORef uniqueRef (n+1) return n ------------------------------------------------ The above code uses two classes: class OnceInit a where onceInit :: IO a class OnceInit a => OnceIO a where runOnceIO :: IO a The OnceInit class lets the programmer to specify how a type is initialized; above, it just allocates a new IORef, but we could also read a configuration file or parse command-line arguments, for example. In contrast, instances of the OnceIO class are not written by the programmer; instead, they are generated automatically by a "deriving OnceIO" clause. Each type for which OnceIO is derived will have a special top-level action associated with it, which is accessed through the runOnceIO function. Its semantics are: - The first time that "runOnceIO" is called, it runs the corresponding "onceInit" action and caches and returns the result. - Every subsequent time that "runOnceIO" is called, it returns the cached result. This behavior is safe precisely because runOnceIO is an IO action. Even though one can't guarantee when in the program an initialization will occur, when the initialization does happen it will be sequenced among other IO actions. To illustrate this behavior, here are a couple sample implementations in plain Haskell. These do use unsafePerformIO, but in practice any such details would be hidden in the instance derived by the compiler (along with any related NOINLINE/NOCSE pragmas): instance Once UniqueRef where runOnceIO = return $! unsafePerformIO onceInit or (less efficient, but multithreaded safe): instance Once UniqueRef where runOnceIO = modifyMVar onceUniqueRef $ \mx -> case mx of Just x -> return (Just x, x) Nothing -> do {x <- onceInit; return (Just x, x)} onceUniqueRef = unsafePerformIO $ newMVar Nothing Finally, note that the deriving clause can easily check whether the type in question is monomorphic (as is necessary for type-safety), since it already has access to the type definition. Anyway, that's the gist of my proposal; I hope I've explained it well, but please let let me know if you have questions, suggestions or criticisms. Best, -Judah

6 6

Re: [Haskell-cafe] The C Equiv of != in Haskell
by PR Stanley 29 May '07

29 May '07

>Hi > >>What is the C equivalent of the inequality operator in Haskell? > >/= > >You can answer these sorts of questions yourself using Hoogle: And what makes you think I haven't tried Google already? Unlike you I only write to the list when I have a legitimate reason to do so.

9 12

Re: [Haskell-cafe] The C Equiv of != in Haskell
by PR Stanley 29 May '07

29 May '07

Thank you Neil, again I'm sorry for getting the wrong end of the stick. Cheers Paul At 02:50 29/05/2007, you wrote: >Hi Paul > >Sorry if you interpreted my answer as a symbol, I never use smilies so >didn't even consider that people may see it in another light! > >Thanks > >Neil > > >On 5/29/07, PR Stanley <prstanley(a)ntlworld.com> wrote: >> >> > > >Hi >> > > > >> > > >>What is the C equivalent of the inequality operator in Haskell? >> > > > >> > > >/= >> > > > >> > > >You can answer these sorts of questions yourself using Hoogle: >> > > >> > > And what makes you think I haven't tried Google already? >> > > Unlike you I only write to the list when I have a legitimate >> reason to do >> > > so. >> > >> >Just in case there was some sort of miscommunication, the actual answer to >> >your question is (/=) :: a -> a -> Bool, as Neil said. >> > >> >The /= wasn't some sort of frowny, quit-wasting-my-time emoticon. >> >_______________________________________________ >>Thank you, Dan. >>Regards >>Paul >> >>_______________________________________________ >>Haskell-Cafe mailing list >>Haskell-Cafe(a)haskell.org >>http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Re: [Haskell-cafe] The C Equiv of != in Haskell (Apologies)
by PR Stanley 29 May '07

29 May '07

>Hi > >> >You can answer these sorts of questions yourself using Hoogle: >>And what makes you think I haven't tried Google already? > >Hoogle, starting with 'H'. Follow the link I gave you, which is a >search engine for Haskell functions, by type and name. If you search >for "a -> a -> Bool" (a likely type that the != would have) then >Hoogle gives you an answer. > >>Unlike you I only write to the list when I have a legitimate reason to do so. > >I am not suggesting you have no legitimate reason, just trying to help >you find the information you need quicker in future. I was in no way >trying to suggest you shouldn't have posted - its a fair question >given its a different choice to most other languages. > >Thanks > >Neil Thank you,Neil. I apologise for my sharp response. It's been a long day. However, I don't think these other individuals had any business poking their hooters into this. All the best, Paul

2 1