Static Type Inference in a Dynamically Typed Language

We present a type inference system for FL based on an operational, rather than a denotational, formulation of types. The essential elements of the system are a type language based on regular trees and a type inference logic that implements an abstract interpretation of the operational semantics of FL. We use a non-standard approach to type inference because our requirements|using type information in the optimization of functional programs|dier substantially from those of other type systems.