Obj births and deathsFoo,
you define the destructor like this:
~Foo() { whatever-you-want-to-do }
We can use this, for example, to simply keep track of the
number of Obj's created and destroyed in our
interpreter. The first thing I want you to do is to modify
your interpreter by adding global variables for counting the
number of Obj's created and destroyed,
adding constructors and destructors to the definition of
Obj to increment the
counters approproiately and, immediately before returning from
main(), to print out the number of
Obj's created and destroyed. Here's how you
should do the first two of these:
// Structure for representing SPL objects by a type/value pair
int objccount = 0, objdcount = 0;
class Obj
{
public:
int otype; union { int ival; bool bval; Closure *fval; };
Obj() { ++objccount; }
~Obj() { ++objdcount; }
};
You might need to add something like this to the loop inside main, in order to get it to stop at the end of input:
if (tree == 0) break;Run this code on the following example (press Ctrl-D after pasting it, to end the input):
new fib := lambda n { if (n < 2) { res := 1; } else { res := fib(n-1) + fib(n-2); } };
write fib(20);
Obj's than were created.
This should cause some consternation. What's going on is
something that's specific to C++. Since C++ uses the
value model for variables and has pass-by-value as its
default for passing function parameters, calling a function
with an Obj as an argument creates a copy of the
Obj, and that copy is made by a special
constructor called the copy constructor, not by the
default constructor from our class definition. If you don't
provide a copy constructor, the compiler provides one
automatically, and its automatic copy constructor isn't going
to increment objccount. So ... we need to define
the copy constructor for ourselves. Here it is (obviously it
needs to be added to the class definition):
Obj(const Obj &X) { ++objccount; *this = X; }
This constructor takes an Obj X and
makes a copy of it. You better be able to answer the
following question: Why does X need to be passed
by reference rather than by value?
Now what happens if you run your program?
fib(30)
it'll be in the millions. Why is this happening? To
investigate, let's consider the two other classes we've
created as part of our implementation of eval:
Frame and Closure. I want you to
instrument your interpreter so that it reports the number of
Frame's and (separately) the number of Closure's created and
destroyed as well as Obj's. Since we never pass
Frames and Closures as function arguments, just
Frame*'s and Closure*'s, you don't
need to worry about copy constructors.
Run your following input:
new fib := lambda n { if (n < 2) { res := 1; } else { res := fib(n-1) + fib(n-2); } };
write fib(20);
... and see how many Obj's,
Frames's and Closure's are created and
destroyed. Create a file called part3.txt in your lab13
directory and copy and paste the interpreter session including
creation/deletion results into the file.
new f := lambda x { res := x*x; };
new g := lambda y { res := lambda z { res := y*y + z*z; }; };
write f(5);
25
new h := g(7);
# At this point the frame generated from calling f can be thrown away.
# The frame generated from calling g cannot, because we'll need it if
# h ever gets called.
It's similarly tricky to determine whether a Closure can be
destroyed, and of course Closures refer to Frames so the
problems are tied together.
What we need is garbage collection, an automatic
method for determining which objects are still needed and
which can be reclaimed. We are going to build a garbage
collector for Frames and Closures. It's going to employ a
technique known as "mark and sweep". After each top-level
evaluation, i.e. when control returns to main, we'll call
the garbage collector. It'll start with the global frame
and loop through every Obj in the Frame, any
Closures there get marked as "live", and the marking process
continues recursively for every closures "env" Frame, as
well as the parent frame. When the marking process
completes, the sweep phase begins: all unmarked closures and
Frames get destroyed (i.e. we call delete on a
pointer to them).
To make this work, we need to
vector<Frame*> containing pointers to all
the Frames that have been created but not deleted. You
should use constructors to make sure a pointer to each new
Frame gets put in this vector (there is a "this" pointer in
C++, just like Java, which you will need), and the garbage
collector will worry about removing pointers from this
vector when Frames get destroyed. Go ahead and make this
vector a global variable. Isn't that liberating!
vector<Closure*> containing pointers to all
the Closures that have been created but not deleted. You
should use constructors to make sure a pointer to each new
Closure gets put in this vector (there is a "this" pointer in
C++, just like Java, which you will need), and the garbage
collector will worry about removing pointers from this
vector when Closures get destroyed. Go ahead and make this
vector a global variable as well. It's like drugs, it
doesn't take much to get hooked.
You should be able to test whether or not you were successful by printing out the lengths of these two vectors at the end of main. They ought to agree with your count of the number of Frames and Closures created.
void mark(Frame* env);
that
Obj in the
Frame env points to
(see below) and for each Obj that's a Closure
Frame
that closure points to
So how do we "loops through each Obj in the
Frame env points to"?
for(map<string,Obj>::iterator itr = env->begin(); itr != env->end(); ++itr)
{
in here "itr->second" is the Obj.
You see *itr is a pair<string,Obj>, i.e. a
string-Obj pair from the map. ".second" gives the second
element of that pair --- the Obj.
}
Convince yourself that you set "mark" to true for every Frame and Closure that's still "live", meaning it might be accessed by subsequent computation. Please: THINK ABOUT IT!
void
sweep(); that goes through the
closure-vector calling delete on each pointer in
the vector that points to an object whose mark is false and
also removing that entry from the vector. (Hint: use some kind of swap, then
pop_back to remove elements efficiently. But be very careful about how you handle iterating through a vector where elements are being removed -- what is the big challenge here?) Do the same for the
frame-vector. Then, go through all the frames and closures that are still left in your two vectors
and set the marks back to false. This is needed so that the next call to mark() has a clean slate to start with.
Finally: in main(), after you call
eval call mark(global); sweep();.
Test this on some examples to make sure that a) your
interpreter still works, and b) that you're successfully
reclaiming Closures, Frames, and Obj's. You can expect that when the program is over at least one frame (the global frame) is still around.
Depending on what variables you have, you might have a few others left. Think about whether what you have is correct.
eval. In the real world, this would be
unacceptable, because a single long computation may require
garbage collections before it is finished. What makes it
difficult to implement garbarge collection during a call to
eval is that the (potentially many recursive ) call(s) to eval
my have local Obj, Frame and Closure objects that the garbage
collector would have to take into account. With a virtual
machine architecture (see upcoming labs) this difficulty
doesn't arise, since there is no recursion and, essentially,
no local Obj/Frame/Closures to worry about.