Paradygmaty programowania - ćwiczenia

Lista 6

1. Dane są następujące środowiska:

E 1 = {X → x 1, Y → x 2} E 2 = {Y → x 3, Z → x 4} E 3 = {X → x 5, Z → x 6}

a) Znajdź wszystkie możliwe i oraz j dla i, j ∈{1, 2, 3} takie, że dla środowiska E = E i + E j zachodzi E(X) = x 1 oraz E(Z) = x 6. Podaj przykładowe fragmenty programów w języku Oz (z wykorzystaniem instrukcji local), dla których środowisko jest równe E.

b) Znajdź wszystkie możliwe i oraz j dla i, j ∈{1, 2, 3} takie, że dla środowiska E = E i + E j zachodzi E(X) = x 1 oraz E(Y) = x 2. Podaj przykładowe fragmenty programów w języku Oz (z wykorzystaniem instrukcji local), dla których środowisko jest równe E.

c) Jak wygląda środowisko E 3|{Z} ?

2. Zadeklarowany jest następujący rekord:

declare

R = r(1:[a b c] 4:[d [e [f]]] z:q(g h [10 11 [12 13]]))

a) Narysuj ten rekord jako drzewo (to nie ma być drzewo rozbioru, tylko graficzna reprezentacja rekordu; patrz wykład 4, str. 26 i 43). Listy również przedstaw w postaci drzew.

b) Podaj wyrażenia, wykorzystujące operacje na rekordzie R (kropka, Width, Label, Arity), które mają zadaną wartość. Na przykład dla wartości g odpowiedzią jest R.z.1, a dla wartości r odpowiedzią jest {Label R}. Jeśli możliwych jest kilka odpowiedzi, podaj przynajmniej dwie.

(1)

b (2)

q

(3) 12

(4)

nil

(5)

‘|’

(6) 3

(7) h

(8) 2

3. (Oz) Typ wyrażeń <Expr> jest zdefiniowany następująco:

<Expr> ::= const(<Int>) | var(<Atom>) | add(<Expr> <Expr>) | mult(<Expr> <Expr>) a) Napisz funkcję {Lookup LAssoc Key}, która dla danej listy asocjacyjnej LAssoc, składającej się z par klucz#wartość, zwraca wartość związaną z danym kluczem Key, jeśli taki klucz znajduje się w liście; w przeciwnym razie zgłasza wyjątek notFound(Key).

b) Napisz funkcję dla ewaluatora wyrażeń {Eval Env Expr}, która oblicza wartość wyrażenia Expr w środowisku Env, reprezentowanym przez listę asocjacyjną. Jeśli w wyrażeniu jest użyta zmienna, np. z, której nie ma w środowisku, to funkcja ma zgłosić wyjątek unboundVariable(z).

Przykłady: {Show {Eval [x#1 y#4] mult(add(var(x) const(2)) var(y))}} => 12

{Show {Eval [x#1 y#4] mult(add(var(x) const(2)) var(q))}} => %** unboundVariable(q) 4. Dana jest gramatyka G=({ Block, Decl, Instr, Cmd}, {; , { , },c,d}, P, Block), ze zbiorem produkcji P: Block ::= { Decl; Instr} | { Instr} | {}

Decl ::= d | d; Decl

Instr ::= Cmd | Cmd; Instr

Cmd ::= c | Block

Czy poniższe słowa należą do języka L( G)? Jeśli tak, narysuj dla nich drzewa rozbioru.

a) {d;c;c}

b) {d} c) {c} d) {d;c;{c}} e) {c;d;c} f) {;} g) {{}}