2 Постановка задачи: о связном предъявлении теории информатики и практики программирования в теме исполнения для теоретического мышления. 13 (стр. 14 из 25)
Рассмотрим, как в учебнике представлено исполнение функции, а именно вызов функции (механизм передачи параметров) и аппликация (применение функций).
“Обозначим через F (функциональное выражение для) функцию с функциональностью
(s1,...,sn)s
и пусть Е1,...,Еn - любые выражения типов s1,...,sn; тогда
F (Е1,...,Еn)
есть выражение типа s, называемое применением функции или вызовом (указателем) функции. Значение указателя функции есть ¦(а1,...,аn), причем пусть ¦ - функция, обозначенная через F, а а1,...,аn - значения выражений Е1,...,Еn. Е1,...,Еn - фактические параметры-выражения (или аргументы), а а1,...,аn - фактические параметры-значения.
В БНФ-нотации синтаксис указателя функции выглядит следующим образом:
<указатель_функции>::=<функция>{(<выражение>{,<выражение>}*)}
При этом предполагаются следующие дополнительные условия: функция, обозначенная через F, должна быть n-местной и типы фактических параметров-выражений Е1,...,Еn должны соответствовать типу функции”.
Автор упоминает в этом контексте различные способы вычислений параметров функций (“по значению”, “по ссылке”), а также другие стратегии вычисления указателя функции (“по имени”).
* Семантика рекурсий.
Существуют два основных подхода для толкования рекурсивных соглашений о функциях:
-индуктивное толкование,
-толкование через равенство фиксированной (неподвижной) точки.
В обоих толкованиях однозначно устанавливается, с каким отображением сопоставляется идентификатор с помощью рекурсивного объявления. Оба способа рассмотрены на простых примерах. Как уже отмечалось, мы считаем полезным продемонстрировать семантику неподвижной точки на более сложных примерах (грамматики, рекурсивные типы данных и т.п.).
Необходимо отметить также, что, развивая перед читателем идею рекурсивных объявлений с помощью толкования через равенство неподвижной точки, автор использует при теоретическом обосновании данного подхода более общий случай: он использует элементы теории решеток, но рассматривает множество функций как полно упорядоченное, а не как полное. Действительно,
“Наряду с индуктивным толкованием, рекурсивное объявление функции
fсt ¦ = (m х)n: Е
можно истолковывать через решение функционального уравнения
(*) ¦=t(¦),
где t было определено выше, т.е. ищут отображение
¦: М®N
с тем свойством, что для всех хÎМ справедливо
¦(х)=t[¦](х).
Тогда ¦ называют неподвижной точкой t, а (*)-функциональным уравнением, относящимся к рекурсивному объявлению ¦. То, что функциональное уравнение всегда обладает решением, будет показано ниже. Для этого понадобятся некоторые теоретические понятия упорядоченности.
Функция
¦: М®N
называется монотонной, если для всех х1,х2ÎМ имеет место:
х1Íх2 Þ ¦(х1)ͦ(х2).
Множество монотонных отображений обозначают через
[М®N].
Для произвольного функционала t не обеспечивается ни существования, ни однозначности неподвижной точки, т.е. решения функционального уравнения. Однако на основе структуры имеющегося ЯП справедливо, что функционал t является монотонным, т.е. для всех функций ¦ и g имеет место:
¦Íg Þ t[¦]Ít[g].
Для монотонного функционала t на вполне упорядоченном множестве с наименьшим элементом гарантируется существование неподвижной точки, т.е. решения приведенного выше уравнения (*). Отсюда всегда имеется однозначно определенная наименьшая неподвижная точка t.
Теорема (Knaster-Tarski). Если t-монотонное отображение на вполне упорядоченном множестве А с наименьшим элементом, то уравнение
х=t(х)
разрешимо и существует однозначно определенная наименьшая неподвижная точка для t.”
Функционал t вводится следующим образом:
“Для заданной конкретизации b с правой частью объявления, т.е. с абстракцией
(m х)n: Е
связывается функционал t, т.е. отображение между множествами отображения:
t : (М®N)®(М®N).
Функционал t для функций g: М®N через t[g] снова дает функцию. Для аргумента аÎМ функция t[g] определяется следующим образом:
причем пусть имеет место b1=b[g/¦,а/х]. Различение случаев снова соответствует принципу строгости. Способ записи t[g](х) означает, что t для каждой функции g через t[g] порождает функцию, которая для каждого значения х типа m доставляет значение t[g](х) типа n. “
Для частично упорядоченного множества Z непустое подмножество Z0ÍZ называется направленным, если для каждой пары х,уÎZ0 существует общая граница zÎZ0, т.е. существует zÎZ0 с хÍz Ù уÍz.
Частично упорядоченное множество называется полно упорядоченным, если для каждого направленного множества имеется наименьшая верхняя граница (suрrеmum).
Частично упорядоченное множество называется полной структурой, если всякое его непустое подмножество имеет как точную верхнюю, так и точную нижнюю грань.
М. Брой рассматривает более общий случай - полно упорядоченный, а не полный, что, в общем, представляется нам лишним (например трудно доказывается теорема Knaster’s).
* Типы на основе аппликативной среды информационного моделирования, предназначенной для базового обучения
Рассмотрим метод разработки учебного материала по теме "Типизация" с учетом выбора за основу теоретической программы учебника M. Broy. Основой для демонстрации понятия типов данных в учебнике служат алгебраические спецификации. А именно, дается определение понятия вычислительной структуры и сигнатуры.
Надо отметить важность момента определения множества основных термов сигнатуры, фактически задающее инициальную модель абстрактной алгебры.
“Îïðåäåëåíèå (âû÷èñëèòåëüíàÿ ñòðóêòóðà). Ïóñòü S è F - ìíîæåñòâà îáîçíà÷åíèé; âû÷èñëèòåëüíàÿ ñòðóêòóðà À ñîñòîèò èç ñåìåéñòâà {sÀ: sÎS} òèïîâ äàííûõ sÀ è ñåìåéñòâà {¦À: ¦ÎF} îòîáðàæåíèé ¦À ìåæäó ýòèìè òèïàìè äàííûõ. Ìû ïèøåì:
À=( { sÀ : sÎS}, {¦À : ¦ÎF} ).
Ýëåìåíòû sÎS åñòü îáîçíà÷åíèÿ äëÿ òèïà äàííûõ è íàçûâàþòñÿ òèïû. Ýëåìåíòû ¦ÎF åñòü îáîçíà÷åíèÿ äëÿ îòîáðàæåíèé è íàçûâàþòñÿ ñèìâîëàìè ôóíêöèé èëè çíàêàìè îïåðàöèé. Äëÿ êàæäîãî ¦ÎF ñóùåñòâóåò îäíî nÎN òàêîå, ÷òî èìååò ìåñòî: ¦À åñòü n-ìåñòíàÿ ôóíêöèÿ, è ñóùåñòâóþò òèïû s1,s2,..,sn+1ÎS òàêèå, ÷òî
Ìîæåò òàêæå áûòü è n=0, ò.å. äîïóñêàþòñÿ è "íóëüìåñòíûå" îòîáðàæåíèÿ. Ýòî òàêèå îòîáðàæåíèÿ, êîòîðûå (ñ ïóñòûì ñïèñêîì àðãóìåíòîâ) ïîëó÷àþò â òî÷íîñòè îäèí ýëåìåíò èç îáëàñòè çíà÷åíèé (ñìîòðè true , false , zårî â ñëåäóþùåì ïðèìåðå), êîòîðûé îïðåäåëåí â òèïå s1 .
Îïðåäåëåíèå (ñèãíàòóðà). Ñèãíàòóðà S - ýòî ïàðà (S,F) ìíîæåñòâ S è F, ïðè÷åì
- S îáîçíà÷àåò ìíîæåñòâî òèïîâ, ò.å. èìåí äëÿ òèïîâ äàííûõ,
- F îáîçíà÷àåò ìíîæåñòâî ñèìâîëîâ ôóíêöèé;
ïóñòü äëÿ êàæäîãî ñèìâîëà ôóíêöèè ¦ÎF çàäàíà åå ôóíêöèîíàëüíîñòü fñt ¦ÎS+.
Âû÷èñëèòåëüíûå ñòðóêòóðû óêàçûâàþò íà ñòðóêòóðíûå ñâîéñòâà èíôîðìàöèîííûõ ñèñòåì ... Èìååò ìåñòî:
( {sÀ: sÎS}, S, Ò )
îáðàçóåò ñíîâà èíôîðìàöèîííóþ ñèñòåìó ñ