Literate Programming Tools Need Not Be Complex
Report ID: TR-351-91Author: Ramsey, Norman
Date: 1991-10-00
Pages: 24
Download Formats: |PDF|
Abstract:
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 ratios. 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.