Movimiento, temporalidad y unicidad referencial

Movimiento

Desde su primer post, he seguido el blog de C++Next de Dave Abrahams (y otros). Empezaron con la conmoción de los conceptos, pero ahora se están dedicando a la optimización mediante movimiento en vez de copia.

La idea es simple: copiar es caro, movamos. La diferencia entre mover A a B y copiar A en B es que, al mover, podemos tocar A y robarle los recursos. Supongamos que el objeto A internamente apunta a otro objeto X. Si copio A en B, debo hacer una copia del ojeto interno X. Si muevo A a B, le quito el objeto X a A y se lo paso a B.

Originalmente:   A--->X,  B

Tras copia:   A--->X,  B---->Y    (Y es copia de X)

Tras movimiento:   A,  B---->X

El problema es que, tras mover A, queda en un estado que podíamos llamar de "desguazado" lo que lo hace, en principio, inusable. ¿Cómo saber si puedo mover desde A de forma que, aunque quede desguazado, no haya problemas?

Temporalidad

La idea vuelve a ser sencilla: los temporales pueden desguazarse porque no se van a usar de nuevo. Los temporales aparecen en expresiones como la siguiente.

c=a+b

El resultado de a+b se tiene que guardar en algún sitio para luego copiarlo a c. Es decir, se tiene que usar un temporal.

t:=a+b //Este := no copia, es más bien "pon el resultado en t"

c=t //Aquí sí que hay copia

El gran problema es que el operador ":=" que me he inventado es interno al compilador. De hecho, incluso el compilador no lo usará en muchos casos. Por ejemplo, cuando "a" y "b" sean valores que quepan en los registros de la máquina no le importará copiar porque sabe que es una operación barata. Si "a" y "b" son matrices, entonces sí que tendrá que reservar el espacio correspondiente a "t" para "poner el resultado en t".

Lo bueno que tienen los temporales es que son de usar y tirar. Así que lo de arriba podría hacerlo así.

t:=a+b

c=t //Mueve, desguazando "t" porque se va a destruir a continuación.

Esta es la aproximación al problema que usa C++. Introduce unas referencias a valores temporales (r-values) de manera que, si el programador usa estas referencias, sabe que se puede mover.

Unicidad referencial

Otro aspecto interesante de los valores temporales es que son únicos en el sentido de que no hay otra referencia a ellos. Sin embargo, ¿podremos generalizar esto? Estoy pensando en el sistema de propiedad de Bartosz Milewski y si hay alguna relación con el movimiento.

El sistema de BM es muy simple. Cada objeto tiene un dueño. Este dueño es responsable de alguna tarea o un valor que indique que no es necesaria la tarea. Ejemplos de tarea son la tarea de sincronizar los accesos entre distintas hebras y la tarea de borrar el objeto una vez se haya acabado de trabajar con él.

En el caso de la sincronización (que es de lo que se encarga BM) un dueño podrá ser: un objeto que sincronize (monitor), un valor que indique que ese objeto no necesita sincronización. De hecho, hay varios valores: porque el objeto es inmutable, porque el objeto es local a la hebra o porque el objeto está referenciado en un único sitio.

¿He dicho en un único sitio? Si el objeto está referenciado en un único sitio significa que

• No es necesaria la sincronización porque sólo una única hebra podrá modificarlo. Esto no es muy relevante para nuestra discusión aquí.
• Es fácil de controlar el desguace ya que sabemos que a partir del punto de movimiento el objeto no debe ser usado. Es decir, deberíamos requerir unicidad referencial para tomar el objeto como temporal y poder moverlo sin peligro.
• Tenemos que mover la referencia para que ésta siga siendo única (copiar la referencia haría que no fuera única) y por tanto hemos de tomar la referencia única como un temporal para esto.

Es muy curiosa la relación que hemos encontrado entre estas tres ideas. Todavía no tengo muy claras las cosas, tengo que seguir analizando qué pasa y por qué pasa, pero creo que todo esto es la punta de un gran iceberg.

Compatibilidad hacia atrás en lenguajes

Una cosa que nunca he entendido es la cerrazón de los diseñadores de lenguajes de programación en mantener la compatibilidad hacia atrás. Esto ha hecho que los lenguajes empiecen a tener complicaciones innecesarias y, como no se pueden quitar, cada vez habrá más complicaciones innecesarias.

¿Por qué no usar una opción en el compilador que regule la versión que queremos usar de una característica del lenguaje? Tenemos infinidad de opciones en el compilador: tipo de biblioteca en tiepo de ejecución, definición de símbolos, grado de optimización, juego de caracteres a usar, directorios de inclusión, etc. ¿Qué ocurriría si añadiésemos una más indicando la versión del código?

Quizás la única parte que no se debería tocar es la de las interfaces ya que tendrían que interoperar y eso implicaría mantener su versión, pero el resto es modificable. Así, los lenguajes irían refinándose. Los códigos antiguos (legacy) seguirían funcionando. ¿Qué problema hay que no atino a ver para que no se use esto?

Herencia y subtipo

Hoy en día en los lenguajes orientados a objetos es común hacer cosas del tipo

class A { int x; };

class B: public A { int y; };

Y decimos que la clase "B" hereda de la clase "A" y por lo tanto puedo usar "B" en cualquier sitio donde pueda usar "A". ¿Seguro?

Esto es erróneo y el ejemplo es claro arriba. La clase "A" ocupa el tamaño de un entero mientras que la clase "B"  ocupa el tamaño de dos por lo que es imposible usar la clase "B" en un espacio donde estaba la clase "A" porque no cabe.

Esto me lleva a pensar que subtipo (sustitución) y herencia (derivación de clases unas de las otras) no son completamente equivalentes. Muchos lenguajes lo ocultan mediante la prohibición de tener acceso directamente a las clases y sólo se pueden usar punteros o referencias a los objetos de las mismas (y el lenguaje se encarga de la gestión de memoria para que no podamos hacer cosas raras). Por ejemplo, Java y C# siguen este paradigma.

En otros lenguajes donde sí se puede acceder directamente a los objetos de las clases ocurren otros tipos de problemas indeseables como el slicing. Ahí están las grietas que separan subtipado de herencia. De hecho, la herencia ¡es una composición! La magia radica en que es una composición especial (usualmente la clase base es el primer miembro oculto de la clase hija) y los símbolos de la clase padre se importan subrepticiamente a la clase hija. De esta manera, cualquier uso de los miembros de la clase padre se corresponden con los mismos miembros de la clase hija. Esto es lo que da esa apariencia de sustitutibilidad.

ADL y clases parciales

Sobrecarga de operadores

La sobrecarga de operadores es una técnica útil y que incluso los que la despreciaban están, poco a poco, admitiendo que es necesaria. Esta técnica consiste en asociar operadores como +, *, <<>

a=b+c

puede ser una suma de enteros, de flotantes u otra cosa. Obviamente, si es una operación de suma de matrices o una concateniación de cadenas es muy útil, pero si es otra cosa poco intuitiva el programa pierde legibilidad. Estas son las ventajas e inconvenientes. Como generalmente se suele hacer buen uso de la sobrecarga de operadores, ha terminado siendo una técnica deseada.

En C++ las funciones asociadas a un operador "*" se llaman "operator *", así que la suma de arriba llamaría a una función con nombre "operator +". Según el tipo de sus argumentos, ya buscaría una sobrecarga adecuada de esta función.

Espacios de nombre

Por otra parte tenemos los espacios de nombres. Un espacio de nombre no es más que un nombre con nombres "dentro". Puedo tener el nombre "x" suelto (en el espacio de nombres global) o el nombre "x" dentro del nombre "y" (en el espacio de nombres "y"). En C++ al primero lo llamaríamos "x" y al segundo "y::x". Los espacios de nombres son importantes porque organizan y evitan las colisiones entre nombres. Un programador podría usar su "x" dentro de su espacio de nombres "fulanito" y otro programador su "x" dentro de su espacio de nombres "menganito". Estas "x" no se confundirían.

El C++ mete sus definiciones de la biblioteca estándar en el espacio de nombres "std". Muchos otros lenguajes hacen cosas similares con otros espacios de nombres como el "java" del Java (aunque en Java los espacios de nombre están relacionados con los módulos por lo que se llaman paquetes). Particularmente, los stream de entrada/salida de C++ están dentro de "std" por lo que tengo que escribir

std::cout << "Hola";

El problema es que este código no compilaría porque, al haber sobrecarga de operadores, el "<<" es una función "operator <<" pero ¡¡que está dentro del espacio de nombres "std"!! Es decir, que existe una incompatibilidad entre los espacios de nombre y los operadores. Lo de arriba debería escribirse algo como

std::operator<< (std::cout, "Hola")

lo cual es inaceptable. ¡Queremos operadores, no funciones!

ADL

La forma que tuvieron los señores de la comisión de estandarización del C++ (y en particular el señor Koenig) de resolver este problema fue la siguiente. Cuando veamos una función, buscamos su nombre no sólo en el espacio de nombres global sino que también en el espacio de nombres de sus argumentos.

De esta forma cuando escribo

std::cout << "Hola";

descubro que "operator <<" está sin definir en el espacio de nombres global. Entonces, veo que uno de sus argumentos (el de la izquierda) proviene del espacio de nombres "std". Así pues, voy a buscar dentro de "std" el "operator <<" y ¡allí está!

A este procedimiento se le llama Argument Dependent Lookup (ADL).

Más allá del ADL

Realmente, el ADL lo tienen todos los lenguajes de programación orientados a objeto de forma encubierta. Ocurre cuando usamos un miembro de una clase. Al escribir

class MiEntero { public: int suma(int b){......} };

MiEntero mi;

mi.suma(3)

el nombre "suma" es un nombre que está dentro del nombre "MiEntero". Aquí las clases se comportan como espacios de nombre y no tenemos ese problema de saber si "suma" es el "suma" que busco o no. ¡Claro que es ese! El que está en el objeto "mi" de la clase "MiEntero". No hay confusión.

Esta técnica se usó también en C++ de manera que se permite definir funciones miembro "operator *" dentro de las clases. El problema con el que nos encontramos es que sólo podemos utilizar el espacio de nombres del argumento de la izquierda.

mi.suma(3) //OK

3.suma(mi) //Error ("suma" que tome un "MiEntero" por la derecha no está definido en "int")

Parece una tontería, pero si usamos sobrecarga de operadores tenemos un problema de compilación de cuidado.

class MiEntero { public: int operator+(int b){......} };

MiEntero mi;

mi + 3 //OK

3 + mi //Error ("operator +" que tome un "MiEntero" por la derecha no está definido en "int")

Clases parciales

Es debido a la limitación de arriba que los señores del C++ eligieron extender ADL para todos los argumentos. Ni que decir tiene que en este caso se buscan muchos nombres y resulta difícil saber qué función se va a usar realmente.

Existe otra forma de solventar el problema de arriba y consiste en añadir métodos a clases (o tipos) ya definidas como "int". Esto es lo que se denomina tener clases parciales. Las clases parciales no son cerradas y siempre se les puede añadir algo más. Imaginemos una palabra clave "continue class" que nos permitiera hacer esto:

continue class int { public: MiEntero operator+(MiEntero x) {......}};

De forma que pudiéramos añadir un nuevo método en la clase. Esto es algo muy parecido a los "extension methods" de C# 3.0. Ahora cuando escriba

3 + mi //OK (Fue añadido dentro de "int" por la clase parcial)

Conclusiones

Los señores del C++ se equivocaron al introducir el ADL porque con él introdujeron una gran complicación tanto en los compiladores como a los programadores. Si hubieran usado clases parciales, incluso restringiendo las extensiones a sólo métodos, la búsqueda de nombres habría sido lineal y tersa. Sólo habría que buscar el nombre en un espacio de nombres (la clase).

Como descargo, hay que decir que en la época en la que se introdujo el ADL en C++ (en 1995) el uso de las clases parciales no era aún ni muy común ni muy conocido.

Finalmente, se puede simplificar aún más el sistema utilizando la técnica de Scala de no poner ni punto ni paréntesis a la hora de llamar a un método. En Scala es lo mismo escribir

a.b(c)

que escribir

a b c

Lo cual es muy útil si "b" es por ejemplo "+"

a.+(c)

a + c

Esto requiere algunos cambios drásticos en la gramática del lenguaje ya que han de permitirse identificadores simbólicos y hay que tratar los operadores prefijos con cuidado.

Covariancia y contravariancia (IV)

El problema de los punteros

Supongamos que tenemos tres tipos de punteros. Los punteros de sólo lectura, los de sólo escritura y los de escritura-lectura. Si apuntan a un tipo T, los llamaremos respectivamente PL(T), PE(T) y P(T).

Debe estar claro que si un puntero es de escritura-lectura entonces es de escritura y de lectura.

PL(T) <: P(T)

PE(T) <: P(T)

Ahora bien, lo que no está tan claro es si tengo un tipo y un subtipo (como los muebles M y las sillas S) si ocurrirá que

PL(S) <: PL(M) ???

PE(S) <: PE(M) ???

P(S) <: P(M) ???

PL(S) <: P(M) ???

Y todas las dieciocho combinaciones.

Para dilucidar si los punteros son covariantes o contravariantes vamos a inventarnos unas operaciones de lectura y de escritura sobre ellos. Estas operaciones serán:

• altura(): Devuelve la altura de un mueble.
• patas(): Devuelve el número de patas de un mueble.
• crea_silla(int, int): Crea una silla con la altura y el número de patas dados
• crea_mueble(int): Crea un mueble con la altura dada.

Ahora, usaremos los punteros plm de tipo PL(M), pls de tipo PL(S), pem de tipo PE(M) y pes de tipo PE(S) y veremos cuándo se pueden o no sustituir unos por otros.

pls.patas() //OK, mismo tipo

plm.patas() //Mal, los muebles no tienen patas

plm.altura() // OK, mismo tipo

pls.altura() //Bien, las sillas tienen altura

pes.crea_silla(110, 4) // OK, mismo tipo

pem.crea_silla(110, 4) // Bien, creamos un mueble que es una silla

pem.crea_mueble(150) // OK, mismo tipo

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

En definitiva, hemos podido usar PL(S) donde había un PL(M) y hemos podido usar un PE(M) donde había un PE(S) de forma que:

S <: M

PL(S) <: PL(M)

PE(S) :> PE(M)

Los punteros de lectura son covariantes y los de escritura son contravariantes. Obviamente, como los punteros de escritura-lectura tienen que compartir ambas propiedades, llegamos a la conclusión que o bien S=M o bien no hay forma de relacionar P(S) con P(M). Esto se puede ver en el libro de Pierce, en el apartado 15.5.

La conversión de const char** a char** 

Este curioso comportamiento tiene sus repercusiones en lenguajes como el C++ y particularmente en las conversionse de cualificación CV. En estas conversiones se prohibe la conversión de "un puntero a un puntero a un dato constante" a "un puntero a un puntero a un dato modificable". ¿Por qué? Veamos los tipos:

const char**  char**

P(PL(T))      P(P(T))

Como el constructor de tipos más exterior es el puntero de escritura-lectura, no podemos decir nada de su relación con el otro puntero.

Esto suele extrañar a la gente porque si sólo fueran punteros de un nivel tendríamos

const char*    char*

PL(T)       <: P(T)

Y la conversión sería posible. Cualquier programador de C++ sabe que podemos pasar un puntero normal donde se requiere un puntero constante.

En la siguiente parte veremos la relación del slicing con los punteros de escritura, cómo usar el conocimiento sobre la variancia en los constructores de tipo y la forma que tienen algunos lenguajes de trabajar con la variancia de tipos.