ФВП поспішають на допомогу

Ця стаття про те, як елементи функціонального програмування допомагають у реальному житті. Таких статей на Хабре багато, але, наскільки я пам'ятаю, про 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 ['] common OR-dir ;


Тримайте свої очі і розум відкритими. Для того щоб зіткнутися з функціональним програмуванням не обов'язково займатися академічною діяльністю. Функції вищого порядку можуть виявитися ближче ніж ви думаєте.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.