Lambda the Ultimate

I wanted to say that i wasn't criticizing the paper, I enjoyed reading it, and it gives a clear view of those different techniques and the issues.

I enjoyed the extractor part, as it seems close to the mapping Tom uses. For example, the "Twice" operator example in Section 4 can be written in Tom:

  %include {int.tom}                                                                                                   
                                                                                                                       
  %op int Twice(n:int) {                                                                                               
    is_fsym(t) { t%2==0 }                                                                                              
    get_slot(n, t) { t/2 }                                                                                             
    make(t) { t*2 }                                                                                                    
  }                                                                                                                    
                                                                                                                       
  public final static void main(String[] args) {                                                                       
    int x = `Twice(21);                                                                                                
    %match(x) {                                                                                                        
      Twice(y) -> { System.out.println(x+" is two times "+`y); }                                                       
      _ -> { System.out.println(x+" is a number"); }                                                                   
    }                                                                                                                  
  }                       

The "_" part will always be executed, as the %match construct in Tom behaves like the switch instruction of Java: after a sucessfull match, the control flow passes to the next pattern unless there is an explicit return or break.

Thanks for the compliment!

Regarding the style, on the one hand, we should have avoided repeating that construction, on the other hand it only appears three times! : ) Seriously, it is not easy to make a comparison between different techniques without stressing the trade-offs involved.

Regarding the upcoming discussion in this forum, I wonder if functional programmers will recognize GADTs as such when they appear in a programming language that happens *not* to be Haskell or ML?

I almost couldn't recognized GADTs in this paper and they said it was about GADTs and I'm an OO programmer by day ;)

Now for something completely different, as there is a connection between OO and coalgebra wouldn't make sense for have GCaDT as well?

Dear Chris, thanks for the compliment. While it is reassuring, it also means that performance is much less predictable from the source, because one needs more information on what the JIT does (and ideally, how it does it). As remarked in the paper, we expected a performance penalty, and it came as quite a surprise that performance was that good (especially for cast). The Sun guys have embraced instanceof without telling anybody :)

Dear Thorsten, thanks. The real OO approach you describe is left out for a reason. People often argued like this, e.g. in response to Martin's blog entry on pattern matching. If we want to make pattern matching popular among the masses, we will have to be clearer on where to draw the line -- but I think most experienced OO designer (experienced as in: burnt by mistakes in real life projects) would see the problems with the approach.

Can you agree with this motto: I would never use this approach at all, except when I am the author of the class and 100% sure that this functionality will not change. Adding a new method means changing all the classes.

The paper however looks for solutions to decomposing "from the outside", the scenario being that one does not have the luxury of owning the classes, or that you have to design classes such that people can add meaningful operations on them without needing access to their source code.

I'm probably spoilt by using Smalltalk in real life projects, which allows extending existing classes with new functionality :-)

Transferring this idea to Scala, it would be nice to be able to write something like the following. Of course, the extensions should only be visible from within the Simplification module (and its users).

module Expr {
  trait Expr { }
  class Num(val value : int) extend Expr { }
  class Mul(val left : Expr, val right : Expr) extend Expr { }
}

module Simplification {
  import Expr

  extend trait Expr {
    def isUnit : boolean = false
    def simplified : Expr = this
  }

  extend class Num {
    override def isUnit = value == 1
  }

  extend class Mul {
    override def simplified = if (right.isUnit) left.simplified else super
  }
}

In mainstream languages where this is not possible, I agree that there it will often be neccessary to be able to decompose from the outside.

To clarify: I'm not against pattern matching. In fact I like it. But I like the OO approach, too :-)

In Scala its fairly easy to get virtual classes using a pattern, your example in Scala:

trait Base {
  type Expr <: ExprImpl;
  trait ExprImpl { def self : Expr; ...}
  type Num <: Expr with NumImpl;
  trait NumImpl extends ExprImpl { def self : Mult; val value : Int; }
  def Num(value : Int) : Num;
  type Mult <: Expr with MultImpl;
  trait MultImpl extends ExprImpl { def self : Mult; val left : Expr; val right : Expr; }
  def Mult(val left : Expr, val right : Expr) : Mult;
}

trait Simplification extends Base {
  type Expr <: ExprImpl;
  trait ExprImpl extends super.ExprImpl {
    def self : Expr;
    def isUnit = false;
    def simplified : Expr = this;
  }
  type Num <: Expr with NumImpl;
  trait NumImpl extends super.NumImpl with ExprImpl {
    def self : Num;
    override def isUnit = value == 1;
  }
  type Mult <: Expr with MultImpl;
  trait MultImpl extends super.MultImpl with ExprImpl {
    def self : Mult;
    override def simplified = if (right.isUnit) left.simplified else   super.simplified;
  }
}
class Compose extends Somplified {
  trait Expr extends ExprImpl { def self : Expr; }
  case class Num(value : Int) extends NumImpl with Expr { def self = this; }
  case class Mult(left : Expr, right : Expr) extends MultImpl with Expr { def self = this; }
}

You can compose multiple extensions together using mixin-inheritance, its very flexible: I've implemented a large software system using this pattern and I'm very satisfied with the results. Of course, we need better syntactic sugar for this; i.e., Scala should support virtual classes in its syntax to support virtual class extension directly.

Thanks for the nice example.

Any reason not to use explicitly typed self references, instead of defining self methods in each trait & class?

I mean:

trait Base {
  type Expr <: ExprImpl;
  trait ExprImpl { self : Expr => /*...*/}
  type Num <: Expr with NumImpl;
  trait NumImpl extends ExprImpl { self : Num => val value : Int; }
  val Num : Int => Num;
  type Mult <: Expr with MultImpl;
  trait MultImpl extends ExprImpl { self : Mult => val left : Expr; val right : Expr; }
  val Mult : (Expr, Expr) => Mult;
}

trait Simplification extends Base {
  type Expr <: ExprImpl;
  trait ExprImpl extends super.ExprImpl { self : Expr =>
    def isUnit = false;
    def simplified : Expr = self;
  }
  type Num <: Expr with NumImpl;
  trait NumImpl extends super.NumImpl with ExprImpl { self : Num =>
    override def isUnit = value == 1;
  }
  type Mult <: Expr with MultImpl;
  trait MultImpl extends super.MultImpl with ExprImpl {	self : Mult =>
    override def simplified = if (right.isUnit) left.simplified else super.simplified;
  }
}
class Compose extends Simplification {
  trait Expr extends ExprImpl
  case class Num(value : Int) extends NumImpl with Expr
  case class Mult(left : Expr, right : Expr) extends MultImpl with Expr
}

Is there any reason NOT to do this? Thanks.

No, not at all. When I did this (5 years ago), something pushed me away from explicit self types, though I have no recollection of what that was. Today, Scala has changed a lot; explicit self types are probably more robust now.

I noticed this too, and assumed that the goal of extensibility
conflicted with the goal of exhaustiveness checking.

I'd like to see some approach to this (maybe "final" case classes or
somesuch) myself. So far all of my Scala code is "toy" sized, but
my experience with OCaml (and C vs Ada) has convinced me that the exhaustiveness checking is a good thing. Much more important to me
than having XML built into the language...

hello, I feel the urge to render this discussion thread a bit more timeless by announcing that the incompleteness check was added to the Scala implementation, roughly one month or two after the post above. however, so far it is not combined with extractors. some workable convention is needed to tell the compiler "this set of extractors is mutually exclusive and complete for this type", so that incompleteness checking can be enabled for extractors aswell.

It's true that extensibility clashes with incompleteness checking, that's why the curent implementation does it only if the sealed keyword is present and the match is on case classes. Mikael Pettersson's 1992 CC paper is very helpul in implementing incompleteness checking.