В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 53

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 53)

(pp) for i:=1 to n do

c := c + a[i] * b[i];

Он вычисляет скалярное произведение двух векторов a и b.

Попытаемся сопоставить его с определением скалярного произведения (d).

Во-первых, сразу видно, что естественная композиция функций в программе

(pp) не отражена. Пришлось заменить ее последовательными действиями с

компонентами векторов.

Во-вторых, пришлось ввести пять названий c,i,n,a,b, никак не

фигурирующих в исходной постановке задачи. Причем, если по отношению к a,b и

с еще можно сказать, что это обозначения исходных данных и результата, то

что такое i и зачем понадобилось n?

Ответ таков, что на Паскале со структурами-массивами по-другому

работать нельзя. Мы работали с выражением в модели МТ как с целостным

объектом, а в Паскале над массивами возможны лишь "мелкие" поэлементные

операции (для этого понадобилась переменная i). К тому же нельзя узнать

размер массива, необходимо явно указывать этот размер (n).

В-третьих, мы уже говорили о возможности распараллелить работу по

функциональной программе-формуле. А как это сделать в программе (pp)? Опять

сравнение не в пользу Паскаля.

Задача. Найдите аргументы в пользу Паскаля.

Замечание. Программа скалярного произведения в модели Б - это формула,

операциями в которой служат формы, а операндами - основные скалярные функции

(+, x) и некоторые другие (транс). В этой связи интересно напомнить, что

Джон Бэкус - "отец" Фортрана, который тоже начинался как Formula Translation

(и "испортился" под натиском "эффективности"). Так что Джон Бэкус пронес

идею "формульного" программирования через многие годы, от своего первого

знаменитого Фортрана до теперь уже также знаменитого "функционального

стиля". Излагая модель Б, мы воспользуемся лекцией, прочитанной Джоном

Бэкусом по случаю вручения ему премии Тьюринга за выдающийся вклад в

информатику [22].

14.2. Функциональное программирование в стиле Бэкуса (модель Б)

Мы показали, как функции высших порядков помогают писать концептуально

ясные программы. Теперь займемся моделью Б подробнее. Одна из целей -

познакомить с разработанной в этой модели алгеброй программ и с ее

применением для доказательства эквивалентности программ. Чтобы законы в этой

алгебре были относительно простыми, нам понадобится, во-первых, ограничить

класс обрабатываемых объектов - считать объектами не произвольные выражения,

а только МТ-термы (т.е. термы в смысле модели МТ); во-вторых, так подправить

определения форм, чтобы их применение всегда давало объекты. В-третьих,

придется ввести функции, позволяющие раскрывать и создавать термы.

Для выразительности и краткости при наших определениях будем

пользоваться общематематической символикой. Однако все нужные объекты,

функции и формы можно без принципиальных трудностей ввести и средствами

модели МТ.

14.2.1. Модель Бэкуса с точки зрения концептуальной схемы

Имея опыт работы со структуризованными объектами (выражениями), формами

и рекурсивными определениями, который мы приобрели, работая в модели МТ,

можно с самого начала рассматривать модель Бэкуса (модель Б) по нашей

концептуальной схеме. Чтобы не загромождать изложение, не будем постоянно

подчеркивать различие между знаками в языке Б (модели Б) и их денотатами,

надеясь, что из контекста всегда будет ясно, о чем идет речь. Например,

будем называть формой как функцию высшего порядка (денотат), так и

представляющее ее выражение (знак). Соответственно примитивной функцией

будем называть как ее идентификатор (знак), так и обозначаемое этим

идентификатором отображение из объектов в объекты (денотат).

Базис. В модели два скалярных типа - атомы и примитивные функции.

Первые служат для конструирования объектов, вторые - для конструирования

функций. Объекты и формы - это два структурных типа. Имеется единственная

операция - аппликация.

Развитие. Единственным средством развития служит возможность пополнять

набор D определений функций. Делается это с помощью фиксированного набора

форм и примитивных функций. Определения могут быть рекурсивными.

14.2.2. Объекты

Объект - это либо атом, либо кортеж (последовательность) вида

< X1, ... , Xn >

где Xi - либо объект, либо специальный знак <?> - "неопределено".

Таким образом, выбор фиксированного множества А атомов полностью

определяет множество всех объектов О.

Будем считать, что в А входят (т.е. служат атомами) идентификаторы,

числа и некоторые специальные знаки (T,F и т.п.). Выделен специальный атом

<> - это единственный объект, который считается одновременно и атомом, и

(пустым) кортежем.

Замечание. Аналогично спискам Лиспа нетрудно предствить Б-объекты МТ-

выражениями, введя подходящие обозначения для специальных объектов и

заключая последовательности объектов в круглые скобки. Это же относится и к

последующему неформальному изложению модели Б (хороший источник полезных

упражнений по представлению Б-понятий МТ-понятиями).

Все объекты, содержащие <?> в качестве элемента, считаются по

определению равными <?> (т.е. знаки различны, а денотаты - равны). Будем

считать, что все такие объекты до применения к ним каких бы то ни было

операций заменяются "каноническим" представлением "<?>".

Примеры объектов: <?>, 15, AB3, <AB,1,2,3>, <a,<<B>,C>,D>.

14.2.3. Аппликация

Смысл этой операции известен. Обозначать ее будем по-прежнему через

":", однако использовать не как префиксную, а как инфиксную операцию. Так

что если f - функция и Х - объект, то

f:X

обозначает результат применения функции f к объекту Х. Например

+:<1,2>=3, 1:<A,B,C>=A, 2:<A,B,C>=B, t1:<A,B,C>=<B,C>

где слева от знака аппликации ":" выписаны знаки функций сложения,

извлечения первого элемента, извлечения второго элемента и хвоста кортежа

соответственно.

14.2.4. Функции

Все Б-функции отображают объекты в объекты (т.е. имеют тип О => О) и

сохраняют неопределенность (т.е. f : <?> = <?> для всех f).

Каждый знак Б-функции - это либо знак примитивной функции, либо знак

формы, либо знак функции, определенной в D. Другими словами, в модели Б

различаются, с одной стороны, предопределенные функции и формы, и ,с другой

стороны, функции, определяемые программистом с помощью пополнения D.

Равенство f : X = <?> возможно всего в двух случаях, которые полезно

различать. Во-первых, выполнение операции ":" может завершаться и давать в

результате <?>, и, во-вторых, оно может оказаться бесконечным - тогда это

равенство считается справедливым по определению операции ":". Другими

словами, виды ненормального выполнения аппликации в модели Б не различаются.

14.2.5. Условные выражения Маккарти

Ниже будем пользоваться модификацией так называемых условных выражений

Маккарти. Условное выражение Маккарти - это запись вида

( P1 --> E1, ... ,Pn --> En, T --> E ),

где через Р с возможными индексами обозначены условия (предикаты, логические

функции), а через Е с возможными индексами - выражения, вычисляющие

произвольные объекты. При конкретной интерпретации входящих в эту запись

переменных ее значение вычисляется по следующему правилу. Последовательно

вычисляются условия, начиная с первого, пока не найдется истинное (такое

всегда найдется. Почему?). Затем вычисляется соответствующее выражение,

значение которого и становится значением всего условного выражения Маккарти.

Аналоги такой конструкции широко используются в ЯП. В сущности,

возможность согласования с левой частью конкретного МТ-предложения можно

рассматривать как аналог условия Pi, а правую часть МТ-предложения - как

аналог выражения Ei.

Упражнение. Укажите различия между Pi и Ei и названными их МТ-

аналогами.

Вслед за Джоном Бэкусом будем записывать условные выражения Маккарти в

виде

P1 --> E1; ... ; Pn --> En; E

т.е. опуская внешние скобки и последнее тождественно истинное условие, а

также используя точку с запятой в качестве разделителя (запятая занята под

знак формы "конструкция").

14.2.6. Примеры примитивных функций

Некоторые из уже известных вам функций опишем заново, во-первых, чтобы

можно было освоиться с введенными обозначениями и, во-вторых, потому, что

они играют важную роль в алгебре программ (АП), к описанию и применению

которой мы стремимся. Определения некоторых ранее рассмотренных функций

уточнены здесь с тем, чтобы упростить АП (соответствующая модификация МТ-

определений может служить полезным упражнением). Отличия касаются, как

правило, тонкостей (действий с пустыми и неопределенными объектами, а также

учета внешних скобок в представлении объектов), однако эти тонкости

существенны с точки зрения АП.

Селекторы (селекторные функции). Будем использовать целые числа для

обозначения функций, выбирающих из кортежей-объектов элементы с

соответствующим номером:

1 : X :: X = <X1, ... , Xn> --> X1 ; <?>.

т.е. функция определяется через аппликацию (этот прием мы уже применяли в

модели МТ). Знак "::" используется, как и раньше, в смысле "есть по

определению", чтобы отличать определение от обычного равенства. Приведенная

запись означает, что применение функции 1 к объекту X дает результат X1

(первый элемент кортежа), если X - кортеж, иначе - неопределено (т.е.

аппликация завершает вычисление с результатом <?>).

Вообще, для положительного целого s

s : X :: X = <X1, ... ,Xn> & n > = s --> Xs; <?>.

Здесь в условном выражении Маккарти употреблено более сложное условие

вида

X = <X1, ... ,Xn> & n > = s.

Замечание. Такого рода определения (и это, и предыдущее) следует

рассматривать лишь как достаточно понятное сокращение точного определения,

которое может быть дано, например, в модели МТ. Модель МТ неплохо подходит

для таких определений, потому что в ее базисе имеются мощные средства

анализа и синтеза. Ведь нужно сказать следующее: если объект X имеет вид

<X1, ... , Xn>

и длина кортежа больше s, то заменить X на s-ю компоненту кортежа. Если же X

не имеет такого вида ("согласование невозможно" с соответсвующим МТ-

предложением), то выдать <?>.

Например:

5{ (t1 t2 t3 t4 t5 e)} --> t5 .

5{ e } --> <?> .

Хвост

t1 : X :: X = <X1> --> <>;

X = <X1, ... ,Xn> & n > = 2 --> <X2, ... ,Xn>; <?>.

Отличие от МТ-функции "хвост" в том, что результат всегда в скобках,

если определен и не пуст.

Тождественная функция

id : X :: X

Логические функции - атом, равенство, пустой

атом : X :: (X - это атом) --> T; X /= <?> --> F; <?>.

Таким образом, атом:<?> = <?> (сохраняет неопределенность).

eq : X :: X = <Y,Z> & Y = Z --> T;

X = <Y,Z> & Y /= Z --> F; <?>.

Например, eq:<2,2,3> = <?>, так как аргумент не пара, а тройка.

null : X :: X = <> --> T; X /= <?> --> F; <?>.

Сложение, вычитание, умножение, деление

+ : X :: X = <Y,Z> & числа (Y,Z) --> Y+Z; <?>.

- : X :: аналогично.

mult : X :: аналогично. [Привычная звездочка занята ]

div : X :: аналогично. [Косая черта занята ]

Расписать левым, расписать правым

distl : X :: X = <Y,<>> --> <>;

X = <Y,<Z1, ... , Zn>> --> <<Y,Z1>, ... , <Y,Zn>>; <?>.

distr : X :: X = <<>,Y> --> <>;

X = <<Z1, ... , Zn>,Y> --> <<Z1,Y>, ... , <Zn,Y>>; <?>. Функция distl

присоединяет левый элемент аргумента ко всем элементам кортежа, который

служит правым элементом аргумента функции, а функция distr, наоборот,

присоединяет правый элемент аргумента. Например

distl:<<A,B>,<C,D>> = <<<A,B>,C>,<<A,B>,D>>.

distr:<<A,B>,<C,D>> = <<A,<C,D>>,<B,<C,D>>>.

Транспонирование

trans : X ::

Характеристики

Список файлов книги