Alberelli in Go

Sommario

Svolgimento dell’esercizio di implementazione di un albero con funzioni ricorsive in linguaggio Go.
Attratto da questo post su questo stesso blog di dikiyvolk, ho provato a reimplementare le funzioni di base per la struttura dati nel nuovo linguaggio targato Google, anziché in Delphi, come la versione originale, anche perché Juhan aveva citato proprio il Go nei commenti…
La visita dell’albero produce la stampa ordinata dei valori memorizzati nell’albero.

L’albero in Go

Il codice che vi riporto tutto d’un fiato di seguito, è molto simile a quello che si sarebbe scritto in C od in C++. Per eseguirlo cliccate su questo link del Go Playground e attivate il pulsante Run, oppure installate Go e date il comando di compilazione e poi quello di esecuzione intendendo che il file sorgente sia stato chiamato otree.go(adattate per il caso di sistemi operativi non derivati da unix):

$ go build otree.go
$ ./otree

Bando alle ciance, ecco il codice:

package main

import "fmt"

func main() {
    // setup a new tree
    tree := NewTree(10, 6, 4, 4, 3, 8, 12)
    tree.Visit()
    // adding a new element
    tree.AddData(9)
    fmt.Println()
    tree.Visit()
    // test an empty tree
    tree2 := NewTree()
    fmt.Println()
    tree2.Visit()
}

type OTree struct {
    root *leaf
}

type leaf struct {
    data        int
    left, right *leaf
}

func NewTree(nargs ...int) *OTree {
    ot := new(OTree)
    ot.AddData(nargs...)
    return ot
}

func (ot *OTree) AddData(nargs ...int) {
    if ot.root == nil && len(nargs) > 0 {
        ot.root = new(leaf)
        ot.root.data = nargs[0]
        nargs = nargs[1:]
    }
    for _, val := range nargs {
        addinteger(ot.root, val)
    }
}

func (ot *OTree) Visit() {
    if ot.root == nil {
        fmt.Println("The tree is empty.")
    } else {
        visit(ot.root)
    }
}

// core functions
func addinteger(t *leaf, n int) {
    switch {
    case n > t.data:
        if t.right == nil {
            t.right = new(leaf)
            t.right.data = n
        } else {
            addinteger(t.right, n)
        }
    case n < t.data:
        if t.left == nil {
            t.left = new(leaf)
            t.left.data = n
        } else {
            addinteger(t.left, n)
        }
    default:
        // duplicated insertion denied
    }
}

func visit(t *leaf) {
    if t.left != nil {
        visit(t.left)
    }
    fmt.Println(t.data)
    if t.right != nil {
        visit(t.right)
    }
}

Un saluto.
Alla prossima.
R.

Pool di goroutine

Sommario

Con il linguaggio Go, studieremo come implementare un pool di goroutine che si occupa di eseguire un insieme di compiti ciclicamente prelevando i dati da un unico canale di ingresso ed inserendo i risultati in un secondo canale di uscita.

Impiegati instancabili

Immaginiamo un gruppo di impiegati che in un unico grande ufficio evade una pila di pratiche una alla volta. Il capo deposita le pratiche sempre una alla volta in una pila, gli impiegati facendo la coda prelevano a turno dal fondo della pila una pratica, tornano alla scrivania per lavorarci e quando hanno finito la depositano in una pila di uscita per poi tornare a prelevare una nuova pratica.
Vedremo che le regole di questo ufficio sono alquanto strane: gli impiegati non si riposano mai nemmeno quando le pratiche sono tutte evase e la pila è vuota!

Tante gooutine si mettono in lista e prelevano il lavoro da fare…

Pool di goroutine

Ok, niente panico! Passiamo a definire la geometria di un pool di gouroutine che si occupa di eseguire compiti. Ciascuna di esse preleva un dato di ingresso dal canale comune a tutte, ed elabora i risultati, li immette nel canale di uscita e ricomincia da capo.
Per concretizzare, mettiamo il caso in cui si voglia calcolare il quadrato di alcuni numeri.
A questo scopo, creiamo una funzione che spedisca uno alla volta in un canale i dati:

// arriva il capo ufficio!
func sending(data []int) chan int {
    ch := make(chan int, 10)
    go func () {
        for _, n := range data {
            ch <- n
        }
        close(ch)
    }()
    return ch
}

La simpatica funzione sending() restituisce il canale in cui inserisce i numeri tramite una goroutine così che quando il canale non è pronto essa rimarrà nello stato di blocco e non la goroutine principale con il rischio di generare un deadlock, a seconda dell’ordine di setup del pool.
Il deadlock è un errore di runtime: il programma in esecuzione si interrompe quando tutte le goroutine non possono proseguire perché bloccate.
Per sperimentare un deadlock, provate questo programma:

package main

func main() {
    ch := make(chan int)
    ch <- 10 // deadlock!
    println(<-ch)
}

Sembra tutto a posto, ma quando spediamo 10 sul canale, la goroutine principale — nella quale sta girando la funzione main() — non può proseguire all’istruzione successiva: entra in blocco nell’attesa che qualcosa richieda un dato all’uscita del canale.
Se definiamo il canale con una capacità maggiore di zero — canale bufferizzato — invece tutto andrà bene.

Tornando all’esempio, rimane da scrivere la funzione che crea il pool di goroutine, eccola:

// assunzione degli impiegati!
func makepool(in chan int, dim int) chan int {
    out := make(chan int) 
    for i := 0; i < dim; i++ {
        go func() {
            dojob(out, in)
        }()
    }
    return out
}

Ciascuna funzione del pool lavora con un ciclo infinito in cui ogni volta si preleva un numero dal canale d’ingresso — alimentato da sending() — e lo si spedisce su quello d’uscita dopo averlo elevato al quadrato:

// gli implacabili impiegati!
func dojob(out chan int, in chan int) {
    for {
        n := <- in 
        out <- n * n
    }
}

La funzione main() orchestra il tutto, prima costruendo ed alimentando il canale di entrata dei dati, poi costruendo il pool di 10 goroutine di elaborazione e per ultimo, attendendo che tutti i risultati arrivino:

func main() {
    // costruzione dello slice di dati
    n := 100
    data := make([]int, n)
    for i := 0; i < n; i++ {
        data[i] = i + 1
    }
    
    // pool's setup
    in := sending(data)
    out := makepool(in, 10)
    
    // waiting for the ending of entire job
    for i := 0; i < n; i++ {
        fmt.Printf("Result %d\n", <- out)
    }
}

Il codice completo pronto per l’esecuzione lo si può trovare a questo link.

Un difetto sottile

Le goroutine del pool operano con un ciclo infinito. Ciascuna di esse tenta di ricevere dati dal canale d’ingresso in che ad un certo punto però viene chiuso una volta terminato l’invio del set di dati.
Poiché in Go, quando si riceve un dato da un canale chiuso non si ottiene un errore ma il valore zero relativo al tipo del canale (in questo caso interi quindi il numero 0), cosa impedisce alle goroutine del pool di continuare a lavorare, almeno fino a quando non termina la goroutine principale?

Nel listato il canale di output out non è bufferizzato, quindi in main() una volta ricevuti i dati attesi viene bloccato. Una goroutine del pool può ancora fare in tempo a calcolare un quadrato ed a richiedere l’invio nel canale di uscita.

Se invece il canale di uscita ha una capacità maggiore di zero, il pool può ancora riempirlo lavorando inutilmente con i valori zero provenienti dal canale di ingresso ormai chiuso, ammettendo che la funzione main() sia ancora impegnata in qualche altro compito, lasciando quindi tempo al pool.

Per riordinare le idee con del codice effettivo, proviamo a verificare cosa succede se continuamo a prelevare dati da un canale chiuso:

package main

func main() {
    ch := make(chan int, 2)
    ch <- 100
    ch <- 200
    close(ch)
    println(<-ch) // stampa 100
    println(<-ch) // stampa 200
    println(<-ch) // stampa 0
}

Possiamo accorgerci però che il canale è chiuso perché ricevere da esso comporta in realtà ottenere non uno ma due valori: il dato utile ed un valore booleano che è vero se il canale è aperto, falso viceversa, esattamente come nel caso della richiesta di una valore in una mappa. Nel seguente programma prima di stampare il valore ci chiediamo se il canale è chiuso e non stiamo per caso ricevendo anziché un dato effettivo solo il valore zero del tipo.
In Go ogni variabile è SEMPRE inizializzata al valore zero corrispondente al tipo, e questa è una grande differenza rispetto ai liguaggi dinamici tipo Lua o Python.

package main

func main() {
    ch := make(chan int, 2)
    ch <- 100
    ch <- 200
    close(ch)
    for val, isOpen:=<-ch;isOpen;val, isOpen = <-ch{
        println(val)
    }
}

Adesso modifichiamo il codice principale nell’intento di rilevare il lavoro ‘imprevisto’ delle goroutine. Mettiamo in pausa per qualche millisecondo la funzione principale prima che termini per dare un po’ di tempo alle goroutine del pool di riempire il canale di uscita di cui è stata aumentata la capacità.
Poi un nuovo canale di interi cycles ci servirà per contare il numero di cicli effettivi compiuti dal pool:

// Simple goroutine pool
package main

import (
    "fmt"
    "time"
)

func main() {
    // costruzione dello slice di dati
    n := 100
    data := make([]int, n)
    for i := 0; i < n; i++ {
        data[i] = i + 1
    }

    // pool's setup
    in := sending(data)
    out := makepool(in, 10)

    // waiting for the ending of job
    for i := 0; i < n; i++ {
        fmt.Printf("Result %d\n", <-out)
    }
    time.Sleep(200 * time.Millisecond)
}

func makepool(in chan int, dim int) chan int {
    out := make(chan int, dim)
    cycles := make(chan int, dim)
    c := 0
    go func() {
        for {
            c += <-cycles
            fmt.Println(c)
        }
    }()
    for i := 0; i < dim; i++ {
        go func() {
            for {
                n := <-in
                out <- n * n
                cycles <- 1
            }
        }()
    }
    return out
}

func sending(data []int) chan int {
    ch := make(chan int, 10)
    go func() {
        for _, n := range data {
            ch <- n
        }
        close(ch)
    }()
    return ch
}

L’esecuzione di questa prova stampa i numeri dei cicli fino a 110. Il pool ha continuato a lavorare fino a saturare il canale di uscita dei risultati, tutti pari a zero. Se richiedessimo la stampa di ulteriori dati dal canale out per controllare che i valori siano zero, si libererebbo dei posti che il pool riempirebbe di nuovo con valori zero, sempre se solo la funzione main() non termini prima.

Soluzione

Abbiamo studiato nei dettagli il problema di un pool di goroutine che tenta di ricevere dati da un canale anche se chiuso. La soluzione è semplicemente quella di modificare il ciclo infinito per tener conto dello stato del canale: nel momento in cui una goroutine del pool scopre che è il canale è chiuso allora può terminare:

func dojob(out chan int, in chan int) {
    for n := range in {
        out <- n * n
    }
}

Alla prossima…
Un saluto.
R.

Go Fibonacci!

Sommario

Creeremo un programma per la generazione dei numeri di Fibonacci per poi entrare nel campo dell’esecuzione concorrente in Go.

Fibonacci

La sequenza di Fibonacci si genera sommando i precendenti due numeri della serie. Questa regola necessita di definire i primi due numeri e questi sono semplicemente assunti pari a 0 ed 1.
In Go il calcolo dell’ennesimo numero della sequenza può essere ottenuto con il codice seguente sfruttando direttamente la definizione della serie e l’assegnazione multipla (linea 8) tra l’altro disponibile anche nei linguaggi Lua e Python:

package main

// trova l'ennesimo numero della serie
// di Fibonacci
func fibonacci(n int) int {
    var a, b int = 0, 1
    for i := 0; i < n-1; i++ {
        a, b = b, a+b
    }
    return a
}

func main() {
    for i := 1; i < 10; i++ {
        print(fibonacci(i), " ")
    }
    println()
}

Calcoli indipendenti

Il supporto alla programmazione concorrente del Go è probabilmente — in un mondo multiprocessore — la principale caratteristica per la sua diffusione, e pensare che nel linguaggio vi sono pochissimi costrutti sintattici per implementarla (caso mai la semplicità fosse un vantaggio).
Li abbiamo visti già tutti all’opera su Ok, panico!, grazie ai post di Juhan ;-).

Come forse avrete intuito, proveremo a calcolare molti numeri di Fibonacci in modo indipendente. Questa parola è importante perché la programmazione concorrente non è altro che un insieme di esecuzioni che si svolgono indipendentemente una dall’altra — come sottolinea Robert Pike. La distinzione è dovuta al fatto che ci si può sbagliare usando per questa modalità di esecuzione il termine parallelismo, che invece indica un insieme di esecuzioni che avvengono contemporamente. Nei moderni pc multicore, l’esecuzione concorrente può avvicinarsi al parallelismo.

Fibonacci independente

Un semplice schema per l’esecuzione concorrente di più funzioni di Fibonacci, è quello di avviarne l’esecuzione in una goroutine ed attenderne in quella principale i risultati provenienti da un canale.

Ecco il codice in cui si deve intendere che la funzione mancante fibonacci() sia quella del listato precedente:

func fibonacci(n int) int64 {
    // as before with int64 return value
}

var num = []int{50, 36, 80, 93, 66}

func main() {
    ans := make(chan int, len(num)) // buffered channel
    for _, f := range num {
        go func(f int) {
            ans <- fibonacci(f)
        }(f)
    }
    
    // stampo i risultati provenienti dal canale
    for i := 0; i < len(num); i++ {
        fib := <-ans
        fmt.Printf("Fibonacci(%d)=%d\n", num[i], fib)
    }
}

Nella funzione main() dopo aver creato un canale, avviamo tante goroutine quanti sono i numeri della serie da calcolare iterando sugli elementi di uno slice (num). Al termine del ciclo avremo nel nostro caso 5 goroutine in esecuzione indipendente da quella principale.
La prima diversità dalla programmazione classica è che l’istruzione go avvia una nuova linea di esecuzione senza attendere che questa termini. Quasi immediatamente raggiungiamo quindi il secondo ciclo for che preleva in sequenza i dati dal canale.

Questo schema è piuttosto semplice. Non conosciamo l’ordine con cui i dati arrivano e dobbiamo ricordarci che l’istruzione

        fib := <-ans

comporta il blocco dell’esecuzione della goroutine principale (quella in cui gira la funzione main()), che attende fino all’arrivo di un dato, assicurandoci che vengano attesi cinque valori dal canale altrimenti la funzione main() terminerà prima che le goroutine di calcolo abbiano portato a termine il lavoro.
La goroutine infatti non sanno niente di quello che stanno facendo le altre eventuali goroutine in esecuzione e se main() termina, termineranno forzatamente tutte.
Dal punto di vista della singola goroutine al termine del calcolo l’invio sul canale del risultato è immediato, essendo questo dotato di capacità pari al numero dei risultati che vi saranno inviati (buffered channel), altrimenti essa avrebbe dovuto attendere che la gorountine main() fosse pronta a ricevere un dato (sincronizzazione del mandante con il ricevente).

Per capire la concorrenza in Go conviene quindi immaginare il funzionamento delle cose in modo dinamico tenendo conto del blocco o meno dell’invio o della ricezione dei dati dai canali.

Prestazioni

Ho fatto alcune prove variando la quantità dei numeri da calcolare. Sulla mia macchina Linux dotata di un processore con un unico core, le prestazioni migliorano solo di alcuni punti percentuali, ed addirittura peggiorano quando crescono i numeri da calcolare in num.
Evidentemente il costo per la creazione delle goroutine — sia pure piccolo — non è compensato su una macchina ad un unico core da vantaggi particolari.
Oltre a capire sperimentando il codice, quello che importa adesso non sono le prestazioni ma che occorre considerare con precisione la natura del problema per poter scegliere o meno una soluzione a calcolo indipentente.

Si tratta di un argomento affascinante!

Difetto

Il codice precedente ha un difetto: è necessario attendere che tutte le goroutine siano state create e lanciate prima di passare a raccogliere i risultati. Per esempio se per creare una goroutine accorresse 1 millisecondo e ciascuna mediamente richiedesse 50ms di esecuzione concorrente, allora i risultati dovrebbero attendere stipati nel canale se le goroutine fossero circa più di 50.

La soluzione è quella di inserire il ciclo di creazione delle goroutine esso stesso all’interno di una goroutine:

func main() {
    // Use all the machine's cores
    runtime.GOMAXPROCS(runtime.NumCPU()) 
    res := make(chan int64)
    
    go func() {
        for _, f := range num {
            go func(f int) {
                res <- fibonacci(f)
            }(f)
        }
    }()
    
    for i := 0; i < len(num); i++ {
        <-res
    }
}

Altro simpatico esempio elegante

Questa volta spediamo sul canale la serie di Fibonacci da una goroutine separata basata su un ciclo for infinito (a terminare il programma sarà brutalmente il termine della funzione main() nella quale chiederemo la stampa dei primi dieci numeri della serie):

package main

import "fmt"

func main() {
    ch := make(chan int)
    go func(a1, a2 int) {
        for {
            ch <- a1
            a1, a2 = a2, a1 + a2
        }
    }(0, 1)
    
    for i := 0; i<10; i++ {
        fmt.Print(<- ch, " ")
    }
    fmt.Println()
}

Sfida…

Invito i visitatori del blog a presentare nuovi schemi di calcolo concorrente o semplicemente solo i risultati ottenuti con i vostri megacalcolatori.

Quello che serve è una installazione di Go, e magari sapere che esistono comode funzioni nel pacchetto time che misurano con precisione il tempo macchina, come nel seguente esempio:

package main

import (
    "fmt"
    "math"
    "time"
)

func main() {
    multiPi := make([]float64, 10000)
    t := time.Now()
    for i := 0; i < 10000; i++ {
        multiPi[i] = math.Pi * float64(i)
    }
    fmt.Printf("Executin time: %v\n", time.Since(t))
}

Un saluto.
R.

La varietà di variabili in Go

Scarica l’articolo per la stampa nel formato pdf: golang_tipi_variabili1.pdf

Sommario

Faremo un excursus sul significato delle variabili chiarendone il loro funzionamento nei moderni linguaggi di programmazione, in particolare con riferimento al Go. Ci soffermeremo sul concetto di variabile valore e su quello di variabile riferimento.
Per la comprensione e l’esecuzione degli esperimenti proposti, è necessario solo un po’ di concentrazione e la lettura dei post sul linguaggio Go apparsi su questo stesso blog.

Variabili

Tutti o quasi tutti i linguaggi di programmazione comprendono tra i concetti di base quello di variabile. Il nome stesso ci dice che è un qualcosa che può cambiare durante l’esecuzione del programma e quel qualcosa è il dato che la variabile rappresenta.

Per fare un esempio di codice in un linguaggio generico, possiamo in modo molto naturale assegnare il valore numerico 10 alla variabile v e sottrarre poi 5:

-- in un linguaggio generico...
v = 10
print( v )  --> stampa 10

v = v - 5
print( v )  --> stampa 5

Se provo a creare una seconda variabile q con il valore della prima mi aspetto che riceva il valore che v conteneva al momento dell’assegnazione. Ma se poi la prima variabile cambia che ne è della seconda?
Il codice seguente chiarisce il dubbio sul comportamento delle variabili:

-- sempre scrivendo il codice
-- in un linguaggio generico
v = 10
q = v

print(q) --> stampa 10

-- poi v cambia...
v = v - 5
print(q) --> stampa 10 o 5?

Ci si può attendere due soli risultati:

1. la seconda variabile non cambia mantenendo il valore 10;
2. la seconda variabile cambia cambiando a sua volta in 5 come la prima.

Dal C, al C++, a Java

Siamo partiti da un concetto piuttosto semplice: dare un nome al contenitore di un dato che può cambiare durante l’esecuzione del programma — ovvero a “run-time” — ma ben presto ci siamo resi conto che è necessario scegliere come effettivamente rappresentare le informazioni, e queste scelte influenzeranno nel bene e nel male le applicazioni.

Ogni linguaggio dunque affronta problemi di progettazione complessi, con esigenze spesso opposte, come ben testimonia la loro evoluzione storica, per esempio dal C, al C++, a Java. Ad ogni generazione l’ingegneria del software mette a frutto anni di lavoro e l’esperienza di milioni di righe di codice in un nuovo linguaggio.

Tipi di variabili

Eravamo rimasti al dubbio se nel nostro ipotetico linguaggio sia opportuno o meno agganciare il valore della seconda variabile a quello della variabile da cui era stata costruita. Verifichiamo subito qual è stata la scelta dei progettisti del Go 🙂

Per una variabile di tipo intero la verifica è:

package main

import "fmt"

func main() {
    v := 10
    q := v
    // modo compatto di scrivere v = v - 5
    v -= 5

    // stampa 10 o stampa 5?
    fmt.Println(q)
}

invece per una variabile di tipo []int, ovvero uno slice la verifica è:

package main

import "fmt"

func main() {
    // uno slice:
    v := []int{10}
    q := v
    v[0] -= 5
    // stampa [10] o stampa [5]?
    fmt.Println(q)
}

Otteniamo tutti e due i comportamenti! Verificate per esercizio a quale dei due esempi corrispondono i casi (non vi farà male e vi ruberà solo un minuto se utilizzate Go Playground).

Variabili valore

Se la variabile è intesa come il contenitore stessso in cui si trova il dato, creandone una per mezzo di un’assegnazione di un’altra variabile verrà creato semplicemente un nuovo contenitore con il dato in quel momento contenuto in quest’ultima.
Stiamo parlando delle variabili valore che forniscono l’accesso diretto al dato.

Quello che abbiamo definito contenitore è in sostanza il segmento di memoria che contiene la rappresentazione binaria del dato. Nella figura di seguito è rappresenta la dinamica della creazione e della modifica delle variabili valore v e q del codice di esempio.

Schema di funzionamento delle variabili valore

…e le strutture?

Questo ve lo posso dire: le strutture in Go sono memorizzate in variabili valore, lascio a voi scrivere per utile esercizio il breve codice che lo verifica…

Variabili riferimento

Se la variabile è intesa come il nome del contenitore in cui si trova il dato, allora creandone una per mezzo di un’assegnazione da un’altra variabile, verrà copiato il nome del contenitore nella nuova. Si tratta delle variabili riferimento che forniscono un accesso indiretto al dato tramite informazioni riguardanti il contenitore.

Anche le variabili riferimento sono di tipo valore nel senso che dopotutto contengono direttamente le informazioni solo che non rappresentano il dato ma solo quello che serve al compilatore per raggiungerlo.

Ecco una rappresentazione schematica dello stesso codice precedente che coinvolge le variabili v e q ma stavolta di classe reference.

Schema di funzionamento delle variabili riferimento

Il terzo tipo: i puntatori

Non dovrebbe esistere un terzo tipo di variabili perché all’inizio del post abbiamo riscontrato che ci possono essere solo due situazioni che poi abbiamo associato alle variabili valore ed alle variabili riferimento.

In Go sono disponibili, come in C ed in C++, i puntatori ed in effetti non costituiscono un terzo tipo di variabile perché (almeno in Go) sono contenuti in normali variabili valore. Per convincerci eseguiamo il solito programma di prova:

package main

import "fmt"

func main() {
    n, m := 10, 5 // tipi int

    p1 := &n // tipo *int
    p2 := p1

    p1 = &m
    fmt.Println(*p1) // stampa 5
    fmt.Println(*p2) // stampa 10
}

I puntatori quindi sono variabili valore che contengono l’indirizzo grezzo di memoria dove si trova un dato. Dal punto di vista del linguaggio possiamo considerare i puntatori come delle variabili riferimento primitive. Con i puntatori infatti, gestiamo esplicitamente indirizzi di memoria ottenendoli con l’operatore & come abbiamo appena visto nel listato precedente, ed indichiamo esplicitamente il valore puntato deferenziando il puntatore con l’operatore *.

Se affermiamo questo, possiamo anche dire in modo speculare che le variabili riferimento sono un tipo evoluto di puntatore perché nel codice le scriviamo come normali variabili. È il compilatore che svolge il lavoro “primitivo” per noi elaborando nel modo opportuno le informazioni effettive celate nella variabile riferimento.

Possiamo a questo punto rispondere a queste domande:

1. due variabili riferimento di uno stesso oggetto avranno lo stesso indirizzo di memoria?
2. sapendo che in Go alle funzioni vengono passate le copie degli argomenti, cosa accade se modifichiamo una variabile riferimento all’interno di una funzione?
3. in Go, conviene passare ad una funzione un puntatore a slice o lo slice stesso?

Risposta uno

Due variabili riferimento di uno stesso oggetto avranno lo stesso indirizzo di memoria?

Se una variabile riferimento è veramente una variabile valore che contiene un riferimento ad un dato in memoria, ne segue che avrà un proprio indirizzo di memoria diverso da quello di qualsiasi altra variabile dello stesso tipo anche se si riferisce allo stesso oggetto.
Verifichiamo per prima cosa se possiamo conoscere facilmente l’indirizzo di memoria di una variabile valore e di una variabile riferimento con questo minicodice:

package main

import "fmt"

func main(){
    val := 10
    // stampa --> 'val' address: 0x10d50038
    fmt.Println("'val' address:", &val)

    ref := []int{1, 2, 3}
    // stampa --> 'ref' address: &[1 2 3]
    fmt.Println("'ref' address:", &ref)
}

L’operatore & restituisce il puntatore con l’indirizzo di memoria di una variabile qualsiasi, ma la funzione fmt.Println() esegue giustamente una stampa ad alto livello del puntatore alla variabile riferimento rispettandone la natura.
Anziché far decidere alla funzione tuttofare fmt.Println() il formato di stampa possiamo farlo esplicitamente usando il segnaposto %p (consulta la documentazione del pacchetto fmt):

package main

import "fmt"

func main() {
    // una slice, due variabili reference
    s1 := []int{1, 2, 3, 4 ,5}
    s2 := s1

    fmt.Printf("address di s1: %p\n", &s1)
    fmt.Printf("address di s2: %p\n", &s2)
    // stampano -->
    // address di s1: 0x10d6f100
    // address di s2: 0x10d6f0f0

    // verifichiamo che le due variabili
    // si riferiscono allo stesso slice
    s1[0]++
    s1[1]++
    s1[2]--
    s2[2]--
    s2[3]++
    s2[4]++
    fmt.Println(s1,s2)
    // stampa --> [2 3 1 5 6] [2 3 1 5 6]
}

La risposta iniziale è corretta: due variabili riferimento non sono puntatori non contenendo un riferimento diretto alla memoria ma contengono dati nascosti al programmatore ciascuna in un’area di memoria propria.

Risposta due

Sapendo che in Go alle funzioni vengono passate le copie degli argomenti, cosa accade se modifichiamo una variabile riferimento all’interno di una funzione?

Dunque, se l’argomento viene copiato all’interno della funzione la variabile riferimento sarà si una copia dell’originale, e conterrà quindi le stesse informazioni nascoste per l’accesso ai dati, ma un istruzione di modifica all’interno della funzione modificherà l’oggetto, l’unico oggetto, a cui sia l’argomento passato che l’argomento di funzione si riferiscono.

Utilizzando il tipo map[string]int lascio al lettore la scrittura del minicodice di verifica…

Risposta tre

In Go, conviene passare ad una funzione un puntatore a slice o lo slice stesso?

La variabile che contiene uno slice è reference, quindi passare un puntatore a slice è solo più complicato: non ci si guadagna nemmeno con la dimensione in memoria degli argomenti.

Una domanda per il lettore curioso

In Go le funzioni sono tipi di prima classe (come in Lua, copioni!). Questo significa che possiamo passare una funzione come argomento di un’altra e creare funzioni anonime.
La domanda è questa:

Le variabili che contengono una funzione in Go sono di tipo valore o di tipo riferimento?

Conclusione

Abbiamo studiato insieme le due classi di variabili in linguaggio Go, variabili valore e variabili riferimento, lasciando al lettore un po’ di utile lavoro da fare su alcuni esercizi.

Come regola generale i moderni linguaggi di programmazione fanno si che ai tipi di dato semplici come i numeri ed i booleani sia associato il tipo di variabile valore, mentre ai dati complessi come gli oggetti sia associato il tipo di variabile riferimento.

Un saluto.
R.

Espressioni regolari in Perl

Il mio primo messaggio 🙂

Ciao a tutti!
Per questo mio primo messaggio su questo blog (grazie mille per l’ospitalità) vi parlerò di espressioni regolari in Perl, ma non fatevi prendere dal panico (altrimenti sarò io a farlo…).

Una definizione intuitiva di espressione regolare

Immaginiamo un file di testo come una serie di porte con serrature corrispondenti ad una qualsiasi sequenza dei suoi caratteri. Se per esempio il testo è ‘Casa dolce casa’ la chiave ‘dolce’ aprirà una porta sola ma la chiave ‘asa’ ne aprirà due, una presente nella prima parola ed una nella terza.

L’espressione regolare non è altro che un modo per generare chiavi da provare sul testo e quando una porta si apre possiamo fare sostanzialmente due cose:
* prendere atto che la chiave ha funzionato (come accade quando si vuol validare un indirizzo di posta elettronica);
* oppure se la chiave ha funzionato possiamo voler manipolare il testo (come accade quando si sostituisce una parola con un’altra).

L’utilità delle espressioni regolari sta nel fatto che con esse possiamo generare chiavi anche molto sofisticate in modo semplice ed essenziale: basta scrivere la giusta sequenza di caratteri criptici… 🙂

Come sperimentare?

Il linguaggio Perl è stato progettato per essere un potente strumento per modificare il testo ed è quindi naturale che disponga di una potente libreria per le espressioni regolari (dette anche RegExpr o RegExp oppure ancora RE), ed è anche facilmente reperibile su moltissimi sistemi operativi compreso Windows ed ovviamente Linux e Mac OS X dove lo troveremo già installato (date il comando perl -v per constatarlo).

Se siete poco pratici della riga di comando consiglio di leggere una buona (spero) guida, essenziale nel darvi i concetti di base come per esempio la Guida Tematica alla riga di comando scaricabile liberamente dal sito del GuIT e contenente ulteriori esempi di correzione massiva del testo.

Invece, l’ottimo tutorial PerlReQuick della documentazione ufficiale di Perl vi fornirà con molta chiarezza le informazioni di base sulle espressioni regolari.

La modalità con cui useremo Perl non sarà quella di scrivere codice in uno script ma quella più semplice di digitare un comando al terminale che eseguirà operazioni di sostituzione su molti file di testo in una volta, in una forma estremamente compatta ed immediata.
Il comando avrà la seguente struttura:

$ perl <opzioni> <regexp> <file> <file> ...

Primo esempio: di città in città

Prima di tutto consiglio vivamente di fare gli esperimenti su una copia dei file originali fino a che non si è sicuri di intervenire correttamente sul testo.

La sostituzione si scrive nella forma ‘s/regexp/nuovo testo/’: il carattere iniziale s sta per string ed è obbligatorio poi, separati da caratteri slash, ci sono due campi: il primo è l’espressione regolare, la chiave che verrà provata nelle porte del testo, il secondo è il nuovo testo di sostituzione.
Immaginiamo che nel testo contenuto nel file ‘city.txt’ devono essere sostituite tutte le occorrenze della parola ‘Savona’ con ‘Genova’. Il comando Perl è questo:

$ perl -i -p -e 's/Savona/Genova/g' city.txt

Se osserviamo il formato dell’espressione regolare ci accorgiamo che il primo campo è semplicemente la sequenza dei caratteri da sostituire, poi, che è comparso un nuovo carattere non previsto in coda all’espressione: la g. Si tratta di un modificatore che sta per global ed assicura che tutte le occorrenze trovate e non solo la prima vengano sostituite.
L’opzione al comando -i (inline) dice al compilatore perl di modificare i file sovrascrivendo gli originali. Per rimediare ad eventuali errori l’unico modo è fare una copia di backup dei file e per comodità possiamo farla fare al comando stesso specificando un suffisso all’opzione inline: -ibak oppure -i.bak.
L’opzione -p processa il file con un ciclo (il testo può passare al comando per singole linee) e l’opzione -e (esegui) indica che il codice da eseguire è quello che seguirà subito dopo.

E se per caso abbiamo scritto ‘savona’ anziché ‘Savona’ cosa succede? Semplice, la chiave non gira e ci perderemo quella sostituzione.
Se vogliamo che la chiave giri per entrambe allora o aggiungiamo in coda un ulteriore modificatore i (ignore case):

$ perl -i -p -e 's/Savona/Genova/gi' city.txt

oppure cambiamo l’espressione regolare usando le classi di caratteri definite con parentesi quadre:

$ perl -i -p -e 's/[Ss]avona/Genova/g' city.txt

Ed ancora, se dobbiamo sostituire la città ‘Sestri Levante’ con ‘Imperia’ come cavarsela con gli spazi? Niente panico, se è possibile che tra ‘Sestri’ e ‘Levante’ ci sia un carattere spazio, o addirittura una tabulazione, basta usare un altro tipo di classe di caratteri: un backslash seguito da un carattere.
Fa al caso nostro \s che rappresenta uno spazio, una tabulazione od un ritorno a capo od altre spaziature.
E se temiamo che vi siano più caratteri di spaziatura tra le parole possiamo usare i quantificatori di match repetitions, per esempio + significa che il carattere che lo precede può presentarsi una o più volte.
Riassumendo il comando sarà:

$ perl -i -p -e 's/Sestri\s+Levante/Imperia/g' city.txt

Secondo esempio: cambiare data

La situazione: nella cartella ‘src’ ci sono molti file sorgenti Python di estensione ‘.py’ che contengono la data di versione 20/01/2008. Vogliamo con un unico comando modificarla in 5/11/2012. Ipotizzando che nei file le date contenute nel testo siano esclusivamente quelle di versione, un possibile comando Perl è il seguente (poiché la slash funziona da separatore dobbiamo inserirla con il carattere di escape che è il backslash quindi ‘\/’ corrisponde a ‘/’):

$ perl -p -i-bak -e 's/20\/01\/2008/5\/11\/2012/g' src/*.py

Possiamo fare di meglio generalizzando il pattern di ricerca delle date per rendere il comando indipendente dal valore attuale, con la classe ‘\d’ che corrisponde ad una cifra qualunque:

$ perl -p -i-bak -e 's/(\d{1,2})\/\d{1,2}\/\d{4}/5\/11\/2012/g' src/*.py

Abbiamo usato tra parentesi graffe una match repetition molto restrittiva: per il giorno ed il mese ricerchiamo numeri con solamente una o due cifre e per l’anno numeri solamente con quattro cifre (certo includendo anche date senza senso del tipo 0/00/0000).
A questo punto è facile modificare il formato della data in quello internazionale yyyymmdd:

$ perl -p -i-bak -e 's/(\d{1,2})\/(\d{1,2})\/(\d{4})/$3$2$1/g' src/*.py

Se inseriamo chiavi tra parentesi tonde formiamo un gruppo la cui corrispondenza sarà assegnata alle variabili $1, $2 ecc a seconda della posizione.

Esercizio: validare una data

Qual è l’espressione regolare che valida anche se non proprio rigorosamente la correttezza della data?
Suggerimento: e se utilizzassimo classi di caratteri includendo tra parentesi quadre le cifre ed il quantificatore ‘?’?

Esempio avanzato: tag html

Situazione: disponiamo di un numero elevato di file in formato html contenenti titoli racchiusi nel tag di header in questo modo:

<h3>Titolo di sezione</h3>

Tuttavia vorremmo rendere i titoli più evidenti. Dovremo quindi sostituire i tag utilizzando un livello superiore di sezione trasformando per esempio il codice precedente nel seguente dove anziché il livello 3 si usa il livello di importanza 2:

<h2>Titolo di sezione</h2>

Per utilizzare le espressioni regolari ci serve qualcosa di sofisticato perché una volta trovato un tag di apertura o di chiusura titolo, è necessario effettuare un calcolo estraendo il numero del livello attuale per diminuirlo di 1. Il testo di sosituzione è una funzione della chiave.
La strategia è la seguente: lanciare un primo comando che marchi tutti i numeri di livello e successivamente lanciare un secondo comando che esegua il calcolo.
Salviamo il file ‘test.html’ con il seguente contenuto:

<h3>Titolo di sezione livello 3</h3>
bla bla bla
<h4>Titolo di sezione livello 4</h4>
bla bla bla
<h5>Titolo di sezione livello 5</h5>
bla bla bla

Un tag di titolo html, di apertura o chiusura che sia, ha come pattern il seguente:

   <h\d> oppure <\/h\d>
   od in un unico pattern:
   <\/?h\d>

Marchiamo il numero di livello con una notazione di cui siamo sicuri non presentandosi mai nei file, per esempio racchiudere con tre caratteri chiocciola il numero di livello. Ecco il comando:

$ perl -i-bak -p -e 's/<(\/?)h(\d)>/<$1h@@@$2@@@>/g' test.html

A questo punto il più è fatto e basta dare il secondo comando che ricerca i numeri di livello precedentemente marcati, estrae il valore con un gruppo e lo sostituisce con il valore diminuito di 1:

$ perl -i-bak -p -e 's/@@@(\d)@@@/$1-1/ge' test.html

Il modificatore g cambia tutte le occorrenze, il modificatore e sta per execute e fa si che il testo sia prima valutato e poi inserito.

Ecco come appare il file dopo l’esecuzione dei comandi:

<h2>Titolo di sezione livello 3</h2>
bla bla bla
<h3>Titolo di sezione livello 4</h3>
bla bla bla
<h4>Titolo di sezione livello 5</h4>
bla bla bla

Non sono riuscito a trovare il modo di far eseguire il calcolo mescolandolo con altro testo, probabilmente perché non conosco abbastanza il Perl, perciò chi di voi trova il modo di lanciare un unico comando anziché due, vince un viaggio premio di una settimana per due persone a Juhansic Park…

Esercizio: estrarre indirizzi e-mail

Per esercizio elaborate il comando Perl per estrarre tutti gli indirizzi di posta elettronica presenti nei file di estensione ‘txt’ presenti nella directory corrente e salvarli nel file ‘email.txt’.
Se ci riuscite questa volta non vincete nulla (tempi duri per i viaggi premio), ma come consolazione potete pubblicare la soluzione nei commenti.
Suggerimenti: forse eliminando l’opzione -p e reindirizzando l’output in un file di testo…

Finale

Possiamo rilassarci adesso. Il temibile guazzabuglio di caratteri delle espressioni regolari dovrebbe fare un po’ meno paura dopo aver fatto gli esperimenti.

Rilassarsi d’accordo, ma non dimenticatevi di mandarci i vostri esempi avanzati. Potremo includerli nel post.
Grazie ed alla prossima.
Robitex

Kinder programming

(questo post è gentilmente offerto da piergiu, nuovo e prezioso collaboratore di ok panico!)

“Ci scusiamo per l’intrusione, il palinsesto di “Ok, panico” riprenderà al più presto!”

Questo post è rivolto ai giovani, che dico giovani, giovanissimi, anzi, appena usciti dall’asilo!
Voi direte: ” Eh, adesso cosa vuoi dire, che questo post di ok panico è per i bambini di 6 anni? eh? vuoi insegnare loro a programmare in python o c++? già da questa età?”
e io potrei tranquillamente rispondervi: “Insegnare a programmare ai bambini di 6 anni? Non io, ma voi! e non in python o c++, troppo presto..casomai tornano qui su Ok, panico e sfogliano il grande archivio costruito da juhan, dr.prof e altri!”

Non tanto per tentare inutilmente di fare concorrenza all’India che sforna prodigi informatici di giovane età,  ma per far si che i nostri futuri successori siano già pronti e con delle armi in più per affrontare questo mondo che ogni giorno trova modo di programmarci! (“ah ci metti pure la morale eh?” – “no però controlla questo video (link a youtube) e poi mi dirai..”)

Quanto iniziai sbadatamente a programmare fu in prima superiore col pascal e turbopascal: un pochetto ostico tant’è che solo in pochi di quella classe di una 20ina studenti ci ‘affezionammo’ alla programmazione. Peccato!

Forse era anche già tardi, ma chissà: per questo non perdiamo altro tempo, bando alle ciance e iniziamo sul serio.
Infondiamo il piacere del programmare ai giovincelli!

Scratch!

Non si tratta di un linguaggio di programmazione, ma il concetto è quello. Certo a un bambino non interessa (per ora) se questo linguaggio sia o meno Turing completo. Non interessa nemmeno avere subito a che fare con i flowchart.
Diamogli qualcosa di familiare, come dei blocchi,mattoncini..mattoncini stile lego!
Andate qua al sito ufficiale e prelevate una bella copia di questo software: anche se siete esperti, vi farà piacere usare questo software.

Scratch è sviluppato dal Lifelong Kindergarten Group dei Media Lab del MIT, con il supporto finanziario della National Science Foundation, di Microsoft, Intel Foundation, Nokia, Iomega, e dei consorzi di ricerca dei Media Lab del MIT.

Grandi nomi per un progetto ambizioso(non sono solo io con idee strane, di programmatori giovani alla Dexter ..)

Quando i ragazzi creano e condividono i loro progetti Scratch, imparano importanti idee matematiche e computazionali e allo stesso tempo imparano a pensare creativamente, a ragionare con sistematicità e a lavorare in collaborazione.

La comunità online di Scratch ne fa di tutti i tipi, dai giochi alle avventure grafiche, ma anche la semplice programmazione è ammessa.
Infatti esistono varie sezioni di ‘mattoncini’ o blocchi, dove è possibile inizializzare variabili, cambiarne valore, generare numeri random, fare confronti da risultati booleani, for, while, while(true), do-while e altri, come anche controlli di collisione e gestione di varie tipologie di eventi: insomma Scratch è per l’informatica, quanto un Phun( ora Algodoo ) è per la fisica, o Geogebra per algebra/matematica!

L’interfaccia è uber-semplice, e l’uso ancora di più: basta fare drag ‘n’drop dalla palette dei blocchi e incastrarli nel piano di lavoro, nel modo più oppurtuno, creando sequenze con annidamenti e gestione parallela di eventi!
Un esempio: ho creato questo script/sketch/scratch che di solito faccio con la penna su un foglio quadrettato quando sono in una situazione noiosa(meeting/lezione/{a scelta}) e non posso uscirne immediatamente.

Da un quadretto mi sposto seguendo una direzione e riempiendo i quadretti che incontro fino ad arrivare ad un bordo per poi cambiare direzione. Fino a riempire il foglio, o fino a creare un qualche pattern carino, o fino a fine inchiostro.
State già pensando a come farlo in Java, c++, python, visualbasic, in fortan vero? Nerd-power ♥
(fatemi sapere come avete fatto voi qui sotto con un commento, ci tengo!)

Ebbene ecco uno screenshot del programma creato in due minuti circa.

Lo scopo originale di Scratch è quello di impartire programmi a un esserino dalle sembianze di un gatto, ma in realtà io ho cambiato semplicemente la cosidetta “sprite”, immagine, che rappresenta il gatto e l’ho sostituita con un pixel(tutto nello stesso ambiente di Scratch).

Per ogni direzione impostata si creano pattern differenti.
Come si può notare ho creato due blocchi, uno che risponde all’evento del click sulla bandiera verde per mandare in Run lo script e uno che risponde alla pressione della barra spaziatrice per fermare lo script.
Nel primo inizializzo delle variabili che mi servono come range per il punto iniziale del disegno, scelto random.
Poi passo a disegnare e in una sorta di loop infinito eseguo i movimenti e controllo se è necessario cambiare direzione poiché giunti al bordo.
Nel secondo blocco impongo di fermare tutta l’esecuzione alla pressione della barra spaziatrice.

Notare il linguaggio naturale, dall’uso dell’imperativo nei verbi, come a ricordare cosa è un algoritmo, ovvero una sequenza di passi da fare per raggiungere uno scopo.
Non c’è molto altro da dire a riguardo, la classica situazione del “si fa prima a fare che a dire”.
Possibilità di playback di audio e di uso di penna( come nell’esempio ), come anche possibilità di mettere in pausa un processo per {n} secondi e così via.

Concludendo questa invasione barbarica su Ok, Panico, vi invito a provare voi stessi Scratch e sopratutto ai vostri parenti più piccoli: evangelizzateli con la parola dell’informatica. Fatemi sapere come va!
Ramen.

Se siete arrivati a leggere fin qua, vi ringrazio per la pazienza e vi ricordo :

Programma o sii programmato.