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)

The Worker/Wrapper Assumptions

There are several different possible worker/wrapper assumptions. The three given in the worker/wrapper paper are

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

The Worker/Wrapper Fusion Rule

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

The Worker/Wrapper Transformation

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, Journal of Functional Programming, 19(2):227-251, March 2009.

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