Programación multiparadigma
Filosofía de la computación
Cada disciplina tiene un propósito y métodos para lograrlo. Es muy importante tener claro esta armazón ósea que sustenta cada detalle de la disciplina en la que se va a ejercer, y explica sus ramas y hasta los cursos de la carrera que estudia. Si no lo ha hecho antes, responda a estas preguntas:
-
¿Cuál es el propósito de la disciplina? Es decir, ¿a qué se dedicará usted el resto de su vida profesional mientras ejerza como un(a) informático(a)?
-
¿Cuál es el método que deberá seguir día a día para lograr ese propósito?
-
¿Es la computación una ciencia? ¿Cuál es el propósito de la ciencia? ¿La computación cumple este propósito?
-
¿Es la computación una ingeniería? ¿Cuál es el propósito de la ingeniería? ¿La computación cumple este propósito?
| No continúe leyendo hasta que no haya respondido estas preguntas por su cuenta. |
Las respuestas a estas preguntas son filosóficas y pueden variar de autor en autor. La siguiente es una posición más.
-
El propósito de la computación es la resolución de problemas con computadoras (software). Es decir, usted día a día estará resolviendo problemas de otras personas, incluso suyos, en los que la intervención de una o varias computadoras resulta de utilidad.
-
El método para lograrlo es el proceso de resolución de problemas. Como todo proceso consta de fases, y el nuestro es repetitivo (Figura 1). En cada iteración usted realiza: un análisis para comprender el problema; el diseño de una solución usando artefactos "baratos"; la implementación de esa solución con los artefactos finales de software y hardware; y la integración de esa parte hecha en la iteración a una solución más compleja. Para saber que puede adecuadamente avanzar de una fase a otra debe probar los artefactos elaborados.
-
Si el propósito de la ciencia es explicar los fenómenos naturales o sociales, la computación no sería una ciencia. Es engañoso el término "ciencias de la computación" que se difundió en Norteamérica porque el término "computación automática" proveniente de Inglaterra no resultó llamativo, pese a describir perfectamente que un fenómeno que siempre han hecho los seres humanos, la computación, ahora se puede hacer también de forma automática con máquinas.
-
Si el propósito de la ingeniería es resolver problemas con artefactos, la computación sería una ingeniería. Los tipos de ingenierías varían de acuerdo al tipo de artefacto usado para resolver problemas. La ingeniería civil usa estructuras, la ingeniería mecánica usa máquinas y motores, la ingeniería electrónica usa circuitos eléctricos, y la ingeniería en computación usa computadoras.
En algunas universidades la computación está ligada a la matemática. Sin embargo, la computación tampoco es una matemática. El propósito de la matemática es encontrar y demostrar propiedades y relaciones entre objetos abstractos. Para conseguir este propósito sigue el método axiomático. La ciencia usa la matemática para modelar los problemas que debe expicar. La ingeniería, y por ende la computación, usa la matemática y la ciencia para modelar las soluciones a los problemas que debe resolver.
Resolución de problemas
Si el propósito de la computación es resolver problemas con computadoras, una persona que se forme en esta disciplina urge aprender estos dos grandes conocimientos: (1) resolver problemas y (2) cómo usar las computadoras para resolverlos. Los planes de estudio en computación típicamente incluyen abundancia de cursos para alcanzar (2), y ausencia de ellos para (1). La resolución de problemas es un objeto de estudio en la disciplina de psicología, una ciencia social.
Un problema es una situación para la cual no se conoce una solución, y por lo tanto hay que idearla. La reacción natural de la mente ante un problema es el bloqueo, una sensación de no saber qué hacer. Un(a) ingeniero(a) no puede permanecer en esta situación de bloqueo sabiendo que los clientes pagan grandes cantidades de dinero por artefactos ingenieriles y que el tiempo apremia. Para superar el bloqueo y poder construir una solución de calidad acorde a la altura, se sigue el proceso de resolución de problemas de la Figura 1.
Durante la fase de análisis su propósito es comprender el problema. Esta fase se torna compleja cuando uno(a) no está familiarizado(a) con el contexto y debe aprender sobre éste. Imagine que debe mejorar un software de espectroscopía médica. El producto o artefacto generado en esta fase son requerimientos, normalmente expresados en documentos. Para probar estos artefactos, se verifican los requerimientos con los usuarios finales o clientes. Conviene durante esta fase generar, junto con los usuarios, casos de prueba que después serán automatizados mediante pruebas de software. Además de incrementar la calidad del software, le ayudarán a comprender significativamente la tarea ingenieril a realizar y así evitar la parálisis del análisis.
Una vez que se ha comprendido el problema o parte de él, se idea una solución aceptable para los requerimientos establecidos. Puede pensarse que esta solución se construye en software. Sin embargo, esto es tan inadecuado como que un arquitecto después de escuchar los deseos de los clientes comience de inmediato a construir la obra gris de la obra que imagina para verificar si es lo que su cliente desea o no. Como es de esperar —si no el cliente lo va a exigir— el arquitecto diseña primero una solución usando planos. Los planos son modelos que puede discutir con sus clientes, son fáciles de modificar respecto a una obra gris, e incluso no son caros si tuviere que descartarlos. Al igual que cualquier otro producto ingenieril, el software debería diseñarse antes de construirse.
La fase de diseño consiste en idear una solución usando artefactos baratos que permitan probarla antes de comenzar a implementarla con los artefactos finales. Los tipos de artefactos usados para diseñar varían de acuerdo a los paradigmas de computación que se expondrán luego. El producto de esta fase son modelos o diseños. La forma de probarlos varía de acuerdo a si se tienen o no herramientas automatizadas para el tipo de modelo. Si no se tienen, los seres humanos pueden hacer pruebas manuales siguiendo los diseños para determinar que la solución cumple con los requerimientos establecidos por los clientes.
Una vez que el diseño ha sido probado se pasa a la fase de implementación, donde los modelos son construidos con los artefactos ingenieriles finales. En computación, los modelos y artefactos dependen del paradigma. El el caso de la programación de computadoras, los diseños se traducen a los lenguajes de programación. Los casos de prueba también son automatizados en esta fase. El producto de la implementación son los artefactos ingenieriles finales. Para probarlos se corren las pruebas automatizadas con la ventaja de que las computadoras pueden realizar miles de ellas en pocos segundos.
Como se aprecia en la Figura 1 el proceso de resolución de problemas es cíclico. El problema se divide en subproblemas, y se realiza el ciclo con un subproblema a la vez. Al finalizar una iteración, se tienen productos ingenieriles parciales que han de agregarse al producto ingenieril total. En la fase de implantación o integración, se agrega el producto parcial en estado de desarrollo al producto final, posiblemente en estado de producción. Este es un proceso delicado que requiere muchas pruebas para saber que no se afectan los datos o los usuarios que están en interacción con el sistema.
1. 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:
-
Leer un valor(es)
-
Imprimir un valor(es)
-
Crear una variable con un valor
-
Cambiarle el valor a una variable
-
Condicionar una instrucción(es)
-
Repetir una instrucción(es)
-
Hacer una subtarea
-
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.
1.1. Entrada y salida
-
Concepto de programa
-
Concepto de archivo y cursor
-
Salida estándar
|
Objetivos de la programación competitiva. Registrarse en UVa, Kattis |
-
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
1.2. Expresiones y condicionales
1.3. Repetición con ciclos
-
Ciclo por contador
-
Ciclo por condición
-
Ciclo por colección
1.4. Subrutinas
Tipos de subrutinas
-
Interfaz e implementación
-
Diseño por contratos
-
Programación defensiva
1.4.1. 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.
1.4.2. 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).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Static library
gcc -c -Wall -Wextra -std=c11 lib_file1.c -o lib_file1.o
gcc -c -Wall -Wextra -std=c11 lib_fileN.c -o lib_fileN.o
ar rs mylib.a lib_file1.o lib_fileN.o
# Static linking
gcc -c -Wall -Wextra -std=c11 main.c -o main.o
gcc -Wall -Wextra -std=c11 main.o mylib.a -o myapp
# Dynamic library
gcc -c -fPIC -Wall -Wextra -std=c11 lib_file1.c -o lib_file1.o
gcc -c -fPIC -Wall -Wextra -std=c11 lib_fileN.c -o lib_fileN.o
gcc -shared lib_file1.o lib_fileN.o -o libmylib.so
# Dynamic linking
gcc -c -Wall -Wextra -std=c11 main.c -o main.o
gcc -Wall -Wextra -std=c11 main.o libmylib.so -o myapp # or
gcc -Wall -Wextra -std=c11 main.o -lmylib -o myapp
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:
LD_LIBRARY_PATH=/path/to/lib /path/to/my/executable argsLa 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:
# 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'-
Metaprogramación
1.5. Indirección, arreglos y matrices
1.5.1. Indirección (punteros)
1.5.2. 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.
| Segmento Longitud |
Longitud fija (fixed-length array) | Longitud variable (variable-length array) |
|---|---|---|
Segmento de código |
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.: |
N/A |
Segmento de datos |
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.: |
N/A |
Segmento de pila |
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.: |
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. Es una vulnerabilidad si es el controlada por el usuario. Se debe evitar si la cantidad de elementos es grande. Ej.: |
Segmento de heap |
N/A |
C no provee constructos del lenguaje para alojar valores en la memoria dinámica, sino las funciones de biblioteca |
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
void test1(size_t count, size_t arr[count]);
void test2(size_t count, size_t arr[]);
void test3(size_t count, size_t* arr);
int main(void) {
size_t arr[4] = { 0 }; // arr = [0, 0, 0, 0]
arr[0] = sizeof(arr); // 32
test1(4, arr);
test2(4, arr);
test3(4, arr);
printf("[%zu, %zu, %zu, %zu]\n", arr[0], arr[1], arr[2], arr[3]);
}
void test1(size_t count, size_t arr[count]) {
arr[1] = sizeof(arr); // 8
}
void test2(size_t count, size_t arr[]) {
arr[2] = sizeof(arr); // 8
}
void test3(size_t count, size_t* arr) {
arr[3] = sizeof(arr); // 8
}
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 .
1
2
3
4
5
6
7
8
9
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!
}
1.5.3. Imprimir rango de números
Haga un programa que lea dos números enteros \$min\$ y \$max\$ en la entrada estándar, e imprima todos los números en el rango \${min, min + 1, ..., max}\$. Si se proveen los valores \$min\$ y \$max\$ invertidos, el programa debe actuar como si el usuario los hubiere escrito bien. Puede tomar el siguiente código inicial.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Copyright 2020 Jeisson Hidalgo
#include <stdio.h>
// Subroutine declaration or Function prototype
void swap(int value1, int value2);
// main: Prints all integer values in range {min, min + 1, ..., max}
int main(void) {
// Read min, max
int min = 0, max = 0;
if (scanf("%d %d", &min, &max) == 2) {
// If min > max then
if (min > max) {
// Swap min with max
swap(min, max); // Arguments
}
// Repeat index from min to max inclusive do
for (int index = min; index <= max; ++index) {
// Print index
printf("%d%c", index, (index == max ? '\n' : ' '));
}
}
return 0;
}
// Swap <value1> with <value2>:
void swap(int value1, int value2) { // Params: DataType varName = initValue
// Create a copy of value1
const int value1_copy = value1;
// Assign value1 as value2
value1 = value2;
// Assign value2 as the copy of value1
value2 = value1_copy;
}
-
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
1.6. Cadenas de caracteres
-
Prob: chext: cambiar la extensión
1.7. Registros de memoria
-
Campos
-
Relleno
-
Punteros a registros
-
Indirección a los campos
-
Colas y pilas
-
Listas doblemente enlazadas
-
Árboles
-
Grafos
1.8. Repetición por recursión
-
Recursión de pila
-
Recursión de cola
2. Programación genérica
2.1. Arreglo dinámico
-
Prob: Clase fracción para mediana
2.2. Lista enlazada
2.3. Árboles
-
Conjunto
-
Mapa (diccionario/arreglo asociativo)
2.4. Grafo
3. Programación orientada a objetos
3.1. Clases y objetos
3.2. Espacios de nombres (namespaces)
-
Prob: Calculadora fraccional (versión 1)
3.3. Sobrecarga de operadores
-
Prob: Calculadora fraccional (versión 2)
