miércoles, 14 de octubre de 2009

Covariancia y contravariancia (V)

Funciones virtuales

En el último post de esta serie dije que la siguiente operación no se podía realizar.

pes.crea_mueble(150) // Mal, no sabemos las patas que tiene la silla

Esto puede soslayarse si el programador asume la responsabilidad de actualizar correctamente el estado de la silla entera cuando se modifica únicamente la parte mueble de la misma. Por ejemplo, en el caso anterior el programador puede usar una versión especial de crea_mueble() para las sillas. En esta versión especial puede optar por, por ejemplo, usar cuatro patas por defecto.

Ahora bien, ¿cómo sabe que, aunque sea un puntero a mueble, realmente es una silla? Se usa lo que se llaman funciones virtuales. Una función virtual es aquella cuyo despacho se realiza en función del tipo de objeto apuntado y no en función del tipo de puntero. De esta forma, aunque tengamos un puntero a mueble, si actuamos sobre una silla, se usará la función especial de la silla.

Con esta técnica, y bajo responsabilidad del programador, los punteros de lectura/escritura terminan siendo como los punteros de lectura: covariantes.

Paso por valor

En otro post dije que la herencia no era lo mismo que el subtipado y di un motivo en concreto: el tamaño que ocupan los objetos en memoria. Si usamos punteros (o referencias) a objetos podemos usar la técnica de arriba, pero si nuestro lenguaje es de paso por valor, tenemos un problema.

Supongamos que una función tiene el tipo f: Unit -> A. Esta función no toma ningún argumento (el tipo unit es algo así como el tipo void en C/C++ en este caso) y devuelve un objeto de tipo A. Claro está que podría devolver un subtipo B de A.

Por lo mencionado antes, los lenguajes orientados a objetos no usan realmente la relación de subtipo. Usan la relación de herencia. Eso significa que B puede ser de mayor tamaño que A y aquí surge el problema: ¿cómo sabe la función llamante si f va a devolver un A o algún otro tipo heredado como B? Porque si va a devolver un B va a tener que reservar más memoria que para un A. En caso contrario tendríamos un desbordamiento de buffer (buffer overflow).

Una solución sería pensar que la función tiene que devolver exactamente un A. Esto la haría invariante y que no podríamos cambiar cualquier aparición de f: Unit -> A por otra función g: Unit -> B.

Por otra parte, sabemos que con los punteros (y gracias a las funciones virtuales) no tenemos ese problema. Es decir, que sí podemos cambiar cualquier aparición de f2: Unit -> PA por otra función g2: Unit -> PB.

¡Pero es que es lógico! Pasamos los punteros por valor y el objeto apuntado por referencia. Los punteros son todos del mismo tamaño por lo que no hay problemas de desbordamiento de buffer. Esto es justo lo que hace el C++: permitir la covariancia de funciones sólo para los punteros (y referencias).

Marcando la variancia en los constructores de tipo

La solución de C++ está bastante encorsetada. Sólo permite covariancia para unos tipos predefindos. ¿No podríamos mejorar esto?

Si el programador supiese que, cuando usa un constructor de tipos, el resultado es otro tipo que

  1. Va a tener estados consistentes y no va a tener slicing (funciones virtuales)
  2. No va a provocar desbordamiento de buffer (mismo tamaño si es paso por valor)
  3. No va a tener problemas semánticos (el programador es responsable y sabe lo que se hace).

Entonces podría asegurar que sus constructores de tipos van a ser covariantes o contravariantes y podría anotarlo en el código. Por ejemplo, un contenedor de sólo lectura es covariante.

Esto es lo que hace el lenguaje de programación Scala y las nuevas versiones del C#. Un ejemplo obtenido de aquí es:

//+A significa que es covariante en A

class Stack[+A] { 

//B >: A significa que A es subtipo de B (A<:B)

def push[B >: A](elem: B): Stack[B] = new Stack[B] {
override def top: B = elem
override def pop: Stack[B] = Stack.this
override def toString() = elem.toString() + " " +
Stack.this.toString()
}

def top: A = error("no element on stack")

def pop: Stack[A] = error("no element on stack")

override def toString() = ""
}

object VariancesTest extends Application {

var s: Stack[Any] = new Stack().push("hello");
s = s.push(new Object())
s = s.push(7)
Console.println(s)

}

Comentarios finales

Con esto doy por acabada la serie de variancias. Seguramente surgirá algún tema más que comentar en el futuro, por lo que no tendré ninguna pereza en reabrirla para nuevos posts. 

0 comentarios:

Publicar un comentario en la entrada