Scuola Politecnica e delle Scienze di Base Corso di Laurea in Ingegneria Informatica

Elaborato finale in Programmazione I

Linguaggio Scala: esempi di sviluppo

Anno Accademico 2016/2017

Relatrice: Chiar.ma Prof.ssa Valeria Vittorini

Candidato: Gianluca Vaccaro matr. N46001110

INDICE

1 Linguaggi di programmazione…………………………………………………….. p. 1

1.1 Programmazione imperativa…………………………………………….. p. 2

1.2 Programmazione orientata agli oggetti………………………………….. p. 2

1.3 Programmazione Concorrente…………………………………………… p. 3

1.4 Programmazione Logica……………………………….………………… p. 4

1.5 Linguaggi di scripting………………………………….………………... p. 4

2 Programmazione Funzionale…………………………….....……………………… p. 5

2.1 Datatype-Generic Programming, Confronto tra un linguaggio funzionale

puro e uno ibrido ………………………………………………………….… p. 6

3 Il Linguaggio Scala………………………………………………………………... p. 7

3.1 Elementi Object Oriented………………………………………………... p. 7

3.1.1 Le Classi in Scala………………………………..…………….. p. 7

3.1.2 Ereditarietà e overriding……………………..………………… p. 8

3.1.3 Trait………...……………………………………..…………… p. 8

3.1.4 Classi Parametriche…………...………………..……………… p. 9

3.1.5 Oggetti singleton………………………………..…..….……… p. 9

3.1.6 Notazioni Variabili..………………….…….…...…………….. p. 10

3.2 Elementi Funzionali…………………………………………………….. p. 11

3.2.1 Funzioni di alto livello e funzioni anonime…………………... p. 11

3.2.2 Upper and lower type bounds…………………….…..………. p. 11

3.2.3 Case classes…………………………………………………… p. 13

3.2.4 Pattern Matching……………………………………..……….. p. 13

3.2.5 Abstract types and Anonymous Class……………….………... p. 14

3.3 Classi Innestate……………………..………………….……………….. p. 14

3.4 Concorrenza in Scala………………………………………….………… p. 15

4 Esempi di sviluppo……………...………………………………………....……… p. 18

4.1 Produttori-Consumatori………………………………………….……... p. 18

4.2 Heap Sort……………………………………………………….………. p. 19

5 Conclusioni…………...………………………………………………………….. p. 24

1

Capitolo 1

Linguaggi di programmazione

Il linguaggio è la fonte principale di comunicazione tra gli esseri umani. Ogni paese o

regione dichiara un proprio linguaggio tramite il quale comunicare con gli abitanti dello

stesso. In egual modo le persone hanno bisogno di comunicare con le macchine, per tale

motivo si ha bisogno di un certo linguaggio che possa essere compreso sia dai computer

che dagli esseri umani. Tali linguaggi sono conosciuti come linguaggi di

programmazione. Per tale scopo sono nati molti linguaggi diversi per svolgere diversi tipi

di lavori sul computer. Ognuno di loro definisce un proprio set di regole, grammatica e

simboli. Questi linguaggi possono essere classificati in molti modi. Mentre il primo vero

linguaggio di programmazione era composto da soli due simboli, ‘0’ e ‘1’ (linguaggio

macchina), oggi possiamo scrivere programmi per computer usando termini comuni di

inglese e matematica.

Un linguaggio di programmazione, per essere definito tale deve rispettare certi requisiti

fondamentali [1]:

Deve essere universale: ogni problema, se può essere risolto da un computer, deve

avere una soluzione che possa essere implementata nel linguaggio adottato. Qualsiasi

linguaggio che definisca funzioni ricorsive o iterazioni è universale.

Deve utilizzare una grammatica che sia ragionevolmente naturale per risolvere

problemi tipici del suo dominio applicativo.

Deve essere implementabile su un computer, cioè, deve essere possibile eseguire

ogni programma, esente da errori, nel linguaggio utilizzato.

Una buona conoscenza delle diverse famiglie di linguaggi di programmazione è

indispensabile tanto quanto la conoscenza del singolo linguaggio poiché questa ci aiuta

a individuare il linguaggio più adatto alla risoluzione di un dato problema. Differenti

selezioni dei concetti chiave supportano stili di programmazione totalmente diversi,

questi sono chiamati paradigmi di programmazione.

Possiamo suddividere i linguaggi in sei paradigmi principali [1]:

Programmazione imperativa: caratterizzata dall’uso di variabili, comandi e

procedure.

Programmazione orientata agli oggetti: caratterizzata dall’uso di oggetti, classi ed

ereditarietà.

Programmazione concorrente: caratterizzata dall’uso di processi concorrenti e

varie astrazioni di controllo.

Programmazione logica: caratterizzata dall’uso di relazioni.

Linguaggi di scripting: utilizzati, in generale, o per automatizzare processi (batch)

o per creare applicazioni web.

Programmazione funzionale: caratterizzata dall’uso di funzioni.

Descriviamo sinteticamente le principali caratteristiche dei vari paradigmi di

programmazione ad eccezione di quella funzionale che approfondiremo nel capitolo

seguente.

2

1.1 Programmazione imperativa

La programmazione imperativa è così definita poiché si basa su comandi che aggiornano

variabili allocate in memoria. Questa è stata il paradigma dominante fino agli anni ’90

quando si dovette scontrare con l’object oriented.

La programmazione imperativa suddivide il codice in subroutine (funzioni e/o procedure)

che eseguono specifici compiti consentendo, tal volta, di sfruttare i salti condizionali (go-

to). La suddivisione in funzioni è pensata per ridurre la complessità del programma

abbracciando un’astrazione di tipo funzionale in cui è sufficiente conoscere solo la

dichiarazione della procedura, tralasciandone i dettagli implementativi.

I concetti chiave della programmazione imperativa sono: variabili, comandi, procedure

e, più recentemente, astrazione dei dati.

Molti programmi hanno lo scopo di modellare processi che interessano entità del mondo

reale, variabili e comandi permettono di rappresentare, rispettivamente, sia le entità stesse

che i processi che agiscono su queste ultime. Le procedure rappresentano un altro

concetto chiave in quanto, come detto prima, creano utili astrazioni sui comandi.

L’astrazione dei dati non è strettamente essenziale ai fini della programmazione

imperativa, infatti non viene supportata dai classici linguaggi imperativi come C e Pascal,

invece è diventata un concetto chiave nei più moderni linguaggi imperativi come Ada.

Con l’astrazione dei dati possiamo distinguere tra il comportamento osservabile di un

dato astratto e l’algoritmo con il quale si agisce su di essi.

1.2 Programmazione orientata agli oggetti

Abbiamo appena visto come l’astrazione dei dati è diventata un concetto importante nei

moderni linguaggi imperativi; infatti possiamo implementare un intero programma in

termini di soli dati astratti e classi. Se facciamo un piccolo passo in avanti rispetto al

paradigma imperativo e introduciamo il concetto di gerarchie di classi raggiungiamo un

distinto paradigma: la programmazione orientata agli oggetti.

I concetti chiave della programmazione orientata agli oggetti sono: oggetti, classi e

sottoclassi, ereditarietà e polimorfismo.

Gli oggetti permettono di modellare le entità del mondo reale in modo naturale; un

oggetto ha uno o più componenti variabili (attributi) ed è equipaggiato con metodi che

operano su di essi. Gli attributi degli oggetti sono in genere privati e, in questo caso, si

può agire su di essi solo tramite i metodi dell’oggetto. Gli oggetti inoltre ci forniscono

anche un modo naturale per esprimere le entità appartenenti al mondo informatico come

file, pagine web e componenti di interfacce grafiche.

Una classe rappresenta l’unità fondamentale dell’object oriented e rappresenta entità con

metodi ed attributi comuni; una sottoclasse, tramite l’Ereditarietà, estende una classe

aggiungendole attributi e, talvolta, modificando (override) metodi. L’istanza di una

classe è definita oggetto, ovvero una entità con uno specifico stato che esegue specifici

compiti.

Il polimorfismo è un concetto chiave che abilita un oggetto di una sottoclasse ad essere

trattato come se fosse un oggetto della sua superclasse. Questo ci permette, ad esempio,

3

di creare collezioni eterogenee di oggetti di differenti classi, definendo la collezione in

termini di una superclasse comune agli oggetti desiderati.

Le classi e le loro gerarchie rappresentano strumenti particolarmente adatti (e

riutilizzabili) per l'analisi e il design di applicazioni distribuite facilitando lo sviluppo di

sistemi software di grandi dimensioni.

I concetti di oggetti e classi trovano le loro origini nel linguaggio Simula (il primo

linguaggio object-oriented), tuttavia il primo linguaggio puro orientato agli oggetti è stato

Smalltalk, in cui interi programmi sono costituiti da sole classi. C++ fu sviluppato

aggiungendo i concetti object-oriented al C, unendo, così, le comunità di programmatori

C e object-oriented; Java fu sviluppato per semplificare drasticamente il C++. Java inoltre

è adatto per la creazione di applet (piccoli programmi applicativi portatili incorporati

nelle pagine Web), come conseguenza della sua implementazione altamente portatile

grazie alla Java Virtual Machine, che è stata incorporata in tutti i principali browser Web.

1.3 Programmazione Concorrente

La programmazione concorrente è ancora abbastanza immatura, nonostante sia antica

quasi quanto la programmazione stessa e siano stati sviluppati attivamente diversi

approcci. Uno dei motivi è che i programmi concorrenti devono spesso essere strutturati

in base ad una specifica architettura hardware poiché tali programmi, generalmente, non

si adattano bene su architetture diverse.

La programmazione suddetta è chiamata in questo modo in quanto consente di

sovrapporre l'esecuzione dei comandi, sia mediante un interblocco arbitrario

(multiprogrammazione) sia mediante esecuzione simultanea su più CPU

(multiprocessing).

I concetti chiave della programmazione concorrente sono: esecuzione parallela di due o

più processi, sincronizzazione tra processi, accesso sincronizzato a dati condivisi da più

processi in mutua esclusione e trasferimenti sincronizzati di dati tramite comunicazione

tra processi.

La principale differenza tra programmazione sequenziale e concorrente riguarda

l’esecuzione parallela delle istruzioni, differenza che porta con sé molte complicazioni

inerenti l’ordine delle istruzioni da eseguire.

La sincronizzazione tra processi permette al programmatore di assicurarsi che i processi

interagiscano tra di loro in maniera ordinata.

La mutua esclusione nell'accesso a variabili condivise ripristina la semantica dell'accesso

e dell'aggiornamento della variabile. Ciò è ottenuto mediante operazioni di

sincronizzazione che consentono a un solo processo di accedere a una variabile condivisa

in qualsiasi momento.

La comunicazione fornisce una forma più generale di interazione tra processi, poiché si

applica nei sistemi distribuiti come nei sistemi centralizzati. Alcuni linguaggi di

programmazione concorrenti sono interamente basati sulla comunicazione, evitando

completamente le variabili condivise e i problemi che esse comportano. Tuttavia, nella

maggior parte dei linguaggi concorrenti la comunicazione si basa sui dati condivisi e non

viceversa.

4

1.4 Programmazione Logica

Anche paradigmi molto diversi tra loro, quali imperativo e funzionale hanno una cosa in

comune: un programma legge degli input e scrive degli output. Poiché gli output sono

funzionalmente dipendenti dagli input, un programma imperativo o funzionale può essere

visto, astrattamente, come una mappatura dagli input agli output. Un programma logico,

invece, implementa delle relazioni. Poiché le relazioni sono più generali delle funzioni

di mapping, un programma logico è potenzialmente di più alto livello risetto ad uno

funzionale o imperativo.

Consideriamo due insiemi di valori S e T, diciamo che r è una relazione tra S e T se, per

ogni 𝑥 ∈ 𝑆 e 𝑦 ∈ 𝑇, 𝑟(𝑥, 𝑦) è vera o falsa. Per esempio “>” è una relazione tra numeri.

Dopo aver implementato una relazione r, potremo eseguire richieste come:

1) Dati a e u, determina se r(a, u) è vera.

2) Dato a, trova tutte le y tali che r(a, y) è vera.

3) Dato u, trova tutte le x tali che r(x, u) è vera.

4) Trova tutte le x e le y tali che r(x, y) è vera.

Una richiesta come la 1) avrà una singola risposta, vero o falso; ma richieste come la 2),

la 3) e la 4) possono avere qualsiasi numero di risposte, anche nessuna. Inoltre richieste

come la 2) e la 3) mostrano che una relazione non fa differenza tra input e output.

Operazioni come questa sono caratteristiche della programmazione logica, questo spiega

perché la programmazione logica è potenzialmente di più alto livello rispetto a quella

imperativa e funzionale.

La programmazione logica pura non utilizza procedure (che appartengono alla

programmazione imperativa e funzionale), utilizzando invece unicamente il

backtracking1, che rappresenta gran parte del suo potere e espressività.

Il maggior, se non unico, esponente della programmazione logica è il Prolog.

1.5 Linguaggi di scripting

Lo scripting è un paradigma caratterizzato da:

Utilizzo di script2 come collante tra sottosistemi.

Rapido sviluppo ed evoluzione degli script.

Modesti requisiti di efficienza.

Funzionalità di alto livello nelle aree specifiche dell’applicazione.

Esso è utilizzato in una varietà di applicazioni. I linguaggi di scripting sono molto diversi

tra loro, tuttavia i punti sopra indicati influenzano la progettazione di tali linguaggi. Un

sistema software spesso è costituito da un numero di sottosistemi controllati o collegati

da uno script. In un tale sistema, lo script è detto collante tra i sottosistemi. Un esempio

di collante può essere un sistema per creare un nuovo account utente in un computer,

1 Il backtracking è una tecnica per trovare soluzioni a problemi in cui devono essere soddisfatti dei vincoli. Una

tecnica classica consiste nell'esplorare strutture ad albero tenendo traccia di tutti i nodi e i rami visitati, in tal modo, nel caso che la ricerca nel ramo attuale non abbia successo, si può tornare indietro al più vicino nodo che conteneva un cammino ancora inesplorato. 2 Uno script è un programma o una sequenza di istruzioni che viene interpretata o eseguita da un altro programma piuttosto che dal processore del computer (come programma compilato).

5

costituito da uno script che invoca i programmi atti ad eseguire le azioni di sistema,

necessarie alla creazione dell’utente.

Gli script sono caratterizzati da rapidi sviluppi e evoluzioni. Alcuni script vengono scritti

e utilizzati una sola volta. Altri script vengono utilizzati frequentemente, ma devono

anche essere modificati spesso in risposta ai cambiamenti dei requisiti richiesti. In tali

circostanze, gli script dovrebbero essere semplici da scrivere e utilizzare una sintassi

sintetica.

L'efficienza non è un requisito essenziale per gli script. Chiaramente uno script usato una

volta non deve essere particolarmente veloce, ma questo è meno evidente per uno script

usato di frequente. Quando uno script viene utilizzato come collante, tuttavia, il tempo di

esecuzione totale del sistema tende a essere dominato dai sottosistemi, che sono

tipicamente scritti in altri linguaggi di programmazione.

I linguaggi di scripting offrono funzionalità di alto livello in determinate aree specifiche

dell'applicazione. Ad esempio, molti script hanno bisogno di analizzare e tradurre testi,

quindi tutti i linguaggi di script forniscono strutture di alto livello per la modellazione

delle stringhe.

I principali linguaggi di scripting sono JavaScript, php e python.

Capitolo 2

Programmazione Funzionale

La programmazione funzionale consente un approccio alla progettazione ed allo sviluppo

del codice in modo differente rispetto alla programmazione imperativa ed OO; il suo

concetto di base risiede nella funzione, nel senso matematico del termine, diverso dalle

funzioni/metodi dei linguaggi procedurali, le quali svolgono pure direttive di calcolo. La

funzione matematica, invece, non esegue calcoli ma si limita a mappare valori e viene

definita, infatti, come una trasformazione.

Il paradigma funzionale si basa sull’idea che un software possa essere descritto attraverso

l’applicazione di tre tecniche principali:

la definizione di un gran numero di funzioni pure, cioè funzioni senza effetti

collaterali, che non dipendono da variabili del mondo esterno ma solo dagli input e da

valori immutabili. Una funzione pura ritorna sempre un valore, tale valore è sempre

lo stesso a parità di condizioni di ingresso, quindi non potrà mai accadere che una

certa funzione ritorni due diversi valori a fronte del medesimo ingresso;

l’applicazione di queste funzioni ai dati soggetti a manipolazione nel software e la

loro combinazione attraverso particolari funzioni, note come funzioni di più alto

ordine, anch’esse pure, che inoltre presentano altre funzioni tra i dati di ingresso e/o

di uscita;

l’uso di dati immutabili e l’assenza di variazione di stato, che permettono di trattare

estese porzioni di un software come se fossero equazioni matematiche.

Orbene, funzioni pure, indipendenti dallo stato di esecuzione di un software,

rappresentano delle relazioni statiche tra entità: il processo di testing sarà quindi più

semplice poiché ogni funzione da testare sarà del tutto indipendente dalle altre. Saremo

quindi in grado di ottenere un software corretto se:

6

ciascuna funzione sarà stata implementata correttamente;

avremo impostato le relazioni corrette tra le entità coinvolte.

Nella programmazione funzionale le funzioni sono anche dati, ossia anch’esse hanno un

tipo associato. Ad esempio, usando la notazione di Scala, possiamo definire il tipo di una

funzione square, che permette di elevare al quadrato un numero intero, nel seguente modo:

type intToInt = (Int) => Int

def square: intToInt = (x) => x*x

possiamo leggere la definizione di type intToInt come una trasformazione che ad un numero

intero in ingresso associa un intero in uscita, def square invece definisce una funzione di

tipo intToInt che a x associa il suo quadrato.

Il primo linguaggio funzionale è stato Lisp, che ha dimostrato in data piuttosto precoce

che programmi significativi possono essere scritti senza ricorrere a variabili e

assegnazione. ML e Haskell, invece, sono linguaggi funzionali moderni. Essi trattano le

funzioni come valori ordinari, che possono essere passati come parametri e restituiti come

risultati di altre funzioni. Inoltre, incorporano sistemi avanzati di tipizzazione,

permettendoci di scrivere funzioni polimorfiche (funzioni che operano su dati di una

varietà di tipi). ML (come Lisp) è un linguaggio funzionale impuro, in quanto supporta le

variabili e l'assegnazione. Haskell è un linguaggio funzionale puro.

2.1 Datatype-Generic Programming, confronto tra un linguaggio funzionale

puro e uno ibrido

La programmazione generica si occupa di rendere i linguaggi di programmazione più

flessibili non compromettendo l’aspetto della sicurezza [2]. La generic programming,

usualmente, si manifesta con parametrizzazioni di vario tipo, grazie alle quali si possono

astrarre le differenze tra diversi oggetti con comportamenti simili. Istanziando i parametri

in vari modi si possono ottenere comportamenti diversi per lo stesso blocco di codice.

Idealmente l’astrazione incrementa l’espressività.

La programmazione generica di tipo Datatype comporta, quindi, la parametrizzazione dei

programmi in base alla forma dei dati. La maggior parte degli approcci al DGP sono

sviluppati in linguaggi di programmazione puramente funzionali come Haskell, che offre

numerose librerie atte alla gestione del DGP. Tuttavia come afferma Jeremy Gibbons [3].

“Noi sosteniamo che il linguaggio ibrido funzionale e orientato agli oggetti, che

implementa Scala, sia in molti modi la scelta migliore. Non solo Scala fornisce gli

equivalenti di tutti i principali vantaggi della programmazione funzionale (come il

Pattern matching o le funzioni di ordine superiore), ma fornisce anche le caratteristiche

più utili della programmazione orientata agli oggetti (come i sottotipi, l'overriding, la

tradizionale ereditarietà singola e l'ereditarietà multipla sotto forma di tratti).” Le

tecniche comuni di Haskell per il DGP possono essere convenientemente replicate in

Scala, mentre l'espressività extra di Scala offre alcuni importanti vantaggi aggiuntivi in

termini di estensibilità e riutilizzo.

7

Capitolo 3

Il Linguaggio Scala

Il nome Scala deriva da “SCAlable LAnguage”, il suo creatore, Martin Odersky, volle

esprimere i modelli comuni di programmazione in modo conciso, elegante e type-safe3.

Trattasi di un linguaggio ibrido, sia funzionale che object oriented, che fa della scalabilità4

il suo punto di forza. Può essere utilizzato come linguaggio di scripting5, come linguaggio

collante in piccoli progetti o come linguaggio concorrente. È puramente orientato agli

oggetti, ossia ogni valore è un oggetto. Tipi e comportamento degli oggetti sono descritti

da classi e tratti, che vedremo a breve. Come suddetto, Scala è anche un linguaggio

funzionale, in quanto ogni funzione è un valore, poiché ogni valore è un oggetto in

definitiva ogni funzione è un oggetto.

È compilato in Java byte Code il quale viene eseguito dalla Java Virtual Machine. Ciò

significa che Scala e Java hanno una piattaforma comune di Runtime e si può facilmente

passare da Java a Scala.

Di seguito analizziamo alcuni aspetti principali del linguaggio Scala suddividendoli in

base al paradigma che rispecchiano. Vediamo dapprima gli elementi Object Oriented ed

in seguito quelli Funzionali, inoltre analizziamo due elementi che non possono essere

assegnati unicamente ad uno dei due mondi, questi sono le classi innestate e la

concorrenza.

3.1 Elementi Object Oriented

3.1.1 Le Classi in Scala

Le classi in Scala sono dichiarate utilizzando una sintassi molto simile a quella usata in

Java. Un’importante differenza rispetto a Java si rinviene nelle definizioni. Scala

definisce per noi: il costruttore, le variabili membro, i getter e, in base al modificatore

var/val, decide se aggiungere o meno i setter. Se i setter non sono aggiunti (caso val) la

classe risulterà immutabile e, quindi, una volta istanziata non se ne potranno modificare

i valori. Inoltre Scala permette di associare un valore di default ai parametri di una classe.

Vediamo un esempio:

class Persona(nome: String = "", cognome: String = "") {

def getNome() = nome

def getCognome() = cognome

}

3 La type safety (sicurezza rispetto ai tipi) è la misura con cui un linguaggio di programmazione previene o avvisa rispetto agli errori

di tipo. 4 Un sistema si dice scalabile quando è possibile aggiungere ulteriori funzionalità senza doverne modificare le caratteristiche

fondamentali. In particolare: - Possibilità di eseguire lo stesso software su computer di potenza diversa. La scalabilità di un software è una caratteristica di grande valore in quanto consente alle aziende che lo acquistano di utilizzarlo inizialmente su macchine poco potenti e successivamente su grossi mainframe. - La scalabilità è un fattore critico per le applicazioni distribuite e indica la capacità di adattarsi all'aumento di utenti, all'incremento dei dati e alla diversificazione delle funzionalità richieste. 5 Un linguaggio di scripting è un linguaggio di programmazione interpretato, destinato, in genere, a compiti di automazione del

sistema operativo (batch) o delle applicazioni (procedure), o a essere usato nella programmazione web all'interno delle pagine web.

8

La classe Persona ha due metodi, getNome e getCognome, che danno l’accesso,

rispettivamente, al nome e al cognome della Persona.

Notiamo che il tipo di ritorno dei due metodi non è specificato esplicitamente. Sarà il

compilatore a inferirlo automaticamente, osservando la parte a destra del segno uguale

dei metodi e deducendo che per entrambi si tratta di valori di tipo String.

3.1.2 Ereditarietà e overriding

In Scala tutte le classi sono figlie di una super-classe. Quando nessuna super-classe viene

specificata, come nell’esempio della classe Persona, la classe scala.AnyRef è

implicitamente usata. La struttura gerarchica di Scala è composta come in Figura 1.

è possibile eseguire la sovrascrittura (override) dei metodi ereditati dalla super-classe.

Pertanto è necessario specificare, esplicitamente, il metodo che si sta sovrascrivendo

utilizzando il modificatore override per evitare sovrascritture accidentali. Come esempio

estendiamo la nostra classe Persona ridefinendo il metodo toString ereditato da Object:

class Persona(nome: String, cognome: String) {

def getNome() = nome

def getCognome() = cognome

override def toString() = s"Persona: nome= $nome, cognome= $cognome";

}

Figura 1

3.1.3 Trait

I tratti in Scala sono simili alle interfacce di java e sono stati inseriti per aggirare il

problema dell’ereditarietà multipla che, a differenza di c++, in Scala non è ammessa.

In Java una classe può implementare un numero arbitrario di interfacce. Questo modello

è molto utile per dichiarare che una classe espone molteplici astrazioni, tuttavia ciò può

comportare che più classi, implementanti la stessa interfaccia, possano avere metodi che

9

eseguono esattamente lo stesso compito. Questo costringerà a copiare e incollare più volte

lo stesso metodo nelle varie implementazioni, rendendo il codice meno leggibile nonché

meno modificabile e riutilizzabile, poiché in caso di necessità, tali comportamenti

dovranno essere modificati all’interno di tutte le classi implementative. Per risolvere

questo problema nei tratti di Scala si ha anche la possibilità di implementare dei metodi;

ad esempio, si potrà definire un tratto generico di Persona in questo modo:

trait Persona{

def mansione() : String

def saluta() = "Ciao"

}

Per implementare un tratto si usa la parola chiave extends, invece per implementare più

tratti si usa la parola chiave with; ad esempio volendo una classe serializzabile, che

implementi anche i dettagli di Persona, si dovrà dichiarare con:

class Studente extends Persona with Serializable

3.1.4 Classi Parametriche

Le classi generiche sono classi che utilizzano un tipo di oggetto come parametro, inserito

all’interno delle parentesi quadre [A], inoltre sono particolarmente utili per definire le

collezioni di dati. Ad esempio:

class Pila[A] {

private var elementi: List[A] = Nil

def inserisci(x: A) { elementi = x :: elementi }

def preleva(): A = {

val currentTop = elementi.head

elementi = elementi.tail

return currentTop }

def size() = elementi.length

}

La classe Pila accetta qualsiasi tipo A come parametro, ciò comporta che la lista di

elementi, inizializzata con l’elemento neutro delle liste “Nil”, può memorizzare elementi

di tipo A. Il metodo inserisci accetta solo oggetti di tipo A, e il metodo preleva ritorna

oggetti di tipo A.

3.1.5 Oggetti singleton

Essendo Scala un linguaggio ad oggetti puro tende ad interpretare tutti i suoi componenti

come se fossero appunto oggetti, per questo motivo, essendo un oggetto dinamico per

definizione i creatori di Scala hanno pensato di rimuovere il concetto di static. Nonostante

l’esistenza di oggetti statici vada contro i dogmi del paradigma ad oggetti, spesso può

tornare utile definire un oggetto che non abbia bisogno di essere istanziato e che possa

essere richiamato in più punti del programma senza rischiare di riferirsi ad un’altra istanza

di sé stesso. Per avere uno strumento equivalente alla keyword static, che però non sia

concettualmente sbagliato (dal punto di vista dell’object oriented), Scala usa il concetto

di oggetto singleton. I singleton sono oggetti istanziati una sola volta e, non essendo

possibile istanziarli su richiesta, non hanno bisogno di alcun costruttore. Possiamo

considerare ogni cosa dichiarata all’interno di un oggetto singleton come fosse uno static.

10

Un singleton si dichiara come una classe sostituendo la parola chiave class con object;

vediamo un semplice esempio di funzionamento:

object OggettoSingleton {

private val array = Array(5, 15, 10, 5, 25, 30, -1,156, 94);

def getArray() = array;

}

Dal main potremo richiamare il metodo getArray() come fosse un metodo statico di

una classe Java: OggettoSingleton.getArray

In realtà questo comportamento non rispecchia appieno il funzionamento dei metodi static

di Java, poiché una funzione dichiarata all’interno di un singleton può essere considerata

solo come static. Per questo motivo, in Scala, una classe e un oggetto singleton possono

essere associati, ossia avere lo stesso nome ed essere dichiarati nello stesso file. In tal

modo, come accade in Java, potremo riferirci ad elementi statici e non della stessa classe.

3.1.6 Notazioni Variabili

Il sistema di tipizzazione di scala tiene conto, insieme al polimorfismo, anche della

gerarchia delle classi. Nel contesto dei linguaggi object oriented se B è una sottoclasse di

A allora Collection[B] è una sottoclasse di Collection[A], nel linguaggio Scala, a seconda

della notazione utilizzata, oltre alla covarianza, vengono introdotte le relazioni di contro-

varianza e invarianza. Per esprimere tale relazione tra gerarchie di classi e tipi polimorfici

si usa la notazione:

Significato Notazione Scala

covariant C[B] è sottoclasse di C[A] [+A]

contravariant C[A] è sottoclasse di C[B] [-A]

invariant C[A] e C[B] non sono correlate [A]

Riportiamo esempi pratici di covarianza e contro-varianza:

class Covariant[+A]

val cv: Covariant[AnyRef] = new Covariant[String]

val cv: Covariant[String] = new Covariant[AnyRef] error: type mismatch;

found: Covariant[AnyRef], required: Covariant[String]

Usando +A e definendo il tipo AnyRef si può istanziare la classe Covariant con qualsiasi

Oggetto che estenda AnyRef, contrariamente se viene definito il tipo come String si può

istanziare Covariant solo con oggetti di tipo String e derivati, ma non con una superclasse

di String.

class Contravariant[-A]

val cv: Contravariant[String] = new Contravariant[AnyRef]

val fail: Contravariant[AnyRef] = new Contravariant[String] error: type mismatch;

found: Contravariant[String], required: Contravariant[AnyRef]

Invece, utilizzando –A e definendo il tipo come String, possiamo istanziare la classe con

qualsiasi superclasse di String, ma non possiamo fare l’inverso.

11

3.2 Elementi Funzionali

3.2.1 Funzioni di alto livello e funzioni anonime

Scala, come abbiamo detto, è un linguaggio funzionale nel senso che ogni funzione è un

valore; per l’uso di tali funzioni Scala inoltre prevede l’uso di funzioni anonime con una

sintassi leggera e supporta l’uso di funzioni innestate.

Per illustrare l’uso delle funzioni passate come valore, consideriamo una funzione exists

che controlla se tutti gli elementi di un dato array soddisfino un certo predicato:

def exists[T](array: Array[T], predicate: (T) => Boolean): Boolean = {

var i: Int = 0;

while (i < array.length && predicate(array(i)))

i = i + 1;

return (i == array.length)

}

Il tipo di elementi dell’array è arbitrario; questo è espresso mediante il parametro [T] della

funzione. Il predicato da verificare è anch’esso arbitrario e viene indicato dalla funzione

di ingresso “predicate”, il cui tipo è un tipo funzionale “(T) => Boolean” che ha come

valore tutte le funzioni aventi come dominio il tipo T e come codominio il tipo Boolean.

La funzione predicate quindi, ad ogni elemento T dell’array assocerà un valore booleano

indicante se l’elemento rispetta il predicato. Le funzioni di ingresso possono essere

applicate come se fossero normali funzioni; un esempio è l’applicazione della funzione

predicate nel ciclo while della funzione. Funzioni che accettano altre funzioni come

argomento o che hanno un codominio funzionale sono dette funzioni di più alto livello.

Ogni qualvolta si vorrà invocare la funzione exists si dovrà specificare il tipo di predicato

che si vuole verificare, questo potrebbe portare a dover definire molte funzioni con nomi

diversi che potrebbero creare confusione e appesantire il codice, per questo motivo Scala

inoltre introduce anche il concetto di funzione anonima, grazie ad esse sarà possibile

specificare il comportamento che dovrà avere la funzione esplicitandolo direttamente in

ingresso ad exists all’atto della sua chiamata; ad esempio se volessimo utilizzare la

funzione appena creata per verificare se tutti gli elementi di un array sono positivi

potremmo semplicemente scrivere (grazie alle funzioni anonime):

val array = Array(5,15,10,5,25,30);

exists(array, (x: Int) => x>0);

In tal modo definiamo la funzione predicate direttamente all’atto dell’invocazione del

metodo exists, tale funzione, dichiarata come “(x: Int) => x>0”, ad ogni elemento di tipo

Int (x: Int) in ingresso associa un valore booleano che indica se quell’elemento sia

maggiore di zero. Questo tipo di funzioni sono dette anonime poiché non necessitano di

un nome che, normalmente, deve essere associato alle funzioni all’atto della loro

definizione.

3.2.2 Upper and lower type bounds

Upper Bound: Scala permette di attribuire un sottoinsieme di Any ad un tipo generico

utilizzando i bounds, in tal modo la variabile definita tramite il tipo generico potrà

accedere ad attributi e metodi specifici del sottoinsieme.

12

Supponiamo, ad esempio, di voler realizzare un metodo generico (tipizzato) che, definito

un sottotipo di Persona, ne stampi nome e cognome:

def printName[A] (persona: A) = println(persona.getNome())

Tale operazione non è consentita poiché il compilatore non trova il metodo getNome, in

quanto è un metodo di una Classe Persona e non di un qualunque tipo A. Possiamo allora

evitare l’errore utilizzando un Upper Buond: affermeremo che il tipo [A] può essere solo

un sottotipo di Persona, e non un qualunque tipo di oggetto.

def printName[A <: Persona] (persona: A) = println(persona.getNome())

In tal modo il compilatore riconoscerà che il generico A è una sottoclasse di Persona,

permettendoci di accedere ad attributi e metodi di Persona tramite un oggetto generico di

tipo [A <: Persona].

Lower Bound: I lower type bound vengono utilizzati per gestire la covarianza dei tipi di

Scala. Per descrivere il funzionamento dei Lower Bound prendiamo ad esempio la

classe standard “List[+A]”. Essendo tale classe covariante se volessimo definire, ad

esempio, una lista di Studente avremo implicitamente anche una lista di Persona.

L’oggetto List fornisce un operatore “:: (elem: A)”, questo operatore viene utilizzato per

creare una nuova lista, aggiungendo un elemento in testa ad una lista già esistente, la

nuova lista sarà dello stesso tipo della lista di partenza. Ad esempio:

trait Persona{

def mansione() : String

def saluta() = "Ciao"

}

class Studente extends Persona{

override def mansione() = "Studiare"

}

class StudenteLavoratore extends Studente{

override def mansione(): String = super.mansione() + " e Lavorare"

}

var lista: List[Studente] = List(new Studente, new Studente)

var lista2 = new StudenteLavoratore :: lista

L’oggetto lista è una lista di Studente, l’oggetto lista2 continuerà ad essere una lista di

Studente.

List definisce anche un altro operatore “:: [elem: B >: A] (elem: B)”, tale operatore può

aggiungere in testa ad una lista un oggetto diverso dal tipo di partenza [A]. Il compilatore

inferirà il super tipo comune più vicino ad A ed al parametro " elem: B " e lo userà come

valore di B; la nuova lista, quindi, sarà di tipo B.

Si noti che la dicitura “B>: A” specifica che l’oggetto B deve essere una superclasse di

A. Questo ci permette di aggiungere una Persona ad una lista di Studenti, rendendo tale

lista genericamente una lista di Persone:

var lista2 = new Persona :: lista

L’oggetto lista2 sarà una lista, più generica, di Persona.

13

3.2.3 Case classes

Le case classes, utili per modellare dati immutabili, sono un’abbreviazione delle classi

normali e del tutto simili ad esse, sebbene presentino determinate differenze chiave:

La parola chiave “case” suggerisce un’associazione con le espressioni “case” nel

pattern matching. Tali classi sono particolarmente adatte ad essere utilizzate in questo

contesto.

La definizione richiede le parole chiave “case class” seguita da un nome e da una lista

di parametri; a seguire un esempio:

case class Studente(nome: String, cognome : String)

val utente = Studente("Gianluca", "Vaccaro")

in tale esempio notiamo l’assenza della keyword new, in quanto le case class hanno un

metodo di default “apply” che si occupa della costruzione della classe e che viene

chiamato implicitamente dal compilatore. Il compilatore converte automaticamente i

parametri del costruttore in campi immutabili (val), a meno che non si usi la parola chiave

var. Ciò comporta che le liste di parametri dei nostri costruttori diventano più corte.

3.2.5 Pattern Matching

Il Pattern Matching di Scala è un costrutto molto simile allo switch di Java con la

differenza che, mentre con lo switch si possono valutare solo valori interi, col Pattern

Matching possiamo, non solo ispezionare ogni tipo di oggetto, ma anche “destrutturarlo”

e analizzarne i suoi singoli elementi.

Di seguito un esempio:

case class Studente(nome: String="", cognome: String="", matricola: String) extends Persona(nome,

cognome)

case class Insegnante(nome: String="", cognome: String="", materia: String) extends Persona(nome,

cognome)

case class Negoziante(nome: String ="", cognome: String="", partitaIVA: String) extends

Persona(nome, cognome)

val persone = List[Persona] (Studente ("1110"), Insegnante("Matematica"), Negoziante("p.iva"))

inspectPersone(persone)

def inspectPersone(persone : List[Persona]) : Unit = {

persone match {

case Studente(matricola) :: others => {

println(s"Studente, matricola = $matricola")

if (others.length > 0) inspectPersone(others) }

case Insegnante(materia) :: others => {

println(s"Insegnante, materia = $materia")

if (others.length > 0) inspectPersone(others) }

case Negoziante(partitaIVA) :: others => {

println(s"Negoziante, partitaIVA = $partitaIVA")

if (others.length > 0) inspectPersone(others) }

case _ => println("no")

}

In tale esempio analizziamo il funzionamento del codice:

14

Con l’uso di “::” si potranno concatenare più elementi diversi. Il costrutto match effettua

confronti tra strutture, nel nostro caso andremo a paragonare la lista in ingresso alla nostra

funzione (persone) con delle strutture note. La prima struttura con cui effettueremo il

confronto è costituita da una lista avente come primo elemento uno studente: “case

Studente(matricola) :: others”. In caso di match il compilatore Scala caricherà all’interno

degli argomenti di “Studente(matricola)” i parametri dello stesso e, all’interno di

“others”, tutti i restanti elementi della lista, che sono poi richiamati in maniera ricorsiva.

Notiamo inoltre che, a differenza dello switch, i singoli case non devono terminare con la

parola chiave break e che il caso di default è identificato dall’underscore.

3.2.6 Abstract types and Anonymous Class

Tratti e classi astratte possono avere membri di tipo astratto, il che significa che sarà

l’implementazione concreta a definire il tipo di dato; ad esempio:

abstract class SeqBuffer{

type U

type T <: Seq[U]

var element: T

def length = element.length

def add[U](elem: U)

}

Abbiamo definito un tipo astratto T per descrivere il tipo di “element” e il tipo astratto U

per porre un Upper-Bound al tipo T. Questa classe ci permette di memorizzare all’interno

del Buffer solo tipi sequenziali, affermando che T deve essere una sottoclasse di Seq[U].

La Funzione Parametrizzata add[U] viene utilizzata per aggiungere elementi al buffer.

Classi Astratte e Tratti contenenti tipi di dato astratti sono spesso utilizzate con istanze di

Classi Anonime. Vediamo, ad esempio, una funzione che crea a Runtime un’istanza ad

hoc di SeqBuffer:

def newSeqBuf[Element, Sequence <: Seq[Element]] (seqence: Sequence): SeqBuffer =

new SeqBuffer {

type U = Element

type T = Sequence

var element = seqence

override def add[U](elem: U) = {

element = (element :+ elem).asInstanceOf[T]

}

}

val buf = newSeqBuf[Int, List[Int]](List(1, 2))

buf.add(5)

buf.add(List(8, 9))

println("content = " + buf.element) Il risultato sarà: List (1, 2, 5, List (8, 9))

3.3 Classi Innestate

In Scala è possibile innestare classi all’interno di altre. Al contrario dei linguaggi simil-

java, in cui tali classi interne sono solo membri della classe di cui fanno parte, in Scala le

classi innestate sono vincolate all'oggetto esterno. Per illustrare il comportamento delle

classi innestate prendiamo ad esempio la classe standard “Graph” utilizzata per costruire

15

grafi. I Path-dependent types istruiscono il compilatore affinché impedisca, a tempo di

compilazione, la connessione tra nodi appartenenti a grafi diversi.

Riportiamo una parte dell’implementazione dell’oggetto Graph di Scala:

class Graph {

class Node {

var connectedNodes: List[Node] = Nil

def connectTo(node: Node) {

if (connectedNodes.find(node.equals).isEmpty) {

connectedNodes = node :: connectedNodes

}

}

}

var nodes: List[Node] = Nil

def newNode: Node = {

val res = new Node

nodes = res :: nodes

return res

}

}

Questa struttura rappresenta il grafo come lista di Nodi (nodes: List[Node). A sua volta

ogni nodo può collegarsi agli altri nodi del grafo mediante il metodo: def connectTo(node:

Node).

La classe Nodo è un Path-dependent types poiché è innestata nella classe Graph. Pertanto,

ogni Nodo della lista connectedNodes deve essere creato utilizzando il metodo newNode

invocato dalla stessa istanza di Graph.

val graph1: Graph = new Graph

val nodo1: graph1.Node = graph1.newNode

val nodo2: graph1.Node = graph1.newNode

nodo1.connectTo(nodo2)

Per chiarezza, abbiamo dichiarato esplicitamente il tipo di nodo1 e nodo2 come

graph1.Node, avremmo potuto evitarlo in quanto, chiamando il metodo graph1.newNode,

creiamo un’istanza di Nodo specifica di graph1. Scala non ci permette di mischiare i nodi

definiti in un grafo con quelli definiti in un altro, poiché i due nodi avrebbero tipi

differenti; ciò può essere constatato con il seguente esempio:

val graph2: Graph = new Graph

val nodo3: graph2.Node = graph2.newNode

nodo1.connectTo(nodo3) // Error! expected graph1.Node, actual is graph2.Node

mentre Java per nodi di diversi grafi avrebbe assegnato lo stesso tipo “Graph.Node”, in

Scala il tipo graph1.Node è diverso dal tipo graph2.Node. Il medesimo comportamento

di Java può essere tuttavia ugualmente ottenuto mediante la definizione Graph#Node. In

conclusione, possiamo affermare che ogni classe innestata dipende dall’oggetto in cui è

contenuta e non dalla sola classe.

3.4 Concorrenza in Scala

Rispetto alla gestione della concorrenza Scala dimostra maggiore efficienza rispetto a

C++ e Java. Negli anni, con la diffusione dei processori multi-core e dei sistemi

distribuiti, molti linguaggi di programmazione hanno messo a disposizione degli

16

sviluppatori strumenti sempre più raffinati per la gestione della concorrenza. Ad esempio

C++ e Java usano i concetti di regioni critiche, variabili lock, monitor e semafori. Questi

costrutti si basano sulla condivisione di una risorsa tra più processi o thread, alla quale

accedere in mutua esclusione. Questo metodo da un lato ha problemi di prestazioni, in

quanto l’inizializzazione e il passaggio di contesto fra thread sono operazioni dispendiose

per elaborazione e memoria, dall’altro è difficilmente estendibile ad ambienti distribuiti.

Scala, invece, adotta un meccanismo di scambio di messaggi su mailbox tra i vari thread

che, non condividendo alcuno stato in comune, non hanno più l’onere di dover accedere

alla risorsa in maniera sincronizzata. La gestione della concorrenza in Scala si basa sul

robusto modello di concorrenza Actors implementato in Erlang6: processi concorrenti che

comunicano inviandosi messaggi sia in modo sincrono che asincrono. Di seguito

elenchiamo brevemente i costrutti e le funzionalità che Scala ci mette a disposizione:

Actor: un attore è un’entità autonoma che opera in concorrenza agli altri attori del

sistema in modo del tutto asincrono. Ogni attore è definito tramite un nome univoco

all’interno del sistema e possiede un proprio comportamento. Ogni attore, quando è

inattivo, si trova nello stato di idle, stato in cui attende la ricezione di messaggi.

Quando un messaggio è pendente nel mailbox, l’attore accetta il messaggio ed esegue

una certa computazione in base a quanto specificato nel proprio comportamento. È

importante chiarire che ogni attore non condivide con gli altri attori del sistema il

proprio stato interno. Quindi, per effettuare una modifica o ottenere informazioni

relativamente a tale stato è necessario inviare un esplicito messaggio all’attore

interessato.

Per creare un attore si deve estendere la classe Actor della libreria scala.actors e

implementare il metodo act(). Una volta istanziato il nuovo attore dovrà essere

invocato il metodo start() per lanciare il nuovo flusso esecutivo che andrà ad eseguire

il codice scritto nel metodo act():

class Attore extends Actor {

def act() {

// (Comportamento Attore) TODO

}

}

val attore = new Attore

attore.start()

Invio messaggi: Sono disponibili tre modalità di invio messaggi al mailbox di un

attore:

o Invio Asincrono: l’attore mittente, a seguito dell’invio, non attende risposta da

parte del destinatario. Per inviare un messaggio asincrono ad un attore si deve

invocare su di esso il metodo “!” inserendo come argomento l’oggetto che si vuole

inviare:

attore! "Corpo Messaggio"

o Invio Sincrono: l’attore mittente, a seguito dell’invio, si blocca in attesa di risposta

da parte del destinatario. Per inviare un messaggio sincrono ad un attore si deve

6 Erlang è un linguaggio funzionale, nato negli anni ‘80, per gestire applicazioni non-stop, distribuite e stabili. Adotta il modello di

concorrenza per scambio di messaggi, questo approccio rende istantanea e trasparente la comunicazione tra processi, assimilando allo stesso modo sia le istanze di un’applicazione sulla stessa macchina sia quelle su macchine remote.

17

invocare su di esso il metodo “!?” inserendo come argomento l’oggetto che si

vuole inviare:

val risposta = attore!? "Corpo Messaggio"

o Invio Ibrido: L’attore mittente, a seguito dell’invio riceve subito un oggetto di tipo

Future[+A] che rappresenta un riferimento della risposta che potrebbe non essere

stata ancora processata. Grazie a questo meccanismo, se il mittente non ha

immediato bisogno della risposta, potrà continuare la sua esecuzione e controllare

in seguito, con il metodo isSet(), se la richiesta è stata processata e richiederne il

valore invocando il metodo bloccante value().

Ricezione Messaggi: ci sono due metodi in Scala per ricevere messaggi e si

distinguono, principalmente, per la gestione del thread sul quale stanno eseguendo:

1. con il metodo receive, quando il thread non ha più messaggi da processare viene

sospeso fino alla prossima ricezione, quindi verrà creato un thread per ogni attore

e, se un attore non riceve nulla, il relativo thread rimarrà sempre attivo senza

eseguire alcun task.

2. con il metodo react, quando il thread non ha più messaggi da processare viene

assegnato ad un altro attore, in tal modo non si ha più bisogno di creare tanti thread

quanti sono gli attori del nostro programma, un attore quindi non occupa alcun

thread a meno che non riceva qualcosa.

Entrambi i metodi accettano come parametro di ingresso una PartialFunction che

provvederà a gestire correttamente il messaggio entrante; viene utilizzata tale

funzione poiché questa ha la peculiarità di poter controllare, prima di eseguire la sua

routine (definita nel metodo apply(…)), se i dati in ingresso sono compatibili con i

propri (tramite il metodo isDefinedAt(…)).

Per definire in modo molto più semplice lo stesso comportamento è sufficiente usare

il pattern matching. Infatti, una sequenza di clausole “case” può essere vista come una

funzione parziale che ad ogni tipologia di messaggio in ingresso associa una routine

da eseguire:

class Attore extends Actor {

def act() {

receive/react {

case mex: String => println(s"String = $mex")

case mex: Int => println(s"Int = $mex")

}

}

}

In questo caso, il metodo isDefinedAt() viene implementato automaticamente e ritornerà

true solo per i messaggi presenti nel mailbox di tipo String e Int.

La differenza tra i due metodi emerge nel tipo di ritorno: mentre il metodo receive ritorna

l’oggetto che gli è stato inviato, il metodo react, per permettere al thread di essere

assegnato ad un altro attore, una volta espletato il suo comportamento, lancia

un’eccezione di tipo SuspendActorException. Tale eccezione viene utilizzata come

mezzo per interrompere l’esecuzione del thread e liberare la call stack affinché questo

possa essere riutilizzato da altri attori. Poiché react lancia sempre un’eccezione il tipo di

ritorno è Nothing.

18

Quando un messaggio non può essere gestito dalla funzione parziale, il metodo receive

rende nota la funzione isDefinedAt e sospende il thread su cui è in esecuzione, mentre il

metodo react mette a disposizione dei potenziali mittenti la funzione parziale per gestire

i messaggi. Se, invece, un messaggio può essere gestito, il metodo receive procede

direttamente all’esecuzione del codice necessario, mentre il metodo react crea un task da

inviare allo Scheduler che gestisce gli attori, poiché deve essere sicuro di poter lanciare

l’eccezione. Per impedire che l’attore termini l’esecuzione dopo aver servito una singola

richiesta si dovranno inserire i metodi receive e react all’interno di un ciclo ma, poiché il

metodo react lancia un’eccezione, questo non potrà essere inserito in un normale ciclo

while (poiché terminerebbe anche il ciclo a fronte dell’eccezione), per questo motivo

Scala introduce l’istruzione loop. Orbene, il nostro codice, utilizzando react, apparirà in

questo modo:

class Attore extends Actor {

def act() {

loop {

react {

case s: String => println(s);

}

}

}

}

Per rispondere ad una richiesta sincrona, sbloccando il mittente, si deve utilizzare lo stesso

canale usato per l’invio. Per fare questo, esiste il metodo reply() o l’oggetto sender che

rappresentano il canale di comunicazione tra i due attori.

Capitolo 4

Esempi di sviluppo

Vediamo ora due esempi di utilizzo del linguaggio Scala, nel primo vedremo

un’implementazione della soluzione al problema dei produttori-consumatori utilizzando

la concorrenza appena vista. Nel secondo implementeremo nel linguaggio Scala

l’algoritmo di ordinamento Heap Sort.

4.1 Produttori-Consumatori.

Vediamo come il processo di risoluzione della concorrenza in Scala permetta di risolvere

il classico problema Produttori-Consumatori.

Il problema descrive due processi, uno produttore ed uno consumatore, che condividono

un buffer comune, di dimensione fissata. Compito del produttore è generare dati e

depositarli nel buffer in continuo. Contemporaneamente, il consumatore utilizzerà i dati

prodotti, rimuovendoli di volta in volta dal buffer. Il problema è assicurare che il

produttore non elabori nuovi dati se il buffer è pieno, e che il consumatore non cerchi dati

se il buffer è vuoto. Tale questione pone la necessità di sincronizzare gli accessi tra

produttori e consumatori: un produttore non può proseguire nel caso in cui lo spazio sia

esaurito e un consumatore non può proseguire nel caso in cui non ci siano messaggi da

prelevare.

19

Per risolvere l’impasse Scala, invece di realizzare la mutua esclusione tra i processi,

realizza una struttura in cui un Attore (Magazzino) detiene il controllo del buffer e attori,

di tipo Produttori e Consumatori, inviano messaggi, rispettivamente, di inserimento e

prelievo dal buffer, quindi l’accesso al buffer sarà consentito solo all’Attore Magazzino.

In questo modo si potrà gestire il buffer circolare che conterrà i messaggi e coordinare

l’attività dei produttori e dei consumatori per evitare che non eseguano operazioni

sbagliate. Il codice d’esempio è riportato nell’appendice A.

4.2 Heap Sort

L’Heap Sort è un algoritmo di ordinamento sul posto, cioè utilizza una quantità di spazio

pari esattamente alla dimensione dell'input, basato sulla struttura dati Heap, la cui

efficienza asintotica è del tipo O(nlogn). Un Heap è una modalità di organizzazione dei

dati che ci permette di vedere un qualsiasi array A, di dimensione n, come un albero

binario completo7 che verifichi una data proprietà.

Sia S un insieme di elementi da ordinare di dimensione n. L'algoritmo Heap Sort

costruisce dapprima una Heap contenente tutti gli elementi di S, quindi estrae

ripetutamente dall’albero il più piccolo elemento finché la Heap risulti vuota. L’albero

avrà tanti nodi quanti sono gli elementi del vettore e la posizione di ognuno di essi sarà

identificata dall’indice di tali elementi nel vettore stesso. La radice dell’Heap è sempre

memorizzata nel primo elemento dell’array.

Per mappare ciascun elemento A[i] del vettore di partenza come i-esimo nodo dell’Heap,

si utilizzano le seguenti regole:

Il padre di ciascun nodo dell’Heap, di indice i, indicato come parent(i), è

rappresentato dall’elemento dell’array di partenza avente come indice

l’approssimazione per difetto di i/2:

𝑝𝑎𝑟𝑒𝑛𝑡(𝑖) = ⌊𝑖

2⌋

Il figlio sinistro di ciascun nodo dell’Heap, di indice i, indicato come left(i), è

rappresentato dall’elemento dell’array di partenza avente come indice 2i:

𝑙𝑒𝑓𝑡(𝑖) = 2𝑖

Il figlio destro di ciascun nodo dell’Heap, di indice i, indicato come right(i), è

rappresentato dall’elemento dell’array di partenza avente come indice 2i+1:

𝑟𝑖𝑔ℎ𝑡(𝑖) = 2𝑖 + 1

L’altezza h di un nodo è rappresentata dalla lunghezza, in termini di numero di archi,

del più lungo percorso semplice dal nodo ad una foglia; quindi l’altezza dell’albero

coincide con l’altezza della radice.

7 Un albero binario completo è un albero binario nel quale ogni livello, escluso eventualmente l’ultimo, è completamente pieno e tutte le foglie hanno la stessa profondità. Un albero completo di n nodi avrà,

quindi, altezza ℎ = ⌊𝑙𝑜𝑔2𝑛⌋ nodi; dualmente un albero di altezza h avrà numero di nodi 𝑛 = 2ℎ+1 − 1.

20

Heap del vettore generico A

Un Heap può essere di due tipi:

Min Heap: 𝐴[𝑖] ≥ 𝑝𝑎𝑟𝑒𝑛𝑡(𝑖) , ∀𝑖 > 1

Max Heap: 𝐴[𝑖] ≤ 𝑝𝑎𝑟𝑒𝑛𝑡(𝑖) , ∀𝑖 > 1

Heap Sort utilizza i Max Heap, quindi, il nodo radice dell’albero risulterà essere il

massimo valore presente nel vettore A. I nodi figli, partendo dal penultimo livello,

rispetteranno la proprietà dell’Heap (poiché alla prima invocazione i nodi figli saranno le

foglie e, alle successive, i figli del nodo in analisi saranno già stati ordinati secondo le

regole del Max Heap), ma ciò non è sempre vero per il padre. L’algoritmo di Heap Sort

fa uso di due procedure:

Max heapify: per assicurare il rispetto della proprietà fondamentale del Max Heap,

cioè che il valore di ogni nodo non sia inferiore a quello dei propri figli.

Build max heap: per la realizzare una struttura Heap a partire dall’array A

considerato.

Analizziamo lo pseudo-codice di Heap Sort per capire in che modo utilizza le due

procedure:

In primo luogo rimodella il vettore A per renderlo una struttura Max Heap.

Successivamente, ne estrae, una per una, tutte le foglie (che saranno gli elementi più

piccoli di A), le scambia col nodo radice dell’Heap e decrementa l’altezza dell’albero.

A questo punto, per poter estrarre la prossima foglia ed avere la certezza che questa sarà

nuovamente l’elemento più piccolo dell’albero, invoca la funzione Max-Heapify che

ripristinerà la struttura di Max Heap su ciò che resta dell’albero a seguito del decremento

di altezza.

Analizziamo di seguito le due procedure Max Heapify e Build Max Heap.

21

Max Heapify

Max Heapify si assicura che la condizione di Max Heap sia verificata per ogni nodo

dell'albero. L’algoritmo Max Heapify prende in ingresso il vettore A e l’indice i,

supponendo per ipotesi che i sottoalberi binari left(i) e right(i) rispettino la proprietà

dell’Heap, ma che il padre A[i] possa essere più piccolo dei figli, così violando la

proprietà del Max Heap. Ad ogni iterazione effettua un confronto tra il nodo i-esimo

considerato ed i nodi figli di sinistra e poi di destra: se il nodo i-esimo risulta essere

minore di uno dei due figli allora verrà scambiato col figlio maggiore e, in seguito, verrà

invocata ricorsivamente Max Heapify sul nodo che è stato appena scambiato per

verificare se il nuovo sottoalbero è Max Heap.

Complessità di Max Heapify

Il tempo di esecuzione è costituito da un contributo costante per individuare il massimo

tra l ed r e dall’esecuzione di Max Heapify sul problema di dimensione minore. Il

contributo maggiore sul tempo di esecuzione della procedura sarà dato quindi dalla

dimensione del sotto problema da risolvere. Detta n la dimensione del problema

originario, m la dimensione del sottoalbero con più elementi ed h l’altezza del nodo

oggetto, possiamo considerare due casi:

1. Ultimo livello pieno

𝑛 = ∑ 2𝑖ℎ

𝑖=0= 2ℎ+1 − 1

𝑚 =∑ 2𝑖ℎ−1

𝑖=0= 2ℎ − 1

𝑚

𝑛=2ℎ − 1

2ℎ+1 − 1 ℎ→∞→

1

2

Notiamo che il numero di nodi di un

sottoalbero m è limitato superiormente

da 𝑂(𝑛 2⁄ ), ne deduciamo che dato un

problema di ordine n, la chiamata

ricorsiva di Max Heapify per un nodo

figlio mi porterà a considerare un caso

massimo di dimensione 𝑛 2⁄

2. Ultimo livello pieno a metà

𝑛 = (2ℎ − 1) + (2ℎ−1 − 1) + 1= 3 ∗ 2ℎ−1 − 1

𝑚 =∑ 2𝑖ℎ−1

𝑖=0= 2ℎ − 1

𝑚

𝑛=

2ℎ − 1

3 ∗ 2ℎ−1 − 1 ℎ→∞→

2

3

Il caso peggiore si ha quando l’ultima

riga dell’albero è piena esattamente a

metà. In questo caso, il tempo di

22

esecuzione di MAX-HEAPIFY potrà

quindi essere descritto dalla ricorrenza: 𝑇(𝑛) ≤ 𝑇(2𝑛 3⁄ ) + Θ(1).

La soluzione di questa ricorrenza, per il caso due del teorema dell’esperto8 è:

𝑇(𝑛) = 𝑂(log 𝑛)

Dato che l’algoritmo in esame è ricorsivo, utilizzeremo il principio di induzione per

dimostrare la correttezza dello stesso.

Passo Base: se n=1 ho un solo nodo e quindi l ed r saranno maggiori di i, non verificando

le condizioni dei tre if. Banalmente, un heap con un solo elemento rispetta le proprietà

dell'heap.

Passo Induttivo: il sottoalbero che non effettua lo scambio con il nodo i non viene

considerato, quindi è verificato per ipotesi il Max Heap. Sul sottoalbero con il quale

effettuo lo scambio riapplico le proprietà dell'heap che, quindi, vengono rispettate.

Build Max Heap

La funzione Build Max Heap permette di costruire un Heap a partire da un vettore,

prendendo in input tale vettore e trasformandolo in un Max-Heap. L’algoritmo per la

costruzione dell’Heap sfrutta la proprietà per la quale partendo dal basso dell’albero, ogni

foglia, non avendo figli, sarà un Max Heap. Andando dal basso verso l’alto si potrà,

quindi, invocare la funzione Max Heapify (che suppone i figli l e r già max heap) sui vari

nodi. Di conseguenza, l’algoritmo Build dovrà modificare l’array di partenza partendo

dalla posizione dell’ultimo nodo non foglia, posizione che si può ottenere considerando:

𝑛°𝑓𝑜𝑔𝑙𝑖𝑒 = 𝑛 − (2ℎ − 1) + 2ℎ−1 − ⌈𝑛 − (2ℎ − 1)

2⌉ = 𝑛 + 1 − ⌈

𝑛 + 1

2⌉

𝑝𝑜𝑠𝑖𝑧𝑖𝑜𝑛𝑒 = 𝑛 − 𝑛°𝑓𝑜𝑔𝑙𝑖𝑒 = ⌈𝑛 + 1

2⌉ − 1 = ⌊

𝑛

2⌋

L’algoritmo, quindi, partendo dalla posizione dell’ultimo nodo non foglia 𝑖 =

⌊𝑑𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑒

2⌋, fino all’inizio dell’array, invocherà la funzione Max Heapify sugli i-esimi

elementi dell’array i quali, in caso non rispettino l’ordinamento imposto, scenderanno

all’interno dell’Heap (scambiandosi con gli elementi più grandi) fino a posizionarsi in

modo da rispettare la proprietà di Max Heap.

Correttezza di Build Max Heap

Per analizzare la correttezza della funzione utilizziamo la tecnica dell’invariante di ciclo:

Invariante: all’inizio di ogni iterazione del ciclo for, ogni nodo 𝑖 + 1, 𝑖 + 2, . . , 𝑛 è la

radice di un Max Heap.

8 Il teorema dell’esperto è un teorema inerente l'analisi degli algoritmi che fornisce una soluzione asintotica ad una famiglia di relazioni di ricorrenza, in particolare il caso due afferma che un

23

Inizializzazione: prima della prima iterazione di ciclo, 𝑖 =𝑛

2. Ogni nodo,

𝑛

2+ 1,

𝑛

2+ 2, . . , 𝑛

è una foglia, e quindi è la radice di un banale Max Heap.

Mantenimento: i nodi figli di i sono radici di max-heap (per ipotesi), quindi è verificata

la precondizione della procedura Max-Heapify, la quale renderà anche il nodo i-esimo,

radice di un max-heap; dunque, incrementando i si conserva l'invariante.

Terminazione: alla fine del ciclo si ha i = 0. Per l’invariante di ciclo, ogni nodo 1, 2, . . .,

n è la radice di un max-heap; in particolare, lo è il nodo 1, il che ci dice che l’intero vettore

è un Max Heap.

Complessità di Build Max Heap

L’algoritmo invoca Max Heapify un numero di volte proporzionale ad n quindi, dato che

Max Heapify ha una complessità di 𝑂(log 𝑛), si può affermare approssimativamente che

la complessità di Build Max Heap è 𝑂(𝑛 log 𝑛).

Si può, però, trovare un limite ancora più stretto tenendo conto che un Max Heap con n

elementi ha:

altezza ℎ = ⌊log 𝑛⌋

numero massimo di nodi con altezza h pari a ⌊𝑛

2ℎ+1⌋

Possiamo quindi asserire che:

𝑇(𝑛) = ∑ ⌈𝑛

2ℎ+1⌉𝑂(ℎ) = 𝑂(𝑛∑ ⌈

ℎ

2ℎ⌉) = 𝑂(2𝑛) = 𝑂(𝑛)

∞

ℎ=0

⌊log𝑛⌋

ℎ=0

Conclusioni Heap Sort

Per comodità riportiamo lo pseudo-codice di Heap Sort:

Complessità

L’algoritmo utilizza le due funzioni appena specificate: Build Max Heap e Max Heapify.

L’elemento più̀ grande del vettore viene memorizzato nella radice A[1] e

successivamente viene scambiato con A[n]. Decrementando la variabile heap-size, non

consideriamo più il nodo A[n] e costruiamo un Heap dal vettore A[1....n-1]. La procedura

Heap Sort impiega un tempo Ο(n log(n)) in tutti i casi, in quanto la chiamata di Build

Max Heap impiega O(n) e ciascuna delle n-1 delle chiamate di Max Heapify impiegano

un tempo Ο(log(n)).

Correttezza

La correttezza dell'Heap Sort viene dimostrata per induzione tramite l'invariante di ciclo:

24

Invariante: al passo i del ciclo for abbiamo che la parte di vettore A[i+1.......n] contiene

gli elementi più grandi del vettore in maniera già ordinata, mentre la restante parte è un

Max Heap che contiene gli elementi ancora da ordinare, e quindi il più grande ancora da

inserire si trova in prima posizione.

Inizializzazione: quando i = A.length, A[i+1, ..., n] è vuoto, mentre il vettore intero è di

sicuro un Max Heap in quanto è appena stato costruito con la funzione Build Max Heap.

Conservazione: per induzione, al passo i, la parte di vettore A[i+1, ..., n] contiene gli

elementi più grandi del vettore in maniera già ordinata, la parte restante, invece, è un Max

Heap; all’interno del ciclo for avviene lo scambio tra A[i] e A[1] ed in questo modo verrà

inserito l’elemento attualmente più grande in posizione A[i]. Diminuendo heap-size e

richiamando la Max Heapify sull’elemento A[1], faremo in modo che il vettore A[1....i-

1] diventi Max Heap e quando inizierà un nuovo ciclo con la diminuzione di i verrà

ristabilita l’invariante.

Conclusione: data la conservazione dell’invariante, avremo che, quando i diventerà 1, il

vettore A[2...n] sarà ordinato, mentre A[1] è l’elemento più grande ancora da inserire,

quindi il vettore è ordinato.

Il codice d’esempio è riportato nell’appendice B.

5 Conclusioni

Attualmente il linguaggio più popolare, nonché il preferito dalle industrie è Java; la sua

diffusione è dovuta alla sua versatilità, forza e capacità di gestire task complessi. Dal mio

primo approccio alla programmazione, avvenuto con il linguaggio C mi sono sempre

domandato se esistesse uno strumento migliore da utilizzare; con l’avanzare delle mie

conoscenze sui paradigmi di programmazione tale pensiero si insinuava sempre più in

me. Le prime risposte arrivarono con il paradigma ad oggetti, prima con C++ e poi con

Java. Per anni ho ritenuto che quest’ultimo rappresentasse il linguaggio per eccellenza;

operazioni che con il linguaggio C potevano apparire complesse, con Java apparivano

naturali, quanto la scrittura di un algoritmo nel linguaggio parlato. La grandezza di Java,

oltre che nell'estrema semplicità di astrazione del mondo reale, risiedeva nella JVM,

un’infrastruttura di mezzo, che, al prezzo di un lieve ritardo, permetteva l'esecuzione e la

distribuzione di applicazioni su macchine anche strutturalmente differenti. In occasione

della stesura di questa tesi lo studio di Scala ha fatto risorgere in me il suddetto

interrogativo. Sebbene la mia forma mentis fosse lontana dal concetto di programmazione

funzionale ho potuto apprezzare la grandezza di Scala per il modo in cui riesce a prendere

i lati positivi di diversi linguaggi di programmazione estendendone addirittura alcuni

concetti. Scala sfrutta la grandezza dell'ereditarietà delle classi di Java riuscendo anche

ad aggiungervi componenti interessanti quali i trait e le case class; eseguendo sulla JVM

sfrutta la portabilità e l'interoperabilità con altri linguaggi che eseguono su di essa; si

serve della potenza dei costrutti della programmazione funzionale, quali il pattern

matching ed altri, escludendo tuttavia la limitazione teorica dei soli valori immutabili; usa

la stabilità e la semplicità del modello della concorrenza ad attori di linguaggi come

ERLANG. L'unico aspetto che non ho apprezzato di Scala è la filosofia secondo la quale

le cose possono essere scritte anche in modi diversi, il che spesso rende il codice poco

comprensibile senza poi aggiungere nessuna nota positiva sostanziale. Orbene, si può dire

che Scala, sotto molti aspetti, rappresenta l'evoluzione naturale di Java riuscendo a farne

25

propri tutti i lati positivi e a fonderli con le strutture del paradigma funzionale. Scala

inoltre non è solo un linguaggio di ricerca, o di creazione di librerie come Spark, ma

attualmente viene utilizzato anche per lo sviluppo di software commerciali. Ad esempio,

diversi siti web ad alto profilo (LinkedIn, Twitter, FourSquare) utilizzano Scala. Anche i

programmatori di Java hanno compreso questo aspetto e, non a caso, dalla versione 8 in

poi di Java sono state introdotte importanti integrazioni con il paradigma funzionale, quali

la classe Function per la creazione di funzioni di alto livello passabili come parametro o

alcuni fondamenti del lambda calcolo o altro. Nei prossimi anni prevedo un’intensa

battaglia a colpi di upgrade tra Scala e Java (che parte molto avvantaggiato), solo il tempo

potrà svelare quale sarà il linguaggio del futuro.

Riferimenti

[1] D. Watt e W. Findlay, Programming Language Design Concept, Chichester, West Sussex:

Casa editrice John Wiley & Sons, 2006.

[2] J. Gibbons, «Datatype-generic programming,» in SSDGP'06 Proceedings of the 2006

international conference on Datatype-generic programming.

[3] B. Oliveira e J. Gibbons, «Scala for generic programmers: Comparing Haskell and Scala

support for generic programming,» Cambridge University Press, vol. 20, n. 3-4, 2010.

[4] B. Kahanwal, «Abstraction Level Taxonomy Of Programming Language Frameworks,»

International Journal of Programming Languages and Applications, vol. 3, n. 4, 2013.

[5] P. Chiusano e R. Bjarnason, Functional Programming in Scala, Shelter Island, NY: Casa

editrice Manning, 2015.

[6] M. Schinz e P. Haller, «A Scala Tutorial for Java Programmers,» 16 Gennaio 2014. [Online].

Available: https://www.scala-lang.org/docu/files/ScalaTutorial.pdf. [Consultato il giorno

2017].

[7] M. Odersky e T. Romf, «Unifyng Functioinal and Object-Oriented Programming with

Scala,» Communications of the ACM, vol. 57, n. 4, 2014.

[8] P. Pellegrino, Java 8 Guida Completa, Apogeo, 2014.

[9] M. Odersky, P. Altherr, V. Cremet, B. Emir, S. Maneth, S. Micheloud, N. Mihaylov, M.

Schinz, E. Stenman e M. Zenger, «An Overview of the Scala Programming Language,» École

Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, Technical Report IC/2004/64.

I

Appendice A

Codice dell’esempio dei Produttori Consumatori

import scala.actors.Actor

case class Set(messaggio: Any)

case class Get()

/* l'attore Magazzino ha il compito ricevere e servire le richieste di

deposito e prelievo inviate rispettivamente da Produttori e

Consumatori */

class Magazzino(val dimBuffer: Int) extends Actor{

private val buffer = new Array[Any](dimBuffer)

// indici per inserire in testa (case Set) e prelevare in coda (case

Get)

private var testa, coda = 0

/* lo spazio disponibile nel Magazzino è inizialmente pari alla

dimensione del buffer */

private var spazio = dimBuffer

def act() { // blocco di esecuzione dell'attore

/* ciclo infinito corrisondente ad un while(true) con la

differenza che

non si blocca in caso di eccezioni */

loop {

/* definisce in che modo l'attore Magazzino risponde alle

richieste

in entrata */

react {

case mex: Set if spazio>0 => {

spazio = spazio-1 // decrementa lo spazio in magazzino

// deposita il "prodotto" in testa al buffer

buffer(testa) = mex.messaggio

/* incrementa la testa (in maniera circolare) per permettere

il prossimo inserimento */

testa = (testa+1)%dimBuffer

/* invia un messaggio vuoto al produttore per informarlo

dell'avvenuto deposito e sbloccarlo dall'attesa */

sender ! ""

}

case Get if spazio<dimBuffer => {

spazio = spazio+1 // incrementa lo spazio in magazzino

sender ! buffer(coda) // invia il "prodotto" al Consumatore

/* incrementa la coda (in maniera circolare) per permettere

il prossimo prelievo */

coda = (coda+1)%dimBuffer

}

}

}

}

}

II

class Produttore(val magazzino: Magazzino) extends Actor{

def act() { // blocco di esecuzione dell'attore

while(true) {

Thread.sleep(10)

// invia una richiesta di inserimento al Magazzino

magazzino !? Set(Thread.currentThread().getId())

}

}

}

class Consumatore(val magazzino: Magazzino) extends Actor{

def act() { // blocco di esecuzione dell'attore

while(true) {

Thread.sleep(10)

// invia una richiesta di prelievo al Magazzino

println(magazzino !? Get)

}

}

}

object ProduttoriConsumatori extends App {

// crea un Magazzino con un buffer di dimensione 1

val magazzino = new Magazzino(1);

magazzino.start() // avvia l'Attore Magazzino

/* crea e avvia 10 Produttori e Consumatori che eseguiranno

richieste sul magazzino */

for (i <- 1 to 10) {

Thread.sleep(100)

(new Produttore(magazzino)).start()

(new Consumatore(magazzino)).start()

}

}

III

Appendice B

Codice esempio Heap Sort

object heapsort extends App{

/* le tre funzioni, partendo dall'indice di un nodo,

ritornano l'indice, rispettivamente, dei nodi sinistro,

destro e superiore*/

def left(i: Int) = (2*i) + 1

def right(i: Int) = left(i) + 1

def parent(i: Int) = Math.ceil((i - 1) / 2)

/* Funzione atta a scambiare la posizione di due elementi

in posizioni pos1 e pos2*/

def scambia(array: Array[Int], pos1: Int, pos2: Int): Unit = {

val temp = array(pos1)

array(pos1) = array(pos2)

array(pos2) = temp

}

def maxHeapify (a: Array[Int], i: Int, size: Int): Unit = {

val l = left(i)

val r = right(i)

var largest = i

/* confronta il valore del nodo padre a(largest) con quello

* dei figli a(l) e a(r), se il pedre è più piccolo dei figli

* non viene rispettata la condizione di Max Heap, quindi

* vengono scambiati e rieseguita la funzione*/

largest = if (l < size && a(l) > a(i)) {l} else {i}

largest = if (r < size && a(r) > a(largest)) {r} else {largest}

if (largest != i) {

scambia(a, i, largest)

maxHeapify(a, largest, size)

}

}

def buildMaxHeap (a: Array[Int]): Unit = {

val lastNode = Math.ceil(a.length / 2).asInstanceOf[Int]

for (i <- (0 to lastNode).reverse) {

maxHeapify(a, i, a.length)

}

}

def heapSort (a: Array[Int]) {

buildMaxHeap(a)

for (i <- (1 until a.length).reverse) {

scambia(a, 0, i)

maxHeapify(a, 0, i)

}

}

val array = Array (1,0,2,9,3,8,4,7,5,6)

heapSort(array)

println(array.toSeq)

}