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

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

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

известной модели.

[Такой стиль можно назвать проекционным - вместе с новым понятием

излагается его проекция (перевод) на уже известный инструментальный язык. В

нашем случае основу этого языка предоставит модель МТ.]

Первая форма, которую следовало бы рассмотреть - это, конечно,

аппликация (которую обозначим двоеточием ":"). Она применяет указанную в ее

аргументе функцию (возможно, форму) к остальным компонентам аргумента. Можно

было бы определить аппликацию в общем виде, однако нам удобнее считать, что

определение МТ-функции ":" формируется постепенно. А именно, группа

предложений со специальной функциональной скобкой вида ":{" пополняется

новыми предложениями по мере введения новых форм.

Таким способом (за счет возможностей МТ-образцов) можно определять

новые формы (и обычные функции), не требуя, чтобы обращение к ним было

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

аргументам). Префиксный способ требует слишком много скобок, поэтому его

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

ассоциативности.

Упражнение. Покажите, как можно вводить инфиксные функции.

Подсказка. Вспомните о переводе в ПОЛИЗ.

Пока будем считать, что в группе аппликации лишь два предложения

:{(f) e} -> :{f e}

(anл)

:{s_f e} -> s_f{ e }

где f - переменная, обозначающая вызов некоторой формы, а s_f - переменная,

обозначающая название применяемой МТ-функции.

Первое предложение снимает скобки, ограничивающие вызов формы (они

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

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

служит вызовом применяемой функции.

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

имеются. Предложения (апл) будут оставаться последними в группе

аппликации. Новые будем добавлять в ее начало (чтобы сначала действовали

формы, а лишь затем их результаты - обычные функции).

14.1.6. Примеры структурирующих форм

Намеченный идеал концептуальной ясности наводит на мысль, что наиболее

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

программу - выражать ее смысл (реализуемую функцию) простой и понятной

комбинацией других функций. Рассмотрим несколько таких структурирующих форм.

1. Композиция (ее часто обозначают звездочкой "*"). Применить результат

композиции двух функций f и g - значит применить функцию f к результату

применения g. "Применить" - это значит использовать аппликацию. В модели МТ

определение композиции выглядит так:

:{(f*g)e} -> :{(f) :{(g) e}}.

Точнее говоря, чтобы это предложение заработало как определение новой

формы (а именно композиции), им следует пополнить группу (апл).

2. "Общая аппликация" (применение указанной в аргументе функции ко всем

непосредственным составляющим обрабатываемого выражения). Обозначим ее через

"А" по аналогии с квантором всеобщности. Для ее определения через аппликацию

в группу (апл) следует добавить два МТ-предложения

:{(Аf)t e} -> :{(f)t} :{(Аf)e}

:{(Аf) } -> <> .

Итак, указанная выражением f функция применяется к компонентам

обрабатываемого выражения. Получается выражение, составленное из результатов

всех применений.

Вопрос. Зачем понадобилось второе предложение?

3. Конструкция (ее обозначим запятой ","). Применить результат

конструкции двух функций f и g к выражению e - значит получить конкатенацию

выражений f(e) и g{e}.

Определить конструкцию в модели МТ можно так.

:{(f,g) e} -> :{(f)e} :{(g)e} .

4. Редукция, которую обозначим через "/". Название, идея и обозначение

восходят к Айверсону, автору языка Апл - одного из самых распространенных

диалоговых языков. Своей исключительной лаконичностью этот язык в

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

:{(/f) t1 t2 e} -> :{(f) t1 :{(/f) t2 e}}.

:{(/f) t} -> t.

Идея редукции в том, что бинарная операция f (двухместная функция)

последовательно применяется, начиная с конца выражения вида (t1 t2 e) - т.е.

выражения, в котором не меньше двух составляющих. Название этой формы

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

(редуцируется) за счет последовательного "сьедания" пар компонент выражения,

начиная с его конца.

Например, с помощью редукции можно определить функцию "сумма".

сумма{e} -> :{(/+) e} .

Тогда, если считать, что бинарная операция "+" предопределена и ее

можно использовать префиксным способом, получим

сумма{10 20 30} = :{(/+) 10 20 30} =

= :{+10 :{(/+) 20 30}} =

= :{+10 :{+20 :{(/+) 30}}} =

= :{+10 :{+20 30}} = :{+10 50} = 60 .

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

сумма{10 20 30} = 60.

Итак, мы определили конструкцию, общую аппликацию, композицию,

редукцию, В том же стиле с помощью аппликации можно определить и другие

полезные формы.

Если программировать с использованием таких форм (и некоторых других),

то по существу мы будем работать в модели Бэкуса (модели Б). И снова

развитие МТ-модели новыми функциями дает новый язык - язык Бэкуса.

Отличительная черта модели Бэкуса - фундаментализация идеи функ-

циональных форм. В частности, четыре названные выше формы считаются

примитивными (предопределенными, т.е. определенными средствами, выходящими

за рамки модели). Аналогичная идея - одна из основных в языке Апл Айверсона.

Однако Айверсону, в отличие от Бэкуса, не удалось ее фундаментализировать

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

Определим в модели МТ еще несколько функций, полезных для работы с

выражениями.

реверс{t e} -> реверс{e} t .

реверс{ } -> <>.

Эта функция преобразует выражение вида t1 ... tn в выражение вида tn

... t1, где ti - термы.

Следующая функция - транспонирование (для краткости будем обозначать ее

"транс"). По сути дела это обычное транспонирование матриц. Ее действие

представим рис.14.1-14.3.

------------------------------------------------------

I e I транс (e) I

------------------------------------------------------

I (a b c) (k l m) I (a k) (b l) (c m) I

I (a b) (c k) (l m) I (a c l) (b k m) I

I (a b c) (k l m) (o p r) I (a k o) (b l p) (c m r) I

------------------------------------------------------

Рис. 14.1

Здесь строки матрицы представлены последовательными термами МТ-

выражения (это обычный способ представления структур в Рефале).

Определим теперь функцию "транс" точно.

транс{e} -> первые{e} транс{хвосты{e}} .

транс{ } -> <>, где "первые" - функция, выделяющая список первых

элементов последовательных подвыражений (рис.14.2), а "хвосты" - функция,

выдающая список хвостов от последовательных подвыражений (рис.14.3).

--------------------------------------------------

I e I первые (e) I

--------------------------------------------------

I (a b c) (k l m) I (a k) I

I (a b) (c k) (l m) I (a c l) I

I (a b c) (k l m) (o p r) I (a k o) I

--------------------------------------------------

Рис. 14.2

---------------------------------------------

I e I хвосты I

---------------------------------------------

I (a b c) (k l m) I (b c) (l m) I

I (a b) (c k) (l m) I (b) (k) (m) I

I ((a b) c) ((r l) m) I (c) (m) I

---------------------------------------------

Рис. 14.3

Определим эти функции точно:

первые{(t1 e1) e2} -> (t1 первые{e2} ) .

первые{ } -> <>.

хвосты{(t1 t2 e1) e2} -> (t2 e1) дл-хвосты{e2} .

хвосты{(t1) e} -> кор-хвосты{e} .

дл-хвосты{(t1 t2 e1) e2} -> (t2 e1) дл-хвосты{e2} .

дл-хвосты{ } -> <>.

кор-хвосты{(t) e} -> кор-хвосты{e} .

кор-хвосты{ } -> <>.

Вопрос. Для чего понадобилось вводить функции дл-хвосты и кор-хвосты?

Подсказка. Мы хотим транспонировать только матрицы.

14.1.8. Пример программы в стиле Бэкуса

Теперь можно написать программу, выражающую в некотором смысле "идеал"

программирования в стиле Бэкуса. Точнее, мы напишем программу-формулу,

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

пошаговой детализации.

Допустим, что предопределены функции "сложить" (+) и "умножить" (x).

Представим подлежащие перемножению векторы выражением вида (e1)(e2), где e1

- первый вектор, e2 - второй. Исходная пара векторов представляет собой

матрицу с двумя строками e1 и e2.

Вспомним определение скалярного произведения - это

Сумма всех произведений

(d) попарно соответствующих компонент

подлежащих перемножению векторов.

Прочитаем это определение "с конца". Нужно получить, во-первых, попарно

компоненты векторов e1 и e2, во-вторых, все произведения этих пар, в-

третьих, сумму всех этих произведений.

Итак, план (программа) наших действий состоит из трех последовательных

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

последующим шагом.

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

f3 * f2 * f1

Какие же это функции?

Функция f1 определяет то, что нужно сделать "во-первых". Если даны два

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

(b1) (10 20 30) (3 2 1)

то нужно получить их компоненты попарно

(b2) (10 3) (20 2) (30 1)

С этим мы уже встречались, так работает функция "транс". Естественно

положить f1 = транс.

Функция f2 определяет то, что нужно сделать "во-вторых": получить все

произведения пар. В нашем примере - это выражение

(b3) 30 40 30

Такое выражение получится, если функцию "умножить" применить к каждому

подвыражению выражения (b2). С подобным мы тоже встречались - так работает

общая аппликация "А" с аргументом "умножить" (x). Значит естественно

положить f2 = (Аx).

Наконец, f3 определяет, что нужно сделать "в-третьих". Нужно получить общую

сумму всех компонент (b3), т.е.

(b4) 100

Такое выражение получится, если к (b3) применить форму "редукция", с

аргументом "сложить" (+). Значит естественно положить

f3 = (/ +).

Итак, можно выписать нашу программу-формулу полностью:

(/+) * (Аx) * транс .

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

т.е. вычисляет скалярное произведение. Использовать ее можно, как и раньше,

двумя способами - либо непосредственно применять к обрабатываемому выражению

:{((/+)*(Аx)*транс) (10 20 30) (3 2 1)} = 100 ,

либо ввести для нее название, например, IP

IP{e} -> :{((/+)*(Аx)*транс) e} .

и использовать как обычную МТ-функцию:

IP{(10 20 30) (3 2 1)} = 100 .

Как видим, наша программа полностью соответствует определению

скалярного произведения - все слова в этом определении использованы и ничего

лишнего не понадобилось вводить (мы записали программу, не использовав ни

одного лишнего понятия).

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

Для других программ вопрос открыт, но направление должно чувствоваться. С

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

вводить адекватные понятия (абстракции), помогают бороться со сложностью

создания программ.

Задача. Можно ли аналогичные средства ввести в Паскале, Фортране,

Бейсике? Дайте обоснованный ответ.

Сравнение функциональной программы с программой на Паскале. Рассмотрим

фрагмент программы на Паскале:

c := 0;

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

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