Ò: S®{sÀ: sÎS}, ïðè÷åì Ò[s]=sÀ.
Òàêæå ( {¦À: ¦ÎF}, F, I ) ñ I: F®{¦À: ¦ÎF}, ïðè÷åì I[¦]=¦À, ÿâëÿåòñÿ èíôîðìàöèîííîé ñèñòåìîé.”
Çàòåì îïðåäåëÿåòñÿ ìíîæåñòâî îñíîâíûõ òåðìîâ ñèãíàòóðû, ïðèáëèæàþùåå îáó÷àåìîãî ê ïîíÿòèþ èíèöèàëüíîé ìîäåëè àáñòðàêòíîé àëãåáðû.
“Îïðåäåëåíèå (ìíîæåñòâî îñíîâíûõ òåðìîâ). Ïóñòü S=(S,F) åñòü ñèãíàòóðà. Ìíîæåñòâî îñíîâíûõ òåðìîâ òèïà s ñ sÎS îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
(i) êàæäûé íóëüìåñòíûé ñèìâîë ôóíêöèè ¦ÎF ñ fñt ¦=s îáðàçóåò îñíîâíîé òåðì òèïà s,
(ii) êàæäàÿ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ¦(t1,...,tn) ñ ¦ÎF è fñt ¦=(s1,...,sn)s åñòü îñíîâíîé òåðì òèïà s, åñëè äëÿ âñåõ i, 1£i£n, ti åñòü îñíîâíîé òåðì òèïà si .
Ìíîæåñòâî âñåõ îñíîâíûõ òåðìîâ ñèãíàòóðû S îáîçíà÷èì ÷åðåç WS, à ìíîæåñòâî îñíîâíûõ òåðìîâ òèïà s ÷åðåç WSs. Åñëè íå ñóùåñòâóåò íóëüìåñòíûõ ñèìâîëîâ ôóíêöèé, òî ìíîæåñòâî WS ïóñòî.
Åñëè èìååòñÿ âû÷èñëèòåëüíàÿ ñòðóêòóðà À ñ ñèãíàòóðîé S, òî îñíîâíûå òåðìû â À äîïóñêàþò èíòåðïðåòàöèþ. Ïåðåõîä îò îñíîâíîãî òåðìà t (ïðåäñòàâëåíèÿ) òèïà s ê ñîîòâåòñòâóþùåìó ýëåìåíòó à ìíîæåñòâà À íàçûâàþò èíòåðïðåòàöèåé t â À. Èíòåðïðåòàöèÿ IÀ ïîýòîìó îçíà÷àåò îòîáðàæåíèå
IÀ : WS ® {àÎsÀ : sÎS}.
Äëÿ êàæäîãî îñíîâíîãî òåðìà t çàïèñü IÀ[t] îáîçíà÷àåò èíòåðïðåòàöèþ t â À. Ïèøóò òàêæå tÀ âìåñòî IÀ[t]. Èíòåðïðåòàöèÿ ïîëó÷àåòñÿ çàìåíîé â îñíîâíîì òåðìå ñèìâîëîâ ôóíêöèé íà ñîîòâåòñòâóþùèå ôóíêöèè:
IÀ [ ¦(t1,...,tn) ] = ¦À ( IÀ [t1],..., IÀ [tn] ).
 ÷àñòíîñòè, ({àÎsÀ: sÎS}, WS, IÀ) îáðàçóåò èíôîðìàöèîííóþ ñèñòåìó.”
"Если имеется вычислительная структура A с сигнатурой S, то основные термы S допускают интерпретацию в A" [Broy]
Таким образом, в учебнике М. Брой фактически предлагаются АТД с инициальными моделями.
В преддверии совместной работы с М. Брой по подготовке компьютерного учебника-задачника перечислим недостатки:
1. Явно не говорится об АТД и инициальных моделях.
2. Плохо предъявляется семантика неподвижной точки для типов (то есть для множеств).
3. Не демонстрируется работа теоремы для интересных случаев - взаимная рекурсия, "циклические типы".
4. Недостатки синтаксиса: обсуждается параметрический тип, но нет синтаксиса для его предъявления (например, можно было бы предъявить через W - грамматики).
5. По видимому, наряду с СПТ (алгоритмы Маркова) для описания алгоримтов следовало бы применить теорему Черча-Россера для объяснения состоятельности алгоритмов на основе лямбда-теории.
* Денотационная семантика.
При рассмотрении языков программирования М. Брой говорит достаточно ясно о двух семантиках.
“Существенно различаются две крайние точки зрения в связи с установлением семантики:
Функциональная семантика: описание функций программы, то есть установление отношения между входными и выходными данными (экстенсиональное или наблюдаемое отношение), называют функциональной семантикой.
Операционная семантика: описание последствий отдельных шагов вычислений, которые имеют место при выполнении программы, называют операционной семантикой”.
То есть фактически рассматривается денотационная семантика (аппликативный стиль) и операционная семантика (императивный стиль программирования). В дальнейшем изложении аппликативного стиль рассматривается именно в свете этих двух семантик. Но автор не показывает ясно, на примерах отличия этих двух семантик со стороны стиля программирования, их достоинства и недостатки. А ведь это очень важно для понимания стиля.
Уместно было бы в этом случае привести примеры, показывающие легкость задания денотационной семантики в аппликативном языке, недостатки семантики императивных языков (побочный эффект). У М. Броя, конечно говорится об этом, но в различных главах, и акцент на это не делается.
Хочется привести пример книги Филд, Харрисон “Функциональное программирование”, где авторы совершенно замечательно выделяют данный случай.
Так в этой книге отмечается, что в последнее время появилось довольно большое число языков, преуспевших в отходе от формы традиционного программирования; примером такого рода могут служить аппликативные, или функциональные, языки. Функциональные программы строятся из “чистых” математических функций, которые по сравнению с функциями многих императивных программ свободны от побочных эффектов (т.е. их вычисление не может изменить среду вычислений). Из-за этого нет возможности программировать “помощью эффекта”, так что сама величина, которая должна быть вычислена программой, и сама программа редуцируются к одному и тому же результату. Выполнение программы тогда становится процессом изменения формы требуемой итоговой величины так, что “8+1” можно заменить на “9”; при этом обе они будут обозначать одну и ту же величину.
Программирование с помощью функций не только возможно, но также вполне естественно и приводит к программам почти всегда более кратким, нежели аналогичные императивные программы, более простым в написании и объяснении.
Авторы проводят сравнения вычислений в императивных и аппликативных языках, показывая сущность различий:
“Функциональность (прозрачность по ссылкам - вычисление выражения просто изменяет форму выражения, но не изменяет его величину) определяет различие между математическими функциями и функциями, которые можно написать на императивных языках программирования, таких, как Паскаль, поскольку эти языки дают функциям возможность ссылаться на глобальные данные и разрешают применять (разрушающее) присваивание, что может привести к изменению значения функции при повторном ее вызове. Такие изменения часто именуются побочными эффектами. Это приводит к тому, что функцию трудно использовать, поскольку необходимо рассмотреть текущую величину глобальных данных. Это же в свою очередь требует рассмотрения истории вычисления. Говорят, что императивные языки являются нефункциональными. Для иллюстрации их нефункциональности рассмотрим пример программы, написанной на языке Паскаль:
program example(output);
var flag : boolean;
function f (n : integer) : integer;
begin
if flag then f:=n
else f:=2*n;
flag:=not flag
end;
begin
flag:=true;
writeln(f(1)+f(2));
writeln(f(2)+f(1))
end.
После выполнения этой программы на терминал будет выведены два числа: 5 и 4. Однако, это довольно странно, поскольку с математической точки зрения коммутативность сложения позволяет заменять x+y на y+x для любых x и y.
Однако, дело здесь не в изменении самой функции ‘+’. Проблема состоит в том, что функция f сильно отличается от математических функций. Следует обратить внимание на то, что величина глобальной переменной flag в нашей программе на языке Паскаль имеет возможность изменяться, и именно это уничтожает свойство функциональности языка. Значение же элементарной функции ‘+’ не изменяется. Источником таких проблем в программах на языке Пвскаль является операция присваивания flag:=not flag, изменяющая величину flag.