Ī»ā¶ (pronounced Lambda Mountain) is a compiler backend that provides a relatively clean implementation of System F<: with Specialization. The language is intended only as an intermediate form, so this project is more similar to GCC than to C.
More information is available on the Ī»ā¶ Wiki.
If we have several overloaded functions then specialization lets us choose the best fit for any particular application.
f := Ī»(: x X). x;
f := Ī»(: y Y). y;
f (: x X)
In this example the function application does not āfitā the application that expects a Y type argument, so there is only one possible candidate function.
type X implies Y;
f := Ī»(: x X). x;
f := Ī»(: y Y). y;
f (: x X)
Now both candidate functions āfitā, however X is a narrower type than Y. All X are Y, but not all Y are X. In this case we say that X is a ābetter fitā than Y.
f := Ī»(: x X). form 1;
f := Ī»(: x X). form 2;
f (: x X)
In this example both candidate functions āfitā AND are equivalent. In this case we apply metrics to determine the best fit. A metric is an order that can be applied to term/type pairs to determine which is a ābetter fitā in non-semantic cases. Metrics are very useful when there exist multiple equivalent forms of code representation that have different performance characteristics.
Specialization allows us to express high-level ideas at the level of a generic functional language AND compile the code down to machine code transparently. There are no hidden layers in the compiler. The programmer gets to inspect and verify every single transformation down to individual instructions.
LM soundly integrates several features that are useful but historically hard to combine. The type system is not decidable in the general case. However, by providing type annotations on all overloaded functions it becomes decidable.
- Higher Order Functions (Functional Programming)
- Parametric Polymorphism (Generic Programming)
- Subtyping (Object Hierarchies)
- Ad-Hoc Polymorphism (Function Hierarchies)
- Plural Types (Types behave more like logical predicates)