- Haskell-Cafe - Haskell.org

Space leak whilst implementing streams
by ephemeral.elusive＠gmail.com 26 Aug '06

26 Aug '06

Hello, I have been using arrows to implement stream processors. At first, I tried using the implementation presented in John Hughes' AFP arrows lectures. However, this appeared to have a space leak in its implementation of the left operator for ArrowChoice. I found a way to remove this space leak, however, I do not really understand why there was a space leak in the first place. I would really appreciate any light that could be shed on this. Below I include the AFP implementation (SF) and a modified implementation that no longer has the space leak (SF'). I am using ghc 6.4.2. Many thanks. import Control.Arrow import Data.Maybe main = test test = print (runSF p (repeat 1)) test' = print (runSF' p (repeat (Just 1))) -- heap profile appears to grow linearly for test, but not test' p :: ArrowChoice a => a Int (Either Int Int) p = arr Right >>> left (arr id) newtype SF a b = SF {runSF :: [a] -> [b]} instance Arrow SF where arr f = SF (map f) SF f >>> SF g = SF (f >>> g) first (SF f) = SF (unzip >>> first f >>> uncurry zip) instance ArrowChoice SF where left (SF f) = SF (\xs -> combine xs (f [y | Left y <- xs])) where combine (Left _:xs) (z:zs) = Left z :combine xs zs combine (Right r:xs) zs = Right r:combine xs zs combine [] _ = [] -- SF' does not exhibit the space leak newtype SF' a b = SF' {runSF' :: [Maybe a] -> [Maybe b]} instance Arrow SF' where arr f = SF' (map (maybe Nothing (Just . f))) SF' f >>> SF' g = SF' (f >>> g) first (SF' f) = SF' (maybe_unzip >>> first f >>> uncurry maybe_zip) where maybe_unzip = foldr mu ([],[]) where mu Nothing ~(xs,ys) = (Nothing:xs, Nothing: ys) mu (Just (x,y)) ~(xs,ys) = (Just x:xs, Just y: ys) maybe_zip = zipWith mz where mz (Just x) (Just y) = Just (x,y) mz Nothing Nothing = Nothing instance ArrowChoice SF' where left (SF' f) = SF' (\xs -> xs `combined` f (map drop_right xs)) where combined = zipWith merge_left drop_right Nothing = Nothing drop_right (Just (Left l)) = Just l drop_right (Just (Right _)) = Nothing merge_left Nothing Nothing = Nothing merge_left (Just (Left _)) (Just x) = Just (Left x) merge_left (Just (Right r)) Nothing = Just (Right r)

2 1

ghc profiling
by Jeff Polakow 25 Aug '06

25 Aug '06

Hello, When I compile my program without profiling: bash-3.1$ ghc --make -auto-all -prof -O -o analysis analysis.hs Chasing modules from: analysis.hs Compiling Main ( analysis.hs, analysis.o ) Linking ... everything works fine. However when I compile with profiling: bash-3.1$ ghc --make -auto-all -prof -O -o analysis analysis.hs Chasing modules from: analysis.hs Could not find module `Data.ByteString.Lazy.Char8': use -v to see a list of the files searched for (imported from analysis.hs) ghc complains about not finding the ByteString library. Is this supposed to hapen, and if so, is there a way to get profiling to work? thanks, Jeff -- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

2 1

USB Drivers in Haskell
by Jason Dagit 25 Aug '06

25 Aug '06

Hello, I recently became the owner a USB gadget that tracks movement via GPS and also tracks heart rate (it's a training device for athletes). This device comes with software that is windows only and...doesn't like up to it's potential (to put it politely). Being a programmer type and someone that prefers to use either linux or osx I quickly realized I should write my own software to use the gadget. Fortunately, the company that makes the device provides documentation to write drivers for the device (including a minimal example USB driver for win32). So then I looked around the net for a few open source things, such as open source drivers for the device or a Haskell library to help me start writing drivers for the gadget. I didn't see anything relevant after a few minutes of searching so I figure that means there isn't much. Did I miss a Haskell library for writing device drivers, specifically USB drivers? Would this be hard to write? I would prefer to support osx and linux at a minimum and I think it would be ideal to shoot for cross platform (win32, osx, linux and *bsd). I have this feeling that it could be done by writing platform specific wrappers using hsc2hs on each platform then bringing them together through a unified 'low' level Haskell api. The Haskell api would then be exposed as a module for application developers. Any thoughts? For the interested, the documentation I spoke of can be found here: http://www.garmin.com/support/commProtocol.html Thanks, Jason

2 2

A possible use for HSFFIG (FFIPKG) was USB Drivers in Haskell
by Dimitry Golubovsky 25 Aug '06

25 Aug '06

Bjorn Bringert wrote: >For cross-platform USB drivers, you may want to have a look at libusb >[1]. I have only used it under Linux, but it seems to support Linux, >*BSD and OS X. There also seems to be a win32 port [2]. A Haskell >binding to libusb would be very welcome. I'm just wondering, would FFIPKG or HSFFIG help out? I just looked at usb.h, and it does not seem to contain anything that would break HSFFIG (mainly C functions that take/return structures rather than pointers to structures, do). I am not very much interested personally in interfacing USB, but if anybody is, feel free to try FFIPKG out and ask questions. PS Sorry for such "self-advertising", but I believe that this tool could be helpful at least for prototyping bindings, so I'd appreciate any feedback. -- Dimitry Golubovsky Anywhere on the Web

1 0

a novice Alex question
by Xiong Yingfei 25 Aug '06

25 Aug '06

Hi, I am trying out Alex. I copied the calculator specification file from Alex's official document and changed the wrapper type from "basic" to "monad". However, after I generated the ".hs" file from the lexical specification and compiled the ".hs" file, I got the message "Variable not in scope: `alexEOF'". I cannot find explanation about this 'alexEOF' function in the document. Can any body be kindly enough to tell me what this function is? Should I write it myself or not? My lexical code is listed as the below. Thanks a lot. { module Lex where } %wrapper "monad" $digit = 0-9 -- digits $alpha = [a-zA-Z] -- alphabetic characters tokens :- $white+ ; "--".* ; let { \s -> Let } in { \s -> In } $digit+ { \s -> Int (read s) } [\=\+\-\*\/] { \s -> Sym (head s) } $alpha [$alpha $digit \_ \']* { \s -> Var s } { -- Each action has type :: String -> Token -- The token type: data Token = Let | In | Sym Char | Var String | Int Int deriving (Eq,Show) } -- Xiong, Yingfei (熊英飞) Ph.D. Student Institute of Software School of Electronics Engineering and Computer Science Peking University Beijing, 100871, PRC. Web: http://xiong.yingfei.googlepages.com

3 2

style question: Writer monad or unsafeIOToST?
by Gregory Wright 25 Aug '06

25 Aug '06

Hi, Thanks to the responses earlier from the list, the core of my simulator now happy processes tens of millions of state updates without running out of stack. The goal of the simulator is to produce a log of tag states, which can be analyzed to find statistics of how often the sensor tags in a particular state. (In the toy model below there is no external signal, so the log isn't very interesting yet.) For the moment, I am using the "big stick" approach of unsafeIOToST to write log messages. Since the only outputs of the program are the log messages, and invocations of "step" are ordered by the ST monad, it seems that unsafeIOToST is safe in this case, in the sense that the outputs will all be ordered the same as the actual state updates. I've tested the program test1.hs below and it quite fast (runs in just under 10 s, or about 10^6 state updates per second). I've considered using a WriterT monad to wrap the ST monad to produce a log. The problem with this seems to be ensuring that the log output is generated lazily so it can be incrementally output. A somewhat broken sketch is the program test2.hs below. I used a function from [String] -> [String] as the monoid to avoid the O(n^2) inefficiency of appending to a list, but my implementation of this may well be faulty. To my eye, the Writer monad should be a better way, since it encapsulates the logging process, separating it from other I/O that the program may do. On the other hand, I don't see an easy way to ensure that the log output is generated lazily so that it can be output incrementally. I think that the main issue is that until_ is building up a list of log strings, but that these aren't passed to the putStrLn until after the completion of the whole runTag function. ATM, running test2 gives a stack overflow. Could someone point out how the Writer monad could be adapted to this, or tell me that, "Real programmers just use unsafe* and get on with it" ? Best, greg ------------------------------------------------------------------------ ------------------------------ test1.hs, the big stick (unsafeIOToST): -- -- test1.hs, state updating with logging via unsafeIOToST. -- module Main where import Control.Monad.ST import Data.STRef import Maybe data TagState = Syncing | Listening | Sleeping deriving (Eq, Show) -- A structure with internal state: -- data Tag s = Tag { tagID :: ! Int, state :: ! (STRef s TagState), count :: ! (STRef s Integer) } data FrozenTag = FrozenTag { ft_tagID :: Int, ft_state :: TagState, ft_count :: Integer } deriving Show -- Repeat a computation until it returns Nothing: -- until_ :: Monad m => m (Maybe a) -> m () until_ action = do result <- action if isNothing result then return () else until_ action -- Here is a toy stateful computation: -- runTag :: ST s (FrozenTag) runTag = do tag <- initialize until_ (step tag) freezeTag tag initialize :: ST s (Tag s) initialize = do init_count <- newSTRef 1000000 init_state <- newSTRef Syncing return (Tag { tagID = 1, state = init_state, count = init_count }) step :: Tag s -> ST s (Maybe Integer) step t = do c <- readSTRef (count t) s <- readSTRef (state t) writeSTRef (count t) $! (c - 1) writeSTRef (state t) $! (nextState s) unsafeIOToST $! putStrLn ("next state is " ++ show s) if (c <= 0) then return Nothing else return (Just c) nextState :: TagState -> TagState nextState s = case s of Syncing -> Listening Listening -> Sleeping Sleeping -> Syncing freezeTag :: Tag s -> ST s (FrozenTag) freezeTag t = do frozen_count <- readSTRef (count t) frozen_state <- readSTRef (state t) return (FrozenTag { ft_tagID = tagID t, ft_count = frozen_count, ft_state = frozen_state }) main :: IO () main = do print $ runST (runTag) ------------------------------------------------------------------------ ----------------------------------------- test2.hs: stacked WriterT and ST monads: -- -- test2.hs, state updating with logging via the WriterT monad. -- module Main where import Control.Monad.ST import Control.Monad.Writer import Data.STRef import Maybe data TagState = Syncing | Listening | Sleeping deriving (Eq, Show) -- A type for combined logging and state transformation: -- type LogMonoid = [String] -> [String] type LogST s a = WriterT LogMonoid (ST s) a -- A structure with internal state: -- data Tag s = Tag { tagID :: ! Int, state :: ! (STRef s TagState), count :: ! (STRef s Integer) } data FrozenTag = FrozenTag { ft_tagID :: Int, ft_state :: TagState, ft_count :: Integer } deriving Show -- Repeat a computation until it returns Nothing: -- until_ :: Monad m => m (Maybe a) -> m () until_ action = do result <- action if isNothing result then return () else until_ action -- Here is a toy stateful computation: -- runTag :: LogST s (FrozenTag) runTag = do tag <- initialize until_ (step tag) freezeTag tag initialize :: LogST s (Tag s) initialize = do init_count <- lift $ newSTRef 1000000 init_state <- lift $ newSTRef Syncing return (Tag { tagID = 1, state = init_state, count = init_count }) step :: Tag s -> LogST s (Maybe Integer) step t = do c <- lift $ readSTRef (count t) s <- lift $ readSTRef (state t) lift $ writeSTRef (count t) $! (c - 1) lift $ writeSTRef (state t) $! (nextState s) tell (("next state is " ++ show s) : ) if (c <= 0) then return Nothing else return (Just c) nextState :: TagState -> TagState nextState s = case s of Syncing -> Listening Listening -> Sleeping Sleeping -> Syncing freezeTag :: Tag s -> LogST s (FrozenTag) freezeTag t = do frozen_count <- lift $ readSTRef (count t) frozen_state <- lift $ readSTRef (state t) return (FrozenTag { ft_tagID = tagID t, ft_count = frozen_count, ft_state = frozen_state }) main :: IO () main = do let (t, l) = runST (runWriterT runTag) putStrLn (show t) putStrLn (unlines (l []))

3 10

monads once again: a newbie perspective
by Andrea Rossato 25 Aug '06

25 Aug '06

Hello! I' m new to Haskell and try to find my way through types and monads. I tried the yet Another Haskell Tutorial, very useful for types, but almost unreadable for monads (that's my perspective!). Then I discovered that wonderful paper by Wadler (Monads for functional programming). So I started "translating it" for someone who can be scared of something with an abstract and footnotes coming from a professor. I started writing it in order to clarify to myself this difficult topic. I think I'm now grasping the concept of monads. I thought that someone else could find my writings useful. It could become a page on the wiki. But before posting there I would like to have your opinion. Perhaps this is just something unreadable. Let me know. Andrea

3 3

stack overflow when using ST monad
by Gregory Wright 24 Aug '06

24 Aug '06

Hi, I have a program, abstracted from a larger application that I am writing for a customer, that persistently overflows its stack. The program is a simulation of the communication protocol of a sensor tag. The code is below. The program mimics a hardware state machine. In the example below, the internal state is just a counter and a another register that holds what is called the tag's "state": Syncing, Listening or Sleeping. The simulation just advances the tags internal state until the counter reaches zero. (In the real application, there are external inputs that can change the state, but that's not needed to see the problem.) The simulation crashes, running out of stack space after only about 400000 cycles on my machine (OS X 10.4.7 ppc). Both hugs and ghci show it: hugs -98 Test2.hs Hugs mode: Restart with command line option +98 for Haskell 98 mode Type :? for help Main> main ERROR - Garbage collection fails to reclaim sufficient space Main> and ghci: Prelude> :load "/Users/gwright/src/haskell/simulator/test2.hs" Compiling Main ( /Users/gwright/src/haskell/simulator/ test2.hs, interpreted ) Ok, modules loaded: Main. *Main> main FrozenTag {ft_tagID = 1, ft_state = *** Exception: stack overflow *Main> Searches through old mailing lists warn me that it can be hard to tell if evaluation is truly tail recursive, and I saw a discussion of this in the context of "monadic loops", but I never saw a solution. Perhaps in my sleep deprived condition I am missing the obvious, but any help would be appreciated. Best, Greg -- -- Test the state transformer calculation. -- -- 21 August 2006 -- module Main where import Control.Monad.ST import Control.Monad.Writer import Data.STRef import Maybe data TagState = Syncing | Listening | Sleeping deriving (Eq, Show) -- A structure with internal state: -- data Tag s = Tag { tagID :: Int, state :: STRef s TagState, count :: STRef s Integer } data FrozenTag = FrozenTag { ft_tagID :: Int, ft_state :: TagState, ft_count :: Integer } deriving Show -- Repeat a computation until it returns Nothing: -- until_ :: Monad m => m (Maybe a) -> m () until_ action = do result <- action if isNothing result then return () else until_ action -- Here is a toy stateful computation: -- runTag :: ST s (FrozenTag) runTag = do tag <- initialize until_ (step tag) freezeTag tag initialize :: ST s (Tag s) initialize = do init_count <- newSTRef 1000000 init_state <- newSTRef Syncing return (Tag { tagID = 1, state = init_state, count = init_count }) step :: Tag s -> ST s (Maybe Integer) step t = do c <- readSTRef (count t) s <- readSTRef (state t) writeSTRef (count t) (c - 1) writeSTRef (state t) (nextState s) if (c <= 0) then return Nothing else return (Just c) nextState :: TagState -> TagState nextState s = case s of Syncing -> Listening Listening -> Sleeping Sleeping -> Syncing freezeTag :: Tag s -> ST s (FrozenTag) freezeTag t = do frozen_count <- readSTRef (count t) frozen_state <- readSTRef (state t) return (FrozenTag { ft_tagID = tagID t, ft_count = frozen_count, ft_state = frozen_state }) main :: IO () main = do putStrLn (show (runST runTag))

5 9

Fran - Functional Reactive Animation
by HIGGINS Neil (ENERGEX) 24 Aug '06

24 Aug '06

> Fran is a Haskell library (or "embedded language") for interactive > animations with 2D and 3D graphics and sound. See > <http://www.conal.net/fran/ <http://www.conal.net/fran/> > and > <http://research.microsoft.com/research/downloads/download.aspx?FUID=c9eff > 407-ce59-4a2a-90cb-de099a9bacbd > <http://research.microsoft.com/research/downloads/download.aspx?FUID=c9eff > 407-ce59-4a2a-90cb-de099a9bacbd> > > > I would like to use Fran as a rapid prototyping environment for > animations, but it appears to be broken under WinHugs. > > I'm looking for someone with much better Haskell prowess than myself who > might be able resurrect Fran under WinHugs. Unfortunately I can only offer > my gratitude in return. > > It's a long shot, I know. > Kind regards, > Neil Higgins > Snr Strategic Planning Engineer > ENERGEX > Em: neilhiggins(a)energex.com.au > Ph: 3407 4800 > Fx: 3407 4832 > ************************************************************************* This email message (including any file attachments transmitted with it) is for the sole use of the intended recipient(s) and may contain confidential and legally privileged information. Any unauthorised review, use, alteration, disclosure or distribution of this email (including any attachments) by an unintended recipient is prohibited. If you have received this email in error, please notify the sender by return email and destroy all copies of the original message. Any confidential or legal professional privilege is not waived or lost by any mistaken delivery of the email. ENERGEX accepts no responsibility for the content of any email which is sent by an employee which is of a personal nature. Sender Details: ENERGEX GPO Box 1461 Brisbane QLD Australia 4001 +61 7 3407 4000 http://www.energex.com.au ENERGEX policy is to not send unsolicited electronic messages. Suspected breaches of this policy can be reported by replying to this message including the original message and the word "UNSUBSCRIBE" in the subject. *************************************************************************

3 2

wiki page Arrays updated
by Bulat Ziganshin 24 Aug '06

24 Aug '06

Hello Haskell-Cafe, i've added a lot of low-level information to the Arrays wiki page. new material starts from note about GHC 6.6 in http://haskell.org/haskellwiki/Modern_array_libraries#StorableArray_.28modu… there are several details, however, which makes it imperfect. first, as usual, is my awkward English. please correct my language misuse. in particular, i don't know how to better name the page itself, meaning "modern library which implements many array types" second is that it will be great to add examples demonstrating each discussed concept: casting, freezing, unsafe indexing, [::]. we also still don't have examples for unboxed and diff arrays third is that i'm not 100% sure that information about GHC internals i provided is correct. can someone with a good knowledge of RTS internals check it, including http://haskell.org/haskellwiki/Modern_array_libraries#Welcome_to_machine:_A… and next section plus abovementioned link with information about StorableArray in GHC 6.6? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0