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

Решение о судьбе клетки в следующем кадре принимается на основании количества живых соседей в текущем кадре; исполнение приговора откладывается до смены кадров. Иначе — несправедливость, результат будет зависеть от порядка перебора клеток.

Ещё один источник несправедливости — крайние или угловые клетки (по понятным причинам). Он устраняется [обсудить] сворачиванием поля в тор (рисунок 37.3. «Тор»).


Как вычислять координаты клеток, соседних с x y ? [обсудить] Для некрайних и неугловых — x ± i y ± j , где i , j 0 1 , причём i и j не равны нулю одновременно. Для остальных — то же, но по модулю w и h. Можно (и нужно) брать по модулю и в общем случае — хуже не будет, зато единообразие.

Как найти a mod b , то есть остаток числа a при делении на b? Заметим, что, во-первых, a mod b = a + n b mod b для всех n , а во-вторых, что 0 a mod b < b . Это означает, что, прибавляя к a значение b (или вычитая из a значение b), мы, не изменяя остатка от деления, попадём в промежуток 0 b . Полученное число будет обладать обоими свойствами остатка от деления, и, следовательно, будет искомым остатком.

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

sub modulo
{
	my ($a, $b)=@_;
	$a+=$b while $a<0;
	$a-=$b while $a>=$b;
	return $a;
}

Однако в такой процедуре нет необходимости, поскольку в Perl имеется встроенный оператор %, который в точности берёт одно число по модулю другого, и делает эту работу быстрее.

Изображение (кадр) должно разворачиваться на весь экран терминала/текстовую консоль. Как определить размер? Консоль/терминал «знают» свой размер и могут сообщить его программам. Как? Через переменные окружения (environment variables). Переменные — набор пар ключ-значение. Ключ — имя переменной, значение. Каждая программа может установить/изменить переменные, может сделать их видимыми запускаемым из неё другим программам. Не путать переменные в программе (для Perl — скаляры и всякие массивы) и environment: первые живут в самой программе, вторые — в ОС. По этой причине именно вторые служат одним из средств межпрограммного обмена информацией. Размеры экрана сидят в переменных окружения LINES и COLUMNS. Для консоли эти переменные устанавливает программа login, для эмулятора терминала — сама программа-терминал (в нашем случае xterm).

Увидеть весь список переменных окружения можно с помощью программы printenv:

Этот командный конвейер выводит имена и значения переменных окружения, по одной переменной на строке (команда printenv); полученный список упорядочивается по алфавиту (команда sort); упорядоченный список направляется в программу-броузер less, которая позволяет просмотреть длинный текст на экране, перемещаясь по нему при помощи клавиш-стрелок. Список в приведённом листинге сокращён. Обратите внимание на переменные LINES и COLUMNS в этом листинге.

Чтобы установить или изменить переменную, используется команда export:

Попробуйте это сделать и убедитесь, что переменная ABC попала в список.

Как получить доступ к переменным окружения из программы на Perl? Для хранения списка пар ключ-значение в Perl наиболее подходят ассоциативные массивы. Изнутри программы окружение видно как особая встроенная переменная — ассоциативный массив %ENV. Угадайте, откуда название?

«Жизнь» — наша первая графическая программа. Современные операционные системы предлагают нам богатые графические возможности, в основе которых лежат оконные системы. Однако программирование оконных графических программ — пока ещё сложная для нас задача. Поэтому мы постараемся обойтись простыми средствами, благо у нашей программы весьма скромные потребности.

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

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

Имеются исключения к вышеописанным правилам. Вывод символа конца строки ("\n") перемещает курсор в начало следующей строки, прокручивая строки, если это необходимо. Вывод знака табуляции приводит к смещению курсора вправо в ближайшую справа позицию табуляции, как будто выводится один или несколько пробелов. Позиции табуляции располагаются в первой, девятой, семнадцатой колонках и так далее — на расстоянии восьми колонок по горизонтали. Наконец, вывод символа «гудок» ("\a") вызывает пренеприятнейший гудок (если, конечно, компьютер оборудован специальным динамиком — писиспикером). Курсор при этом не сдвигается, на экране ничего не появляется. Других возможностей для управления терминалом мы пока не знаем. А они нам понадобятся.

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

Оказывается, все эти вещи можно выполнить всё теми же средствами файлового вывода (что согласуется с файловой семантикой терминала — представлением о терминале как о файле).

Особое управление терминалом осуществляется путём вывода особых последовательностей символов — так называемых escape-последовательностей. Они так называются, потому что начинаются с символа Escape. Он не имеет общепринятого изображения и служит как раз для специальных целей. В ""-строках в Perl его можно задать литералом "\e" (так же, как "\n" задаёт символ конца строки). Каждый тип терминала может иметь свой набор управляющих escape-последовательностей, однако наиболее популярные — одни и те же, они описаны в стандарте ANSI (American National Standards Institute). В их числе:

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

[Примечание]Примечание

Не следует искать логику в этих управляющих последовательностях, не нужно запоминать, но надо записать. Мало логики также и в кодах цветов, можно поэкспериментировать; в нашей программе "\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!'CFortran
(Hello, \x1B[1;33mworld\x1B[m!) printPostScript
(display "Hello, \x1B[1;33mworld\x1B[m!")Scheme

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

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

В нашем распоряжении имеется встроенная процедура rand. rand(x) возвращает случайное число r 0 x , равномерно распределённое на этом промежутке. Равномерная распределённость на множестве M — это вот что: для любого интервала I M обозначим r I количество чисел r, попавших в этот интервал, обозначим r M общее количество чисел r. Если r I r M неограниченно приближается к 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 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 в правой части присваивания, так как мы вызывали процедуры по их именам, а не по ссылкам. Тело процедуры довольно простое:

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

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

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

Нам понадобится две однотипные структуры, которые будут хранить информацию о состоянии текущего и последующего кадра. Зачем две? Затем, чтобы, располагая расстановкой клеток в текущем кадре (в первой структуре), подготовить следующий кадр (во второй структуре). Что это будут за структуры? Состояние кадра может быть представлено как прямоугольная таблица логических значений размером h × 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].

Информатика-54© А. Н. Швец