Courses » Class » LMC0809 » Progetti

Progetti

Note:

Si ricordano i principali aspetti relativi ai progetti da svolgere per l'esame:

  • Il progetto è comunque facoltativo, e può essere rimpiazzato da una prova orale sul programma del corso (la cui preparazione richiede tuttavia un tempo analogo)
  • Il progetto è ideato e scelto dallo studente, e comunicato al docente in anticipo in modo da stabilire gli obbiettivi precisi, che comportino un impegno temporale di circa 75 ore (ogni studente è tenuto a tenere traccia delle ore impiegate per svolgere il progetto)
  • Una volta assegnato il progetto, questo deve essere terminato nel giro di un mese circa. Fa eccezione il caso in cui il progetto venga assegnato durante il periodo del corso: in tal caso deve essere terminato entro fine Gennaio. Nel caso scada il periodo, si ri-contatti il docente per stabilire il dafarsi (tipicamnete, ristabilendo una nuova scadenza)
  • Qui sotto si elencano proposte di progetto per chi non avesse idea di cosa fare, o per chi cercassi spunti per proporre un progetto proprio. Rimane inteso che qualunque altra proposta può essere avanzata.
  • Per qualunque delucidazione o maggiori informazioni non si esiti a chiedere
  • Questa lista verrà estesa via via durante lo svolgimento del corso

Consegna del Progetto:

  • Il progetto si consegna in anticipo (solitamente per e-mail) al docente, che dopo aver fatto alcune verifiche di completezza/adeguatezza fissa una data per l'esame di comune accordo (solitamente nel giro di una settimana)
  • Si deve includere una relazione, in formato PDF e completa di bibliografia anche minima. Un ambiente consigliato per produrre la relazione è Latex (anche se questa scelta non è imposta).
  • Si deve includere il software eventualmente prodotto. Si raccomanda che esista un deployment semplice per tale software (l'ideale sarebbe in un JAR direttamente eseguibile ed auto-contenuto), e che sia descritto in un file README.txt
  • Per l'esame ci si deve preparare una presentazione di 15 minuti a cui seguirà una discussione (è possibile ma non necessario prepararsi delle slides)

Proposte di Progetto

Si elencano qui sotto alcune proposte di progetto. Nella sezione "Bioinformatica" si troverrano progetti recentemente aggiunti, e di particolare significatività.

Prolog

  • DCG-like Tokenization: Partendo dall' analisi di sistemi di tokenizzazione esistenti, ad esempio come supportato in JavaCC e nel compilatore Java, realizzare un supporto generale alla tokenizzazione in Prolog, tramite DCG o loro estensione.
  • XMLProlog: Questo progetto esplora la bidirezionalità tra rappresentazioni XML e Prolog, fornendo soluzioni per caricare documenti XML/Prolog, maneggiarli (accessi e modifiche) via predicati logici, e risalvarli come documenti XML/Prolog. [ASSEGNATA]
  • RDFProlog: Questo progetto esplora la convenienza nel rappresentare documenti RDF in Prolog, e sviluppa le funzionalità base per accedere e manipolare gli aspetti semantici contenuti in questi documenti. [ASSEGNATA]
  • ODSProlog: Questo progetto esplora la bidirezionalità tra rappresentazioni di fogli elettronici OpenOffice (che sono memorizzati come documenti XML compressi) e Prolog, fornendo soluzioni per caricare fogli elettronici in Prolog, maneggiarli (accessi e modifiche) via predicati logici, e risalvarli come fogli elettronici. [ASSEGNATA]
  • MetaCheck: Costruire un checker per programmi prolog che individui errori semantici, come l'uso di predicati non definiti e l'uso di variabili singoletto. Questo checker potrebbe essere realizzato utilizzando le tecniche di metaprogrammazione viste a lezione, e incorporare tutte le funzionalità che si ritengono utili per supportare lo sviluppo di programmi Prolog.
  • MetaCut: Estendere il meta-interprete Vanilla visto a lezione in modo da gestire anche la semantica dell'operatore di cut. A tal scopo è necessario che il meta-interprete mantenga una rappresentazione dei risolutori pendenti e sia in grado di simulare il backtracking.
  • MetaSequence: Costruire un metainterprete in cui l'unificazione sia in grado di gestire un operatore di sequenza associativo (e che assorba la sequenza vuota). Per esempio: [1,2,3,4]={X;3;Y}. -> Yes, X/{1;2}, Y/{4}. [ASSEGNATA]
  • MetaParallel: Costruire un metainterprete in cui l'unificazione sia in grado di gestire un operatore di parallelo associativo e commutativo. Per esempio: unify([1,2,3,4], {X // 3}). -> Yes, X/{1 // 2 // 4}. [ASSEGNATA]

Integrazione Java-Prolog

Si noti che molti dei progetti di cui sopra possono essere realizzati come librerie Prolog scritte in Java, e rientrare quindi in questa categoria

  • IDEWarn: Costruire una estensione dell'IDE sperimentale tuProlog che supporti funzionalità di debugging varie come warning relativi a variabili singoletto o all'uso di predicati non definiti.
  • PUnit: Costruire un framework per il collaudo di programmi Prolog, da utilizzare sia per singoli predicati sia per teorie più complesse. La specifica dei test andrebbe realizzata in maniera dichiarativa, ma possono essere sfruttate le funzionalità Java attraverso la realizzazione di specifici predicati di libreria.
  • JPGraph: Un aspetto che avrebbe senso programmare in modo dichiarativo nelle applicazioni è la parte di disegno grafici (2D, 3D, pie-charts, line-charts etc..). In questo progetto si studia come usare una teoria Prolog per specificare la logica di disegno grafici, poi di fatto realizzata attraverso le API 2D di Java.
  • PJGraph: Un aspetto che avrebbe senso programmare in modo dichiarativo nelle applicazioni è la parte di disegno grafici (2D, 3D, pie-charts, line-charts etc..). In questo progetto si introduce una libreria Prolog realizzata in Java usando le API 2D per fornire funzionalità per creare finestre con aree di disegno.
  • JPWindowLayout: Un aspetto che avrebbe senso programmare in modo dichiarativo nelle applicazioni è la parte di layout delle finestre grafiche (swing/awt). In questo progetto si studia come usare una teoria Prolog per specificare la logica di piazzamento di componenti grafici (Labels, TextFields, Buttons) all'interno di una finestra. [ASSEGNATA]
  • ABoardGame: Costruire una applicazione Java che realizza un gioco da scacchiera, e che usa una teoria Prolog per ragionare su quale mossa il computer deve compiere ogni volta per vincere la partita. Si noti che l'algoritmo generale di decisione è noto in letteratura ed è semplice: il problema si risolve codificando opportunamente le mosse possibili e il valore di profitto attribuito ad ogni possibile stato del gioco. [ASSEGNATA]
  • ACardGame: Come nel caso precedente è possibile realizzare una applicazione per giochi di carte e/o giochi da tavolo. Si noti in questo caso che l'enfasi non va data sull'aspetto grafico del frontend Java. [ASSEGNATA]
  • Fast unification: L'algoritmo standard di unificazione di termini del prim'ordine può essere ottimzzato usando tecniche di hash-consing e una opportuna codifica in bit (i termini via via usati vengono inseriti in una hashtable ad accesso veloce). Il progetto verterà nell'analisi astratta del problema, delle performance di ventuali soluzioni ottimizzate, ed infine di una realizzazione in tuprolog.
  • Fast data structures for tuProlog: Uno dei motivi per il quale codice tuProlog risulta spesso lento è dovuto all'uso di strutture lista (e quindi al reperimento sequenziale dell'informazione). Come noto, tuProlog permette l'uso di vettori e hashtables(/hashsets) di Java sia tramite JavaLibrary o wrappati dentro a nuove librerie, e quindi perdendo le facility fornite dall'unificazione. In questo progetto si dovrà valutare la possibilità di modificare il motore tuprolog per supportare a livello sintattico e semantico insiemi e vettori.

Progetto di Linguaggi, Interpreti e Traduttori

I progetti di questo tipo consistono nelle seguenti fasi: (i) individuazione della problematica da gestire tramite un linguaggio specifico (potrebbe essere una di quelle sopra citate), (ii) individuazione del linguaggio (sintassi), (iii) realizzazione di un supporto sintattico (parser) e semantico (interprete; generatore di codice verso Prolog, Java, o altro; generatore di un formato intermedio leggibile da un diverso software).

Altre possibilità includono:

  • Java parsing in Prolog : Il compilatore Java realizza parsing e generazione d'albero in un passo ben delineato, che attualmente è tuttavia realizzato in un complesso frammento di codice Java ad-hoc. In questo progetto si dovrà valutare una re-implementazione di tale frammento sfruttando la tecnologia tuprolog, ossia descrivendo il parsing in modo dichiarative, per esempio tramite DCG.

Studio e supporto di modelli computazionali avanzati

A lezione sono stati visti modelli avanzati come algebre di processo e reti di petri. Altri ne esistono in letterature, come amorphous computing, automi cellulari, membrane computing, sistemi multi-agenti. Alcuni di questi modelli hanno poi estensioni timed, probabilistiche, stocastiche, e sono utilizzabili in simulazioni. Si cerchi in rete o si chieda al docente per maggiori informazioni. I progetti in questa area sono volti a studiare questi modelli e/o sperimentare software di supporto esistente e/o applicarli a casi di studio di interesse e/o produrre prototipi in Prolog o Java/Prolog.

  • AdvancedModelToProlog: Preso un modello avanzato, definirne la semantica operazionale mediante lo schema dell'interprete di transition systems visto a lezione, che è utilizzabile per simulazioni e/o come core per un frontend Java
  • AdvancedModelToMaude: Preso un modello avanzato, definirne la semantica operazionale mediante MAUDE, con la possibilità quindi di fare model-checking.
  • ConcurrencyAnalysis: Preso un sistema concorrente, modellarlo con qualcuno degli strumenti visti. Analizzarlo con model-checking e/o simulandone una variante stocastica.
  • AdvancedModelToPrism: Preso un modello o linguaggio stocastico (tempo continuo o discreto), costruire un trasnformatore verso codice PRISM, che consenta quindi di simulare/verificare proprietà di interesse. Un esempio di tale linguaggio/modello potrebbe essere quello delle reti di Petri in versione stocastica: in questo caso si potrebbe definire un linguaggio in Prolog, e poi (sempre in Prolog) una traduzione verso PRISM. (Si noti che un articolo sul mapping fra stochastic pi-calculus e PRISM è appena apparso sulla più importante rivista di Ingegneria del Software al mondo: ossia, si tratta di attività di enorme rilevanza scientifica)

Bioinformatics

Nonostante poco spazio sia stato dato a lezione su questa branca di applicazione dei linguaggi e dei modelli computazionali, molti progetti possono essere svolti in questa area (non richiedendo alcuna conoscenza pregressa esterna al corso). Tutti questi progetti sono a elevato valore scientifico, nonostante non richiedano particolare difficoltà realizzative. Si elencano qui sotto i principali temi, ma si sollecita lo studente a contattare il docente per una discussione più dettagliata:

  • ChemicalToPrism: I sistemi chimici corrispondono a semplici sistemi stocastici tempo continui e come tali sono simulabili e verificabili. Come per il progetto di cui sopra, costruire un traduttore da specifiche di reazioni chimiche verso PRISM. [ASSEGNATA]
  • BioNetToPrism: Partendo da un interprete esistente scritto in Prolog, per la specifica di reti biochimiche cellulari, costruire un traduttore verso specifiche PRISM.
  • BioNetToSPIM: Partendo da un interprete esistente scritto in Prolog, per la specifica di reti biochimiche cellulari, costruire un traduttore verso specifiche SPIM.
  • BioNetToSPIM: BioPEPA è un tool per la simulazione di sistemi biochmici, con finalità simili a SPIM. In questo progetto se ne dovrà studiare il funzionamento applicando case study nall'ambito delle reti biochimiche multicellulari
  • ChemicalPatterns: I sistemi chimici possono essere visti dualmente come sistemi ecologici, in cui le reazioni chimiche evolvono poplazioni di individui (prede, predatori, item di cibo, etc..), e come tal sono rilevanti per la coordinazione adattativa di sistemi ad agenti. In questo progetto, partendo da reazioni chimiche note (naturali e artificiali) si dovrà costruire un catalogo di pattern chimici/ecologii utili nel contesto della multiagent coordination.