My advisor had asked me in May or June of 2019, more or less in these exact words, “So Evan, do I still need to pay you next year?” to which I said “Yeah that’ll be nice!” Thus, shortly after I finished my PhD thesis defense, I became a postdoc for a year in the same lab while I looked for jobs. So the story started roughly sometimes September 2019, during my year as a post-doc.
At the time I was very interested in viewing program synthesis in the style of 20 Questions. Essentially, can a user interact with a synthesis system in a series of question-answering rounds to indicate which program they have in mind? This way, a novice user can still program, without expertise in the programming language. My rationale was that, human communication in 20 Questions is undeniably powerful: One can often identify a single correct object against a set of infinitely many distractor objects in just 20 rounds. Therefore, if program synthesis is figuring out which program the user have in mind out of the almost infinite set of all programs, clearly there’s some good research to be done in relating these two processes.
To keep my set up simple and grounded, I focused on simple objects that are nonetheless combinatorial in nature, and with a set of attributes: They are as good as real programs from a communication point of view. I made a pattern communication game, where each pattern consists of an arrangement of colored blocks, with a set of attributes you can use to describe them, such as colors and the number of pieces. I imagined that there are two players, player1 (the user) with a particular pattern in mind (i.e. a program), and player2 (the system) that owns a set of all patterns (i.e. space of programs), and is acting in collaboration to identify which pattern player1 had in mind. Here’s a note showing part of this game, interestingly, the also has some other funny tidbits and doodles that’s off topic.
I also made a physical version of the game which I can carry around with me to play with my friends (or some unfortunate stranger I ran across in school). It consists of two identical set of 10 lego constructions, {a1,a2,…,a10}, each made by combining 2 to 3 basic blocks. I put the two sets in two small paper boxes, and I would give one box to a friend and ask them to draw from the box a construction at random, and attempt to communicate to me which piece they had drawn until I find the corresponding piece in my box. I compared two setups, under one setup I just let the other person talk, and under a different setup I get to ask clarification questions. (I have these pieces somewhere, when I find them I’ll upload their photo)
At some point I arrived at a very useful metaphor for this communication process: That of a person shopping for an item. The person has some requirement for the item in their mind, and the shop owner has a set of items that they can offer. By collaboratively talking to each other, the shop owner finds the right item for the shopper. Here’s a small transcript in the context of ordering food from a restaurant.