Erasure Wars: No End in Sight

Among the other excellent sessions at the JVM Language Summit yesterday, Mads Torgersen talked about .NET and its CLR multilanguage VM. The CLR runs C#, among other languages (including Java, if you get Jeroen Frijters's IKVM—he treated us to the astonishing spectacle of Eclipse running on .NET in a later session yesterday).

For those of who spend most of our time with the JVM, the CLR is a fascinating alternate universe. Originally inspired by the Java VM, most of its details are familiar, but enough are different that contemplating the CLR gives me that hint of vertigo you feel when you've been looking at the world through one eye and then suddenly switch to stereo vision.

Perhaps the most conspicuous difference between the two VMs is that the CLR does not erase type parameters, a choice made to support the semantics of C#'s parameterized types. By not throwing away the information about how a parameterized class instance is allocated, the CLR enables things like specialization based on the type arguments, as well as the ability to answer obvious runtime questions like, what is that List a list of?

To be sure, unerased types have a cost; you actually have to construct and store the runtime representation of the types in question. Furthermore, introducing unerased types to the JVM at this late date would be extremely disruptive, and the Java folks discourage speculation about it, although I got the impression yesterday that they're a bit of envious of what the CLR can do with them. But if there are other negative consequences of unerased types, I'm not aware of them—although someone said yesterday that Martin Odersky thinks type erasure is a Good Thing, which is enough to give one pause.

Not erasing types does raise some exotic possibilities. If type arguments are real arguments actually passed when an object is constructed, and the constructed object's type depends on those arguments, what if the object's type depended on arguments that weren't types? This is a peek into the world of dependent types, which should be enough to keep the mathematically minded awake at night.

Cooler heads may have decided that I don't get my unerased type arguments, but I still can't help looking over the fence and drooling. There may be workarounds in theory to the lack of runtime type arguments on the JVM, but in practice, it seems there's never a manifest around when you need one.

A Human Condition

A while ago I was talking with a friend of mine about some science fiction I'd read. I don't remember the story's premise, but it was something different from the everyday reality we moderns are familiar with. My friend's reaction was to dismiss the story as absurd: “But that would change the human condition!”

People often use the term “human condition” as if it referred to something immutable and eternal. Although I suspect that some aspects of our existence are forced upon us by the fact that we are tool-using social animals, a lot of the assumption we and everyone we know make about our lives seem more likely to be specific to our time and place. So I've wondered from time to time: what does constitute a change to the human condition? (And is the human condition shared by all humans at all times? Could some nonhumans also experience the human condition?)

I'll take a shot at answering my question, even though other people have answered it often and with more thought. A human condition, I'll say, is a broad cultural outlook constrained by human institutions, and includes the possibilities people perceive for their own lives when they live under those institutions. A human condition is not specific to a particular culture, in the usual sense of the world “culture”, but belongs instead to a broad complex of cultures at roughly the same level of development. A change in the human condition is a change in the shape of the psychological space of the people who share that condition, or at any rate in the consensus of those people on what psychological spaces exist.

I think agriculture was probably a technology big enough to have changed the human condition. It turned the landscape from a natural place to a made place. It created property and wealth in the modern sense—you could own more than you could carry. Agriculture required longer-term planning and longer persistence at a single activity than hunting and gathering, and so created the beginnings of the modern sense of time.

Agriculture enabled cities, another human-condition disruption. Cities meant that, for the first time, most people you encountered on a daily basis were strangers. That meant rules for how to behave in public, and so there was now a distinction between public and private spaces.

Cities required larger and more anonymous systems of government than agricultural villages, and so begat the state. States, and the elaborate religions that accompanied them, created the possibility of loyalties to things and people other than your family and friends.

And perhaps my favorite of all, there's writing. Writing, for the literate, turns memory from a short-term feat shared with few to enduring knowledge shared with many—with the world and with the ages, if you're lucky and you write skillfully enough. Knowledge has always been a form of power, but writing let you acquire a whole heap of knowledge and literally lock it up.

For the five millennia from the invention of writing and the rise of the first city-states until the industrial revolution, I would say that the human condition remained largely unchanged in the most densely populated parts of the world. States came and went; religions came and went; languages and customs came and went; technologies came and went. But the shape of psychological possibilities in most urban and agricultural societies was similar: if you were a member of the elite, you had some measure of freedom and some scope for ambition, and often a reasonably broad education even by modern standards. And if you were not one of the elite, you usually had little or none of those. And it was obvious to everyone that there had to be an elite who had the freedom to obey their desires, and a much larger mass of people who had to obey the elite.

The harnessing of fossil fuels and the invention of mass production again changed the shape of society and of human ambitions. Even relatively poor people could afford more than the minimum needed to keep them alive. Societies could afford to educate everyone. Knowledge was still power, but there was a lot more power around, both in terms of the physical expenditure of energy and the degree of control people had over their lives. The assumption that an elite is inevitable became open to question. Democracy became widely viewed not as a dangerous experiment but as the default way to organize government.

The latest thing to change the human condition is the internet, or more precisely, inexhaustible storage and retrieval of information and ubiquitous connectivity to that information. Remember conversations before Google? Traveling before GPS? Those experiences are shrinking in the rear view mirror, off to join the telegraph and the steam locomotive. Now everyone knows everything, or at least everything for which they can come up with decent search terms. Although there are types of power other than knowledge, the power that is knowledge belongs to everyone in the world who can afford a phone or a computer.

I don't think I've fully internalized what it means to be human now that our condition has changed again. Have you? What do we do with ourselves now?

Pushing Back

Streams are Scala's flagship lazy data structure, and they let you do all the good things that lazy evaluation enables. But although laziness can have performance benefits (by not evaluating something that will never be used, or delaying a computation that would entail deep recursion if performed eagerly), it can also incur a performance cost by unnecessarily wrapping an already-evaluated value in a thunk.

If every item in a sequence is already evaluated, you'll want to use a List, not a Stream. But sometimes you have a sequence that is a mix of evaluated and unevaluated items, often because you look ahead in a stream and evaluate and then push back items that are not processed immediately. This can occur in compiling programming languages, or in normalizing the order of a prettyprinting token stream, as in S. Doaitse Swierstra and Olaf Chitil's 2009 paper Linear, Bounded, Functional Pretty-Printing.

It occurred to me that you can write a Scala-style stream that avoids the thunk-wrapping and unwrapping that occurs when you push an item onto the head of an already-evaluated stream (in Scala, only the tail of the stream is ever passed by name; the head of a stream is passed by value when the stream is created, and so is always preevaluated). Every function that constructs a stream knows whether its tail is passed by name, and could theoretically create different types of cons cell for evaluated and unevaluated streams:

  abstract class Cons [+A] extends Stream[A] {
    ...
  }

  class LazyCons [+A] (val head: A, after: => Stream[A])
      extends Cons[A] {
    lazy val tail = after
  }

  case class EagerCons [+A] (head: A, tail: Stream[A])
    extends Cons[A]

In SI-4698 I submitted a timing test that lets you observe the cost of LazyCons vs. EagerCons in the case where the tail has already been evaluated. On my machine it takes over 50% longer to construct or examine a lazy cell than an eager cell.

I don't know whether Scala streams users add items to the head of already-evaluated streams often enough to make it worth complicating the standard streams implementation with a change like this just for the speedup. But it's an idea.

Exceptionally Lazy Messages

In a perfecter world, wouldn't Java exceptions have been better defined with their messages as by-name arguments?:

  class Throwable (message: => String, cause: Option[Throwable] = None)

Not that that's Java syntax, but you know what I mean.

Any number of times, I've gone to throw an exception with a nice detailed message, but confused myself by getting an exception during the construction of the message instead. The latter exception obscures the occurrence of the problem that would have thrown the former exception.

Maybe I'm the only one who writes message-building code complicated enough to have bugs of its own, but maybe not. I'm just sayin'.

Too Lazy to Recurse

If a tree doesn't fall in the forest, but instead you record some instructions (which you might or might not carry out later) on how to make the tree fall, does the Scala compiler make a sound?

The answer appears to be yes, at least when you're trying to use the @tailrec annotation (which complains about recursive calls when they don't appear in tail position).

For example, consider this completely useless function, which computes a value equal to its (nonnegative) argument by recursing in nontail position:

  def foo (i: Int): Int = if (i == 0) 0 else 1 + foo(i - 1)

If you mark this declaration @tailrec, the Scala compiler complains, as expected; the call to foo(i - 1) is not the last thing evaluated in foo, because the 1 + remains to be done after foo returns.

Now consider:

  case class Later1 (deferredI: () => Int) {
    lazy val i = deferredI()
    override def toString: String = i.toString
  }

  def foo1 (i: Int): Later1 =
    if (i == 0) Later1(() => 0) else Later1(() => 1 + foo1(i - 1).i)

Like foo, foo1 contains (textually) a call to itself. But foo1 doesn't actually call itself during an invocation of itself; it just computes and stores a function that would call foo1 later, if anyone bothered to invoke it. It's clear that such a call to foo1 isn't tail-recursive—you could never replace it with a goto—but then you would never expect it to be, since it's not called from foo1.

So is the Scala compiler being too picky about @tailrec? To be fair, you might want it to complain if instead you did something like:

  def foo1a (i: Int): Int =
    if (i == 0) 0 else Later1(() => 1 + foo1a(i - 1)).i

foo1a defers the call to itself only long enough to wrap the call in a Later1, then goes ahead and forces the call to complete anyway before returning. Even if you didn't want a warning for the foo1 case, you might want one here.

And even in the previous case, although foo1 returns a Later1 without ever reinvoking foo1, the computation captured in the Later1 will recurse, if it's ever carried out. Later1.i calls the deferredI created by foo1, and that deferredI calls Later1.i (where the latter Later1 results from calling foo1 again, although there are never two calls to foo1 on the stack at the same time).

As an aside, Scala does provide a more succinct way to express a deferred call to a function with no arguments. Although by-name vals are illegal, so that this won't compile:

  // BAD: case class pararameter i is a val:
  case class Later2 (i: => Int) {
    override def toString: String = i.toString
  }

you can trade some added boilerplate at the declaration of Later2 for some reduced boilerplate when you construct a Later2:

  class Later2 (deferredI: => Int) {
    lazy val i = deferredI
    override def toString: String = i.toString
  }

  object Later2 {
    def apply (i: => Int) = new Later2(i)
  }

  def foo2 (i: Int): Later2 =
    if (i == 0) Later2(0) else Later2(1 + foo2(i - 1).i)

Note that there's no need for “() =>” in the arguments to Later2.

The version using Later2 works as expected, but foo2 still provokes the compiler's wrath if you annotate it with @tailrec.

Scala Internal DSL for Lambda Calculus

I've been playing with the untyped lambda calculus recently, and come up with this notation for it in Scala:

    'x ^: 'y ^: 'x ! 'y
    'x ^: 'y ^: 'x ! ('x ! 'y)
    'x ^: 'y ^: 'x ! ('x ! ('x ! 'y))

which translates to:

    λx.λy.xy
    λx.λy.x(xy)
    λx.λy.x(x(xy))

(You might recognize these as the Church numerals one through three.)

To digest this, you first have to imagine abstraction as an infix operator rather than a prefix operator. If you squint a little, you can see a caret as a lambda (the colon is necessary to get Scala to make the operator right-associative, as is conventional).

The exclamation point is the application operator by analogy with the notation used in Scala Actors. It takes only a wee bit of mental squinting to see passing an argument to a function as sending a message to an actor.

The single quote prefix in Scala turns an identifier into a Symbol, which is like a String but with only half the quoting. Scala Symbols are intended for purposes that are, uh, symbolic—I think a lambda calculus variable qualifies.

As cute as dancing kittens? You be the judge.

Almost Literate Syntax Trees

Suppose you're translating a lambda calculus expression like:

λx.λy.λz.xyz

into a Lisp-like syntax tree:

  (fun 'x
    (fun 'y
      (fun 'z
        (apply
          (apply (sym 'x) (sym 'y))
          (sym 'z)
        )
      )
    )
  )

where sym expresses a reference to a symbol that is (or should be) bound in the current context.

If you replace fun with givenA and sym with the, the result looks like:

  (givenA 'x
    (givenA 'y
      (givenA 'z
        (apply
          (apply (the 'x) (the 'y))
          (the 'z)
        )
      )
    )
  )

This exploits an English speaker's understanding that “a” introduces a term, and “the” refers to an occurrence of that term in the same context.

The second example reads better to me, but I haven't been able to come up with an everyday-English equivalent for apply. Maybe it's just not an everyday concept.