An Interview with John Macdonald, Co-author of Mastering Algorithms with Perl

John Macdonald, co-author of Mastering Algorithms with Perl, is a long-time user of Perl for Unix system administration tools. His background includes work on compilers, kernel internals, and device drivers. Betsy Waliszewski was able to pry him away from his work to answer a few questions about this best-selling book.

Waliszewski:

Why a book on algorithms with Perl?

Macdonald:

Algorithms form a significant part of most programming tasks. This field of study records how a variety of common tasks can be carried out: which ways work well and which work poorly, and which circumstances force you to use the poorer methods. Some problems have no good solution, and knowing when you have to use an approximation can be essential. In Garey and Johnson's book: "Computers and Intractability: A Guide to the Theory of NP-Completeness", there is an interesting pair of cartoons. If I recall correctly, the first has a man going dejectedly to his boss "I can't solve this problem. I guess I'm just stupid." In the second, he is more more confident, pointing to line after line of people outside the door, "I can't solve this problem and neither can any of these famous experts."

In the abstract, the choice of programming environment doesn't matter to studying algorithms. The change in performance from one to the next will be a constant factor. Amongst peer environments that factor will usually be small, but even if it is a factor of 1,000 it is generally not important. Using the wrong algorithm can change run times from seconds to centuries--from trivial to impossible, regardless of the environment.

In practice, of course, it does matter. While you're reading about algorithms, you want to understand the code; if it is written in a familiar language your task is easier. And once you've progressed from studying, and have determined the right algorithm to use, there is still the matter of using it. There is a vast difference between copying or downloading code that is written in the language you need and translating pseudo-code into your language.

So, for a programmer who uses Perl, an algorithms book based on Perl is very useful.

Waliszewski:

How does this book differ from other algorithm books?

Macdonald:

The focus on Perl is unique to this book. Our orientation is strongly on the practical side. We don't avoid teaching concepts, but we focus more on the engineering side--using the algorithm and choosing amongst the alternatives--than on the theory of how the algorithm works. That practical orientation means that there are many places where we point to code on the net instead of (or in addition to) providing explicit code of our own.

Waliszewski:

What kind of algorithms does this book cover?

Macdonald:

It fits the typical set you'd find in most algorithms books: data structures, sorting, searching, sets, matrices, graphs, strings, geometry, number theoretic, cryptography, probability, statistics, and numerical analysis.

It's hard to do adequate justice to all of them; the book ended up with about 50% more pages than the original guesstimate.

Waliszewski:

Algorithms typically imply efficiency; does this work well with Perl?

Macdonald:

Sure. Tom Christiansen's rule of thumb is that a well-written Perl program will be within a factor of 'e' (2.71828...) of the equivalent program written in C (give or take an order of magnitude). That level of speed difference corresponds to using an 18 month old computer instead of a new one. There are very few programs that are so close to the border of feasibility that such a difference matters.

Things that can have an effect are:

• Having access to libraries of canned algorithms so that the programmer doesn't have to start from scratch.

• The CPAN has provided a major resource already and we've added more while writing this book.

• There are lots of libraries of C code, too. For specialized needs, you write in the language that can best use the available libraries. (That need not be the language that the library is written in: lots of CPAN modules provide a Perl interface to library packages written in C or other languages. It may be more convenient to use Perl and access a library through an interface module than to use C and access it directly. That can give you the performance of the C library for the critical part, while retaining the convenience of Perl for the user interface and reporting parts.)

• Being able to restructure your code as you realize that it would be served by using a particular algorithm.

• Because Perl operates at a higher level than C, it is sometimes easier to understand your code at a higher level, which might mean being able to recognize that a particular algorithm is appropriate.

• It may be easier to totally restructure the program than to use a different algorithm. This is because the Perl code is generally much shorter.

Waliszewski:

Are there things you can do with algorithms in Perl that you can't with algorithms in other programming lanuages?

Macdonald:

Some algorithms are easier to implement in Perl. For example, Perl provides garbage collection and dynamically sized arrays. A Perl array and standard Perl operators can be used for a queue, or a stack, or a deque. In other languages, you need to write code to provide those structures and the code has to go to a lot of effort if it will deal with changes in the size of the structure correctly.

Waliszewski:

Is Perl gaining greater usage in the computer science arena?

Macdonald:

I would expect so. Many of today's computer science students began by writing Perl for the CGI in their private Web pages.

Waliszewski:

When is it appropriate to create a module to put in CPAN (a popular collection of canned Perl code), and when should a programmer code something himself or herself?

Macdonald:

First, check to see whether something appropriate is already there. Don't write code when you can steal it.

Coding directly or using a separate module is not an either-or proposition. When the code for an operation is so simple that you can type it in the middle of an expression without error, you'll tend to just write it as you go. If the way to write the code is highly dependent upon the context, you'll also tend to write it as you go. If the algorithm is harder to get right, putting it in a canned module is best.

Knuth points out that many decades passed after the binary search algorithm was described and when the first error-free implementation was published.

Waliszewski:

What led you to be such a Perl advocate?

Macdonald:

I've been using Perl since 1988. That code has been augmented significantly, but the basis is still running essentially unchanged. When I'm writing in some other language (C, sed, awk), I constantly find that I'm missing features that are standard with Perl.

Waliszewski:

What do you think is the future for Perl?

Macdonald:

World domination [laughs].

Perl will continue to evolve and grow, because it has a group of extremely talented people making that happen.

Copyright © 2007 O'Reilly Media, Inc.