C Piscine — C 11

Punteros a función: pasar comportamiento como argumento. Ocho ejercicios que construyen, a mano, las piezas que en cualquier lenguaje moderno se llaman map, filter, any y sort — y un mini-intérprete de operadores resuelto con una tabla de funciones.

La idea que atraviesa el módulo — Hasta aquí una función era algo que llamabas. En C 11 una función pasa a ser un valor: se guarda en una variable, se mete en un array, se pasa como argumento. La sintaxis void (*f)(int) se lee «puntero a una función que toma un int y no devuelve nada». En cuanto lo tienes, puedes escribir código que decide qué hacer sin saber cómo se hace: eso es la genericidad, y es la base de los callbacks, de qsort y de cualquier event loop.

GGlosario de teoría

C 11 trae vocabulario nuevo: funciones que se pasan como datos, predicados, comparadores y tablas de funciones. Aquí está cada término explicado desde cero y con un ejemplo sacado del propio módulo. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.

Funciones como valores

Puntero a función

El código de una función compilada vive en memoria igual que los datos, así que tiene una dirección. Un puntero a función es una variable que guarda esa dirección. Con él puedes llamar a la función sin escribir su nombre: la decides en tiempo de ejecución, no al escribir el código.

En C el nombre de una función, usado sin paréntesis, ya es su dirección. Por eso el enunciado de ex00 escribe ft_foreach(tab, 1337, &ft_putnbr), pero ft_foreach(tab, 1337, ft_putnbr) es exactamente lo mismo. Y dentro, f(tab[i]) y (*f)(tab[i]) también son equivalentes: el compilador acepta las dos formas.

Cómo leer int (*f)(int, int)

Se lee desde el nombre hacia fuera: f es… (*f) un puntero… a una función que recibe (int, int)… y devuelve int. Los paréntesis alrededor de *f son obligatorios: sin ellos, int *f(int, int) declara una función llamada f que devuelve un int *, que es otra cosa.

En el módulo salen cuatro formas: void (*f)(int) (ex00, no devuelve nada), int (*f)(int) (ex01, devuelve el valor transformado), int (*f)(char *) (ex02 y ex03, responde sí o no sobre una cadena) e int (*cmp)(char *, char *) (ex07, compara dos cadenas). El tipo del puntero tiene que coincidir con el de la función que le pasas: a ft_foreach no le puedes dar una función que reciba un char *.

Callback (función de retrollamada)

Una función que tú le das a otra para que ella la llame cuando toque. Tú no decides cuándo se ejecuta ni con qué argumento: eso lo decide la función que la recibe. El nombre viene del inglés call back, «devolver la llamada».

En C 11 todos los f y cmp son callbacks. ft_foreach no sabe qué hace f; solo la llama una vez por elemento, en orden. Con un f que imprime, imprime la tabla; con uno que suma en una variable global, la suma.

Función de orden superior: map, filter, any

Una función que recibe otra función como argumento (o la devuelve). Los lenguajes modernos traen varias hechas, y C 11 te hace escribir sus equivalentes:

EjercicioQué haceEn Python
ft_foreachaplica f a cada elementofor x in tab: f(x)
ft_maptabla nueva con f(x) de cada unomap(f, tab)
ft_any¿alguno cumple f?any(map(f, tab))
ft_count_ifcuántos cumplen fsum(1 for x in tab if f(x))
ft_advanced_sort_string_tabordena según cmpsorted(tab, key=…)
Predicado

Una función que responde sí o no sobre un elemento. En C no hay tipo booleano en la piscine, así que el convenio es: 0 es «no» y cualquier otro valor es «sí». Fíjate en que el enunciado de ex02 no dice «devuelve 1», dice «devuelve algo diferente de 0».

Es el f de ft_any y ft_count_if. Un predicado posible: «la cadena empieza por mayúscula». Con {"hola", "Adiós", "Sí", NULL}, ft_any devuelve 1 al llegar a "Adiós" y ft_count_if con length 3 devuelve 2.

Comparador y convenio de signo

Una función que recibe dos elementos y dice cómo están entre sí con el signo de lo que devuelve: negativo si el primero va antes, 0 si son iguales y positivo si el primero va después. No importa el valor exacto, solo el signo: strcmp puede devolver −1 o −32 y significa lo mismo.

Es el f de ft_is_sort y el cmp de ex07. Para enteros, el comparador más corto es return (a - b);, que vale para números pequeños pero puede desbordar con valores extremos (INT_MIN - 1); el seguro es return ((a > b) - (a < b));.

Tabla de punteros a función (dispatcher)

Un array cuyos elementos son punteros a función, a menudo emparejados con una clave. En vez de escribir un if por caso, se busca la clave en la tabla y se llama a la función que la acompaña. Repartir así el trabajo según una clave se llama dispatch.

Es lo que pide do-op: la tabla ops[] tiene cinco filas como {"+", &ft_add}, y el bucle compara el operador con cada sym hasta dar con el bueno. Si ninguno coincide, se devuelve 0, que es justo lo que pide el enunciado para un operador desconocido.

struct y typedef

Un struct agrupa varias variables de tipos distintos bajo un nombre: t_op junta un char *sym y un int (*f)(int, int). Se accede a cada campo con un punto: ops[i].sym, ops[i].f. Un typedef le da un nombre corto al tipo, para escribir t_op en vez de struct s_op.

La Norma fija los nombres: los struct empiezan por s_ y los typedef por t_. Lo mismo verás en C 12 con t_list.

Tablas y memoria

char **: una tabla de cadenas

Una cadena en C es un char *: la dirección de su primer carácter. Una tabla de cadenas es entonces un array de char *, y su dirección es un char **. tab[i] es la cadena i (un char *) y tab[i][0] su primer carácter.

Lo importante para ex06 y ex07: la tabla solo guarda direcciones. Las letras están en otro sitio. Por eso intercambiar tab[i] y tab[i + 1] cambia el orden de las cadenas sin mover ni una letra.

Tabla terminada en NULL frente a tabla con length

Una función que recibe una tabla tiene que saber dónde acaba. Hay dos formas: que le pasen el tamaño (length), o que el último elemento sea un valor especial que marca el final, un centinela. Para tablas de punteros el centinela es NULL, igual que el '\0' lo es para las cadenas.

El módulo usa las dos: ft_count_if recibe length y recorre con i < length; ft_any, ft_sort_string_tab y ft_advanced_sort_string_tab no lo reciben y paran en while (tab[i]). Si alguien te pasa una tabla sin el NULL final, el bucle sigue leyendo memoria que no es suya.

malloc, el heap y quién libera

malloc(n) pide n bytes al sistema en el heap, una zona de memoria que no desaparece al salir de la función, y devuelve su dirección, o NULL si no hay memoria. Lo que se reserva con malloc se queda reservado hasta que alguien llama a free con esa dirección; si nadie lo hace, es una fuga de memoria (leak).

ft_map tiene que usar malloc porque devuelve una tabla nueva: un array local (int res[length]) moriría al hacer return. Reserva sizeof(int) * length bytes, comprueba el NULL y devuelve la tabla. El free no es suyo: lo hará quien la reciba cuando ya no la use.

Algoritmos y comportamiento

Cortocircuito (salir en cuanto se sabe)

Dejar de trabajar en cuanto el resultado ya está decidido. Los operadores && y || de C lo hacen solos: en a || b, si a es cierto, b ni se evalúa.

ft_any lo hace a mano con el return (1) dentro del bucle: si el primer elemento cumple f, el resto no se mira. ft_count_if no puede hacerlo, porque para contar hay que verlos todos. En el peor caso los dos recorren la tabla entera.

Ordenación por intercambio de vecinos (burbuja)

Se comparan dos vecinos y, si están al revés, se intercambian. Repitiendo eso hasta que no quede ninguna pareja al revés, la tabla queda ordenada. Es el método de la burbuja: fácil de escribir y de razonar, pero lento con tablas grandes, porque hace del orden de n² comparaciones.

El fragmento de ex06 es una variante: tras cada intercambio vuelve a i = 0 y empieza de nuevo. Es correcto (solo termina cuando recorre la tabla sin encontrar ninguna pareja al revés), aunque más lento que la burbuja clásica, que sigue avanzando después de intercambiar.

Orden ASCII y strcmp

Cada carácter es un número (su código ASCII): 'A' es 65, 'Z' 90, 'a' 97. Ordenar «por código ASCII» es comparar las cadenas carácter a carácter con esos números, que es lo que hace strcmp: avanza mientras sean iguales y devuelve la diferencia del primer carácter distinto.

Consecuencias que sorprenden: todas las mayúsculas van antes que todas las minúsculas ("Zorro" antes que "abeja"), las cifras antes que las letras, y una cadena va antes que las que la continúan ("ab" antes que "abc", porque su '\0' vale 0).

qsort

La función de ordenación de la biblioteca estándar de C (<stdlib.h>). Ordena cualquier array porque no sabe qué hay dentro: recibe la dirección, cuántos elementos hay, cuánto mide cada uno y un comparador con el convenio de signo de siempre. No se puede usar en la piscine, pero su diseño es el de ex07: el algoritmo es fijo y el criterio llega de fuera.

El programa do-op

argc y argv

Los argumentos de main(int argc, char **argv). argc cuenta las palabras de la línea de órdenes, incluido el nombre del programa, y argv es la tabla de esas palabras como cadenas, terminada en NULL. Con ./do-op 42 "+" 21, argc vale 4 y argv[2] es "+".

Por eso la primera comprobación de do-op es argc != 4: entonces no se muestra nada. Y como todo llega como texto, "42" hay que convertirlo a número a mano.

atoi tolerante

El ft_atoi de C 04 convierte texto en int con unas reglas fijas: se salta los espacios iniciales, lee cualquier cantidad de + y - (cada - cambia el signo), lee cifras y se para en el primer carácter que no lo sea, sin dar error.

Con esas reglas salen los ejemplos del enunciado: 42amis vale 42, --+-20toto12 vale −20 (tres -, impar, negativo), y toto3 vale 0 porque no empieza por cifra. Por eso ./do-op 1 + toto3 da 1.

División por cero y SIGFPE

Dividir un entero entre 0 en C es comportamiento indefinido: el lenguaje no dice qué pasa. En los Linux de 42 (procesadores x86) el procesador lo detecta y el sistema mata el programa con la señal SIGFPE (floating point exception, aunque no haya ningún float). Lo mismo con %.

No hay forma de «capturar» el error después con un if: cuando se ejecuta la división ya es tarde. Por eso do-op mira b == 0 antes de llamar a la función y escribe Stop : division by zero o Stop : modulo by zero. Hay un segundo caso que también da SIGFPE: -2147483648 / -1, porque el resultado no cabe en un int. Compilado con cc, ese programa termina con código 136 (128 + 8, el número de SIGFPE).

Makefile

Un archivo de reglas para make: qué se construye, a partir de qué archivos y con qué orden. make solo recompila lo que ha cambiado. Las reglas habituales en 42 son all, clean (borra los .o), fclean (borra también el ejecutable) y re.

En ex05 el enunciado no da lista de archivos («todos los necesarios») y su ejemplo de prueba empieza con make clean y make: la Moulinette compila do-op con tu Makefile, así que tiene que existir y producir un ejecutable que se llame exactamente do-op.

ex00ft_foreach

Entregable: ft_foreach.cAutorizadas: ninguna

Aplicar una función a cada entero de la tabla, en orden.

void	ft_foreach(int *tab, int length, void (*f)(int))
{
	int	i;

	i = 0;
	while (i < length)
	{
		f(tab[i]);
		i++;
	}
}
Qué te obliga a aprender — Que el bucle y la acción son cosas separables. ft_foreach es el bucle; f es la acción, y llega de fuera. El mismo recorrido sirve para imprimir, para sumar o para lo que sea, sin tocar ft_foreach. Es el patrón iterador + callback en su forma más pura.

ex01ft_map

Entregable: ft_map.cAutorizadas: malloc

Como foreach, pero f devuelve un valor y se acumula todo en una tabla nueva que se retorna.

int	*ft_map(int *tab, int length, int (*f)(int))
{
	int	*res;
	int	i;

	res = malloc(sizeof(int) * length);
	if (!res)
		return (NULL);
	i = 0;
	while (i < length)
	{
		res[i] = f(tab[i]);
		i++;
	}
	return (res);
}
Qué te obliga a aprender — La diferencia entre transformar en el sitio y producir algo nuevo. map no toca la tabla original: reserva memoria y devuelve otra. Aparece aquí la responsabilidad del malloc (comprobar el NULL) y la regla implícita: quien reserva, avisa; el free lo hará quien reciba la tabla.

ex02ft_any

Entregable: ft_any.cAutorizadas: ninguna

Devuelve 1 si algún elemento hace que f devuelva algo distinto de 0. La tabla acaba en NULL.

int	ft_any(char **tab, int (*f)(char *))
{
	int	i;

	i = 0;
	while (tab[i])
	{
		if (f(tab[i]))
			return (1);
		i++;
	}
	return (0);
}
Qué te obliga a aprender — f aquí es un predicado: una función que responde sí/no sobre un elemento. Y el return (1) en cuanto encuentra uno es la evaluación en cortocircuito: no hace falta mirar el resto. Es exactamente el any() de Python o el some() de JavaScript.

ex03ft_count_if

Entregable: ft_count_if.cAutorizadas: ninguna

Cuenta cuántos elementos cumplen el predicado f.

int	ft_count_if(char **tab, int length, int (*f)(char *))
{
	int	i;
	int	count;

	i = 0;
	count = 0;
	while (i < length)
	{
		if (f(tab[i]))
			count++;
		i++;
	}
	return (count);
}
Qué te obliga a aprender — El mismo predicado de ft_any, pero ahora sin cortocircuito: hay que recorrerlo entero. Es la pareja filtrar + contar. Cambiando solo la función que pasas, la misma rutina cuenta pares, positivos o palabras que empiezan por vocal: la lógica del recuento no sabe nada del criterio.

ex04ft_is_sort

Entregable: ft_is_sort.cAutorizadas: ninguna

Devuelve 1 si la tabla está ordenada según el comparador f (negativo si el primero es menor, 0 si iguales, positivo si mayor).

int	ft_is_sort(int *tab, int length, int (*f)(int, int))
{
	int	i;
	int	up;
	int	down;

	i = 0;
	up = 1;
	down = 1;
	while (i < length - 1)
	{
		if (f(tab[i], tab[i + 1]) > 0)
			up = 0;
		if (f(tab[i], tab[i + 1]) < 0)
			down = 0;
		i++;
	}
	return (up || down);
}
Qué te obliga a aprender — Aquí f no es un predicado sino un comparador: no dice sí/no, dice «menor, igual o mayor», con el mismo convenio de signo que strcmp. Y una decisión de diseño: «ordenada» debería valer tanto para ascendente como descendente, así que llevamos dos banderas (up, down) y damos por buena la tabla si alguna se mantiene. Ese convenio de signo es el que luego usa qsort.

ex05do-op

Entregable: programa do-opAutorizadas: write

Un programa ./do-op valor1 operador valor2 que aplica + - * / %. Operador desconocido → 0; número de argumentos incorrecto → nada; división o módulo por cero → mensaje. El enunciado pide explícitamente resolverlo con una tabla de punteros a función.

typedef struct s_op
{
	char	*sym;
	int		(*f)(int, int);
}	t_op;

/* ... se rellena ops[] con {"+", &ft_add}, {"-", &ft_sub}, ... */
while (i < 5)
{
	if (!ft_strcmp(ops[i].sym, op))
		return (ops[i].f(a, b));
	i++;
}
return (0);   /* operador desconocido: el resultado es 0 */

Dos trampas del enunciado, visibles en sus ejemplos:

Qué te obliga a aprender — Que una tabla de punteros a función es un dispatcher: sustituye una escalera de if/else por una búsqueda en datos. Añadir un operador es añadir una fila, no tocar la lógica. Así funcionan por dentro los intérpretes, las máquinas virtuales y las tablas de syscalls del kernel. La Norma, además, empuja a trocearlo en ficheros (máx. 5 funciones cada uno) con un Makefile que los enlaza.

ex06ft_sort_string_tab

Entregable: ft_sort_string_tab.cAutorizadas: ninguna

Ordena por código ASCII un array de cadenas terminado en NULL, intercambiando los punteros de la tabla (nunca copiando las cadenas).

if (ft_strcmp(tab[i], tab[i + 1]) > 0)
{
	tmp = tab[i];
	tab[i] = tab[i + 1];
	tab[i + 1] = tmp;
	i = 0;
}
Qué te obliga a aprender — Que ordenar no es mover datos, es mover referencias. Las cadenas se quedan donde están en memoria; lo único que baraja el algoritmo son los punteros del array. Intercambiar tres char * es barato; copiar cadenas enteras sería caro e innecesario. Es la misma razón por la que se ordenan índices o punteros, no registros completos.

ex07ft_advanced_sort_string_tab

Entregable: ft_advanced_sort_string_tab.cAutorizadas: ninguna

Igual que el anterior, pero el criterio de orden llega como parámetro. Pasándole ft_strcmp se obtiene el mismo resultado que ft_sort_string_tab.

void	ft_advanced_sort_string_tab(char **tab, int (*cmp)(char *, char *))
{
	/* ... mismo bucle, pero comparando con cmp(tab[i], tab[i + 1]) ... */
}
Qué te obliga a aprender — El paso final de la abstracción: sacar el criterio fuera del algoritmo. El mismo ordenador sirve para orden ASCII, por longitud o inverso; solo cambia la función que le pasas. Esto es, literalmente, la firma de qsort de la librería estándar: void qsort(void *, size_t, size_t, int (*)(const void *, const void *)). Acabas de reinventarla.

?Preguntas probables de la evaluación

Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado. Están agrupadas en: punteros a función, casos límite, do-op y entrega. Antes de mirar la respuesta, intenta contestar tú.

Punteros a función

¿Qué es exactamente void (*f)(int)? ¿Y si quito los paréntesis?

Un parámetro f que es un puntero a una función que recibe un int y no devuelve nada. Sin los paréntesis, void *f(int) sería una función que devuelve un void *, no un puntero a función. → cómo leer la declaración, ex00

¿Hace falta el & en &ft_putnbr? ¿Y el * al llamar?

No. El nombre de una función ya es su dirección, así que ft_putnbr y &ft_putnbr son lo mismo, igual que f(x) y (*f)(x). → puntero a función

¿En qué se diferencian ft_any y ft_count_if, aparte del resultado?

ft_any para en cuanto encuentra uno (cortocircuito) y sabe dónde acaba la tabla por el NULL final; ft_count_if recorre siempre los length elementos, porque para contar hay que verlos todos. → ex02, ex03

Casos límite

¿ft_is_sort da 1 con una tabla descendente? ¿Y con todos iguales o vacía?

Sí a las tres. Con {3, 2, 1} se mantiene down; con {2, 2, 2} el comparador da siempre 0 y no apaga ninguna bandera; con length 0 o 1 el bucle no entra. Solo {1, 3, 2} (sube y baja) da 0. Comprobado compilando el código de la tarjeta. → ex04

¿Qué pasa con ft_map si length es 0?

malloc(0) puede devolver NULL o una dirección válida que no se puede usar: depende del sistema. En los dos casos el bucle no entra y la función no rompe; quien llame no debe leer nada de la tabla, y si no es NULL, debe liberarla igual. → malloc

¿Quién libera la tabla de ft_map? ¿Tiene leaks?

La función no puede liberarla, porque la devuelve. La libera quien la recibe, con un free cuando ya no la use; si no, sí habría una fuga, pero en el programa que llama, no en ft_map. → ex01

do-op

¿Por qué una tabla de punteros a función y no cinco if?

Porque el enunciado lo pide, y porque añadir un operador es añadir una fila (un t_op) a ops[] sin tocar el bucle. El caso «operador desconocido → 0» sale solo: si ninguna fila coincide, se llega al return (0). → dispatcher, ex05

¿Cómo evitas que ./do-op 25 / 0 rompa el programa?

Comprobando que el segundo número es 0 antes de dividir, y escribiendo el mensaje en su lugar. Si se divide, el programa muere con SIGFPE y ya no se puede arreglar. Punto débil para tener preparado: -2147483648 / -1 también da SIGFPE y el enunciado no lo menciona. → SIGFPE

¿Por qué ./do-op 42amis - --+-20toto12 da 62?

Porque los números se leen con el ft_atoi de C 04: 42amis es 42 (para en la a) y --+-20toto12 es −20 (tres -, para en la t). 42 − (−20) = 62. → atoi tolerante

Entrega, Norma y Moulinette

¿Qué entregas en ex05 y qué funciones puedes usar?

Todos los archivos que necesite el programa más un Makefile que genere do-op, porque la Moulinette hace make clean y make. Solo está autorizada write: nada de printf ni atoi, así que el ft_putnbr, el ft_atoi y el ft_strcmp son tuyos. Y como es un programa, aquí sí va un main. → Makefile, ex05

En ex06, ¿por qué intercambias punteros y no copias las cadenas?

Porque lo exige el enunciado («intercambiando los punteros de la tabla») y porque es más barato: tres asignaciones de char * en vez de copiar letras, que además podría no caber si las cadenas miden distinto. → char **, ex06