In a Nutshell
LambdaCube 3D is a domain specific language and library that makes it possible to program GPUs in a purely functional style.
Purely Functional Rendering Engine
You probably know that lists and tuples are in no way special data types in Haskell. They are basically the following ADTs (algebraic data types) with special syntax:
data List a -- syntax in type context: [a] = Nil -- syntax in expression context:  | Cons a (List a) -- syntax in expression context: (a : as) data Tuple2 a b -- syntax in type context: (a, b) = Tuple2 a b -- syntax in expression context: (a, b) data Tuple3 a b c -- syntax in type context: (a, b, c) = Tuple3 a b c -- syntax in expression context: (a, b, c) data Tuple4 a b c d -- syntax in type context: (a, b, c, d) = Tuple4 a b c d -- syntax in expression context: (a, b, c, d) ...
All right, but what exactly does that ... mean at the end? Do infinite tuples exist? Or at least, are there infinitely many tuples with different arities? In the case of GHC the answer is no, and this is very easy to demonstrate. Try to enter this tuple in ghci:
GHCi, version 7.10.3: http://www.haskell.org/ghc/ :? for help Prelude> (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0) <interactive>:2:1: A 63-tuple is too large for GHC (max size is 62) Workaround: use nested tuples or define a data type
Although this seems reasonable, those who strive for perfection are not satisfied. What is the right solution for this problem? What is the real problem by the way?
I consider the Tuple2, Tuple3, Tuple4, … ADT family an inferior representation of tuples because of the following reasons:
What would be a better representation of tuples? Heterogeneous lists, of course!
data HList :: List Type -> Type where HNil :: HList 'Nil HCons :: forall t ts . t -> HList ts -> HList ('Cons t ts)
HNil :: HList 'Nil HCons True HNil :: HList ('Cons Bool 'Nil) HCons 3 (HCons True HNil) :: HList ('Cons Int ('Cons Bool 'Nil)
The syntactic sugar for heterogeneous lists could be the same as for tuples, for example
() ==> HNil -- in expression context () ==> HList 'Nil -- in type context (3, True) ==> HCons 3 (HCons True HNil) -- in expression context (Int, Bool) ==> HList ('Cons Int ('Cons Bool 'Nil) -- in type context
What are the issues of representing tuples by heterogeneous lists?
The LambaCube 3D compiler solves the above issues the following way:
After solving these issues, and migrating to the new representation of tuples, the built-in LambdaCube 3D library could be simplified significantly.
Some examples: previously we had repetitive, incomplete and potentially wrong functions for tuples like
type family JoinTupleType t1 t2 where JoinTupleType a () = a JoinTupleType a (b, c) = (a, b, c) JoinTupleType a (b, c, d) = (a, b, c, d) JoinTupleType a (b, c, d, e) = (a, b, c, d, e) JoinTupleType a b = (a, b) -- this is wrong if b is a 5-tuple! -- JoinTupleType a ((b)) = (a, b) -- something like this would be OK remSemantics :: ImageSemantics -> Type remSemantics = ... -- definition is not relevant now remSemantics_ :: [ImageSemantics] -> Type remSemantics_  = '() remSemantics_ [a] = remSemantics a -- not good enough... -- remSemantics_ [a] = '((remSemantics a)) -- something like this would be OK remSemantics_ [a, b] = '(remSemantics a, remSemantics b) remSemantics_ [a, b, c] = '(remSemantics a, remSemantics b, remSemantics c) remSemantics_ [a, b, c, d] = '(remSemantics a, remSemantics b, remSemantics c, remSemantics d) remSemantics_ [a, b, c, d, e] = '(remSemantics a, remSemantics b, remSemantics c, remSemantics d, remSemantics e)
With heterogeneous lists as tuples these and similar functions shrank considerably:
type family JoinTupleType a b where JoinTupleType x (HList xs) = HList '(x: xs)
remSemantics_ :: [ImageSemantics] -> Type remSemantics_ ts = 'HList (map remSemantics ts)
By the way, with heterogeneous lists it was also easier to add row polymorphism (one solution for generic records) to the type system, but that is a different story.
The pattern matching issue deserves a bit more detail. Why is it a good idea to restrict pattern matching for heterogeneous lists? Well, consider the following function with no type annotation:
swap (a, b) = (b, a)
Of course we expect the compiler to infer the type of swap. On the other hand, if tuples are heterogeneous lists, the following function is also typeable:
f (_, _) = 2 f (_, _, _) = 3 f _ = 0
It seems that type inference is not feasible for heterogeneous lists in general. For LambdaCube 3D we settled with above mentioned restriction in order to retain type inference. It seems feasible to create a system that allows the definition of f with a type annotation, but this would not buy much for the users of LambdaCube 3D so we didn’t go for it.
I have found a few implementations of heterogeneous lists in Haskell, Idris and Agda. So far I have not found a language where tuples are represented with heterogeneous lists, neither a language with special syntax for heterogeneous lists.
To sum it up, in the case of LambdaCube 3D, representing tuples as heterogeneous lists has no drawback and at the same time the base library (which provides the OpenGL binding) became more complete, shorter and more correct. We definitely consider switching to this representation an overall win.