semantica limbajelor formaleusers.utcluj.ro/~eneia/limbaje.pdf · cuprins i introducere 1 1...

Semantica limbajelor formale:

principii si tehnici

Eneia Nicolae Todoran

-2008-

Cuprins

I Introducere 1

1 Concepte de baza 2

2 Semantica denotationala 5

2.1 Principiile semanticii denotationale . . . . . . . . . . . . . . . . . . . . 6

2.2 Domenii semantice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3 Semantica denotationala ın Haskell . . . . . . . . . . . . . . . . . . . . 11

3 Semantica operationala 14

3.1 Sisteme de tranzitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Semantica operationala ın Prolog . . . . . . . . . . . . . . . . . . . . . 18

II Tehnici semantice 19

4 Modele semantice pentru un limbaj uniform 20

4.1 Semantica directa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.2 Semantica de continuare . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.3 Continuari structurate - tehnica CSC . . . . . . . . . . . . . . . . . . . 29

4.3.1 Domenii semantice pentru CSC . . . . . . . . . . . . . . . . . . 33

4.3.2 Mecanismul de evaluare a continuarilor CSC . . . . . . . . . . . 36

5 Semantica constructiilor imperative 43

5.1 Conceptul de stare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.1.1 Implementare ca functie . . . . . . . . . . . . . . . . . . . . . . 46

5.1.2 Implementare ca lista de asociatie . . . . . . . . . . . . . . . . . 47

5.2 Semantica expresiilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.3 Transformari de stare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.3.1 Semantica directa . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.3.2 Semantica de continuare . . . . . . . . . . . . . . . . . . . . . . 51

5.4 Istorii de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.4.1 Semantica de continuare clasica . . . . . . . . . . . . . . . . . . 54

5.4.2 Semantica CSC . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.4.3 Istorii de valori observabile . . . . . . . . . . . . . . . . . . . . . 56

II

6 Recursivitate si semantica de punct fix 59

6.1 Notatia letrec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606.2 Medii semantice si constructii de punct fix . . . . . . . . . . . . . . . . 636.3 Notatia µ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.4 Semantica de punct fix ın Haskell . . . . . . . . . . . . . . . . . . . . . 71

6.4.1 Semantica directa pentru Lrec

1si L

µ

1. . . . . . . . . . . . . . . . 74

6.4.2 Semantica CSC pentru Lrec

1si L

µ

1. . . . . . . . . . . . . . . . . 78

7 Semantica de continuare pentru concurenta 83

7.1 Compunere paralela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 877.1.1 Specificare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897.1.2 Prototip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7.2 Comunicare sincrona . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1047.2.1 Specificare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1137.2.2 Prototip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

8 Semantica constructiilor aplicative 117

8.1 Un limbaj de tip PCF . . . . . . . . . . . . . . . . . . . . . . . . . . . 1188.2 Verificarea tipurilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1208.3 Semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

A Definitii pentru starea ca lista de asociatie 145

B Definitii auxiliare pentru sectiunea 7.1 146

C Definitii auxiliare pentru sectiunea 7.2 147

D Definitii auxiliare pentru capitolul 8 148

Partea I

Introducere

1

Capitolul 1

Concepte de baza

• Acest curs:

– ofera metode precise de descriere si proiectarea programelor si limbajelor de programare;

– prezinta conceptele si principiile ce stau la bazalimbajelor imperative, functionale, orientate peobiecte si concurente;

– evidentiaza importanta semanticii formale;

– prezinta metode si tehnici generale de proiectarea limbajelor de programare;

– valideaza metodele si tehnicile de proiectare se-mantica prin construirea de interpretoare pro-totip (executabile) pentru limbaje complexe deprogramare concurenta si orientata pe obiecte.

2

Concepte de baza 3

• Cursul utilizeaza doua metode (discipline) consacrateın proiectarea semantica:

– semantica denotationala

∗ constructiile program denota valori dintr-undomeniu matematic de interpretare

∗ se opereaza cu definitii compozitionale

– semantica operationala

∗ ofera o descriere intuitiva a modului de executiea programelor

∗ are la baza conceptul de sistem de tranzitie

• Sunt prezentate tehnici semantice: stari, con-tinuari clasice, continuari pentru concurenta.

• In proiectarea masinilor abstracte este utilizatasemantica operationala structurata.

• Sunt oferite exemple de proiectare matematica

a modelelor semantice bazate pe rationamente in-ductive si rationamente de punct fix.

• Sunt studiate concepte aplicative ce au la baza cal-culul lambda simplu tipizat (ın stil PCF).

• Sunt prezentate aplicatii complexe: interpre-toare semantice pentru limbaje imperative, aplica-tive, orientate pe obiecte si concurente.

4 Concepte de baza

• Precizari si note bibliografice:

– Principiile semanticii denotationale au fost in-troduse la sfarsitul anilor ’60 si ınceputul anilor’70 [30, 31, 25, 27].

– Referintele de baza pentru semantica operationalastructurata sunt [23, 10].

– In majoritatea aplicatiilor, domeniile matema-tice utilizate ın semantica denotationala suntmultimi partial ordonate [9, 22] sau spatii met-rice [4].

– Materialul despre calculul lambda simplu tip-izat si PCF este din [33, 8].

– Tehnica clasica a semanticii de continuare a fostintrodusa ca instrument pentru semantica denota-tionala ın [32].

– Semantica de continuare pentru concurenta afost introdusa ın [35, 36].

– In cursurile avansate de limbajelor de progra-mare se utilizeaza adesea urmatoarele mono-grafii [33, 8, 16, 4, 19, 7].

Capitolul 2

Semantica denotationala

• Prin definirea unei semantici denotationale pentruun limbaj de programare se ataseaza valori ma-tematice fiecarei constructii program si astfel seobtine o definitie precisa a limbajului de progra-mare.

• O asemenea definitie permite verificarea corecti-tudinii diverselor implementari ale limbajului sipoate fi utilizata ın demonstrarea proprietatilorprogramelor.

• In aceste note de curs termenul semantica denotao functie S de forma:

S : L → D

unde L este multimea constructiilor limbajului dat,iar D este un domeniu matematic de interpretare.

– In reprezentarea acestor functii se utilizeaza ade-sea ’parantezele semantice’: [[ · ]] : L → D.

5

6 Semantica denotationala

2.1 Principiile semanticii denotationale

1. Constructiile program denota valori dintr-un dome-niu matematic de interpretare.

2. Definitiile denotationale sunt compozitionale:semantica unei constructii sintactice compuseeste exprimata ca functie de semantica constructiilorsintactice componente.

[[ · · · s1 · · · sn · · · ]] = · · · [[ s1 ]] · · · [[ sn ]] · · ·

Realizarea unei semantici denotationale cuprindeurmatoarele activitati:

– definirea unui domeniu matematic de interpretare;

– proiectarea unei functii compozitionale care ma-peaza constructiile sintactice la valori din dome-niul de interpretare.

Semantica denotationala 7

2.2 Domenii semantice

• Un domeniu este o structura matematica care de-scrie notiunea de calcul si aproximare [29].

– Un calcul efectuat pe baza unui algoritm se re-alizeaza ın pasi discreti.

– Dupa fiecare pas se obtine mai multa informatiedespre rezultatul calculului.

– Rezultatul obtinut dupa fiecare pas poate fi privitdrept o aproximare a rezultatului final.

• In semantica, domeniile sunt descrise prin structurimatematice.

• Intuitiv, un domeniu este o multime echipata cu oanumita structura (o relatie de ordine partiala sauo metrica).

• Domeniile compuse sunt obtinute prin utilizareacatorva constructii de baza: produsul cartezian,reuniunea (disjuncta), spatiul de functii, domeniileputere (multimi de submultimi).


• Domeniile semantice trebuie sa permitareprezentarea proceselor de calcul perpetue; acesttip de comportament apare ın prezenta recursivitatii.

• In abordarea clasica, domeniile sunt multimi partialordonate complete si se opereaza cu functii con-tinue [22, 33, 16].

• O alta abordare cunoscuta utilizeaza spatii metricecomplete si contractii peste spatii metrice [4].

• Comportamentul perpetuu (infinit) se obtine calimita a unor procese de calcul finite.


• Domeniile se definesc prin ecuatii de domeniu (ıngeneral recursive) de forma:

X = E

unde E este o expresie compusa data ın notatieBNF printr-o gramatica de forma:

E ::= A | X | P(E) |

E × E | E + E | E → E

ın care A este un domeniu arbitrar dar constant(care nu depinde de X) si sunt utilizate urmatoareleconstructii:

– spatiu de functii:

E1 → E2

– domeniu putere (multimea submultimilor):

P(E)

– produs cartezian:

E1 × E2

– reuniune disjuncta (suma):

E1 + E2 (= ({1} × E1) ∪ ({2} × E2))


• De exemplu, un domeniu de liste finite sau infinitede numere naturale poate fi definit astfel:

L = {Nil} + (N × L)

Cateva elemente din L sunt date mai jos:

Nil

(1, (2, (3, Nil)))

(1, (1, (1, ...)))

• Metoda consacrata de rezolvare a ecuatiilor de dome-niu se bazeaza pe teoria categoriilor [15], atat ıncazul domeniilor clasice [28] cat si ın cazul spatiilormetrice [3].


2.3 Semantica denotationala ın Haskell

• In cadrul acestor note de curs, ın locul notatieimatematice este utilizat adesea limbajul Haskell[18] pentru exprimarea modelelor denotationale.

– Semantica denotationala este prin natura sa osemantica functionala ın care se opereaza cudefinitii compozitionale.

– Limbajul Haskell ofera ın mod natural suportpentru implementarea tehnicilor majore utilizateın semantica denotationala: stari, medii seman-tice, continuari, etc.

• Se au ın vedere urmatoarele beneficii:

– se evita dificultatile legate de prezentarea sis-tematica a aparatului matematic utilizat ın teo-ria clasica a domeniilor sau ın sematica metrica;

– modelele denotationale devin interpretoare pro-totip pentru limbajele considerate si pot fi ime-diat evaluate si testate.


• Domeniile semantice pot fi exprimate ın limbajulHaskell astfel:

– produsul cartezian prin tuple;

– reuniunea (disjuncta) prin reuniuni (sume);

– spatiile de functii prin constructorul ->;

– domeniile putere prin constructorul [].

• De exemplu, daca D si E sunt tipuri atunci se potintroduce tipuri noi astfel:

type ProdusCartezian = (D,E)

data ReuniuneDisjuncta = D D | E E

type SpatiuFunctii = D -> E

type DomeniuPutere = [D]


• Sintaxa limbajelor studiate este data prin definitiide forma:

data X = ...

| OpSin X X

...

• Semantica este definita prin functii compozitionale

sem :: X -> D

...

sem (OpSin x1 x2) =

(sem x1) ‘opSem‘ (sem x2)

...

unde

opSem :: D -> D -> D

Capitolul 3

Semantica operationala

• In semantica operationala executia unui programeste modelata sub forma unei secvente de configuratii

c1, c2, ..., cn, ...

stabilita pe baza unei relatii de tranzitie ’→’ ıntreconfiguratii astfel ıncat (ci, ci+1) ∈→, fapt expri-mat mai sugestiv ın forma: ci → ci+1.

– De exemplu, o configuratie poate fi o instructiuneprogram, sau o pereche constand dintr-o instructiuneprogram ımpreuna cu starea curenta.

• Adesea, se opereaza cu tranzitii etichetate de forma:

ciai→ ci+1.

– Eticheta de tranzitie ar putea fi o actiune atomicasau starea curenta.

14

Semantica operationala 15

3.1 Sisteme de tranzitie

• Incepand cu [23, 10], abordarea preferata ın ma-joritatea aplicatiilor este semantica operationalastructurata (SOS).

• SOS are la baza conceptul de sistem de tranzitie.

– Introducem masinaria semanticii operationaledirect pentru cazul sistemelor de tranzitie etichetate(engl. labeled transition system) LTS.

– Sistemele neetichetate se obtin cu usurinta prinspecializare.

• Un LTS este un triplet (C, A,→) constand dintr-o multime1 (c ∈)C de configuratii, o multime(a ∈)A de etichete de tranzitie si o relatie detranzitie →⊆ C × A × C.

– In acest caz faptul ca tripletul (c, a, c′) este unelement al relatiei de tranzitie ((c, a, c′) ∈→)

se exprima de obicei sub forma ca→ c′.

1In aceasta lucrare notatia (x, y, ... ∈)X introduce multimea X cu elemente tipice x, y, ... (care iauvalori din X).

16 Semantica operationala

• In abordarea SOS relatia de tranzitie ’→’ este in-dusa de o specificare de sistem de tranzitie (engl.transition system specification) TSS, care este ocolectie de reguli de forma:

c1a1→ c′1 · · · cn

an→ c′n

ca→ c′

Elementele ciai→ c′i se numesc premise, iar c

a→ c′

se numeste concluzia regulei. Daca n = 0 (adicanu exista premise) regula se numeste axioma.

– Tranzitiile date sub forma de axiome au loc prindefinitie.

– In plus, orice tranzitie care este concluzia uneireguli este un element al relatiei de tranzitiedaca se poate stabili ın baza regulilor TSS capremisele sale sunt adevarate.

• Relatia de tranzitie specificata printr-un TSS estecea mai mica relatie care satisface regulile TSS.

Semantica operationala 17

• Observatii

– In unele aplicatii nu sunt necesare tranzitii etichetate.In acest caz

∗ relatia de tranzitie ’→’ este o submultime aC × C (→⊆ (C × C)),

∗ iar regulile de deductie sunt de forma:

c1 → c′1 · · · cn → c′nc → c′

– In majoritatea aplicatiilor o configuratie este

∗ fie un element a limbajului (o constructie sin-tactica reprezintand instructiunea curenta amasinii abstracte de calcul),

∗ fie o pereche constand dintr-un element allimbajului ımpreuna cu starea curenta a masiniiabstracte.

– Termenul structurat din denumirea SOS se re-fera la proiectarea ghidata de sintaxa a regulilorTSS.

18 Semantica operationala

3.2 Semantica operationala ın Prolog

• Un sistem de tranzitie este un sistem de deductiealcatuit din axiome si reguli ce permit specificareaunei relatii de tranzitie. Deducerea tranzitiilor seface, la fel ca ın limbajul Prolog, prin ınlantuireınapoi (engl. backward chaining).

• Este deci naturala transcrierea unui sistem de tranzitieca program logic sub forma unui set de clauze Horn.

– Fiecare axioma TSS poate fi implementata subforma unui fapt ın Prolog.

– Fiecare regula TSS poate fi implementata subforma unei reguli Prolog corespunzatoare.

De exemplu, o regula:

c1a1→ c′1 · · · cn

an→ c′n

ca→ c′

poate fi implementata ın Prolog sub forma uneiclauze a unui predicat tss/3:

tss(C,A,C’) :-

tss(C1,A1,C1’),...,tss(Cn,An,Cn’).

Partea II

Tehnici semantice

19

Capitolul 4

Modele semantice pentru un limbaj

uniform

• Se considera un limbaj secvential (nerecursiv) cuactiuni elementare (atomice) neinterpretate L0.

• Un limbaj cu actiuni elementare neinterpretate sezice uniform [4].

• Fie (a ∈)Act o multime de actiuni atomice.Definim sintaxa L0 ın BNF1. Clasa (x ∈)X ainstructiunilor L0 este introdusa prin gramatica:

x ::= a | x; x

unde ’x1; x2’ reprezinta compunerea secventiala ainstructiunilor x1 si x2; punem L0 = X .

• In Haskell, sintaxa L0 poate fi implementata astfel:

type Act = String

data X = A Act | Seq X X

1Backus-Naur Formalism

20

Modele semantice pentru un limbaj uniform 21

4.1 Semantica directa

• Interpretarea semantica a programelor L0 o damprin secvente finite peste Act. Domeniul semanticpt. L0 este2:

P = Act∗

D = P

Definim o semantica denotationala directa pentruL0(= X) astfel:

[[ · ]] : X → D

[[ a ]] = a

[[ x1; x2 ]] = [[ x1 ]] ; [[ x2 ]]

unde ın partea dreapta, ’ ; ’ este operatorul seman-tic de concatenare secvente peste D.

2Act∗ include secventa vida. Strict vorbind, L0 nu poate genera secventa vida, deci domeniul Act+

ar fi mai potrivit. Ignoram ınsa acest aspect, deoarece ın Haskell este convenabil sa reprezentamsecventele ca liste de tipul [a], iar tipul [a] include implicit lista vida [].

22 Modele semantice pentru un limbaj uniform

• Semantica denotationala directa a L0 data maisus poate fi implementata ın limbajul Haskell cumurmeaza:

type P = [Act]

type D = P

sem :: X -> D

sem (A a) = [a]

sem (Seq x1 x2) =

(sem x1) ++ (sem x2)

Operatorul ’++’ (de concatenare liste) este definitın modulul standard Prelude.hs astfel:

(++) :: [a] -> [a] -> [a]

[] ++ bs = bs

(a:as) ++ bs = a:(as ++ bs)


– Fie

x0, x1 :: X

x0 = Seq (A "a") (A "b")

x1 = Seq (Seq (A "a")

(Seq (A "b")

(A "c")))

(A "d")

– Se pot efectua urmatoarele experimente3:

Main> sem x0

["a","b"]

Main> sem x1

["a","b","c","d"]

3Experimentele au fost realizate utilizand interpretorul Hugs, disponibil la adresahttp://www.haskell.org.


Exercitii

• E 4.1.1 Sa se arate ca ın L0 compunerea secventialaeste asociativa, (demonstrand asociativitatea op-eratorului ’++’).


4.2 Semantica de continuare

• Tehnica continuarilor reprezinta un instrument de-osebit de util pentru modelarea controlului ın se-mantica denotationala. Tehnica clasica a seman-ticii de continuare a fost introdusa ın [32].

• In aceasta abordare, functia denotationala depindede un parametru aditional, numit continuare.

• Un program este descompus conceptual ıntr-oinstructiune curenta si restul programului.

• Conform definitiei originale [32], o continuare esteeste o reprezentare semantica a acestui rest de pro-gram.


• Prezentam o semantica denotationala pentru L0

proiectata cu tehnica clasica a continuarilor [32].

• O continuare este o reprezentare semantica a restu-lui programului. Definim deci domeniul continuarilorpentru L0 astfel:

P = Act∗

(γ ∈)Cont = P

• Semantica de continuare pentru L0 este:

D = Cont → P

[[ · ]] : X → D

[[ a ]] γ = a · γ

[[ x1; x2 ]] γ = [[ x1 ]] ( [[ x2 ]] γ)

• unde ’ · ’ este operatorul semantic de prefixare aunui element la o secventa, rezultatul fiind o nouasecventa (mai lunga cu un element).


• Oferim o implementare Haskell a semanticii de con-tinuare pentru L0.

type P = [Act]

type Cont = P

type D = Cont -> P

sem :: X -> D

sem (A a) c = a:c

sem (Seq x1 x2) c =

sem x1 (sem x2 c)

• Pentru a putea efectua experimente cu aceastafunctie semantica trebuie sa definim o continuareainitiala c0. In acest caz, continuarea initiala estesecventa vida de observabile (actiuni atomice).

c0 :: Cont

c0 = []

• Fie x0, x1 :: X ca ın sectiunea 4.1. Se potrealiza urmatoarele evaluari:

Main> sem x0 c0

["a","b"]

Main> sem x1 c0

["a","b","c","d"]


Exercitii

• E 4.2.1 Sa se arate ca semantica de continuare(functia sem din definitia de mai sus) este definitacompozitional.

• E 4.2.2 Sa se arate ca operatia de compuneresecventiala este asociativa si ın cazul semanticiide continuare.

• E 4.2.3 Sa se arate ca pentru orice x :: X sipentru orice c :: Cont:

semc x c = semd x ++ c

unde semd este semantica directa definita ınsectiunea 4.1 iar semc este semantica de conti-nuare definita ın aceasta sectiune.4 In particu-lar avem:

semc x [] = semd x

4Operatorul ’++’ are prioritate mai mica decat operatia de aplicare a functiei. Urmeaza ca ecuatiace trebuie demonstrata este:

semc x c = (semd x) ++ c


4.3 Continuari structurate - tehnica CSC

• Tehnica continuarilor este cunoscuta pentru flexi-bilitatea pe care o furnizeaza ın proiectarea seman-tica. Insa continuarile clasice prezinta limitari ınmodelarea sistemelor concurente [11].

• Tehnica CSC (engl. continuation semantics forconcurrency) a fost introdusa ın [35]. Aceastatehnica permite ın acelasi timp modelarea com-punerii secventiale si modelarea compunerii para-lele ın sematica de ıntretesere furnizand o foartebuna flexibilitate ın proiectarea semantica.

• In abordarea CSC o continuare este o structura dedenotatii partial evaluate, sau calcule.

• Structura continuarilor CSC depinde de aplicatie.Urmand [38], utilizam conceptul de stiva pentrua modela compunerea secventiala si conceptul demultiset pentru a modela compunerea paralela.

• Conceptul de semantica de ıntretesere - utilizatın modelarea sistemelor concurente - va fi intro-dus ıntr-un capitol ulterior. Deocamdata, tehnicaCSC este aplicata ın proiectarea unei semanticidenotationale pentru limbajul secvential L0.


• In cazul limbajului L0 o continuare CSC este osimpla stiva de calcule, pe care o implementamca lista ın Haskell. Comp este domeniul calculelor(engl. computations) pentru L0.

type P = [Act]

type D = Cont -> P

data Comp = D D

type Cont = [Comp]

• Utilizand tehnica CSC se poate implementa o se-mantica denotationala pentru L0 astfel:

sem :: X -> D

sem (A a) c = a : cc c

sem (Seq x1 x2) c =

sem x1 (D (sem x2) : c)

• cc (engl. continuation completion) este functiace executa continuarea. In cazul limbajului L0,cc activeaza calculul (denotatia) din varful stiveitransmitandu-i drept continuare restul stivei.

cc :: Cont -> P

cc [] = []

cc (D d:c) = d c


• In cazul modelului CSC continuarea initiala estestiva vida de calcule.

c0 :: Cont

c0 = []

• Fie (din nou) x0, x1 :: X ca ın sectiunea 4.1.Se pot efectua urmatoarele teste:

Main> sem x0 c0

["a","b"]

Main> sem x1 c0

["a","b","c","d"]


Exercitii

• E 4.3.1 Sa se arate ca operatia de compuneresecventiala este asociativa si ın cazul semanticiiCSC.

• E 4.3.2 Sa se arate ca semantica de continuareclasica coincide cu semantica CSC pentru L0.Mai precis, daca semcsc este functia semanticadefinita ın aceasta sectiune (4.3), iar semc estefunctia semantica definita ın sectiunea 4.2, atuncidaca ccsc este o continuare CSC iar cc este ocontinuare clasica astfel ıncat:

cc = cc ccsc

atunci pentru orice x :: X:

semc x cc = semcsc x ccsc

In particular asta ınseamna ca relatia are loc sipentru continuarile initiale:

semc x [] = semcsc x []

deoarece

[] = cc []


4.3.1 Domenii semantice pentru CSC

• Conceptul de domeniu (sau domeniu semantic)ofera o fundamentare matematica pentru programelerecursive.

• Pentru aplicatii mai avansate domeniile se definescprin ecuatii recursive de domeniu. Este si cazultehnicii CSC, pentru care domeniul continuariloreste solutia unei ecuatii recursive ın care variabilade domeniu apare ın partea stanga a unei constructiide tip spatiu de functii [35].

– Solutia acestui tip de ecuatii necesita constructiicomplexe preluate din teoria categoriilor [28, 3].

– In acest sens modelul CSC este complex.

• Insa din punctul de vedere al proiectantului de lim-baj tehnica CSC este usor de utilizat, continuarileputand fi proiectate prin combinarea unor struc-turi simple ce furnizeaza intuitie operationala [38].

• Este celebra ecuatia de domeniu pentru calculullambda netipizat (rezolvata de Dana Scott ın 1970).

D ∼= D → D

Simbolul ’∼=’ denota izomorfism de domenii: solutiaunei asemenea ecuatii este determinata pana laizomorfism, nu pana la egalitate.


• In aceste note de curs vom utiliza ın special urmatoareleclase de domenii (definite prin ecuatii recursive):

– liste (finite sau infinite) de elemente dintr-undomeniu A dat (unde ǫ denota terminare, iarδ denota deadlock):

Q ∼= {ǫ} + (A × Q), sau

Q ∼= {ǫ} + {δ} + (A × Q);

∗ implementarea Haskell este:

data Q = Epsilon | Q A Q

∗ (sau chiar type Q = [A]), respectiv

data Q = Epsilon | Deadlock | Q A Q

– domenii putere de forma (Q este un domeniu deliste, cum sunt cele definite mai sus; un elemental domeniului P este o colectie de liste5):

P = P(Q);

∗ implementarea Haskell este:

type P = [Q]

5Domeniile putere au fost introduse de Gordon Plotkin [20] pentru modelarea comportamentuluiconcurent si nedeterminist. In exemplul nostru, daca fiecare lista de tipul Q reprezinta o trasare deexecutie a unui program, atunci un element de tipul P poate modela colectia tuturor trasarilor posibilepentru un program concurent (nedeterminist).


– continuari pentru tehnica CSC, care suntconfiguratii (structuri) de denotatii partial eval-uate (sau calcule); ın ecuatia de mai jos, o con-tinuare (de tipul Cont) este o lista de denotatii(adica o lista de functii):6

D = Cont → P

Cont ∼= {empty} + (D × Cont)

∗ implementarea directa ar fi:

type D = Cont -> P

data Cont = Empty | Cont D Cont

∗ dar ın aplicatii mai complexe este preferabilsa se introduca un domeniu Comp de calcule(engl. computations), care poate fi elaboratın functie de aplicatie:

type D = Cont -> P

data Comp = D D

type Cont = [Comp]

· este important faptul ca o asemenea listade denotatii sau calcule, poate modela unmultiset7 de calcule (procese) executate ınparalel.

6Daca dorim sa avem acces indexat la denotatiile dintr-o continuare, se poate utiliza un domeniude forma:

Cont ∼= Id → D

unde elementele din Id sunt identificatori de proces. O asemenea continuare poate modela un multisetde denotatii. Oricum, continuarile pentru concurenta pot fi utilizate si pentru a modela compunereasecventiala; ın acest caz, ın locul disciplinei de multiset se considera o disciplina de tip stiva.

7Un multiset este o colectie ce admite duplicate.


4.3.2 Mecanismul de evaluare a continuarilor CSC

• Exista doua interpretari posibile pentru conceptulde continuare.

– In interpretarea initiala o continuare este oreprezentare a restului de calcul [32].

– Alternativ, o continuare poate fi interpretatadrept context de evaluare [7, 6].

• In abordarea CSC spatiul de calcule este ımpartitastfel:

– un calcul activ (sau o denotatie activa) si

– restul calculelor care sunt ıncapsulate ın conti-nuare.

• Continuarile CSC pot fi ımpartite ın:

– continuari active sau deschise (engl. open con-tinuations)

– continuari ınchise (engl. closed continuations)

• Ambele tipuri de continuari sunt reprezentari alerestului de calcul.

• O continuare activa (deschisa) este un context deevaluare pentru calculul activ.

– Conceptul de continuare ınchisa nu poate fi de-scris utilizand conceptul de context de evaluare.


• Functiile unui interpretor semantic CSC pot fi gru-pate ın urmatoarele trei componente:

1. un evaluator

2. o functia de executie a continuarii si o procedurade normalizare

3. un planificator (de procese / calcule)

• Un interpretor semantic CSC implementeaza o bucla”evaluate-normalize-schedule” [6, 38].


1. Evaluatorul mapeaza o continuare deschisa la uncomportament program.

• Este alcatuit din definitia (compozitionala a)functiei semantice ımpreuna cu operatori de con-trol specifici limbajului.

• Toate functiile evaluatorului manipuleaza (doar)continuari deschise (contexte de evaluare).

2. Functia de executie a continuarii mapeaza o con-tinuare deschisa la un comportament program core-spunzator:

• mai ıntai apeleaza procedura de normalizarecare transforma o continuare deschisa ıntr-o con-tinuare ınchisa corespunzatoare,

• apoi apeleaza planificatorul.

3. Planificatorul mapeaza o continuare ınchisa la uncomportament program.

• In cazul unui limbaj secvential planificatorul de-scompune o continuare ınchisa ıntr-un calcul ac-tiv si o continuare deschisa corespunzatoare.

• Pentru un limbaj concurent ınsa sunt posibilemai multe asemenea activari; asta poate da nasterela nedeterminism. In plus, poate fi necesar caplanificatorul sa execute un numar de actiunide sincronizare ınainte de activarea unui calcul.


• In continuare utilizam

– tipul Kont pentru a implementa continuarileınchise si

– tipul Cont pentru a implementa continuariledeschise.

• Diferenta ıntre continuarile deschise si continuarileınchise poate fi codificata explicit ın domeniile se-mantice, dar aceasta este doar o decizie de imple-mentare.

• In cele ce urmeaza punem Cont = Kont si dis-tingem ıntre continuarile deschise si continuarileınchise numai la nivel conceptual.


• Exemplificam mecanismul de evaluare a continuarilorCSC restructurand interpretorul semantic (pentrulimbajul L0) dat ın sectiunea 4.3.

• Domeniul denotatiilor D si domeniul calculelor Compraman ca la ınceputul sectiunii 4.3.

type P = [Act]

type D = Cont -> P

data Comp = D D

• In cazul L0 domeniul continuarilor deschiseCont si domeniul continuarilor ınchise Kont

sunt definite pe baza unui domeniu SC de stivede calcule. Figura 4.1 reprezinta o continuare ac-tiva (deschisa). Cerculetul negru indica pozitiaconceptuala a calculului activ (varful stivei); cele-lalte calcule sunt inactive. Continuarea initiala(c0 = []) este o continuare deschisa c0 :: Cont.

type SC = [Comp]

type Kont = SC

type Cont = Kont

...

calcul activ

calcul inactiv SC

Figura 4.1: Structura continuarilor CSC pentru L0: o stiva de calcule.


• Evaluatorul interpretorului CSC pentru L0 cuprindedefinitia (compozitionala a) functiei semantice ımpreunacu un operator de control addc pentru compunereasecventiala. In cazul acestui limbaj simplu addc

adauga un calcul ın varful stivei ce implementeazacontinuarea. Subliniem faptul ca toate functiileevaluatorului manipuleaza continuari deschise.

sem :: X -> D

sem (A a) c = a : cc c

sem (Seq x1 x2) c =

sem x1 (addc (D (sem x2)) c)

addc :: Comp -> Cont -> Cont

addc p sc = p : sc

• Functia de executie a continuarii cc normalizeaza

continuarea si apeleaza planificatorul kc. In cazullimbajului L0 procedura de normalizare re coin-cide cu functia identitate.

cc :: Cont -> P

cc c = case re c of

[] -> empty

k -> kc k

re :: Cont -> Kont

re = id


– Constanta empty modeleaza terminarea.

empty :: P

empty = []

– Procedura de normalizare transforma o conti-nuare deschisa / activa (adica un context deevaluare pentru calculul activ) ıntr-o continuareınchisa (ce contine doar calcule inactive).

• In cazul foarte simplu al limbajului L0 planificatoruldescompune o continuarea ınchisa ıntr-un calculactiv (o denotatie activa) si o continuare deschisacorespunzatoare. Exista o singura descompunereposibila, acest fapt reflectand caracterul determin-ist al limbajului L0. Planificatorul activeaza denotatiadin varful stivei transmitandu-i restul stivei dreptcontinuare.

kc :: Kont -> P

kc (D d:c) = d c

Capitolul 5

Semantica constructiilor imperative

• Un limbaj se zice neuniform daca semanticainstructiunilor (elementare) depinde de stareamasinii de calcul (terminologie din [4]).

• Starea (care este un concept abstract) memoreazavalorile variabilelor programului.

• Introducem un limbaj neuniform L1.

• L1 este un limbaj imperativ secvential ın care mod-ificarea starii masinii de calcul poate fi comandataprin instructiuni de atribuire, si se pot executasecvente arbitrare de instructiuni.

43

44 Semantica constructiilor imperative

• Definim sintaxa L1. Clasa (x ∈)X a instructiunilorL1 este introdusa prin gramatica:

x ::= v := n | x ; x

unde se presupun date

– o clasa (v ∈)V de variabile numerice

– si o clasa (n ∈)N de expresii numerice deforma (aici z ∈ Z):

n ::= z | v | n + n | · · ·

– iar x1 ; x2 reprezinta compunerea secventiala ainstructiunilor x1 si x2.

Punem L1 = X .

• In Haskell, implementam sintaxa L1 astfel:

type V = String

data N = Z Int | V V | Plus N N

data X = Assign V N | Seq X X

Semantica constructiilor imperative 45

5.1 Conceptul de stare

• In semantica limbajelor de programare o stare esteo functie de la variabile la valori:1

(σ ∈)Σ = V → V al

In implementare vom considera: V al = Z.

• Conceptul abstract de stare este legat de capaci-tatea de stocare a valorilor ın variabile program side modificare a valorilor stocate ın variabile.

• Fie f : A → B o functie, a ∈ A si b ∈ B. Notatia(f | a 7→ b) denota o varianta a functiei f care esteidentica cu f ın toate punctele, exceptand punctula ın care ia valoarea b.

(f | a 7→ b)(a′) =

{

b if a′ = a

f (a′) if a′ 6= a

Operatorul (f | a 7→ b) ”perturba” functia f ınpunctul a.

– Asa cum se va vedea ın continuare, acest oper-ator poate fi utilizat

∗ atat ın modelarea semanticii instructiunilorde atribuire din limbajele imperative,

∗ cat si ın modelarea semanticii legarilor devariabile din limbajele aplicative.

1In aplicatii mai complexe notiunea poate fi elaborata ın functie de necesitati.


5.1.1 Implementare ca functie

• Domeniul starilor Σ poate fi implementat ın Haskellastfel:

type S = V -> Int

• Utilizand aceasta reprezentare, valoarea atasata uneivariabile ıntr-o stare data este:

val :: V -> S -> Int

val v s = s v

• In Haskell, implementam operatorul de ”pertur-bare” (f | a 7→ b) ca functie polimorfica.

upd :: Eq a =>

(a -> b) -> a -> b -> (a -> b)

upd f a b a’ =

if (a’ == a) then b else f a’

• Aceasta implementare corespunde fidel definitieimatematice dar nu face posibila vizualizarea starilor.2

• In exemple consideram ca ın starea initiala toatevariabilele sunt neinitializate:

s0 :: S

s0 v =

error ("var. neinitializata" ++ v)

2In general, o functie nu poate fi vizualizata.


5.1.2 Implementare ca lista de asociatie

• In aplicatiile ın care dorim sa vizualizam starilepreferam o reprezentare a conceptului de stare calista de asocieri variabila-valoare.

type S = [(V,Int)]

cu conventia ca toate variabilele care nu sunt prezenteın lista sunt implicit neinitializate.

• Desigur, aceasta reprezentare este posibila doaratunci cand starea contine doar un numar finit devariabile ce au valori interesante.

• In aceasta reprezentare starea initiala este:

s0 :: S

s0 = []

• Un alt exemplu este starea:

[("v",10),("u",7)]

ın care variabila "v" are valoarea 10, variabila"u" are valoarea 7, si toate celelalte variabile suntneinitializate.

• Implementarea operatorilor val si upd pentru aceastareprezentare este data ın anexa A.


5.2 Semantica expresiilor

• In general, ın L1 valoarea unei expresii n(∈ N)depinde de starea curenta a masinii.

• Semantica expresiilor este definita cu usurinta printr-o functie de forma:

N [[ · ]] : N → Σ → Z

N [[ z ]] σ = z

N [[ v ]] σ = σ(v)

N [[ n1 + n2 ]] σ = N [[ n1 ]] σ + N [[ n2 ]] σ

· · ·

pe care o implementam ın Haskell astfel:

evN :: N -> S -> Int

evN (Z z) s = z

evN (V v) s = val v s

evN (Plus n1 n2) s =

evN n1 s + evN n2 s

...


5.3 Transformari de stare

• In aceasta sectiune modelam comportamentul unuiprogram ca functie de transformare a starii:

type P = S -> S

• O asemenea functie semantica mapeaza starea initialala starea finala, care este unic determinata ın cazullimbajului L1.

• De remarcat faptul ca orice program L1 se ter-mina ın timp finit. Acest lucru nu ar fi adevaratdaca limbajul L1 ar incorpora un mecanism pentrudefinitii recursive (sau pentru iteratie nedefinita).Conceptul de recursivitate va fi introdus formalıntr-un capitol ulterior.


5.3.1 Semantica directa

• Oferim mai ıntai o semantica directa ce imple-menteaza o transformare de stare.

sem :: X -> P {-- type P = S -> S --}

sem (Assign v n) s =

upd s v (evN n s)

sem (Seq x1 x2) s =

sem x2 (sem x1 s)

• In semantica directa o compunere secventiala x1 ; x2

este evaluata astfel. Mai ıntai se evalueazainstructiunea x1 ın starea curenta; aceasta produceo noua stare ce este utilizata ca stare initiala pen-tru evaluarea instructiunii x2.

• Operatia de atribuire este implementata direct pebaza operatorului upd.

• Testam acest program utilizand stari reprezentateca liste de asociatie. Fie:

x = Seq (Assign "v" (Plus (Z 1) (Z 2)))

(Assign "u" (Plus (V "v") (Z 4)))

• Se poate efectua urmatorul experiment:

Main> sem x s0

[("v",3),("u",7)]


5.3.2 Semantica de continuare

• Utilizand tehnica continuarilor clasice se poate definio semantica de transformare de stare astfel:

type Cont = P {-- type P = S -> S --}

c0 :: Cont

c0 = \s -> s

sem :: X -> Cont -> P

sem (Assign v n) c s =

c (upd s v (evN n s))

sem (Seq x1 x2) c s =

sem x1 (sem x2 c) s

• De data aceasta o continuare este o functie, iarcontinuarea initiala este functia identitate.


Main> sem x c0 s0

[("v",3),("u",7)]


Exercitii

• E 5.3.1 Sa se proiecteze o semantica CSC cafunctie de transformare de stare.

• E 5.3.2 Sa se arate ca ın L1 compunerea secventialaeste asociativa pentru fiecare dintre modelele con-siderate: semantica directa (data ın 5.3.1), se-mantica continuare (data ın 5.3.2), si modelulCSC proiectat ın exercitiul 5.3.1.


5.4 Istorii de calcul

• In aceasta sectiune modelam comportamentul unuiprogram ca istorie de calcul, mai precis sub formaunei functii ce mapeaza starea initiala la lista starilorprin care trece programul:

type P = S -> [S]

• Din nou, se remarcat faptul ca orice program L1 setermina ın timp finit. Acest lucru nu ar fi adevaratdaca limbajul L1 ar incorpora un mecanism pentrudefinitii recursive (sau pentru iteratie nedefinita).Conceptul de recursivitate va fi introdus formalıntr-un capitol ulterior.

– Conceptul de istorie (lista) infinita de stari poatefi implementat pe baza mecanismului de eval-uare lenesa a limbajului Haskell [18]. Deocam-data nu avem nevoie de acest mecanism.

• In aceasta sectiune oferim numai modele proiectateın semantica de continuare.


5.4.1 Semantica de continuare clasica

• Utilizand tehnica continuarilor clasice se poate definio semantica denotationala ce produce lista starilorprin care trece programul astfel:

type Cont = P

c0 :: Cont

c0 = \s -> []

sem :: X -> Cont -> P


let s’ = upd s v (evN n s)

in s’ : (c s’)

sem (Seq x1 x2) c s =

sem x1 (sem x2 c) s

• Se poate efectua urmatorul experiment (unde x

este ca ın sectiunea 5.3.1), ın care am utilizat ıncontinuare reprezentarea ca lista de asociatie pen-tru stari:

Main> sem x c0 s0

[[("v",3)],[("v",3),("u",7)]]


5.4.2 Semantica CSC

• Proiectam un model CSC plecand de la definitiiledate ın 4.3.2. Prezentam numai definitiile care semodifica.

• Domeniul P este cel definit la ınceputul sectiunii5.4, iar pentru domeniul starilor utilizam reprezentareaca lista de asociatii.

• Definitiile urmatoarelor domenii raman ca ın 4.3.2:D (denotatii), Comp (calcule), Kont (continuari ınchise),Cont (continuari active / deschise).

• De asemenea, definitiile urmatoarelor constante sifunctii raman ca ın 4.3.2: c0 :: Cont (contin-uarea initiala), operatorul de control addc, functiade executie a continuarii cc, procedura de nor-malizare re si functia planificator kc.

• Se modifica numai constanta empty, care devine:

empty :: P

empty = \s -> []

si prima ecuatie din definitia semanticii denotationale(declaratia de tip pentru sem ramane ca ın 4.3.2).


let s’ = upd s v (evN n s)

in s’ : (cc c s’)


5.4.3 Istorii de valori observabile

• Reprezentarea starilor ridica probleme la nivel deimplementare. Pentru a simplifica procesul de pro-totipizare semantica consideram limbajul L2 ((x ∈)X = L2) ce extinde L1 cu o constructie write (n)ce produce valoarea expresiei n ca element observ-abil.

x ::= v := n | write (n) | x1 ; x2

• Consideram urmatoarea implementare Haskell asintaxei L2.

data X = Assign V N | Write N | Seq X X

• In aceste conditii, utilizam reprezentarea teoreticaa domeniului starilor ca functie de la variabile lavalori (data ın sectiunea 5.1.1), deoarece ne prop-unem ca interpretorul semantic sa produca o listade valori observabile (ce pot fi vizualizate cu usurinta),iar nu o lista de stari.

type S = V -> Int

• Modelam comportamentul programului sub formaunei functii ce mapeaza starea initiala la lista val-orilor observabile produse de program.

type Obs = Int

type P = S -> [Obs]


• Prezentam doar o semantica CSC pentru L2. Toatedefinitiile raman ca ın sectiunea 5.4.2 (dar ın raportcu noul domeniu P), exceptand functia denotationala.

• Se modifica doar semantica instructiunii de atribuiresi se adauga o clauza pentru producerea unei valoriobservabile (ecuatia semantica pentru compunereasecventiala ramane neschimbata).


cc c (upd s v (evN n s))

sem (Write n) c s =

evN n s : cc c s

• Modelul semantic bazat pe istorii de valori observa-bile este convenabil din perspectiva prototipizariisemantice.

• Fie acum

x :: X

x = Seq (Seq (Assign "v" (Plus (Z 1) (Z 2)))

(Write (V "v")))

(Seq (Assign "u" (Plus (V "v") (Z 4)))

(Write (V "u")))


Main> sem x c0 s0

[3,7]


Exercitii

• E 5.4.1 Sa se proiecteze o semantica de conti-nuare clasica pentru L2.

Capitolul 6

Recursivitate si semantica de punct

fix

• Majoritatea limbajelor de programare admit definitiirecursive.

• Recursivitatea introduce posibilitatea comporta-mentului infinit (procese de calcul perpetue).

• Justificarea riguroasa a recursivitatii se realizeazaın cadrul teoriei domeniilor utilizand medii se-mantice si constructii punct fix.

• Se utilizeaza:

– multimi partial ordonate complete si functii con-tinue (ın acest caz se opereaza cu conceptul decel mai mic punct fix) [22, 33, 29, 16];

– spatii metrice complete si functii contractive (ocontractie peste un spatiu metric complet areun punct fix unic, cf. teor. Banach) [4].

59

60 Recursivitate si semantica de punct fix

6.1 Notatia letrec

• Introducem limbajul neuniform Lrec1 , care extinde

L1 cu o instructiune vida, selectie conditionala, sirecursivitate.

• Clasa (x ∈)X a instructiunilor Lrec1 (= X) este:

x ::= skip | v := n

| x; x | if b then x else x

| y | letrec y be x in x

• Celelalte clase sintactice sunt:

– o clasa de variabile numerice (v ∈)V (ca ıncapitolul 5);

– o clasa de expresii numerice (n ∈)N (ca ıncapitolul 5);

– o clasa de expresii booleene (b ∈)B de forma:

b ::= n == n | n < n | · · ·

– o clasa de variabile de procedura (y ∈)Y .

Recursivitate si semantica de punct fix 61

• skip este instructiunea inoperanta (nu modificastarea).

• v := n este instructiunea de atribuire.

• x1; x2 este compunerea secventiala.

• if b then x1 else x2 este instructiunea conditionala.

• b este o expresie booleana; expresiile de acest tippot fi testate, dar, pentru simplitate, nu pot fiatribuite; variabilele (v ∈)V pot pastra numai val-ori numerice.

• y este un apel de procedura.

• Constructia letrec y be x1 in x2 defineste proce-dura y cu corpul x1 spre a fi utilizata ın bloculx2.


• D.p.d.v. sintactic, Lrec1 este foarte asemanator cu

L1 (L1 a fost introdus ın capitulul 5).

• Semantic ınsa, exista o mare deosebire ıntre celedoua limbaje, deoarece ın Lrec

1 exista posibilitateaca executia unui program sa nu se termine.

• Semantica L1 poate fi definita utilizand exclusivconceptele traditionale de multime, functie (ordi-nara peste multimi), si cateva constructii simple.De asemenea, operatorii semantici pot fi definitiprin argumente inductive.

• Pentru a defini semantica Lrec1 fiecare multime tre-

buie sa fie ınlocuita cu un domeniu, si fiecare functie(ordinara) cu o functie continua. De asemenea, ar-gumentele inductive trebuie sa fie suplimentate cuargumente de punct fix.

• Intuitiv, un domeniu semantic este o multimeechipata cu o anumita structura, care permitereprezentarea conceptului de calcul si aproximareın pasi discreti [22, 29, 4, 33, 16].

• Deocamdata, vom utiliza conceptul de domeniuıntr-un mod strict intuitiv, dar implementarile Haskellne vor ajuta sa ıi ıntelegem (partial) semnificatia.

• Metodologia matematica de tratare a recursivitatiiare la baza teoria matematica a domeniilor.


6.2 Medii semantice si constructii de punct fix

• Dorim sa definim o semantica denotationala pen-tru Lrec

1 de forma [[ · ]] : X → Env → D.

• Sa zicem ca introducem semantica sub forma uneifunctii de transformare de stare (vezi 5.3):

(p ∈)P = Σ → Σ

• Pentru ilustrarea proiectam o semantica directa,deci punem:

(φ ∈)D = P

• Presupunem date functii de evaluare pentru expre-sii numerice si booleene (care depind de stare):

N [[ · ]] : N → Σ → Z

B[[ · ]] : B → Σ → {true, false}

• Elementul de noutate este adus de utilizarea unuidomeniu (η ∈)Env de medii semantice (engl. se-mantic environment), care mapeaza fiecare pro-cedura direct la semantica atasata.

(η ∈)Env = Y → D


• Majoritatea clauzelor care definesc functiadenotationala [[ · ]] pentru Lrec

1 sunt cunoscute, sauusor de ınteles. Modelul dat mai jos este proiectatın semantica directa (vezi sectiunea 5.3.1). Pentrulizibilitate folosim aici o notatie matematica, darmodelul este implementat ın sectiunea 6.4.

[[ skip ]] η = λσ. σ

[[ v := n ]] η = λσ. (σ | v 7→ N [[ n ]] σ)

[[ if b then x1 else x2 ]] η

= λσ.

{

[[ x1 ]] ησ if B[[ b ]] σ = true

[[ x2 ]] ησ if B[[ b ]] σ = false

[[ x1; x2 ]] η = λσ. [[ x2 ]] η( [[ x1 ]] ησ)

• Ultima clauza (care defineste comportamentul com-punerii secventiale ın semantica directa) este echiva-lenta cu:

[[ x1 ; x2 ]] η = [[ x2 ]] η ◦ [[ x1 ]] η

unde ’◦’ este operatorul de compunere a functiilor.

• De asemenea, dorim sa avem:

[[ y ]] η = η(y)


• Urmeaza ca singura dificultatea este legata dedefinirea unei semantici compozitionale pentruconstructia letrec y be x1 in x2, deoarece ın x1

pot exista apeluri recursive y.

• Ideea de baza este ca semantica variabilei deprocedura y definita printr-o constructieletrec y be x1 in · · · ın raport cu un mediusemantic η este solutia urmatoarei ecuatii:

φ = [[ x1 ]] (η | y 7→ φ) (∗)

• Vedem ca apelurile lui y din x1 sunt interpretateca fiind tocmai aceasta semantica φ(∈ D).

• Intrebarea este:

– Exista un aparat matematic care permite re-zolvarea ecuatiei (∗) ???

• Raspunsul la aceasta ıntrebare este afirmativ. Solutiaecuatiei (∗) este construita ın mod formal ın cadrulmatematic al teoriei domeniilor. In aceasta sectiuneintroducem doar la nivel intuitiv ideea ce sta labaza solutiei.


• Desigur, se poate ınlocui aparitia lui φ din parteadreapta a ecuatiei (∗) cu expresia care ıl definestesi se obtine:

φ = [[ x1 ]] (η | y 7→ [[ x1 ]] (η | y 7→ φ))

• Repetand de un numar finit de ori o asemenea’depliere’ nu vom ajunge ınsa la o solutie a ecuatiei.Totusi, intuitiv, solutia s-ar putea obtine ca limitaa unui sir de asemenea ’deplieri’, cand ’efectul’ (ne-cunoscut al) lui φ din partea dreapta a ecuatiei arputea fi neglijat.

• Fiecare ’depliere’ corespunde, intuitiv, unui nivelde imbricare a apelurilor recursive. Deoarece ınsadorim sa permitem un nivel arbitrar de imbricarea apelurilor recursive este necesar sa angajam unaparat matematic suficient de puternic pentru aobtine o solutie generala pentru ecuatia (∗).

• In matematica, o ecuatie de forma

χ = · · · χ · · ·

se numeste ecuatie de punct fix.


• Formal, solutia ecuatiei (∗) se obtine ca punct fixal unei functii de ordin superior de forma:

f : P → P, f (φ) = [[ x1 ]] (η | y 7→ φ)

pentru orice η ∈ Env. Cu alte cuvinte, pentru unη(∈ Env) dat, solutia ecuatiei (∗) este

fix(f ) = fix(λφ. [[ x1 ]] (η | y 7→ φ))

• fix : (P → P) → P este operatorul ce calculeazapunctul fix al unei functii de tipul P → P. Pro-prietatea caracteristica a acestui operator este:

fix(f ) = f (fix(f ))

• Semantica a constructiei letrec este:

[[ letrec y be x1 in x2 ]] η =

[[ x2 ]] (η | y 7→ fix(λφ. [[ x1 ]] (η | y 7→ φ)))


6.3 Notatia µ

• Constructia letrec este intuitiva dar mai putin con-venabila din punct de vedere matematic.

• In studiile matematice este preferata constructia:

µ y. x

• Utilizand sintaxa Lrec1 , aceasta constructie poate fi

privita drept o prescurtare pentru expresia:

letrec y be x in y

• Expresia µ y. x reprezinta o definitie si ın acelasitimp o utilizare a (un apel al) procedurii y.


• Pentru exemplificare consideram si limbajul Lµ1 ,

definit prin gramatica ((x ∈)X = Lµ1):

x ::= skip | v := n

| x; x | if b then x else x

| y | µ y. x

unde clasele sintactice (v ∈)V, (n ∈)N, (b ∈)B si(y ∈)Y raman ca la Lrec

1 (vezi sectiunea 6.1).

• Semantica constructiei µ se poate defini ın raportcu un mediu semantic η astfel:

[[ µ y. x ]] η = fix( λφ. [[ x ]] (η | y 7→ φ) )

Celelalte definitii si ecuatii semantice se pot pre-lua fara modificari din sectiunea 6.1 si se obtine osemantica directa pentru L

µ1 .

• Se pot efectua urmatoarele calcule:

[[ µ y. x ]] η

= [[ letrec y be x in y ]] η

= [[ y ]] (η | y 7→ fix( λφ. [[ x ]] (η | y 7→ φ) ))

= fix( λφ. [[ x ]] (η | y 7→ φ) )


Exercitii

• E 6.3.1 Se considera urmatorul program scrisıntr-un limbaj de tip Pascal:

v := 0 ;

while v < 10 do v := v + 1 ;

u := 7 ;

Se cere sa se proiecteze un program cu acelasicomportament:

1. ın limbajul Lrec1 utilizand constructia letrec si

2. ın limbajul Lµ1 utilizand constructia µ.


6.4 Semantica de punct fix ın Haskell

• Sintaxa Lrec1 poate fi implementata ın limbajul Haskell

astfel:

data X = Skip | Assign V N

| Seq X X | If B X X

| Call Y | Letrec Y X X

unde declaratiile tipurilor V (variabile) si N (ex-presii numerice) sunt cele introduse la ınceputulcapitolului 5, iar tipurile Y si B sunt definite astfel:

type Y = String

data B = Eq N N | Lt N N

• In aceasta sectiune oferim numai modele ın seman-tica de transformare de stare (ca ın 5.3):

type P = S -> S

• Pentru stari utilizam reprezentarea teoretica ca functiide la variabile la valori (reprezentare introdusa ın5.1.1). Semantica expresiilor numerice (N [[ · ]] )este cea definita ın sectiunea 5.2.

• Semantica expresiilor booleene (B[[ · ]] ) este:

evB :: B -> S -> Bool

evB (Eq n1 n2) s = evN n1 s == evN n2 s

evB (Lt n1 n2) s = evN n1 s < evN n2 s


• Implementam domeniul mediilor semantice prin tipulHaskell Env.

type Env = Y -> D

• Tipul D depinde de tehnica utilizata ın proiectareasemantica (de exemplu type D = P pentru seman-tica directa si type D = Cont -> P pentru se-mantica de continuare).

• Pentru ”perturbarea” mediilor semantice utilizamoperatorul polimorfic upd introdus ın sectiunea 5.1.1.Repetam aici definitia upd:

upd :: Eq a =>

(a -> b) -> a -> b -> (a -> b)

upd f a b a’ =


• In exemplele de test consideram ca initial toateprocedurile sunt nedefinite.

e0 :: Env

e0 y = error ("proc. nedefinita " ++ y)


• Am ales sa reprezentam starile ca functii de la vari-abile la valori.

– Aceasta optiune ne permite sa utilizam acelasioperator polimorfic upd pentru a modifica mediisemantice sau stari.

– Aceasta strategie corespunde mai bine definitiilormatematice.

– In absenta unei instructiuni write ınsa, aceastastrategie ıngreuneaza testarea interpretoarelor.

• In baza mecanismului de evaluare lenesa limbajulHaskell permite urmatoare definitie succinta a op-eratorului de punct fix.

fix :: (a -> a) -> a

fix f = f (fix f)


6.4.1 Semantica directa pentru Lrec1 si L

µ1

• In semantica directa codomeniul semanticiidenotationale este chiar tipul P.

type D = P

• Suntem acum pregatiti pentru prezentarea functieisemantice. Prezentam aici o semantica directa pen-tru limbajul Lrec

1 (oferim implementarea functieisemantice ce a fost introdusa ın sectiunea 6.2, acoloutilizand o notatie matematica).

sem :: X -> Env -> D

sem Skip e = \s -> s

sem (Assign v n) e = \s ->

upd s v (evN n s)

sem (If b x1 x2) e = \s ->

if (evB b s) then sem x1 e s

else sem x2 e s

sem (Seq x1 x2) e =

(sem x2 e) . (sem x1 e)

sem (Call y) e = e y

sem (Letrec y x1 x2) e =

sem x2 (upd e y

(fix

(\d ->

sem x1 (upd e y d))))


• Pentru testarea acestui interpretor semantic se con-sidera urmatorul program Lrec

1

x :: X

x =

Letrec "while"

(If (Lt (V "v") (Z 100))

(Seq

(Assign "v" (Plus (V "v")(Z 1)))

(Call "while"))

Skip

)

(Seq (Assign "v" (Z 0))

(Call "while"))

• Acest program incrementeaza variabila (V "v")

ıntr-o bucla pana cand ajunge la valoarea 100.

• Reprezentarea starilor ca functii ıngreuneaza testareaprogramelor Lrec

1 , dar se pot efectua experimentede genul:

Main> let s = sem x e0 s0 in s "v"

100


• Studiem si limbajul Lµ1 . Implementam sintaxa L

µ1

astfel:

data X = Skip | Assign V N

| Seq X X | If B X X

| Call Y | Mu Y X

• Putem obtine cu usurinta un interpretor semanticpentru limbajul L

µ1 prin simpla ınlocuire a ecuatiei

ce defineste semantica constructiei letrec (din in-terpretorul limbajului Lrec

1 ) cu urmatoarea ecuatiesemantica pentru constructia µ:

sem (Mu y x) e =

fix (\d -> sem x (upd e y d))

• Toate celelalte definitii (date pentru interpretorullimbajului Lrec

1 ) raman neschimbate.


• Pentru testarea acestui interpretor semantic se con-sidera urmatorul program L

µ1 :

x :: X

x =

Seq

(Assign "v" (Z 0))

(Mu "while"

(If (Lt (V "v") (Z 100))

(Seq

(Assign "v" (Plus (V "v")(Z 1)))

(Call "while"))

Skip))


Main> let s = sem x e0 s0 in s "v"

100


6.4.2 Semantica CSC pentru Lrec1 si L

µ1

• Atat continuarile clasice cat si continuarile struc-turate CSC pot fi utilizate fara nici o dificultate ınsemantica de punct fix.

• In aceasta sectiune oferim modele proiectate cutehnica CSC pentru Lrec

1 si Lµ1 . Aceste modele

pot fi reproiectate fara dificultate si cu continuariclasice.

• Aici discutam numai semantica de transformare destare, dar se pot proiecta la fel de bine si modelebazate pe istorii de calcul.


• In proiectarea modelului CSC pentru Lrec1 se uti-

lizeaza toate definitiile si conventiile introduse ınsectiunea 6.4 (ınainte de subsectiunea 6.4.1).

• Definitiile tipurilor Comp, SC, Kont si Cont ramanca ın sectiunea 4.3.2.

• De asemenea, definitiile urmatoarelor constante sifunctii raman ca ın 4.3.2: c0 :: Cont (contin-uarea initiala), operatorul de control addc, functiade executie a continuarii cc, procedura de nor-malizare re, si functia planificator kc.

• Domeniul D (din signatura functiei denotationale)este tot ca ın sectiunea 4.3.2, dar repetam aicidefinitia sa pentru a sublinia faptul ca proiectamo semantica de continuare.

type D = Cont -> P

• Constanta empty (utilizata ın definitia functiei cc)devine:

empty :: P

empty = \s -> s


• Cu aceste pregatiri, semantica CSC pentru Lrec1

este:


sem Skip e c = cc c

sem (Assign v n) e c =

\s -> (cc c (upd s v (evN n s)))

sem (If b x1 x2) e c =

\s -> if (evB b s) then sem x1 e c s

else sem x2 e c s

sem (Seq x1 x2) e c =

sem x1 e (addc (D (sem x2 e)) c)

sem (Call y) e c = e y c

sem (Letrec y x1 x2) e c =

sem x2 (upd e y

(fix

(\d ->

sem x1 (upd e y d)))) c

• Acest interpretor semantic poate fi testat pe pro-gramul Lrec

1 dat ın sectiunea 6.4.1 astfel:

Main> let s = sem x e0 c0 s0 in s "v"

100


• La fel ca si ın sectiunea 6.4.1, plecand de la inter-pretorul CSC al Lrec

1 se poate obtine un interpretorCSC pentru L

µ1 prin simpla ınlocuire a ecuatiei ce

defineste semantica constructiei letrec cu ecuatiasemantica pentru constructia µ:

sem (Mu y x) e c =

fix (\d -> sem x (upd e y d)) c

• Testarea acestui interpretor CSC se poate face peprogramul L

µ1 dat ın sectiunea 6.4.1 astfel:

Main> let s = sem x e0 c0 s0 in s "v"

100


Exercitii

• E 6.4.1 Sa se elaboreze modele semantice proiec-tate cu continuari clasice pentru Lrec

1 si Lµ1 .

Capitolul 7

Semantica de continuare pentru

concurenta

• Tehnica CSC (engl. continuation semantics forconcurrency) [35, 36] permite atat modelarea com-punerii secventiale cat si modelarea compunerii pa-ralele ın semantica de ıntretesere, furnizand o foartebuna flexibilitate ın proiectarea conceptelor de con-trol concurent.

• Intuitiv, tehnica CSC este o formalizare seman-tica a unui planificator de procese simulat pe omasin]ua secventiala. In fiecare moment exista osingura denotatie activa. O denotatie ramane ac-tiva numai pana cand executa o actiune elemen-tara. Ulterior, o alta denotatie, preluata din con-tinuare este planificata spre a deveni activa. Inacest mod se poate modela executia ıntretesuta aproceselor paralele.

83

84 Semantica de continuare pentru concurenta

• Tehnica CSC permite proiectantului de limbaj sastabileasca o relatie simpla ıntre o notiune generalade continuare structurata si conceptele de controlale limbajului (concurent) studiat.

• Am vazut ın capitolele precedente ca pentru mod-elarea compunerii secventiale continuarea poate fistructurata sub forma unei stive de calcule.

• Pentru modelarea compunerii paralele ın seman-tica de ıntretesere1 continuarile CSC pot fi struc-turate utilizand conceptul de multiset.2

• Impreuna, conceptele de stiva si multiset par safurnizeze un fundament pentru semantica de fluentaa controlului.

• In aplicatii mai avansate, se utilizeaza continuariCSC cu structura mai complexa, de exemplu arborips [38], care au la baza o combinatie a conceptelorde stiva si multiset.

• Atat conceptul de stiva cat si conceptul de multisetpot fi implementate ca liste Haskell.

1De exemplu, daca a1 si a2 sunt actiuni elementare (atomice / neıntreruptibile) dintr-un limbajconcurent uniform (notiunea de limbaj uniform a fost introdusa ın capitolul 4) atunci semantica com-punerii paralele a1 ‖ a2 este data de urmatoarea ’multime’ de doua trasari:

[[ a1 ‖ a2 ]] = {a1a2, a2a1}.

ın care actiunile a1 si a2 sunt ’ıntretesute’. Tehnic vorbind, {a1a2, a2a1} este un element al unuidomeniu putere cu structura lineara [4].

In cele ce urmeaza vom defini semantica denotationala a concurentei utilizand tehnica continuarilor,deci functia denotationala va mai avea un parametru (continuarea). Semantica compunerii paralelepoate fi ınsa definita si fara continuari [24, 4].

2Un multiset este o colectie ce admite elemente duplicate.

Semantica de continuare pentru concurenta 85

• Comportamentul structurii de stiva poate fi definitdirect utilizand operatiile de baza (car, cdr, cons)atasate listelor Haskell.

• Comportamentul structurii de multiset (din punc-tul de vedere al planificatoarelor CSC) este definitde urmatorul algoritm de planificare a calculelordintr-un multiset:

ms :: [a] -> [(a,[a])]

ms xs = aux xs []

where aux [] ys = []

aux (x : xs) ys =

(x,xs ++ ys) : aux xs (x : ys)


– Se considera o continuare CSC ınchisa reprezen-tata prin multisetul: [d1,d2,d3]. Atunci:

ms [d1,d2,d3] =

[(d1,[•,d2,d3]),

(d2,[•,d3,d1]),

(d3,[•,d2,d1])]

∗ Exista trei descompuneri (planificari) posi-bile. In fiecare este ales un element al mul-tisetului spre a fi activat iar celelalte douaelemente formeaza o continuare deschisa.

∗ Cerculetul negru ’•’ (care sugereaza lipsa unuielement) indica pozitia conceptuala a elemen-tului activabil (care a fost selectat).

∗ Un multiset este o structura neordonata; pozitiaexacta a elementului activ (sau a celorlalteelemente) ın lista care implementeaza multi-setul nu este importanta.

∗ Alegem sa consideram ca elementul activ esteplasat ın capul listei ce implementeaza con-tinuarea deschisa.


7.1 Compunere paralela

• In aceasta sectiune studiem limbajul Lpar, ce furnizeazao constructie x1 ‖ x2 pentru compunerea par-alela a proceselor. Clasa (x ∈)X a instructiunilorLpar(= X) este introdusa prin uratoarea gramatica:

a ::= v := n | write (n)

x ::= skip | a ·x | if b then x else x

| y | letrec y be x in x | x ‖ x

unde clasele (∈)V a variabilelor numerice, (n ∈)N a expresiilor numerice, (b ∈)B a expresiilorbooleene si (y ∈)Y a variabilelor de procedura suntca ın capitolul 6.

• Reutilizand declaratiile tipurilor V, N, B si Y dincapitolul 6 implementam sintaxa Lpar astfel:

data A = Assign V N | Write N

data X = Skip | Prefix A X | If B X X

| Call Y | Letrec Y X X

| Par X X

• Construim o semantica denotationala pentru Lpar

proiectata cu tehnica CSC.

• In aceasta constructie consideram reprezentarea starilor(tipul S) ca functii de la variabile la valori (vezi


5.1.1), iar semantica expresiilor numerice si booleeneraman ca ın capitolul 6.

• Optam aici pentru o functie semantica ce depindede starea curenta si produce istorii de observabile

1. fie asamblate ın colectia tuturor trasarilor posi-bile,

2. fie alese ın mod (pseudo-)aleator.

• In prima varianta interpretorul semantic implementeazao semantica denotationala clasica ce utilizeaza undomeniu putere [20] pentru a implementa concep-tul de nedeterminism. In acest caz interpretorul nueste tractabil, putand fi testat numai pe programe”de jucarie”.

• In cea de a doua varianta, nedeterminismul iner-ent unui sistem concurent este modelat cu ajutorulunui generator de numere (pseudo-)aleatoare. Inacest caz este vorba despre o simulare a nedeter-minismului, dar interpretorul semantic este tractabilputand fi testat pe programe netriviale.


7.1.1 Specificare

• Incepem prin a prezenta modelul teoretic ce pro-duce toate trasarile posibile pentru un programnedeterminist. In acest model semantica denotationaladepinde de starea curenta si produce colectii detrasari. Implementam acest model pe baza urmatoarelortipuri Haskell:

type P = S -> [Q]

data Q = Empty | Observe Obs Q

type Obs = Int

• Constanta empty este:

empty :: P

empty = \s -> [Empty]

• Tipul Q implementeaza secvente de observabile.In principiu ar fi putut fi implementat printr-odeclaratie de forma type Q = [Obs], dar declaratiapentru care am optat aici va permite o tranzitiemai usoara spre un model semantic ce incorporeazanotiunea de blocare (engl. deadlock) ıntr-o sectiuneulterioara. In anexa B sunt prezentate o instantaEq si o instanta Show pentru aceasta declaratie atipului Q.


• Pentru tipul P implementam:

– o operatie put de prefixare a unei valori obser-vabile la un element de tipul P

put :: Obs -> P -> P

put o p =

\s -> [ Observe o q | q <- p s ]

– doua operatii pentru modelarea alegerii nede-terministe

∗ Operatia ned modeleaza o alegere nedeter-minista ıntre doua alternative; operatiabigned modeleaza o alegere nedeterministaıntre o lista de alternative. Alegerea nede-terminista este aici o reuniune de comporta-mente.

ned :: P -> P -> P

ned p1 p2 = \s -> union (p1 s) (p2 s)

bigned :: [P] -> P

bigned [] = \s -> []

bigned (p : ps) = ned p (bigned ps)

union [] ys = ys

union (x : xs) ys =

if (x ‘elem‘ ys) then union xs ys

else x : union xs ys


• Desi multe definitii se repeta din capitolele an-terioare, pentru a evita orice ambiguitate oferimo prezentare completa a interpretorului semanticpentru Lpar.

• Domeniile D (de denotatii) si Env (de medii seman-tice) sunt cele uzuale pentru semantica de conti-nuare.

type D = Cont -> P

type Env = Y -> D

• Definitia mediului semantic initial e0 precum sidefinitia operatorului polimorfic upd raman ca ınsectiunea 6.4.

• Deocamdata si definitia domeniului de calcule Compramane ca ın 4.3.2, dar aceasta definitie va trebuisa fie modificata ın sectiunea 7.2 odata cu intro-ducerea conceptului de sincronizare.

data Comp = Den D


• Pentru modelarea compunerii paralele (prin executiaıntretesuta) a proceselor din Lpar domeniul con-tinuarilor este definit pe baza unui domeniu PC demultiseturi de calcule. Continuarea initiala(c0 :: Cont) este c0 = [].

type PC = [Comp]

type Kont = PC

type Cont = KontPC

...

Figura 7.1: Structura continuarilor CSC pentru Lpar: un multiset de cal-cule.

Reamintim urmatoarele:

– Cont este domeniul continuarilor deschise (sauactive), iar Kont este domeniul continuarilorınchise.

– O continuare deschisa este un context de eval-uare pentru denotatia activa.

– Continuarile deschise sunt manipulate de eval-uator, iar continuarile ınchise sunt manipulatede planificator.


• Evaluatorului CSC pentru Lpar cuprinde definitiafunctiilor semantice semA si sem ımpreuna cu op-eratorii de control addc si addp.

semA :: A -> D

semA (Assign v n) c =

\s -> cc c (upd s v (evN n s))

semA (Write n) c =

\s -> put (evN n s) (cc c) s


sem Skip e c = cc c

sem (Prefix a x) e c =

semA a (addc (Den (sem x e)) c)

sem (Call y) e c = e y c

sem (Letrec y x1 x2) e c =

sem x2 (upd e y

(fix

(\d ->

sem x1 (upd e y d)))) c

sem (If b x1 x2) e c = \s ->

if evB b s then sem x1 e c s

else sem x2 e c s

sem (Par x1 x2) e c =

sem x1 e (addp (Den (sem x2 e)) c) ‘ned‘

sem x2 e (addp (Den (sem x1 e)) c)


addc :: Comp -> Cont -> Cont

addc p sc = p : sc

addp :: Comp -> Cont -> Cont

addp p pc = p : pc

Compunerea paralela a doua instructiuni x1 si x2este modelata ca o alegere nedeterminista ıntredoua alternative: una ıncepand cu instructiuneax1, cealalta ıncepand cu x2.

In cazul simplu al limbajului Lpar operatorii decontrol addc si addp adauga un calcul la multiset.In alte aplicatii definitiile operatorilor de control aievaluatorului pot fi ceva mai complicate [38].


• Functia de executie a continuarii si procedura denormalizare raman ca ın capitolele precedente; doarconstanta empty se modifica (repetam totusi definitiilefunctiilor cc si re).

cc :: Cont -> P

cc c = case re c of

[] -> empty

k -> kc k

re :: Cont -> Kont

re = id

Procedura de normalizare este functia identitate.Pentru limbaje ce incorporeaza constructii de con-trol mai avansate (de exemplu pentru limbaje mod-elate prin continuari structurate sub forma arbo-rilor ps) definitia procedurii de normalizare esteceva mai complexa.

– Reamintim ca procedura de normalizare trans-forma o continuare activa (deschisa) ıntr-o con-tinuare ınchisa corespunzatoare. In esenta, con-tinuarile CSC sunt normalizare pentru a facilitaprocesul de planificare.


• Planificatorul CSC al limbajului Lpar alege ın modnedeterminist ıntre toate planificarile posibile. Dome-niul planificarilor este Sched. Acest domeniu va fielaborat ın sectiunea 7.2 unde modelam sincronizareaproceselor concurente.

data Sched = Scheda D Cont

kc :: Kont -> P

kc k = bigned (map exe (scheda k))

where exe (Scheda d c) = d c

scheda :: Kont -> [Sched]

scheda k =

[ Scheda d c | (Den d,c) <- actc k ]

actc :: Kont -> [(Comp,Cont)]

actc = ms

Functia scheda utilizeaza actc pentru a calculatoate planificarile de activare posibile. In cazulsimplu al limbajului Lpar (unde o continuare esteun multiset) functia actc coincide cu ms. Pen-tru structuri de continuari mai complexe definitiaactc este mai elaborata.


• Pentru testarea acestui interpretor semantic con-sideram urmatoarea instructiune Lpar:

x1 :: X

x1 =

Par

(Prefix (Write (Z 1))

(Prefix (Write (Z 2)) Skip))

(Prefix (Write (Z 3)) Skip)


Main> sem x1 e0 c0 s0

[[1,2,3],[1,3,2],[3,1,2]]


7.1.2 Prototip

• Pentru testarea unui interpretor semantic modelelebazate pe domenii putere nu sunt convenabile deoarecepot fi evaluate numai pe exemple foarte simple.

– Problema este ca un element al unui domeniuputere este exponential ın lungimea trasarilorde executie.

• Este ınsa posibil sa se modifice un interpretor CSCastfel ıncat sa produca la fiecare executie o singuratrasare aleasa ın mod (pseudo-)aleator. Modificarilenecesare sunt localizate exclusiv la nivelul domeni-ului P.

• In acest scop se utilizeaza un domeniu RNG de gen-eratoare de numere aleatoare. O valoare de tipulRNG este o pereche constand dintr-un numar aleatorsi o functie ce poate produce un numar aleator nou.Un numar aleator este o valoare de tipul R.


• In experimente utilizam urmatorul generator sim-plu de numere aleatoare (preluat din [34]).

type R = Int

type RNG = (R,R -> R)

rng0 :: RNG

rng0 = (17489,

\r -> (25173 * r + 13849)

‘mod‘ 65536)

• Se poate obtine un interpretor CSC pentru Lpar ceproduce o unica trasare (arbitrar aleasa) la fiecareexecutie modificand exclusiv domeniul P si opera-torii atasati cum urmeaza:

type P = S -> RNG -> Q

put :: Obs -> P -> P

put o p = \s r -> Observe o (p s r)


ned :: P -> P -> P

ned p1 p2 = bigned [p1,p2]

bigned :: [P] -> P

bigned ps =

\s (r,next) ->

(rand ps r s (next r,next))

where rand :: [a] -> R -> a

rand xs r =

nth xs (r ‘mod‘ (length xs))

nth :: [a] -> R -> a

nth (x:xs) 0 = x

nth (x:xs) r = nth xs (r-1)

• Mai trebuie modificata doar definitia constanteiempty (care este tot de tip P).

empty :: P

empty = \s r -> Empty

• Toate celelalte definitii raman asa cum au fost dateın sectiunea 7.1.1.


• Pentru testarea acestei noi variante a interpretoru-lui este convenabil sa utilizam urmatoarea functie,care executa de un numar specificat de ori o instructiuneinitializand de fiecare data generatorul de numerealeatoare cu o alta valoare. In consecinta, la executiisuccesive se pot obtine trasari diferite pentru acelasiprogram (daca programul este nedeterminist).

test :: X -> Int -> IO ()

test x n = run x n rng0

where

run :: X -> Int -> RNG -> IO ()

run x 0 rng = return ()

run x n (r,next) =

do print (sem x e0 c0 s0 (r,next))

run x (n-1) (next r,next)


• Pentru testarea interpretorului consideram instructiuneax1 introdusa ın sectiunea 7.1.1, ımpreuna cu urmatoareainstructiune Lpar:

x2 :: X

x2 =

(Letrec "y1"

(If (Lt (Z 0) (V "v"))


(Prefix (Atrib "v"

(Minus (V "v") (Z 1)))

(Call "y1")))

Skip)

(Letrec "y2"

(If (Lt (Z 0) (V "u"))


(Prefix (Atrib "u"

(Minus (V "u") (Z 1)))

(Call "y2")))

Skip)

(Letrec "y3"

(If (Lt (Z 0) (V "w"))


(Prefix (Atrib "w"

(Minus (V "w") (Z 1)))

(Call "y3")))

Skip)


(Prefix (Atrib "v" (Z 5))

(Prefix (Atrib "u" (Z 5))

(Prefix (Atrib "w" (Z 5))

(Par (Par (Call "y1") (Call "y2"))

(Call "y3"))))))))

• Programul x2 executa ın paralel trei procese; executiaproceselor paralele apare ıntretesuta pentru obser-vatorul extern.

• Se pot efectua urmatoarele experimente:

Main> test x1 5

[3,1,2]

[1,3,2]

[3,1,2]

[1,3,2]

[3,1,2]

Main> test x2 5

[2,3,1,3,2,1,2,3,1,2,3,1,2,1,3]

[3,1,2,3,1,3,2,2,1,3,1,2,3,1,2]

[2,1,3,2,1,3,3,1,2,2,1,3,1,2,3]

[3,1,2,3,3,2,1,3,2,1,3,2,1,2,1]

[2,1,3,3,1,2,2,3,1,2,3,1,3,1,2]

• In general, la fiecare executie se poate obtine otrasare diferita.


7.2 Comunicare sincrona

• Introducem un limbaj Lsyn, care extinde Lpar cucomunicare sincrona de tip CSP [12, 13].

• Clasa (x ∈)X a instructiunilor Lsyn(= X) estedata de urmatoarea gramatica:

a ::= v := n | write (n)

x ::= skip | a ·x | if b then x else x

| y | letrec y be x in x | x ‖ x

| ned [( ϑ → i )∗]

• Unica noutate este data de constructianed [( ϑ → i )∗] . Toate celelalte constructii si clasesintactice raman ca ın limbajul Lpar.

• Se utilizeaza o clasa (c ∈)Ch de canale de comu-nicare. Garzile alternativelor nedeterminste sunt:

ϑ ::= c!n | c?v


• Oferim un exemplu de program Lsyn:

letrec y1 be

if (0 < v) then ned [ c!(v − 1) → y1

| c!(v + 1) → y1

| c!(v − 1) → y1 ]

else skip

in letrec y2 be

if (0 < v) then

ned [ c?v → write (v) · y2 ]

else skip

in v := 3 · write (v) · (y2 ‖ y1 ‖ y1 ‖ y2)

Acest program creeaza o retea de 4 procese co-municante, care tind (ın mod nedeterminist) samicsoreze valoarea variabilei v. Nu este dificil devazut ca programul se poate termina normal, darse poate termina si ın deadlock.


• Constructiile c!n si c?v sunt ca ın Occam [14].

• Executia sincrona a doua actiuni c!n, c?v care aparın procese paralele revine la transmiterea valoriiexpresiei n prin canalul c de la procesul care ex-ecuta instructiunea de transmitere c!n la proce-sul care executa instructiunea de receptionare c?v.Procesul care receptioneaza valoarea expresiei n oatribuie variabilei v.

• Este un mecanism de atribuire distribuita. Mecan-ismul este sugerat ın figura de mai jos, ın care pro-cesele paralele sunt reprezentate sub forma de cer-curi, iar valoarea expresiei n este notata prin V (n).

c?vV(e)

c!n


• O constructie ned [( ϑ → i )∗] contine un set dealternative nedeterministe gardate prin primitivede comunicare (c!n sau c?v).

• Daca se poate realiza sincronizarea cu procese con-curente pe mai multe alternative, atunci se va alegeın mod nedeterminist una dintre alternative.

• Un proces este suspendat atat timp cat sincronizareacu procese paralele nu este posibila.

• Un program ajunge ın stare de blocare, sau dead-lock, atunci cand toate procesele paralele sunt sus-pendate pe tentative de comunicare nereusite.

• Un program se termina normal daca toate proce-sele ısi finalizeaza activitatea.


• Implementam sintaxa Lsyn astfel:

data A = Assign V N | Write N

data X = Skip | Prefix A X | If B X X

| Call Y | Letrec Y X X | Par X X

| Ned [(C,X)]

data C = Snd Ch N | Rcv Ch V

type Ch = String

unde Ch este tipul canalelor de comunicatie si Ceste tipul garzilor alternativelor nedeterministe.

• Clasa instructiunilor este modificata ın raport cudefinitia corespunzatoare pentru Lpar numai prinadaugarea alternativei Ned [(C,X)].

• Tipurile V, N, B si Y sunt la fel ca pentru Lpar.

• In cele ce urmeaza prezentam numai extensiile simodificarile ce trebuie sa fie aduse definitiilor dateın sectiunea 7.1 pentru limbajul Lpar pentru a seobtine un interpretor semantic pentru limbajul Lsyn.


• Este mai ıntai necesar sa redefinim domeniul deliste de observabile pentru a reflecta posibilitateade blocare (engl. deadlock) a programelor Lsyn.

data Q = Empty | Deadlock

| Observe Obs Q

• Instantele Eq si Show atasate tipului Q sunt dateın anexa C (Obs este un sinonim pentru tipul Int,type Obs = Int, la fel ca ın sectiunea 5.4.3).

• Pentru a modela sincronizarea proceselor concurenteextindem definitia domeniului de calcule Comp ast-fel:

data SemC = SemSnd Ch (S -> Int)

| SemRcv Ch V

data Comp = Den D | Sync [(SemC, D)]

• Definitiile domeniilor pentru denotatii (D), mediisemantice (Env) si continuari (tipurile Cont, Kontsi PC) raman ca ın sectiunea 7.1, dar domeniul con-tinuarilor utilizeaza noul domeniu de calcule Comp.De asemenea mediul semantic initial (e0) si con-tinuarea initiala (c0) raman ca ın 7.1.


• Evaluatorul CSC pentru limbajului Lsyn se poateobtine din evaluatorul CSC al limbajului Lpar prinadaugarea urmatoarei ecuatii ce defineste seman-tica constructiei (Ned gx):

sem (Ned gx) e c = cc (addc p c)

where

p = Sync [(semC g, sem x e)

| (g, x) <- gx]

semC :: C -> SemC

semC (Snd ch e) = SemSnd ch (evN e)

semC (Rcv ch v) = SemRcv ch v

Toate celelalte clauze ale functiei semantice sem,precum si functia semantica semA si operatorii decontrol addc si addp raman ca ın sectiunea 7.1.

• De asemenea, functia de executie a continuarii cc(inclusiv constanta empty) si procedura de nor-malizare re raman ca ın sectiunea 7.1.


• Planificatorul CSC pentru limbajul Lsyn reutilizeazanumai definitiile functiilor scheda si actc date ınsectiunea 7.1 pentru Lpar. Domeniul planificarilorSched si functia planificator trebuie sa fie modifi-cate ca mai jos.

data Sched = Scheda D Cont

| Scheds V (S -> Int) Kont

kc :: Kont -> P

kc k = case scheda k ++ scheds k of

[] -> deadlock

ws -> bigned (map exe ws)

where exe (Scheda d c’) = d c’

exe (Scheds v pe k’) =

\s -> kc k’ (upd s v (pe s))

scheds :: Kont -> [Sched]

scheds k = [ w | (ps,pc) <- ms k,

w <- sync [ps] pc ]


sync :: Kont -> Kont -> [Sched]

sync k1 k2 =

[ Scheds v pe (re (addc (Den d1) c1) ++

re (addc (Den d2) c2))

| (Sync snd, c1) <- actc k1,

(Sync rcv, c2) <- actc k2,

(SemSnd chs pe, d1) <- snd,

(SemRcv chr v, d2) <- rcv,

chs == chr ]

Reamintim ca functia scheda (data ın 7.1) cal-culeaza lista planificarilor de activare de forma(Scheda d c). Planificatorul kc mai utilizeazaacum o functie scheds ce calculeaza lista plani-ficarilor de sincronizare de forma(Scheds v pe k).

• Implementarea constantelor empty si deadlockdepinde de tipul de semantica considerat: toatetrasarile posibile sau o singura trasare.


7.2.1 Specificare

• Pentru a obtine un model semantic ce calculeazatoate trasarile posibile pentru orice program Lsyn

se poate reutiliza tipul P asa cum a fost definitımpreuna cu operatorii put, ned, bigned si con-stanta empty ın sectiunea 7.1.1. In acest caz con-stanta deadlock este:

deadlock :: P

deadlock = \s -> [Deadlock]

• Pentru testare consideram urmatorul program Lsyn:

x3 :: X

x3 =

Par

(Ned [(Snd "c" (Z 1),

Ned [(Rcv "c" "v", Skip)]),

(Snd "c" (Z 2),

Prefix (Write (Z 3)) Skip)])

(Ned [(Rcv "c" "v",

Prefix (Write (V "v")) Skip)])


Main> sem x3 e0 c0 s0

[[1,deadlock],[3,2],[2,3]]


7.2.2 Prototip

• Pentru a obtine un model semantic ce calculeazao singura trasare aleasa ın mod (pseudo-)aleatorpentru orice program Lsyn se poate reutiliza tipulP asa cum a fost definit ımpreuna cu operatoriiput, ned, bigned si constanta empty ın sectiunea7.1.2. In acest caz constanta deadlock este:

deadlock :: P

deadlock = \s r -> Deadlock


• Pentru testare consideram urmatorul program Lsyn:

x4 :: X

x4 =

LetRec "y1"

(If (Lt (Z 0) (V "v"))

(Ned

[(Snd "c" (Minus (V "v") (Z 1)),

Call "y1"),

(Snd "c" (Plus (V "v") (Z 1)),

Call "y1"),

(Snd "c" (Minus (V "v") (Z 1)),

Call "y1")

])

Skip)

(LetRec "y2"

(If (Lt (Z 0) (V "v"))

(Ned [(Rcv "c" "v",

Prefix (Write (V "v"))

(Call "y2"))])

Skip)

(Prefix (Assign "v" (Z 3))

(Prefix (Write (V "v"))

(Par (Par (Call "y2")

(Call "y1"))

(Par (Call "y1")

(Call "y2"))))))


Constanta x4 implementeaza programul dat ın sin-taxa abstracta la ınceputul sectiunii 7.2.

• Utilizand functia test data ın sectiunea 7.1.2 sepoate efectua urmatorul experiment:

Main> test x4 5

[3,4,3,2,1,0,deadlock]

[3,2,0,0]

[3,2,2,2,2,2,4,4,2,2,3,4,3,4,4,4,2,1,

1,0,deadlock]

[3,2,4,4,4,4,3,4,2,3,4,4,3,1,0,0]

[3,2,0,0,deadlock]

Se remarca faptul ca prima, a treia si ultima trasarede executie se termina ın deadlock.

Capitolul 8

Semantica constructiilor aplicative

• In acest capitol studiem un limbaj aplicativ Lpcf detip PCF1 [21]. Prezentarea porneste de la [8, 33, 7].

• In esenta, PCF extinde calculul λ simplu tipizatcu constante si operatii peste tipuri primitive.

• Introducem Lpcf printr-o definitie BNF ımpreunacu reguli de deductie ce permit verificarea staticaa corectitudinii tipurilor. Regulile de deductie aula baza pe triplete de forma:

u ⊢ x : t

unde u este o atribuire de tipuri (notiune ce va fiexplicata imediat), x este un termen Lpcf si t esteun tip.

• Un triplet u ⊢ x : t exprima faptul ca termenulx are tipul t ın raport cu atribuirea de tipuri u.

1Programming Language for Computable Functions

117

118 Semantica constructiilor aplicative

8.1 Un limbaj de tip PCF

• Introducem sintaxa constructiilor (x(∈ X)) si tipurilor(t) Lpcf prin urmatoarea gramatica:

t ::= bool | nat | t → t

x ::= true | 0

| not(x) | succ(x) | pred(x)

| x and x | x == x | · · ·

| i | if x then x else x | let i be x in x

| x x | λ i : t . x | µ i : t. x

• Explicatii

– Constantele si operatiile primitive au semanticaintuitiva. Se pot introduce si alte constante sialti operatori peste tipurile primitive.

– Tipul unui identificator i este definit ın raportcu o atribuire de tipuri, iar semantica sa estedefinita ın raport cu un mediu semantic.

– Intr-o constructie x1 x2 termenul x1 denota ofunctie ce poate fi aplicata asupra valorii ter-menului x2.

– Constructia λ i : t . x reprezinta o abstractielambda ın care t este tipul identificatorului i.

– Constructia µ i : t. x este folosita pentru definitiirecursive, ın care t este tipul identificatorului i.

Semantica constructiilor aplicative 119

• Implementam sintaxa Lpcf ın Haskell astfel:

type I = String

data T = BOOL | NAT | Fun T T

data X = TRUE | ZERO

| Not X | Succ X | Pred X

| And X X | Eq X X | Mul X X

| I I | If X X X | Let I X X

| Apply X X | Lambda (I,T) X

| Mu (I,T) X

• Pentru a simplifica testarea interpretorului am in-trodus si constructia (Mul x1 x2) pentru operatiade ınmultire x1 ∗ x2 (care nu apare ın sintaxa ab-stracta). Desigur, se pot introduce si alte asemeneaoperatii primitive.

– Nu este ınsa dificil de vazut ca operatii precumadunarea sau ınmultirea se pot implementa prindefinitii recursive pe baza operatiilor primitivesucc si pred. De aceea, nu este uzual ca operatiiprecum ınmultirea sa fie predefinite ın studiilesemantice asupra PCF.

• Anexa D contine instantele Eq si Show utilizate ınacest capitol.


8.2 Verificarea tipurilor

• Fie (i ∈)I o clasa de identificatori. O atribuirede tipuri u(∈ U) este o lista i1 : t1, ..., in : tnde perechi identificator-tip, ın care identificatoriiii sunt distincti. Conceptual, o atribuire de tipurieste o functie ce mapeaza un domeniu (finit de)identificatori la tipuri. In Haskell punem:

type U = [(I,T)]

• Pentru atribuirile de tipuri definim o operatie de”perturbare” (u | i 7→ t), implementata aici defunctia updu, si o operatie de evaluare u(i), imple-mentata de functia iu.2

2updu este o simpla redenumire a functiei upd data ın anexa A; iu este o varianta a functiei valdin anexa A.


updu :: Eq a =>

[(a,b)] -> a -> b -> [(a,b)]

updu [] a b = [(a,b)]

updu ((a’,b’) : u) a b =

if (a == a’) then (a,b) : u

else (a’,b’) : updu u a b

iu :: I -> U -> T

iu i [] =

error ("Id. nelegat: " ++ i)

iu i ((i’,t’) : u) =

if (i == i’) then t’ else iu i u


• Verificarea tipurilor expresiilor Lpcf se poate facepe baza unui set de reguli de forma [33, 8, 16]:

u1 ⊢ x1 : t1 · · · un ⊢ xn : tn

u ⊢ · · ·x1 · · ·xn · · · : t

• De exemplu, regula pentru conjunctia logica este(aici se utilizeaza aceeasi atribuire de tipuri ın premisesi ın concluzie, dar nu toate regulile respecta oasemenea disciplina):

u ⊢ x1 : bool u ⊢ x2 : bool

u ⊢ x1 and x2 : bool

• Regulile sunt proiectate astfel ıncat sa ataseze untip unic oricarei expresii Lpcf . In Haskell, spe-cificam aceste reguli de deductie printr-o functie:

t :: X -> U -> T

De exemplu, specificam regula pentru conjunctieastfel:

t (And x1 x2) u =

case (t x1 u,t x2 u) of

(BOOL,BOOL) -> BOOL

_ -> err "And"


• Functia auxiliara err este:

err :: String -> a

err s = error ("Eroare de tip: " ++ s)

• Oferim acum definitia completa a functiei t ceataseaza un tip unic oricarei expresii Lpcf ın ra-port cu o atribuire de tipuri data.

t :: X -> U -> T

t TRUE u = BOOL

t ZERO u = NAT

t (Not x) u =

case t x u of

BOOL -> BOOL

_ -> err "Not"

t (Succ x) u =

case t x u of

NAT -> NAT

_ -> err "Succ"

t (Pred x) u =

case t x u of

NAT -> NAT

_ -> err "Pred"

t (And x1 x2) u =


(BOOL,BOOL) -> BOOL

_ -> err "And"


t (Eq x1 x2) u =


(BOOL,BOOL) -> BOOL

(NAT ,NAT ) -> BOOL

_ -> err "Eq"

t (Mul x1 x2) u =


(NAT,NAT) -> NAT

_ -> err "Mul"

t (I i) u = iu i u

t (If b x1 x2) u =

case (t b u,t x1 u,t x2 u) of

(BOOL,t1,t2) ->

if (t1 == t2)

then t1

else err "If"

_ -> err "If"

t (Let i x1 x2) u =

t x2 (updu u i (t x1 u))

t (Apply x1 x2) u =


(Fun t1 t1’,t2) ->

if (t1 == t2)

then t1’

else err "Apply"

_ -> err "Apply"


t (Lambda (i,ti) x) u =

Fun ti (t x (updu u i ti))

t (Mu (i,ti) x) u =

if (t x (updu u i ti) == ti)

then ti

else err "Mu"


Exercitii

• E 8.2.1 Sa se descrie regulile implementate defunctia t utilizand notatia abstracta:

u1 ⊢ x1 : t1 · · · un ⊢ xn : tn

u ⊢ · · ·x1 · · ·xn · · · : t


8.3 Semantica

• Datorita recursivitatii, semantica Lpcf poate fi definitaın mod riguros doar ın cadrul matematic al teorieidomeniilor (vezi, de exemplu, [33, 8, 16]).

• Un domeniu este o structura matematica care de-scrie notiunea de calcul si aproximare [29].

– Dana Scott a introdus un element, ⊥, pentrureprezentarea notiunii de calcul ”nedefinit” sau”divergent” (care nu se termina).

– ⊥ este cel mai mic element al unui domeniuın abordarea clasica ın care se opereaza cu con-ceptul de cel mai mic punct fix (al unei functiicontinue).

– In aceasta abordare se utilizeaza adesea notiuneade multime partial ordonata completa (engl.complete partial order (cpo)3) ca sinonim pen-tru conceptul de domeniu semantic.

3Ideile de baza sunt urmatoarele (pentru mai multe informatii cititorul poate consulta [33, 8, 16]):

1. O relatie de ordine partiala ’⊑’ peste o multime (x, y, z) ∈ X este o relatie:

reflexiva: x ⊑ x

tranzitiva: x ⊑ y si y ⊑ z implica x ⊑ z, si

antisimetrica: x ⊑ y si y ⊑ x implica x = y.

2. Foarte pe scurt, o multime partial ordonata (x ∈)X este (ω-)completa daca odata cu toateelementele unui (ω-)sir crescator x1 ⊑ x2 · · · ⊑ xn ⊑ · · · contine si elementul supremum (engl.least upper bound) al sirului.


• De exemplu, daca opsyn este un operator sintac-tic unar (cum este succ , pred sau not ) atuncisemantica expresiei opsyn(x) este:

[[ opsyn(x) ]] η =

{

opsem( [[ x ]] η) daca [[ x ]] η 6= ⊥⊥ daca [[ x ]] η = ⊥

– Se evalueaza expresia x (ın mediul semanticη) si daca rezultatul este definit atunci asuprarezultatului se aplica operatorul semantic opsem .

– Daca rezultatul evaluarii expresiei x este nedefinit(⊥) atunci si rezultatul evaluarii expresiei opsyn(x)este nedefinit.

• In Haskell nu vom implementa explicit constanta⊥. Aceasta este o abstractie ce exprima un calculcare nu se termina (un calcul divergent).

• De exemplu, vom implementa semantica unei operatiiopsyn(x) (ın Haskell (OpSyn x)) ın forma:

sem (OpSyn x) e = opSem (sem x e)

• Calculele care nu se termina pot fi modelate ınHaskell pe baza mecanismului de evaluare lenesa.Daca ınsa evaluarea semanticii (sem x e) nu setermina atunci nici pentru expresia (OpSyn x) nuse va putea calcula semantica.


• In absenta recursivitatii, semantica tipurilor Lpcf

ar putea fi definita (inductiv) astfel:

[[ bool ]] = {true, false}

[[ nat ]] = N

[[ t1 → t2 ]] = [[ t1 ]] → [[ t2 ]]

unde aici [[ · ]] este multimea valorilor (interpretarilor)semantice de tipul ’·’.

– O expresie de tip bool s-ar evalua la o valoare∈ {true, false},

– o expresie de tip nat s-ar evalua la o valoare∈ N,

– o expresie de tip nat → nat s-ar evalua la ofunctie ∈ N → N, etc.


• In prezenta recursivitati, este necesar sa se utilizezedomenii (iar nu multimi ordinare) pentru inter-pretarea semantica. Schitam cateva idei:

– Orice multime (m ∈)M devine un cpo (M,⊑)daca este echipata cu relatia de ordine discreta:

m1 ⊑ m2 ⇔ m1 = m2.

– Pentru orice multime M se poate construi uncpo M⊥ = (M ∪ {⊥},⊑) ın care

m1 ⊑ m2 ⇔ (m1 = m2 sau m1 = ⊥)

– Este posibil sa se defineasca ın mod rigurosoperatii ce construiesc spatii de functii (→),produse carteziene (×) si sume (+) de domenii,rezultatele pastrand structura de domeniu (cpo).

• Domeniul pentru semantica denotationala a lim-bajului Lpcf poate fi definit (prin inductie dupastructura tipurilor t) astfel:

[[ bool ]] = {true, false}⊥[[ nat ]] = N⊥

[[ t1 → t2 ]] = [[ t1 ]] → [[ t2 ]]


• Dupa cum am explicat ınainte, ın implementareaHaskell nu exista o reprezentare explicita pentru el-ementul cel mai mic al unui domeniu (⊥), divergentafiind modelata pe baza mecanismului de evaluarelenesa. Domeniul semanticii denotationale a Lpcf

poate fi implementat prin urmatoarea declaratiede tip Haskell:

data D = B Bool | N Int | F (D -> D)

• In Lpcf semantica unui termen x depinde de tipul

identificatorilor pe care ıi contine. In general, se-mantica unui termen x se defineste ın raport cuo atribuire de tipuri u fata de care x are tipul t:u ⊢ x : t.

• Exista o legatura naturala ıntre mediile semantice(care mapeaza identificatori la valori) si atribuirilede tipuri (care mapeaza identificatori la tipuri).


• Spunem despre un mediu semantic η ca este com-patibil [33] cu o atribuire de tipuri u daca pentruorice identificator i din domeniul lui u

(u = ..., i : t, ...), η(i) ∈ [[ u(i) ]] (= [[ t ]] ).

– Notam cu (η ∈)Envu domeniul mediilor se-mantice compatibile cu atribuirea de tipuri u.

• Semantica denotationala poate fi definita pentrufiecare atribuire de tipuri u si tip t prin functii[[ · ]] ut ce mapeaza termeni x pentru care u ⊢ x : t

la functii de la Envu la [[ t ]] :

[[ · ]] ut : {x | u ⊢ x : t} → Envu → [[ t ]]

• De exemplu, ecuatia ce defineste semantica abstractieiµ este:

[[ µ i : t. x ]] ut η =

fix(λd . [[ x ]] (u|i7→t)t(η | i 7→ d))

• Indicii u si t sunt ınsa adesea omisi din ecuatiilesemantice.


Exercitii

• E 8.3.1 Sa se descrie ın forma [[ x ]] ut η = · · ·ecuatiile ce definesc semantica urmatoarelorconstructii Lpcf :

0 −constanta 0

succ(x) −operatia succesori −identificatorλ i : t . x −abstractie λ

x1 x2 −aplicareµ i : t. x −abstractie µ


• Interpretorul semantic pentru limbajul Lpcf esteproiectat ın baza presupunerii ca verificarea tipuriloreste realizata static (ınainte de executie) printr-un apel al functiei t (vezi definitia functiei exe).

– In consecinta, indicii u si t nu apar ın ecuatiilece definesc functia semantica sem.

• Semantica denotationala a Lpcf utilizeaza opera-torul fix definit ın sectiunea 6.4.

• Operatorul upde (utilizat aici doar pentru ”pertur-barea” mediilor semantice) coincide cu operatorulupd definit ın sectiunea 5.1.1, dar este redenumitpentru a nu fi confundat cu operatorul updu (uti-lizat aici numai pentru atribuiri de tipuri).

upde :: Eq a =>

(a -> b) -> a -> b -> (a -> b)

upde f a b a’ =


• Domeniul mediilor semantice este:

type Env = I -> D


• Implementam semantica denotationala a Lpcf ast-fel (pentru definitiile matematice se poate consulta,de exemplu, [33, 8, 16]):


sem TRUE e = B True

sem ZERO e = N 0

sem (Not x) e = nots (sem x e)

sem (Succ x) e = succs (sem x e)

sem (Pred x) e = preds (sem x e)

sem (And x1 x2) e =

ands (sem x1 e) (sem x2 e)

sem (Eq x1 x2) e =

eqs (sem x1 e) (sem x2 e)

sem (Mul x1 x2) e =

muls (sem x1 e) (sem x2 e)

sem (I i) e = e i

sem (If b x1 x2) e =

ifs (sem b e) (sem x1 e) (sem x2 e)

sem (Let i x1 x2) e =

sem x2 (upde e i (sem x1 e))

sem (Apply x1 x2) e =

applys (sem x1 e) (sem x2 e)

sem (Lambda (i,ti) x) e =

F (\d -> sem x (upde e i d))

sem (Mu (i,ti) x) e =

fix (\d -> sem x (upde e i d))


• Operatorii semantici sunt:

nots :: D -> D

nots (B b) = B (not b)

succs :: D -> D

succs (N n) = N (n + 1)

preds :: D -> D

preds (N n) =

if (n > 0) then N (n - 1) else N 0

ands :: D -> D -> D

ands (B b1) (B b2) = B (b1 && b2)

eqs :: D -> D -> D

eqs (B b1) (B b2) = B (b1 == b2)

eqs (N n1) (N n2) = B (n1 == n2)

muls :: D -> D -> D

muls (N n1) (N n2) = N (n1 * n2)

ifs :: D -> D -> D -> D

ifs (B b) d1 d2 = if b then d1 else d2

applys :: D -> D -> D

applys (F f) d = f d


• Pentru testarea interpretorului Lpcf mai utilizamurmatoarele definitii:

exe :: X -> IO ()

exe x =

do print (t x u0)

print (sem x e0)

where

u0 :: U

u0 = []

e0 :: Env

e0 i =

error ("Id. nedefinit: " ++ i)

n :: Int -> X

n 0 = ZERO

n k = Succ (n (k-1))


• Fie acum:

x :: X

x =

Apply

(Mu ("factorial",Fun NAT NAT)

(Lambda ("n",NAT)

(If (Eq (I "n") ZERO)

(n 1)

(Mul (I "n")

(Apply (I "factorial")

(Pred (I "n"))))

)

)

)

(n 5)


Main> exe x

NAT

120

Bibliografie

[1] P. America. Issues in the design of a parallel object-oriented language. Formal Aspects of Computing,1(4):366–411, 1989.

[2] P. America, J.W. de Bakker, J.N. Kok, J.J.M.M.Rutten. Denotational semantics of a parallel ob-ject oriented language. Information and Compu-tation, 83(2):152–205, 1989.

[3] P. America and J.J.M.M. Rutten. Solving reflexivedomain equations in a category of complete metricspaces. Journal of Computer System Sciences,39:343–375, 1989.

[4] J.W. De Bakker, E.P. De Vink. Control flow se-mantics. MIT Press, 1996.

[5] S. Brookes. The essence of parallel Algol. Infor-mation and Computation, 179(1):118–149,2002.

[6] O. Danvy. On evaluation contexts, continuationsand the rest of the computation. In H. Thielecke,editor, Proceedings of the 4th ACM SIGPLAN

139

140

Continuations Workshop (CW’04), pages 13–23,2004.

[7] M. Felleisen and M. Flat. Programming lan-guages and Lambda calculi. Available fromhttp://www.cs.utah.edu/plt/publications/pllc.pdf

2006.

[8] C. Gunter. Semantics of programming lan-guages: structures and techniques. MIT Press,1992.

[9] C.A. Gunter, D.S. Scott. Semantic domains. InJ. van Leeuwen, editor, Handbook of TheoreticalComputer Science, pages 633-674, 1990.

[10] M. Hennessy, G.D. Plotkin. Full abstraction for asimple parallel programming language. In Proc. of8th Symposium on Mathematical Foundations ofComputer Science, LNCS 74, pages 108-120, 1979.

[11] R. Hieb, R.K. Dybvig and C.W. Anderson. Sub-continuations. Lisp and Symbolic Computation,7(1):83–110, 1994.

[12] C.A.R. Hoare. Communicating sequential pro-cesses. Communications of the ACM, 21:667-677,1978.

[13] C.A.R. Hoare. Communicating sequential pro-cesses. Prentice Hall, 1985.

141

[14] INMOS Ltd. Occam programming manual.Prentice Hall, 1984.

[15] S. Mac Lane. Categories for the working math-ematician. Springer, 1971.

[16] J.C. Mitchell. Foundations for programminglanguages. MIT Press, 1996.

[17] P.W. O’Hearn and R.D. Tennent. Algol-like lan-guages. Birkhauser, 1997.

[18] S. Peyton Jones and J. Hughes, editors. Reporton the programming language Haskell 98: a non-strict purely functional language. Yale University,Department of Computer Science, Tech. ReportYALEU/DCS/RR-1106, 1999.

[19] B. Pierce. Types and programming languages.MIT Press, 2002.

[20] G. Plotkin. A powerdomain construction. SIAMJournal on Computing, 5:522–587, 1976.

[21] G. Plotkin. LCF considered as a programminglanguage. Theoretical Computer Science, 5:223-255, 1977.

[22] G. Plotkin. The category of complete partial or-ders: a tool for making meanings. Lecture notes

142

for the Summer School on Foundations of ArtificialIntelligence and Computer Science, Pisa, 1978.

[23] G. Plotkin. A structural approach to operationalsematics. Report DAIMI FN-19, Aaurhus Univer-sity, 1981.

[24] G. Plotkin. Pisa notes, 1983.

[25] D.S. Scott. Outline of a mathematical theory ofcomputation. In Proc. of 4th Annual PrincetownConference of Inf. Sciences and Systems, pages169–176, Princetown, 1970.

[26] D.S. Scott. Data types as lattices. SIAM Journalon Computing, 5:522–587, 1976.

[27] D.S. Scott and C. Stratchey. Towards a mathe-matical semantics for computer languages. In Proc.Symp. on Computers and Automata, vol. 21 ofMicrowave Research Institute Symposia Series,pages 19–46, New York, 1971.

[28] M.B. Smyth and G.D. Plotkin. The category-theoretic solution of recursive domain ecuations.SIAM Journal on Computing, 11:761–783, 1982.

[29] V. Stoltenberg-Hansen, I. Lindstrom and E.R.Griffor. Mathematical theory of domains. Cam-bridge University Press, 1994.

143

[30] C. Strachey. Towards a formal semantics. InProc. IFIP TC2 Working Conference on For-mal Language Description Languages for Com-puter Programming, pages 198–220, Amsterdam,1966.

[31] C. Strachey. Fundamental concepts of program-ming languages. Lecture Notes for a NATO Sum-mer School, Copenhagen, 1967.

[32] C. Strachey and C. Wadsworth. Continuations:a mathematical semantics for handling full jumps.Tech. Monograph PRG-11, Programming ResearchGroup, Univ. Oxford, 1974.

[33] R.D. Tennent. Semantics of programming lan-guages. Prentice Hall, 1991.

[34] S. Thompson. Haskell: the craft of functionalprogramming. Addison-Wesley, 1999.

[35] E.N. Todoran. Metric semantics for synchronousand asynchronous communication: a continuation-based approach. In Proceedings of FCT’99 Work-shop on Distributed Systems, Electronic Notesin Theoretical Computer Science (ENTCS),28:119–146, Elsevier, 2000.

[36] E.N. Todoran, N. Papaspyrou. Continuations forparallel logic programming. In Proc. of 2nd Inter-

144

national ACM-SIGPLAN Conference on Prin-ciples and Practice of Declarative Programming(PPDP’00), pages 257–267, ACM Press, 2000.

[37] E.N. Todoran and N.S. Papaspyrou. Denotationalprototype semantics for a simple concurrent lan-guage with synchronous communication. Techni-cal Report CSD-SW-TR-1-04, National TechnicalUniversity of Athens, School of Electrical and Com-puter Engineering, Software Engineering Labora-tory, 2004.

[38] E.N. Todoran and N.S. Papaspyrou. Continua-tions for prototyping concurrent languages. Tech-nical Report CSD-SW-TR-1-07, National Techni-cal University of Athens, School of Electrical andComputer Engineering, Software Engineering Lab-oratory, 2007.

Anexa A

Definitii pentru starea ca lista de

asociatie

• Aceasta anexa ofera implementarea operatorilorval si upd pentru reprezentarea conceptului destare ca lista de asociatie data ın sectiunea 5.1.2.

• Operatorul val este:

val :: V -> S -> Int

val v [] =

error ("var. neinitializata" ++ v)

val v ((v’,z’):s) =

if (v == v’) then z’ else val v s

• upd poate fi implementat ca operator polimorfic:

upd :: Eq a =>

[(a,b)] -> a -> b -> [(a,b)]

upd [] a b = [(a,b)]

upd ((a’,b’) : s) a b =

if (a == a’) then ((a,b) : s)

else (a’,b’) : upd s a b

145

Anexa B

Definitii auxiliare pentru sectiunea

7.1

instance Eq Q where

Empty == Empty =

True

Observe o1 q1 == Observe o2 q2 =

(o1 == o2) && (q1 == q2)

_ == _ = False

instance Show Q where

show Empty = "[]"

show q = "[" ++ (aux q) ++ "]"

where aux :: Q -> String

aux (Observe o Empty) = show o

aux (Observe o q) =

(show o) ++ "," ++ (aux q)

146

Anexa C

Definitii auxiliare pentru sectiunea

7.2

instance Eq Q where

Empty == Empty = True

Deadlock == Deadlock = True

Observe o1 q1 == Observe o2 q2 =

(o1 == o2) && (q1 == q2)

_ == _ = False

instance Show Q where

show Empty = "[]"

show Deadlock = "[deadlock]"

show q = "[" ++ (aux q) ++ "]"

where aux :: Q -> String

aux (Observe o Empty) = show o

aux (Observe o Deadlock) =

(show o) ++ "," ++ "deadlock"

aux (Observe o q) =

(show o) ++ "," ++ (aux q)

147

Anexa D

Definitii auxiliare pentru capitolul 8

instance Eq T where

BOOL == BOOL = True

NAT == NAT = True

(Fun t1 t2) == (Fun t1’ t2’) =

(t1 == t1’) && (t2 == t2’)

_ == _ = False

instance Show T where

show BOOL = "BOOL"

show NAT = "NAT"

show (Fun t1 t2) =

"(Fun " ++ (show t1) ++

" " ++ (show t2) ++")"

instance Show D where

show (B b) = show b

show (N n) = show n

show (F f) = "{functie}"

148

semantica limbajelor formaleusers.utcluj.ro/~eneia/limbaje.pdf · cuprins i introducere 1 1...

Documents