ФВП спешат на помощь

Эта статья о том, как элементы функционального программирования помогают в реальной жизни. Таких статей на Хабре много, но, насколько я помню, про Forth, на эту тему, ещё никто не писал. Кроме того, я не собираюсь разводить по этому поводу теорию (теоретик из меня ещё тот). Я расскажу о сугубо практической задаче, с которой столкнулся буквально вчера. Надеюсь, мой рассказ будет интересен.
 

Строго говоря, речь пойдёт не о Forth-е, а о его специализированном диалекте ForthScript, разработанном Грегом Шмидтом, в рамках его проекта Axiom Development Kit, для описания настольных игр. Я уже довольно давно пользуюсь этим продуктом и успел разработать несколько игр с его помощью. В настоящее время, я работаю над очень интересной, на мой взгляд, игрой, чем-то напоминающей Го. Я уже упоминал о ней в предыдущей статье. Выглядеть она будет приблизительно так:

Отображение имён полей включено специально. Дело в том, что платформа Zillions of Games, на которой ведётся разработка, не позволяет размещать фигуры «с наложением» друг на друга. Каждая «фигура» здесь составлена из 4 частей — тайлов. Понимание этого факта крайне важно для последующего изложения. Доска становится в 4 раза больше, а код сложнее (ZSG-нотация становится совершенно нечитаемой), но результат определённо того стоит.

Как легко догадаться, доска в этой игре трёхмерная. Для варианта игры 7x7 проще всего хранить состояние 14x14x7 = 1372 позиций. В ZRF с этим не возникает проблем (этот язык позволяет определять многомерные доски), но, к сожалению, у меня возникла проблема с самим ZRF. Алгоритмы удаления фигур, при выполнении хода в Margo, слишком сложны для этого языка. Кроме того, AI ZoG наверняка не справится с этой игрой. Используя Axiom я стараюсь убить сразу двух этих зайцев. Увы, Axiom приносит с собой новые проблемы. В частности, этот продукт не позволяет определять трёхмерные доски:

Наивное определение доски в Axiom

7		 CONSTANT	DIM
DIM 2 *		 CONSTANT	COLS
COLS DIM * 	 CONSTANT	ROWS

{board
	ROWS COLS	{grid}
board}

Легко заметить, что здесь определяется двумерная доска. Слои третьего измерения просто «выкладываются» друг за другом по координате Y. На самом деле, Axiom определяет одномерный массив, руководствуясь следующей схемой:

Поля доски нумеруются сверху-вниз слева-направо. Кроме того, автоматически создаются константы, используемые для именования полей, по аналогии с шахматной доской. Для доски 8x7, показанной выше, нет никакой разницы будет ли использоваться в коде имя позиции a2 или соответствующее её числовое значение (часто это бывает удобно). Допускается определение каждой позиции вручную, без использования grid, но я боюсь себе даже представить объём такого описания для доски 14x14x7 и, что самое главное, время его загрузки.

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

Определение направлений

COLS         CONSTANT	DDIR
DDIR NEGATE  CONSTANT	UDIR

{directions
	-1	  0	{direction} n
	 1	  0	{direction} s
	 0	  1	{direction} e
	 0	 -1	{direction} w
	-1	 -1	{direction} nw
	 1	 -1	{direction} sw
	-1	  1	{direction} ne
	 1	  1	{direction} se
	 DDIR 0	{direction} down
	 UDIR 0	{direction} up
directions}

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

: move-to-north ( -- )
	n verify		( Переместиться на север, если такая связь существует )
	empty? verify	( Целевое поле пусто )
	from here move	( Переместить фигуру )
	add-move		( Завершить формирование хода )
;

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

Передача функции через стек

: move-to ( 'dir -- )
    EXECUTE verify	( Выполнить полученную функцию и прерваться, если выполнение не успешно )
    empty? verify	( Целевое поле пусто )
    from here move	( Переместить фигуру )
    add-move		( Завершить формирование хода )
;

: move-to-n ( -- ) ['] n move-to ;
: move-to-s ( -- ) ['] s move-to ;
: move-to-w ( -- ) ['] w move-to ;
: move-to-e ( -- ) ['] e move-to ;

Это очень распространённая идиома Axiom и редкая программа без неё обходится (разумеется толку от всей этой эквилибристики тем больше чем сложнее обобщённая функция). Но вернёмся к Margo. Описанная мной выше реализация доски работает вплоть до размера 8x8 (16x16x8 = 2048 позиций), но уже для доски 9x9 (18x18x9 = 2916 позиций) работать перестаёт. Видимо это значение больше максимально допустимого размера доски (упоминания об этом ограничении в документации по Axiom я не нашёл). Разумеется, я не мог с этим смириться. Только не после того, как я долго и упорно рисовал хоси для этой доски (на самом деле, четыре сан-сана и один тэнген, но именно они и требуются для доски такого размера).

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

Оптимизированное определение доски

9		 CONSTANT	DIM
DIM 2 *		 CONSTANT	COLS
90 	 	 CONSTANT	ROWS
COLS 1- 	 CONSTANT	DDIR
DDIR NEGATE	 CONSTANT	UDIR

{board
	ROWS COLS	{grid}
board}

Для доски 9x9 потребуется хранить всего 18x90 = 1710 позиций. Такой объём Axiom вполне по силам. Обратите внимание на изменение константы DDIR, используемой для определения направления «вглубь» доски (забыл сказать, что доску мы будем хранить в перевёрнутом виде). К сожалению, это не единственное необходимое изменение. Что произойдёт если попытаться перейти вниз из любой позиции нулевой строки? Поскольку DDIR стала меньше на единичку, мы попадём на последнюю строку того же слоя! Это может сломать всю логику игры.

Также, может получиться нехорошо если пойти с последней строки слоя на юг или с первой на север (за исключением нулевой строки первого слоя). Можно было бы запретить все лишние связи вручную, но мне не очень-то нравится много работать руками. Попробуем решить задачку по-умному. Для начала, научимся определять текущие координаты. Это совсем просто:

: get-x ( pos -- x )
	COLS MOD
;

: get-y ( pos -- y )
	COLS /
;

Определить граничную строку слоя немного сложнее:

: is-edge? ( -- ? )
	COLS here get-y
	BEGIN
		2DUP <= IF
			OVER -
			SWAP 2 - SWAP
			FALSE
		ELSE
			TRUE
		ENDIF
	UNTIL
	SWAP 1- OVER = SWAP 0= OR
;

Суть этой стековой акробатики проста. Из номера текущей строки мы вычитаем (до тех пока есть из чего вычитать) ширину слоя, начиная с COLS и уменьшая это значение на 2 в каждой итерации цикла. Если в результате значение обнулилось или стало на единичку меньше текущей ширины слоя — строка граничная. Теперь, можно легко запретить все перемещения из этих строк (для интересующих нас направлений):

{directions
	-1	  0	{direction} n-internal
	 1	  0	{direction} s-internal
	 0	  1	{direction} e
	 0	 -1	{direction} w
	-1	 -1	{direction} nw
	 1	 -1	{direction} sw
	-1	  1	{direction} ne
	 1	  1	{direction} se
	 DDIR 0	{direction} d-internal
	 UDIR 0	{direction} u
directions}

: common-dir ( 'dir -- ? )
	is-edge? IF		( Это край? )
		DROP FALSE	( Функция отбрасывается и возвращается результат не успешного выполнения )
	ELSE
		EXECUTE		( Выполняем функцию перехода и возвращаем результат её выполнения )
	ENDIF
;

: n ( -- ) ['] n-internal common-dir ;
: s ( -- ) ['] s-internal common-dir ;
: d ( -- ) ['] d-internal common-dir ;

Функции высшего порядка снова с нами! К сожалению, этот код содержит серьёзную ошибку. Дело в том, что только для направления вниз необходимо запрещать движение из любой граничной строки. Северное направление следует запрещать лишь в верхних граничных строках, а южное — в нижних. Предикат is-edge? должен вычисляться по-разному, в зависимости от выбранного направления! Перед нами вновь предстаёт зловещая тень «копипаста». К счастью, никто не запрещает передавать указатели и на функции от нескольких аргументов. Вот корректная реализация:

Окончательное решение вопроса

: is-edge? ( 'op -- ? )
	COLS here get-y
	BEGIN
		2DUP <= IF
			OVER -
			SWAP 2 - SWAP
			FALSE
		ELSE
			TRUE
		ENDIF
	UNTIL
	SWAP 1- OVER = SWAP 0= ROT EXECUTE
;

: my-first ( a b -- b )
	SWAP DROP
;

: n ( -- ) ['] n-internal ['] my-first common-dir ;
: s ( -- ) ['] s-internal ['] DROP     common-dir ;
: d ( -- ) ['] d-internal ['] OR       common-dir ;

Держите свои глаза и ум открытыми. Для того чтобы столкнуться с функциональным программированием не обязательно заниматься академической деятельностью. Функции высшего порядка могут оказаться ближе чем вы думаете.