Mes: diciembre 2023

Categorías
Austra

List comprehensions in Austra

Hay quien traduce el término inglés list comprehension literalmente como «comprensión de listas» o, aún peor, «listas de comprensión». Lo interesante es que David Turner, el autor del lenguaje funcional Miranda, llamó inicialmente a estas expresiones Zermelo-Frankel expressions, pero alguien lo convenció para llamarlas list comprehensions, que en inglés no suena tan mal. Yo, porque soy un tipo caprichoso, cuando traduzca el término en el contexto de Austra, las llamaré constructores de secuencias, a secas. Menos pretencioso, y más comprensible, creo.

Un truco para escribir menos

¿Que es un constructor de secuencias? Pues es un truco sencillo para eso mismo: construir secuencias, pero usando menos código, con el añadido de que el resultado es normalmente más sencillo de leer (no siempre). Imagine que tenemos un vector de números reales, y queremos quedarnos con los que son enteros divisibles por dos, para elevarlos al cuadrado. En Austra, hasta ahora, haríamos esto, suponiendo que tenemos el vector ya almacenado en una variable global v:

v.filter(x => x % 2 = 0).map(x => x^2)

Con el mecanismo nuevo de construcción de secuencias, la expresión anterior se reduciría a esto:

[x in v : x % 2 = 0 => x^2]

No hace falta contar caracteres para ver que realmente hemos escrito menos. Nos hemos ahorrado los paréntesis de los métodos, y los parámetros de las funciones lambdas se han reducido a uno solo, reflejando el hecho de que los valores que fluyen por el constructor son casi siempre (casi) del mismo tipo. El resultado del constructor, en este caso, es un vector, y puedo seguir aplicando métodos y operadores tras el corchete de cierre. Por ejemplo, puedo hacer algo algo estúpido como añadir uno a cada valor (lo podía haber hecho al elevar al cuadrado):

([x in v : x % 2 = 0 => x^2] + 1).plot

Pero también podía haber transformado el vector resultante con una matriz, o cualquier otra cosa posible con un vector.

También podía haber creado una secuencia en el constructor, aunque los datos viniesen de un vector, o de una matriz:

[x in seq(v) : x % 2 = 0 => x^2];
[x in seq(v1^v2) : x % 2 = 0 => x^2];
[x in iseq(1, 100) : x % 2 = 0 => x^2];
[x in 1..100 : x % 2 = 0 => x^2];

El primer ejemplo usa una secuencia basada en un vector. El segundo, una secuencia basada en una matriz que se genera a partir de dos vectores. En el tercero, simplemente uso una secuencia de enteros construida a partir de un range. Y en el último ejemplo uso más «syntatic sugar» para generar la secuencia directamente a partir de un rango.

Ojo con las series

Con las series, hay que tener un poco de cuidado, porque el método que filtra una serie recibe como parámetro una lambda del tipo Func<Point<Date> bool>, mientras que el método Map usa una de tipo Func<double, double>. El constructor de secuencias lo tiene en cuenta, pero tenemos que recordarlo:

let mean = MSFT.mean in
    [x in MSFT : x.date >= jan2020 and x.value >= mean];

Observe que el filtro utiliza tanto la fecha como el valor de los puntos de la serie. Además, he omitido la transformación. Podemos omitir el filtro, la transformación (o proyección, en terminología SQL y C#) o incluso ambos.

Cuantificadores lógicos

De todas maneras podemos ir un poco más lejos que Python y Haskell. Vamos a comenzar por algo sencillo. ¿Es el 97 un número primo? Vamos a preguntarlo usando constructores de listas:

[all x in 2..96: 97 % x != 0]

La expresión anterior no devuelve una lista, sino un valor de tipo lógico. Será verdadero si alguno de los números entre 2 y 96 divide al número 97. Podríamos haber usado una cota superior más baja, por supuesto, pero no quiero complicar la explicación con detalles innecesarios.

all y any, en AUSTRA, no son palabras reservadas, pero en este caso se consideran palabras reservadas contextuales. La expresión anterior es equivalente a esta otra:

iseq(2..96).all(x => 97 % x != 0)

Esto, naturalmente, aunque sea ligeramente interesante, es sólo un rodeo hacia nuestro objetivo. ¿Qué tal si quiero todos los números primos del 2 al 1000?

[y in 2..1000 : all x in 2..96: y % x != 0]

La presencia de dos caracteres : nos está indicando que hay dos expresiones entre los corchetes. De hecho, estamos usando una función lambda anidada dentro de otra, y la más interna está «capturando» el parámetro de la más externa:

iseq(2, 1000).filter(y => iseq(2, y - 1).all(x => y % x != 0))

Y si quisiéramos elevar cada primo al cuadrado, añadiríamos una función de proyección al engendro que hemos creado:

[y in 2..1000 : all x in 2..96: y % x != 0 => y^2]

¡Chúpate esa, Python…!

Categorías
Música

Babelle

¡Tengo una sobrina artista! Naturalmente, el tío opina que la chica lo hace muy bien. Pero aquí le dejo el enlace a su última canción, para contrastar opiniones:

Es más guapa, por cierto, de lo que aparenta la foto, pero esa también es una opinión personal.

Categorías
Austra

Unfold

¿Cómo puedo calcular la serie de Fibonacci en Austra, utilizando una secuencia? Con vectores (voy a usar vectores y secuencias reales para evitar problemas de desbordamiento), es relativamente sencillo, si aprovechamos los safe indexers en una expresión lambda:

vec::new(128, (i, v) =>
  if i = 0 then 1 else v{i-1} + v{i-2})

El problema de esta solución es que consume memoria. Tenemos los dos últimos números generados a la izquierda (por así decirlo) del número que estamos generando, pero en realidad, es porque tenemos todo la memoria del vector ya reservada. ¿Y si quisiéramos hacerlo con las nuevas secuencias?

La solución en lenguajes funcionales

Los lenguajes funcionales suelen usar una función unfold para estos casos. Por ejemplo, en F# se define unfold de esta manera:

val unfold : ('State -> ('T * 'State) option) -> 'State -> seq<'T>

La función, en sí, escrita como una secuencia infinita, sería más o menos esto.

let fib = Seq.unfold (fun (lastValue, currentValue)
    -> Some (lastValue,
    (currentValue, lastValue + currentValue))) (1, 1)

Ahora, las explicaciones: necesitaríamos que Austra fuese un lenguaje con tipos genéricos e inferencia automática de tipos… y no es un objetivo mío a corto plazo. Nyx, que es una idea de lenguaje con capacidades numéricas y aceleración que me guardo bajo la manga, tendrá genericidad, pero no estoy del todo convencido que tenga que ser funcional «puro». La función en F#, que sería casi idéntica en Haskell, necesita un «estado» para ir arrastrando en las sucesivas llamadas. En el caso de Fibonacci, el estado son los últimos dos números generados.

De regreso a Austra

No obstante, podemos hacer algo útil para el 99% de los casos. Estos son los tres métodos que se han implementado en C# para soportar unfold en el lenguaje de fórmulas:

public static DSequence Unfold(int size,
  double seed,
  Func<double, double> unfold);
public static DSequence Unfold(int size,
  double seed,
  Func<int, double, double> unfold);
public static DSequence Unfold(int size,
  double first, double second,
  Func<double, double, double> unfold);

La idea es proporcionar sobrecargas para los casos más frecuentes. El primer caso es para cuando el estado es un solo número real. El segundo caso es más sutil: el estado es un número real… más la posición del elemento que se va a generar. Si estuviésemos en un lenguaje funcional, esa posición tendría que estar explícitamente representada en el estado. Y en el tercer caso, el estado son dos números reales, como necesitamos para la secuencia de Fibonacci.

Veamos ahora cómo se usa esto en el lenguaje de fórmulas:

-- Potencias de 2, desde 2 a 1024.
seq::unfold(10, 2, x => 2x);
-- Serie de Maclaurin para exp(1).
1 + seq::unfold(100000, 1, (n, x) => x / (n + 1)).sum;

He tenido que sumar explícitamente un uno a la serie de Maclaurin, porque era lo más sencillo. Si quiere practicar, piense en cómo calcular ln(2) con una secuencia de estas.

La secuencia de Fibonacci se calcula así:

seq::unfold(50, 1, 1, (x, y) => x + y);

Con números enteros, haríamos esto:

iseq::unfold(30, 1, 1, (x, y) => x + y);

No es la solución perfecta, pero es fácil de entender, y encima se ejecuta con rapidez.

Algo curioso relacionado con el diseño de lenguajes: imagine un lenguaje que ofrece un vec<double> y un vec<complex>, en vez del vec y el cvec del lenguaje de fórmulas de Austra. ¿Se ha dado cuenta de que el vector de complejos no podría soportar todas las operaciones del vector de números reales? El caso más evidente: no se puede ordenar el vector de complejos, ni calcular la entrada con el menor o mayor valor. Los números complejos no soportan un orden total que tenga sentido. ¿Cómo haría usted para que una clase genérica tuviese en cuenta estos detalles? Ahora mismo, si quieres hacer esto en C#, tienes que definir una clase genérica «recortada», en plan Vec<T>, y las clases finales serán clases que ya no serán genéricas, pero que añadirían la funcionalidad no común. Algo así es que lo hace Math.NET.

Ese es el problema que intento resolver: un lenguaje de programación con auto-vectorización, en el que programar una librería como la de Austra no sea tan complicado, y que me deje definir tipos matemáticos como el vector de complejos y el vector de reales utilizando una base común genérica. Hay más cosas en las matemáticas que no se ajustan a la idea de la programación de que «lo derivado tiene más operaciones».