Finale

Well, this is it - the final blog post. And you know what, in spite of having written so many critical posts earlier, I have to say I feel good having taken this course.

Of course, I still stick to my previous argument that the textbook should not simply be left for weekend reading. A lot of core object oriented concepts got relegated to the 2-minute quizzes, and I feel this course would be more true to its title if it discussed those issues. Even if there isn't all that much time to discuss them in class, the "object-oriented" projects should be brought on earlier, and projects like "Grades" should be modified so that the emphasis is on the object-oriented nature of the system we're trying to model and not on printing tables.  Prof. Downing might even consider the idea of having one massive project substitute the last 2-3 projects (after all one of the main concepts of object-oriented programming is to make huge complex projects manageable)

 Sure, if you look at it from the narrow day-to-day perspective, it may seem trivial; but when I look at the course as a whole - I feel it has been a worthwhile experience. Do I know more about C++ than when I started out - yes. Am I more confident about better software design and engineering practices - yes. Will all the tiny nuances about the language come together to help me write better code - definitely! The pair programming has also helped me - I was quite skeptical initially since I prefer not to irritate someone with my obsessive compulsive needs for bracing styles etc. But as the projects progressed, I got more and more comfortable working with my project partners - and it's a huge weight off your shoulders when you can do that. If anything, just the experience of collaborating so closely with someone on a project was worth the time and effort spent on this course.

#14 April 29

This week was entirely spent on learning about Handle classes in C++. This is a pretty interesting concept, and even more so, since the paper I reviewed a couple of weeks back is about smart pointers in C++ which can manage an underlying raw pointer -  which is almost exactly what the Handle classes do. 

We studied three different kinds of Handle classes - going from the simple Handle1, which is a very basic wrapper which doesn't even have support for de-referencing or indirection - implying that all the public API of the object of the underlying pointer will have to be replicated. The advantage, though is that the Handle1 objects can be looked upon as (polymorphic) objects and not pointers. A slightly more sophisticated version - Handle2 - overloads the de-reference and indirection pointers, thus saving us the trouble of replicating the public API in the handler class. But we lose the ability to look at Handle2 as an object - and it is now very clearly a pointer to the objects we want to use, however with memory management being handled internally. This resembles the unique_ptr in the C++ standard. It's also interesting to notice how the copy constructor works for these classes. Since they contain a pointer, we cannot simply copy over the pointer to the newly constructed class, because this could lead to delete being called twice on the same object. There are 2 solutions - one in which strict ownership is maintained, and another in which the object itself is copied. In the first one, the raw pointer "moves" to the newly constructed Handle, while the one in the old Handle is made NULL. If we want to keep using the old Handle, we can use the 2nd solution in which the pointer is cloned (the object it points to is copied, and the new pointer points to this new object). The final version of Handle is similar to C++'s shared_ptr. It uses reference counting so that multiple pointers could point to the same object and delete is called only when the last pointer to the object is deleted.

We used a variation of Handle1 for the Cell class in the project Life - and it allowed us to have a heterogeneous cell on the grid. By wrapping an underlying AbstractCell pointer, it allowed us to use polymorphism to have either a FredkinCell object or a ConwayCell object at a grid location.

#13 April 22

The 6th project is under our belts...and the only hurdle between me and sunny freedom is Test 3. We'll cross that bridge later.

The final project was based on Conway's game of life, but with a slight variation of the cells - Fredkin cells, also in the fray. I think the whole point of the project was to appreciate inheritance and abstract base classes and how polymorphism could be used to construct generic heterogenous structures. It was also interesting because I just reviewed a paper on smart pointers, and the Cell class that we were writing was similar to one - a wrapper around a raw pointer whose memory management was being dealt with internally. It's interesting to write the copy-assignment and copy constructors for such classes, because you have to be very careful about strict ownership of the raw pointer(so that delete is called only once) and other possibilities of memory leaks.

The code for the FredkinCell and the ConwayCell in itself was not hard to do at all - especially since my partner and I spent a good amount of time thinking about the design (we did not give in to the temptation of writing monolithic un-maintainable monster functions to avoid unit tests - though it is kind of ambiguous whether you should write unit tests for every implementation of shared functions). Our initial design was the simple 1-pass update, in which every cell - dead or alive - was checking its neighbors and updating its state accordingly. However, when we ran the ConwayCell case using valgrind - this was taking nearly 8 minutes to run! There was an obvious need for re-design! So we re-designed it so that only the live cells would be checked and its neighbors' neighbor counts would be updated. Much faster, but wait! There's havoc on the generic Cell board. A FredkinCell won't update a ConwayCell which is diagonally its neighbor, and a ConwayCell will try to update the neighbor count of a diagonally placed FredkinCell whether it likes to or not! The realization was that we had to handle orthogonal neighbors (the kind that FredkinCells recognize) and diagonal neighbors differently. With that tweak, and some optimizations as far as vector handling was concerned, our run time using valgrind dropped to ~6s! And without the overhead of valgrind's checks, it runs in less than a second. Now that's what we're talking about!

Another interesting issue that I'm glad to have learned is the concept of the virtual destructor. If you get used to Java, you forget the dangers of polymorphism being turned OFF by default. One of these is the innocuous fact that the free destructors the compiler generates for you in C++ can be dangerous when it comes to inheritance hierarchies. If you assign a derived class object to a base pointer and then call delete on it, unless the base destructor has been marked virtual - this will cause undefined behavior (the base destructor will be invoked, not the derived one)! You have been warned!

Paper review

Smart Pointers - What, Why, Which? - Yonat Sharon

Let me preface this review with the disclaimer that the article is a bit old, but what it tries to convey is as relevant today as it was back then. I have tried to update sections in this review with reference to the C++11 standard introduced last year. C++ programmers have the power to directly access memory addresses using pointers. But with great power comes great responsibility - explicit memory management can lead to all sorts of bugs : dangling pointers, memory leaks, pitfalls of including pointers in STL containers...just to name a few. This paper gives a clear introduction of smart pointers and the motivation behind their use.

Smart pointers emulate raw pointers in C++, but handle memory management. This allows the programmer to use the pointer normally, but not worry about cleaning up behind it. The simplest example of smart pointers is auto_ptr which is simply a wrapper around a raw pointer, behaving identically as far as dereferencing and indirection is concerned, but the difference lies in the destructor which performs the delete on the contained raw pointer. As of the C++11 standard, std::auto_ptr has been deprecated in favor of std::unique_ptr. I will briefly discuss this later.

The article mentions many reasons for using smart pointers apart from the automatic cleanup mentioned above : smart pointers get initialized to NULL by default, the danger of dangling pointers is reduced since smart pointers allow you to explicitly test for NULL to ensure that the pointer is in fact pointing to something, enforcing strict ownership means that the same resource will not be deleted more than once, they allow for exception safety (see the RAII idiom) and preclude a situation which could cause a memory leak because an exception was thrown before delete could be called on the pointer. Smart pointers can also be used to increase efficiency by following the Copy on Write (COW) strategy - i.e. the same object is used by multiple pointers so long as they behave in a read-only fashion; the moment one of them attempts to modify the object, the smart pointer makes a copy. This kind of semantics is seen in the std::string class. Another reason for using smart pointers is their use in STL containers. Since STL containers store objects by value, it’s not possible to have Child objects being stored in a vector<Parent>. To overcome this, we could have a vector<Parent*>, however cleaning up afterwards is error-prone and not exception-safe. Using a smart pointer that cleans up after itself is obviously desirable. However, not all smart pointers can be used since STL containers may copy/ delete their elements while resizing, etc.Thus any smart pointer that transfers ownership (auto_ptr, may it rest in peace, did this) cannot be used.

So which smart pointers should one use, and when? The article keeps this section generalized, so I’ll try to review it in terms of the C++11 standard. If you have been using std::auto_ptr, then your best bet is to switch to std::unique_ptr keeping in mind that now ownership transfer is explicit using move and copy construction is prohibited. The following is taken from Danny Kalev’s C++ reference guide:

auto_ptr<int> ap1(new int);
auto_ptr<int> ap2 = ap1; // OK, albeit unsafe
unique_ptr<int> up1(new int);
unique_ptr<int> up2 = up1; // compilation error
unique_ptr<int> up1(new int);
unique_ptr<int> up2 = move(up1); // ok, explicit move

Thus unique_ptr should be used when we want a single pointer to an object whose memory will automatically get reclaimed when the single owning pointer gets destroyed.

On the other hand, shared_ptr allows multiple pointers to point to the same object and the object is reclaimed only when the last shared_ptr to it is destroyed (it keeps track of this using reference counting, so one must beware of cycles). The use of shared_ptr is recommended within STL containers. There are other smart pointers that ship with the Boost library, and the interested reader can find a brief summary of them here and an interesting discussion on them here. In conclusion, smart pointers can be quite helpful in preventing subtle memory management bugs, and with the introduction of some of the popular Boost smart pointers in the current C++ standard, there’s all the more reason to use them.

#12 April 15th

The final project has been announced - it's the famous Conway's game of Life. It would be interesting to have glider guns as one of the input cases. It's also interesting to have another evolutionary-style project handed to us after Darwin. This one again, is solidly suited for object-oriented design and I suspect the first half of the semester was prepping us to get comfortable with the eccentricities of C++ so that we could tackle these with a lot of tools under our belts. This one also makes use of abstract classes and inheritance to reuse code, something which I have wanted to hone - and even if it's just one project, I appreciate that this is being thrown at us as part of the problem. I'm really looking forward to solving this one, but I need to get hold of a partner first! So, more on "Life experiences" later.

As for the material covered this week - we went through copy assignment in Java and C++ using a Complex class example. We also started on inheritance. Some of the interesting things that came out of this week's lectures are:

• In a constructor's initialization list, the order of variables is immaterial. Initialization of variables occurs in the order that the variables have been declared in the class.
• You can access private members of an object if it is the same type as yourself.
• A non-static const method CAN modify static data
• delete 0 is well defined to do nothing
• The Rule of Three comes in to the picture when you're writing a class that has to perform explicit memory management (say you're writing the vector class and need to manage the underlying array). It states that: "If you need to explicitly declare either the destructor, copy constructor or copy assignment operator yourself, you probably need to explicitly declare all three of them." Something important to keep in mind! See this StackOverflow article for the full story on copying objects.

#11 April 8th

I feel like a marathon runner entering the final few laps. There's 3 more weeks to go - so it's time to buckle up and get this thing done well.

This week had a diverse range of topics. We covered static and instance methods in both Java and C++. We also touched upon friends in C++. One interesting thing in that discussion was the following:

Say you have a templated global function:

template <typename T>
int f();

Then, if you want to declare all instances of it as a friend in one of your classes, the syntax is:

template<typename U>
friend int f(); //Notice the U is not used

However if you have another templated class C which contains f(), and you want all instances of C's f() to be friends with your class, then the syntax changes to:

template<typename U>
friend int C<U>::f();

Another new thing that I learned was the explicit keyword. Since C++ allows implicit conversions of the parameters while constructing objects, if the class Foo had a constructor with a single int argument, ordinarily it would allow something like:

Foo f = 2;

However, as you can imagine, this is a slippery slope towards a landmine of bugs (interesting visualization, eh). If that constructor was now declared as explicit, then the line would not compile anymore.

One final bit of trivia to end this post - one can overload member functions (class methods) not simply by changing the number and/or type of arguments, but also by changing the constness of that method.

#10 April 1st

It seems like I should write something witty given that it's April Fool's day, but I'm just too tired. This week has definitely been a learning experience. I was not aware of the tremendous variety with which variables could be declared and/ or initialized in C++. I know it sounds like a trivial thing, but it's not.

A case in point: We are working on the Darwin problem, which you can find more about here. This is, refreshingly, a problem which begs the OOP paradigm. So we made a Creature class to represent the different creatures in the world. Now the thing is, every Creature needs to have a reference to the Darwin world it belongs to. This is so that it can ask its world - "hey is there a wall ahead of me?" and other such useful questions. All of them need to have the same reference - so it's obvious that an externally created Darwin object must be passed to each Creature and stored as a const reference. However, in C++ you cannot initialize reference variables in the body of your constructor! And you definitely need to have it initialized since it's a reference variable, for crying out loud! Initialization lists come to the rescue. The initialization lists run before the constructors are called and can therefore initialize any member reference variables you may have declared.

That's not where the idiosyncrasies end. Have a static member variable in your class, do ya?! Well you can't initialize it in there. You MUST redeclare and intialize it outside the class in the form:

Type ClassName::staticMember = value;

Rather annoying!

An interesting list of other facts I learnt is:

• Local static variables get initialized only once and consequent initializations don't throw an error, they are simply ignored. Thus they can be considered as global variables as far as value is concerned, but with limited scope.
• If you have a statement globally, such as int j = g() , then g() runs before main, so that j can be initialized.
• You cannot have the same name for globals in 2 different C++ files unless one of them is static, which will make the global variable file-scoped.
• Uninitialized built-in local variables get initialized to garbage, global ones to 0.
• A static class variable in Java has just one copy across template flavors. Thus one cannot declare a static variable of the template type when defining the templated class. This, however is allowed in C++, since there is a copy per template flavor.

Well, this has definitely been an eye-opening experience for me. I hope I don't garbage-collect it all!

#9 March 25

And so ends the 2nd part in the CS 371p trilogy...

This Friday we had the second test in the course and it was in the same format as the previous one - 100 marks worth of multiple choice questions and then 50 marks worth of coding problems. Since some students may still be taking make-up exams, I won't discuss the actual content of the test; however I will remark on its structure. The multiple choice questions were anything but "statistically independent" (I'm a machine learning sorta guy). Based on bits of C++ trivia, entire series of questions (ranging from 25-40 marks) had the same options hinging on the very same concept. In other words, if you had the misfortune of forgetting that concept, you were going to lose out big time! The test felt a lot like gambling in Vegas - when you hit it, you hit it big or you simply lost everything! Rather unfair....and it has also left me a bit averse to the letter "A".

This is also a good time to reflect on why I took the course and what I feel I'm getting out of it. When I registered for this course, I did it for 2 reasons - I had heard that Prof. Downing ran an excellent albeit tight class and I also wanted to hone my C++ skills. Looking objectively at the course so far - it has been run well, quizzes keeping you on your toes, projects that help you grow comfortable with good software development practices and a lot of information. But when I step back and look at the bigger picture - I feel like the course lacks substance. We're getting tons of information, no doubt about that, but a lot of it simply seems to be C++/ Java trivia that you would perhaps learn for a coding certification test. Honestly, the only "object-oriented" parts of the course - a couple of papers and the textbook, have been completely self-study. The one object-oriented project so far seemed to have more of an emphasis on formatting the output than anything else. I feel that the course could be so much more enriching if the contents of the textbook weren't simply dismissed by a 5 point quiz; rather actively discussed and debated in class. How about giving a software design scenario and then discussing how to engineer a good design using object-oriented programming. Talking about designing well-thought out interfaces to make more pluggable code. Discussing code reuse and inheritance hierarchies, discussing how to layer abstractions into your design. These are very important skills to learn and we would benefit a lot from the experience of Prof. Downing as well as the collective knowledge of the class. Yet week after week we end up poring over minutiae like "Java caches String literals" (and this is a senior level course) or the many little code snippets like "Filling out an array with values" or "Checking if 2 arrays are equal" that are simply not intellectually stimulating after you've gone through the first example and understood different iterators.

I know that a good programmer has all these tips and tricks under his belt. However, it would be so much better if these were an addendum to the course rather than its entirety. In fact, simply flipping what is assigned reading and what is actually covered in class would benefit students greatly in my opinion.

#8 March 18

Welcome to the spring break edition of the 371p blog. I'm not entirely sure if we're even supposed to be writing one for this week, but hey I like tradition!

The only thing to discuss for this week is the Grades project. I had the impression that this could be easily done in a few hours. I was MISTAKEN! This has honestly been the most irritating project so far. The good first: implementation was a breeze and designing it by avoiding getters and setters was interesting and challenging.

But the sheer tedium of the formatted output! I think most of the time spent on this project was calculating what the width of a multitude of items would be and then how many corresponding spaces would make it look nice! Look, I'm all for formatted output - but please don't ask me to write unit tests where I have to manually count out spaces and -'s to the point where I'm going bat-crazy!

And that brings me to the next grouse - unit tests are good, but this "written-in-stone" 3 unit tests per function idea is not practical. There are some functions (like the constructors and destructors in the previous project) which don't need more than 1 or 2 unit tests. I often have way more than 3 unit tests for functions which have a number of corner cases etc., but I have started writing more monolithic functions (far less cohesive than I would want them to be) simply to avoid writing 3 unit tests for simple helper functions like calculating the number of digits in an integer etc. This is obviously not desirable and I hope Prof. Downing leaves it to the students' discretion as to what to unit test and to what degree.

I did learn a lot about C++ formatting - I'd become too used to the C-style printf format specifiers. The article on getters and setters was interesting too, though labeling them as evil is probably extreme. Anyway, I leave you with a meme I never knew existed:

#7 Mar 11

Well this was a slow week in the OOP class. Most of this week was spent discussing the ins and outs of arrays in C++. How we can only use it as a pointer when passed as a functional argument, how you can dynamically initialize them with values, but cannot initialize them with the same syntactic sweetness as int i = j. The same thing goes for when you're trying to reassign an array tonanother array. Something as simple yet dumb as a = b where a and b are arrays can actually cause a memory leak if you have created a on the heap. So it all boils down to use vectors - they are a part of the standard template library, they provide the syntactic sugar which lets you handle them very nearly like built-in types and are also blazingly fast about it. But what personally tilts the balance in favor of vectors is the fact that they handle all memory management on their own under the covers, so the chances of having a memory leak are now very low as compared to when we were using arrays.

This also brings us to our first really Object Oriented project for the semester. We're basically given a bunch of scores for students in a course and are expected to compute the statistics on it. While honestly this doesn't really need an object oriented approach to solve it I can still see why making a Student object might be helpful - especially is this were to go on to become part of a more complex system. The getters and setters are evil ideology makes a lot of sense once you think about it, and also brings up the question - how do you come up with a good design. In my case, I'm keeping most of the statistical functionality with the Course class and only personal stuff like ID and individual scores with the Student. Of course, this means that student objects will have to pass over their vector of scores to the course object, but I could not see a way around this minimal message passing. This project also made me realize how much I like Python :)

#6 March 4

Another week and some more intricacies of C++ come to light - the many different uses of the const keyword. While I have covered const pointers before, it's still handy to brush up on how const can change the usage of a variable or a pointer depending on how you place it in the declaration.

So let's break things down:
When you declare something as const, quite intuitively, you're saying that it can't be changed. This obviously means that a const variable MUST be initialized during declaration.
So, for example:

const i = 2;

would initialize the constant in i to 2 and then you would not be able to modify it (i becomes read-only).

This becomes slightly more tricky once you start using pointers:

const int* p = &i;
int* const p = &i;

In the first case, we're declaring a pointer to a constant, i.e., the value being pointed to by p (in this case i) must be constant and cannot be changed, while p itself can. Thus I can reassign p, but something like ++*p would not be allowed.

In the second case, we're declaring a constant pointer. This means once initialized to some address, we will not be able to modify p. This is particularly useful if you think of pointers being returned to indicate the start of an allocated memory location - we want to ensure that we keep this address constant.

There are other variants to this, including mixing it up with references, but once these 2 have been clearly distinguished, the rest fall into place.

#5 Feb 26

So begins the 2nd part of the course (I've logically divided it into 3 parts based on the Tests). First piece of advice - don't miss a single class! Due to personal reasons, I missed the class on Monday - when the 3rd project was being described - it's basically to implement the functionality of a heap. I felt lost when I came to class the other day - partly because there's no specs listed on the project page and also because I didn't realize how dependent I was to little things mentioned in class which help during quizzes and the project implementation. But I think I've caught up and now the project is going along full-steam ahead! Pair programming is going well - and I think I'm lucky to have found a partner who's as obsessive about correct indentation, spacing and brace-styles as I am!

So I don't have much material to talk about, since the class I did attend was mostly spent in re-introducing the different versions of the sum function for different iterators. Readings have finally started - and the quiz brought up the point of IS-A (inheritance) vs HAS-A (containment). For now, it's back to the project - we're knee-deep in pointer territory and you never know when a stray pointer could attack (the dereferenced ones are particularly vicious)!

#4 Feb 19

The week of the test...<Hitchcock scream + thunder and lightning>. Well, not so much - it was a pretty simple test if you've been following the material in class - and the best part was that most of it was a multiple-choice format which meant that we got the results in a day. I've always found the aftermath of a test to be more stressful than the test or its preparation, so I was quite happy.

This week we mostly covered different data structures, container classes and the cost of performing operations on those structures. But before I talk about that, there was one point made about using references instead of pointers which I really liked:
A reference always needs an l-value, so if you have a function that takes an argument by reference, mistakenly doing something like f(0) will cause a compiler error, but if you were taking the argument by pointer, then it would compile - but now you're dealing with that dark evil which has haunted programmers for centuries - the NULL pointer!

Back to data structures - the summary of all that was taught can be found in Prof. Downing's schedule here. Some interesting things in the discussion -

• A Deque is a variation of ArrayList except that instead of being front-loaded, it is center-loaded. This means that the cost of insertion and removal becomes an amortized constant - way better than the O(n) it was for insertion into an ArrayList. 
• Also, stacks and queues are backed up by sequential structures, but queues cannot be backed by vector since vector does not offer a push_front / pop_front functionality. (It's O(n) for front-access, but ~O(1) for back-access)
• Similarly, priority_queues cannot be backed by lists since they need to implement heaps which need indexing capability. Also, it can't be modified in place since it doesn't return an l-value.

Also, this week we turned in project 2  - the Australian voting problem. The problem itself was quite easy - the unit tests took a very long time, since the problem input was quite cumbersome. Also, we did it as a pair programming exercise. The experience was a mixed bag - it's always better to have another pair of eyes on the code you do, but managing time to have compatible schedules so that we could program together was more of a challenge than the problem itself. This led to us tackling the problem quite late, which is something I dislike since I prefer finishing off assignments as soon as I possibly can.
I'm looking forward to see how the other projects go. In the meantime, do not be fooled into extending the XP philosophy into your shopping patterns (from xkcd.com):

Btw, did you realize that a third of the course is already complete!

#3 Feb 12

This week was mostly a continuation of the discussion of exceptions. Some of the things that I found interesting:

• C++ can throw any type whatsoever, it doesn't have to be an exception (soon you might see an int hurtling over your head!)
• If you are doing exception handling in C++, you should always throw by value and catch by reference. Catching it by value leads to 2 copies (ugly) and catching it by pointer means you have to throw a pointer and that can lead to all sorts of memory management hell.
• Stack allocation is faster than heap allocation, so avoid using the new operator if you can.
• Wondering what the differences between references and pointers are? Well one is that you can always declare a pointer variable uninitialized and it's OK to reassign them to different variables. References NEED to be initialized to some variable, and like swans - they mate for life.
• Finally in Java, (I know this but tend to ignore it while programming) use StringBuilder when repeatedly concatenating Strings, since doing something like str1 += str2 causes a new String to be built and assigned to str1 while its older value is garbage collected (they're immutable, remember)

We also started on the UVa Australian Voting problem. The logic seems pretty straightforward, once you're past the reading/ writing issues. More on that next week.

#2 Feb 5

This week was submission week - and while Collatz V1 went as smoothly as a warm knife through butter, V2 nearly drove me insane with the obstinate "wrong answer" posted after 2 excruciating seconds of running the code. And I wasn't alone! This led tons of acceptance testing and then to a hailstorm of comments and discussions on Piazza - and finally it turned out that Sphere wasn't, in fact, expecting the right answer, rather one that had been masked to 32-bits even though the calculations clearly led to numbers beyond that range. Who would have known!! Anyway, Project 1 is done and dusted...and it's time to move on to Project 2, and with it, pair programming! More on that next week!

As far as class material goes, we've mostly been covering assertions and exceptions and also the l-value, r-value concepts related to operators. So far so good....more to come! 

#1 Jan 29

Well, it's almost been a fortnight of classes for CS 371p - and my first impression is that this isn't the standard object-oriented class I thought it would be. I had the idea we'd be going over inheritance, polymorphism, abstraction, yada yada yada. It's refreshing to have these ideas be presented (I'm hoping they will be in due course) as something straight out of Google Code Jam. Project 1 is chugging along nicely - in fact, the course seems more related to software development than OOP, but good programming practice is just good programming practice, so I can't complain! Also, like it or not, Prof. Downing keeps you on your toes with his questions. The quizzes are neat in that they are actually ideas for you to optimize your code (damn it Collatz V2, I'm going to get you!). I'm surprised at the level of detail Prof. Downing is explaining the code - this is the first course I've taken that where every line of every function has been examined in such excruciating detail. I wonder if this is simply for the first project or if the entire course is structured this way - we'll have to wait and watch.

In the meantime, here's a visualization of the Collatz fractal: