Translation by Instantiation: Integrating Functional Features into an Imperative Language

In this paper, we present an imperative language enhanced with higher-order functions, function currying and a polymorphic type system. This enables high-level programming, as known from functional languages. On the other hand, this language can be efficiently implemented, by translating the functional features into constructs of the imperative base language. An instantiation procedure generates for each (polymorphic) higher-order function one or more monomorphic first-order functions. Since the transformation is done at compile-time, we have to make a restriction with respect to the functional arguments of recursively-defined higher-order functions. 1 Introduction Efficiency is a crucial issue in the implementation of functional languages, since the acceptance of these languages depends to a large extent on their performance. One way to raise this efficiency is to enhance functional languages with imperative features. The integration of the two programming paradigms thus represents ..