A Type-Based Compiler for Standard ML

Abstract:

Compile-time type information should be valuable in efficient compilation
of statically typed functional languages such as Standard ML. But how
should type-directed compilation work in real compilers, and how much
performance gain will type-based optimizations yield? In order to support
more efficient data representations and gain more experience about
type-directed compilation, we have implemented a new type-based middle
end and back end for the Standard ML of New Jersey compiler. We describe
the basic design of the new compiler, identify a number of practical
issues, and then compare the performance of our new compiler with the old
non-type-based compiler. Our measurement shows that a combination of several
simple type-based optimizations reduces heap allocation by 36\%; and improves
the already-efficient code generated by the old non-type-based compiler by
about 19\% on a DECstation 5000.

This technical report has been published as

A Type-Based Compiler for Standard ML. Zhong Shao and Andrew
W. Appel, Proc. 1995 ACM Conf. on Programming
Language Design and Implementation, (ACM
SIGPLAN Notices vol. 30, number 6), pp. 116-129,
June 1995.