One approach to making numerical algorithms easier to write and understand is to provide a high-level library of polymorphic container types and higher-order functions for manipulating collections of data. Although polymorphic functions and data types are a common feature of programming languages, programming language implementations conventionally rely on compile-time knowledge of data layout when generating machine code.  Ensuring that sizes are known at compile time requires boxing objects, which sacrifices performance; dynamically compiling functions, which requires heavyweight runtime support; prohibiting first-class polymorphism, which limits expressiveness; or using a predetermined set of monomorphic data types, which limits the range of usable types.

To use efficient data layouts in statically compiled polymorphic code without limiting the use of polymorphism, we propose a low-level language that allows object sizes to depend on run-time type information.  This language is used as an intermediate language in our prototype compiler, Triolet.  So that users do not need to be aware of the details of data layout and object sizes, we further propose a translation from a high-level, fully boxed language to the internal language. To evaluate Triolet, we measured the performance of a number of functional numerical algorithms.  These algorithms use a library of data types and functions, some of which utilize first-class polymorphism. These algorithms achieve 52% of the performance of equivalent monomorphic implementations in C, often allocating the same amount of memory. In contrast, using boxed arrays slows down Triolet by 2.87 times. These results demonstrate that it is possible to achieve efficient data layout in this style of numerical code, and good data layout is key to achieving good performance.