Sig: Inicio de los Tipos Sup: Análisis de Tipos Ant: Expresiones de Tipo en Err: Si hallas una errata ...

Construcción de las Declaraciones de Tipo con hnew

Una manera aún mas conveniente de representar una expresión de tipo es atraves de un grafo dirigido acíclico o DAG (Directed Acyclic Graph).

hnew

Parse::Eyapp provee el método Parse::Eyapp::Node->hnew el cual facilita la construcción de DAGs. El método hnew trabaja siguiendo lo que en programación funcional se denomina hashed consing. En Lisp la función de asignación de memoria es cons y la forma habitual de compartición es a través de una tabla hash. Hash consing es una técnica para compartir datos que son estructuralmente iguales. De esta forma se ahorra memoria. La técnica esta relacionada con - puede considerarse una aplicación concreta de - la técnica conocida con el nombre de memoization [4]. Si alguno de los subárboles (o el árbol) fueron creados anteriormente no serán creados de nuevo sino que hnew retorna una referencia al ya existente. Esto hace mas rápida la comprobación de tipos: en vez de comprobar que los dos árboles son estructuralmente equivalentes basta con comprobar que las referencias son iguales. Asi la comprobación de la equivalencia de tipos pasa a requerir tiempo constante.

Observe los siguientes comandos:

 DB<2> x $a = Parse::Eyapp::Node->hnew('F(X_3(A_3(A_5(INT)), CHAR, A_5(INT)),CHAR)')
0  F=HASH(0x85f6a20)
   'children' => ARRAY(0x85e92e4)
   |- 0  X_3=HASH(0x83f55fc)
   |     'children' => ARRAY(0x83f5608)
   |     |- 0  A_3=HASH(0x85a0488)
   |     |     'children' => ARRAY(0x859fad4)
   |     |        0  A_5=HASH(0x85e5d3c)
   |     |           'children' => ARRAY(0x83f4120)
   |     |              0  INT=HASH(0x83f5200)
   |     |                 'children' => ARRAY(0x852ccb4)
   |     |                      empty array
   |     |- 1  CHAR=HASH(0x8513564)
   |     |     'children' => ARRAY(0x852cad4)
   |     |          empty array
   |     `- 2  A_5=HASH(0x85e5d3c)
   |           -> REUSED_ADDRESS
   `- 1  CHAR=HASH(0x8513564)
         -> REUSED_ADDRESS
 DB<3> x $a->str
0  'F(X_3(A_3(A_5(INT)),CHAR,A_5(INT)),CHAR)'

La segunda aparición de A_5(INT) aparece etiquetada como reusada (tercer hijo de X_3). Lo mismo ocurre con la segunda aparición de CHAR.

hnew y el Manejador de Atributos

El valor asignado a los atributos no influye en la memoización de hnew: si los términos tienen la misma forma se devolverán los mismos árboles:

pl@nereida:~/src/perl/testing$ perl -MParse::Eyapp::Node -wde 0
main::(-e:1):   0
  DB<1> @x = Parse::Eyapp::Node->hnew('A(B,C(D))', sub { $_->{n} = $i++ for @_ })
  DB<2> @y = Parse::Eyapp::Node->hnew('C(D)', sub { $_->{t} = 10-$j++ for @_ })
  DB<3> x @x
0  A=HASH(0x850935c)
   'children' => ARRAY(0x8509530)
      0  B=HASH(0x85095a8)
         'children' => ARRAY(0x8326800)
              empty array
         'n' => 1
      1  C=HASH(0x8509410)
         'children' => ARRAY(0x85094dc)
            0  D=HASH(0x85094b8)
               'children' => ARRAY(0x85095f0)
                    empty array
               'n' => 3
               't' => 9
         'n' => 2
         't' => 10
   'n' => 0
1  B=HASH(0x85095a8)
   -> REUSED_ADDRESS
2  C=HASH(0x8509410)
   -> REUSED_ADDRESS
3  D=HASH(0x85094b8)
   -> REUSED_ADDRESS
  DB<4> x @y
0  C=HASH(0x8509410)
   'children' => ARRAY(0x85094dc)
      0  D=HASH(0x85094b8)
         'children' => ARRAY(0x85095f0)
              empty array
         'n' => 3
         't' => 9
   'n' => 2
   't' => 10
1  D=HASH(0x85094b8)
   -> REUSED_ADDRESS

La Función build_function_scope

Sigue el código de la función build_function_scope:

pl@nereida:~/doc/casiano/PLBOOK/PLBOOK/code/Simple-Types/lib/Simple$ \
                  sed -ne '/sub bu.*scop/,/^}/p' Types.eyp | cat -n
 1  sub build_function_scope {
 2    my ($funcDef, $returntype) = @_;
 3
 4    my $function_name = $funcDef->{function_name}[0];
 5    my @parameters = @{$funcDef->{parameters}};
 6    my $lst = $funcDef->{symboltable};
 7    my $numargs = scalar(@parameters);
 8
 9    #compute type
10    my $partype = "";
11    my @types = map { $lst->{$_}{type} } @parameters;
12    $partype .= join ",", @types if @types;
13
14    my $type = "F(X_$numargs($partype),$returntype)";
15
16    #insert it in the hash of types
17    $type{$type} = Parse::Eyapp::Node->hnew($type);
18    $funcDef->{type} = $type;
19    $funcDef->{t} = $type{$type};
20
21    #insert it in the global symbol table
22    die "Duplicated declaration of $function_name at line $funcDef->{function_name}[1]\n"
23      if exists($st{$function_name});
24    $st{$function_name}->{type} = $type;
25    $st{$function_name}->{line} = $funcDef->{function_name}[1];
26
27    return $funcDef;
28  }

Obsérvese que para acelerar los accesos al atributo tipo dotamos a los nodos del atributo t que permite acceder directamente al DAG representando el tipo.

Sig: Inicio de los Tipos Sup: Análisis de Tipos Ant: Expresiones de Tipo en Err: Si hallas una errata ...