Iteradores e a história do for (final)
Publicado por fsomalia em 30, Agosto, 2008
No post anterior, você viu que o iterador é ótimo porque protege a sua coleção. O iterador foi a solução orientada a objeto para as coleções. O iterador permite o encapsulamento: ninguém precisa saber como meu objeto guarda essa coleção; se os clientes quiserem iterar por ela, é o iterador do meu objeto que dita as regras.
Só que em C#, a sintaxe para criar um iterador é um pouco trabalhosa. Convenhamos, se o iterador é uma coisa tão boa, porque é tão burocrático criá-los?
Ouvindo a voz da razão, a Microsoft incluiu no .NET Framework uma sintaxe mais direta para criar iteradores. Mas para você entendê-la, vou lhe apresentar minha amiga co-rotina!
Co-rotinas: seu companheiro de aventuras!
Creio que você já ouviu falar no termo sub-rotina. A criação de sub-rotinas foi histórica e permitiu fazer coisas fantásticas. Não fossem elas, estaríamos fazendo goto até hoje.
Uma sub-rotina é um trecho de código marcado com um ponto de entrada e um ponto de saída. Quando uma sub-rotina é chamada, ocorre um desvio do programa para o ponto de entrada, e quando a sub-rotina atinge seu ponto de saída, o programa desaloca a subrotina, e volta para o mesmo ponto de onde tinha saído. Assim, ó:
Chamada a uma sub-rotina
Quando uma subrotina termina, ela é desalocada das estruturas internas do programa. Seu tempo de vida termina. Como se ela nunca tivesse existido. Podemos chamá-la de novo, claro, mas será uma nova encarnação da sub-rotina: o programa novamente começará executando desde seu ponto de entrada.
Uma co-rotina não funciona assim. Na co-rotina, o trecho de código trabalha conjuntamente com o código chamador até que sua tarefa seja terminada. O controle do programa é passado da co-rotina para o chamador e de volta para a co-rotina até que a tarefa da co-rotina termine.
Numa co-rotina, existe o ponto de entrada (que é por onde se inicia o processamento), um ponto de saída (pela qual o tempo de vida da co-rotina termina), e um ponto de retorno parcial. Esse retorno parcial não termina com a vida da co-rotina. Do contrário, apenas passa o controle do programa para a rotina chamadora, e marca um ponto de re-entrada. Quando a rotina chamadora devolver o controle para a co-rotina, o processamento começa a partir do último ponto de retorno parcial.
Na prática, uma co-rotina permite retornar valores diversas vezes antes de terminar o seu tempo de vida. Se eu fosse desenhar isso, seria algo assim:
Rotina e co-rotina interagindo
A chave para criar uma sintaxe simples para iteradores foi implementar as co-rotinas em C#. Por quê? Bom, tem a ver com o fato de que o foreach itera por todos os itens que alguém entregar para ele. Quem tem essa responsabilidade de entregar coisas para o oreach é o cara que vem depois do in. Na sintaxe padrão, o cara que vem depois do in precisa ser um objeto iterador, alguém que implemente a interface IEnumerable.
Mas na nova sintaxe, não precisa ser. Só precisa ser uma co-rotina. Ora, o foreach vai andar quantas vezes o iterador quiser. O foreach só precisa que, a cada passo, o iterador retorne um valor para ele. Então, tanto faz o iterador ser um objeto que implementa IEnumerator (com seus MoveNext(), Reset() e Current) ou uma co-rotina, que também retorna várias vezes.
Agora, mãos na massa. Uma co-rotina, em C#, é um método ou propriedade que retorna IEnumerable<>. Esse IEnumerable<> é semelhante ao IEnumerable padrão, só que ele especifica o tipo de retorno da co-rotina. Se a co-rotina retornar inteiros, declare IEnumerable<int>; Se a co-rotina retornar Endereco, declare IEnumerable<Endereco>.
Exemplo:
IEnumerable<int> CoRotina()
{
yield return 4;
yield return 3;
yield return 2;
yield return 1;
}
O que temos de novo aqui é o yield return. O yield return faz um retorno imediato à rotina chamadora, assim como o return normal. Mas o yield return também marca também um ponto de reentrada no lugar onde ele aparece. Assim, quando a co-rotina volta a ser executada, ela começa a partir do último yield return que foi chamado. Note que o yield return deve retornar o mesmo tipo que o declarado no IEnumerable<>. No nosso exemplo, se você tentar fazer um yield return “Teste”, o programa não compila porque “Teste” é string e não int. Da mesma forma, tentar fazer um simples return 4 também dá erro porque 4 é um int, e não um objeto IEnumerable<int> (a checagem de tipo do retorno simples continua valendo em co-rotinas).
E como chamamos uma co-rotina? Com o todo-poderoso foreach, é claro!
foreach (int i in CoRotina())
{
Console.Write(i + " ");
}
// Imprime: 4 3 2 1
Como funciona isso? Quando o foreach chama CoRotina() pela primeira vez, o controle é passado para a co-rotina, que inicia seu código desde yield return 4. Acontece que, nesse ponto, yield return obriga o retorno parcial do valor 4, suspendendo temporariamente a execução da co-rotina. Esse valor é retornado para o foreach, que o o joga para a variável i. Quando o foreach chama novamente CoRotina(), o código é executado a partir de yield return 4. A co-rotina retorna então o valor 3, e marca um ponto de reentrada nesse local. E assim por diante, até que a co-rotina finalize todos os retornos.
Embora isso não pareça ter muito a ver com nosso problema de proteger as coleções, na verdade, tem tudo a ver. Vamos revisitar nossa amiga Pessoa, aquela que tinha vários Endereços.
Pessoas e seus problemas de moradias, parte 2
Recapitulando o problema visto no último post, tínhamos uma Pessoa que possuia vários Enderecos (de residência, comercial, de correspondência, etc). Havia dois requisitos em relação a isso: primeiro, uma pessoa não podia aceitar qualquer endereço, era preciso fazer um filtro de endereços válidos. Segundo, os endereços precisavam ficar disponíveis para que o catálogo de endereços pudesse imprimí-los.
Nossa solução então foi usar um objeto iterador. Esse objeto iterador iria permitir que usuários externos (o catálogo de endereços) iterassem pelos endereços, ao mesmo tempo que a coleção interna de endereços ficasse protegida contra inserções desreguladas. Para lembrar o código fonte desse iterador, corra ao post anterior e dê uma olhada.
Com as co-rotinas do C# 2.0, a criação desse iterador ficou mais simples. Veja:
class Pessoa
{
string _nome;
List<Endereco> _ends;
public Pessoa(string nome)
{
_nome = nome;
_ends = new List<Endereco>();
}
public bool AdicionarNovoEndereco(Endereco endereco)
{
if (endereco.Rua.IndexOf("sabão", StringComparison.CurrentCultureIgnoreCase) < 0)
{
_ends.Add(endereco);
return true;
}
return false;
}
public string Nome
{
get { return _nome; }
}
// Trocamos o objeto iterador por uma co-rotina
public IEnumerable<Endereco> Enderecos
{
get
{
for (int i = 0; i < _ends.Count; i++)
{
yield return _ends[i];
}
}
}
}
Três coisas mudaram aqui:
- Modificamos a propriedade Enderecos, que retornava um objeto iterador (IteradorEndereco), por uma co-rotina. Uma propriedade pode ser uma co-rotina, basta retornar um IEnumerable<> e fazer uso de yield return
- Nossa classe IteradorEndereco, que era o objeto iterador, não precisa mais existir. Uma classe a menos, mais facilidade para implementar iteradores, ponto positivo!
- Internamente, a co-rotina faz um laço de repetição sobre a coleção de endereços. Isso é totalmente válido, na prática, a co-rotina vai terminar depois de passar por todos os elementos da coleção. Eu usei o for para iterar, mas poderia ter usado o foreach também!
Os iteradores feitos com co-rotinas podem ser bem mais complexos, depende de o que e como você quer iterar. Suponhamos que você queria iterar só pelos 5 primeiros endereços da pessoa. A co-rotina pode ser escrita assim:
public IEnumerable<Endereco> Top5Enderecos
{
get
{
for (int i = 0; i < _ends.Count; i++)
{
if (i > 4)
{
yield break;
}
yield return _ends[i];
}
}
}
Note o uso de yield break para parar a iteração quando 5 endereços já iverem sido retornados. O yield break funciona como um ponto de saída da co-rotina: depois que yield break é chamado, a co-rotina termina seu tempo de vida.
Mais exemplos? Vamos lá.
Brincadeiras com co-rotinas
Vamos expandir nosso Iterador Simples, mostrado no post anterior. Agora, vamos criar uma classe não instanciável que permite iterar uma quantidade de vezes. Vamos usar co-rotinas parametrizadas como iteradores.
abstract class IteradorSimples
{
// Itera uma quantidade de vezes
// retornando numeros de 1 ate o especificado em quant
public static IEnumerable<int> IterarAte(int quant)
{
if (quant < 1)
{
throw new ApplicationException("Não posso iterar " + quant + " vezes");
}
return Iterar(1, quant);
}
// Itera pelos numeros inteiros a partir de "de", até "ate"
// Para iterar em ordem descrescente, basta informar "de" com valor maior que "ate"
// Retorna "ate", inclusive
public static IEnumerable<int> Iterar(int de, int ate)
{
int passo = de > ate ? -1 : 1;
for (int i = de; i != ate; i += passo)
{
yield return i;
}
yield return ate;
}
}
E veja um código cliente desses iteradores:
foreach (int x in IteradorSimples.Iterar(2, 7))
{
Console.Write(x + " ");
}
Console.WriteLine();
// Imprime 2 3 4 5 6 7
foreach (int x in IteradorSimples.Iterar(6, 3))
{
Console.Write(x + " ");
}
Console.WriteLine();
// Imprime 6 5 4 3
foreach (int x in IteradorSimples.IterarAte(5))
{
Console.Write(x + " ");
}
Console.WriteLine();
// Imprime 1 2 3 4 5
Olha agora essa implementação de uma Pilha que pode empilha qualquer coisa (uma Pilha genérica). Ela possui três iteradores que possuem responsabilidades diferentes:
public class Pilha<T>;
{
T[] _itens = new T[100];
int _topo = 0;
public void Push(T t) { _itens[_topo++] = t; }
public T Pop() { return _itens[--_topo]; }
// Itera do topo ao fundo da pilha
public IEnumerable<T> TopoAoFundo
{
get
{
for (int i = _topo - 1; i <= 0; i--)
{
yield return _itens[i];
}
}
}
// Itera do fundo ao topo da pilha
public IEnumerable<T> FundoAoTopo
{
get
{
for (int i = 0; i < _topo; i++)
{
yield return _itens[i];
}
}
}
// Um iterador parametrizado que retorna os primeiros
// N itens do topo da pilha
public IEnumerable<T> TopoN(int n)
{
// As vezes, um valor menor que N será retornado
int j = n >= _topo ? 0 : _topo - n;
for (int i = _topo; --i &>= j; )
{
yield return _itens[i];
}
}
}
Veja um exemplo de uso:
// Carrega a pilha
Pilha<int> p = new Pilha<int>();
for (int i = 0; i < 10; i++)
{
p.Push(i);
}
foreach (int n in p.TopoAoFundo)
{
System.Console.Write("{0} ", n);
}
System.Console.WriteLine();
// Imprime: 9 8 7 6 5 4 3 2 1 0
foreach (int n in p.FundoAoTopo)
{
System.Console.Write("{0} ", n);
}
System.Console.WriteLine();
// Imprime: 0 1 2 3 4 5 6 7 8 9
foreach (int n in p.TopoN(5))
{
System.Console.Write("{0} ", n);
}
System.Console.WriteLine();
// Imprime: 9 8 7 6 5
Você pode pensar em uma implementação de uma árvore que tenha iteradores do tipo profundidade-primeiro e largura-primeiro? Divirta-se!
O que há em um nome?
Tecnicamente, as co-rotinas de C# não podem ser chamadas de iteradores porque quem itera mesmo é o foreach do cliente. A co-rotina só entrega os valores que são iterados pelo foreach. Para o foreach, a co-rotina é a geradora de valores. E de fato, os puristas chamarão os iteradores baseados em co-rotinas de geradores (generators, em inglês).
E qual a diferença entre co-rotinas geradoras e verdadeiros iteradores? A diferença é que, nos iteradores verdadeiros, não existe foreach cliente: um iterador verdadeiro é um método que recebe uma rotina e executa a rotina para cada item a ser iterado. Vamos a um exemplo. Você já viu uma co-rotina utilizada para iterar pelos endereços de uma pessoa:
public IEnumerable<Endereco> Enderecos
{
get
{
for (int i = 0; i < _ends.Count; i++)
{
yield return _ends[i];
}
}
}
// Uso
foreach (Endereco end in p.Enderecos)
{
Console.WriteLine(end.Rua);
}
Se implementado como um iterador verdadeiro, fica assim:
public delegate void ChamadaEndereco(Endereco end);
public void ParaCadaEndereco(ChamadaEndereco call)
{
for (int i = 0; i < _ends.Count; i++)
{
call(_ends[i]);
}
}
// Uso
p.ParaCadaEndereco(delegate(Endereco end)
{
Console.WriteLine(end.Rua);
});
São várias mudanças. A primeira é que a propriedade que utilizávamos como co-rotina geradora passa a ser um método. Não utilizamos uma co-rotina nesse método, na verdade fazemos a iteração e, para cada item, nós invocamos uma rotina passada como parâmetro, na forma de um delegate. O uso do iterador é muito mais direto. Ao invés controlar a iteração no código cliente, simplesmente chamamos o método iterador e passamos a rotina que quisermos para ser executada para cada item. Essa sintaxe de delegate() faz parte da nova sintaxe de métodos anônimos de C# 2.0; você não vai encontrar isso no .NET Framework 1.1.
O iterador verdadeiro acrescenta mas uma camada de proteção contra erros de programação no cliente. Ele mantém até o controle da iteração longe dos olhos do cliente. Também permite que mais de um item seja retornado por vez (se estiver iterando por um Hashtable, por exemplo, é possível criar um iterador que dê acesso ao mesmo tempo à chave e ao valor).
No entanto, o iterador verdadeiro não permite nenhum controle da iteração por parte do cliente. Se ele precisar parar a iteração depois de ter encontrado o que queria, ele não pode. break não funciona no código cliente. Além disso, existe o trabalho adicional de declarar o tipo do delegate que se quer usar no iterador.
Para finalizar
Geradores ou Iteradores verdadeiros, todos eles possuem a mesma finalidade: deixar o código menos acoplado e a programação mais simples. Qualquer sistema que deseja ter uma manutenção com menor custo vai usar iteradores no código.
Houve um tempo até que o padrão Iterator saísse dos primeiros esboços com classes, depois para o papel, e depois para uma sintaxe própria. Mas agora a sintaxe própria existe em cada uma das linguagens mais proeminentes: C#, Ruby, Python, Java, JavaScript, VB.NET, Lua (yeah!) e várias outras. Espero que essa série de artigos tenha contribuído para que você comece a usufruir das vantagens dos iteradores.
O velho for deve estar morrendo de inveja!
