On Nov 10, 2007 1:33 PM, Jon Harrop <[EMAIL PROTECTED]> wrote:
>
>
> On Saturday 10 November 2007 04:33, hlovatt wrote:
> > public interface Exp extends MultipleDispatch { Exp d( Var x ); }
> >
> > public abstract class AbstractExp implements Exp {
> > public final Exp d( Var x ) { return null; } // Body replaced by
> > PEC!
> > public final static Exp d( Var v, Var x ) { return v == x ? new
> > Lit( 1 ) : new Lit( 0 ); }
> > public final static Exp d( Lit l, Var x ) { return new Lit( 0 ); }
> > public final static Exp d( Add a, Var x ) { return new
> > Add( a.left.d( x ), a.right.d( x ) ); }
> > public final static Exp d( Mul m, Var x ) { return new Add( new
> > Mul( m.left, m.right.d( x ) ), new Mul( m.right, m.left.d( x ) ) ); }
> > }
> >
> > public class Var extends AbstractExp {
> > public final String name;
> > public Var( String name ) { this.name = name; }
> > public String toString() { return name; }
> > }
> >
> > public class Lit extends AbstractExp {
> > public final double value;
> > public Lit( final double value ) { this.value = value; }
> > public String toString() { return Double.toString( value ); }
> > }
> >
> > public class Add extends AbstractExp {
> > public final Exp left;
> > public final Exp right;
> > public Add( Exp left, Exp right ) {
> > this.left = left;
> > this.right = right;
> > }
> > public String toString() { return left + " + " + right; }
> > }
> >
> > public class Mul extends AbstractExp {
> > public final Exp left;
> > public final Exp right;
> > public Mul( Exp left, Exp right ) {
> > this.left = left;
> > this.right = right;
> > }
> > public String toString() { return left + " * " + right; }
> > }
>
> I cannot see why you would prefer the above 40 lines of code to the 5 line
> equivalent in OCaml:
I think you're conflating two issues. Yes, OCaml's variants are quite
nice (or at least they look it. I only know the subset of OCaml that
looks behaves more or less like SML), but they're neither neccessary
nor sufficient for pattern matching. A fairer comparison would be
between multiple dispatch and pattern matching on explicitly named
types.
Also, with all due respect to PEC, it's not really a good example of
multiple dispatch - it's Java with multiple dispatch tacked on. So,
here's the corresponding Nice code:
package expression;
// We don't need to declare this, but it will help for type safety.
interface Expr<!T> { }
// Expression types. Note that we do have to declare fields. It would be neat if
// we could extend tuples and get the advantages of destructuring bind
on top of
// multiple dispatch, but Nice doesn't allow that.
class Add<!T> implements Expr<!T>{
Expr<!T> fst;
Expr<!T> snd;
}
class Mult<!T> implements Expr<!T>{
Expr<!T> fst;
Expr<!T> snd;
}
class Int<!T> implements Expr<!T>{
int i;
}
class Var<!T> implements Expr<!T>{
T t;
}
// Syntactic nicety
<!T> Expr<!T> `+` (Expr<!T> fst, Expr<!T> snd) = new Add(fst : fst, snd : snd);
<!T> Expr<!T> `*` (Expr<!T> fst, Expr<!T> snd) = new Mult(fst : fst, snd : snd);
<!T> Expr<!T> int(int i) = new Int(i : i);
// Differentiation of expressions.
// I swear there's a way to omit both the 'override' and the return
types for the overridden methods
// but I can't figure out how the syntax interacts with declaring type
parameters. :-/
<!T> Expr<!T> diff(Expr<!T> v, T x);
override <!T> Expr<!T> diff(Var<!T> v, T x) = int(x == v.t ? 1 : 0);
override <!T> Expr<!T> diff(Int<!T> v, T x) = new Int(i : 0);
override <!T> Expr<!T> diff(Mult<!T> v, T x) = v.fst * diff(v.snd, x)
+ diff(v.fst, x) * v.snd;
override <!T> Expr<!T> diff(Add<!T> v, T x) = diff(v.fst, x) + diff(v.snd, x);
> let rec d f x = match f with
> | `Var y when x=y -> `Int 1
> | `Int _ | `Var _ -> `Int 0
> | `Add(f, g) -> `Add(d f x, d g x)
> | `Mul(f, g) -> `Add(`Mul(f, d g x), `Mul(g, d f x))
>
> You have added a toString() function. However, it is broken: you need to
> bracket according to precedence. Doing this correctly is actually quite an
> interesting exercise as well. Here is an OCaml implementation:
>
> open Printf;;
> let rec string_of () = function
> | `Var x -> x
> | `Int n -> sprintf "%d" n
> | `Add(f, g) -> sprintf "%a + %a" string_of f string_of g
> | `Mul(f, g) -> sprintf "%a %a" string_of_mul f string_of_mul g
> and string_of_mul () = function
> | `Add(f, g) as e -> sprintf "(%a)" string_of e
> | e -> string_of () e;;
>
> How does that translate?
// I'm pretty sure it should be possible to declare f inside the
toString method for Mult (which is the only place it's used),
// but once again I can't figure out the syntax.
<!T> String f(Expr<!T> t) = toString(t);
override <!T> String f(Add<!T> t) = "(" toString(t) ")";
<!T> String toString (Int<!T> i) = toString(i.i);
<!T> String toString (Var<!T> v) = toString(v.t);
<!T> String toString (Mult<!T> m) = f(m.fst) + f(m.snd);
Some things of note:
a) There are various language problems here, and various places where
it's clumsier than it should be. These are mostly unrelated to the
multiple dispatch. Some of them are Nice being clumsy, some of them
are me being really rusty at the language.
b) Nice doesn't do destructuring bind of constructors, but there's
absolutely no reason why it couldn't. It's just syntax. If it did then
the multiple dispatch declarations would look *much* closer to the
pattern matching.
c) Once we've declared the types, the only additional code over the
ocaml version is the need to include some type declarations it omits.
Philosophically speaking, pattern matching is extremely close to a
more limited form of multiple dispatch + destructuring bind of
constructors. But because it's more limited (and because a great deal
more work has been put into making it good!) the compiler can infer
more information in the statically typed case.
> > One aspect of the syntax that I like with multiple dispatch is that
> > you write overloaded functions rather than a switch statement, which
> > reads better to my eyes.
>
> I suspect the bloat caused incurred by the approach that you are advocating is
> even worse though: more complicated patterns (particularly parallel patterns
> and deep patterns) will probably require asymptotically more code.
>
> Consider this simplifying symbolic multiplication function, for example:
>
> let rec ( *: ) f g = match f, g with
> `Int n, `Int m -> `Int(n * m)
> | f, `Int 0 | `Int 0, f -> `Int 0
> | f, `Int 1 | `Int 1, f -> f
> | f, `Mul(g, h) -> f *: g *: h
> | f, g -> `Mul(f, g)
>
> How does that translate? Particularly the associativity match case?
This one indeed *doesn't* translate as well as I'd like. This is
basically because of the inability for Nice to chain the dispatch
rules nicely.
In particular there's no easy equivalent of the combining patterns,
and although we can dispatch on 0 and 1 specially this doesn't lift to
let us dispatch on Int 0 and Int 1 specially. I'm not sure why you
thought the associativity would be difficult though - that works out
fine.
// Multiplication
<!T> Expr<T> `*` (int i, Expr<T> x) = new Mult(int(i), x);
override <!T> Expr<T> `*` (int i, Int<T> x) = int(i * x.i);
override <!T> Expr<T> `*` (0, x) = int(0);
override <!T> Expr<T> `*` (int 1, x) = x;
<!T> Expr<T> `*` (Expr<T> x, int i) = new Mult(x, int i);
override <!T> Expr<T> `*` (Int<T> x, int i) = int(i * x.i);
override <!T> Expr<T> `*` (x, int 0) = int(0);
override <!T> Expr<T> `*` (x, int 1) = x;
override <!T> Expr<T> `*` (Int<T> i, Expr<T> x) = i.i * x;
override <!T> Expr<T> `*` (Expr<T> x, Int<T> i) = i.i * x;
override <!T> Expr<T> `*` (Expr<T> x, Mult<T> y) = (x * y.fst) * y.snd;
As you can see, it involves a bunch of repetition and some annoying hacks.
Don't get me wrong - I agree that the OCaml code is better in places,
and there's not much in the Nice code which I can point to as better
(at least nothing relevant). Particularly the multiplication example.
There are various limitations on the Nice dispatch system which make
it hard to beat a good pattern matching system in this instance, and
the lack of destructuring bind is a real nuisance. But hopefully these
examples show that the basic facility to do what you want is there,
and none of these problems are inherent to the idea of multiple
dispatch. Additionally, I don't think the OCaml code is *much* better.
There are a few problems which will always be there - it's much harder
to infer things in the presence of full blown nominal subtyping for
example. But on the other hand there are a lot of things which
multiple dispatch makes noticably easier as well. There are tradeoffs,
but I don't think either approach is obviously better than the other.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "JVM
Languages" group.
To post to this group, send email to jvm-languages@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/jvm-languages?hl=en
-~----------~----~----~----~------~----~------~--~---
