Category: computers

For a school project, I’ve been reading lots of papers on good old PageRank. We’re doing something similar to this venerable algorithm in a streaming context. For a basis of comparison, I needed a simple, reliable implementation of the classic algorithm, and Matlab (octave) happens to excel at this kind of thing. So here’s my version. Initialized appropriately, this gives the same results as the diagram on the appropriate Wikipedia page. You probably wouldn’t want to run this on the web graph though: it wants to be run in a cluster at that scale.

function[R] = pagerank(A, R, d, epsilon)
N=size(A)(1);
E=ones(N);
R_last = R;
delta=epsilon;
while (delta >= epsilon)
    R = (d * A + (1-d)/N * E) * R_last;
    dist=R-R_last;
    delta = sqrt(dot(dist,dist));
    R_last = R;
end

R is the initial ranking vector. Typically this is just 1/N for each entry, but it can be some other probability distribution to arrive at personalized rankings. A is the column-oriented adjacency matrix divided by out-degree (with a plain adjacency matrix T, K=diag(sum(T)); A=K^-1 * T). Nodes with out-degree zero should be marked adjacent to everyone. d is the dampening factor, and epsilon is the convergence threshold.

I’m pretty sure my Matlab coding skills are quite lackluster, but it works.

In addition to the idea that the least interesting and most trivial patches get the most scrutiny, I think the bike-shedding effect is doubled if someone claims their implementation is extra clever. Then Linus unleashes his Thunderbolt of Clarity and sanity is restored.

To exploit this phenomenon, one seeking reviews should claim that one’s code is better than any Knuth himself could have dreamed up, uses the minimal number of clock cycles on any present or future architecture, and solves Clique in P. Then nerds will come at you like zombies.

So I’ve now had experience fixing other peoples’ software in several different domains. Here’s how it plays out:

Open-source project:

Thanks! Applied.

Proprietary application:

Thank you for your submission. We have taken your request under consideration, and assigned it ticket #17231. In our review for the next release, scheduled to be released in Q4 next year, we will consider each resolved ticket for possible inclusion in our product.

Government project:
[paraphrasing an angry letter to division heads]

Please find attached a 9-page document describing why we cannot include any changes in our software, even 80-line changes that fix crashes such as the ones your agency has experienced. We suggest your agency maintain your own copy of the software with the change applied.

P.S. We doubt seriously it’s really our problem even though you gave us an explanation and a reasonable code fix. Please waste some more time trying to prove it to us.

I suppose I’m old enough now, and the rate of change in computing is fast enough, that I can regale young software developers with I-remember-when stories. You know, the ones that start off like “all of my punchcards were rubber-banded together, but I had neglected to number them…” I’ll spare you the tale of how we used to screen-scrape the mainframes at LargeAirline.com for today; instead you get to read my ramblings on languages-older-than-Go.

Today’s topic is inspired by my reading on LWN about the fact that Emacs is still around, which led me to David Wheeler’s argument that parentheses are why no one uses Lisp and that we can do better. Perhaps so, but I found his plugging of SKILL interesting, since once, long ago, when I was but a fresh young hacker, I spent a rather significant bit of time writing software in this language.

Since you have likely never heard of it, SKILL is a Lisp implementation that is (or was?) embedded in the Cadence suite of Electronic Design Automation products. As I recall, the biggest warts were:

• the fact that you could use C-like prefixing — f(x y) was equivalent to (f x y) — but other constructs, like using parentheses for grouping, behaved as in Lisp (i.e. errored).
• the runtime library used C-like functions, such as printf, fread, etc
• the developer’s manual encouraged using imperative style programming like loops; indeed using recursion instead would usually lead to stack overflows

I typically wrote in the Lisp style and just ignored the C-like features as much as possible. The experience soured me on functional languages forever, which isn’t really fair, because SKILL was particularly bad.

But I’ve often wondered why it was so horrible, and how it came to be that Cadence, a large successful company, selected it as its primary extension language. Of course, almost all EDA software is horrible so the bar is pretty low, but I wondered if this was a case of Cadence not realizing how bad it was, or if it was just historical baggage. Or did a bored programmer just decide one day, “hey, let’s write our own crappy Lisp!” (cf. much of Android).

Luckily, there’s a paper on it to shed some light: “SKILL: A Lisp-based extension language” by E. Petrus, 1993. I snagged a version from behind the ACM paywall, so I won’t post it, but I’ll quote a few interesting bits here.

SKILL was originally conceived as a base language for developing simulation and test description languages… Lisp was chosen as a base language because it lent itself well to an interpreter based implementation and Lisp is a natural choice for code generation and as a meta language. The first implementation was an interpreter based on the Franz Lisp developed at Cadence Design Systems in the mid-1980s.

Fair enough. Mostly historical baggage, partly not-invented-here.

The popular syntax for SKILL is a C-like alternative to Lisp. When SKILL was first introduced, the connection with Lisp was not promoted in electronic engineering circles.

Too bad. Maybe if the same engineers had compared it to an allegedly decent Lisp, they might have demanded better.

Because of the large installed SKILL base, it has been difficult to move SKILL [in the direction of Common Lisp].

Oops.

For the most part, SKILL developers come from a EE background and lack general familiarity with functional languages. As a result, company wide code inspections revealed the need for a high level code analysis tool.

Even Cadence internal staff couldn’t use SKILL.

The paper goes on to describe why extension languages are useful as a component of software-reuse. While I won’t disagree, I find the characterizations of EDA software more an indictment on the state of software development in the industry circa mid-90s. The products I used from Mentor Graphics, Cadence, and so on were just horrendous. Each application was typically a 40 meg, crashy, statically linked executable, in which a lot of functionality was shared between a few other executables that mostly did the same thing but had subtly different missing features (probably in the name of their byzantine licensing strategies).

• ECAD software is too large and diverse to be contained in a single executable
• Need “fire-walls” between products. Separating major products into separate executables reduces the chance of one set of code from corrupting data in another.
• Change control is easier when the software is built separately.
• Independent release of products. Products linked together in the same executable must be shipped together. In separate executables, products can be shipped whenever necessary.

(Shared libraries anyone?)

I think I wouldn’t mind SKILL if it had been a decent Lisp, but unfortunately Cadence got stuck with maintaining their own one-off fork and the software ecosystem that grew up around it. At the EDA firm at which I worked, we were lucky to be a late-comer, which allowed us to use a reasonable extension language: perl. I haven’t kept up with the industry, but I hope others have followed suit.