-
Levity: The property of a expression to have bottom (⊥) as part of its potential results. For example, an expression of type Bool can evaluate to the following values: True, False, ⊥. Expressions that do not allow for bottom are unlifted. As a result, an unlifted value is never lazy, but can still be boxed.
-
Boxity: The property of a value to be passed as a pointer (boxed), or directly (unboxed). For example:
- Int is boxed, at it is a pointer to its data that you have to follow
- Int# is unboxed, as we pass the literal data in the register
-
Representation Polymorphism (rep-polymorphism):
The particular combination of levity and boxity of a value.
Values declare their particular combination of levity and boxity by using type-level markers like:
-
TYPE LiftedRep : The lifted, boxed values we know and love
-
TYPE UnliftedRep : Unlifted, boxed values that still contain a pointer to the data
-
TYPE IntRep/WordRep/AddrRep: The Unlifted, unboxed values.
Examples An example of combining different levels of levity and boxity is the case of SmallMutableArray#, an unlifted yet boxed type. It is a pointer that points to a memory area that knows its own length The array itself is evaluated, even though its content may not be
Another example is the 2-tuple pair: As a common (a, b) pair, it is boxed and points to a 2-elements array. As an unboxed pair, each member is a copy of the data.
Concerning its content, it could be of type Int, or Int#:
A boxed pair of Int would be two registers with a pointer in each register An unboxed pair of Int# would be two registers with integer data in them
Corollary: If you are unboxed, you cannot be lifted.
| Levity / Boxity | Boxed | Unboxed |
|---|---|---|
| Lifted | Normal Haskell values | Impossible |
| Unlifted | A pointer to a non-bottom, strict value | The raw strict value |
If I know your representation, I know how to pass you to a function (calling convention)
If I know the representation of your arguments, I know how to compile you
Golden Rule: We cannot have rep-polymorphic variables and functions that operate on such variables are un-implementable
Problem
Representation Polymorphism today is a second-rate feature, as we do not know how to pass representation-polymorphic variables to functions. But typeclass methods are exempt from this limitation. As such we cannot really define anything in a representation-polymorphic way without Typeclasses.
However, some Typeclasses from base have the potential to be rep-polymorphic. For example, Eq would be “free”. However (/=) as a function would be impossible because it is not a class method anymore (see Golden Rule).
As such, the most we can manage is to be rep-polymorphic in the return types.
If a Typeclasse is rep-polymorphic, when we define an instance, by default we have to choose the representation. The typeclass method is not one function but one function instance.
For the typeclass it looks like it's polymorphic, but typeclass methods are not just "method", but rather a triplet of (Typeclass, Instance type, Method).
Upside: Typeclasses are a prime gateway to use rep-polymorphic functions and types
Downside: There isn't any other mechanism to use rep-polymorphic functions and types -> We can't have default implementations (we would have to bind variables) -> We can't have default implementations in terms of other typeclass methods (like {get, put | state} in StateT)
As such, representation polymorphism today is an area of the extended Haskell language that has benefitted from spurious occasional improvements, but we do not have any design or strategy as a whole. Wiki pages exist , but these documents do not meet the quality requirements for design documents.