Progettazione del sistema di numerazione con firma non firmata

Question

Sto provando a progettare un sistema di numerazione attorno a interi non firmati e interi con segno. Entrambi questi tipi hanno un valore underlying che rappresenta il numero nel sistema numerico di Scala. Ecco la gerarchia di tipi che ho finora.

sealed trait Number { 
    def + (num : Number) : Number = ??? 
    def - (num : Number) : Number = ??? 
    def * (num : Number) : Number = ??? 
} 

sealed trait SignedNumber extends Number 

sealed trait UnsignedNumber extends Number 

sealed trait UInt32 extends UnsignedNumber { 
    def underlying : Long 
} 

sealed trait UInt64 extends UnsignedNumber { 
    def underlying : BigInt 
} 

sealed trait Int32 extends SignedNumber { 
    def underlying : Int 
} 

sealed trait Int64 extends SignedNumber { 
    def underlying : Long 
} 

vorrei definire underlying nel tratto Number in modo che il compilatore può imporre che underlying è definito in tutti i bambini. Tuttavia, i tipi di underlying variano per ogni tratto: voglio mantenere il tipo più piccolo possibile per ogni tipo. Ad esempio, uno UInt32 può essere memorizzato come uno long in Scala, mentre uno UInt64 deve essere memorizzato come BigInt.

Qual è il modo più efficace per farlo?

Answer 1

È possibile dichiarare un type nel tratto principale e sovrascriverlo nelle sottotitoli.

sealed trait Number { 
    type A 
    def underlying: A 
    def + (num : Number) : Number = ??? 
    def - (num : Number) : Number = ??? 
    def * (num : Number) : Number = ??? 
} 

sealed trait SignedNumber extends Number 

sealed trait UnsignedNumber extends Number 

sealed trait UInt32 extends UnsignedNumber { 
    override type A = Long 
} 

sealed trait UInt64 extends UnsignedNumber { 
    override type A = BigInt 
} 

sealed trait Int32 extends SignedNumber { 
    override type A = Int 
} 

sealed trait Int64 extends SignedNumber { 
    override type A = Long 
} 

Un esempio solo per mostrare l'uso del tipo dipendente dal percorso nel caso in cui non è chiaro:

def getUnderlying(x: Number): x.A = x.underlying 

Per ottenere i tipi di ritorno corretta, penso che potrebbe essere necessario un altro type.

sealed trait Number { 
    type A 
    type B 
    def underlying: A 
    def +(that: B): B 
} 

sealed trait UInt32 extends Number { x => 
    override type A = Long 
    override type B = UInt32 
    override def +(y: B): B = new UInt32 { 
    // todo - naive implementation, doesn't check overflow 
    override val underlying = x.underlying + y.underlying 
    } 
} 

def main(args: Array[String]) { 
    print((
    new UInt32 { def underlying = 3 } + 
    new UInt32 { def underlying = 4 } 
).underlying) 
} 

Answer 2

Il modo più efficace è memorizzare i numeri primitivi (Int Double ...) come tipo non elaborato.

La mancanza di segno deve essere memorizzata in un parametro Type, che verrà cancellato in fase di esecuzione. Scala lo fa quando lasci che semplici classi di casi estendano AnyVal.

Il codice seguente lo fa per Ints, Longs, Doubles e Bigint. Ho aggiunto alcune classificazioni in adition a unsigned e rinominato unsigned to positive.

Inoltre, poiché la classificazione viene eseguita interamente nel sistema di tipi, non è necessario fornire tutte le funzioni + e * sovraccaricate. Ciò consente di risparmiare spazio quando si tenta di implementarlo per tutti i tipi di numeri.

C'è ancora un po 'da fare durante il collegamento tra i vari tipi. Domani darò un'occhiata a questo.

I tratti Classificazione:

sealed trait SignTag{ 
    type SubTag <:SignTag; 
    type AddTag <:SignTag; 
    type MultTag<:SignTag; 
} 

sealed trait Signed extends SignTag{ 
    type SubTag=Signed; 
    type AddTag=Signed; 
    type MultTag=Signed; 
} 

sealed trait Positive extends SignTag{ 
    type SubTag=Signed; 
    type AddTag=Negative; 
    type MultTag=Negative; 
} 

sealed trait Negative extends SignTag{ 
    type SubTag=Signed; 
    type AddTag=Negative; 
    type MultTag=Positive; 
} 

sealed trait Zero extends SignTag{ 
    type SubTag=Zero; 
    type AddTag=Zero; 
    type MultTag=Zero; 
} 

Int involucro:

object SInt { 
    @inline 
    implicit def toSigned[T <: SignTag](int:SInt[T]):SInt[Signed]=int.asInstanceOf[SInt[Signed]]; 

    @inline implicit def toLong[T <: SignTag](int:SInt[T]):SLong[T]=SLong(int.underlying); 
    @inline implicit def toDouble[T <: SignTag](int:SInt[T]):SDouble[T]=SDouble(int.underlying); 
    @inline implicit def toBig[T <: SignTag](int:SInt[T]):SBigInt[T]=SBigInt(int.underlying); 
} 

case class SInt[T <: SignTag](val underlying:Int) extends AnyVal{ 
    def -(second: SInt[_ <: T#InTag]):SInt[T#SubTag]=new SInt[T#SubTag](underlying - second.underlying); 

    def +(second: SInt[_ <: T#InTag]):SInt[T#AddTag]=new SInt[T#AddTag](underlying + second.underlying); 

    def *(second: SInt[_ <: T#InTag]):SInt[T#MultTag]=new SInt[T#MultTag](underlying * second.underlying); 

    def assertSameType(other:SInt[T])={}; 
} 

lungo avvolgitore:

object SLong { 

    @inline 
    implicit def toSigned[T <: SignTag](int:SLong[T]):SLong[Signed]=int.asInstanceOf[SLong[Signed]]; 

    @inline implicit def toDouble[T <: SignTag](int:SLong[T]):SDouble[T]=SDouble(int.underlying); 
    @inline implicit def toBig[T <: SignTag](int:SLong[T]):SBigInt[T]=SBigInt(int.underlying); 
} 

case class SLong[T <: SignTag](val underlying:Long) extends AnyVal{ 
    def -(second: SLong[_ <: T#InTag]):SLong[T#SubTag]=new SLong[T#SubTag](underlying - second.underlying); 

    def +(second: SLong[_ <: T#InTag]):SLong[T#AddTag]=new SLong[T#AddTag](underlying + second.underlying); 

    def *(second: SLong[_ <: T#InTag]):SLong[T#MultTag]=new SLong[T#MultTag](underlying * second.underlying); 

    def assertSameType(other:SLong[T])={}; 
} 

doppio involucro:

object SDouble { 
    @inline 
    implicit def toSigned[T <: SignTag](int:SDouble[T]):SDouble[Signed]=int.asInstanceOf[SDouble[Signed]]; 
} 

case class SDouble[T <: SignTag](val underlying:Double) extends AnyVal{ 
    def -(second: SDouble[_ <: T#InTag]):SDouble[T#SubTag]=new SDouble[T#SubTag](underlying - second.underlying); 

    def +(second: SDouble[_ <: T#InTag]):SDouble[T#AddTag]=new SDouble[T#AddTag](underlying + second.underlying); 

    def *(second: SDouble[_ <: T#InTag]):SDouble[T#MultTag]=new SDouble[T#MultTag](underlying * second.underlying); 

    def assertSameType(other:SDouble[T])={}; 
} 

BigInt avvolgitore:

object SBigInt { 
    @inline 
    implicit def toSigned[T <: SignTag](int:SLong[T]):SLong[Signed]=int.asInstanceOf[SLong[Signed]]; 

    @inline 
    implicit def toDouble[T <: SignTag](int:SBigInt[T]):SDouble[T]=SDouble(int.underlying.toDouble); 
} 

case class SBigInt[T <: SignTag](val underlying:BigInt) extends AnyVal{ 
    def -(second: SBigInt[_ <: T#InTag]):SBigInt[T#SubTag]=new SBigInt[T#SubTag](underlying - second.underlying); 

    def +(second: SBigInt[_ <: T#InTag]):SBigInt[T#AddTag]=new SBigInt[T#AddTag](underlying + second.underlying); 

    def *(second: SBigInt[_ <: T#InTag]):SBigInt[T#MultTag]=new SBigInt[T#MultTag](underlying * second.underlying); 

    def assertSameType(other:SBigInt[T])={}; 
} 

prova la sintassi:

class CompileToTest { 
    val signed=new SInt[Signed](5); 
    val positive=new SInt[Positive](5); 
    val negative=new SInt[Negative](-5); 
    val zero=new SInt[Zero](0); 

    (signed + signed).assertSameType(signed); 
    (negative + signed).assertSameType(signed); 
    (positive - positive).assertSameType(signed); 
    (positive * negative).assertSameType(signed); 
    (zero + zero).assertSameType(zero); 

    val positiveDouble=SDouble[Positive](4.4) 
    val negativeDouble=SDouble[Negative](-4.4) 
    val signedDouble=SDouble[Signed](-4.4) 

    (positiveDouble * negativeDouble).assertSameType(signedDouble); 
} 

Ps. In realtà non ho guardato il bytecode, ma i documenti suggeriscono che questo dovrebbe essere inline e compilato in base alle primitive.

Adoro questa lingua.