Turtles all the way down, please

My other favourite interview question

Someone was once phone-screening me for a job in a start up, and they asked me to name my two strongest languages. At the time, the answer was Java and C++, partly because I had just finished writing Java development tools in C++, and partly because while I loved Scheme and Smalltalk, I knew that anyone using them in day to day production would quickly expose me as a dilettante if I were to answer with my heart instead of my head.

After I said “Java and C++,” the follow-up was interesting. The interviewer asked me: If you could change both languages, name one feature from Java that you would add to C++, and why. And name one feature from C++ you would add to Java, and why.¹

Today I would answer that question differently, of course, but I bring it up because there is a feature of Common Lisp, Arc, and C++ that I miss whenever I use a conventional object-oriented language like Smalltalk or Ruby: lvalues and references. In short, what I miss is the ability to redefine the assignment operator.

Or do I? Let’s have a look at what that means and why I miss it.

Defining a = b

In Ruby, you have a limited ability to define the assignment operator. Specifically, you can define methods that look like fields or instance variables:

class Foo
    def something= value
        # do something
    end
    def []= index, value
        # do something else
    end
end

f = Foo.new
f.something = :else
f.[:where] = :what

Of course, that means something entirely different than writing:

something_else = :fizbuzz

Which binds :fizzbuzz to the local variable something_else. But that’s really it. All uses of “=” in Ruby are one of these cases: binding a variable, calling “[]=,” or calling a named method on an object and passing one parameter.

So?

Well, there’s something I would like to do in Ruby that simply cannot be done. If I have an array I make from a range, say (1..100).to_a, how do I double the odd numbers in that array? Obviously, I can write things like

a = (1..100).to_a
...
a.each_with_index do |i,n|
    a[i] *= 2 if n % 2 == 0
end

But imperative loops are yucky. I could write it a little functionally:

a = a.map { |n| n % 2 == 0 ? n * 2 : n }

But that creates a new array and overwrites my variable. Besides the fact that it seems wasteful, this is absolutely the wrong solution if the original array is shared elsewhere in my code: I am not changing the original array, I am merely binding a local variable to a different array. Try writing a function called “double_the_even_values!(arr)” (that doubles the values of arr), and you’ll see what I mean.

Really, I want to write:

a.select { |n| n % 2 == 0 } *= 2 # or perhaps:
a.select { |n| n % 2 == 0 }.each { |n| n *= 2 }

But I can’t. If a.something gives me a value and a.something = else sets a value, and if a[where] gives me another value and a[where] = what sets another value, then:

When a.select { … } gives me some values, why doesn’t a.select { … } = stuff set some values?

Why not

There’s a reason it doesn’t work that way. Never mind whether Matz was copying some of Smalltalk’s assignment semantics when he designed this piece of Ruby, let’s talk about if statements and cases. Once upon a time, people wrote programs with lots of explicit branches in their code. If this is the case, do this. If that is the case, do that.

The problem with languages like Ruby and Java is that everything is an object and every action is a message, except when it isn’t.

One of the big ideas in OOP was polymorphism. When you program with interfaces, a lot of the logic of what do do for each case goes into your class hierarchy: that’s what method dispatching is all about. This is great, because when you want to do something new, the whole idea is that you create new classes with interfaces just like your existing classes and they just work.

Okay, we can stop smoking the good stuff, nothing just works and OOP is not a silver bullet. But the key idea is that by moving some of our logic into our objects, we can write more generalized code elsewhere, code that does not need to know what an object is doing inside itself.

Let’s look at a different paradigm: Higher-order functional programming. In this paradigm, functions are first-class values: you can write functions that take functions as arguments and/or return functions. Again, there is a de-coupling: if you write a compose function that creates a new function out of two or more other functions, it does not need to know what those other functions do, just how to wire them together. Monads are based on this premise as well, on the premise of writing generalized functions that do not need to know the intimate details of the things they consume and produce.

The problem with languages like Ruby and Java is that everything is an object and every action is a message, except when it isn’t. The things that are objects and messages are remarkably flexible and work well. The things that aren’t objects and messages are like case statements in older programs: places where you cannot extend the language without dealing with thousands of these case statements that are all coupled to each other in unexpected ways.

In Ruby’s case, the rules for what it means when you write expression1 = expression2 are hard-coded into the parser like a case statement. You cannot create a select= method that modifies its receiver. (Actually, you can define the method. Good luck calling it without resorting to send.)

Of course, you can write a method to do what we want:

a.update(
  :where => lambda { |n| n % 2 == 0 },
  :with => lambda { |n| n * 2 }
)

But now we have a serious inelegance: why do three kinds of getting and setting values use one syntax, but the fourth uses a different syntax?

How Common Lisp handles this

Common Lisp has something called a Generalized Variable (also called a generalized reference).² In OO terms, it’s an object that has a setter and a getter method, although you can call them the access and update operations if you prefer.

Common lisp has a macro, setf that performs an update. In short, if you call:

(setf expr1 expr2)

Common Lisp does something analogous to:

expr1.update( expr2.respond_to?(:access) ? expr2.access() : expr2 )

Let’s pretend that Ruby did this. This would be very interesting! For starters, instead of writing an accessor this way:

class Bar
    def something
        @something
    end
    def something=(else)
        @something = else
    end
end

You would define a single method that returns a generalized variable:

class Bar
    def something
        GeneralizedVariable.new.me do |gv|
            def gv.access
                @something
            end
            def gv.update(else)
                @something = else
            end
        end
    end
end

Now whenever you write some_bar.something you would get a generalized variable and Ruby would figure out when you need its value and when you need to assign something to it. Of course, that looks like a lot of boilerplate, but you could rewrite the existing attribute class methods to do this for you. (Actually, this exact code wouldn’t even come close to working because @something would belong to the new object, but squint at it sideways and pretend we can do that.)

You could then write your select method to return either a single generalized variable or a collection of them, depending on how you want your semantics to read. For example, you could choose which of the following ought to work:

a.select { ... } = expr
a.select { ... }.each { |x| x = expr }
a.each { |x| x = expr if ... }

The reason why this is interesting is that the original language designer does not need to worry about whether people want to write select methods that can update their host collections. The language designer merely needs to write things in a sufficiently general way, and people will work out the implications for themselves.

Returning to Ruby (and a lot of other languages), now we see why everything being an object and everything that happens being a method invocation “except when they aren’t” is a problem: Assignment is one of those things that isn’t, and because of that, there are places where our programs aren’t going to be consistent with the language’s philosophy. If assignment was always a method invocation, I suggest that there would be a way to write a select that modifies its receiver.

Of course, there would also be things like this:

2 = 3

Which would now pass blithely though the parser only to raise a NoMethodError at run time because numbers do not implement an update method (At least, not in Ruby. Legend has it that this was legal in early versions of FORTRAN. But those systems were built by Real Programmers who eschewed type safety, quiche, and semiconductor memory).

I think it’s a good thing when languages are highly consistent, in the vein of Scheme, Smalltalk, and Forth. Although you cannot redefine “:=” in Smalltalk for select methods, you can’t redefine it for anything else either, so at least we’re clear that you can never do it, not do it some of the time. Such languages are remarkably consistent, they are quite stable, and although they may be unfamiliar to someone approaching them from a different paradigm, they are highly discoverable.

Turtles, it’s always the damn turtles

Like any program, languages evolve over time as people realize they need new features. A lot of the difference between languages boils down to a basic decision every implementor has to make when deciding how to add a new feature:

Should I add this feature? Or should I make this feature possible?

Adding a feature is like adding a new case to an if statement. You want List Comprehensions? You’ve got it. Syntactic sugar for closures? Done.

Making a new feature possible is the deeper, more challenging option. It involves rewiring the way the language works such that the new feature becomes a special case of a more general language capability. So instead of modifying Ruby to support select=, you add generalized variables, which make select= possible.

Some people will argue with this,³ but I think languages where “It’s turtles all the way down” are better than languages that are exceeding well thought-out and painstakingly chosen collections of features that amount to a heap of if statements and special cases for everything.

Turtles all the way down is a philosophy where you try to define a ridiculously minimal set of orthogonal axioms and build the language by combining those axioms. At the lowest level it feels like pure math: Combinatory Logic can be built out of three, two, or even one combinator if you are careful. Scheme has five special forms. But with the right abstractions and syntactic sugar on top, you can produce a language with an amazingly diverse feeling to it.

But the advantage of having everything in the language built on top of a small set of axioms is that when you want to make a new feature possible, it’s often just a case of burrowing down a level of abstraction and combining the existing things in new ways. For example, it could be as simple as rewriting select to return generalized variables instead of values… if Ruby really treated “=” as a method instead of treating it as a special case that is sometimes a method and sometimes something else and sometimes a third thing.

Of course, you can make new things possible in languages that aren’t turtles all the way down. But your new things never feel like they fit with the things already in the language, just as pairing select and update doesn’t fit naturally alongside something, something=, [], and []= in Ruby. And that means that the thing you build aren’t as discoverable or as readable as they could be.

I started by saying that I like the way you can define lvalues in C++, exactly because you can define methods like select that return generalized variables. But following that thread, I ended up with the conclusion that what I really like is a language with as few special cases as possible, a language which feels like everything is built out of a small set of well-chosen primitives or axioms that I can combine and recombine to create new things that work just like the old things.

A language where it’s turtles all the way down.

---

1. Now this essay is about turtles, so I am probably insane for starting with an anecdote that has every potential of blowing up into a debate about the right way to interview people. So I’ll just say a couple of things about that: First, it’s a screening question. If you ask it and then argue over the phone with the candidate about whether adding the const keyword to Java is a good idea, you are missing the point. The point in a screening question is to weed out people who are flat out lying about their experience, not to decide if they happen to be your intellectual and cultural clone. The moment they demonstrate that they actually have some non-trivial experience with the two languages, you are done.
   
   Second, language nuänce questions have limited value. This is because while there is a correlation between tools knowledge and experience, the argument for causality is tenuous at best. Meaning, people with non-trivial experience usually know a lot more about their tools than people without experience. However, it is possible to learn a lot about a tool without actually having real-world experience. And maybe somebody knows a lot about a tool but doesn’t know the answer to the specific trivial question you want to ask. So… a question like this has some utility as a filter, and perhaps it is useful in a longer interview if you use it as an excuse get the candidate to talk about how their proposed changes would have helped them with their actual projects, which leads them into talking about their experience.
   [back]


2. You can read about them in On LISP: Advanced Techniques for Common LISP. It’s available on line, or you can download the pdf.
   [back]


3. Here’s one such argument: Perl, the first postmodern computer language.
   [back]

  ¶ 2:52 PM