1987 · 15 citations · 12 references
ComputingComputer ScienceAlgorithmsProgramming LanguagesSyntaxData TypesFormal SemanticsType CheckingType SystemsInference RulesLambda CalculusStatic Type CheckingType InferenceType TheoryTyped Lambda Calculus
We study the strictness problem for the untyped lambda-calculus and for an ML-like typed calculus. We establish that strictness is a necessary and sufficient condition for the “eager” evaluation of function arguments. For the untyped calculus, we show that the strictness problem is elementary and describe a complete algorithm for strictness analysis of convergent terms. We show that typed terms possess a much richer set of strictness properties. A type-theoretic characterization of strictness is developed and it is shown that the strictness properties of a term can be represented as a collection of types related to the standard term type. A set of type inference rules that support reasoning about strictness related types is given. The inference rules are shown to be invariant under type change by substitution. This provides a sound basis for reasoning about strictness properties of terms by considering only their principal type. For our final result, we describe a practical system that carries out type checking and strictness analysis simultaneously in a unified framework. Our main result is thus the discovery that the problem of strictness analysis is a particular case of type inference.
12
A theory of type polymorphism in programming
Robin Milner · Journal of Computer and System Sciences · 1978 · 2.2K citations · Full text
Robert Kowalski, Steve Smoliar · ACM SIGSOFT Software Engineering Notes · 1982 · 1.2K citations
Principal type-schemes for functional programs
Robin Milner · 1982 · 1.1K citations
Efficient compilation of lazy evaluation
Thomas Johnsson · 1984 · 226 citations