Language design

Philip Wadler

How to add laziness to a strict language, without even being odd

Philip Wadler, Walid Taha, and David MacQueen. Workshop on Standard ML, Baltimore, September 1998.

There are two styles of lazy evaluation, one (called `odd') that is easy to encode in the traditional `delay' and `force' syntax, but forces too much evaluation, and another (called `even') that delays evaluation as in traditional lazy languages, but is harder to encode. This note presents a new `lazy' syntax, and shows how the even style is easy to encode in this syntax, while the odd style is harder to encode. The new `lazy' syntax is defined by translation into the `delay-force' syntax. Comparisons are drawn with two other syntaxes, one used in CAML and one proposed by Chris Okasaki.

Available in: dvi, ps, dvi.gz, ps.gz.


A prettier printer

Philip Wadler. The Fun of Programming. A symposium in honour of Professor Richard Bird's 60th birthday Examination Schools, Oxford, 24-25 March 2003. (Original paper April 1997, revised March 1998.)

John Hughes has made pretty-printers one of the prime demonstrations of using combinators to develop a library, and algebra to implement it. This note presents a new design for pretty printers which improves on Hughes's classic design. The new design is based on a single concatenation operator which is associative and has a left and right unit. Hughes's design requires two separate operators for concatenation, where horizontal concatenation has a right unit but no left unit, and vertical concatenation has neither unit.

Available in: pdf.


Views: a way for pattern matching to cohabit with data abstraction

Philip Wadler. 14'th ACM Symposium on Principles of Programming Languages, Munich, Germany, January 1987.

Pattern matching and data abstraction are important concepts in designing programs, but they do not fit well together. Pattern matching depends on making public a free data type representation, while data abstraction depends on hiding the representation. This paper proposes the views mechanism as a means of reconciling this conflict. A view allows any type to be viewed as a free data type, thus combining the clarity of pattern matching with the efficiency of data abstraction.

Available in: dvi, ps, dvi.gz, ps.gz


A new array operation

Philip Wadler. Proceedings of the Workshop on Graph Reduction, Santa Fe, New Mexico, J. Fasel and R. Keller, editors, Springer-Verlag, October 1986.

Providing efficient operations on arrays in a functional language is problematic. No completely satisfactory solution has yet been found. This paper proposes a new solution, which is a variant on the ``monolothic'' approach to array operations. The new solution is also not completely satisfactory, but does have advantages complementary to other proposals. It makes a class of programs easy to express, notably those involving the construction of histograms. It also allows for parallel implementations without the need to introduce non-determinism.

Available in: dvi, ps, dvi.gz, ps.gz


The concatenate vanishes

Philip Wadler. Note. December 1987 (revised, November 1989).

This note presents a trivial transformation that can eliminate many calls of the concatenate (or append) operator from a program. The general form of the transformation is well known, and one of the examples, transforming the reverse function, is a classic. However, so far as I am aware, this style of transformation has not previously been systematised in the way done here. The transformation is suitable for incorporation in a compiler, and improves the asymptotic time complexity of some programs from quadratic to linear. There is a syntactic test that determines when the transformation will succeed in eliminating a concatenate operation.

Available in: dvi, ps, dvi.gz, ps.gz, pdf.


Derivation of a pattern matching compiler

Geoff Barrett and Philip Wadler. Note. 1986.

This paper presents the derivation of an efficient compiler for pattern-matching in a functional language. The algorithm was published, independently, by Augustsson and Wadler, and is used in the LML compiler. The derivation is based on that given in Barrett's M.Sc. dissertation The algorithm relates to functional languages in two ways: a functional language is used as the medium of the derivation, and the algorithm is useful for compiling functional languages.

Available in: dvi, pdf.


Philip Wadler,