Todo es una función: reseña de las clases de SICP con David Beazley

Reseña de las clases de SICP con David Beazley: una experiencia de 1 semana

Comparto mi experiencia participando a finales de 2022 en las clases de SICP de David Beazley. Hay muchos materiales gratuitos, pero las clases de Dave fueron muy efectivas porque eligieron temas específicos y los explicaron a profundidad.

Punto de partida

Las clases de SICP se impartieron en el lenguaje Scheme, y aquí se explica el concepto básico del modelo de sustitución (substitution) implementando un intérprete simple de Scheme en Python.

Fundamentos del lenguaje Scheme

• Primitivos (Primitive): valores básicos (por ejemplo, enteros)
• Operadores: operaciones básicas como +, -, *, / usando notación prefija
• define: definición de variables

> (define x 2)  
> (+ x 3) ; resultado: 5  

• if: condicional
• lambda: definición de funciones anónimas

> ((lambda (x) (* x x)) 3) ; resultado: 9  

Intérprete de Scheme en Python

Se implementa un intérprete simple para evaluar código Scheme usando Python. Las operaciones básicas se definen como funciones de Python.

definitions = {  
    "+": lambda x, y: x + y,  
    "*": lambda x, y: x * y,  
}  

Ejemplo:

> evaluate(("+", 2, 3)) # resultado: 5  

También incluye la implementación de define y lambda, además del manejo de la condicional if.

Modelo de sustitución (Substitution Model)

El modelo de sustitución es una forma simple de interpretar programas: evalúa el programa reemplazando las variables por valores. Sin embargo, este modelo falla cuando entra en juego la asignación (assignment).

Estado (State)

Un ejemplo de cómo se rompe el modelo de sustitución es la asignación (assignment). Por ejemplo, al modelar el saldo de una cuenta bancaria, se usa set! para actualizar la variable.

(define balance 100)  
  
(define (withdraw amount)  
  (set! balance (- balance amount))  
  balance)  

En este caso, el modelo de sustitución no puede distinguir entre el estado del saldo antes y después.

Se vuelve necesario el modelo de entornos (Environment). Las variables se definen dentro de un entorno, y cada procedimiento tiene su propio entorno.

Streams

Otra forma de modelar el estado son los streams. Los streams también pueden modelar valores futuros mediante evaluación diferida (lazy evaluation).

Bucles infinitos y orden de evaluación

Diferencia en el orden de evaluación: la mayoría de los lenguajes usan evaluación en orden aplicativo (applicative-order evaluation), evaluando primero los argumentos.

> (square (+ 1 2)) ; resultado: 9  

Sin embargo, la evaluación en orden normal (normal-order evaluation) retrasa la evaluación hasta que los argumentos realmente se necesitan. Gracias a esto, es posible evitar un bucle infinito.

> (define (p) (p))  
> (define (test x y) (if (= x 0) 0 y))  
> (test 0 (p)) ; en orden normal devuelve 0, en orden aplicativo entra en bucle infinito  

Cálculo lambda y numerales de Church

Mediante Church encoding, los números pueden representarse como procedimientos. Este es un concepto importante de la programación funcional.

(define (zero f) (lambda (x) x))  
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))  

• zero es una función que devuelve el argumento tal cual (identity).
• increment aplica una llamada de función una vez más.

Ejemplo

> ((zero (lambda (x) (+ x 1))) 0) ; resultado: 0  
> (((increment zero) (lambda (x) (+ x 1))) 0) ; resultado: 1  

Iteración vs recursión

Scheme realiza tareas repetitivas usando recursión en lugar de for loops.

Ejemplo de recursión: factorial

(define (factorial n)  
  (if (= n 1)   
    1   
    (* n (factorial (- n 1)))))  

Esta llamada recursiva puede consumir mucha memoria al usar la pila.

Optimización de tail calls (Tail-call optimization)

Scheme reduce el uso de memoria mediante tail-call optimization. Gracias a esto, puede comportarse como un proceso iterativo.

(define (factorial n)  
  (define (iter product counter)  
    (if (> counter n)  
        product  
        (iter (* product counter) (+ counter 1))))  
  (iter 1 1))  

Cierre

Las clases de David Beazley abordan en profundidad conceptos clave de SICP seleccionando sus temas principales. En particular, ayudan a comprender distintos paradigmas de programación como la programación funcional, el cálculo lambda y el orden de evaluación.

Cita de Knuth

Si solo estudias teoría, significa que ya es momento de enfocarte en la práctica; y si solo practicas, significa que ya es momento de enfocarte en la teoría.

[GN⁺]

Comentarios de Hacker News

• El curso de SICP tiene una alta densidad de información, pero consume mucho tiempo por las preguntas y respuestas de los estudiantes y el uso del pizarrón. También podría reorganizarse el orden de las clases. Personalmente, estoy planeando una nueva serie de videos

  • El curso de SICP usa un lenguaje moderno como Python, pero mantiene la intención original
  • Python es un lenguaje multiparadigma con una gran expresividad

• Se presenta cómo codificar estado como funciones puras. Existen codificaciones puramente funcionales para distintos tipos de datos

  • La codificación puede ser confusa, pero es elegante y concisa
  • Se muestra un ejemplo de una implementación funcional de la mónada Maybe en JavaScript

• El ancla/hash de la URL de la publicación me llevó directamente al postscript, lo que fue confuso

• Ver cons/car/cdr implementado con lambdas se sintió como magia la primera vez que lo vi. Esto muestra que el runtime del lenguaje tiene que implementar un diccionario de clave/valor

• David Beazley es una figura legendaria en el mundo de Python, y este curso al principio me sorprendió, pero pronto empecé a pensar que era una combinación perfecta. Me inscribí en el siguiente curso

  • Esto muestra cómo podría desarrollarse la educación continua de los ingenieros de software

• Me encontré con la idea de que se necesitan tipos de datos inductivos. Solo con codificación Church no se pueden demostrar teoremas como 0 != 1

  • Publiqué contenido relacionado en Notion

• El artículo en sí fue interesante, pero era difícil navegar la página. No se podía hacer scroll con las flechas del teclado

• Hay un error tipográfico en el código de la sección "modelo alternativo". Debe usarse fibonacci en lugar de fib. El código del repositorio de GitHub es correcto

• Hay un enlace donde se está desarrollando una discusión sobre el libro. Me pregunto por qué el enlace va directamente a la discusión al final de la página. También me pregunto si puede integrarse en otra discusión

• Se proporciona un enlace de YouTube