Готовый перевод Concepts, Techniques and Models of Computer Programming / Концепции, Техники и Модели Компьютерного Программирования: Глава 1 - Введение в Концепции Программирования

"Царской дороги в геометрии нет."
- ответ Евклида Птолемею, Евклид (около 300 лет до н. э.)

"Следуй по дороге из жёлтого кирпича."
- Удивительный волшебник из страны Оз, Лаймен Фрэнк Баум (1856 - 1919)

Программирование - это указание компьютеру о том как он должен выполнять свою работу. В этой главе содержится простое, практическое введение в наиболее важные концепции программирования. Мы предполагаем что увы уже имели некоторый опыт работы с компьютерами. Мы используем интерактивный интерфейс Моцарт для постепенного введения в концепции программирования. Мы настоятельно рекомендуем вам пробовать выполнять приведённый в книге код на системе Моцарт.

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

1.1 Калькулятор

Начнём с использования системы для выполнения вычислений. Запустим систему Моцарт напечатав:

oz

или дважды кликнув мышью по иконке Моцарт. Будет открыто окно редактора с двумя областями. В верхней области напечатайте следующую строку:

{Browse 9999*9999}

Используйте мышь для выделения строки. Теперь перейдите в меню Oz и выберите Feed Region. Выделенный текст будет передан в систему. Система выполнит вычисление 9999*9999 и отобразит результат, 99980001, в специальном окне под названием браузер (browser). Фигурные скобки { ... } используются для вызова процедуры или функции. Browse - это процедура с одним аргументом, и вызывается как {Browse X}. Будет открыто окно браузера, если оно уже не открыто, и в нём будет отображено X.

1.2 Переменные

При работе с калькулятором, нам может понадобиться запомнить старый результат для того, чтобы не печатать его ещё раз. Мы можем сделать это объявив переменную (variable):

declare
V=9999*9999

Так мы объявили V и привязали его к 99980001. Мы можем использовать эту переменную в последующих вычислениях:

{Browse V*V}

Будет дан ответ 9996000599960001.

Переменные - это всего лишь ярлыки для значений. То есть, они не могут быть присвоены более одного раза. Но, вы можете определить другую переменную с тем же именем, что и предыдущая переменная. Это означает что старая переменная уже станет недоступной. Но предыдущие вычисления, использовавшие старую переменную, не изменятся. А происходит это потому, что за словом "переменная" скрываются две концепции:

Идентификатор. Это то, что вы печатаете. Переменные начинаются с заглавной буквы и могут быть продолжены любыми буквами или цифрами. Например, заглавная буква "V" может быть идентификатором переменной.

Сохраняемое значение. Это то, что используется системой для вычислений. Часть системной памяти, которую мы называем сохранённой.

Оператор declare создаёт новое сохранённое значение и делает так, что идентификатор переменной начинает ссылаться на это значение. Старые вычисления, использующие аналогичный идентификатор V, не будут изменяться, поскольку идентификатор относится к другой переменной.

1.3 Функции

А теперь выполним более сложный расчёт. Предположим что нам нужно вычислить функцию факториал n!, которая определяется как 1 x 2 x ... x (n-1) x n. У нас получаются количество перестановок из n элементов, то есть, количество разнообразных способов размещения этих элементов в строку. Факториал 10:

{Browse 1*2*3*4*5*6*7*8*9*10}

Будет отображено 3628800. А если мы захотим вычислить факториал 100? Мы были бы непротив если бы система выполнила за нас эту утомительную работу по печати целых чисел от 1 до 100. Мы сделаем даже больше: мы объясним системе как вычислить факториал для любых n. Мы сделаем это определив функцию:

declare
fun {Fact N}
if N==0 then 1 else N*{Fact N-1} end
end

Ключевое слово declare что мы хотим определить нечто новое. Ключевое слово fun обозначает начало новой функции. Функция называется Fuct и имеет один аргумент N. Аргумент является локальной переменной, то есть, известен только внутри тела функции. Каждый раз мы вызываем функцию с новой объявленной переменной.

Рекурсия

Тело функции - это инструкция с выражением if. При вызове функции выражение if выполняет следующие шаги:

Первым делом выполняется проверка на равенство N нулю с помощью выполнения теста N==0.

Если тест завершился успешно, то вычисляется выражение после then. В данном случае просто возвращается число 1. Происходит это потому что факториал 0 равен 1.

Если тест провалился, то вычисляется выражение после else. Таким образом если N не равен 0, то выполняется выражение N*{Fact N-1}. Это выражение использует Fact, функцию, которую мы уже определили! Это называется рекурсией (recursion). Это абсолютно нормально и нет причин для тревоги. Fact рекурсивен поскольку факториал N - это просто N умноженный на факториал N-1. Fact использует следующее математическое определение факториала:

0! = 1
n! = n * (n-1)! если n > 0

а это рекурсия.

Теперь мы можем попробовать запустить функцию:

{Browse {Fact 10}}

В результате будет отображено 3628800. Можно быть уверенным, что Fact выполняет верные вычисления. А теперь попробуем ввести более крупный ввод:

{Browse {Fact 100}}

Будет отображено огромное число:

933 26215 44394 41526 81699 23885 62667 00490 71596 82643 81621 46859 29638 95217 59999 32299 15608 94146 39761 56518 28625 36979 20827 22375 82511 85210 91686 40000 00000 00000 00000 00000

Это пример арифметики с независимой точностью, иногда называемой "бесконечной точностью", хотя она и не является бесконечной.Точность ограничивается количеством памяти в вашей системе. Типичные персональные компьютеры низкого ценового диапазона с 64 MB памяти может обрабатывать сотни из тысяч цифр. Скептически настроенный читатель может спросить: действительно ли это огромное число является факториалом 100? Как мы можем это проверить? Выполнение ручного вычисления займёт много времени и возможно результат будет неверным. Позже мы увидим как можно проверить корректность работы системы.

Комбинации

Напишем функцию, вычисляющую число комбинаций r элементов из n элементов. Это равносильно числу подмножеств размером r, которые можно собрать из набора размером n. В математическом виде записывается как (n r) и произносится "r выбранные из n". И может быть определено с помощью использования факториала:

n
r

=
n!
r !( n − r )!

что дословно можно переписать в следующую функцию:

declare
fun {Comb N R}
{Fact N} div ({Fact R}*{Fact N-R})
end

Например, {Comb 10 3} даёт 120, являющееся числом способов с помощью которых можно выбрать 3 элемента из 10. Способ с помощью которого написан Comb не самый эффективный, но, скорее всего, самый простой.

Функциональные абстракции

Функция Comb вызывает Fact три раза. Всегда возможно использовать существующие функции для облегчения определения новых функций. Этот принцип называется функциональной абстракцией (functional abstraction), поскольку использует функции для постройки абстракций. Таким образом, большие программы похожи на лук, то есть, слой на слое из функций, вызывающих функции.

1.4 Списки

Теперь мы можем вычислять целые числа с помощью функций. Но сами по себе целые числа не столь интересны. Предположим что нам нужно вычислять лишь некоторые целые числа. Например, мы можем захотеть вычислить треугольник Паскаля:

1
11
121
1331

Рисунок 1.1: Конструкция списка [5 6 7 8]

Этот треугольник назван в честь учёного и мистика Блеза Паскаля. Он начинается с 1 в первой строке. Каждый элемент представляет сумму двух других вышестоящих элементов: правого и левого. (Если соседних элементов нет, например на грани, то в качестве недостающего элемента берут ноль.) Мы хотели бы определить одну функцию, которая формирует n-ую строку за один раз. N-ая строка содержит n целых чисел. Мы можем реализовать такую функцию с помощью списков целых чисел.

Список - это всего лишь последовательность элементов, окружённая скобками справа и слева, например [5 6 7 8]. По историческим причинам, пустой список пишется как nil (а не []). Списки могут отображаться как числа:

{Browse [5 6 7 8]}

Запись вида [5 6 7 8] - это просто сокращение. На самом деле список - это цепь из ссылок, где каждая ссылка содержит две вещи: один элемент списка и указатель на остальную часть цепи. Списки всегда создаются из одного элемента, начинаются с nil и к нему добавляются один за другим ссылки. Новая ссылка пишется как H|T, где H - это новый элемент и T - старая часть цепи. Построим список. Мы начнём с Z=nil. Мы добавим первую ссылку Y=7|Z, а затем вторую ссылку X=6|Y. Теперь X ссылается на список из двух ссылок, а сам список может быть написан как [6 7].

Ссылка H|T часто называется как cons, это термин, который пришёл к нам из Лиспа 1. Также мы называем ссылку парой списка. Создание новых ссылок называется консингом (consing). Если T - это список, то консинг H и T создаёт новый список H|T:

1 Большинство списковой терминологии возникло вместе с появлением языка Лисп в конце 1950 годов и с тех пор так и прижилось [120]. Использование вертикальной разделительной черты пришло из Prolog, языка логического программирования, изобретённого в начале 1970 годов [40, 182]. В Лиспе cons записывается как (H . T), что называется точечной парой.

Рисунок 1.2: Вычисление пятой строки треугольника Паскаля

declare
H=5
T=[6 7 8]
{Browse H|T}

Список H|T может быть записан как [5 6 7 8]. Здесь голова (head) 5 и хвост (tail) [6 7 8]. Cons H|T можно разобрать и вернуться к голове и хвосту:

declare
L=[5 6 7 8]
{Browse L.1}
{Browse L.2}

Здесь применяется оператор точка ".", служит для выбора первого или второго аргумента из пары списка. Выполнение L.1 возвращает голову L, целочисленное 5. Выполнение L.2 возвращает хвост L, список [6 7 8]. Рисунок 1.1 изображает строение списка: L - это цепь, в которой каждое звено обладает одним списковым элементом и nil обозначает конец. Выполнение L.1 возвращает первый элемент, а выполнение L.2 возвращает остальную часть цепи.

Сравнение с шаблоном

Мы можем сократить нашу работу и получить части списка воспользовавшись инструкцией case, за один шаг получающей голову и хвост:

declare
L=[5 6 7 8]
case L of H|T then {Browse H} {Browse T} end

Возвращаются 5 и [6 7 8], также, как и в примере выше. Инструкция case определяет две локальные переменные, H и T, и привязывает их к голове и хвосту списка L. Мы говорим что инструкция case выполняет сравнение с шаблоном (pattern matching), поскольку она выполняет разложение L в соответствии с "шаблоном" H|T. Локальные переменные определённые в case - подобны переменным, определённым с помощью declare, с тем исключением что переменные существуют только в теле оператора case, то есть, между then и end.

1.5 Функции для работы над списками

Теперь, когда мы можем производить вычисления над списками, определим функцию, {Pascal N}, предназначенную для вычисления n-ой строки треугольника Паскаля. Для начала разберём вычисление в ручную. Рисунок 1.2 иллюстрирует вычисление пятой строки, основанное на четвёртой строке. Рассмотрим механизм вычисления в случае когда каждая строка представляет список из целых чисел. Вычисление текущей строки мы начинаем с предыдущей строки. Мы сдвигаем её налево на одну позицию и сдвигаем направо на одну позицию. Дальше мы складываем вместе две сдвинутые строки. Например возьмём четвёртую строку:

[1 3 3 1]

Мы сдвинули эту строку влево и вправо и сложили получившиеся строки вместе:

[1 3 3 1 0]
+ [0 1 3 3 1]

Заметьте, что сдвиг влево добавляет ноль справа, а сдвиг налево добавляет ноль слева. Выполнение сложения даёт следующий результат:

[1 4 6 4 1]

что является пятой строкой.

Главная функция

Теперь, когда мы поняли как решать проблему, мы можем написать функцию, выполняющую те же операции. Вот она:

declare Pascal AddList ShiftLeft ShiftRight
fun {Pascal N}
if N==1 then [1]
else
{AddList {ShiftLeft {Pascal N-1}}
{ShiftRight {Pascal N-1}}}
end
end

В дополнение к определению Pascal мы определили переменные для трёх дополнительных функций, которые ещё нужно определить.

Дополнительные функции

Проблема решена не до конца. Мы определили ещё три функции: ShiftLeft, сдвигающую влево на одну позицию, ShiftRight, сдвигающую вправо на одну позицию и AddList, складывающую два списка. Вот ShiftLeft и ShiftRight:

fun {ShiftLeft L}
case L of H|T then
H|{ShiftLeft T}
else [0] end
end
fun {ShiftRight L} 0|L end

ShiftRight всего лишь добавляет ноль слева. ShiftLeft проходит через L по одному элементу за раз и строит вывод также в один элемент за единицу времени. Мы добавили else в инструкцию case. Аналогично else в if: исполняется при несовпадении с шаблоном case. Таким образом, если L окажется пустым, то на выходе будет [0], то есть, список с единственным нулём внутри.

Вот AddList:

fun {AddList L1 L2}
case L1 of H1|T1 then
case L2 of H2|T2 then
H1+H2|{AddList T1 T2}
end
else nil end
end

Это самая сложная функция из всех виденных на данный момент. Она использует две case инструкции, одна в другой, поскольку нам нужно разобрать два списка, L1 и L2. Теперь, когда у нас есть полное определение Pascal, мы можем вычислить любую строку из треугольника Паскаля. Например, вызов {Pascal 20} вернёт 20-ю строку:

[1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1]

Это правильный ответ? Как это можно доказать? Он выглядит правильным: он симметричен (если написать его справа налево, то мы получим тот же список) и первый и второй аргументы равны 1 и 19, что тоже правильно. Взглянув на рисунок 1.2, можно увидеть что второй элемент n-ой строки всегда n-1 (он всегда на единицу больше предыдущей строки и для первой строки начинается с ноля). В следующем разделе мы узнаем как надо выяснять корректность.

Разработка программного обеспечения методом сверху-вниз

Просуммируем технику, применённую для написания Pascal:

* Первый шаг - это выяснение выполнения вычислений и ручное воспроизведение вычислений.

* Второй шаг - это написание главной функции, решающей нашу задачу, предполагая что некоторые вспомогательные функции (в нашем примере, ShiftLeft, ShiftRight и AddList) уже известны.

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

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

1.6 Корректность

Программа корректна тогда, когда она выполняет то, что мы от неё хотим. Как мы можем доказать что программа корректна? Обычно невозможно повторить программные вычисления вручную. Нам нужен другой способ. Один из простых способов, который мы уже применяли заключается в том, чтобы проверить программу на уже заранее известных данных. Это повышает доверие к программе. Но на этот способ нельзя полностью положиться. Для того, чтобы в целом доказать корректность, надо произвести рассуждения о программе. Это означает три вещи:

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

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

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

Программа, для которой доказана её корректность, может возвращать некорректные результаты, если система, на которой она запущена, реализована некорректно. Как нам убедиться что система удовлетворяет семантике? Здесь нужно выполнить проверку: это означает проверку компилятора, исполняющей системы, операционной системы и даже аппаратного обеспечения! Это важная тема, но освещение этой темы лежит за пределом этой книги. В этой книге мы доверяемся разработчикам Моцарта, компаниям, выпускающим программное обеспечение и производителям аппаратного обеспечения.2

2 Некоторые скажут что это звучит глупо. Перефразируя Томаса Джефферсона, они скажут что цена корректности - это вечная бдительность.

Математическая индукция

Математическая индукция - это одна из очень полезных техник. Она заключается в двух шагах. Вначале нам нужно показать что программа корректна для простых случаев. Далее нам нужно показать, что если программа корректна для простого случая, то она будет корректной и для следующего случая. Исходя из этих двух шагов, математическая индукция позволяет нам сделать вывод о том, что программа будет всегда корректной. Эта техника может быть применена для целочисленных значений и списков:

Для целочисленных значений базовым случаем является 0 или 1, а для данного целого числа n следующим случаем будет n+1.

Для списков базовым случаем будет nil (пустой список) или список с одним или несколькими элементами, и для данного T списка следующим случаем будет H|T (без условий для H).

Рассмотрим как применяется индукция для функции факториала:

{Fact 0} возвращает правильный ответ, а именно, 1.

Предположим, что {Fact N-1} корректен. Тогда рассмотрим вызов {Fact N}. Мы увидим что инструкция if выполняет случай else, и вычисляет N*{Fact N-1}. По условию, {Fact N-1} возвращает правильный ответ. Таким образом, предположив что умножение тоже возвращает правильный результат, {Fact N} также возвращает правильный ответ.

Это рассуждение использует математическое определение факториала, а именно: n! = n x (n - 1)! если n > 0, и 0! = 1. Дальше в этой книге мы увидим более сложные техники рассуждений. Но, базовый подход всегда остаётся тем же самым: начинаем с семантики языка и спецификации задачи и применяем математические рассуждения для доказательства того, что программа корректно реализует спецификацию.

1.7 Сложность

Функция Pascal, уже определённая нами выше, работает очень медленно если мы попытаемся вычислить строки с большим номером. Вычисление строки 20 займёт по времени около двух или одной секунд. Вычисление 30-й строки уже займёт значительное количество минут. Если вы запустите это вычисление, то приготовьтесь к длительному ожиданию. В чём причина столь долгой работы? Давайте ещё раз взглянем на функцию Pascal:

fun {Pascal N}
if N==1 then [1]
else
{AddList {ShiftLeft {Pascal N-1}}
{ShiftRight {Pascal N-1}}}
end
end

Вызов {Pascal N} приведёт к двукратному вызову {Pascal N-1}. Таким образом, вызов {Pascal 30} приведёт к двукратному вызову {Pascal 29}, что в свою очередь приведёт к четырёхкратному вызову {Pascal 28}, к восьмикратному {Pascal 27} и так далее, удваивая каждый следующий ряд. В результате у нас получается 2 29 вызовов {Pascal 1}, а это примерно равно пол миллиарду вызовов. Нет ничего удивительного в том, что {Pascal 30} настолько медлителен. Можем ли мы ускорить его? Да, есть один простой способ: достаточно вызывать {Pascal N-1} один раз, а не дважды. Поскольку второй вызов возвращает тот же результат что и первый вызов, то нам будет достаточно запомнить первый вызов. Мы можем запомнить его воспользовавшись локальной переменной. Вот новая функция FastPascal, использующая локальную переменную:

fun {FastPascal N}
if N==1 then [1]
else L in
L={FastPascal N-1}
{AddList {ShiftLeft L} {ShiftRight L}}
end
end

Мы определили локальную переменную L добавив "L in" в else. Всё равно что использование declare, с тем исключением что переменная будет существовать между else и end. Мы привязали L к результату {FastPascal N-1}. Теперь мы можем использовать L везде, где только захотим. Насколько быстр FastPascal? Попробуйте вычислить 30-ю строку. В случае с Pascal потребуются минуты, но FastPascal отрабатывает практически мгновенно. Урок, который мы можем извлечь из этого примера, говорит о том, что использование хорошего алгоритма более важно чем наличие самого лучшего компилятора или самой быстрой машины.

Время выполнение (run-time) гарантирует исполнение программы в течение определённого времени

Как показывает пример выше, очень важно иметь сведения о времени выполнения программы. Знание, касающееся времени, затраченного на выполнение программы менее важно нежели знание того, что время не будет расти взрывообразно с ростом входных данных. Время, затраченное на исполнение программы можно рассматривать как или функцию от входных данных, или константу и называющуюся временной сложностью (time complexity). Эта функция зависит от изменения размеров входных данных. Мы предполагаем что эта функция зависит от того как используется программа. Например, входной размер {Pascal N} будет простым целочисленным N (а не, например, количеством памяти, требуемой для хранения N).

Временная сложность {Pascal N} пропорциональна 2n. Это экспоненциальная функция от n, растущая очень быстро при увеличении n. Какова временная сложность {FastPascal N}? Есть n рекурсивных вызовов, и каждый вызов создаёт список со средним размером n/2. Таким образом временная сложность пропорциональна n2. Эта полиномиальная функция от n, растущая гораздо меньше чем экспоненциальная функция. Программы с экспоненциальной временной сложностью непрактичны за исключением очень малых входных данных. И наоборот, программы с низкой полиномиальной временной сложностью - практичны.

1.8 Ленивое вычисление

Функции, которые мы до сих пор писали, выполняют вычисления сразу же после вызова. Такое поведение называется энергичным вычислением (eager evaluation). Другой способ вычисления функций называется ленивым вычислением (lazy evaluation). 3 В ленивом вычислении выполнение программы начинается только тогда, когда нужен результат. Вот простой пример ленивой функции, вычисляющей список целых чисел:

3 Иногда называется как вычисление управляемое данными (data-driven) и вычисление по-требованию (demand-driven) соответственно.

fun lazy {Ints N}
N|{Ints N+1}
end

Вызов {Ints 0} вычисляет бесконечный список 0|1|2|3|4|5|... . Выглядит как бесконечный цикл, но это не так. Аннотация lazy указывает что функция будет вычисляться только тогда, когда будет нужен результат. В этом одно из достоинств ленивого вычисления: мы можем вычислять потенциально бесконечные структуры данных без всяких условий, ограничивающих цикл. Например:

L={Ints 0}
{Browse L}

Будет отображено следующее, то есть, почти ничего:

L<Future>

(Браузер отобразит значения, не влияющие на их вычисление.) Аннотация "Future" означает что L обладает ленивой функцией, присоединённой к нему. Если потребуется значение L, то эта функция будет автоматически вызвана. Таким образом, для того, чтобы получить результаты, мы должны выполнить что-то, для чего требуется список. Например:

{Browse L.1}

Будет отображён первый элемент, а именно 0. Мы можем вычислить список так, как будто он уже существует:

case L of A|B|C|_ then {Browse A+B+C} end

Результатом будет вычисление только первых трёх элементов L и ничего более. Что будет отображено?

Ленивое вычисление треугольника Паскаля

Сделаем что нибудь полезное с помощью ленивого вычисления. Было бы неплохо написать функцию, вычисляющую столько строк треугольника Паскаля, сколько нам нужно, но, мы не знаем сколько строк нам нужно вычислить. Нам нужна возможность наблюдать ряды и самим решать когда их количество будет нас удовлетворять. Вот ленивая функция, которая генерирует бесконечный список строк:

fun lazy {PascalList Row}
Row|{PascalList
{AddList {ShiftLeft Row}
{ShiftRight Row}}}
end

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

declare
L={PascalList [1]}
{Browse L}

(Аргумент [1] - это первая строка треугольника.) Для того, чтобы получить больше результатов, нужно уведомить об этом систему:

{Browse L.1}
{Browse L.2.1}

Будут отображены первая и вторая строки.

Вместо написания ленивой функции, мы могли бы написать функцию, получающую N, число требуемых строк, и прямо вычисляющую эти строки, начиная с начальной строки:

fun {PascalList2 N Row}
if N==1 then [Row]
else
Row|{PascalList2 N-1
{AddList {ShiftLeft Row}
{ShiftRight Row}}}
end
end

Мы можем отобразить 10 строк с помощью вызова {Browse {PascalList2 10 [1]}}. А вдруг позже нам понадобится 11 строк? Нам придётся вызвать PascalList2 ещё раз, на этот раз с аргументом 11. Вся наша предыдущая работа по вычислению 10 строк будет напрасной. Ленивая версия позволяет избежать необходимости в выполнении всей работы заново. Она всегда готова продолжить работу с того места, где произошла пауза.

1.9 Высокоуровневое программирование

Мы написали эффективную функцию, FastPascal, вычисляющую строки треугольника Паскаля. Теперь было бы неплохо поэкспериментировать с различными вариациями треугольника Паскаля. Например, вместо сложения чисел для получения строки, мы могли бы вычитать их или применять к ним exclusive-or (для вычисления чётности или нечётности) или какие-нибудь другие операции. Один из возможных способов - это написать отдельную версию FastPascal, реализующую какой-либо один вариант. Но подобный подход быстро становится утомительным. Можем ли мы вместо создания различных вариантов использовать какой-либо один вариант? Это возможно. Назовём эту реализацию GenericPascal. Всякий раз, когда мы вызываем её, мы будем передавать ей какую-либо изменяющуюся функцию (сложение, выяснение чётности и т.д.) в виде аргумента. Возможность передачи функций как аргументов известна как высокоуровневое программирование.

Вот определение GenericPascal. Она принимает ещё один аргумент, Op, хранящий функцию, которая вычисляет каждое число:

fun {GenericPascal Op N}
if N==1 then [1]
else L in
L={GenericPascal Op N-1}
{OpList Op {ShiftLeft L} {ShiftRight L}}
end
end

AddList заменён на OpList. Дополнительный аргумент Op передаётся в OpList. ShiftLeft и ShiftRight не надо ничего знать об Op, поэтому мы продолжаем использовать старые версии. Определение OpList:

fun {OpList Op L1 L2}
case L1 of H1|T1 then
case L2 of H2|T2 then
{Op H1 H2}|{OpList Op T1 T2}
end
else nil end
end

Вместо сложения H1+H2 эта версия выполняет {Op H1 H2}.

Разновидности треугольника Паскаля.

Определим некоторые функции для того, чтобы испытать GenericPascal. Для получения исходного треугольника Паскаля мы можем определить функцию сложения:

fun {Add X Y} X+Y end

Теперь мы можем запустить {GenericPascal Add 5}. 4 В результате мы получим всё ту же пятую строку. С помощью GenericPascal мы можем определить FastPascal:

4 Мы могли бы вызвать {GenericPascal Number. ́+ ́ 5}, поскольку операция сложения ́+ ́ - это часть модуля Number. Но в этой главе модули не упоминаются.

fun {FastPascal N} {GenericPascal Add N} end

Определим другую функцию:

fun {Xor X Y} if X==Y then 0 else 1 end end

Эта функция реализует операцию исключающее ИЛИ, определяемую так:

X Y {Xor X Y}
0 0 0
0 1 1
1 0 1
1 1 0

Исключающее ИЛИ позволяет вычислить чётность каждого числа в треугольнике Паскаля, то есть, является ли число чётным или нечётным. Сами числа не вычисляются. Вызов {GenericPascal Xor N} даст такой результат:

1
1
1
1
1
1
1
0
1
1
0
1
1
0
0
1
0
0
1
1
1
1
0
1
0
1
0
1
. . . . . . . . . . . . . .

Некоторые другие функции даны в упражнениях.

1.10 Параллелизм

Было бы неплохо если бы программа могла выполнять несколько действий и каждое действие могло выполняться обособленно. Это называется параллелизмом (concurrency). Между выполняемыми операциями не должно быть никаких взаимодействий, только если программист не решит что они должны обмениваться между собой информацией. Это отображение работы реального мира вне системы. Неплохо бы повторить это внутри системы.

Мы вводим параллелизм через создание нитей. Нить (thread) - это простое исполнение таких программ, как функции, которые мы видели ранее. Разница в том, что программа может содержать в себе более одной нити. Нити создаются с помощью инструкции thread. Помните насколько медленной была исходная функция Pascal? Мы могли вызывать Pascal внутри его собственной нити. Это означает что Pascal не будет выполнять никаких других вычислений. Если Pascal будет выполнять много вычислений, то время ожидания может затянуться. А всё потому, что нити разделяют между собой один компьютер. Но, ни одна нить не будет останавливаться. Пример:

thread P in
P={Pascal 30}
{Browse P}
end
{Browse 99*99}

Так мы создали новую нить. Внутри этой новой нити мы вызвали {Pascal 30} и затем вызвали Browse для отображения результата. Новая нить будет работать долгое время. Но это не остановит систему и она немедленно отобразит результат вычисления 99*99.

1.11 Поток данных

Что произойдёт если операция будет пытаться использовать переменную, которая ещё не была привязана? С чисто эстетической точки зрения было бы неплохо если бы операция просто дождалась привязки переменной. Возможно какая-нибудь другая нить привязала бы переменную, и после этого операция могла бы продолжиться. Это цивилизованное поведение известно под названием поток данных (dataflow). Рисунок 1.3 демонстрирует простой пример: два умножения ждут пока их аргументы будут привязаны и сложение ждёт пока не будут завершены операции умножения. Позже мы увидим что существует множество хороших причин по которым крайне желателен поток данных. А теперь, посмотрим как работает вместе поток данных и параллелизм. Возьмём такой пример:

declare X in
thread {Delay 10000} X=99 end
{Browse start} {Browse X*X}

Умножение X*X будет ждать до тех пор, пока не будет привязано значение X. Первый Browse незамедлительно отобразит start. Второй Browse будет ожидать окончания перемножения, и поэтому ничего не отобразит. Вызов {Delay 10000} создаст паузу на 10000 миллисекунд (то есть, на 10 секунд). X будет привязан только по прошествии паузы. Когда X будет привязан, тогда будет продолжена операция умножения и сработает второе Browse, отображающее 9801. Две операции X=99 и X*X могут выполняться в любом порядке с паузами любой продолжительности; поток данных всегда будет возвращать один результат. Замедление вычисления результата может вызвать только эффект паузы. Например:

declare X in
thread {Browse start} {Browse X*X} end
{Delay 10000} X=99

Поведение такое же что и в предыдущем примере: браузер отобразит 9801 после 10 секунд. Это иллюстрация двух удобных особенностей потока данных. Первое, вычисления работают корректно вне зависимости от того как они разбиты между нитями. Второе, вычисления терпеливы: они не порождают сигналы об ошибках, а просто ждут.

Добавление нитей и задержек в программу может коренным образом изменить внешний вид программы. Но, пока вызываются одни и те же операции с одними и теми же аргументами, то результаты программы будут неизменными. Это ключевая особенность параллелизма потока данных. Вот почему параллелизм потока данных позволяет использовать большинство преимуществ параллелизма попутно избежав сложностей, обычно ассоциируемых с ним.

1.12 Состояние

Как сделать так, чтобы функция могла знать что происходило с ней в прошлом? Это означает что функция должна обладать некоторой внутренней памятью, которая бы помогала ей выполнять свою работу. Память нужна функциям, которые могут изменять своё поведение и знать своё прошлое. Эта разновидность памяти называется явным состоянием (explicit state). Как и параллелизм, модели явного состояния - это важные аспекты отображающие работу настоящего мира. И нам нужно смоделировать их в нашей системе. В дальнейшем, по мере чтения, вы увидите более глубокие причины для явного состояния. Ну а теперь, рассмотрим работу состояния.

Например, нам может понадобиться знать как часто была использована функция FastPascal. Каким способом FastPascal может запомнить количество предыдущих вызовов? Мы реализуем это через добавление явного состояния.

Ячейка памяти

Есть несколько способов определения явного состояния. Простейший способ - это определение единственной ячейки памяти (memory cell). Это некая разновидность ящика в который вы можете помещать произвольное содержимое. Многие языки программирования называют этот ящик "переменной". Мы называем её "ячейкой" для того, чтобы избежать путаницы с ранее использованными переменными, которые скорее подобны математическим переменным, то есть, простые обозначения некоторых значений. Для ячеек существует три функции: NewCell создаёт новую ячейку, := (присваивание) вставляет новое значение в ячейку и @ (доступ) получает текущее значение, сохранённое в ячейке. Доступ и присваивание также называются как чтение и запись. Например:

declare
C={NewCell 0}
C:=@C+1
{Browse @C}

Тут создаётся ячейка C с инициализирующим содержимым 0, содержимое увеличивается на единицу и отображается содержимое ячейки C.

Добавление памяти к FastPascal

Благодаря ячейки памяти мы можем добавить FastPascal возможность подсчитывать количество вызовов. Для начала мы создадим ячейку за пределами FastPascal. Затем внутри FastPascal мы добавим единицу к содержимому ячейки. Результат будет таким:

declare
C={NewCell 0}
fun {FastPascal N}
C:=@C+1
{GenericPascal Add N}
end

(Ради сокращения это определение использует GenericPascal.)

1.13 Объекты

Функции с внутренней памятью, обычно, называются объектами (objects). Таким образом определённая в предыдущем разделе расширенная версия FastPascal является объектом. Оказывается что объекты - это очень полезные звери. Дадим другой пример. Мы определим объект-счётчик. Счётчик обладает ячейкой, в которой хранит текущий счёт. У счётчика есть две операции, Bump и Read. Bump добавляет единицу и возвращает получившийся счёт. Read просто возвращает счёт. Определение:

declare
local C in
C={NewCell 0}
fun {Bump}
C:=@C+1
@C
end
fun {Read}
@C
end
end

Здесь происходит нечто особенное: ячейка, на которую ссылается локальная переменная, абсолютно невидима снаружи. Это свойство называется инкапсуляцией (encapsulation). Это означает, что никто не сможет ничего сделать с внутренним устройством счётчика. Мы можем гарантировать что счётчик всегда будет работать корректно вне зависимости от того, как его используют. Этого мы не могли сказать о расширенном FastPascal, поскольку кто угодно мог получить доступ к ячейке и осуществить модификацию ячейки.

Мы можем увеличить счётчик:

{Browse {Bump}}
{Browse {Bump}}

Что будет отображено? Bump можно использовать в любой программе для подсчёта каких-либо событий. Например, FastPascal может использовать Bump:

declare
fun {FastPascal N}
{Browse {Bump}}
{GenericPascal Add N}
end

1.14 Классы

В последнем разделе мы определили один объект-счётчик. Что же нам делать если понадобится больше счётчиков? Было бы неплохо если бы у нас был "завод", производящий столько счётчиков, сколько нам нужно. Такой завод называется класс (class). Один из способов для определения класса:

declare
fun {NewCounter}
C Bump Read in
C={NewCell 0}
fun {Bump}
C:=@C+1
@C
end
fun {Read}
@C
end
counter(bump:Bump read:Read)
end

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

Мы сгруппировали функции Bump и Read вместе в составную структуру данных под названием запись (record). Запись counter(bump:Bump read:Read) характеризуется меткой (label) counter и двумя полями (fields), соответственно названными как bump и read. Создадим два счётчика:

declare
Ctr1={NewCounter}
Ctr2={NewCounter}

Каждый счётчик обладает своей внутренней памятью и своим собственными функциями Bump и Read. Доступ к этим функциям можно получить с помощью оператора "." (точка). Ctr1.bump служит для получения доступа к функции Bump первого счётчика. Увеличим значение первого счётчика и отобразим результат:

{Browse {Ctr1.bump}}

На пути к объектно-ориентированному программированию

Мы дали пример простого класса, NewCounter, определяющего две операции, Bump и Read. Операции, определённые внутри класса, обычно называются методами (methods). Класс можно использовать для создания стольких объектов-счётчиков, сколько может потребоваться. Все эти объекты разделяют одни методы, но каждый из объектов обладает своей собственной отдельной памятью. Программирование с помощью классов и объектов называется объектно-основанным программированием (object-based programming).

Добавление новой идеи, наследования (inheritance), в объектно-основанное программирование даёт объектно-ориентированное программирование (object-oriented programming). Наследование обозначает что новый класс может определяться в терминах существующих классов с указанием только того, чем новый класс будет отличаться от существующих классов. Мы говорим что новый класс был унаследован от существующих классов. Наследование - это мощная концепция для структурирования программ. Она позволяет определять классы последовательно, в разных частях программы. Наследование - это довольно сложная концепция для правильного использования. Для того, чтобы упростить использование наследования, объектно-ориентированные языки добавляют специальный синтаксис для наследования. В главе 7 рассказывается об объектно-ориентированном программировании и программировании с использованием наследования.

1.15 Индетерминизм и время

Мы увидели как по отдельности добавить параллелизм и состояние в программу. Что случится если в программу добавить обе концепции? Оказывается, что одновременное наличие обеих концепций может быть непростым делом, поскольку одна и та же программа может возвращать различные результаты при нескольких запусках. Причина в том, что порядок, по которому нити получают доступ к состоянию может меняться от одного запуска к другому. Эта изменчивость называется индетерминизмом (nondeterminism). Индетерминизм существует по причине недостатка информации о точном времени исполнения каждой базовой операции. Если бы мы знали точное время, то и не существовало бы индетерминизма. Но мы не знаем это время просто потому что нити независимы. Поскольку нити ничего не знают друг о друге, то по этой же причине они ничего не знают об операциях выполненных другими нитями.

Индетерминизм, сам по себе, не является проблемой; мы уже имели дело с индетерминизмом при параллелизме. Трудности появляются тогда, когда индетерминизм проявляется в программе, то есть, если индетерминизм стал наблюдаемым. (Наблюдаемый индетерминизм иногда называется состоянием гонки (race condition).) Пример:

declare
C={NewCell 0}
thread
C:=1
end
thread
C:=2
end

Каким будет содержимое C после выполнения программы? Рисунок 1.4 показывает два возможных варианта выполнения программы. В зависимости от варианта конечное содержимое ячейки может быть либо 1 либо 2. Проблема в том, что мы не можем предсказать развитие событий. Это был простой пример наблюдаемого индетерминизма. Но происходящие события могут быть ещё более запутанными. Например, используем ячейку для хранения счётчика, значение которого могут изменять сразу несколько нитей:

Рисунок 1.4: Все возможные варианты событий для первого примера индетерминизма

declare
C={NewCell 0}
thread I in
I=@C
C:=I+1
end
thread J in
J=@C
C:=J+1
end

Каким будет содержимое C после исполнения программы? Похоже что каждая нить просто добавляет 1 к содержимому ячейки, в результате мы должны получить 2. Но, тут есть сюрприз: конечное содержимое может быть 1! Каким образом это возможно? Прежде чем продолжить чтение объясните причины такого поведения.

Чередование

Содержимое может быть равным 1 по причине чередования (interleaved) выполнения нитей. То есть, нити выполняются понемногу. Мы должны предположить, что в этом случае возможны любые чередования. Например, рассмотрите исполнение программы, продемонстрированное на рисунке 1.5. И I и J привязаны к 0. Затем, поскольку I+1 и J+1 привязаны к 1, ячейке может присваиваться дважды значение 1. Конечным результатом содержимого ячейки будет 1.

Рисунок 1.5: Один из возможных вариантов выполнения второго примера индетерминизма

Это простой пример. В более сложных программах возможны ещё большие варианты чередований. В целом программирование с использованием параллелизма и состояний - это вопрос управления чередованиями. В истории компьютерных технологий самые знаменитые и опасные ошибки были допущены архитекторами программного обеспечения не осознававшими сложность индетерминизма. Печально известным примером может послужить машина радиационной терапии Therac-25. Иногда она облучала пациентов радиационными дозами в тысячи раз превосходящими норму, что в результате приводило к смертям или серьёзному урону здоровью [112].

Это первый урок о программировании с состоянием и параллелизмом: по возможности, никогда не используйте их вместе! Довольно часто оказывается что на самом деле нам не нужно смешивать параллелизм с состоянием. Если же возникнет необходимость использования параллелизма и состояния в программе, то почти всегда можно спроектировать программу так, чтобы они взаимодействовали только в очень малой части программы.

1.16 Атомарность

Подумаем немного о том как программировать с параллелизмом и состоянием. Один из способов облегчающих такое программирование - это использование атомарных операций. Операция называется атомарной (atomic) если в ней не наблюдается никаких промежуточных состояний. То есть непосредственный переход от инициализирующего состояния к результирующему состоянию.

С помощью атомарных операций мы можем решить проблему чередования, затрагивающую ячейку счётчика. Идея заключается в атомарности каждого тела нити. Для этого нам нужен способ построения атомарных операций. Мы введём новую сущность в язык - lock. Lock - это операция блокирования. Блокирование может осуществляться как изнутри, так и снаружи. Программист определяет внутренние инструкции. При блокировании возможна работа только одной нити. Если другая нить попытается получить доступ к блокировке, то ей придётся дождаться окончания работы первой нити. Поэтому всё, что происходит внутри блокировки будет атомарным.

Для блокировки нужно две операции. Первое - для создания новой блокировки мы вызываем функцию NewLock. Второе - мы определяем внутренне содержимое блокировки с помощью инструкции lock L then ... end, где L - это блокировка. Теперь мы можем исправить проблему ячейки счётчика:

declare
C={NewCell 0}
L={NewLock}
thread
lock L then I in
I=@C
C:=I+1
end
end
thread
lock L then J in
J=@C
C:=J+1
end
end

В этой версии конечным результатом всегда будет 2. Тела обеих нитей охраняются одной блокировкой, в противном случае возможно появление нежелательного чередования. Вы видите причину?

1.17 Куда мы пойдём дальше

Эта глава дала поверхностный обзор многих наиболее важных концепций в программировании. Базовые знания, которые вы усвоили в этой главе сослужат вам хорошую службу в следующих главах, когда мы будем более углублённо изучать концепции и модели вычислений соответствующих тем.

1.18 Упражнения

1. В разделе 1.1 мы использовали систему как калькулятор. Изучим её возможности:

(a) Вычислите точное значение 2 100 без использования новых функций. Попытайтесь мыслить сокращениями для того, чтобы не печатать 2*2*2*...*2 с сотней двоек. Подсказка: используйте переменные для хранения промежуточных результатов.

(b) Вычислите точное значение 100! без использования новых функций. Возможно ли в этом случае использование сокращений?

2. В разделе 1.3 определяется функция Comb для вычисления комбинаций. Эта функция не очень эффективна, потому что она может потребовать вычисления очень больших факториалов. Цель этого упражнения - написать более эффективную версию Comb.

(a) В качестве первого шага используем следующее альтернативное определение для создания более эффективной функции:

Вычислите отдельно числитель и знаменатель и затем разделите их. Убедитесь что результат равен 1 при r = 0.

(b) В качестве второго шага, используйте следующее тождество:

для большего повышения эффективности. То есть, если r > n/2, то выполняйте вычисления с помощью n - r вместо r.

3. В разделе 1.6 описываются базовые идеи корректности программ и эти идеи применяются для доказательства корректности функции факториала, определённого в разделе 1.3. Задача этого упражнения: примените эти же идеи к функции Pascal из раздела 1.5 и докажите её корректность.

4. Какой вывод можно сделать о программах с высокоуровневой полиномиальной сложностью исходя из раздела 1.7? Практичны ли они или нет? Что вы об этом думаете?

5. В разделе 1.8 определяется ленивая функция Ints, которая вычисляет ленивую бесконечную последовательность целых чисел. Определим функцию, вычисляющую сумму списка целых чисел:

fun {SumList L}
case L of X|L1 then X+{SumList L1}
else 0 end
end

Что произойдёт если мы вызовем {SumList {Ints 0}}? Хороша ли эта идея?

6. В разделе 1.9 описывается использование высокоуровневого программирования для вычисления различных вариаций треугольника Паскаля. Цель данного упражнения заключается в исследовании этих вариаций.

(a) Вычислите отдельные строки применив вычитание, умножение и другие операции. Почему использование умножения даёт треугольник со всеми нулями? Попробуйте такую разновидность умножения:

fun {Mul1 X Y} (X+1)*(Y+1) end

Как будет выглядеть 10-я строка, вычисленная с помощью Mul1?

(b) Следующая цикличная инструкция будет вычислять и отображать 10 строк:

for I in 1..10 do {Browse {GenericPascal Op I}} end

Используйте эту цикличную инструкцию и упростите получение вариаций.

7. В этом упражнении сравниваются переменные и ячейки. Мы дадим два фрагмента кода. Первый использует переменные:

local X in
X=23
local X in
X=44
end
{Browse X}
end

Второй использует ячейку:

local X in
X={NewCell 23}
X:=44
{Browse @X}
end

В первом идентификатор X относится к двум различным переменным. Во втором X относится к ячейке. Что отобразит Browse в каждом фрагменте? Объясните.

8. Это упражнение исследует вопрос использования ячеек совместно с функциями. Определим функцию {Accumulate N}, аккумулирующую все входные данные, то есть, складывающую вместе все аргументы с которыми она была вызвана. Пример:

{Browse {Accumulate 5}}
{Browse {Accumulate 100}}
{Browse {Accumulate 45}}

Будет отображено 5, 105 и 150, предполагается что в начале аккумулятор содержал ноль. Ниже показан неправильный способ реализации Accumulate:

declare
fun {Accumulate N}
Acc in
Acc={NewCell 0}
Acc:=@Acc+N
@Acc
end

Что не так с этим определением? Как можно исправить эту реализацию?

9. Это упражнение исследует другой способ введения состояния: хранилище памяти (a memory store). Хранилище памяти может быть использовано для создания улучшенной версии FastPascal, запоминающую уже вычисленные строки.

(a) Хранилище памяти аналогично памяти компьютера. Оно имеет серию ячеек памяти, пронумерованных от 1 и до используемого максимума. Существует четыре функции, работающих с хранилищем памяти: NewStore создаёт новое хранилище, Put вставляет новое значение в ячейку памяти, Get получает текущее значение, сохранённое в ячейку памяти и Size возвращает номер последней использованной ячейки. Например:

declare
S={NewStore}
{Put S 2 [22 33]}
{Browse {Get S 2}}
{Browse {Size S}}

[22 33] сохраняется в ячейку памяти 2, отображается [22 33], а затем отображается 2. Загрузите в систему Моцарт хранилище памяти, определённое в файле дополнений, находящемуся на Web сайте книги. Затем используйте интерактивный интерфейс и разберитесь в работе хранилища.

(b) Теперь используйте хранилище памяти для написания улучшенной версии FastPascal, названную как FasterPascal, сохраняющую уже вычисленные строки. Если при следующем вызове произойдёт запрос ранее вычисленных строк, то функция сможете вернуть их без повторного выполнения вычислений. Эта техника называется мемоизацией (memoization - запоминание), поскольку функция осуществляет "запоминание" уже выполненной работы. Это улучшает их производительность. Вот как это работает:

* В начале создаётся хранилище S, доступное для FasterPascal.

* Для вызова {FasterPascal N}, обозначим через M число строк, сохранённых в S, то есть, строки с 1 до M хранятся в S.

* Если N>M, то выполняется вычисление строк с M+1 до N с последующим сохранением в S.

* Возврат N-ой строки, найденной в S.

Если посмотреть извне, то FasterPascal это тот же FastPascal, но быстрее.

(c) Мы дали реализацию хранилища памяти в виде библиотеки. Оказывается хранилище памяти можно определить воспользовавшись ячейкой памяти. Мы опишем то, как может быть сделана такая реализация, а вы сможете написать определение. Ячейка хранит содержимое в виде списка в форме [N1|X1 ... Nn|Xn], где cons Ni|Xi обозначает ячейку памяти Ni, с содержимым Xi. Это означает, что удобно реализованное хранилище памяти не вносит никаких дополнительных телодвижение над ячейками памяти.

(d) В разделе 1.13 определяется счётчик только с одной операцией, Bump. Это обозначает что у нас нет другого способа считать счётчик, кроме как добавить к нему единицу. Поэтому присутствует некоторая неуклюжесть при работе со счётчиком. Практичный счётчик должен иметь по крайней мере две операции, скажем Bump и Read, где Read возвращает текущее значение счётчика без его изменения. Практичный счётчик выглядит примерно так:

declare
local C in
C={NewCell 0}
fun {Bump}
C:=@C+1
@C
end
fun {Read}
@C
end
end

Измените вашу реализацию хранилища памяти таким образом, чтобы она отслеживала изменение размера хранилища с помощью этого счётчика.

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

(a) Попробуйте выполнить этот пример несколько раз. Какие результаты вы получите? Всегда ли результат равнялся 1? Почему это может происходить?

(b) Модифицируйте пример добавив вызовы Delay в каждую нить. Это изменит чередование нитей не затрагивая вычисления, выполняемые нитями. Можете ли вы разработать схему, всегда возвращающую результат равный 1?

(c) В разделе 1.16 дан счётчик, который никогда не возвращает результат равный 1. Что случится если вы попробуете воспользоваться техникой задержек для того, чтобы получить 1 в любом случае?

Переведено на Нотабеноиде
http://notabenoid.org/book/49638/209404

Переводчики: Charlz_Klug