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.
This blog has been silent for a long time, so it’s definitely time for a little update. A lot of things happened since the last post! Our most visible achievement from this period is the opening of the official website for LambdaCube 3D at ‒ wait for it! ‒ lambdacube3d.com, which features an interactive editor among other things. The most important, on the other hand, is the fact that Péter Diviánszky joined the team in the meantime and has been very active in the development of the latest LambdaCube generation. Oh yes, we have a completely new system now, and the big change is that LambdaCube 3D is finally an independent DSL instead of a language embedded in Haskell. Consult the website for further details.
Soon we’ll be writing more about the work done recently, but the real meat of this post is to talk about our summer adventure: the LambdaCube 3D Tour. This is the short story of how Csaba and Péter presented LambdaCube 3D during a 7-week tour around Europe.
Csaba started to work on LambdaCube 3D full time in the autumn of 2014 and Péter joined him at the same time. We knew that we should advertise our work somehow, preferably without involving individual sponsors. Csaba already had experience with meetups and hackathons, and Péter had bought his first car in the summer, so it seemed feasible to travel around Europe by car and give presentations for various self-organised tech communities.
At the end of March 2015 we decided that the tour should start around ZuriHack 2015, which we wanted to participate in anyway. We had a preliminary route which was quite close to the final itinerary shown on the following map:
We included Munich because we knew that Haskell is used there in multiple ways and we missed it last year during the way to ZuriHack 2014. We included Paris later because a friend of us was at MGS 2015 and while chatting with Nicolas Rolland, he got interested in our tour and invited us to Paris. We included Nottingham because Ambrus Kaposi, Peter’s previous student, was doing research in HoTT there and he invited us too. We included Helsinki because Gergely, our team member and Csaba’s previous Haskell teacher, lives there and we have also heard that lots of indie game developers work in Helsinki. The other destinations were included mainly because we knew that there are Haskell communities there.
After deciding the starting time, we made sure to fully focus on the tour. We made a detailed work schedule for 4 x 2 weeks such that we would have enough content for the presentations. The work went surprisingly well, we reached most milestones although the schedule was quite tight. We have done more for the success of LambdaCube 3D in this two-month period than in the previous half year.
We had a rehearsal presentation in Budapest at Prezi, mainly in front of our friends. It was a good idea because we got lots of feedback on our style of presentation. We felt that the presentation was not that successful but we were happy that we could learn from it.
We hardly dealt with other details like where we would sleep or how to travel. All we did was the minimum effort to kickstart the trip: Peter brought his 14 years old Peugeot 206 to a review, he sent some CouchSurfing requests and Csaba asked some of his friends whether they can host us. We bought food for the tour at the morning when we left Budapest. Two oszkar.com (car-sharing service) clients were waiting for us at the car while we were packing our stuff for the tour.
Up until Vienna there were four of us in the car with big packs on our laps. This was rather inconvenient, so we mostly skipped transporting others later on. Otherwise, the best moments were when we occasionally gave a ride to friends or hitchhikers.
Peter was relatively new to driving but at the end of the tour he already appreciated travelling on smaller local roads because highways turned out to be a bit boring for him. Csaba was the navigator using an open-source offline navigation software running on an NVidia Shield, which we won at the Function 2014 demoscene party.
Being lazy with actual route planning hit back only once when it was combined with a bad decision: we bought an expensive EuroTunnel ticket instead of going by ferry to England. Even with this expense, the whole journey including all costs was about the same price as visiting a one-week conference somewhere in Europe. This was possible because we only paid once for accommodation, in a hostel. Otherwise we were staying at friends or CouchSurfing hosts. We slept in a tent on two occasions. We learned during our tour about the Swedish law, The Right of Public Access (Allemansrätten), which allows everyone to visit somebody else’s land, use their waters for bathing and riding boats on, and to pick the wild flowers, mushrooms, berries. We didn’t have the chance to try all these activities, though.
All of our hosts were amazing and very different people, living in different conditions. We hope that we can return the hospitality either to them or to someone else in need in Budapest.
Our main task was to give one presentation every 3-4 days on average, which was a quite convenient rate. We were lucky because our first presentation was strikingly successful in Munich. We got so many questions during and after the presentation that we could only leave 4 hours after the beginning. At first we made free-style presentations but near the end we switched to using slides because they are altogether more reliable. Sometimes it was refreshing to diverge from the presentation and speak about Agda or laziness if the audience was interested about it.
We reached approximately 200 people at 12 presentations and we had lots of private discussions about our interests. This was combined with a diverse summer vacation with lots of impressions. We think of it as a total success!
In hindsight, there are a few things we would do differently if we were to begin the tour now:
It matters a lot to us that the importance of our work was confirmed by the feedback we received during the trip. It’s also clear that C/C++ programmers would only be interested in an already successful system. On the other hand, functional programmers (especially Haskellers) are open to cooperation right now.
The tour ended two weeks ago, and by now we had enough rest to carry on with development, taking into account the all feedback from the tour. We shall write about our plans for LambdaCube 3D in another blog post soon enough. Stay tuned!