Lavorare con le liste: quando il gioco si fà duro… (parte 2)

6 08 2009

google_translate.gif Translate To English!

Avete “digerito” la prima parte? Ok, allora proseguiamo! Nella prima parte abbiamo parlato anche degli array, gestendoli però con alcuni semplici metodi standard. newLisp però prevede delle funzioni (di cui alcune già viste la volta scorsa) per la manipolazione di liste-array. Prima di tutto, facciamo un “brutale” copia/incolla dal manuale, e vediamo quali funzioni abbiamo a nostra disposizione:

append Appende gli array
array Crea ed inizializza un array fino a 16 dimensioni
array-list Converte un array in una lista
array? Controlla se una espressione è un array
det Ritorna il determinante di una matrice
first Ritorna la prima riga di un array
invert Ritorna l’inversa di una matrice
last Ritorna l’ultima riga di un array
mat Esegue operazioni scalari su matrici
multiply Moltiplica due matrici
nth Ritorna un elemento di un array
rest Ritorna tutti gli elementi di un array tranne il primo
setf Set (imposta) i contenuti di un array per reference
slice Ritorna uno slice (una parte, un sottoinsieme) di un array
sort Mette in ordine gli elementi di un array
transpose Traspone una matrice

Alcune note importanti:

  1. Gli array multidimensionali vengono gestiti come array di array.
  2. Quando usato in modo interattivo, gli array sono mostrati come liste, e non c’è nessun modo per distinguerli.
  3. Gli array possono essere non-rettangolari, ma quando vengono serializzati diventano rettangolari.
  4. La funzione array crea sempre array rettangolari.
La nota più importante di tutte: gli array così creati sono veri array, e non liste! Questo significa che non si possono applicare su di essi tutte le funzioni che normalmente si applicano sulle liste, e che gli array possono fornire “out-of-bounds error” (cosa che non può accadere con le liste).

E allora quando dobbiamo usare gli array? Vanno usati quando si devono gestire GRANDI quantità di dati, ad accesso casuale, i quali risultano troppo lenti per essere gestiti tramite le liste. Per inizializzare un array dobbiamo procedere in questo modo:

> (array 2 3)
((nil nil nil) (nil nil nil))

Se volessimo inserire un elemento all’interno durante la sua creazione, aggiungiamolo con una lista:

> (array 2 3 '(1))
((1 1 1) (1 1 1))
> (array 2 3 (sequence 1 6))
((1 2 3) (4 5 6))
> (array 2 3 '("X"))
(("X" "X" "X") ("X" "X" "X"))

Per inserire un valore nell’array possiamo ricorrere alla funzione setf, che inserirà il valore “by-reference” (quindi è molto veloce):

> (setq mio (array 2 3 '(".")))
(("." "." ".") ("." "." "."))
> (setf (mio 0 1) "X")
"X"
> mio
(("." "X" ".") ("." "." "."))
> (setf (mio 1 2) "Z")
"Z"
> mio
(("." "X" ".") ("." "." "Z"))
Ricordatevi che gli indici partono sempre da zero!

Possiamo anche lavorare con array in altri array:

> (setf (mio 1 0) '(A B C))
(A B C)
> mio
(("." "X" ".") ((A B C) "." "Z"))
> (setf (mio 1 ) '(X Y Z))
(X Y Z)
> mio
(("." "X" ".") (X Y Z))

Nell’ultimo caso ho sostituito un intera dimensione dell’array (in termini di contenuti) con un’altra! Ed ora guardate qui:

> (setf (mio 3 ) '(W A S D))
ERR: array index out of bounds in function setf : 3

Ho cercato di inserire un elemento in un posto inesistente, ed ho ottenuto un Out of bounds. Questo perchè la funzione (setf), lavorando per reference, deve necessariamente lavorare su elementi esistenti (non si può referenziare qualcosa che non esiste!).

Come posso estrarre i dati di una riga? Ed una cella singola? Guardate questi esempi:

> (setq mio (array 4 3 (sequence 0 11)))
((0 1 2) (3 4 5) (6 7 8 ) (9 10 11))
> (mio 1 1)
4
> (mio 1)
(3 4 5)

> (mio -1) ;; INDICE NEGATIVO: LEGGO L'ULTIMO ELEMENTO!
(9 10 11)

Si possono anche estrarre “pezzi” di array, tramite la funzione (slice):

> (slice mio 1 2)
((3 4 5) (6 7 8))

Per essere certi di lavorare con degli array, possiamo usare la funzione (array?):

> (setq mio (array 3 2 (sequence 1 6)))
((1 2) (3 4) (5 6))
> (array? mio)
true
> (array? (array-list mio)) ;; CONVERTO L'ARRAY IN LISTA
nil

> (list? (array-list mio)) ;; CONVERTO L'ARRAY IN LISTA
true

Invece se si vuole convertire una lista in un array, dobbiamo usare la funzione (flat) che si occuperà di “appiattire” la lista e darla in pasto al generatore di array:

> (setq mioArray (array 2 3 (flat lista)))
((1 2 3) (4 5 6))
> (setq mioArray (array 3 2 (flat lista)))
((1 2) (3 4) (5 6))

E’ interessante notare come questo sistema permetta di “distribuire” i valori nell’array, senza preoccuparsi della “forma” dell’array stesso nè della forma della lista.

Prima di concludere (ma la terza parte di questo workshop è già alle porte ;-)  ) vediamo le funzioni (source) (save). Esse permettono di serializzare espressioni, simboli, context, etc… e, ovviamente, array!

Facciamo subito una prova:

> (setq mioArray (array 3 2 (sequence 1 6)))
((1 2) (3 4) (5 6))

> (println (source 'mioArray))
(set 'mioArray (array 3 2 (flat '(
  (1 2)
  (3 4)
  (5 6)))))

"(set 'mioArray (array 3 2 (flat '(\n  (1 2) \n  (3 4) \n  (5 6)))))\n\n"

Ho aggiunto la funzione (println) per comodità di lettura. La funzione (source) genera tutto l’indispensabile per ricrare l’elemento da un’altra parte, o per salvarlo. La funzione (source) fà la stessa cosa, ma salva il codice generato direttamente su file.

Ora pensate al potenziale di queste funzioni, unite alla (net-eval).

Come dite? Non sapete cosa è la (net-eval)?! Ne parleremo in un prossimo workshop, insieme alla programmazione distribuita. Promesso!





Lavorare con le liste: quando il gioco si fà duro… (parte 1)

2 08 2009

google_translate.gif
Translate To English!

Come ormai ben sapete, le liste sono l’elemento cardine di newLisp. Le liste sono validi sostituti degli array, delle hash tables, degli array associativi, etc… Molti linguaggi di programmazione infatti complicano la vita al programmatore inserendo diversi tipi di dato con, ovviamente, funzioni ad-hoc per il loro uso. In newLisp la situazione è diversa: la base di tutto sono le liste. E la cosa più importante è che le funzioni necessarie per il loro uso sono semplicemente perfette. In questo workshop faremo meglio la loro conoscenza. Vi accorgerete quanto sono flessibili. Si inizia! Prima di tutto realizzeremo dei classici: cioè vedremo come implementare (e gestire!) gli stacks (LIFO) e le code (FIFO).

Lavorare con uno stack.

Cosa è uno stack LIFO (Last In First Out, cioè l’ultimo elemento che entra è il primo ad uscire)? Allora, prendete dei libri e poneteli ad uno ad uno all’interno di una scatola, uno sopra all’altro, formando una pila. In cima, dove si trova ilcoperchio è l’unica apertura. Potete facilmente verificare che l’ultimo libro posto sulla pila (messo sopra tutti gli altri), sarà il primo libro che potrete riprendere: LIBRO 3 <— Cima della pila (ultimo libro posto sulla pila) LIBRO 2 LIBRO 1 <— Fondo della pila La regola per implementare uno stack è che i libri non si possono prendere dal mezzo (libro 2), nè dal fondo della pila (libro 1). Per creare un oggetto come questo si usano, ovviamente, li liste ;-) Qui c’è tutta la flessibilità di newLisp, infatti una lista-stack è una comune lista, ma noi la gestiremo  in modo tale da farla comportare come uno stack. Per inserire dati nello stacca usiamo la funzione (push), mentre per estrarre elementi useremo (pop). Ecco un esempio:

> (setq scatola '())
()
> (push 'libro1 scatola)
(libro1)
> (push 'libro2 scatola)
(libro2 libro1)
> (push 'libro3 scatola)
(libro3 libro2 libro1)
>

Notate come l’ultimo libro inserito, libro3, si trova in cima alla lista (primo elemento della lista). Ora preleviamo gli elementi:

> (pop scatola)
libro3
> (pop scatola)
libro2
> (pop scatola)
libro1
> scatola
()
>

La funzione pop preleva l’ultimo elemento inserito. Notate che, ad ogni chiamata pop, gli elementi vengono fisicamente eliminati dalla lista (scatola). Al termine delle tre chiamate pop, la scatola sarà vuota. Semplicissimo!

Lavorare con una coda.

Le code sono contenitori di tipo FIFO (First In First Out). Immaginate un tubo. Esso avrà due “porte di accesso”: una per l’ingresso (le palline entreranno da questa porta), ed una per l’uscita:

ENTRATA –> pallina-rossa –> pallina-verde –> pallina blu –> USCITA

La pallina blu è la prima ad essere entrata (First In) e sarà la prima ad uscire (First Out).
Come implementarlo in newLisp?

> (setq tubo '())
()
> (push 'pallina-blu tubo)
(pallina-blu)
> (push 'pallina-verde tubo)
(pallina-verde pallina-blu)
> (push 'pallina-rossa tubo)
(pallina-rossa pallina-verde pallina-blu)
>

Uso la stessa funzione push per inserire le palline nel tubo. Ora come le prelevo?

> (pop tubo -1)
pallina-blu
> (pop tubo -1)
pallina-verde
> (pop tubo -1)
pallina-rossa
> tubo
()

L’indice “-1″ usato nella funzione pop indica di prelevare l’ultimo elemento della lista, e non il primo. Abbiamo quindi realizzato un contenitore molto diverso dallo stack, ma abbiamo usato gli stessi elementi (una lista, la funzione pop e la push). Semplice, flessibile, efficace.

Creare e manipolare un array.

Cosa è un array? Immaginate un corridoio, molto lungo, con tantissime porte, una dietro all’altra, tutte numerate (0, 1, 2, 3, etc…). Ogni porta dà accesso ad una piccola stanza, in cui depositare qualcosa. Potete mettere oggetti nelle stanze facendo riferimento al numero della stanza. Lo stesso vale per prelevare oggetti da esse. In molti linguaggi di programmazione, gli array hanno una lunghezza fissa, e talvolta possono essere ridimensionati (ma ciò comporta diversi svantaggi: in alcuni linguggi il ridimensionamento viene fatto RICOPIANDO tutti gli elementi in un nuovo array, con grande spreco di risorse e di tempo).
In newLisp gli array possono essere gestiti con… le liste ovviamente! La parte interessante è che abbiamo molteplici strumenti per farlo (funzioni), ognuno con caratteristiche particolari. Sono veramente tante le strade che si possono percorrere per gestire un array, ed alcune di esse si mescolano con il concetto di liste, permettendo quindi una gestione molto più flessibile e dinamica degli array classici. Io vi mostrerò solo le funzioni inerenti ad una gestione tipica di un array, mentre in seguito vedremo come far “esplodere” le vere potenzialità di newLisp e delle sue liste!
Partiamo con un esempio:

> (setq mio-array '(1 2 3 4 5 6 7 8 9 10))
> (setf (mio-array 2) 'X)

(1 2 X 4 5 6 7 8 9 10)

Prima di tutto creiamo una lista con i numeri da 1 a 10. Poi, usando la funzione setf, metto il simbolo X nella stanza numero 2 (cioè la terza stanza del corridoio).
NOTA: il primo numero della stanza vale “0″ (zero), e non “1″. Quindi la stanza “2″ è la terza stanza del corridoio (il linguaggio C, C++, Java, etc… usano tutti questa stessa notazione).
NOTA 2: il valore inserito ha sovrascritto il precedente! Questo è il funzionamento di un array.
Normalmente in un array, leggendo il suo valore, non si elimina tale valore (come invece accade negli stack e nelle code). Vediamo quindi come fare.

> mio-array
(1 2 X 4 5 6 7 8 9 10) <--- mio-array contiene questi valori
> (mio-array 1)        <--- chiedo di leggere il valore contenuto nella stanza numero "1"
2
> (mio-array 2)        <--- chiedo di leggere il valore contenuto nella stanza numero "2"
X
> (mio-array 3)        <--- chiedo di leggere il valore contenuto nella stanza numero "3"
4

Oppure posso usare quest’altro modo (usando la funzione nth):

> mio-array
(1 2 X 4 5 6 7 8 9 10)
> (nth 2 mio-array)
X
> (nth 3 mio-array)
4

Vorrei mettere in evidenza anche quest’altra forma:

> mio-array
(1 2 X 4 5 6 7 8 9 10)
> (2 mio-array)    <--- Ottengo i valori della stanza "2" e seguenti.
(X 4 5 6 7 8 9 10)
> (5 mio-array)    <--- Ottengo i valori della stanza "5" e seguenti.
(6 7 8 9 10)

In quest’ultimo caso vengono letti TUTTI i valori a partire dalla stanza indicata.

Ma come potrei gestire gli array multidimensionali? La risposta è semplice: le liste sono dei “contenitori” di simboli o… altre liste. Un array con n-dimensioni può essere facilmente rappresentato come delle matrici ad n-dimensioni. Le matrici sono facilmente rappresentabili con le liste…

Matrice = [ [1 2] [3 4] ]

Questa matrice la posso rappresentare con un array “tradizionale”, in questo modo:

Matrice[0, 0] = 1
Matrice[0, 1] = 2
Matrice[1, 0] = 3
Matrice[1, 1] = 4

Ecco come scriverlo in newLisp:

> (setq Matrice '( (1 2) (3 4) ) )
((1 2) (3 4))

Come possiamo accedere ai suoi elementi?

> (Matrice 0)
(1 2)
> (Matrice 1)
(3 4)
> (Matrice 1 0)
3
> (Matrice 1 1)
4

Ed ora, che abbiamo visto come implementare gli array con le liste, prima di concludere questo workshop, vi dò una bella notizia: in newLisp esistono gli array! Quelli veri! Li vedremo nella seconda puntata… per ora è tutto! (per quelli che non sanno aspettare, leggete qui – in inglese -)

A presto!





Sfida lanciata!

2 07 2009

google_translate.gif Translate To English!

Questa volta sono qui per lanciarvi una sfida! Ovviamente sarà una “competizione” costruttiva (ne usciremo tutti vincitori!).

L’idea mi è venuta da un messaggio che ho inviato io stesso su Twitter: come calcolare gli anni bisestili in newLisp.
Bene, l’idea è semplice: inviatemi…

1) Una funzione, più corta possibile (fatto in newLisp ovviamente!) per calcolare l’anno bisestile (in pure “stile” Twitter,  dove ogni singolo carattere è preziosissimo!)

2) Fare un altro programma che calcola e mostra SOLO anni bisestili dei primi 1000000 anni di vita (da 0 a 1000000). Si, avete capito bene: il primo MILIONE di anni!

Ripeto: non voglio una corrispondenza completa, ma SOLO gli anni effettivamente bisestili!

Gli anni non dovranno essere mostrati a video, ma memorizzati in una lista.

Esempio:

> (setq anni '()) (dotimes (i 50) (if (leap i) (push i anni -1)))
> anni
(0 4 8 12 16 20 24 28 32 36 40 44 48)

Nell’esempio, la lista anni contiene gli anni bisestili dei primi 50 anni (0->50). Bene: fate lo stesso, il più velocemente possibile, con il primo milione di anni  :-)

Vi ricordo che per misurare le performance, newLisp offre la comoda funzione (time).

Mandatemi i vostri risultati sotto forma di commenti a questo articolo!

Buon lavoro!