The worker/wrapper transformation is a technique for transforming a computation of one type into a worker of a different type, together with a wrapper that acts as an impedance matcher between the original and new computations. The technique can be used to improve the performance of functional programs by improving the choice of data structures used.
The Worker/Wrapper transformation
This image is an abstract diagram explaining the worker/wrapper transformation, where arrows signify usage. The (smaller) boxes are computations that have a type, given as an incoming arrow on the left hand side, and require the use of a second computation, given as an outgoing arrow on the right hand side. These computational boxes can be considered representing functions with higher-order arguments. A and B should be read as providing a typed service by using the box to their right to provide this service.
The original computation is a recursive function, that is it uses itself, notated with a right arrow that arcs back to the type of the computation, A. The ultimate result is a wrapper and an optimized worker, which operates using a new type, B.
The worker/wrapper transformation operates as follows:
- A target type for the recursion is selected, called B.
- A coercion chain is constructed from two higher-order functions that coerce from A to B, and back to A.
- The worker/wrapper local preconditions are verified; one example is when abs and rep form an identity.
- The worker/wrapper transformation is applied, replacing then the original computation with the post worker/wrapper chain.
- This new formulation can be transformed and optimized using well understood local refinements into a worker that operates efficiently over B, and a wrapper abs that allows original users of A to call this new function.
This general pattern captures many possible transformations and refinements.
Example of using the Worker/Wrapper Transformation
...The transformation can be expressed formally, using fix points.
The Worker/Wrapper Theorem
where work :: B is defined by
work = fix (rep ο body ο abs)
The Worker/Wrapper Assumptions
There are several different possible worker/wrapper assumptions. The three given in the worker/wrapper paper are
| abs ο rep | = id | (basic assumption) |
| abs ο rep ο body | = body | (body assumption) |
| fix (abs ο rep ο body) | = fix body | (fix-point assumption) |
There is also another possible assumption, which uses the fixed point fusion rule (hence the name fpf assumption) and only holds for a strict wrap
| wrap ο rep ο body ο abs | = body ο abs | (fpf assumption) |
The Worker/Wrapper Fusion Rule
Papers
This paper introduces the Worker/Wrapper Theorem and the Worker/Wrapper Fusion Rule (see right sidebar) and applies the theorem to four examples.
- Unboxed values as first class citizens in a non-strict functional language, Simon L Peyton Jones and John Launchbury, FPCA 91.
This paper applies the Worker/Wrapper Theorem to folds.
This paper introduces the Worker/Wrapper Transformation using the application area of using strictness analysis to allow call-by-value in a non-strict language.
Use Cases
The Worker/Wrapper Transformation is surprisingly general! In has been applied to the following application areas.
- Using strictness information
- was the original motivating example for this transformation.
- CPS translation
- is just using an alternative representation for computation.
- Memoization
- is using a data-structure to represent a function.
- Accumulation
- is often possible when the result is a monoid; worker/wrapper enables this change of type.
- Constructor specialization
- creates specialized workers and wrappers.
- Cross-function short-cut fusion
- uses worker/wrapper to transmit fusion opportunities over function boundaries.
We expect there are many others.