Camilo Chacón Sartori - 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. aRosa 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

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

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».