Семантика на езиците за програмиране 2005/06 - упражнения

Рекурсивни програми

Нека D е произволно непразно множество (тип) с набор вградени операции и предикати (например множеството на естествените числа N с операциите +, -, *, div, mod и предикатите even, odd, zero, >, <, =). Ще дефинираме рекурсивни програми над D. Разглеждаме два типа - основен (D) и булев (B = {tt, ff}).

1. Термове от тип D наричаме
   • всички константи от D (a,b,c,...)
   • обектовите променливи (X,Y,Z,...)
   • $$f(\tau_1,\ldots\tau_n)$$, ако $$f:D^n\rightarrow D$$ е примитивна (вградена, основна) операция в типа D, а $$\tau_1,...\tau_n$$ са термове от тип D.
   • $$F_i^{n_i}(\tau_1,\ldots\tau_{n_i})$$, ако $$F_i^{n_i}$$ е функционална променлива, а $$\tau_1,...\tau_n$$ са термове от тип D. Функционалните променливи са имената на потребителски дефинираните рекурсивни функции на програмите, които ще изследваме.
2. Термове от тип B наричаме
   • константите от B (tt,ff)
   • $$p(\tau_1,\ldots\tau_n)$$, ако $$p:D^n\rightarrow B$$ е примитивен предикат в D, а $$\tau_1,...\tau_n$$ са термове от тип D.
   • $$\pi(\tau_1,\ldots\tau_n)$$, ако $$\pi:B^n\rightarrow B$$ е примитивна логическа операция, а $$\tau_1,...\tau_n$$ са термове от тип B.
3. Условни термове наричаме
   • if p then $$\tau_1$$ else $$\tau_2$$, ако p е терм от тип B, а $$\tau_1$$ и $$\tau_2$$ са термове от тип D или условни термове.
4. Рекурсивна програма наричаме поредица от дефиниции на взаимно рекурсивни функции с указано стартиращо извикване. Имената на дефинираните функции означаваме с функционалните променливи $$F_i^{n_i}$$, където долният индекс означава поредния номер, а горният - броят на аргументите. Формално рекурсивна програма е:
   $$\tau_0(X_1,\ldots,X_n,F_1^{n_1},\ldots,F_k^{n_k})$$, where
   $$F_1^{n_1}(X_1,\ldots,X_{n_1}) = \tau_1(X_1,\ldots,X_n,F_1^{n_1},\ldots,F_k^{n_k})$$
   
   $$\ldots$$
   
   $$F_k^{n_k}(X_1,\ldots,X_{n_k}) = \tau_1(X_1,\ldots,X_n,F_1^{n_1},\ldots,F_k^{n_k})$$
   Тук $$\tau_0$$ е терм от тип D (стартиращото извикване), а $$\tau_1,\ldots,\tau_k$$ са термове от тип D или условни термове (дефинициите на функциите).
   Вижда се, че всяка дефинирана функция може да извиква всяка друга, включително и себе си.

Операционна семантика с предаване на параметрите по стойност (O_v)

...

Денотационна семантика с предаване на параметрите по стойност (D_v)

...

Задачи

• стр. 234 / зад. 2
• стр. 234 / зад. 3 а) б) в)
• стр. 235 / зад. 6
• стр. 238 / зад. 14