Vincent Gable’s Blog

September 11, 2009

Never Start An Integer With 0

When programming, never start an integer with 0. Most programming languages treat a decimal number that starts with 0 as octal (base-8). So x = 013; does not set x to 13. Instead x is 11, because 013 is interpreted as 138 not 1310.

Languages with this quirk include: C, C++, Objective-C, Java, JavaScript, Perl, Python 3.0, and Ruby. If you add up the “market share” of these languages, it comes out to above 50%, which is why I say most languages.

“But I use {Smalltalk, Haskell, Lisp, etc.}”

I’m jealous that you get to use such a nice language. However, it’s bad programming hygiene to pick up habits that are dangerous in common languages.

Now, I assume you wouldn’t write 7 as 007, unless the leading zero(s) carried some extra meaning. There are cases where this clarity outweighs “cleanliness” (unless the code meant to be ported to a C-like language).

But you should at least be aware of this inter-lingual gotcha.

May 31, 2009

The Best Quicksort Ever

Filed under: Design,Programming,Sample Code | , , , ,
― Vincent Gable on May 31, 2009

The first time I saw this quicksort in Haskell was an eye opening moment,

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

The first line reads: “When you sort an empty list ([]), the result is another empty list”. The second line reads: “To sort a list whose first element is named x and the rest of which is named xs, sort the elements of xs that are less than x, sort the elements of xs that are greater than or equal to x, and concatenate (++) the results, with x sandwiched in the middle.”

The code is so concise, yet clear (even with cryptic variable names like xs). The day my professor wrote it on the whiteboard was the first time I internalized that there might be something good about the alien world of functional programming.

The biggest revelation to me was, filter (< x) xs . It’s amazing that (< x) builds a temporary, unnamed, function equivalent to C++,

bool lessThanX(AnyOrderedType y){
    return y < X;
//plus the definition of X somewhere...

Building a function! It’s still profound stuff to me. And clearly it really uses fewer lines of code. Amazingly, using list comprehension syntax is not more concise,

qsort (x:xs) = qsort [i | i <- xs, i < x] ++ [x] ++ qsort [i | i <- xs, i <= x]

compared to the original,

qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

I hope this is an ah-ah moment for someone else too. I’d love to know what made you interested in functional programming; or if you know of a more elegant quicksort implementation.

July 3, 2008

NP-Complete is Often Easy

Filed under: Design,Programming,Quotes | , , ,
― Vincent Gable on July 3, 2008

There are a lot of problems that are, in theory, incredibly difficult – but because the difficult cases are very rare and rather contrived, they’re actually very easy to solve. Two examples of this that I find particularly interesting are both NP complete. Type checking in Haskell is one of them: in fact, the general type inference in Haskell is worse that NP complete: the type validation is NP-complete; type inference is NP-hard. But on real code, it’s effectively approximately linear. The other one is a logic problem called 3-SAT. I once attended a great talk by a guy named Daniel Jackson, talking about a formal specification language he’d designed called Alloy. Alloy reduces its specification checking to 3-SAT. Dan explained this saying: “The bad news is, analyzing Alloy specifications is 3-SAT, so it’s exponential and NP-complete. But the good news is that analyzing Alloy specifications is 3-SAT, so we can solve it really quickly

Mark Chu-Carroll (aka MarkCC

Powered by WordPress