Las reglas para la comprobación de tipos para funciones polimorfas
difiere del de las funciones ordinarias en varios aspectos.
Consideremos de nuevo el árbol para la llamada
first(first(q))
decorado con los tipos que deberan
ser inferidos:
1 first : list(ALPHA) -> ALPHA; 2 q : list(list(int)) 3 { 4 first(first(q)) 5 } |
EXPS( FUNCTIONCALL[int]( ID[first:F(LIST(INT),INT)], FUNCTIONCALL[list(int)]( ID[first:F(LIST(LIST(INT)) LIST(INT))], ID[q:LIST(LIST(INT))] ) ) # FUNCTIONCALL ) # EXPS |
Del ejercicio de hacer la inferencia para el ejemplo sacamos algunas consecuencias:
En la expresión first(first(q))
la instancia interna de la función
first
tiene el tipo
list(list(int)) -> list(int)
mientras que la externa tiene el tipo
list(int) -> int
Se sigue que cada ocurrencia de first
tiene su propia visión de la variable ALPHA
que se instancia (se unifica)
a un valor distinto. Por tanto, en cada ocurrencia de first
,
reemplazaremos la variable de tipo ALPHA
por una variable fresca ALPHA
. Así habrán
variables frescas ALPHA
para los nodos interno y externo de las llamadas
FUNCTIONCALL(ID[first], ...)
Puesto que ahora las expresiones de tipo contienen variables debemos extender
la noción de equivalencia de tipos. Supongamos que una función f
de tipo ALPHA -> ALPHA
es aplicada a una expresión exp
de tipo
list(GAMMA)
. Es necesario unificar ambas expresiones.
En este caso obtendriámos que ALPHA = list(GAMMA)
y que f
es una función del tipo list(GAMMA) -> list(GAMMA)
Es necesario disponer de un mecanismo para grabar el resultado
de la unificación de dos árboles/dags. Si la unificación de dos expresiones de tipo
s
y s'
resulta en la variable ALPHA
representando al tipo t
entonces ALPHA
deberá seguir representando al tipo t
conforme avancemos en la comprobación de tipos.
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho$ \ cat -n Trans.trg 1 /***************** Polymorphic Type Checking *****************/ 2 /* 3 eyapp -m Aho::Polymorphism Polymorphism.eyp; 4 treereg -m Aho::Polymorphism Trans.trg 5 */ 6 7 { 8 use Aho::Unify qw(:all); 9 } 10 11 functioncall: FUNCTIONCALL($f, $arg) 12 => { 13 my ($name, $line) = @{$f->{attr}}; 14 15 my $p = new_var(); 16 17 my $q = Parse::Eyapp::Node->hexpand("F", $arg->{t}, $p, \&selfrep); 18 19 if (unify($f->{t}, $q)) { 20 print "Unified\n"; 21 print "Now type of ".$f->str." is ".strunifiedtree($q)."\n"; 22 } 23 else { 24 die "Type error at $line\n"; 25 } 26 27 $FUNCTIONCALL->{t} = representative($p); 28 print "Type of ".$FUNCTIONCALL->str." is ".$FUNCTIONCALL->{t}->str."\n"; 29 30 return 1; 31 } 32 33 tuple: ARGS($x, $y) 34 => { 35 $ARGS->{t} = Parse::Eyapp::Node->hexpand("X", $x->{t}, $y->{t}, \&selfrep); 36 } 37 38 id: ID 39 => { 40 my ($name, $line) = @{$ID->{attr}}; 41 our %st; 42 my $ts = $st{$name}->{ts}; 43 $ID->{t} = fresh($ts); 44 }
ts
).
A partir de el se construye el DAG que representa el tipo llamando a
la funcion fresh
de Aho::Unify
. Esta función antes de
llamar a hnew
''refresca'' todas las apariciones de variables de tipo.
Una variable como ALPHA
será sustituida por ALPHA#number
.
46 sub fresh { 47 my $ts = shift; 48 my $regexp = shift; 49 $regexp = 'Parse::Eyapp::Node::TYPEVAR::[\w:]+' unless defined($regexp); 50 51 $ts =~ s/($regexp)/$1$count/g; 52 $count++; 53 my @t = Parse::Eyapp::Node->hnew($ts); 54 representative($_, $_) for @t; 55 return $t[0]; 56 }
El algoritmo de unificación decora los nodos de los DAGs que estan siendo unificados
con un atributo (atributo cuyo nombre viene dado por la variable $set
)
que es una referencia al representante de la clase de equivalencia a la que pertenece
el nodo. Cada clase tiene un único representante al que denominaremos
representante canónico. El representante de un nodo
puede obtenerse/modificarse usando la función representative
proveída por
Aho::Unify
.
83 sub representative { 84 my $t = shift; 85 86 if (@_) { 87 $t->{$set} = shift; 88 return $t; 89 } 90 $t = $t->{$set} while defined($t->{set}) && ($t != $t->{$set}); 91 die "Representative ($set) not defined!".Dumper($t) unless defined($t->{set}); 92 return $t; 93 }
Al comienzo del algoritmo cada nodo pertenece a una clase en la que el único nodo es el mismo. Conforme se avanza en el proceso de unificación las clases van aumentando de tamaño.
tuple
correspondiente a expresiones de la forma
x, y
en los argumentos es construir el tipo producto cartesiano
de los tipos de x
e y
.
33 tuple: ARGS($x, $y) 34 => { 35 $ARGS->{t} = Parse::Eyapp::Node->hexpand("X", $x->{t}, $y->{t}, \&selfrep); 36 }
El método hexpand de Parse::Eyapp::Node
permite construir un DAG
compatible con los construidos con hnew
ya que utiliza la misma cache
de memoización. El método admite como último argumento un manejador-decorador
de atributos que funciona de manera parecida a como lo hace el correspondiente
argumento en new
y hnew
. El manejador es llamado por
hexpand
con el nodo que acaba de ser creado como único argumento.
Parse::Eyapp:Node->new('X')
y expandiendo el nodo con hijos $x
y $y
.
Sin embargo, este método no conservaría la propiedad de DAG de los grafos de tipo.
¿Porqué?
Parse::Eyapp:Node->hnew('X')
y luego se expandiera con hijos $x
y $y
?
hexpand
podríamos formar un DAG compatible con hnew
para
el árbol X($x->{t}->str, $y->{t}->str)
?
La función selfrep
- también en Aho::Unify
-
tiene por función iniciar el representante del nodo al propio nodo. De hecho
su código es:
95 sub selfrep { 96 representative($_[0], $_[0]) 97 };
functioncall
para las llamadas FUNCTIONCALL($f, $arg)
parte de que el tipo mas general asociado con esta clase de nodo debe tener la forma
F($arg->{t},$p)
donde $p
es una nueva variable libre.
13 my ($name, $line) = @{$f->{attr}}; 14 15 my $p = new_var(); 16 17 my $q = Parse::Eyapp::Node->hexpand("F", $arg->{t}, $p, \&selfrep);
La función new_var
(en Aho::Unify
) proporciona una nueva variable:
58 # The name space Parse::Eyapp::Node::TYPEVAR:: is reserved for tree variables 59 # Parse::Eyapp::Node::TYPEVAR::_#number is reserved for generated variables 60 sub new_var { 61 my $p = Parse::Eyapp::Node->hnew("Parse::Eyapp::Node::TYPEVAR::_$count"); 62 representative($p, $p); 63 $count++; 64 return $p; 65 }
Las variables
proveídas tiene la forma Parse::Eyapp::Node::TYPEVAR::_#number
.
La llamada al método hexpand
se encarga de crear el DAG asociado con
F($arg->{t},$p)
.
El último argumento de la llamada a hexpand
es el manejador de atributos. Pasamos \&selfrep
para
indicar que se trata de un árbol no unificado.
Acto seguido se pasa a unificar el tipo
de $f
y el tipo mas general F($arg->{t},$p)
.
19 if (unify($f->{t}, $q)) { 20 print "Unified\n"; 21 print "Now type of ".$f->str." is ".strunifiedtree($q)."\n"; 22 } 23 else { 24 die "Type error at line $line\n"; 25 }
Si la unificación tiene éxito el tipo asociado con la imagen (con el valor retornado) debe ser
el tipo unificado de la nueva variable $p
que es accedido por medio de la función
representative
.
27 $FUNCTIONCALL->{t} = representative($p);
strunifiedtree
.
La función strunifiedtree
(en Aho::Unify
) recorre
el árbol de representantes construyendo el término que lo describe:
125 sub strunifiedtree { 126 my $self = shift; 127 128 my $rep = representative($self); 129 my @children = $rep->children; 130 my $desc = ref($rep); 131 return $desc unless @children; 132 133 my @d; 134 for (@children) { 135 push @d, strunifiedtree($_); 136 } 137 local $" = ","; 138 $desc .= "(@d)"; 139 return $desc; 140 }
La ejecución del compilador con el programa que hemos usado como ejemplo muestra el proceso de inferencia. Empecemos repasando la estructura del árbol y la representación de las declaraciones:
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ \ usepoly.pl prueba01.ply 2 first type: F(LIST(Parse::Eyapp::Node::TYPEVAR::ALPHA),Parse::Eyapp::Node::TYPEVAR::ALPHA) q type: LIST(LIST(INT)) first : list(ALPHA) -> ALPHA; q : list(list(int)) { first(first(q)) } .... Tree: EXPS( FUNCTIONCALL( ID[first], FUNCTIONCALL( ID[first], ID[q] ) ) # FUNCTIONCALL ) # EXPS
En primer lugar se calculan los tipos para la llamada interna:
Unifying F(LIST(TYPEVAR::ALPHA1),TYPEVAR::ALPHA1) and F(LIST(LIST(INT)),TYPEVAR::_3) Unifying LIST(TYPEVAR::ALPHA1) and LIST(LIST(INT)) Unifying TYPEVAR::ALPHA1 and LIST(INT) TYPEVAR::ALPHA1 = LIST(INT) Unifying LIST(INT) and TYPEVAR::_3 TYPEVAR::_3 = LIST(INT) Unified Now type of ID[first] is F(LIST(LIST(INT)),LIST(INT)) Type of FUNCTIONCALL(ID[first],ID[q]) is LIST(INT)Asi se ha inferido que el tipo del argumento de la llamada externa a
first
es
LIST(INT)
. La inferencia para el tipo del
nodo externo FUNCTIONCALL
prosigue con una nueva variable fresca ALPHA0
:
Unifying F(LIST(TYPEVAR::ALPHA0),TYPEVAR::ALPHA0) and F(LIST(INT),TYPEVAR::_4) Unifying LIST(TYPEVAR::ALPHA0) and LIST(INT) Unifying TYPEVAR::ALPHA0 and INT TYPEVAR::ALPHA0 = INT Unifying INT and TYPEVAR::_4 TYPEVAR::_4 = INT Unified Now type of ID[first] is F(LIST(INT),INT) Type of FUNCTIONCALL(ID[first],FUNCTIONCALL(ID[first],ID[q])) is INTPor último el programa nos muestra el árbol sintáctico abstracto con los tipos inferidos:
Tree: EXPS( FUNCTIONCALL[INT]( ID[first:F(LIST(INT),INT)], FUNCTIONCALL[LIST(INT)]( ID[first:F(LIST(LIST(INT)),LIST(INT))], ID[q:LIST(LIST(INT))] ) ) # FUNCTIONCALL ) # EXPS
La expresión g(g)
en el siguiente programa C muestra la aplicación de una función a
ella misma. La declaración de la línea 7 define la imagen de g
como entera pero
el tipo de los argumentos queda sin especificar.
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ \ cat -n macqueen.c pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ cat -n macqueen.c 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int n = 5; 5 6 int f(int g()) 7 { 8 int m; 9 10 m = n; 11 if (m == 0) return 1; 12 else { 13 n = n - 1; 14 return m * g(g); 15 } 16 } 17 18 main() { 19 printf("%d factorial is %d\n", n, f(f)); 20 }
Al ser compilado con gcc
el programa no produce errores ni mensajes de advertencia:
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ gcc macqueen.c pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ a.out 0 factorial is 120El error que se aprecia en la salida se corrige cuando cambiamos el orden de los argumentos en la llamada a
printf
:
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ \ sed -ne '/printf/p' macqueen2.c; gcc macqueen2.c ; a.out printf("%d is the factorial of %d\n", f(f), n); 120 is the factorial of 5
¿Cuál es la especificación completa del tipo de g
?
Este ejemplo esta basado en un programa Algol dado por Ledgard en 1971 [12]. Aparece como ejercicio 6.31 en el libro de Aho, Sethi y Ullman [9].
El siguiente programa en nuestro pequeño lenguaje polimorfo modela el problema de determinar el tipo de esta función:
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ \ usepoly.pl exercise6_31.ply 2 m : int; times : int * int -> int; g : ALPHA { times(m, g(g)) }El árbol y la tabla de símbolos quedan montados después de la primera fase:
Tree: EXPS( FUNCTIONCALL( ID[times], ARGS( ID[m], FUNCTIONCALL( ID[g], ID[g] ) ) # ARGS ) # FUNCTIONCALL ) # EXPS g type: Parse::Eyapp::Node::TYPEVAR::ALPHA m type: INT times type: F(X(INT,INT),INT)
En primer lugar se procede a la unificación de la llamada interna
FUNCTIONCALL(ID[g],ID[g])
:
Unifying TYPEVAR::ALPHA2 and F(TYPEVAR::ALPHA3,TYPEVAR::_4) TYPEVAR::ALPHA2 = F(TYPEVAR::ALPHA3,TYPEVAR::_4) Unified Now type of ID[g] is F(Parse::Eyapp::Node::TYPEVAR::ALPHA3,Parse::Eyapp::Node::TYPEVAR::_4) Type of FUNCTIONCALL(ID[g],ID[g]) is TYPEVAR::_4Después se pasa a la unificación de la llamada externa
FUNCTIONCALL(ID[times],ARGS(ID[m], FUNCTIONCALL(...)))
:
Unifying F(X(INT,INT),INT) and F(X(INT,TYPEVAR::_4),TYPEVAR::_5) Unifying X(INT,INT) and X(INT,TYPEVAR::_4) Unifying INT and TYPEVAR::_4 TYPEVAR::_4 = INT Unifying INT and TYPEVAR::_5 TYPEVAR::_5 = INT Unified Now type of ID[times] is F(X(INT,INT),INT) Type of FUNCTIONCALL(ID[times],ARGS(ID[m],FUNCTIONCALL(ID[g],ID[g]))) is INT
Vemos que el tipo de g
es F(Parse::Eyapp::Node::TYPEVAR::ALPHA3,Parse::Eyapp::Node::TYPEVAR::_4)
y que TYPEVAR::_4 = INT
. Asi pues el tipo ALPHA
de g
es
F(ALPHA,INT)
. Por tanto tenemos
que el tipo inferido para g
es un tipo recursivo:
typedef int ALPHA(ALPHA);El programa nos muestra el árbol anotado con los tipos inferidos:
Tree: EXPS( FUNCTIONCALL[INT]( ID[times:F(X(INT,INT),INT)], ARGS[X(INT,INT)]( ID[m:INT], FUNCTIONCALL[INT]( ID[g:F(Parse::Eyapp::Node::TYPEVAR::ALPHA3,INT)], ID[g:Parse::Eyapp::Node::TYPEVAR::ALPHA3] ) ) # ARGS ) # FUNCTIONCALL ) # EXPS
La decoración ocurre de abajo-arriba y la inferencia sólo se hace en los nodos de llamada. Sin embargo, Se puede producir la inferencia del tipo de una variable después de que su nodo haya sido visitado, como muestra el ejemplo:
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ \ usepoly.pl reverseinference.ply 2 first : int -> int; q : ALPHA { first(q) } Unifying F(INT,INT) and F(TYPEVAR::ALPHA1,TYPEVAR::_2) Unifying INT and TYPEVAR::ALPHA1 TYPEVAR::ALPHA1 = INT Unifying INT and TYPEVAR::_2 TYPEVAR::_2 = INT Unified Now type of ID[first] is F(INT,INT) Type of FUNCTIONCALL(ID[first],ID[q]) is INT Tree: EXPS( FUNCTIONCALL[INT]( ID[first:F(INT,INT)], ID[q:INT] ) ) # EXPS first type: F(INT,INT) q type: Parse::Eyapp::Node::TYPEVAR::ALPHA
No obstante, parece razonable que el tipo de una variable que no sea una función debería ser fijo. Dado que las ventajas del polimorfismo se aprecian fundamentalmente en las funciones podemos añadir a nuestro lenguaje reglas que prohiban el polimorfismo de variables que no sean funciones.