Data-flow analysis and type recovery in Scheme

Abstract: "The lack of explicit type information in Scheme prevents the application of many compiler optimizations. Implicit type information can oftentimes be recovered by analyzing the flow of control through primitive operations and conditionals. Such flow analysis, however, is difficult in the presence of higher-order functions. This paper presents a technique for recovering type information from Scheme programs using flow analysis. The algorithm used for flow analysis is semantically based, and is novel in that it correctly handles the 'environment flow' problem. Several examples of a working implementation of the analysis are presented.The techniques are applicable not only to Scheme type recovery, but also to related languages, such as Common Lisp and Standard ML, and to related data-flow analyses, such as range analysis, future analysis, and copy propagation."