:xrefstyle: short :figure-caption: Figura :figure-refsig: Fig. :listing-caption: Listado :stem: [[procedural_programming]] == Programación procedimental . Ideal del paradigma: control, necesario para aplicaciones de tiempo real y sistemas operativos . Diseño: los 8 tipos de instrucciones . Comentarios El proceso de resolución de problemas, que consta de: *Análisis*. Comprender el problema. Se recomienda rotular cada trozo de la entrada y salida con los nombres con que el cliente los llama. Como prueba, el estudiante debe estar seguro de que comprende _qué_ debe hacer el programa y saber qué es cada trozo de información de la entrada y de la salida. *Diseño*. Resolver el problema. Se recomienda al estudiante resolver el problema, traduciendo de la entrada a la salida, sin pensar en computadoras. Debe usar sus habilidades humanas y matemáticas. No se puede instruir una computadora si no se sabe resolver el problema como humano. Luego de resolver el problema como humano, escribir un diseño siguiendo las convenciones del paradigma de programación usado. Para el paradigma de programación procedimental consiste en escribir un algoritmo usando los ocho tipos de instrucciones: 1. Leer un valor(es) 2. Imprimir un valor(es) 3. Crear una variable con un valor 4. Cambiarle el valor a una variable 5. Condicionar una instrucción(es) 6. Repetir una instrucción(es) 7. Hacer una subtarea 8. Definir una subtarea La fase de diseño es la más difícil del proceso, y la que más caracteriza al trabajo ingenieril. Una vez elaborado el algoritmo, se debe probar. El estudiante puede ejecutar el algoritmo paso a paso al pie de la letra, anotando en una tabla los valores de las variables, marcando con un cursor la entrada, y escribiendo los resultados en un texto de salida. Cuando el algoritmo resuelva el problema se pasa a la siguiente fase. *Implementación*. Consiste en traducir instrucción por instrucción a un lenguaje de programación que se apegue al paradigma. Requiere mucho dominio del lenguaje de programación, y se considera la fase más fácil del proceso, a veces conocida como "codificación". Cuando el programa está implementado, se prueba contra usando algún mecanismo de pruebas de software (testing). En este curso se usa pruebas de caja negra apoyados por un juez automático en línea. El siguiente ejemplo recorre todas las fases del proceso descrito. === Entrada y salida . Concepto de programa . Concepto de archivo y cursor . Salida estándar [TIP] ==== Objetivos de la programación competitiva. Registrarse en UVa, Kattis . link:https://open.kattis.com/problems/hello[Hello World!] ==== . Error estándar . Salida con formato . Concepto de tipo de dato (conjunto) . Concepto de valor literal y constante nombrada . Concepto de variable y su relación con la memoria . Cuatro tipos de uso de memoria en la máquina: variable, indirección, arreglo y registro . Tabla con los tipos de datos . Entrada estándar . Argumentos de línea de comandos . Entrada con formato . Fallos de lectura . Prob: Replicador de la entrada? . Ejemplos de lectura e impresión de diferentes tipos de datos: ej char e int . Cambio de tipos . Makefile . Compiladores de C === Expresiones y condicionales //// . Definición de expresión (ya se vio qué es valor) . Operadores . Prioridad de operadores . Asociatividad de operadores . Aridad de operadores . Evaluación recursiva . Prob: Validador de ensayos //// Prediga la salida de las siguientes instrucciones. [source,c] ---- include::expr_cond/incr_decr/main.c[] ---- === Repetición con ciclos [#fig_repetition_types] .Tipos de repetición image::loops/repetition_types.svg[Tipos de repetición] . Ciclo por contador . Ciclo por condición . Ciclo por colección === Subrutinas Tipos de subrutinas [#fig_subroutine_types] .Tipos de subrutinas image::subroutines/subroutine_types.svg[Tipos de subrutinas] . Interfaz e implementación . Diseño por contratos . Programación defensiva ==== Compilador: unidades de traducción El siguiente diagrama ilustra el proceso de compilación, preprocesamiento, y enlazado de ejecutables, bibliotecas estáticas y dinámicas. Cada archivo fuente (`.c` o `.cpp`) es una unidad de traducción independiente, incluso aunque el compilador se invoque con varios de ellos en los argumentos de línea de comandos. [#fig_compilation_process] .Proceso de compilación image::subroutines/compilation_process.svg[Proceso de compilación] ==== Bibliotecas estáticas y dinámicas Los siguientes comandos resumen la forma de crear y compilar con bibliotecas estáticas y dinámicas de software en C. La opción `-fPIC` pide al compilador generar código independiente de la posición (dirección de memoria) donde se encuentre en el segmento de código (PIC, _Position-Independent Code_). [source,sh,linenums] ---- include::subroutines/libraries.sh[] ---- Un ejecutable que depende de una biblioteca dinámica, guarda dentro la ruta hacia la biblioteca. Si esta se encuentra en una ruta estándar como `/usr/lib` o `/usr/local/lib`, el programa correrá con una invocación normal no importa dónde se encuentre el programa dentro del sistema de archivos. Si la biblioteca está en otra carpeta y el programa se mueve de lugar, por ejemplo, tras una instalación, se romperá el enlace. Se puede indicar temporalmente al sistema operativo dónde se encuentra la biblioteca con la variable de ambiente `LD_LIBRARY_PATH`, algo como: [source,sh] ---- LD_LIBRARY_PATH=/path/to/lib /path/to/my/executable args ---- La segunda forma es generar un ejecutable que guarde la referencia a la ubicación donde estará la biblioteca. El _linker_ (`ld`) tiene el parámetro `-rpath` que indica la ruta de ejecución (_runtime path_) donde el ejecutable buscará bibliotecas dinámicas. Dado que no llamamos directamente al linker, sino a través del compilador, necesitamos entonces que el compilador pase parámetros específicos al linker. GCC ofrece este servicio con el parámetro `-Wl`, y los argumentos para el linker se separan por comas en lugar de espacios. Por ejemplo, para decirle al linker que genere un ejecutable que busque la biblioteca dinámica en la misma carpeta donde se encuentra el ejecutable: [source,sh] ---- # Dynamic linking gcc -c -Wall -Wextra -std=c11 main.c -o main.o gcc -Wall -Wextra -std=c11 main.o -o myapp mylib_dir/libmylib.so -Wl,-rpath,'$$ORIGIN' # or gcc -Wall -Wextra -std=c11 main.o -o myapp -lmylib -L/mylib_dir -Wl,-rpath,'$$ORIGIN' ---- // TODO(jhc): probar esos comandos previos . Metaprogramación . Crear una biblioteca que resuelva el problema de link:procedural/subroutines/triangle_inequality[Desigualdad triangular^]. Cree dos programas, uno clasificador de triángulos que pase los casos de prueba. Otro programa de caja blanca. El código compartido por ambos programas debe estar en una biblioteca reutilizable de C. [[indirection_array_matrix]] === Indirección, arreglos y matrices [[indirection]] ==== Indirección (punteros) [#fig_airport_pointer_metaphor] .Metáfora de la señal de tránsito para un puntero image::indirection/airport_pointer_metaphor.png[Metáfora de la señal de tránsito para un puntero] [#fig_variable_vs_pointer] .Diferencia entre variable y puntero image::indirection/variable_vs_pointer.svg[Diferencia entre variable y puntero] [[arrays]] ==== Arreglos (vectores) Un arreglo o vector es una región continua de la memoria que aloja elementos del mismo tipo de datos. Al igual que cualquier otra variable, se pueden alojar en cualquiera de los segmentos de memoria del proceso, como se lista en la siguiente tabla. [cols="10,45,45",options="header"] |=== |Segmento + Longitud |Longitud fija (_fixed-length array_) |Longitud variable (_variable-length array_) |Segmento de código a|Se declara constante en cualquier lugar del código. Al ser constante todos los valores del arreglo deben inicializarse. Si no se indica el tamaño dentro de corchetes, el compilador lo infiere. Ej.: [source,c] ---- const char ans[2] = {'y', 'n'}; ---- |N/A |Segmento de datos a|No se indica constancia por lo tanto es de lectura/escritura. Se declara global, global estático, o local estático. Los valores que no tengan inicialización, el compilador lo hará con ceros en el código objeto. Ej.: [source,c] ---- double g_arr[] = {-1.0, 0.0, 1.0}; static char gs_arr[2]; int main(void) { static int s_arr[5] = {1, 0}; } ---- |N/A |Segmento de pila a|Se declara como cualquier variable local. Si no se inicializa, los valores obtendrán "basura". Si no se indica el tamaño, se infiere de la inicialización. Si hay menos inicializadores que valores, los demás valores se inicializan con cero. Se debe evitar si la cantidad de elementos es grande. Ej.: [source,c] ---- int main(void) { int arr[] = {1, 0}; } ---- a|El arreglo se declara como una variable local. La cantidad de elementos es controlada por una variable o expresión que puede cambiar en cada ejecución. [red]#Es una vulnerabilidad# si es el controlada por el usuario. Se debe evitar si la cantidad de elementos es grande. Ej.: [source,c] ---- int main(void) { size_t count = 0; scanf("%zu", &count); int arr[count]; // VULNERABILITY! } ---- |Segmento de _heap_ |N/A a|C no provee constructos del lenguaje para alojar valores en la memoria dinámica, sino las funciones de biblioteca `malloc(size_in_bytes)` que no inicializa, `calloc(count, element_size)` que inicializa en cero, y `realloc(pointer, new_size)`. Las tres alojan un bloque de bytes en el _heap_ y retornan la dirección de memoria donde inicia el bloque o cero (`NULL`) en caso de fallo. Por lo tanto, no es posible acceder directamente al bloque, sino indirectamente a través de un puntero. Si no se libera el bloque con `free(address)` generará una [red]#fuga de memoria#. Ej.: [source,c] ---- int main(void) { size_t count = 0; scanf("%zu", &count); int* arr = (int*)calloc(count, sizeof(int)); if (arr) { free(arr); } } ---- |=== El operador `sizeof(arr)` retorna la cantidad de bytes que ocupa la suma de los elementos del arreglo, siempre y cuando sea el arreglo declarado con el operador corchetes y para el que se conoce la cantidad de elementos. Un puntero no es un arreglo. Un _puntero al arreglo_ es realmente un puntero al primer elemento del arreglo, nada más. Su tamaño es el de cualquier puntero, y por tanto, depende la cantidad de bits de la arquitectura. Como se ve en el ejemplo siguiente, hay varias formas de pasar un arreglo por parámetro a una subrutina. No importa cuál de ellas se use, el arreglo no se copia, C siempre va a pasar un puntero (una dirección de memoria) al primer elemento del arreglo original. [source,c,linenums] ---- include::arrays/array_sizeof.c[] ---- Un error común es retornar un puntero a un valor en pila que será destruido apenas la subrutina retorne, como en el listado de abajo. Se puede corregir de varias formas, como crear el arreglo en la subrutina que llama (`main()` en el ejemplo de abajo) y pasar un puntero al arreglo a la subrutina . [source,c,linenums] ---- char* dtoints(const double value) { char buffer[20]; snprintf(buffer, 32, "%020ld", (long)value); return buffer; } // buffer is destroyed at the return int main(void) { printf("%s\n", dtoints(144.28)); // ERROR! } ---- [[range_problem]] ==== Imprimir rango de números .Problema del rango [range_problem] [[act_range_problem]] ==== Haga un programa que lea dos números enteros stem:[min] y stem:[max] en la entrada estándar, e imprima todos los números en el rango stem:[{min, min + 1, ..., max}]. Si se proveen los valores stem:[min] y stem:[max] invertidos, el programa debe actuar como si el usuario los hubiere escrito bien. Puede tomar el siguiente código inicial. .Código inicial al rango de números (link:indirection/range/range_initial.c[range_initial.c^]) [source,c,linenums] ---- include::indirection/range/range_initial.c[] ---- ==== . Prob: Mediana estadística (arreglo automático) . Prob: Mediana estadística (arreglo estático) . Prob: Mediana estadística (arreglo con alojamiento dinámico) . Tipos de arreglos en C === Cadenas de caracteres . Prob: chext: cambiar la extensión === Registros de memoria . Campos . Relleno . Punteros a registros . Indirección a los campos . Colas y pilas . Listas doblemente enlazadas . Árboles . Grafos === Repetición por recursión . Recursión de pila . Recursión de cola