Beautiful. This paper starts to make a connection that I've somewhat thought about, and I think it's a fundamental idea in program synthesis that everyone has been missing so far.
Here's the deal. In program synthesis based on input-output examples, there's an obvious problem of massive ambiguity. For example, what is a function that takes the number 2 and returns 4? It could be $f_1(x) = 2x$, or $f_2(x) = 2 + x$, but it could also be $f_3(x) = 2$, $f_4(x) = 10 - 3x$, or $f_5(x) = 1073741834 - x^{30}$. It doesn't matter how many examples you give - being just a finite number of them, I can always come up with infinitely many weird functions that match them, and that are not what you want. How is a synthesizer supposed to guess?
Now comes the cool connection to the world of pragmatics, in linguistics. Let's say the user of the synthesizer is a speaker, that wants to refer to a program. What this user says is a set of examples. The listener, the synthesizer, has to guess which program the user is referring to.
The Rational Speech Act (RSA) framework explains quite well in practice how human beings choose what to say when they want to refer to things. The famous hat+glasses example illustrates it very neatly. Suppose there are two people, one wearing glasses and a hat, and the other wearing just glasses. If I say "the person with glasses", literally it could be any of them, but you would surely guess I'm referring to the person with just glasses. Why? Because you recursively think about what I could have said instead if I wanted to refer to the other person. I could have said "The one with a hat", but because I didn't, I'm less likely to be referring to that person. RSA was proposed by Noah, my current PhD advisor, and I started doing my PhD in program synthesis, so this paper comes as such a pleasant surprise to see people thinking about this connection that is elegant and still unexplored.
So that's the paper: given a space of programs and examples where both are tractable to build a _meaning matrix_ (i.e. see whether each program matches each possible example), you can apply RSA rather directly. They have a user study, where it's clear that people find it easier to communicate with a pragmatic synthesizer, instead of a literal one.
Cheers to this paper!