En esta sección introducimos un pequeño lenguaje que permite el polimorfismo paramétrico.
Los programas generados por esta gramática consisten en secuencias de declaraciones seguidas de secuencias de las expresiones cuyos tipos vamos a inferir. Por ejemplo:
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho/script$ \
cat -n prueba01.ply
1 first : list(ALPHA) -> ALPHA;
2 q : list(list(int))
3 {
4 first(first(q))
5 }
Las declaraciones admiten variables de tipo. Las variables de tipo son identificadores
formados por letras en mayúsculas. Los identificadores estan formados por minúsculas.
La gramática que define el lenguaje es:
p: d <+ ';'> '{' e <%name EXPS + ';'> '}'
;
d: id ':' t
;
t: INT
| STRING
| TYPEVAR
| LIST '(' t ')'
| t '*' t
| t '->' t
| '(' t ')'
;
e: id '(' optargs ')'
| id
;
optargs:
/* empty */
| args
;
args: e
| args ',' e
;
id: ID
;
Para las expresiones nos limitamos a construir el árbol usando bypass automático. Las expresiones se reducen al uso de identificadores y llamadas a función:
47 p:
48 d <+ ';'> '{' e <%name EXPS + ';'>.expressions '}'
49 {
50 $expressions->{symboltable} = \%st;
51 $expressions
52 }
53 ;
54
55 d:
56 $id ':' $t
57 {
58 $st{$id->key} = { ts => $t };
59 }
60 ;
61
62 t:
63 INT
64 {
65 'INT';
66 }
67 | STRING
68 {
69 'STRING';
70 }
71 | TYPEVAR
72 {
73 "Parse::Eyapp::Node::TYPEVAR::$_[1]->[0]"
74 }
75 | LIST '(' $t ')'
76 {
77 "LIST($t)"
78 }
79 | t.left '*' t.right
80 {
81 "X($left,$right)"
82 }
83 | t.domain '->' t.image
84 {
85 "F($domain,$image)"
86 }
87 | '(' $t ')'
88 {
89 $t;
90 }
91 ;
92
93 e:
94 %name FUNCTIONCALL
95 id '(' optargs ')'
96 | id
97 ;
98
99 optargs:
100 /* empty */
101 | args
102 ;
103
104 args:
105 e
106 | %name ARGS
107 args ',' e
108 ;
109
110 id:
111 %name ID
112 ID
113 ;
Para cada declaración se construye un término que describe el tipo y se almacena en
la tabla de símbolos %st. Por ejemplo, las expresiones de tipo construidas
a partir de las declaraciones del programa anterior son:
first type: F(LIST(Parse::Eyapp::Node::TYPEVAR::ALPHA),Parse::Eyapp::Node::TYPEVAR::ALPHA) q type: LIST(LIST(INT))
Usaremos el espacio de nombres Parse::Eyapp::Node::TYPEVAR para
representar los nodos variable.
El árbol resultante para el programa anterior es:
1 first : list(ALPHA) -> ALPHA;
2 q : list(list(int))
3 {
4 first(first(q))
5 }
|
EXPS(
FUNCTIONCALL(
ID[first],
FUNCTIONCALL(
ID[first],
ID[q]
)
) # FUNCTIONCALL
) # EXPS
|
Obsérvese que no hay asignación ni operaciones binarias en el lenguaje (aunque estas últimas
pueden ser emuladas mediante funciones add, times, etc.). Por ello la comprobación
de tipos se centra en las llamadas a función.
En la cola figuran la subrutina de análisis léxico y la
de tratamiento de errores. Son una adaptación de las presentadas
en las secciones anteriores para Simple::Types.
El análisis de tipo para este lenguaje con variables de tipo
lo haremos usando expresiones regulares árbol (fichero Trans.trg)
asi como un módulo que implanta el algoritmo de unificación
y que hemos llamado Aho::Unify.
En concreto tenemos los siguientes ficheros en la
librería:
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho$ ls -l total 112 -rw-r--r-- 1 pl users 639 2008-01-07 13:01 Makefile -rw-r--r-- 1 pl users 3837 2008-01-11 16:47 Polymorphism.eyp -rw-r--r-- 1 pl users 945 2008-01-11 12:20 Trans.trg -rw-r--r-- 1 pl users 3212 2008-01-11 12:57 Unify.pmLos ficheros son compilados con los comandos:
treereg -nonumbers -m Aho::Polymorphism Trans.trg eyapp -m Aho::Polymorphism Polymorphism.eyp
La llamada $t = $self->YYParse de la
línea 192 realiza el análisis sintáctico y el análisis de ámbito.
El análisis
de ámbito es trivial ya que hay un sólo ámbito.
115 %%
... ...................................
186 sub compile {
187 my($self)=shift;
188
189 my ($t);
190
191 $self->YYData->{INPUT} = $_[0];
192
193 $t = $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error,
194 #yydebug => 0x1F
195 );
196
197 my @typecheck = (
198 our $functioncall,
199 our $tuple,
200 our $id,
201 );
202
203 Aho::Unify->set(
204 key => 'set',
205 isvar => sub { $_[0] =~ /^Parse::Eyapp::Node::TYPEVAR/ },
206 samebasic => sub {
207 my ($s, $t) = @_;
208
209 return (((ref($s) eq 'INT') || (ref($s) eq'STRING')) && (ref($s) eq ref($t)));
210 },
211 debug => $debug,
212 );
213
214 $t->bud(@typecheck);
215
216 return $t;
217 }
218
219 sub ID::key {
220 return $_[0]->{attr}[0]
221 }
222
223 insert_method('ID', 'info', \&ID::key);
Las líneas de la 197 a la 212 se encargan de la inferencia de tipos. Volveremos sobre ellas mas adelante. Por ahora observe que hay tres transformaciones:
$functioncall se encarga de la inferencia y comprobación para las llamadas,
$tuple del cálculo de tipos para las expresiones args, exp
que aparecen en los argumentos. Estas expresiones dan lugar
a árboles de la forma ARGS($x, $y). Por ejemplo, en el siguiente programa:
f : ALPHA * BETA * GAMMA -> ALPHA;
q : int;
r : int;
s : list(int)
{
f(q,r,s)
}
El árbol construido para la expresión es:
EXPS(FUNCTIONCALL(ID[f],ARGS(ARGS(ID[q],ID[r]),ID[s])))mientras que los tipos son:
r type: INT
q type: INT
s type: LIST(INT)
f type: F(
X(
X(
Parse::Eyapp::Node::TYPEVAR::ALPHA,
Parse::Eyapp::Node::TYPEVAR::BETA
),
Parse::Eyapp::Node::TYPEVAR::GAMMA
),
Parse::Eyapp::Node::TYPEVAR::ALPHA
)
Trans.trg es $id,
la cual se encarga del cálculo de los tipos para los nodos ID.
Como las anteriores, esta transformación decorará el nodo con un atributo t
denotando el DAG que describe al tipo. En este caso se tomará el tipo
de la tabla de símbolos
y se crearán nuevas instancias de las variables de tipo si las hubiera.
El comportamiento del algoritmo de unificación depende de un conjunto
de parámetros que es inicializado mediante la llamada a la función
set del módulo Aho::Unify.
La llamada $t->bud(@typecheck) aplica las transformaciones
en un recorrido abajo-arriba infiriendo los tipos y decorando los nodos.
La cabecera muestra la carga de los módulos
para la unificación (Aho::Unify) y para la
inferencia y comprobación de tipos (Aho::Trans).
Por defecto Parse::Eyapp decide que aquellos símbolos que no figuran
en la parte izquierda de una regla son terminales (tokens).
La directiva %strict utilizada en la línea 7 fuerza la declaración
de todos los terminales. Cuando se usa la directiva %strict
el compilador eyapp emite un mensaje
de advertencia si detecta algún símbolo que no figura
en la parte izquierda de alguna regla y no ha sido explícitamente
declarado como terminal (mediante directivas como
%token, %left, etc.).
pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Aho-Polymorphism/lib/Aho$ \
cat -n Polymorphism.eyp
1 /*
2 File: Aho/Polymorphism.eyp
3 To build it, Do make or:
4 eyapp -m Aho::Polymorphism Polymorphism.eyp;
5 treereg -m Aho::Polymorphism Trans.trg
6 */
7 %strict
8 %{
9 use strict;
10 use Carp;
11 use warnings;
12 use Aho::Unify qw(:all);
13 use Aho::Trans;
14 use Data::Dumper;
15 our $VERSION = "0.3";
16
17 my $debug = 1;
18 my %reserved = (
19 int => "INT",
20 string => "STRING",
21 list => "LIST",
22 );
23
24 my %lexeme = (
25 ',' => "COMMA",
26 ';' => "SEMICOLON",
27 ':' => "COLON",
28 '*' => "TIMES",
29 '(' => "LEFTPARENTHESIS",
30 ')' => "RIGHTPARENTHESIS",
31 '{' => "LEFTCURLY",
32 '}' => "RIGHTCURLY",
33 '->' => "FUNCTION",
34 );
35 my ($tokenbegin, $tokenend) = (1, 1);
36 our %st; # Symbol table
37 %}
38
39 %tree bypass
40
41 %token ID TYPEVAR STRING INT LIST
42
43 %right '->'
44 %left '*'
45
46 %%
La regla de producción t -> t '*' t es obviamente ambigua. La directiva
%left '*' permite deshacer la ambiguedad. Lo mismo ocurre con la regla
para las funciones t -> t '->' t. En este caso nos decidimos por una asociatividad
a derechas, de modo que una declaración como int -> int -> int es interpretado como una función
que recibe enteros y devuelve funciones. Una tercera fuente de ambiguedad se
produce en expresiones como:
int * int -> int
que puede ser interpretado como int * (int -> int) o bien
(int * int) -> int. Al darle mayor prioridad al * nos decidimos
por la segunda interpretación.