The Worker/Wrapper Transformation

If comp :: A is defined by comp = fix body for some body :: A->A, and wrap :: B->A and unwrap :: A->B satisfy any of the worker/wrapper assumptions, then

comp = wrap work
where work :: B is defined by
work = fix (unwrap . body . wrap)

If wrap . unwrap = id_A, then (unwrap . wrap) work = work

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.

This web page is a central repository for people using or wanting to understand the worker/wrapper transformation.

Papers

The Worker/Wrapper Transformation, Andy Gill and Graham Hutton, submitted for publication in JFP

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 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.

Other Resources

Changes and Suggestions?

These pages are stored as a darcs repo. Feel free to email editor@workerwrapper.comwith changes or darcs patches. The darcs repo can be downloading using

$ darcs get http://www.workerwrapper.com

wrap . unwrap	= id	(basic assumption)
wrap . unwrap . body	= body	(body assumption)
fix (wrap . unwrap . body)	= fix body	(fix-point assumption)

The Worker/Wrapper Theorem

The Worker/Wrapper Assumptions

The Worker/Wrapper Fusion Rule