Глава 37. «Жизнь» Джона Конвея

Идеи реализации
	Глава 37. «Жизнь» Джона Конвея

escape-последовательность	назначение
`"\e[2J"`	очистка экрана
`"\e[ $p$ m"` или `"\e[ $p$ ; $q$ m"`	переключение цвета
`"\e[?25l"` и `"\e[?25h"`	выключить/включить курсор
`"\e[ $y$ ; $x$ H"`	позиционировать курсор (в т. ч. невидимый) в положение $(x - 1, y - 1)$

	Примечание
Не следует искать логику в этих управляющих последовательностях, не нужно запоминать, но надо записать. Мало логики также и в кодах цветов, можно поэкспериментировать; в нашей программе `"\e[1;33m"` — цвет живых, `"\e[0;34m"` — мёртвых. Вернуться к нормальному цвету — `"\e[m"`.

Не следует искать логику в этих управляющих последовательностях, не нужно запоминать, но надо записать. Мало логики также и в кодах цветов, можно поэкспериментировать; в нашей программе "\e[1;33m" — цвет живых, "\e[0;34m" — мёртвых. Вернуться к нормальному цвету — "\e[m".

Примечание

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

команда вывода с escape-последовательностями	алгоритмический язык
`print "Hello, \e[1;33mworld\e[m!";`	Perl
`printf("Hello, \x1B[1;33mworld\x1B[m!");`	C
`std::cout<<"Hello, \x1B[1;33mworld\x1B[m!";`	C++
`System.out.print("Hello, \x1B[1;33mworld\x1B[m!");`	Java
`write('Hello, '+#27+'[1;33mworld'+#27+'[m!');`	Pascal
`WRITE (,) 'Hello, \x1B[1;33mworld\x1B[m!'C`	Fortran
`(Hello, \x1B[1;33mworld\x1B[m!) print`	PostScript
`(display "Hello, \x1B[1;33mworld\x1B[m!")`	Scheme

Как видно, отличия связаны с представлением символа «Escape» в строковых выражениях. В других языках из-за отсутствия литерала "\e" используется литерал "\x1B" (1B — шестнадцатеричный код символа «Escape»). Этот способ, между прочим, будет работать и в Perl.

Расстановка клеток на первом кадре

Поскольку эволюция на клетчатом поле вполне определяется начальной расстановкой клеток, интересно было бы сделать так, чтобы видео по возможности не повторялось при повторных запусках программы. Возможное решение — расставить клетки на начальном поле случайно, примерно поровну живых и мёртвых клеток. Требуется источник, из которого можно вытягивать жребии — «жив/мёртв», $1$ / $0$ , примерно с одинаковой вероятностью.

В нашем распоряжении имеется встроенная процедура rand. rand(x) возвращает случайное число $r \in [0; x)$ , равномерно распределённое на этом промежутке. Равномерная распределённость на множестве $M$ — это вот что: для любого интервала $I \subset M$ обозначим $r_{I}$ количество чисел $r$ , попавших в этот интервал, обозначим $r_{M}$ общее количество чисел $r$ . Если $\frac{r_{I}}{r_{M}}$ неограниченно приближается к $\frac{|I|}{|M|}$ с ростом $r_{M}$ , то это и есть равномерная распределённость. Всем этим словам в математике придаётся точный смысл, мы же обойдёмся и этими словами.

Поскольку нам нужны только числа $0$ / $1$ , можно извлекать случайные числа из промежутка $[0; 2)$ и брать их целую часть: int rand 2.

Достойное завершение программы

Условие завершения программы

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

Для ответа на этот вопрос нужно вспомнить известную теорему — принцип Дирихле (о зайцах), которая гласит: если разместить $m$ зайцев в $n$ клетках ( $m > n$ ), то хотя бы в одной клетке окажется более одного зайца.

В нашем случае в качестве заячьих клеток выступят возможные состояния клетчатого поля, а в роли зайцев Дирихле — сменяющие друг друга кадры. На каждом кадре запечатлено одно из возможных состояний поля. Поскольку количество различных состояний у клетчатого поля размером $w h$ равно $2^{w h}$ , рано или поздно очередной кадр повторит ту же сцену, которая была на одном из предыдущих кадров. Так что зацикливание непременно произойдёт. Но не придётся ли нам слишком долго ждать зацикливания?

Если предположить самый худший сценарий, кадры не будут повторяться, пока не изобразят каждое из $2^{w h}$ возможных состояний. Если, к примеру, $w = 80$ , $h = 25$ , количество состояний будет равно $2^{2000}$ . Если кадры будут сменяться 24 раза в секунду (это обычное значение для телевидения), то придётся подождать $2^{1970,5} \approx 10^{600}$ лет. Единица и шестьсот нулей! Лет!

Когда зацикливание состоится, продолжительность цикла может быть такой же большой. Так что дожидаться зацикливания — затея безнадёжная.

Не исключено, что из-за особенности правил, описывающих «Жизнь», такие длинные циклы невозможны. Однако, как нам представляется, этот вопрос не исследован. Эксперименты с программой показывают, что зацикливание наступает довольно скоро, а длина цикла невелика (при разумных значениях $w$ и $h$ ).

Сигналы

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

В операционной системе имеется ещё одно средство межпрограммного обмена информацией: сигналы. Возможности примитивные, но сигналы чрезвычайно важны. В Linux бывает 32 вида сигналов. У каждого кроме номера имеется символическое название. Любой процесс может послать другому процессу сигнал любого вида, если обладает соответствующим правом (в данный момент мы уклонимся от разговора о правах). Каждый процесс, получив сигнал, обрабатывает его. Обработка заключается в том, что срабатывает процедура, соответствующая типу полученного сигнала. Эти процедуры обычно определяются не в программе, а в среде, в которой программа работает (программа работает не в вакууме). Это процедуры-обработчики сигналов по умолчанию. Однако программист может перепрограммировать некоторые из процедур-обработчиков сигналов.

Некоторые из сигналов в процесс посылает ядро операционной системы. Например, сигнал № 11 (SIGSEGV — SEGment Violation — насилие над памятью) посылается в том случае, если процесс пытается обратиться к ячейке памяти, ему не принадлежащей. Сигналы некоторых других видов посылает в процесс терминал, в котором исполняется этот процесс. Если в терминале пользователь нажимает комбинацию клавиш Ctrl+C, терминал шлёт в исполняющийся процесс сигнал № 2 (SIGINT — INTerrupt — прерывание). В обоих случаях обработчики сигнала по умолчанию немедленно завершают программу; в первом случае из-за серьёзности ошибки, во втором — поскольку этот сигнал и предназначен для немедленного завершения процесса.

Сигналы №№ 9 (SIGKILL — KILL — убить), 15 (SIGTERM — завершить) по умолчанию завершают программу. Зачем их две штуки? При «культурном» выключении компьютера необходимо завершить все работающие процессы. При нажатии кнопки «Завершение работы» запускается программа, которая, в частности, рассылает всем процессам сначала SIGKILL, затем — SIGTERM. Если в какой-то программе программист переопределил процедуру-обработчик сигнала SIGKILL, процесс может не завершиться, но тогда есть надежда, что SIGTERM добьёт этот процесс. Если уж и это не поможет, то, возможно, поможет выключение питания.

Хотелось бы не просто завершить программу при нажатии Ctrl+C. В случае такого экстренного завершения текущий кадр, скорее всего, будет выведен частично, курсор останется в случайном месте на экране, и, кроме того, останется в выключенном состоянии. Следует, получив сигнал завершения, выполнить кое-какие действия: очистить экран, зажечь курсор, переключиться на обычный цвет и вывести тёплые слова благодарности. Важно не забыть при этом вызвать процедуру exit, которая завершит выполнение программы.

Для этого переопределим процедуру-обработчик SIGINT. Как? Встроенный ассоциативный массив %SIG содержит пары ключ — значение. Ключи в этом ассоциативном массиве — названия сигналов без префикса SIG (например, INT), значения — ссылки на процедуры-обработчики соответствующего сигнала. Определим свою процедуру-обработчик и разместим в %SIG ссылку на неё как значение, отвечающее ключу 'INT': $SIG{'INT'}=….

Как создать ссылку на процедуру? Встроенная и знакомая нам команда sub { … } возвращает ссылку на процедуру с телом { … }: $SIG{'INT'}=sub { … }. Обычно возвращаемая ссылка не используется, поскольку определённая при помощи sub процедура будет доступна по имени. Но в нашем случае нужно записать процедуру в ассоциативный массив в качестве значения, отвечающего определённому ключу. Требуется скалярное значение, с помощью которого было бы возможно вызвать процедуру. Единственный способ разместить в скаляре указание на процедуру — создать ссылку. Имя процедуры сразу после sub можно не указывать. Нам ранее не приходилось использовать sub в правой части присваивания, так как мы вызывали процедуры по их именам, а не по ссылкам. Тело процедуры довольно простое:

Perl
print "\e[?25h\e[1;1H\e[0m\e[2JThank you!\n";
exit;

(зажигаем курсор, устанавливаем в позицию $(1, 1)$ , восстанавливаем нормальный цвет, очищаем экран, всем спасибо…). Итак, где-то в начале исполнения программы нужен код

Perl
$SIG{'INT'}=sub
{
	print "\e[?25h\e[1;1H\e[0m\e[2JThank you!\n";
	exit;
};

Хранение состояния клетчатого поля

Нам понадобится две однотипные структуры, которые будут хранить информацию о состоянии текущего и последующего кадра. Зачем две? Затем, чтобы, располагая расстановкой клеток в текущем кадре (в первой структуре), подготовить следующий кадр (во второй структуре). Что это будут за структуры? Состояние кадра может быть представлено как прямоугольная таблица логических значений размером $h \times w$ .

Можно, конечно, смоделировать прямоугольную таблицу с помощью обычного длинного массива, в котором за элементами одной строки следуют элементы следующей. Нужно лишь указать размеры прямоугольника. Простые арифметические преобразования позволят пересчитать двумерные координаты $(x, y)$ в одномерную $k$ — индекс в длинном массиве, и наоборот: $k = w y + x$ , $y = k div w$ , $x = k mod w$ ( $y$ и $x$ — частное и остаток от деления $k$ на $w$ ). Таким образом, если длинный массив хранить в переменной @frame, то состояние клетки, находящейся в $y-й строке и в $x-м столбце, можно получить, вычислив выражение $frame[$w*$y+$x].

Но зачем мудрить с обычным массивом, когда Perl предоставляет нам двумерный, идеально подходящий для наших целей? Двумерные массивы в Perl, напомним, реализуются как массивы ссылок на массивы. В нашем случае «внешний» массив содержит строки — ссылки на «внутренние» массивы. Если назвать такой массив @frame, то состояние клетки в $y-й строке и в $x-м столбце даётся выражением $frame[$y][$x].

Идеи реализации

Порядок перебора клеток

Края клетчатого поля

Определение размера экрана

Управление терминалом

Расстановка клеток на первом кадре

Достойное завершение программы

Условие завершения программы

Сигналы

Хранение состояния клетчатого поля


Глава 37. «Жизнь» Джона Конвея		Разработка