Lambda the Ultimate

I'm very interested in the order in which various "typical" FP compiler optimizations are performed.

For example, lambda-lifting vs. closure creation vs. parameter augmentation vs. beta reduction vs. escape analysis vs. pattern match simplification and optimization vs. representation selection for things like nullary constructors (True | False, etc.) within algebraic data types vs. stack map generation/consolidation for precise GC of call frames vs. any potential "name mangling" to support some linking policy - and so on and so forth.

I'm very curious what other typical "high level" optimizations either 1) are typical or 2) not so typical, but can add greatly to performance - emphasizing again, at some "higher level" IR and typical of mostly-functional languages.

Any information on compilation of functional array processing languages (APL or J or something else?) would also greatly peek my interest, as I'm curious about achieving "competitive" numerical performance in a functional language context.

Let's call the above compiler IR(s) and optimizations the "FP stuff" - presumably, prior to some future transformation to basic-blocks-of-quads (and perhaps SSA and so on), i.e. some lower level IR(s), upon which the compiler performs a more "traditional" (and relatively, very well documented) set of "low level" compiler optimizations .

My little personal "language lab" happens to be strict, just in case that matters.

Many thanks!

Scott

Vincent Cremet and Philippe Altherr: Adding Type Constructor Parameterization to Java, JOT vol. 7, no. 5.

We present a generalization of Java’s parametric polymorphism that enables parameterization of classes and methods by type constructors, i.e., functions from types to types. Our extension is formalized as a calculus called FGJ_ω. It is implemented in a prototype compiler and its type system is proven safe and decidable. We describe our extension and motivate its introduction in an object-oriented context through two examples: the definition of generic data-types with binary methods and the definition of generalized algebraic data-types. The Coq proof assistant was used to formalize FGJ_ω and to mechanically check its proof of type safety.

FGJ_ω is a simple extension of (Featherweight) Java's generics, where type parameters may be type constructors (functions from types to types). This very readable paper finally made me understand GADTs.

(Previously: Generics of a Higher Kind on Scala's support for the same idea.)