Semantyka i weryfikacja programów/Ćwiczenia 9

Procedury i funkcje. Przekazywanie parametrów.

Zadanie 1

Zdefiniuj semantykę denotacyjną następującego języka:

$n::=0|1|\dots$

$x::=\dots (identyfikatory)\dots$

$e::=n|x|e_1+e_2$

$b::=e_1=e_2|\mathbf{𝐧}\mathbf{𝐨}\mathbf{𝐭}b|b_1\mathbf{𝐨}\mathbf{𝐫}{b}_2$

$i::=x:=e|i_1;i_2|\mathbf{𝐢}\mathbf{𝐟}b\mathbf{𝐭}\mathbf{𝐡}\mathbf{𝐞}\mathbf{𝐧}{i}_1\mathbf{𝐞}\mathbf{𝐥}\mathbf{𝐬}\mathbf{𝐞}{i}_2|\mathbf{𝐬}\mathbf{𝐤}\mathbf{𝐢}\mathbf{𝐩}|\mathbf{𝐰}\mathbf{𝐡}\mathbf{𝐢}\mathbf{𝐥}\mathbf{𝐞}b\mathbf{𝐝}\mathbf{𝐨}i|\mathbf{𝐜}\mathbf{𝐚}\mathbf{𝐥}\mathbf{𝐥}P(x)|\mathbf{𝐛}\mathbf{𝐞}\mathbf{𝐠}\mathbf{𝐢}\mathbf{𝐧}d;i\mathbf{𝐞}\mathbf{𝐧}\mathbf{𝐝}$

$d::=\mathbf{𝐯}\mathbf{𝐚}\mathbf{𝐫}x:=e|d_1;d_2|\mathbf{𝐩}\mathbf{𝐫}\mathbf{𝐨}\mathbf{𝐜}P(x);i\mathbf{𝐞}\mathbf{𝐧}\mathbf{𝐝}\mathbf{𝐩}\mathbf{𝐫}\mathbf{𝐨}\mathbf{𝐜}$

Deklaracja $\mathbf{𝐯}\mathbf{𝐚}\mathbf{𝐫}x:=e$ wprowadza zmienną x i nadaje jej wartość obliczonego wyrażenia e. Deklaracja $\mathbf{𝐩}\mathbf{𝐫}\mathbf{𝐨}\mathbf{𝐜}P(x);i\mathbf{𝐞}\mathbf{𝐧}\mathbf{𝐝}\mathbf{𝐩}\mathbf{𝐫}\mathbf{𝐨}\mathbf{𝐜}$ wprowadza procedurę o nazwie P z jednym parametrem x przekazywanym przez zmienną. Treścią procedury jest instrukcja i.

Instrukcja bloku $\mathbf{𝐛}\mathbf{𝐞}\mathbf{𝐠}\mathbf{𝐢}\mathbf{𝐧}d;i\mathbf{𝐞}\mathbf{𝐧}\mathbf{𝐝}$ polega na wykonaniu instrukcji i po uprzednim wzbogaceniu środowiska deklaracją d. Wszystkie zmienne i procedury wprowadzone przez d są lokalne w bloku. Instrukcja $\mathbf{𝐜}\mathbf{𝐚}\mathbf{𝐥}\mathbf{𝐥}P(x)$ to wywołanie procedury P.

Zadanie 2

Jaką wartość ma zmienna z przy semantyce z poprzedniego zadania po wykonaniu następującej instrukcji:

begin
  var
    y := 1;
    proc P (x); x := y endproc;
    begin
      var y := 2;
      var z := 0;
      call P(z);
    end
 end
    

Zadanie 3

Wyjaśnij różnicę między wiązaniami statycznymi a dynamicznymi. Zmień semantykę języka z zadania 1 tak, aby uzyskać dynamiczne wiązania identyfikatorów.

Zadanie 4

Czy semantyka z zadania 1 umożliwia pisanie procedur rekurencyjnych? A semantyka z zadania 3? Jak należy zmienić semantykę, aby procedury rekurencyjne były możliwe?

Zadanie 5

Przypuśćmy, że składnia wywołania procedury z zadania 1 przyjmuje teraz postać:

$i::=\mathbf{𝐜}\mathbf{𝐚}\mathbf{𝐥}\mathbf{𝐥}P(e)$

Pozostałe elementy nie zmieniają się. Przekazywanie parametrów odbywa się teraz jednak przez wartość. Opisz semantykę takiego języka. Zadbaj o możliwość definiowania procedur rekurencyjnych i statyczne wiązania zmiennych globalnych.