Reiterador III

Andei pensando e concluí que, como o primeiro artigo já foi voltado para programadores, o segundo deveria ter sido um pouco mais explicativo.

Introdução

O objetivo aqui é explicar um pouco mais de metatabelas e corrotinas através da criação de um reiterador.

Mas o que diabos é um reiterador?

Reiterador (em inglês iterator) é um objeto que percorre uma lista geralmente grande demais para ser carregada na memória, retornando cada elemento sem precisar carregar toda a lista de uma só vez.

Por exemplo, um cursor de uma consulta de banco de dados. A tabela retornada pela consulta pode ter 200MB ou mais, mas o cursor jamais vai ocupar mais espaço na memória do que o suficiente para manipular um único registro.

Como funciona?

O cursor aponta para o vazio. Quando seu valor é requerido (geralmente pelo método next()), ele avança para o primeiro registro e retorna seus campos. Quando é requerido novamente, ele avança para o próximo registro, retornando-o, e assim sucessivamente até o último.

É assim que funciona um reiterador.

Outro exemplo é um descritor de arquivo.

O descritor começa apontando para a posição 0 do arquivo. Quando seu valor é requerido, ele retorna o byte dessa posição e avança para a próxima posição, e assim até o fim do arquivo. O funcionamento é similar.

Vamos criar um reiterador muito simples que retorne cada elemento da sequência de Fibonacci.

Metatabela

Metatabela é um recurso da linguagem Lua que funciona de modo similar a uma classe em linguagens orientadas a objetos.

A metatabela é uma tabela que contém a chaves especiais para tratamento de chamadas. As tabelas que recebem a metatabela como sua trabalham de modo similar a instâncias.

Por questão de simplicidade passeremos a usar os seguintes termos:
- instância: uma tabela relacionada a uma metatabela (apesar de não ser o termo mais adequado);
- método: um par chave-valor onde o valor é uma função;
- atributo: qualquer outro par chave-valor de uma instância ou metatabela.

A chave __index da metatabela é chamada quando é feita uma tentativa de leitura de uma chave que a instância não possui.

Se o valor de __index da metatabela for uma tabela, a chave requerida é consultada nessa tabela. Por exemplo:

t = { a = 2 }
setmetatable(t, { __index = { x = 0, y = 3 } })

Então t.x retornará 0, pois o valor vem da tabela em __index.

Esta chave também pode conter uma função, onde o primeiro parâmetro é a instância e o segundo a chave. O valor é o retorno da função:

t = { a = 2 }
setmetatable(t, {
    __index = function (t, k)
        return "-- chave " .. k .. " --"
    end
} )

Então t.x retornará a string «-- chave x --».

Já a chave __newindex da metatabela é chamada quando é feita uma tentativa de gravação em uma chave que a instância não possui. Seu valor é uma função cujos argumentos recebem a instância, a chave e o valor.

Criando a metatabela

Como nossa metatabela será um reiterador, vamos chamá-la iter. Podemos usar a própria metatabela para armazenar as chaves.

Esta é uma prática comum de programação em orientação a objetos em Lua: usar a própria metatabela como valor para a chave __index.

Precisaremos apenas de dois métodos: construtor e next().

Vamos criar primeiro a metatabela:

local iter = {}
iter.__index = iter
iter.__newindex = function (t, k, v)
    -- Esta função apenas evita a criação de novas chaves
    error("Chave " .. k .. " não existe")
end

O construtor

O construtor é o método que é executado na criação de uma instância, e torna muito mais simpática a instanciação em Lua.

A idéia é a seguinte: ao contrário dos demais métodos, self é a classe e o primeiro argumento será a instância. Um construtor padrão em Lua é:

function iter:new(o)
    o = o or {}
    setmetatable(o, self)
    return o
end

Mas, como a metatabela iter é local (digamos, privada), o construtor também será. Precisaremos de um construtor público... é nessa função que começaremos a mexer com corrotina.

Corrotina

Corrotina é a biblioteca de Lua para criação de reiteradores.

O foco da biblioteca de corrotina é fazer algo similar a manipulação de threads, mas na prática se assemelha mais a reiteradores em Python (yield).

Como funciona?

A função coroutine.create() recebe uma função como parâmetro e retorna uma corrotina.

O tipo retornado para uma corrotina (função type()) é thread.

Quando a corrotina é passada como primeiro parâmetro para coroutine.resume(), a função da corrotina é executada até encontrar uma chamada a coroutine.yield(). Então coroutine.resume() retorna true e o parâmetro de coroutine.yield().

A cada chamada de coroutine.resume() a função da corrotina continua até encontrar novamente coroutine.yield().

Confuso? Vai clarear...

Construtor público

O construtor público precisa criar a corrotina com uma função que calcule os elementos de Fibonacci e passar a corrotina para a tabela que será transformada numa instância de iter:

function new()
    local t = {}
    t.co = coroutine.create(function ()
        local a, b = 0, 1
        while true do
            a, b = b, a+b
            coroutine.yield(a)
        end
    end)

    return iter:new(t)
end

Esta é uma função simples (algoritmo reiterativo, hehe) para calcular Fibonacci. A cada chamada de coroutine.resume() a função correrá até o coroutine.yield(), que retornará o próximo elemento.

Método principal

Vamos criar o método next(), que tratará toda essa brincadeira e retornará um valor limpo:

function iter:next()
    local _, r = coroutine.resume(self.co)
    return r
end

A função coroutine.resume() retorna como primeiro valor true para indicar que tudo correu bem, e como segundo o elemento que queremos. Então isolamos o retorno (na variável r) e retornamos só o que interessa.

Criando um módulo compatível com 5.1

Precisamos tornar locais todas as bibliotecas e funções globais que usamos, depois criamos o módulo:

local coroutine = coroutine
local error = error
local setmetatable = setmetatable

module "fib"

Colocando tudo junto

local coroutine = coroutine
local error = error
local setmetatable = setmetatable

module "fib"

local iter = {}
iter.__index = iter
iter.__newindex = function (t, k, v)
    -- Esta função apenas evita a criação de novas chaves
    error("Chave " .. k .. " não existe")
end

function iter:new(o)
    o = o or {}
    setmetatable(o, self)
    return o
end

function iter:next()
    local _, r = coroutine.resume(self.co)
    return r
end

function new()
    local t = {}
    t.co = coroutine.create(function ()
        local a, b = 0, 1
        while true do
            a, b = b, a+b
            coroutine.yield(a)
        end
    end)

    return iter:new(t)
end

Salve tudo num arquivo (por exemplo, fib.lua), depois levante o interpretador e veja funcionando:

lua> require "fib"
lua> f = fib.new()
lua> for i = 1, 10 do print(f:next()) end
1
1
2
3
5
8
13
21
34
55

[]'s