lawbreakers in Text.PrettyPrint.HughesPJ

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

lawbreakers in Text.PrettyPrint.HughesPJ

Conal Elliott
The comments in HughesPJ say that empty is an identity for <> and $$,
but the implementation doesn't satisfy either of these laws.  Here are
the implementations:

> p $$ q = Above p False q

> p <> q = Beside p False q

and definitions for empty and isEmpty:

> empty = Empty

> isEmpty Empty = True
> isEmpty _     = False

It's an easy fix, just adding these two lines before the current
definitions of $$:

> Empty $$ q = q
> p $$ Empty = p

And these before the current definition of <>:

> Empty <> q = q
> p <> Empty = p


- Conal

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: lawbreakers in Text.PrettyPrint.HughesPJ

Christian Maeder
Conal Elliott wrote:
> The comments in HughesPJ say that empty is an identity for <> and $$,
> but the implementation doesn't satisfy either of these laws.  Here are
> the implementations:

I think, the "observable" results of <> and $$ satisfy these laws. Can
you construct an example were these laws can be observed to be not
fulfilled (for a reduced doc)?

>> p $$ q = Above p False q
>
>> p <> q = Beside p False q

Above and Beside are not observable and (I think) your proposed fix is
not necessary.

Christian
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

RE: lawbreakers in Text.PrettyPrint.HughesPJ

Conal Elliott
> Can you construct an example [...]

Certainly.  Here's the example that caught my attention (in my GHC 6.5
STABLE):

    Prelude Text.PrettyPrint> isEmpty empty
    True
    Prelude Text.PrettyPrint> isEmpty (empty<>empty)
    False

Similarly,

    Prelude Text.PrettyPrint> isEmpty (empty$$empty)
    False

Cheers, - Conal

-----Original Message-----
From: Christian Maeder [mailto:[hidden email]]
Sent: Thursday, November 24, 2005 1:12 AM
To: Conal Elliott
Cc: [hidden email]
Subject: Re: lawbreakers in Text.PrettyPrint.HughesPJ

Conal Elliott wrote:
> The comments in HughesPJ say that empty is an identity for <> and $$,
> but the implementation doesn't satisfy either of these laws.  Here are
> the implementations:

I think, the "observable" results of <> and $$ satisfy these laws. Can
you construct an example were these laws can be observed to be not
fulfilled (for a reduced doc)?

>> p $$ q = Above p False q
>
>> p <> q = Beside p False q

Above and Beside are not observable and (I think) your proposed fix is
not necessary.

Christian

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: lawbreakers in Text.PrettyPrint.HughesPJ

Christian Maeder
Conal Elliott wrote:
>> Can you construct an example [...]
>
>     Prelude Text.PrettyPrint> isEmpty (empty<>empty)
>     False

Indeed, isEmpty seems to be the problem that needs a fix:

   isEmpty d     = case reduceDoc d of
                 Empty -> True
                 _ -> False

Christian
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

RE: lawbreakers in Text.PrettyPrint.HughesPJ

Conal Elliott
Or the combinators (<>, $$, etc) might take care to build their results
in reduced form, which seems to be the strategy that "nest" takes.

BTW, there's an invariant comment (about Doc, I think) that says "An
empty document is always represented by @Empty@."  If the combinators
aren't going to ensure that's true, then probably the comment should be
removed or fixed.

- Conal

-----Original Message-----
From: Christian Maeder [mailto:[hidden email]]
Sent: Thursday, November 24, 2005 8:56 AM
To: Conal Elliott
Cc: [hidden email]
Subject: Re: lawbreakers in Text.PrettyPrint.HughesPJ

Conal Elliott wrote:
>> Can you construct an example [...]
>
>     Prelude Text.PrettyPrint> isEmpty (empty<>empty)
>     False

Indeed, isEmpty seems to be the problem that needs a fix:

   isEmpty d     = case reduceDoc d of
                 Empty -> True
                 _ -> False

Christian

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: lawbreakers in Text.PrettyPrint.HughesPJ

Christian Maeder
Conal Elliott wrote:
> Or the combinators (<>, $$, etc) might take care to build their results
> in reduced form, which seems to be the strategy that "nest" takes.

maybe that is possible, too (as now an extra call of reduceDoc for
isEmpty is done). Fortunately isEmpty is rarely used, and if it is used
the original input is usually thrown away.

> BTW, there's an invariant comment (about Doc, I think) that says "An
> empty document is always represented by @Empty@."  If the combinators
> aren't going to ensure that's true, then probably the comment should be
> removed or fixed.

The comment only seems to apply to RDoc that don't have Above or Beside
(at least on the top-level).

Christian
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

RE: lawbreakers in Text.PrettyPrint.HughesPJ

Simon Peyton Jones
In reply to this post by Conal Elliott
It's a long time since I looked at this library.  If you two can agree
on what needs to be done, I'll gladly execute the change!

Simon

| -----Original Message-----
| From: [hidden email]
[mailto:[hidden email]] On Behalf Of Christian
| Maeder
| Sent: 24 November 2005 18:05
| To: Conal Elliott
| Cc: [hidden email]
| Subject: Re: lawbreakers in Text.PrettyPrint.HughesPJ
|
| Conal Elliott wrote:
| > Or the combinators (<>, $$, etc) might take care to build their
results
| > in reduced form, which seems to be the strategy that "nest" takes.
|
| maybe that is possible, too (as now an extra call of reduceDoc for
| isEmpty is done). Fortunately isEmpty is rarely used, and if it is
used
| the original input is usually thrown away.
|
| > BTW, there's an invariant comment (about Doc, I think) that says "An
| > empty document is always represented by @Empty@."  If the
combinators
| > aren't going to ensure that's true, then probably the comment should
be
| > removed or fixed.
|
| The comment only seems to apply to RDoc that don't have Above or
Beside
| (at least on the top-level).
|
| Christian
| _______________________________________________
| Libraries mailing list
| [hidden email]
| http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: lawbreakers in Text.PrettyPrint.HughesPJ

Christian Maeder
Simon Peyton-Jones wrote:
> It's a long time since I looked at this library.  If you two can agree
> on what needs to be done, I'll gladly execute the change!

I've tried both versions, without noticing a difference. So take the
following patch (as suggested by Conal).

Cheers Christian


  --
---------------------------------------------------------------------------
  -- Vertical composition @$$@

-p $$  q = Above p False q
-p $+$ q = Above p True q
+above_ :: Doc -> Bool -> Doc -> Doc
+above_ Empty _ q = q
+above_ p _ Empty = p
+above_ p g q = Above p g q
+
+p $$  q = above_ p False q
+p $+$ q = above_ p True q

  above :: Doc -> Bool -> RDoc -> RDoc
  above (Above p g1 q1)  g2 q2 = above p g1 (above q1 g2 q2)
@@ -607,8 +611,13 @@
  --
---------------------------------------------------------------------------
  -- Horizontal composition @<>@

-p <>  q = Beside p False q
-p <+> q = Beside p True  q
+beside_ :: Doc -> Bool -> Doc -> Doc
+beside_ Empty _ q = q
+beside_ p _ Empty = p
+beside_ p g q = Beside p g q
+
+p <>  q = beside_ p False q
+p <+> q = beside_ p True  q

  beside :: Doc -> Bool -> RDoc -> RDoc
  -- Specification: beside g p q = p <g> q
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: lawbreakers in Text.PrettyPrint.HughesPJ

Christian Maeder
Christian Maeder wrote:
> @@ -607,8 +611,13 @@

Myline number may be wrong, because I used an older version of the
module. After the introduction of above_ and beside_ it also makes sense
to move the call of reduceDoc to the last argument (and remove this
calls in reduceDoc and above). The patch for this is below. I cannot
observe speed differences, though.

Christian

@@ -461,8 +461,8 @@
  type RDoc = Doc

  reduceDoc :: Doc -> RDoc
-reduceDoc (Beside p g q) = beside p g (reduceDoc q)
-reduceDoc (Above  p g q) = above  p g (reduceDoc q)
+reduceDoc (Beside p g q) = beside p g q
+reduceDoc (Above  p g q) = above  p g q
  reduceDoc p              = p


@@ -562,15 +562,15 @@
  above_ :: Doc -> Bool -> Doc -> Doc
  above_ Empty _ q = q
  above_ p _ Empty = p
-above_ p g q = Above p g q
+above_ p g q = Above p g (reduceDoc q)

  p $$  q = above_ p False q
  p $+$ q = above_ p True q

  above :: Doc -> Bool -> RDoc -> RDoc
  above (Above p g1 q1)  g2 q2 = above p g1 (above q1 g2 q2)
-above p@(Beside _ _ _) g  q  = aboveNest (reduceDoc p) g 0 (reduceDoc q)
-above p g q                  = aboveNest p             g 0 (reduceDoc q)
+above p@(Beside _ _ _) g  q  = aboveNest (reduceDoc p) g 0 q
+above p g q                  = aboveNest p             g 0 q

  aboveNest :: RDoc -> Bool -> Int -> RDoc -> RDoc
  -- Specfication: aboveNest p g k q = p $g$ (nest k q)
@@ -614,7 +614,7 @@
  beside_ :: Doc -> Bool -> Doc -> Doc
  beside_ Empty _ q = q
  beside_ p _ Empty = p
-beside_ p g q = Beside p g q
+beside_ p g q = Beside p g (reduceDoc q)

  p <>  q = beside_ p False q
  p <+> q = beside_ p True  q

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: lawbreakers in Text.PrettyPrint.HughesPJ

Christian Maeder
In reply to this post by Christian Maeder
Christian Maeder wrote:
> I've tried both versions, without noticing a difference. So take the
> following patch (as suggested by Conal).

I became a problem with my (Conal's) suggested patch on a mac. When
compiled with optimization the code was so blown up that it could no
longer be linked on a mac. (The problem does not occur if only isEmpty
is changed as suggested before.)

Unfortunately the example is large and takes ages to be reproduced and
it took me an age to find that the cause was my change to our version of
HughesPJ.hs.

Christian

the link error shows up as:

[...]
/usr/bin/ld: ./Logic/Logic.o relocation overflow for relocation entry
5401 in se
ction (__TEXT,__text) (displacement too large)
collect2: ld returned 1 exit status
make: *** [hets] Error 1
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

RE: lawbreakers in Text.PrettyPrint.HughesPJ

Simon Peyton Jones
In reply to this post by Conal Elliott
I had trouble parsing your message.

Are you saying that
  (a) before changing the library you have a program that compiles ok
  (b) after changing the library, the program becomes gigantic and won't
link
?

Nothing to do with *running* the program?  

If I have understood right, what are the sizes of the .o files in (a)
and (b)?   Has one (or lots) gotten gigantic?

Simon

| -----Original Message-----
| From: [hidden email]
[mailto:[hidden email]] On Behalf Of Christian
| Maeder
| Sent: 30 November 2005 14:45
| To: Simon Peyton-Jones
| Cc: [hidden email]
| Subject: Re: lawbreakers in Text.PrettyPrint.HughesPJ
|
| Christian Maeder wrote:
| > I've tried both versions, without noticing a difference. So take the
| > following patch (as suggested by Conal).
|
| I became a problem with my (Conal's) suggested patch on a mac. When
| compiled with optimization the code was so blown up that it could no
| longer be linked on a mac. (The problem does not occur if only isEmpty
| is changed as suggested before.)
|
| Unfortunately the example is large and takes ages to be reproduced and
| it took me an age to find that the cause was my change to our version
of
| HughesPJ.hs.
|
| Christian
|
| the link error shows up as:
|
| [...]
| /usr/bin/ld: ./Logic/Logic.o relocation overflow for relocation entry
| 5401 in se
| ction (__TEXT,__text) (displacement too large)
| collect2: ld returned 1 exit status
| make: *** [hets] Error 1
| _______________________________________________
| Libraries mailing list
| [hidden email]
| http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: lawbreakers in Text.PrettyPrint.HughesPJ

Christian Maeder
Simon Peyton-Jones wrote:
> I had trouble parsing your message.

Sorry, what should I improve? At last, you've parsed my message correctly.

> Are you saying that
>   (a) before changing the library you have a program that compiles ok
>   (b) after changing the library, the program becomes gigantic and won't
> link
> ?

Yes, I say (a) and (b)

> Nothing to do with *running* the program?  

Right, no run-time problem.

> If I have understood right, what are the sizes of the .o files in (a)
> and (b)?   Has one (or lots) gotten gigantic?

Yes, one .o file has (a) 150 KB before and (b) 4 MB after the library
change. I assume, I should supply a test case (to
[hidden email]). I'll do so later.

Better, do not commit the patch I've sent you to
Text.PrettyPrint.HughesPJ before this issue is settled.

Christian

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: lawbreakers in Text.PrettyPrint.HughesPJ

Christian Maeder
In reply to this post by Simon Peyton Jones
Hi Simon,

> | Christian Maeder wrote:
> | I became a problem with my (Conal's) suggested patch on a mac. When
> | compiled with optimization the code was so blown up that it could no
> | longer be linked on a mac. (The problem does not occur if only isEmpty
> | is changed as suggested before.)

Before HughesPJ.hs does not get fixed at all, because of the open
"object code blow up by minor source code change" bug

http://hackage.haskell.org/trac/ghc/ticket/490

You may apply the alternative patch (attached), that worked for me.

Cheers Christian

Index: HughesPJ.hs
===================================================================
RCS file: /cvs/fptools/libraries/base/Text/PrettyPrint/HughesPJ.hs,v
retrieving revision 1.17
diff -u -r1.17 HughesPJ.hs
--- HughesPJ.hs 22 Sep 2005 09:43:01 -0000 1.17
+++ HughesPJ.hs 22 Dec 2005 16:11:27 -0000
@@ -582,8 +582,9 @@
 
 empty = Empty
 
-isEmpty Empty = True
-isEmpty _     = False
+isEmpty d = case reduceDoc d of
+              Empty -> True
+              _ -> False
 
 char  c = textBeside_ (Chr c) 1 Empty
 text  s = case length s of {sl -> textBeside_ (Str s)  sl Empty}

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries