This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.
3.9 Referential Garbage Collection
Loading...
From the course by University of California, Santa Cruz
C++ For C Programmers, Part B
70 ratings
From the lesson
Hex and the use of AI and C++ Move semantics
This module explains Min-Max and the Alpha-Beta algorithm for game playing. Its programming topics include C++ 11 Move semantics and a detailed example of referential garbage collection.
Meet the Instructors
Ira PohlProfessor
Computer Science
Now, we're gonna write a program that does all of this automatically.
And I think what you're gonna see with this program, the coding program,
is how it can also be used to expand on the ideas I've just said.
Can give you a general way to polymorphically evaluate expressions.
Very powerful.
There are other ideas buried in this program, so this one example
has several really powerful ideas and they're all very succinct.
One of the powerful ideas is, we're gonna use referential garbage collection.
So, the way we're coding this, referential garbage collection,
we're gonna have these big aggregates.
Like trees.
And we don't necessarily want these trees to proliferate.
So we want an efficient mechanism for
representing multiple trees, and if we need to clone a tree for some purpose,
we want that clone to be what's called a shallow copy or a referential copy.
So this example will show you how to do shallow copying and
garbage collection that's referential.
In referential garbage collection rather than a full copy,
we maintain pointers to aggregates.
So again, everybody's has come into this course form C.
The hallmark of proficiency programmers really understanding pointer.
Pointer is critical.
Pointer and the reference is critical.
And also in C you have to know how to use Malik and Free or
analogously in C++ you now have to use new and delete.
Now, we're not going to do a full copy.
Think about it this way.
If you're in the library and you need to use the Encyclopedia Britannica and
you're still old school so you wanna really get a hold of
the paper copy in the library, that's pretty expensive.
I think the last years of that encyclopedia, your cost for
a nicely bound Encyclopedia Britannica is something on the order of a $1,000.
So it's not like they're gonna let it out of the library, and
it's not like there's gonna be multiple copies.
It's gonna be a single copy.
But the single copy can service many people.
Why?
Cuz it's not being modified, and
each person can go and point at the section they need to use.
So since there's no modification, and
since there's ready access to different sections.
You can have many people using the one library copy efficiently.
It's somewhat the same way that we are going to allow
use of multiple copies in a program, where we don't need
to manufacture a new copy, that's a huge saving.
So when we don't need to manufacture a copy, but
we merely need to point at an existing copy, we'll do referential copying.
We'll just establish a new pointer.
Copying to the right place in the aggregate.
Just imagine pointing at the right position in the encyclopedia.
Now we may actually modify these aggregates,
and as we modify them, we may need to discard some.
And there is actually a call on knowing when to delete an object.
And that tends to be what's called the use, or reference count.
So there's going to be a A special variable in these aggregates.
Called how many people are pointing at me?
If I have many people pointing at me and
one guy no longer uses the Encyclopedia Britannica, I can't just close it down.
I still have to use the aggregate.
So until its use goes to zero, I don't abandon the aggregate.
So the use calendar is keeping track of how many
people are using it or how many, in our case, parts of the program are using it.
And only deletes it,
only does real deletion of the aggregate when the use counter goes to zero.
And any time we have a new instance for example, we modify an old instance.
We're gonna create a new instance and make its' use value one.
So that's referential, that's the heart of reverential correction and
we'll see that in this example.
So.
Here again think about what we're doing, we're doing evaluation of expressions,
the evaluation of expressions involves computing over an expression tree,
the basic element of the expression tree is going to be a node.
The node is gonna be represented by something we're calling
an abstract base class.
So there's lots of interesting stuff in this particular example.
First off node is gonna work with tree.
A tree is gonna be some series of nodes.
They're gonna be intimately connected.
It's not an inheritance relationship.
But because they're intimately connected I want both of them to be able to
access the other one, even its hidden parts for its' efficiency purposes,
so these are what we might call kissing cousins, and that's sort of a.
It's okay to see
their privates.
Here's what I said, that's the referential garbage collection file.
There will be an inheritance hierarchy, so I want things to be protected.
And then, I have these virtual functions.
Notice, very important that destructure is virtual.
If the destructor was not virtual, and
again by the end of running this example for you, writing it.
What you need to understand is why this needed to be virtual.
So that's a take away.
And then there's this notation.
The equals zero notation.
An equals zero means these are pure.
Meaning they are to be overridden.
But here they have no meaning.
And this has an effect why we call this abstract is there can be no
instances of node.
If there were instances of node then we would expect there to be
a meaning for these pure virtual functions.
And we could execute them but
since they don't have a meaning, we can't have instances.
So it's sort of a circular reasoning thing,
rather than call this some other kind of
programming language designer might have decided to just name this abstract.
It's inherently abstract through this little device.
So there's a bunch of takeaways.
Garbage collections for referential use, pure virtual functions and
abstract base classes, and the use of virtual destructors.
And here's this other.
Remember when we were doing the actual evaluation of the Polish expression
just a few instances ago, we walked around the tree.
So this is a tree, and the tree is going to again,
there's that kissing cousin relationship with node.
Notice, remember node is an abstract based class.
So there can't be concrete instances of node, but there can be pointer to node.
Pointer is okay.
Because the pointer is the base class type.
And that makes it polymorphic.
So this is a polymorphic pointer.
And that means that depending on what kind of actual node is defined later on
in the tree, like we'll have binary nodes doing binary plus.
By activating evaluations through this base class type,
we automatically through polymorphism,
dynamic dispatch, we call the right evaluation function,
the right member function in the class hierarchy.
This is where all these subtle ideas interact to get you a marvelous solution,
a very simple solution, and a solution that's readily extensible.
Okay, so as with many interesting classes, there's a whole bunch of constructors,
And these are for different kinds of trees,
like these would be trees in which there was an int,
a tree in which there was a variable, which would be a character.
We're gonna use simple characters to talk about variables.
It could be a tree with a unary operator,
it could be a tree who has a binary operator operating on two separate trees.
So these are analogous to the various expressions.
I could have the tree that's just 5, so that would be this first one and
its evaluation would just end up just being 5.
Or I can have a tree of two tress with a binary operator like plus and
then some subtrees here.
And these would both have to be evaluated before plus got evaluated.
And then this is, critical here, is this is again, what kind of constructor?
Look at the signature.
Everybody should immediately know what that is.
It's a copy constructor.
And notice referential copy.
And then notice the destructure, and this also, both are making use of use.
I'm also going to overload assignment and I'm going to overload evaluation.
And here evaluation is done via the base pointer and recall that that base pointer
is going to polymorphically, vowel is going to be a virtual function.
So this is gonna be done polymorphically.
So let's look at focus on two key elements in the last slide.
This gives you the exact way referential copying and deletion work.
If I have a pre-existing Encyclopedia Brittanica and
somebody else needs it and I'm not gonna modify it.
I just provide to that person a further
pointer and an increment use.
[COUGH] So if one person is already using it and I now copy it,
now there'll be two people using it.
So if there's one person using it, and I've copied it,
now there's a second person using it.
And I could have a third person, etc.
etc. So this use can keep going up.
Notice what's the order of copying?
Constant.
It's order 1.
Why?
Because this is just no matter how big the aggregate, nor how big the encyclopedia,
how big the tree, I only need to increment use pointer and do one assignment.
One assignment, one implementation.
Now, if for some reason I call a destructor,
let's say a person in the library is checking out and
he's no longer needing his access to
the Encyclopedia Britannica, that person goes away.
So we call the destructor.
It says decrement use.
And test.
Is use 0.
And only if use is 0 do we do the concrete.
The actual deletion only happens when use goes to 0.
So this protects us until we no longer need the aggregate.
Okay, let's turn to some other things that are interesting about this code.
Part of what we have is a polymorphic print routine.
Again, I'm gonna do things that are pointer based.
P is pointer to node.
It's the top of the hierarchy of nodes.
So it invokes dynamically at run time.
The appropriate print.
And then, I'll return.
This is just our normal way of overloading.
Our IO operation.
So print acts throughout this tree polymorphically.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
