Cadenas Infinitas con Java 8


En este artículo presento ejemplos diversos del uso de las nuevas características en Java 8 para implementar el concepto de una cadena infinita de datos (t.c.c. stream): una estructura de datos clásica similar a una lista y que usa evaluación perezosa. El concepto desarrollado en este artículo se basa en la idea de una cadena de datos tal como la desarrollaron Abelson, Gerard y Julie Sussman usando Lisp en su libro Estructura e Interpretación de Programas de Computadora.

Los ejemplos desarrollados aquí representan un ejercicio interesante para comprender mejor la creación de clausuras a través de expresiones lambda y el valor de algunas de las nuevas características de Java 8, como lo son los métodos predeterminados y los métodos estáticos en interfaces. A lo largo del artículo se desarrollarán, progresivamente, varios ejemplos de cadenas infinitas de datos con Java, particularmente una cadena infinita de números naturales, y encima de esta, una cadena infinita de números primos usando la criba de Eratóstenes y, finalmente, una cadena infinita de números Fibonacci.

Definiendo el Tipo de la Cadena

Una lista suele ser definida en función de un sólo eslabón compuesto por dos elementos: el primero es el dato que el eslabón almacena, y el segundo es una referencia al siguiente eslabón de la cadena. Cuando una lista no tiene más eslabones, este segundo elemento puede ser nulo o hacer referencia a otro objeto que represente la ausencia de valor. Una cadena infinita de datos se basa en estos mismos principios, con la única diferencia de que el siguiente eslabón en la cadena es evaluado de forma perezosa, es decir, hasta el momento en que realmente se necesita conocer su contenido. Una forma clásica de conseguir este efecto es por medio de definir la referencia al siguiente eslabón como una clausura sin parámetros (t.c.c. thunk) que al ser evaluada genera, al punto, un nuevo eslabón de la cadena, que a su vez puede generar el siguiente eslabón cuando se necesite, y así por estilo. En otras palabras, es como si tuviésemos una cadena mágica de un solo eslabón que quisiéramos sacar de un agujero y cada vez que halamos ese único eslabón para sacarlo del agujero, un nuevo eslabón se le añade a la cadena. A esto también se le conoce como una corriente o stream, y si dicha corriente no tiene fin pues es, evidentemente, una corriente infinita.

Consideremos ahora la definición de la siguiente interfaz para representar este concepto de ese único eslabón de nuestra mágica cadena:

public interface Stream<T> {
    public T head();
    public Stream<T> tail();
    public boolean isEmpty();
}

Se puede ver que al invocar el método head() obtenemos acceso a un valor de un tipo paramétrico contenido en el eslabón, y al invocar el método tail() podemos solicitar la generación del siguiente eslabón que, como vemos, es del mismo tipo que el primero y por tanto tiene similares capacidades. Ahora bien, la comprensión de que una corriente no es nada más que este simple eslabón con dos valores asociados es de vital importancia para poder asimilar los conceptos presentados en los siguientes párrafos.

Implementación de la Cadena

Pasemos ahora a la implementación de los tipos de eslabones. Para esto nos basaremos en la definición de un tipo de dato algebraico para listas. Bajo este modelo, tenemos dos tipos de eslabones, uno de ellos puede almacenar un valor, y el otro representa un eslabón vacío. Para comenzar definamos el más sencillo de los dos: el eslabón vacío (t.c.c. Null o Nil).

public class Empty<T> implements Stream<T> {
   public T head() {
      throw new UnsupportedOperationException("Empty stream");
   }
   public Stream<T> tail() {
      throw new UnsupportedOperationException("Empty stream");
   }
   public boolean isEmpty() { return true; }
}

Un eslabón de este tipo tan solo representa la ausencia de valor y se utiliza para marcar el final de la estructura de datos cuando es finita, como veremos más adelante. Nótese como el método isEmpty() retorna verdadero.

En contraste veamos ahora la definición de un eslabón diseñado para contener un valor paramétrico cualquiera.

public class Cons<T> implements Stream<T>{

        private final T head;
        //clausura/thunk
        private final Supplier<Stream<T>> tail;

        public Cons(T head, Supplier<Stream<T>> tail) {
            this.head = head;
            this.tail = tail;
        }

        public T head() {
            return this.head;
        }

        public Stream<T> tail() {
            //desencadena evaluación de la clausura
            return this.tail.get();
        }

        public boolean isEmpty() {
            return false;
        }
}

Nótese como se provee un valor en el constructor para que el eslabón lo almacene. Sin embargo, el punto importante aquí es que en el constructor no se provee una referencia al siguiente eslabón, sino más bien se provee un objeto de tipo Supplier. Esta es una de las nuevas interfaces en Java 8 y contiene un solo método llamado get() que puede retornar cualquier valor paramétrico que queramos. Este argumento representa una clausura sin parámetros que podemos utilizar para generar el siguiente eslabón de la cadena al invocar su método get(). En Java 8 esta interfaz puede ser implementada mediante una expresión lambda (o una referencia de método), lo cual simplifica significativamente su definición. Se puede ver como el método tail(), más abajo, desencadena la invocación del método get() en la cola, evaluando mediante esto la clausura y causando como resultado la creación de un nuevo eslabón.

La fortaleza de este modelo es que el siguiente eslabón de la cadena no será generado sino hasta que se solicite mediante invocar el método tail(), que a su vez desencadena la evaluación del método get() en la clausura o thunk. Esto quiere decir, también, que cuando un eslabón se crea, no se está en la obligación de definir el siguiente eslabón de la cadena de inmediato, sino solo de proveer un medio para crearlo cuando se necesite.

Una Cadena Infinita de Números

Veamos ahora cómo podemos utilizar todo esto para escribir una pequeña pieza de código que represente una corriente infinita de números enteros comenzando desde un número n:

public static Stream<Integer> from(int n) {
   return new Cons<>(n, () -> from(n+1));
}

Como lo prometimos el eslabón está compuesto por dos valores: el primero es el valor de n, y el segundo es una expresión lamba que es la implementación del método get de la clausura (un objeto de tipo Supplier). Esta expresión lambda contiene suficiente información sobre cómo generar el siguiente eslabón de la cadena, en este caso mediante volver a invocar al método from, pero esta vez comenzando en n+1. Dicha invocación solo ocurrirá si se invoca al método tail del eslabón eslabón original, lo cual desencadenará la generación de este nuevo eslabón con el valor de n+1 y una nueva clausura capaz, a su vez, de calcular el siguiente eslabón si se necesita, y así por el estilo, infinitamente. Entonces, lo más importante es reconocer que la función de la clausura no será evaluada en el mismo instante en que se invoca el método from, sino hasta el momento en que se invoque el método tail del eslabón y por eso la clausura es el mecanismo ideal para implementar la evaluación perezosa.

Conceptualmente hablando, la corriente de datos definida arriba es infinita. Si creamos un ciclo para extraer el primer elemento de cada eslabón podríamos correr este ciclo por la eternidad (si no fuera por las limitaciones en los recursos de memoria de la computadora y por el hecho de que los enteros de Java son de 32 bits y se reinician en el extremo opuesto cuando ocurre un desbordamiento).

Una Cadena Finita Basada en un Predicado

Ahora bien, dado que la cadena es infinita y no podemos recorrerla sin entrar en un ciclo infinito necesitamos un mecanismo para limitar el tamaño de la cadena a un número discreto de elementos. Una manera de conseguir esto es por medio de crear otra cadena basada en la primera, pero esta segunda será una cadena finita. Para definir el número de elementos que la cadena finita debe contener podemos usar un predicado, es decir una función booleana que nos dice si un eslabón dado satisface nuestro criterio de selección.

Para efectos de implementar esta funcionalidad podemos usar la nueva interfaz funcional de Java 8 apropiadamente llamada Predicate. También, convenientemente, ahora Java soporta métodos predeterminados y métodos estáticos en  las interfaces lo cual nos permite añadir comportamiento directamente en la interfaz Stream original y así garantizar que este comportamiento será heredado por todas las implementaciones de forma predeterminada. Usando todas estas nuevas características podemos agregar los siguientes métodos a nuestra interfaz original:

public interface Stream<T> {
   //…
   public default Stream<T> takeWhile(Predicate<? super T>) {
       return takeWhile(this, predicate);
   }

   public static <T>  Stream<T> takeWhile(Stream<? extends T> source,
                                          Predicate<? super T> predicate) {
       if(source.isEmpty() || !predicate.test(source.head())) {
           return new Empty<>();
       }
       //un nuevo eslabón y una clausura para buscar el siguiente
       return new Cons<>(source.head(),
                         () -> takeWhile(source.tail(), predicate));
   }
}

Nótese como el método takeWhile verifica si un el valor dentro del eslabón pasado como argumento satisface el predicado o criterio de búsqueda, y si es así, lo pone en un nuevo eslabón cuya clausura contiene una función para buscar el siguiente eslabón que satisfaga el mismo predicado dentro de la corriente original.  El punto de mayor relevancia es que cuando se encuentre un eslabón que no satisface el criterio de búsqueda, en ese momento se retorna un eslabón vacío para marcar el final de la cadena y así definir una cadena finita. Cabe rescatar que, de nuevo, al invocar este método sólo se crea el primer eslabón de la cadena, y el siguiente eslabón será creado a solicitud mediante invocar al método tail en este primer eslabón creado.

Podemos ahora crear una cadena finita a partir de la cadena infinita como la del ejemplo siguiente en donde se crea una cadena que contiene los primeros 10 números naturales:

Stream<Integer> tenNats = from(0).takeWhile(n -> n < 10);

Consumiendo la Cadena

El siguiente paso consiste en implementar un método que nos permita consumir el contenido de una cadena finita. Para este propósito agregaremos un método forEach a nuestra interfaz y le proveeremos como argumento un Consumer, una de las nuevas interfaces funcionales en Java 8, que será el objeto que finalmente consumirá el valor en cada eslabón, por ejemplo, imprimiendo su valor a la salida del sistema.

public interface Stream<T> {
   //…
   public default void forEach(Consumer<? super T> consumer) {
      forEach(this, consumer);
   }

   public static <T>  void forEach(Stream<? extends T> source,
                                   Consumer<? super T> consumer) {
      while(!source.isEmpty()) {
         consumer.accept(source.head());
         //desencadena evaluación de la clausura
         source = source.tail();
      }
  }
}

Podemos ver como acá sacamos provecho que los eslabones vacíos retornan verdadero en el método isEmpty. Ahora si queremos imprimir esos primeros 10 números naturales todo lo que hay que hacer es:

from(0).takeWhile(n –> n < 10)
       .forEach(System.out::println);

Esto significa que de la cadena infinita creada por el método from deseamos crear una nueva cadena finita que contenga solo aquellos elementos que sean menores a 10, y de esta nueva cadena finita, deseamos imprimir el valor de cada eslabón a la consola del sistema.

Filtrando Elementos

Otro método de gran utilidad es uno que nos permita filtrar elementos de la cadena basándose en un predicado. Este método se distingue del método takeWhile en que este último extrae los primeros elementos de una cadena hasta encontrar uno que ya no satisface el predicado, mientras que filter debería extraer todos los elementos del cadena de que satisfacen el un predicado, independientemente de su ubicación o de que entre dos elementos candidatos haya uno que no satisface el predicado. Es decir, filter está en la obligación de recorrer la cadena completa a fin de encontrar los elementos filtrables, y por lo tanto, en el caso de cadenas infinitas, el método se debe implementar con evaluación perezosa, o de lo contrario su ejecución no tendría fin.

public interface Stream<T> {
   //…
   public default Stream<T> filter(Predicate<? super T> predicate) {
      return filter(this, predicate);
   }

   public static <T> Stream<T> filter(Stream<? extends T> source,
                                      Predicate<? super T> predicate) {
      if(source.isEmpty()) {
         return new Empty<>();
      }
       if(predicate.test(source.head())) {
          return new Cons<>(source.head(),
                            () -> filter(source.tail(), predicate));
       }
      return filter(source.tail(), predicate);
   }
}

Este enfoque tiene la desventaja de que nos podemos topar con un StackoverflowError en la última línea, pero dejando esto de lado, podemos ver como se itera sobre la cadena original hasta encontrar el primer eslabón que satisface el predicado, en cuyo caso se crea y retorna un nuevo eslabón conteniendo el valor encontrado y mediante una clausura se define la manera de buscar el siguiente eslabón del filtro, de forma perezosa. Ahora podemos hacer algo interesante como imprimir sólo los números impares entre un rango de 0 a 9 a partir de nuestra cadena infinita, algo así:

from(0).takeWhile(n -> n < 10)
       .filter(n -> n % 2!= 0)
       .forEach(System.out::println);

Claro que podemos trabajar con cualquier otro número de elementos, no solo 10, porque nuestra cadena original es infinita y es solo limitada por las condiciones de nuestro predicado. Así que de la misma sencilla manera podríamos extraer los primeros 100 números y definir un consumidor que los envíe por la red a través de un socket.

La Criba de Eratóstenes

Llegados a este punto estamos listos para implementar algo realmente interesante como la criba de Eratóstenes, un algoritmo ejemplar para crear una cadena infinita de números primos.

La criba de Eratóstenes consiste en algo como lo siguiente: supongamos que tenemos una cadena infinita de números, comenzando con el número 2. Tomamos el primer elemento (2 en este caso) y removemos del resto de la cadena (su cola) todos los divisores de 2, mediante esto, creando una nueva cadena infinita que no contiene los divisores de 2. A continuación, de esta nueva cadena infinita tomamos el siguiente eslabón, es decir 3, y removemos de la cola de la cadena todos los elementos divisibles por 3, de nuevo, generando una nueva cadena infinita que no contiene los divisores de tres. Ahora tomamos el siguiente eslabón, en este caso 5 (puesto que 4 ya había sido removido al ser divisible entre 2), y continuamos con este proceso infinito. Así, esta cadena infinita que se genera mediante este proceso solo contiene número primos.

public static Stream<Integer> sieve(Stream<Integer> s) {
    return new Cons<>(s.head(),
                 ()-> sieve(s.tail().filter(n -> n % s.head() != 0)));
}

Nótese que el método recibe una cadena original s, que podemos asumir es una cadena infinita de número naturales comenzando con el número 2. De ahí partimos para crear una nueva cadena (la criba) que solo contiene este primer elemento, y el siguiente elemento es una clausura que al ser evaluada genera un nuevo eslabón basado en volver a invocar el método sieve pero esta vez usando como cadena de origen la cola de la cadena anterior, solo que esta vez se han filtrado todos los eslabones divisibles entre el valor del eslabón anterior.

Usando todo lo que hemos definido hasta ahora podemos hacer algo interesante como imprimir a la consola los números primos menores que 100:

sieve(from(2)).takeWhile(n -> n < 100)
              .forEach(System.out::println);

Acá usamos el método from para generar la cadena de números naturales inicial comenzando con el primer número primo (es decir 2) y el método sieve usa este primer argumento para filtrar los elementos de su cola, que la clausura usará como argumento para generar el siguiente eslabón en la cadena infinita.

Una Cadena Infinita de Números Fibonacci

Con la misma simplicidad podemos definir ahora una cadena infinita de números Fibonacci, así:

public static Stream<Integer> fibonacci() {
   //first two fibonacci and a closure to get the rest.
   return new Cons<>(0,() -> new Cons<>(1, () -> nextFibPair(0,1)));
}

private static Stream<Integer> nextFibPair(int a, int b) {
   int fib = a + b, prev = b;
   return new Cons<>(fib, () -> nextFibPair(prev, fib));
}

Podemos ver que la cadena comienza con los eslabones conteniendo los valores 0 y 1, que son los dos primeros números Fibonacci, y de ahí definimos una clausura capas de generar el siguiente número Fibonacci basado en los dos anteriores.

Claramente el hecho de que Java ahora soporta expresiones lambda y métodos predeterminados ha simplificado la programación de estos ejemplos. Aunque se puede reconocer también que esto ya se podía hacer con Java antes de esta versión, es solo que se requería el uso de clases anónimas y mucho código repetitivo.

Se puede descargar implementación completa de este ejemplo desde este Gist.

Comments

  1. Al implementar código de la criba de Erastotenes funciona bien solo para números muy pequeños; no se si fue porque corrí el código con el bluej 3.1.5 que tiene integrado el jdk 8, pero instalado en mi Mac con macosx leon 10.7

    • Gracias por el comentario. Disculpa que me tomara tanto tiempo responder a tu mensaje. El tema es que los algoritmos desarrollados en el articulo no tienen la intención de ser algoritmos de alto rendimiento, sino solamente son un ejemplo de como se puede construir una cadena rudimentaria. Sin embargo probé el algoritmo generando todos los primos existentes hasta 100,000 el cual general 9592 primos y solo se tarda ~5 segundos. En mi ordenador la cadena sufre un StackOverflowError alrededor de los 126,000 nodos. Claramente la estructura de datos que usé tiene sus limitaciones. Hay formas de hacer esto de forma optimizada, pero no hubiera sido tan sencillo de explicar, que era el propósito del articulo. Quizás puedas escribir algún articulo sobre como hacer una estructura de datos en una cadena que pueda calcular números mucho mayores que la versión que yo escribí. ¿Que te parece?

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

A %d blogueros les gusta esto: