# Laboratorio de la semana 13: álgebra de expresiones

Hay dos sesiones de 2 horas. Cada una está pensada para unos 90 minutos de trabajo. Los comandos se
corren desde `code/week-13`. Las ideas están en los apuntes, en la sección "El laboratorio, paso a paso".

| Archivo | Qué es | ¿Lo cambian? |
|---|---|---|
| `expr.h` | El tipo `Expr` y la interfaz de todo el módulo. Sus comentarios son el enunciado | No |
| `expr.c` | Las funciones de `Expr` | **Sí** |
| `env.h` | La interfaz de la tabla de variables `Env` | No |
| `env.c` | La tabla de variables. Funciona, y no hace falta leerla | No |
| `expr_tests.c` | Sus pruebas con `assert`. Ya trae tres, como modelo | **Sí** |
| `algebra.c` | Un programa que usa todo el módulo y compara cada derivada con un cálculo numérico | No |

```sh
make lab                  # compila todo en build/lab/
make test-lab             # comprueba todo el laboratorio; falla hasta que terminen
```

`make test-lab` corre pruebas de las dos sesiones. Se puede correr un grupo solo:

```sh
LAB_DIR=lab python3 -m unittest test_lab.Constructors
```

Los grupos, en orden, son `Constructors`, `Free`, `Print` y `Eval` para la sesión 1, y `Copy`, `Equal`,
`Simplify` y `Derive` para la sesión 2. `Whole` comprueba al final que no haya advertencias ni variables
globales, y que `expr_tests` y `algebra` terminen bien.

Todo se compila con ASan y UBSan: una fuga hace fallar la prueba, aunque el resultado sea correcto. Varias
pruebas hacen fallar `malloc` a propósito, una reserva a la vez, para revisar sus caminos de error. Por eso,
**toda reserva se revisa, y al fallar no deja nada reservado**. En `-std=c17` no existe `strdup`: la copia del
nombre se hace con `malloc` y `strcpy`, como en la semana 7.

## Sesión 1: construir, liberar, escribir y evaluar

### Parte 1: leer (unos 15 minutos)

Lean `expr.h` completo, `env.h` y `expr_tests.c`. No hace falta abrir `env.c`. Respondan por escrito, sin
ejecutar nada:

1. Dibujen el árbol de `(1 + 2) * x`, con el contenido de cada nodo. ¿Cuántos nodos tiene? ¿Cuántas llamadas
   a `malloc` hará construirlo?
2. En `expr_tests.c`, `test_constructors` anida llamadas y solo revisa la última. ¿Por qué eso no deja fugas
   si un `expr_number` de adentro devuelve `NULL`?
3. ¿Por qué `expr_eval` devuelve un `int` y guarda el valor en `*result`, en vez de devolver el `double`?

### Parte 2: constructores y `expr_free` (unos 25 minutos)

Escriban `expr_number`, `expr_variable`, `expr_binary` y `expr_free`. Una función auxiliar `static` que reserve el
nodo y ponga la etiqueta les ahorra repetir código.

```sh
LAB_DIR=lab python3 -m unittest test_lab.Constructors test_lab.Free
```

### Parte 3: `expr_print` (unos 25 minutos)

Escriban `expr_print`. Las reglas de paréntesis están en `expr.h`, y estos casos son la prueba de que las entendieron:

| Árbol | Se escribe |
|---|---|
| suma de 2 y el producto de 3 y `x` | `2 + 3 * x` |
| producto de la suma de 2 y 3, y `x` | `(2 + 3) * x` |
| resta de la resta de 1 y 2, y 3 | `1 - 2 - 3` |
| resta de 1, y la resta de 2 y 3 | `1 - (2 - 3)` |
| suma de 1, y la suma de 2 y 3 | `1 + (2 + 3)` |

Escriban en `out`, no en la pantalla. Usen `fprintf` y `fputs`.

```sh
LAB_DIR=lab python3 -m unittest test_lab.Print
```

### Parte 4: `expr_eval` (unos 25 minutos)

Escriban `expr_eval` a partir del pseudocódigo de los apuntes. Usen `env_get`, y **no toquen `*result` si hay un
error**: cada lado se evalúa en una variable local. Corran `make lab` y luego `build/lab/expr_tests`, que debe
decir que todas las pruebas pasaron.

```sh
LAB_DIR=lab python3 -m unittest test_lab.Eval
```

**Si no alcanza el tiempo:** lo que falte de esta sesión lo terminan antes de la siguiente, porque la sesión 2
construye sobre todo esto.

## Sesión 2: copiar, comparar, simplificar y derivar

### Parte 1: `expr_copy` y `expr_equal` (unos 20 minutos)

Escriban las dos. Agreguen a `expr_tests.c` una función de prueba que copie un árbol, compruebe que las dos
versiones son iguales, cambie un número de la copia y compruebe que ya no lo son. ¿Por qué `expr_copy` queda
tan corta si usan bien `expr_binary`?

```sh
LAB_DIR=lab python3 -m unittest test_lab.Copy test_lab.Equal
```

### Parte 2: `expr_simplify` (unos 35 minutos)

Antes de escribir, respondan: al aplicar `x * 1`, ¿qué nodos se liberan, y cuál se devuelve? ¿Y al aplicar
`x * 0`?

Las reglas están en `expr.h`. Simplifiquen primero a los hijos, y guarden lo que devuelven: un hijo puede haber
cambiado de dirección. Cuiden el orden: revisen `x * 0` antes de operar constantes, para que `-3 * 0` dé `0` y no
`-0`.

No agreguen reglas como `0 - x` o `0 / x`: una cambia el resultado, y la otra cambia cuándo hay un error.

```sh
LAB_DIR=lab python3 -m unittest test_lab.Simplify
```

### Parte 3: `expr_derive` (unos 35 minutos)

Las reglas están en los apuntes. La idea que hay que cuidar: un nodo tiene un solo padre. Si la regla usa `g` dos
veces, hay dos copias. `e` no se cambia.

```sh
make lab
build/lab/algebra
LAB_DIR=lab python3 -m unittest test_lab.Derive
make test-lab
```

`algebra` escribe la derivada de cuatro expresiones y la compara con la pendiente calculada entre dos puntos muy
cercanos. Cada línea debe decir `bien`. Su derivada puede tener otra forma que la de los apuntes, por ejemplo con
los términos en otro orden. Lo que debe coincidir es el valor.

**Si no alcanza el tiempo:** el caso de `/` en `expr_derive` y la revisión con `algebra` son lo que se puede
terminar antes de la próxima clase.

## Si sobra tiempo

1. Agreguen una regla a `expr_simplify` que convierta `x - x` en `0` cuando los dos lados sean iguales, usando
   `expr_equal`. Busquen un ejemplo en el que eso cambie lo que hace `expr_eval`.
2. Escriban `int expr_count(const Expr *e)` y úsenla en `algebra.c` para ver cuántos nodos ahorra simplificar.
3. Escriban `Expr *expr_substitute(const Expr *e, const char *name, const Expr *value)`, que devuelve un árbol nuevo
   donde cada `name` se cambió por una copia de `value`. ¿Cuántas copias de `value` se hacen?