The Y combinator for computing fixed points can be expressed in Standard ML. It is frequently used as an example of the power of higher-order functions, but is not generally regarded as a useful programming construction.
Here, we look at how a programming technique based on the Y combinator and wrappers can give programmers a level of control over the internal workings of functions not otherwise possible without rewriting and recompiling code.
As an experiment, the type-inference algorithm W is implemented using this technique, so that error messages are produced with minimum interference to the algorithm. The code for this example program illustrates the genuine usefulness of the concepts and the ease with which they can be applied. A number of other implementation techniques and possible applications are also discussed, including the use of higher-order functions to simulate the use of exceptions and continuations.ECS-LFCS-97-375.
This report is available in the following formats: