November 2010 - Haskell-Cafe

GHC 7.0.1 developer challenges
by John D. Ramsdell 24 Dec '10

24 Dec '10

A quick review of GHC 7.0.1 revealed two challenges for developers. I downloaded the GHC 7.0.1 sources, configured for a home directory install, and built and installed the compiler. Very close to the end, my machine froze, perhaps due to memory exhaustion. In any event, a reboot allowed me to complete the installation. I tested the new compiler on an application I distribute, CPSA. The algorithm implemented by the program is not guaranteed to terminate, and it's hard to predict when non-termination is inevitable. Sometimes the way it terminates is to allocate all the memory in swap space and freeze the machine. It's an ugly crash. So in my documentation, I recommend people supply a runtime flag limiting memory usage. Due to a security concern, GHC 7.0.1 disables all runtime flags unless a new flag is provided during linking. Since limiting memory usage is so important, many developers will modify their cabal files to add the linker flag or prepare for complaints from users that the developer's program caused their machine to freeze and lose their work. The irony of this situation is deep. CPSA is a program that analyzes cryptographic protocols in an effort to expose security flaws. To ensure that the program does not crash a user's machine, I have to use a linker option that may expose the user to some security problems. There is one more disappointment in GHC 7.0.1 for developers. Cabal sdist is still hosed. Since ten months ago, cabal sdist fails to preserve the file mode bits of the source files put into the tarball being generated (Ticket #627 reported by draconx). An executable shell script and a source file world readable both have a mode of 600 in the tarball! So developers, continue to keep GHC 6.10.4 around so you can create source distributions. That's what I do. John

19 44

type class design
by Uwe Schmidt 21 Dec '10

21 Dec '10

Dear Haskellers, I've a question about type class design. When developing the set of functions for a class, there are often two or more functions, let's say f and g, where the semantics of g can be expressed by f. When writing down the code, there are two choices for g. First g is included in the type class, second g is defined outside and the signature has a context referencing the class. 1. case class Foo a where f :: ... a ... g :: ... a ... g = expr[f] 2. case class Foo a where f :: ... a ... g :: Foo a => ... a ... g = expr[f] What are the reasons for choosing 1., what are the arguments for 2.? My arguments for 1.: a) Efficiency: g may be overwritten in an instance declaration by a more efficient piece of code. b) Readability: All functions, which are logically connected are grouped together in a single syntactic construct and can be found in one place (similar to an interface in Java). My argument for 2.: c) Correctness: The semantics for g are fix (relative to f), All laws for g hold everywhere, assuming f is implemented correctly. I've sometimes the problem to balance the reasons for 1. and 2 and I doubt, that this list of criteria is complete. In the standard Haskell classes we can find both cases, even within a single class. Eq with (==) as f and (/=) as g belongs to the 1. case, so does Monad and (>>=) as f and (>>) as g. But (>=>) and the Monad class fall into the 2. case. It seem, there is no uniform or consistent strategy in the core Haskell classes. What are your best practice rules for this problem? Expecting your advices, Uwe

6 8

Where are all the Taiwanese Haskellers?
by Pasqualino "Titto" Assini 21 Dec '10

21 Dec '10

Hello, I am going to Taiwan with my family for about five weeks (I am Italian, my wife is Taiwanese and we have two kids) and I wondered if there was any Taiwanese Haskeller that would be interested in meeting for a chat about Haskell, Life and Everything else, maybe in front of a nice cup of 高山茶. We arrive in Taiwan on the 4th of December, spend a few days nearby Taipei and then down to Pu-Li and Kaoshong, where we will spend about 4 weeks and then probably back to Taipei for a few more days around the 10 of January. I am afraid that my Chinese is almost non-existent (yes I know, that's so stupid of me) so the conversation will have to be in English (Italian or French would be fine as well :-)). All the very best, titto -- Dr. Pasqualino "Titto" Assini http://quid2.org/

2 1

non-hackage cabal repos? unpacking non-repo package tarballs?
by Claus Reinke 20 Dec '10

20 Dec '10

I often find myself writing example code that I'd like to distribute via cabal, but without further burdening hackage with not generally useful packages. 1. The simplest approach would be if cabal could expose its internal 'unpackPackage' as a command, so that author: cabal sdist user: cabal unpackPackage Example.tar.gz would work (the point being that cabal handles .tar.gz, which not all users have installed separately; distributing the .tar.gz would be handled via the usual channels; and after unpacking, cabal can build the source package). Note that 'cabal unpack' does not seem helpful here, as it touches the package index instead of just looking at the tarball. Could this be made possible, please? Or is it already? 2. Failing that, I remembered that cabal used to be designed without a fixed package repo address, and a little digging found options --remote-repo and --local-repo, as well as the directory layout for package repositories: http://hackage.haskell.org/trac/hackage/wiki/HackageDB So this scenario seems possible, in principle: author: expose a package repo http://myrepo user: cabal --remote-repo=http://myrepo fetch Example Is it possible to add a (temporary) repo location like this, especially for 'cabal fetch'/'cabal unpack'? I've managed to get 'cabal --local-repo=myrepo list Example' to work (needs uncompressed 00-index.tar), but not the remote variant, and fetching from the local repo doesn't work, either. Are there any usage examples of these features? Claus

3 2

Is there a tutorial interpreter to teach haskell?
by Larry Evans 20 Dec '10

20 Dec '10

By tutorial interpreter, I means something like an expert system having a list of rules and than a problem which is solved by using those list of rules. The tutorial means the trace of the "problem state" before and after each rule is applied along with which parts of the rule are matched with which part of the "problem state". W.R.T. haskell, the "problem state" would be a haskell expression and each "rule application" would be simply reducing the haskell expression (using some rule, which would be cited during the reduction) to a simpler form until the final answer was achieved. Obviously the rule applications to be trace should be user selectable to avoid way too much output, but that seems similar to setting breakpoints in selected functions; hence, I guess it wouldn't be hard to do. The attached file illustrates what I'm after. I laboriously composed that attached to enable me to understand what the haskell code was doing. It would help other novices if such a trace could be automated. I'm currently trying to understand: sequence (c:cs) = return (:) `ap` c `ap` sequence cs from p. 2 of: http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf and again I'm having a lot of difficulty what the code is doing. So far I've got: --{--eshell-- Prelude Monad> :t ap ap :: (Monad m) => m (a -> b) -> m a -> m b Prelude Monad> :t return (:) return (:) :: (Monad m) => m (a -> [a] -> [a]) Prelude Monad> (:) 'a' "bc" "abc" Prelude Monad> :t return (:) `ap` "a" return (:) `ap` "a" :: [[Char] -> [Char]] --}--eshell-- so now I must "manually" figure out what the a and b in the ap declaration correspond to in the return(:) type: m ( a -> b ) __ _ _ 1: [] Char -> [Char]->[Char] 2: [] Char->[Char] -> [Char] IOW, is it choice 1: in the above table for choice 2:? I'd guess, since application associates to the left, that it's choice 1:. But you see, I'm not sure, and I have to work too hard to figure it all out. I *may* get it eventually, but it's a *lot* of work. I tutorial interpreter would make this so much easier! -regards, Larry

3 3

Printing of asynchronous exceptions to stderr
by Mitar 16 Dec '10

16 Dec '10

Hi! I have been spend some time to debug this in my program. ;-) Why is ThreadKilled not displayed by RTS when send to thread (and unhandled), but any other exception is? For example, I am using custom exceptions to signal different kinds of thread killing. Based on those my threads cleanup in different ways. But after they cleanup they keep "running". Not really running as their computations were interrupted. But simply hanging there. And if then new custom exception arrives it is not handled anymore (as it is after my normal exception handlers already cleaned everything) and it is printed to stderr. Now I added "`finally` throwIO ThreadKilled" at the end of my cleanup computations to really kill the thread. So that possible later exceptions are not delivered anymore. Why it is not so that after all computations in a thread finish, thread is not killed/disposed of? Because it can be reused by some other computation? But then my exceptions could be delivered to wrong (new) thread while they were meant for old one? Mitar

5 21

Conditional compilation for different versions of GHC?
by Jinjing Wang 13 Dec '10

13 Dec '10

Dear list, >From ghc 7.0.1 release notes: > The Language.Haskell.TH.Quote.QuasiQuoter type has two new fields: quoteType and quoteDec. Some of my code needs to be conditionally compiled to support both version 6 and 7, what is the recommended way to do it? ref: * http://new-www.haskell.org/ghc/docs/7.0.1/html/users_guide/release-7-0-1.ht… -- jinjing

9 18

Bifold: a simultaneous foldr and foldl
by Noah Easterly 06 Dec '10

06 Dec '10

Somebody suggested I post this here if I wanted feedback. So I was thinking about the ReverseState monad I saw mentioned on r/haskell a couple days ago, and playing around with the concept of information flowing two directions when I came up with this function: bifold :: (l -> a -> r -> (r,l)) -> (l,r) -> [a] -> (r,l) bifold _ (l,r) [] = (r,l) bifold f (l,r) (a:as) = (ra,las) where (ras,las) = bifold f (la,r) as (ra,la) = f l a ras (I'm sure someone else has come up with this before, so I'll just say I discovered it, not invented it). Basically, it's a simultaneous left and right fold, passing one value from the start of the list toward the end, and one from the end toward the start. It lets you do some interesting stuff, like filter based on positionor other left-dependent information: evenIndexed :: [a] -> [a] evenIndexed = fst . bifold alternate (0,[]) where alternate 0 x xs = (x:xs, 1) alternate 1 _ xs = (xs, 0) maximums :: (Ord a) => [a] -> [a] maximums [] = [] maximums (a:as) = a : (fst $ bifold (\m a l -> if a > m then (a:l,a) else (l,m)) (a,[]) as) As long as you don't examine the left-to-right value, it can still work on infinite lists: ghci> take 20 $ evenIndexed [0..] [0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38] Also, it can be used for corecursive data (or, at least, doubly-linked lists): data DList a = Start { first :: DList a } | Entry { value :: a, next :: DList a, prev :: DList a } | End { last :: DList a } deriving (Eq) ofList :: [a] -> (DList a, DList a) ofList as = (start,end) where start = Start first end = End last (first,last) = bifold mkEntry (start,end) as mkEntry p v n = let e = Entry v n p in (e,e) It's just been running around my head all night, so I thought I'd share.

2 5

Safer common subexpression elimination
by Joachim Breitner 04 Dec '10

04 Dec '10

Hi, although semantically it could, ghc does not do common subexpression elimination (CSE), at least not in every case. The canonical example where it would be bad is the function (with div to avoid numerical casting): > avg :: [Int] -> Int > avg n = (sum [0..n] `div` length [0..n]) The reason why [0..n] is not shared is because then it would be kept in memory completely after the evaluation of sum, because length will still need it, possibly overflowing the memory. In the non-shared form, though, the garbage collector can clean up directly behind sum and length, and the program runs in constant space. Note that the shared expression would be very large compared to the thunks. Now consider the program: > avg' :: [Int] -> (Int, Int) > avg' n = (sum [0..n] `div` length [0..n], length [0..n]) I’d say that CSE to > avg n = (sum [0..n] `div` l, l) > where l = length [0..n] is safe, because the shared expression (an Int) is smaller than the thunks and the compiler can tell. So I wonder: * Is sharing values of type Int (and Bool and similar small values) always safe? * If so: does GHC already do that? * Would it be technically possible? * Is there an established theory that can tell, for a sharing candidate, whether it is safe to share it? Thanks, Joachim -- Joachim "nomeata" Breitner mail: mail(a)joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C JID: nomeata(a)joachim-breitner.de | http://www.joachim-breitner.de/ Debian Developer: nomeata(a)debian.org

4 5

Reduceron: reduced to numbers.
by Serguey Zefirov 04 Dec '10

04 Dec '10

I decided to calculate Reduceron's number of transistors (I had to, we have some argument here;). Reduceron allocate 14% of 17300 slices of Virtex-5 FPGA. If we assume that each slice correspond to 8 4-input NAND-NOT elements, we will get 20000 4-input NAND. Each 4-input NAND contains 8 transistors, so the count of logic transistors is about 160000. Reduceron use 90% of 1.5Kbyte RAM blocks. Using 6 transistors per RAM bit, we get 66K transistors more. So Reduceron should contain about 230K transistors if someone decides to go ASIC. It's 3 orders of magnitude less than x86, on par with most late chips of Chuck Moore (inventor of Forth, MISC concept and the one who develops some strange chips in GreenArrays http://greenarraychips.com/ now). The difference between Reduceron and GA144 of Chuck Moore is that Reduceron could be programmed much more easily, and that rocks. Clock frequency of 96MHz should go up too. My experience suggest numbers between 5 and 8 times. So single Reduceron should be of equal performance to Core2 Duo, at least. PS Of course, Reduceron in ASIC will require some cache memory, some controllers, etc. So it won't be that small, like 230K transistors. But, mzke it 2.3M transistors and it still be 2 orders of magnitude less than Core2 Duo... ;)

2 2