[m-dev.] diff: use pretty printer in mdb

Ralph Becket rbeck at microsoft.com
Wed May 24 02:37:15 AEST 2000


> From: Mark Anthony BROWN [mailto:dougl at cs.mu.OZ.AU]
> Sent: 23 May 2000 16:27
> 
> That's true, but notice that the condition of the if-then-else below
> still contains the call to fits/2, which considers the succeeding docs
> as well as the flattened group.  So my solution would handle this
> situation correctly.

Sorry - missed that.

> Fergus pointed out that my solution overflows the det stack when
formatting
> very large terms (eg. dumping the MLDS).  I believe this is caused by
> the way be/3 traverses the tree---there is one level of recursion for
> every node in the document, due to the way 'SEQ' is handled in the
> third clause.  Unfortunately, both our solutions have this problem,
> and I can't see an easy way of dealing with it.

Umm, I don't think that's the problem.  be/3 is tail recursive everywhere
except at the point where it handles the `TEXT' and `LINE' primitives.
We could work around this one by adding an accumulator argument, collecting
all the text and newline+indents in a list and reversing the whole thing at
the end of the day.

That really wouldn't be too hard, come to think of it...

I've just tried it out and done some profiling.  Both versions seem to take
the same amount of space and time on the test data I've thrown at it (which
includes full binary trees up to 8 ply deep.)  However, the time profiles
suggest (by distribution) that the accumulator version has the edge and
remind me that string__duplicate/1 is coded in an absolutely mad way (it's
O(n^2)).

The new version of be/N is

    % Now, with accumulator!

:- pred be(int, int, list(pair(string, doc)), list(string), list(string)).
:- mode be(in, in, in, out, in) is det.

be(_, _, [], Out, In)             :-  Out = list__reverse(In).
be(W, K, [_ - 'NIL'         | Z]) --> be(W, K, Z).
be(W, K, [I - 'SEQ'(X, Y)   | Z]) --> be(W, K, [I - X, I - Y | Z]).
be(W, K, [I - 'NEST'(J, X)  | Z]) --> be(W, K, [extend(I, J) - X | Z]).
be(W, K, [I - 'LABEL'(L, X) | Z]) --> be(W, K, [string__append(I, L) - X |
Z]).
be(W, K, [_ - 'TEXT'(S)     | Z]) --> [S],  be(W, (K + string__length(S)),
Z).
be(W, _, [I - 'LINE'        | Z]) --> ["\n", I], be(W, string__length(I),
Z).
be(W, K, [I - 'GROUP'(X)    | Z]) -->
    ( if { flattening_works(X, Z, W - K) } then
        be(W, K, [I - flatten(X) | Z])
      else
        be(W, K, [I - X | Z])
    ).

I'm tempted to stick with this one since it *should* be more efficient,
being
tail recursive'n'all that (does the profiler measure stack usage?), and
simplifies simple_doc to just list(string), but I'm a little chary of the 
sneaky "reverse DCG"ism used to construct the output list.

Oh well, people have until tomorrow to scream, otherwise I'll check it in
then.

Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------



More information about the developers mailing list