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

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

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

которой представляют исходные матрицы. Так что

1:Х = В1 , 2:Х = В2

(здесь В1 и В2 используются как обозначения матриц, а не как Б-атомы!). При

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

если

В1 = 3 5 7 , В2 = 9 5

2 4 6 6 3

1 2

то X = < <<3,5,7>,<2,4,6>> , <<9,5>,<6,3>,<1,2>> >.

Так что

leng:(1:X) = 2 и это число строк в матрице В1,

leng:(1:(1:X)) = 3 и это число столбцов в матрице В1,

leng:(2:X) = 3 и это число строк в матрице В2,

leng:(1:(2:X)) = 2 и это число столбцов в матрице В2.

Итак, мы научились представлять матрицы "по строкам" и говорить об их

размерах в терминах "объектного представления". Осталось отметить, что если

объект Y представляет матрицу, то ее элемент, стоящий на пересечении i-й

строки и j-го столбца, можно получить с помощью функции

j * i .

При этом элементы матрицы В1 можно получить из Х функцией

j * i * 1 ,

а элементы матрицы В2 - функцией

j * i * 2 .

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

Как и раньше, начнем с "конца" определения (def). Там сказано, что "каждый

элемент" результата - это скалярное произведение некоторых объектов.

Следовательно, ММ можно определить как композицию двух функций, из которых

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

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

DEF MM :: f2 * f1 .

Можно ли сразу же продолжить функциональную декомпозицию? На первый

взгляд можно, тем более что совсем недавно шла речь о ее независимости от

контекста. Но как же детализировать, например, f2, не зная, какова структура

аргумента у этой функции? Все дело в том, что мы по существу еще не

завершили предыдущего шага декомпозиции - мало обозначить компоненты

функциональной формы, нужно еще описать их внешний эффект (или, как говорят,

спроектировать их внешнюю спецификацию). Другими словами, нужно решить,

каково у каждой из этих функций множество исходных данных, каково множество

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

второе каждая из функций осуществляет.

В нашем случае для ММ все это ясно (и тем самым определены исходные

данные для f1 и результаты для f2). Нужно "разделить сферы влияния" f1 и f2,

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

функции f1).

Вспомнив (def), нетрудно понять, что строение аргумента функции f2

должно отличаться от строения результата лишь тем, что на местах элементов

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

соответствующие с(i,j) будут получены скалярным умножением. Например, в

случае наших В1 и В2 аргумент функции f2 должен представлять собой объект,

соответствующий матрице размером 2 на 2, из которого функция, например, 2 *

1 извлекает пару <<3,5,7>,<5,3,2>>. Назовем поэтому аргумент функции f2

матрицей пар. Вот теперь можно продолжить декомпозицию.

На втором шаге займемся функцией f2. Она должна применять функцию IP

(скалярное умножение) КО ВСЕМ элементам матрицы пар. Если бы в нашем

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

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

f2 через эту форму и IP (кстати, как это сделать?). Но у нас есть лишь общая

аппликация А (применяющая заданную ей в качестве аргумента функцию ко всем

элементам кортежа). Таким образом, если ввести определение

DEF f2 :: (A f3) ,

то f2 окажется представленной через общую аппликацию с функцией f3,

применяемой ко всем "строкам" матрицы пар. Осталось обеспечить, чтобы при

каждом своем применении f3 применяла IP ко всем элементам "строки" (т.е.

кортежа пар). Ясно, что нужная функция легко выражается через А и IP.

DEF f3 :: (A IP) .

Подставляя вместо f3 ее определение и вслед за Бэкусом убирая вторые скобки,

завершим декомпозицию f2 определением

DEF f2 :: (AA IP) .

Вполне можно считать, что через АА обозначена та самая форма, которая

применяет свой аргумент ко всем элементам кортежа кортежей. Ее называют

двойной общей аппликацией.

На третьем шаге детализации займемся f1. Как мы выяснили, эта функция

из пары исходных матриц получает матрицу пар. При этом элемент матрицы пар

составлен из i-ой строки первой исходной матрицы и j-го столбца второй

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

столбцом второй. Например, в случае матриц В1 и В2 функция 2 * 1 должна

выбрать из матрицы пар объект <<3,5,7>,<2,4,6>>. Но раз каждая сочетается с

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

функциями - distl и distr. Однако чтобы "расписать", нужно иметь, что

"расписывать". И если строки первой матрицы представлены объектами-

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

ведь матрицы представлены "по строкам"! Поэтому следует представить f1

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

столбцам", внешняя - "расписывает" матрицу пар. Итак, третий шаг детализации

завершает определение

DEF f1 :: f5 * f4 .

(При этом считаем, что внешняя спецификация новых функций очевидна;

кстати, понимаете ли Вы, что у них на входе и что на выходе?).

На четвертом шаге функциональной декомпозиции займемся f4.

Содержательно ее назначение - подготовить из исходной новую пару матриц,

сохранив ее первую компоненту и переписав "по столбцам" вторую. При уже

имеющемся у нас опыте Б-программирования можно сразу выписать определение

DEF f4 :: (1,trans * 2) .

Действительно, такая конструкция составляет новую пару из первой

компоненты исходной пары и транспонированной второй.

На пятом шаге рассмотрим f5. Ее назначение - по двум матрицам получить

матрицу пар, сочетая каждую строку первой матрицы с каждой строкой второй.

При этом i-я строка матрицы пар (т.е. ее i-й элемент как кортежа)

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

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

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

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

такую пару <строка,матрица> превратить в кортеж пар <строка,строка>.

Здесь пригодятся наши "расписывающие" функции. Действительно, кортеж

пар <строка,матрица> получается применением к паре матриц функции distr

("расписать правым" - ведь правая компонента сочетается со всеми

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

получить кортеж вида <строка,строка> применением общей аппликации с функцией

distl (ведь левая компонента ее аргумента сочетается со всеми компонентами

правой матрицы). Итак, декомпозицию f5 завершает определение

DEF f5 :: (A distl) * distr .

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

функциональной декомпозиции функции ММ. Подставляя вместо обозначений

промежуточных функций их определения, получаем определение MM

DEF MM :: (AA IP) * (A distl) * distr * (1,trans * 2) .

******* ----------------- =============

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

матрицы столбцам второй (выделено двойной чертой), подготовку пар (выделено

одинарной чертой) и собственно перемножение (выделено звездочками).

И опять ничего лишнего, структура программы-формулы получена

непосредственно из постановки задачи! Принцип концептуальной ясности снова

действует. Конечно, сначала такая программа может показаться и не слишком

понятной. Новое, тем более принципиально новое, усваивается не сразу. Однако

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

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

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

инициализации (установки начальных значений).

Как видите, многого нет с точки зрения традиционного программирования в

стиле фон Неймана. Зато есть концептуальная ясность, есть обобщенность (в

качестве исходных данных пригодны любые согласованные по размерам матрицы;

кстати, где учтено требование согласованности размеров?), есть возможность

распараллеливания, есть, наконец, возможность оптимизации (так как

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

последовательно, не требуя большой памяти - эту возможность мы еще

продемонстрируем)

Замечание. Важно понять, что стиль программирования, ориентированнный

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

на сути решаемой задачи при возможно более полном игнорировании таких

второстепенных на этом этапе вопросов, как ресурсоемкость решения с точки

зрения исполнителя. Самое главное - найти правильное и понятное (убедительно

правильное, концептуально ясное) решение.

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

ресурсоемкости, осмысленно тратить время и силы на постановку и решение

новой задачи - искать лучшее решение. (Кстати, это тоже пошаговая

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

такой детализации (на котором в сущности конструктивно доказывается теорема

существования решения) принципиально важно с методологической и

технологической точек зрения. Ведь на последующих шагах оптимальное решение

ищется в надежных и комфортных условиях - есть куда отступать и есть с чем

сравнивать.

Такой подход требует определенной психологической подготовки. Например,

когда в процессе пошаговой детализации мы обнаружили, что i-ая строка

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

очевиден - размножить каждую строку в нужном количестве экземпляров! При

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

"квалифицированному" программисту - он интуитивно игнорирует его как

расточительное по ресурсам. Но именно такое решение ведет не только к

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

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

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

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

показавшейся привлекательной программой.

Итак, мы рассмотрели три модели ЯП (в основном с технологической

позиции, т.е. с точки зрения программиста). Модель Н - самая близкая к ЯП,

получившим наибольшее распространение (неймановским ЯП). Вместе с тем она

проявляет основной источник сложности программирования на этих ЯП -

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

демонстрирует один из перспективных подходов к созданию таких средств - она

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

ключевых абстракций (анализа и синтеза текстов посредством образцов).

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

которого опираются на многовековой опыт применения алгебраических формул. С

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

современного массового программирования (однако она находится в центре

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

Таким образом, ЯП можно строить на весьма различных базисах и различных

средствах развития.

15. Доказательное программирование (модель Д)

15.1. Зачем оно нужно

Если согласиться, что надежность - важнейшее качество программы, то

понятен интерес современных исследователей к таким методам создания

программ, которые бы в максимальной степени способствовали устранению ошибок

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

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