- Haskell - Haskell.org

RTA 2002 Call for papers
by Pierre Lescanne 15 Oct '01

15 Oct '01

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ CALL FOR PAPERS RTA 2002 13th International Conference on Rewriting Techniques and Applications July 22--24, Copenhagen, Denmark as part of FLoC'02 (http://floc02.diku.dk) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ TOPICS: RTA is the major forum for the presentation of research on all aspects of rewriting. The 13th International Conference on Rewriting Techniques and Applications solicits original papers on theoretical and practical topics related to rewriting in a broad sense. Suggested, but not exclusive, topics include: * Applications: case studies; rule-based programming; symbolic and algebraic computation; theorem proving; functional and logic programming; proof checking. * Foundations: matching and unification; completion techniques; strategies; constraint solving; explicit substitutions; tree automata. * Frameworks: string, term, and graph rewriting; lambda-calculus and higher-order rewriting; conditional rewriting; constrained rewriting and deduction; proof nets; categorical and infinitary rewriting. * Implementation: compilation techniques; parallel execution; rewriting tools. * Semantics: equational logic; rewriting logic. INVITED SPEAKERS Franz Baader (RWTH Aachen, Germany ) John Mitchell (Stanford, USA) Natarajan Shankar (SRI, USA) (joint FME-LICS-RTA) SUBMISSIONS: Submissions must be original and not submitted for publication elsewhere. Submissions should fall into one of the following categories: 1. Regular research papers describing new results; they will be judged on correctness and significance. 2. Papers describing the experience of applying rewriting techniques in other areas; they will be judged on relevance and comparison with other approaches. 3. Problem sets that provide realistic and interesting challenges in the field of rewriting. 4. System descriptions; they should contain a link to a working system and will be judged on usefulness and design. Submissions in the first three categories can be up to 15 proceedings pages long, system descriptions 4 proceedings pages. Authors are strongly encouraged to use LaTeX2e and the Springer llncs class file, available at http://www.springer.de/comp/lncs/authors.html. The title page should include the submission category. Submission is by email: Send a self-contained postscript file and an ASCII version of the paper's cover page (title, authors, submission category, abstract, contact information) to rta2002(a)lifl.fr CONFERENCE CHAIR: Thomas Arts Ericsson Computer Science Laboratory Box 1505 125 25 Alvsjo SWEDEN <thomas(a)cslab.ericsson.se> PROGRAM CHAIR: Sophie Tison LIFL Université de Lille I Cité Scientifique -- Bat.M3 59655 Villeneuve d'Ascq Cedex France <rta2002(a)lifl.fr> PROGRAM COMMITTEE: Andrea Corradini (Pisa) Daniel J. Dougherty (Wesleyan University) Jürgen Giesl (Aachen) Bernhard Gramlich (Wien) Thérèse Hardin (Paris) Christopher Lynch (Postdam) Jerzy Marcinkowski (Wroclaw) Aart Middeldorp (Tsukuba) Joachim Niehren (Saarbrucken) Femke van Raamsdonk (Amsterdam) Albert Rubio (Barcelona) Sophie Tison (Lille) Ralf Treinen (Paris-Sud) BEST PAPER AWARD: A prize of 500 EUR will be given to the best paper as judged by the program committee. The program committee may decline to make the award or may split it among several papers. IMPORTANT DATES: Submission: January 15, 2002 Notification: March 22, 2002 Final Version: April 25, 2002 RTA 2002 WEB SITE: http://www.ericsson.com/cslab/rta2002/ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ PostScript version: http://www.ens-lyon.fr/~plescann/CONTRIBUTIONS/RTA_2002.ps

1 0

RE: let-floating
by Simon Peyton-Jones 15 Oct '01

15 Oct '01

| Is there a compiler (which version?) that optimizes qsort1 to | (essentially) qsort2 ? | | Any hints concerning the possibility/impossibility of this | would be helpful. Thanks and regards, Janis. Alas, (still) not yet. As you say, the transformation depends on spotting a one-shot lambda, and our plan was to use Keith Wansbrough's usage-type work to do that. But Keith has another job, and is busy writing up his thesis. I'm still hoping to get his stuff into GHC though, but it's not imminent. A possible stop-gap would be a simpler analysis to catch common cases like the one you give. Any volunteers? Simon

1 0

Robustness of instance Read Char
by Peter Thiemann 15 Oct '01

15 Oct '01

Folks, my code has unwillingly been forced to read a large string generated by show. This turned out to be a robustness test because the effect is a stack overflow (with Hugs as well as with GHC) and, of course, this error happened in a CGI script. If you want to try the effect yourself, just take a file "foo" of, say, 150k and type this into you hungry Hugs prompt: readFile "foo" >>= \s -> putStr (read (show foo)) Digging down into the prelude code (taken from Hugs's prelude file), you find this: > instance Read Char where > readsPrec p = readParen False > (\r -> [(c,t) | ('\'':s,t) <- lex r, > (c,"\'") <- readLitChar s ]) > readList = readParen False (\r -> [(l,t) | ('"':s, t) <- lex r, > (l,_) <- readl s ]) > where readl ('"':s) = [("",s)] > readl ('\\':'&':s) = readl s > readl s = [(c:cs,u) | (c ,t) <- readLitChar s, > (cs,u) <- readl t ] which means that the parser reading this string has the ability to fail and to backtrack *at every single character*. While this might be useful in the general case, it certainly causes our little one-line program to die. Unfortunately, in my real program, the String is embedded in a data type which is deriving Read, so that writing the specific instance of read is a major pain. Two things would help me in this situation: 1. some kind-hearted maintainer of a particularly well-behaved Haskell implementation might put in a more efficient definition in the instance Read Char (or convince me that backtracking inside of reading a String is a useful gadget). The following code will do: readListChar :: String -> [(String, String)] readListChar = return . readListChar' . dropWhile isSpace readListChar' ('\"':rest) = readListChar'' rest readListChar'' ('\"':rest) = ("",rest) readListChar'' rest = let (c, s') = head (readLitChar rest) (s, s'') = readListChar'' s' in (c:s, s'') {- clearly, taking the head should be guarded and a proper error message generated -} 2. provide a way of locally replacing the offending instance of Read with something else. [urgh, a language extension] Any suggestions or comments? -Peter

1 0

let-floating
by Janis Voigtlaender 15 Oct '01

15 Oct '01

Hello, I've got a question regarding let-floating [1]. Consider the following two versions of the quicksort algorithm: > qsort1 l = f l [] > where f [] = (\y -> y) > f (x:xs) = let (xs_1,xs_2) = part (<x) xs > in (\y -> f xs_1 (x:(f xs_2 y))) > qsort2 l = f l [] > where f [] = (\y -> y) > f (x:xs) = (\y -> let (xs_1,xs_2) = part (<x) xs > in f xs_1 (x:(f xs_2 y))) where the following auxiliary function is used for partitioning a list according to some predicate p: > part p l = part' p l [] [] > part' p [] = (\y_1 y_2 -> (y_1,y_2)) > part' p (x:xs) = (\y_1 y_2 -> if p x then part' p xs (x:y_1) y_2 > else part' p xs y_1 (x:y_2)) If compiled with "ghc -O", qsort1 runs considerably slower than qsort2 (profiling shows that the problem is garbage collection). However, qsort2 can be obtained from qsort1 by floating the let-binding into the lambda-abstraction. Of course, [1] states that this is no good idea unless we know that the lambda-abstraction will be applied only once (as is the case here, right?). There it is also stated that an analysis phase is added to GHC that spots such "one-shot-lambdas". I use a fairly old GHC, so my question is: Is there a compiler (which version?) that optimizes qsort1 to (essentially) qsort2 ? Any hints concerning the possibility/impossibility of this would be helpful. Thanks and regards, Janis. [1] Simon L. Peyton Jones, Will Partain, André Santos: "Let-floating: Moving Bindings to Give Faster Programs", ICFP 1996. -- Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

1 0

bracket_
by Ken Shan 15 Oct '01

15 Oct '01

In Haskell's standard IO module, bracket_ is defined to have type IO a -> (a -> IO b) -> IO c -> IO c However, in the Exception module in hslibs, bracket_ has type IO a -> IO b -> IO c -> IO c which IMHO is much less useful, not to mention confusing. Could this be considered a bug? -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig Sometimes my spirit's empty; don't have the will to go on. I wish someone would send me energy.

1 0

Arrow notation, etc.
by Dylan Thurston 15 Oct '01

15 Oct '01

So when I read the "Syntactic Sugar for Arrows" proposal, my initial reaction is "Wow, that's a little complicated. It doesn't look like syntactic sugar to me." (Err, no offense, I hope.) This contrasts with the do-notation, which does look like syntactic sugar: you can rewrite any do expression in terms of the basic combinators with a bounded amount of pain.[1] Somehow with Arrows the point-free syntax you are forced into is extraordinarily unwieldy, and the arrows "syntactic sugar" is much handier. I presume people have tried and failed to come up with a more efficient set of combinators? Any thoughts as to why the arrow combinators need to be so unwieldy? A possibly related question: are there any general results on the verboseness of lambda calculus versus combinators? Incidentally, it seems to me that this is one case where a Lisp-like macro facility might be useful. With Haskell, it is impossible to play with bindings, while presumably you can do this with good Lisp macro systems. Best, Dylan Thurston Footnotes: [1] A quick look at the Haskell report reveals that named fields, pattern matching, and deriving declarations are not "syntactic sugar" in this sense. Of these, pattern matching is fundamental, named fields have clear semantics, and deriving declarations are more iffy [though very handy]. Did I miss any?

5 7

Re: Namespaces (was Re: GUI Library Task Force)
by John Hughes 14 Oct '01

14 Oct '01

1 0

RE: read-ing scientific notation
by Simon Peyton-Jones 14 Oct '01

14 Oct '01

| GHC is oddly particular about decimal points in "read"-ing in | of Doubles in scientific notation. It seems that read | "3.0e-06" is acceptable but read "3e-06" is not (both read | "3" and read "3.0" work fine as Doubles). It's the same in | nhc and hugs. Perhaps this is some standard somewhere that | Perl doesn't understand? It's true about the Haskell language too, and that's why it's true of Read. The lexical syntax says that 10e3 means 10 e3 (i.e. two lexemes). I don't like this choice, and it could be "fixed" in the Revised H98 report. The current production for float is float -> decimal . decimal[(e | E)[- | +]decimal] I guess we could change that to exponent -> (e|E) [+|-] decimal float -> decimal . decimal [exponent] | decimal exponent It's an unforced change and therefore to be regarded with deep suspicion. I'd be interested in people's views about this. Simon

4 3

RE: GHC 5.02, import Prelude hiding ...
by Simon Peyton-Jones 13 Oct '01

13 Oct '01

Thomas Hallgren says: | The following program was accepted by previous versions of | GHC, but is not in GHC 5.02 | | module HidingBug where | import Prelude hiding (lookup) | | lookup env x = Prelude.lookup x env | | Instead, you get the error message | | HidingBug.hs:4: Variable not in scope: `Prelude.lookup' | | This behaviour does not seem to agree with the | Haskell 98 Report, which in section 5.6.1 says | | The Prelude module is imported automatically into all modules as if | by the statement `import Prelude', if and only if it is not imported | with an explicit import declaration. This provision for explicit | import allows values defined in the Prelude to be hidden from the | unqualified name space. The Prelude module is always available as a | qualified import: an implicit `import qualified Prelude ' is part of | every module and names prefixed by `Prelude.' can always be used to | refer to entities in the Prelude. An(other) excellent point. This didn't happen on purpose, but it did happen for a reason. In the current Report draft, the idea is that a hiding clause hides both qualified and unqualified names import Foo hiding( f ) hides Foo.f as well as unqualified f. I think we all agreed that is a good change. But we (ahem, I) forgot to propagate that change to the sections about the Prelude. It's really odd to say import Prelude hiding( map ) does *not* hide Prelule.map, after all. In GHC we didn't implement this inconsistency, hence the original message. I therefore PROPOSE to replace the current text with: The Prelude module is imported automatically into all modules as if by the statement `import Prelude', if and only if it is not imported with an explicit import declaration. This provision for explicit import allows values defined in the Prelude to be selectively imported, just like any other module. The fact that this makes the Report behave like GHC is purely coincidental :-) Seriously, comments anyone? Simon

2 1

Re: macros. Was: Arrow notation, etc.
by Marcin 'Qrczak' Kowalczyk 12 Oct '01

12 Oct '01

Fri, 12 Oct 2001 15:38:21 +0200, Jerzy Karczmarczuk <karczma(a)info.unicaen.fr> pisze: > They are heavily used in Clean, so, there *are* people who see a > need for them in a lazy language. The Clean implementation doesn't inline functions across modules, right? -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0