So today is Valentine’s Day. I’m not big on huge fancy dinners or elaborate plans, and thankfully neither is my sweetheart. Today will be spent in with good food; a good movie; and, of course, a good gal.
Valentine’s Day == Chinese Food!
Feb 14th, 2010 by Bryan St. Amour
More tr1: Static Arrays
Feb 7th, 2010 by Bryan St. Amour
One of the old throwbacks to C in C++ is the notion of the “C-style array”: essentially a block of contiguous memory that you allocate either statically, or dynamically with malloc/free or new/delete. These structures were used in a time where efficiency was everything and programmers rode dinosaurs to work. In C++ there are many safe alternatives to the C-style array: vectors, lists, dequeues, etc. But sometimes you just want a simple, safe array to pass around. And that brings us to static arrays, C++ style 
Check out the following code:
void foo()
{
// Initialize my array of three ints.
std::tr1::array<int, 3> myStaticArray;
myStaticArray[0] = 0;
myStaticArray[1] = 1;
myStaticArray[2] = 2;
// The [ ] operator behaves just like a traditional array: unchecked, dangerous.
for (unsigned i = 0; i < 3; ++i)
{
cout << myStaticArray[i] << endl;
}
// The array also offers safe alternatives. The at() method is a bounds-checked version of the [ ] operator. Also note the use of size().
for (unsigned i = 0; i < myStaticArray.size(); ++i)
{
cout << myStaticArray.at(i) << endl;
}
}
As you can see, there are safe alternatives to traditional array indexing, but the unchecked ways are still around in case you still need every ounce of speed out of your application.
Checked Arrays: another example of how modern C++ is safer and cleaner than traditional C. These, in conjunction with smart pointers, and a whole plethora of data structures and algorithms in the STL, make C++ a joy to work with.
Shared pointers, and why you should use them
Jan 31st, 2010 by Bryan St. Amour
NOTE: The ideas expressed below are in part based on the book Effective C++ by Scott Myers. He uses auto_ptr in his example, but essentially the lesson is the same.
Let’s face it: pointers are dangerous. If you allocate something, you always have to make sure you deallocate it, or you will end up with a memory leak. Under most circumstances this is easy; for every new, you should have a matching delete. However when dangerous things like exceptions are thrown into the mix, making sure to free your memory can become a daunting task, and you may end up with a lot of code duplication.
Here’s an example.
void foo()
{
Silly* mySilly = CreateSilly();
/* Do some stuff with mySilly here. */
delete mySilly;
}
This kind of code can be common especially if you’re having to use old C libraries. Notice that you’re expected to delete your created Silly yourself. All of this looks pretty standard, but what if somewhere in the body of the function an exception gets thrown? When an exception is thrown in C++, all local variables declared have their destructors called, but no such claim is made for variables declared on the free store with new/delete or malloc/free. Essentially in the above code, your mySilly may never be freed!
One way to fix this is with a try/catch block, as seen below:
void foo()
{
Silly mySilly = CreateSilly();
try
{
/* Here be dragons */
}
catch (...)
{
delete mySilly;
}
delete mySilly;
}
Safe, but notice the code duplication? That should set off some red flags. Now an ideal solution would be to have some sort of way to delete mySilly in a 100% assured way, and that is where the RAII pattern comes into play.
RAII stands for “Resource Allocation is Initialization”. Essentially any time you need to access a resource, such as memory on the free store, a file pointer, an area of shared memory, etc. you should be wrapping it in an object such that:
- Your resource can be allocated safely in a constructor
- Your resource can be safely deleted in a destructor.
And this is where smart pointers come into play. The boost library has some amazing things, but one of the most useful parts of boost is the shared_ptr class. shared_ptr is a templated class whose job is to allocate something in its constructor, and free it in its destructor. Because of operator overloading, shared_ptr behaves semantically the same as a raw pointer, and it uses reference counting internally to ensure that nothing gets deleted if there are multiple shared pointers pointing at the same piece of data.
Our code example above becomes this:
void foo()
{
shared_ptr<Silly> mySillyPtr(CreateSilly());
/* Do some dangerous stuff here. */
}
If our dangerous section throws an exception, the destructor of mySillyPtr gets called, which frees the memory (if it’s the only pointer to it), and thus no memory leaks occur. Notice how much simpler the above code is compared to the try/catch code.
The boost shared_ptr can be used either by downloading the boost library and including the file <boost/shared_ptr.hpp> or it can be obtained in the <tr1/memory> header file, since shared_ptr may find its way into the next C++ standard update.
Shared pointers are yet one more reason to use the many new modern features of C++ over the old C techniques as often as you can. Properly coded C++ should leak no memory at all
Good Morning World!
Jan 5th, 2010 by Bryan St. Amour
By the time this post gets published it won’t be early morning any more. However I have had the most relaxing morning! I start classes again this Thursday, so I need to get my sleep schedule back on track. I was on a good routine, then I hit a bout of sleep trouble making it hard to sleep before 4 or so in the morning. Thus as a response I started sleeping later into the day, which is never good.
Tomorrow I plan to wake up even earlier than I did today. I would eventually like to get to a point where when noon crawls around I feel like I’ve already accomplished half of a day’s worth of activities.
Decking the halls with fibonaccis
Dec 14th, 2009 by Bryan St. Amour
Today I’d like to show off how awesome the Haskell language is with a few example programs. This blog is valid Literate Haskell, which means that you should be able to copy this entire text, save it with a .lhs extension, and immediatly be able to run the code!
Today I’m going to be showcasing three different ways of computing Fibonacci Numbers.
First some boilerplate code: a module name and some imports. We’ll be using the State Monad for two examples, the function nub from Data.List, and some funky functors in Control.Applicative to help with the testing.
> module Fib where
> import Control.Monad.State
> import Data.List
> import Control.Applicative
The below method comes courtesy of Thomas Hartman from the Patch-Tag blog. I belive that it shows how elegant Haskell code can look, even while using the State Monad to hide the plumbing. This function computes the nth Fibonacci number iteratively, and the below code looks dangerously non-functional. The function takes advantage of the State Monad to store state, but the overall function is still “pure”. Monads give you a lot of expressive power
> fibs1 :: Integer -> Integer
> fibs1 n = flip evalState (0, 1) $ do
> forM_ [0..n-1] $ \_ -> do
> (a, b) <- get
> put (b, a+b)
> (a, _) <- get
> return a
The next function computes Fibonacci numbers using a Dynamic Programming method called memoization. Essentially it stores previously computed numbers in a lookup table so that future computations take constant time. Note however that since this code uses a list to store the values, the lookup will not be constant, but it’s simpler this way. For real performance we can use an array or a hash table.
Like the above function, fibs2 uses the State Monad to store some state behind the scenes. This time it stores the table of previously computed values. Every time our function is called, it first checks the table to see if the asked for Fibonacci number has already been computed. If so, no work needs to be done! However if there is no entry for n, fibs2 computes it, stores it, and then returns it! How neat is that! Be careful, the following code isn’t as elegant as the code above:
> fibs2 :: Integer -> Integer
> fibs2 n = evalState (fibs2′ n) [(0,0), (1,1)]
> where
> fibs2′ n = do
> table <- get
> case lookup n table of
> Just m -> return m
> Nothing -> do
> n’ <- fibs2′ (n-1)
> n” <- fibs2′ (n-2)
> let m’ = n’ + n”
> table’ <- get
> put ((n, m’) : table’)
> return m’
Finally we have the naive definition of Fibonacci. This function is almost guaranteed to blow its stack after about thirty iterations. The actual runtime complexity is of order 
> fibs3 :: Integer -> Integer
> fibs3 0 = 0
> fibs3 1 = 1
> fibs3 n = fibs3 (n-1) + fibs3 (n-2)
The final little bit of code simply tests the above three functions to see if they return the same value. We could test this manually, but coding stuff is fun, so why not?
The <*> operator takes a list of functions on the left and applies them to a list of numbers on the right (essentially). We only wish to test our functions on the number n, hence the singleton list. Next the nub function, defined in Data.List, removes duplicate elements from a list. Since all of our functions return the same value (we hope), the resulting list when passed through nub should simply be the nth Fibonacci number. To test this, we check its length. If more than one number remains in the list, that means we have a problem with one of our functions.
Running testFibs, we should get back the value True, meaning all of our Fibonacci functions return the same number back.
> testFibs :: Integer -> Bool
> testFibs n = length results == 1
> where results = nub $ [fibs1, fibs2, fibs3] <*> [n]
To finish off this post, I’ll also leave you with the famous Haskell one-liner to generate an infinite list of Fibonaccis. The code takes use of a recursive definition and is very concise:
> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
If I don’t blog again this season, have a happy holiday, and I’ll see you in the new year
An example of how to solve a basic recurrence
Dec 13th, 2009 by Bryan St. Amour
The time complexity of most recursive algorithms can be represented by a mathematical function called a recurrence. An example of such function is
As you can see, solving for some n involves solving for 
Solving recurrences involves a sort of backwards induction technique. Step back for a moment and recall the definition of Big-oh:
That reads, 
So, the first task is to pick a 
There, that should do. Basically if we’re looking at solving this recurrence for
Since 
From the inequality previously discussed, and our inductive hypothesis, we have 
By getting rid of the recursive term, we have already made this recurrence one step easier to solve. Next, from the rules of logarithms, we transform the equation into
Notice here that if we pick out 
We have concluded the inductive step, and now all that remains is to show it works for the base case. Since our 
Therefore we can conclude that 
Notice that in the above example I was not as mathematically formal as I could have been. The above solution works, and is a pretty good outline of how to solve a generic recurrence. I hope this helps someone.
Test Post
Dec 5th, 2009 by Bryan St. Amour
This is only a test post. I downloaded some desktop blogging software and wanted to test it out… This post is the result of said test.
Nice Weather
Nov 14th, 2009 by Bryan St. Amour
… For November. It’s supposed to be chilly out now isn’t it?
November is my favourite month: the leaves change colours and the weather gets chilly (but not too chilly). It’s the perfect time of year for a nice afternoon walk, or for a casual game of frisbee.
Speaking of frisbee, if you’re around the University of Windsor and see a gang of scruffy-looking dudes playing frisbee between Erie and Essex Halls, feel free to join in. We’re out there as often as we can be, and the more the merrier.
Five Things …
Oct 25th, 2009 by Bryan St. Amour
… you may not know about me.
- I hold a second degree black belt in Issinryu Karate
- I am French and Italian, yet speak neither French nor Italian
- I was a huge fan of the band AFI during their Black Sails – Art of Drowning years.
- I did not own a cell phone until about a month ago. I’m still getting used to living in the 21st century.
- My biggest fear is that one day we will be living in a cybernetic future. The first “human-computer” virus will bluescreen all civilization.
Welcome Week – Over!
Sep 10th, 2009 by Bryan St. Amour
Welcome Week is finally over, and I’m surprised at how well it went. This year CSS and SciSoc teamed up to deliver an excellent BBQ for the first years, and despite the weather not behaving nicely, I think we did a pretty good job. One less thing to worry about, time for classes.