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

[oleg@okmij.org]

> 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.