Typesetting program

From: Johan Boye <jb_at_sectra.se>
Date: Fri, 04 Jul 1997 11:43:32 +0200

Hi everyone,
Speaking about applications, Harold Boley suggested that I send
the following typesetting program example to the mailing list.
The program is really an illustration of how residuation can be
used. To solve the same problem in Prolog would require either a
less efficient solution (two passes over the input), or the use
of meta-programming and "dirty" features. To solve the problem in
a conventional language (like C) would either require a two-pass
solution or the use of pointers. (By the way, the same kind of
situation frequently arises in when constructing compilers and
assemblers). The example might take some time to digest. Hope
you'll find it worth the effort. (If you have questions, please
write soon, as I'm leaving for vacation this afternoon!)

Unfortunately I am not familiar with the Curry syntax, so I will
use my own (me too!). The syntax used in the example is Prolog where
some contructors have a functional interpretation (I have not
written the definitions of the functions). The operational semantics
is the one of Prolog + reduction of ground functional calls.
Non-ground functional calls residuate until the arguments become
ground. (This is explained in more detail in the article Harold
quoted).

Regards,
Johan Boye.


The problem
-----------
Write a program that typesets tables as follows. The input consists
of a list of lists, e.g.

[[this, is, some, text], [another, line, of, text]]

The output should be a list of typesetting commands:

[[put(1,1,this), put(1,8,this), put(1,12,some), put(1,16,text)],
 [put(2,1,another), put(2,8,line), put(2,12,of), put(2,16,text)]]

representing the table

this is some text
another line of text

The crux is the column indentation: every column should have the
width of the longest word in the column, so the widths of the
columns cannot be computed until the whole input has been processed.
Still, it is possible to solve the problem in one pass.


A solution
----------
The idea is to construct the output list of typesetting commands as
the input is processed, but put logical variables as placeholders
for the column widths. The logical variables are bound to the results
of function calls which residuate until the the whole input is
processed. Thus the program computes with non-ground data structures,
but at the end of computation everything becomes instantiated.

The predicate typesetrow/6 typesets one row in the program:


typesetrow(_, _, [], [], [], []).

typesetrow(Line, Ind, [Text|Ts], [ColWid|Cs], [size(Text)|Ss],
            [put(Line, Ind, Text)|Insts]) :-
   typesetrow(Line, Ind+ColWid, Ts, Cs, Ss, Insts).


'+' and 'size' are functions, the latter returning the number of
characters of its argument. The arguments represent (from left to
right) the current line number,
       the current indentation on the line,
       a list describing one row in the table
              (e.g. [this, is, some, text]),
       a list containing the widths of all columns,
       a list containing the number of chars of each item in the row,
       the output list of typesetting commands.

As we will see, the list of widths of all columns will be non-ground
at when this predicate is called, so every instance of the function
call Ind+ColWid will residuate.

typesetrow/6 is called from typesettab/5:


typesettab(_, [], X, X, []).

typesettab(Line, [Row|Rows], ColWidths, WidSoFar, [InstsRow|Insts]) :-
  typesetrow(Line, 1, Row, ColWidths, Widths, InstsRow),
  compute_max(Widths, WidSoFar, NewWidSoFar),
  typesettab(Line+1, Rows, ColWidths, NewWidSoFar, Insts).


The arguments represent (from left to right):
      the current line number
      the list of lists describing the whole table
      a list containing the widths of each column
      a list containing the widths of the widest item in
            each column in the row processed so far
      the output list of typesetting instructions

The predicate compute_max is a predicate that, given two lists of
integers [i1,...,in] and [j1,...,jn] in the two first arguments,
produces the list [max(i1,j1),...,max(in,jn)]. Its definition is
straightforward.

An example query to the program is

typesettab(1, 1, [[this,is,some,text],[another,line,of,text]],
           _, [0,0,0,0], I).

which will succed, binding the variable I to the list of typesetting
commands listed in the beginning of the example.
Received on Fr Jul 04 1997 - 13:49:00 CEST