Quick links

Literate Programming Tools Need Not Be Complex

Report ID:
September 1991
Download Formats:


When it was introduced, literate programming meant WEB. Desire to use
This thesis presents research done by the author on competitive analysis of
on-line problems.
An on-line problem is a problem that is given and solved one piece at a time.
An on-line strategy for solving such a problem must give the solution to each
piece knowing only the current piece and preceding pieces, in ignorance of the
pieces to be given in the future.
We consider on-line strategies that are competitive (guaranteeing
solutions whose costs are within a constant factor of optimal) for several
combinatorial optimization problems: paging, weighted caching, the k-server
problem, and weighted matching.
We introduce variations on the standard model of competitive analysis for
paging: allowing randomization, allowing resource-bounded lookahead, and
loose competitiveness, in which performance over a range of fast memory
sizes is considered and noncompetitiveness is allowed provided the fault rate
is insignificant. Each variation leads to substantially better competitive
We present a general technique for competitive analysis of linear optimization
problems: competitive analyses are obtained by using linear programming
duality to obtain bounds on the optimal cost. The technique is implicit in
previous work on paging, weighted caching, and weighted matching. We
generalize the implicit previous use of the technique, obtaining the
greedy dual algorithm for weighted caching. The strategy generalizes the
least-recently-used and first-in-first-out algorithms for paging and the
balance algorithm for weighted caching. The analysis strengthens a previous
analysis of the balance algorithm for weighted caching.
We explore the linear programming dual of the k-server problem, showing that
the k-server problem is a special case of on-line minimum-weight matching,
revealing close relationships between on-line weighted caching and assignment
algorithms, and showing how duality can yield potential function analyses.
WEB with languages other than Pascal led to the implementation of many
versions. WEB is complex, and the difficulty of using WEB creates an
artificial barrier to experimentation with literate programming.
noweb provides much of the functionality of WEB, with a fraction of
the complexity. noweb is independent of the target programming
language, and its formatter-dependent part is less than 40~lines.
noweb is extensible, because it uses two representations of programs:
one easily manipulated by authors and one easily manipulated by tools.
This paper explains how to use the { t noweb} tools and gives
examples of their use. It sketches the implementation of the tools
and describes how new tools are added to the set. Because { t WEB}
and { t noweb} overlap, but each does some things that the other
cannot, this paper enumerates the differences.

Follow us: Facebook Twitter Linkedin