November 2010 - Haskell-Cafe

Reference for technique wanted
by Richard O'Keefe 05 Nov '10

05 Nov '10

There's a long-known technique in functional languages where [x1,...,xn] => \tail -> x1:...xn:tail xs ++ ys => f . g xs => f [] A correspondent mentioned to me that he couldn't find a reference to the idea (which I gather he had independently rediscovered). I know I've read about it somewhere. Can anyone provide a reference?

6 22

Are newtypes optimised and how much?
by Christopher Done 05 Nov '10

05 Nov '10

So I have the following nice things: {-# LANGUAGE GeneralizedNewtypeDeriving, OverloadedStrings #-} import Data.String newtype Foo = Foo { unFoo :: String } deriving (IsString) x :: Foo x = "Hello, World!" newtype Bar = Bar { unBar :: Integer } deriving (Eq,Show,Num,Integral,Real,Enum,Ord) y :: Bar y = 2 I can write literals and they will be converted to the type I wanted with no extra verbiage needed. Questions (I'm talking about GHC when I refer to compilation): (1) Are fromString and fromIntegral ran at compile time? I don't think that this is the case. I think they are just translated to fromString "Hello, World!" and fromIntegral 2 verbatim. (2) Regardless of this, the implementation of fromString and fromIntegral is essentially a no-op, it's just fromString = Foo, fromIntegral = Bar, which is in turn essentially fromString = id, fromIntegral = id, as far as I understand it. It's purely compile time. But supposing I write: fromIntegral (fromIntegral (2::Integer) :: Bar) :: Integer Is this at the end of the day equal to just (2::Integer)? Thinking simple-mindedly, I would say, yes. The compiler knows that fromIntegral :: Integer -> Bar == id, and that fromIntegral :: Bar -> Integer == id (right?). But is that the case? Perhaps the type class methods have some dictionary and thus cannot be inlined, or maybe that doesn't matter? At the end of the day what motivated me to ask these questions it that I like very much defining newtypes for most of the types I use, I have completely forgotten about `type' aliasing. I'm completely happy to write Foo and unFoo all over the place to aid my type correctness, but I want a nice generic way to convert to/from newtypes but keeping it a compile-time concept. Sometimes I have unThisThat, unTheOther, unThoseWhoShantBeNamed, etc. and it I could just use fromIntegral and fromString then that would be super. Also, is 'map unFoo' optimised away at compile-time, too? I think that it would be compiled to map id. So it would still wrap a thunk around each cons. How far does it go? So, if I go around using fromIntegral/fromString (etc. for other newtype types), is it still kept compile time? After having newtypes catch dozens of type mismatches that otherwise wouldn't unified happily but were completely wrong (e.g. wrong argument order), I've found newtype to be an indispensable part of Haskell and of writing a large piece of software. Cheers

8 14

SBLP 2011 - call for papers
by Simon Thompson 05 Nov '10

05 Nov '10

SBLP 2011: Call For Papers 15th Brazilian Symposium on Programming Languages Sao Paulo, Brazil September 26-30, 2010 http://www.each.usp.br/cbsoft2011/ IMPORTANT DATES Paper abstract submission (15 lines): April 22nd, 2011 Full paper submission: April 29th, 2011 Notification of acceptance: May 30th, 2011 Final papers due: July 29th, 2011 INVITED SPEAKERS Gary T. Leavens, Univ. of Central Florida Jose Luis Fiadeiro, Univ. of Leicester INTRODUCTION The 15th Brazilian Symposium on Programming Languages, SBLP 2011, will be held in Sao Paulo, Brazil, between September 26th and 30th, 2011. SBLP provides a venue for researchers and practitioners interested in the fundamental principles and innovations in the design and implementation of programming languages and systems. The symposium will be part of the 2nd Brazilian Conference on Software: Theory and Practice, CBSoft 2011, http://www.each.usp.br/cbsoft2011/, which will host four well-established Brazilian symposia: * XXV Brazilian Symposium on Software Engineering (SBES) * XV Brazilian Symposium on Programming Languages (SBLP) * XIV Brazilian Symposium on Formal Methods (SBMF) * V Brazilian Symposium on Components, Software Architecture and Software Reuse (SBCARS) SBLP 2011 invites authors to contribute with technical papers related (but not limited) to: * Program generation and transformation, including domain-specific languages and model-driven development in the context of programming languages. * Programming paradigms and styles, including functional, object-oriented, aspect-oriented, scripting languages, real-time, service-oriented, multithreaded, parallel, and distributed programming. * Formal semantics and theoretical foundations, including denotational, operational, algebraic and categorical approaches. * Program analysis and verification, including type systems, static analysis and abstract interpretation. * Programming language design and implementation, including new programming models, programming language environments, compilation and interpretation techniques. SUBMISSIONS Submissions should be done using SBLP 2011 installation of the EasyChair conference management system at http://www.easychair.org/conferences/?conf=sblp2011. Contributions should be written in Portuguese or English. We solicit papers that should fall into one of two different categories: full papers, with at most 15 pages, or short papers, with at most 5 pages. All papers should be prepared using the Easychair template. (http://www.easychair.org/easychair.zip) In particular, we encourage the submission of short papers reporting on master dissertations or doctoral theses at early stages of their development. All accepted papers will be published in the conference proceedings. As in previous editions, a journal special issue, with selected papers from accepted contributions, is anticipated. From 2003 to 2008 there were special issues of the Journal of Universal Computer Science, published by Springer, with the post-proceedings of SBLP. The post-proceedings of SBLP 2009 and 2010 are being edited as special issues of Science of Computer Programming, published by Elsevier. GENERAL CO-CHAIRS Denise Stringhini FCI, Mackenzie Alfredo Goldman IME, USP PROGRAMME CHAIRS Christiano Braga, UFF Jose Luiz Fiadeiro, Univ. of Leicester PROGRAMME COMMITTEE * Alberto Pardo, Univ. de La Republica * Alex Garcia, IME * Alvaro Freitas Moreira, UFRGS (TBC) * Andre Santos, UFPE * Artur Boronat, Univ. of Leicester * Carlos Camarao, UFMG * Christiano Braga, UFF (co-chair) * Edward Hermann Haeusler, PUC-Rio (TBC) * Fernando Castor Filho, UFPE * Fernando Pereira, UFMG * Francisco Heron de Carvalho Junior, UFC (TBC) * Giuseppe Castagna, Paris 7 (TBC) * Jens Palsberg, UCLA * Joao Saraiva, Universidade do Minho * Johan Jeuring, Utrecht Univ. * Jonathan Aldrich, Carnegie Mellon Univ. * Jose Luiz Fiadeiro, Univ. of Leicester (co-chair) * Lucilia Figueiredo, UFOP * Luis Soares Barbosa, Univ. do Minho * Marcelo A. Maia, UFU * Marcelo d'Amorim, UFPE * Marco Tulio Valente, UFMG * Mariza A. S. Bigonha, UFMG * Martin A. Musicante, UFRN * Noemi Rodriguez, PUC-Rio * Paulo Borba, UFPE (TBC) * Peter Mosses, Swansea University * Renato Cerqueira, PUC-Rio * Ricardo Massa, UFPE * Roberto S. Bigonha, UFMG (TBC) * Roberto Ierusalimschy, PUC-Rio * Sandro Rigo, UNICAMP * Sergio Soares, UFPE (TBC) * Sergiu Dascalu, Univ. of Nevada * Simon Thompson, Univ. of Kent * Sophia Drossopoulou, Imperial College (TBC) * Varmo Vene, Univ. de Tartu (TBC) * Vladimir Di Iorio, UFV (TBC)

1 0

Is Curry alive?
by Gregory Crosswhite 05 Nov '10

05 Nov '10

Hey everyone, This is a little off-topic, but I just ran into a problem which might benefit from being attacked by a logic language, so I've been looking for a good one to try out --- and hopefully one that has a very efficient implementation since I want to iterate through billions and possibly trillions of nondeterministically generated solutions. I was thinking about using Curry, but it looks to me like the language is dead and hasn't seen much activity for a few years. Does anyone know about whether there is still much going on over there? Or, alternatively, do you have any suggestions regarding other logic language/implementations I should check out? I've also been looking at Prolog but I am having trouble seeing whether I can process N non-deterministic solutions in O(1) space (rather than first generating a O(N) size list), and I checked out Mercury but the documentation for it is a bit sparse. Thanks! Greg

6 12

Type inference algorithm in Prolog and Haskell
by oleg＠okmij.org 05 Nov '10

05 Nov '10

Dan Doel wrote: > Implementing type inference can be very easy in a logic language, > because most of the work in a non-logic language is implementing > unification: > http://muaddibspace.blogspot.com/2008/01/type-inference-for-simply-typed-la… Correctly implementing type inference in Prolog is much more complicated. The cited code is elegant, but it is not correct. Here's the code without Unicode embellishments: GNU Prolog 1.3.0 By Daniel Diaz Copyright (C) 1999-2007 Daniel Diaz | ?- [user]. compiling user for byte code... :- op(150, xfx, --). :- op(140, xfx, :). :- op(100, xfy, ->). :- op(100, yfx, $). Gamma -- Term : Type :- atom(Term), member(Term : Type, Gamma). Gamma -- lam(A, B) : Alpha -> Beta :- [A : Alpha|Gamma] -- B : Beta. Gamma -- A $ B : Beta :- Gamma -- A : Alpha -> Beta, Gamma -- B : Alpha. user compiled, 9 lines read - 1801 bytes written, 8746 ms % We define a boolean and an integer constants -- only to make the examples % smaller. ?- G0 = [i1:int, b1: bool], E = lam(f, lam(x, f $ (x $ i1))), G0 -- E : T. E = lam(f,lam(x,f$(x$i1))) G0 = [i1:int,b1:bool] T = (A->B)->(int->A)->B % so far, so good. ?- G0 = [i1:int, b1: bool], E = lam(f, lam(x, f $ (x $ i1) $ (x $ b1))), G0 -- E : T. no % Still good: we can't apply x both to a boolean and an integer. ?- G0 = [i1:int, b1: bool], E = lam(f, lam(x, lam(x, f $ (x $ i1) $ (x $ b1)))), G0 -- E : T. E = lam(f,lam(x,lam(x,f$(x$i1)$(x$b1)))) G0 = [i1:int,b1:bool] T = (A->B->C)->(bool->B)->(int->A)->C ? % What happened? How come we embedded an untypable term in a larger % term, and it type-checked? % Look at the type: why the first x has the type bool->B? % Because two occurrences of x in the body of the term are % different identifiers, one inner and one outer. % The type checker does not understand lexical scoping! % That is not Lambda-calculus! % It gets worse: | ?- E = lam(f, lam(x, (f $ (x $ lam(z,z))) $ (x $ (lam(u,lam(v,u)))))), [] -- E : T. % lopes forever, has to be aborted. ?- E = lam(x, x $ x), [] -- E : T. Illegal instruction: 4 Finally we've got a segmentation fault. I submit that a type-checker that accepts ill-typed terms, loops and causes segmentation faults is not correct. The member() predicate is (one of the) culprits. In a real type-checker, if we find the binding x:t in Gamma and we fail to type-check, we should not look for another binding in Gamma. We have to fail. But that is not how member works: it selects one element from the list; if it is not good, it selects another. It is also tempting to use Prolog variables for lambda-bound variables. That brings another can of worms: generally speaking, we need disequality constraints. Prolog sure makes some things easier, but some things quite more complicated. Implementing type inference for simply-typed lambda-calculus in Haskell is not that complex: http://okmij.org/ftp/Computation/FLOLAC/TInfT.hs However, we don't even have to do that. Haskell itself can do that for us: http://okmij.org/ftp/tagless-final/course/TTF.hs It boils out to three lines: class Symantics repr where lam :: (repr a -> repr b) -> repr (a->b) app :: repr (a->b) -> repr a -> repr b That is it: the type system of simply-typed lambda-calculus (which we can read as the implication fragment of minimal logic). Two rules, implication introduction and elimination, is all it takes. Now, when we try to typecheck the problematic term *TTF> lam (\x -> app x x) <interactive>:1:17: Occurs check: cannot construct the infinite type: a = a -> b Expected type: repr a Inferred type: repr (a -> b) In the second argument of `app', namely `x' In the expression: app x x we actually get a type error -- with a good error message -- rather than a segmentation fault.

1 0

Re: HSCurses - Hello World? (can't find much documentation)
by Michael Forster 05 Nov '10

05 Nov '10

On Fri, Oct 22, 2010 at 17:09:52 EDT, Ari Rahikkala wrote: > On Fri, Oct 22, 2010 at 11:18 PM, Anonymous Void <byteasphyxia at gmail.com> wrote: > > But since I've never seen how the HSCurses functions really integrate > > together, or any tutorials/examples (besides hsFishEx), > > I fear toying with it is going to be annoying until I figure it out on my > > own, especially since I'm already doing a project for someone... > > So, I was wondering if anyone would be kind enough to point me to (or write > > me) a basic example of how HSCurses works, > > maybe w/ some very simple example of interactivity (e.g. getch processing, > > screen refresh, ..) support. > > Also, maybe warn me of some of the common pitfalls and differences in > > hscurses vs ncurses in other languages. > > UI.HSCurses.Curses follows ncurses quite closely so you can get pretty > far reading the NCurses Programming HOWTO: > http://tldp.org/HOWTO/NCURSES-Programming-HOWTO/ Also, http://invisible-island.net/ncurses/ncurses-intro.html. And below is a hscurses version of the first example from that document. Cheers, Mike module Main where import Control.Exception (bracket_) import qualified UI.HSCurses.Curses as Curses import qualified UI.HSCurses.CursesHelper as CursesH start = do Curses.initScr Curses.keypad Curses.stdScr True Curses.nl False Curses.cBreak True Curses.echo True hasColors <- Curses.hasColors if hasColors then do Curses.startColor Curses.initPair (Curses.Pair 1) (CursesH.black) (CursesH.black) Curses.initPair (Curses.Pair 2) (CursesH.green) (CursesH.black) Curses.initPair (Curses.Pair 3) (CursesH.red) (CursesH.black) Curses.initPair (Curses.Pair 4) (CursesH.cyan) (CursesH.black) Curses.initPair (Curses.Pair 5) (CursesH.white) (CursesH.black) Curses.initPair (Curses.Pair 6) (CursesH.magenta) (CursesH.black) Curses.initPair (Curses.Pair 7) (CursesH.blue) (CursesH.black) Curses.initPair (Curses.Pair 8) (CursesH.yellow) (CursesH.black) return () else return () Curses.wclear Curses.stdScr return () loop num = do c <- Curses.getch Curses.attrSet Curses.attr0 (Curses.Pair (mod num 8)) Curses.refresh if Curses.decodeKey c == Curses.KeyChar 'q' then return() else loop (num + 1) end = do Curses.endWin return () main = do bracket_ start end (loop 0)

2 1

ANNOUNCE: coroutine-enumerator
by Mario Blažević 04 Nov '10

04 Nov '10

The newly released coroutine-enumerator package can be used as a bridge between the enumerator and monad-coroutine packages. It provides two-way conversion functions between an Iteratee and an Await-suspending coroutine, and also between an Enumerator and a Yield-suspending coroutine. As a little example, the following program combines the http-enumerator, monad-coroutine, and SCC packages using the coroutine-enumerator package to print out all lines from the Hackage database containing substring "enumerator": > import Control.Exception.Base (SomeException) > import Control.Monad.Trans.Class (lift) > > import Data.ByteString (ByteString) > import Data.Text.Encoding (decodeUtf8) > > import Network.HTTP.Enumerator > > import Control.Monad.Coroutine > import Control.Monad.Coroutine.SuspensionFunctors > import Control.Monad.Coroutine.Nested > import Control.Monad.Coroutine.Enumerator > > import Control.Concurrent.SCC.Sequential > > main = httpRedirect (\_ _-> coroutineIteratee consumer) =<< parseUrl address > > address = "http://hackage.haskell.org/packages/archive/pkg-list.html" > > consumer :: Coroutine (Await [ByteString]) IO (Either SomeException ((), [ByteString])) > consumer = pipe translator (consume worker) >> return (Right ((), [])) > > translator :: Functor f => Sink IO (EitherFunctor (Await [a]) f) a -> Coroutine (EitherFunctor (Await [a]) f) IO () > translator sink = do chunks <- liftParent await > if null chunks > then lift (putStrLn "END") > else putList chunks sink >> translator sink > > worker :: Consumer IO ByteString () > worker = toChars >-> foreach (line `having` substring "enumerator") > (append (fromList "\n") >-> toStdOut) > suppress > > toChars :: Monad m => Transducer m ByteString Char > toChars = oneToOneTransducer decodeUtf8 >-> coerce Alternatively, the worker coroutine can parse the XML database and print out all elements whose any attribute value contains the substring "enumerator": > worker = toChars > >-> parseXMLTokens > >-> foreach (xmlElementHavingTagWith (xmlAttributeValue `having` substring "enumerator") > `nestedIn` xmlElementContent) > (coerce >-> toStdOut) > suppress

1 0

ANNOUNCE: version 0.6 of monad-coroutine and SCC
by Mario Blažević 04 Nov '10

04 Nov '10

Packages monad-coroutine and SCC have been upgraded to version 0.6 on Hackage. The monad-coroutine package exports a generic monad transformer Coroutine: Functor s => MonadTrans (Coroutine s). A Coroutine-transformed monad can suspend at any point, returning its resumption wrapped in the functor s. There are also some functions for manipulating and running coroutines, as well as a couple of useful suspension functors such as Yield and Await. Version 0.6 of monad-coroutine makes running pairs of coroutines simpler by adding several predefined resolvers. The new version of Streaming Component Combinators (a.k.a. SCC) is mostly about performance enhancements. The coroutines now communicate through chunks of data rather than individual items, which reduces the coroutine switching overhead. The module hierarchy has been reorganized for easier use, but the exported type and function names have mostly remained the same. Both packages have been tested with GHC 6.12.3 and 7.0.

1 0

Concurrency and ghc 6.12.3
by Ketil Malde 04 Nov '10

04 Nov '10

Hi, On experimenting with concurrency, I got somewhat surprising result. I have a program ('flower') that reads an input file and generates one or more output files. As the different output files are independent, I construct one IO action for each output requested on the command line, and just forkIO one thread for each. This seems to work fairly well on one CPU, so I decided to try on multiple CPUs, using +RTS -N. To my surprise, this made the program take several times longer (wall clock). So I tried -N2 and -N4 to see how that turned out. Results are, in minutes: format def -N2 -N4 -N i 0 0 0 0 q 2 2 2 13 f 2 5 1 14 h 8 10 2 27 s 26 17 11 - T 37 23 16 - F 47 38 42 - CPU 2543u 3027u (lost) - 36s 593s 92% 161% I had to terminate -N after five hours wall time and 158026.68s user 60682.76s system 1210% CPU. So, well, it seems this scales okay as long as there are enough threads, but scales *horribly* when you run more threads than processes. Is this a correct assessment? Would it make sense to simply cap -N to the number of forked threads? I guess I should try this with GHC7, but is there reason to believe it will perform better? -k -- If I haven't seen further, it is by standing in the footprints of giants

2 1

Is "let" special?
by Günther Schmidt 04 Nov '10

04 Nov '10

Hi all, is there something special about "let"? I don't mean only its use in haskell, but in the general context of programming languages. I've been given a few hints over time when I asked question concerning DSLs but regretfully didn't follow them up. Günther

11 12