Pensar con lenguajes de arreglos

 (github.com/razetime)
2 puntos por GN⁺ 2024-01-15 | 1 comentarios | Compartir por WhatsApp
  • La programación en K se enfoca en mover código experimentado en el REPL a scripts, reduciendo continuamente patrones imperativos grandes a patrones de arreglos declarativos más pequeños
  • Los scripts de ngn/k se ejecutan línea por línea como si fueran entradas del REPL, y con \\l file.k se pueden cargar en el REPL datos y funciones guardados
  • Si se traslada literalmente la multiplicación de matrices con triple bucle al estilo Wikipedia, se termina con muchas variables globales, bucles anidados y mutación, lo que va en contra de las ventajas de K
  • El proceso de mejora pasa por fold +/, each ', eachright /:, eachleft \:, eliminación de la transposición y conversión tacit, hasta condensarse de matmul: {x{+/x*y}\:y} a matmul: (+/*)\:
  • El ejemplo de multiplicación de matrices muestra que la habilidad en K consiste en repetir el proceso de condensar código para convertir procedimientos complejos en expresiones de arreglos más legibles

Flujo de desarrollo en K centrado en el REPL

  • El código fuente completo puede verse en GitHub en matmul.k
  • La programación en K ocurre en su mayor parte en el REPL, lo que facilita experimentar y mejorar rápidamente sobre código previo
  • La combinación de ngn/k y rlfe soporta historial con flechas arriba/abajo, suficiente para desarrollar programas K más grandes
  • Es natural probar primero las funciones en el REPL y luego moverlas al código real
  • El prettyprinting de ngn/k siempre devuelve datos K válidos, por lo que algunos valores pueden precalcularse para acelerar el programa

Modelo de ejecución de scripts K

  • Un script K se ejecuta como si se hubiera escrito en el REPL
    • Cada línea se ejecuta en orden
    • Si una línea no termina en punto y coma, se imprime el valor de retorno
  • Los scripts permiten definiciones en varias líneas para mejorar la legibilidad
  • Para usar en el REPL datos y funciones guardados, se ejecuta \\l file.k
    • El archivo se ejecuta
    • Los datos del archivo se cargan
    • Si se carga el mismo archivo varias veces, los datos previos se sobrescriben
  • En la ayuda del REPL accesible con \\ se pueden consultar más comandos

Cómo reducir patrones en un lenguaje de arreglos

  • K y la programación de arreglos son un proceso de simplificar patrones continuamente
  • Incluso los patrones grandes y difíciles de manejar tienen una o más formas de reducirse a estructuras más pequeñas, declarativas y fáciles de leer
  • Una discusión relacionada puede verse en detalle en Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17
  • Un punto de partida común es querer traducir a K algoritmos conocidos de GeeksforGeeks o Wikipedia
  • El ejemplo usa la multiplicación de matrices

Qué pasa al trasladar literalmente la multiplicación imperativa de matrices

  • El algoritmo de multiplicación de matrices de Wikipedia llena la matriz C con un triple bucle i, j, k y una acumulación en sum
  • Si se traduce directamente a K, se terminan asignando muchos valores globales como A, B, n, m, p, C, i, j, k y sum
  • Ese código usa K como si fuera un lenguaje imperativo, así que no encaja bien con su diseño
  • El problema se reduce a tres puntos
    • Hay muchas asignaciones globales
    • Permanecen varias capas de bucles anidados
    • La mutación ocurre con frecuencia

Empezar a compactar desde el bucle más interno

  • El bucle más interno inicializa sum en 0 y recorre k acumulando A[i;k]*B[k;j]
  • La primera mejora es usar el fold / para convertir la suma en +/
    • La variable global sum desaparece
    • Se reorganiza a una forma como C[i;j]::+/...
  • Luego, aprovechando que each ' devuelve un arreglo, se puede usar directamente el valor devuelto por los bucles anidados sin mutar C
  • Después de esta etapa solo quedan tres bucles sin mutación, y las variables clave son i, j, k

El proceso de eliminar k, j e i

  • Las funciones de las tres variables son las siguientes
    • i indexa cada fila de A
    • j indexa cada columna de B
    • k indexa cada columna de A y cada fila de B
  • k hace que se emparejen cada fila de A y cada columna de B para multiplicarlas, así que puede eliminarse el índice intermedio y hacer la correspondencia de forma directa
    • En esta etapa desaparecen un bucle y la necesidad de m
  • Para eliminar j, hay que tomar cada columna de B y emparejarla con A[i]
    • Se transpone B y se usa eachright /: para emparejar cada elemento
  • i también puede eliminarse de la misma manera
    • Se usa eachleft \: para emparejar cada fila de A con cada columna de B
  • Tras este proceso, sin globales, queda la siguiente forma
matmul: {x{+/x*y}/:\:+y}

Eliminar la transposición y llegar a la forma tacit final

  • La transposición + es costosa, así que puede eliminarse
  • El enfoque previo es la forma ingenua de multiplicar cada fila de x con cada columna de y
  • En cambio, si se alinean las filas de B con toda A, se puede realizar implícitamente el mismo trabajo
matmul: {x{+/x*y}\:y}
  • Esta función puede convertirse a forma tacit aplicando las reglas del Capítulo 3
  • El resultado final es el siguiente
matmul: (+/*)\:

Una intuición de lenguajes de arreglos que se forma con práctica

  • matmul: (+/*)\: queda organizado como una función de multiplicación de matrices idiomática en K
  • Al principio, el proceso de condensación puede parecer que tiene muchos pasos
  • A medida que se practica K, la condensación de código se vuelve una tarea más fácil e intuitiva
  • La multiplicación de matrices es un procedimiento simple que encaja bien con el soporte de arreglos de K
  • En capítulos posteriores se abordarán algoritmos que no encajan tan bien con K y cómo tratarlos

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-01-15
Opiniones en Hacker News

  • En realidad, lo que mostró de forma más convincente el potencial de los lenguajes de arreglos fue un video en el que Aaron Hsu explicaba cómo desarrolló Co-dfns, un compilador APL paralelo: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
    En HN, bajo el nombre arcfide, también escribió varias veces sobre la densidad semántica, y explicó que el código APL está diseñado para que se pueda ver, casi sin desplazarse, cómo funciona, su contexto alrededor y sus dependencias dentro de una sola pantalla: https://news.ycombinator.com/item?id=13571159
    La idea es que, cuando algo se vuelve tan conciso que el nombre de un algoritmo llega a tener una longitud similar a la de escribir el algoritmo en sí, uno empieza a leer el código por modismos, como si leyera frases en inglés, y puede ser más rápido modificar directamente todos los usos visibles en pantalla que crear abstracciones reutilizables.

    • Me da curiosidad si un LLM con una ventana de contexto finita quizá maneje APL mejor que otros lenguajes.
    • Creo que tener que escribir una explicación tan larga se debe a que el código se ve horrible. Si hubieran elegido símbolos que se vieran menos feos al pegarse unos con otros, quizá no tendrían que pasar 18 horas convenciendo a la gente de que el lenguaje no es malo.

  • Si no conoces bien la programación de arreglos, recomiendo The Array Cast como material introductorio: https://www.arraycast.com/episodes/
    La URL del RSS es https://www.arraycast.com/episodes?format=rss

    • Escuché más o menos los primeros 5 episodios de The Array Cast para ver si me convencía, pero al final no me convenció. Los conductores decían que la notación breve de los lenguajes de arreglos y los símbolos no ASCII están bien una vez que te acostumbras, y que vale la pena aceptarlos por sus ventajas, pero la mayoría de esas ventajas ya son cosas familiares en los lenguajes mainstream actuales gracias a las funciones de orden superior.
      map/filter/reduce ya están prácticamente en todas partes, y sentí que se pasaba por alto el hecho de que pueden usarse sin aprender un nuevo sistema de notación parecido a ideogramas.
    • Gracias a eso conocí BQN, pero todavía no sé si lo usaría en un entorno real de producción. Aunque me gusta, salvo R, NumPy y Julia, la mayoría de los lenguajes de arreglos resultan extraños, y si me meto a fondo en APL, J o BQN, siento que terminaría alejándome yo mismo de las personas que podrían ayudarme después.

  • En los 70 conocí APL/APL2 en terminales de papel que de verdad usaban sobreimpresión, y me enganché de inmediato; pero más tarde, después de descubrir la programación funcional con ML y Haskell, me di cuenta de que lo que realmente me gustaba de APL no eran tanto los arreglos sino su capacidad de composición de funciones.
    Haskell es completamente puro y tiene tipos aplicados de forma generalizada, así que en este aspecto es mucho mejor; también me resultó más divertido y potente que APL. Hice muchos proyectos pequeños y medianos, también un prototipo para mostrar que el parser de LLVM Flang podía implementarse con parser combinators, y cada año resuelvo Advent of Code en apenas unos cientos de líneas en total. Si te gusta APL, vale la pena probar Haskell.
    Hoy, el aspecto de APL como “notación como herramienta de pensamiento” me parece más bien una forma de racionalizar una concisión excesiva. Sirve para mostrar el poder de la composición, pero también puede perjudicar la claridad.

    • En este tema termino repitiendo siempre lo mismo, pero desde que aprendí a usar bastante bien Haskell point-free, casi no he vuelto a tocar J ni K. Cuando además entran los functores, se vuelve más potente que los trenes de verbos; <=< ya existe, y usando algo equivalente a fmap todo funciona realmente bien.
      |||, +++, &&&, *** también son buenos, y se pueden crear operadores UTF-8 propios para hacerlos más cortos y bonitos. Aun así, es una lástima que en el trabajo real o en el código Haskell serio publicado rara vez se sea tan amable con el espacio vertical de la pantalla.
    • Me gustaría poder ver un enlace al código fuente de Advent of Code.

  • Me da curiosidad cómo se suelen abordar en los lenguajes de arreglos problemas del tipo “encontrar todos los números menores que N para los que el predicado P es verdadero”. Por ejemplo, encontrar primos menores que 1000 o ternas pitagóricas con z menor que 1,000,000.
    En un lenguaje imperativo se comprobaría el predicado en un bucle, y en uno funcional se usaría recursión o map/filter sobre listas perezosas, pero entiendo que en un lenguaje de arreglos normalmente se crea el arreglo 1..N, se aplica el predicado para crear un arreglo de máscara y luego se filtra el arreglo original con esa máscara.
    Si N es grande, como mil millones, y el predicado casi nunca es verdadero, crear dos arreglos temporales enormes —el arreglo 1..N y la máscara— parece un gran desperdicio de memoria y recursos. Me pregunto si los lenguajes de arreglos se vuelven lentos por crear continuamente estos arreglos temporales, o si las implementaciones optimizan con algo como evaluación perezosa.

    • Sí, se desperdicia mucha memoria. Dicho eso, la memoria es barata y, si hace falta, el cálculo se puede dividir en bloques. En la práctica rara vez se agota la memoria, pero el blocking es útil para mantenerse en niveles más bajos de la jerarquía de caché.
      Los lenguajes escalares, por el contrario, procesan por defecto un valor a la vez, así que desperdician el paralelismo potencial que los lenguajes de arreglos aprovechan con algoritmos SIMD. Eso tampoco suele verse como un gran problema porque estamos acostumbrados al estado actual, y la solución también es el blocking.
      Que un lenguaje de arreglos sea realmente bueno depende del problema. En la gran mayoría de usos prácticos, el rendimiento no importa en absoluto, y creo que la reputación de k viene más de que kdb es rápido como base de datos que de que las implementaciones de k sean lenguajes rápidos en sí mismos. Aun así, enfocarse en algoritmos de arreglos elegantes en vez de optimizaciones específicas de cada máquina puede producir velocidades sorprendentemente altas: https://mlochbaum.github.io/BQN/implementation/versusc.html
    • Hay varias formas de evitarlo. La evaluación perezosa es una de ellas, y Kap la usa: https://aplwiki.com/wiki/KAP
      Otra forma clara es hacer fusión de bucles de todo el cuerpo para que no se creen arreglos temporales. Una opción más simple es dividir los arreglos de entrada y salida en chunks de unas decenas de KB para limitar el uso innecesario de memoria temporal; que yo sepa, ningún lenguaje de arreglos lo hace automáticamente, y algún día me gustaría probarlo en CBQN. El usuario también puede hacerlo manualmente y, para maximizar el rendimiento, en realidad hay que hacerlo con frecuencia.
    • Tu intuición es mayormente correcta, pero en la práctica es un problema poco común. En la familia de k, por ejemplo en ngn/k, hay una estructura perezosa que trata algo como !10000000, el iota de 0 a diez millones, como un rango simple, sin crear realmente un arreglo de diez millones de enteros.
      Claro que, según qué operador uses, ese arreglo puede terminar creándose de todos modos. También hay optimizaciones que convierten patrones como +|x, que invierte x y toma el primer elemento, en simplemente tomar el último elemento.
    • Parece que estás asumiendo que la creación del arreglo ocurre literalmente. No hay razón para que un lenguaje de arreglos no pueda procesar internamente por chunks. Aunque pidas un arreglo de 10 mil millones de enteros, puede no crearlo ingenuamente tal cual.
    • Muchos lenguajes de arreglos sí tienen este problema. Más precisamente, el problema es que el enfoque simple e intuitivo tiende a calcular muchísimo más de lo necesario.
      Por supuesto, se puede evitar escribiéndolo de otra manera, pero esas soluciones pueden ser más largas y menos bonitas. El dialecto de APL en el que estoy trabajando, Kap, maneja varios casos posponiendo el cálculo hasta que el resultado sea necesario, de modo que puedas escribir el código de forma intuitiva sin calcular resultados que se van a descartar.

  • Las mayores revelaciones que tuve al usar lenguajes de arreglos, especialmente k, fueron estas. Los verbos son algoritmos, y en lenguajes imperativos u orientados a objetos muchas veces hay que implementar directamente algoritmos comunes como find, sort o group.
    Una sucesión de verbos o adverbios fue la forma de composición más directa que he usado, y la composición es fácil y natural. Un programa deja de verse como una colección de sentencias y expresiones, y pasa a verse como una composición de algoritmos.
    Tratar de forma consistente los conceptos de dominio y codominio en arreglos, mapas y funciones simplifica las decisiones de diseño, y si la evaluación va de derecha a izquierda, al leer el código no tienes que saltar la vista de un lado a otro.
    Es posible, y preferible, enviar el código hacia los datos en vez de traer los datos al código. La mayoría de los proyectos grandes en k, excluyendo comentarios, caben dentro del MTU de red, es decir, 1540 bytes. Como bonus de k, las vistas pueden implementar relaciones funcionales directamente, y la carga en caliente de código mediante el intérprete permite aplicaciones que corren “para siempre”.

  • Mi impresión personal, sesgada y limitada tras resolver problemas en el lenguaje K como preparación para entrevistas de trabajo, es que el lenguaje es intencionalmente críptico. Es un buen lenguaje para acertijos y soluciones ingeniosas.
    Pero creo que lo que enseña los lenguajes de arreglos y cómo pensar con arreglos es la experiencia de trabajar con arreglos de NumPy en Python.

    • Me da curiosidad saber para qué entrevista fue.

  • Tras usar J unas 50 horas, honestamente sentí que este paradigma está demasiado inclinado hacia un solo lado.
    No sé si pensar todos los problemas como anidamientos de arreglos ayuda como herramienta de pensamiento. Si puedes crear libremente estructuras de datos que capturen bien el problema, la parte algorítmica puede simplificarse mucho.
    Creo que para usar APL/J/K tienes que ser más inteligente. En lenguajes más flexibles, enfoques que están disponibles de inmediato a menudo no son posibles ahí, así que hay que transformar el problema, y ese proceso puede requerir mucho más pensamiento.

  • Este ejemplo está basado en K, pero otro lenguaje de arreglos es J: http://jsoftware.com
    En J, si escribes dot =: +/ . *, P =: 2 3 4, Q =: 1 0 2, P dot Q, devuelve 10, el producto punto de P y Q.

    • El lenguaje de arreglos original es APL, y el producto punto puede escribirse como dot←+.×. Pero si la notación desarrollada es tan corta como un nombre razonablemente breve, no hace falta ponerle nombre, y quizá incluso haya que poner espacios alrededor del nombre.
    • Todavía no veo bien qué ventaja tiene esto sobre Haskell. Se puede escribir dot = (sum.) . zipWith (*), p = [2, 3, 4], q = [1, 0, 2], p `dot` q.
      A mis ojos, la única diferencia parece ser que se les da nombre a sum y zipWith, y que el lifting o las transformaciones estructurales no ocurren “por arte de magia”.
    • En KlongPy, el producto punto se escribe dot::{+/x*y}. La forma es P::[2 3 4], Q::[1 0 2], dot(P;Q).

  • Al ver el ejemplo, no entiendo qué sentido tiene. ¿De alguna manera tiene mejor rendimiento?
    La sintaxis de multiplicación de matrices es más corta, pero parece ser porque hay que llevar en la cabeza mucho contexto integrado sobre cómo funciona el lenguaje K.

    • El hecho de ser más conciso tiene valor por sí mismo. Es especialmente parecido si pensamos que las matemáticas son un proceso de comprimir cada vez más conceptos en definiciones de más alto nivel. Cuando los conceptos de más alto nivel se vuelven elementos primitivos, puedes pensar más rápido y construir cosas más complejas.
    • Puede tener mejor rendimiento. Las computadoras son muy rápidas recorriendo arreglos, sobre todo si pueden aprovechar SIMD, pero eso no es todo.
      Vale la pena probar un lenguaje de arreglos y jugar con él hasta entender el paradigma. A menudo el código imperativo se expresa mejor en estilo de arreglos, y a veces funciones largas y llenas de detalles se simplifican muchísimo usando solo operaciones de arreglos, o combinándolas con otros estilos.
    • La verbosidad también tiene un costo, y si crees que solo las funciones realmente complejas tienen el privilegio de ser verbosas, el sentido se vuelve fácil de ver.
      En Haskell, comparando (+) <$> Just 1 <*> Just 2 con do x <- Just 1; y <- Just 2; Just (x + y), para este nivel de complejidad siempre prefiero la primera. La segunda ocupa más espacio y hace sentir que está pasando algo más complejo.
      Si fuera una tarea más compleja, en vez de usar la segunda forma, querría descomponerla en funciones pequeñas para que tenga sentido una variante de la primera. Es una concesión que cambia “algunos principiantes pueden leerlo rápido” por “lo puede leer cualquiera por encima de principiante”.
      Creo que optimizar para “algunos principiantes pueden leerlo” tiene rendimientos decrecientes muy grandes, y en su lugar apunto a que sea legible para “principiantes en adelante” o, según el caso, “intermedios en adelante”.

  • Hay muchas razones para usar cualquier lenguaje, y muchas razones para no usarlo. Pero lo esencial no es la notación breve, la claridad relativa ni la capacidad de compilar a código rápido, sino si el programador que llegue después podrá modificar y mantener ese código para su uso real.
    Con demasiada frecuencia los programadores quieren demostrar sus habilidades leet, sin considerar a las pobres personas que después tendrán que hacerse cargo de ese código. En la práctica, mucho código leet tiene que desecharse o reescribirse por completo para obtener algo que pueda sostenerse a largo plazo.
    Me tomó mucho tiempo entender esto, y desde entonces intenté escribir código limpio, simple y comprensible para que otras personas pudieran mantenerlo. Demasiadas veces el código descartable se solidifica como infraestructura básica de una organización, y se convierte en algo incomprensible para la siguiente generación.