Subsecciones

Un Lenguaje con Funciones Polimorfas

En esta sección introducimos un pequeño lenguaje que permite el polimorfismo paramétrico.

El Cuerpo

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.

La Cola

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.pm
Los 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:

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

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).

La directiva %strict

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  %% 

Ambiguedades

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.

Casiano Rodríguez León
2009-12-09