language works.

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

rule-based control language.

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

one can be anything.

So in this little pattern-matching syntax,

there's only one distinction you make.

There's either literal things or variables, and variables

begin with question mark.

So this matches any list of three things of which the

first is a and the second is c.

This one matches any list of three things of which the

first is the symbol job.

The second can be anything.

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

means arbitrary number.

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

the first is a.

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

be the same thing.

They're both called x.

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

you've already seen.

And remember, that's implemented by some procedure

called match.

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

that are already in this dictionary?

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,

that says x equals a.

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

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

dictionary to say that x equals a.

And the result of the match is the extended dictionary that

says x equals a and y equals b.

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

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

match, says that it fails.

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

a, then the matcher would put out fail.

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

been doing before.

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

It's essentially the same matcher.

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

we're not worrying about arbitrary constants and

expressions and things.

There's just variables and constants.

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

Primitive query is going to be a rather complicated thing.

It's going to be--

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

That's a query we might type in.

That's going to be implemented in the system.

We'll think of it as this little box.

Here's the primitive query.

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

and put out a stream.

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

where two streams come in and one stream goes out.

What these streams are going to be is

down here is the database.

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?

Oh, job of Alyssa is something and some

other job is something.

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

the stream.

That's what comes in here.

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

and matching the database with respect to this dictionary

that's coming in.

So for each fact in the database, it calls the matcher

using the pattern, fact, and dictionary.

And every time it gets a good match, it puts out the

extended dictionary.

So, for example, if this one comes in and it finds a match,

out will come a dictionary that in this case will have y

equals programmer and x equals something.

y is programmer, x is something, and d

is whatever it found.

And that's all.

And, of course, it's going to try this for every fact in the

dictionary.

So it might find lots of them.

It might find another one that says y equals programmer and x

equals, and d equals.

So for one frame coming in, it might put out--

for one dictionary coming in, it might put out a lot of

dictionaries, or it might put out none.

It might have something that wouldn't match

like x equals FOO.

This one might not match anything in which case nothing

will go into this stream corresponding to this frame.

Or what you might do is put in an empty frame, and an empty

frame says try matching all ways--

find all possible ways of matching the query against

something in the database subject to no previous

restrictions.

And if you think about what that means, that's just the

computation that's done when you type in a query right off.

It tries to find all matches.

So a primitive query sets up this mechanism.

And what the language does, when you type in the query at

the top level, it takes this mechanism, feeds in one single

empty dictionary, and then for each thing that comes out

takes the original query and instantiates the result with

all the different dictionaries, producing a new

stream of instantiated patterns here.

And that's what gets printed on the terminal.

That's the basic mechanism going on there.

Well, why is that so complicated?

You probably can think of a lot simpler ways to arrange

this match for a primitive query rather than having all

of these streams floating around.

And the answer is--

you probably guess already.

The answer is this thing extends elegantly to implement

the means of combination.

So, for instance, suppose I don't only want to do this.

I don't want to say who to be everybody's job description.

Suppose I want to say AND the job of x is d dot y and the

supervisor of x is z.

Now, supervisor of x is z is going to be another primitive

query that has the same shape to take in a stream of data

objects, a stream of initial dictionaries, which are the

restrictions to try and use when you match, and it's going

to put out a stream of dictionaries.

So that's what this primitive query looks like.

And how do I implement the AND?

Well, it's simple.

I just hook them together.

I take the output of this one, and I put that to the

input of that one.

And I take the dictionary here and I fan it out.

And then you see how that's going to work, because what's

going to happen is a frame will now come in here, which

has a binding for x, y, and d.

And then when this one gets it, it'll say, oh, gee,

subject to these restrictions, which now already have values

in the dictionary for y and x and d, it looks in the

database and says, gee, can I find any supervisor facts?

And if it finds any, out will come dictionaries which have

bindings for y and x and d and z now.

And then notice that because the frames coming in here have

these restrictions, that's the thing that assures that when

you do the AND, this x will mean the same thing as that x.

Because by the time something comes floating in here, x has

a value that you have to match against consistently.

And then you remember from the code from the matcher, there

was something in the way the matcher did dictionaries that

arrange consistent matches.

So there's AND.

The important point to notice is the general shape.

Look at what happened: the AND of two queries, say, P and Q.

Here's P and Q. The AND of two queries, well,

it looks like this.

Each query takes in a stream from the database, a stream of

inputs, and puts out a stream of outputs.

And the important point to notice is that if I draw a box

around this thing and say this is AND of P and Q, then that

box has exactly the same overall shape.

It's something that takes in a stream from the database.

Here it's going to get fanned out inside, but from the

outside you don't see that.

It takes an input stream and puts out an output stream.

So this is AND.

And then similarly, OR would look like this.

OR would--

although I didn't show you examples of OR.

OR would say can I find all ways of matching P or Q. So I

have P and Q. Each will have their shape.

And the way OR is implemented is I'll

take my database stream.

I'll fan it out.

I'll put one into P and one into Q. I'll take my initial

query stream coming in and fan it out.

So I'll look at all the answers I might get from P and

all the answers I might get from Q, and I'll put them

through some sort of thing that appends them or merges

the result into one stream, and that's what will come out.

And this whole thing from the outside is OR.

And again, you see it has the same overall shape when looked

at from the outside.

What's NOT?

NOT works kind of the same way.

If I have some query P, I take the primitive query for P.

Here, I'm going to implement NOT P. And NOT's just going to

act as a filter.

I'll take in the database and my original stream of

dictionaries coming in, and what NOT P will do is it will

filter these guys.

And the way it will filter it, it will say when I get in a

dictionary here, I'll find all the matches, and if I find

any, I'll throw it away.

And if I don't find any matches to something coming in

here, I'll just pass that through, so

NOT is a pure filter.

So AND is--

think of these sort of electoral

resistors or something.

AND is series combination and OR is parallel combination.

And then NOT is not going to extend any

dictionaries at all.

It's just going to filter it.

It's going to throw away the ones for which it

finds a way to match.

And list value is sort of the same way.

The filter's a little more complicated.