Binding-Time Analysis for Standard ML.
Lars Birkedal, Morten Welinder · 1994
. We present an efficient base algorithm for binding-time analysis based on constraint solving and the union-find algorithm. In practice it has been used to handle all of Standard ML except modules and we show the principles of how constraints can be used for binding-time analysis of Standard ML; in particular we show how to binding-time analyse nested pattern matching. To the best of our knowledge no previous binding-time analysis has treated nested pattern matching. Keywords: binding-time analysis, partial evaluation, Standard ML. 1. Introduction There are two commonways of doing binding-time analysis: by fixed-point iteration and by constraint solving. Analyses based on the former method tend to be stronger as proven by Palsberg and Schwartzbach [11], but have so far been rather slow --- cubic complexity for higher-order languages --- and thus impractical for large programs. Analyses based on the latter method are as fast as we can expect --- essentially linear-time complexity ---...