briancarper.net (λ) (Tag: C_plus_plus)

Math fun

Mon, 05 Nov 2007 00:07:30 -0800

I solved another 17 problems on Project Euler today. I've not solved more than the average Ruby participant on the site. But Rubyists have a pretty low average ranking on that site compared with other languages like Python and C.

Kind of makes sense given the number-crunching nature of most of the problems; Ruby isn't that kind of language. But it's also a bit surprising given that many of the problems there can be solved in one or two lines of code using standard Ruby libraries or a gem or two. In particular Ruby Facets is a great resource any time you find yourself dealing with combinatorics (permutations, combinations etc.).

Also, thanks to the speed of modern computers, given a decent algorithm, the difference between a C solution and a Ruby solution is often a matter of less than one second with C vs. 5 or 10 seconds with Ruby. The speed with which you can bang out working Ruby code likely more than offsets this.

I used to be good at math, back in the day. I was top of the class in all of the (few) calc classes I took. But then I verged into computer science and never looked back. Pure math never really held my interest. Now I find myself pretty lost even on simple math problems, which is sad.

Design Patterns continued

Tue, 14 Aug 2007 21:49:46 -0700

I'm about halfway through Design Patterns: Elements of Reusable Object-Oriented Software, and it's pretty good. I can't read Smalltalk very well, so that's an impediment, but most of the code is C++ so it's OK. The book itself is very well-written. The patterns are laid out in a clear and thorough format, explaining pros and cons, giving good examples of when to use each pattern and when not to. The patterns are grouped by what purpose they're trying to serve, and similar patterns are compared / contrasted. The book sounds almost like it's trying to prove to the world that design patterns really are practical and relevant, which is amusing in hindsight because they obviously succeeded in doing so, at least among some large portion of programmers today. The "Lexi" example program used to introduce patterns in the first third of the book is pretty dated at this point, based on what looks like Motif and Windows 3.1 widgets etc., which isn't surprising given that this book is from 1994.? But the catalogs that come after are still very relevant and a joy to read.

I've been struggling with something in a Rails app I've been working on. It has to do with how to organize a hierarchy of parallel "model" classes. I had a sort of Eureka moment reading Design Patterns, when I realized one of the patterns is exactly what I need to solve this problem. That's always good. My original solution was a horrendous hack involving runtime editing of classes to inject methods into them, and it was entirely broken when pushed beyond a certain point.

For some reason I tend to overlook inheritance as a "decision-making" tool.? Saying "I'll take any object that implements this interface" or "I'll take any object of this class or its subclasses" is a nice open-ended yet well-structured way of implementing a conditional.? "When you give me an object, if the object meets these criteria (by nature of being of a certain type or implementing a certain interface), proceed, else fail immediately."? You let the compiler or interpreter do the work for you.? And if the object meets the criteria, you can use it while blindly assuming it'll work as expected.? I'm always muddling up my code and trying to juggle a million things at once and doing other classes' work for them in all the wrong places, instead of letting classes properly handle their own business independently.? I definitely have some bad programming habits that I'm trying to unlearn, with some success I think.? If nothing else, I have experience doing things the wrong way and clearly seeing how and why they're wrong and the price of being wrong, so hopefully in the future I can avoid the same mistakes.

So, the book is largely about design decisions.? Not just breaking a problem up into parts, but breaking them up into parts with the right granularity, and with the right relationship to other parts, and with the ability to be easily used in the future to solve other problems.? That's the hard part of programming, I guess: making those design decisions.? For me anyways, at this point.? The book is helpful in that regard.

It's interesting how so many of these patterns have little or no relevance to Ruby. For example, the Abstract Factory pattern. The book uses Smalltalk as an example of a language with classes that are themselves objects like any other objects; a language with class objects can just use the class objects themselves as factories. As the book says, a class object is already a factory: a factory that produces objects of a single sort. And produces them very nicely, for that matter.? But other patterns do apply to Ruby. Obviously it also depends somewhat on the specific problem you're trying to solve, but it's fun to try to think of which patterns might be more relevant than others given how different a language like Ruby is from a C++ or Java or what have you.

expat

Sun, 12 Aug 2007 19:27:17 -0700

Thank you very much to numerodix's latest blog entry, which caused me to pay extra attention when upgrading system packages this week. I do read my elogs, but I don't read it as carefully as I should. I know I would have missed the warning about expat1 -> 2 necessitating a revdep-rebuild. I am going to tail them onto my desktop from now on.

expat really does affect a huge number of packages. Every GUI app on my system is affected. Possibly because GTK and QT are affected. But I don't know. urxvt and conky are also affected. Thankfully I had a Firefox window already open, along with a few urxvt terminals, when I did my expat upgrade. So as long as I don't close them I should be OK to keep using them for a while.

Looking at these issues, I realized today how little I know about the specifics of how linking works in Linux. I had a few days about it in a class on OS design in college, but it was a few years ago after all and we didn't go into much detail back then. This all inspired me to read up again on how linking works. I am reading this article on linux.org to start with. It looks like a good article, keeping in mind that someone who actually needs the article (e.g. me) is probably the worst person to judge whether it's a good article or not.

In other non-news, I recently ordered Design Patterns: Elements of Reusable Object-Oriented Software. I have a design patterns book already, namely Head First Design Patterns, but it's geared very specifically toward Java, and the whole book is written in a fairly unorthodox and sometimes extremely annoying way. It also doesn't cover ALL the design patterns, only a few. I'd like to read the original source, and read something that isn't polluted with Java ugliness.

DISASTROUS

Wed, 25 Jul 2007 21:06:35 -0700

If only I had a dime for every time Stroustrup used the phrase "This would be disastrous". It can refer to everything from misuse of pointers, to making your destructors non-virtual in a class that will be a base class for some derived class, to all sorts of other C++ pitfalls. I got my copy of Effective C++: 55 Specific Ways to Improve Your Programs and Designs today, and Meyers seems to use the same phrase a lot too. Maybe that says something about C++.

Maybe it's my twisted sense of humor, but I really get a kick out of that kind of over-the-top hyperbole though. The other thing I get a kick out of is programs that insult their users. You can't beat that for a laugh. Scott Meyers has already insulted the average uninformed C++ programmer a bunch of times in his book, and I'm only on chapter 1. Clearly good times are ahead.

Although I'm theoretically "done" reading Stroustrup, I've resolved to go back through the book and do all the end-of-chapter exercises. I figure that's a good place to start before trying any kind of larger project in C++. He must've included all those problems in there for a good reason. I can already think of something at work I'm going to try to redo in C++ to try to speed it up a bit compared to the Ruby version I have now. (I doubt I could make it any slower than Ruby if I tried.)

Tonight though I was distracted by a really fun site called Project Euler, which is a collection of small mathematical-type programming problems that you can try to solve for fun. I finished 15 of the 159 problems after work tonight. All in Ruby, of course. But I think I did the easy ones. Some are harder than others. But according to the FAQ, all problems on the site are meant to be able to be solved in less than a minute of runtime on a modern computer. Some of the problems are brute-force solvable but some others require some sophisticated algorithms to have any chance of solving before the universe ends. Coming up with an algorithm for a problem that has a nice big-O runtime is by far one of my weakest areas, so this is good practice.

You can register on the site, write a solution, submit it and it'll tell you if you're right. It also collects statistics (if you choose to give them) about who's using what programming language to solve the problems, and what country you're from. And then it ranks how many people use each language, and how successful each languages' users are (going by how many problems they've solved). So in that sense the whole site is a kind of programming language battle to the death. (Did some people really solve these problems in Tcl?)

If that site is any judge, C and C++ (lumped together perhaps inappropriately, according to Stroustrup anyways) is/are the most popular language(s), followed by Python and Java. Ruby made a good showing, which makes me happy. Ruby's immense standard libraries make many of the problems there trivial no-brainers. Either way, this seems to indicate that there are a lot of C programmers out there. Or it may be that the number-crunching mathematical nature of these problems lends itself well to C, which is why so many people picked C to solve it.

Ruby Interfaces

Wed, 25 Jul 2007 08:18:26 -0700

I'm almost done with The C++ Programming Language. My eyes started to glaze over when I hit the long drawn-out descriptions of some of the STL classes. It might be good as a reference but it doesn't do much to keep me awake at 6:30 AM on the bus every morning. The last couple chapters about overall design methodology are nice though. I just finally realized the usefulness of private inheritance, for example. I also learned about NVI after googling for related info, which is interesting.

I got to thinking a bit about how C++ inheritance differs from Ruby. (The answer is "a heck of a lot", obviously.) For example Ruby lacks the concept of interfaces or abstract classes for the most part. There's no built-in mechanism to say "A subclass must implement this method". The closest I've seen (via the Ruby mailing lists) is something like

class Base
  def foo
    raise NotImplementedError
  end
end

class Sub < Base
  def foo
    puts "IMPLEMENTED"
  end
end

Rubyists tend to say that this is not a good thing to do in Ruby. One reason given is that if you leave method foo out of class Base, and you don't implement it in class Sub, you'll get an exception when you try to use Sub#foo anyways. But in that case you'll get a NoMethodError, not a NotImplementedError, which isn't as nice; the benefit of raising a NotImplementedError is to say "This method SHOULD do something, but it doesn't YET because the programmer hasn't gotten around to writing it", as opposed to NoMethodError which says "This method doesn't exist, and I have no idea if it should or not".

Someone on the mailing list also raised a good point that Sub#method_missing may cause breakage unless you implement a method foo that raises an exception explicitly. Otherwise a call to Sub#foo may or may not raise an exception at all, depending on what method_missing does.

In Ruby, even if you have a Sub object, or even a Base object, you don't really know that it actually has a method called foo at the moment anyways, because someone could have used Module.remove_method to erase that method out of the class. And even if there's a foo method in class Sub that does the right thing, any object of type Sub could override it using a singleton class. So even given you know the class of an object, you can't know ahead of time if the method exists, and if it does exist you can't know exactly what it does, which kind of defeats the purpose of trying to enforce interfaces through inheritance. And to confuse matters further, again on the topic of method_missing, even if a method isn't defined as a method it may still be handled. Consider if someone implemented class Sub like this:

class Sub < Base
  def method_missing(sym, *args, &b)
    if sym == :foo
      puts "IMPLEMENTED!"
    end
  end
end

In this case, you still get a NotImplementedError when you try to call Sub#foo, because it was defined via Base. So there's an argument to be made that if a method isn't implemented, leave it undefined and let every class deal with it as it sees fit.

Interfaces of this sort also goes against duck typing. As long as an object has a method called foo that "does the right thing", a Rubyist would expect that it can be used anywhere you'd use a Base or Sub object. In Ruby it's pointless to force people to subclass Base just so they inherit a method of a certain name. Given a lack of multiple inheritance in Ruby, being forced to subclass Base may very well make it impossible to get an object to pass an "is a Base?" test.

Ruby has mixins via Modules, which are kind of like interfaces and seem to be used in the general spirit of interfaces pretty often. But nothing is enforced by the interpreter when you use them, which can be fun to debug.

class Foo
  include Comparable
end

f = Foo.new
f2 = Foo.new

puts f < f2

That code is perfectly legal, but obviously doesn't work because <=> is not defined. It's up to you whether you define <=> or not. If you don't, the methods you mixed in from Comparable will just fail at runtime, but again, with a perhaps somewhat less-than-ideal NoMethodError.

In place of explicit interfaces, what we have in Ruby seems to be lots and lots of convention. If you make a method that just so happens to be called to_s, it just so happens that your class will work with lots of other methods that expect it to exist. This is nice, if you already know the conventions, but if you don't know the conventions, you're screwed. I'm in the process of training someone at work to use Ruby, and I'm often asked "Where are all these conventions written down? How was I supposed to know that?" That's a good question. There's no way to know it, other than to read lots of other people's code. In a type-checked language you have the benefit of having right in front of your face a bit sign saying "I'm an abstract class. Implement me."

I can see the benefit in (and often take advantage of) the flexibility of Ruby, but I can also see potential benefit in the strong type checking of C++, when it comes to dealing with interfaces. I haven't written enough C++ to know which appeals to me more though.

Mozilla C++ portability guide

Wed, 18 Jul 2007 19:48:40 -0700

I'm up to Chapter 18 of Stroustrup's The C++ Programming Language. The templates chapter was painful and I had to read it twice. I think I got it the second time through. Stroustrup talks about how people ask him how long it takes to learn C++ and he says (paraphrased) "a year or two probably; be happy, it's not as long as it takes to learn a spoken language or a musical instrument". It's still frustrating. The syntax and whatnot are so easy to learn, but the idioms and common practices take forever to ingrain.

Today in my somewhat futile half-hearted attempt to learn autotools, I chanced upon the Mozilla C++ portability guide It includes such advice as:

Don't use templates.
Don't use exceptions.
Don't use namespaces.
Don't use the C++ standard library, not even iostream.
Don't put assignments in if statements.
Use macros.

This is interesting, since it's the exact opposite of what Stroustrup writes. And Stroustrup also says he wrote this book in such a way as to demonstrate "standard" portable code. I guess I don't doubt that the Mozilla guys know what they're talking about, but if that's the extent you have to bend in order to write "portable" code, I hope I don't ever have to.

Interfaces

Thu, 12 Jul 2007 21:31:23 -0700

I'm done with 10 chapters of my new book so far. There's some good stuff in there. I'm always glad when I get a book that makes me realize how little I actually know about something, because it's probably a good sign I'm learning something.

Stroustrup makes some nice comments about interfaces. He wrote a little lexer/parser program and then showed how he would break up the code into logical chunks and organize it. He split the "user interface" and the "implementer's interface" into two different pieces in the process. I'd never seen a problem laid out in quite that way done before. But it made me think about a lot of problems I have at work. When I think of "interface" I think of what the end-user sees when running the program. But the code a programmer sees when dealing with code you wrote is also an interface. In the interests of expediency at work I often find myself thinking "I have no time to clean up the backend. I'm smart enough to figure this out anyways, who cares if it's a bit clunky?" I'm pretty sure that comes back to haunt me more often than it should.

As a novice programmer, it's an effort just to get something that solves a problem at all. As you learn more, you start to think about how to solve it well: efficiently and cleanly. I think the next step is when you take it for granted that all the little parts of your program will work as they should; the new problem is getting all the little solutions to play well with solutions to other problems. I wonder sometimes how much of that part of it can be learned and how much of it is having a proper aesthetic taste and a proper way of thinking about problems.

It always amazes me just how easy it is to write horribly crappy code. Computer programming is like trying to shoot a target with a gun that has a nearly overwhelming tendency to want to point at your own foot.

I love that new textbook smell

Wed, 11 Jul 2007 20:53:47 -0700

So as I alluded to after chattering on for hours, C++ is my new language of the week/month(/year?). My copy of The C++ Programming Language came in the mail a day early today, so I got to read it on the bus ride home from work, which was fun. I've apparently already read five chapters without realizing. Time goes fast I guess. It's been a long time since I did homework problems, but I gave some of the ones in the book a shot.

You can really tell this is a book for geeks. From (?1.1.2):

The exercises vary considerably in difficulty, so they are marked with an estimate of their difficulty. The scale is exponential so that if a (1) exercise takes you ten minutes, a (2) exercise might take an hour, and a (*3) exercise might take a day.

Then he goes on to give some problems a difficulty of (*1.5), which means some exercises have fractional exponents for difficulty levels. I haven't quite worked out how many hours that comes to.

There's probably a reason all the non-geeks at work recoiled in horror when I gleefully brandished my shiny new book at them. For some reason no one took me up on my offer to let them read my book during their lunch break. Their loss.

Education

Sat, 07 Jul 2007 21:37:47 -0700

I've been out of college almost exactly four years. Looking back at my Computer Science classes, I think I can see some ways that my education was woefully inadequate. Or at least not what I wish it would have been, knowing what I (hope I) know now.

My classes were in C and C++ for the first year or two. I remember being very turned off of C++ because it didn't have a native "string" type and you always HAD to screw with null-terminated arrays of characters. I never once heard mentioned the STL or the benefits of using it, so far as I remember. Only a couple years after graduating did I learn that using C-style header files and functions in C++ was antiquated; it was tolerated in homework assignments and my professors didn't say much about it. I remember learning about C++ templates, but it was a chapter or two blown through in a week. We never did anything useful with them.

I remember distinctly someone asking a professor "which version" of C++ we were allowed to use on an assignment. He responded "standard". When pressed further, he conceded "whatever Visual C++ can handle". My university was and as far as I know remains a Microsoft sort of place. We all got Visual Studio "for free" (meaning it was included as a fee in our tuition, most probably). Linux wasn't discouraged, but all assignments had to be done in VC++. I wish that would have been different. I wish I'd have used gcc or something once or twice. Most of the professors I liked were crusty old Unix guys who advocated *nix personally if not formally in the curriculum; it's one of the things that got me interested in Linux. I wish I'd picked their brains more.

In my last year or so of classes, the entire university was in the process of phasing out C++ and teaching all the core classes in Java. I was lucky to get a mix of Java and C and C++, if only so I could see the differences between them, and I got enough of a taste of Java to know I don't like it. I had one Perl class (the only one offered, that I'm aware of), but it was half a term and focused on CGI. I had some assembler language classes but they were run on a little toy MIPS emulator in (of course) Windows. How bad must it be for the next generation of coders coming from my old college, who have Java as their primary or perhaps only language?

I remember learning about object oriented programming, but the only thing I actually learned from those courses was terminology: constructor, destructor, inspector, mutator. We learned about inheritance but nothing about how it can be useful. We learned about overloading and overriding operators and methods but never anything about when to do it and when not to. I think the word polymorphism was mentioned and defined, but never explained with good examples. We never touched design patterns; I read a book about those a few months ago and it was a real revelation in many ways.

I learned a lot about binary trees and stacks and priority queues and graph search algorithms. But I never really learned about when we should use those things and when not. I never had an assignment that said "Here's some data; pick the right data structure to model and organize and query the data and write a program that does it". In 90% of my classes I probably never wrote a program longer than 200 lines of code. My courses had me writing and re-writing and re-re-writing implementations of singly-linked lists until I was blue in the face. It's nice to know how those things work, but it's also nice to know that reinventing the wheel is stupid when you're trying to get a program done on a budget; they could have mentioned that tidbit at least in passing.

Strangely I never had a single database class in college. I never learned SQL until I taught myself after I graduated. If anything I would think SQL is almost essential for any programmer to know. I never learned shell scripting along the lines of bash scripting or Perl as a shell scripting language.

How about Vim? Vim has contributed greatly to whatever productivity I have at work (and home) nowadays. But the one time I remember it being mentioned in college was a professor saying something about "this really old and weird editor called VEE EYE, anyone ever heard of it?". Left to my own devices, I always used the sucktastic Visual Studio IDE, since it was the best thing I knew existed at the time. I did have one good class (again taught by one of the crusty old Unix guys) where we discussed the importance of a good editor, how syntax highlighting and auto-indentation can help a coder catch errors and be more productive. I don't remember if Vim was mentioned by name, I think it was more an advocation of fancy IDEs along the lines of Visual Studio. But it was something I wish we'd have gone into more detail on.

The thing I probably value most from my formal education are the things that are the least practically useful. Theory of computation stuff. Compiler design, programming language design, things like that. State machines and grammars and string parsing. The history and evolution of programming languages. How programming languages work under the hood, garbage collection algorithms, object heaps and call stacks. Those were really interesting and I think helpful in understanding what's really going on when you write and run code. But I'm unsure how much it helps in a practical sense, when your boss says "Give me this by Friday".

I'd say only within the past year have I even begun to approach the level of "adequate" programmer in terms of skill level, and it's almost entirely thanks to things I've learned on my own since college. Maybe I'm misremembering, maybe college gave me some kind of magical foundation upon which all other knowledge has been built. Maybe there isn't enough time in college to learn the things I wish I had learned. I don't buy that.

There's no doubt the piece of paper saying that I graduated has helped me in practical ways, e.g. finding and getting a job. But I can't help but think that things I've learned privately just because I like learning them has been more useful in being able to actually do my job. On that note, having started in high school with hideous old QBASIC, ventured through C and C++, hurried past Java, gone down the Perl path for a long while, briefly glanced at the likes of Haskell and PHP and many others, and ended up firmly in Ruby territory, I'm planning to revisit C++ again a bit now. Maybe it'll all make more sense now. I ordered a book last week, we'll see how it looks once it gets here.