Monomorphization and dynamic dispatch are two common techniques for implementing polymorphism in statically typed programming languages. Function templates in C++ use the former technique to enable algorithms written as generic functions to be efficiently reused with multiple different data types by producing a separate function instantiation for each invocation that uses a unique permutation of argument types. This avoids the overhead of indirection associated with dynamic dispatch and allows the generated code of each instantiation to be optimized by the compiler for its specific concrete types, which typically yields great improvements in runtime performance over any dynamic approach. The disadvantage of this implementation, compared to the type-erased generics found in many other programming languages, is that careless over-use of templates with many different argument types can lead to an excessive amount of redundant code being generated for the same function. This increase in code size may increase the binary size of the final program and reduce the amount of useful code that can fit into the processor's instruction cache during execution, reducing code locality and thereby potentially reducing performance. Monomorphization can also increase compilation time due to the increase in generated code that needs to be compiled and optimized. This thesis presents a heuristic-based approach to generic programming that allows function templates to be automatically converted to use dynamic dispatch in scenarios where the resulting negative impact on runtime performance is predicted to be low. The thesis project includes the development of a proof of concept plugin for the Clang compiler frontend that can be used to compile existing C++ projects with the conversions applied. The design of a heuristic function for determining whether a given function template should use monomorphization or dynamic dispatch based on statically known metrics is proposed based on the results of an experiment. This heuristic is shown to achieve a small general improvement in program size across a set of open-source C++ projects when they are compiled using the plugin. The key findings from the experiment and from the development of the plugin are summarized with a general strategy for how the approach can be integrated into the design of future programming languages to promote more extensive use of generic programming in performance-sensitive code while avoiding regressions in program size and compilation time.

[pt] Se diz que uma linguagem de programação tem funções de primeira classe quando ela fornece a capacidade de manipular funções da mesma maneira que outros valores, isto é, guardar em variáveis, passar como parâmetros, etc.. Programar com funções de primeira classe abre o programadora novas formas de abstração e é o padrão em linguagens de programação funcionais. Porém, se tratando de linguagens imperativas (incluindo linguagens orientadas a objeto), cada linguagem tem semântica, propriedades e terminologia diferentes para funções—em grande parte graças a seu foco em mutabilidade, que as linguagens funcionais não têm. Para esclarecer essas diferenças, nós fizemos um levantamento sobre a especificação de funções como valores em linguagens de programação imperativas de várias disciplinas diferentes. Para cada linguagem, nós ilustramos, nos baseando em exemplos, as propriedades dos valores de funções nela,destacando onde ela difere de outras linguagens—tudo isso usando uma terminologia consistente em todas as linguagens. Nós esperamos oferecer uma referência para desenvolvedores compararem e contrastarem as diferentes versões de funções num só lugar. / [en] A programming language is said to have first-class functions when it provides the capability of manipulating functions in the same way as other values, i.e., storing in variables, passing as parameters, etc.. Programming with first-class functions opens the programmer to new forms of abstractions and it s the default in functional programming languages. However, in the realm of imperative languages (including object-oriented languages), each language has different semantics, properties, and terminology for functions—in great part, thanks to their focus on mutability, which isn t present in functional languages. To help shed light on these differences, we made a survey of the specifi-cation of function values in imperative programming languages from many different disciplines. For each language, we illustrate, based on examples,the properties of function values in it, highlighting where it differs from other languages—all this with a consistent terminology in all languages. We provide a reference that compares and contrasts different renditions offunctions in one single place and conclude that the design of functions in a language depends on the interaction of its features and constraints with its functions.