2 Programmazione web client-side 7 2.1 XML DOM . . . . 8

Indice

1 Introduzione 1

1.1 XDuce2Js . . . . 4

1.2 Organizzazione della tesi . . . . 5

2 Programmazione web client-side 7 2.1 XML DOM . . . . 8

2.2 E4X . . . 13

2.3 XSLT . . . 18

3 XDuce 25 3.1 XDuce by examples . . . 26

3.1.1 Espressioni regolari di tipo . . . 26

3.1.2 La relazione di subtyping . . . 28

3.1.3 Pattern matching . . . 29

3.1.4 XDuce: un esempio completo . . . 30

3.2 Aspetti avanzati . . . 32

3.2.1 Ancora sul pattern matching . . . 32

3.2.2 Pattern Ambigui . . . 34

3.2.3 Esaustivit`a e ridondanza . . . 36

3.2.4 Flessibilit`a rispetto ai cambiamenti . . . 37

3.2.5 Type inference . . . 40

3.2.6 Analisi statica . . . 43

3.3 La semantica formale . . . 43

3.3.1 Tipi regolari . . . 44

i

3.3.2 Patterns . . . 46

3.3.3 Termini . . . 51

3.3.4 Rappresentazione interna . . . 54

3.3.5 Attributi . . . 60

4 Xduce2Js: progettazione e realizzazione 65 4.1 Architettura software . . . 66

4.2 Overview del processo di traduzione . . . 68

4.3 Traduzione . . . 72

4.3.1 Traduzione delle definizioni di tipo . . . 72

4.3.2 Traduzione delle espressioni di tipo . . . 73

4.3.3 Traduzione delle definizioni di funzione . . . 86

4.3.4 Traduzione delle espressioni . . . 88

4.3.5 Traduzione delle dichiarazioni globali . . . 99

4.3.6 Traduzione delle dichiarazioni di namespace . . . 100

4.4 Generazione del codice . . . 100

4.4.1 Rappresentazione dei tipi di dato Ocaml . . . 102

4.4.2 Generazione del codice per le strutture dati runtime . . 107

4.4.3 Generazione del codice per le definizioni di funzione . . 110

4.5 Un esempio di compilazione . . . 119

5 Conclusioni 125

Capitolo 1 Introduzione

Negli ultimi 10 anni il web ha subito una profonda evoluzione che ha profon- damente modificato il modo stesso di intenderne la programmazione.

Se all’inizio la navigazione avveniva tra pagine statiche il cui contenuto era immutabile, oggigiorno navigando sul web ci si imbatte spesso in pagine di- namiche il cui contenuto varia in risposta a differenti contesti di valutazione.

La modifica dinamica del contenuto di una pagina pu`o avvenire server-side oppure client-side.

Nel primo caso l’interazione tra il browser ed il server web pu`o essere riassunta nel seguente modo:

1. Il browser richiede una certa pagina web.

2. Il server recupera il documento richiesto.

3. Il server esegue lo script o il programma contenuto nel documento inviando la risultante pagina HTML al browser.

4. Il browser riceve la pagina HTML e la visualizza.

L’esecuzione del codice in questo caso avviene sul server ed il risultato varia in funzione degli argomenti inviati dal browser (tipo del browser, dati inseriti dall’utente in un form, . . . ) e dello stato del server (data corrente, stato del database da interrogare, . . . ).

Nel secondo caso, invece:

1

1. Il browser richiede la pagina web.

2. Il server invia il documento richiesto al browser.

3. Il browser esegue gli scripts contenuti nella pagina modificandola in risposta ad eventi di sistema o causati dall’utente.

Da qui in avanti chiameremo pagine generate dinamicamente le prime e pa- gine dinamiche le seconde.

Ovviamente nulla vieta di avere pagine dinamiche generate dinamicamente.

Le tecniche usate per generare o modificare dinamicamente il contenuto di una pagina web pongono importanti domande sul fronte della sicurezza.

Il questo contesto per sicurezza si intende la correttezza del documento prodotto che, essendo un documento XML (XHTML), deve essere:

• Ben formato e cio`e corretto sintatticamente (es. ogni tags aperto deve essere chiuso).

• Valido rispetto ad un certo schema XML (es. una pagina XHTML deve avere una radice etichettata con il nome html con esattamente 2 figli . . . ).

Per garantire la correttezza delle pagine generate server-side sono stati fatti molti sforzi negli ultimi anni.

Il linguaggio CDuce (vedi [2] e [6]) `e un linguaggio funzionale orientato ad XML con un sistema di tipi forte che permette di rappresentare come tipi le definizioni di schema DTD oppure XML-Schema.

I valori XML sono decomposti per mezzo di un potente costrutto di pattern matching simile a quello di ML.

Nonostante CDuce non sia nato esplicitamente per la programmazione web, la sua capacit`a di trasformare documenti XHTML in maniera sicura lo ren- de adatto ad essere usato server-side (a patto di disporre di un interprete OCaml sul server) per generare dinamicamente pagine web garantendo che il tipo della pagina risultante sia quello atteso.

Molta meno attenzione finora `e stata posta sul problema della sicurezza nella

3

programmazione client-side.

Inizialmente il genere di modifiche che uno script poteva effettuare client-side si limitava alla modifica di una immagine al passaggio del mouse oppure alla validazione del contenuto di un form al momento dell’invio e poco altro.

Col tempo il numero di propriet`a del documento a cui uno script pu`o acce- dere e che possono essere modificate `e cresciuto sempre pi` u.

Nel tentativo di standardizzare tale insieme di propriet`a definendo un’inter- faccia comune a tutti i browsers fu definito il Document Object Model (DOM).

Il DOM `e indipendente dalla piattaforma e dal linguaggio usato.

Pu`o essere usato da qualunque linguaggio di programmazione come Java, Javascript o VBScript di cui esista un interprete nel browser dell’utente (ri- cordiamo che stiamo parlando di programmazione client-side).

Per la sua disponibilit`a praticamente su tutti i browsers moderni general- mente la scelta del linguaggio ricade su Javascript.

Javascript `e un linguaggio funzionale loosely-typed che a causa di alcuni aspetti linguistici (in particolare quelli legati alla possibilit`a di aggiungere o rimuovere dinamicamente propriet`a dai suoi oggetti) non permette di effet- tuare una robusta analisi statica dei programmi.

Anche i controlli effettuati dinamicamente sono pochissimi e la politica di gestione degli errori a runtime `e quella di ignorarli finch´e possibile.

Per capire il perch´e di queste scelte bisogna pensare che quando fu definito Javascript doveva servire per scrivere programmi non pi` u lunghi di qualche decina di righe che facevano cose relativamente semplici.

Al giorno d’oggi le applicazioni web come GMail o Google Map sono diven- tate molto pi` u complesse e sofisticate che in passato.

In particolare assume sempre maggiore importanza il ruolo del browser che generalmente non riceve pi` u la pagina HTML calcolata dal server, ma il suo

“contenuto informativo” in XML.

Sar`a poi compito del client presentare opportunamente i dati ricevuti calco-

lando dinamicamente la pagina HTML da visualizzare.

In questo modo:

• Si risparmia lavoro sul server.

• Si risparmia banda, perch´e il documento XML contenente i dati gene- ralmente occupa meno spazio del documento HTML prodotto alla fine della trasformazione.

Va da s´e che le righe di codice client-side tendono a moltiplicarsi rendendo sempre pi` u arduo il lavoro del programmatore Javascript.

Se la programmazione in Javascript `e un’attivit`a cos`ı incline ad errori che vanno dai banali errori sintattici, ad errori di “unbound identifier”, passando per errori di tipo, ma non si pu`o fare a meno di usare Javascript visto che

`e l’unico linguaggio supportato da tutti i browsers, perch´e non pensare di scrivere il codice in qualche altro linguaggio che permetta un’approfondita analisi statica per poi compilare il sorgente in Javascript?

1.1 XDuce2Js

Questa idea che a prima vista sembra a dir poco bizzarra `e stata recente- mente percorsa da progetti quali Google Web Toolkit ed Haxe.

Nel primo caso (vedi [8]) `e stato scelto Java come linguaggio sorgente.

In questo modo `e possibile usare tutti i tools usati in Java per scrivere, fare l’analisi statica ed il debugging dell’applicazione che in primo momento `e eseguita come un normale programma Java sulla Java Virtual Machine.

Successivamente il sorgente viene compilato in un insieme di file Javascript ed HTML che potranno essere interpretati da un normale browser.

Haxe invece (vedi [16]) `e un linguaggio object-oriented ma con un sistema di tipi forte.

Anche in questo caso il sorgente Haxe se supera l’analisi statica viene com- pilato in Javascript per poter essere interpretato da un browser.

L’idea di XDuce2Js `e esattamente la stessa di quella di Haxe o del compila-

tore di GWT, ma il linguaggio sorgente `e XDuce.

1.2 Organizzazione della tesi 5

N´e Java n´e Haxe hanno un sistema di tipi capace di rappresentare le espres- sioni regolari di tipo che sono usate nei linguaggi di schema come DTD o XML-Schema per definire l’insieme dei documenti XML validi.

Il sistema di tipi di XDuce `e stato definito con questo obiettivo.

XDuce mette inoltre a disposizione dell’utente un costrutto di pattern mat- ching simile a quello di ML molto utile nel decomporre valori XML.

1.2 Organizzazione della tesi

Il presente elaborato `e organizzato come segue; nel secondo capitolo si discu-

tono alcune delle tecnologie oggi disponibili per la trasformazione di docu-

menti XML, se ne valutano i punti di forza e le carenze; il capitolo tre descrive

il linguaggio orientato ad XML XDuce, dapprima dal punto di vista dell’u-

tente e poi pi` u formalmente; nel capitolo quattro si descrive l’architettura

software del compilatore XDuce2Js soffermandosi in particolare sul processo

di generazione del codice Javascript; il capitolo cinque conclude descrivendo

alcuni possibili sviluppi futuri del progetto.

Capitolo 2

Programmazione web client-side

Prima di descrivere nel dettaglio XDuce vediamo con qualche esempio quali sono le principali possibilit`a che ha un programmatore web che voglia trasfor- mare un documento XML client-side, i loro punti di forza e le loro carenze.

Nel seguito immagineremo di avere il seguente documento XML

<students>

<student>

<name>Giovanni Battaglia</name>

<email>gbattag@gmail.com</email>

<email>gbattag@cli.di.unipi.it</email>

</student>

<student>

<name>Rosamaria Figliuzzi</name>

<email>rosy@libero.it</email>

<tel>0932965632</tel>

</student>

</students>

che `e istanza del tipo di nodo students definito dalla seguente DTD:

<!ELEMENT students student*>

7

<!ELEMENT student (name,email*,tel?)>

<!ELEMENT name #PCDATA>

<!ELEMENT email #PCDATA>

<!ELEMENT tel #PCDATA>

La funzione da rappresentare prende in input documenti del tipo precedente e restituisce una sequenza eventualmente vuota di elementi etichettati con name il cui contenuto `e il nome di uno studente, cio`e un documento di tipo

<!ELEMENT names name*>

<!ELEMENT name #PCDATA>

Chiameremo questa funzione getNames.

Ad esempio, applicandola al documento sopra definito si otterrebbe la se- quenza

<names>

<name>Giovanni Battaglia</name>

<name>Rosamaria Figliuzzi</name>

</names>

2.1 XML DOM

L’XML Document Object Model (XML DOM) rappresenta una ma- niera standard per accedere e manipolare documenti XML.

Per essere pi` u precisi il W3C Document Object Model `e una interfaccia in- dipendente dalla piattaforma e dal linguaggio che permette ai programmi ed agli scripts di ispezionare e modificare il contenuto, la struttura e lo stile di un documento.

Il W3C DOM definisce un insieme standard di oggetti per i documenti HTML ed XML ed una interfaccia standardizzata per ispezionarli e modificarli.

Tale interfaccia `e strutturata in varie parti (Core, XML, HTML) e differenti livelli (DOM livello 1/2/3).

Le tre parti precedenti definiscono:

2.1 XML DOM 9

• Core DOM: definisce un insieme di oggetti valido per ogni documento strutturato.

• XML DOM: definisce un insieme di oggetti valido per documenti XML.

• HTML DOM: definisce un insieme di oggetti valido per documenti HTML.

Per quanto riguarda i livelli:

• Livello 0: non `e una specifica del W3C, serve solo per retro compa- tibilit`a con i vecchi browser come Netscape Navigator 3.0 ed Internet Explorer 3.

• Livello 1: si concentra sui modelli per documenti HTML ed XML definendo le funzioni di base per la loro navigazione e modifica.

• Livello 2: aggiunge lo “stylesheet object model” al livello 1 e definisce l’interfaccia per leggere e modificare tali informazioni di stile.

Definisce inoltre il modello degli eventi ed introduce il supporto per i namespaces XML.

Si suddivide in vari moduli: Core, HTML, Views, Style, Events, Traversal- Range.

• Livello 3: definisce l’interfaccia per validare un documento rispetto ad una DTD o un XML-Schema, quella per salvare, caricare e formattare un documento.

Aggiunge altri eventi a quelli definiti dal livello 2.

Si suddivide in: Core, Events, Load and Save, Views and Formatting.

Purtroppo, ogni browser implementa solo una parte di queste interfacce ed alcune piccole differenze con la specifica rendono la scrittura di codice cross- browser difficoltosa.

In generale, comunque, le funzionalit`a dei livelli 0, 1 e 2 sono supportate

da tutti i principali browsers in commercio e sono pi` u che sufficienti per la maggior parte delle applicazioni web.

Il DOM rappresenta un documento XML con una struttura ad albero i cui nodi sono elementi, attributi e nodi di testo.

Il documento del paragrafo precedente ad esempio `e rappresentato dall’albero

<students>

eeeee eeeee eeee eeeee e

Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z

<student>

jjj jjj jjj jj

T T T T T T T T T T

T <student>

jjj jjj jjj jj

T T T T T T T T T T T

<name> <email> <email> <name> <email>

“Giovanni..” “gbattag@..” “gbattag@..” “Rosamaria..” “rosy@..”

Da notare che:

1. Ogni nodo tranne la radice memorizza un riferimento al padre.

2. Ogni nodo memorizza un riferimento al fratello precedente e successivo.

Nonostante il DOM sia indipendente dal linguaggio, il requisito che il codice debba essere eseguito dal browser limita notevolmente la possibilit`a di scelta (potrei avere un binding del DOM anche per OCaml, ma non ho un inter- prete nel browser!).

Tutti i principali browsers moderni (Firefox, Internet Explorer, Safari, Ope- ra) hanno un interprete Javascript per cui questa certamente `e una alterna- tiva.

Ognuno di questi browser permette inoltre di aggiungere altri interpreti sotto forma di componenti aggiuntivi.

Java, ad esempio, seppure non supportato nativamente dai suddetti browsers

`e disponibile per ognuno di essi sotto forma di componente aggiuntivo.

Usare il DOM in Java `e completamente diverso dal farlo in Javascript.

L’interfaccia in s´e `e sempre la stessa, ma `e implementata per mezzo dei co- strutti forniti dai 2 linguaggi, per cui un oggetto del DOM `e implementato con un oggetto “dinamico” in Javascript e con un oggetto in Java.

Nonostante anche in Java siano possibili errori di tipo a runtime, l’analisi

2.1 XML DOM 11

statica permette di identificare molti errori gi`a a tempo di compilazione ri- ducendo il numero di errori a runtime.

In Javascript la possibilit`a di aggiungere o rimuovere a tempo di esecuzione le propriet`a di un oggetto (non resettare ma proprio rimuovere!) rende impos- sibile l’analisi statica ed addirittura molti errori non sono segnalati neanche a runtime: i programmi in caso di errore spesso falliscono silenziosamente rendendo difficile anche il processo di debugging.

Ma allora perch´e non definire un’applet Java all’interno della pagina HTML che sia responsabile della trasformazione dei documenti XML?

Purtroppo l’interfaccia tra Java e Javascript `e orribile e lo sviluppo di un’ap- plicazione che la usi `e una attivit`a frustrante a causa dei bugs e delle incom- patibilit`a tra i diversi browsers.

Lo stato attuale dell’implementazione (sia in IE che in Firefox) rende difficile persino creare un nuovo nodo di testo oppure modificarne uno gi`a esistente, rendendo inutilizzabile il DOM.

Per questi motivi generalmente la scelta del linguaggio client-side ricade su Javascript.

La funzione getNames in Javascript potrebbe essere scritta come:

function getNames(inDoc) {

var outDoc;

if(document.implementation && document.implementation.createDocument) {

//W3C browsers

outDoc =document.implementation.createDocument(null,null,null);

} else {

//Microsoft Internet Explorer

outDoc =new ActiveXObject("MSXML2.DOMDocument");

}

//seleziona tutti gli elementi <name> del doc in input

var rootNode =inDoc.documentElement;

var nameNodes =rootNode.getElementsByTagName("name");

//aggiunge <names> al doc da restituire var namesNode =outDoc.createElement("names");

outDoc.appendChild(namesNode);

var tmpNode;

for(var i=0;i <nameNodes.length;i++) {

tmpNode =nameNodes[i].cloneNode(true);

namesNode.appendChild(tmpNode);

}

return outDoc;

}

L’if iniziale serve per creare il nuovo documento XML da restituire.

Nonostante gli sforzi di standardizzazione del W3C, codice condizionale co- me il precedente abbonda nella programmazione web.

Il test controlla se la funzione createDocument prevista dalla specifica del DOM risulta definita.

In questo caso la si usa per creare il nuovo documento XML da restituire.

In caso contrario vuol dire che siamo in Internet Explorer, per cui si crea un

nuovo documento per mezzo del costruttore ActiveXObject(MSXML2.DOMDocument).

A questo punto si selezionano tutti i discendenti della radice etichettati con

<name> per mezzo della funzione getElementsByTagName che restituisce l’ar- ray di nodi nameNodes.

Dopo aver creato l’elemento radice <names> ed averlo aggiunto al documen- to da restituire, invocando cloneNode si clona ogni nodo di nameNodes e lo aggiunge come figlio di <names> per mezzo della funzione appendChild.

I principali problemi legati alla manipolazione del DOM in Javascript riguar- dano l’espressivit`a e la sicurezza.

Il codice precedente, nonostante siano stati omessi alcuni controlli dinamici

2.2 E4X 13

come quello per controllare che il valore in input non sia nullo, `e abbastanza prolisso.

L’accesso ai figli di un nodo avviene accedendo alla propriet`a childNodes e quello agli attributi per mezzo di opportuni metodi.

Anche la costruzione dei nuovi documenti XML implica la creazione del no- do radice e l’aggiunta di ogni singolo nodo con l’applicazione della funzione appendChild.

Osserviamo inoltre che l’argomento in input non ha un tipo (n´e esplicitamen- te annotato, n´e inferito) e neanche il risultato in output.

Non si pu`o quindi in alcun modo garantire che la funzione restituisca un documento valido rispetto allo schema

<!ELEMENT names name*>

<!ELEMENT name #PCDATA>

2.2 E4X

ECMAScript for XML (E4X) `e una estensione di Javascript che aggiunge supporto nativo per XML fornendo una sintassi e dei costrutti alternativi al DOM per ispezionare e modificare i documenti XML.

Nonostante al momento questa estensione sia scarsamente supportata (solo l’interprete Javascript di Firefox la implementa) vale la pena di presentarla brevemente per fare vedere come si possano facilmente superare i limiti di espressivit`a imposti dal DOM (come vedremo, non altrettanto si pu`o fare sotto il profilo della sicurezza).

In E4X gli elementi XML diventano parte della sintassi permettendo di scrivere

var s1 =<student>

<name>Giovanni Battaglia</name>

</student>;

dove la variabile s1 memorizza un valore XML.

Tali valori non sono dei nodi del DOM validi, ma sono fornite delle funzioni

per convertire nodi del DOM in valori XML E4X e viceversa.

L’obiettivo di E4X `e quello di fornire un’alternativa alle funzioni del DOM, ma molte di queste hanno un funzione E4X corrispondente con lo stesso nome, per cui si pu`o ad esempio scrivere

var s1 =<student/>;

var n =<name/>;

s1.appendChild(n);

Il vero potenziale di E4X risiede per`o nella sua capacit`a di interagire stret- tamente con Javascript.

Grazie alla notazione {} `e possibile assegnare il risultato della valutazione di una espressione Javascript al valore di un elemento E4X come in

var s =<student>{Math.abs(x-y)}<student/>;

Cos`ı come gli operatori . e [] sono usati in Javascript per selezionare le propriet`a degli oggetti, in E4X gli stessi operatori permettono di accedere ai nodi figli di un certo elemento XML.

Ad esempio

var s =<student>

<name/>

</student>;

var elem =<email/>;

s.name.appendChild(elem);

s["name"].appendChild(<email2/>);

aggiunge due figli all’elemento <name/> modificando s in

<student>

<name>

<email/>

<email2/>

</name>

</student>

Come per le propriet`a di un oggetto Javascript, assegnando un valore non

XML ad un elemento figlio che non esiste si crea tale elemento, quindi

2.2 E4X 15

var s =<student/>;

s.name ="Giovanni";

assegna ad s il valore

<student>

<name>Giovanni</name>

</student>

Se invece il nodo esiste si cambia il suo valore var s =<student>

<name>Giovanni</name>

</student>;

s.name ="Rosy";

modifica il valore di s in

<student>

<name>Rosy</name>

</student>

L’operatore delete `e usato in Javascript per rimuovere le propriet`a di un oggetto ed in E4X per rimuovere un nodo figlio come ad esempio in

var s =<student>

<name/>

<email/>

</student>;

delete s.name;

che modifica s in

<student>

<email/>

</student>

Se l’espressione a destra dell’uguale `e valutata in un elemento XML, il sot-

toalbero a sinistra viene sostituito con il nuovo valore

var s =<students>

<student/>

</students>;

s.students.student =<student>

<name/>

<email/>

</student>;

modifica il contenuto di s in

<students>

<student>

<name/>

<email/>

</student>

</students>

In molti casi un nodo ha pi` u figli etichettati con lo stesso nome come in var s =<student>

<name/>

<email/>

<email/>

</student>;

In questo caso l’espressione s.email verr`a valutata in una lista di valori XML.

Tali liste sono molto simili agli array Javascript (in particolare sono 0-based) per cui nel caso precedente si sarebbe potuto selezionare il primo elemento

<email> scrivendo s.email[0]

E importante sottolineare che `e responsabilit`a del programmatore determi- `

nare se il risultato dell’applicazione dell’operatore . `e un elemento XML

oppure una lista di elementi: nessun controllo viene fatto dal linguaggio n´e

staticamente n´e dinamicamente.

2.2 E4X 17

La selezione del valore di un attributo di un elemento `e effettuato con l’ope- ratore .@.

Tale valore pu`o poi essere modificato con un normale assegnamento come ad esempio in

var s =<student age="23" />

s.@id =18;

E4X definisce anche l’operatore .. per selezionare un elemento che non `e il figlio del nodo considerato, ma si trova ad una maggiore profondit`a.

Ad esempio

var s =<people>

<students>

<giovanni age="23"/>

<rosy age="22"/>

</students>

</people>;

s..giovanni.@age =24;

s..rosy.@age =23;

cambia l’et`a di entrambi gli studenti.

L’operatore * permette di selezionare tutti i figli di un elemento XML e pu`o essere combinato con un predicato che funge da filtro come in

var s =<students>

<student age="23"/>

<student age="22"/>

<student age="22"/>

</students>;

var list =s.*.(@age ==22);

dove s.* restituisce la lista contenente tutti i figli di <students>, mentre il predicato (@age ==22) seleziona solo gli studenti di 22 anni.

Usando E4X la funzione getNames del paragrafo precedente pu`o essere scritta

come:

function getNames(xmlDoc) {

return <names>{xmlDoc..name}</names>;

}

dove il contenuto dell’elemento <names> restituito `e la lista dei nodi <name>

contenuti del documento in input.

La semplicit`a con cui E4X permette di definire trasformazioni complesse in maniera concisa `e incredibile.

I problemi relativi alla sicurezza invece restano tutti.

Come accennato prima, `e responsabilit`a del programmatore nel caso di una espressione come xmlDoc..name la gestione del caso in cui il risultato sia un valore XML e quello in cui sia una lista di valori (eventualmente vuota!).

Tutti i problemi di sicurezza di Javascript sono ereditati da E4X che altro non `e che una estensione del linguaggio.

Si pu`o quindi concludere che E4X migliora certamente l’espressivit`a di Java- script per quanto riguarda la trasformazione di valori XML, ma non risolve i problemi relativi alla sicurezza.

2.3 XSLT

Un’altra possibile alternativa per trasformare un documento XML `e quella di usare uno stylesheet XSLT.

XSLT `e acronimo di “Extensible Stylesheet Language Transformation” ed `e un linguaggio usato per trasformare un documento XML in un altro.

Molte applicazioni web usano XSLT server-side per trasformare un docu- mento XML risultante dall’interrogazione di un database in un documento XHTML da inviare al browser che lo ha richiesto.

Lo svantaggio di questo approccio `e che il processing del documento XML `e

a carico del server e che ad essere inviato al browser non `e pi` u il contenuto in-

formativo della pagina da visualizzare, ma la pagina stessa che generalmente

2.3 XSLT 19

ha dimensioni maggiori.

Oggigiorno sia Internet Explorer che Firefox supportano XSLT client-side permettendo al server di risparmiare cpu e banda.

Lo stylesheet che rappresenta la trasformazione getNames potrebbe essere il seguente:

<?xml version="1.0"?>

<xsl:stylesheet

xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">

<xsl:output method="xml" indent="yes"/>

<xsl:template match="/">

<names>

<xsl:apply-templates select="./students/student/name"/>

</names>

</xsl:template>

<xsl:template match="name">

<name>

<xsl:value-of select="."/>

</name>

</xsl:template>

</xsl:stylesheet>

La prima cosa da notare `e che un XSLT stylesheet `e un documento XML ben formato come ci ricorda la riga iniziale

<?xml version="1.0"?>

Questa scelta a prima vista pu`o sembrare un po’ svantaggiosa in quanto ren- de il codice prolisso dovendolo scrivere nella sintassi di XML.

Il vantaggio `e che per fare il parsing di uno stylesheet come il precedente

basta un parser XML e non ne serve uno ad hoc per la sintassi del nuovo

linguaggio.

La radice del documento `e l’elemento <xsl:stylesheet> che dichiara il na- mespace xsl a cui apparterranno i tags di XSLT necessari per descrivere la trasformazione.

L’elemento

<xsl:output method="xml" indent="yes"/>

definisce il formato del documento in output.

L’attributo method dichiara che il documento in output in questo caso `e un documento XML, ma potrebbe anche essere un documento HTML oppure un semplice file di testo.

I due successivi elementi <xsl:template> definiscono l’insieme di regole che descrivono la trasformazione vera e propria.

Una trasformazione in XSLT `e infatti definita da un insieme di regole ciascu- na delle quali formata da un pattern che `e una espressione XPath che verr`a confrontato con i nodi del documento sorgente ed un template che verr`a istan- ziato qualora si trovi un nodo accettato dal pattern, formando un frammento del risultato.

XPath `e un semplice linguaggio che permette di riferire gli elementi di un documento, i loro attributi ed il loro contenuto.

Una espressione XPath pu`o selezionare un elemento XML in base alla sua posizione nella struttura ad albero del documento oppure in base al valore (o alla presenza) di un attributo.

Una discussione approfondita di XPath `e oltre gli scopi di questo capitolo, ma per avere un’idea del linguaggio vediamo qualche semplice esempio.

Una espressione XPath `e sempre valutata a partire da un contesto costituito da uno dei nodi del documento.

La pi` u semplice espressione XPath indica semplicemente il nome del tag degli elementi da selezionare per cui l’espressione

name

`e valutata nell’insieme di tutti gli elementi <name> che appartengono al sottoalbero radicato nel context node, mentre

name[1]

2.3 XSLT 21

seleziona il primo di tali nodi (XPath `e 1-based).

La parola “path” contenuta nel nome si riferisce al fatto che il linguaggio con- sidera i livelli dell’albero che descrive un documento XML come directories di un filesystem usando il carattere / per separare i livelli della gerarchia.

L’espressione /

indica la radice del documento, mentre /students/student

seleziona tutti gli elementi <student> che sono figli dell’elemento <students>

che `e figlio della radice del documento.

Il punto . in una espressione XPath si riferisce al context node, mentre un doppio slash // permette di ignorare i livelli della gerarchia riferendosi ad ogni discendente invece che solo ai figli di un nodo, per esempio

.//name

seleziona tutti gli elementi <name> discendenti del context node.

Il simbolo @ `e usato per identificare un nome di attributo, per cui

@id

seleziona il valore dell’attributo id del context node, mentre students/@id

il valore dell’attributo id del figlio <students>.

Il valore di un attributo pu`o essere usato per filtrare l’insieme degli elementi risultante dalla valutazione di una espressione, come nel caso di

student[@id="257967"]

che seleziona tutti gli elementi <student> figli del context node con un at- tributo id avente valore 257967.

Concludiamo questa breve carrellata discutendo come verrebbe valutato lo

stylesheet che rappresenta la funzione getNames se il documento in input

fosse

<students>

<student>

<name>Giovanni Battaglia</name>

<email>gbattag@gmail.com</email>

<email>gbattag@cli.di.unipi.it</email>

</student>

<student>

<name>Rosamaria Figliuzzi</name>

<email>rosy@libero.it</email>

<tel>0932965632</tel>

</student>

</students>

Il context node iniziale `e un nodo fittizio che funge da radice e che ha come unico figlio <students>.

L’interprete XSLT cerca tra le regole dello stylesheet una che accetti il context node corrente (nel caso in cui pi` u regole accettino il context node verr`a scelta la pi` u specifica).

In questo caso viene scelta

<xsl:template match="/">

<names>

<xsl:apply-templates select="./students/student/name"/>

</names>

</xsl:template>

che ha come pattern / che accetta proprio il nodo radice.

L’elemento <name> siccome non `e qualificato da alcun namespace `e riscritto in output inalterato e la valutazione prosegue valutando

<xsl:apply-templates select="./students/student/name"/>

L’espressione XPath che costituisce il valore dell’attributo select viene va- lutata nella lista di tutti gli elementi etichettati con name che sono figli di uno studente che `e figlio dell’elemento students che `e figlio del nodo corrente.

Ad ognuno di questi elementi (seguendo l’ordine in cui compaiono nella lista)

2.3 XSLT 23

si tenter`a di applicare una delle regole dello stylesheet e si concateneranno i risultati.

L’unica regola che si pu`o applicare `e la seconda e cio`e

<xsl:template match="name">

<name>

<xsl:value-of select="."/>

</name>

</xsl:template>

che restituisce un elemento <name> con dentro il contenuto del context node (restituisce cio`e una copia dell’elemento <name> in input).

Alla fine il documento restituito in output `e

<names>

<name>Giovanni Battaglia</name>

<name>Rosamaria Figliuzzi</name>

</names>

Rispetto all’approccio che usa il DOM, XSLT ha uno stile maggiormente dichiarativo usando delle concise espressioni XPath per selezionare elementi ed attributi ed una sorta di costrutto di pattern matching per decomporre il documento in input.

Anche in questo caso per`o il problema principale resta la sicurezza.

Nonostante siano disponibili alcuni prototipi in grado di tipare una trasfor-

mazione scritta usando un sottoinsieme di XSLT (si vedano [17] e [18]) la

validazione di una generica trasformazione XSLT resta ancora un problema

non del tutto risolto.

Capitolo 3

XDuce

Scopo di questo capitolo `e quello di presentare le caratteristiche fondamentali di XDuce.

Dapprima saranno presentati alcuni semplici esempi di espressioni regolari di tipo e pattern matching di espressioni regolari.

Il secondo paragrafo approfondisce gli esempi precedenti discutendo pi` u nel dettaglio la semantica dei patterns, introducendo i problemi della esaustivit`a e della non ridondanza.

Infine si mostrer`a la semantica formale dei tipi, dei pattern e delle espressio- ni.

Questo capitolo non pretende di essere esaustivo, ma vuole solo fornire al lettore i concetti fondamentali per poter leggere e capire i programmi scritti in XDuce.

Per fare ci`o `e necessaria una comprensione di base dei tipi, dei patterns e della funzione di valutazione semantica del linguaggio.

Per motivi di spazio non si descriveranno nel dettaglio l’algoritmo di subty- ping e quello di type inference, chi volesse approfondire pu`o consultare [14]

e [15].

25

3.1 XDuce by examples

3.1.1 Espressioni regolari di tipo

Le espressioni regolari di tipo sono un type system basato sui linguaggi di schema per XML che descrive tipi XML usando espressioni regolari (ed i classici operatori di concatenazione, unione, stella di Kleene), supportando una nozione di semantic subtyping, che rende flessibili i programmi rispetto a cambiamenti dei tipi.

Il pattern matching di espressioni regolari `e una estensione di quello di ML che usa espressioni regolari di tipo per decomporre a runtime valori XML.

Consideriamo il seguente documento XML:

<students>

<student>

<name>Giovanni Battaglia</name>

<email>gbattag@gmail.com</email>

<email>gbattag@cli.di.unipi.it</email>

</student>

<student>

<name>Rosamaria Figliuzzi</name>

<email>rosy@libero.it</email>

<tel>0932965632</tel>

</student>

</students>

Nella sintassi XML un nodo `e rappresentato da un tag di apertura <label>

e dal corrispondente tag di chiusura </label>.

I figli del nodo sono contenuti all’interno dei tags.

In questo caso il nodo radice `e etichettato students e contiene una sequenza di 2 nodi con etichetta student.

Il primo student contiene una sequenza formata da un elemento name, se- guito da 2 elementi email.

Il secondo student contiene una sequenza il cui primo elemento `e etichettato

3.1 XDuce by examples 27

name, il secondo email ed il terzo tel.

Ognuno dei nodi name, email e tel contiene una stringa ma nulla vieta di avere un albero arbitrariamente profondo, come ad esempio:

<tel>

<prefix>0932</prefix>

<num>965630</num>

</tel>

Il documento XML dell’esempio precedente `e una istanza del tipo di nodo students definito nella seguente DTD

<!ELEMENT students student*>

<!ELEMENT student (name,email*,tel?)>

<!ELEMENT name #PCDATA>

<!ELEMENT email #PCDATA>

<!ELEMENT tel #PCDATA>

Ogni riga dichiara il tipo del contenuto di un tag.

Ognuno di questi tipi `e specificato da una espressione regolare di tags.

La prima riga dichiara che students contiene zero o pi` u ripetizioni (*) di nodi con etichetta student.

Analogamente la seconda riga dichiara che student contiene una sequenza il cui primo elemento `e un name node, seguito da zero o pi` u ripetizioni di nodi email e da un nodo tel che pu`o anche non essere presente (?).

Ogni nodo name, email e tel contiene un valore di tipo #PCDATA (una stringa nella sintassi DTD).

Riscrivendo le precedenti dichiarazioni DTD con espressioni regolari di tipo otteniamo (nella sintassi di XDuce)

type Students = students[Student*]

type Student = student[Name,Email*,Tel?]

type Name = name[String]

type Email = email[String]

type Tel = tel[String]

I costruttori di tipo della forma label[...] classificano nodi con l’etichetta label (valori XML della forma <label>...</label>).

I tipi Name, Email, Tel denotano insiemi di valori etichettati con name, email, tel il cui contenuto `e una stringa.

Per definire nuovi tipi si possono, inoltre, usare gli operatori classici delle espressioni regolari su stringhe: * (ripetizione), ? (occorrenza opzionale) e | (altenatore).

Nell’esempio precedente il tipo Students descrive valori di etichetta students contenenti zero o pi` u ripetizioni di sottoalberi di tipo Student.

Il tipo Student descrive valori di etichetta student che contengono un sot- toalbero di tipo Name, zero o pi` u sottoalberi di tipo Email ed opzionalmente un sottoalbero di tipo Tel.

3.1.2 La relazione di subtyping

Ogni tipo in XDuce denota un insieme di sequenze.

La relazione di subtyping indica semplicemente l’inclusione tra gli insiemi di valori denotati dai 2 tipi in relazione, cio`e s `e in relazione con t se e solo se l’insieme dei valori che s denota `e incluso (non strettamente) in quello denotato da t.

Per esempio, consideriamo il tipo Student definito prima ed il tipo seguente:

type Student2 = student[Name,Email*,Tel*]

Student denota valori con al pi` u un sottoalbero di tipo Tel, mentre Student2 denota valori con un numero arbitrario di numeri di telefono.

Ogni valore di tipo Student `e anche valore di tipo Student2 per cui il primo

`e sottotipo del secondo.

Questa relazione di subtyping, come accennato prima, pu`o rendere i pro-

grammi flessibili rispetto a cambiamenti di tipo, infatti anche modificando

la definizione del tipo Student con quella di Student2 non `e necessario ap-

portare alcun cambiamento al programma in quanto ogni espressione di tipo

3.1 XDuce by examples 29

Student `e anche di tipo Student2.

3.1.3 Pattern matching

Il pattern matching di espressioni regolari pu`o essere visto come una esten- sione del pattern matching di ML che usa espressioni regolari di tipo per decomporre a runtime valori XML.

Usando i tipi definiti nel paragrafo 3.2.1 si pu`o scrivere la seguente espres- sione di pattern matching che dato un valore s di tipo student testa se t contiene un elemento Tel ed in questo caso estrae il contenuto degli elementi Name e Tel.

match s with

student[name[val n],Email*,tel[val t]]

->(*usa n e t*)

| student[val s]

->(*usa s*)

La prima clausola accetta un nodo etichettato student il cui contenuto `e una sequenza formata da un elemento Name, zero o pi` u Emails ed un elemento Tel.

In questo caso la variabile di cattura n sar`a legata al contenuto dell’elemento Name e la variabile t al contenuto dell’elemento Tel.

La seconda clausola accetta un valore etichettato con student legando la variabile s al suo contenuto.

Il pattern matching di XDuce implementa una politica first-match risolven- do eventuali ambiguit`a dando maggiore priorit`a alle clausole che appaiono prima.

Da notare come la prima clausola usi il tipo Email* per saltare una sequenza di lunghezza arbitraria (eventualmente vuota) di emails ed estrarre il valore di tipo Tel che la segue.

Per supportare il costrutto di pattern matching in un linguaggio di program-

mazione staticamente tipato `e importante che il compilatore sia capace di

inferire il tipo di quante pi` u variabili di cattura possibile riducendo il nume- ro di asserzione di tipo richieste all’utente.

L’algoritmo usato per inferire il tipo delle variabili di cattura in una espres- sione di pattern matching assume che sia noto il tipo del valore in input, calcolando ricorsivamente i tipi dei sotto-patterns.

Consideriamo di nuovo l’espressione precedente.

Dato in input il tipo Student, l’algoritmo di type inference calcola il tipo String per le variabili n e t ed il tipo (Name,Email*) per la variabile s.

Si osservi che il tipo inferito per s non `e (Name,Email*,Tel) perch´e la po- litica di first-match assicura che tutti i valori di tipo Student con un valore di tipo Tel siano catturati dalla prima clausola per cui solo quelli senza un numero di telefono verranno confrontati con la seconda.

3.1.4 XDuce: un esempio completo

Un tipico programma XDuce `e formato da un insieme di definizione di tipo mutuamente ricorsive, da un insieme di funzioni mutuamente ricorsive e da una query che generalmente consiste nell’applicazione di una funzione.

Il seguente programma calcola la sequenza di nomi che compaiono nel docu- mento di tipo Students in input:

type Students = students[Student*]

type Student = student[Name,Email*,Tel?]

type Name = name[String]

type Email = email[String]

type Tel = tel[String]

fun getNames (val students as Students) : names[Name*] = names[getNames1(students)]

fun getNames1 (val students as Students) : Name* =

match students with

3.1 XDuce by examples 31

students[student[name[val n],Email*,Tel?],val rest]

->name[n],getNames1(students[rest])

| students[()]

->()

let val inValue = students[

student[

name["Giovanni Battaglia"], email["gbattag@gmail.com"], email["gbattag@cli.di.unipi.it"]

],

student[

name["Rosamaria Figliuzzi"], email["rosy@libero.it"], tel["0932965632"]

] ]

let val names =getNames(inValue)

Le prime righe contengono le definizioni dei tipi che saranno usati nelle espres- sioni successive.

Il corpo della funzione getNames1 usa il pattern matching per analizzare per casi il valore del parametro students.

Se l’etichetta students contiene una sequenza non vuota di studenti, si estrae il nome del primo studente della sequenza e lo si aggiunge in cima alla se- quenza restituita dalla chiamata ricorsiva della funzione getNames1.

Se, invece, students contiene una sequenza vuota, la funzione restituisce la sequenza vuota.

La funzione getNames restituisce un nuovo elemento names contenente la se- quenza dei nomi calcolati dalla funzione getNames1.

La dichiarazione top-level successiva lega alla variabile globale inValue il

valore XML dell’esempio del paragrafo 3.1.1 riscritto nella sintassi di XDuce.

La query finale applica la funzione getNames ad inValue legando alla varia- bile globale names il risultato.

3.2 Aspetti avanzati

Nei paragrafi precedenti abbiamo familiarizzato con il costrutto di pattern matching.

Analizziamolo adesso nel dettaglio, discutendo i problemi relativi all’am- biguit`a dei patterns, all’esaustivit`a ed alla ridondanza delle clausole e le soluzioni adottate da XDuce.

3.2.1 Ancora sul pattern matching

Consideriamo ancora i tipi

type Students = students[Student*]

type Student = student[Name,Email*,Tel?]

type Name = name[String]

type Email = email[String]

type Tel = tel[String]

e la seguente espressione di pattern matching:

match s with

student[name[val n],tel[val t]]

->...

| student[name[val n],val rest]

->...

Come sappiamo, la prima clausola accetta valori etichettati con student il

cui contenuto `e una sequenza di lunghezza due il cui primo elemento `e di

tipo Name ed il secondo `e di tipo Tel.

3.2 Aspetti avanzati 33

In caso di successo viene calcolato un ambiente in cui la variabile n sar`a legata al contenuto dell’elemento name e la variabile t al contenuto dell’elemento tel.

La seconda clausola accetta valori etichettati con student il cui contenuto `e una sequenza avente come testa un elemento di tipo Name e come coda una sequenza eventualmente vuota di emails seguita da zero o un tel.

In realt`a, come si vedr`a meglio in seguito, il pattern matching di XDuce usa una politica first-match per cui la seconda clausola verr`a usata solo se il valore in input non `e accettato dal primo pattern, per cui la variabile di cattura rest potr`a essere legata alla sequenza vuota, ad una sequenza non vuota contenente solo emails oppure ad una sequenza non vuota di emails seguita da un numero di telefono, ma non alla sequenza contenente solo un numero di telefono, perch´e questo valore sarebbe stato gi`a catturato dal primo pattern.

I patterns in XDuce possono anche contenere espressioni regolari di tipo, come nel seguente esempio:

match s with

student[name[val n],val e as Email*,tel[val t]]

->...

| student[name[val n],val e as Email*]

->...

Qui, nella prima clausola la variabile di cattura e viene legata alla sequenza di zero o pi` u emails tra name e tel.

In generale, un “as pattern” della forma x as P decompone il valore in input usando il pattern P (che potrebbe contenere altre variabili di cattura) e lega x all’intera sequenza accettata da P.

Il pattern (e as Email*) mette inoltre in evidenza una differenza sostan- ziale tra il pattern matching di ML e quello di XDuce.

Quando la funzione di pattern matching interpreta il pattern (e as Email*) non `e noto quante emails siano presenti nel valore in input.

Occorre scandire la sequenza in input finch`e non si trovi l’ultima email, la

cui posizione non `e nota staticamente.

Questo comportamento iterativo permette il matching di sequenze di lun- ghezza arbitraria andando oltre le capacit`a del pattern matching di ML.

3.2.2 Pattern Ambigui

In XDuce, nonostante il pattern matching calcoli un unico binding per ogni variabile di cattura che compare nel pattern, sono consentiti pattern ambi- gui, cio`e che possono decomporre il valore in input in pi` u modi, generando bindings diversi.

Tale ambiguit`a non `e risolta staticamente rigettando i patterns ambigui, ma adottando la politica first-match per il pattern matching.

I pattern possono presentare due tipi diversi di ambiguit`a.

Il primo tipo di ambiguit`a si ha quando due o pi` u patterns accettano lo stesso valore in input.

Ad esempio in

match s with

student[name[val n],tel[val t]]

->...

| student[name[val n],val rest]

->...

i due patterns sono ambigui perch´e ogni valore accettato dal primo `e accet- tato anche dal secondo.

In questo caso la politica di first-match impone di scegliere il primo.

Questa politica (identica a quella di ML) rende semplice la scrittura di un caso di default come ultima clausola di un pattern matching, mentre, imporre che l’insieme dei patterns debba essere non ambiguo imporrebbe di scrivere una clausola finale che accetti solo i valori non accettati dai patterns prece- denti.

La seconda forma di ambiguit`a si ha quando un singolo pattern pu`o decom-

3.2 Aspetti avanzati 35

porre il valore in input in differenti modi.

E questo il caso della seguente espressione `

match e with

e1 as Email*,e2 as Email*

->...

in cui si assume che e abbia tipo Email*.

Il pattern decompone la sequenza in input in due, ma non `e chiaro quante emails debbano far parte della prima sottosequenza e quante della seconda.

Se, ad esempio, il valore in input fosse email["gbattag@gmail.com"], email["rosy@libero.it"]

l’ambiente risultante potrebbe essere

{e1 =email["gbattag@gmail.com"],email["rosy@libero.it"] , e2 =()}

oppure

{e1 =email["gbattag@gmail.com"] , e2 =email["rosy@libero.it"]}

oppure

{e1 =() , e2 =email["rosy@libero.it"],email["gbattag@gmail.com"]}

XDuce risolve questa ambiguit`a adottando una politica longest-match: i pat- terns che appaiono prima hanno maggiore priorit`a.

In questo caso quindi l’ambiente risultante sar`a

{e1 =email["gbattag@gmail.com"],email["rosy@libero.it"] , e2 =()}

Sebbene la politica first-match e quella longest-match a prima vista sembrino

del tutto scorrelate, la sezione 3.3.2 mette in evidenza come la seconda derivi

in maniera naturale dalla prima.

3.2.3 Esaustivit` a e ridondanza

XDuce supporta gli abituali controlli statici per assicurare l’esaustivit`a e la non ridondanza di ogni espressione di pattern matching.

Un pattern matching `e esaustivo se ogni valore in input `e accettato da almeno uno dei patterns.

Una clausola `e ridondante se ogni valore da essa accettato lo `e anche da qualche altra clausola che la precede.

Consideriamo la seguente espressione che data una sequenza di Student trova il primo studente con un numero telefonico e ne estrae il nome ed il numero di telefono.

match s with

student[Name,Email*],student[name[val n],Email*,tel[val t]], val rest

->...

| student[Name,Email*]*

->...

Assumendo che s sia di tipo Student* il pattern matching `e intuitivamente esaustivo perch´e la prima clausola cattura le sequenze contenenti almeno uno studente con un numero di telefono (la variabile di cattura rest potrebbe catturarne delle altre!), mentre la seconda cattura le sequenze che non con- tengono studenti con un numero di telefono.

La seconda clausola non `e ridondante in quanto le sequenze che non con- tengono nessuno studente con un numero di telefono non sono catturate dal primo pattern.

Per effettuare questo genere di controlli `e necessario ricondursi ai problemi

di inclusione, intersezione e complementazione di linguaggi regolari di alberi,

come descritto nella sezione 3.3.4.

3.2 Aspetti avanzati 37

3.2.4 Flessibilit` a rispetto ai cambiamenti

Uno dei principali usi di XML `e quello di rappresentare e trasmettere data- bases.

Per questo motivo un linguaggio orientato ad XML deve minimizzare le mo- difiche necessarie ai programmi (in particolare alle annotazioni di tipo) a seguito di modifiche del database o qualora si vogliano integrare i contenuti di due o pi` u databases diversi.

Consideriamo l’esempio del paragrafo 3.1.4 in cui si erano definiti i seguenti tipi:

type Students = students[Student*]

type Student = student[Name,Email*,Tel?]

type Name = name[String]

type Email = email[String]

type Tel = tel[String]

ed immaginiamo di modificare il database aggiungendo uno Student con pi` u di un numero di telefono, come nel seguente esempio

students[

student[

name["Giovanni Battaglia"], email["gbattag@gmail.com"], email["gbattag@cli.di.unipi.it"]

],

student[

name["Rosamaria Figliuzzi"], email["rosy@libero.it"], tel["0932965632"]

tel["0932721456"]

] ]

che chiameremo database B.

Questo cambiamento si ripercuote sia sulle definizione dei tipi che su quelle

delle funzioni del programma XDuce.

Le modifiche ai tipi riguardano solo Student, che adesso deve permettere ad ogni studente di avere un numero arbitrario di elementi di tipo Tel e che diventa:

type Student = student[Name,Email*,Tel*]

In questo modo il nuovo tipo del contenuto di Student `e (Name,Email*,Tel*)

che `e supertipo di quello vecchio (Name,Email*,Tel?)

per cui anche il tipo Students dell’intero database diventa un supertipo di quello vecchio.

Questo significa che il vecchio database del paragrafo 3.1.4 `e anche valore del nuovo tipo Students.

Per quanto riguarda la modifica delle funzioni, siccome il nuovo tipo `e su- pertipo di quello vecchio, tutte le funzioni che lo hanno come tipo di output Students non necessitano di alcuna modifica, mentre quelle che lo hanno in input devono essere modificate in maniera da considerare i casi aggiuntivi.

In questo caso la funzione getNames1 diventa:

fun getNames1 (val students as Students) : Name* = match students with

students[student[name[val n],Email*,Tel*],val rest]

->name[n],getNames1(students[rest])

| students[()]

->()

dove nella prima clausola del pattern matching Tel? `e stato sostituito da Tel*.

Il type system di XDuce permette di integrare in maniera semplice due o pi` u

3.2 Aspetti avanzati 39

databases.

Proviamo, ad esempio, ad integrare il database B con un altro database C in cui ogni studente invece di avere zero o pi` u elementi di tipo Tel ha una sequenza eventualmente vuota di MobilePhone.

Si assuma che il tipo di C sia:

type Students2 = students[Student2*]

type Student2 = student[Name,Email*,MobilePhone*]

type Name = name[String]

type Email = email[String]

type MobilePhone = mobilePhone[String]

L’integrazione tra i databases B e C avviene costruendo un albero la cui radice `e etichettata da students ed il cui contenuto `e la concatenazione del contenuto dei due databases.

Il tipo risultante quindi dovrebbe essere

type Students = students[Student*,Student2*]

In questo modo per riscrivere la funzione getNames1 il tipo Students sopra definito renderebbe necessari due differenti “loops”: uno per estrarre i nomi della sequenza iniziale di Student ed il secondo per la sequenza di Student2.

La reazione di subtyping per`o ci semplifica le cose.

Trascurando il fatto che tutti gli elementi di tipo Student precedono quelli di tipo Student2 si pu`o scrivere:

Student*,Student2* <: (Student | Student2)*

dove il tipo a destra, che `e una sequenza in cui ogni elemento `e di tipo Student oppure di tipo Student2, `e supertipo di quello a sinistra.

In questo modo la funzione getNames1 `e riscritta come:

fun getNames1 (val students as students[(Student | Student2)*]) : Name* = match students with

students[student[name[val n],Email*,Tel*],val rest]

->name[n],getNames1(students[rest])

| students[student[name[val n],Email*,MobilePhone*],val rest]

->name[n],getNames1(students[rest])

| students[()]

->()

in cui si `e modificata l’asserzione sul tipo in input trasformandolo nel tipo somma

students[(Student | Student2)]

in maniera da considerare anche i valori di tipo Student2 provenienti dal secondo database.

Occorre, inoltre, aggiungere una nuova clausola al pattern matching (il secon- do caso) in maniera da gestire gli elementi della sequenza di tipo Student2.

3.2.5 Type inference

Al fine di usare il pattern matching in un linguaggio tipato `e necessario un algoritmo per inferire i tipi delle variabili di cattura che compaiono nei patterns, in maniera da evitare di annotare esplicitamente il tipo di ogni va- riabile.

L’algoritmo di inferenza di XDuce assume che un tipo T per i valori in input del pattern sia noto dal contesto e restituisce il tipo di ogni variabile di cat- tura.

Il tipo inferito per ogni variabile x `e esatto nel senso che “contiene” tutti e soli i valori a cui la variabile potr`a essere legata a seguito del matching con un valore in input di tipo T.

Siccome il pattern matching usa la politica first-match, occorre prestare at- tenzione al tipo in input delle clausole successive alla prima.

Si consideri, ad esempio, la seguente espressione match s with

student[name[val n],tel[val t]]

3.2 Aspetti avanzati 41

->...

| student[name[val n],val rest]

->...

dove il tipo in input `e

type Student = student[Name,Email*,Tel?]

Il tipo delle variabili n e t `e chiaramente String, ma qual `e il tipo della variabile rest? A prima vista sembrerebbe essere

(Email*,Tel?)

perch´e il contenuto di Student `e (Name,Email*,Tel?)

ma in realt`a il tipo inferito `e Email+,Tel? | ()

La politica first-match infatti prevede che la seconda clausola catturi i valori che non sono catturati dalla prima.

Ma se la sequenza in input non `e catturata dal primo pattern vuol dire che l’elemento name non `e immediatamente seguito da un elemento tel, cio`e che

`e seguito da una sequenza non vuota di emails seguita da zero oppure un tel oppure dalla sequenza vuota.

Per inferire il tipo di rest occorre innanzitutto calcolare la differenza tra il tipo

student[Name,Email*,Tel?]

del valore in input ed il tipo dei valori accettati dal primo pattern cio`e student[Name,Tel]

che risulta essere

student[Name,((Email+,Tel?) | ())]

Questa differenza `e effettivamente calcolabile perch´e, come si vedr`a nella sezione 3.3.4 i tipi di XDuce sono equivalenti ad automi di alberi e questi sono chiusi rispetto alla differenza.

Adesso `e facile, considerando il pattern student[name[val n],val rest]

il tipo

student[Name,((Email+,Tel?) | ())]

e ricordando che

type Name = name[String]

inferire per n il tipo String e per rest il tipo (Email+,Tel?) | ()

Per quanto riguarda gli as-pattern (cio`e patterns come val x as P) l’algo- ritmo di type inference pu`o inferire un tipo pi` u preciso di quello associato a P.

Per esempio, consideriamo la seguente espressione (dove il tipo in input `e Student):

match s with

student[Name,val x as (Email | Tel)+]

->...

| ...

Il pattern (Email|Tel)+ impone che x possa essere legata a sequenze non vuote in cui ogni elemento `e di tipo Email oppure di tipo Tel.

Da notare che questo pattern non `e esaustivo perch´e non cattura gli studenti che non hanno nessuna email n´e numero di telefono.

In realt`a dalla definizione di Student `e noto che al pi` u un elemento tel pu`o seguire la sequenza di emails.

L’algoritmo di type inference in questo caso calcola per la variabile x il tipo

3.3 La semantica formale 43

(Email+,Tel?) | Tel

che `e sottotipo di (Email | Tel)+

3.2.6 Analisi statica

L’algoritmo di type checking usa i test di subtyping, esaustivit`a, non ridon- danza e l’algoritmo di type inference per garantire staticamente che:

1. Non avvengano errori di “pattern mismatch” a tempo d’esecuzione.

2. I valori risultanti siano del tipo atteso.

Per garantire queste due propriet`a:

• Per ogni applicazione di funzione si controlla che il tipo dell’argomen- to sia sottotipo di quello del parametro formale della funzione (che `e definito da una annotazione di tipo).

• Per il corpo di ogni clausola di un pattern matching si controlla che il tipo restituito dalla funzione (anche esso annotato manualmente) sia un supertipo di quello del corpo.

• Per ogni espressione di pattern matching, noto il tipo in input dal contesto, si controlla l’esaustivit`a delle clausole e non la non ridondanza di nessun pattern.

• In ogni espressione di pattern matching si usa l’algoritmo di type infe- rence per calcolare il tipo esatto per ogni variabile di cattura.

3.3 La semantica formale

Tentiamo adesso di definire pi` u formalmente i concetti che sono stati presen-

tati in maniera intuitiva nei paragrafi precedenti.

3.3.1 Tipi regolari

Indicando con l una etichetta, i valori sono definiti come v ::= l 1 [v], . . . , l n [v] n ≥ 0

Si scriver`a () per la sequenza vuota e v, w per la concatenazione delle sequenze v e w.

Si assuma che esista un insieme infinito di nomi di tipo e che X sia un suo generico elemento.

Le espressioni di tipo sono definite nel seguente modo:

T ::= () sequenza vuota X nome di tipo l[T ] tipo etichettato T, T concatenazione T | T unione

Definiamo un unico insieme globale delle definizioni di tipo E che associa ai nomi dei tipi la loro definizione, che contiene definizioni della forma

type X = T

Il costruttore ∗ pu`o essere derivato dai precedenti usando una definizione ricorsiva, cio`e il tipo T ∗ `e uguale al nome di tipo X definito dall’equazione

type X = T, X | () mentre i costruttori ? e + sono abbreviazioni di

T ? = T | () T + = T, T ∗

Si assuma inoltre l’esistenza di una relazione di subtagging sulle etichette ≺ riflessiva e transitiva.

Definendo i tipi in questo modo essi corrispondono ad arbitrarie grammatiche

3.3 La semantica formale 45

context-free, per esempio si potrebbe definire un tipo ricorsivo che contiene una sequenza di a[ ] di lunghezza uguale a quella di b[ ]

type X = a[ ], X, b[ ] | ()

che corrisponde ad un linguaggio context-free (di alberi), ma non ad un linguaggio regolare.

Siccome il problema dell’inclusione tra linguaggi context-free non `e decidibile,

`e necessario imporre una restrizione ausiliaria in maniera da ridurre il potere espressivo del sistema facendo s`ı che i tipi corrispondano solo a linguaggi regolari di alberi: la “ben formatezza”.

Questa condizione permette alle variabili che non compaiono come contenuto di una etichetta di essere presenti solo in coda ad una definizione.

Per esempio, le seguenti definizioni sono corrette:

type X = a[ ], Y type Y = b[ ], X | ()

Un tipo X `e protetto in T , scritto T : gd(X), se esiste un insieme S di tipi tale che

1. T ∈ S

2. Ogni tipo in S non contiene occorrenze non protette di X cio`e:

• X / ∈ S

• if Y ∈ S ∧ X 6= Y then E(Y ) ∈ S

• if (T | U) ∈ S then T ∈ S ∧ U ∈ S

• if (T, U) ∈ S then T ∈ S ∧ U ∈ S

T `e ben formato in X, scritto T : wf (X), se esiste un insieme S di tipi tale che

1. T ∈ S

2. Ogni tipo in S contiene occorrenze non protette di X solo in coda, cio`e:

• if Y ∈ S ∧ X 6= Y then E(Y ) ∈ S

• if (T | U) ∈ S then T ∈ S ∧ U ∈ S

• if (T, U) ∈ S then T : gd(X) ∧ U ∈ S L’intero insieme E `e ben formato se

E(X) : wf (X) for all X ∈ dom(E) In seguito si assumer`a che E sia ben formato.

La semantica dei tipi `e definita dalla relazione v ∈ T (“v ha tipo T ”) che `e definita nel seguente modo:

() ∈ ()

type X = T ∈ E v ∈ T v ∈ X

v ∈ T l ≺ l ^′ l[v] ∈ l ^′ [T ] v ∈ T w ∈ U

v, w ∈ T, U v ∈ T ₁ v ∈ T 1 | T ₂

v ∈ T 2

v ∈ T 1 | T 2

La relazione di subtyping a questo punto pu`o essere definita nel seguente modo:

S <: T iff v ∈ S ⇒ v ∈ T for all v

3.3.2 Patterns

Assumiamo che esista un insieme infinito di nomi di pattern, con Y generico

nome di pattern ed un insieme infinito di variabili di cattura con x generica