Una de las asignaturas pendientes de los lenguajes de programación modernos sigue siendo el encapsulamiento de la iteración. Los lenguajes .NET, especialmente C#, han dado algunos pasos esperanzadores en esta dirección, y la versión 2 de C# incluye un interesante mecanismo para definir iteradores.

Freya incluye soporte para iteradores desde su primera versión, y su implementación es totalmente compatible con los restantes lenguajes .NET. Además, la sintaxis de Freya para los iteradores es más tersa que la de C#, y abre nuevas posibilidades para la optimización de estas construcciones.

UNA ASIGNATURA PENDIENTE

El Tiempo es nuestro peor enemigo. No es sólo que nos mata al final, sino que nos cuesta trabajo atraparlo, y mucho más, entenderlo. Una de las manifestaciones en Informática de nuestra pelea con el Tiempo son las dificultades que crean las dependencias temporales al programador, y que la Programación Orientada a Objetos intenta minimizar.

Considere, por ejemplo, cómo se imprime un documento en Word Basic:

doc.PrintOut(Background, Append, Range, OutputFileName,
   From, To, Item, Copies, Pages, PageType, PrintToFile, Collate,
   FileName, ActivePrinterMacGX, ManualDuplexPrint)

Aunque Word Basic es, presuntamente, un lenguaje de script "orientado a objetos" (sería mejor llamarlo "levemente inclinado a objetos", o quizás "orientado ma non troppo") este es un pésimo ejemplo de estilo. ¿Cuál parámetro debe ir antes, el número de copias o las páginas a imprimir? Es impensable que un ser humano pueda recordarlo. En estos casos, lo que suele hacerse es crear una clase PrintOut, con propiedades que correspondan a cuantos parámetros lo permitan. La mayoría de estas propiedades tendrán valores por omisión aceptables, y sólo tendremos que asignar explícitamente algunas de ellas:

printOutObj.Copies = 2;
printOutObj.Pages = "s1";
printOutObj.Print();

Lo que ahora nos interesa es que, si la clase está programada correctamente, debe ser indiferente asignar primero Pages o Copies. Y esa es la moraleja que debemos extraer:

• En la medida de lo posible, debemos evitar clases para las que haya que aclarar: "para lograr X, hay que hacer primero Y, luego Z y sólo entonces W, a no ser que antes se haya disparado el evento XYZ".

Sin embargo, los mecanismos de iteración tradicionales de los lenguajes orientados a objetos han sido precisamente de este tipo:

• Si quieres recorrer los nodos de un TArbol, primero llama a su método GetIterator. Con el objeto obtenido, haz un bucle en el que primero preguntes si EndOfIteration es True, luego utiliza la propiedad CurrentNode, y no olvides llamar a MoveNext si no quieres terminar dentro de un bucle infinito. Ah, y cuando salgas de la oficina, pasa por el supermercado y compra leche y pañales para los niños.

Muchas oportunidades para olvidar algo...

ITERADORES CERRADOS

Tradicionalmente, los iteradores se han clasificado en dos tipos: el iterador abierto y el cerrado. Al no existir una técnica universalmente aceptada de definir iteradores, la distinción se ha basado sobre todo en cómo se implementa la iteración. En vez de intentar formalizar ahora estos conceptos, haré como todos y explicaré la diferencia entre estas dos técnicas mediante ejemplos.

Un iterador cerrado se implementa casi siempre como un método, o procedimiento, que recibe un puntero a función o un evento como parámetro. Internamente, el método recorre todos los elementos de la estructura de datos y llama al método o función pasado como parámetro en cada paso. El adjetivo cerrado se debe a que la iteración en sí queda encerrada dentro de este método, y no hay que que usar más bucles cuando se llama al iterador.

Vemos un ejemplo de iterador cerrado sobre un árbol, a la vieja usanza. El iterador recorre los nodos de un árbol binario en preorden, visitando primero la raíz y sólo después sus dos ramas, de manera recursiva:

// Delphi
type
   TEventoVisita = procedure (const Valor: string) of object;
   PNodoArbol = ^TNodoArbol;
   TNodoArbol = record
      Valor: string;
      Izq, Der: PNodoArbol;
   end;

procedure PreOrden(A: PNodoArbol; Evento: TEventoVisita);
begin
   if A <> nil then
   begin
      if Evento <> nil then
         Evento(A.Valor);
      PreOrden(A.Izq);
      PreOrden(A.Der); 
   end;
end;

Es algo complicado utilizar este iterador, porque el programador debe prever su uso y preparar un método por separado que se llamará para cada nodo "visitado":

procedure TForm1.Button1Click(Sender: TObject);
begin
  PreOrden(MiArbol, MiEvento);
end;

procedure TForm1.MiEvento(const Valor: string);
begin
  Memo1.Lines.Add(Valor);
end;

Podríamos extender este mecanismo básico, añadiendo un parámetro por referencia al evento de visita, para que el cliente del iterador pudiese detener el recorrido asignando un valor especial en el mismo. Tampoco es complicado ejecutar bucles anidados: el evento de visita puede, en un momento dado, llamar a PreOrden sobre otro árbol; incluso sobre el mismo árbol.

La verdadera limitación consiste en que una segunda iteración, ya sea sobre la misma estructura o sobre otra, debe ejecutarse obligatoriamente de forma anidada o de forma totalmente independiente. No podemos organizar un algoritmo que recorra dos árboles y que en cada paso visite sólo un nodo de cada uno. ¿Le parece un algoritmo demasiado extraño? Pues es precisamente lo que hace el algoritmo de mezcla ordenada: se reciben dos listas ordenadas, y se mezclan en tiempo lineal en una tercera lista también ordenada. Para ello, se comparan los dos primeros elementos de las listas, se copia el primero de ellos en el resultado, y se mueve el iterador sobre esa lista. Esto no podríamos hacerlo si las listas sólo ofrecieran un iterador cerrado.

ITERADORES ABIERTOS EN C# V1.1

La alternativa son los iteradores abiertos. .NET v1.0 & v1.1 ofrecen un mecanismo de iteración basado en iteradores abiertos, que es el que utilizaré como ejemplo. En C#, una clase puede implementar la siguiente interfaz:

public interface IEnumerable {
   IEnumerator GetEnumerator();
}

A su vez, IEnumerator es otro tipo de interfaz con la siguiente declaración:

public interface IEnumerator {
    // Una propiedad Current de sólo lectura
    object Current { get; }
    // Un método para avanzar y saber si hemos llegado al final
    bool MoveNext();
    // Un método especial para devolver el iterador al principio
    void Reset();
}

Si tenemos una clase que implementa IEnumerable, podemos recorrer sus elementos extrayendo de ella un IEnumerator y recorriéndolo de acuerdo a este patrón:

// Falta un detalle en este código...
IEnumerator enum = ((IEnumerable) Arbol).GetEnumerator();
while (enum.MoveNext()) {
     // Hacer algo con enum.Current
     ...
}

Mejor aún, podemos utilizar la instrucción foreach de C# para simplificar el uso del iterador:

foreach (object Nodo in Arbol) {
     // Hacer algo con Nodo
     ...
}

Este mecanismo de iteración es sumamente flexible: como puede comprobar, podríamos implementar sin problema alguno una mezcla ordenada... aunque para ello tendríamos que usar directamente la interfaz IEnumerator y olvidarnos de foreach. Es decir, este tipo de iterador es aún más sencillo de usar que el iterador cerrado en la mayoría de los casos (siempre que podamos usar foreach), pero también disfrutamos de mayor flexibilidad en su uso. ¿Dónde está entonces el problema?

¡Ah, las dependencias temporales que vuelven a machacarnos! Si ha estudiado la asignatura de Estructuras de datos, recordará lo complicado que es programar un recorrido en preorden si no puede utilizar el algoritmo recursivo del iterador cerrado. Tendríamos que usar una clase que contuviese una pila de nodos, inicializada con el nodo raíz. Cada llamada a MoveNext debería sacar un elemento de la pila y almacenarlo en Current, y en compensación, empujar sus dos hijos inmediatos en la pila. MoveNext debería devolver false y terminar cuando la pila quedase vacía. ¿Fácil? Quizás, pero lo difícil no es memorizar, sino deducir el algoritmo. Inténtelo usted con el recorrido en post-orden y en orden simétrico...

ITERADORES EN C# "WHIDBEY"

La dificultad para crear un iterador de este tipo consiste en que tenemos que diseñar un autómata: un objeto con transiciones complejas entre sus estados. Y además, debemos verificar que el autómata funcione correctamente, usando técnicas matemáticas como la inducción completa, cuando muchos programadores, por desgracia, padecen alergia a estas formalidades.

Por este motivo, en la versión 2 de C#, los diseñadores del lenguaje introdujeron una técnica para facilitar la creación de iteradores. Comencemos por un ejemplo sencillo:

class MiClase {
    public static IEnumerable<int> Rango(int desde, int hasta) {
        while (desde <= hasta)
            yield return desde++;
    }
}

Tenemos una clase MiClase, que ofrece un método estático Rango, que al ser ejecutado devuelve una interfaz "genérica" IEnumerable, instanciada con enteros. La clase y el método se pueden utilizar de esta forma:

foreach (int i in MiClase.Rango(1, 10))
    System.Console.WriteLine(i);

Es difícil mostrar un equivalente exacto de este recurso en la v1.1, pero en cualquier caso, tendríamos que crear una clase iteradora como la siguiente:

class Rango: IEnumerator
{
    private int current, desde, hasta;
    private bool primeraVez = true;

    public Rango(int desde, int hasta) {
        this.desde = desde;
        this.hasta = hasta;
    }

    object IEnumerator.Current {
        get { return current; }
    }

    bool IEnumerator.MoveNext() {
        if (primeraVez) {
            current = desde;
            primeraVez = false;
            if (current > hasta)
               return false;
        }
        else {
            if (current == hasta)
                return false;
            current++;
        }
        return true;
    }

    void IEnumerator.Reset() {
        primeraVez = true;
    }
}

Asombra ver la diferencia en cantidad de líneas... y en complejidad, por supuesto. Internamente, el compilador de C# "Whidbey" transforma el código del método Range en un autómata finito parecido al que acabo de mostrar. A pesar de la finitud del autómata, podemos también crear iteradores recursivos en C# v2:

public class NodoArbol {
    private NodoArbol izquierda, derecha;
    private string valor;

    // ...

    public IEnumerator PreOrden() {
        yield return valor;
        if (izquierda != null)
            foreach (v in izquierda.PreOrden())
                yield return v;
        if (derecha != null)
            foreach (v in derecha.PreOrden())
                yield return v;
    }
}

Aquí la pila de nodo se crea de manera implícita. Nuestro iterador no es tan simple como el primer iterador cerrado que mostré, pero no es ni la décima parte de lo complejo que podría ser un iterador equivalente al estilo .NET v1.1.

ITERADORES EN FREYA

A pesar de que los iteradores de C# v2.0 son un claro avance, que por añadidura mantiene la compatibilidad con el modelo de iteración de las versiones anteriores, estos presentan algunos problemas de diseño, provocados sobre todo por la compatibilidad con el pasado y por la típica sintaxis al estilo C. Identifiquemos esos problemas:

1. ¿Cómo sabemos si un método es un iterador? No existe una forma directa: hay que comprobar si el método devuelve un IEnumerator, un IEnumerable o alguna de las variantes genéricas de estos tipos de interfaz. Luego, hay que ver si el cuerpo del método contiene "bloques de iteración"... es decir, bloques de instrucciones que contengan instrucciones yield return o yield break.
2. C# ha tenido que añadir dos nuevas instrucciones: las ya mencionadas yield return o yield break. Sin embargo, es difícil justificar la existencia de la segunda de ellas.
3. Como los métodos iteradores mencionan explícitamente las interfaces de iteración de C#, estos métodos deben implementarse obligatoriamente mediante iteradores abiertos. Luego veremos que Freya puede introducir cambios en este sentido, a modo de optimización.

El problema 1 se produce porque los lenguajes con sintaxis derivada de C no tienen marcas semánticas especiales para distinguir entre tipos de rutinas. Delphi, por ejemplo, ofrece constructor, destructor, procedure y function. En cambio, para distinguir una función de un procedimiento en C hay que mirar el tipo de retorno (la chapuza de usar void). Para resolver este asunto, Freya introduce otra marca adicional: iterator, que permite identificar inmediatamente que estamos declarando o implementando un iterador.

MiClase = class
static public
    iterator Rango(Desde, Hasta: Integer): Integer;
end;

Observe también que se simplifica el tipo de retorno del iterador. En C# teníamos que devolver IEnumerable<int>, y se nos complicaba averiguar que el iterador realmente devolvía enteros. En Freya, la intención del iterador es explícita: vamos a devolver una secuencia de valores enteros.

El problema 2 se produce en C# como consecuencia del problema 1. En principio, un iterador podría "ceder" el control de dos formas: con un return "tradicional", sin devolver elemento alguno, o con un yield, hablando con propiedad, que sí devolvería un elemento. Pero es complicado justificar una instrucción return "a secas" dentro de una función declarada para que devuelva un IEnumerator. Además, como la identificación de los bloques de iteración se basa en detectar una de las dos variantes de yield, si yield return se simplificase a un return de los de toda la vida, se complicaría esta identificación.

En Freya no necesitamos estas dos variantes de yield. Nos basta con una instrucción llamada Yield (al estilo de Exit, Break y Continue en Delphi Pascal), porque podemos seguir usando Exit para abandonar definitivamente el iterador sin devolver valor alguno. La declaración e implementación del iterador sobre un rango, mostrado antes para C#, tendría este aspecto en Freya:

// Freya
namespace Freya.Iteration.Examples;
public

    MiClase = class
    static public
        iterator Rango(Desde, Hasta: Integer): Integer;
    end;

implementation for MiClase is

    iterator Rango(Desde, Hasta: Integer): Integer;
    begin
        for Result := Desde to Hasta do
            Yield;
    end;

end.

Por último, creo que está clara la causa del problema 3, pero no es muy evidente qué mejoras se pueden hacer en este sentido. Veamos antes una posible implementación recursiva del iterador en preorden sobre árboles binarios, en Freya:

implementation for NodoArbol is

    iterator Preorden: string;
    begin
        Result := Value;
        Yield;
        if Izquierda <> nil then
            for Result in Izquierda.Preorden do
                Yield;
        if Derecha <> nil then
            for Result in Derecha.Preorden do
                Yield;
    end;

¿Hay algo en el iterador anterior que lo vincule al mecanismo de iteración basado en IEnumerator? Evidentemente no. Freya tiene que soportar este mecanismo, de todos modos, para ser compatible con otros lenguajes .NET, y porque hay casos que no pueden resolverse mediante un iterador cerrado, como el ya mencionado algoritmo de mezcla ordenada. Pero aparte de una implementación de iterador abierta, un iterador Freya puede ofrecer como servicio adicional una implementación interna basada en iteración cerrada, para uso interno del código escrito en Freya.

En el caso del recorrido en preorden, Freya crearía también, de ser necesario, un método interno que recibiría como parámetro un delegado. Si en la misma clase, o en una clase derivada declarada e implementada en Freya, se utiliza el iterador Preorden, puede valorarse la posibilidad de crear un método anónimo con el cuerpo de la instrucción for, y pasar el correspondiente delegado al método interno creado como alternativa de iteración. Observe que la llamada a for dentro del propio iterador debería utilizar un tercer caso de generación de código para for.

Y hay más posibilidades. ¿Cree usted que alguien utilizaría en serio la siguiente instrucción, si sabe que va a traducirse en la creación de un objeto que implementa IEnumerator, seguida por un bucle basado en ese objeto?

for I: Integer in MiClase.Rango(0, 9) do
    // etcétera

Freya podría aplicar aquí una técnica interna de inlining, y expandir en línea la definición del propio iterador sobre rangos. De todos modos, Freya proporcionaría una segunda implementación adicional basada en las interfaces de iteración de la versión 1.1, para poder utilizar el iterador desde C# y los restantes lenguajes de la plataforma.

ITERADORES ANONIMOS EN FREYA

Tanto Rango como Preorden son iteradores con nombre: al traducirlos a la semántica de las versiones anteriores de .NET, estos iteradores se comportarían como funciones que devuelven una implementación de alguna de las interfaces de iteración. Sin embargo, .NET también permite que la propia clase sea quien implemente IEnumerable. Para expresar este caso en Freya se necesitan iteradores anónimos.

En realidad, ya existen otras construcciones "anónimas" en Freya, por otros motivos. Tal es el caso de los constructores y destructores. Los recursos anónimos se declaran en Freya usando el nombre de la clase:

NodoArbol = class
    // ...
public
    constructor NodoArbol;
    destructor NodoArbol;

    iterator NodoArbol: string;
end;

La sintaxis de Freya nos echa una mano para poder distinguir entre sí todos estos recursos anónimos. Los lenguajes inspirados en C, por el contrario, tienen que recurrir a chapuzas como la tilde (˜) para distinguir al destructor del constructor. Para el indexador anónimo, además, se utiliza this como nombre, rompiendo la uniformidad.

Freya debe implementar sus métodos en una sección privada de la unidad, para mantener una de las características clásicas de Pascal. Y aquí también hay novedades: como los cuerpos de los métodos se agrupan en una sección implementation for (una para cada clase), no se necesita la notación NombreClase.NombreRecurso:

implementation for NodoArbol is

    constructor NodoArbol;
    begin
        // etcétera
    end;

    destructor NodoArbol;
    begin
        // etcétera
    end;

    iterator NodoArbol: string;
    begin
        // etcétera
    end;

end.

Nuevamente, la marca semántica del tipo de recurso de la clase nos salva la vida, ahorrándonos la repetición absurda del nombre de la clase, sin perder la distinción entre los tipos de recursos. Este ahorro sería más complicado en Delphi, por su naturaleza híbrida. En Freya no hay "procedimientos globales", por lo que tampoco hay ambigüedad en ese sentido.