August 2011 - Haskell-Cafe

ML Workshop: register early by August 15
by Chung-chieh Shan 13 Aug '11

13 Aug '11

ACM SIGPLAN Workshop on ML Sunday, 18 September 2011, Tokyo, Japan (co-located with ICFP) http://conway.rutgers.edu/ml2011/ CALL FOR PARTICIPATION * Early Registration deadline is August 15! * The ML family of programming languages includes dialects known as Standard ML, Objective Caml, and F#. These languages have inspired a large amount of computer-science research, both practical and theoretical. This workshop aims to provide a forum for discussion and research on ML and related technology (higher-order, typed, or strict languages). The format of ML 2011 will continue the return in 2010 to a more informal model: a workshop with presentations selected from submitted abstracts. Presenters will be invited to submit working notes, source code, and extended papers for distribution to the attendees, but the workshop will not publish proceedings, so any contributions may be submitted for publication elsewhere. We hope that this format will encourage the presentation of exciting (if unpolished) research and deliver a lively workshop atmosphere. INVITED SPEAKERS Naoki Kobayashi (Tohoku University) Atsushi Ohori (Tohoku University) ACCEPTED TALKS Efficiently scrapping boilerplate code in OCaml Dmitri Boulytchev, Sergey Mechtaev Implementing implicit self-adjusting computation (short talk) Yan Chen, Joshua Dunfield, Matthew A. Hammer, Umut A. Acar Lightweight typed customizable unmarshaling Pascal Cuoq, Damien Doligez, Julien Signoles Adding GADTs to OCaml: the direct approach Jacques Garrigue, Jacques Le Normand A demo of Coco: a compiler of monadic coercions in ML (short talk) Nataliya Guts, Michael Hicks, Nikhil Swamy, Daan Leijen Verifying liveness properties of ML programs M. M. Lester, R. P. Neatherway, C.-H. L. Ong, S. J. Ramsay MixML remixed Andreas Rossberg, Derek Dreyer Report on OCaml type debugger Kanae Tsushima, Kenichi Asai Camomile: a Unicode library for OCaml (short talk) Yoriyuki Yamagata PROGRAM COMMITTEE Amal Ahmed (Indiana University) Andrew Tolmach (Portland State University) Anil Madhavapeddy (University of Cambridge) Chung-chieh Shan (chair) Joshua Dunfield (Max Planck Institute for Software Systems) Julia Lawall (University of Copenhagen) Keisuke Nakano (University of Electro-Communications) Martin Elsman (SimCorp) Walid Taha (Halmstad University) STEERING COMMITTEE Eijiro Sumii (chair) (Tohoku University) Andreas Rossberg (Google) Jacques Garrigue (Nagoya University) Matthew Fluet (Rochester Institute of Technology) Robert Harper (Carnegie Mellon University) Yaron Minsky (Jane Street)

1 0

logic and types
by Patrick Browne 13 Aug '11

13 Aug '11

Hi, Below are some questions about the logical interpretation of types and type classes. Thanks, Pat module J where type Id = String type Position = Integer data Person = Person Id Position deriving Show -- Is this an axiom at type level? class Pos a where getPos :: a -> Position -- The :type command says -- forall a. (Pos a) => a -> Position -- How do I write this in logic? (e.g. implies, and, or, etc) -- What exactly is being asserted about the type variable and/or about the class? -- I am not sure of the respective roles of => and -> in a logical context -- Is the following a fact at type level, class level or both? instance Pos Person where getPos (Person i p) = p -- Is it the evaluation or the type checking that provides a proof of type correctness? -- getPos(Person "1" 2) This message has been scanned for content and viruses by the DIT Information Services E-Mail Scanning Service, and is believed to be clean. http://www.dit.ie

6 8

Re: [Haskell-cafe] library on common sub-expression elimination?
by oleg＠okmij.org 13 Aug '11

13 Aug '11

I guess you mean the function that converts an abstract syntax tree to a directed acyclic graph (DAG). Just for completeness I should mention that if the object language has effects including non-termination, one has to be careful eliminating seemingly common expressions. For example, in \a i -> if i >= 0 then a ! i else if i > 0 then a ! i + a ! (i-1) else .... we see the expression (a ! i) repeated in both branches of the conditional. Eliminating the `duplicate' by pulling it out \a i -> let t = a ! i in if i >= 0 then t else if i > 0 then t + a ! (i-1) else .... would be wrong, wouldn't it? This issue has been extensively investigated in the Fortran compiler community; Elliott, Finne and de Moor's ``Compiling Embedded Languages'' (JFP 2003) talks about it at length. The standard technique to detect occurrences of common subexpressions is so-called hash-consing. There are (OCaml) libraries for it: author = {Jean-Christophe Filli{\^a}tre and Sylvain Conchon}, title = {Type-Safe Modular Hash-Consing}, pages = {12--19}, crossref = "ml2006", doi = "10.1145/1159876.1159880", The upcoming distilled tutorial at DSL 2011 http://dsl2011.bordeaux.inria.fr/index.php?option=com_content&view=article&… will present a Haskell library for hash-consing. The library can work with the standard Haskell Hash-tables or without them (using Data.Map, for example). The library does _not_ rely on Stable names and other internal GHC operations with unstable semantics. The library will find all common sub-expressions. Incidentally, despite the Lisp-sounding name, hash-consing was invented before Lisp. It was described, for the English audience, in the first volume of Comm. ACM, in 1958: @Article{ Ershov-hash-consing, author = {A. P. Ershov}, title = {On programming of arithmetic operations}, journal = "Communications of the {ACM}", year = 1958, volume = 1, number = 8, pages = {3--6}, doi ="10.1145/368892.368907", url = "http://portal.acm.org/citation.cfm?id=368907" } The translation is quite accurate, as far as I could see, but misses the flowcharts and the diagram of the original paper. This short paper fully describes what we now call hash tables, hash functions, useful properties of hash functions, and hash-consing. The article analyzes the time complexity of the algorithm. Since the algorithm has two exits, writing programs in the continuation-passing style must have been familiar back then. The library to be presented at DSL 2011 unwittingly follows Ershov's algorithm closely. The library is (hopefully) better described (see the preface to the English translation of Ershov's paper). Nowadays, starting a paper with the phrase ``All unexplained terms are those from [1]'' (where [1] is the single reference) would not be taken kindly by reviewers.

4 3

fyi GHC 7.2.1 release on the benchmarks game
by Isaac Gouy 12 Aug '11

12 Aug '11

1) Some of the GHC programs contributed to the benchmarks game have problems with recent GHC releases - meteor-contest #5 - Ambiguous occurrence `permutations' http://shootout.alioth.debian.org/u64q/program.php?test=meteor&lang=ghc&id=… - regex-dna #2 - Precedence parsing error http://shootout.alioth.debian.org/u64q/program.php?test=regexdna&lang=ghc&i… - reverse-complement #2 - parse error on input `->' http://shootout.alioth.debian.org/u64q/program.php?test=revcomp&lang=ghc&id… - reverse-complement #3 - Could not find module `Monad' http://shootout.alioth.debian.org/u64q/program.php?test=revcomp&lang=ghc&id… 2) I noticed `-fvia-C` has now gone away and there were half-a-dozen programs that had been written to use `-fvia-C` so how might that effect performance of those programs?

4 4

Distributions link on Hackage
by Peter Simons 12 Aug '11

12 Aug '11

Hi, the home page of a package on Hackage links to various distributions to show which versions are available, i.e. Fedora, Debian, FreeBSD, etc. In NixOS, we have fairly up-to-date package set, and I would like to see that distribution included on Hackage. Now I wonder how to get that done? Can anyone advice on the procedure to add support for a distribution to Hackage? Take care, Peter

2 1

Potential problem with AC-Vector-Fancy package
by Dave Tapley 12 Aug '11

12 Aug '11

Is anyone maintaining the AC-Vector-Fancy package? I haven't had a reply from the latest maintainer (Andrew Coppin) on Hackage, so I thought I'd open it up to cafe: I think I have found a problem with the union function: If you look here: http://hpaste.org/49889 You will see that line 4 gives a different result to lines 6, 8, 10; this shouldn't be the case because union is commutative.

3 3

Building ? using kleene closure {not haskell specific}
by C K Kashyap 12 Aug '11

12 Aug '11

Hello gentle Haskell folks, I happened to read "Beautiful code"'s chapter 1 today and found Brian Kerninghan's regex implementation. In it he only shows the * meta character. I can easily understand how + can be built but am having trouble with building ? (zero or one). I'd really appreciate it if some one could help me understand it. Regards, Kashyap

3 3

Help understanding Haskell runtime costs
by Thiago Negri 11 Aug '11

11 Aug '11

Hello all, I'm relatively new to Haskell and trying to solve some online judge's problems in it. One of the problems is to say if a given sentence is a tautogram or not. A tautogram is just a sentence with all the words starting with the same letter. My first try (solution is ok) was to do it as haskeller as possible, trying to overcome my imperative mind. But it did bad at performance (0.30 secs of runtime, 4.6 mb of memory): -- code start import Data.Char (toLower) main = getContents >>= mapM_ (putStrLn . toStr . isTautogram . words) . takeWhile (/= "*") . lines toStr :: Bool -> [Char] toStr True = "Y" toStr False = "N" isTautogram :: [[Char]] -> Bool isTautogram (x:[]) = True isTautogram (x:xs) = all ((== firstChar) . toLower . head) xs where firstChar = toLower . head $ x -- code end I tried to profile the code, but didn't find anything useful. My bet is that all this "words . lines" is consuming more memory than necessary, maybe saving space for the lines already processed. Then I tried a some-what tail-call function, consuming one line at each iteration: -- code start import Data.Char (toLower) main :: IO () main = getLine >>= mainLoop mainLoop :: [Char] -> IO () mainLoop s | (head s) == '*' = return () | otherwise = (putStrLn . toStr . isTautogram . words $ s) >> main toStr :: Bool -> [Char] toStr True = "Y" toStr False = "N" isTautogram :: [[Char]] -> Bool isTautogram (x:[]) = True isTautogram (x:xs) = all ((== firstChar) . toLower . head) xs where firstChar = toLower . head $ x -- code end Note that the only thing that changed between the two tries was the main-loop. The second version runs faster (got 0.11 secs) and with less memory (3.6 mb) Can someone explain to me what is really going on? Maybe pointing out how I can achieve these optimizations using profiling information... Thanks, Thiago.

2 2

Trouble with readProcess
by Charles-Pierre Astolfi 11 Aug '11

11 Aug '11

Hi -cafe, I'm using readProcess and I don't know how to handle this issue: readProcess cmd [opt1,opt2] seems to execute the following: $ cmd "opt1" "opt2" That is usually fine, but I'm using an external program that doesn't understand the quotes, so I need to execute instead: $ cmd opt1 opt2 How should I do that? -- Cp

4 5

ANNOUNCE: Chell: A quiet test runner (low-output alternative to test-framework)
by John Millikin 11 Aug '11

11 Aug '11

Homepage: https://john-millikin.com/software/chell/ Hackage: http://hackage.haskell.org/package/chell -------- This is just a quick package I whipped up out of frustration with test-framework scrolling an error message out of sight, for the millionth time. Chell has the same general purpose (aggregate your assertions + properties + whatever into a single executable), but only prints when a test fails or aborts. It also has a small built-in test library, similar to HUnit, so you don't need to depend on 2-3 separate libraries if you're just doing simple tests. Cool features thereof: * it reports the line number of failed assertions * you can use $expect instead of $assert, so even if it fails, the test keeps going (all the failures are printed at the end) * you can add "notes" to a test, which are saved in logs and reports. you can put in any sort of metadata you want (nice for figuring out why a test is failing) * assertions for text diffs, so if you're testing two big chunks of text for equality you don't have to copy+paste to see what's different.

2 3