venerdì 24 aprile 2015

Corso Lua - puntata 8 - Iteratori


Iteratori predefiniti per le tabelle

Benvenuti a una nuova puntata del corso base su Lua. Il compito di oggi è spiegare come iterare le tabelle e come costruire nuovi iteratori.

Gli iteratori offrono un approccio semplice e universale per scorrere uno alla volta i valori di una collezione di dati. Vi dedicheremo una puntata proprio perché sono molto utili per scrivere codice efficiente, pulito ed elegante.
Il linguaggio Lua prevede il ciclo generic for per iterare i dati che introduce la nuova parola chiave 'in' secondo questa semantica:
for 'lista variabili' in iterator_function() do
 -- codice
end

Le tabelle di Lua sono oggetti che possono essere impiegati per rappresentare degli array oppure dei dizionari. In entrambe i casi Lua mette a disposizione due iteratori predefiniti tramite le funzioni ipairs() e pairs().

Queste funzioni restituiscono un iteratore che è a sua volta una funzione conforme alle specifiche del 'generic for'. Mentre impareremo più tardi a scrivere iteratori personalizzati, dedicheremo le prossime due sezioni a questi importanti iteratori per le tabelle.

Funzione ipairs()

Questa funzione d'iterazione restituisce a ogni ciclo due valori: l'indice dell'array e il valore corrispondente. Essa comincierà dalla posizione 1 e terminerà quando il valore alla posizione data sarà nil:
-- una tabella array
local t = {45, 56, 89, 12, 0, 2, -98}

-- iterazione tabella come array
for i, n in ipairs(t) do
    print(i, n)
end

Se la tabella contiene valori nil allora l'iteratore non raggiungerà nessuno degli elementi successivi e verranno ignorate tutte le chiavi di tipo non intero.
Il ciclo con ipairs() è equivalente a questo codice:
-- una tabella array
local t = {45, 56, 89, 12, 0, 2, -98}

local i, v = 1, t[1]
while v do
    print(i, v)
    i = i + 1
    v = t[i]
end

Se non interessa il valore dell'indice possiamo convenzionalmente utilizzare per esso il nome di variabile corrispondente a un segno di underscore che in Lua è una definizione valida:
-- una tabella array
local t = {45, 56, 89, 12, 0, 2, -98}

local sum = 0
for _, elem in ipairs(t) do
    sum = sum + elem
end
print(sum)

Se non vogliamo incorrere in errori è molto importante ricordarsi che con ipairs() verranno restituiti i valori in ordine di posizione da 1 in poi solo fino a che non verrà trovato un valore nil. Se ci troveremo in questa situazione dovremo far ricorso all'iteratore pairs() trattato alla prossima sezione.

Funzione pairs()

Questa funzione primitiva di Lua vede la tabella come dizionario pertanto l'iteratore restituirà in un ordine casuale tutte le coppie chiave valore contenute nella tabella stessa.

Una tabella con indici a salti verrà iterata parzialmente da ipairs() ma completamente da pairs():
-- produzione tabella con salto
local t = {45, 56, 89}
local i = 10
for _, v in ipairs({12, 0, 2, -98})  do
    t[i] = v
    i = i + 1
end

print("ipairs() table iteration test")
for index, elem in ipairs(t) do
    print(string.format("t[%2d] = %d", index, elem))
end

print("\npairs() table iteration test")
for key, val in pairs(t) do
    print(string.format("t[%2d] = %d", key, val))
end

Il comportamento di questi due iteratori può lasciare perplessi ma è coerente con un linguaggio di scripting.

Generic for


Come può essere implementato un iteratore in Lua?
Per iterare è necessario mantenere alcune informazioni essenziali chiamate stato dell'iteratore. Per esempio l'indice a cui siamo arrivati nell'iterazione di una tabella/array e la tabella stessa.

Perchè non utilizzare la closure per memorizzare lo stato dell'iteratore?

Abbiamo incontrato le closure nella puntata 6 del corso base su Lua, post che vi invito a rileggere se non vi ricordate o non sapete di cosa si tratta. E allora proviamo a scrivere il codice per iterare una tabella:
-- costructor
local t = {45, 87, 98, 10, 16}

function iter(t)
    local i = 0
    return function ()
        i = i + 1
        return t[i]
    end
end

-- utilizzo
local iter_test = iter(t)
while true do
    local val = iter_test()
    if val == nil then
        break
    end
    print(val)
end

Ok. Funziona, molto semplicemente. Non è stato necessario introdurre nessun nuovo elemento al linguaggio. L'iteratore è solamente una questione d'implementazione che tra l'altro ricrea l'iteratore ipairs() visto poco fa.

Infatti, la funzione iter_test() mantiene nella closure lo stato dell'iteratore e restituisce uno dopo l'altro gli elementi della tabella. Il ciclo infinito --- il while loop --- s'interrompe quando il valore è nil.

Tuttavia data l'importanza degli iteratori Lua introduce un nuovo costrutto chiamato 'generic for' che si aspetta una funzione proprio come la iter() del codice precedente ed effettua i controlli necessari. Vediamo se funziona:
-- costructor
local t = {45, 87, 98, 10, 16}

function iter(t)
    local i = 0
    return function ()
        i = i + 1
        return t[i]
    end
end

-- utilizzo con il generic for
for v in iter(t) do
    print(v)
end

Riassumendo, la costruzione di un iteratore in Lua si basa sulla creazione di una funzione che restituisce uno alla volta gli elementi dell’insieme nella sequenza desiderata. Una volta costruito l’iteratore, questo potrà essere impiegato in un ciclo che in Lua viene chiamato 'generic for'.

Se per esempio si volesse iterare la collezione dei numeri pari compresi nell’intervallo da 1 a 10, avendo a disposizione l’apposito iteratore evenNum(first, last) che definiremo in seguito, potrei scrivere semplicemente:
for n in evenNum(1,10) do
   print(n)
end

L'esempio dei numeri pari

Per definire questo iteratore dobbiamo creare una funzione che restituisce a sua volta una funzione in grado di generare la sequenza dei numeri pari. L’iterazione termina quando giunti all’ultimo elemento, la funzione restituirà il valore nullo ovvero ‘nil’, cosa che succede in automatico senza dover esplicitare un’istruzione di return grazie al funzionamento del 'generic for'.

Potremo fare così: dato il numero iniziale per prima cosa potremo calcolare il numero pari successivo usando la funzione della libreria standard di Lua math.ceil() che fornisce il numero arrotondato al primo intero superiore dell’argomento.
Poi potremo creare la funzione di iterazione in sintassi anonima che prima incrementa di 2 il numero pari precedente --- ed ecco perché dovremo inizialmente sottrarre la stessa quantità all’indice --- e, se questo è inferiore all’estremo superiore dell’intervallo ritornerà l’indice e il numero pari della sequenza. Ecco il codice completo:
-- iteratore dei numeri pari compresi
-- nell'intervallo [first, last]
function evenNum(first, last)
   -- primo numero pari della sequenza
   local val = 2*math.ceil(first/2) - 2
   local i = 0
   return function ()
             i = i + 1
             val = val + 2
             if val<=last then
                return i, val -- due variabili di ciclo
             end
          end
end

-- ciclo con due variabili di ciclo
for idx, val in evenNum(13,20) do
    print(idx, val)
end

In questo esempio, oltre ad approfondire il concetto di iterazione basata sulla closure di Lua, possiamo notare che il 'generic for' effettua correttamente anche l'assegnazione a più variabili di ciclo con regole viste nella puntata del corso in cui abbiamo parlato dell'argomento (la puntata 2).

Naturalmente, l’implementazione data di evenNum() è solo una delle possibili soluzioni, e non è detto che non debbano essere considerate situazioni particolari come quella in cui si passa all’iteratore un solo numero o addirittura nessun argomento.

Stateless iterator


Una seconda versione del generatore di numeri pari può essere un buon esempio di un iteratore in Lua che non necessita di una closure per un risultato ancora più efficiente.

Per capire come ciò sia possibile dobbiamo conoscere nel dettaglio come funziona il 'generic for' in Lua; dopo la parola chiave 'in' esso si aspetta tre parametri: la funzione dell’iteratore da chiamare a ogni ciclo, una variabile che rappresenta lo stato invariante e la variabile di controllo.

Nel seguente codice la funzione evenNum() provvede a restituire i tre parametri necessari: la funzione nextEven() come iteratore, lo stato invariante che per noi è il numero a cui la sequenza dovrà fermarsi e la variabile di controllo che è proprio il valore nella sequenza dei numeri pari, e con ciò abbiamo realizzato un stateless iterator in Lua.
La funzione iteratrice nextEven() verrà chiamata a ogni ciclo con nell’ordine lo stato invariante e la variabile di controllo, pertanto fate attenzione, dovete mettere in questo stesso ordine gli argomenti nella definizione:
-- even numbers stateless iterator
local function nextEven(last, i)
   i = i + 2
   if i<=last then
      return i
   end
end
 
local function evenNum(a, b)
   a = 2*math.ceil(a/2)
   return nextEven, b, a-2
end
 
-- example of the 'generic for' cycle
for n in evenNum(10, 20) do
    print(n)
end

E ora gli esercizi...

1 - Dopo aver definito una tabella con chiavi e valori stampare le singole coppie tramite l'iteratore predefinito 'pairs()'.

2 - Scrivere una funzione che accetta una tabella/array di stringhe e utilizzare la funzione di libreria 'string.upper()' per restituire una tabella/array con il testo trasformato in maiuscolo (per esempio con '{"abc", "def", "ghi"}' in '{"ABC", "DEF", "GHI"}').

3 - Scrivere la funzione/closure per l'iteratore che restituisce la sequenza dei quadrati dei numeri naturali a partire da 1 fino a un valore dato.

4 - Scrivere la versione 'stateless' per l'iteratore dell'esercizio precedente.

Riassunto della puntata

Con gli iteratori abbiamo terminato l'esplorazione di base del linguaggio Lua.
Queste prime otto puntate pubblicate sul blog di Luigi sono sufficienti per scrivere programmi utili in Lua perché trattano con essenzialità di tutti gli argomenti necessari.

Il programma del corso prosegue con la prossima puntata che sarà dedicata alla programmazione a oggetti in Lua. State pronti.
R.

Nessun commento:

Posta un commento