## Boltzmann sampling for generic Arbitrary instances

tl;dr: I know how to generate random instances of data types in a generic way, and even have some old code that already does all the hard work, but won’t have time to polish and package it until this summer. If you’re interested in helping, let me know!

This morning Kenny Foner pointed out to me this tweet by Gabriel Gonzales, asking why there isn’t a default Arbitrary instance for types implementing Generic. It reminded me that I’ve been meaning for a while now (years, in fact!) to get around to packaging up some code that does this.

As several pointed out on Twitter, this seems obvious, but it isn’t. It’s easy to write a generic Arbitrary instance, but hard to write one that generates a good distribution of values. The basic idea is clear: randomly pick a constructor, and then recursively generate random subtrees. The problem is that this is very likely to either blow up and generate gigantic (even infinite) trees, or to generate almost all tiny trees, or both. I wrote a post about this three years ago which illustrates the problem. It also explains half of the solution: generate random trees with a target size in mind, and throw out any which are not within some epsilon of the target size (crucially, stopping the generation early as soon as the tree being generated gets too big).

However, I never got around to explaining the other half of the solution: it’s crucially important to use the right probabilities when picking a constructor. With the wrong probabilities, you will spend too much time generating trees that are either too small or too big. The surprising thing is that with exactly the right probabilities, you can expect to wait only $O(n)$ time before generating a tree of size (approximately1) $n$.2

So, how does one pick the right probabilities? Essentially, you turn the generic description of your data type into a mutually recursive system of generating functions, and (numerically) find their radii of convergence, when thought of as functions in the complex plane. Using these values it is straightforward to compute the right probabilities to use. For the intrepid, this is explained in Duchon et. al3.

I have some old Haskell code from Alexis Darrasse which already does a bunch of the work. It would have to be updated a bit to work with modern libraries and with GHC.Generics, and packaged up to go on Hackage. I won’t really have time to work on this until the summer—but if anyone else is interested in working on this, let me know! I’d be happy to send you the code and provide some guidance in figuring it out.

1. The constant factor depends on how approximate you are willing to be.

2. I wanted to put an exclamation point at the end of that sentence, because this is really surprising. But it looked like $n$ factorial. So, here is the exclamation point: !

3. Duchon, Philippe, et al. “Boltzmann samplers for the random generation of combinatorial structures.” Combinatorics Probability and Computing 13.4-5 (2004): 577-625.

## At SIGCSE 2016 in Memphis

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!

## The network reliability problem

Let $G = (V,E)$ be a directed graph with vertices $V$ and edges $E$. Multiple edges between the same pair of vertices are allowed. For concreteness’ sake, think of the vertices as routers, and the edges as (one-way) connections. Let $\mathbb{P} = [0,1]$ denote the set of probabilities, and $\varphi : E \to \mathbb{P}$ be a function which assigns some probability to each edge. Think of $\varphi(e)$ as the probability that a single message sent along the edge $e$ from the source router will successfully reach the target router on the other end.

Suppose that when a router receives a message on an incoming connection, it immediately resends it on all outgoing connections. For $s,t \in V$, let $P(s,t)$ denote the probability that, under this “flooding” scenario, at least one copy of a message originating at $s$ will eventually reach $t$.

For example, consider the simple network shown below.

A message sent from $s$ along the upper route through $r$ has an $0.5 \times 0.9 = 0.45$ probability of arriving at $t$. By definition a message sent along the bottom route has an $0.7$ probability of arriving at $t$. One way to think about computing the overall probability $P(s,t)$ is to compute the probability that it is not the case that the message fails to traverse both links, that is, $1 - (1 - 0.45)(1 - 0.7) = 1 - 0.165 = 0.835$. Alternatively, in general we can see that $1 - (1 - p)(1 - q) = p + q - pq$, so $0.45 + 0.7 - 0.45 \times 0.7 = 0.835$ as well. Intuitively, since the two events are not mutually exclusive, if we add them we are double-counting the situation where both links work, so we subtract the probability of both working.

The question is, given some graph $G$ and some specified nodes $s$ and $t$, how can we efficiently compute $P(s,t)$? For now I am calling this the “network reliability problem” (though I fully expect someone to point out that it already has a name). Note that it might make the problem a bit easier to restrict to directed acyclic graphs; but the problem is still well-defined even in the presence of cycles.

This problem turned out to be surprisingly more difficult and interesting than it first appeared. In a future post or two I will explain my solution, with a Haskell implementation. In the meantime, feel free to chime in with thoughts, questions, solutions, or pointers to the literature.

Posted in math | Tagged , , , | 17 Comments

## A strange representation of Z6

On my other blog I am writing about a proof of the Lucas-Lehmer test, and today in the course of working up some examples I stumbled across this little gem.

Let $M$ be a monoid, and let $M^*$ denote the subset of elements of $M$ which actually have an inverse. Then it is not hard to show that $M^*$ is a group: the identity is its own inverse and hence is in $M^*$; it is closed under the monoid operation since if $a$ and $b$ have inverses then so does $ab$ (namely, $b^{-1}a^{-1}$); and clearly the inverse of every element in $M^*$ is also in $M^*$, because being an inverse also implies having one.

Now let $M = \{a + b\sqrt{3} \mid 0 \leq a,b < 3\}$, where the operation is multiplication, but the coefficients $a$ and $b$ are reduced modulo 3. For example, $(2 + \sqrt 3)(2 + 2 \sqrt 3) = (4 + 6) + (4 + 2) \sqrt 3 = 1 + 0 \sqrt 3$. This does turn out to be associative, and is clearly commutative; and $1 = 1 + 0\sqrt 3$ is the identity. I wrote a little program to see which elements have inverses, and it turns out that the three elements with $a = 0$ do not, but the other six do. So this is an Abelian group of order 6; but there’s only one such group, namely, the cyclic group $\mathbb{Z}_6$. And, sure enough, $M^*$ turns out to be generated by $2 + \sqrt 3$ and $2 + 2 \sqrt 3$.

Posted in math | Tagged , , , | 11 Comments

## ICFP roundup

Well, ICFP 2015 in Vancouver is already two months in the past… I’ve been meaning for a while to write a post reflecting on the experience. Better late than never!

## The Place

I had never been to Vancouver before; it seems like a beautiful and fun city. One afternoon I skipped all the talks and went for a long hike—I ended up walking around the entire perimeter of the Stanley Park seawall, which was gorgeous. The banquet was at the (really cool) aquarium—definitely the first time I have eaten dinner while being watched by an octopus.

## The People

Instead of staying in the conference hotel, four of us (me, Ryan Yates, Ryan Trinkle, and Michael Sloan) rented an apartment through AirBnB.1 The apartment was really great, it ended up being cheaper per person than sharing two hotel rooms, and it was a lot of fun to have a comfortable place to hang out in the evenings—where we could sit around in our pajamas, and talk, or write code, or whatever, without having to be “on”.

I met some new people, including Aahlad Gogineni from Tufts (along with another Tufts student whose name I unfortunately forget); Zac Slade and Boyd Smith from my new home state of Arkansas; and some folks from Vancouver whose names I am also blanking on at the moment. I also met a few people in person for the first time I had previously only communicated with electronically, like Rein Heinrich and Chris Smith.

I also saw lots of old friends—way too many to list. It once again reminded me how thankful I am to be part of such a great community. Of course, the community is also far from perfect; towards that end I really enjoyed and appreciated the ally skills tutorial taught by Valerie Aurora (which probably deserves its own post).

## The Content

Here are just a few of my favorite talks:

I had a lot of great discussions relating to diagrams. For example:

• I talked with Alan Zimmerman about using his and Matthew Pickering’s great work on ghc-exactprint with an eye towards shipping future diagrams releases along with an automated refactoring tool for updating users’ diagrams code.

• After talking a bit with Michael Sloan I got a much better sense for the ways stack can support our development and CI testing process.

• I had a lot of fun talking with Ryan Yates about various things, including projecting diagrams from 3D into 2D, and reworking the semantics and API for diagrams’ paths and trails to be more elegant and consistent. We gave a presentation at FARM which seemed to be well-received.

I got another peek at how well Idris is coming along, including a few personal demonstrations from David Christiansen (thanks David!). I am quite impressed, and plan to look into using it during the last few weeks of my functional programming course this spring (in the past I have used Agda).

If I had written this as soon as I got back, I probably could have remembered a lot more; oh well. All in all, a wonderful week, and I’m looking forward to Japan next year!

2. I asked him afterwards how he made the great animations in his slides, and sadly it seems he tediously constructed them using PowerPoint. Someday, it will be possible to do this with diagrams!

## Experience report: oral final exam

This past spring I taught a standard data structures course (stacks, queues, binary trees, heaps, asymptotic analysis, that kind of thing). Inspired by a group I participated in exploring pedagogy and course design—led by the wonderful Betsy Burris—I decided to give an oral final exam instead of a typical written exam. For whatever reason, oral exams don’t seem very popular in the US these days, but overall I think my experiment was a success and I definitely hope to repeat it in the future. This post reports on how I organized things, what went well and poorly, and what I learned overall. I’d love to hear from anyone else who tries something like this in their own course. I’m also happy to answer questions, either in a comment on this post or via email.

## Exam content

I prepared three questions for the exam. The first was fairly simple (“explain algorithm X and analyze its time complexity”) and I actually told the students ahead of time what it would be—to help them feel more comfortable and prepared. The other questions were a bit more open-ended:

• The second question was of the form “I want to store X information and do operations Y and Z on it. What sorts of data structure(s) might you use, and what would be the tradeoffs?” There were then a couple rounds of “OK, now I want to add another operation W. How does that change your analysis?” In answering this I expected them to deploy metrics like code complexity, time and memory usage etc. to compare different data structures. I wanted to see them think about a lot of the different data structures we had discussed over the course of the semester and their advantages and disadvantages at a high level.

• The final question was of the form “Here is some code. What does it do? What is its time complexity? Now please design a more efficient version that does the same thing.” With some students there was enough time to have them actually write code, with other students I just had them talk through the design of an algorithm. This question got more at their ability to design and analyze appropriate algorithms on data structures. The algorithm I asked them to develop was not something they had seen before, but it was similar to other things they had seen, put together in a new way.

Overall I was happy with the questions and the quality of the responses they elicited. If I do this again I would use similar sorts of questions.

## Time

So overall, the oral exam took up less of my time, and I can tell you, hands down, that my time was spent much more enjoyably than it would have been with a written exam. It was really fun to have each student come into my office, to get a chance to talk with them individually (or as a pair) and see what they had learned. It felt like a fitting end to the semester.

## Assessment

In order to assess the students, I prepared a detailed rubric beforehand, which was really critical. With a written exam you can just give the exam and then later come up with a rubric when you go to grade them (although I think even written exams are usually improved by coming up with a rubric beforehand, as part of the exam design process—it helps you to analyze whether your exam is really assessing the things you want it to). For an oral exam, this is impossible: there is no way to remember all of the responses that each student gives, and even if you write down a bunch of notes during or after each exam, you would probably find later that you didn’t write down everything that you should have.

In any case, it worked pretty well to have a rubric in front of me, where I could check things off or jot down quick notes in real time.

## Social aspects

People are often surprised when I say that I allowed the students to come in pairs. My reasons were as follows:

• For many students, being able to come with a partner may help ease their anxiety about the exam. I was especially sensitive to this since for many of them an oral exam was a new experience. (I asked beforehand, and only two or three of them had ever had an oral exam, and those were in foreign language classes.)
• Computer science, like most disciplines, is often collaborative. No matter whether a student ends up going into industry or academia, it is very likely that any data structure design or analysis that they end up doing in “real life” will be in collaboration with others. So in this sense a collaborative oral exam is fairly authentic—much more so than a written exam. That is, the skills, activities, and modes of thinking and communicating required by a collaborative oral exam are actually fairly similar to what might be required of the students in the “real world”.
• There was also, of course, the simple reason of expedience: it cut down on the amount of time I had to spend administering the exam.

Overall I was really happy with the result. Many of the students had been working with a particular partner on their labs for the whole semester and came to the exam with that same partner. For quite a few pairs this obviously worked well for them: it was really fun to watch the back-and-forth between them as they suggested different ideas, debated, corrected each other, and occasionally even seemed to forget that I was in the room.

One might worry about mismatched pairs, where one person does all of the talking and the other is just along for the ride. I only had this happen to some extent with one or two pairs. I told all the students up front that I would take points off in this sort of situation (I ended up taking off 10%). In the end this almost certainly meant that one member of the pair still ended up with a higher grade than they would have had they taken the exam individually. I decided I just didn’t care. I imagine I might rethink this for an individual class where there were many of these sorts of pairings going on during the semester—but in that case I would also try to do something about it before the final exam.

Another interesting social aspect of the process was figuring out what to do when students were floundering. One explicit thing one can do is to offer a hint in exchange for a certain number of points off, but I only ended up using this explicit option a few times. More often, after the right amount of time, I simply guided them on to the next part, either by suggesting that we move on in the interest of time, or by giving them whatever part of the answer they needed to move on to the next part of the question. I then took off points appropriately in my grading.

It was difficult figuring out how to verbally respond to students: on the one hand, stony-faced silence would be unnatural and unnerving; on the other hand, responding enthusiastically when they said something correct would give too much away (i.e. by the absence of such a response when they said something incorrect). As the exams went on I got better (I think) at giving interested-yet-non-committal sorts of responses that encouraged the students but didn’t give too much away. But I still found this to be one of the most perplexing challenges of the whole process.

## Coverage

One might wonder how much of the material from an entire semester can really be covered in a 30-minute conversation. Of course, you most certainly cannot cover every single detail. But you can actually cover quite a lot of the important ideas, along with enough details to get a sense for whether a student understands the details or not. In the end, after all, I don’t care whether a student remembers all the details from my course. Heck, I don’t even remember all the details from my course. But I care a great deal about whether they remember the big ideas, how the details fit, and how to re-derive or look up the details that they have forgotten. Overall, I am happy with the way the exam was able to cover the high points of the syllabus and to test students’ grasp of its breadth.

My one regret, content-wise, is that with only 30 minutes, it’s not really possible to put truly difficult questions on the exam—the sorts of questions that students might have to wrestle with for ten or twenty minutes before getting a handle on them.

## Next time

Would I do this again? Absolutely, given the right circumstances. But there are probably a few things I would change or experiment with. Here are a few off the top of my head:

• This time, I only decided to do an oral final exam quite late in the semester. Next time, with more planning, I would like to think carefully about how to explicitly prepare students for this type of assessment, i.e. to give them chances to practice the necessary skills and to receive feedback. I am not yet sure what that would look like.
• I might try something like a system for e-mailing students a harder question a certain amount of time before their slot—the idea being that they would have that time to think about and prepare their answer to the question, which they could then present during the slot (in addition to answering some questions on the spot). However, a potential major downside is that students who struggle with the hard question might come in feeling demoralized and do even worse on the rest of the exam.
• Next time I will definitely be more careful and intentional about writing down a script for exactly what I want to say at the start of each exam. There were a lot of things I wanted to remember to say, and specific ways I wanted to frame the time, and at times it seemed a bit haphazard and inconsistent.

Again, I’m happy to answer questions in the comments or by email. If you are inspired to also try giving an oral exam, let me know how it goes!

Posted in teaching | Tagged , , , , | 5 Comments

## Meeting new people at ICFP

This afternoon I’ll be getting on a plane to Vancouver for ICFP. I’m looking forward to seeing many friends, of course, but I also enjoy meeting new people—whether or not they are “famous”, whether or not I think they can “advance my career”. So I’ll just throw this out there: if you will be in Vancouver this week and would like to meet me, just leave a comment and I will make a point of trying to find you to chat! I’ll be attending the Haskell Implementor’s Workshop, the Ally Skills Tutorial, ICFP itself, the Haskell Symposium, and FARM, but there’s also plenty of time to chat in the hallway or over a meal.

Posted in haskell | 1 Comment