Categoría: Austra

Categorías
Austra

Destrucción creativa

El compilador de Austra sigue mejorando. Y la librería también, que todo hay que decirlo.

Finalmente, he podido añadir generación de valores aleatorios con AVX2, además de la que ya había implementado con AVX512. La dificultad residía en la necesidad de rotar circularmente un entero largo. AVX512 te da la instrucción. Pero es fácil ver que en AVX2 es posible hacer lo mismo con dos desplazamientos lógicos y una conjunción lógica.

El otro avance importante es la vectorización del algoritmo de Box-Muller para generar distribuciones normales. Ya teníamos un logaritmo natural para vectores de 256 y de 512 bits. Ahora añadimos una función que calcula simultáneamente el seno y el coseno para estos dos tipos de vectores. De hecho, hay una variante especial que es la que usa Box-Muller, en la que todos los valores están entre cero y dos veces pi, y es un poco más rápida. Añadí esta función, la utilicé en el código del generador normal y, finalmente, se ha usado en las clases de vectores, matrices y secuencias.

Operaciones in situ

El compilador intenta ahora optimizar expresiones como la siguiente:

vector1 + vector2 + vector3

¿Qué hay aquí para optimizar? A primera vista, parecería que esa expresión es candidata para reescribirse mediante un combinador lineal, que de hecho existe y se usa para algunas optimizaciones ya:

vec([1, 1, 1, vector1, vector2, vector3)

Se podría utilizar, pero este constructor añadiría tres multiplicaciones escalares innecesarias. Lo que sí nos ahorraríamos sería la creación de dos búferes temporales como resultado de las dos sumas de la expresión original. Lo que ha aprendido a hacer el compilador es a modificar la expresión original a este otro patrón, que es más general:

(vector1 + vector2).InplaceAdd(vector3)

InplaceAdd no se puede llamar directamente desde el lenguaje: es una instrucción peligrosa, porque sobrescribe el búfer del primer operando. El compilador tiene que detectar que el primer operando es de tipo temporal, y no va a utilizarse en el resto de la fórmula, o en el peor de los casos, en el resto de la sesión. Pero en el ejemplo mostrado, la primera suma es evidentemente una construcción temporal, independientemente del sitio de donde estemos sacando las tres variables usadas.

Naturalmente, podemos hacerlo mejor si ya sabemos qué son vector1 y sus dos amigos. Si son variables de sesión, no hay nada más que podamos hacer. Lo mismo ocurre si son parámetros de una función definida por el usuario o variables locales, introducidas por una cláusula let. Pero supongamos que la expresión original fuese la siguiente:

vec::random(10) + vector2 + vector3

En ese caso, el primer operando se crea en un constructor y sólo se usa en esa expresión. El compilador puede entonces crear el siguiente código equivalente:

vec::random(10).InplaceAdd(vector2).InplaceAdd(vector3)

No importa de dónde salgan vector2 y vector3. El búfer del primer operando puede ser reutilizado, y eso es lo que hacemos. El resultado de InplaceAdd, dicho sea de paso, también se puede sobrescribir con total seguridad.

Este tipo de optimizaciones es mejor que las haga un compilador, y no la librería. Es el compilador quien tiene toda la información sobre el uso de un operando. De momento, nos movemos sobre terreno seguro. Hay algunas operaciones que podrían optimizarse con este truco, pero de momento no lo hacemos. Por ejemplo, si una variable local sólo se utiliza una vez, no hay memoria compartida que tengamos que respetar. De momento, no contamos el número de usos de cada variable local.

Finalmente, hemos ampliado las optimizaciones que hacíamos sobre vectores reales a vectores complejos. Es un poco más de código, pero no se hace más lenta la compilación.

Se supone que la señorita de la imagen es Freya bailando sobre calaveras. Eran Kali y Shiva quienes practicaban este tipo de danza, pero estaba seguro de que la tía que la IA iba a generar para Freya iba a ser más guapa. ¿Y las calaveras? Pues están debajo. Pero los generadores de Inteligencia Artificial siguen teniendo problemas para generar manos humanas. De hecho, la imagen que utilizo para Austra la llamo en mi cabeza «la chica del eccema». Llevo meses haciendo retoques a sus manos, y todavía tienen problemas. Pero me gusta el tono del pelo, el óvalo facial y la postura. No se puede tener todo.

Categorías
Austra

Funciones definidas por el usuario

Vamos al grano, o, como diría Haskell B. Curry, «let’s cut to the chase». Esto ya se puede hacer en AUSTRA (en cuanto libere la próxima versión):

let mcd(a, b: int): int =
    let m = a % b in iff(m = 0, b, mcd(b, m)) in
        mcd(80, 140)

Esta es una versión recursiva del máximo común divisor, calculado no con restas, sino con el módulo de la división. Observaciones importantes:

  • Estoy declarando la función como una función local del script. Me falta permitir ahora la declaración de funciones como si fuesen definiciones paramétricas. No lo he hecho todavía porque la implementación de este tipo de funciones se realiza mediante lambdas, que se asignan a una variable local. La recursividad es posible porque la variable local está disponible, con toda la gloria de su prototipo, cuando se compila el cuerpo de la función. Cuando se trate de una definición, probablemente use un truco parecido, pero no es tan inmediato (internamente) como cuando defino una función como parte de una cláusula let.
  • Como se trata de una función recursiva, observe que he definido su tipo de retorno explícitamente. Si no, cuando el compilador encuentre la llamada recursiva a mcd va a tener que volverse loco infiriendo cuál es el tipo de retorno. Ese tipo de inferencias es posible, pero ahora mismo el compilador no está preparado para ello. En mi defensa, recuerde que incluso el gran F# necesita el modificador rec para declarar funciones recursivas. Y F# sí es un lenguaje funcional con todas las de la ley.
  • En este caso, hay una cláusula let anidada dentro de la definición de función. Austra tenía una regla para «aplanar» siempre estas cláusulas en el nivel superior, pero aquí me interesa violar la regla. Eso, o tengo que calcular dos veces el módulo de los dos parámetros.

Otro ejemplo de función recursiva, que utiliza también una cláusula let anidada, aunque esta vez, de tipo diferente:

let fact(n: int) =
    let f(n, acc: int): int = iff(n <= 1, acc, f(n - 1, n * acc)) in
        f(n, 1);
fact(10);
  • Esta es la archifamosa función factorial, pero en vez de definirla en la forma más simple, la defino con una función auxiliar que permite recursividad "por la cola".
  • Aunque el factorial es normalmente recursivo, esta vez no se llama a sí mismo, y no hay que declarar explícitamente el tipo de retorno.
  • Por el contrario, la función interna f sí se llama a sí misma, y hay que tener cuidado con su prototipo.

Claro está que podemos declarar funciones sin tanta fanfarria. Por ejemplo, el factorial es mejor programarlo así:

let fact(n: int) = [x in 2..n].prod;
fact(10);

Recuerde que empezamos con una secuencia de enteros, disfrazada de constructor de secuencias, por lo que no necesitamos poner los valores de la secuencia en un vector, ocupando memoria.

Por cierto, mire lo que podemos hacer ahora con las secuencias:

let collatz(n: int) =
    iseq::unfold(1000000, n, x => iff(x % 2 = 0, x / 2, 3x + 1))
    .until(x => x = 1);
collatz(137)

Esta función genera la secuencia de la conjetura de Collatz para el número entero suministrado como parámetro. Es un problema interesante, y aparentemente fácil, pero que aún no está resuelto. La novedad es que ahora Austra tiene un método Until y un método While que sirven para este tipo de acrobacias. Nuestra función mcd podría haberse también programado sin recursión, mezclando unfold con uno de estos métodos.

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