  The class of Basic Feasible Functionals BFF$_2$ is the type-2 counterpart of
the class FP of type-1 functions computable in polynomial time. Several
characterizations have been suggested in the literature, but none of these
present a programming language with a type system guaranteeing this complexity
bound. We give a characterization of BFF$_2$ based on an imperative language
with oracle calls using a tier-based type system whose inference is decidable.
Such a characterization should make it possible to link higher-order complexity
with programming theory. The low complexity (cubic in the size of the program)
of the type inference algorithm contrasts with the intractability of the
aforementioned methods and does not overly constrain the expressive power of
the language.
