Thursday, 18 March 2010

Type Frustrations II : Return of the Erasure

Work is currently sucking up every single scrap of energy I have. Work does this. Sweet, sweet release is on the distant horizon though. In order to not go completely insane, I have been continuing to fiddle with my own stuff, and here's another irritated braindump:

This seems interesting. Where by 'interesting' I mean 'very frustrating'.

I found a lovely little implementation of the simply-typed lambda calculus in the paper "Matching Objects With Patterns". This looked like an interesting way to approach the storage of heterogeneous data for game entities, so here's the bare bones in this context:

case class Var[A]( name: String )

  abstract class Env {
    def apply[A]( v: Var[A] ) : A
    def extend[A]( v: Var[A], x: A ) : Env = new Env {
      def apply[B]( w: Var[B] ) : B = w match {
        case _ : v.type => x
        case _ => Env.this.apply(w)

  object Empty extends Env {
    def apply[A]( v: Var[A] ) : A = error( "not found: " )

  //use it like this:
  val entity = Empty.extend(Var[Int]("health"),95).extend(Var[String]("desc"),"a wild fnord")
  val entity_desc = entity(Var[String]("desc"))

This is easily fiddled with to remove a lot of the boilerplate when extending the Env, but anyway...

It's a little bit odd. The slightly strange v.type is what got me excited; this is the singleton type of v, in Scala parlance. This means it's a type unique to v, equal to another singleton type only if the objects compare equal according to the method eq.

Because Var[A] is a case class (and a very simple one at that), this means that v.type == w.type if the constructor arguments are the same and - my assumption - if the type parameters of the two Vars are also the same. After all, Var[Int] clearly has a different type to Var[String].


Enter type erasure. At runtime, all those Var[Int] and Var[String] and Var[Pony] are just plain Var. Singleton types for these now only depend on the constructor arguments, which means stuff like this:

//this should produce a "not found" error:

java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String

This becomes even more horrible if the code is extended to return an Option, so that rather than producing an error on accessing an undefined variable we simply return None. In this case, the above code returns what appears to be a perfectly valid Some[String], right up until you try to access the contained 'string' and hit the same cast exception but in an entirely arbitrary point in the code, potentially miles from the source of error.

It's so very frustrating that this elegant code doesn't work, simply because a little chunk of information is not present at runtime. Type erasure; it really is the most annoying thing about working with Scala, and I bump into it far more than I would like.

PS: Picked up Clojure again. Maybe I'm completely insane (I am), but I'm tempted to write the game as a sever/client app, with the game logic entirely in Clojure and using Scala for the rendering/IO. That's a lot of extra protocols to implement, and it still has problems, but... this is exactly the kind of thing that is a non-issue in a Lisp.

PPS: I made a half-hearted stab at implementing the Env in Haskell. Yeah, the syntax has entirely leaked out of my head after a mere few months of disuse. It wasn't pretty.


Paul said...

First of all, if you're thinking of reimplementing the lambda calculus, it's time to start using a lisp.

If I wanted to write a game using a lisp within the JVM, I would look at either Armed Bear Common Lisp, or Kawa (scheme). Maybe the latter as Kawa is more mature, though I think CL is the superior language.

If you don't require the JVM, there are many more options.

Clojure is a very interesting language, but quite young, and lacks any OOP facilities (Rich Hickey is set firmly against OOP). More generally, it's a pure functional language like Haskell, and there is a reason that almost no games are written in such languages: it is a very unnatural paradigm in which to write games.

Snut said...

Hey Paul, cheers for the comment!

I suspect I should have written with more clarity on this point: I'm not interested in implementing any flavour of lambda calculus.

I have a far less interesting problem. I want to represent a wide variety of game objects in a manner which is elegant to use and extremely flexible. The standard approach of just writing static classes is, well, boring to implement and inflexible. Component systems are pleasantly labile but tend towards ugly syntax, at least in my implementations.

The 'property bag' approach is nice, but static typing in Scala makes it a pain to implement and, again, it gets ugly (Clojure or another lisp makes this deliciously easy). This implementation of environments seemed to address this, but run afoul of type erasure problems. Hence frustrated blog post and re-examining dynamically typed languages.

I'll check out Kawa again, though, thanks for reminding me! Common Lisp is a bit... warty, I'm more of a Scheme person I suspect.

I'm not married to the JVM, but it does make an interesting platform for writing windows/linux games and I am a huge fan of Scala, so anything with easy Java interop gets points.

Re: Clojure... it's hardly pure, based on my limited experience. Like Scala, it defaults to a functional style but you can drop into imperative mode as needed, which seems very practical for writing (certain classes of) games. I'm not fussed about OO for the game logic, either.

James Iry said...

You mention Haskell but what you don't mention is that GHC Haskell lives in type erasure land. It just doesn't get you into trouble because, unlike Scala, there isn't a general "match on dynamic type" mechanism - only a match on constructor mechanism.

Anyway, since v.type is the singleton type of v, I have to ask why you don't write the much simpler

def apply[B]( w: Var[B] ) : B = w match {
case `v` => x
case _ => Env.this.apply(w)

The backticks just mean you don't want to bind a new v you want to use an existing binding and match for equality (using .equals).

Snut said...

Hi James,

I didn't mention it because it's news to me!

I really am a rank amateur when it comes to Haskell, and only very, very slightly better with Scala. A lot of my frustration is not aimed at type erasure per se, but my thwarted expectations whenever it pops up. It looks obvious and correct, but doesn't work.

Maybe this is the kind of thing manifests will help deal with. Simply tagging the Var[A] with an automatically generated type string might be sufficient for my needs...

Regarding the nicely compact refactoring, I'm ashamed to admit I've not encountered the Scala backtick before. I assume it was left out of the original paper in this case to prevent the introduction of additional syntax.

Cheers for the comment, and for introducing me to a handy bit of sugar!