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

 (ezzeriesa.notion.site)
2 puntos por GN⁺ 2024-11-18 | 1 comentarios | Compartir por WhatsApp

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.

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-11-18
Opiniones de Hacker News

  • Como advertencia, si te metes de lleno en SICP/Lisp/Scheme, puede cambiar tu forma de pensar la programación, y ese tipo de estímulo intelectual siempre es bienvenido.
    Pero si aplicas esas ideas tal cual a una base de código orientada a objetos, por lo general resulta contraproducente o provoca rechazo en el equipo.
    Por ejemplo, después de Lisp podrías querer convertir todos los bucles for en forEach, o transformar todo en cadenas de map/reduce, pero si el lenguaje no abraza por completo la programación funcional, eso puede perjudicar tanto la legibilidad como el rendimiento.
    Al final, recordar que la memoria mutable y la CPU son las que procesan el código ayuda a mantener los pies en la tierra; hoy en día, en lo cotidiano, me parece más práctico el diseño orientado a datos y la “empatía mecánica” ajustada a la realidad del hardware que conceptos abstractos como los numerales de Church.

    • Creo que la inmutabilidad es más segura.
      Cuantos menos efectos secundarios haya, más predecible es todo, y la orientación a objetos suele usarse incluso donde bastarían funciones.
      En desarrollo de juegos hay muchos cálculos y código riesgoso, así que la orientación a objetos encaja bastante bien; pero en desarrollo web la programación funcional se siente mucho más natural, y en SaaS lenguajes como Elixir permiten escribir código más confiable, con menos bugs y más fácil de probar.
    • Me parece que también existe algo como Common Lisp Object System.
      Además, cosas como forEach y map/reduce ya existían en las colecciones de Smalltalk, y aunque no fueran sintaxis de primera clase, también se copiaron a Object Pascal y C++.
      Como la memoria subyacente es mutable, cuando realmente se necesita, incluso los lenguajes de la familia ML tienen mecanismos para manejar la mutación.
    • La única forma en que una CPU implementa el flujo de control se parece a goto, pero goto es incluso menos popular que Lisp.
      Lo más curioso es que, aunque para obtener rendimiento en las CPU modernas la caché es indispensable, todavía no hay lenguajes que traten la jerarquía de memoria como ciudadano de primera clase.
      Lo más cercano parece ser el C al estilo Linux, con un mar de guiones bajos.

  • Ofrece una buena introducción a cómo codificar el estado con funciones puras.
    De hecho, existen muchas más codificaciones puramente funcionales para todo tipo de datos: árboles, enteros, tipos suma/producto, imágenes, mónadas, etc.
    Las codificaciones pueden ser un poco confusas, pero a la vez son elegantes y pequeñas.
    Por ejemplo, una implementación funcional de la mónada Maybe en JavaScript se vería así:
    Nothing = nothing => just => nothing
    Just = v => nothing => just => just(v)
    pure = Just
    bind = mx => f => mx(mx)(f)
    evalMaybe = maybe => maybe("Nothing")(v => "Just " + v)
    console.log(evalMaybe(bind(Nothing)(n => pure(n + 1)))) // Nothing
    console.log(evalMaybe(bind(Just(42))(n => pure(n + 1)))) // Just 43

    • Este tipo de implementación puede derivarse del principio de recursión de ese tipo.
      data Maybe a = Nothing | Just a
      foldMaybe :: (Unit -> r) -> (a -> r) -> Maybe a -> r
      Las dos funciones de orden superior que se pasan a foldMaybe corresponden a Nothing y Just, respectivamente.
      Sin embargo, del lado de Nothing se agrega un parámetro Unit para ser un poco más preciso.
    • Puede verse como convertir un tipo inductivo en el tipo de su función recursora.
      En teoría de tipos es bastante elegante, pero no es muy bueno para la programación real.
    • Matemáticamente puede ser elegante, pero cuando se transmite a través de un lenguaje compuesto solo por el conjunto de caracteres ASCII, sin ordenación ni justificación interna, visualmente resulta bastante doloroso.
    • En pocas palabras, el cálculo lambda no tipado es Turing completo.

  • Hace tiempo vi las clases reales de SICP, es decir, las grabaciones de 1986 de MIT OCW.
    Suelen elogiarlas por su alta densidad de información, pero en la práctica se pierde bastante tiempo en cosas como preguntas y respuestas con estudiantes, el rato en que el profesor llama la atención por intentos de hacer presentaciones “multimedia” en el aula, y partes donde el plan completo del curso no estaba totalmente organizado de antemano, así que no podía anticiparse y evitar ciertas preguntas.
    El tiempo de escribir en el pizarrón también suma bastante.
    Por supuesto, el orden del material se puede debatir y reorganizar de mil maneras, y algún día también planeo hacer yo mismo una serie de videos que explique este contenido según mi propio criterio.
    Me alegra que esta clase parezca mantener sus raíces aun usando un lenguaje más moderno como Python, y creo que, aunque Python no sea completamente puro, como es un lenguaje práctico multiparadigma, la gente no reconoce lo suficiente la expresividad que ofrecen los modismos funcionales.

    • Esta clase implementa Scheme en Python y luego vuelve a implementar Scheme en Scheme.
      Creo que Python podría, y debería, quitarse de esta clase.
      Python tiene un soporte muy débil para la programación funcional.
      Las listas no están basadas en cons, las lambdas tienen muchas restricciones, el pattern matching es horrible y no está basado en expresiones, y los espacios de nombres también son raros.
      Python difícilmente puede considerarse un lenguaje moderno; se quedó en los años 90 y, lamentablemente, creció a costa de lenguajes mejores solo porque tiene una C-API decente.
    • La programación funcional en Python es bastante débil, y en ese aspecto creo que JavaScript es incluso mejor.
      Como no hay optimización de llamadas de cola, algunos ejercicios de código requieren soluciones completamente distintas a las de Scheme.
      Si una traducción 1:1 del código falla, me pregunto si el profesor debe decirles a los estudiantes que simplemente le crean porque se comporta así por el lenguaje elegido, o si debe plantearlo todo como un problema de externalizar la pila y resolverlo de esa forma.
      Forzar SICP dentro de Python parece bastante tonto.
    • También están las clases de ArsDigita University.
      El sitio está fuera de línea ahora, pero las clases se pueden ver en archive.org.
      https://en.m.wikipedia.org/wiki/ArsDigita#ArsDigita_Foundati...
      https://archive.org/details/arsdigita_01_sicp/
      Vendían una llave USB con todo el currículum; sería genial que alguien subiera la ISO.
      https://web.archive.org/web/20190222145553/aduni.org/drives/
    • El problema de Python y de la mayoría de los lenguajes no pertenecientes a la familia Lisp es que no permiten fácilmente tratar los programas como datos.
      Cosas que en Scheme se expresan de forma sencilla se vuelven ejercicios complejos en otros lenguajes.
      En lugar de concentrarse en los conceptos de fondo, los estudiantes terminan enfocándose en detalles del lenguaje de implementación de los que en Scheme no tendrían que preocuparse.

  • La primera vez que vi cons/car/cdr implementados con lambdas me pareció magia.
    Pero al final creo que muestra que el runtime del lenguaje implementa un diccionario clave/valor, y que se puede aprovechar esa implementación para crear otras estructuras de datos.

    • La lógica de destructuración de Elixir me parece mucho más interesante, y la versión debilitada de ES6 me parece mucho más práctica.
      En Elixir puedes extraer desde el principio tantos elementos como quieras.
    • No hace falta un diccionario clave/valor, solo punteros.
      Un closure sin comportamiento es simplemente un puntero a variables cerradas, y un closure con dos punteros es un par del que se pueden obtener car y cdr.
      El runtime debe hacer que lo apuntado pueda usarse incluso fuera de la definición, así que se necesitan análisis de escape, garbage collection, etc., pero no un diccionario.

  • Hace poco me encontré con la idea de que, para demostrar algo como 0 != 1 en demostración de teoremas, la codificación de Church por sí sola no alcanza y se necesitan tipos de datos inductivos.
    Dejé aquí algo relacionado, junto con una crítica aparte a SICP: https://intellec7.notion.site/Drinking-SICP-hatorade-and-why...
    Quiero entender mejor los límites de la perspectiva de que “todo es simplemente una función”.

    • Si hay algún otro hecho concreto que pueda aprovecharse sobre desigualdades, parece que se podría demostrar 0 ≠ 1.
      Se puede inferir a partir del teorema f = g -> f x = g x para crear un hecho de desigualdad en el lado derecho, y luego tomar su contrapositiva.
      Parece correcto decir que las desigualdades entre numerales de Church no pueden demostrarse directamente sin otros hechos sobre desigualdad.
      En cambio, en los tipos de datos inductivos, el sistema de demostración puede “observar” directamente la igualdad o desigualdad entre dos instancias concretas del mismo tipo inductivo, eliminando recursivamente la aplicación del constructor más externo.
    • Para la demostración de teoremas se necesitan tipos Sigma y tipos Pi, y algún tipo de noción de igualdad.
      Me pregunto si eso puede lograrse con codificación de Scott o codificación de Church.
    • Enlace corregido: https://goosetaco.notion.site/Drinking-SICP-hatorade-and-why...

  • El libro en sí ya se está discutiendo aquí: https://news.ycombinator.com/item?id=42157558
    Me pregunto si hay alguna razón por la que el enlace vaya a una discusión más abajo y no al inicio de esa página.
    Creo que este post podría fusionarse con la discusión existente.

  • David Beazley es una figura bastante legendaria en el mundo de Python, y aunque al principio este curso parecía una idea sorprendente, después de pensarlo unos 2 segundos me pareció una combinación perfecta, así que me inscribí en la siguiente clase.
    La clave es que este formato parece ser cómo se verá en el futuro la educación continua para ingenieros de software.

    • Si no cubrieron la compilación del capítulo 5, entonces no cubrieron la mejor parte de SICP.

  • Hay un error tipográfico en el código de la sección “the substitution model”.
    ("+", ("fib", ("-", "n", 2)), ("fib", ("-", "n", 1))),
    Lo definido es fibonacci, y fib no está definido, así que esas dos llamadas a fib claramente deberían ser fibonacci.
    El código del repositorio real de GitHub sí está bien: https://github.com/savarin/pyscheme/blob/0f47292c8e5112425b5...

  • Creo que SICP es excelente.
    Sin embargo, mientras más aprendo y más estudio matemáticas, más me acerco a la conclusión de que las relaciones son un concepto primitivo más fundamental.
    Toda función puede expresarse como una forma restringida de relación, pero lo contrario no se cumple sin agregar bastante maquinaria adicional.
    Aunque las bases de datos relacionales y SQL son los ejemplos más conocidos y exitosos de programación relacional, considero que este campo sigue estando en gran medida inexplorado.
    Ahora mi interés está más cerca de enseñar fundamentos de matemáticas a niños muy pequeños que del diseño de lenguajes de programación.
    Curiosamente, enseñar predicados como “es grande” como relaciones unarias y “es mayor que” como relaciones binarias es mucho más fácil que intentar capturar esos mismos conceptos como funciones.

  • No me gusta mucho la perspectiva de “todo es una función”, porque está demasiado simplificada y a menudo no ayuda.
    Por ejemplo, hay funciones que no caben en caché, RAM, disco, etc.; funciones cuyo Big O explota, como un JOIN de N vías o búsquedas/matching; y funciones con efectos secundarios, incluida la no idempotencia.
    Casi nadie piensa en ataques de canal lateral contra funciones.
    También hay funciones no deterministas que dependen de fechas, horas, duraciones, etc.; y las funciones pueden fallar a mitad de camino o no fallar de manera elegante.
    También es difícil asumir que no consumen recursos que afectan a otras “funciones” que usan un pool de recursos compartidos.
    Los argumentos de una función pueden ser arbitrariamente grandes o complejos, pero en la realidad hay límites; entonces se necesitan punteros, y luego referencias remotas como la web o el disco.
    Avísenme cuándo parar; podría seguir hablando.

    • A veces una simplificación excesiva puede ser excelente.
      En este caso, el modelo de cálculo lambda es la base del enfoque de “todo es simplemente una función”, y es un buen modelo de computación porque, aun siendo muy simple, es más fácil de manejar y razonar que las máquinas de Turing, etc.
      Por eso está en la base de la mayor parte de la lógica computacional y los sistemas de demostración.
    • Mucho de eso se puede modelar como funciones, y en la práctica basta con escribirlo de esa forma.
      Si una función necesita recursos, se la hace requerir esos recursos; si depende de la fecha/hora, se la hace depender de la fecha/hora; si devuelve un valor no determinista, se la hace devolver un valor no determinista.
      Una de las razones por las que brilla el enfoque de programación funcional es que te obliga a tratar estas cosas con seriedad.
      Si quieres usar un recurso compartido implícitamente, debes modelarlo, y una “función” que depende de un recurso compartido implícito queda explícitamente distinguida de una función real.
    • La mitad de lo que aquí llamaste funciones en realidad no son funciones, y muchas personas en el mundo de la programación funcional tampoco las llamarían funciones.
      Más bien se parecen a procedimientos.
      Una función es un procedimiento, pero no todo procedimiento es una función.
    • Para fines teóricos, creo que esa es la única esperanza.