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

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

Charlz_Klug 03.04.14 в 06:21

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

Charlz_Klug 03.04.14 в 06:24

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

Charlz_Klug 03.04.14 в 06:35

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

Charlz_Klug 03.04.14 в 06:38

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

Charlz_Klug 03.04.14 в 06:38

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

Charlz_Klug 03.04.14 в 06:45

oz

Charlz_Klug 03.04.14 в 06:45

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

Charlz_Klug 03.04.14 в 09:39

{Browse 9999*9999}

Charlz_Klug 03.04.14 в 09:40

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

Charlz_Klug 03.04.14 в 09:52

1.2 Переменные

Charlz_Klug 03.04.14 в 11:05

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

Charlz_Klug 04.04.14 в 03:25

declare
V=9999*9999

Charlz_Klug 04.04.14 в 03:25

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

Charlz_Klug 04.04.14 в 03:27

{Browse V*V}

Charlz_Klug 04.04.14 в 04:31

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

Charlz_Klug 04.04.14 в 04:33

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

Charlz_Klug 04.04.14 в 04:42

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

Charlz_Klug 04.04.14 в 05:00

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

Charlz_Klug 04.04.14 в 06:32

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

Charlz_Klug 04.04.14 в 06:39

1.3 Функции

Charlz_Klug 04.04.14 в 10:03

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

Charlz_Klug 04.04.14 в 10:17

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

Charlz_Klug 04.04.14 в 10:17

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

Charlz_Klug 04.04.14 в 10:48

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

Charlz_Klug 07.04.14 в 04:32

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

Charlz_Klug 07.04.14 в 04:36

Рекурсия

Charlz_Klug 07.04.14 в 04:36

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

Charlz_Klug 07.04.14 в 04:39

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

Charlz_Klug 07.04.14 в 04:40

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

Charlz_Klug 07.04.14 в 04:42

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

Charlz_Klug 07.04.14 в 04:56

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

Charlz_Klug 07.04.14 в 04:57

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

Charlz_Klug 07.04.14 в 04:57

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

Charlz_Klug 07.04.14 в 04:59

{Browse {Fact 10}}

Charlz_Klug 07.04.14 в 04:59

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

Charlz_Klug 07.04.14 в 05:12

{Browse {Fact 100}}

Charlz_Klug 07.04.14 в 05:12

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

Charlz_Klug 07.04.14 в 05:13

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

Charlz_Klug 07.04.14 в 05:13

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

Charlz_Klug 09.04.14 в 10:59

Комбинации

Charlz_Klug 09.04.14 в 10:59

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

Charlz_Klug 09.04.14 в 11:04

n
r

=
n!
r !( n − r )!

Charlz_Klug 09.04.14 в 11:04

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

Charlz_Klug 09.04.14 в 11:05

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

Charlz_Klug 09.04.14 в 11:05

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

Charlz_Klug 09.04.14 в 11:07

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

Charlz_Klug 09.04.14 в 11:08

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

Charlz_Klug 09.04.14 в 11:12

1.4 Списки

Charlz_Klug 09.04.14 в 11:13

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

Charlz_Klug 09.04.14 в 11:16