Lambda the Ultimate

inactiveTopic Typing Dynamic Typing
started 12/18/2002; 2:42:07 AM - last post 12/18/2002; 2:42:07 AM
Frank Atanassow - Typing Dynamic Typing  blueArrow
12/18/2002; 2:42:07 AM (reads: 403, responses: 0)
Arthur I. Baars and S. Doaitse Swierstra. Typing Dynamic Typing. Proc. ICFP '02, 2002.

We show how, by a careful use of existentially and universally quantified types, one may achieve the [effect of dynamic typing], without extending the language with new or unsafe features. The techniques explained are universally applicable, provided the core language is expressive enough; this is the case for the common implementations of Haskell. The techniques are used in the description of a type checking compiler that, starting from an expression term, constructs a typed function representing the semantics of that expression. In this function the overhead associated with the type checking is only once being paid for; in this sense we have thus achieved static type checking.

They construct a calculus of proofs of type equality. A dynamically typed value is a value paired with a representation of its type. It is eliminated by passing a representation of the expected type, and exhibiting a witness proof that shows the expected type is equal to the one stored with the value.