Two weeks ago, I had the pleasure of attending the BOB Konferenz 2016 in Berlin, Germany, where I gave an introductory talk on functional reactive programming (FRP) in english. The talk was videotaped and the recording is now available online. So, if you like to hear a short introduction from me on what FRP is all about, and why it’s a good idea, I invite you to have a look. Slides are available, too.
The purpose of the conference was to bring together
[…] developers, architects and builders to explore technologies beyond the mainstream and to discover the best tools available today for building software.
My favorite talks were the presentation by Andres Löh on the Servant library, which allows the specification of REST APIs in the type system and eliminates a lot of boilerplate, and the talk by Stefan Wehr on the Swift language (that new language by Apple), where he demonstrated that functional programming actually has already become mainstream.
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:
- There is this ugly … at the end with several consequences.
- This family has no proper beginning. We can define both Tuple0 and Tuple1, but one-element tuples are not yet embraced by the Haskell community.
- Tuples with different arities are not related to each other, because they are defined separately, not at once as one data family. One consequence of this is that it is not possible to write generic functions for tuples.
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)
Some examples: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?
- There is a thing called one-element tuple, which needs explicit syntax.
- We need some type system extensions (at least GADTs and type level lists are needed).
- The compiler backend has to be a little bit smarter to produce efficient code for tuples.
- Pattern matching on tuples is not obvious anymore.
The LambaCube 3D compiler solves the above issues the following way:
- One element tuples are denoted by (( element )).
- The compiler has a dependently typed core language, therefore defining and using the HList data type works out-of-the-box.
- Currently the compiler has no code generator for CPUs and it has only a limited code generator for GPUs with no support for tuples. Tuples either vanish during reduction, or they are transformed away in the shader code generator.
- Pattern matching on heterogeneous lists is restricted: when a tuple is matched, all patterns should have the same tuple arity. We’re okay with this, since this behaviour is not surprising for most programmers, and in LambdaCube 3D code tuple patterns tend to appear without alternative choices anyway.
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 liketype 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.
- HVect in reroute package is the same as HList.
- HVect in hvect package is a strict variant of HList.
- Tuples in Idris are different: (x, y, z) is a synonym for (x, (y, z)). On the other hand, HVect in the standard library is similar to HList. The difference is that the type level list is indexed by its length. I have found this discussion about whether tuples could be represented with HVect. It seems that efficient code generation is the difficult part.
- I have found an implementation of HList and HVec in Agda. However, I also found this discussion about size problems, so it is not so convenient to use them. We don’t have such issues because we use type-in-type.
- https://wiki.haskell.org/Heterogenous_collections gives a summary about implementing heterogeneous collections in Haskell. Heterogeneous lists are at the bottom (see next item).
- Strongly typed heterogeneous collections by Oleg Kiselyov has a more complicated implementation of heterogeneous lists in Haskell using less type system extensions.
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.
Summary: How to compile GHC on Windows using Stack and the new Shake-based GHC build system.
Here are a list of instructions to compile GHC, from source, on Windows. I tested these instructions on a clean machine using the free Windows 10 VirtualBox image (I bumped the VM CPUs to 4, and RAM to 4096Mb).
The first step is to install Stack (I just accepted all the defaults), then open a command prompt and run:stack setup
stack install happy alex
stack exec -- pacman -S gcc binutils git automake-wrapper tar make patch autoconf --noconfirm
stack exec -- git clone --recursive git://git.haskell.org/ghc.git
stack exec -- git clone git://github.com/snowleopard/shaking-up-ghc shake-build
stack build --stack-yaml=shake-build/stack.yaml --only-dependencies
stack exec -- perl boot
stack exec -- bash configure --enable-tarballs-autodownload
stack exec --stack-yaml=shake-build/stack.yaml -- shake-build/build.bat -j
The entire process (after the VM has downloaded) takes a bit less than an hour. These steps use the Stack supplied tools (MinGW, Git), and the new Shake-based build system. The hope is that by using the isolation Stack provides, combined with the portability improvements from writing the build system in Haskell, these instructions will work robustly on many Windows machines.
I have not tried these instructions on other platforms, but suspect that removing the pacman line might be sufficient to get it to work.
This weekend I’m in Memphis for SIGCSE 2016. This is my first time at SIGCSE, so I’m looking forward to picking up some new ideas in CS education, and more importantly to meeting lots of new people. If you’re here too, feel free to say hi!