Vincent Gable’s Blog

June 17, 2010

The Arrow Points Up

And so continues one of the biggest constants in software development: the unerring sense among developers that the level of abstraction they’re current working at is exactly the right one for the task at hand. Anything lower-level is seen as barbaric, and anything higher-level is a bloated, slow waste of resources. This remains true even as the overall level of abstraction across the industry marches ever higher.

First the C guys can’t imagine writing in assembly anymore, but C++’s vtable dispatch is still just too slow to consider. Then the C++ guys look back with chagrin at the bad-old-days of rolling their own half-assed object systems in C, but Java is dismissed as a ridiculous pig. Still later, the Java guys sneer at pointers and manual memory management, but JavaScript is ridiculed as a toy “scripting” language for validating web forms. And on and on.

And in the short term, in the moment, they’re often right. But this arrow points only one way, and that’s in the direction of ever-higher abstraction. To judge how much time remains before the next leap forwards, look at the leading edge of the industry.

John Siracusa (emphasis mine)

Here’s my two cents on the future of abstraction: systems are clearly getting wider (paralell), not faster; technologies like Grand Central Dispatch help us deal with concurrency today, but longer term, I think a functional programming abstraction is the answer.

December 10, 2009

Being a Lisp is a Handicap

Filed under: Accessibility,Programming | , , , ,
― Vincent Gable on December 10, 2009

Being a Lisp Is a Handicap

There are a large number of people who find Lisp code hard to read. I’m one of them. I’m fully prepared to admit that this is a shortcoming in myself not Lisp, but I think the shortcoming is widely shared.

Perhaps if I’d learned Lisp before plunging into the procedural mainstream, I wouldn’t have this problem — but it’s not clear the results of MIT’s decades-long experiment in doing so would support that hypothesis.

I think it’s worse than that. In school, we all learn
3 + 4 = 7 and then
sin(?/2) = 1
and then many of us speak languages with infix verbs. So Lisp is fighting uphill.

It also may be the case that there’s something about some human minds that has trouble with thinking about data list-at-a-time rather than item-at-a-time

I think I really totally understand the value of being homoiconic, and the awesome power of macros, and the notion of the reader. I want to like Lisp; but I think readability is an insanely important characteristic in programming systems.

Practically speaking, this means that it’d be hard for me to go out there on Sun’s (or Oracle’s) behalf and tell them that the way to take the best advantage of modern many-core hardware is to start with S-Expressions before breakfast.

Tim Bray (emphasis mine)

I’m afraid he’s on to something. We have an amazing ability to parse language. But people aren’t terribly good at building the kinds of stacks needed to parse LISP with their short term memory.

This is the cheese that the rat that the cat that the dog that the neighbor owned bothered chased ate.

Say what?!

(This is the cheese (that the rat (that the cat (that the dog (that the neighbor owned) bothered) chased) ate)).

See the LISP connection?

All functional languages are fighting an uphill battle to be understood. The world we evolved in is stateful (modal) and imperative. We navigate it in a me-at-a-time way. Unfortunately, LISP’s prefix syntax is another, unnecessary, barrier.

The bottom line is that every word of code spends more time being read than written — so writing in a syntax that most people have a hard time reading is one of the worst programming choices imaginable. I believe functional programming languages are well worth learning; but I don’t believe it’s worth suffering a poor syntax.

October 20, 2009

JavaScript Nailed ||

One thing about JavaScript I really like is that its ||, the Logical Or operator, is really a more general ‘Eval Until True‘ operation. (If you have a better name for this operation, please leave a comment!) It’s the same kind of or operator used in Lisp. And I believe it’s the best choice for a language to use.

In C/C++, a || b is equivalent to,

  if a evaluates to a non-zero value:
    return true;
  if b evaluates to a non-zero value:
    return true;
  otherwise:
    return false;

Note that if a can be converted to true, then b is not evaluated. Importantly, in C/C++ || always returns a bool.

But the JavaScript || returns the value of the first variable that can be converted to true, or the last variable if both variables can’t be interpreted as true,

  if a evaluates to a non-zero value:
    return a;
  otherwise:
    return b;

Concise

JavaScript’s || is some sweet syntactic sugar.

We can write,

return playerName || "Player 1";

instead of,

return playerName ? playerName : "Player 1";

And simplify assert-like code in a perl-esq way,

x || throw "x was unexpectedly null!";

It’s interesting that a more concise definition of || allows more concise code, even though intuitively we’d expect a more complex || to “do more work for us”.

General

Defining || to return values, not true/false, is much more useful for functional programming.

The short-circuit-evaluation is powerful enough to replace if-statements. For example, the familiar factorial function,

function factorial(n){
	if(n == 0) return 1;
	return n*factorial(n-1);
}

can be written in JavaScript using && and || expressions,

function factorial2(n){ return n * (n && factorial2(n-1)) || 1;}

Yes, I know this isn’t the clearest way to write a factorial, and it would still be an expression if it used ?:, but hopefully this gives you a sense of what short-circuiting operations can do.

Unlike ?:, the two-argument || intuitively generalizes to n arguments, equivalent to a1 || a2 || ... || an. This makes it even more useful for dealing with abstractions.

Logical operators that return values, instead of simply booleans, are more expressive and powerful, although at first they may not seem useful — especially coming from a language without them.

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.

May 14, 2009

Emergent Libraries

I have latched onto an idea, but don’t have the resources to follow up on it: could a static-analysis tool identify repeated patterns of code, across many code bases, that should be extracted out as subroutines and higher-level functions? How universal would these “emergent libraries” be?

My inspiration here is Section 4.1 Identifying Common Functions, in the excellent paper Some Thoughts on Security After Ten Years of qmail 1.0 (PDF), by Daniel J. Bernstein,

Most programmers would never bother to create such a small function. But several words of code are saved whenever one occurrence of the dup2()/close() pattern is replaced with one call to fd_move(); replacing a dozen occurrences saves considerably more code than were spent writing the function itself. (The function is also a natural target for tests.) The same benefit scales to larger systems and to a huge variety of functions; fd_move() is just one example. In many cases an automated scan for common operation sequences can suggest helpful new functions, but even without automation I frequently find myself thinking “Haven’t I seen this before?” and extracting a new function out of existing code.

What’s particularly fascinating to me are the new operations we might find.

Before I was exposed to the Haskell prelude I hadn’t known about the fundamentally useful foldl and foldr operations. I had written dozens of programs that used accumulation, but it’s generalization hadn’t occurred to me — and probably never would have. Static analysis can help uncover generalizations that we might have missed, or didn’t think were important, but turn out in practice to be widely used operations.

February 1, 2009

“I Deployed More Scheme Runtimes Than Anybody Else on the Planet”

Filed under: Programming,Quotes | , , ,
― Vincent Gable on February 1, 2009

From an Interview with an Adware Author,

Sherri Davidoff
You wrote adware. You bastard.

Matt Knox: [sheepishly] Yes, I did. I got to write half of it in Scheme, which probably means that I deployed more Scheme runtimes than anybody else on the planet.

So are most scheme programs in the wild used for evil? That’s a depressing thought.

Powered by WordPress