Refactoring: improving modularization

 

Modularità

In generale, per modularità si intende la misura in cui un sistema può essere decomposto e ricombinato. La modularizzazione è applicata al fine di ridurre la complessità di un sistema decomponendolo in varie parti che presentano relazioni di indipendenza e di interdipendenza.

In questa sede parleremo di modularità riferendoci alla decomposizione in classi e non a "moduli" intesi come insiemi di classi.

La dipendenza tra classi diverse è identificata dall'accoppiamento tra di esse, mentre la qualità della decomposizione ha come buon indicatore la coesione della classe stessa.

Accoppiamento

L'accoppiamento misura la dipendenza tra due moduli, e idealmente deve essere minore possibile. Distinguiamo vari livelli di accoppiamento, che elenco dal migliore al peggiore:

• nessun accoppiamento
• per dati: lista di parametri passati costituiti da dati semplici, oppure un modulo usa un dato, semplice, prodotto da  un altro modulo
• per struttura: nell'interfaccia di un metodo è presente una struttura dati, o un modulo usa una struttura prodotta da un altro modulo
• per controllo: un modulo passa elementi di controllo (flag, ..) ad un altro modulo per condizionarne l'esecuzione
• esterno: due moduli comunicano in modo strutturato attraverso dati comuni
• comune: due moduli accedono a dati globali senza seguire un particolare protocollo
• per contenuto: un modulo usa e modifica dati "privati" di un altro modulo

Coesione

Esprime il grado di correlazione tra gli elementi dello stesso modulo. Ogni modulo dovrebbe avere una altra coesione, e questo è raggiungibile se il modulo ha un unico compito, e lo esegue bene. 

Distinguiamo vari livelli di coesione, che elenco dalla peggiore alla migliore:

• casuale: azioni o istruzioni completamente  scorrelate tra loro
• logica: azioni correlate, ossia che trattano lo stesso argomento (I/O, trattamento errori, check..)
• temporale: azioni che devono essere eseguite insieme (inizializzazioni, terminazioni..)
• procedurale: azioni che devono essere eseguiti in un determinato ordine
• comunicazionale: azioni che agiscono sugli stessi dati
• sequenziale: azioni ognuna della quale dipende dal risultato della precedente
• funzionale: modulo che svolge una sola attività e tutti gli elementi del modulo contribuiscono a realizzarla

Per approfondimenti su accoppiamento e coesione consiglio [1] e [2]

Avendo bene in mente questi obiettivi, ogni classe dovrebbe contenere un set di dati e le funzioni atte ad agire su quei dati, le classi dovrebbero essere di dimensioni non troppo grandi (sarebbe un segnale che stanno facendo troppe cose), non dovrebbero esserci dipendenze cicliche tra le classi e ogni classe non dovrebbe avere troppe dipendenze da altre classi. Denominati il fan-in ed il fan-out come le dipendenze in ingresso ed in uscita da una classe, questi dovrebbero in generale essere compresi in 5-9.

Il fan-out dovrebbe essere maggiore per i livelli logici più elevati, perché utilizzano servizi, mentre il fan in dovrebbe essere maggiore per quelli più bassi poiché sono quelli che forniscono servizi.

Vediamo i principali problemi che possono presentarsi con la modularizzazione.

Errata  decomposizione

Questo accade quando funzioni che logicamente avrebbero dovuto essere nella stessa classe, si trovano sparse in diversi punti, oppure ci sono classi con pochi metodi (perché gestiti da funzioni esterne alla classe), oppure ci sono metodi che agiscono su dati di classi esterne (altra faccia della stessa medaglia).

In questo caso abbiamo un cattivo accoppiamento ed una bassa coesione.

Soluzioni

• se ci sono metodi che agiscono prevalentemente su dati di altre classi, valutare se spostare tali metodi (o parte di essi) nelle classi opportune in modo da ripristinare una buona coesione e correggere l'accoppiamento
• Se ci sono classi "data" senza metodi o con pochi metodi, creare in esse la giusta interfaccia affinché le altre classi "client" possano agire sui dati di queste classi "data" senza accedere direttamente alle strutture
• se un metodo di una classe B che non accede ai dati della classe B è più usato in una classe A che nella classe B stessa, valutare se spostarlo nella classe A, sempre se l'operazione ha senso e migliora la coesione e l'accoppiamento.
• se un campo di B è più usato da una classe A che non nella classe B stessa (situazione direi abbastanza tragica), valutare se spostare tale campo nella classe A, , sempre se l'operazione ha senso e migliora la coesione e l'accoppiamento.
• rendere privati i dati su cui è possibile operare tramite metodi
• spostare campi non strettamente collegati alla funzione (astrazione) implementata dalla classe andrebbero spostati in altre classi

Insufficiente modularità

Questo accade quando una funzione non è stata completamente decomposta, e ci sarebbe bisogno di un'ulteriore decomposizione ai fini di ridurne la complessità e/o la dimensione. 

Sintomi possono essere:

•  un numero elevato di membri e metodi nell'interfaccia, e questo può essere il sintomo che questa classe "fa troppe cose". Questo caso può nascere anche se più metodi sono stati raggruppati perché agivano sugli stessi dati, ma non sempre è una buona idea, infatti si migliora l'accoppiamento ma può peggiorare la coesione, senza tenere conto del fatto che una classe dovrebbe seguire il principio di "single responsibility"
• un numero molto elevato di metodi nell'implementazione, e questo può essere il sintomo che a sua volta poteva essere decomposta in classi più semplici. 

Soluzioni

Se una classe ha troppi metodi o metodi molto complessi, una soluzione è decomporla ulteriormente incapsulando in un'altra classe parte delle sue funzionalità, sempre con  in mente l'obiettivo di non comprometterne la coesione. 

Se ci sono "isole" di metodi che si riferiscono a insiemi di dati diversi, separare tali isole in classi diverse.

Se ci sono gruppi di (molti) metodi che hanno scopi diversi, valutare se suddividere tali metodi in classi diverse con uno scopo più specifico, eventualmente esponenti un'interfaccia comune.

Se ci sono metodi molto complessi, valutare anche la creazione di classi private "helper" per semplificare la classe principale. 

Dipendenze cicliche

Succede quando tra due o più moduli si instaura una dipendenza circolare. Questo è un errore perché rende difficile comprendere la struttura complessiva, e anche il testing. Inoltre da un punto di vista logico risulta difficile capire chi dipende da chi.

Può accadere per vari motivi:

• perché ci sono metodi collocati in classi sbagliate
• ci sono metodi in cui viene passato "this" come parametro e il metodo chiamato agisce sui metodi del chiamante
• ci sono funzioni di callback non necessarie

Soluzioni

In questi casi è possibile, a seconda dei casi:

• introdurre nuove classi o interfacce 
• spostare il metodo che crea la dipendenza circolare nella classe che esso richiama
• unire due classi se in effetti implementano la stessa funzione

Moduli "hub"

Succede quando una classe ha un fan-in ed un fan-out elevato.

Abbiamo già visto che per i moduli di livello elevato ci aspettiamo un fan out maggiore mentre per quelli di livello più basso un maggiore fan in. 

Un simultaneo fan-in e fan-out elevato è senz'altro un sintomo che la classe sta facendo troppe cose, e, a meno che non si tratti  di una classe facente parte di un framework (come un mediator) questo non va bene, poiché diventa impossibile da cambiare senza che cambino i suoi utilizzatori, e viceversa diventa molto passibile di cambiamenti quando cambiano le classi da cui dipende.

Soluzioni

Certamente in questi casi si può cercare di suddividere la classe in classi diverse ed il più possibile indipendenti tra loro.

Se le dipendenze sono dovute a funzioni mal collocate, si può agire spostando i metodi dove sono chiamati, analogamente per l'accesso ai membri di altre classi (orrore)

Se il fan in è elevato, a volte si può ovviare utilizzando il pattern chain of responsibility in modo che ogni funzione deleghi ad una (sola) altra l'elaborazione qualora non la svolga lei stessa.

bibliografia

Refactoring for Software design smells  Girish Suryanarayana, Ganesh Samarthyam, Tushar Sharma

Refactoring: improving encapsulation

 

Incapsulamento

L'incapsulamento è la proprietà che hanno le classi di nascondere i dettagli di una certa funzionalità o servizio ed esporre un'interfaccia che consenta al client di poterla utilizzare ad un maggior livello di astrazione.

L'incapsulamento attua il principio dell'information-hiding, che è uno dei principali cardini della programmazione. Affinché questo sia ben progettato, occorre quindi che siano nascosti al client i dettagli implementativi, e che modifiche dell'implementazione non rendano necessarie variazioni dei client.

Esamineremo alcuni problemi che si possono presentare sull'incapsulamento e vedremo come risolverli.

Insufficiente incapsulamento

Avviene quando una classe espone dei dettagli implementativi esponendo uno o più membri, creando quindi un accoppiamento indesiderato che esporrà i client ad un impatto qualora l'implementazione cambi. 

Il peggiore dei casi è esporre variabili globali che possono dunque essere modificate da più client.

A volte può essere dovuto all'applicazione di soluzioni quick-fix, o a volte le informazioni sono rese pubbliche per poterle verificare in unit test, oppure semplicemente si è progettata male la classe pensandola in termini procedurali anziché OOP.

Soluzioni possibili

• evitare l'esposizione di variabili o membri di classe e al loro posto usare degli accessors di lettura o scrittura o dei metodi appositi, oppure esplicitarne la dipendenza in un costruttore
• utilizzare l'uso di parametri espliciti per le funzioni invece di configurazioni tramite variabili globali, considerare l'uso di uno strategy pattern o di un builder pattern.
• non esporre classi o strutture utilizzate nell'implementazione, anche qui potrebbe essere indicato un oggetto builder.

Incapsulamento parziale

Avviene quando una classe espone dei dettagli implementativi  attraverso la sua interfaccia pubblica.

Anche in questo caso è molto difficile in seguito cambiare l'implementazione della classe senza cambiare il codice dei client.

Quando si progetta una classe, si deve avere ben chiara la sua funzionalità (principio della single-responsibility) e definirne un'interfaccia che non sia sensibile ai cambiamenti dell'implementazione. Stabilire "cosa nascondere" (implementazione) e "cosa mostrare" (interfaccia) è probabilmente l'aspetto più importante in fase di progettazione e richiede esperienza e riflessione.

Soluzioni possibili

• non esporre metodi collegati all'implementazione bensì focalizzarsi su un'interfaccia il più possibile generica, seppur completa di tutte le funzionalità indispensabili.

• non fare proliferare il numero dei metodi di un'interfaccia, semmai considerare uno strategy pattern o la creazione di sottoclassi se si intendono fornire comportamenti simili ma diversi nella stessa classe. Questo serve a mantenere la classe semplice e ridurre l'accoppiamento degli utilizzatori. Infatti il solo fatto di sapere che una classe ha dieci metodi per eseguire un calcolo e sceglierne uno, rappresenta un accoppiamento: cosa dovrà fare quando ne sarà aggiunto l'undicesimo?

Incapsulamento violato

Si ha quando un client utilizza dei type check espliciti al fine di effettuare dei downcasting invece di  avvalersi in pieno delle interfacce.

Questo fa si che il client debba essere a conoscenza dei diversi tipi concreti che potrebbero implementare l'interfaccia, rendendo l'information hiding che era alla base della creazione dell'interfaccia del tutto violato.

Soluzioni possibili

• non usare type-checking nell'implementazione di metodi di oggetti che espongono un'interfaccia, ossia se un parametro è astratto, non tentare di cambiare il comportamento di un metodo in base al tipo specifico del parametro. L'uso del type checking di solito è indice di un'interfaccia mal progettata.
• ove necessario creare interfacce aggiuntive se si vuole verificare la presenza di determinate funzionalità in un oggetto, invece di verificarne il tipo esatto
• individuare i motivi di violazione dell'incapsulamento e valutare l'introduzione di un pattern facade

Gestione del technical debt

 Technical debt

Il peso del technical debt

Introduzione

Il mondo è in continua evoluzione e con esso cambiano i requisiti e le funzionalità che si richiedono ai software. La manutenzione del software occupa l'80-90% della vita di un software, a volte anche più. 

Le continue modifiche al software deteriorano la qualità del software e il suo technical debt. Questo nome, introdotto da Ward Cunningham, rappresenta il costo aggiuntivo delle manutenzioni successive dovuto a scelte non ottimali effettuate. 

Una manutenzione non attenta alla limitazione del technical debt fa si che i costi delle manutenzioni successive aumentino sempre più sino a quando diventa più economico scrivere un nuovo software che manutenere il vecchio, con costi enormi ove si tratti di software di grande complessità.

E' dunque essenziale prendere coscienza dei motivi per cui nasce il technical debt e sia riconoscere le varie forme in cui esso si presenta, al fine di poter sia evitarlo che correggerlo prima che sia troppo tardi.

Modelli di processo per la manutenzione

Distinguiamo principalmente due modalità di manutenzione: il quick fix e l'iterative enhancement.

Quick Fix

Sono effettuate modifiche al codice cercando di correggere esattamente l'errore che si presenta o implementando la funzionalità mancante col minore sforzo possibile in termini di tempo. Le conseguenze tipiche di questa modalità sono il degrado della struttura e della qualità del codice, e una documentazione che di solito non viene aggiornata o viene aggiornata a posteriori.

E' ammissibile se c'è un difetto serio nel software che deve essere corretto con estrema urgenza, perché i suoi effetti collaterali stanno creando seri problemi agli utenti. Ma anche in quei casi dovrebbe poi essere seguito da una revisione ed eventuale integrazione della modifica effettuata.

Studi condotti su molteplici progetti indicano in questo modello di processo la principale causa di  un rapido aumento del technical debt.

Iterative Enhancement

Si effettua una attenta analisi dei requisiti sulla modifica da implementare, si valutano le possibili soluzioni e si sceglie la migliore in base a dei criteri ben chiari, quali possono essere il maggiore o minore impatto sul sistema, l'impatto sulle prestazioni, l'aumento di complessità della struttura, la semplicità di interfaccia. E' più lento e costoso sul breve termine del quick fix, ma nel lungo termine ove utilizzato con costanza, fa si che i tempi di manutenzione non "esplodano" dopo un certo numero di manutenzioni. Prevede che la documentazione sia sempre aggiornata, insieme agli unit test e ai test di integrazione.

Cause del debito tecnico

Considerato che il debito tecnico si crea con la manutenzione, è ovvio che la qualità della manutenzione sia essenziale, quindi quali motivi possono concorrere a trascurare questo aspetto?

Senz'altro la pressione dei clienti per ricevere molte nuove funzioni o l'evolversi dell'ambiente circostante con le sue regole, e questo può indurre il manager a richiedere più modifiche nello stesso lotto di richiesta. D'altra parte i progettisti e gli sviluppatori, a loro volta pressati sui tempi di consegna, possono comprimere o saltare alcune fasi previste nel normale modello di sviluppo (ad esempio non analizzare l''impatto o ignorare i vari use cases, o non scrivere gli unit test...) per soddisfare le richieste in meno tempo, trascurando quindi gli effetti a lungo termine del debito tecnico.

Ma oltre all'ignoranza e alla non consapevolezza su cosa comporti il debito tecnico, la comunità degli sviluppatori ha individuato altre cause:

• date di consegna da rispettare, e questo effetto aumenta man mano che la data diviene più prossima, causando una maggiore disattenzione verso i paradigmi basilari per la progettazione e lo sviluppo
• mancanza di buoni progettisti, che quindi non seguano i principi fondamentali e le best practices
• non conoscenza delle corrette modalità di applicazione del refactoring e sulla qualità della struttura del software 

Tipologie di debito tecnico

• Codice: Parametri di qualità non rispettati (es. eccessiva complessità ciclomatica, eccessivo accoppiamento, mancanza di coesione...), stili di codice non omogeneo
• Progettazione: violazione dei principi della software engineering, quali l'information hiding, e scarsa attenzione alla successiva manutenibilità
• Test: mancanza di procedure di test automatico e copertura con i test dei vari use case
• Documentazione: insufficiente o non aggiornata documentazione sulle varie fasi di sviluppo

Conseguenze del debito tecnico

Ci sono diversi aspetti del software che vengono seriamente danneggiati dal debito tecnico:

• Affidabilità, la capacità di essere eseguito senza incorrere in bug
• Testabilità, il corredo di test e la possibilità di verificarne il funzionamento
• Riusabilità delle componenti, ossia la possibilità di non disseminare di oggetti simili il sistema, per una cattiva progettazione degli stessi
• Estendibilità, la facilità con cui ad un software si possono aggiungere nuove funzionalità senza doverlo modificare radicalmente
• Modificabilità, la facilità con cui è possibile cambiare una funzionalità senza doverlo modificare radicalmente, ossia con un impatto limitato sul codice esistente
• Leggibilità, la semplicità con cui è possibile, leggendo la documentazione ed il codice, comprenderlo e riuscire a manutenerlo.

Conclusioni

Se un software fosse rilasciato e poi non più manutenuto, non avrebbe senso preoccuparsi del debito tecnico. Ma per i software utilizzati per vari anni e di cui sono rilasciati, per vari motivi, degli aggiornamenti periodici, la gestione del debito tecnico assume un'importanza vitale ai fini della possibilità che il software continui ad esistere.

Nei prossimi articoli esamineremo alcuni "design smells" per imparare a riconoscere gli errori introdotti dal technical debt e vedremo come affrontarli e risolverli.

bibliografia

Refactoring for Software design smells  Girish Suryanarayana, Ganesh Samarthyam, Tushar Sharma

I pattern di concorrenza: accesso a risorse condivise

 

Introduzione

Definiremo alcuni concetti relativi all'accesso di risorse condivise, considereremo alcune situazioni critiche che possono presentarsi e analizzeremo le soluzioni esistenti in letteratura.

Processo

Definiamo in questa sede un Processo come una sequenza di istruzioni svolte da un calcolatore per eseguire un programma P. Un processore è un dispositivo in grado di eseguire tali azioni. Un processore può alternare nel tempo l'esecuzione di istruzioni di programmi diversi, viceversa l'esecuzione di un programma può essere sospesa e ripresa più volte, anche su processori diversi. Il processo può dunque essere complessivamente svolto in tempi diversi e su processori diversi.

Nota L'interruzione di un processo è un'operazione di solito in carico al sistema operativo, ma per i linguaggi interpretati o semi interpretati può anche essere gestito indirettamente dall'ambiente di run-time in cui avviene l'esecuzione.

In ogni istante t un processo può trovarsi essenzialmente in due stati: in esecuzione o in attesa. Quando è posto in attesa, il suo stato è preservato per poter consentire la ripresa della sua esecuzione. Si noti che il salvataggio dello stato ed il ripristino è un'operazione che in generale richiede delle risorse e del tempo.

Risorse

Si definiscono risorse tutti i dispositivi, hardware o software, fisiche o virtuali utilizzate da un processo. Ad esempio consideriamo un database come risorsa, così come (ad un livello più basso) un disco rigido,  ma anche una zona di memoria o un'istanza di una classe può essere considerata una risorsa, a seconda del livello logico in cui ci troviamo.

Distinguiamo risorse permanenti e risorse consumabili. Le risorse permanenti possono essere usate ripetutamente da più processi. Le risorse consumabili sono create da un processo e distrutte da un altro.

Possono presentarsi vari problemi quando più processi in esecuzione utilizzano una stessa risorsa:

• potrebbe essere necessario impedire che uno dei due inizi ad usarla prima che l'altro abbia finito, si pensi banalmente ad una stampante, in cui non è possibile stampare righe da un documento intervallate da righe di un altro documento
• ogni processo presume di conoscere lo stato della risorsa quando inizia ad operarvi, ma se più processi vi operano simultaneamente questo non è più vero

pertanto è necessario gestire queste situazioni.

Interazioni tra processi

Due processi A e B possono interagire tra loro in modo diretto, se il processo A produce una risorsa che il processo B consuma (in questo caso si dice che B dipende da A), o in modo indiretto, se competono nell'uso di una risorsa, ossia ne fanno uso entrambi.

Nel caso di interazione indiretta abbiamo un problema detto "della mutua esclusione", mentre nell'interazione diretta abbiamo una situazione di "produttore - consumatore"

Problema della mutua esclusione

Sia R una risorsa, ed i processi P1..Pn, si vuole garantire che in ogni istante vi sia solo un processo che accede ad R, e che ogni processo riesca ad ottenere l'accesso alla risorsa in un tempo finito.

Questo problema può essere risolto con l'uso di un arbitro che conserva un indicatore S sulla risorsa, che vale 1 se la risorsa è al momento in uso da parte di qualche processore, o 0 se nessun processore la sta utilizzando. L'arbitro può essere un dispositivo o un algoritmo. I processori chiedono all'arbitro l'uso della risorsa, e l'arbitro valuta se in quel momento la risorsa è libera, nel qual caso l'assegna al processore con priorità più elevata. Alla fine di ogni ciclo di esecuzione (ossia sin quando il processo non viene nuovamente sospeso per qualche motivo), la risorsa viene liberata.

Distinguiamo due casi quando un processo richiede una risorsa che però è già in uso:

• il processo continua ad impegnare il processore in attesa della risorsa (attesa attiva)
• il processo viene sospeso sin quando la risorsa non diviene disponibile (attesa passiva)

Il secondo caso è certamente da preferirsi poiché consente ad altri processi di essere eseguiti nel frattempo e rende più efficiente l'uso del processore.

Si noti che l'arbitro interagisce direttamente con i processori e non con i processi, che in questo caso accedono alla risorsa in modo trasparente come se ne detenessero l'uso esclusivo.

In questo caso la competizione sulla risorsa è "nascosta" ed implementata dall'arbitro, pertanto si ha una interazione indiretta tra i processi.

Questo caso può sembrare "accademico" e confinato alla progettazione di moduli hardware, ma lo è di meno quando l'arbitro è una classe progettata per gestire una risorsa.

Interazione diretta

In questo caso i processi, mediante opportune tecniche e convenzioni, ad esempio scambiandosi dei messaggi di sincronizzazione, risolvono i problemi di competizione senza ricorrere all'uso di un arbitro.

In questo caso si parla anche di cooperazione tra i processi, che dovranno contenere delle istruzioni apposite per prevenire i conflitti.

A livello di linguaggio macchina, il nucleo di questi meccanismi risiede in istruzioni di test and set, cmpxchg o xchg su cui viene applicato un lock a livello di bus per impedirne la concorrenza.

Produttore consumatore

Supponiamo che ci sia un processo A che produce delle risorse R ed un processo B che le consumi. Distinguiamo due primitive che vengono usate per gestire questa situazione, wait e cause.

Il processo che produce invocherà la primitiva cause( Ri) per ogni risorsa prodotta ed il processo che le consuma effettua una R = wait ( ) quando necessita della risorsa.

E' da notare che non è detto che ci sia un processo in attesa di consumare le risorse quando vengono prodotte, e non è neanche detto che quando un processo esegue la wait ( ) vi sia già una risorsa da consumare.

Se un processo esegue la wait ( ) quando non vi sono ancora risorse disponibili, viene posto in stato di attesa sin quando questa non è disponibile. Tale processo sarà ripreso quando il produttore eseguirà la primitiva cause.

Prima di analizzare come si risolvono i problemi di sincronizzazione in un linguaggio specifico, considereremo il C#, esaminiamo in genere quali strumenti esistono allo scopo:

• mutex sono oggetti in generale che consentono l'accesso esclusivo a risorse
• semaforo è un oggetto che gestisce l'accesso condiviso ad una risorsa, non necessariamente esclusivo, gestendo una coda di richieste da  parte di più processi

In C# esiste l'istruzione lock, che è il meccanismo più semplice per gestire una risorsa condivisa, e si usa così:

object x= new object(); //rappresenta simbolicamente la risorsa condivisa
lock (x) {
    // istruzioni che accedono alla risorsa associata ad x

    //    solo un processo alla volta può eseguire questo codice o altre 
    //    sezioni simili incorporate in un lock(x)
}

x in questo caso rappresenta la risorsa condivisa, e potrebbe essere una variabile di istanza o statica a secondo della "portata" che si intende dare al lock. Se più processi eseguono quello o altri blocchi di istruzioni che fanno riferimento alla stessa variabile x, la loro esecuzione sarà sospesa all'ingresso dell'istruzione lock, sin quando il processo che ne ha acquisito il lock non termina l'esecuzione di quel blocco.

L'istruzione lock è sintatticamente equivalente ad una coppia di istruzioni Monitor.enter(x) e Monitor.exit(x) che vedremo tra poco.

In C# ci sono varie classi per gestire la sincronizzazione tra più processi, di cui elenco di seguito i principali, con i principali metodi:

• Mutex consente di ottenere l'accesso esclusivo ad una risorsa. Si avvisa che esistono anche altri metodi di Mutex che consentono, tramite un nome, di accedere a mutex esterni all'applicazione, tramite meccanismi forniti dal sistema operativo ospitante.
• Mutex(bool initiallyOwned) costruisce il mutex, eventualmente auto-assegnandoselo se initiallyOwned è true
• bool waitOne() acquisice un blocco esclusivo sul mutex. L'esecuzione si blocca, anche indefinitamente, sin quando non è acquisito il blocco. Il metodo restituisce sempre true.
• bool waitOne(int milliseconds) simile al precedente, ma con un limite di tempo per l'acquisizione; se il lock non è acquisito entro il tempo prefissato, la funzione restituisce false
• void ReleaseMutex() rilascia il mutex
• Semaphore limita il numero di processi che accedono simultaneamente ad una risorsa
• Semaphore(int nInitial, int nMax) crea un semaforo per l'accesso ad una risorsa  a cui potranno accedere massimo nMax processi e inizialmente si assume che nInitial stiano già accedendo ad esso
• bool waitOne(), bool waitOne(int milliSeconds) come per il Mutex
• int Release() rilascia il semaforo e restituisce il numero di utilizzatori prima dell'istruzione Release
• int Release(nTime) rilascia il semaforo nTime volte, è equivalente a chiamare Release() nTime volte
• SemaphoreSlim simile a Semaphore ma non utilizza il kernel di sistema, quindi è più efficiente, ma funziona a patto che sia usato all'interno di uno stesso programma. Non presenta le varianti "per nome" di Semaphore e del Mutex
• 
  
• EventWaitHandle rappresenta un evento di sincronizzazione
• EventWaitHandle(bool initialState, EventResetMode tipoReset) crea un evento con uno stato iniziale (risorsa disponibile=true o non disponibile=false), ed un tipo di reset. Se il tipo reset è autoReset, l'evento diventa non disponibile non appena un processo ne ottiene l'accesso (con waitOne ad esempio). Se il tipo reset è manualReset, occorre chiamare i metodi Reset e Set per cambiarne lo stato.
• bool Reset() imposta l'evento come non disponibile (e bloccare i vari processi), restituisce true se riesce
• bool Set() imposta l'evento come disponibile (e sbloccare uno o più processi)
• bool waitOne(), bool waitOne(int milliSeconds) come per il Mutex
• bool SignalAndWait(WaitHandle toSignal, WaitHandle toWait) rilascia il lock su un evento (toSignal) e si mette in attesa di un altro (toWait), sin quando non viene rilasciato. 
• Monitor garantisce l'accesso ad una risorsa condivisa, ed è simile per certi versi all'istruzione lock, ma consente di riferirsi anche a lock di sistema su oggetti esterni al programma
• static void Enter(object o) rimane in attesa della risorsa o, sin quando non diviene disponibile
• static void Exit(object o)  rilascia la risorsa collegata
• static void Wait(object o) rilascia la risorsa e si mette in attesa della risorsa stessa (che avviene tramite una Pulse)
• static void Pulse(object O) rilascia nuovamente la risorsa al processo che l'aveva rilasciata con Wait. 

I metodi Wait e Pulse della classe Monitor servono per implementare comportamenti cooperativi come quello del produttore-consumatore.

Polling vs Event Driven  I metodi considerati si intendono essere tutti "event driven" ossia il thread che li esegue  rimane bloccato e in attesa "passiva", ossia non impegna il processore,  sin quando il lock non viene acquisito. Questo meccanismo si contrappone al meccanismo di "polling" in cui il processo interroga, in maniera attiva, eventualmente ad intervalli di tempo, lo stato di una risorsa, sin quando questa non divenga disponibile.

Considereremo ora alcuni problemi classici che ricorrono nell'ambito dell'accesso concorrente a risorse condivise e ne schematizzeremo una soluzione.

C# Produttore Consumatore- semaphore

Vediamo un esempio utilizzando l'oggetto semaphore

public class Producer {
    static List<T>  data = new List<T>();
    static object queue= new Semaphore(initialCount:1, maximumCount:10);
    void produce() {
        //qualche elaborazione
        lock(data){
            data.Add(risultato);
        }
        queue.Release();
    }

    void consume() {
        queue.WaitOne();
        object dataToProcess;
        lock(data){
            dataToProcess = data[0];
            data.RemoveAt(0);
        }
        //elaborazione di dataToProcess 
        ...
    }

}

In questo esempio produce e consume potranno essere usati in thread diversi, ad esempio ci potrebbe essere un thread sempre attivo che utilizza tutti i dati prodotti:

Task.Run ( () => { while(true) consume(); } );

mentre il metodo produce potrebbe essere chiamato in dipendenza di qualche altro evento.

E' importante l'istruzione lock in questo caso per evitare la concorrenza nell'accedere alla lista dataToProcess. Avendo fatto in modo da avere una Release per ogni elemento prodotto possiamo essere certi che il thread che esegue la consume, quando supera GetOne() troverà almeno un elemento nella coda.

C# Produttore Consumatore - senza semaphore

Senza l'oggetto semaphore avremmo dovuto effettuare un polling per assicurarci della disponibilità dei dati da elaborare, usando la sola istruzione lock, ad esempio:

 void consume() {
        object dataToProcess=null;
        lock(data){

            if (data.Count>0){

            dataToProcess = data[0];
            data.RemoveAt(0);
        }

        if (dataToProcess!=null) {
            //elaborazione di dataToProcess 

        }
        ...
    }

ed in questo caso sarebbe stato necessario un polling

Task.Run ( () => { while(true) {    
    consume(); 
    await Task.Delay(5000);
} );

I teoremi di incompletezza di Gödel

Kurt Gödel

I teoremi di incompletezza

Introduzione

In questa nota saranno descritti i due teoremi di incompletezza di Gödel

Innanzitutto introduciamo alcuni concetti di base, senza dei quali sarebbe impossibile enunciare e spiegare i due teoremi.

Logica matematica

La logica matematica è la scienza che si occupa di studiare il modo di codificare i calcoli e le dimostrazioni  effettuate nell'ambito di una logica formale

Ma cos'è una logica formale? è un insieme di

• un alfabeto utilizzato
• una grammatica che specifica quali sequenze sono costituiscono "formule" del sistema
• un insieme di "assiomi", ossia, intuitivamente, "formule" che nel sistema si assumono vere
• un insieme di regole di inferenza, ognuna delle quali associa a N formule del sistema (premesse) ad una nuova formula (conseguenza)

In  un  sistema formale si definisce l'insieme dei teoremi come l'insieme degli assiomi unito a tutte le formule che si possono ottenere dall'applicazione delle regole di inferenze agli assiomi stessi e alle altre formule ottenute, ricorsivamente.

 

Logica proposizionale

E' un linguaggio formale che consente di esprimere proposizioni booleane elementari o composte, basato sui connettivi logici (and, or, not, implica, se e solo se) ed un  insieme di simboli.

Possiamo quindi dire che è una logica formale avente, per alfabeto utilizzato: le lettere dell'alfabeto, unito ai connettori logici ¬ (NOT),  (AND),  (OR), → (implicazione), ↔ (doppia implicazione), e le parentesi tonde, usate per evitare ambiguità sull'applicazione dei connettori.
Per insieme regole di inferenza abbiamo:

1. una proposizione è una formula ben formata (fbf)
2. se A è una fbf allora anche ￢A è una fbf
3. se A e B sono fbf allora anche (A ⋁ B) , (A⋀B), (A↔️B), (A➡️B) sono fbf
4. tutto il resto non è una fbf

Alle fbf della logica proposizionale è possibile associare una semantica mediante una funzione di valutazione.

Si definisce funzione di valutazione una funzione che va da L delle fbf  nell'insieme (vero, falso)

v: L ➡️ { vero, falso }

tale che:

v( ￢ x ) =V   se v(x) = F

v( ￢ x ) =F   se v(x) = V

v ( x ⋀ y ) = V se e solo se v(x) = V e v(Y)=V

v ( x ⋁ y ) = V se e solo se v(x) = V oppure  v(Y)=V

v ( x ➡️ y ) = V se e solo se v(x) = F oppure  v(Y)=V

v ( x ↔️ y ) = V se e solo se v(x) = v(Y)

che attribuiscono ai connettori logici il significato consueto.

Per attribuire il valore ad una fbf in base alla funzione di valutazione, si attribuisce alle proposizioni elementari un valore di vero/falso e poi a partire da quelle si calcolano, risalendo le parentesi a partire dalle più interne, tutte le altre.

Un limite della logica proposizionale è che se si vuole esprimere un concetto di (ogni A(i) è vero per i che va da 1 a n) lo si può fare solo esprimendo

A1 ⋀ A2 ⋀ A3 ⋀ .... An

ma se vogliamo esprimere lo stesso concetto per un numero imprecisato o infinito di termini non possiamo farlo, in sostanza mancano i "quantificatori", inoltre non abbiamo nella logica proposizionale la possibilità di riferirci a predicati o funzioni.

Linguaggio del primo ordine

Un linguaggio del primo ordine è una logica formale in cui l'alfabeto è composto da:

• simboli per variabili: x1, x2,..
• simboli per costanti: a1, a2,..
• simboli per predicati o relazioni, a ciascuno dei quali è associato il suo numero di argomenti: P¹,Q¹,P²,Q²,...
• simboli per funzioni, a ciascuna delle quali è associato il suo numero di argomenti:  f¹,g¹,f²,g²,...
• simboli ausiliari; parentesi tonde e virgola
• simboli per connettivi logici (come per la logica proposizionale)
• simboli per quantificatori: ∀ (quantificatore universale) e  ∃ (quantificatore esistenziale)

per le regole di inferenza si rimanda a wikipedia, "linguaggi del primo ordine", ma in sostanza sono le regole comuni con cui scriviamo in matematica le formule, tuttavia è bene osservare che:

• costanti e variabili si riferiscono ad un "universo del discorso" U
• le funzioni f, g,.. hanno per dominio Uⁿ e per codominio Uⁿ
• i predicati o relazioni sono sottoinsiemi di Uⁿ
• i quantificatori si riferiscono ad elementi di U

In sostanza con un linguaggio del primo ordine possiamo esprimere predicati su U, relazioni di implicazione di predicati su U. In base all'ultimo vincolo, non possiamo utilizzare i quantificatori su sottoinsiemi di U (variabili predicative). Si dimostra che una teoria del primo ordine è sufficiente a "contenere" l'aritmetica e la teoria degli insiemi.

Un esempio di linguaggio del primo ordine è l'aritmetica di peano

Linguaggi del secondo ordine

Se ammettiamo la possibilità di menzionare, nel linguaggio, anche variabili e costanti che rappresentino funzioni e predicati, otteniamo un linguaggio del secondo ordine. In un linguaggio del secondo ordine posso quindi esprimere concetti di esistenza o di universalità sui predicati oltre che sugli elementi di  U.

Per fare un esempio, si può esprimere che

∀R∀x(R(x) ∨ ¬R(x))

dove R è un predicato generico ed x è un elemento di U. Questa espressione non è ammessa in un linguaggio del primo ordine, poiché in tale linguaggio questo non è ammesso.

Consideriamo il principio del buon ordinamento dei numeri naturali, secondo il quale ogni sottoinsieme non vuoto dell'insieme dei numeri naturali ammette un minimo. Per esprimere questo principio occorre avere un quantificatore esistenziale sugli insiemi, e questo è ammesso in un linguaggio del secondo ordine, ma non del primo.

Se consideriamo il principio di induzione, che afferma che per una generica proprietà se P(0) è vera e se P(n) => P(n+1) allora P è vera per tutto N, è necessario utilizzare un quantificatore universale sui predicati, è questo è possibile solo in una teoria del secondo ordine.

Nel linguaggio di secondo ordine si possono esprimere e generalizzare relazioni  (proprietà) su U ma non relazioni tra relazioni, ossia le relazioni hanno sempre per dominio U e non l'insieme delle relazioni stesse. Questo richiederebbe un linguaggio di ordine superiore.

Tra i predicati è possibile esprimere delle relazioni logiche con connettori  propri del linguaggio del secondo ordine, e sono simili a quelli del primo ordine, ma si indicano solitamente con termini diversi per non generare confusione, e sono:

• not per il not di un predicato
• vel per l'or logico
• et per l'and logico
• seq per l'implicazione logica
• eeq per la doppia implicazione
• om per il quantificatore universale
• ex per il quantificatore esistenziale

Teoria, Metateoria

Si può considerare, in un linguaggio di ordine superiore al primo, "teoria" il sottoinsieme relativo alla logica proposizionale, e metateoria le proposizioni che si riferiscono ai predicati stessi. 

Intuitivamente, per "parlare" della teoria U abbiamo bisogno di una metateoria M, poiché U non contiene in sé i nomi e le proprie regole di inferenza intese in senso astratto.

Per parlare di come descriviamo la teoria, abbiamo bisogno di una meta-metateoria  e via dicendo.

Completezza di una teoria

In una logica del primo ordine tutto quel che è vero è dimostrabile, e questa proprietà si definisce di completezza. In una logica del secondo ordine o superiore, si acquista in espressività ma si perde la proprietà di completezza.

Detto più formalmente, una teoria è completa se per una qualsiasi formula ben formata φ (fbf) è possibile dimostrare formalmente φ se  φ è vera o dimostrare formalmente  ￢φ se φ è falsa.

Si può alternativamente dire che una una teoria è completa se non esistono formule indecidibili, ossia di cui non è possibile fornire una dimostrazione od una confutazione.

Coerenza di una teoria

Una teoria si dice coerente se non esiste alcuna formula ben formata φ (fbf)  di cui è possibile dimostrare formalmente sia  φ che   ￢φ.

La coerenza è un concetto importante poiché si può dimostrare che in una teoria incoerente si può dimostrare qualsiasi cosa, dunque perde di significato.

w-Coerenza di una teoria

Una teoria si dice w-coerente se non esiste nessuna formula ben formata φ tale che si possa dimostrare al contempo: ∀xφ(x)   e   ∃x¬φ(x).  

La w-coerenza è un concetto più forte della semplice coerenza.

Primo teorema di incompletezza di Goedel

In una teoria T sufficientemente espressiva da contenere l'aritmetica e coerente, esiste almeno una formula φ  che non può essere né dimostrata né confutata.

Dimostrazione 

La dimostrazione si basa sulla possibilità di definire una formula logica che neghi la propria dimostrabilità. A tal fine si codifica una formula "autoreferenziale", ossia che parla di se stessa.

Si associa ad ogni simbolo dell'alfabeto della teoria un numero naturale. Quindi ad una formula, che è data da un insieme di simboli, possiamo associare un "numero di goedel", pari a

p₁^s1 p₂^s2....p_n^sn 

ove p₁,..p_n sono i primi n numeri primi , e s1..sn sono i numeri associati ai simboli della formula considerata.

In sostanza abbiamo trasformato una generica formula della teoria in un numero naturale.

Chiamiamo G(φ) il Godeliano della formula ben formata φ.

Visto che per ipotesi T è abbastanza espressiva da contenere l'aritmetica, può trattare le formule al pari dei numeri stessi.

Gli assiomi di T devono essere almeno sufficienti a dimostrare alcuni enunciati fondamentali:

i) ogni numero naturale ha un numero di Goedel (che si ottiene ottenendo reiteratamente la funzione successore all'elemento 0)

ii) dato un qualsiasi numero di Goedel di una formula φ(x), con variabile libera x ed un qualsiasi numero naturale m, vi è un numero di Goedel associato alla formula φ(G(m)) ottenuto sostituendo le occorrenze di x in φ(x) con il numero di Goedel associato ad m.

Dette D1,..Dn le regole di deduzione della teoria, supponiamo che D1 consenta di passare dalle formule 1 e a2 di T ad una nuova formula a3, si avrà che il numero di Goedel della sequenza a1,a2, che chiamiamo n, ed il numero m associato alla formula a3, saranno in relazione R1 tra loro, ossia (n,m) ∈ R1, sarà pertanto meccanicamente verificare se una dimostrazione è corretta, verificando i vari passaggi sei i corrispondenti numeri naturali sono in relazione tra loro.

Definiamo H l'insieme dei numeri di Goedel di tutti gli enunciati dimostrabili. 

Per quanto detto H è chiuso relativamente alle relazioni binarie R1..Rn associate alle regole di deduzione D1..Dn, ossia se n è nell'insieme H e (n,m) è elemento di R(i) allora anche m appartiene ad H, ossia è dimostrabile.

Attraverso una serie di passi, Goedel costruisce un predicato metamatematico 

    Dim(y,x) 

che rappresenta la relazione  "y è il godeliano di una dimostrazione della formula di godeliano x"

ed una formula    Teor(x) della forma ∃y Dim(y,x)

si noti che Teor è una formula come tutte le altre

In sostanza Teor(x) è vera per tutti gli x goedeliani di qualche teorema.

Si possono dimostrare tre proprietà di Teor, ossia

1) se φ è dimostrabile allora  Teor(G(φ) è vera

2) se Teor( G(φ ⇒  θ) ) allora  Teor ( G(φ)  ) ⇒ Teor ( G ( θ ) ) 

3) se Teor( G(φ ) ) allora Teor ( G(  Teor ( G(φ)  ) )  )

Si considera la funzione sost(x, y) dove y è il godeliano di una formula con variabile libera  ed x un numero associa il risultato della sostituzione nella formula y di x ovunque appare la variabile libera.

sost aritmetizza la sostituzione di un numerale al posto di una variabile libera in una formula.

Si considera la funzione not(x) che al godeliano di una formula x associa il godeliano della negazione di quella formula.

Si considera la composizione di sost e not come 

sostnot(x)  = sost ( x, not(x) )

che ad una formula che ha una variabile libera, il cui godeliano è  x, fornisce il godeliano della formula che si ottiene sostituendo nella variabile libera il godeliano di x nella negazione della formula il cui godeliano è x. 

Ossia sostnot(x) nega la formula il cui godeliano è x, e sostituisce alla variabile libera in essa presente il godeliano di x stesso.

Queste funzioni sono rappresentabili numericamente secondo lo schema fornito da Goedel.

Fatte tali premesse, consideriamo il numero n godeliano della formula 

    Teor(sostnot(x))  (2)

Questa formula vuol dire data una formula di godeliano x avente una variabile libera, "sostnot(x) è dimostrabile"

Se sostituiamo il numerale di n alla variabile x nella negazione di questa formula otteniamo

 ￢Teor(sostnot(n))  (3)

il godeliano di questa formula, per le premesse fatte, è proprio sostnot(n)

Infatti sostituendo si ha:

sostnot(n) =  (dobbiamo negare la formula il cui godeliano è n (ossia Teor(sostnot(x)) e sostituire nella sua variabile libera il numerale n) =  G(￢Teor(sostnot(n)) )

Questa formula concettualmente vuol dire "io non sono dimostrabile" infatti Teor(x) vuol dire che esiste una dimostrazione y di x quindi ￢Teor vuol dire "non esiste una dimostrazione", di sostnot(n).

Vediamo cosa succede allora se per esempio (3) ￢Teor(sostnot(n)) sia dimostrabile e sia m il godeliano della dimostrazione.

Allora  sarebbe dimostrabile Dim(m, sostnot(n)),

pertanto ∃y Dim(y, sostnot(n))

quindi sarebbe dimostrabile Teor(sostnot(n)), che è la negazione della (3), quindi avremmo un'incoerenza.

Supponiamo invece che (2) Teor(sostnot(n)) sia dimostrabile. 

Se lo fosse esisterebbe m tale che Dim(m, sostnot(n))

Avendo già dimostrato che (3) non è dimostrabile allora non esiste y tale  Dim(y, sostnot(n))

quindi neanche m è tale che Dim(m, sostnot(n)), ossia si avrebbe ￢Dim(m, sostnot(n))

che contraddice l'assunto.

        

Secondo teorema di incompletezza di Goedel

In una teoria T sufficientemente espressiva da contenere l'aritmetica , non è possibile provare la coerenza di T all'interno di T.

Considerazioni

Il primo teorema di Goedel stabilisce che in una teoria sufficientemente espressiva, ci sono sempre teoremi che non possono essere dimostrati. Si potrebbe aggiungere degli assiomi per renderli veri, ma si otterrebbe una nuova teoria con gli stessi limiti della precedente, creando spazio per nuovi teoremi indimostrabili e cosi via.

La mia perplessità sulla dimostrazione del primo teorema non è di tipo prettamente matematico, ma sull'interpretazione del risultato.

La dimostrazione consiste principalmente nel costruire una formula, ossia Teor(sostnot(n)) autoreferenziale, che afferma di non essere dimostrabile.

Tuttavia nel farlo assimila una dimostrazione con la sua rappresentazione "tipografica" ben precisa.

Una prima perplessità sta proprio in questo, che potrebbe apparire un limite, tuttavia anche ammettendo che ci siano altri teoremi, tipograficamente diversi, attestanti lo stesso concetto, potrebbero essere usati in una catena di dimostrazioni per ottenere il teorema "indimostrabile", che diverrebbe pertanto "dimostrabile". Pertanto la scelta "tipografica" della dimostrazione, ossia i caratteri usati o l'ordine o persino una modalità di dimostrazione diversa non serve ad aggirare il vincolo dato dalla formula Teor.

bibliografia

http://www.recensionifilosofiche.info/2008/02/lolli-gabriele-sotto-il-segno-di-godel.html

https://docplayer.it/2837590-Il-primo-teorema-di-incompletezza-di-godel.html

https://www.treccani.it/enciclopedia/la-seconda-rivoluzione-scientifica-matematica-e-logica-i-teoremi-di-incompletezza-di-godel_%28Storia-della-Scienza%29/

http://fc.lazio.cgil.it/FOV1-0004C55E/S0417867B.66/Francesco%20Berto%20-%20Tutti%20pazzi%20per%20G%C3%B6del!.pdf

https://plato.stanford.edu/entries/goedel/#FirIncThe

https://it.wikibooks.org/wiki/Logica_matematica/Incompletezza/Teoremi_di_incompletezza_di_G%C3%B6del