Lambda the Ultimate

I believe that any class+functionality encoded using these approaches (i.e. using inernal methods as mentioned in the above quote) can be written using multimethods both more easily and more concisely (but the "more easily" part is subjective and therefore arguable). The type system should prevent using multimethods that have no default case - just as it would prevent using methods that aren't implemented in the approaches used in this paper. I believe that multimethods can indeed be more flexible as some kind of advanced type system could check whether the need for default case actually arises (maybe a multimethod is never used on a class with no case defined but only on its subclasses... and similar).

The possible weakness of multimethods that I see and wonder whether its "a real weakness" (meaning it can be the issue in practice) is that multimethods are "global", as compared the mechanism explained in the previous paper, The expression problem, Scandinavian style, where a class family can not be extended, but a new family can be defined, inheriting all the old functionality (so no code repetition) and extending it. In this manner, the old family is not modified and both (the new and the old) families can be used independently. Any comments?

Seems to me that you don't need much of anything, just sum and recursive types, to basically solve the expression problem. Additional language features only serve to reduce, but (it seems) never completely eliminate, the boiler plate required to create particular ad hoc combinations.

Here is a toy example along the lines of Garrigue's solution using polymorphic variants except that here we use only ordinary variant types and SML. The essence of this technique is to produce a combination of the form fix (f1 + ... + fN). Multiple inheritance isn't an issue, because taking the fixpoint is only the last step.

First some reusable datatype and function fragments:

datatype 'e lam = ABS of string * 'e | APP of 'e * 'e | VAR of string

fun lookup s = List.find (fn (s', _) => s = s')
val gensym = let
   val i = ref 0
in
   fn () => "_" ^ Int.toString (!i) before i := !i + 1
end

fun lamEval {from, to} eval e =
 fn ABS (s, b) => let val s' = gensym ()
                  in to (ABS (s', eval ((s, to (VAR s'))::e) b))
                  end
  | APP (f, x) => let val f = eval e f
                      val x = eval e x
                  in case from f of
                        SOME (ABS (s, b)) => eval ((s, x)::e) b
                      | _                 => to (APP (f, x))
                  end
  | VAR s      => case lookup s e of
                     SOME (_, v) => v
                   | _ => to (VAR s)

fun lamToString toString =
 fn ABS (s, b) => "(\\"^s^"."^toString b^")"
  | APP (f, x) => "("^toString f^" "^toString x^")"
  | VAR s      => s

datatype 'e num = NUM of int | ADD of 'e * 'e | MUL of 'e * 'e

fun numEval {from, to} eval env = let
   fun evalBop bop con (l, r) = let
      val l = eval env l
      val r = eval env r
   in
      case (from l, from r) of
         (SOME (NUM l), SOME (NUM r)) => to (NUM (bop (l, r)))
       | _                            => to (con (l, r))
   end
in
   fn NUM i => to (NUM i)
    | ADD ? => evalBop op + ADD ?
    | MUL ? => evalBop op * MUL ?
end

fun numToString toString =
 fn NUM i => Int.toString i
  | ADD (l, r) => "("^toString l^" + "^toString r^")"
  | MUL (l, r) => "("^toString l^" * "^toString r^")"

datatype 'e cons = CONS of 'e * 'e | FST of 'e | SND of 'e

fun consToString toString =
 fn CONS (l, r) => "("^toString l^", "^toString r^")"
  | FST e       => "(#1 "^toString e^")"
  | SND e       => "(#2 "^toString e^")"

fun consEval {from, to} eval e = let
   fun prj f c t = let
      val t = eval e t
   in
      case from t of
         SOME (CONS p) => f p
       | _             => to (c t)
   end
in
   fn CONS (f, s) => to (CONS (eval e f, eval e s))
    | FST t       => prj #1 FST t
    | SND t       => prj #2 SND t
end

Then an ad hoc combination of said fragments:

datatype t = L of t lam | N of t num | C of t cons

fun toString t =
    case t of
       L l => lamToString  toString l
     | N n => numToString  toString n
     | C c => consToString toString c

fun eval e t =
    case t of
       L l => lamEval  {from = fn L l => SOME l | _ => NONE, to = L} eval e l
     | N n => numEval  {from = fn N n => SOME n | _ => NONE, to = N} eval e n
     | C c => consEval {from = fn C c => SOME c | _ => NONE, to = C} eval e c

val e = L (APP (L (ABS ("x",
                        N (ADD (C (FST (L (VAR "x"))),
                                N (NUM 1))))),
                C (CONS (N (NUM 2), N (NUM 3)))))

val N (NUM 3) = eval [] e
val "((\\x.((#1 x) + 1)) (2, 3))" = toString e
val L (VAR "y") = eval [] (L (APP (L (ABS ("x", L (VAR "x"))), L (VAR "y"))))

Adding both new datatype fragments and new functions is easy. Producing a new ad hoc combination takes some amount of boiler plate, but it is entirely straightforward and can be factored in various ways (e.g. using a generic sum type) for increased reuse (of the combination code). Indeed, all solutions to the expression problem (including Garrigues's use of polymorphic variants) that I've seen require some amount of ad hoc code to produce a particular combination and some authors argue that it is fundamentally unavoidable. However, I doubt that reducing the amount of boiler plate required to implement an ad hoc combination is all that significant in practice. Most applications aren't going to use dozens of combinations. What matters is the ability to build a library of combinable datatype and function fragments that allow one to produce a desired combination for a particular application.