Treat is a special purpose language for use in compiler writing. A Treat program translates a graph into c-trees (the intermediate language of the pcc compiler) and uses the back end of the C compiler to generate code. Treat has been developed specifically for use in an AdaTM compiler. A Treat program consists of applicative transformation rules. Treat's distinctive aspects include triggering transformations during pattern matching, a context mechanism for dynamic binding and assignment in a language with lazy evaluation.

This paper studies two approximation algorithms for packing rectangles, using the two-dimensional packing model of Baker, Coffman and Rivest [SIAM J. Comput., 9 (1980), pp. 846–855]. The algorithms studied are called next-fit and first-fit shelf algorithms, respectively. They differ from previous algorithms by packing the rectangles in the order given; the previous algorithms required sorting the rectangles by decreasing height or width before packing them, which is not possible in some applications. The shelf algorithms are a modification of the next-fit and first-fit decreasing height level algorithms of Coffman, Garey, Johnson and Tarjan [SIAM J. Comput., 9 (1980), pp. 808–826]. Each shelf algorithm takes a parameter r. It is shown that by choosing r appropriately, the asymptotic worst case performance of the shelf algorithms can be made arbitrarily close to that of the next-fit and first-fit level algorithms, without the restriction that items must be packed in order of decreasing height. Nonasymptotic worst case performance bounds are also investigated.

The use of annotated recursion equations as a programming technique is investigated by considering the "telegram problem." The annotations are used to select alternative strategies for evaluating the applicative expressions contained in the recursion equations, while the equations serve as an abstract specification of the desired results. This method has the advantage that the annotations explicitly display certain kinds of decision that would otherwise be implicit.