Okay. So here we are, looking at the queue code from unit 1,
and what we're going to do is try to figure out
what kind of assertions we can add to this queue code
that would make it more robust with respect to mistakes.
So we go through the code--and this is the same code
we already looked at--and what you can see is
at the end, I've added a check rep function.
And what check rep is is a function that stands for check
representation, and this is a function
that we commonly add to a data structure
or to other functions that checks
the variables in the program for self-consistency.
And so what it's going to do is basically try
and terminate the program if some invariant that we know
should hold over the program's data structures
fails to hold.
What I first want to do, though, is run this program.
And when I run it, what's going to happen is
some testing code that I haven't shown you
is going to create a queue and call its
methods in a loop, and it's going to look at
the output of the queu and try to find any mistakes.
So the test function has the test oracle built into it
that I wrote that's going to try and see if our queue is correct.
What we hope is that it's correct,
and, also, we know that the check rep is going to succeed,
because it contains no assertions right now, so let's run.
Okay. Now that we've seen that our queue passes
the test harness, let's see if we can harden up the queue
a little bit by thinking of a good assertion to add to it.
And so I think that the first assertion that we're going to add
is going to be over the size variable.
And if you recall from earlier, the size variable tracks
the number of elements currently in the queue.
So let's go ahead and add an assertion about the size.
One thing we know about the size variable
is it should never be negative, because we
can't possibly ever have a negative number
of elements in a queue, so let's assert that self.size
is greater than or equal to zero.
And the other thing we can assert about self.size
is that it never exceeds self.max,
which is the constant variable, which counts the
most elements that could ever be in our queue.
So here we're asserting self.size is not negative
and doesn't exceed self.max, and so now
when I run the test harness again,
we're going to again check the queue for
functional correctness and also call the check rep.
Let's see what happens, so it printed a
finished over the old finished, and so that's good.
Okay. That invariant was good.
So what I want to do next is I'm going to break
our queue, so I'm going to break our queue
by making the enqueue fail to properly
reset the tail variable when it overflows.
What we have here is logic that when self.tail
is equal to self.max, we reset it back to 0.
And I'm going to set it to 1 instead.
So let's see what happens when we run the queue now.
It failed, and what it did is
it failed in an assertion inside the test harness.
This was in my test function down here on line 90.
See, we only have 40 lines of this code.
So way below is my test function, and we failed there.
What this means is we've messed with
our data structure in such a way that it actually
returns a wrong result, so this is the result
not be equal to the expected result assertion.
And so what we've done is we've created a data structure
that's broken, and when it returns wrong results,
this is going to be deeply buried in some program
that we care about, so it's going to return the wrong results
to some deeply buried part of the program, and probably
that program is going to keep running for a while.
And it's going to start to do very bad things.
It's going to lose track of webpages or it's going to
start to do other things that we don't like.
And so what we want is to write a tighter set of
assertions for our queue so that
our check rep can catch this before
we actually return the wrong thing to the user.
And so this is your API quiz.
Your API quiz is write an assertion
that goes under mine
in the check rep which catches
the bug in the queue before it can actually misbehave.
The trick you're going to have to do is
since our buggy code sets self-tail to 1,
that's in range, so another invariant besides
saying self.size is between 0 and self.max inclusive
is we could've asserted the same things for self.head
and self.tail, but the bug here
is not going to violate those particular checks.
Rather, what's going to violate is a relative check
between the values of head, tail and size.
And so that's what you should be thinking about
to add to your assertion here, and so what I want
you to do is come up with the correct
data structure invariant to assert here,
so that that assertion fails when we run our queue tester
before we actually return a wrong result.
And additionally what we're going to do is
we're going to check your assertion against a correct
version of the queue, so we're going to take your
check rep code and put it in the correct version of the queue
and check that it doesn't fail spuriously.
So what we want to do is write an assertion
that's tight enough that it catches the error that
we've introduced here but not so tight
that it always fails.
Okay. I hope you'll have fun with this.