10
Per la realizzazione dell’implementazione è stato scelto il linguaggio JAVA,
perché perfettamente in linea con il requisito di portabilità sopra descritto ed
inoltre stesso linguaggio utilizzato per la realizzazione di SMF. Lo sviluppo
dell’interfaccia ha anche tenuto conto delle tematiche riguardanti lo studio, la
pianificazione e la progettazione di interfacce grafiche proposte da IBM in [13].
Nel capitolo 1 viene fornita una panoramica riguardo ai sistemi di calcolo
simbolico in generale, vengono descritte le principali caratteristiche e
problematiche legate alla creazione di una interfaccia verso tali sistemi e viene
quindi analizzata nel dettaglio la struttura del sistema di calcolo CoCoA.
Il capitolo 2 introduce le principali caratteristiche del linguaggio Java, scelto
per lo sviluppo effettivo dell’interfaccia; particolare rilievo viene dato alla
tecnologia Swing di Java, strumento con cui di fatto vengono create le componenti
grafiche dell’interfaccia, ed alle modalità che Java offre per la gestione degli
eventi legati a tali componenti.
Nel capitolo 3 viene descritto in dettaglio il sistema SMF (Session
Management Framework) con particolare attenzione ai concetti di sessione e di
query SMF, che sono alla base del contributo che SMF offre all’intera
applicazione.
Il capitolo 4 analizza dettagliatamente il lavoro svolto per la realizzazione
dell’intera applicazione (chiamata jCoCoA) a partire dalla soluzione ai problemi
scaturiti dai requisiti, analizzando le problematiche di interazione tra ciò che si
sarebbe implementato e ciò che era presente nello scenario. Viene
contemporaneamente e di pari passo fornita nello stesso capitolo una sorta di
“manuale utente” dell’applicazione realizzata, per la quale viene dato anche uno
sguardo più da vicino ai punti chiave del codice JAVA.
Nel capitolo 5 vengono infine analizzati i risultati ottenuti in rapporto alle
aspettative ed ai requisiti iniziali, valutandone nel contempo gli attuali limiti e
fornendo per quest’ultimi alcune possibili soluzioni in termini di idee e
suggerimenti per futuri sviluppi.
11
1
Sistemi di calcolo
1.1 Introduzione ai sistemi di calcolo simbolico
Oggigiorno il calcolo simbolico è una parte della scienza in rapido sviluppo
che si colloca a metà strada tra la matematica e l’informatica.
Dal punto di vista informatico lo sviluppo di nuove applicazioni e
metodologie computazionali, assieme all’aumento della tecnologia ed al ribasso
dei costi nel settore, hanno permesso negli ultimi anni la diffusione di tecniche di
calcolo che in passato erano considerate unicamente dal punto di vista teorico.
Risulta pertanto possibile al giorno d’oggi utilizzare esempi di calcolo che,
per il loro elevato livello di complessità, sarebbero molto lontani dalle possibilità
umane di calcolo; i ricercatori sono dunque in grado di formulare con grande
precisione congetture che in passato non potevano essere espresse.
Si può pertanto affermare che il mondo matematico sia fortemente
interessato alla realizzazione di strumenti di calcolo simbolico sempre più
sofisticati al fine di progredire nella ricerca di quelle proprietà per le quali esiste
una “testimonianza sperimentale”.
1.1.1 Computer Algebra Systems (CAS)
Un Computer Algebra System (CAS) consiste in un particolare pacchetto
software che fornisce la possibilità di manipolare ed automatizzare calcoli
algebrici di notevole complessità. La principale caratteristica di un sistema di
questo tipo risiede nella capacità di lavorare sulle equazioni in modo simbolico
piuttosto che numerico.
Storicamente il primo programma orientato alla computazione algebrica fu
un programma per il calcolo differenziale realizzato per UNIVAC I da
Kahrimanian nell’anno 1953. Il primo vero sistema per la manipolazione algebrica
12
venne implementato negli anni ’60 in FORTRAN e si chiamava ALgebra
TRANslator (ALTRAN): tra la altre cose questo sistema aveva implementati
nuovi algoritmi per la moltiplicazione tra polinomi ed il calcolo del massimo
comun divisore .
In data 1968 Carl Engleman sviluppò MATHLAB il primo sistema di
calcolo interattivo, mentre gli anni ’80 videro la nascita di alcuni sistemi “general
purpose” come Axiom [http://www.nag.co.uk:70/1h/symbolic/AX.html](precedentemente
noto come SCRATCHPAD), Derive [http://www.derive.com/], Macsyma, Maple
[http://www.maplesoft.com/], Mathematica [http://www.wolfram.com/products/mathematica/]
e Reduce [http://www.rrz.uni-koeln.de/REDUCE/]; alcuni anni più tardi furono
sviluppati sistemi “special purpose”, specializzati nel campo dell’algebra
commutativa: Macaulay [http://www.math.columbia.edu/~bayer/Macaulay.html] e CoCoA
[http://cocoa.dima.unige.it/ ].
1.1.2 Caratteristiche di base per un Computer Algebra System
Le principali qualità specifiche di un sistema “special purpose” specializzato
nel campo della Computer Algebra, sono le seguenti:
• strutture dati speciali per la rappresentazione dei dati non numerici;
• un linguaggio per la manipolazione di tali strutture dati;
• una libreria di funzioni per l’esecuzione delle operazioni algebriche di
base;
• capacità di lavorare con espressioni matematiche;
• possibilità di operare in modo interattivo;
• programmabilità, al fine di estendere le capacità del sistema;
• precisione arbitraria per i numeri interi e razionali.
È naturale che ognuna delle caratteristiche appena descritte debba essere
implementata in maniera del tutto efficiente, considerata la grande complessità
degli algoritmi di base. Tutto il sistema deve inoltre essere il più “user-friendly”
possibile, cioè deve garantire la possibilità di utilizzo anche a matematici non
esperti di computer.
Nel paragrafo 1.3 viene descritto dettagliatamente il sistema di calcolo CoCoA
nella sua attuale versione.
13
1.2 Interfacciamento ad un sistema di calcolo
In questo paragrafo viene esaminata una serie di requisiti necessari ad un
buon interfacciamento utente per un sistema di calcolo; tali considerazioni
derivano direttamente dall’esperienza di utenti e sviluppatori del sistema di
calcolo CoCoA, descritto nel paragrafo successivo.
In un sistema di calcolo l’interazione tra l’utente ed il sistema stesso è
caratterizzata da una mistura di operazioni ad alto costo computazionale (ad
esempio per il calcolo di basi di Gröbner [12]) e di operazioni che consentano una
sorta di “navigazione dei dati”; l’interfacciamento al sistema, tenendo conto di
ciò, dovrebbe avere dunque la possibilità di ottenere differenti “viste” dello stesso
output.
Il fatto che vengano coinvolte operazioni piuttosto dispendiose in termini di
calcolo, dovrebbe suggerire inoltre la capacità del sistema di utilizzare
un’appropriata risorsa computazionale.
1.3 Il sistema di calcolo CoCoA
CoCoA è un sistema di calcolo orientato principalmente alla computazione
nell’ambito dell’algebra commutativa (Computations in Commutative Algebra)
ed è il risultato del gruppo di ricerca in Computer Algebra presso l’Università di
Genova.
CoCoA è il nome del progetto di ricerca iniziato verso la metà degli anni
ottanta coordinato da Lorenzo Robbiano e sviluppato nella sua prima versione da
Alessandro Giovini e Gianfranco Niesi. L’idea originaria fu quella di produrre un
software che fosse un valido strumento di utilità per il lavoro di matematici ed al
tempo stesso una sorta di laboratorio di ricerca in vari campi, a partire dalla
Commutative Algebra fino al Software Engineering. Dopo la prematura morte di
Giovini venne a crearsi un nuovo progetto, nuovamente sotto la direzione di
Robbiano, avente come autori Antonio Capani e Gianfranco Niesi coadiuvati da
alcuni ricercatori quali John Abbott, Anna Bigatti, Massimo Caboara e Gabriel De
Dominicis.
Attualmente CoCoA viene soprattutto utilizzato in varie nazioni da
ricercatori algebristi, ma anche da statisti ed analisti matematici, vista la
completezza del sistema. Il coordinamento tecnico dello sviluppo di CoCoA è
attualmente affidato a John Abbott.
14
CoCoA è in grado di effettuare operazioni “base” quali ad esempio: somme,
prodotti, elevamenti a potenza, derivate, MCD, mcm di polinomi; somme,
prodotti, elevamenti a potenza, derivate di funzioni razionali; somme, prodotti,
elevamenti a potenza di ideali; somme di moduli; somme, prodotti, elevamenti a
potenza, determinanti e aggiunte di matrici e cosi via. Sono tuttavia possibili
operazioni “avanzate” come ad esempio le principali operazioni sugli ideali e sui
moduli (basi di Gröbner, sizigia, risoluzioni libere minimali, intersezione e
divisione, inclusione e test di uguaglianza), oppure come il calcolo delle serie di
Poincaré o delle funzioni di Hilbert.
1.3.1 Il linguaggio di programmazione CoCoA L
Una delle principali caratteristiche di CoCoA consiste nel fatto di includere
un linguaggio di programmazione, simile al Pascal, battezzato CoCoA L.
Tale linguaggio è stato studiato e sviluppato affinché l’utente fosse in grado,
avvalendosi unicamente di alcuni concetti base di programmazione, di creare
nuove librerie o di estendere quelle già fornite dal sistema. La sintassi del
linguaggio permette inoltre la scrittura di notazioni prettamente in stile
matematico: l’utente può ad esempio scrivere xy intendendo x * y .
Il linguaggio fornisce una collezione di tipi predefiniti:
• tipi base : interi, numeri razionali, interi modulo p, polinomi a più
variabili, funzioni razionali a più variabili, stringhe e tipi
1
.
• tipi strutturati : liste, matrici e record aperti
2
(conosciuti anche come
array associativi).
Esempio
La seguente funzione calcola la matrice jacobiana di un insieme S di
polinomi rispetto alle variabili dell’anello corrente. La notazione usata per
dichiarare la funzione è vicina all’usuale notazione matematica.
Jacobian(S) := Mat[ [Der(P,X) | X Indets()]|PinS];
1
L’utente ha la possibilità di utilizzare valori di tipo TYPE ad esempio per controllare il tipo di un
parametro allo scopo di scegliere una corretta implementazione.
2
Il tipo “record aperto” consiste in un insieme di coppie del tipo (nome, valore) in cui valore può
essere di tipo qualsiasi; il nome open deriva dal fatto che la lista dei nomi non è fissata a priori, il
che offre la possibilità di aggiungere o rimuovere le coppie dinamicamente.
15
1.3.2 Architettura di CoCoA
CoCoA è composto da due moduli: un interprete per il linguaggio CoCoA L
e un’interfaccia utente.
Figura 1 : architettura di CoCoA
Come è possibile osservare in Figura 1, l’interfaccia ha il compito di
trasformare le richieste (comandi) dell’utente dal formato del linguaggio CoCoA L
a termini di formato diverso chiamati CoCoA Terms (CTerms) appartenenti ad un
protocollo interno dedicato (CTL, vedi sezione 1.3.3.2); tale protocollo
corrisponde grossomodo ad un parse tree delle richieste e garantisce una
maggiore indipendenza dai dettagli notazionali e lessicali del linguaggio,
favorendo pertanto un buon interfacciamento verso il mondo esterno.
A questo punto l’interprete riceve i comandi nel linguaggio CTL e li
esegue all’interno di un ringenv, cioè un ambiente costruito sopra un anello base.
L’interprete inoltra infine la richiesta ad un nucleo (kernel) di funzioni
matematiche le quali si occupano della manipolazione dei coefficienti, dei
polinomi, degli ideali e così via.
Nei paragrafi seguenti viene maggiormente particolareggiata l’architettura
del sistema CoCoA.
user
interface
user request
(CoCoAL)
interpreter Kernel of
mathematical
functions
16
1.3.3 Scomposizione dell’architettura di CoCoA
1.3.3.1 Struttura generale di una applicazione CoCoA
Figura 2: Struttura generale di una applicazione CoCoA
Il sistema CoCoA di per se’ non è una applicazione, o meglio non è
possibile eseguirlo direttamente in quanto non possiede un programma principale.
Un’applicazione CoCoA consiste dunque in un unico programma formato da un
Application Main, dal kernel di CoCoA e da un modulo di Input/Output formato
da una lista di “device astratti” (chiamati CoCoA Devices, brevemente CDevices)
che consentono al sistema CoCoA di accedere al mondo esterno (ad esempio verso
componenti fisici quali terminali, stampanti, filesystems, reti di comunicazione).
L’application main controlla l’esecuzione del programma trasmettendo le
richieste al Kernel facendo uso di un protocollo dedicato chiamato CoCoA Terms
Language (CTL), descritto in maggior dettaglio nella sezione 1.3.3.2.;
l’application main può inoltre interagire con altre applicazioni esterne.
terminals
filesystems
printers
network
…
PHISICAL
DEVICES
Application Main
CDevices
CoCoA Kernel
CoCoA Application
External
Applications
17
Il kernel e l’application main hanno la possibilità di leggere comandi CTL
dai CDevices di input e scrivere valori (i risultati, sempre in formato CTL) sui
CDevices di output.
Al momento in cui avviene la stesura della presente Tesi, sono state
sviluppate due applicazioni grafiche di CoCoA, per piattaforme Macintosh e
Windows, ed una in formato di solo testo utilizzabile su piattaforme Unix e su
sistemi DOS senza accesso a Windows.
1.3.3.2 CoCoA Terms Language (CTL)
Come già accennato, il linguaggio CTL è un linguaggio dedicato utilizzato
sia per l’interazione fra il CoCoA application main e kernel, sia per lo scambio di
informazioni ad alto livello tra i CDevices di input/output.
Un elemento di questo linguaggio, detto CoCoA term (CTerm), consiste in
una rappresentazione ad albero di una operazione: la radice dell’albero
rappresenta l’operatore ed i suoi sottoalberi, che sono a loro volta CTerms,
identificano i parametri dell’operazione. Le foglie dell’albero possono essere
operazioni costanti o stringhe.
Gli elementi del linguaggio CTL sono suddivisi in tre categorie: comandi
CTL, espressioni CTL e valori CTL. Ogni CTerm è ottenuto unendo operatori
CTL e stringhe. Più precisamente i Cterms risultano in una delle seguenti forme:
• “una stringa”
• operazioni di arità zero: o() (dove o è un operatore CTL)
• operazioni di arità n : o(t
1
, …t
n
) (dove o è un operatore CTL e t
i
sono
CTerms)
Il linguaggio CTL risulta vantaggioso per le seguenti ragioni:
• astrae da una particolare sintassi (per esempio la sintassi di CoCoA L) e risulta
maggiormente orientato alla semantica (a grandi linee si ha un operatore CTL
per ogni operazione di CoCoA)
• permette una utile distinzione tra espressioni e valori; per esempio una dicitura
del tipo 3x+y può essere vista come un’espressione del tipo:
sum(mult( 3 , x )), y ) oppure come valore (polinomio) della forma:
poly(mon( 3 , x ),mon( 1 , y )). La capacità di distinzione fra le due
interpretazioni risulta molto importante ai fini dell’efficienza del sistema,
come si evidenzia verificando le operazioni da effettuarsi in entrambi i casi:
18
nel primo caso, infatti, devono essere eseguite le seguenti operazioni:
• calcolare l’espressione “3”, ottenendo un intero
• valutare l’espressione “x”, ottenendo un polinomio
• moltiplicare l’intero per il polinomio, ottenendo un altro polinomio P
• valutare “y”, ottenendo un polinomio Q
• valutare l’intera espressione, calcolando la somma dei due polinomi P
e Q
nel secondo caso, invece, viene costruito direttamente il polinomio finale,
usando i due monomi.
• in virtù del fatto che un CTerm è esso stesso un “parse tree” è possibile
eseguire un comando direttamente nel kernel di CoCoA, tralasciando il
controllo della sintassi e garantendosi pertanto una maggiore efficienza
1.3.3.3 I CoCoA devices (CDevices)
I CDevices sono una astrazione delle componenti fisiche di input/output
che forniscono l’interazione tra applicazione CoCoA e mondo esterno. Ogni
CDevice è quindi in grado di acquisire dati da componenti come file, finestre, reti
di comunicazione o stringhe in memoria, e di scrivere dati su componenti di
output quali ad esempio file, finestre, stampanti, memorie buffer.
I CDevices implementano di fatto sia operazioni a basso livello quali
getChar(), getString(), putChar() e putString(), sia operazioni più ad alto
livello come getCTerm() e putCTerm() per la lettura e scrittura dei dati. Ogni
device deve inoltre implementare un protocollo al fine di tradurre i dati di input in
CTerms (utilizzando la funzione getCTerm() ) e di tradurre i CTerms in dati di
output.
1.3.3.4 Il Parser di CoCoA
Il Parser di CoCoA si fa carico della traduzione dei dati dal linguaggio
CoCoA L ai comandi ed espressioni in CTL. Un CDevice di input è in grado
pertanto di implementare il protocollo CoCoA L per mezzo di tale parser. I valori
CTL vengono tradotti in CoCoA L grazie ad un modulo detto “Pretty printing”; un
Cdevice di output può pertanto far uso di tale modulo per implementare il
protocollo CoCoA L.
19
Rimane da notare che il linguaggio CoCoA L, sebbene sia al momento
l’unico protocollo implementato per accedere ad alto livello al sistema, è soltanto
uno dei possibili protocolli implementabili per i CDevices.
Figura 3 : il parser di CoCoA
1.3.3.5 Il Kernel di CoCoA
In un sistema come CoCoA le computazioni matematiche costituiscono,
ovviamente, l’obiettivo principale; per questo motivo all’interno del sistema stesso
risiedono vari algoritmi di carattere matematico. Allo stesso tempo, tuttavia,
CoCoA è stato progettato allo scopo di rendere il sistema di facile utilizzo ed
estensibile.
In virtù di tali considerazioni l’architettura del sistema, come si può vedere
in Figura 4, pone una netta distinzione tra il modulo responsabile della
comunicazione all’esterno, l’ Engine module, e la libreria matematica, il Math
module.
Application Main
CDevices
CoCoA Kernel
CoCoAL
Parser
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
