Sugar-Free Loops

Sugar-free loops: not a breakfast cereal.

I've recently been playing with a minimalist language that eschews pretty much all syntactic sugar. It has no classes (or typeclasses), no mutable state, no jumps or labels, no modules or packages. It has no libraries—and if it did, they'd be useless, because it has no identifiers with which to name the contents of the libraries.

The language is basically the lambda calculus, plus built-in integers, a few integer functions, and a conditional If. Variables are represented as zero-based De Bruijn indices, using the notation V(i) for the variable in the ith enclosing scope. V is actually a special case of the Var operator, whose argument can be an arbitrary expression rather than just an integer constant—useful if you want to invent arrays.

Calling this thing a “language” is probably an abuse of the term; it's just a data structure with an interpreter.

Although I wouldn't want to program such a thing on a regular basis, I did want to be able to process sequences of varying lengths with it. Given the pure functional nature of the language, this requires recursion. And given the lack of identifiers, the language doesn't do the recursion for me; I need to use an explicit fixpoint combinator. The call-by-value Y combinator in this language looks like:

  fix =
    Lam(
      Lam(V(1)(Lam(V(1)(V(1))(V(0)))))(
        Lam(V(1)(Lam(V(1)(V(1))(V(0)))))))

So I know I'll apply this to my looping function, but what does the looping function look like? Well, you can generally view a loop that computes a value as a fold. But unlike folds in high-level languages, there aren't have any prepackaged sequence operations to use in the fold, so I have to take those operations as parameters. Specifically, my fold (as passed to the Y comnbinator to create a usable recursive fold) will look like:

  λf.λmore?.λhead.λtail.λstep.λaccum.λnext.
    if not more? next then
      accum
    else
      f more? head tail step (step accum (head next)) (tail next)

where more? applied to a sequence tells whether there are any more elements (the sequence is not empty), head provides the current element of the sequence and tail the rest, step performs one step of the fold operation, accum is the value accumulated by the fold, and next is the sequence from which to get the next element. Stripped of sugar, this becomes:

  unfixedFold =
    Lam(                              // f (fold itself): V(6)
      Lam(                            // more: V(5)
        Lam(                          // head: V(4)
          Lam(                        // tail: V(3)
            Lam(                      // step: V(2)
              Lam(                    // accum: V(1)
                Lam(                  // next: V(0)
                  If(
                    Not(V(5)(V(0))),  // not more?
                    V(1),             // no more, return accum
                    V(6)(             // else apply f to
                      V(5))(V(4))(V(3))(V(2))(
                                      // same more?, head, tail, step,
                      V(2)(V(1))(V(4)(V(0))))(
                                      // step(accum,head(next)),
                      V(3)(V(0)))))))))))
                                      // and tail(next)

The only form of input in this language is to bind the input to variables, as if the program were called from within a series of nested functions applied to the inputs. A program to iterate through such inputs and compute the maximum value looks like:

  fix(unfixedFold)(
    Lam(Lt(V(0),Minus(Depth,I(1)))))(   // more?: variable index less
                                        // than lexical depth
    Lam(Var(Plus(V(0),I(1)))))(         // head: index into inputs (add
                                        // 1 to index to account for
                                        // head function itself)
    Lam(Plus(V(0),I(1))))(              // tail: increment index
    Lam(If(Gt(V(0),V(1)),V(0),V(1))))(  // step: max of arguments
    V(0))(                              // accum starts as zeroth input
    I(1))                               // index after zeroth input

Four out of five dentists do not recommend sugar-free languages, at least for their patients without patience.

No Comment

Of all the features ever introduced into programming languages, surely the ability to insert natural-language comments is the worst thought out.

Think about it: have you ever seen a comment of more than one line that wasn't out-of-date by the time you read it? Or, if the comment was more-or-less accurate, one that didn't at least contain distracting misspellings and mispunctuations?

An ideal programming language would let you write all comments in the language itself, so that the compiler could verify that comments are properly structured and consistent with the code they describe.

Now I realize this post is appearing just a few days after April 1st, but I'm not entirely joking. Static type checking is, in effect, a system of compiler-checked comments. Type checking, of course, has a role in avoiding errors—and I do find that I do make type errors that the compiler flags, and I appreciate the ability to correct those errors before runtime. But far more often than the compiler finds a type error in my code, I read the type annotations I've made, because from day to day I tend to forget the types I'm working with at any given point in the code. That is, type annotations—like pretty much everything else in programming language source code—are best thought of as more for human consumption than for the compiler.

One reason I enjoy working with Scala more than Haskell is precisely what many people consider to be a flaw in Scala, namely that Scala can't do type inference in many places where Haskell can. Scala code is consequently littered with type annotations in places where Haskell would omit them—but that means I don't have to look very far to be reminded what anything is. As with natural language, redundancy may take up more space or time in transmission, but if not overdone it's a great aid to comprehension.

I've written some Python, and I enjoy the speed and concision with which you can whip up some code when you don't have to bother with type annotations. But it's not a language I would use for code I planned to work on for a long time, or to share with other people; I don't think I could keep the types clear in my head long enough. Unless, of course, I wrote some natural-language comments to remind me. But then I'd really want the compiler to make sure those comments didn't get out of date.

I'm still looking forward to the compiler that will complain when I write a comment that says “here is an implementation of quicksort” when what I've actually coded is bubblesort. But perhaps, a few years from now, someone will announce such a thing. On April 1st.

Unknown Works of Charles Dickens

It was a little over a year ago that, having just finished up Andrew Ng's machine learning course on Coursera, I was inspired to build a little neural network of my own. I designed it to predict the next character of a sequence of input characters, given the previous 20 characters. Then I set it to work training itself on the text of Charles Dickens's A Christmas Carol, A Tale of Two Cities, and David Copperfield.

I was working on this while on vacation in Morocco. It took the little Atom-powered netbook I had brought with me about 36 hours to finish the training. When it was done, I set it to work generating more characters based on its own output—that is, taking the previous 20 characters of its own output, it would generate a next character, and then another given the trailing 19 characters of the original sequence followed by the newly generated character, and so on.

The result was a series of literary gems like this paragraph:

dodod aS mading a9 bRinoiceataid me cor s8 and tie howe, and the made the for, and said of tartat on dadi beat eo fore add, bow berinod, and was mn of thou in what he Sas, in hadd he baid was withing, mavedaisRoe d a. Ce isable gore and spo~ed ,o arind was Paid sai?,o a dase of be you in for had waice a+m, and I in the keed=ratld Whe, and sbate mawer Ag is, and sNow of the so it was it a fiid and xawis.d&o, with a dowther(ave qpine the wabe do ha d sasbed was of the worbere beAd, comce it hisaid the was bead was it of Bere, I and berq, Winder deadored w!thin the fireaceo fored w; I waacaing waid wor to in the be bor, ?

Has my netbook unearthed what Dickens really meant to say? And should Tolstoy be worried?

I Can See Right through You

I've been doing some reading and thinking about contracts and hybrid type checking, and there's something I haven't seen mentioned yet.

Those of us who use languages with decent support for abstraction are used to thinking of operations that can have different implementations—depending, for example, on the particular class associated with an object.

But there are some operations for which multiple implementations don't really make sense. For example, consider an interface for integers that supports even and odd operations. In a language with nominal typing, you can't get very specific about what these methods return:

  trait Integer {
    def isOdd: Boolean
    def isEven: Boolean
  }

But in a language where your contracts can be more specific, you could say something like:

  trait Integer {
    def isOdd: { _ % 2 == 1 }
    def isEven: { _ % 2 == 0 }
  }

That is, the contract of odd specifies that it returns whether its argument is odd, and similarly for even.

Assuming that you don't mind putting code in your interface, you can make sure that no override of these methods violates the contract by insisting on the implementation:

  trait Integer {
    final def isOdd: { _ % 2 == 1 } = this % 2 == 1
    final def isEven: { _ % 2 == 0 } = this % 2 == 0
  }

Holy redundancy, Batman! The type is the implementation! In fact, if these are pure functions, the types specify the only reasonable implementation of these operations (modulo optimizations, such as using a shift instead of a division operation).

If, like me, you tend to assume that everything you encounter is just a special case of some more general phenomenon, you might want to give this sort of function a name. I'm inclined to use the word transparent, because the function's type acts like a window that lets you see the whole inside of the function—although I'm not sure that term wouldn't lead to confusion with referential transparency, which is something else.

But if this phenomenon is indeed sufficiently common to receive a name, you might want to support it directly in a programming language, with something like:

  trait Integer {
    def isOdd transparently this % 2 == 1
    def isEven transparently this % 2 == 0
  }

On a related note, if a contract is a function, then that function might have a sort of transparency—that is, a reflection facility that let you inspect a contract might not just let you test whether the contract holds of a particular value, but also let you look directly at the code that specifies the contract. An alternative is to hide the contents of the contract, and reveal only whether one contract implies another; but since that is impossible to deduce in general, the reflection system would probably serve you better by giving you the raw code and letting you make of it what you will.

The Y Conspiracy

Some phenomena are so outlandish that to explain them seems to require a conspiracy by the powerful.

For example, consider the modern computer chip. Is it really believable that a tiny piece of slightly adulterated silicon can, when an electric current is passed through it, compute millions of digits of pi? Well, maybe you can swallow the pi, but doesn't it burst the bounds of credulity to accept that it can also show you videos of cute kittens dancing?

Surely there's a more plausible explanation for the technology we all enjoy, preferably an explanation involving wickedness and shadowy forces. Is it possible that the computer companies of the world have made a deal with Satan, and imprisoned damned souls inside their machines, forcing them to do billions of calculations per second under threat of intensified torment?

Alas, my theory doesn't stand up to examination. There are conspiracies in the world, but they don't explain all hard-to-believe phenomena. For a conspiracy theory to be plausible, the conspiracy has to have a small enough number of participants that its details could reasonably remain secret—or at any rate, that has to be more reasonable than the alternatives. Given how much difficulty most people I know have in keeping a secret, my minions-of-Satan hypothesis falls apart if more than about three people are involved in the computer industry. Lacking a better explanation, then, I'll just have to accept the information-processing abilities of dirty sand.

Even more mind-bending are the properties of fixpoint combinators. No matter how many times I step through a demonstration of the Y combinator turning a nonsensical up-by-its-own-bootstraps lambda expression into a tidy well-behaved function, I can't quite convince myself that it could ever really work.

The problem with disbelief in stuff that can be demonstrated mathematically is that you have no freedom to invoke a conspiracy. Not even the Trilateral Commission with a fleet of black helicopters could fool us into putting our faith in the Y combinator if it didn't actually perform as advertised.

I'll just have fall back on the idea that The Lambda Calculus Is Magic.

Landauer vs. the Fan

Darn that !@#$% laptop fan. Why is it running again?

Maybe because I took Stanford's free online courses in artificial intelligence and machine learning last quarter, and I've been running experiments with neural networks on and off since then.

Neural networks are fun and flexible ways of coming up with a function when you really have no clue how the outputs relate to the inputs, but it sure takes a lot of time and electricity to train them. I'm basically turning coal (or whatever the local power plant burns) into functions.

I suppose the fact that we recently put photovoltaic panels on our roof should salve my conscience a little, but it still seems as if it's going to take an awful lot of expensive electrons to train enough AIs to provide us all with robot maids and butlers. Can't we do any better?

A recent Scientific American article suggests that Fujitsu's K Computer has around 4 times as much computational power as a human brain, but uses about half a million times as much energy. There's plenty of room to argue that the K computer and the brain do types of processing that aren't comparable, and even if you ignored that, I imagine there's plenty of fudging in the figure the article cites for the brain. Still, we can probably say that the brain is several decimal orders of magnitude more efficient than a modern electronic computer.

What about the brain itself? Is it actually as efficient as possible, or does physics permit computational systems that use even less energy? Well, it was only recently that I discovered the Landauer limit, which describes the minimum energy required to change one bit of information. The Wikipedia article says that at room temperature, the Landauer limit requires at least 2.85 picowatts to record a billion bits of information per second. I'm not sure what that translates to in flops—maybe a single floating point operation requires recording a thousand bits of intermediate information? If so, a billion bits per second is a megaflop, or less than a billionth of a human brain, per the Scientific American article. If I've done the math right, that leaves the brain only a few orders of magnitude less efficient the room-temperature limit (but fortunately, Landauer says colder computers would do better).

At any rate, physics does leave some room for cooler computers. Maybe I won't have to listen to fan noise every time I hang out with Rosey and Mac after all.

Yes, I Have No Class

OK, I think I do kind of get what's going on with Beta. Yes, function activations are objects, and function bodies are object initializers. (I can find references to this being a concept that Beta inherited from Simula, but what I haven't found is any actual Simula documentation that says Simula does things this way. As far as I can see, Simula has rather conventional-looking, distinct syntaxes for declaring classes and procedures. But Beta has just one syntax for both.)

(There's some other stuff going on in Beta, like the ability to keep a function activation around and rerun it in the same activation frame. This is excusable as an optimization of tail recursion, but letting people do it by hand at arbitrary points in the program is a perfect example of the principle that just because you can think of something, you are not obliged to go off and implement it.)

Not Your Grandpappy's this

To illustrate the activation-as-object idea (without resorting to Beta syntax, which is baffling to the uninitiated), here's a bowdlerized version that I hope won't be too offensive to modern functional sensibilities. Consider a representation of binary expressions:

    def Binary (
        public left: Expr,
        public op: BinOp,
        public right: Expr) =
      this

using the usual ill-defined mongrel syntax. In this case, this is understood not to mean what it would in Java or Scala (the object that owns the function where this appears), but rather the current invocation (or call or activation) of the Binary function itself. So Binary is the name of a class. It's also the name of a function that constructs an instance of the class. We can tell Binary is a class because it returns this. (We could also make the return type of Binary explicit, as in:

    def Binary (
        public left: Expr,
        public op: BinOp,
        public right: Expr): Binary =
      this

but my imaginary compiler for this non-language is somehow smart enough to infer this.)

A class with no features is not very useful. Binary has three features, all functions (because the universe contains nothing except functions and activations of functions. Of course, the functions themselves must be activations of the function constructor function. Does my head hurt enough yet?). I've marked these functions (left, op, and right) with public, not the more Scalaish val, to emphasize that I'm specifying only the visibility of these features, not that they are variables (even constant variables) in the usual sense—because there are no variables in the usual sense, only functions that always return the same value. Things that look like variable bindings are just functions defined always to return the argument (a function activation) passed to them.

A fatter example:

    def Binary (
        public left: Expr,
        public op: BinOp,
        public right: Expr) = {
      def eval: Int =
        left.eval mumble mumble right.eval
      def show: String =
        "(" + left.show + " " + op.show + " " + right.show + ")"
      this
    }

where I suppose the defs should actually be publics for consistency, but this train of thought is still way too half-baked to merit consistency (or unmixed metaphors). Since eval doesn't return an eval, and show doesn't return a show, we know these aren't constructors; they're just plain old functions.

Calling a plain old function, like calling a constructor function, allocates an activation record for the function (at least conceptually). But if the activation never escapes, it becomes garbage as soon as the function returns. An execution environment with a lick of sense would put such a thing on a stack instead of a heap, but let's loftily dismiss that as a mere implementation detail.

Found: One Grail (Slightly Holy)

Anyway, yes, activation-as-object does offer a solution to the puzzle of constructors.

To recap, that puzzle is: what is an object before its constructor is called? Bytecode fans will recall that the JVM constructs an object in two phases, first allocating it with the new instruction, and then invokespecialing its class's <init> method. The JVM verifier ensures that you can't get a hold of the object in between new and <init>, because it's not valid then: it's not a proper instance of its class yet, but (because new had to refer to the class to allocate it), it's clearly not an instance of anything else. It's just a nonthing from which you must avert your eyes.

But function invocation, at least as far as we let ourselves know, is atomic. Once the arguments are prepared, boom!, you're executing the function, with its activation record all nicely laid out for you, and with not so much as an eyeblink in between (assembly language programmers may dissent, but our fingers are firmly in our ears and we can't hear a word they're saying). That means that when objects are activations, there is no object to wonder about before its constructor is called: the object is the call to the constructor.

Further Adventures of a Vague Idea

In this non-language that I'm not describing, every identifier that appears in an expression (as opposed to a type declaration) is the name of a function. If that identifier is followed by an open paren or nothing, it's a function invocation. So left.eval above invokes left, which returns the first argument passed to Binary, and then invokes the eval function that is a feature of left (and presumably of every Expr). An identifier followed by an underscore is a reference to the function itself, as in Scala.

Since classes are functions, Expr _ is properly the name of the type of instances of (activations of, calls to) Expr. But after a colon, the trailing underscore is implied, so we can say left: Expr instead of left: Expr _. You might need the underscore in other contexts, like if (foo.class == Expr _) ....

Another random observation is that in Scala, val and var have different meanings in classes and functions. Declarations in a class can refer to each other (so that functions can recurse, and so on); but variable definitions in a function can refer only to local identifiers declared earlier in the function, not later. Since Non-Language functions are both classes and functions, you'll need some kind of syntax to distinguish between letrec-like declarations and sequential declarations, unless you can persuade yourself that you can do without the latter (can you? I never thought about this).

Hey, Look at the Ducks!

Please distract yourself immediately, lest you come up with questions about how this scheme might relate to inheritance, or parametric types, or anything else complicated. If you must, consider these an exercise for the reader (or for Gilad Bracha, whose Newspeak also borrows ideas, but thankfully not syntax, from Beta).