Datos recursivos

Hasta la semana pasada, lo recursivo eran las funciones: una función que se llama a sí misma, sobre un problema más pequeño. Hoy lo recursivo serán los datos: un tipo cuyos valores contienen, adentro, otros valores del mismo tipo. Van a ver que las dos ideas calzan casi solas. Si los datos tienen forma de árbol, la función que los recorre tiene esa misma forma.

Con esta semana empieza la última parte del curso. En tres semanas van a escribir un intérprete (interpreter): un programa que lee y ejecuta programas de otro lenguaje, uno pequeño que llamaremos Mini. Un programa de Mini tendrá expresiones como 2 + 3 * x. Antes de poder ejecutarlas, hay que decidir cómo se guarda una expresión en la memoria, y esa es la pregunta de hoy. La semana 14 convertirá texto en esta estructura. Esta semana, en cambio, los árboles se construyen a mano, llamando a funciones.

Para este tema se juntan cosas de todo el semestre: la unión etiquetada de la semana 7, el owner de cada bloque de la semana 5, los tipos con puntero a sí mismos que vieron de pasada en la semana 6 y el razonamiento recursivo de la semana 9. Casi nada de lo que veremos es nuevo por separado. Lo nuevo es usarlo todo junto.

En el laboratorio escribirán un pequeño módulo de álgebra: construye expresiones, las escribe, las evalúa, las simplifica y las deriva. Para no adelantarles ese trabajo, los ejemplos en C de este capítulo usan otro árbol, el de una fórmula lógica. Del tipo Expr veremos la definición, el pseudocódigo y las reglas.

Ruta de lectura.

• Antes de clase (15 a 20 minutos, obligatoria): la introducción, Por qué 2 + 3 * x es un árbol y Un tipo que se apunta a sí mismo.
• En clase: Construir: quién es owner de cada nodo, La función sigue a los datos, Liberar en el orden correcto, Escribir el árbol como texto y Evaluar: hace falta un entorno. Transformar: simplificar y entregar el árbol (✂️) entra si alcanza el tiempo.
• Después de clase: Los otros recorridos: copiar y comparar y El laboratorio, paso a paso. Luego el Resumen y los Ejercicios. Si Transformar no se vio en clase, queda como lectura. Para ir más allá: Derivar: un recorrido que construye.

Código. Los programas de este capítulo están en code/week-13. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. Los programas de errors/ tienen errores a propósito y se compilan a mano, como se muestra en cada caso.

Por qué 2 + 3 * x es un árbol

Miremos 2 + 3 * x como lo ve un archivo de texto: una lista de cinco símbolos.

2   +   3   *   x

Con x igual a 4, ¿cuánto vale? Si la recorren de izquierda a derecha, haciendo cada operación al llegar a ella, obtienen 2 + 3 = 5 y luego 5 × 4 = 20. Es falso: vale 14, porque la multiplicación va primero. La lista tiene los símbolos, pero no dice qué se opera con qué. Para saberlo, habría que mirar hacia adelante cada vez, buscar el operador más fuerte, y volver. Y con paréntesis sería peor.

Esa información tiene una forma natural. La suma opera sobre dos cosas: el 2 y “el resultado de 3 * x”. Y ese resultado, a su vez, viene de operar el 3 y la x:

Esto es un árbol de expresión (expression tree). Ya conocen el vocabulario, de los árboles de decisiones de la semana 11. Cada símbolo del dibujo es un nodo. El nodo de arriba, aquí el +, es la raíz, y los nodos sin nada debajo, aquí 2, 3 y x, son las hojas. Lo que cuelga de un nodo son sus hijos. Y cada hijo, con todo lo que tiene debajo, es un árbol completo: un subárbol. Eso último es lo que hace recursiva a la definición.

La diferencia con el árbol de decisiones es importante. Aquel era un dibujo de lo que hacía un programa: nunca existió en la memoria, salvo por el camino que estaba en la pila. Este árbol sí existe: son bloques en el heap, unidos por punteros, y vive todo lo que su owner quiera.

Compárenlo con el de (2 + 3) * x:

      *
     / \
    +   x
   / \
  2   3

Los mismos cinco símbolos, y otra forma. Noten que los paréntesis no están en el árbol. Sirven para escribir el texto, y su trabajo termina ahí: una vez que la forma existe, ya dice todo lo que decían. Por eso, cuando volvamos a escribir el árbol como texto, tendremos que decidir qué paréntesis hacen falta.

Evaluar es recorrer

El orden de las operaciones ya no hay que buscarlo. Para saber cuánto vale un nodo, hay que saber primero cuánto valen sus hijos. Sigamos el primer árbol con x igual a 4, en el orden en que se termina cada nodo:

Es el mismo patrón de la recursión que ya conocen: se baja hasta los casos base, y los resultados se combinan al volver. La diferencia es de dónde sale el problema más pequeño. No lo inventamos restando 1: ya está en los datos. Es el hijo.

Idea clave. Un árbol de expresión guarda qué se opera con qué. El orden de evaluación, la precedencia y los paréntesis del texto ya no hacen falta: quedaron convertidos en la forma del árbol.

Un tipo que se apunta a sí mismo

Un nodo de 2 + 3 * x puede ser de tres formas: un número, una variable o una operación. Un valor que tiene una de varias formas es exactamente lo que resuelve una unión etiquetada, de la semana 7. Lo nuevo es que una de las variantes contiene otros nodos.

La primera idea sería esta, en errors/self_by_value.c, con un nodo dentro de otro:

struct node {
    int kind;
    struct node left;
    struct node right;
};

$ gcc -Wall -Wextra -std=c17 errors/self_by_value.c -o build/self_by_value
errors/self_by_value.c:4:17: error: field 'left' has incomplete type

gcc no sabe cuánto mide struct node mientras lo está definiendo. Y aunque lo supiera, no tendría solución: un struct node debería medir más que dos struct node. Un árbol real, además, tiene hojas, y este tipo no podría terminar nunca.

La salida es la que vieron con los bloques de la pila en la semana 6: un puntero. Para reservar un puntero, el compilador no necesita saber cuánto mide lo que hay al otro lado. El nodo no contiene a sus hijos: apunta a ellos, y cada uno vive en su propio bloque.

La fórmula lógica de la clase

Nuestro ejemplo será una fórmula lógica, como (a and not b) or c. Sus hojas son constantes, verdadero o falso, o entradas con el nombre de una letra. Sus operaciones son not, con un hijo, y and y or, con dos. Este es el tipo, en logic.h:

typedef enum { LOGIC_CONSTANT, LOGIC_INPUT, LOGIC_NOT, LOGIC_AND, LOGIC_OR } LogicKind;

typedef struct logic Logic;

struct logic {
    LogicKind kind;
    union {
        int constant;                                // LOGIC_CONSTANT: 0 o 1
        char input;                                  // LOGIC_INPUT: una letra de 'a' a 'z'
        Logic *child;                                // LOGIC_NOT
        struct { Logic *left; Logic *right; } pair;  // LOGIC_AND y LOGIC_OR
    } as;
};

Léanlo igual que el Payment de la semana 7: kind es la etiqueta, y cada campo de la union es una variante. Hay dos detalles nuevos.

El primero es el orden. typedef struct logic Logic; va antes de la definición, así que Logic * ya se puede usar adentro. Es la misma declaración que usaron para los tipos opacos: dice que el tipo existe, y por ahora nada más.

El segundo es la variante pair: una variante puede ser un struct con varios campos. Se accede por partes, como e->as.pair.left.

La fórmula (a and not b) or c, en la memoria, es esto:

Cada rectángulo es un bloque del heap, con su propio malloc. Todos miden lo mismo, sea el nodo que sea, porque el tamaño de una union es el de su variante más grande:

$ build/node_sizes
sizeof(Logic) = 24
sizeof(Expr) = 32

Esos números dependen del entorno. Una hoja desperdicia el espacio de la variante que no usa, y eso casi nunca importa.

El tipo Expr

El tipo del laboratorio tiene la misma idea, con tres variantes. Ya viene dado, en lab/expr.h:

typedef enum { EXPR_NUMBER, EXPR_VARIABLE, EXPR_BINARY } ExprKind;
typedef enum { OP_ADD, OP_SUB, OP_MUL, OP_DIV } BinaryOp;

typedef struct expr Expr;

struct expr {
    ExprKind kind;
    union {
        double number;                                             // EXPR_NUMBER
        char *name;                                                // EXPR_VARIABLE: el nodo es owner de su copia
        struct { BinaryOp op; Expr *left; Expr *right; } binary;   // EXPR_BINARY: el nodo es owner de sus hijos
    } as;
};

Hay dos diferencias con Logic. Todas las operaciones son binarias, así que un solo EXPR_BINARY las cubre, con un campo op que dice cuál. Y una variable tiene un nombre de verdad, una cadena que el nodo posee, como el teléfono de PAY_WALLET en la semana 7.

Expr no es opaco, a propósito: el código que lo usa mira kind y hace un switch. Es la misma decisión de la semana 7, y por la misma razón.

Construir: quién es owner de cada nodo

Un constructor crea un nodo bien formado, como en la semana 7. La novedad es que ahora devuelve un puntero a un bloque nuevo. Una hoja es lo más simple. En logic.c, una función static reserva el nodo y pone la etiqueta:

static Logic *logic_node(LogicKind kind) {
    Logic *e = malloc(sizeof *e);
    if (e == NULL) {
        return NULL;
    }
    e->kind = kind;
    return e;
}

Logic *logic_input(char letter) {
    Logic *e = logic_node(LOGIC_INPUT);
    if (e == NULL) {
        return NULL;
    }
    e->as.input = letter;
    return e;
}

Las operaciones traen la pregunta de esta semana. Un and recibe dos subárboles que ya existen, cada uno con su owner: quien los creó. ¿Quién es el owner después?

La respuesta es la regla que sostiene todo el capítulo: cada nodo es owner de sus hijos. Un constructor se queda con lo que recibe. Después de logic_and(a, b), quien llamó ya no es owner de a ni de b: es owner solo del and, y al liberarlo se libera todo. El árbol entero tiene un solo owner, por una sola raíz. Es lo que en la semana 7 llamamos mover.

¿Y si algo falla? Miren cómo queda armar (a and not b) or c si cada llamada se revisa:

a ← crear entrada a
si a falló entonces
    devolver error
fin si
b ← crear entrada b
si b falló entonces
    liberar a
    devolver error
fin si
...

Es muchísimo código para un solo árbol, y cada vez hay más cosas por liberar, así que es muy fácil olvidar un caso. Por eso los constructores de este curso toman una decisión de diseño: se quedan con sus hijos también cuando fallan, y aceptan hijos NULL. Si un hijo es NULL, es que algo falló antes, así que liberan al otro y devuelven NULL también:

static Logic *logic_pair(LogicKind kind, Logic *left, Logic *right) {
    if (left == NULL || right == NULL) {
        logic_free(left);
        logic_free(right);
        return NULL;
    }
    Logic *e = logic_node(kind);
    if (e == NULL) {
        logic_free(left);
        logic_free(right);
        return NULL;
    }
    e->as.pair.left = left;
    e->as.pair.right = right;
    return e;
}

El error sube solo, y no queda nada reservado. Así se pueden anidar las llamadas, y se revisa solo el resultado final. Esto es logic_demo.c:

Logic *formula = logic_or(logic_and(logic_input('a'), logic_not(logic_input('b'))),
                          logic_input('c'));
if (formula == NULL) {

La forma de las llamadas es la forma del árbol. C no dice en qué orden evalúa los argumentos de una función, pero aquí no importa: cada uno crea su propio subárbol, sin depender de los demás. El expr_binary del laboratorio sigue esta misma regla, y lab/expr.h la tiene escrita. Las pruebas hacen fallar malloc a propósito para revisar esos caminos.

En C. Con -std=c17, string.h no declara strdup, porque no es parte de ese estándar. El nombre de una variable se copia con malloc y strcpy, como payment_wallet en la semana 7. Y si falla el segundo malloc, hay que liberar el primero.

Un nodo, un padre

“Un solo owner” tiene una consecuencia que no se ve hasta que explota. Como un subárbol vale lo mismo en cualquier lugar, es tentador reutilizarlo. En errors/shared_child.c:

Logic *a = logic_input('a');
Logic *formula = logic_and(a, a);

Es la fórmula a and a, y se escribe bien. Pero son dos padres para un mismo nodo, es decir, dos owners:

formula ──> | LOGIC_AND | left ──┐ | right ──┐ |
                                 │           │
                                 └─────┬─────┘
                                       v
                               | LOGIC_INPUT | 'a' |

Al liberar, el and libera a su hijo izquierdo y después intenta liberar al derecho, que es el mismo:

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -I. errors/shared_child.c logic.c -o build/shared_child
$ build/shared_child
==49==ERROR: AddressSanitizer: heap-use-after-free on address 0x503000000040
READ of size 4 at 0x503000000040 thread T0
    #0 0xaaaad56746a4 in logic_free logic.c:76
    #1 0xaaaad5674850 in logic_free logic.c:86
...
freed by thread T0 here:
...
    #2 0xaaaad56747d0 in logic_free logic.c:85

Lean las líneas: la 85 de logic.c es la llamada que libera al hijo izquierdo, y la 86, la del derecho. Noten que el informe no dice double-free. Antes de liberar, logic_free lee e->kind para saber la variante, y es esa lectura, en la línea 76, la que ASan detecta primero. Fue el mismo error de dos owners de la semana 7, descubierto un poco antes.

Por eso, si se necesita el mismo subárbol en dos lugares, se copia. Es lo que pasa en una derivada, y por eso el laboratorio pide escribir expr_copy antes.

Error común. Seguir usando una variable después de pasársela a un constructor. Después de formula = logic_not(a), a todavía guarda una dirección, pero ya no es de ustedes: cuando alguien libere formula, esa dirección quedará inválida. Traten esa variable como si ya no existiera.

La función sigue a los datos

Veamos la función más simple posible sobre un árbol: contar sus nodos. No hay que pensar en cómo recorrerlo. Basta con hacerse una pregunta por cada variante.

• ¿Cuántos nodos tiene una hoja? Uno.
• ¿Cuántos tiene un not? Uno, más los de su hijo.
• ¿Cuántos tiene un and o un or? Uno, más los de sus dos hijos.

Y eso se escribe tal cual, en logic.c:

int logic_count(const Logic *e) {
    switch (e->kind) {
    case LOGIC_CONSTANT:
    case LOGIC_INPUT:
        return 1;
    case LOGIC_NOT:
        return 1 + logic_count(e->as.child);
    case LOGIC_AND:
    case LOGIC_OR:
        return 1 + logic_count(e->as.pair.left) + logic_count(e->as.pair.right);
    }
    return 0;
}

Esta es la receta de toda la semana, y de la semana 15:

1. Un switch sobre kind, sin default, con un caso por variante.
2. En una variante sin punteros al mismo tipo, la respuesta es directa: es un caso base.
3. En una variante con hijos, se llama a la función sobre cada hijo, y se combinan los resultados.

Es decir, la forma de la función es la forma de los datos. La recursión aparece exactamente donde el tipo tiene un puntero a sí mismo. El return 0 del final nunca corre si los datos están bien formados, y está ahí porque gcc no sabe eso: sin él, avisa que la función puede terminar sin devolver nada.

La profundidad, es decir, cuántos nodos hay en el camino más largo desde la raíz, se escribe igual:

int logic_depth(const Logic *e) {
    switch (e->kind) {
    case LOGIC_CONSTANT:
    case LOGIC_INPUT:
        return 1;
    case LOGIC_NOT:
        return 1 + logic_depth(e->as.child);
    case LOGIC_AND:
    case LOGIC_OR: {
        int left = logic_depth(e->as.pair.left);
        int right = logic_depth(e->as.pair.right);
        return 1 + (left > right ? left : right);
    }
    }
    return 0;
}

Las llaves del último case son necesarias, porque declara variables. Como e es const Logic *, la firma promete que estas funciones solo miran.

$ build/logic_demo
or(and(a, not(b)), c)
nodos: 6
profundidad: 4
a b c | resultado
0 0 0 | 0
0 0 1 | 1
0 1 0 | 0
0 1 1 | 1
1 0 0 | 1
1 0 1 | 1
1 1 0 | 0
1 1 1 | 1

Comprueben los 6 nodos y la profundidad 4 sobre este dibujo, y sigan a mano una fila de la tabla:

        or
       /  \
     and   c
    /   \
   a    not
         |
         b

Por qué es correcta, y por qué termina

Sirven las dos preguntas de la semana 9. ¿Es correcta? Supongan que logic_count ya da la respuesta correcta para los hijos, y comprueben que entonces la da para el padre. Es el salto de fe, y aquí es muy natural: el conteo de un and es 1 más los conteos de sus subárboles. ¿Termina? Hay que encontrar un número entero que baje en cada llamada y no pueda bajar para siempre: es la cantidad de nodos del subárbol. Un hijo siempre tiene menos nodos que su padre, y una hoja no llama a nadie.

Ese argumento supone que el árbol es un árbol de verdad, con un padre por nodo y sin ciclos. Si un nodo se apuntara a sí mismo, la recursión no terminaría. Es otra razón para construirlos solo con constructores.

Sobre el costo: cada nodo se visita una vez, así que el tiempo es proporcional a la cantidad de nodos. En la pila hay, como máximo, tantos marcos como la profundidad. Es lo mismo que vieron en el árbol de la semana 11: la pila guarda solo el camino desde la raíz hasta el nodo actual.

-Wall revisa los casos

¿Por qué sin default? Por lo mismo que en la semana 7: si falta una variante, -Wall lo avisa. En errors/missing_case.c, a una función se le olvidó LOGIC_OR:

$ gcc -Wall -Wextra -std=c17 -I. errors/missing_case.c logic.c -o build/missing_case
errors/missing_case.c:7:5: warning: enumeration value 'LOGIC_OR' not handled in switch [-Wswitch]

En la semana 15 agregarán dos variantes a Expr. Sin default, gcc les dirá cada switch que deben cambiar. Con un default, se callaría.

Idea clave. Para escribir una función sobre un tipo recursivo, no piensen en el recorrido. Escriban un caso por variante, y en cada uno supongan que la función ya funciona para los hijos.

Liberar en el orden correcto

logic_free también sigue a los datos. Lo interesante es el orden:

void logic_free(Logic *e) {
    if (e == NULL) {
        return;
    }
    switch (e->kind) {
    case LOGIC_CONSTANT:
    case LOGIC_INPUT:
        break;
    case LOGIC_NOT:
        logic_free(e->as.child);
        break;
    case LOGIC_AND:
    case LOGIC_OR:
        logic_free(e->as.pair.left);
        logic_free(e->as.pair.right);
        break;
    }
    free(e);
}

Primero los hijos, después el nodo. logic_free_order.c hace lo mismo, y va escribiendo qué libera:

$ build/logic_free_order
libero a
libero b
libero un not
libero un and
libero c
libero un or

La raíz va última. ¿Por qué? Porque las direcciones de los hijos están adentro del nodo. Si se libera primero, ya no se pueden leer. En errors/free_parent_first.c, alguien lo hace al revés:

free(e);
if (e->kind == LOGIC_AND) {

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -I. errors/free_parent_first.c logic.c -o build/free_parent_first
errors/free_parent_first.c:11:10: warning: pointer 'e' used after 'free' [-Wuse-after-free]
$ build/free_parent_first
==24==ERROR: AddressSanitizer: heap-use-after-free on address 0x5030000000a0
READ of size 4 at 0x5030000000a0 thread T0
    #0 0xaaaab2c74344 in bad_free errors/free_parent_first.c:11
...
freed by thread T0 here:
...
    #1 0xaaaab2c742c4 in bad_free errors/free_parent_first.c:10

Aquí gcc lo avisó, porque el free y la lectura están pegados. No cuenten con eso: cuando los separan otras llamadas, solo ASan lo ve. Es el error de la pila con bloques de la semana 6: guarden lo que necesitan antes de free.

El error contrario es liberar solo la raíz, como en errors/free_only_root.c:

free(formula);

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -I. errors/free_only_root.c logic.c -o build/free_only_root
$ build/free_only_root
==35==ERROR: LeakSanitizer: detected memory leaks
...
SUMMARY: AddressSanitizer: 72 byte(s) leaked in 3 allocation(s).

El árbol a and not b tiene cuatro nodos, y se liberó uno. Quedan tres, de 24 bytes cada uno en este entorno. El informe completo distingue fugas directas (direct leak), bloques a los que ya nadie apunta, de indirectas (indirect leak), bloques a los que solo apunta otro bloque perdido. Al arreglar las directas, suelen arreglarse las indirectas.

Error común. Creer que el informe cuenta todas las fugas. LeakSanitizer da por perdido un bloque solo si no encuentra ningún puntero a él en la memoria, y una copia vieja en un registro o en la pila puede esconderlo. Por eso otra máquina puede contar menos bloques con este mismo programa. Una fuga reportada es real, pero que reporte pocas no dice que sean todas: arreglen y vuelvan a correr hasta que no reporte ninguna.

Escribir el árbol como texto

Una vez que un árbol existe, hay que poder verlo. logic_print usa la forma más simple: lo escribe como llamadas, por ejemplo or(and(a, not(b)), c). Con esa forma no hay ninguna duda de qué se opera con qué, y es útil para depurar:

case LOGIC_NOT:
    fputs("not(", out);
    logic_print(e->as.child, out);
    fputc(')', out);
    break;

Pero nadie quiere leer add(2, mul(3, x)), y el laboratorio pide la forma de siempre, 2 + 3 * x. Ahí aparece el problema que dejamos pendiente: la forma del árbol tiene que volver a convertirse en paréntesis.

La primera idea es poner paréntesis en todas las operaciones. Es correcto y feo: (2 + (3 * x)). Queremos solo los necesarios, y eso se decide mirando a un padre y a su hijo.

El hijo necesita paréntesis cuando, sin ellos, el texto se leería de otra forma. Primero, la precedencia: si el hijo tiene un operador más débil que el del padre, sin paréntesis sería otro árbol.

Eso no basta. ¿Qué pasa con la misma precedencia? Calculen estos dos a mano:

Los operadores de C, y los de Mini, asocian por la izquierda: 1 - 2 - 3 significa (1 - 2) - 3. Por eso los dos lados no se tratan igual. Al hijo izquierdo no le hacen falta paréntesis cuando empata con el padre, y al derecho sí.

un hijo izquierdo lleva paréntesis si su operador tiene menor precedencia que el del padre
un hijo derecho   lleva paréntesis si su operador tiene menor o igual precedencia

Con esa regla, 1 + (2 + 3) conserva sus paréntesis. Como matemática sobran, porque la suma es asociativa, pero sirven para conservar la forma: 1 + 2 + 3 es otro árbol, con otra raíz. Es lo que queremos: expr_print muestra el árbol que hay, para que lo que vean sea lo que tienen.

Las hojas nunca llevan paréntesis. Y un número negativo se escribe tal cual, como -3.

Error común. Decidir los paréntesis mirando solo al padre o solo al hijo. La pregunta siempre es sobre los dos: ¿este hijo, en este lado, bajo este padre?

Por qué expr_print recibe un FILE *

Noten que logic_print no escribe en la pantalla, sino en out. Así, un mismo código sirve para stdout, para un archivo, y para las pruebas. lab/expr_tests.c escribe en un archivo temporal, creado con tmpfile, de la biblioteca estándar, y lo lee de vuelta para comparar:

FILE *file = tmpfile();
assert(file != NULL);
expr_print(e, file);
rewind(file);
if (fgets(text, size, file) == NULL) {

Es el mismo patrón de separar el qué del cómo de la semana pasada, y es la razón por la que print en Mini podrá, más adelante, escribir donde le digan.

Evaluar: hace falta un entorno

Una fórmula lógica se evalúa con un arreglo de valores, uno por letra:

int logic_eval(const Logic *e, const int *inputs) {
    switch (e->kind) {
    case LOGIC_CONSTANT:
        return e->as.constant;
    case LOGIC_INPUT:
        return inputs[e->as.input - 'a'];
    case LOGIC_NOT:
        return !logic_eval(e->as.child, inputs);
    case LOGIC_AND:
        return logic_eval(e->as.pair.left, inputs) && logic_eval(e->as.pair.right, inputs);
    case LOGIC_OR:
        return logic_eval(e->as.pair.left, inputs) || logic_eval(e->as.pair.right, inputs);
    }
    return 0;
}

El mismo patrón otra vez. inputs es un parámetro que pasa sin cambios por toda la recursión, porque todos los nodos necesitan consultarlo.

Con Expr, hay dos diferencias. La primera es que las variables tienen nombres de cualquier largo, y un arreglo por letra ya no alcanza. Hace falta una tabla que asocie un nombre con un valor. A eso se le llama un entorno (environment): es lo mismo que dibujan en cada marco del modelo de entornos, desde la semana 3.

Esa tabla se les da hecha, y solo necesitan su encabezado, lab/env.h:

Env *env_new(Env *parent);
void env_free(Env *env);
int env_set(Env *env, const char *name, double value);
int env_get(const Env *env, const char *name, double *value);

Env es un tipo opaco, y por eso no hace falta leer env.c. Cómo guardar esa tabla de forma eficiente es tema de Estructuras de Datos. Por ahora, usen NULL como parent: la semana 15 le dará un sentido. Un programa que la usa, en env_demo.c:

double value = -1.0;
if (env_get(env, "x", &value)) {
    printf("x vale %g\n", value);
}

$ build/env_demo
x vale 10
y vale 2.5
z no existe, y value sigue en 2.5

La x vale 10 porque el programa llama a env_set dos veces con ese nombre, primero con 4 y luego con 10: la segunda cambia el valor. Y la última línea es importante: env_get no toca la variable cuando el nombre no existe.

Una función que puede fallar

La segunda diferencia es que evaluar puede salir mal: una variable que no existe, o una división entre cero. Una fórmula lógica siempre tiene un valor. Una expresión, no.

¿Cómo se devuelve ese error? Revisemos las opciones:

Elegimos la última, porque el valor y el éxito son dos cosas separadas. Es la firma de lab/expr.h:

int expr_eval(const Expr *e, const Env *env, double *result);

Devuelve 1 si pudo y 0 si no. Y queda el pseudocódigo, que ustedes traducirán a C en el laboratorio:

algoritmo evaluar(e, entorno)
    si e es un número entonces
        devolver éxito con su valor
    sino si e es una variable entonces
        devolver lo que diga buscar(entorno, nombre de e)
    sino
        izquierda ← evaluar(hijo izquierdo de e, entorno)
        si izquierda falló entonces
            devolver fracaso
        fin si
        derecha ← evaluar(hijo derecho de e, entorno)
        si derecha falló entonces
            devolver fracaso
        fin si
        si el operador es la división y derecha = 0 entonces
            devolver fracaso
        fin si
        devolver éxito con la operación de izquierda y derecha
    fin si
fin algoritmo

Fíjense en cómo sube el error. El nodo donde ocurrió devuelve fracaso, su padre lo ve y devuelve fracaso sin calcular nada, y así hasta la raíz. No hace falta nada especial: es la misma recursión. Y los valores parciales van en variables locales de cada marco, de modo que *result solo se escribe si todo salió bien.

Error común. Pasar result a las dos llamadas recursivas. La derecha escribiría encima del valor de la izquierda. Cada lado necesita su propia variable local.

Los otros recorridos: copiar y comparar

Con la receta, estas dos salen sin sorpresas, y las escribirán en el laboratorio. Solo un par de ideas.

Copiar. expr_copy crea un árbol nuevo, nodo por nodo, que no comparte nada con el original: ni los nodos ni los nombres. Es la “copia de verdad” de la semana 7. El caso de la operación es construir un nodo con las copias de sus hijos. Si recuerdan cómo se comporta expr_binary con un hijo NULL, ya saben cómo no dejar fugas cuando falle una copia: casi no hay que hacer nada.

Comparar. expr_equal responde si dos árboles son iguales en forma y contenido. Si las etiquetas son distintas, no lo son. Si son iguales, depende de la variante. Dos errores típicos:

• Comparar los punteros, a == b, dice si son el mismo árbol, no si son iguales. Dos copias nunca dan iguales así.
• Comparar nombres con == tiene el mismo problema. Las cadenas se comparan con strcmp.

Con eso, 1 + 2 y 2 + 1 no son iguales, aunque valgan lo mismo. Tampoco (1 + 2) + 3 y 1 + (2 + 3). Lo que se compara es el árbol, no el valor.

En C. Aquí sí se comparan double con ==, algo que normalmente se evita. La razón es que no comparamos resultados de un cálculo, sino valores guardados: queremos saber si son exactamente el mismo número.

Transformar: simplificar y entregar el árbol

Hasta ahora, los recorridos solo miraban el árbol o creaban otro. El siguiente cambia el árbol, y por eso es el que más exige sobre quién es owner de qué.

Una fórmula como a and true vale siempre lo mismo que a, y a and false siempre es falsa. Podemos reemplazar un subárbol por otro más simple. Ahora piensen en la firma:

Logic *logic_simplify(Logic *e);

Recibe e, sin const, y devuelve un árbol. Es un contrato de entrega: quien llama le entrega el árbol, y lo que devuelve es el nuevo árbol. Por eso siempre se usa de esta forma, en logic_simplify_demo.c:

e = logic_simplify(e);

Error común. Llamar logic_simplify(e); sin guardar el resultado. La raíz pudo cambiar, o incluso quedar liberada. e ya no es de ustedes.

La receta sigue siendo la misma, con primero los hijos. Si los hijos se simplifican antes, las reglas se aplican en cadena: en or(and(true, a), not(true)), el and se vuelve a, el not se vuelve false, y recién entonces el or puede ver que su hijo derecho es false.

static Logic *simplify_pair(Logic *e) {
    e->as.pair.left = logic_simplify(e->as.pair.left);
    e->as.pair.right = logic_simplify(e->as.pair.right);
    Logic *left = e->as.pair.left;
    Logic *right = e->as.pair.right;
    // En AND, true no cambia nada y false decide. En OR, al revés.
    int neutral = e->kind == LOGIC_AND;
    if (is_constant(left, neutral)) {
        return keep_child(e, right, left);
    }
    if (is_constant(right, neutral)) {
        return keep_child(e, left, right);
    }
    if (is_constant(left, !neutral)) {
        return keep_child(e, left, right);
    }
    if (is_constant(right, !neutral)) {
        return keep_child(e, right, left);
    }
    return e;
}

Hay que guardar lo que devuelve cada llamada: un hijo puede ser ahora un nodo distinto. Toda la dificultad está en keep_child, y son tres líneas:

static Logic *keep_child(Logic *node, Logic *kept, Logic *dropped) {
    logic_free(dropped);
    free(node);
    return kept;
}

Sigamos and(or(a, b), false). Aquí false decide, así que el resultado es el hijo derecho:

Hay tres destinos, y cada uno tiene su herramienta:

Se puede fallar en las dos direcciones. Si solo se libera el nodo y se olvida el subárbol descartado, hay una fuga. En errors/simplify_leak.c:

Logic *right = e->as.pair.right;
free(e);
return right;

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -I. errors/simplify_leak.c logic.c -o build/simplify_leak
$ build/simplify_leak
==69==ERROR: LeakSanitizer: detected memory leaks
...
SUMMARY: AddressSanitizer: 72 byte(s) leaked in 3 allocation(s).

Son los nodos de or(a, b). Y eso responde una pregunta de la guía: si la regla x * 0 del laboratorio no libera el subárbol de x, ese subárbol queda sin nadie que apunte a él. Por grande que sea, se pierde.

Si se libera con logic_free un nodo cuyo hijo se quiere conservar, ese hijo se va con él, y lo que se devuelve es una dirección inválida. En errors/simplify_dangling.c:

Logic *left = e->as.pair.left;
logic_free(e);
return left;

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -I. errors/simplify_dangling.c logic.c -o build/simplify_dangling
$ build/simplify_dangling
==81==ERROR: AddressSanitizer: heap-use-after-free on address 0x503000000040
...
freed by thread T0 here:
...
    #3 0xaaaad8174854 in bad_simplify errors/simplify_dangling.c:10

La versión correcta:

$ build/logic_simplify_demo
and(a, true)  ->  a  (nodos: de 3 a 1)
and(or(a, b), false)  ->  false  (nodos: de 5 a 1)
not(not(a))  ->  a  (nodos: de 3 a 1)
or(and(true, a), not(true))  ->  a  (nodos: de 6 a 1)
and(a, or(b, c))  ->  and(a, or(b, c))  (nodos: de 5 a 5)

La última no cambia, y también es un resultado válido: e se devuelve tal cual.

Las reglas de expr_simplify

En el laboratorio, las reglas son estas, y están en lab/expr.h:

Hay tres cuidados:

1 / 0 no se simplifica. Sigue siendo un árbol, porque el error le toca a quien evalúe. Tampoco se aplican 0 - x, que no vale x, ni 0 / x: con x igual a 0, eso es un error y no un 0.

Revisen x * 0 antes de operar constantes. En un double, -3 × 0 da -0, que %g escribe como -0. Con la regla x * 0 primero, queda un 0.

Un nodo puede cambiar de variante. Para x * 0 o una constante no hace falta malloc: se liberan los hijos, y el mismo nodo se convierte en número cambiando kind. Así expr_simplify no reserva nada, y no puede fallar por falta de memoria.

Idea clave. Simplificar x * 0 a 0 no es del todo inocente. Si x era una variable que no existe, o 1 / 0, el árbol original daba error al evaluarlo, y el simplificado da 0. Las reglas suponen que x tiene un valor. Es una decisión, y conviene que la tengan presente: un optimizador de verdad debe preguntarse si puede borrar un error.

Derivar: un recorrido que construye

Otro recorrido, ahora para repasar la receta con una idea nueva: en vez de un número, cada caso devuelve un árbol nuevo. Si llevaron cálculo, ya conocen las reglas, y si no, se pueden usar tal cual. Son una por variante, como siempre, y la función es una traducción directa de esta tabla. Aquí f y g son los subárboles, y f' y g' son sus derivadas respecto de la variable que se pide:

Miren la regla de la multiplicación desde el punto de vista del ownership. f y g aparecen cada una dos veces: una como subárbol derivado, y otra tal cual. Y en la del cociente, g aparece tres veces. Como un nodo tiene un solo padre, cada aparición de f o de g es una copia, hecha con expr_copy. Si no copian, tienen el error de shared_child.c. Además, e se recibe como const Expr *: se mira, y al final sigue siendo de quien llamó, sin cambios.

Una derivada recién hecha es larga y fea, porque las reglas son mecánicas. Y aquí es donde expr_simplify se gana su lugar. Esta es la salida de algebra, el programa ya hecho del laboratorio, con una solución terminada:

$ build/lab/algebra
expresión:    (x + 1) * (x - 2)
copia igual:  sí
derivada:     (1 + 0) * (x - 2) + (x + 1) * (1 - 0)
simplificada: x - 2 + (x + 1)
  x = 0   derivada = -1.0000   numérica = -1.0000   bien
  x = 1   derivada = 1.0000    numérica = 1.0000    bien
  x = 2.5 derivada = 4.0000    numérica = 4.0000    bien

expresión:    3 * x * x + 2 * x + 7
copia igual:  sí
derivada:     (0 * x + 3 * 1) * x + 3 * x * 1 + (0 * x + 2 * 1) + 0
simplificada: 3 * x + 3 * x + 2
  x = 0   derivada = 2.0000    numérica = 2.0000    bien
  x = 1   derivada = 8.0000    numérica = 8.0000    bien
  x = 2.5 derivada = 17.0000   numérica = 17.0000   bien

expresión:    x / (x + 1)
copia igual:  sí
derivada:     (1 * (x + 1) - x * (1 + 0)) / ((x + 1) * (x + 1))
simplificada: (x + 1 - x) / ((x + 1) * (x + 1))
  x = 0   derivada = 1.0000    numérica = 1.0000    bien
  x = 1   derivada = 0.2500    numérica = 0.2500    bien
  x = 2.5 derivada = 0.0816    numérica = 0.0816    bien

expresión:    1 / x
copia igual:  sí
derivada:     (0 * x - 1 * 1) / (x * x)
simplificada: -1 / (x * x)
  x = 0   no se puede evaluar
  x = 1   derivada = -1.0000   numérica = -1.0000   bien
  x = 2.5 derivada = -0.1600   numérica = -0.1600   bien

Sigan a mano la línea derivada: de la primera expresión. (x + 1) * (x - 2) es f * g, con f' igual a 1 + 0 y g' igual a 1 - 0: es exactamente la regla. Al simplificar, 1 + 0 da 1, 1 * (x - 2) da x - 2, y lo mismo con el otro lado.

Noten que nuestras reglas no reúnen 3 * x + 3 * x en 6 * x, ni x + 1 - x en 1. Eso es otra clase de simplificación, bastante más difícil, y no es necesaria: el valor es correcto.

¿Cómo sabemos que la derivada es correcta, sin confiar en las mismas reglas que queremos revisar? Con los números. La derivada es la pendiente en un punto, y se puede aproximar sin saber cálculo: se evalúa la expresión en x un poquito antes y un poquito después, y se calcula la pendiente entre esos dos puntos. La última columna es esa cuenta, y algebra compara las dos.

numérica ← (f(x + h) - f(x - h)) / (2 * h)       con h = 0.00001

Comprobar con otro método, que no comparte errores con el primero, es una buena costumbre. Un error en la regla del cociente no aparece en el cálculo numérico, porque este no la usa.

Error común. Comparar el texto de la derivada con el de otra persona. Hay muchas formas correctas de escribir el mismo árbol: f' * g o g * f'. Lo que debe coincidir es el valor. Por eso, las pruebas de expr_derive evalúan.

Quién es owner: el resumen

Las firmas de todo el módulo se leen como una tabla de ownership:

Y una aclaración, para que no se confundan con lo que viene. Un árbol de expresión existe para representar expresiones. Los árboles que sirven para buscar datos rápido, igual que las tablas hash, se estudian e implementan en el curso de Estructuras de Datos.

El código de esta semana

make compila los programas de la clase en build/. make test corre tres archivos de pruebas:

make test-lab corre esas mismas pruebas de laboratorio sobre su código.

El laboratorio, paso a paso

Los archivos de partida están en code/week-13/lab, y su README.md tiene las preguntas y lo que pide cada parte. Aquí están las ideas, no el código. expr.h y env.h no se cambian. Sus comentarios son el enunciado, así que léanlos con calma.

Sesión 1

Constructores. Escriban primero un auxiliar static que reserve el nodo. expr_variable reserva dos bloques, el nodo y su copia del nombre, y si falla el segundo debe liberar el primero. expr_binary sigue la regla de logic_pair. Las pruebas revisan cada reserva haciéndola fallar, una a la vez.

expr_free. Es un switch, con los hijos primero, y solo EXPR_VARIABLE tiene un nombre que liberar.

expr_print. Una función auxiliar static que diga la precedencia de un nodo, y otra que escriba un hijo con paréntesis o sin ellos, lo dejan muy corto. Usen %g para los números, y escriban en out.

expr_eval. Traduzcan el pseudocódigo. Una variable se resuelve con una sola llamada a env_get. ¿Por qué ya cumple lo de no tocar *result?

Sesión 2

expr_copy y expr_equal. Son las más cortas. Si expr_copy les queda larga, revisen cómo usan expr_binary.

expr_simplify. Es la más delicada. Simplifiquen los hijos, guarden lo que devuelven, y usen auxiliares como keep_child y otro que convierta un nodo en número. Antes de cada regla, pregúntense qué pasa con cada nodo del dibujo. ASan les va a decir si se equivocan, y en qué línea.

expr_derive. Traduzcan la tabla, con un caso por variante y otro por operador. Cada f o g que aparezca tal cual es una llamada a expr_copy. Como expr_binary acepta hijos NULL, no hace falta revisar cada llamada, y no queda ninguna fuga si una falla. build/lab/algebra es la comprobación final, y sus números deben coincidir con los de arriba. La forma de su derivada puede ser otra.

Resumen

• Un árbol de expresión guarda qué se opera con qué. Los paréntesis y la precedencia del texto se convierten en la forma del árbol, y no se guardan.
• Un tipo recursivo es una unión etiquetada con punteros a sí misma. Un nodo no puede contener a otro: apunta a él.
• Cada nodo es owner de sus hijos. El árbol tiene un solo owner, por la raíz, y un nodo tiene un solo padre.
• Un constructor se queda con sus hijos, también cuando falla, y acepta hijos NULL. Así se pueden anidar, y basta con revisar el resultado final.
• La función sigue a los datos: un switch sin default, con un caso por variante. La recursión aparece donde el tipo se apunta a sí mismo, y termina porque un subárbol tiene menos nodos.
• Para liberar, primero los hijos, porque sus direcciones están en el nodo. Liberar solo la raíz deja fugas.
• expr_print solo pone los paréntesis necesarios para conservar la forma: el hijo izquierdo con menor precedencia, y el derecho con menor o igual.
• Evaluar necesita un entorno, una tabla de nombres y valores. Se usa solo por su encabezado.
• Lo que puede fallar devuelve un int de éxito y el valor por un puntero, porque todo double es un resultado válido.
• Dos árboles son iguales si coinciden en forma y contenido, no en valor. No se comparan con == entre punteros.
• Una función que transforma el árbol se queda con él, y se usa como e = logic_simplify(e);. Lo que conserva se devuelve, un subárbol descartado se libera con su función recursiva, y el nodo que desaparece, con free.
• Cuando una regla usa un subárbol dos veces, se copia.
• Una derivada se puede revisar con otro método: la pendiente numérica.

Ejercicios

Decidan primero y ejecuten después. Todo programa revisa sus lecturas, compila sin advertencias y libera lo que reserva.

1. Dibujen el árbol de cada una. ¿Cuántos nodos tiene cada una? ¿Cuántas hojas?

   a) (1 + 2) * x
   b) 1 + 2 * x - 3
   c) a / b / c
   d) a / (b / c)

2. Tomen los árboles del ejercicio 1 y sigan a mano su evaluación con x = 4, a = 8, b = 4 y c = 2. Hagan una tabla como la de 2 + 3 * x, en el orden en que termina cada nodo.

3. ¿Por qué logic_free libera primero a los hijos? Sigan a mano la versión al revés sobre not(a), y digan exactamente qué línea lee memoria liberada.

4. ¿En cuál de estos árboles hacen falta paréntesis? Escriban cada uno con las reglas de expr_print, y comprueben en su laboratorio.

   a) suma de x y el producto de y y z
   b) producto de x y la suma de y y z
   c) resta de x y la suma de y y z
   d) división de x y el producto de y y z
   e) suma de la suma de x y y, y z

5. Agreguen a logic.c una función int logic_count_inputs(const Logic *e) que cuente las hojas que son entradas, y comprueben que -Wall no avisa nada. Luego quiten el caso LOGIC_NOT. ¿Qué dice ahora?

6. Escriban int logic_uses(const Logic *e, char letter), que responde si la fórmula usa una letra. ¿Sigue haciendo falta recorrer todo el árbol si ya la encontró? Escriban Logic *logic_copy(const Logic *e), y compruébenla sin fugas con una prueba que libere el original antes de evaluar la copia.

7. logic_simplify no reconoce a and a. Agreguen esa regla, escribiendo antes int logic_equal(const Logic *a, const Logic *b). ¿Qué se libera? ¿Qué se devuelve? ¿La regla cambia el resultado de logic_eval en algún caso?

8. Sin ejecutar, digan qué pasa si, después de construir not(not(a)), alguien escribe logic_simplify(e); y luego logic_print(e, stdout);, sin guardar lo que devolvió. Compruébenlo con ASan. ¿Qué línea cambia para arreglarlo?

9. Con su laboratorio terminado, escriban un árbol en el que expr_eval falle antes de simplificar y funcione después, y otro en el que expr_simplify no cambie nada. Para el primero, expliquen qué regla borró el error. ¿Hay algún árbol que funcione antes y falle después?

10. Escriban Expr *expr_substitute(const Expr *e, const char *name, const Expr *value), que devuelve un árbol nuevo donde cada variable name se cambió por una copia de value. Comprueben que la evaluación de expr_substitute(e, "x", v) coincide con evaluar e, en un entorno donde x vale lo que vale v.

11. Una expresión con n multiplicaciones anidadas a la izquierda, como x * x * x * x, ¿cuántos nodos tiene su derivada sin simplificar? Escriban un programa que la construya para n de 1 a 10 y lo mida con una función que cuente nodos. ¿Crece parejo? ¿Qué parte de la regla es la que lo hace crecer?

12. Mini no tiene potencias. Agreguen a su copia de expr.h un OP_POW para potencias con un exponente que es un número: x ^ 3. Sigan los avisos de -Wswitch para saber qué funciones cambiar. ¿Cuál es su precedencia? ¿Con qué lado asocia, en matemáticas? ¿Qué regla de expr_print deja de valer?