Drinking with Datalog
psst, hey kid, wanna read a weird programming book
March 21, 2021
Drinking with Datalog
Given the contents of my bar:
$ cat facts/bar<br>brandy<br>dry vermouth<br>lemon<br>light rum<br>lime<br>orange liqueur<br>reposado tequila<br>sugar<br>And my cocktail recipe book:
$ head facts/recipes<br>martini What cocktails can I mix?
$ cat results/mixable<br>daiquiri<br>margarita<br>sidecar<br>Gosh, that’s not very many. What could I add to my bar to expand my options?
$ cat results/shopping-list<br>london dry gin -> gimlet<br>london dry gin -> martini<br>champagne -> airmail<br>cognac -> between-the-sheets<br>sherry -> sherry-cobbler<br>rhum agricole -> ti-punch<br>this seems dumb
No you’re wrong it’s smart. Take a closer look at that Daiquiri: the recipe calls for lime juice, but we don’t have lime juice in our bar. We only have lime. So why does it show up as mixable?
I’m so glad you asked. These results are generated by something called Mixologician, a tiny Datalog program I wrote.
And Mixologician knows some rules. It knows that limes make lime juice – and lime wedge, and lime zest, etc. It even knows that lime zest plus sugar makes lime cordial – so it knows that we’re only one ingredient away from being able to make a Gimlet, even though we don’t technically have a single ingredient that the drink calls for.
can you ease me into this with a semi-apocryphal origin story
Sure can!
I like cocktails. Once upon a time, I liked to go to restaurants and order cocktails. But for some reason I haven’t been going to restaurants for a while, and instead I’ve been making cocktails at home.
But I don’t want to mix the same cocktails every time. A big part of what I enjoyed about the restaurant-cocktail-ordering experience was the variety: every fancy hipster restaurant I used to frequent had its own cocktail menu – it’s own unique set of drinks, full of ingredients I had never heard of.
Which is sort of a problem, for the home bartender.
See, I don’t have a very comprehensive liquor collection. I’ve got the basics, sure, and over the course of quarantining I’ve acquired a few fancier ingredients. But fancy ingredients usually aren’t very versatile: I bought a bottle of Amaro Nonino once to mix a Paper Plane. But it turns out I don’t like really Paper Planes. So now I just have, like, 97.1% of a bottle of Amaro Nonino, and nothing to do with it.1
That was not very efficient purchase. We can do better.
So I wrote a little program to tell me: given what I have in my bar right now, what should I add that will enable me to make the maximum number of new cocktails. Or in other words, what is my most efficient purchase – what is the ingredient that I am most “blocked on.”
that relatable story captured my attention tell me more
I thought this would be a good opportunity to try out Datalog, a word that I’d heard before.
Now, you might be thinking that this sounds like a trivial problem, and you can just write a couple lines of Python to do set subtraction based on what you have and what you need and then just filter down to the cocktails missing exactly one ingredient.
And… that’s true. This is not a very hard problem.
The reason logic programming seemed appropriate to me was the idea of these “production rules:” ingredients that can become (or combine to become) other ingredients.
Now, I’m not saying that it would be hard to model that in your favorite scripting language, but it’s not really obvious any more how to do it without a guess-and-check sort of brute force search. Not that there’s anything wrong with that; it just feels like a more natural fit for logic programming.
Or not! Who knows. It’s not like I know anything about logic programming. This whole thing is just an excuse to try it out.
well let’s see it
The code, like all code, is on GitHub. You can look through the project – I would recommend starting with the tests, as they provide a sort of literate guide to how it works.
But I dare say the code is not all that interesting, by itself: if you already know Datalog, it’s trivial; if you don’t, it’s inscrutable.
So instead, I’m going to walk through the final result piece by piece, and talk about some of the missteps and mistakes I made along the way. Since this was my first encounter with Datalog, it took me a little while before I was able to “think” the way that Datalog wanted me to – and I think the errors I made along the way are a lot more interesting than the final result.
cat mixologician.dl
You can follow along at home if you’d like.
We open with some type definitions:
.type Ingredient
Custom types make the rest of the code more readable, and will let the compiler catch dumb mistakes like mixing up the order of my relations.
symbol is what Datalog calls “string” – I point this out because it...