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-differ substantially from those of other type systems.