|
A Simple Solution to Type Specialization
Olivier Danvy January 1998 |
Abstract:
Partial evaluation specializes terms, but traditionally this
specialization does not apply to the type of these terms. As a
result, specializing, e.g., an interpreter written in a typed
language, which requires a ``universal'' type to encode expressible
values, yields residual programs with type tags all over. Neil Jones
has stated that getting rid of these type tags was an open problem,
despite possible solutions such as Torben Mogensen's ``constructor
specialization.'' To solve this problem, John Hughes has proposed a
new paradigm for partial evaluation, ``Type Specialization,'' based
on type inference instead of being based on symbolic interpretation.
Type Specialization is very elegant in principle but it also appears
non-trivial in practice.
Stating the problem in terms of types instead of in terms of type encodings suggests a very simple type-directed solution, namely, to use a projection from the universal type to the specific type of the residual program. Standard partial evaluation then yields a residual program without type tags, simply and efficiently. Available as PostScript, PDF, DVI. |