From: Robert Feldt <feldt@...>
Date: 2002-01-14T21:56:57+09:00
Subject: Re: MetaRuby : RubySchema.rb howto?

On Mon, 14 Jan 2002, Tanaka Akira wrote:

> > Ok, then there are some simplifications because the standard funcprog
> > pretty-printing libraries are known to have non-linear complexities.
> 
> Since Wadler's pretty printing is very simple, I think it is possible.
> (I think it is simplest.)
> 
Maybe. A too simplistic test by running the file:

require 'pp'

def nested_array(depth, len = 5)
  res = []
  depth.times {
    new_res = Array.new(len).map {rand(10)}
    new_res[rand(len)] = res
    res = new_res
  }
  res
end

GC.disable
start = Process.times.utime
PP.pp(nested_array(ARGV[0].to_i), 79, out = "")
puts "#{Process.times.utime - start} seconds"

seems to suggest it's not linear but its unclear since it fails when
more than 1200 nested arrays:

ruby pp_test.rb 50          0.13 seconds
ruby pp_test.rb 100         0.28 seconds
ruby pp_test.rb 500         1.862 seconds
ruby pp_test.rb 1000        4.767 seconds
ruby pp_test.rb 1200        6.279 seconds

But the size of these data is very large so in practice it should be
linear. Good work!

> >     [1, 2, 3, 4,
> >      5, 6, 7]
> > 
> >   which I think is a bit nicer.
> > 
> > Would it be possible?
> 
> Impossible, I think.
> 
Hmm, then I agree we need more powerful lib since the two alternatives
below are not very "pretty" (well the first is but for longer arrays).

> Because breakable positions contained by a (non-nested) group cannot
> mix spaces and breaks.
> 
> I think we needs more powerful library.  Although I don't know which
> algorithm is better: extention to Wadler's or other algorithms.
>
Me neither. But since we could implement the BalancedGroup constructor by
hand I think the chosen algorithm/extension should be able to support
it. Another constructor we'd need would be FilledGroup which fills from
group until end of line and then continues filing (with the
left-indentation we discussed previously) on the next line. I think these
two are mong the most used constructs.

In the example above FillGroup would give (we're assuming a width of 20
here):

   [1, 2, 3, 4, 5, 6,
    7]

 while BalancedGroup would give
 
   [1, 2, 3, 4,
    5, 6, 7]

 while the current lib would do

   [1,
    2,
    ...,
    7]

I think we need at least FillGroup. BalancedGroup might be overkill.

Could you describe the current "imperative" implementation of Wadler's
lazy pretty-print library? It feels like we can probably get away with
extending the current approach...

Anyone else got pointers to good pretty-printing libs?

Regards,

Robert