- Haskell-Cafe - Haskell.org

ANN: linearscan, linearscan-hoopl 1.0.0
by John Wiegley 20 Nov '15

20 Nov '15

linearscan[1] is a linear scan register allocator[2], written in Coq[3], and extracted to Haskell, as a library for Haskell programs that need to allocate registers. It may also be used directly from Coq. This project is the result of a year-long effort, funded by BAE Systems[4], to explore the application of dependent-types and mathematical verification to a typical engineering task. During the course of construction, several hundred theorems about the code were proven -- although exhaustive coverage was not, in the end, achievable given our time constraints. To remedy this, and as a test of the extraction to Haskell, an optional runtime verifier was built to certify the resulting allocations. Coq 8.5b2[5] was used, as well as the ssreflect[6] library created for that version[7]. linearscan further relies on another library, coq-haskell[8], that I created to facilitate inter-operation between Haskell and Coq. For those using Hoopl[9] to represent program graphs, incorporating linearscan is quite easy: provide an instance of NodeAlloc using the linearscan-hoopl[10] library. Examples of doing so are provided in the test suite for that library. The allocation algorithm implemented by this library was first written in Java by Hanspeter Mössenböck and Michael Pfeiffer[11], and later improved upon by Christian Wimmer[12], whose master's thesis provided the specification for our implementation. John Wiegley BAE Systems Footnotes: [1] http://hackage.haskell.org/package/linearscan [2] http://www.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf [3] https://coq.inria.fr/ [4] http://www.baesystems.com/en-us/our-company/inc-businesses/electronic-syste… [5] https://coq.inria.fr/news/125.html [6] http://ssr.msr-inria.inria.fr/ [7] http://ssr.msr-inria.inria.fr/FTP/ [8] https://github.com/jwiegley/coq-haskell [9] https://hackage.haskell.org/package/hoopl [10] http://hackage.haskell.org/package/linearscan-hoopl [11] http://dl.acm.org/citation.cfm?id=647478.727924 [12] http://www.christianwimmer.at/Publications/Wimmer04a/

1 0

Why is my mappend so slow?
by martin 20 Nov '15

20 Nov '15

Hello all, I wrote a Logger which, under certain conditions, prepends log-entries to a log and a Monoid instance of it. But as soon as I mappend two Loggers my performance drops by 50%. This even happens when I mappend mempty as shown below in --<2--. I understand that the system has to do *something*, but it seems to cost a bit much. Without the strictness annotation in --<1-- the performance degradation is even more dramatic (orders of magnitude). The profile tells me that more that 50% of the time is spent in mappend. COST CENTRE MODULE %time %alloc mappend.\ Logger 50.6 35.8 logCount'.f Logger 18.7 40.3 logCount' Logger 5.4 0.0 Why is that so, and can I do anything about it? I am willing to change the overall design if required. This is the code -- | A writer does the formatting newtype Wtr a log = Wtr {runWtr :: a -> log} -- | A looger is a writer plus an internal state data Logger a log = Lgr {runLogger :: a -> log -> (log, Logger a log)} instance Monoid (Logger a log) where mempty = Lgr (\_ l -> (l,mempty)) mappend lgr1 lgr2 = Lgr $ \a l -> let !(log1',!lgr1') = runLogger lgr1 a l --<1-- !(log2',!lgr2') = runLogger lgr2 a log1' --<1-- in (log2', mappend lgr1' lgr2') and this is how I test it -- | Count calls __s__ and write log when s has reached nxt and then every dn calls logCount' :: Monoid log => Int -> Int -> Int -> Wtr (Int,a) log -> Logger a log logCount' dn nxt s wtr = Lgr f where f a l = if s == nxt then (runWtr wtr (s,a) <> l, logCount' dn (nxt+dn) (s+1) wtr) else (l, logCount' dn nxt (s+1) wtr) -- | Count calls and write log every dn calls logCount dn = logCount' dn dn 0 -- testLogger :: Logger Int Int [String] -> [String] testLogger lgr xs = fst $ foldl' f ([],lgr) xs where f (log', lgr') x = runLogger lgr' x log' ex_wtr :: Wtr (Int,a) [String] ex_wtr = Wtr $ \(x,_) -> ["Counted to " ++ (show x)] ex_wtr2 :: Wtr Int [String] ex_wtr2 = Wtr $ \x -> ["Counted to " ++ (show x)] ex_inputs :: [Int] ex_inputs = [1..10000000] ex_logger = mempty <> logCount 300000 ex_wtr <> mempty --<2-- -- ex_logger = logCount 300000 ex_wtr ex_main = do timeIt $ putStrLn $ ppShow $ testLogger ex_logger ex_inputs main = ex_main

4 8

Partition int 180. Out of memory
by Kees Bleijenberg 19 Nov '15

19 Nov '15

I want to partition the integer n=180 with terms >=5 I.e. n=15 => [[5,5,5],[8,7],[9,6],[10,5],[15]] The function part does this. memopart does it with memoization a lot faster. mempart works fine on my machine until n=120. For n=130 I get 'out of memory'. For other reasons I work on Win64 with ghc32. To save memory I replaced Int with Word8. I also replaced [Word8] with B.ByteString (memopartB). But no luck. I still get 'out of memory' for n=130. I run the program with: part +RTS -M4294967295 (429... is according to ghc the max memory I can use) Any ideas how to solve this? What is the most memory efficient replacement for a list? module Main ( main,part,memopart ) where import Data.Int import System.Time import qualified Data.ByteString.Lazy as B import Data.Word import Data.List (intercalate) part :: Int -> [[Int]] part 0 = [[]] part n = [x:y | x <- [5..n], y <- part (n-x), [x] >= take 1 y] partB :: Word8 -> [B.ByteString] partB 0 = [B.empty] partB n = [B.cons x y | x <- [5..n], y <- partB (n-x), B.singleton x >= y] memopart a = memo !! a where memo = [[]] : [[x:y | x <- [5..n], y <- memo !! (n-x), [x] >= take 1 y] | n <- [5..]] memopartB :: Int -> [B.ByteString] memopartB a = memo !! a where memo :: [[B.ByteString]] memo = [B.empty] : [[B.cons x y | x <- [5 :: Word8 .. n :: Word8], y <- memo !! minusWord8 n x, B.singleton x >= y] | n <- [5 :: Word8 ..]] minusWord8 :: Word8 -> Word8 -> Int minusWord8 c d = (fromIntegral c :: Int) - (fromIntegral d:: Int) main = do startTime <- getClockTime -- print $ length $ memopart 50 putStrLn $ showPartBRes $ memopartB 120 stopTime <- getClockTime putStrLn ("Time: " ++ timeDiffToString (diffClockTimes stopTime startTime)) showPartBRes :: [B.ByteString] -> String showPartBRes res = intercalate ", " $ map showB res where showB :: B.ByteString -> String showB arr = '[' : intercalate "," (B.foldr (\w acc -> show w : acc) [] arr) ++ "]"

3 3

ANN: haskell-src-exts 1.17
by Matthew Pickering 18 Nov '15

18 Nov '15

Dear list, I am pleased to report that Peter has just released a new version of haskell-src-exts. I include the release notes below. This release fixes a large number of long standing bugs so I urge all users to update their projects to use this new version. If haskell-src-exts fails to parse a program which GHC accepts then please report an issue to the issue tracker. Best wishes, Matt --------- I am pleased to announce the release of haskell-src-exts-1.17.0! Hackage: https://hackage.haskell.org/package/haskell-src-exts-1.17.0 GitHub: https://github.com/haskell-suite/haskell-src-exts This release brings bugfixes, as well as the following language features: * Type wildcards and expression holes (#252). * Pattern Synonyms (#197). The full changelog is available at https://github.com/haskell-suite/haskell-src-exts/blob/1.17.0/CHANGELOG This release is brought to you by: Matthew Pickering Michael Walker Simon Marlow Neil Mitchell JP Moresmau Артур Файзрахманов phischu Michael Sloan m00nlight Niklas Broberg Stijn van Drongelen Jakub Kozlowski Leonid Onokhov Matthew Pickering is a force of nature who deserves a special mention for all his contributions to this release. Peter

1 0

Call For Presentations: Compose 2016, New York, Feb 4-5
by Gershom B 18 Nov '15

18 Nov '15

Compose is a conference for typed functional programmers, focused specifically on Haskell, OCaml, F#, and related technologies. It will be held in New York on Thursday and Friday, Feb 4-5, 2016. Registration will be open shortly. http://www.composeconference.org/ To get a sense of Compose, you can check out the great talks from the 2015 conference: http://www.composeconference.org/2015/summary/ Below is our call for presentations. We recognize the deadline is tight, so feel free to submit proposals and ideas on the less-polished side. http://www.composeconference.org/2016/cfp/ * * * The audience for Compose is Haskell, OCaml, F#, or SML developers who are looking to increase their skills or learn new technologies and libraries. Presentations should be aimed at teaching or introducing new ideas or tools. We are also interested in presentations aiming at taking complex concepts, such as program derivation, and putting them into productive use. However proposals on anything that you suspect our audience may find interesting are welcome. The following are some of the types of talks we would welcome: Library/Tool Talks — Exploring the uses of a powerful toolkit or library, be it for parsing, testing, data access and analysis, or anything else. Production Systems — Experience reports on deploying functional techniques in real systems; insights revealed, mistakes made, lessons learned. Theory made Practical — Just because it’s locked away in papers doesn’t mean it’s hard! Accessible lectures on classic results and why they matter to us today. Such talks can include simply introducing the principles of a field of research so as to help the audience read up on it in the future; from abstract machines to program derivation to branch-and-bound algorithms, the sky’s the limit. We also welcome proposals for more formal tutorials. Tutorials should be aimed at a smaller audience of beginner-to-novice understanding, and ideally include hands-on exercises. The due date for submissions is December 14, 2015. We will send out notice of acceptance by December 24th. We prefer that submissions be via the EasyChair website (https://easychair.org/conferences/?conf=compose2016) Please suggest a title, and describe the topic you intend to speak on. Talks can be either 30 or 45 minutes, please indicate how much time you would prefer to take. Additional information may be included on both your expertise and the interesting elements of your topic, going on what might be included in a public abstract. Furthermore, if your abstract doesn't feel "final"—don't worry! We'll work with you to polish it up. If you want to discuss your proposal(s) before submitting, or to further nail down what you intend to speak on, please feel free to contact us at info(a)composeconference.org. We're happy to work with you, even if you are a new or inexperienced speaker, to help your talk be great. * * * Diversity We would like to put an emphasis on soliciting a diverse set of speakers - anything you can do to distribute information about this CFP and encourage submissions from under-represented groups would be greatly appreciated. We welcome your contributions and encourage you to apply! Best, Gershom

1 0

reactive-banana project examples
by Michael Litchard 17 Nov '15

17 Nov '15

Could I get some pointers to projects using reactive-banana. I'm looking for projects that have code testing their Behaviors.

1 0

Re: [Haskell-cafe] turn off "thread blocked indefinitely in an STM transaction"?
by Johannes Waldmann 17 Nov '15

17 Nov '15

myThreadId >>= newStablePtr ; atomically retry Yes, that works. Thanks.

1 0

Re: [Haskell-cafe] turn off "thread blocked indefinitely in an STM transaction"?
by Johannes Waldmann 17 Nov '15

17 Nov '15

Ah, neat. I get the idea. But does it work here? import Control.Concurrent.STM import Foreign.StablePtr main = atomically retry >>= newStablePtr ghc -threaded -rtsopts -O2 sp.hs ./sp +RTS -N sp: thread blocked indefinitely in an STM transaction - J.

2 1

turn off "thread blocked indefinitely in an STM transaction"?
by Johannes Waldmann 17 Nov '15

17 Nov '15

I find the following mildly annoying: Prelude> import Control.Concurrent.STM Prelude Control.Concurrent.STM> atomically retry *** Exception: thread blocked indefinitely in an STM transaction Is there a way to not raise this exception, and block the thread? I don't see this behaviour (raising the exception) mentioned in the API docs nor in the defining paper (Composable memory transactions, PPoPP'05) that is referenced there. I understand it might come in handy for debugging, but sometimes (e.g., for teaching) I might really want a transaction that never commits. For instance, I am forkIO'ing some worker threads and the main program really should do absolutely nothing. So I thought I could just block the main thread. I can make some work-around with forM [1..n] $ \ p -> ( if p < n then void . forkIO else id ) $ forever $ do but that feels clumsy (since asymmetric). - J.W.

2 1

the last mile in haskell performance
by Alberto G. Corona 17 Nov '15

17 Nov '15

Looking at this: https://downloads.haskell.org/~ghc/6.12.3/docs/html/users_guide/primitives.… It seems that it is impossible to manage data in Haskell within a core without L1 cache faults. Except for unboxed arrays of primitive types. Since it is impossible to have unboxed arrays of user-defined types. Am I right? This is definitively very bad for tasks that are inherently single threaded and in general for the image of Haskell as a practical language. I have more to say about that, but I would like to know first if I´m right and second If there is some idea to going on to permit user defined boxed datatypes. Or if there is some low level trick for having it using foreign call and unsafeCoerce in some way, I know that the language ATS has unboxing a la carte.... -- Alberto.

9 14