Re: [Groff] Formatting algorithm

[Ulrich Lauther]

On Sun, May 04, 2014 at 02:59:19PM -0400, Doug McIlroy wrote:
> >  I don't see why any forking should be needed.
> 
> I am all ears. I'd love to know a better way to cope with events
> that are triggered by line breaks, when several different potential
> line breaks are in play, as were discussed in my posting to which
> Peter's referred. Forking is certainly unappealing, though in the
> future of multicore processors it may not be as daunting as before.
> 
> It seems there's an awful lot of state that may potentially vary
> with line breaks. Forking is an easy way to cope. My question
> remains: is there a better way?
> 
> Doug

In dynamic programming we maintain a set of optimum partial solutions,
each stored as a node in an acyclic directed graph. Edges of the graph
indicate from which partial solution an extended partial solution was
derived.
Finally we end up with a set of complete solutions, pick the best one
and follow the path in the graph to recover the decisions made to
arrive at this best solution.
Afterwards all nodes of the graph a thrown away, i.e., they can be used to
solve the next problem - in our case, the next paragraph.
Often, useless nodes can already be discarded before the final solution
is found.

All this could possibly also be implemented using recursion and/or forking,
but that would be less efficient (in terms of memory and running time needs)
and - in my opinion - also harder to understand.

Kind regards,

     ulrich