Name: Lecture 8B: Logic Programming, Part 2
Uploaded: 2020-03-29T16:25:23.000Z
Duration: 1 h 8 min 45 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

PROFESSOR: All right, well, we've seen how the query

Now, let's talk about how it's implemented.

You already pretty much can guess what's going on there.

At the bottom of it, there's a pattern matcher.

And we looked at a pattern matcher when we did the

Just to remind you, here are some sample patterns.

This is a pattern that will match any list of three things

of which the first is a and the second is c and the middle

So in this little pattern-matching syntax,

There's either literal things or variables, and variables

So this matches any list of three things of which the

This one matches any list of three things of which the

And the third is a list of two things of which the first is

the symbol computer and the second can be anything.

And this one, this next one matches any list of three

things, and the only difference is, here, the third

list, the first is the symbol computer, and then there's

some rest of the list. So this means two elements and this

And our language implementation isn't even

going to have to worry about implementing this dot because

that's automatically done by Lisp's reader.

Remember matchers also have some consistency in them.

This match is a list of three things of which

And the second and third can be anything, but they have to

And this matches a list of four things of which the first

is the fourth and the second is the same as the third.

And this last one matches any list that begins with a.

The first thing is a, and the rest can be anything.

So that's just a review of pattern matcher syntax that

And remember, that's implemented by some procedure

And match takes a pattern and some data and a dictionary.

And match asks the question is there any way to match this

pattern against this data object subject to the bindings

So, for instance, if we're going to match the pattern x,

y, y, x against the data a, b, b, a subject to a dictionary,

Then the matcher would say, yes, that's consistent.

These match, and it's consistent with what's in the

And the result of the match is the extended dictionary that

So a matcher takes in pattern data dictionary, puts out an

extended dictionary if it matches, or if it doesn't

So, for example, if I use the same pattern here, if I say

this x, y, y, x match a, b, b, a with the dictionary y equals

Well, you've already seen the code for a pattern matcher so

I'm not going to go over it, but it's the same thing we've

You saw that in the system on rule-based control.

In fact, I think the syntax is a little bit simpler because

we're not worrying about arbitrary constants and

OK, well, given that, what's a primitive query?

Primitive query is going to be a rather complicated thing.

let's think about the query job of x is d dot y.

That's going to be implemented in the system.

What this little box is going to do is take in two streams

So the shape of a primitive query is that it's a thing

where two streams come in and one stream goes out.

So we imagine all the things in the database sort of

sitting there in a stream and this thing sucks on them.

So what are some things that might be in the database?

So imagine all of the facts in the database sitting there in

What comes in here is a stream of dictionaries.

So one particular dictionary might say y equals programmer.

Now, what the query does when it gets in a dictionary from

this stream, it finds all possible ways of matching the

query against whatever is coming in from the database.

It looks at the query as a pattern, matches it against

any fact from the database or all possible ways of finding

Subtitles ListPlay Video

Lecture 8B: Logic Programming, Part 2

sort

pattern

structure

consistent