Usando a Tipagem de Scala para Validar Parâmetros

Bom, primeiramente, muita coisa aconteceu por isso a falta de postagens, mas espero que daqui pra frente seja possível postar mais coisas interessantes.

Esses dias, estou tentando encapsular um código Java em um código Scala, basicamente, um código de matrizes, multiplicação de matrizes, etc, e será este o exemplo que usarei neste post. Para os que não lembram de matrizes, as operações sobre matrizes devem seguir uma determinada regra, por exemplo, adição de matrizes só podem ser efetuadas quando as duas matrizes possuem mesmo número de elementos:

class Matrix(protected val list: List[List[Double]] {
  def +(other: Matrix) = new Matrix(list zip other.list map { case(me, other) =>
    me zip other map { case(e1, e2) => e1 + e2 }
  })
}

Para os que não conhecem tão bem Scala, o código a seguir soma uma matriz com a outra chamando o método zip, que basicamente, de posse de dois objetos que possam ser iterados (tipo um List), combinam seus elementos:

List(1, 2, 3) zip List(4, 5, 6)
=> List( (1, 4), (2, 5), (3, 6) )
List(List(1, 2)) zip List(List(3, 4))
=> List( (List(1, 2), List(3, 4)) )

O “case”, no map (e no foreach, e em qualquer closure) separa os dois elementos. Seria possível separar também com map { e => e._1, e._2 } mas fica um pouco mais feio o código.

Legal, o código acima funciona mas… ele permite somar matrizes de dimensões diferentes. Claramente, isso não é desejado. Podemos fazer o método nos retornar um erro quando tentarmos somar matrizes de dimensões diferentes:

  def +(other: Matrix) = {
    require(list.size == other.list.size, "Number of rows must be the same")
    require(list(0).size == other.list(0).size, "Number of cols must be the same")

    new Matrix(list zip other.list map { case(me, other) =>
      me zip other map { case(e1, e2) => e1 + e2 }
    })
  }

Ou podemos usar a tipagem para isto.

Usar a tipagem para este tipo de coisa parece meio absurdo, e de fato o é. Talvez esse post deveria estar em “coisas que você nunca quis fazer com Scala”, mas como demonstra o poder da tipagem de Scala, é possível que em outra ocasião ele seja útil. Em primeiro lugar, vamos pensar em “abstração”: o computador nos abstrai um monte de coisas, como já sabemos. O byte “3”, por exemplo, é abstraído para a sequência de 00000011, e no caso das letras, temos situações semelhantes.

Porém, o que queremos fazer aqui é representar o número de colunas e o número de linhas usando TIPAGEM. Claramente, a tipagem não nos reservou nada parecido. O que podemos fazer é:

trait _0
trait _1
trait _2

class Matrix[R, C] {
  def +(other: Matrix[R, C]) = ...//Corpo do método removido para simplificar o código.
}

Mas claramente isso é absurdo: vamos criar um tipo novo pra cada número que inventarmos? E se tivermos, sei lá, matrizes de 1000×1000? Vamos digitar “trait _?” 1000 vezes? Então, me baseando na idéia do blog Apocalisp, é possível fazer algo bem interessante: fixar um número (digamos, o 0) e os outros são definidos a partir de operações a partir deste número:

trait Nat //Números naturais
trait _0 extends Nat //O número 0
trait Suc[A <: Nat] extends Nat //Números sucessores de 0

class Matrix[R <: Nat, C <: Nat] {
  def +(other: Matrix[R, C]) = ...
}

Bem melhor. Podemos definir agora números naturais a partir da tipagem. Mas, ainda precisamos criar as matrizes. Isto pode ser complicado, até porque alguém pode “trapacear” e criar uma matriz 2×2 e, na tipagem, informar que ela é 4×4. Mas tem como resolver, e para isto, deixamos nosso construtor privado e passamos a responsabilidade de criar a matriz para um object:

class Matrix[R <: Nat, C <: Nat] private(protected val list: List[List[Double]]) {
  //...
}

object Matrix {
  def fromNumber(number: Double) = new Matrix[Suc[_0], Suc[_0]](List(List(number)))
}

Então, agora temos um construtor que constrói matrizes 1×1. Mas isso não nos interessa, queremos construir matrizes arbitrárias. Para isto, vejamos: as seguintes maneiras são válidas de se construir uma lista:

List(1, 2, 3)
1 :: List(2, 3)
1 :: 2 :: 3 :: List()
1 :: 2 :: 3 :: Nil

Podemos usar essa notação: concatenar uma matrix de n colunas por 1 linha com a matriz atual. Só que, só podemos concatenar uma matriz com outra desde que ambas possuam o mesmo número de colunas. Para concatenar uma List[List[Double]] com outra, basta somar ambas: List(List(1, 2, 3)) ++ List(List(4, 5, 6)) == List(List(1, 2, 3), List(4, 5, 6)).

class Matrix[R <: Nat, C <: Nat] private(protected val list: List[List[Double]]) {
  def ^::(other: Matrix[Suc[_0], C]) = {
    val newData = other.list :: list
    new Matrix[Suc[R], C](newData)
  }
}

A assinatura do método diz: “eu aceito um parâmetro, que é uma Matrix, e que possui número de linhas (R) igual a 1 (sucessor de 0), e que possui o número de colunas (C) igual a mim“. Como o método insere uma nova linha no começo, o parâmetro (other) vem antes da lista atual. O retorno do método é uma nova Matrix, cujo número de linhas é um a mais do que o atual (Suc[R]), e o número de colunas é inalterado.

Já para o método de inserir uma nova coluna no começo, o código é mais complicadinho, mas a ênfase deste post é na tipagem: a tipagem do método é exatamente igual ao acima, porém com os parâmetros (R e C) trocados:

  def ::(other: Matrix[R, Succ[_0]]) = {
    val newData = list.zip(other.list).map { case (myRow, otherRow) =>
      otherRow ++ myRow
    }

    new Matrix[R, Succ[C]](newData)
  }

Agora, temos a tipagem de Scala garantindo que as matrizes possuem o mesmo número de linhas e colunas, e podemos garantir erros em tempo de compilação e não de execução. Por conveniência, o código inteiro está abaixo:

sealed trait Nat
sealed trait _0 extends Nat
sealed trait Suc[N <: Nat] extends Nat

class Matrix[R <: Nat, C <: Nat] private(protected val list: List[List[Double]]) {
  def ^::(other: Matrix[Suc[_0], C]) = {
    val newData = other.list ++ list
    new Matrix[Suc[R], C](newData)
  }                          
                             
  def ::(other: Matrix[R, Suc[_0]]) = {
    val newData = list.zip(other.list).map { case (myRow, otherRow) =>
      otherRow ++ myRow
    }

    new Matrix[R, Suc[C]](newData)
  }

  def +(other: Matrix[R, C]) = new Matrix[R, C](list zip other.list map { case(me, other) =>
    me zip other map { case(e1, e2) => e1 + e2 }
  })

  override def toString = "Matrix:\n" + list.map { _.mkString(",\t") }.mkString("\n")
}

object Matrix {
  def fromNumber(number: Double) = new Matrix[Suc[_0], Suc[_0]](List(List(number)))
}

val matrix1x2 = Matrix.fromNumber(1) :: Matrix.fromNumber(2)
val matrix2x1 = Matrix.fromNumber(2) ^:: Matrix.fromNumber(3)

println(matrix1x2 + matrix1x2) //Retorna uma nova matriz 1x2, [2.0,    4.0]
println(matrix2x1 + matrix1x2) //ERRO de compilação!

Interessante, não? Porém, infelizmente, para este tipo de coisa funcionar, é necessário que a classe seja invariante. Logo, qualquer assinatura de método deve levar em consideração o tamanho das matrizes… logo, é impossível assinar um método que aceita uma matriz de número arbitrário de linhas e colunas. Pior ainda, a criação de matrizes torna-se MUITO mais complicada:

//Criação da matrix:
//| 1     2 |
//| 3     4 |

Matrix.fromNumber(1) :: Matrix.fromNumber(2) ^:: (Matrix.fromNumber(3) :: Matrix.fromNumber(4))

Logo, para este exemplo, talvez usar a tipagem não seja uma boa idéia. Mas talvez, usar de forma limitada (caso a matriz possua apenas uma linha, converta-a implicitamente para vetor) não seja uma má idéia. O código acima apenas demonstra o poder da tipagem de Scala, que foi provada ser Turing-Complete. Mais exemplos, e um código mostrando como fazer operações aritméticas somente com a tipagem, podem ser vistos no blog Apocalisp.

Advertisements
This entry was posted in Scala and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s