March 2002 - Haskell - Haskell.org

RE: Haskell report: deriving Show & Read instances, Appendix D
by Simon Peyton-Jones 12 Mar '02

12 Mar '02

Folks Olaf points out a problem with the specification of 'deriving' Show. In particular: | "The representation will be enclosed in parentheses | if the precedence of the top-level constructor operator in x | is less than d." Olaf proposes that we should change "less than" to "less than or equal to". His reasoning is below, and seems persuasive to me. Briefly, the consequences of the change would be: a) The current specification yields syntactically incorrect Haskell for some associativities. The changed specification would avoid this. b) The changed spec would yield more than the minimum number of parentheses. c) The current spec makes it hard for simple recursive descent parsers, such as that suggested by the Report for Read, to avoid divergence on left recursion. The changed spec makes it easy. d) The downside is that all compilers would need to change, slightly. Any comments? Simon | In all Haskell implementations (tested Hugs,Ghc and nhc98) | show sometimes produces output that does not represent | well-formed expressions. For example: | | data Tree a = Node a | Tree a :^: Tree a | Tree a ::: Tree a | deriving (Eq,Show) | | infixl 6 ::: | infixr 6 :^: | | main = print ((Node True :^: Node False) ::: Node True) | | yields | | Node True :^: Node False ::: Node True | | The expression is ill-formed because one constructor is left- | and the other one is right-associative. | | Finally, left-recursive data constructors that are | left-associative lead read into infinite recursion. Example: | | infixl 5 :^: | | data Tree a = Leaf a | Tree a :^: Tree a deriving (Show,Read) | | main = do | print (read "(Leaf True :^: Leaf False) :^: Leaf True" :: Tree Bool) | | | I have a solution for the two last problems. It means all | Haskell compilers have to change, but I believe that it is worth it. | | The source of the show problem is that show tries to handle | associativity of infix constructors. But there is no way to | do this correctly. showsPrec gets as argument the precedence | of the surounding expression, but not its associativity. This | associativity would be needed to use associativity of | constructors correctly. | | The solution is simple: dont' try to use associativity to | avoid parenthesis. Thus you get some superfluous paranthesis, | but the output is always correct and the implementation of | deriving is even a bit simpler. E.g.: | | showsPrec d (u :^: v) = showParen (d > 5) showStr | where | showStr = showsPrec 6 u . | showString " :^: " . | showsPrec 6 v | For all of | | infix 5 :^: | infixl 5 :^: | infixr 5 :^: | | The second advantage of this simplification is, that the | additional parentheses prevent infinite left recursion. You | can read in the tree expression given above, because | parentheses are now compulsory: | | instance (Read a) => Read (Tree a) where | | readsPrec d r = readParen (d > 5) | (\r -> [(u:^:v,w) | | (u,s) <- readsPrec 6 r, | (":^:",t) <- lex s, | (v,w) <- readsPrec 6 t]) r | | ++ readParen (d > 9) | (\r -> [(Leaf m,t) | | ("Leaf",s) <- lex r, | (m,t) <- readsPrec 10 s]) r | | What do you think? | | Discussing all the other minor problems with the report | specification doesn't make sense before this major issue is | cleared up. | | Ciao, | Olaf | | -- | OLAF CHITIL, | Dept. of Computer Science, The University of York, York YO10 | 5DD, UK. | URL: http://www.cs.york.ac.uk/~olaf/ | Tel: +44 1904 434756; Fax: +44 1904 432767 |

1 0

FW: H98 Report: expression syntax glitch
by Simon Peyton-Jones 12 Mar '02

12 Mar '02

In response to my recent message (below), Ross asks: "Are you rejecting the fix I suggested: Add a side condition to the grammar in 3.13: the guard must not end with a type signature (because the following -> looks like part of the type)." Indeed, this would be possible. It would reject programs like f x = case x of { (a,b) | b :: Bool -> a } which are in principle reasonable, but are really hard to parse. Indeed, GHC, Hugs, and nhc all reject it. I suppose that the term "ends with" is a bit imprecise, too. Presumably this would be OK f x = case x of { (a,b) | (b :: Bool) -> a } Still, Ross's suggestion is pragmatic: if all the impls find this corner of the language too hard to parse, then some guidance about what not to write would be a good plan. As usual, this is not a big deal: it's a dark corner that few will trip over. But it is my joyful task (aided by many others) to try to illuminate the darkness, so I invite your opinions about which fix (the one below, or Ross's) is better. Simon -----Original Message----- From: Ross Paterson [mailto:ross@soi.city.ac.uk] Sent: 11 March 2002 17:59 To: Simon Peyton-Jones Subject: Re: H98 Report: expression syntax glitch Simon, > Ross points out that this is really hard to parse: > > | case x of y | ($ True) $ \ z -> z :: Bool -> Bool -> y > > because the parser doesn't know when to stop eating the type and treat > the arrow as the case-alternative arrow. > But in neither case can I see a cure that is better than the > disease. Remember, large-scale fixes are out of court. An easier case than Carl's, I think.

1 0

FW: Layout indentation marking
by Simon Peyton-Jones 12 Mar '02

12 Mar '02

I agree with Ian here (and not just because of what GHC does!) Does anyone disagree? Simon -----Original Message----- From: Ian Lynagh [mailto:igloo@earth.li] Sent: 10 March 2002 15:23 To: Haskell list Subject: Layout indentation marking Given this module module Main where main :: IO() main = putStrLn $ show $ foo foo :: Int foo = x + y where x = 6 s = "foo\ \bar" y = 7 nhc98 and hugs correctly (as per the revised report) print 13. ghc gives q.lhs:11: parse error on input `=' I think ghc is in the right here and the report should be updated to read + Where the start of a lexeme does not follow the end of a lexeme on the same line, this lexeme is preceded by <n> where n is the indentation of the lexeme, provided that it is not, as a consequence of the first two rules, preceded by {n}. (A string literal may span multiple lines -- Section 2.6.) (it currently reads + Where the start of a lexeme does not follow a complete lexeme on the same line, this lexeme is preceded by <n> where n is the indentation of the lexeme, provided that it is not, as a consequence of the first two rules, preceded by {n}. (A string literal may span multiple lines -- Section 2.6.) where I have altered only the first line). Thanks Ian _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

1 0

A Cygwin port of hmake?
by Antony Courtney 12 Mar '02

12 Mar '02

Hi, Has anyone attempted / considered porting hmake to Cygwin? I'd like to try HaXmL under ghc on Windows, but it seems to require hmake to build. I made a naieve attempt to configure and build hmake under Cygwin myself, but the resulting Makefile tried to pass Cygwin-style /cygdrive/c/... paths to ghc, which promptly choked. I made some abortive attempts to hand-edit the Makefile.inc, but it then attempted to create some directories above my current working directory, and I eventually got lost trying to trace down the nested Makefile inclusions. Before I invest more time in either porting hmake or writing a portable Makefile for HaXmL, I thought I'd post here to see if anyone else had already been down this road. If you have, please get in touch. Thanks, -antony -- Antony Courtney Grad. Student, Dept. of Computer Science, Yale University antony(a)apocalypse.org http://www.apocalypse.org/pub/u/antony

3 3

RE: first-class polymorphism beats rank-2 polymorphism
by Simon Peyton-Jones 12 Mar '02

12 Mar '02

| Ok, that's what I meant: in RHSs of other type synonyms. | BTW, it also works when passing parameters to parameterized | datatypes. Here is a variation on defining Generic as a | datatypes as opposed to the earlier type synonym. Id is still | the same type synonym as before. | | data Generic' i o = G (forall x. i x -> o x) | type TP = Generic Id Id | | Yes, I was surprised to see that it works to this extent. This works because you said Generic not Generic' in the RHS of TP. If you use Generic' the program is rejected, and so it should be. | system would ask for. So I revise my question: Does the | current support for partially applied type synonyms | pose any challenges or is it basically just like macro | expansion? That is, is the type system maybe not even | affected by it? If it is easy, why is not in Haskell 98 and | in hugs? It is terribly useful. It's just macro expansion. GHC expands saturated type synonyms before looking for well-formedness in types. This is indeed rather useful, and it's easy too. It's not in H98 because no one thought of it then. Simon

1 0

minor H98 inconsistency: sections
by Ross Paterson 12 Mar '02

12 Mar '02

The following passages differ on the status of (a+b+): 3 Expressions aexp -> ... | ( expi+1 qop(a,i) ) (left section) | ( qop(a,i) expi+1 ) (right section) 3.5 Sections Syntactic precedence rules apply to sections as follows. (op e) is legal if and only if (x op e) parses in the same way as (x op (e)); and similarly for (e op). For example, (*a+b) is syntactically invalid, but (+a*b) and (*(a+b)) are valid. Because (+) is left associative, (a+b+) is syntactically correct, but (+a+b) is not; the latter may legally be written as (+(a+b)). ghc follows the grammar, rejecting (a+b+) Hugs accepts (op a op' b) and rejects (a op b op') regardless of associativity and precedence, while nhc accepts them both. The grammar could be made to match the text by adding two alternatives: | ( lexpi qop(l,i) ) (left section) | ( qop(r,i) rexpi ) (right section) Changing the text to match the grammar seems less attractive. But the text says more than the revised grammar. For example, it deals with the expression glitch I mentioned the other week: together with the disambiguation meta-rule, it implies that the expression (let x = 10 in x `div`) is invalid, because let x = 10 in x `div` z doesn't parse as (let x = 10 in x) `div` z (might be worth adding this as an example) but it's no help with SimonM's example let x = 10 in x == x == True

1 0

RE: first-class polymorphism beats rank-2 polymorphism
by Simon Peyton-Jones 12 Mar '02

12 Mar '02

| type Generic i o = forall x. i x -> o x | | type Id x = x | | comb :: | (Generic Id Id) | -> (Generic Id Id) | -> (Generic Id Id) | comb = undefined | So now let's ask for the type of comb in ghc. | It turns out to be the rank-1 (!!!) type I captured as | explicit type annotation for comb'. I would have expected a | rank-2 type because the forall is scoped by the type synonym | Generic. So why should I like to see the forall going to the | top? I still would say that THIS IS A BUG. Here is why the Yes, indeed this is a bug. Thank you for finding it. It turned out that in liberalising GHC's treatment of type synonyms (which you remark is a good thing) I had failed to cover a case. Fortunately, an ASSERT caught the bug in my build, and the fix is easy. | yacomb1 :: (forall x. x -> x) | -> (forall x. x -> x) | -> (forall x. x -> x) | yacomb1 = (.) | | yacomb2 :: forall x y z. (x -> x) -> (y -> y) -> (z -> z) | yacomb2 = undefined | | Now let's try to define yacomb2 in terms of yacomb1, that is: | | yacomb2 = yacomb1 | | This works. Let us not wonder why. We should wonder why. It's plain wrong. yacomb1's type signature is more restrictive than that of yacomb2. This is a bug in the 5.03 snapshot, which fortunately I fixed a week or two ago. The compiler in the respository rejects the definition. Bottom line: you found two bugs, for which much thanks. But I stand by forall-lifting! (But note that the foralls are lifted only from *after* the arrow, not before. (forall a.a->a) -> Int is not the same as (forall a. (a->a) -> Int).) Simon

1 0

RE: Concurrent Haskell (GHC) and Win32 Applications ?
by Simon Peyton-Jones 12 Mar '02

12 Mar '02

| Ahem - how far would this be from a "real" multithreaded | implementation, i.e. one that could use a few OS threads to | take advantage of multiple CPUs in an SMP system? Not very far. We have had a working implementation of such a thing, but not in a robust releasable state. S

2 1

RE: Concurrent Haskell (GHC) and Win32 Applications ?
by Simon Peyton-Jones 12 Mar '02

12 Mar '02

| The problem I think is with the lightweight thread implementation - | Win32 calls can (and will) block the OS thread that makes the call, | which blocks the entire system. Given that I'm wanting to write a | network server with a Win32 GUI, this is obviously a Bad Thing. Yes, that's true at the moment, but it's something that we expect to fix shortly. More precisely, Sigbjorn has been working on a fix. It relies on using an OS thread to make a potentially-blocking call, so it's a robust fix. I don't quite know when he'll be done with this -- Sigbjorn do you know? Meanwhile, all you can do is to avoid making blocking I/O calls. Simon

3 2

type aliases in instances
by Bernhard Reus 12 Mar '02

12 Mar '02

In Haskell type aliases are not allowed in instance definitions. Is there a particular reason for this? For example, is there a problem with type inference? I noticed that when composing monads (in the Moggi/Wadler style) one easily ends up with a cascade of coercions enforced by datatype declarations. Looks a bit tedious. This can be avoided by using type aliases but then the monads in use cannot be instances of the Monad class. Phil uses aliases in his "Essence of functional programming" paper too. But not declaring the monads to be in class Monad can hardly be good style, can it? Many thanks for your help in advance. Bernhard --- Bernhard Reus, COGS University of Sussex

5 5