CS Cabal

Toronto-based reading group that meets weekly to read computer science books and papers.

Currently reading: The Little Typer

GuildMeetup listings

Mastodon Social Hub

Mailing list Communication nexus

Code of Conduct Must read


December 12, 2016

By Scott

Hey everyone, We were short a couple of regulars but still enough to make quorum, we started on the modules chapter of PFPL 44, and Huma showed us an example dictionary implementation like in the text that was using C++ concepts, very neat!

This was the last meeting of the year, so everybody polish your modules over the holidays and we will continue with chapter 44 again in the new year, Friday Jan 6th, 6:30pm at Gamma Space.

This chapter is all about the modules, and by modules I mean interfaces, and by interfaces I mean one of the hardest things to get right in software. Even though modules may not help you choose a good API for your users, they will give you a language for selectively hiding or exposing implementation details across software interfaces. Signatures are introduced as a new construct and they describe a module boundary. They can be fully abstract interfaces like in chapter 17 or they can act as partial views into an implementation, called type classes.

For instance if you want to distribute a sorting function, sort(keys, values)you might worry about:

  1. how to make it work for different types of keys?
  2. how to allow users to swap the compare function without hurting efficiency?
  3. how to keep users from depending on details of your implementation?

The last one we have seen earlier in chapter 17, we can use type abstraction to hide all of the implementation details behind an abstract interface. Similarly, you could use type abstraction to solve the first worry as well, by making your sort function depend on abstract Key, Value, and compare modules. This can work quite well, in fact the qsort function in the C standard library has an interface like this, where you pass in pointers to your data and a custom compare function.

Where this approach can fall short is that you as the implementor of the sort function you can’t make any optimizations based on the type of the keys or the choice of compare function. For sorting performance this can be pretty important since if you are sorting integers for instance it is often better to use a linear time radix sort then to use quick sort or something else. To do this you could use type classes which would let you take advantage of some implementation aspects of the Key type and comparison function.

Ok all for now, happy holidays, until next time! Scott