www.hackification.com

Back to Basics

To most (all?) programmers, the following code is pretty self-evident:

Multiply( Add( 1, 2 ), Add( 3, 4 ) )

You expect the value 21 to be returned, and you’re familiar with the idea of representing this as a tree of operations:

Fine. Not earth-shattering, but it’s sometimes worth going back to basics to question things we take for granted.

Back in Time

It’s not very popular nowadays, but there’s another way of expressing this:

PUSH 1
PUSH 2
"ADD" (pop, pop, add, push)
PUSH 3
PUSH 4
"ADD" (pop, pop, add, push)
"MULTIPLY" (pop, pop, multiply, push)
"RESULT" (pop)

(Actually I lied when I said that it wasn’t popular. Many virtual machines – JVM and CLR included – are stack machines).

So What?

Although I wouldn’t want to write code like that normally, a stack-based representation has one really nice feature: the structure is linear. Simple functions can be represented as a linear sequence of operations, instead of as a tree. And sometimes, that lets you write really simple code.

As an example, suppose you had to write an evaluator for one of the following: which would take you less time:

MULTIPLY(ADD(1,2),ADD(3,4))

or

PUSH 1, PUSH 2, ADD, PUSH 3, PUSH 4, ADD, MULTIPLY, RESULT

The first requires both lexing and parsing. The second only requires lexing (and in fact, you could do most of it just with string splitting).

In part two I’ll give an example of where a stack-based organisation vastly simplified my code.