In the previous chapter, we discussed how a method such as:
Weapon: [PreBuff] [WeaponType] [PostBuff]
can be though of as a grammar rule describing kinds of phrases:
A (description of) a weapon is a pre-buff followed by a weapon type followed by a post-buff
This chapter explores how other kinds of methods can be thought of as logical rules describing possible inferences. This introduces three big ideas:
- Predicates: tasks that answer questions rather than printing things
- Soft failure: calls in a method can fail. This isn't an error, it just means Step tries another choice path.
- Relaxed variables: variables begin life without specific values and acquire values as your use them.
Together, they give us our first real example of clairvoyant (nondeterministic) programming in Step: each call to each task involves choosing a method. Some, or even most, of those methods might fail. But the system behaves as if it always guesses correctly.
We'll see that this allows a programming style in which methods can be thought of as statements of fact. And the execution of certain tasks can naturally be thought of as answering questions about those facts.
Preview
We'll go through these ideas more slowly in the rest of the chapter, but here's a quick example to give you a sense of where we're headed. We're going to start by writing some methods for some Step tasks that don't print anything. Don't worry about the [predicate] annotation1 or the fact that the methods end with periods rather than colons:
# Try: [Dog lassie]
[predicate]
Dog benji.
Dog lassie.
[predicate]
Cat morris.
Cat garfield.
If you aren't familiar with US pop culture from the 1970s, Benji and Lassie were famous dogs from movies, Morris was a cat from cat-food commercials, and Garfield is a famous cartoon cat. So these methods form a little database of cats and dogs.
Calls as queries
Remember that you can run code in boxes like the one above by clicking in side the box. Try clicking above and running [Dog lassie].
When we run [Dog lassie], it works even though it doesn't print anything. We say the call succeeds. Its succeeds so long as there's a choice path through it that succeeds. Here's the choice tree for it, and the path of the left succeeds, so the call succeeds:
graph TB
start("[Dog lassie]") -- "<b>Dog benji.</b>" --> f[Fail]
style f fill:red
start -- "<b>Dog lassie.</b>" --> s(Succeed)
style s fill:green
It doesn't generate any output, but there is a path it can take the where the matching works. It chooses that path, completes successfully, and the command line prints “yes”, meaning the call worked.
Now what happens if we run [Dog garfield]?
# Try: [Dog garfield]
[predicate]
Dog benji.
Dog lassie.
[predicate]
Cat morris.
Cat garfield.
Here's the choice tree:
graph TB
start("[Dog garfield]") -- "<b>Dog benji.</b>" --> f[Fail]
style f fill:red
start -- "<b>Dog lassie.</b>" --> f2(Fail)
style f2 fill:red
Neither method matches, so both methods fail. That means the call itself fails. The command line prints “no”.
So Dog executes successfully – it succeeds – if you call it with a parameter it knows to be a dog. It fails if you call it with a something else. So we can test the doghood of something by calling Dog with the something as a parameter.
Now what happens if we run [Dog ?x]?
# Try: [Dog ?]
[predicate]
Dog benji.
Dog lassie.
[predicate]
Cat morris.
Cat garfield.
Remember that Step lets you specify variables as parameters in the command line. When you do that, it reports back the value it ended up with for that variable. So what does running [Dog ?x] do? Here's the choice diagram:
graph TB
start("[Dog ?x]") -- "<b>Dog benji.</b><br> ?x = benji" --> s1[Succeed]
style s1 fill:green
start -- "<b>Dog lassie.</b><br> ?x = lassie" --> s2(Succeed)
style s2 fill:green
Either path is acceptable, but since Dog isn't tagged [randomly], it prefers the first method over the second. So the command line prints “yes” and tells you that ?x = benji.
So this query is like asking "who is a dog?", or equivalently, “give me the name of a dog,” and it replies benji. If we tagged it [randomly] it would randomly choose one of the dogs each time we called it.
Methods as inference rules
Now suppose we add another task that doesn't print anything:
[predicate]
Animal ?x: [Dog ?x]
Animal ?x: [Cat ?x]
When we run [Animal lassie], it succeeds. Try it:
# Try: [Animal lassie]
[predicate]
Animal ?x: [Dog ?x]
Animal ?x: [Cat ?x]
[predicate]
Dog benji.
Dog lassie.
[predicate]
Cat morris.
Cat garfield.
It starts by choosing a method for Animal. The chosen method then calls either Dog or Cat, so then it chooses a method for that. Here's the choice tree:
graph TB
start("[Animal lassie]") -- "<b>Animal ?x: [Dog ?x]</b> <br> ?x = lassie" --> dog("[Dog lassie]")
dog -- "<b>Dog benji.</b>" --> f1(Fail)
style f1 fill:red
dog -- "<b>Dog lassie.</b>" --> s(Succeed)
style s fill:green
start -- "<b>Animal ?x: [Cat ?x]</b> <br> ?x = lassie" --> cat("[Cat lassie]")
cat -- "<b>Cat morris.</b>" --> f2(Fail)
style f2 fill:red
cat -- "<b>Cat garfield.</b>" --> f3(Fail)
style f3 fill:red
Since there is a successful path, the command line prints “yes”.
If we run [Animal garfield], that succeeds too:
# Try: [Animal garfield]
[predicate]
Animal ?x: [Dog ?x]
Animal ?x: [Cat ?x]
[predicate]
Dog benji.
Dog lassie.
[predicate]
Cat morris.
Cat garfield.
It's basically the same choice tree, but with different variable values, and so a different solution path:
graph TB
start("[Animal garfield]") -- "<b>Animal ?x: [Dog ?x]</b> <br> ?x = garfield" --> dog("[Dog garfield]")
dog -- "<b>Dog benji.</b>" --> f1(Fail)
style f1 fill:red
dog -- "<b>Dog lassie.</b>" --> f2(Fail)
style s fill:green
start -- "<b>Animal ?x: [Cat ?x]</b> <br> ?x = garfield" --> cat("[Cat garfield]")
cat -- "<b>Cat morris.</b>" --> f3(Fail)
style f2 fill:red
cat -- "<b>Cat garfield.</b>" --> s(Succeed)
style f3 fill:red
On the other hand, if we run [Animal coffee], that call fails:
# Try: [Animal coffee]
[predicate]
Animal ?x: [Dog ?x]
Animal ?x: [Cat ?x]
[predicate]
Dog benji.
Dog lassie.
[predicate]
Cat morris.
Cat garfield.
Because every possible set of choices fails:
graph TB
start("[Animal coffee]") -- "<b>Animal ?x: [Dog ?x]</b> <br> ?x = coffee" --> dog("[Dog coffee]")
dog -- "<b>Dog benji.</b>" --> f1(Fail)
style f1 fill:red
dog -- "<b>Dog lassie.</b>" --> f2(Fail)
style f4 fill:red
start -- "<b>Animal ?x: [Cat ?x]</b> <br> ?x = coffee" --> cat("[Cat coffee]")
cat -- "<b>Cat morris.</b>" --> f3(Fail)
style f2 fill:red
cat -- "<b>Cat garfield.</b>" --> f4(Fail)
style f3 fill:red
So, again Animal behaves like a test for animalhood: it succeeds when its argument is an animal. It fails when the argument isn't an animal given the information available to the computer. Once again, if we call [Animal ?a], it will report back to us a value for ?a that is an animal:
graph TB
start("[Animal ?a]") -- "<b>Animal ?x: [Dog ?x]</b> <br> ?x = ?a" --> dog("[Dog ?a]")
dog -- "<b>Dog benji.</b> <br> ?a = benji" --> f1(Succeed)
style f1 fill:green
dog -- "<b>Dog lassie.</b> <br> ?a = lassie" --> f2(Succeed)
style f4 fill:green
start -- "<b>Animal ?x: [Cat ?x]</b> <br> ?x = ?a" --> cat("[Cat ?a]")
cat -- "<b>Cat morris.</b> <br> ?a = morris" --> f3(Succeed)
style f2 fill:green
cat -- "<b>Cat garfield.</b> <br> ?a = garfield" --> f4(Succeed)
style f3 fill:green
If we don't include [randomly] on any of the tasks, Step will always report the leftmost successful path (?a = benji). But if we add [randomly] to all our tasks, then we have an random animal generator. Try it a few times:
# Try: [Animal ?a]
[predicate] [randomly]
Animal ?x: [Dog ?x]
Animal ?x: [Cat ?x]
[predicate] [randomly]
Dog benji.
Dog lassie.
[predicate] [randomly]
Cat morris.
Cat garfield.
Although the computer is really just matching calls to methods, we as humans can interpret the method:
Animal ?x: [Dog ?x]
as a rule saying:
If \(x\) is a dog, then it's an animal
Or equivalently:
All dogs are animals
And similarly, the method:
Animal ?x: [Cat ?x]
can be interpreted as:
All cats are animals.
This is why researchers in the 1970s jumped on this idea of choice + pattern-matching as being a kind of logical reasoning and called it logic programming.