Patrones Árbol y Transformaciones Árbol

En la fase de optimización presentada en la sección 33.11 transformabamos el programa en su representación intermedia, como un AAA decorado, para obtener otro AAA decorado.

Una transformación de un programa puede ser descrita como un conjunto de reglas de transformación o esquema de traducción árbol sobre el árbol abstracto que representa el programa.

Antes de seguir, es conveniente que repase los conceptos en la sección 33.9.1 sobre lenguajes y gramáticas árbol.

En su forma mas sencilla, estas reglas de transformación vienen definidas por ternas $(p, e, action)$, donde la primera componente de la terna $p$ es un patrón árbol que dice que árboles deben ser seleccionados. La segunda componente $e$ dice cómo debe transformarse el árbol que casa con el patrón $p$. La acción $action$ indica como deben computarse los atributos del árbol transformado a partir de los atributos del árbol que casa con el patrón $p$. Una forma de representar este esquema sería:

$p \Longrightarrow e$ { action }

Por ejemplo:

$PLUS(NUM_1, NUM_2) \Longrightarrow NUM_3$ { $NUM_3{VAL} = $NUM_1{VAL} + $NUM_2{VAL} }

cuyo significado es que dondequiera que haya un nódo del AAA que case con el patrón de entrada $PLUS(NUM, NUM)$ deberá sustituirse el subárbol $PLUS(NUM, NUM)$ por el subárbol $NUM$. Al igual que en los esquemas de traducción, enumeramos las apariciones de los símbolos, para distinguirlos en la parte semántica. La acción indica como deben recomputarse los atributos para el nuevo árbol: El atributo VAL del árbol resultante es la suma de los atributos VAL de los operandos en el árbol que ha casado. La transformación se repite hasta que se produce la normalización del árbol.

Las reglas de ``casamiento'' de árboles pueden ser mas complejas, haciendo alusión a propiedades de los atributos, por ejemplo

$ASSIGN(LEFTVALUE, x) and$ { notlive($LEFTVALUE{VAL}) } $\Longrightarrow NIL$

indica que se pueden eliminar aquellos árboles de tipo asignación en los cuáles la variable asociada con el nodo $LEFTVALUE$ no se usa posteriormente.

Otros ejemplos con variables $S_1$ y $S_2$:

$IFELSE(NUM, S_1, S_2)$ and { $NUM{VAL} != 0 } $\Longrightarrow S_1$
$IFELSE(NUM, S_1, S_2)$ and { $NUM{VAL} == 0 } $\Longrightarrow S_2$

Observe que en el patrón de entrada $ASSIGN(LEFTVALUE, x)$ aparece un ``comodín'': la variable-árbol $x$, que hace que el árbol patrón $ASSIGN(LEFTVALUE, x)$ case con cualquier árbol de asignación, independientemente de la forma que tenga su subárbol derecho.

Las siguientes definiciones formalizan una aproximación simplificada al significado de los conceptos patrones árbol y casamiento de árboles.

Definición 33.12.1   Sea $(\Sigma, \rho)$ un alfabeto con función de aridad y un conjunto (puede ser infinito) de variables $V =\{ x_1, x_2, \ldots \}$. Las variables tienen aridad cero:

$\rho(x) = 0 \forall x \in V$.

Un elemento de $B(V \cup \Sigma)$ se denomina patrón sobre $\Sigma$.

Definición 33.12.2   Se dice que un patrón es un patrón lineal si ninguna variable se repite.

Definición 33.12.3   Se dice que un patrón es de tipo $(x_1, \ldots x_k)$ si las variables que aparecen en el patrón leidas de izquierda a derecha en el árbol son $x_1, \ldots x_k$.

Ejemplo 33.12.1   Sea $\Sigma = \{A, CONS, NIL \}$ con $\rho(A) = \rho(NIL) = 0, \rho(CONS) = 2$ y sea $V = \{ x \}$. Los siguientes árboles son ejemplos de patrones sobre $\Sigma$:

{ $x, CONS(A, x), CONS(A, CONS(x, NIL)), \ldots \}$

El patrón $CONS(x, CONS(x, NIL))$ es un ejemplo de patrón no lineal. La idea es que un patrón lineal como éste ``fuerza'' a que los árboles $t$ que casen con el patrón deben tener iguales los dos correspondientes subárboles $t/1$ y $t/2\ldotp1$ situados en las posiciones de las variables ^33.1

Ejercicio 33.12.1   Dado la gramática árbol:

$S \rightarrow S_1(a, S, b)$
$S \rightarrow S_2(NIL)$

la cuál genera los árboles concretos para la gramática

$S \rightarrow aSb$ $\vert$ $\epsilon$

¿Es $S_1(a, X(NIL), b)$ un patrón árbol sobre el conjunto de variables $\{X, Y\}$? ¿Lo es $S_1(X, Y, a)$? ¿Es $S_1(X, Y, Y)$ un patrón árbol?

Ejemplo 33.12.2   Ejemplos de patrones para el AAA definido en el ejemplo 33.9.2 para el lenguaje Tutu son:

$x, y, PLUS(x, y), ASSIGN(x, TIMES(y,ID)), PRINT(y) \ldots$

considerando el conjunto de variables $V = \{ x, y \}$. El patrón $ASSIGN(x, TIMES(y,ID))$ es del tipo $(x, y)$.

Definición 33.12.4   Una sustitución es una aplicación $\theta$ que asigna variables a patrones $\theta: V \rightarrow B(V \cup \Sigma)$.

Tal función puede ser naturalmente extendida de las variables a los árboles: los nodos (hoja) etiquetados con dichas variables son sustituidos por los correspondientes subárboles.

$\theta : B(V \cup \Sigma) \rightarrow B(V \cup \Sigma)$

$t \theta = \left \{ \begin{array}{ll} x \theta & \mbox{si $t = x \in V$}\\ ... ...ldots, t_k \theta) & \mbox{si $t = a(t_1, \ldots, t_k)$} \end{array} \right.$

Obsérvese que, al revés de lo que es costumbre, la aplicación de la sustitución $\theta$ al patrón se escribe por detrás: $t \theta$.

También se escribe $t \theta = t\{x_1/x_1 \theta, \ldots x_k/x_k \theta\}$ si las variables que aparecen en $t$ de izquierda a derecha son $x_1, \ldots x_k$.

Ejemplo 33.12.3   Si aplicamos la sustitución $\theta = \{x/A, y/CONS(A, NIL)\}$ al patrón $CONS(x, y)$ obtenemos el árbol $CONS(A, CONS(A,NIL))$. En efecto:

$CONS(x, y)\theta = CONS(x\theta, y\theta) = CONS(A, CONS(A, NIL))$

Ejemplo 33.12.4   Si aplicamos la sustitución $\theta = \{x/PLUS(NUM, x), y/TIMES(ID, NUM)\}$ al patrón $PLUS(x, y)$ obtenemos el árbol $PLUS(PLUS(NUM,x), TIMES(ID, NUM))$:

$PLUS(x, y)\theta = PLUS(x\theta, y\theta) = PLUS(PLUS(NUM,x), TIMES(ID, NUM))$

Definición 33.12.5   Se dice que un patrón $\tau \in B(V \cup \Sigma)$ con variables $x_1, \ldots x_k$ casa con un árbol $t \in B(\Sigma)$ si existe una sustitución de $\tau$ que produce $t$, esto es, si existen $t_1, \ldots t_k \in B(\Sigma)$ tales que $t = \tau \{x_1/t_1, \ldots x_k/t_k\}$. También se dice que $\tau$ casa con la sustitución $\{x_1/t_1, \ldots x_k/t_k\}$.

Ejemplo 33.12.5   El patrón $\tau = CONS(x, NIL)$ casa con el árbol $t = CONS(CONS(A,NIL),NIL)$ y con el subárbol $t \ldotp 1$. Las respectivas sustituciones son $t\{x/CONS(A,NIL)\}$ y $t \ldotp 1 \{x/A\}$.

$t = \tau \{x/CONS(A,NIL)\}$
$t \ldotp 1 = \tau \{x/A\}$

Ejercicio 33.12.2   Sea $\tau = PLUS(x, y)$ y $t = TIMES(PLUS(NUM, NUM), TIMES(ID, ID))$. Calcule los subárboles $t'$ de $t$ y las sustituciones $\{x/t_1, y/t_2\}$ que hacen que $\tau$ case con $t'$.

Por ejemplo es obvio que para el árbol raíz $t/\epsilon$ no existe sustitución posible:

$t = TIMES(PLUS(NUM, NUM), TIMES(ID, ID)) = \tau\{x/t_1, y/t_2\} = PLUS(x, y)\{x/t_1, y/t_2\}$

ya que un término con raíz $TIMES$ nunca podrá ser igual a un término con raíz $PLUS$.

El problema aquí es equivalente al de las expresiones regulares en el caso de los lenguajes lineales. En aquellos, los autómatas finitos nos proveen con un mecanismo para reconocer si una determinada cadena ``casa''' o no con la expresión regular. Existe un concepto análogo, el de autómata árbol que resuelve el problema del ``casamiento'' de patrones árbol. Al igual que el concepto de autómata permite la construcción de software para la búsqueda de cadenas y su posterior modificación, el concepto de autómata árbol permite la construcción de software para la búsqueda de los subárboles que casan con un patrón árbol dado.

Estamos ahora en condiciones de plantear una segunda aproximación al problema de la optimización independiente de la máquina utilizando una subrutina que busque por aquellos árboles que queremos optimizar (en el caso del plegado los árboles de tipo operación) y los transforme adecuadamente.

La función match_and_transform_list recibe una lista de árboles los cuales recorre sometiéndolos a las transformaciones especificadas. La llamada para producir el plegado sería:

  Tree::Transform::match_and_transform_list(
    NODES => $tree->{STS}, # lista de sentencias
    PATTERN => sub {
       $_[0]->is_operation and $_[0]->LEFT->isa("NUM") 
       and $_[0]->RIGHT->isa("NUM") 
    },
    ACTION => sub { 
      $_[0] = Machine::Independent::Optimization::reduce_children($_[0]) 
    }
  );

Además de la lista de nodos le pasamos como argumentos una referencia a la subrutina encargada de reconocer los patrónes árbol (clave PATTERN) y una referencia a la subrutina que describe la acción que se ejecutará (clave ACTION) sobre el árbol que ha casado. Ambas subrutinas asumen que el primer argumento que se les pasa es la referencia a la raíz del árbol que está siendo explorado.

Los métodos isa, can y VERSION son proporcionados por una clase especial denominada clase UNIVERSAL, de la cual implícitamente hereda toda clase. El método isa nos permite saber si una clase hereda de otra.

La subrutina match_and_transform_list recibe los argumentos y da valores por defecto a los mismos en el caso de que no hayan sido establecidos. Finalmente, llama a match_and_transform sobre cada uno de los nodos ``sentencia'' del programa.

sub match_and_transform_list {
  my %arg = @_;
  my @statements = @{$arg{NODES}} or 
   Error::fatal("Internal error. match_and_transform_list ".
   "espera una lista anónima de nodos");
  local $pattern = ($arg{PATTERN} or sub { 1 });
  local @pattern_args = @{$arg{PATTERN_ARGS}} if defined $arg{PATTERN_ARGS};
  local $action = ($arg{ACTION} or sub { print ref($_[0]),"\n" }); 
  local @action_args = @{$arg{ACTION_ARGS}} if defined $arg{ACTION_ARGS};

  for (@statements) {
    match_and_transform($_);
  }
}

La subrutina match_and_transform utiliza el método can para comprobar que el nodo actual dispone de un método para calcular la lista con los hijos del nodo. Una vez transformados los subárboles del nodo actual procede a comprobar que el nodo casa con el patrón y si es el caso le aplica la acción definida:

package Tree::Transform;

our $pattern;
our @pattern_args;
our $action;
our @action_args;
our @statements;

sub match_and_transform {
  my $node = $_[0] or Error::fatal("Error interno. match_and_transform necesita un nodo");
  Error::fatal("Error interno. El nodo de la clase",ref($node),
               " no dispone de método 'children'") unless $node->can("children");
  
  my %children = $node->children;

  for my $k (keys %children) {
    $node->{$k} = match_and_transform($children{$k});
  }

  if ($pattern->($node, @pattern_args)) {
    $action->( $node, @action_args); 
  }
  return $node;
}

Recordemos el esquema de herencia que presentamos en la sección anterior. Las clases Leaf y Binary proveen versiones del método children. Teníamos:

package Node;

sub is_operation {
  my $node = shift;

  return ref($node) =~ /^(TIMES)|(PLUS)$/;
}

package Leaf; # hoja del AAA
our @ISA = ("Node");
sub children {
  return ();
}

package Binary;
our @ISA = ("Node");
sub children {
  my $self = shift;

  return (LEFT => $self->{LEFT}, RIGHT => $self->{RIGHT});
}

Los objetos de la clase Leaf tienen acceso al método is_operation.

Las clases PLUS y TIMES heredan de la clase BINARY:

package PLUS;
our @ISA = ("Binary");

sub operator {
  my $self = shift;

  $_[0]+$_[1];
}

....

package TIMES;
our @ISA = ("Binary");

sub operator {
  my $self = shift;

  $_[0]*$_[1];
}

....

La subrutina reduce_children introducida en la sección 33.11 es la encargada de crear el nuevo nodo con el resultado de operar los hijos izquierdo y derecho:

1 sub reduce_children {
2   my ($node) = @_;
3 
4   my $value = $node->operator($node->LEFT->VAL, $node->RIGHT->VAL);
5   NUM->new(VAL => $value, TYPE => $PL::Tutu::int_type);
6 }

En la línea 4 se usa el método operator asociado con un nodo operación.

Práctica: Casando y Transformando Árboles

Complete su proyecto para el compilador de Tutu completando las subrutinas match_and_transform tal y como se explicó en la sección 33.12.

Ademas del plegado de constantes use las nuevas subrutinas para aplicar simultáneamente las siguientes transformaciones algebraicas:

$PLUS(NUM, x)$	$\wedge$ { $NUM{VAL} == 0 }	$\Longrightarrow x$
$PLUS(x, NUM)$	$\wedge$ { $NUM{VAL} == 0 }	$\Longrightarrow x$
$TIMES(NUM, x)$	$\wedge$ { $NUM{VAL} == 1 }	$\Longrightarrow x$
$TIMES(x, NUM)$	$\wedge$ { $NUM{VAL} == 1 }	$\Longrightarrow x$

1. Dado un programa como

   int a; a = a * 4 * 5;
   

   ¿Será plegado el 4 * 5? Sin embargo si que se pliega si el programa es de la forma:

   int a; a = a * (4 * 5);
   

   No intente en esta práctica que programas como el primero o como 4*a*5*b sean plegados. Para lograrlo sería necesario introducir transformaciones adicionales y esto no se requiere en esta práctica.
2. ¿Existe un orden óptimo en el que ejecutar las transformaciones?
3. Ponga un ejemplo en el que sea beneficioso ejecutar el plegado primero.
4. Ponga otro ejemplo en el que sea beneficioso ejecutar el plegado después.
5. ¿Es necesario aplicar las transformaciones reiteradamente?
6. ¿Cuál es la condición de parada?
7. Como es habitual la pregunta 6 tiene una respuesta TIMTOWTDI: una posibilidad la da el módulo Data::Compare el cual puede obtenerse desde CPAN y que permite comparar estructuras de datos, pero existe una solución mas sencilla. ¿Cuál?