Il compilatore Scala non può dedurre il tipo di mix-in per la corrispondenza di modelli

Question

Ho un caso d'uso per gruppi algebrici su insiemi di permutazioni finiti. Poiché mi piacerebbe utilizzare il gruppo per varie classi di permutazione che sono altrimenti non correlate, mi piacerebbe farlo come tratto di mix-in. Ecco un estratto del mio tentativo

trait Permutation[P <: Permutation[P]] { this: P => 
    def +(that: P): P 

    //final override def equals(that: Any) = ... 
    //final override lazy val hashCode = ... 

    // Lots of other stuff 
} 

object Permutation { 
    trait Sum[P <: Permutation[P]] extends Permutation[P] { this: P => 
    val perm1, perm2: P 

    // Lots of other stuff 
    } 

    private object Sum { 
    def unapply[P <: Permutation[P]](s: Sum[P]): Some[(P, P)] = Some(s.perm1, s.perm2) 
    //def unapply(s: Sum[_ <: Permutation[_]]): Some[(Permutation[_], Permutation[_])] = Some(s.perm1, s.perm2) 
    } 

    private def simplify[P <: Permutation[P]](p: P): P = { 
    p match { 
     case Sum(a, Sum(b, c)) => simplify(simplify(a + b) + c) 

     // Lots of other rules 

     case _ => p 
    } 
    } 
} 

Ad un certo punto nel tempo, vorrei chiamare il metodo di semplificazione al fine di, beh, semplificare un'espressione di operazioni di gruppo con gli assiomi algebrici. Usare la corrispondenza dei pattern sembra avere senso in quanto vi sono molti assiomi da valutare e la sintassi è concisa. Tuttavia, se compilo il codice, ottengo:

error: inferred type arguments [P] do not conform to method unapply's type parameter bounds [P <: Permutation[P]] 

Non capisco il motivo per cui il compilatore non può dedurre il tipo corretto e non so come aiutarlo. In realtà, il tipo di parametro di P è irrilevante quando la corrispondenza del modello in questo caso. Se p è una Somma delle permutazioni, il modello deve corrispondere. Il tipo restituito è ancora un P perché la trasformazione viene effettuata esclusivamente chiamando l'operatore + su P.

Quindi in un secondo tentativo si scambia la versione commentata di unpply. Tuttavia, allora ottengo un errore di asserzione del compilatore (2.8.2):

assertion failed: Sum((a @ _), (b @ _)) ==> Permutation.Sum.unapply(<unapply-selector>) <unapply> ((a @ _), (b @ _)), pt = Permutation[?>: Nothing <: Any] 

Degli indizi come posso fare il compilatore accettare questo?

Grazie in anticipo!

Answer 1

Dopo averlo riprodotto per due giorni, ho finalmente trovato una soluzione che compila senza alcun preavviso e supera il mio test delle specifiche. Di seguito è un estratto compilabile del mio codice per mostrare ciò che è richiesto. Si noti, tuttavia, che il codice è un no-op perché ho lasciato fuori le parti di svolgere effettivamente le permutazioni:

/** 
* A generic mix-in for permutations. 
* <p> 
* The <code>+</code> operator (and the apply function) is defined as the 
* concatenation of this permutation and another permutation. 
* This operator is called the group operator because it forms an algebraic 
* group on the set of all moves. 
* Note that this group is not abelian, that is the group operator is not 
* commutative. 
* <p> 
* The <code>*</code> operator is the concatenation of a move with itself for 
* <code>n</code> times, where <code>n</code> is an integer. 
* This operator is called the scalar operator because the following subset(!) 
* of the axioms for an algebraic module apply to it: 
* <ul> 
* <li>the operation is associative, 
*  that is (a*x)*y = a*(x*y) 
*  for any move a and any integers x and y. 
* <li>the operation is a group homomorphism from integers to moves, 
*  that is a*(x+y) = a*x + a*y 
*  for any move a and any integers x and y. 
* <li>the operation has one as its neutral element, 
*  that is a*1 = m for any move a. 
* </ul> 
* 
* @param <P> The target type which represents the permutation resulting from 
*  mixing in this trait. 
* @see Move3Spec for details of the specification. 
*/ 
trait Permutation[P <: Permutation[P]] { this: P => 
    def identity: P 

    def *(that: Int): P 
    def +(that: P): P 
    def unary_- : P 

    final def -(that: P) = this + -that 
    final def unary_+ = this 

    def simplify = this 

    /** Succeeds iff `that` is another permutation with an equivalent sequence. */ 
    /*final*/ override def equals(that: Any): Boolean // = code omitted 
    /** Is consistent with equals. */ 
    /*final*/ override def hashCode: Int // = code omitted 

    // Lots of other stuff: The term string, the permutation sequence, the order etc. 
} 

object Permutation { 
    trait Identity[P <: Permutation[P]] extends Permutation[P] { this: P => 
    final override def identity = this 

    // Lots of other stuff. 
    } 

    trait Product[P <: Permutation[P]] extends Permutation[P] { this: P => 
    val perm: P 
    val scalar: Int 

    final override lazy val simplify = simplifyTop(perm.simplify * scalar) 

    // Lots of other stuff. 
    } 

    trait Sum[P <: Permutation[P]] extends Permutation[P] { this: P => 
    val perm1, perm2: P 

    final override lazy val simplify = simplifyTop(perm1.simplify + perm2.simplify) 

    // Lots of other stuff. 
    } 

    trait Inverse[P <: Permutation[P]] extends Permutation[P] { this: P => 
    val perm: P 

    final override lazy val simplify = simplifyTop(-perm.simplify) 

    // Lots of other stuff. 
    } 

    private def simplifyTop[P <: Permutation[P]](p: P): P = { 
    // This is the prelude required to make the extraction work. 
    type Pr = Product[_ <: P] 
    type Su = Sum[_ <: P] 
    type In = Inverse[_ <: P] 
    object Pr { def unapply(p: Pr) = Some(p.perm, p.scalar) } 
    object Su { def unapply(s: Su) = Some(s.perm1, s.perm2) } 
    object In { def unapply(i: In) = Some(i.perm) } 
    import Permutation.{simplifyTop => s} 

    // Finally, here comes the pattern matching and the transformation of the 
    // composed permutation term. 
    // See how expressive and concise the code is - this is where Scala really 
    // shines! 
    p match { 
     case Pr(Pr(a, x), y) => s(a*(x*y)) 
     case Su(Pr(a, x), Pr(b, y)) if a == b => s(a*(x + y)) 
     case Su(a, Su(b, c)) => s(s(a + b) + c) 
     case In(Pr(a, x)) => s(s(-a)*x) 
     case In(a) if a == a.identity => a.identity 
     // Lots of other rules 

     case _ => p 
    } 
    } ensuring (_ == p) 

    // Lots of other stuff 
} 

/** Here's a simple application of the mix-in. */ 
class Foo extends Permutation[Foo] { 
    import Foo._ 

    def identity: Foo = Identity 
    def *(that: Int): Foo = new Product(this, that) 
    def +(that: Foo): Foo = new Sum(this, that) 
    lazy val unary_- : Foo = new Inverse(this) 

    // Lots of other stuff 
} 

object Foo { 
    private object Identity 
    extends Foo with Permutation.Identity[Foo] 

    private class Product(val perm: Foo, val scalar: Int) 
    extends Foo with Permutation.Product[Foo] 

    private class Sum(val perm1: Foo, val perm2: Foo) 
    extends Foo with Permutation.Sum[Foo] 

    private class Inverse(val perm: Foo) 
    extends Foo with Permutation.Inverse[Foo] 

    // Lots of other stuff 
} 

Come si può vedere, la soluzione è quella di definire i tipi e gli oggetti di aspirazione che sono locali al Semplifica il metodo Top.

Ho anche incluso un piccolo esempio di come applicare un tale mix-in alla classe Foo. Come puoi vedere, Foo è poco più di una fabbrica per permutazioni composte di un suo tipo. Questo è un grande vantaggio se hai molte classi come questa che sono altrimenti non correlate.

<sproloquio>

Tuttavia, non posso resistere a dire che il sistema di tipi di Scala è follemente complessa! Sono un esperto sviluppatore di librerie Java e mi sento molto abile con Java Generics. Eppure mi ci sono voluti due giorni per capire le sei righe di codice con le tre definizioni di tipo e oggetto! Se questo non fosse per scopi educativi, avrei abbandonato l'approccio.

In questo momento, sono tentato di oracle che Scala NON sarà la prossima grande novità in termini di linguaggi di programmazione a causa di questa complessità. Se sei uno sviluppatore Java che si sente un po 'a disagio nei confronti dei generici Java ora (non io), allora odiesti il ​​sistema di tipi di Scala perché aggiunge invarianti, covarianti e controversi al concetto di generici Java, per usare un eufemismo.

Nel complesso, il sistema di tipo Scala sembra rivolgersi a più scienziati che agli sviluppatori. Da un punto di vista scientifico, è bello ragionare sulla sicurezza del tipo di un programma. Dal punto di vista degli sviluppatori, il tempo per capire questi dettagli è sprecato perché li tiene lontani dagli aspetti funzionali del programma.

Non importa, continuerò sicuramente con Scala. La combinazione di combinazioni di pattern, mix-in e funzioni di alto livello è troppo potente per mancare. Tuttavia, ritengo che Scala sarebbe un linguaggio molto più produttivo senza il suo sistema di tipi eccessivamente complesso.

</rant >