Computación y programación funcional

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 I INTRODUCCIÓ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 II CÁ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 III PROGRAMACIÓ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.¹

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.