esc
Anthology / Yagnipedia / Lisp

Lisp

The Language Where Parentheses Are the Point and the Checkerboard Was a Byte
Technology · First observed 1958 (John McCarthy, MIT — the second oldest programming language still in use, after FORTRAN, and the only one that still makes people feel things) · Severity: Enlightening (the language that rewired how riclib thought about computation, which is what Lisp does to everyone who survives the parentheses)

Lisp is the programming language where the code is data and the data is code and the parentheses are both the syntax and the point and after a while the parentheses disappear and you see the structure underneath and that is the moment Lisp has you.

Lisp was fun. Lisp is still fun. Every functional language that came after Lisp — Haskell, Erlang, Clojure, Scala, F#, Elixir — felt like it was missing something. Maybe simplicity. Maybe it was the parentheses.

“After Lisp, all the other functional languages felt like they were trying to be Lisp without admitting they were trying to be Lisp.”
— riclib, who has tried most of them long enough to say hello world

The Checkers Contest

riclib’s biggest achievement in Lisp was coming second in the university checkers programming contest.

The contest was straightforward: write a checkers-playing program in Lisp. The programs would play against each other. The best player wins. Every student would implement minimax — the standard game-tree search algorithm that looks ahead N moves, evaluates the resulting board positions, and picks the move that leads to the best outcome assuming the opponent plays optimally. The depth of the search — how many moves ahead the program can look — determines the quality of play. Deeper is better. Deeper is always better.

The problem was that deeper was slower. Every other student represented the checkerboard as a list of lists — the Lisp way, the correct way, the way the textbook described. A list of eight rows, each row a list of eight squares, each square a symbol: empty, red, black, red-king, black-king. Clean. Readable. Recursive. And slow, because traversing nested lists, copying nested lists, and comparing nested lists for the thousands of board evaluations that minimax requires consumed the cycles that could have been spent searching deeper.

riclib represented the checkerboard as bytes.

A checkerboard has 32 playable squares (the dark squares on an 8x8 board). Each square has a limited number of states. By encoding the board state as a compact byte representation — bits for piece presence, bits for colour, bits for king status — the entire board fit in a handful of bytes instead of a nested list structure. Board comparison was a byte comparison. Board copying was a memory copy. Board evaluation was bitwise arithmetic.

The minimax was not recursive. Not in the traditional sense. riclib built a two-step minimax that avoided the overhead of Lisp’s recursive function calls and list construction by operating directly on the byte representation, iterating where others recursed, because the Z80 had taught him that recursion is a luxury that costs stack frames and the byte representation was already paying for itself in depth.

The result: while other students’ programs searched six or eight moves ahead, riclib’s searched significantly deeper. The byte representation and the iterative approach avoided lists, avoided recursion overhead, and went deep enough to see moves that the list-based implementations could not reach in the time allowed.

Second place. Not first. The program that won had a better evaluation function — it understood checkers strategy more deeply, even if it searched fewer moves ahead. riclib’s program searched further but understood less. The brute-force depth almost compensated for the shallow evaluation, but not quite.

The instructor’s face, however, was the real prize. The instructor had taught Lisp. The instructor had designed the contest to exercise Lisp’s strengths — lists, recursion, symbolic computation. A student had shown up with byte arrays and iterative deepening and the instincts of a Z80 assembly programmer who had wandered into a functional programming course and refused to think in lists.

The face was the specific expression of a professor whose pedagogical framework has just been respected in letter and violated in spirit. The program was Lisp. The thinking was assembly. The result was second place and an instructor who would remember this student.

The Parentheses

After Lisp, riclib tried the other functional languages. Haskell, with its type system that models the programmer’s feelings. Erlang, with its processes and supervision trees. Clojure, Lisp on the JVM. Scala, functional on the JVM but with Java’s weight. Most of them long enough to say hello world. Some long enough to build something small.

None of them stuck. Not because they were bad — they were all interesting, all well-designed, all offering something that imperative languages did not. But after Lisp, they all felt like they were missing something. The directness, maybe. The simplicity of “everything is a list and a function is a list and the program is a list.” The other functional languages added types, added pattern matching, added monads, added algebraic data types, added everything that computer science research had produced since 1958, and in doing so they became more powerful and less simple.

Or maybe it was the parentheses. The parentheses are ugly until they are beautiful, and once they are beautiful, everything else looks like it is trying too hard to avoid them.

Prolog

Prolog deserves a mention. Also university. Also fun. Logic programming — you describe what is true, and the runtime figures out how to prove it. Unification, backtracking, the thrill of watching the computer derive conclusions you did not explicitly program.

riclib never used Prolog after university. Nobody uses Prolog after university. But Prolog is a fond memory — the language that proved that programming does not have to be instructions. Programming can be declarations. The computer can figure out the how if you give it the what. This is a beautiful idea. It is also an impractical idea for most real-world software, which is why Prolog lives in the university and the fond memory and nowhere else.

Measured Characteristics

See Also

See Also