Dogma and Ritual

Computer Science, mathematics, and magic

There’s a long-standing metaphor in computer science and programming literature that compares programming with magic. Structure and Interpretation of Computer Programs (SICP) famously features a woodcut-style image on the cover, which has earned it the nickname the Wizard Book over the years. The cover of SICP
Figure The famous cover of Structure and Interpretation of Computer Programs (pdf). In the very opening chapter of SICP, we find:

A computational process is indeed much like a sorcerer’s idea of a spirit. It cannot be seen or touched. It is not composed of matter at all. However, it is very real. … The programs we use to conjure processes are like a sorcerer’s spells. They are carefully composed from symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we want our processes to perform.

Harold Abelson, Gerald Jay & Julie Sussman, Structure and Interpretation of Computer Programs

From Fred Brooks The Mythical Man Month, by Fred Brooks, is considered a classic in the literature of practical software engineering in the industry. :

The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds castles in the air, from air, creating by exertion of the imagination. Few media of creation are so flexible, so easy to polish and rework, so readily capable of realizing grand conceptual structures. …
Yet the program construct, unlike the poet’s words, is real in the sense that it moves and works, producing visible outputs separate from the construct itself. It prints results, draws pictures, produces sounds, moves arms. The magic of myth and legend has come true in our time. One types the correct incantation on a keyboard, and a display screen comes to life, showing things that never were nor could be. …
Not all is delight, however … One must perform perfectly. The computer resembles the magic of legend in this respect, too. If one character, one pause, of the incantation is not strictly in proper form, the magic doesn’t work.

Frederick P. Brooks, The Mythical Man Month

Some version of the idea frequently appears in science fiction, such as Vernor Vinge’s True Names or Neal Stephenson’s Snow Crash.

And we can’t forget the classic aphorism from Arthur C. Clarke:

Any sufficiently advanced technology is indistinguishable from magic.

Arthur C. Clarke

It comes up in the way we talk about code and languages as well. We use words like “automagical” to describe how some things just work in some contexts, or we refer to metaprogramming as magic.

The word “occult,” after all, just means hidden. It’s meant to imply some sort of hidden knowledge, which the initiate is eventually given, or at least, is led toward understanding. It comes from the same root from which we get words like occluded.

I think about this in a couple different ways. On the one hand, what is hidden behind our programs is a quite arcane artifact known as object code or machine code. Behind everything, there’s a whole lot of C and pointers, and behind that, there’s some sort of assembly language:

Figure OMG it’s full of *’s A variation of the classic flammarion engraving, showing someone peeking out beyond the sphere of the known universe to see a listing of assembly code behind it all.

There’s good reason to see it that way, because in a very real sense, that’s what is there.

This reminds me of this quote from James Micken James Mickens ’s well-known essay The Night Watch The Night Watch has become a contemporary classic essay on the importance of system programming. It’s also incredibly well-written and funny. :

You might ask, “Why would someone write code in a grotesque language that exposes raw memory addresses? Why not use a modern language with garbage collection and functional programming and free massages after lunch?” Here’s the answer: Pointers are real. They’re what the hardware understands. Somebody has to deal with them. You can’t just place a LISP book on top of an x86 chip and hope that the hardware learns about lambda calculus by osmosis. Denying the existence of pointers is like living in ancient Greece and denying the existence of Krackens and then being confused about why none of your ships ever make it to Morocco, or Ur-Morocco, or whatever Morocco was called back then. Pointers are like Krackens—real, living things that must be dealt with so that polite society can exist.

James Mickens, The Night Watch, Usenix

But speaking of LISP, there’s another way that I think about what’s really behind our code. Yes, of course, it’s the system’s language, the assembly and/or the bytecode that actually exists behind the interpretation or compilation of our programs. But there’s also what the program means. Depending on the programming language we are using, it can be closer or further away, but in some sense, in my mind, there’s a different sort of assembly layer hidden behind our software, and it’s something like lambda calculus.

Figure OMG it’s full of MATH A variation of the classic flammarion engraving, showing someone peeking out beyond the sphere of the known universe to see a listing of lambda calculus behind it all.

The Church-Turing thesis tells us that any computable function can be computed by a Turing Machine. Not only that, but the computational power of a Turing machine is equivalent to the lambda calculus, or to Gödel’s recursive functions. Not usually brought up in this trio, but it turns out that anything we can express in lambda calculus, we could express in just S, K, and I combinators (really, in just S and K, because I can be expressed in terms of S and K as well).

For example, for reasons I can’t really explain, I recently went through the exercise of converting a ternary fork in lambda calculus in to just S, K, and I This is written in Ruby, with implementations of S, K, and I as Ruby lambda expressions. A full gist with tests is over here. The library I’m using for the combinators is one I wrote called smullyan. :

fork3 = S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S)))).(S.(S.(K.(S)).(S
      .(S.(K.(S)).(S.(K.(K)).(K.(S)))).(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(S))))))
      .(S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S)))).(S.(S
      .(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S)))).(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(S))))))
      .(S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S)))).(S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S))))
      .(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(S)))))).(S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S))))
      .(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(K)))))).(S.(S.(K.(S)).(S.(K.(K)).(K.(K))))
      .(S.(K.(K)).(I))))))).(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(I))))))))
      .(S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S)))).(S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S))))
      .(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(S)))))).(S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S))))
      .(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(K)))))).(S.(S.(K.(S)).(S.(K.(K)).(K.(K))))
      .(K.(I))))))).(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(I))))))))).(S.(S.(K.(S))
      .(S.(S.(K.(S)).(S.(K.(K)).(K.(S)))).(S.(S.(K.(S)).(S.(S.(K.(S)).(S.(K.(K)).(K.(S))))
      .(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(S)))))).(S.(S.(K.(S))
      .(S.(S.(K.(S)).(S.(K.(K)).(K.(S)))).(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(K))))))
      .(S.(K.(K)).(K.(I))))))).(S.(S.(K.(S)).(S.(K.(K)).(K.(K)))).(S.(K.(K)).(K.(I)))))

Wow. Let’s not ever do that again.

So in one way I think of it, there are registers and memory addresses, and pointers underlying everything we do. In another way I think about it, there is lambda calculus, logic, and maths underlying everything we do. They are both correct, and I think we can think about our code one way or the other to have different sorts of insights into how and why it works. We can even think about them both at the same time, which is how I think about Elements of Programming by Alexander Stepanov and Paul McJones Elements of Programming by Alexander Stepanov and Paul McJones is about the mathematical foundations of computer programming, algorithms, and generic programming. .

There are, of course, and may have always been, books that purport to be about actual magic. One such was Dogme et Rituel de la Haute Magie by Eliphas Levi. The cover of SICP
Figure The title page of Dogme et Rituel. I’ve always thought that title very interesting, because it occurred to me that the ideas of dogma (belief, teaching) and ritual were analogous to a similar pair of words that show up a lot in educational tradition: theory and practice.

Now, of course, they are not quite the same in meaning. Both dogma and ritual carry a little bit different implications and context than theory and practice. That said, I kind of like the somewhat esoteric and mysterious implications that go along with those words, especially given the common metaphoric thread of magic that often goes along with computer science and programming.

Since for the foreseeable future (I think), what I’m mostly going to be studying and writing about is programming language and type theory, and maybe even occasionally its applications, I decided to change the name of the blog to Dogma and Ritual.

I don’t currently have any sort of mailing list or way to get people to sign up, because I’m a terrible marketer and I have no plan. But if this is the sort of thing that interests you, I hope you might come back. Like Abraham Lincoln is supposed to have said, I hope that:

People who like this sort of thing will find this the sort of thing that they like.

See you around.