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

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

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

X = <<X11, ... ,X1m>, <<X11, ... ,Xn1>,

<X21, ... ,X2m>, --> <X12, ... ,Xn2>,

... ...

<Xn1, ... ,Xnm>> <X1m, ... , Xnm>> ; <?>.

Здесь для наглядности строки матрицы выписаны друг под другом. С

подобной функцией мы работали в модели МТ. К объектам, не являющимся

матрицами, она не применима (т.е. результат - <?> ).

Присоединить

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

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

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

качестве самого левого элемента правой компоненты аргумента. Поэтому ее

естественно назвать "присоединить левый". Например

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

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

X = <<Y1, ... ,Yn,Z> --> <Y1, ... ,Yn,Z>; <?>.

Такую функцию естественно назвать "присоединить правый". Например

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

Примеры форм, частично известных по работе в модели МТ.

Композиция (обозначение - *).

(f * g) : X :: f : (g :X).

Конструкция (обозначение - ,).

(f1, ... ,fn) : X :: <f1:X, ... , fn:X>.

Замечание. В отличие от МТ-конструкции, здесь результат - целостный

объект в скобках, причем все n результатов применения каждой функции - также

целостные объекты (т.е. каждая компонента общего результата явно отделена от

остальных). В МТ-конструкции отделить результаты функций-компонент в общем

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

разделенные между собой явно. По указанной причине для МТ-конструкции не

выполняются некоторые важные алгебраические законы, верные в случае Б-

конструкции. Так что указанные отличия МТ- и Б-конструкций существенны.

Упражнение. Определите МТ-конструкцию со свойствами, аналогичными Б-

конструкции.

Подсказка. Нужно использовать не конкатенацию выражений, а функцию,

аналогичную созданию списка из атомов и (или) списков.

Вопрос. Какие важные алгебраические законы не выполняются для МТ-

конструкции?

Подсказка. Что будет, если некоторый объект присоединить левым, а затем

выбрать первый (т.е. левый) элемент? Зависит ли результат от структуры этого

объекта в случае Б-конструкции? А в случае МТ-конструкции?

Условие

(p --> f;g):X :: (p:X) = T --> f:X; (p:X) = F --> g:X; <?>.

В отличие от условного выражения Маккарти, в форме "условие" все

аргументы - функции, а не объекты. Вслед за Бэкусом вместо

(p1 --> f1; (p2 --> f2;g))

будем писать без скобок: p1 --> f1; p2 --> f2 ; g.

Генератор постоянных

const(X) : Y :: Y = <?> --> <?>; X.

Аргумент этой формы - некоторый объект, а результат - функция, значение

которой на всех определенных объектах совпадает с объектом, заданным в

качестве аргумента формы. Другими словами, результатом формы служит функция-

константа с заданным значением. Например, для любого Y /= <?>

const (<A,B>):Y = <A,B>.

Редукция (обозначение - /)

/f : X :: X = <X1> --> X1;

X = <X1, ... ,Xn> & n >= 2 --> f:<X1,/f:<X2, ... ,Xn>>;

<?>.

Общая аппликация (обозначение - А)

Af : X :: X = <> --> <>; X = <X1, ... ,Xn> -->

<f:X1, ... , f:Xn>; <?>.

Отличие от МТ-общей аппликации аналогичны отличиям МТ- и Б-конструкций.

Упражнение. Написать определение МТ-общей-аппликации, соответствующее

приведенному Б-определению.

Итерация

(while p f) : X :: (p:X) = T --> (while p f):(f:X);

(p:X) = F --> X ; <?>.

Смысл этой формы в том, что функция f в общем случае многократно

применяется к объекту X до тех пор, пока не станет ложным результат

применения к X логической функции (условия) p.

Специализатор (обозначение - s).

(s f X) : Y :: f:<X,Y>.

У этой формы два аргумента - бинарная операция f (функция от

двухэлементных объектов) и объект X. Результат формы - унарная операция,

получающаяся из f при ее специализации (иногда говорят "конкретизации") за

счет отождествления первого операнда с объектом X. Например

(s + 1) : Y = +:<1,Y> т.е. 1 + Y в обычных инфиксных обозначениях.

14.2.7. Определения

Б-определение новой функции - это выражение вида

DEF I :: r .

где в качестве I указано неиспользованное ранее название функции

(функциональный символ), а в качестве r - функциональная форма (которая

может зависеть от I - допустимы рекурсивные определения). Например

DEF last :: null * t1 --> 1; last * t1 ,

где справа от знака "::" - форма "условие", в которую входят в качестве p

композиция null * t1, в качестве f - селекторная функция "1", в качестве g -

композиция last * t1.

Так что last:<A,B> = B. Убедитесь, что это действительно верно!.

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

введенными или предопределенными. Использование в D функционального символа

всюду вне левой части определения (т.е. в качестве I) формально означает,

что вместо него нужно подставить соответствующее r и попытаться вычислить

полученную аппликацию. Если в процессе вычисления снова встретится

функциональный символ, определенный в D, то снова заменить его

соответствующей правой частью определения и т.д.

Ясно, что можно зациклиться. Как уже было сказано, это один из способов

получить <?> в качестве результата. Конечно, в разумных рекурсивных

определениях прямо или косвенно применяются условные выражения Маккарти,

которые позволяют вычислить аппликацию за конечное число шагов (за счет

чего?).

Б-определение, в сущности, еще одна форма, ставящая в соответствие

функциям-аргументам определяемую функцию. Тем самым мы закончили описывать

базис модели Б, а также основное (и единственное) средство развития - форму

DEF.

14.2.8. Программа вычисления факториала

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

прежнему стремясь к идеалу концептуальной ясности.

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

запрограммировать факториал, а показать, как это делается с помощью форм.

Начнем, как и раньше, с математического определения нужной функции

"факториал" (обозначение - !) и снова применим пошаговую детализацию.

Обычное математическое определение:

!n равен 1, если n = 0; иначе равен n, умноженному на !(n-1).

Как такое определение переписать в стиле Бэкуса?

На первом шаге нужно выявить функции, на которые непосредственно

разлагается исходная функция "факториал". Ее исходное определение не

устраивает нас потому, что оно не разлагает факториал на компоненты-функции,

а описывает его результат через результаты применения некоторых функций.

С учетом сказаного вернемся к исходному определению факториала. Что

известно про функцию "!"? То, что она разлагается на различные составные

части в зависимости от некоторого свойства аргумента (в зависимости от его

равенства нулю).

Следовательно, можно представить факториал условной формой

DEF ! :: (p --> f;g) .

где p,f и g - пока не определенные функции.

Вот и выполнен первый шаг детализации. Теперь займемся введенными

функциями.

Что известно про р? Это функция, проверяющая равенство нулю исходного

аргумента. Итак, р можно представить в виде композиции функции eq и

некоторой пока еще не определенной функции, которая готовит для eg аргументы

(точнее, формально один аргумент - кортеж из двух содержательных

аргументов). Получим

DEF p :: eq * f1 .

Что делает f1? Она ведь должна приготовить аргументы для проверки

исходного аргумента на равенство другому объекту, а именно нулю. Другими

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

аргумента факториала и нуля. Пару естественно получить формой "конструкция".

Так что

DEF f1 :: f2,f3 .

Что делает f2? Поставляет первый аргумент пары. Но ведь это исходный

аргумент без изменений! Следовательно,

DEF f2 :: id .

А что делает f3? Поставляет второй аргумент пары. Но ведь это нуль!

Отлично, значит f3 - постоянная, которую естественно определить через форму

const

DEF f3 :: const(0) .

Итак, функция р определена полностью. Продолжим детализацию для f и g.

Что делает f? Всегда дает в результате единицу. Значит, это постоянная,

которую также легко выразить через const.

DEF f :: const(1) .

А что делает g? Вычисляет произведение двух объектов, каждый из

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

Значит g естественно представить композицией функций "mult" (умножить) и

некоторой конструкции двух функций:

DEF g :: mult * (g1,g2) .

Очевидно, что g1 совпадает с id (почему?). А g2 представляет собой

композицию определяемой функции "!" и функции g3, вычитающей единицу из

исходного аргумента. Поэтому

DEF g2 :: ! * g3 .

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

готовящей для этого вычитания аргумент. Позволим себе пропустить шаг

подробной детализации и сразу написать

DEF g3 :: - * (id , const(1)) .

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

вычисляющая факториал, написана. Метод пошаговой детализации

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

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

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

нашем случае получим следующее функциональное соотношение, определяющее

факториал

DEF ! :: eq0 --> const(1); mult * (id , ! * sub1)

где через eq0 переобозначена для наглядности функция р, а через sub1 -

функция g3.

[Кстати, eq0 = (s eq 0). Верно ли, что sub1 = (s - 1)?].

Замечательное свойство пошаговой детализации (функциональной

декомпозиции) в модели Б состоит в том, что нам ни разу не понадобилось

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

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

контекстно-свободна). Это важнейшее преимущество функционального

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

Вопрос. За счет чего оно достигнуто?

Упражнение.. Запрограммируйте в стиле Бэкуса другое определение

факториала:

!n равен произведению всех различных натуральных чисел, меньших или

равных n.

14.2.9. Программа перемножения матриц

Напишем в стиле Бэкуса программу, перемножающую две прямоугольные

матрицы (согласованных размеров). Снова применим метод пошаговой

детализации. Начнем, как обычно, с постановки задачи, т.е. с определения

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

Результат умножения двух матриц B1(m,n) и B2(n,k)

(def) - это такая матрица С(m,k), каждый элемент с(i,j)

которой - скалярное произведение i-й строки

матрицы В1 на j-й столбец матрицы В2.

До сих пор в наших примерах мы имели дело с программами, работающими с

относительно просто устроенными данными. Поэтому можно было не заниматься

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

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

значимость отдельных аспектов программирования: "Дайте мне структуру данных,

а уж программу я и сам напишу!". Мы еще не раз поговорим о данных, а пока

займемся представлением исходных данных в нашей задаче, т.е. представим

матрицы в виде Б-объектов (других типов данных в модели Б просто нет).

При описании представления нам потребуется говорить о длине объектов-

кортежей. Поэтому введем еще одну примитивную функцию

leng : X :: X = <> --> 0; X = <X1, ... ,Xn> --> n; <?>.

Функция leng вычисляет число непосредственных компонент объекта Х (его

длину как кортежа). Например

leng:<A,<B,C>,D> = 3, leng:(2:<A,<B,C>,D>) = 2 .

Представим аргумент Х функции ММ парой (объектом длины 2), компоненты

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

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