Computación y programación funcional E-Book

Camilo Chacón Sartori

• Herausgeber: Marcombo
• Kategorie: Fachliteratur
• Sprache: Spanisch
• Veröffentlichungsjahr: 2021

Seitenzahl: 398

Beschreibung

La programación funcional ofrece diversas ventajas a la hora de construir software: reducción de errores, manejo eficiente de datos en entornos concurrentes y paralelos, y un gran respaldo teórico. No obstante, muchos programadores fracasan en su intento de adentrarse en ella por ir directamente a aprenderla usando un lenguaje de programación (tecnología), con lo que omiten la teoría y el contexto histórico que le dio origen. Este libro incluye una introducción sobre qué son la computación y la programación en pos de delimitar su campo de acción. En segundo lugar, presenta el cálculo lambda, el modelo de computación que influenció a la programación funcional en los años cuando ni siquiera existían los lenguajes de programación, ni mucho menos los ordenadores digitales. Para concluir, el libro emplea los lenguajes de programación Racket y Python para enseñar las diversas características de la programación funcional, sus fortalezas y debilidades, y cómo ellas pueden combinarse con otros paradigmas. Con todo ello, aprenderá: La visión general de la computación, la programación y los lenguajes de programación. Los fundamentos que subyacen a la programación funcional, como el cálculo lambda. Las diferencias entre el cálculo lambda libre de tipos y tipado. La aplicación de estos conceptos en un lenguaje de programación de estirpe funcional, como lo es Racket, y en otro de uso masivo, como Python. El diseño y la construcción de un pequeño lenguaje de programación usando el enfoque funcional. Si tiene un mínimo conocimiento en programación y desea adentrarse en otra forma de pensar y construir sistemas computacionales, donde viven conceptos como reducción, funciones puras, transparencia referencial, búsqueda de patrones, entre otros, no espere más para hacerse con este libro. Gracias a él no descubrirá tan solo la programación funcional, sino que ampliará su perspectiva con respecto a la computación desde una óptica sistémica y libre de dogmas. Camilo Chacón Sartori fue elegido escritor destacado por Quora en español durante tres años seguidos (2018, 2019 y 2020) por sus más de 700 respuestas sobre ciencias de la computación. Actualmente tiene un podcast llamado Había una vez un algoritmo, donde trata temas filosóficos, prácticos y teóricos sobre la computación. Obtuvo su licenciatura y máster en Ingeniería Informática, ambos, con distinción máxima. "El libro nos presenta un sólido análisis teórico y conceptual de los tópicos vertidos aquí […]. La lectura y el estudio detallado de su contenido proveerán al lector de conocimientos necesarios que le permitirán comprender, resolver y extender los problemas asociados al desarrollo de programas computacionales, conforme a las tendencias actuales".

Leseprobe

COMPUTACIÓN Y PROGRAMACIÓN FUNCIONAL

Introducción al cálculo lambda y la programación funcional usando Racket y Python

Camilo Chacón Sartori

COMPUTACIÓN Y PROGRAMACIÓN FUNCIONAL

Introducción al cálculo lambda y la programación funcional usando Racket y Python

Camilo Chacón Sartori

Computación y programación funcional

Primera edición, 2021

© 2021 Camilo Chacón Sartori

© 2021 MARCOMBO, S. L.

www.marcombo.com

Diseño de cubierta: ENEDENÚ DISEÑO GRÁFICO

Corrección: Manel Fernández y Haizea Beitia

Maquetación: D. Márquez

Directora de producción: M.a Rosa Castillo

«Cualquier forma de reproducción, distribución, comunicación pública o transformación de esta obra solo puede ser realizada con la autorización de sus titulares, salvo excepción prevista por la ley. Diríjase a CEDRO (Centro Español de Derechos Reprográficos, www.cedro.org) si necesita fotocopiar o escanear algún fragmento de esta obra».

ISBN: 78-84-26732-84-2

Producción del ePub: booqlab

A mi padre y mi abuelo,José Chacón y Carlos Sartori

ÍNDICE

Prólogo

Acerca del libro

PARTE IINTRODUCCIÓN A LA COMPUTACIÓN Y LA PROGRAMACIÓN

Capítulo 1. ¿Qué es la computación?

1.1 Modelos de computación

1.1.1 Máquina de Turing

1.1.2 Cálculo lambda

1.1.3 Otros

1.2 Tesis de Church-Turing

1.2.1 Implicaciones filosóficas

1.3 Filosofía de la ciencia de la computación

Capítulo 2. ¿Qué es la programación?

2.1 Algoritmos

2.2 Especificación

2.2.1 Verificación formal

2.2.2 ¿Pensar antes de programar?

2.3 Implementación

Capítulo 3. Lenguajes de programación

3.1 Características de los lenguajes de programación

3.2 Paradigmas clásicos de la programación

3.2.1 Programación imperativa

3.2.2 Programación orientada a objetos

3.2.3 Programación lógica

3.2.4 Programación funcional

PARTE IICÁLCULO LAMBDA

Capítulo 4. ¿Qué es el cálculo lambda?

4.1 Historia

4.2 Sintaxis

4.2.1 Notación Backus-Naur extendida

4.2.2 Cálculo lambda

Capítulo 5. Operadores y variables

5.1 Operadores

5.1.1 Abstracción

5.1.2 Aplicación

5.2 Variables

5.2.1 Bound

5.2.2 Free

Capítulo 6. Reducción

6.1 Reducción alfa (α)

6.2 Reducción beta (β)

6.2.1 Reglas

6.2.2 Teorema de Church-Rosser

6.3 Reducción eta (η)

Capítulo 7. Aritmética

7.1 Números

7.2 Operaciones

7.2.1 Sucesor

7.2.2 Suma

7.2.3 Multiplicación

7.2.4 Predecesor

7.2.5 Resta

Capítulo 8. Condicionales

8.1 Valor booleano

8.2 Operadores

8.2.1 AND

8.2.2 OR

8.2.3 NOT

8.2.4 XOR

Capítulo 9. Tuplas y listas

9.1 Tuplas

9.1.1 Operaciones de acceso

9.2 Listas

9.2.1 Append

9.2.2 Head

9.2.3 Tail

9.2.4 IsEmpty

Capítulo 10. Tipos

10.1 Cálculo-λ tipado

10.2 Definiciones de reglas

10.2.1 Variable

10.2.2 Abstracción

10.2.3 Aplicación

10.3 Reducción de tipo

10.4 Una breve introducción a Haskell

10.4.1 Funciones

10.4.2 Listas

10.4.3 Tuplas

10.5 Otras características

10.5.1 Pattern matching

10.5.2 Guards

Capítulo 11. Cálculo-λcomo base de un lenguaje de programación real

11.1 Diferencias e influencias

11.1.1 Lenguajes de programación funcional

11.2 Límites del cálculo-λ

PARTE IIIPROGRAMACIÓN FUNCIONAL

Capítulo 12. ¿Qué es la programación funcional?

12.1 Introducción

12.1.1 Justificaciones previas

12.1.2 Racket

12.1.3 Python

12.2 Función, recursión y datos

12.2.1 Sobre funciones

12.2.2 Recursividad

12.2.3 Lista

12.3 Principales conceptos de la programación funcional

12.3.1 Funciones puras

12.3.2 Higher-order functions

12.3.3 Pattern matching

12.3.4 Lazy evaluation

12.3.5 Transparencia referencial

12.3.6 Inmutabilidad

Capítulo 13. Estructuras de datos

13.1 Lista

13.1.1 Búsqueda

13.1.2 Inserción

13.1.3 Eliminación

13.1.4 Filtrado

13.2 Tabla hash

13.2.1 Búsqueda

13.2.2 Inserción

13.2.3 Eliminación

13.3 Par

13.3.1 Operadores de acceso

13.4 Estructura de tipos

13.4.1 Operadores de acceso

13.5 Árbol de búsqueda binario

13.5.1 Búsqueda

13.5.2 Cantidad de elementos

Capítulo 14. Algoritmos

14.1 Ordenamiento

14.1.1 Quicksort

14.1.2 Merge sort

14.2 Recursividad

14.2.1 Torre de Hanói

14.3 Búsqueda de subcadenas

14.3.1 Karp-Rabin

14.4 Compresión de datos

14.4.1 Codificación Huffman

Capítulo 15. Crear un pequeño lenguaje de programación usando Racket

15.1 Especificación

15.2 Analizador léxico

15.3 Analizador sintáctico

15.4 Intérprete

15.4.1 Pruebas

Epílogo - Lecturas recomendadas

Agradecimientos

Apéndice A - Notación Big O

Apéndice B – Introducción a TLA+ (PlusCal)

Bibliografía

Glosario

PRÓLOGO

El cálculo automático es una invención con fecha antigua. Hace 2000 años ya se había construido el «mecanismo de Anticitera», un dispositivo que permitía calcular los eclipses lunares. Más tarde, en el siglo XVII, el matemático Wilhelm Schickard desarrolló la primera calculadora mecánica.

En el siglo XX aparecieron casi concurrentemente los modelos teóricos de la computación y los desarrollos tecnológicos asociados. Muchos de estos últimos estaban basados en la intuición; otros, fundamentados en bases formales. Aparecen los modelos de Church y Turing en el área de la teoría de la computación, y de Chomsky en el área de los lenguajes formales.

Los tres enfoques, complementados con las ideas y los estudios de muchos científicos y profesionales, fueron el punto de partida de lo que hoy denominamos «Ciencia de la Computación».

A la par de estos nuevos conocimientos, surgió la necesidad de expresarlos de manera inteligible para el ser humano, y procesables por un sistema automatizado. Esto dio origen a los lenguajes de programación, cada uno con sus enfoques y sus sabores sintácticos. Los procesos involucrados en el análisis de esos lenguajes se fundamentan en los aportes de Chomsky y Backus: las teorías de Chomsky (1956) relativas a los lenguajes formales y las gramáticas y los aportes de Backus relativos a cómo expresar las reglas gramaticales. Backus creó un lenguaje recursivo, que fue denominado «BNF» (Backus Normal Form, 1959) en su honor.

Los primeros lenguajes de programación surgieron para satisfacer diferentes necesidades: Fortran (1954), para el cálculo numérico; APL (1957) incorporó la computación funcional; Algol (1958) muestra el camino hacia la programación estructurada; Lisp (1958), basado en el cálculo lambda, derivó en el primer lenguaje para inteligencia artificial; Cobol (1959), para el procesamiento masivo de registros, y Simula (1962) introduce el concepto de «clase».

Sin temor a equivocarnos, podemos afirmar que la mayoría de los paradigmas computacionales actualmente en boga tienen su semilla en las décadas de los 50 y los 60: la programación orientada a objetos, la inteligencia artificial, la computación funcional, el cálculo lambda, la programación estocástica y tantas otras ideas. Las sucesivas encantaciones de dichas creaciones primigenias devienen, gracias a los nuevos aportes, interacciones y experiencias, en el mundo digital que vivimos hoy.

Los paradigmas reaparecen adaptados y evolucionados para enfrentar necesidades nuevas, tales como los crecientes volúmenes de información y los tamaños de los sistemas computacionales, que en muchos casos superan los millones de líneas de código. Así, por ejemplo, en su momento florece el concepto de programación estructurada como consecuencia del creciente tamaño de los programas y la necesidad de garantizar un código computacional libre de errores. También aparecen nuevos enfoques de administración de datos, con la creación de lenguajes especializados como lo fue SQL (1970), fundamentado en el cálculo relacional propuesto por C. J. Date.

Nacen lenguajes que favorecen la programación orientada a objetos basados en el concepto de clase ofrecido por el lenguaje Simula. Estos lenguajes evolucionaron de diversas formas, de ellas solo mencionaremos Python (1991) y Java (1995) dadas sus notorias diferencias conceptuales: Java exige clasificar los objetos durante la fase de compilación, mientras que Python delega la clasificación de los objetos en el momento de ejecución. El primero busca garantizar la correcta interacción entre objetos, mientras que el segundo busca una forma más simple de especificación. En el segundo caso, se reduce la necesidad de tener un conocimiento detallado de los objetos utilizados, pero se aumenta la carga de trabajo durante la ejecución.

En 1994, junto al Internet abierto y público, aparece el procesamiento distribuido. Ahora sus componentes ya no forman parte de sistemas localizados, donde los diversos módulos que interactúan son conocidos, sino que deben interactuar con objetos y procedimientos remotos cuyo detalle se desconoce. Esto conlleva la necesidad de definir interfaces con contexto laxo para simplificar su interacción. Es aquí donde aparecen necesidades conceptuales y lingüísticas que deben ser provistas por nuevas herramientas que permitan la implementación de las interfaces necesarias.

Lo descrito presenta el entorno donde se ubica la computación funcional y el cálculo lambda contenidos en este libro.

El libro nos presenta un sólido análisis teórico y conceptual de los tópicos vertidos aquí, y describe detalladamente la manera en la que estas ideas se hacen disponibles en los lenguajes Haskell (1980), Python (1991) y Racket (1995). La lectura y el estudio detallado de su contenido proveerán al lector de los conocimientos necesarios que le permitirán comprender, resolver y extender los problemas asociados al desarrollo de programas computacionales conforme las tendencias actuales.

Quisiera terminar con un pensamiento que el matemático D.H. Lehmer escribió en 1966:

Hay dos tipos de actividades en la investigación matemática: (a) la mejora de las carreteras entre las partes bien establecidas de las matemáticas y los puestos avanzados de su dominio, y (b) el establecimiento de nuevos puestos de avanzada.

Tomando la segunda actividad primero, parece haber dos escuelas de pensamiento sobre la cuestión de cómo descubrir mejor nuevos puestos de avanzada. La escuela más popular de nuestros días favorece la extensión de la prueba a situaciones más generales. Este procedimiento tiende a debilitar las hipótesis más que a fortalecer las conclusiones. Favorece la proliferación de teoremas de existencia y es psicológicamente reconfortante porque es menos probable que uno se encuentre con teoremas que no puede probar.

Bajo este régimen, las matemáticas se convertirían en un universo en expansión de generalidad y abstracción, extendiéndose sobre un paisaje multidimensional sin rasgos distintivos en el que cada piedra se convierte en una pepita de oro, por definición.1

Carlos Lauterbach R.

PhD en Ciencias de la Computación

UCLA, 1976.

_________________

1 Lehmer D.H. «Mechanized Mathematics», Bulletin of the American Mathematical Society, September 1966, Vol 72, pp 739-750.

ACERCA DEL LIBRO

La popularidad de la programación funcional ha crecido en los últimos años debido a sus principales ventajas a la hora de construir software: reducción de errores, manejo eficiente de datos en entornos concurrentes que deben escalar y un gran respaldo teórico. Sin embargo, muchos programadores fracasan en su intento de adentrase en ella por ir directamente a aprenderla usando un lenguaje de programación (tecnología), omitiendo así la teoría y el contexto histórico que le dio origen.

Por eso este libro presenta una tesis muy simple: «la programación funcional no puede reducirse solo al uso de la tecnología».

Para sustentarla, ofrecemos una introducción a lo qué es la computación y la programación, en pos de delimitar su campo de acción. En segundo lugar, presentamos el cálculo lambda, que es el modelo de computación que influenció a la programación funcional en los años en los que ni siquiera existían los lenguajes de programación ni mucho menos los ordenadores digitales. Y para concluir, usamos los lenguajes de programación Racket y Python para enseñar las diversas características de la programación funcional, sus fortalezas y debilidades y como ellas pueden combinarse con otros paradigmas.

Este libro está dividido en tres partes fundamentales:

 I.Introducción a la computación y la programación. En los primeros tres capítulos abordaremos los fundamentos de la computación, la programación y los lenguajes de programación. Incluso, y no menos importante, trataremos sus implicaciones filosóficas.

II.Cálculo lambda. Los capítulos del 4 al 11 serán una introducción a este modelo de computación, que es la base de la programación funcional. En ellos encontraremos diversos ejemplos para su mayor comprensión.

III.Programación funcional. En los capítulos restantes entraremos a la parte aplicada del libro, donde veremos cuáles son los conceptos principales de este paradigma usando lenguajes de programación.

Asimismo, este libro no renuncia a una visión teórica de la computación, ni mucho menos a la parte práctica. Se deduce así que la computación es una conversación entre estas dos cuestiones y que una no puede reducir o absorber a la otra.

Por otro lado, y no menos importante, todo el libro es un recorrido a través del cálculo lambda no tipado y, por consiguiente, significa que haremos uso de lenguajes de programación que son dinámicos y libres de tipos. No obstante, la importancia de los sistemas de tipos en la programación funcional es innegable y fundamental. Por ello, se dedica un capítulo para conocer el cálculo lambda tipado con una breve introducción a Haskell.

En resumen, usted aprenderá lo siguiente:

• Qué es la computación, la programación y los lenguajes de programación. Así tendrá una visión general del área que le permitirá entender el porqué de la existencia de diferentes paradigmas de programación y cómo ellos se entrelazan para construir software, con un énfasis en el modelo funcional.

• Los fundamentos que subyacen a la programación funcional, a saber: el cálculo lambda.

• Cómo aplicar estos fundamentos en un lenguaje de programación de origen funcional como lo es Racket, y en otro de uso masivo, como Python.

• A diseñar y construir un pequeño lenguaje de programación usando el enfoque funcional.

Al final del libro se incorpora una lista de lecturas recomendadas y un glosario de términos que sirve de soporte y ampliación a lo exhibido en esta obra.

A quién va dirigido el libro

Es para cualquier persona que tenga algún conocimiento básico en programación. Este libro incorpora temas que no han sido tratados en la literatura disponible en español de manera conjunta, por ende, puede ser interesante para todo aquel que quiera incorporar estos conocimientos a su ambiente laboral, ya sea un programador o programadora con varios años de experiencia o que recién este dando sus primeros pasos en el desarrollo de software.

Será de primordial interés para una persona que quiera comprender la programación funcional desde un contexto histórico y teórico antes de enfocarse en la tecnología. Alguien a quien le gusta la computación independientemente de la herramienta de moda. Igualmente, para esa persona que no desprecia la filosofía, la teoría, ni los múltiples paradigmas de la programación y, por ello, mantiene su curiosidad en el transcurso de la vida y suele evadir centrarse en una sola herramienta sin un contexto. En resumen, es para quien ama aprender.

Un camino visual de cómo leer el libro se ve en la siguiente figura:

Cada nodo del grafo es un capítulo del libro y las flechas (aristas) representan la prioridad de lectura. Por ejemplo, para leer el capítulo 4 podría leer los capítulos 1 y 2 o 1 y 3. O si usted prefiere, puede leer los capítulos 1, 2 y 3. Nada lo imposibilita. Asimismo, se añade a la derecha el enfoque de cada parte del libro.

Notas

De principio a fin de este libro, aparecen contenidos en un cuadro como este. Se trata de información extra, aclaraciones y comentarios que son relevantes como complemento a lo que se está tratando en dicho apartado. Por lo cual, le rogamos no omitirlo.

Ejercicios

Al final de cada capítulo de las partes II y III se encontrará con una sección de ejercicios. Cada uno de ellos tiene asociado el signo «*» que representa la dificultad del problema:

• (*) Fácil

• (**) Intermedio

• (***) Difícil

Cualquier otro signo indica que el autor de este libro le está proponiendo un desafío intelectual o, quizá, una broma.

Material

Toda la información está disponible en:

www.camilochacon.com

Ahí se encuentra el enlace al repositorio de GitHub que contiene lo siguiente:

• Cada código utilizado en la parte III.

• Cada figura en una mayor resolución y a color.

• Enlace para instalar Racket, Python y Haskell. (Usamos las últimas versiones de cada uno.)

• Enlace al intérprete web. Para este libro se ha creado un entorno que permite evaluar expresiones del cálculo lambda, por ello, usted podrá ejecutar cada ejemplo de la parte II y saber y verificar si ha podido resolver exitosamente cada ejercicio. Será su asistente en el aprendizaje.

PARTE I

INTRODUCCIÓN A LA COMPUTACIÓN Y LA PROGRAMACIÓN

  1. ¿Qué es la computación?

  2. ¿Qué es la programación?

  3. Lenguajes de programación

La computación es esencial en nuestra vida. Y la programación la hace posible. Ambas se combinan a través de los lenguajes de programación, que son piezas vitales para entender su rol, contexto y relevancia.

Capítulo 1

¿QUÉ ES LA COMPUTACIÓN?

Si alguien me preguntara qué consejo le daría a un joven [...] Creo que una de las cosas que le diría es que no porque algo esté de moda significa que sea bueno. Probablemente iría más allá: si encuentro demasiada gente adoptando una cierta idea, probablemente pensaría que está mal o, ya sabes, si mi trabajo se hubiera vuelto demasiado popular, probablemente pensaría que tengo que cambiar.

Donald Knuth

Esta pregunta puede parecer simple en su formulación, pero nos puede llevar a confines que van desde aspectos técnicos hasta filosóficos. A su vez, la misma se ha vuelto relevante con el paso de los años y tuvo su mayor auge a comienzo del siglo XX, en particular, hacia la década de los treinta, cuando un grupo de científicos, matemáticos y lógicos buscaban comprender qué era la computación como tal, ya sea desde un punto de vista teórico o práctico.

Así como también sus posibilidades y limitaciones para tratar con diversos problemas. De esta manera, y producto de sus esfuerzos, fue como nació el concepto de «modelos de computación». Este concepto apareció antes de la existencia del primer ordenador digital (de nombre ENIAC, construido durante la segunda guerra mundial [1943]).

Pero ¿qué es un modelo de computación? Esta pregunta usa dos palabras relevantes: «modelo» y «computación». Primero, un «modelo» es una representación del funcionamiento de algo en particular (ya sea abstracto o concreto) que puede ser reproducible. Por otra parte, «computación» refiere a la capacidad de hacer tareas repetitivas que se puedan automatizar sin la intervención humana, de lo cual se desprenden dos cuestiones: (1) la acción de hacer estas tareas se llama computar y (2) si es posible realizar dichas tareas, entonces se suele decir que son computables.

Así, un «modelo de computación» es una representación abstracta que representa qué tareas son computables o no a través de computar operaciones. Dado que estos modelos son abstractos, podemos decir que un modelo de computación es equivalente a un modelo matemático. Con la salvedad de que el primero se enfoca en el contexto de la computación y hace uso de sus ventajas y desventajas.

Por ello la computación es en sí —al menos en su origen— es un área de las matemáticas. Por lo tanto, la computación es un conjunto de modelos de computación.

Sin embargo, la computación misma ha sufrido cambios en las últimas décadas, y decir que solo se trata de un conjunto de modelos de computación parece caer en un reduccionismo teórico. Más bien, tomaremos partido por ampliar esta definición a la siguiente: la computación es un conjunto de modelos de computación que se pueden expresar a través de artefactos abstractos (software) y concretos (hardware), mediante el uso de una metodología científica o ingenieril, teórica o práctica.

Objetivos de este capítulo:

• Conocer los principales modelos de computación.

• Conocer qué es la tesis de Church-Turing y cuáles son sus implicaciones en la computación.

• Comprender qué es la filosofía de la ciencia de la computación y cómo nos puede ayudar a ser mejores conocedores de nuestra propia área.

Nota:

Aún hoy, existe un debate sobre la naturaleza de la computación. ¿Es una ciencia? ¿Una ingeniería? ¿O algo totalmente nuevo? Son preguntas difíciles de responder que han suscitado libros, artículos y amplios debates en las últimas décadas. Pero tomaremos una postura. Creemos, como dicen Peter J. Denning y Peter A. Freeman en su interesante artículo «Computing’s Paradigm» («Paradigma de la computación») de 2009, que la computación es un «nuevo paradigma» que combina cuestiones de diversas disciplinas del saber: ciencias, ingeniería y matemáticas. Además, ellos dicen que la computación no trata sobre ordenadores, sino más bien sobre el procesamiento de la información, y los ordenadores son máquinas que implementan esos procesos.

Y no faltan motivos para creerlo, ya que la computación puede ser una herramienta muy útil para una innumerable cantidad de áreas, desde humanidades hasta ciencias, aparte de estudiarse a sí misma (procesos computacionales y sus límites teóricos). Algo que no se compara con nada hasta la fecha. Por tanto, deberíamos tratarla como algo nuevo, en desarrollo y en búsqueda de su propio significado.

Este libro no intentará entrar en ese debate. Pero daremos una introducción clásica y teórica de lo que es la computación, con algunas pinceladas filosóficas. Para más información le recomendamos leer el libro Computational thinking («Pensamiento computacional») de Peter J. Denning y Matti Tedre.

1.1 MODELOS DE COMPUTACIÓN

Un modelo de computación es un modelo matemático, es decir, un modelo formal con una sintaxis definida, no ambigua, y que nos permite representar un proceso computable, al cual conocemos como algoritmo.

Problema de decisión

¿De dónde nace el concepto de modelos de computación? En primer lugar, debemos volver al principio del siglo XX y fijarnos en una persona que es relevante en la historia de las matemáticas: David Hilbert (véase figura 1.1). Fue un eminente matemático que a comienzos del siglo XX dio una famosa conferencia2 en la que presentó veintitrés problemas matemáticos que serían importantes e influyentes para el desarrollo de las matemáticas y, por eso mismo, él esperaba que se encontrara una solución para cada uno de ellos. (Hasta el día de hoy hay muchos de ellos que siguen sin solución.) Luego, en 1928, junto a William Ackermann (su alumno de doctorado), publicó un libro titulado Grundzüge der theoretischen Logik («Fundamentos de la lógica teórica») donde postularon lo que se conoce como problema de decisión (originalmente conocido como Entscheidungsproblem, en alemán), el cual se define como sigue:

Encontrar un procedimiento P que siempre encuentre la solución a un problema A según sus premisas y conclusiones.

A este «procedimiento» se le conoce, hoy en día, como «algoritmo». Por ejemplo, este problema plantea la pregunta de si es posible encontrar un algoritmo que siempre dé una respuesta («sí» o «no») a preguntas tales como: «dado un número natural, ¿es posible saber si es miembro de un conjunto?» o «dado un número natural, ¿puede responder si es un número primo o no?». Esto lleva a la siguiente cuestión, un problema de decisión es un problema de decidibilidad que busca responder a la pregunta de si existe un método efectivo (algoritmo) que demuestre si un objeto matemático (por ejemplo, un número) es miembro de un conjunto.

Un problema que demostró que no es posible encontrar un algoritmo para resolver un problema de decisión, es el conocido problema de la parada (halting problem en inglés). Este se puede definir de la siguiente forma:

Si existe un programa P que recibe como argumento un programa K con datos de entrada X; P debe devolver 1 si K con la entrada X termina en un número finito de pasos, mientras que devuelve un 0 si K con X cae en un bucle infinito.

Esto desembocó, casi en paralelo y de manera independiente, en que Alan Turing, con su máquina de Turing,3 y Alonzo Church, con el cálculo lambda, probaran que no existe un algoritmo para resolver el problema de la parada para cualquier valor de entrada (es decir, es «indecidible»), derrumbando, así, el sueño de Hilbert.

Figura 1.1 David Hilbert.

1.1.1 Máquina de Turing

En 1936, Alan Turing formularía en su artículo «On Computable Numbers, with an Application to the Entscheidungsproblem» («Sobre los números computables, con una aplicación al problema de la decisión») la prueba de que no es posible dar respuesta al problema de decisión.

En este trabajo Turing presentaría lo que hoy en día llamamos máquina de Turing. Una abstracción matemática que representa la computación o, para ser más precisos, lo que es computable o no.

Michael Sipser, importante teórico de la computación diría en su libro Introduction to the Theory of Computation («Introducción a la teoría de la computación») lo siguiente:

Una máquina de Turing puede hacer todo lo que un ordenador de propósito general puede hacer. Sin embargo, hay algunos problemas que ni la máquina de Turing puede resolver. En concreto, estos problemas van más allá de los límites teóricos de la computación. (Sipser, 1997)

Esto quiere decir que, de hecho, una máquina de Turing puede hacer todo lo que un ordenador digital puede hacer (teóricamente) y que, a su vez, posee las mismas limitaciones. Por ello, queda claro que existe una influencia en su nivel más subyacente y esencial. Los ordenadores digitales que usamos en la actualidad corresponden a la arquitectura propuesta por John von Neumann en su borrador sobre EDVAC, en el que presenta la organización y el mecanismo de cómo debería funcionar este. Pero ya volveremos a esto.

Algunas características de una máquina de Turing son las que se presentan a continuación:

• Existe una cinta infinita (que puede entenderse como una memoria).

• Existe un cabezal que puede leer y escribir sobre cada celda de la cinta.

• El cabezal se puede mover de izquierda a derecha o viceversa.

• Existe una tabla de instrucciones; haciendo uso de ella, la máquina sabe qué valores puede reemplazar en cada operación y también cuándo detenerse.

Intuitivamente podría ser vista como se muestra en la figura 1.2:

Figura 1.2 Una representación visual de una máquina de Turing, donde el cabezal se posiciona en el símbolo 0. El símbolo al final (derecha) «#» significa que el procedimiento se va a parar (comúnmente conocido como halt, en inglés).

Ejemplo

Imaginemos que necesitamos realizar una operación muy simple: reemplazar cada aparición de cierto carácter en una secuencia de texto dada, por ejemplo, pasar de «00011010» a «11111111», o sea, reemplazar el carácter 0 por 1. Para ello, es necesario crear una máquina de Turing.

Para esto necesitamos una tabla de instrucciones que contenga la mecánica de cómo se realizará cada cambio de estado:

Tabla 1.1 Tabla de instrucciones de lo que debe realizar la máquina.

Considere el siguiente texto de entrada:

00011010#

La secuencia comenzaría de izquierda a derecha. Se agrega el símbolo «*» para indicar la posición del cabezal junto al carácter actual, que estará a la izquierda. Así pues, los cambios de estado serían los siguientes:

1. 0*0011010#

2. 10*011010#

3. 110*11010#

4. 1111*1010#

5. 11111*010#

6. 111111*10#

7. 1111111*0#

8. 11111111*#

9. 11111111#*

10. 11111111

En el primer paso, por ejemplo, el cabezal encuentra el carácter «0». Entonces, si vemos la tabla (primera fila), cuando el estado actual es E0 y tiene el símbolo de entrada «0», se mantiene en el estado E0 y lo cambia por el símbolo de salida «1», y el cabezal se mueve a la derecha. Esto ocurre sucesivamente hasta el tercer paso.

Ahora bien, si vamos al cuarto paso, que es donde encontramos un «1» en el cabezal, esto nos lleva a la segunda fila de la tabla. Si el estado actual es E0 y el símbolo de entrada es «1», entonces se mantienen el estado actual y el valor «1», y se mueve el cabezal a la derecha.

El proceso sigue ocurriendo hasta que se encuentra el estado E0 y el símbolo de entrada «#» (última fila de la tabla) devuelve un símbolo vacío «-» y detiene el procesamiento de la máquina de Turing (estado H). Por consiguiente, ya no hay ningún tipo de movimiento más por realizar. La computación se ha terminado.

Máquina de Turing universal

Una máquina de Turing universal U puede simular otra máquina de Turing T como una entrada. ¿Cómo lo logra? Leyendo (1) una descripción o tabla de instrucciones Dt de la máquina Et a ser simulada y (2) los valores de entrada de dicha máquina Et. Pues bien, con esto se puede, con una sola máquina, lograr «ejecutar» cualquier otra máquina de Turing.

Esto lo representamos con la figura 1.3, donde una máquina de Turing universal U puede simular otra máquina de Turing Et con (1) descripción, (2) contenido y (3) estados. Esto conlleva la idea de que una máquina de Turing universal puede simular cualquier otra máquina de Turing dándole la información requerida en otra «cinta».

Figura 1.3 Una máquina de Turing universal.

Una máquina de Turing universal, concretamente, según dice Martin Davis, inspiró a John von Neumann para crear la primera arquitectura de computadoras en 1945, en su documento «First Draft of a Report on EDVAC» («Primer borrador de un informe sobre EDVAC»). En este documento, von Neumann presenta las ventajas del sistema binario sobre el decimal para las operaciones aritméticas elementales (+, -, ×, ÷), y según sus propias palabras, esto se explica por lo siguiente:

La principal virtud del sistema binario, en contraposición con el decimal, reside en la mayor simplicidad y velocidad con que se pueden ejecutar las operaciones elementales. (von Neumann, 1945)

Igualmente, se incorporan los registros especiales de memoria cuyo objetivo es, antes que nada, tener un conjunto de funciones ya definidas en memoria (por ejemplo: √, ||, log10, log2, ln, sin, etc.). Esto significa que no es necesario redefinir dichas funciones y, por ello, como es de suponer, el tiempo de cómputo se vería disminuido.

Por otro lado, el trabajo de Turing tuvo notables implicaciones en los fundamentos de la teoría de la complejidad computacional. Por su misma naturaleza, la capacidad explícita de secuencialidad de cada instrucción hace más simple poder clasificar problemas computacionales de acuerdo con su dificultad. Por ejemplo, las diversas clases de complejidad.

Antes de eso, primero debemos diferenciar dos cuestiones fundamentales: tiempo polinomial y tiempo exponencial. El tiempo polinomial, o mejor dicho, el tiempo polinomial de un algoritmo, es aquel en el que el tiempo de cómputo crece según la cantidad de datos de entrada n, los cuales no son exponenciales. Esto significa que la computación es más rápida. En la tabla 1.2 se presentan varios algoritmos4 clásicos, que usan la notación Big O5 (en el peor de los casos):

Tiempo polinomial

Tiempo exponencial

Búsqueda lineal

O(n)

Knapsack 0/1

O(2n)

Búsqueda binaria

O(log n)

Travelling salesman problem

O(2n)

Quicksort

O(n2)

Graph coloring

O(2n)

Merge sort

O(n log n)

Hamylton cycle

O(2n)

Tabla 1.2 Comparación de complejidad algorítmica entre tiempo polinomial y tiempo exponencial.

Cualquier algoritmo que tenga una complejidad elevada a la enésima potencia (como los que aparecen en la columna de la derecha) es computacionalmente demasiado complejo de solucionar en un tiempo de cómputo óptimo (polinomial). Esto se traduce en que se tarda demasiado tiempo en terminar la computación.

Pasemos a ver las principales clases de complejidad:

•P (polynomial en inglés). Es la clase de problema que es posible tratar, es decir, hay un algoritmo determinístico que lo resuelve de manera eficiente en un tiempo polinomial. Por ejemplo, los algoritmos de ordenamiento y de búsqueda de una subcadena dentro de un texto o del camino más corto entre dos nodos dentro de un grafo, entre otros.

•NP-Completo. Problemas más difíciles que los NP y, obviamente, que los P. Son problemas de decisión que se diferencian de los NP en lo siguiente: representan el conjunto de todos los problemas X en NP que se pueden reducir a cualquier otro problema NP en tiempo polinomial, es decir, intuitivamente lo entendemos así: si tenemos la solución para el problema X, entonces podríamos encontrar rápidamente la solución al problema Z. Ejemplos de problemas de esta clase son: 3-SAT, el problema del vendedor viajero, camino hamiltoniano, etc.

•NP-Difícil (NP-harden inglés). Son problemas de decisión tan complejos como los NP, pero no se sabe si existe un algoritmo verificable en tiempo polinomial para todos los casos. Esto último nunca ha sido demostrado, es decir, si P ≠ NP, entonces los problemas de esta categoría no pueden ser resueltos en tiempo polinomial. Un ejemplo de este tipo es el problema de la parada, que es NP-Difícil pero no NP-Completo.

La figura 1.4 resume la relación entre estas tres clases de complejidad:

Figura 1.4 Características de cada clase de problema de complejidad. El signo «|» significa «o».

Resumiendo, las clases de complejidad existen porque hay muchos tipos de problemas computacionales y una forma de tratarlos de mejor manera es clasificarlos por su dificultad. Con esto es posible diseñar técnicas algorítmicas más adecuadas según su clase.

1.1.2 Cálculo lambda

El cálculo lambda es un modelo de computación que está basado en funciones computables. Fue creado por Alonzo Church y lo veremos con mayor detalle en la parte II del libro (capítulo 4), pero aquí daremos un esbozo general del modelo. Al igual que Alan Turing con su máquina de Turing, el cálculo lambda de Alonzo Church probó negativamente el problema de decisión.

A diferencia de la máquina de Turing, que tiene un proceso secuencial, el cálculo lambda construye la computación a través de funciones computables que se forjan en una notación formal con una gran expresividad. El cálculo lambda es una máquina de recursividad que cuenta con operadores, variables y operaciones de reducción (conocida como reducción b). Por tanto, hace un uso asiduo de la recursividad y de mantener estados inmutables en cada una de sus fases de reducción o derivación.

Antes de presentar una función lambda, es fundamental entender qué es una función matemática. Una función se puede definir de la siguiente manera: f:a → b, donde la función f recibe un valor a y devuelve b. Además, a y b pueden ser representados como conjuntos de elementos. Así, la función es una relación entre elementos de dos conjuntos.

Entonces, volviendo a las funciones lambda, estas tienen como mecanismo de operación la reducción hasta donde sea posible. A esto lo llamamos computación.

Un ejemplo de función lambda es la siguiente:

(λx.(λy.y)x) (λy.y)

donde la función lambda es (λx.(λy.y)x) y el argumento es (λy.y). Para derivar o reducir esta función se puede aplicar reducción β, que es una propiedad del cálculo lambda:

(λx.(λy.y)x) (λy.y)

Termina las operaciones cuando alcanza la función (λy.y), que es, dicho sea de paso, una función de identidad que no puede ser reducida porque ya no tiene argumentos a la derecha. Para comprender esta reducción, vea la figura 1.5, donde se indica el argumento (desde donde nace la flecha, a la derecha), junto con la variable «X» (fase 1), y la variable «y» (fase 2) vendría a ser la posición donde dicho argumento tendrá su lugar (sustitución).

Básicamente, el primer paso es aplicar el primer argumento, (λy.y), a la función de la derecha. Y, debido a que toda variable que se encuentra a la derecha del símbolo λ se asocia a un argumento, esto quedaría así: [x:= (λy.y)]. Por lo tanto, se aplica una sustitución. (Una función lambda solo acepta un argumento.)

Así, a cada paso de reducción se aplica una sustitución de términos, hasta donde sea posible. Esto conlleva que la primera función exhibida se reduzca a la expresión (λy.y), donde ya no es posible continuar derivando.

Figura 1.5 Reducción de una función lambda, donde el primer argumento es (λy . y) y sustituye a la variable «X» definida dentro de la función lambda. Así, en la fase 2, se crea una reducción y vuelve a sustituir la siguiente variable, hasta llegar a la fase 3, donde ya no es posible aplicar ninguna otra reducción.

Podríamos decir que el cálculo lambda es un pequeño lenguaje de programación que permite expresar la computación a través de una sintaxis simple, acotada, flexible y, a su vez, poderosa. Algo para tener en cuenta es que una función lambda como (λ x.x) tiene una variable «X» que no especifica nada sobre el tipo de dato que tiene, es decir, este cálculo lambda es no tipado o libre de tipos, porque así fue presentado por Alonzo Church para la primera versión del cálculo lambda. La idea central, entonces, es ver que podemos manejar una función lambda como un valor y usarla como argumento de otra función lambda.

Esto último trae consigo alcances que explican las características de los lenguajes de programación funcionales y su surgimiento.

1.1.3 Otros

La máquina de Turing y el cálculo lambda no son los únicos modelos de computación. Existen muchos más e incluso hoy en día aparecen nuevos. Por otro lado, cada lenguaje de programación es, en sí mismo, un modelo de computación. Es por ello que se tiende a decir que un lenguaje como C++ o Python es «Turing completo», porque puede ser equivalente al funcionamiento de una máquina de Turing universal. Esto no acontece con otros lenguajes, como HTML o XML, que solo son de marcados y carecen de las características de un lenguaje de programación (condicionales, flujo de control, etc.).

Los modelos de computación, desde un punto de vista teórico de la computación, se pueden agrupar en tres categorías:

•Secuencial. En esta categoría caen los clásicos modelos de autómatas, finitos y con pila. Por otro lado, tenemos las máquinas de acceso aleatorio (RAM) y la máquina de Turing. Cada uno de ellos se cataloga como secuencial porque sigue un mecanismo paso a paso por cada operación.

•Funcional. El modelo de funciones recursivas, lógica combinatoria y, obviamente, el cálculo lambda. La idea principal no es la secuencia de paso, sino más bien construir la computación a través de funciones y reducción de estas.

•Concurrente. Algunos, como el autómata celular, la máquina paralela de acceso aleatorio (PRAM), el modelo en actores y la red de Petri, son modelos concurrentes. ¿Por qué concurrentes? Porque pueden suceder eventos que no siguen una secuencia y, en cambio, pueden «ejecutarse» fuera de un orden parcial sin afectar el resultado final de la computación.

1.2 TESIS DE CHURCH-TURING

Producto de la equivalencia entre los dos modelos, el cálculo lambda y la máquina de Turing, aparece el concepto de la tesis de Church-Turing, que reza lo siguiente:

Cualquiera que sea la función computable (algoritmo), esta es equivalente a una máquina de Turing.

Es decir, para que una función sea computable debe ser sí o sí computable por una máquina de Turing. En la actualidad, esto se sigue cumpliendo, y es difícil adherirse a la idea de que la tesis sea falsa, aunque es formalmente indemostrable. Esto radica en la incapacidad actual de definir qué es un «método efectivo» o «algoritmo», ya que no son conceptos fácilmente definibles. Simplemente se asume que cualquier algoritmo es una máquina de Turing.

Sobre esto, B. A. Trakhtenbrot, en su artículo: «Algorithms» de 1960, dijo lo siguiente sobre la incapacidad de demostrar esta tesis o hipótesis:

¿Cuál es la base de esta importante hipótesis? No podemos comprobarla como lo hacemos con un teorema matemático, puesto que es una declaración sobre el concepto general de algoritmo, que no está definido de manera precisa y no es, por tanto, un objeto propio de la discusión matemática. (Trakhtenbrot, 1960)

Sin embargo, en las últimas décadas se han añadido más datos que la han confirmado, por ejemplo, la equivalencia con otros modelos de computación (por ejemplo, lenguajes de programación), los cuales se suelen llamar «Turing completo».

1.2.1 Implicaciones filosóficas

Las implicaciones de la tesis no son solo técnicas o científicas. También trae consigo cuestiones filosóficas. Si llevamos el concepto de máquina de Turing al mundo físico, por ejemplo, se podría postular que el universo es una máquina de Turing universal, donde, dada la tabla de instrucción (leyes físicas), podemos crear una simulación de nuestro universo. Aunque claro, una objeción sería que las leyes físicas no son computables (aunque eso no está probado), pero incluso si lo asumimos, nada nos asegura que no se pueda construir otra máquina incluso más poderosa que la máquina de Turing.

Siguiendo este mismo razonamiento, Jack Copeland creó el concepto de «hipercomputación» (hypercomputation en inglés), el cual trata sobre la idea de poseer una máquina que no tenga los límites de una máquina de Turing. Con ello, se resolvería el problema de decisión. Aunque claro, la hipercomputación solo existe a nivel hipotético. Aun así, no se ha demostrado su imposibilidad.

Sin embargo, Martin Davis, en su artículo «The Myth of Hypercomputation» («El mito de la hipercomputación») del 2004, indicaría lo siguiente:

Si se permiten entradas no computables, entonces se pueden obtener salidas no computables. (Davis, 2004).

Con esta simple afirmación, Davis derriba la idea de la hipercomputación, ya que, si se aceptan valores no computables de entrada, entonces ¿por qué asumimos que siempre debería devolver una salida computable?

1.3 FILOSOFÍA DE LA CIENCIA DE LA COMPUTACIÓN

Es curioso ver la palabra «filosofía» en un libro de computación, y más si tiene como objetivo enseñar técnicas de programación. Quizá por este motivo existe este apartado. Tómelo como una persona que se autoinvita a su casa sin su consentimiento, pero que, a diferencia de ser una persona que viene con el propósito de hacerle perder el tiempo, este, en cambio, viene con noticias que «podrían» interesarle.

La filosofía de la ciencia de la computación es la búsqueda de respuestas a preguntas tales como las siguientes:

• ¿Qué es un programa computacional? ¿Un artefacto abstracto o concreto?

• ¿Cuáles son las diferencias entre programas computacionales y algoritmos?

• ¿Qué es una especificación e implementación?

• ¿Cuáles son los roles de los tipos de ciencias de la computación? ¿Es una ciencia o una ingeniería?

• ¿Qué es la abstracción en las ciencias de la computación? ¿Cómo se relaciona esta con la abstracción en las matemáticas?

• ¿La ingeniería de software plantea problemas filosóficos?

• ¿Cuál es el propósito de la programación?

• ¿Un algoritmo puede tener atributos estéticos?

• ¿Un algoritmo puede ser ético o solo es algo que corresponde a la persona que desarrolló el algoritmo?

En la filosofía, a diferencia de las ciencias, las preguntas ocupan un rol predominante por sobre las respuestas. Y esto no es casualidad, ocurre, como era de suponer, por la misma complejidad que supone encontrar respuestas a estas preguntas. Entonces, conceptos como hipótesis, experimento, refutación, falsación, etc. no forman parte de la filosofía; por el contrario, una teoría filosófica mide su valor sobre la base de su propia consistencia interna dentro del sistema propuesto.

Por lo mismo, el hecho de realizarnos preguntas trae consigo el mayor de los placeres, el intentar comprender mejor un área de estudio. Como todo profesional que busca la verdad, debe tener una visión crítica, abierta y evitar ideas dogmáticas que —generalmente en la computación— provienen de nuevas tecnologías de dudosa utilidad.

La computación no puede, simplemente, caer en un reduccionismo de aspectos técnicos o teóricos. Las implicaciones filosóficas de la computación son heterogéneas y, principalmente, inevitables. ¿Por qué? No solo por las cuestiones sobre si un sistema podrá alcanzar a emular o superar la inteligencia humana (inteligencia artificial fuerte) o sobre hasta qué límite un sistema que interactúa con humanos tiene responsabilidades éticas. Creemos, sin duda, que en los últimos años la orientación excesiva hacia la tecnología ha traído consigo cosas positivas y otras que no lo son tanto, especialmente por su parcial omisión y desvío de la atención hacia cuestiones que no tienen que ver con los principios de la computación.

Por ello, la filosofía de la ciencia de la computación se hace indispensable en un área que cada año se vuelve más compleja, especialista e imprecisa, y en la que surgen nuevos conjuntos de términos que muchas veces se usan de manera inexacta y que traen consigo una mayor confusión que claridad. La labor de una persona que pretenda abocarse a esta empresa desde un punto de vista filosófico es la búsqueda del orden y la sistematización general de toda el área. Para que a través de las preguntas adecuadas y propuestas sistémicas de cómo tratarlas (a saber: dar un orden y claridad a los conceptos que se usan a diario en los saberes que componen la computación), pueda y debiera, ser de ayuda a programadores, ingenieros y científicos. En consecuencia, la computación necesita de la filosofía.

Raymond Turner, en su libro Computational Artifacts. Towards a Philosophy of Computer Science («Artefactos computacionales. Hacia una filosofía de la ciencia de la computación»), que es uno de los referentes en cuanto a la filosofía de la ciencia de la computación, mencionó lo siguiente:

La ciencia de la computación es un área dominada por lenguajes. (Turner, 2018)

Creemos que no puede ser mejor afirmación para dar paso a los siguientes dos capítulos: (1) ¿qué es la programación? y (2) sobre los lenguajes de programación, en los cuales trataremos de demostrar que lo que dice Turner es verdad.

_________________

2 Conferencia en París, en el Congreso Internacional de Matemáticos de 1900.

3 Claramente Alan Turing no llamó a su modelo «Máquina de Turing». Él uso el término «a–machines» (la «a» por automática [máquinas automáticas]).

4 Hemos mantenido el nombre en inglés en los algoritmos en que, gracias a esto, se puede encontrar más literatura.

5 Para una breve introducción puede ver el apéndice A.

Capítulo 2

¿QUÉ ES LA PROGRAMACIÓN?

Haremos el trabajo de programar mucho mejor […] si respetamos las limitaciones intrínsecas de la mente humana y si nos acercamos a esta tarea como programadores humildes.

Edsger W. Dijkstra

La programación no es sinónimo de la ciencia de la computación ni de la ingeniería de software. Esta afirmación podría hacerle pensar a usted de manera implícita que la programación es algo informal, artesanal y, por ello, no tan importante. Pues no, todo lo contrario. La programación se erige sobre bases de la matemática y la lógica y hace uso de lenguajes formales a los que llamamos lenguajes de programación para crear artefactos abstractos: software, donde el medio para expresar estas ideas y llevarlas a la realidad son artefactos concretos: hardware. Prácticamente en cualquier área de la computación no podemos escapar de la actividad de programar. Algunas veces está más enfocada a la obtención de un producto comercial, y otras, en cambio, a la construcción de prototipos que nos ayudan a verificar hipótesis en nuestra investigación.

A mediados del siglo XX, la programación era una actividad que, ante todo, realizaban matemáticos con inclinación a la parte aplicada de su misma profesión, puesto que, por cuestiones obvias, en aquellos años no existía una carrera universitaria en computación, ya que el área estaba en pleno surgimiento. A ello se suman las dificultades para realizar ciertos trabajos en un ordenador que, por aquel entonces, tenía muchas limitaciones en cuanto a recursos (a saber: espacio de disco, velocidad de cómputo, memoria, etc.).

La programación es parte de un área más amplia que llamaremos simplemente computación. Pero por encima de la programación existe un término que convive en una simbiosis constante e inmutable que cubre toda la computación y, así, a la misma programación: algoritmo.

Objetivos de este capítulo:

• Entender qué son los algoritmos y cuál es su rol dentro de la computación.

•