Ragionamento su aggregati e numeri a supporto della programmazione e relative verifiche: dagli algoritmi di decisione alla programmazione con vincoli con multi-insiemi, insiemi e mappe

CANTONE	DOMENICO
(cognome)	(nome)
Università degli Studi di CATANIA	Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI
(università)	(facoltà)
K05B	Dipartimento di MATEMATICA E INFORMATICA
(settore scient.discipl.)	(Dipartimento/Istituto)

cantone@dmi.unict.it
(E-mail)

ROSSI	GIANFRANCO
(cognome)	(nome)

Professore associato	30/08/1956	RSSGFR56M30H223G
(qualifica)	(data di nascita)	(codice di identificazione personale)

Università degli Studi di PARMA	Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI
(università)	(facoltà)
K05B	Dipartimento di MATEMATICA
(settore scient.discipl.)	(Dipartimento/Istituto)

0521/902309	0521/902350	gianfr@prmat.math.unipr.it
(prefisso e telefono)	(numero fax)	(E-mail)

Testo italiano

Gianfranco Rossi ha ricevuto la laurea in Scienze dell'Informazione dall'Universita' di Pisa nel 1979. Dal 1981 al 1983 ha lavorato presso la societa` Intecs Co. System House a Pisa. Da Novembre 1983 a Febbraio 1989 e` stato ricercatore presso il Dipartimento di Informatica dell'Universita` di Torino. Da Marzo 1989 e' Professore Associato di Fondamenti dell'Informatica, attualmente in servizio presso l'Universita' di Parma. E` autore di numerosi articoli riguardanti principalmente i linguaggi di programmazione, con particolare riferimento ai linguaggi di programmazione logica e al Prolog, e gli algoritmi di unificazione estesi. I suoi attuali interessi di ricerca sono nel campo dei linguaggi (logici) con vincoli insiemistici e degli algoritmi di unificazione insiemistica.

Testo inglese

Gianfranco Rossi received his degree in Computer Science from the University of Pisa in 1979. From 1981 to 1983 he was employed at Intecs Co. System House in Pisa. From November 1983 to February 1989 he was a researcher at the Dipartimento di Informatica of the University of Turin. Since March 1989 he is an Associate Professor of Computer Science, currently with the University of Parma. He is the author of several papers dealing mainly with programming languages, in particular logic programming languages and Prolog, and extended unification algorithms. His current research interests are in constraint (logic) programming languages with set and in set unification algorithms.

1. DOVIER A., PIAZZA C., PONTELLI E., ROSSI G. (2001). Sets and Constraint Logic Programming. ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS. to appear.
2. DOVIER A., PONTELLI E.., ROSSI G. (2001). Constructive negation and constraint logic programming with sets. NEW GENERATION COMPUTING. vol. 19 (3) to appear.
3. DOVIER A., PONTELLI E., ROSSI G. (2000). A Necessary Condition for Constructive Negation in Constraint Logic Programming. INFORMATION PROCESSING LETTERS. vol. 74 (3-4), pp. 147-156.
4. DOVIER A., POLICRITI A., ROSSI G. (1998). A Uniform Axiomatic View of Lists, Multisets, and Sets, and the Relevant Unification Algorithms. FUNDAMENTA INFORMATICAE. vol. 36(2/3), pp. 201-234.
5. DOVIER A., PONTELLI E., ROSSI G., OMODEO E. (1996). {log}: A Language for Programming in Logic with Finite Sets. JOURNAL OF LOGIC PROGRAMMING. vol. 28(1), pp. 1-55.

Nº	Cognome	Nome	Dipart./Istituto	Qualifica	Settore scient.	Mesi uomo
						2001	2002
Personale docente:
1	ROSSI	GIANFRANCO	MATEMATICA	Prof. associato	K05B	11 (ore: 1507)	9 (ore: 1233)
2	BAGNARA	ROBERTO	MATEMATICA	Ricercatore	K05B	3 (ore: 411)	3 (ore: 411)
Altro personale:
3	ALFIERI	ROBERTO	FISICA	Coord.Tecn. (vinc. posto Ric.)		5 (ore: 685)	5 (ore: 685)

1.8.2 Personale universitario di altre Università

Nº	Cognome	Nome	Università	Dipart./Istituto	Qualifica	Settore scient.	Mesi uomo
							2001	2002
Personale docente:
1	DOVIER	AGOSTINO	VERONA	SCIENTIFICO E TECNOLOGICO	Ricercatore	K05B	5 (ore: 685)	8 (ore: 1100)
Altro personale:

1.8.3 Titolari di assegni di ricerca

Nº	Cognome	Nome	Dipart./Istituto	Anno del titolo	Mesi uomo
					2001	2002
1	ZAFFANELLA	ENEA	Dip. MATEMATICA	2000	4 (ore: 550)	4 (ore: 550)

1.8.4 Titolari di borse per Dottorati di Ricerca e ex L. 398/89 art.4 (post-dottorato e specializzazione)

Nº	Cognome	Nome	Dipart./Istituto	Anno del titolo	Mesi uomo

1.8.5 Personale a contratto da destinare a questo specifico programma

Nº	Qualifica	Costo previsto	Mesi uomo
1.	Dott. di ricerca	60	22  (ore: 3025)

1.8.6 Personale extrauniversitario dipendente da altri Enti

Nº	Cognome	Nome	Dipart./Istituto	Qualifica	Mesi uomo
1.	PONTELLI	ENRICO	Dept. Computer Science, New Mexico State Univ.	Assistant Professor	10  (ore: 1375)

Testo italiano

Programmazione dichiarativa con vincoli su insiemi e multi-insiemi

Testo inglese

Declarative programming with set and multiset constraints

Testo italiano
PROGRAMMAZIONE DICHIARATIVA ; PROGRAMMAZIONE CON VINCOLI ; VINCOLI INSIEMISTICI ; TEORIA COMPUTABILE DEGLI INSIEMI ; RISCRITTURA DI MULTI-INSIEMI

Testo inglese
DECLARATIVE PROGRAMMING ; CONSTRAINT PROGRAMMING ; SET CONSTRAINTS ; COMPUTABLE SET-THEORY ; MULTISET REWRITING

Testo italiano

Negli ultimi anni si e' osservato un crescente interesse per l'utilizzo di varie forme di aggregazione dei dati e di costrutti insiemistici all'interno dei vari paradigmi di programmazione e di specifica del software. Attualmente esistono vari linguaggi che offrono costrutti insiemistici come entita' di "prima classe" – si va dai linguaggi imperativi (come, ad esempio, SETL [SDDS86]), ai linguaggi funzionali e logici (come, ad esempio, SuRE [JM95], CLP(SET) [DPPR00], CLPS [LL91], SETA [SFA98]), ai linguaggi "object-oriented" (ad esempio, CLAIRE [CL96]), fino a paradigmi piu' specialistici adottati, ad esempio, nella specifica del software (come Z [Spi92]) o in domini applicativi piu' ristretti, come nei modelli di coordinamento (ad esempio, Gamma [BL-M93]), nel "non-monotonic reasoning" (ad esempio, Smodels), o nelle applicazioni di database (ad esempio, LDL [BNST91]). Inoltre, molti altri linguaggi di programmazione (quali, ad esempio, ECLiPSe [eclipse99], Oz [Vro99], Escher [Llo99]) forniscono insiemi ed operazioni su insiemi come parte dello loro librerie standard.

Un utilizzo particolarmente interessante delle astrazioni di tipo insiemistico si ha in combinazione con i cosiddetti linguaggi dichiarativi. Infatti i costrutti insiemistici e le varie operazioni su insiemi sono per loro stessa natura fortemente "dichiarativi", e permettono di descrivere in modo naturale ed astratto soluzioni non-deterministiche a problemi anche complessi (cfr. [Ros97]). Il fatto che le operazioni su insiemi possano venir trattate come vincoli permette di accrescere ulteriormente la loro "dichiarativita'". La presenza di adeguate astrazioni di tipo insiemistico, come ad esempio gli insiemi intensionali, permette poi di dare formulazioni chiare e concise di problemi che coinvolgono operazioni di aggregazione o di "collezione" di insiemi. L'idea alla base di questo stile di programmazione è che, usando un linguaggio adeguato, molte definizioni di tipo insiemistico possono essere usate immediatamente come programmi eseguibili. Linguaggi dichiarativi con insiemi possono pertanto diventare un interessante strumento per la prototipazione rapida del software, in cui normalmente l'efficienza computazionale non è un requisito di primaria importanza. Aree di applicazione privilegiate per questo tipo di linguaggi comprendono i database deduttivi, i problemi combinatori, le applicazioni basate su grafi (ad es., la colorazione di grafi) e la ricerca operativa in genere (ad es., problemi di allocazione risorse), come evidenziato per esempio in [Ger97,LL91,CL96].

Negli ultimi dieci anni varie persone dell'Unita' di Parma sono state fortemente coinvolte nello studio e nello sviluppo di linguaggi logici arricchiti con insiemi e vincoli insiemistici. Recentemente è stata completata la definizione e realizzazione prototipale di uno di questi linguaggi – denominato CLP(SET) [DPPR00] – un linguaggio logico a vincoli che fornisce varie forme generali e flessibili di costrutti insiemistici con le relative operazioni di base per la loro manipolazione. Gli insiemi in CLP(SET) sono visti come oggetti primitivi del linguaggio, precisamente termini della logica del prim'ordine, mentre tutti i predicati predefiniti che hanno a che fare con insiemi sono visti come vincoli ("constraint") primitivi del linguaggio. Il linguaggio CLP(SET) descritto in [DPPR00] rappresenta un'evoluzione e revisione in termini di una visione CLP ("Constraint Logic Programming") del linguaggio logico esteso {log} descritto in [DOPR96]. Un interprete funzionante – implementato in SICStus Prolog – del linguaggio in [DPPR00] e' disponibile al sito WEB www.math.unipr.it/~gianfr/setlog.Home.html. Va notato, inoltre, che parte del lavoro fin qui svolto - specificatamente l'individuazione di particolari formule insiemistiche, i "set constraints", di cui si puo' decidere la soddisfacibilita' - e' strettamente collegato agli studi sulla "Computable Set Theory" (CST) [CFO89]. La CST e' stata sviluppata negli anni '80 principalmente per rispondere all’esigenza di migliorare i motori inferenziali dei dimostratori di teoremi e per l'implementazione del linguaggio imperativo con insiemi SETL [SDDS86]. Il problema generale che ci si pone in quel contesto e' quello di identificare delle opportune classi computabili di formule di sotto-teorie della teoria generale degli insiemi di Zermelo-Fraenkel.

Nella letteratura vengono spesso considerati anche altri tipi di aggregati, quali multi-insiemi e liste. Effettivamente, esistono varie interessanti applicazioni per le quali queste diverse forme di aggregato sembrano adattarsi piu' naturalmente alle caratteristiche del problema considerato. In particolare, i multi-insiemi – collezioni di oggetti in cui sono ammessi elementi ripetuti – vengono utilizzati in vari contesti. Molte recenti proposte, in vari campi anche molto distanti tra loro, si basano essenzialmente proprio sulla nozione di riscrittura di multi-insiemi ("multiset rewriting"). Si va dal "membrane computing" di [Paun00], all'analisi di protocolli [CDML2000], ai modelli di oggetti comunicanti [BPM00], alle "constraint multiset grammars" [MMW98]. Relativamente pochi sono invece i linguaggi e gli ambienti di programmazione che offrono un supporto adeguato alla gestione di multi-insiemi. Tra questi vanno senz'altro citati il linguaggio di coordinamento GAMMA [BM93] e la Chemical Abstract Machine [BB98], in cui i multi-insiemi e la riscrittura di multi-insiemi rappresentano, rispettivamente, la struttura dati e la struttura di controllo fondamentali. Un'altra proposta in questa direzione è quella del linguaggio logico-funzionale SETA [SFA98] che offre varie possibilita' di gestione dei multi-insiemi tramite cui è possibile realizzare elaborazioni anche complesse su multi-insiemi.

Il gruppo di Parma si e' di recente interessato alla definizione ed utilizzo di altre forme di aggregato, affrontando dapprima il problema di una loro caratterizzazione formale precisa. In [DPR98] viene fornita una descrizione assiomatica uniforme delle diverse teorie del prim'ordine che descrivono varie forme di aggregato e mostrata la definizione dei relativi algoritmi di unificazione, parametrica rispetto al tipo di aggregato considerato. In [DPR00] è stato poi affrontato, in via preliminare, l'estensione di questo studio al caso di altre operazioni insiemistiche (in particolare, appartenenza, non appartenenza e disuguaglianza) ed il loro inserimento in un contesto di programmazione logica a vincoli. I risultati teorici sopra menzionati, combinati con il fatto che le soluzioni e le tecniche adottate in CLP(SET) sono largamente generali e flessibili, dovrebbero permettere di estendere facilmente CLP(SET) – in cui sono stati considerati finora soltanto insiemi convenzionali – al caso piu' generale in cui si trattano altre forme di aggregato, in particolare multi-insiemi.

Testo inglese

In the last few years we have observed a progressively increasing interest in the use of various forms of aggregations and set-theoretical constructions within programming and specification paradigms. A variety of languages have become available which provide set-theoretical components as first-class data formats - ranging from well-known imperative languages (e.g., SETL [SDDS86]), functional and (constraint) logic programming languages (e.g., SuRE [JM95], CLP(SET) [DPPR00], CLPS [LL91], SETA [SFA98]), object-oriented languages (e.g., CLAIRE [CL96]), to more specialized paradigms adopted for software specification (e.g., Z [Spi92]) or for more restricted application domains, such as coordination models (e.g., Gamma [BL-M93]), non-monotonic reasoning (e.g., Smodels), and database applications (e.g., LDL [BNST91]). Furthermore, many other programming languages (e.g., ECLiPSe [eclipse99], Oz [Vro99], Escher [Llo99]) provide sets as part of their standard libraries.

A particularly interesting usage of set-theoretical abstractions is in conjunction with declarative programming languages. Indeed, set constructs and operations are by their own nature highly declarative entities. They provide a natural and very abstract way to describe non-deterministic solutions to complex problems [Ros97]. Dealing with them as constraints further enhances their declarativeness. Moreover, availability of suitable set abstractions, such as intensional sets, may help render clear and concise formulations to problems involving set collection and aggregate operations. The basic idea underlying this programming style is that, using a suitable language, many set-theoretical definitions can be readily used as executable programs. Thus, declarative languages with sets turn out to be an interesting tool for rapid software prototyping where computational efficiency is usually not a primary requirement. Privileged application areas for these languages include deductive databases, combinatorial problems, graph-related applications (e.g., graph coloring), and operational research in general (e.g., resource allocation problems), as pointed out for instance in [Ger97,LL91,CL96].

In the last ten years people in the Unit of Parma have been deeply involved in studying and developing logic-based languages for set constraint management. One such language – called CLP(SET) [DPPR00] – which provides very flexible and general forms of sets along with basic operations for set manipulation, has been recently defined and implemented. Sets in CLP(SET) are seen as primitive data objects of the language, namely first-order logic terms, whereas all the predefined predicates dealing with sets are viewed as primitive constraints of the language, handled through the use of suitable constraint solving procedures.
The language in [DPPR00] represents an evolution and a revision in terms of the CLP (Constraint Logic Programming) paradigm of the extended logic programming language {log}, described in [DOPR96]. A CLP(SET) interpreter - implemented in SICStus Prolog - is available at the WEB page www.math.unipr.it/~gianfr/setlog.Home.html. It must be noted that part of the work done so far – namely, singling out a special kind of first-order formulae, i.e., the set constraints, for which we can decide satisfability - is closely related to the work on Computable Set Theory (CST) [CFO89]. CST was mainly developed to answer the need to enhance the inferential engines of theorem provers and for the implementation of the imperative language with sets SETL [SDDS86]. The general problem was that of identifying computable classes of formulae of suitable sub-theories of the general Zermelo-Fraenkel set theory.

Other classes of aggregates have been also considered in the literature, such as multisets and lists. Indeed, there are variuos interesting applications for which these different kind of aggregates seem to fit more naturally the problem requirements than sets. In particular, multisets – i.e., aggregates where elements are allowed to have multiple occurrences – are employed in various contexts. A number of recent proposals, ranging from membrane computing [Paun00] to security protocol analysis [CDML2000], from communicating object models [BPM00] to constraint multiset grammars [MMW98], are based on some notion of multiset rewriting. In contrast, only relatively few programming environments and languages offer suitable support for multiset management. Among them one must cite the coordination language GAMMA [BM93] and the Chemical Abstract Machine [BB98] where multisets and multiset rewriting are the fundamental data and control structure, respectively. Another proposal in this direction is that of the functional-logic language SETA [SFA98] which offers various multiset management capabilities through which it is possible to implement various form of multiset processing (in particular, multiset rewriting).

The group of Parma has recently faced the problem of defining and using different forms of aggregates. The first step has been a precise formal characterization of the aggregates. In [DPR98] we provide a uniform axiomatic view of the first-order theories used to characterize the various data aggregates and we show the definition of the relevant unification algorithms, parametrized with respect to the considered aggregates. A preliminary study on how to extend these results to the case of other basic set-theoretical operations (namely, membership, non-memberbership and inequality) and how to insert them into a CLP context is reported in [DPR00]. These theoretical results, along with the fact that the solutions and techniques adopted in CLP(SET) are quite general and flexible, should allow us to easily extend CLP(SET) – which is now limited to `conventional' sets - to the more general case where it is possible to deal with various kinds of aggregates simultaneously, in particular sets and multisets.

[ADSP98] K.R. Apt, J. Brunekreef, A. Schaerf and V. Partington. Alma-0: An Imperative Language that Supports Declarative Programming. ACM TOPLAS, 20(5), 1998, pp. 1014-1066.
[AS00] K.R. Apt and A. Schaerf. Programming in Alma-0, or Imperative and Declarative Programming Reconciled, in Frontiers of Combining Systems 2, Research Studies Press Ltd, D. M. Gabbay and M. de Rijke (editors), 2000, pages 1-16.
[Bag97] R. Bagnara. Data-Flow Analysis for Constraint Logic-Based Languages, PhD thesis, Dipartimento di Informatica, Universita' di Pisa, Italy, Mar. 1997. Printed as Report TD-1/97.
[BLM93] J.P. Banatre and D.LeMetayer. Programming by Multiset Transformation. Communications of the ACM, 36, 1, Jan. 1993, 98-111.
[BB98] G. Berry and G. Boudol. The Chemical Abstract Machine. Theoretical Computer Science, vol. 96 (1992) 217--248.
[BNST91] Beeri C., Naqvi S., Shmueli O., Tsur S. Set Constructors in a Logic Database Language. Journal of Logic Programming, 10, 3, 1991.
[BPM00] J.-P. Bodeveix, C. Percebois, S. Majoul. An Object-Oriented Coordination Model based on MultisetRewriting. In Proc. of Ninth International Conference on Parallel and Distributed Computing Systems.
[CDR97] R. Carmona, A. Dovier, and G. Rossi. Dealing with Infinite Intensional Sets in CLP In M. Falaschi, editor, APPIA-GULP-PRODE'97. Joint Conference on Declarative Programming. (Grado, Italy, June 1997)
[CDML2000] I. Cervesato, N. Durgin, P. Lincoln, J. Mitchell, and A. Scedrov. Relating Strands and Multiset Rewriting for Security Protocol Analysis. In P. Syverson, ed., 13th IEEE Computer Security Foundations Workshop - CSFW'00, pp. 35-51, 2000.
[CFO89] Cantone, D., Ferro, A., and Omodeo., E.G. Computable Set Theory, Vol.1, Number 6 in International Series of Monographs on Computer Science. Clarendon Press, Oxford.
[CL96] Caseau, Y., Laburthe, F. Introduction to the CLAIRE Programming Language, Technical report, LIENS, 1996.
[CD93] P. Codognet and D. Diaz. A Minimal Extension of the WAM for clp(FD). In 10th International Conference on Logic Programming, Budapest, Hungary, The MIT Press 1993.
[DOPR96] A.Dovier, E.Omodeo, E.Pontelli, G.Rossi. {log}: A Language for Programming in Logic with Finite Sets. Journal of Logic Programming, Vol.28(1), North Holland, 1996, 1--55.
[DPPR00] A.Dovier, C.Piazza, E.Pontelli, and G.Rossi. Sets and Constraint Logic Programming, To appear in ACM Transaction on Programming Language and Systems.
[DPR98] A. Dovier, A. Policriti, and G. Rossi. A uniform axiomatic view of lists, multisets, and sets, and the relevant unification algorithms. Fundamenta Informaticae, 36(2/3):201-234, 1998.
[DPR00] A. Dovier, C.Piazza, and G.Rossi. A uniform approach to constraint-solving for lists, multisets, compact lists, and sets. Technical Report, Dipartimento di Matematica, Universita' di Parma, no. 235, July 2000.
[eclipse99] ECLiPSe, User Manual. Tech. rep., Imperial College, London. August 1999. Available at www.icparc.ic.ac.uk/eclipse.
[Ger97] C.Gervet. Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language. Constraints 1(3):191--244, 1997.
[JM94] Jaffar, J., and Maher, M.J. Constraint Logic }rogramming: A Survey. Journal of Logic Programming 19--20, 503-581, 1994.
[JM95] Jayaraman, B., Moon, K. The SuRE Programming Framework. In Algebraic Methodology and Software Technology, 4th International Conference, AMAST '95, V.S. Alagar and M.Nivat, Eds., Lecture Notes in Computer Science, vol. 936. Springer-Verlag, Berlin, 1995.
[Koz98] D.Kozen. Set Constraints and Logic Programming. Information and Computation 142(1):2--25, 1998.
[LL91] B.Legeard and E.Legros. Short overview of the CLPS system. In J.Maluszynsky and M.Wirsing, eds., Proc. of PLILP'91, vol.528 of LNCS,
[Llo99] Lloyd, J.W. Programming in an Integrated Functional and Logic Language. Journal of Logic Programming, 1999, 3, 1-49.
[Pau00] G. Paun. Computing with Membranes. Journal of Computer and System Science, 61, 2000.
[Ros97] G.F. Rossi. Program Specification and Programming with Sets in Logic.
In I.Plander, ed., Proceedings of the Seventh Int'l Conference on Artificial Intelligence and Information-Control Systems of Robots, World Scientific Publishing, 1997.
[SFA98] P. Arenas-Sanchez, F. J. Lopez-Fraguas, M. Rodriguez-Artalejo. Embedding Multiset Constraints into a Lazy Functional Logic Language. In C.Palamidessi, H.Glaser, K.Meinke, editors, Principles of Declarative Programming, LNCS 1490, Springer-Verlag, pp.429-444, 1998.
[SDDS86] Schwartz, J.T., Dewar, R. B.K., Dubinsky, E., Schonberg, E. Programming with Sets, an Introduction to SETL. Springer-Verlag, Berlin.
[Spi92] Spivey, J.M. The Z Notation: A reference Manual, 2nd edition. International Series in Computer Science. Prentice Hall, 1992.
[VRo99] Van Roy, P. Logic Programming in Oz with Mozart. In International Conference on Logic Programming, D.D.Schreye, Ed. The MIT Press, Cambridge, Mass., 1999, 38-51.

Testo italiano

L'Unita' di Parma si propone di continuare ed approfondire le ricerche inerenti la definizione, uso e realizzazione di linguaggi di programmazione che incorporano la nozione di insieme e le relative operazioni insiemistiche di base. In particolare, si intende:
- estendere lo studio ad altre forme di aggregati, in particolare multi-insiemi e liste;
- migliorare ed ampliare l'interprete del linguaggio logico a vincoli finora sviluppato, anche con l'utilizzo di strumenti di analisi statica di programmi;
- estendere lo studio relativo all'inserimento di vincoli insiemistici, dal contesto dei linguaggi logici a vincoli (CLP) a quello piu' ampio dei linguaggi dichiarativi, quali ad esempio il linguaggio Alma-0 [ADSP98,AS00];
- approfondire lo studio dei problemi connessi con la definizione e l'uso di insiemi intensionali;
- valutare l'uso dei linguaggi con insiemi e multi-insiemi in diverse applicazioni, in particolare in quelle basate su tecniche di "multiset rewriting";
- progettare e sviluppare un prototipo del nucleo di un linguaggio visuale che offra strumenti visuali di base per la definizione e manipolazione di oggetti insiemistici.

Il lavoro necessario a raggiungere gli obiettivi sopra esposti verra' svolto in piu' fasi successive in accordo con la suddivisione in fasi previste dal progetto.
La prima fase puo' essere suddivisa in piu' attivita'.
- Completare lo sviluppo del nuovo linguaggio CLP con insiemi e multi-insiemi - qui indicato col nome di {log}+. Inizialmente verra' completata la definizione e realizzazione dei risolutori di vincoli su multi-insiemi e liste; quindi si procederà ad inserirli ed integrarli nel linguaggio logico con insiemi esistente CLP(SET).
- Analizzare l'utilizzo del linguaggio {log}+ per lo sviluppo di semplici applicazioni. In particolare, analizzeremo l'adeguatezza delle varie possibilita' di rappresentazione e manipolazione di insiemi/multi-insiemi offerte da {log}+ alla formulazione di algoritmi inerenti il noto Teorema dei Quattro Colori, che verranno studiati da altri gruppi all'interno di questo progetto. Inoltre, prevediamo di confrontare il linguaggio {log}+ con il linguaggio GAMMA [BLM93], analizzando l'uso del nostro linguaggio per realizzare computazioni basate su "multiset rewriting" quali quelle previste nel cosiddetto "membrane computing" [Pau00].
- Investigare le possibilita' di "esportare" le tecniche utilizzate per la gestione di vincoli insiemistici e multi-insiemistici, e più in generale la nozione di programmazione basata su insiemi, a contesti diversi da quello strettamente CLP, soffermandoci in particolare sul linguaggio dichiarativo ALMA-0, in corso di sviluppo all'Universita' di Amsterdam.
- Iniziare lo studio ed il progetto della parte centrale di un linguaggio di programmazione visuale, fortemente basato sulla nozione di insieme (e multi-insieme) che fornisca all'utente un insieme di "facilities" visuali per la definizione di oggetti insiemistici (e multi-insiemeistici) e la loro manipolazione in accordo con un paradigma di riscrittura di insiemi/multi-insiemi. Nel progetto di questo linguaggio cercheremo di trarre vantaggio il piu' possibile dall'eseperienza maturata nello sviluppo dei linguaggi CLP con insiemi e multi-insiemi svolto in precedenza.

La seconda fase puo' essere suddivisa in tre attivita' parallele.
- Migliorare le prestazioni dell'interprete del linguaggio {log}+ con l'utilizzo e la messa a punto di sofisticati strumenti di analisi statica di programmi. In particolare si intende avvalersi dell'analizzatore per programmi CLP China, sviluppato da alcuni membri di questa Unità negli ultimi anni [Bag97]. Prima di tutto, questo strumento verra' impiegato per individuare porzioni particolarmente "critiche" nell'interprete {log}+ su cui intervenire per migliorarne l'efficienza complessiva. Quindi, si esplorera' la possibilita' di utilizzare l'analisi statica per effettuare, ove possibile, una traduzione automatica di constraint {log}+ in constraint CLP(FD) [CD93], il che dovrebbe comportare una riduzione sensibile dei tempi di esecuzione. Inoltre, si intende avvalersi del l'analisi statica di programmi in congiunzione con l'implementazione degli insiemi intensionali come descritto al punto successivo.
- Analizzare la definizione e gestione degli insiemi intensionali. Questo richiedera' di elaborare ulteriormente e raffinare la nozione di "intensional set constraint" introdotta in [CDR97]. Inoltre si intende sfruttare gli strumenti di analisi statica sopra menzionati per eseguire controlli a tempo di compilazione che, da una parte, possano garantire a priori la completezza delle computazioni effettuate e, dall'altra, possano aiutare nello selezionare la strategia di implementazione piu' adeguata per le operazioni di "set grouping" che possono essere richieste dalla valutazione di un insieme intensionale.
- Progettare un nuovo linguaggio dichiarativo con insiemi "Alma-like". Il linguaggio - che indichiamo qui con il nome di L0 - dovrebbe fornire la maggior parte degli aspetti caratterizzanti di {log}+ (specificatamente, astrazioni di aggregati di dati, quali insiemi e liste, definite sia estensionalmente che intensionalmente, constraint, computazioni non-deterministiche), ma incorporate in un ambiente piu' convenzionale, usando una sintassi e delle convenzioni Pascal-like, come avviene in Alma-0.

Nell'ultima fase l'obiettivo primario è quello di concretizzare il lavoro svolto nelle fasi precedenti. Questo puo' essere ottenuto suddividendo il lavoro da svolgere nelle seguenti azioni.
- Testare l'implementazione di {log}+ su esempi non banali.
- Implementare un semplice prototipo per il linguaggio L0. L'implementazione sara' basata su una traduzione diretta da programmi L0 a programmi {log}+, utilizzando l'interprete {log}+ per fornire l'ambiente di esecuzione dei programmi L0. Questo dovrebbe permetterci di raggiungere il nostro obiettivo in un tempo relativamente breve, sebbene rinunciando completamente a considerazioni di efficienza.
- Implementare un semplice prototipo di un linguaggio visuale con insiemi (e multi-insiemi), progettato nella prima fase. L'implementazione si focalizzera' soltanto su quella parte del linguaggio riguardante la rappresentazione e manipolazione di insiemi e multi-insiemi, assumendo di utilizzare tecniche e linguaggi convenzionali (specificatamente, Java) per rappresentare tutte quelle situazioni non direttamente esprimibili in termini di operazioni di manipolazione di insiemi/multi-insiemi. Come linguaggio di implementazione si intende avvalersi del linguaggio Java ed, in particolare, di sfruttare le possibilità di manipolazione di oggetti grafici che esso fornisce. Intendiamo anche sfruttare le possibilita' di risoluzione di vincoli fornite da {log}+ se nella progettazione del linguaggio visuale sara' possibile anche introdurre la possibilita' di definire vincoli sugli aggetti visuali che è possibile manipolare.

Testo inglese

The Unit of Parma plans to continue and deepen the researches concerned with the definition, application, and implementation of programming languages that embed the notion of set and the relevant basic set-theoretical operations. In particular we plan to address the following topics:
- enlarging our framework to different forms of data aggregates, in particular, multisets and lists;
- enhancing and optimizing the interpreter of the constraint logic programming developed so far, in particular by using static program analysis tools;
- widening the analysis of set constraint embedding, from the context of constraint logic programming (CLP) languages to the wider context of declarative languages, such as the language Alma-0 [ADSP98,AS00];
- studying problems connected with the definition and use of intensional sets;
- evaluating the use of our programming languages with sets and multisets in various applications, in particular those based on multiset rewriting techniques;
- designing and implementing the core part of a visual language that provides basic visual facilities to define and manipulate set (and multiset) objects.

The work we plan to do in order to fullfill the above mentioned goals will be organized in subsequent phases, according to the overall organization of the project.
The first phase can be split into the following subtasks.
- Completing the development of the new CLP language with sets and multisets - here named {log}+. First we shall complete the definition and implementation of the constraint solvers for multisets and lists; then we shall proceed to embed them into the existing logic language with sets CLP(SET).
- Analyzing the use of {log}+ to develop simple applications. In particular, we will analyze adequacy of the various {log}+ facilities for set/multiset representation and manipulation to describe algorithms inherent to the well-known Four-Color Theorem, which will be developed by other groups in the present project. Furthermore, we plan to compare the language {log}+ with the language GAMMA [BLM93], studying the use of our language to describe multiset rewriting-based computations, such as those required in "membrane computing" [Pau00].
- Investigating the possibility to "export" our techniques for set and multiset constraint handling to contexts other than those provided by the usual CLP scheme [JM94]. In particular we plan to focus our attention on the declarative language Alma-0, recently developed at the University of Amsterdam.
- Starting the study and design of the core part of a visual programming language, strongly based on the notion of set (and multiset), which provides the user with visual facilities for the definition of set (multiset) objects and for their manipulation, according to a set (multiset) rewriting paradigm. In the design of this language we will try to take advantage as much as possible from the experience gained in the development of the former CLP languages with sets and multisets.

The second phase can be split into three main parallel subtasks.
- Improving the {log}+ interpreter implementation by using powerful static program analysis tools. Specifically, we plan to exploit the China analyzer, a data-flow analyzer for CLP programs developed by members of this Unit during the last years [Bag97]. First of all, this tool will be used to find out "critical" portions of the {log}+ interpreter code which deserve to be modified in order to gain global efficiency. Then, it will be explored the possibility to use static analysis to perform, whenever it is feasible, automatic translation of {log}+ constraints to CLP(FD) constraints [CD93], which may result in a sensible reduction of program execution times. Furthermore, static program analysis will be exploited in conjunction with intensional set implementation as explained in the next item.
- Investigating the definition and management of intensional sets. This will require to further elaborate and refine the notion of intensional set constraints introduced in [CDR97]. Moreover we plan to exploit the above mentioned static analysis tools to perform compile-time checks which, on the one hand, may ensure "a priori" completeness of the computations carried on, and, on the other hand, may help in automatically selecting the most adequate implementation strategy for the set collection operation possibly required by the evaluation of intensional sets.
- Designing a new "Alma-like" declarative language embedding sets. The language - here named L0 - should provide most of the features of {log}+ (namely, data aggregate abstractions, such as sets and lists, both extentionally and intensionally defined, constraints, non-deterministic computations), but embedded in a more conventional framework, using Pascal-like syntax and conventions, like in Alma-0.

In the last phase, the main goal is to concretize the work done during the previous phases. This will be accomplished by splitting the work to be done into the following subtasks.
- Testing the {log}+ implementation on non-trivial applications.
- Implementing a simple prototype for the L0 language. The implementation will be based on a straightforward translation of L0 programs to {log}+ programs, using the {log}+ interpreter to provide a suitable execution environment for L0 programs. This should allow us to achieve our goal in a relatively short time, though completely ignoring efficiency matters.
- Implementing a simple prototype for the visual programming language with sets/multisets designed in the first phase. The implementation will focus on (only) that part of the language concerned with the visual representation and manipulation of sets and multisets, assuming conventional programming techniques and languages (specifically, Java) are used for expressing algorithms not directly representable in terms of set/multiset manipulation operations. We plan to use Java as the implementation language and, in particular, to exploit Java's facilities for managing graphical objects. We plan also to exploit the {log}+ constraint solving facilities if the design of the visual language will make it possible to express constraints over the visual objects it deals with.

Nº	Anno di acquisizione	Descrizione
		Testo italiano	Testo inglese

Attrezzatura I
Descrizione

valore presunto (milioni)   percentuale di utilizzo per il programma

Attrezzatura II
Descrizione

valore presunto (milioni)   percentuale di utilizzo per il programma

QUADRO RD

4.1.1 Altro

QUADRO RA

4.2.1 Altro

Firma ____________________________________________

(per la copia da depositare presso l'Ateneo e per l'assenso alla diffusione via Internet delle informazioni riguardanti i programmi finanziati; legge del 31.12.96 n° 675 sulla "Tutela dei dati personali")