Constraint handling rules. Compositional semantics and program transformation

This thesis intends to investigate two aspects of Constraint Handling Rules (CHR). It proposes a compositional semantics and a technique for program transformation. CHR is a concurrent committed-choice constraint logic programming language consisting of guarded rules, which transform multi-sets of atomic formulas (constraints) into simpler ones until exhaustion [Frü06] and it belongs to the declarative languages family. It was initially designed for writing constraint solvers but it has recently also proven to be a general purpose language, being as it is Turing equivalent [SSD05a]. Compositionality is the first CHR aspect to be considered. A trace based compositional semantics for CHR was previously defined in [DGM05]. The reference operational semantics for such a compositional model was the original operational semantics for CHR which, due to the propagation rule, admits trivial non-termination. In this thesis we extend the work of [DGM05] by introducing a more refined trace based compositional semantics which also includes the history. The use of history is a well-known technique in CHR which permits us to trace the application of propagation rules and consequently it permits trivial non-termination avoidance [Abd97, DSGdlBH04]. Naturally, the reference operational semantics, of our new compositional one, uses history to avoid trivial non-termination too. Program transformation is the second CHR aspect to be considered, with particular regard to the unfolding technique. Said technique is an appealing approach which allows us to optimize a given program and in more detail to improve run-time efficiency or spaceconsumption. Essentially it consists of a sequence of syntactic program manipulations which preserve a kind of semantic equivalence called qualified answer [Frü98], between the original program and the transformed ones. The unfolding technique is one of the basic operations which is used by most program transformation systems. It consists in the replacement of a procedure-call by its definition. In CHR every conjunction of constraints can be considered as a procedure-call, every CHR rule can be considered as a procedure and the body of said rule represents the definition of the call. While there is a large body of literature on transformation and unfolding of sequential programs, very few papers have addressed this issue for concurrent languages. We define an unfolding rule, show its correctness and discuss some conditions in which it can be used to delete an unfolded rule while preserving the meaning of the original program. Finally, confluence and termination maintenance between the original and transformed programs are shown. This thesis is organized in the following manner. Chapter 1 gives some general notion about CHR. Section 1.1 outlines the history of programming languages with particular attention to CHR and related languages. Then, Section 1.2 introduces CHR using examples. Section 1.3 gives some preliminaries which will be used during the thesis. Subsequentely, Section 1.4 introduces the syntax and the operational and declarative semantics for the first CHR language proposed. Finally, the methodologies to solve the problem of trivial non-termination related to propagation rules are discussed in Section 1.5. Chapter 2 introduces a compositional semantics for CHR where the propagation rules are considered. In particular, Section 2.1 contains the definition of the semantics. Hence, Section 2.2 presents the compositionality results. Afterwards Section 2.3 expounds upon the correctness results. Chapter 3 presents a particular program transformation known as unfolding. This transformation needs a particular syntax called annotated which is introduced in Section 3.1 and its related modified operational semantics !0t is presented in Section 3.2. Subsequently, Section 3.3 defines the unfolding rule and prove its correctness. Then, in Section 3.4 the problems related to the replacement of a rule by its unfolded version are discussed and this in turn gives a correctness condition which holds for a specific class of rules. Section 3.5 proves that confluence and termination are preserved by the program modifications introduced. Finally, Chapter 4 concludes by discussing related works and directions for future work.

Semantic coordination through programmable Tuple spaces

Two of the main features of today complex software systems like pervasive computing systems and Internet-based applications are distribution and openness. Distribution revolves around three orthogonal dimensions: (i) distribution of control|systems are characterised by several independent computational entities and devices, each representing an autonomous and proactive locus of control; (ii) spatial distribution|entities and devices are physically distributed and connected in a global (such as the Internet) or local network; and (iii) temporal distribution|interacting system components come and go over time, and are not required to be available for interaction at the same time. Openness deals with the heterogeneity and dynamism of system components: complex computational systems are open to the integration of diverse components, heterogeneous in terms of architecture and technology, and are dynamic since they allow components to be updated, added, or removed while the system is running. The engineering of open and distributed computational systems mandates for the adoption of a software infrastructure whose underlying model and technology could provide the required level of uncoupling among system components. This is the main motivation behind current research trends in the area of coordination middleware to exploit tuple-based coordination models in the engineering of complex software systems, since they intrinsically provide coordinated components with communication uncoupling and further details in the references therein. An additional daunting challenge for tuple-based models comes from knowledge-intensive application scenarios, namely, scenarios where most of the activities are based on knowledge in some form|and where knowledge becomes the prominent means by which systems get coordinated. Handling knowledge in tuple-based systems induces problems in terms of syntax - e.g., two tuples containing the same data may not match due to differences in the tuple structure - and (mostly) of semantics|e.g., two tuples representing the same information may not match based on a dierent syntax adopted. Till now, the problem has been faced by exploiting tuple-based coordination within a middleware for knowledge intensive environments: e.g., experiments with tuple-based coordination within a Semantic Web middleware (surveys analogous approaches). However, they appear to be designed to tackle the design of coordination for specic application contexts like Semantic Web and Semantic Web Services, and they result in a rather involved extension of the tuple space model. The main goal of this thesis was to conceive a more general approach to semantic coordination. In particular, it was developed the model and technology of semantic tuple centres. It is adopted the tuple centre model as main coordination abstraction to manage system interactions. A tuple centre can be seen as a programmable tuple space, i.e. an extension of a Linda tuple space, where the behaviour of the tuple space can be programmed so as to react to interaction events. By encapsulating coordination laws within coordination media, tuple centres promote coordination uncoupling among coordinated components. Then, the tuple centre model was semantically enriched: a main design choice in this work was to try not to completely redesign the existing syntactic tuple space model, but rather provide a smooth extension that { although supporting semantic reasoning { keep the simplicity of tuple and tuple matching as easier as possible. By encapsulating the semantic representation of the domain of discourse within coordination media, semantic tuple centres promote semantic uncoupling among coordinated components. The main contributions of the thesis are: (i) the design of the semantic tuple centre model; (ii) the implementation and evaluation of the model based on an existent coordination infrastructure; (iii) a view of the application scenarios in which semantic tuple centres seem to be suitable as coordination media.

Retorica come dissimulazione. Il ritmo della prosa manganelliana

La tesi è incentrata sull'analisi dell'organizzazione retorica della prosa di Giorgio Manganelli, indagando il sistema ritmico attraverso il quale l'autore è in grado di creare un fluire sintattico che sfugge alle classificazioni di genere. Per Manganelli, infatti, il linguaggio è solamente organizzazione di se stesso, e perciò la scrittura ruota attorno a un centro narrativo vuoto, dissimulando l'assenza di necessità. Egli è un retore puntuale dotato di una straordinaria abilità compositiva, che gli consente di mettere in scena l'ambiguità insita nella retorica. Per affrontare questa analisi è stato opportuno avvalersi della critique du rythme ideata da Henri Meschonnic, a partire dalle riflessioni di Emile Benveniste sul concetto eracliteo di ritmo, poiché essa fornisce una prospettiva duttile, dinamica e svincolata da pregiudizi critici. Meschonnic infatti considera il ritmo non come schema metrico ma in quanto organizzazione del senso nel discorso, volto alla signifiance del testo. In quest'ottica si è tentato di costruire un percorso attraverso le opere di Manganelli per descrivere il sistema retorico su cui si fonda la sua scrittura, a partire dai materiali del suo laboratorio (poesie, prose, appunti di diario, scambi epistolari) fino all'ideazione di discorsi pseudo-teologici che si presentano come allegoria stessa della scrittura. Si sono analizzati in particolare la trasposizione letteraria della tecnica musicale della variazione in Nuovo commento (1969), e il ritmo del periodo ipotetico in Rumori o voci (1987), testo emblematico della ricerca di Manganelli sulle potenzialità del linguaggio. Infine la prosa manganelliana è stata messa a confronto con quella di altri importanti autori italiani del Novecento (Pavese, Gadda, Camporesi, Celati), al fine di comparare tra loro diverse organizzazioni ritmiche del linguaggio, e ricollocando così Manganelli al centro del panorama letterario italiano con tutta la sua eversiva marginalità.

Semantic under-determinacy, Content and Context

The aim of the thesis is to investigate the topic of semantic under-determinacy, i.e. the failure of the semantic content of certain expressions to determine a truth-evaluable utterance content. In the first part of the thesis, I engage with the problem of setting apart semantic under-determinacy as opposed to other phenomena such as ambiguity, vagueness, indexicality. As I will argue, the feature that distinguishes semantic under-determinacy from these phenomena is its being explainable solely in terms of under-articulation. In the second part of the thesis, I discuss the topic of how communication is possible, despite the semantic under-determinacy of language. I discuss a number of answers that have been offered: (i) the Radical Contextualist explanation which emphasises the role of pragmatic processes in utterance comprehension; (ii) the Indexicalist explanation in terms of hidden syntactic positions; (iii) the Relativist account, which regards sentences as true or false relative to extra coordinates in the circumstances of evaluation (besides possible worlds). In the final chapter, I propose an account of the comprehension of utterances of semantically under-determined sentences in terms of conceptual constraints, i.e. ways of organising information which regulate thought and discourse on certain matters. Conceptual constraints help the hearer to work out the truth-conditions of an utterance of a semantically under-determined sentence. Their role is clearly semantic, in that they contribute to “what is said” (rather than to “what is implied”); however, they do not respond to any syntactic constraint. The view I propose therefore differs, on the one hand, from Radical Contextualism, because it stresses the role of semantic-governed processes as opposed to pragmatics-governed processes; on the other hand, it differs from Indexicalism in its not endorsing any commitment as to hidden syntactic positions; and it differs from Relativism in that it maintains a monadic notion if truth.

L'italiano di apprendenti lituani: elementi acquisizionali e implicazioni didattiche

La ricerca, che ha per oggetto lo studio dell’apprendimento guidato dell’italiano come lingua seconda da parte di apprendenti lituani, si articola in quattro capitoli. I primi due costituiscono il quadro teorico della ricerca, dedicando il primo ai fondamenti teorici e ricerche empiriche in generale e il secondo alle ricerche sull’apprendimento dell’italiano come L2. Nel terzo capitolo viene presentata la metodologia della ricerca, mentre nel quarto capitolo vengono presentati i risultati, concentrandosi in particolare sull’ortografia, sulla morfologia del nome, sulla categoria del verbo e sugli aspetti sintattici.In base ai risultati conseguiti, che in parte confermano i percorsi acquisizionali rilevati in contesto di apprendimento spontaneo, vengono all’ultimo suggerite alcune proposte applicative.

Knowledge Patterns for the Web: extraction, tranformation and reuse

This thesis aims at investigating methods and software architectures for discovering what are the typical and frequently occurring structures used for organizing knowledge in the Web. We identify these structures as Knowledge Patterns (KPs). KP discovery needs to address two main research problems: the heterogeneity of sources, formats and semantics in the Web (i.e., the knowledge soup problem) and the difficulty to draw relevant boundary around data that allows to capture the meaningful knowledge with respect to a certain context (i.e., the knowledge boundary problem). Hence, we introduce two methods that provide different solutions to these two problems by tackling KP discovery from two different perspectives: (i) the transformation of KP-like artifacts to KPs formalized as OWL2 ontologies; (ii) the bottom-up extraction of KPs by analyzing how data are organized in Linked Data. The two methods address the knowledge soup and boundary problems in different ways. The first method provides a solution to the two aforementioned problems that is based on a purely syntactic transformation step of the original source to RDF followed by a refactoring step whose aim is to add semantics to RDF by select meaningful RDF triples. The second method allows to draw boundaries around RDF in Linked Data by analyzing type paths. A type path is a possible route through an RDF that takes into account the types associated to the nodes of a path. Then we present K~ore, a software architecture conceived to be the basis for developing KP discovery systems and designed according to two software architectural styles, i.e, the Component-based and REST. Finally we provide an example of reuse of KP based on Aemoo, an exploratory search tool which exploits KPs for performing entity summarization.

Ricerche sul lessico della provvidenza in Agostino

Questa ricerca è un’indagine semasiologica del lessico agostiniano della provvidenza divina, costituito dalle parole-chiave prouidentia, prouideo, prouidens, prouidus, prouisio, prouisor, prouisus, e dai lessemi in relazione logico-sintattica diretta con esse. La prospettiva è sia sincronica (si considerano tutte le attestazioni delle parole-chiave presenti nel corpus agostiniano), sia diacronica: si soppesano di volta in volta analogie e differenze agostiniane rispetto agli antecedenti, nell’intento di arricchire il panorama dei possibili modelli lessicali latini (pagani, biblici, patristici) di Agostino. I dati lessicali sono stati raccolti in una banca dati appositamente costituita, selezionati secondo i criteri di frequenza e pregnanza semantica, e analizzati per nuclei tematici, coincidenti in parte con i capitoli della tesi. Si studiano dapprima i lessemi che esprimono il governo della provvidenza (le famiglie lessicali di administro, guberno e rego, e altri lessemi che designano l’azione della provvidenza); sono poi analizzati lessemi e iuncturae in cui prevale l’idea del mistero della provvidenza. Gli ultimi due capitoli sono dedicati al tema della cura divina, e a quello della cosiddetta “pedagogia divina”: attraverso i segni esteriori, la provvidenza ‘richiama’ l’uomo a rientrare in se stesso. Un’appendice approfondisce infine l’uso agostiniano di Sap 6,16 e Sap 8,1. L’apporto di Agostino al lessico filosofico latino va individuato a livello semantico più che nell’innovazione lessicale. Accanto a suffissazione, composizione, calco, la metafora svolge un ruolo essenziale nella formazione del lessico dell’Ipponate, e proviene spesso da altre lingue tecniche oppure è radicata nel patrimonio di immagini tradizionali della religione pagana. Il debito di Agostino è indubbiamente verso Cicerone, ma anche verso Seneca, per l’uso in ambito esistenziale-biografico di alcuni lessemi. Agostino li trasferisce però dal piano umano a quello divino, come nel caso del concetto di admonitio: parte integrante del programma filosofico senecano; ‘richiamo’ della provvidenza per Agostino, concetto che risente anche dell’apporto di retorica ed esegesi.