From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <oleg@okmij.org>
X-Original-To: caml-list@sympa.inria.fr
Delivered-To: caml-list@sympa.inria.fr
Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104])
	by sympa.inria.fr (Postfix) with ESMTPS id B51747ED94
	for <caml-list@sympa.inria.fr>; Tue, 11 Mar 2014 10:32:46 +0100 (CET)
Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender
  authenticity information available from domain of
  oleg@okmij.org) identity=pra; client-ip=66.39.3.115;
  receiver=mail3-smtp-sop.national.inria.fr;
  envelope-from="oleg@okmij.org"; x-sender="oleg@okmij.org";
  x-conformance=sidf_compatible
Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of
  oleg@okmij.org designates 66.39.3.115 as permitted sender)
  identity=mailfrom; client-ip=66.39.3.115;
  receiver=mail3-smtp-sop.national.inria.fr;
  envelope-from="oleg@okmij.org"; x-sender="oleg@okmij.org";
  x-conformance=sidf_compatible; x-record-type="v=spf1"
Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@www1.g3.pair.com) identity=helo;
  client-ip=66.39.3.115;
  receiver=mail3-smtp-sop.national.inria.fr;
  envelope-from="oleg@okmij.org";
  x-sender="postmaster@www1.g3.pair.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AncNAKDXHlNCJwNzY2dsb2JhbABag0GIOqxJOohLhAWBNAMYBw4IPIIlAQEBAwF5BRY0aRSHdggN0HcXjlwHFoQiBJhEAYEylCg9
X-IPAS-Result: AncNAKDXHlNCJwNzY2dsb2JhbABag0GIOqxJOohLhAWBNAMYBw4IPIIlAQEBAwF5BRY0aRSHdggN0HcXjlwHFoQiBJhEAYEylCg9
X-IronPort-AV: E=Sophos;i="4.97,629,1389740400"; 
   d="scan'208";a="52104422"
Received: from www1.g3.pair.com ([66.39.3.115])
  by mail3-smtp-sop.national.inria.fr with SMTP; 11 Mar 2014 10:32:36 +0100
Received: (qmail 92384 invoked by uid 9370); 11 Mar 2014 09:32:35 -0000
Date: 11 Mar 2014 09:32:35 -0000
Message-ID: <20140311093235.92383.qmail@www1.g3.pair.com>
From: oleg@okmij.org
To: bob.atkey@gmail.com
CC: caml-list@inria.fr
In-reply-to:
	<CA+aevF_n0T1FQeka029scoXKy2dd+j3RWVeQUp988+UVgL6kmQ@mail.gmail.com>
Subject: Re: [Caml-list] I never succeeded in using Format


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