DeconstructSeattle, WA - Thu & Fri, Apr 23-24 2020

← Back to 2019 talks


(Editor's note: transcripts don't do talks justice. This transcript is useful for searching and reference, but we recommend watching the video rather than reading the transcript alone! For a reader of typical speed, reading this will take 15% less time than watching the video, but you'll miss out on body language and the speaker's slides!)

[APPLAUSE] Hello, everybody. So the only thing standing between you and lunch right now is a 25 minute talk about mushrooms. So, yeah, this is me. Like many of you I work with computers. Sometimes for money, sometimes for fun, sometimes for neither. And I've worked on a pretty wide range of things. I've worked on self-driving vehicles. I've worked on video streaming websites. I've made large Arduino-driven LED light installations. And more recently I've actually done some programming for escape rooms. So I'm a pretty broad generalist by most measures.

The number of programming languages and frameworks that I've used professionally seems to grow every like six or eight months or so. And one of the reasons for that is I really, really enjoy learning new programming languages. I think each language has sort of its own unique viewpoint on the world in its own way of sort of viewing problem-solving as a whole. And I find that exploring these different ways of problem-solving is a good way to expand my own problem-solving abilities.

So, yeah, so I'm hoping to explore a little bit of that with Prolog today as much as we can in the next 20 minutes or so. Another thing I really like is mushroom hunting and mushroom identification. I live in Western Pennsylvania for most of the year, which is home to thousands of species from the fungi kingdom. And I really enjoy just going and finding like weird, strange mushrooms and then seeing if I can figure out what they are, just sort of like taking that process from finding weird thing and figuring out its name.

But early on in this hobby, I sort of ran into a problem, or what I viewed as a problem. I met a lot of really intelligent people, like really smart people for whom identification seemed second nature. They were able to just look at something and know immediately, oh, this is clearly that. It's like, yeah, of course.

And then there was me who was trying to piece together just like the loosest idea of what something might be by like Google searches or like flipping through field guides. And, yeah, and to make this work, I didn't see an easy way to get from where I was to where all the pros were short of just memorizing every field guide I could get my hands on. So I decided, what if I make a software program, a Prolog program, that can help me identify mushrooms?

So that's what I'm going to talk to you about today. We're going to walk through the creation of a mushroom identifying program starting from some basic Prolog facts and working our way up to a functioning identified rule. But first, I have some disclaimers. At various points throughout this talk, I'm going to discuss the topic of mushroom edibility. Don't eat mushrooms if you don't know what they are. Everyone really likes to ask like, hey, is this editable, as like their first question.

Please don't make that your first question when you find a new mushroom. Mushrooms contain some of the most like deadly toxins in the world. And, yeah, just make sure you know what you're eating. Disclaimer number two, I'm using SWI-Prolog. There are about 20 different flavors of the [INAUDIBLE] Prolog out there. My choice of SWI was somewhat arbitrary. So, yeah-- but all the code examples are using SWI.

And also, I'm going to be using the Latin names of mushrooms. A lot of mushrooms have really fun whimsical names, like the shaggy parasol or-- yeah, there're many of them. But not every mushroom has a fun whimsical name. So I'll include the whimsical names as we go, but our program has to use the Latin names. I'm sorry in advance.

So let's dive into it. When you find a mushroom and you're trying to figure out what it is, one of the first things you should know is what ecological role the mushroom is playing. This is a fancy way of saying, what is the mushroom eating? And there are three main answers to this question. A mushroom can be saprotrophic, which means it's eating something that is dead. This is usually a dead tree or a fallen tree.

A mushroom can be parasitic. This means it's eating something that is alive. Once again, usually a tree. But in the case of the cordyceps mushroom up here, it can be a like living insect that the fungus actually colonizes in a weird, gross way. And then mushrooms can also be mycorrhizal. And what this means is the mushroom is growing in the dirt colonizing the root system of the plants around it, creating this really beautiful symbiotic relationship.

Cool. So that's like our first set of mushroom facts. Let's encode that in Prolog. So we're going to open up our mushroomdb.profile. And we're going to put in lines that look like this. So this is our first Prolog fact. And what it's saying is the ecological type of trametes versicolor, which is the turkey tail mushroom, is saprotrophic. And this is just asserting this fact to Prolog. This is just telling it that it is a true thing about the world.

The different parts of this fact are the predicate is ecological type. And then the two arguments to the predicate are called Prolog atoms. So, yeah, like note that this looks sort of like a function call in a lot of languages, but it's not a function call. It doesn't have a return value. It's just a logical predicate that can be either true or false. And we're just telling Prolog explicitly, this is true.

So we can add ecological types of various other mushrooms-- cerioporus squamosus, the pheasant back mushroom, is a parasitic mushroom. This one, amanita mascaria is probably the most visually recognizable mushroom. This is the emoji mushroom. And that is a mycorrhizal mushroom. And hericium erinaceus, the lion's mane mushroom, is a parasitic mushroom, and so on and so forth. And we can list these out for as many as mushroom species as we can find that information for.

And then what we can do is we can open our Prolog shell, which is swipl, and we can tell it we're going to be looking the fact in our mushroomdb file. So that's the consult mushroomdb line. And then we can write our first Prolog query. It's just a query. I know it looks a lot like a fact, but we're just asking it, is the ecological type of the turkey tail mushroom saprotrophic? And Prolog, since we explicitly told us that-- told Prolog that that is a true fact, it's going to respond true, because it was able to figure out, yeah, that's true.

But we don't have to be explicit about every part of our query. We can also include variables. In Prolog, a variable begins with a capital letter. So that's how Prolog distinguishes a Prolog atom from a Prolog variable. And what this query is saying is, it's saying, OK, what is the ecological type of the turkey tail mushroom? We're just asking Prolog like, OK, what is a value for x that would make this query true? And Prolog will search and try and find a value for x that makes that evaluate to true. And when it finds one, it will return the value for us.

We can also run this the other direction. We can say, OK, what is a mushroom x that has the ecological type of-- ecological type of parasitic? And Prolog will respond, this is the honey mushroom, and it'll say, OK, if x is equal to this, then you're-- the query that you have given me is true. But since there are multiple answers to this question, Prolog is able to answer our query multiple times. So it will say, well, x could also be-- could also be this. It could also be this, et cetera. And it will list out as many as we ask for.

We're not limited to just a single variable. We can say, OK, we'll do a query with two variables. So this is just asking Prolog for x and y value pairs that satisfy the query. So once again, it'll say, the turkey tail mushroom and saprotrophic is one possible solution to the query-- the pheasant backed mushroom and parasitic.

So it's neat, but it gets a little bit more interesting if we add more information to our Prolog db. So let's talk about edibility. As I said before, edibility is probably one of the most asked about properties about mushrooms. The data set that I'm working with breaks edibility down into these 10 categories. Most of them are pretty self-explanatory. I'll talk about choice a bit.

So choice is all the really good mushrooms, like chanterelles and morels that everyone's like looking for and trying to find. And then there's also a bunch of weird overlap between these-- the little-- these the like categories and ways you wouldn't really expect. And we'll talk about that more in a little bit. But it's not super intuitive.

But for now, let's just encode this information in our Prolog db. So we open and we add the following lines. We tell it, OK, the pheasant back mushroom is edible. We tell it amanita muscaria is a psychoactive mushroom. Morchella americana, the morel mushroom, or a morel mushroom, is a choice edible, et cetera. Amanita bisporigera is the destroying angel mushroom, which is another fun, weird, whimsical name.

So, yeah-- so now that we've told Prolog about all these facts, we can query it the same way we queried ecological role. We can say, OK, the edibility of mushroom x is choice. Show me a mushroom x that has that edibility. And we can also combine with the other predicate and say, OK, and the ecological type of x is mycorrhizal. And the key thing to note here is that those x's have to be the same value. Prolog has to unify those to the same value in order to make our query true.

So it'll search and it'll find, OK, I found a few x's that will satisfy the constraints you had provided for me. These are all in the cantharellus genus, which are chanterelle mushrooms starting to pop up now in Western Pennsylvania, which is pretty exciting. But as I said before, edibility of mushrooms is really complicated. And edibility can vary between field guides, between cultures.

So here is a query where we're asking for a mushroom x that is both edible, but also inedible. And it will happily return the pheasant back mushroom, cerioporus squamosus. And the reason for this is that when this mushroom is young, it's like really tender and you can eat it and you break it open and it smells sort of like watermelon rind. But as it grows old, it gets really tough. And like if you try and eat it when it's larger, it's a lot like chewing on wet cardboard, which is-- yeah, like I would definitely call it not edible at that point.

So-- but, yeah-- but there are many reasons why edibility can vary. But what if we just want to know, OK, I found a mushroom. I want to know is this like safe to eat? Is it going to-- is it going to harm me? Is it going to be a bad time, et cetera. So we can accomplish that using what is called a Rule. So a Rule is a way in Prolog for us to state a conditional truth about the world. It's a way of just logically defining something that is true if other things are also true.

So the syntax for that looks like this. So foo of x is true if these other things are also true. Yeah. So let's reaffirm that a little bit with a Rule to tell us if a given mushroom is edible, like really edible, not just like edible but maybe also poisonous sort of thing. So we'll make a Rule that says, OK, mushroom x is edible if the edibility of x is choice, or in the line-- in Prolog the semicolon means or. It has a lot of weird-- weird things like that.

But, yeah-- or the edibility of mushroom x is edible. And any time you see a comma outside of a predicate, that means and. And that mushroom x is not poisonous and it's not a deadly mushroom. And it's not allergenic. OK. Cool. So that's like logically what we want edible to mean. And note that this isn't a function. We're not giving Prolog a series of steps to execute. We're giving it the logical relationships between the atoms of our program.

And the way that it-- and it's able to use those logical relationships to try and satisfy our queries. So we can write a query and say, OK, show me a edible mushroom. And it'll list, OK, yeah, sure, I can do that. I can find a bunch of values for x that satisfy your restraints. Yeah. Fun fact about the first mushroom up here, agaricus bisporus is your common white button mushroom. It accounts for about 90% to 95% of all mushrooms that are eaten in the United States.

Yeah. Most mushrooms are that species that you eat. But, OK, so we can figure out if something is edible. But another thing that you really want to know if you're going to eat a mushroom that you found is, could I have misidentified this mushroom? Could it-- and more importantly, does this mushroom have any poisonous lookalikes? Is there a mushroom that looks just like this that will kill me, or like harm me in some way?

So we can also create a poisonous look alike rule. But before we define what a poisonous lookalike is, we should probably logically define what a lookalike is. So we can say, OK, mushrooms x and y are lookalikes if they have the same ecological Rule, the same ecological type. So what this is saying is, the ecological type of x is a variable called EcoType. And the ecological type of y is that same variable called EcoType.

And once again, the key realization there is that-- is that any variables that are the same here have to be unified to the same value for Prolog to satisfy our query. But we probably want to take into account more traits when we talk about if two mushrooms are lookalikes or not. Otherwise, our program will say things like, the lion's mane mushroom is a lookalike of cerioporus squamosus, the pheasant back and that would-- that would just be embarrassing.

So let's add some more traits. We'll say, OK, we know about the-- we know about the ecological Rule. The cap shape of a mushroom is also really useful if you're trying to tell what it is. Like caps can be either flat or convex or concave. The gill type or gill attachment is also a very useful trait. This-- yeah, this refers to how attached the gills are to the stem. So in the case of agaricus bisporus, the gills are free, meaning they're not attached at all.

But in the case of the chanterelle mushroom, they are fully attached the light down the stem. And the last trait I will talk about is the spore color. You can usually tell what color spore is a mushroom has by looking at its gills, or you can do something called spore printing where you cut the cap off and you put it on a piece of paper overnight. And then when you look at it the next day, you'll have a fun little pattern that looks like this. And that will pretty clearly tell you what color of spores the mushroom has. And it just looks pretty.

So now that we know a few more traits our lookalike Rule can be a little bit more robust. So we can say mushrooms x and y are lookalikes if they have the same ecological type, if they have the same cap shape, if they have the same gill type, and if they have the same spore color. OK. Cool. So that's logically what a lookalike means in our program right now.

So let's just ask Prolog to generate some lookalikes for us. Say, OK, Prolog, show me a mushroom x and a mushroom y that have all the same traits. And Prolog will cleverly respond, ah-ha, I found a way of satisfying your query. If I make x equal to y, then I can note that these are the same mushrooms. It's like, yeah, Prolog, you're technically right. Like, OK. We get it.

So, yeah-- so we have to sort of close this logical loophole if we want Prolog to actually do what we want it to. And the way that we do that is, we have to go back into our lookalike rule and at the end of it say, OK, x is not-- over here. X is not equal to y. X is not unifiable with y, meaning they can't be made to be the same value. And then once we've closed that loophole, we can go back and say, OK, Prolog, now show me x and y mushrooms that are lookalikes. And it will say, OK, I've found some now that actually meet your requirements.

So this is neat. And now that we have a lookalike rule and we have an edibility rule that makes making a poisonous lookalike Rule fairly straightforward. So we can say mushrooms x and y are poisonous lookalikes, if they are lookalikes, and the edibility of x is not unifiable with the edibility of y, or they have different edibility. And that's cool. And a cool thing about that is it works.

We can say, OK, Prolog, show me mushroom x and mushroom y where one is poisonous and the other is not. And it'll say, OK, how about chanterelles and the Jack O'Lantern mushroom. So note that these look very similar, but the Jack O'Lantern mushroom is a pretty poisonous mushroom. It's very unpleasant if you eat it. It won't actually kill you, but it's a very unpleasant experience. And it looks a lot like chanterelles, which are a choice edible mushroom that everyone is out there looking for right now.

So if you're going to eat mushrooms that you find, make sure that you know the poisonous lookalikes of whatever you are eating, and also how to differentiate them. It's very useful. So do your research. And it'll spit out as many poisonous lookalikes as it is able to find.

So it was at this point in making my mushroom identifying program that I was like, oh, this is pretty cool. I can tell edible mushrooms. I can find poisonous lookalikes fairly easily. But the actual process of identifying mushrooms was like pretty verbose. I had to type out-- I had to type out a lot. I had to say, OK, I found a mushroom x and-- OK. The gill type of x is free, ecological type is saprotrophic, et cetera. And like, it would work, but it was very verbose. And I didn't-- I couldn't see a very easy way to give-- to make like a Rule that would simplify that for me.

So it was at that point that I decided to rip everything up and completely restructure my database to look more like this. So this is kind of gross but bear with me. It will work. I swear. It's exactly what I was thinking to myself while doing this.

So instead of having trait specific predicates, I'm just going to make one predicate called has trait. And what this says is, OK, this mushroom coprinopsis variegata has adnate gills. And that same mushroom has black spores and a conical cap, et cetera. And I'm going to encode all of my mushroom facts in this way instead.

A fun fact about this mushroom, this is called the scaly ink cat mushroom. And over the course of 24 hours, it will release a bunch of spores and then just turn to this black goo in a process called autodigestion, or it just eats itself. It's neat.

So a cool thing about restructuring our database that way is we haven't really lost any functionality. We can still say, OK, Prolog, show me some saprotrophic mushrooms. And Prolog will happily list out the-- list out the turkey tail mushroom for us once again, et cetera. We've also gained a bit of functionality essentially for free. I just had to write a script to restructure the database.

And we can now say, OK, show me all the traits of hericium erinaceus, the lion's mane mushroom. And Pro-- and Prolog will gladly list out any value for x, any trait that satisfies this query. And that was not trivial to do before using the trait specific predicates. So like-- so that was kind of happy. I was able to gain some functionality there.

But the coolest thing that this enables is now we can make a functioning identify Rule that says, OK, identify mushroom x with this list of traits. And if you're not familiar with this syntax for a list, what that pipe in the middle is doing is it's just separating the head of the list, or the first element, from the rest of the list. So I just put the Python syntax up there as a reference.

But so we're saying, OK, mushroom x-- identify mushroom x by this list of traits. If mushroom x has the first trait. And then we can use recursion and say, OK, and our identify function is logically sound with our list of the other traits. And as with any recursion, we need to define our base case. So we need to say, OK, our base case in this situation is, if the other traits list is empty.

So what we'll say is, OK, either other traits is unifiable with the empty list, or the identify function with x and other traits succeeds. And the cool thing about this is it works. I can say-- I can say, OK, I found this mushroom x and I know it's saprotrophic and it has no cap, but that's all I can really tell. And it'll say, OK, it could be artomyces pyxidatus, which is the crown tipped coral fungus, which has been fairly common in Western Pennsylvania for the past month or so.

And it'll give us as many suggestions for ID as we want. But I want to look at the-- look at our Rule again. And I want you to think what will happen here if we run it the other direction? What will happen if I give it a mushroom name and then a variable for the list of traits, which is not really a use case I was thinking about while writing this, and-- but like logically, it should still hold because that logical relationship is still there.

So I want everyone to come up with a guess in your minds. Think of what this might return. Like, what we might want it to return is traits being unified with a list that has all of the traits of agaricus bisporus. What it will actually return is traits equals brown spores. OK. Which is one of the traits of agaricus bisporus. So that's useful, sort of.

And then Prolog-- so that a little semicolon there means Prolog thinks it has more answers for us. When we say, OK, Prolog, what other answers do you think you have for us? And Prolog will say, ah, a list-- a list of two brown spores, and has more answers. And it will give us-- it will give you a list as big as you want that just says brown spores. And it's like, yeah, it's another situation. It's like, yeah, OK, I get it. You're technically right.

And, yeah-- so while working with Prolog, I find you run into these situations pretty frequently where Prolog does something weird and different. It's like trying to talk to a child sort of. And, yeah, at first these situations sort of frustrated me. But then after you work with Prolog for a little bit, I now find it kind of endearing and find it-- It's like-- it's sort of representative of the difference between how I'm thinking about a problem and how Prolog is thinking about a problem. And I find that to be pretty cool.

I've since fixed this-- like this bug. The solution is nowhere near as interesting as the problem itself, so I'm not going to-- I'm not going to present that to you. And I'm also preventing everybody from lunch right now. So, yeah, if you'd like to learn more, I hope this maybe sparked interest in either Prolog or mushrooms or both in you. If you would like to learn more, there are tons of great Prolog tutorials online that I would highly recommend you check out. I was barely I barely had time to like scratch the surface of the cool stuff Prolog is capable of, and all the cool stuff it can do.

So, yeah, talk to me afterwards. Check out some stuff-- some stuff for the online. Also, if you want to learn more about mushrooms, many of the pictures in this talk were taken by a friend of mine named Adam Haritan. He runs a website called Learn Your Land where he just posts a bunch of like educational materials, and like videos and stuff. And it's a really, really, really accessible if you're not y-- or if you're not already familiar with mushrooms. So, yeah. Thank you for listening to my talk. That's all I have.