El modelo de entornos

En las semanas 1 y 2 repasamos C, y aprendimos a leer un programa ajeno antes de cambiarlo. Leer bien exige algo más que entender cada línea: hay que saber qué existe en cada momento de la ejecución. ¿Esta x es la de main o la de la función? ¿Este valor sigue ahí después de retornar? ¿Por qué una función pudo cambiar un arreglo y no pudo cambiar un int?

En Introducción a la Computación vieron la pila de llamadas como un dibujo que explicaba el paso por valor. Hoy convertimos ese dibujo en una herramienta de trabajo, con reglas precisas: el modelo de entornos (environment model). Con él se predice qué hace un programa sin ejecutarlo. Después comprobamos las predicciones en gdb, mirando los marcos reales. Las semanas que vienen dependen de esto: los punteros de la semana 4 y la memoria dinámica de la semana 5 se entienden dibujándolos, y la recursión de la semana 9 es este mismo modelo con muchos marcos.

El laboratorio trabaja con imágenes en escala de grises. Una imagen es un struct con un arreglo adentro, y eso nos da el mejor ejemplo de la semana: un caso donde se copia todo, y otro, muy parecido, donde no se copia casi nada.

Ruta de lectura.

• Antes de clase (15 a 20 minutos, obligatoria): la introducción, Por qué hace falta un modelo y Las reglas del modelo.
• En clase: Alcance y tiempo de vida, Ver los marcos en gdb, Paso por valor en el modelo y una presentación corta de Imágenes en PGM y Filtros.
• Después de clase: Imágenes en PGM y Filtros completos, que el laboratorio usa, y El laboratorio, paso a paso. Luego el Resumen y los Ejercicios. Para ir más allá: los últimos ejercicios del capítulo.

Código. Los programas de este capítulo están en code/week-03. 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é hace falta un modelo

Lean este programa, frames.c, y digan qué imprime antes de seguir.

int triple(int n) {
    int result = n * 3;
    return result;
}

int add_triple(int a, int b) {
    int t = triple(b);
    a = a + t;
    return a;
}

int main(void) {
    int a = 2;
    int b = 5;
    int c = add_triple(a, b);

    printf("a = %d, b = %d, c = %d\n", a, b, c);
    return 0;
}

La línea a = a + t cambia a. La duda es si cambia la a que luego imprime main. Se puede responder de dos formas. Una es correr el programa y aceptar lo que salga. La otra es tener un modelo que dé la respuesta, y usar la corrida para comprobarlo.

$ build/frames
a = 2, b = 5, c = 17

Correr el programa no basta por tres razones. Una corrida solo dice qué pasó con esos datos, no por qué, y por tanto no dice qué pasará con otros. Un error de memoria puede dar el resultado correcto en una corrida y el incorrecto en otra. Y antes de escribir un programa no hay nada que correr: para diseñarlo, hay que poder imaginar su ejecución.

Idea clave. Un modelo es útil si predice. Dibujen primero y ejecuten después. Cuando la predicción y la realidad no coinciden, algo aprendieron: o el programa tiene un bug, o su modelo tiene un error.

Las reglas del modelo

Un marco de llamada (stack frame), o simplemente marco, es el espacio que crea cada llamada para guardar sus parámetros y sus variables locales. El modelo se resume en cuatro reglas.

La regla 2 sorprende al principio. Cuando corre triple, el marco de add_triple sigue existiendo justo debajo, con sus variables, y aun así triple no las puede nombrar. Una función solo conoce los nombres que están escritos en su propio texto. El compilador lo revisa antes de que exista ningún marco:

void show_total(void) {
    printf("%d\n", total);
}

int main(void) {
    int total = 5;

    show_total();

$ gcc -Wall -Wextra -std=c17 errors/caller_local.c -o build/caller_local
errors/caller_local.c: In function 'show_total':
errors/caller_local.c:5:20: error: 'total' undeclared (first use in this function)
    5 |     printf("%d\n", total);
      |                    ^~~~~
errors/caller_local.c:5:20: note: each undeclared identifier is reported only once for each function it appears in

Cómo se dibuja

Usaremos este formato en los apuntes, en la pizarra y en sus hojas. El marco activo, el más reciente, va arriba. Cada marco lleva el nombre de la función. Un ? indica una variable que ya tiene su espacio, pero que todavía no recibió un valor.

Sigamos frames.c. Antes de la primera llamada, solo está main, y c espera su resultado:

main         a = 2   b = 5   c = ?

Al llamar a add_triple(a, b), la regla 1 calcula los argumentos, 2 y 5, y los copia. Se llaman igual que las variables de main, y eso no importa: son otras casillas.

add_triple   a = 2   b = 5   t = ?
main         a = 2   b = 5   c = ?

La línea int t = triple(b) necesita una llamada antes de poder guardar nada. La b se busca en el marco actual, y vale 5.

triple       n = 5   result = ?
add_triple   a = 2   b = 5   t = ?
main         a = 2   b = 5   c = ?

triple calcula result, que vale 15, y retorna. Su marco desaparece, y el 15 llega a t. Ahora a = a + t usa la a del marco actual (regla 2) y solo cambia esa (regla 3).

add_triple   a = 17  b = 5   t = 15
main         a = 2   b = 5   c = ?

add_triple retorna 17, su marco desaparece, y c recibe el valor. La a de main nunca se tocó.

main         a = 2   b = 5   c = 17

Por eso la salida es a = 2, b = 5, c = 17. Lo que antes era una duda ahora se puede deducir.

Error común. Dibujar un solo a porque el nombre se repite. Una casilla pertenece a un marco. Si dos funciones usan el mismo nombre, hay dos casillas, y además cada llamada crea las suyas.

Qué marcos existen en cada momento

Cuando main llama a f y f llama a g, dentro de g existen tres marcos: el de main, el de f y el de g. Los tres están vivos, porque main y f no terminaron: están esperando. Solo el de g está activo, es decir, solo sus nombres se pueden usar en ese momento.

Esa secuencia de marcos es la pila (stack). Se llama así porque el último marco que entra es el primero que sale. Si la misma función se llama dos veces, se crean dos marcos distintos, cada uno con sus casillas. Y el primero ya no existe cuando se crea el segundo, salvo que la función se llame a sí misma; ese caso lo estudiaremos en la semana 9.

En C. El modelo es una forma de razonar, y el estándar de C no habla de marcos: describe qué debe hacer el programa, no dónde guarda cada cosa. No fija en qué dirección queda una local ni hacia dónde crece la pila, y el compilador puede guardar una variable en un registro de la CPU o incluso eliminarla si nadie nota la diferencia. Lo que el lenguaje sí garantiza es lo que el modelo predice: cada llamada tiene sus propias variables, y al volver se sigue donde se quedó.

Alcance y tiempo de vida

Son dos preguntas distintas sobre una variable, y es fácil confundirlas.

• El alcance (scope) es una propiedad del texto del programa: ¿en qué líneas se puede usar este nombre?
• El tiempo de vida (lifetime) es una propiedad de la ejecución: ¿durante cuánto tiempo existe este dato en la memoria?

Una variable puede existir sin que su nombre se pueda usar. Es lo que pasa en el ejemplo anterior: mientras corre triple, la t de add_triple está viva, pero fuera de alcance.

Alcance: los bloques

El alcance de una variable local va desde su declaración hasta la } que cierra su bloque. Un parámetro tiene como alcance toda su función. Y un bloque interno puede declarar otra variable con el mismo nombre: esta oculta a la de afuera mientras dura el bloque. Miren blocks.c:

int x = 1;
printf("afuera: x = %d\n", x);

{
    int x = 2;
    x = x + 10;
    printf("adentro: x = %d\n", x);
}
printf("afuera otra vez: x = %d\n", x);

int total = 0;
for (int i = 1; i <= 3; i++) {
    int square = i * i;
    total = total + square;
}
printf("total = %d\n", total);

$ build/blocks
afuera: x = 1
adentro: x = 12
afuera otra vez: x = 1
total = 14

Son dos x. La asignación x = x + 10 encuentra la más cercana, por la regla 2, y la de afuera sigue en 1. gcc no avisa de esto ni con -Wall -Wextra: es legal, aunque rara vez es buena idea. Lo usamos aquí porque en código ajeno lo van a encontrar.

Fuera de su bloque, el nombre no existe, aunque el programa siga corriendo: errors/out_of_block.c no compila, y gcc dice 'square' undeclared.

Tiempo de vida: variables locales

Una variable local vive mientras se ejecuta su bloque. Si el bloque es el cuerpo de una función, eso coincide con la vida del marco. El square del for nace y muere en cada vuelta, y se vuelve a inicializar cada vez. No recuerda nada de la vuelta anterior.

Al terminar la vida de una variable, su valor no se borra: simplemente, ese espacio deja de ser de ella. Una llamada posterior puede usar el mismo espacio y encontrar ahí lo que otra función dejó. De ahí viene la “basura” de una local sin inicializar: leer ese valor en el programa es comportamiento indefinido (undefined behavior), es decir, el estándar de C no exige ningún resultado.

static: alcance local, vida completa

En Introducción a la Computación, count_calls intentó contar sus llamadas con una local y no pudo. La palabra static en una variable local cambia justo una de las dos cosas: el tiempo de vida. El alcance sigue siendo el bloque. En static_counter.c están las dos versiones:

int count_local(void) {
    int calls = 0;
    calls = calls + 1;
    return calls;
}

int count_static(void) {
    static int calls = 0;
    calls = calls + 1;
    return calls;
}

$ build/static_counter
local: 1, static: 1
local: 1, static: 2
local: 1, static: 3

Una local static no vive en el marco: existe una sola vez, durante todo el programa, fuera de la pila. Por eso sobrevive de una llamada a otra. Su inicialización ocurre una sola vez, antes de que el programa empiece a correr, no en cada llamada. La línea static int calls = 0; no se ejecuta en cada llamada. Por eso mismo, su valor inicial debe ser constante. Si nunca se inicializa, empieza en 0.

$ gcc -Wall -Wextra -std=c17 errors/static_init.c -o build/static_init
errors/static_init.c: In function 'next_from':
errors/static_init.c:5:24: error: initializer element is not constant
    5 |     static int value = n;
      |                        ^

En el dibujo, una variable static va aparte, fuera de la pila:

Pila:                               Fuera de la pila:
count_static   (sin locales aquí)   count_static.calls = 1
main           i = 0  first = 1  second = ?

Esta tabla es lo que hay que recordar:

Una local static tiene un costo: la función deja de depender solo de sus parámetros, y con los mismos argumentos da resultados distintos en cada llamada. Eso complica sus pruebas, por la misma razón que vieron con rand. Sirve en pocos casos, y no la necesitarán en los filtros de este laboratorio.

Constantes globales

La regla del curso prohíbe las variables globales, porque si cualquier función puede cambiar un dato, un error puede estar en cualquier parte. Una constante global no tiene ese problema: todas las funciones la ven y ninguna la puede cambiar. En global_constant.c:

const int PASSING_GRADE = 11;

int is_passing(int grade) {
    return grade >= PASSING_GRADE;
}

$ build/global_constant
Aprobados: 2 de 4

Si una función intenta cambiarla, como en errors/assign_constant.c, no compila: gcc dice assignment of read-only variable 'PASSING_GRADE'.

Ese mismo programa usa #define MAX_STUDENTS 4. Las dos formas no son lo mismo. #define reemplaza el texto antes de compilar, así que MAX_STUDENTS no es una variable, no ocupa memoria, y donde aparece el compilador ve un 4. const int, en cambio, es una variable de solo lectura. Por eso, en C, no sirve como tamaño de un campo de un struct:

const int MAX_WIDTH = 64;

struct line {
    int cells[MAX_WIDTH];
};

$ gcc -Wall -Wextra -std=c17 errors/const_size.c -o build/const_size
errors/const_size.c:7:9: error: variably modified 'cells' at file scope
    7 |     int cells[MAX_WIDTH];
      |         ^~~~~

Por eso el módulo de imágenes usa #define para el tamaño máximo, como verán en un momento.

Ver los marcos en gdb

gdb ya lo conocen de Introducción a la Computación. Hoy lo usamos con un objetivo preciso: comprobar los dibujos. Recuerden compilar con -g -O0 y sin sanitizers. Además de break, run, next, step, print, finish y continue, necesitamos estos comandos:

Compilemos frames.c. También aquí, como en Introducción a la Computación, recortamos la ruta de la línea Starting program y quitamos las dos líneas de libthread_db. Las direcciones que empiezan con 0x, los números de proceso y el valor de las variables sin inicializar dependen del entorno.

$ gcc -Wall -Wextra -std=c17 -g -O0 frames.c -o build/frames_gdb

$ gdb -q build/frames_gdb
Reading symbols from build/frames_gdb...
(gdb) break triple
Breakpoint 1 at 0x7b0: file frames.c, line 5.
(gdb) run
Starting program: .../build/frames_gdb

Breakpoint 1, triple (n=5) at frames.c:5
5	    int result = n * 3;
(gdb) backtrace
#0  triple (n=5) at frames.c:5
#1  0x0000aaaaaaaa07e8 in add_triple (a=2, b=5) at frames.c:10
#2  0x0000aaaaaaaa082c in main () at frames.c:18
(gdb) info args
n = 5
(gdb) info locals
result = 0
(gdb) frame 1
#1  0x0000aaaaaaaa07e8 in add_triple (a=2, b=5) at frames.c:10
10	    int t = triple(b);
(gdb) info args
a = 2
b = 5
(gdb) info locals
t = 65535
(gdb) frame 2
#2  0x0000aaaaaaaa082c in main () at frames.c:18
18	    int c = add_triple(a, b);
(gdb) info locals
a = 2
b = 5
c = 65535
(gdb) continue
Continuing.
a = 2, b = 5, c = 17
[Inferior 1 (process 134) exited normally]
(gdb) quit

Comparen esto con el tercer dibujo de la sección anterior. Son los mismos tres marcos, con los mismos valores. Donde dibujamos ?, gdb muestra lo que había en esa memoria: 0, 65535. No significan nada, y en su máquina pueden salir otros. Es lo que un ? quiere decir.

Dos detalles de esta lectura:

• frame no retrocede en el tiempo. Solo elige qué marco mirar. El programa sigue detenido en triple. Por eso, en frame 1 se ve la línea 10, y t todavía no tiene valor: esa línea está a medias, esperando que triple termine.
• La línea que gdb muestra todavía no se ejecutó. Por eso result aún no valía 15 en la línea 5.

Ver el alcance

En blocks.c, info locals muestra todas las variables que existen en el bloque actual y en los que lo rodean, de adentro hacia afuera.

$ gcc -Wall -Wextra -std=c17 -g -O0 blocks.c -o build/blocks_gdb

$ gdb -q build/blocks_gdb
Reading symbols from build/blocks_gdb...
(gdb) break 11
Breakpoint 1 at 0x7dc: file blocks.c, line 11.
(gdb) run
Starting program: .../build/blocks_gdb
afuera: x = 1

Breakpoint 1, main () at blocks.c:11
11	        printf("adentro: x = %d\n", x);
(gdb) info locals
x = 12
x = 1
total = 2
(gdb) print x
$1 = 12
(gdb) break 18
Breakpoint 2 at 0xaaaaaaaa0818: file blocks.c, line 18.
(gdb) continue
Continuing.
adentro: x = 12
afuera otra vez: x = 1

Breakpoint 2, main () at blocks.c:18
18	        total = total + square;
(gdb) info locals
square = 1
i = 1
x = 1
total = 0
(gdb) delete 2
(gdb) continue
Continuing.
total = 14
[Inferior 1 (process 147) exited normally]
(gdb) quit

La primera parada muestra algo que vale la pena mirar con calma. Aparecen las dos x, la de adentro primero, y print x elige la de adentro, como dice la regla 2. Además aparece total, con un valor cualquiera, aunque su declaración está varias líneas más abajo. Es la diferencia entre las dos preguntas de esta sección: la variable ya existe, porque su bloque ya empezó, pero su nombre aún no tiene alcance. Si escribieran total en la línea 11, no compilaría. Es decir, en este caso el tiempo de vida empieza antes que el alcance.

Ver una variable static

$ gcc -Wall -Wextra -std=c17 -g -O0 static_counter.c -o build/static_counter_gdb

$ gdb -q build/static_counter_gdb
Reading symbols from build/static_counter_gdb...
(gdb) break count_static
Breakpoint 1 at 0x7c8: file static_counter.c, line 12.
(gdb) run
Starting program: .../build/static_counter_gdb

Breakpoint 1, count_static () at static_counter.c:12
12	    calls = calls + 1;
(gdb) info locals
calls = 0
(gdb) continue
Continuing.
local: 1, static: 1

Breakpoint 1, count_static () at static_counter.c:12
12	    calls = calls + 1;
(gdb) info locals
calls = 1
(gdb) up
#1  0x0000aaaaaaaa0810 in main () at static_counter.c:19
19	        int second = count_static();
(gdb) info locals
first = 1
second = 1
i = 1
(gdb) print count_static::calls
$1 = 1
(gdb) print calls
No symbol "calls" in current context.
(gdb) delete 1
(gdb) continue
Continuing.
local: 1, static: 2
local: 1, static: 3
[Inferior 1 (process 160) exited normally]
(gdb) quit

Hay cuatro cosas para mirar:

• El punto de parada quedó en la línea 12, no en la 11: la línea static int calls = 0; no genera nada que ejecutar en cada llamada.
• En la segunda llamada, calls ya vale 1 al entrar. Es el valor de la llamada anterior.
• info locals lista a calls, porque el nombre es local aunque el dato no viva en el marco.
• Desde main, print calls falla, porque el nombre no tiene alcance ahí. print count_static::calls funciona, porque el dato existe. Esa sintaxis es propia de gdb, no de C.

Paso por valor en el modelo

La pregunta de por qué void inc(int x) { x++; } no cambia la variable de quien llama ya tiene una respuesta corta: por la regla 1, x es una casilla de otro marco, que recibió una copia. Por la regla 3, x++ solo cambia esa casilla. Al retornar, la casilla desaparece. Está en by_value.c:

$ build/by_value
en inc: x = 8
en main: x = 7
con return: x = 8

inc          x = 8       <- esta se cambió
main         x = 7       <- esta no

La información sale de una función por el return, como en x = plus_one(x). Todo lo que sigue es la misma regla aplicada a otros tipos: C siempre copia el valor del argumento. La pregunta es qué es “el valor” en cada caso.

Arreglos: se copia la dirección

Como vieron en la semana 10 de Introducción a la Computación, en casi toda expresión el nombre de un arreglo da la dirección de memoria (memory address) donde empieza. Pasar un arreglo a una función es una de esas expresiones. En array_param.c:

void change_int(int x) {
    x = 99;

void change_array(int values[], int n) {
    for (int i = 0; i < n; i++) {
        values[i] = values[i] * 10;
    }
    n = 0;

change_int(data[0]);
print_array(data, count);

change_array(data, count);
print_array(data, count);
printf("count = %d\n", count);

$ build/array_param
en change_int: x = 99
1 2 3 4
en change_array: n = 0
10 20 30 40
count = 4

Es un mismo programa con tres resultados, y los tres salen de la misma regla:

En el dibujo, ese parámetro no lleva un valor sino una flecha que apunta al arreglo:

Hay un solo arreglo, y está en el marco de main. Lo que la función tiene es una copia de la dirección. Si la función asignara un valor nuevo a values, main no se enteraría, igual que con n. Pero con values[i] = ... se llega a los elementos originales.

Comprobémoslo en gdb. Noten el tipo que reporta para values.

$ gcc -Wall -Wextra -std=c17 -g -O0 array_param.c -o build/array_param_gdb

$ gdb -q build/array_param_gdb
Reading symbols from build/array_param_gdb...
(gdb) break change_array
Breakpoint 1 at 0x828: file array_param.c, line 12.
(gdb) run
Starting program: .../build/array_param_gdb
en change_int: x = 99
1 2 3 4 

Breakpoint 1, change_array (values=0xfffffffffa18, n=4) at array_param.c:12
12	    for (int i = 0; i < n; i++) {
(gdb) info args
values = 0xfffffffffa18
n = 4
(gdb) whatis values
type = int *
(gdb) print values
$1 = (int *) 0xfffffffffa18
(gdb) print values[0]@4
$2 = {1, 2, 3, 4}
(gdb) up
#1  0x0000aaaaaaaa0960 in main () at array_param.c:33
33	    change_array(data, count);
(gdb) info locals
count = 4
data = {1, 2, 3, 4}
(gdb) whatis data
type = int [4]
(gdb) print sizeof(data)
$3 = 16
(gdb) down
#0  change_array (values=0xfffffffffa18, n=4) at array_param.c:12
12	    for (int i = 0; i < n; i++) {
(gdb) print sizeof(values)
$4 = 8
(gdb) continue
Continuing.
en change_array: n = 0
10 20 30 40 
count = 4
[Inferior 1 (process 173) exited normally]
(gdb) quit

gdb confirma el dibujo. En main, data es un arreglo de 4 int, de 16 bytes. En change_array, values es una dirección, de 8 bytes en este entorno, aunque lo hayamos escrito con corchetes. El tipo int * significa “dirección de un int”, y values[0]@4 le pide a gdb cuatro elementos desde ahí. Ese tipo tiene nombre, puntero (pointer), y es el tema de la próxima semana.

También explica por qué siempre pasamos la longitud por separado: sizeof no puede medir el arreglo dentro de la función. gcc incluso lo advierte:

$ gcc -Wall -Wextra -std=c17 errors/sizeof_param.c -o build/sizeof_param
errors/sizeof_param.c: In function 'show_size':
errors/sizeof_param.c:5:42: warning: 'sizeof' on array function parameter 'values' will return size of 'int *' [-Wsizeof-array-argument]
    5 |     printf("en la función: %zu\n", sizeof(values));
      |                                          ^
errors/sizeof_param.c:4:20: note: declared here
    4 | void show_size(int values[]) {
      |                ~~~~^~~~~~~~
$ build/sizeof_param
en main: 20
en la función: 8

Idea clave. C no tiene un caso especial para los arreglos al pasar parámetros: sigue copiando un valor. Lo especial es que el valor de un arreglo, en esa expresión, es su dirección.

struct: se copia todo, incluso un arreglo adentro

Aquí viene el caso en que más gente se equivoca. En la semana 12 de Introducción a la Computación vieron que asignar un struct copia todo y que un struct suelto llega a una función como copia. Eso sigue siendo cierto si el struct tiene un arreglo adentro. El arreglo se copia completo, elemento por elemento. En struct_copy.c:

struct row {
    int size;
    int cells[3];
};

void change_copy(struct row r) {
    r.cells[0] = 99;

struct row changed(struct row r) {
    r.cells[0] = 99;
    return r;
}

void change_cells(int cells[]) {
    cells[1] = 77;
}

struct row a = {3, {1, 2, 3}};

change_copy(a);
printf("en main: cells[0] = %d\n", a.cells[0]);

struct row b = changed(a);
printf("a: %d, b: %d\n", a.cells[0], b.cells[0]);

change_cells(a.cells);
printf("a.cells[1] = %d\n", a.cells[1]);

$ build/struct_copy
en change_copy: cells[0] = 99
en main: cells[0] = 1
a: 1, b: 99
a.cells[1] = 77

Sigamos cada línea con el modelo. Al pasar a, se copia todo el struct, y los dos marcos tienen un arreglo cada uno. No hay ninguna flecha. gdb lo confirma, con dos arreglos distintos:

$ gcc -Wall -Wextra -std=c17 -g -O0 struct_copy.c -o build/struct_copy_gdb

$ gdb -q build/struct_copy_gdb
Reading symbols from build/struct_copy_gdb...
(gdb) break change_copy
Breakpoint 1 at 0x7c0: file struct_copy.c, line 10.
(gdb) run
Starting program: .../build/struct_copy_gdb

Breakpoint 1, change_copy (r=...) at struct_copy.c:10
10	    r.cells[0] = 99;
(gdb) info args
r = {size = 3, cells = {1, 2, 3}}
(gdb) next
11	    printf("en change_copy: cells[0] = %d\n", r.cells[0]);
(gdb) print r
$1 = {size = 3, cells = {99, 2, 3}}
(gdb) up
#1  0x0000aaaaaaaa0884 in main () at struct_copy.c:26
26	    change_copy(a);
(gdb) print a
$2 = {size = 3, cells = {1, 2, 3}}
(gdb) continue
Continuing.
en change_copy: cells[0] = 99
en main: cells[0] = 1
a: 1, b: 99
a.cells[1] = 77
[Inferior 1 (process 186) exited normally]
(gdb) quit

La función changed muestra el camino de salida. Recibe su copia, la cambia y la devuelve. El valor devuelto, también completo, se copia en b. Una función de C no puede devolver un arreglo, pero sí un struct que tenga uno.

La última llamada, change_cells(a.cells), es diferente, aunque se parece. Lo que se pasa no es el struct, sino su campo cells, que es un arreglo. Entonces se aplica la regla de los arreglos, se copia la dirección, y el original sí cambia.

Error común. Decir que “los arreglos se pasan por referencia”, y por eso creer que un struct con un arreglo también. C no pasa nada por referencia: copia. Lo que hay que preguntarse es qué se copia.

Imágenes en PGM

Un píxel es un punto de una imagen. En una imagen en escala de grises, cada píxel es un número: 0 es negro, y el valor máximo es blanco. Una imagen es entonces una matriz de números, y ya saben manejar matrices.

El formato PGM de texto (también llamado P2) guarda esa matriz en un archivo de texto común, que se puede abrir con un editor. Este es lab/images/tiny.pgm:

$ cat lab/images/tiny.pgm
P2
# Tres columnas y dos filas, con un comentario.
3 2
255
0 10 20
30 40 50

Los saltos de línea no significan nada: los datos se separan con cualquier espacio. Lo que define dónde empieza cada fila es el ancho.

El módulo de imágenes

Un módulo es un grupo de funciones sobre un mismo tema, con una interfaz (interface), que dice lo que ofrece, y una implementación (implementation), que dice cómo lo hace. El nuestro viene en dos archivos, lab/image.h y lab/image.c. Cómo se arma un programa en varios archivos es el tema de la semana 6. Por ahora basta con esto: #include "image.h" permite usar las funciones del módulo, y el Makefile se encarga de compilar image.c junto con su programa.

Este es el tipo, que resume las decisiones de esta semana:

#define IMAGE_MAX_WIDTH 64
#define IMAGE_MAX_HEIGHT 64
#define IMAGE_MAX_VALUE 255

struct image {
    int width;
    int height;
    int max_value;
    int pixels[IMAGE_MAX_HEIGHT][IMAGE_MAX_WIDTH];
};

El tamaño de la matriz es fijo y siempre se reserva completo, aunque la imagen sea de 3 x 2. Los píxeles en uso son pixels[y][x], con y menor que height y x menor que width. Recuerden el orden: primero la fila. Es la misma idea de capacidad y longitud del vector de Introducción a la Computación. En la semana 5 quitaremos ese límite con memoria dinámica.

La interfaz completa:

Como no hemos visto punteros, image_load no tiene una forma directa de devolver dos cosas, la imagen y si funcionó. La solución es una convención: si algo falla, devuelve una imagen inválida, con width igual a 0. Quien llama lo revisa con image_is_valid. En show_sun.c:

struct image img = image_load("lab/images/sun.pgm");
if (!image_is_valid(img)) {
    fprintf(stderr, "No se pudo leer lab/images/sun.pgm\n");
    return 1;
}

$ build/show_sun
................................
................................
........@.......................
....@@@@@@@@@...................
...@@@@@@@@@@@..................
..@@@@@@@@@@@@@.................
...@@@@@@@@@@@..................
....@@@@@@@@@.................==
........@................=======
....................============
...............=================
..........======================
.....===========================
================================
================================
================================
Tamaño: 32 x 16

Es un sol a la izquierda y un cerro que sube hacia la derecha, dibujados a propósito para esta clase. El programa guardó también una copia. Fíjense que no es idéntica al original, aunque representa la misma imagen: image_save no conserva el comentario y escribe a su manera los saltos de línea.

$ head -5 build/sun_copy.pgm
P2
32 16
255
40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40
40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40

Leer el módulo

Lean image.c como aprendieron en la semana 2: primero la interfaz, luego qué llama a qué, y al final los detalles. La función más interesante es read_number, que entrega el siguiente número del archivo y se salta espacios y comentarios. Devuelve -1 si lo que sigue no es un número. Se puede usar -1 como aviso porque ningún dato válido de un PGM es negativo. Las pruebas de test_examples.py comprueban que el módulo rechaza los archivos con un formato distinto, con píxeles de menos, con un tamaño que no cabe o con un píxel mayor que el valor máximo.

En C. FILE *file es el mismo FILE * de Introducción a la Computación. const char name[] recibe la dirección de una cadena, y promete no cambiarla. El módulo no usa más punteros que esos. Y dos cosas que verán en el código y que se explican en la semana 6: static delante de una función no tiene que ver con el tiempo de vida, sino que dice que solo ese archivo la puede usar; y las líneas #ifndef, #define y #endif de image.h evitan que el encabezado se incluya dos veces.

Una imagen en el modelo

Con todo lo anterior, ya pueden predecir esto. image_demo.c tiene una función que recibe la imagen y otra que recibe una fila:

void paint_copy(struct image img) {
    img.pixels[0][0] = 99;

void paint_row(int row[], int width) {
    for (int x = 0; x < width; x++) {
        row[x] = 99;
    }
}

paint_copy(img);

paint_row(img.pixels[0], img.width);

img.pixels[0] es una fila de la matriz, y una fila es un arreglo de int. ¿Qué escribe el programa?

$ build/image_demo
sizeof(struct image) = 16396 bytes
3 x 2, max 255
   0  10  20
  30  40  50
En paint_copy, el primer píxel vale 99
Después de paint_copy:
3 x 2, max 255
   0  10  20
  30  40  50
Después de paint_row:
3 x 2, max 255
  99  99  99
  30  40  50

paint_copy trabajó sobre su copia. paint_row recibió la dirección de la fila 0 de la imagen de main, y la cambió. Y la primera línea tiene una consecuencia práctica: cada vez que se pasa o se devuelve una struct image, se copian 16396 bytes en este entorno, aunque la imagen tenga 6 píxeles. La razón se ve en gdb, si se detienen en paint_copy y piden la imagen: están los 6 píxeles en uso y, resumido, todo el espacio reservado que no se usa. Para mirar una imagen grande, conviene pedir un solo campo, como print img.width.

(gdb) print img
$1 = {width = 3, height = 2, max_value = 255, pixels = {{0, 10, 20, 
      0 <repeats 61 times>}, {30, 40, 50, 0 <repeats 61 times>}, {
      0 <repeats 64 times>} <repeats 62 times>}}

Copiar 16 KB funciona, pero es un desperdicio: se copia todo el espacio reservado, sea cual sea el tamaño de la imagen, y crecería si subiéramos el máximo. Por eso, la próxima semana reescribiremos los filtros para recibir la dirección de la imagen.

Filtros

Un filtro recibe una imagen y produce otra. Los nuestros siguen el mismo esquema, y el paso por valor lo hace muy limpio: el parámetro img ya es una copia, propia de la función, que se puede cambiar y devolver, y la imagen de quien llama queda intacta. Este es el filtro de modelo, en lab/filters.c:

struct image brighten(struct image img, int amount) {
    for (int y = 0; y < img.height; y++) {
        for (int x = 0; x < img.width; x++) {
            int value = img.pixels[y][x] + amount;
            if (value < 0) {
                value = 0;
            }
            if (value > img.max_value) {
                value = img.max_value;
            }
            img.pixels[y][x] = value;
        }
    }
    return img;
}

Fíjense en dos detalles. El ciclo llega hasta img.height y img.width, no hasta IMAGE_MAX_HEIGHT y IMAGE_MAX_WIDTH: la imagen puede ser más pequeña que el espacio reservado. Y el resultado se recorta para que no salga del rango, usando max_value y no un 255 escrito a mano.

Los filtros se llaman como cualquier función, y como devuelven una imagen, se pueden anidar: flip_horizontal(invert(img)). Según el modelo, cada llamada crea un marco con su propia copia de la imagen.

El problema de los bordes

Los tres primeros filtros del laboratorio transforman cada píxel mirando un solo lugar. box_blur, el desenfoque, es distinto: cada píxel pasa a ser el promedio de una ventana cuadrada a su alrededor, de lado 2 * radius + 1. En pseudocódigo:

algoritmo desenfocar(img, radio)
    resultado ← una copia de img
    para y desde 0 hasta alto - 1 hacer
        para x desde 0 hasta ancho - 1 hacer
            resultado[y][x] ← promedio de img en la ventana alrededor de (x, y)
        fin para
    fin para
    devolver resultado
fin algoritmo

Dos cosas pueden salir mal aquí. La primera: los promedios deben usar los valores originales. Por eso el algoritmo escribe en otra imagen. Si escribieran sobre img, cada píxel usaría a sus vecinos ya desenfocados, y el resultado sería otro.

La segunda es el borde. Con radius igual a 1, la ventana de un píxel en la esquina tiene 9 casillas, pero solo 4 están dentro de la imagen. ¿Qué se hace con las otras 5? Tomemos esta imagen de 3 x 3, y calculemos a mano el resultado en la esquina donde está el 90:

90   0   0
 0   0   0
 0   0   0

Ninguna es la única correcta, y cada programa de imágenes elige la suya. Lo que importa es decidirlo a propósito y saber qué produce. Tratar lo de afuera como 0 tiene un defecto visible: una imagen toda blanca quedaría con el borde oscuro. Dejar el borde sin cambiar deja un marco sin desenfocar. En este laboratorio usamos la última regla, promediar solo las casillas que existen, con la división entera de C. Es simple, no oscurece el borde, y las pruebas la comprueban.

Error común. Recorrer la ventana sin comprobar los límites de la imagen. Con x - 1 igual a -1, el sanitizer avisa, porque el índice se sale de la fila. Pero con x + 1 igual a width, en una imagen más angosta que 64, el índice sigue dentro del arreglo: nadie avisa, y se lee un 0 que no es parte de la imagen. Las herramientas protegen el espacio reservado, no la imagen. Por eso las pruebas incluyen una imagen uniforme, que debe quedar igual.

Esto debe producir su filtro con radius igual a 2 sobre el sol, al final de la salida de filter_demo:

box_blur 2:
................................
...:::-----:::..................
..::-=======-::.................
.:-=++*****++=-:................
.:-+*#######*+-:................
.:=+#%@@@@@%#+=:................
.:-+*#######*+-:...........:::::
.:-=++*****++=-:......::::::::--
..::-=======--::.::::::::-------
...:::------::::::::--------====
......:::::::::--------=========
::::::::::--------==============
:::::--------===================
--------========================
----============================
================================

El laboratorio, paso a paso

Los archivos de partida están en code/week-03/lab, y su README.md tiene las preguntas de la sesión 1 y lo que pide cada parte. make test-lab comprueba los filtros: falla hasta que terminen. Aquí están las ideas, no el código.

Sesión 1: marcos y lectura

Los programas frames_calls.c, frames_static.c y frames_array.c ponen a prueba cada regla del modelo. El método es siempre el mismo: primero el dibujo en papel, sin ejecutar, y luego gdb. Si copian lo que gdb muestra y después hacen el dibujo, no aprenden nada, porque no hubo predicción que pudiera fallar. make gdb los compila en build/gdb/, con -g -O0.

Después lean el módulo y respondan las preguntas del README.md. Las van a necesitar: este mismo módulo va a ir cambiando en las semanas 4, 5 y 6, y en la semana 10 lo van a extender.

Sesión 2: los filtros

lab/filters.h dice exactamente qué debe hacer cada filtro. Antes de escribirlo, calculen a mano un caso en lab/filter_tests.c. Con imágenes pequeñas, de 3 x 2 por ejemplo, el resultado se calcula en un minuto, y una imagen que no es cuadrada descubre si se confundieron width y height.

Lo que debe cuidar cada uno:

• invert usa max_value, no 255.
• threshold: un píxel igual a level pasa a max_value. Pruébenlo con ese caso exacto.
• flip_horizontal: si intercambian en el mismo arreglo, el ciclo llega solo hasta la mitad de la fila. Si recorren toda la fila, cada par se intercambia dos veces y la imagen queda igual. Si prefieren, escriban en una imagen aparte. Pruébenlo con ancho par y con ancho impar.
• box_blur: conviene una función auxiliar que promedie una ventana. Lean otra vez la sección de los bordes, y empiecen por una imagen con un solo píxel distinto de 0, como la de arriba.

Resumen

• El modelo de entornos sirve para predecir un programa sin ejecutarlo. Cada llamada crea un marco, con sus parámetros y variables locales. Al retornar, el marco desaparece.
• Las cuatro reglas: al llamar, se copian los argumentos en un marco nuevo. Un nombre se busca, entre los ya declarados, en el bloque actual, en los bloques que lo rodean y fuera de toda función, nunca en el marco de otra llamada. Asignar cambia solo esa casilla. Al retornar, el valor vuelve al punto de la llamada.
• La pila es la secuencia de marcos. Si main llama a f y f llama a g, dentro de g existen los tres marcos, pero solo se pueden usar los nombres de g.
• El alcance es dónde se puede usar un nombre. El tiempo de vida es cuánto existe el dato.
• Una local static conserva el alcance de su bloque, pero vive todo el programa, fuera de la pila, y se inicializa una sola vez, antes de empezar.
• Las constantes globales están permitidas. Las variables globales, no. #define reemplaza texto, y const int es una variable de solo lectura.
• C siempre copia el valor del argumento. Un int se copia. De un arreglo se copia la dirección, y por eso la función puede cambiar sus elementos. Un struct se copia completo, incluso con un arreglo adentro.
• En gdb: backtrace muestra la pila, frame y up eligen un marco, e info args e info locals muestran sus variables. La línea que muestra todavía no se ejecutó.
• Una imagen PGM de texto es una matriz de números con un encabezado pequeño. struct image tiene un tamaño máximo fijo, y una imagen inválida, con width igual a 0, es la forma de avisar que algo falló.
• box_blur debe leer los valores originales y debe decidir qué hacer en los bordes.

Ejercicios

Dibujen primero y ejecuten después. Todo programa revisa sus lecturas y compila sin advertencias.

1. Sin compilar, dibujen la pila cuando corre g, y digan qué se imprime. Luego compruébenlo en gdb.

   int g(int y) { y = y + 1; return y * 2; }
   int f(int x) { int y = g(x); x = x + y; return x; }
   int main(void) { int x = 3; int y = f(x); printf("%d %d\n", x, y); return 0; }

2. ¿Qué diferencia hay entre el alcance y el tiempo de vida de una variable static local? Respondan con un ejemplo de dos líneas en las que el dato exista y su nombre no se pueda usar.

3. Sin compilar, digan si cada fragmento compila. Si compila, digan qué escribe. Luego compruébenlo.

   a) int x = 1; { int x = x + 1; printf("%d", x); }
   b) int x = 1; { x = x + 1; int x = 5; printf("%d", x); } printf("%d", x);
   c) for (int i = 0; i < 2; i++) { int n = 0; n++; printf("%d", n); }
   d) for (int i = 0; i < 2; i++) { static int n = 0; n++; printf("%d", n); }

   El caso a) es una trampa. Piensen en dónde empieza el alcance de la x de adentro, y qué dice -Wall -Wextra.

4. Escriban int next_id(void), que devuelva 1, 2, 3 en llamadas sucesivas, usando una local static. Luego escriban int next_id_from(int last), que haga lo mismo sin static. ¿Cuál de las dos es más fácil de probar con assert, y por qué?

5. Corran gdb sobre static_counter, y usen break count_local. ¿Qué muestra info locals antes de la línea int calls = 0;? ¿Por qué gdb sí se detiene en esa línea, y en count_static no?

6. Sin compilar, digan qué escribe cada printf, y dibujen los marcos justo antes de retornar de h. Después compruébenlo.

   void h(int a[], int b) { a[0] = a[0] + b; b = b + 1; a[1] = b; }
   int main(void) { int v[2] = {1, 2}; int w = 10; h(v, w); printf("%d %d %d\n", v[0], v[1], w); return 0; }

7. Definan struct pair { int values[2]; };. Escriban una función swap_values que de verdad intercambie los dos elementos para quien llama, sin declarar punteros. ¿Qué debe recibir y qué debe devolver? Hay dos respuestas correctas: den las dos.

8. En el dibujo de change_array, ¿qué cambiaría si la función hiciera int local[4], y copiara ahí los elementos antes de multiplicarlos? ¿Lo vería main? Reescríbanla así y compruébenlo.

9. Escriban struct image crop(struct image img, int left, int top, int width, int height), que recorta un rectángulo. Decidan qué devuelve si el rectángulo no cabe en la imagen. Pruébenla con una imagen de 3 x 2.

10. Escriban struct image flip_vertical(struct image img), y una prueba que compruebe que aplicarla dos veces da la imagen original. ¿Por qué esa prueba sola no basta? Muestren una implementación incorrecta que la pase.

11. Escriban struct image rotate_90(struct image img), que gira la imagen en el sentido de las agujas del reloj. Una imagen de 3 x 2 debe quedar de 2 x 3. ¿Por qué aquí no se puede escribir sobre img?

12. Cambien box_blur para usar otra regla de bordes de la tabla, y comparen su salida con la del laboratorio sobre lab/images/sun.pgm. ¿Cuál se nota más? Luego cuenten cuántas struct image se pasan a un parámetro en box_blur(flip_horizontal(invert(img)), 1), sin contar lo que pase dentro de box_blur. ¿Cuántos bytes son en total? ¿Esa cantidad depende del tamaño de la imagen o del tamaño máximo?