[Caml-list] I never succeeded in using Format

[Caml-list] I never succeeded in using Format

[Matthieu Dubuget]

Is the following behaviour expected, or a misunderstanding of mine?

In short, I'd like to use the Format module to prepare an
output inside a Buffer.t. But a basic <hov> box does not
break lines as I would expect, while printf does.

OCaml version 4.01.0

# open Format;;
# printf "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
111,222,333,444,555,666
- : unit = ()
# set_margin 9;;
- : unit
= ()
# printf "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
111,222,
333,444,
555,666
- : unit
= ()
# sprintf "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
- : string
=
"111,222,333,444,555,666\n"

Why doesn't sprintf exhibit the same behaviour as printf?
Trying with fprintf…

# fprintf str_formatter "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
- : unit
= ()
# flush_str_formatter ();;
- : string
=
"111,222,333,444,555,666\n"

-- 
Matthieu Dubuget

Re: [Caml-list] I never succeeded in using Format

[Jeremy Yallop]

On 6 March 2014 16:34, Matthieu Dubuget <matthieu.dubuget@gmail.com> wrote:
> Why doesn't sprintf exhibit the same behaviour as printf?

The set_margin function only affects std_formatter:

   https://github.com/ocaml/ocaml/blob/8ba031a/stdlib/format.ml#L1027

You need to use pp_set_margin for other formatters.

Jeremy.

Re: [Caml-list] I never succeeded in using Format

[Benoit Vaugon]

[-- Attachment #1: Type: text/plain, Size: 1916 bytes --]

Hi,

The set_margin function configure the std_formatter, ie the formatter of
the standard output (the one used by printf). To change the margin when
printing in a buffer, you can run something like this :

# open Format;;
# let buf = Buffer.create 16;;
val buf : Buffer.t = <abstr>
# let formatter = formatter_of_buffer buf;;
val formatter : Format.formatter = <abstr>
# pp_set_margin formatter 9;;
- : unit = ()
# fprintf formatter "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
- : unit = ()
# Buffer.contents buf;;
- : string = "111,222,\n333,444,\n555,666\n"

Best regards,
Benoît Vaugon.



2014-03-06 17:34 GMT+01:00 Matthieu Dubuget <matthieu.dubuget@gmail.com>:

> Is the following behaviour expected, or a misunderstanding of mine?
>
> In short, I'd like to use the Format module to prepare an
> output inside a Buffer.t. But a basic <hov> box does not
> break lines as I would expect, while printf does.
>
> OCaml version 4.01.0
>
> # open Format;;
> # printf "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
> 111,222,333,444,555,666
> - : unit = ()
> # set_margin 9;;
> - : unit
> = ()
> # printf "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
> 111,222,
> 333,444,
> 555,666
> - : unit
> = ()
> # sprintf "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
> - : string
> =
> "111,222,333,444,555,666\n"
>
> Why doesn't sprintf exhibit the same behaviour as printf?
> Trying with fprintf...
>
> # fprintf str_formatter "@[<hov0>111,@,222,@,333,@,444,@,555,@,666@]@.";;
> - : unit
> = ()
> # flush_str_formatter ();;
> - : string
> =
> "111,222,333,444,555,666\n"
>
> --
> Matthieu Dubuget
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 2966 bytes --]

Re: [Caml-list] I never succeeded in using Format

[Matthieu Dubuget]

Oh! Thanks for your answers…

I had checked in the documentation if set_margin was not only for
std_formatter, but did not find any warning…

And I overlooked pp_set_margin…

OK. I now could propose a small improvement of the documentation.

Is the documentation in a public repository?

Salutations

-- 
Matthieu Dubuget

Re: [Caml-list] I never succeeded in using Format

[David Sheets]

On Thu, Mar 6, 2014 at 5:02 PM, Matthieu Dubuget
<matthieu.dubuget@gmail.com> wrote:
> Oh! Thanks for your answers...
>
> I had checked in the documentation if set_margin was not only for
> std_formatter, but did not find any warning...
>
> And I overlooked pp_set_margin...
>
> OK. I now could propose a small improvement of the documentation.
>
> Is the documentation in a public repository?

<https://github.com/ocaml/ocaml/blob/trunk/stdlib/format.mli>

> Salutations
>
> --
> Matthieu Dubuget
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] I never succeeded in using Format

[Matthieu Dubuget]

Thanks again!

I never realized that the documentation was generated from the .mli.

Maybe, it is the time to go home…


-- 
Matthieu Dubuget

Re: [Caml-list] I never succeeded in using Format

[Martin Jambon]

Note that I made a library called easy-format that supposedly makes it 
easier to pretty-print code exactly the way you want:

project page:
  http://mjambon.com/easy-format.html

sample code + output:
  http://mjambon.com/easy_format_example.html


Martin

On Thu 06 Mar 2014 09:09:38 AM PST, Matthieu Dubuget wrote:
> Thanks again!
>
> I never realized that the documentation was generated from the .mli.
>
> Maybe, it is the time to go home…
>
>

Re: [Caml-list] I never succeeded in using Format

[Raphaël Proust]

On Thu, Mar 6, 2014 at 7:08 PM, Martin Jambon
<martin.jambon@ens-lyon.org> wrote:
> Note that I made a library called easy-format that supposedly makes it
> easier to pretty-print code exactly the way you want:
>
> project page:
>  http://mjambon.com/easy-format.html
>
> sample code + output:
>  http://mjambon.com/easy_format_example.html

Another alternative to format for pretty-printing code (or other things): PPrint

Release blog post (with some examples of use):
http://gallium.inria.fr/blog/first-release-of-pprint/
Documentation: http://gallium.inria.fr/~fpottier/pprint/doc/PPrint.html
Installation instruction: `opam install pprint`


Cheers,
-- 
______________
Raphaël Proust

Re: [Caml-list] I never succeeded in using Format

[oleg]

> Another alternative to format for pretty-printing code (or other things): PPrint
>
> Release blog post (with some examples of use):
> http://gallium.inria.fr/blog/first-release-of-pprint/
> Documentation: http://gallium.inria.fr/~fpottier/pprint/doc/PPrint.html
> Installation instruction: `opam install pprint`

That formatter uses Wadler's Pretty-printer, which is not optimal. The
optimal one takes linear time in the size of the document (regardless
of the page width), and, for constant page width, formats documents of
any size in constant space. It is obviously incremental and has
bounded latency. There are several optimal formatters. The recent one
was based on simple generators, described in
        http://okmij.org/ftp/continuations/PPYield/index.html#pp

Curiously, a Clojure programmer has read our paper and re-wrote the
algorithm in Clojure -- without any help from us. It seems he is very
satisfied with the results:
        https://github.com/brandonbloom/fipp
That web page has a few examples.

Re: [Caml-list] I never succeeded in using Format

[Bob Atkey]

Hi Oleg,

Have you compared your implementation to Christian Lindig's 'Strictly Pretty'?:

   http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2200

I think the runtime of his implementation is dependent on page width,
due to repeated use of the fits function to measure whether a group
fits within the current line. A simple optimisation is to precompute
this width, as (I think) you do. I did this in my simple
implementation of Lindig's idea:

   https://github.com/bobatkey/pretty-monospace/blob/master/lib/Pretty.ml

Neither of these implementations are incremental though; both require
the entire document to be present up front.

Bob



On 10 March 2014 00:47,  <oleg@okmij.org> wrote:
>
>> Another alternative to format for pretty-printing code (or other things): PPrint
>>
>> Release blog post (with some examples of use):
>> http://gallium.inria.fr/blog/first-release-of-pprint/
>> Documentation: http://gallium.inria.fr/~fpottier/pprint/doc/PPrint.html
>> Installation instruction: `opam install pprint`
>
> That formatter uses Wadler's Pretty-printer, which is not optimal. The
> optimal one takes linear time in the size of the document (regardless
> of the page width), and, for constant page width, formats documents of
> any size in constant space. It is obviously incremental and has
> bounded latency. There are several optimal formatters. The recent one
> was based on simple generators, described in
>         http://okmij.org/ftp/continuations/PPYield/index.html#pp
>
> Curiously, a Clojure programmer has read our paper and re-wrote the
> algorithm in Clojure -- without any help from us. It seems he is very
> satisfied with the results:
>         https://github.com/brandonbloom/fipp
> That web page has a few examples.
>
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] I never succeeded in using Format

[oleg]

> Have you compared your implementation to Christian Lindig's 'Strictly Pretty'?:
>    http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2200
>
> ... 
> A simple optimisation is to precompute this width, as (I think) you
> do. I did this in my simple implementation of Lindig's idea:
>
>    https://github.com/bobatkey/pretty-monospace/blob/master/lib/Pretty.ml
>
> Neither of these implementations are incremental though; both require
> the entire document to be present up front.

Thank you for the reference! I should compare with his and your
implementations.

Our pretty-printer is designed from the outset to be incremental. It
operates on a stream of tokens: text-string, newline, begin-group,
end-group.  It is literally a functional composition of four stream
transformers which annotate the stream tokens and then format them,
outputting chunks of the final text. The formatting is simple if the
begin-group token is annotated with the width of the corresponding
group. The key idea is that we need to know this width only up to the
point: if it exceeds the page width, we don't need to know by how
much. So, computing this annotation requires only a bounded
look-ahead. It is crucial for the performance to use a sequence data
structure with the amortized constant-time addition and removal on
both ends. Standard libraries of Haskell and Clojure luckily provide
such a data structure.

Re: [Caml-list] I never succeeded in using Format

[Francois Pottier]

Dear all,

Interesting discussion, which prompted me to come out of my retreat and
publish a new implementation of PPrint, available now :-)

Oleg is right: the now-old PPrint implementation uses backtracking and its
time complexity is dependent on the window width.

Oleg's message caused me to think, and I realized that I had missed a major
opportunity for simplification and optimization, which in fact was shortly
thereafter mentioned by Bob in his reply to Oleg's message. The idea is
simple. The PPrint API requires the document to be constructed in an eager,
bottom-up manner. (One reason for this decision was syntax: I did not want the
user to have to write "lazy" everywhere, and I did not want to impose the use
of a syntax extension.) So, we are paying a high cost in space (linear space
overhead), but in return, it is easy to compute the required width of every
(sub-)document as it is constructed. This in turn means that the rendering
process can be performed in linear time, without dependency on the window
width, without any backtracking or buffering.

I have implemented this idea in the new version of PPrint and compared it with
the old version. In short, the results are as follows, for a set of
randomly-generated documents:

  - the construction of the document is roughly just as fast as it was
    (but documents occupy slightly more space in memory)

  - rendering is faster than before, between 2x and 3x faster

  - the code is much simpler than before (this is the key benefit)

  - two features are lost (namely, the primitive operators [nesting] and
    [column], which were used to get access to the engine's state during
    rendering; they are no longer supported because they prevent the width
    pre-computation).

I should point out that rendering is now between 10x and 20x faster than the
construction of the document, which (I believe) means that the current
implementation is essentially unbeatable in terms of throughput. So, in my
view, the bottom line is, if one is willing to live with linear space
overhead, then this approach is preferable for its simplicity and efficiency;
if one must work in constant space, then Oleg's approach is preferable.

The new release of PPrint is available here:

  http://gallium.inria.fr/~fpottier/pprint/pprint.tar.gz

and should reach opam pretty soon ("opam install pprint").

Best regards,

-- 
François Pottier
Francois.Pottier@inria.fr
http://gallium.inria.fr/~fpottier/