2009 → Выпуск 1

Давно не брал я в руки шашек

Дмитрий Астапов

Аннотация: Функциональные языки обладают рядом полезных свойств, позволяющих ускорить прототипирование и разработку программ. В частности, функциональные языки существенно облегчают разработку программ методом «сверху вниз», позволяя программисту сосредоточиться на высокоуровневом проектировании системы до того, как он углубится в детали реализации.
Данная статья на практическом примере демонстрирует процесс проектирования и разработки «сверху вниз» программ на языке Haskell. Она рассчитана на программистов, которые уже начали знакомство с функциональным программированием и языком Haskell, но испытывают нехватку практических примеров того, как проектируются и разрабатываются программы на Haskell и функциональных языках.

1 Введение

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

В то же время, существует целый ряд причин, по которым подход к разработке в противоположном направлении — «сверху вниз» — может оказаться предпочтительнее:

Контекст всегда понятен.: Проектирование высокоуровневой структуры системы дает контекст для проектирования более мелких компонентов — будь то подсистемы, классы или функции — повышая вероятность того, что они будут правильно абстрагированы, а интерфейсы между ними будут качественно построены. При проектировании «снизу вверх», напротив, легко потерять общий контекст и упустить из виду какой-то аспект решаемой задачи.
Идентификация рисков.: Построение системы «от общего к частному» дает дополнительные возможности по идентификации рисков. После того, как основные подсистемы и компоненты реализованы (пусть даже в виде «пустышек»), появляется возможность оценить сложность их реализации и заранее предотвратить возможные риски, например, изменив дизайн системы.
Управление временем.: Когда основные модули системы уже написаны (или спроектированы), у разработчика появляется возможность примерно оценить сложность и время, требуемое на разработку того или иного компонента. В дальнейшем разработчик, скорее всего, будет стремиться рационально распределять свои усилия и не тратить слишком много времени на углубление в какой-то один аспект системы. В то же время, при разработке «снизу вверх» велик риск потратить слишком много времени на «вылизывание» одного мелкого участка в ущерб общему качеству продукта.

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

Впрочем, лучше один раз увидеть, чем сто раз услышать. Данная статья покажет на практическом примере, как выполняется дизайн и пишется «сверху вниз» программный код на функциональном языке программирования Haskell.

Предполагается, что читатель уже ознакомился с синтаксисом языка Haskell при помощи книг (например, [10] и [12]) или учебников (например, [9], [8] или [4]). Характерные приемы написания кода, использованные в примерах, будут указываться в сносках, начинающихся со слова Haskell. Предполагается, что читатель сам сможет углубленно ознакомиться с указанными темами, используя свободно доступные в сети ресурсы.

2 Постановка задачи и функция main

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

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

Соответствующий код на Haskell выглядит так²:

main = do (newBoard, playerA, playerB) <- getConfig play newBoard playerA playerB

Поскольку устройство функций getConfig и play пока еще не рассматривается, их определение временно будет состоять из вызова функции undefined:

getConfig = undefined play = undefined

Вызов функции undefined приводит к генерации ошибки во время исполнения программы и выводу сообщения «Prelude: undefined». Однако у этой функции есть одно примечательное свойство, позволяющее использовать ее в качестве универсального маркера «TODO» при написании кода: компилятор считает, что тип результата этой функции — это самый общий, самый глобальный тип, который только может быть. Все остальные типы, с точки зрения компилятора, являются подтипами этого общего типа. Некоторой аналогией подобной концепции может служить тип Object в языке Java или void * в языке C³.

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

Безусловно, в программах на Java/C/C++ тоже можно описывать методы или функции с пустым телом для достижения подобной цели. Однако при этом программисту необходимо будет сразу указать полную сигнатуру метода или функции: количество и тип аргументов, тип возвращаемого результата. Если же в ходе проектирования высокоуровневые функции или методы будут изменены, программисту с большой вероятностью потребуется изменить сигнатуры многих пустых методов, прежде чем код сможет снова быть скомпилирован. Charles Petzold⁴ считает [11], что подобные особенности императивных языков, вкупе с технологиями интеллектуального дополнения кода (Intellisense), опирающимися на информацию о типах объявленных функций и методов, приводят к практической невозможности заниматься разработкой «сверху вниз», вынуждая программиста работать «снизу вверх».

Чтобы убедиться, что написанный код на Haskell действительно компилируется, его можно сохранить в файл (допустим, «checkers01.hs») и загрузить в интерпретатор Haskell⁵:

% ghci checkers01.hs
GHCi, version 6.10.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( checkers01.hs, interpreted )
Ok, modules loaded: Main.

3 Формализация правил игры

Поскольку способ настройки программы и конкретный вид настроек сильно зависят от деталей реализации игры, разумно временно забыть про функцию getConfig и сосредоточить внимание на функции play, отвечающей за проведение одной игровой партии.

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

Данное описание фактически дословно переводится в код на Haskell:

play newBoard playerA playerB = do displayBoard newBoard makeMove newBoard White where makeMove board side = do nextBoard <- undefined displayBoard nextBoard if isVictory side nextBoard then return ("Winner is " ++ show side) else makeMove nextBoard (otherSide side) isVictory = undefined data Side = White | Black deriving Show otherSide White = Black otherSide Black = White displayBoard = undefined

Функция makeMove производит обновление состояния доски без использования переменных — новое состояние передается в рекурсивный вызов функции makeMove.

Объявление deriving Show просит компилятор автоматически реализовать для указанного типа данных функцию show, используемую при объявлении победителя.

Так как функция displayBoard производит вывод на экран, для записи функции makeMove также используется do-нотация.

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

Новое расширенное определение функции play включает в себя две «заглушки»: функцию isVictory, используемую для определения конца партии, и код генерации нового состояния доски newBoard на основании хода игрока. Поскольку правила игры в шашки жестко регламентируют приоритет и очередность всех действий игрока в течении хода, их можно (и нужно) запрограммировать.

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

Если по окончании хода шашка игрока оказалась на самом дальнем от него ряду игрового поля, она превращается в «дамку»⁷ и получает возможность ходить (и бить) на произвольное количество полей по диагонали как вперед, так и назад. Расширенное определение локальной функции makeMove, реализующей эти правила, выглядит так:

makeMove board side = do afterMove <- if canAttack board side then undefined -- do attack else undefined -- do move let nextBoard = upgradeToKings afterMove displayBoard nextBoard if isVictory side nextBoard then ... upgradeToKings = undefined canAttack = undefined

Выбор фигуры, которая будет ходить или выполнять взятие, должен выполняться функцией playerA (или playerB, в зависимости от того, чей ход). В качестве результата эти функции должны возвращать обновленное состояние доски после завершения хода.

Очевидно, что для принятия правильного решения эти функции должны получить, как минимум, информацию о:

текущем состоянии доски (фигур);
цвете фигур, которыми играет игрок;
том, какого рода ход надо сделать — простой или со взятием.

Для кодирования типа хода будет введен тип данных MoveType:

data MoveType = Move | Attack

Теперь пробелы в определении функции makeMove могут быть заполнены таким образом:

makeMove board side = do let player = getPlayer side afterMove <- if canAttack board side then attackLoop player board side else player Move board side ... getPlayer = undefined

Этот пример хорошо иллюстрирует отсутствие какого-либо особого статуса у функций по сравнению со всеми прочими типами данных. Видно, что player — это результат работы функции getPlayer. При этом player используется в выражении player Move board side. То есть, player — это функция; как функция, она может быть возвращена в качестве результата работы других функций. В то же время, player передается в качестве аргумента в функцию attackLoop.

Функция getPlayer, выбирающая правильную функцию-реализацию поведения игрока в зависимости от того, чей сейчас ход, выглядит при этом так⁸:

getPlayer White = playerA getPlayer Black = playerB

Осталось описать вспомогательную функцию attackLoop, реализующую взятие фигур до тех пор, пока это возможно:

attackLoop player board side = do board' <- player Attack board side if canAttack board' side then attackLoop player board' side else return board'

Полная версия кода, получившегося в результате, приведена на рисунке 1. Она также находится в файле «checkers02.hs», расположенном в архиве с примерами кода.

module Main where main = do (newBoard, playerA, playerB) <- getConfig play newBoard playerA playerB play newBoard playerA playerB = do let board = newBoard displayBoard board makeMove board White where makeMove board side = do let player = getPlayer side afterMove <- if canAttack board side then attackLoop player board side else player Move board side let nextBoard = upgradeToKings afterMove side displayBoard nextBoard if isVictory side nextBoard then return ("Winner is " ++ show side) else makeMove nextBoard (otherSide side) attackLoop player board side = do board' <- player Attack board side if canAttack board' side then attackLoop player board' side else return board' getPlayer White = playerA getPlayer Black = playerB isVictory = undefined canAttack = undefined data Side = White | Black deriving Show otherSide White = Black otherSide Black = White data MoveType = Move | Attack getConfig = undefined displayBoard = undefined upgradeToKings = undefined
Рис. 1: Листинг checkers02.hs

4 Компьютерный игрок с примитивной стратегией

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

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

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

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

Код, реализующий выбор хода компьютерным игроком, может быть записан с использованием функции availableMoves так⁹:

randomComputer Move board side = case availableMoves board side of [] -> return board variants -> do v <- getRandom variants return $ move board side v

Тут функция move — это (еще не реализованная) функция из API работы с доской, выполняющая манипуляции по перемещению фигуры в результате хода.

По аналогии, функция выбора атакующего кода будет записана так:

randomComputer Attack board side = do v <- getRandom (availableAttacks board side) return $ attack board side v

Компьютерный игрок будет выполнять выбор атакующего кода только в том случае, если функция play проверила потенциальную возможность выполнения взятия этим игроком. Соответственно, нет необходимости проверять, вернула ли функция availableAttacks хотя бы один вариант хода — его наличие гарантируется. С другой стороны, функция availableMoves вполне может возвратить пустое множество доступных ходов — в этом случае компьютерный игрок пропускает ход (возвращает состояние доски без изменений).

Несмотря на довольно большой список нереализованных функций (isVictory, getConfig, displayBoard, canAttack, upgradeToKings, availableMoves, availableAttacks, move, attack, getRandom), написанный код компилируется — то есть он синтаксически корректен.

Читатели, самостоятельно пишущие код в процессе чтения статьи, могут сравнить свой вариант с файлом «checkers03.hs», расположенным в архиве с примерами кода.

5 Сбор информации о доступных ходах со взятием

Чтобы выяснить, какие еще функции должны входить в API работы с состоянием доски, приступим к реализации функции availableAttacks, которой потребуется всесторонне анализировать информацию о расстановке фигур обоих игроков.

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

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

availableAttacks board side = concatMap (checkDiagonals board side) (pieces side board) where checkDiagonals board side (piece,coords) = if isChecker piece then checkerAttack coords forward left ++ checkerAttack coords forward right else kingAttack coords forward left ++ kingAttack coords forward right ++ kingAttack coords (-forward) left ++ kingAttack coords (-forward) right (forward,left,right) = if side == White then (-1, -1, 1) else (1,1,-1) checkerAttack coords deltaRow deltaColumn | hasTargetAndEmptySquareBehind squares = undefined | otherwise = [] where squares = diagonal board coords deltaRow deltaColumn kingAttack coords deltaRow deltaColumn | emptySqrsThenTargetAndEmptySqrBehind squares = undefined | otherwise = [] where squares = diagonal board coords deltaRow deltaColumn isChecker = undefined diagonal = undefined hasTargetAndEmptySquareBehind = undefined emptySqrsThenTargetAndEmptySqrBehind = undefined

Из определения функции checkDiagonals следует, что она принимает три аргумента. В то же время, в строке concatMap (checkDiagonals board side) эта функция применена к двум аргументам. Результатом такого частичного применения (partial application, см. [7]) является функция одного аргумента, принимающая на вход пару (piece,coords). Именно такая функция требуется для обработки списка фигур с помощью функции concatMap.

В определении функций checkerAttack и kingAttack использованы охранные выражения (guards, см. [2]), позволяющие выбирать тот или иной вариант поведения в зависимости от истинности указанных условий.

Предполагается, что функция diagonal возвращает список координат клеток, лежащих по диагонали от клетки с координатами coords в направлении, указанном при помощи (deltaRow, deltaColumn).

Функция availableAttacks, даже не будучи реализованной в полном объеме, получается достаточно громоздкой. Кроме того, если задуматься о реализации функции availableMoves, то станет понятно, что ее код будет практически полностью повторять код функции availableAttacks. Отличие будет заключаться в том, что вместо hasTargetAndEmptySquareBehind будет использована другая функция, проверяющая наличие перед шашкой пустой клетки, на которую можно будет сделать ход.

Аналогичное изменение будет сделано для обработки «дамок», но весь остальной код, осуществляющий последовательный перебор фигур, объединение результатов работы checkDiagonals, генерацию списков клеток, лежащих на диагонали и т. п., останется без изменений.

Разумно вынести общий алгоритм работы availableMoves и availableAttacks в отдельную функцию collectOpportunities. Эта функция будет заниматься сбором информации о «возможностях», доступных игроку в текущем игровом состоянии, где под «возможностями» понимаются ходы со взятием или без него. В качестве аргумента ей будет передаваться функция, проверяющая, подходит ли данное диагональное направление для того, чтобы осуществить данной фигурой ход нужного типа (со взятием или без). Кроме того, аргументом collectOpportunities должна быть еще одна функция, которая сформирует данные о «возможности» (возможном ходе) и вернет их в качестве результата работы checkerAttack или kingAttack.

6 Сбор информации о доступных ходах: вторая попытка

В процессе написания функции collectOpportunities можно сделать еще несколько упрощений имеющегося кода.

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

Кроме того, можно объединить функции checkerAttack и kingAttack в одну, вынеся функциональность, реализующую разное поведение фигуры в зависимости от ее типа за пределы collectOpportunities.

Теперь сама функция collectOpportunities может быть записана следующим образом:

collectOpportunities board side canAct describeAction = concatMap checkDiagonals (pieces side board) where checkDiagonals (coords,piece) = concatMap (checkDirection coords piece) (validDirections piece) checkDirection coords piece direction | canAct piece squares = describeAction piece coords squares | otherwise = [] where squares = diagonal coords direction validDirections = undefined diagonal = undefined pieces = undefined

Тут функция checkDirection выполняет проверку хода фигуры piece в направлении direction. Если набор клеток на нужной диагонали будет признан подходящим функцией canAct, то будет вызвана функция describeAction для генерации информации о возможном ходе фигуры в этом направлении.

Функция checkDiagonals выполняет обработку всех возможных направлений движения одной фигуры, а функция collectOpportunities просто применяет checkDiagonals ко всем фигурам конкретного игрока. Реализация функции pieces, возвращающей список фигур, отложена на будущее.

Непосредственная работа с направлениями будет реализована в функциях validDirections и diagonal, которые, скорее всего, будут содержать код, похожий на использованный в первом варианте availableAttacks. Но так как функция collectOpportunities получилась более высокоуровневой, можно сейчас не углубляться в детали их реализации.

Теперь можно свести функции availableAttacks и availableMoves к вызову collectOpportunities с правильными аргументами:

availableAttacks board side = collectOpportunities board side canTake genAttackInfo where canTake = undefined genAttackInfo = undefined availableMoves board side = collectOpportunities board side canMove genMoveInfo where canMove = undefined genMoveInfo = undefined

Получившийся код находится в файле «checkers04.hs» в архиве с примерами кода. На рисунке 2 можно видеть иерархию функций, описанных в этом файле, пунктиром обозначены еще не реализованные функции.

Рис. 2: Дерево вызовов функций в файле checkers04.hs

7 Передвижение фигур

К настоящему моменту в коде насчитывается пятнадцать функций-«заглушек», определенных как undefined. Несмотря на это, компилятор уже может делать определенные выводы о том, какие значения будут принимать и возвращать описанные функции. Если загрузить код в интерпретатор Haskell и поинтересоваться, какой тип был автоматически определен для функции availableAttacks, можно получить вполне конкретный ответ:

*Main> :load checkers04.hs
[1 of 1] Compiling Main             ( checkers04.hs, interpreted )
Ok, modules loaded: Main.

*Main> :type availableAttacks
availableAttacks :: t -> t1 -> [α]

Хотя компилятор еще не знает, какие конкретно типы данных будут использованы для описания игровой доски и допустимых ходов, он уже может сделать вывод о том, что функция availableAttacks будет возвращать список значений.

Список будет пуст, если допустимых ходов со взятием нет. Зная это, можно реализовать одну из функций-«заглушек»:

canAttack board side = not $ null $ availableAttacks board side

Теперь самое время углубится в детали, которые помогут связать друг с другом разные части кода. По дизайну, компьютерный игрок randomComputer будет выбирать один из элементов списка, возвращаемого функциями availableAttacks или availableMoves, и без изменений передавать его в функции attack или move.

Какого же типа должны быть эти значения, и какие данные они должны содержать? Чтобы функция move могла обновить информацию о состоянии доски, ей потребуются сведения о том:

что за фигура (шашка или «дамка») ходит;
с какой клетки;
на какую клетку.

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

data MoveInfo = MoveInfo { piece :: Piece , from :: Coords , to :: Coords } | AttackInfo { piece :: Piece , from :: Coords , victim :: Coords , to :: Coords }

Описание типа MoveInfo выполнено с использованием record syntax, чтобы компилятор автоматически генерировал функции piece :: MoveInfo -> Coords, from :: MoveInfo -> Coords и т. п. для доступа к компонентам данных.

Имя типа данных MoveInfo совпадает с именем одного из его конструкторов. Это довольно распространенная практика. При употреблении MoveInfo компилятор (и программист) из контекста в любой момент может легко понять, что именно имеется в виду.

Детали реализации типов Piece и Coords пока обсуждать рано, можно временно описать их как «типы без данных» (аналог трюка с undefined для описания типов данных):

data Piece = Piece data Coords = Coords

Модификация доски при ходе фигуры piece с клетки from на клетку to заключается в том, чтобы убрать фигуру указанного цвета со старых координат и разместить ее на новых:

move board side (MoveInfo piece from to) = replace (from,piece) (to,piece) side board replace = undefined

При ходе со взятием фигура piece выполняет передвижение с клетки from на клетку to, перепрыгивая через «жертву», стоящую на клетке victim. По окончании хода «жертва» убирается с доски:

attack board side (AttackInfo piece from victim to) = remove victim (otherSide side) $ replace (from,piece) (to,piece) side board remove = undefined

Получившийся код находится в файле «checkers05.hs» в архиве с примерами кода.

8 Доска, фигуры, координаты

Функции replace и remove будут работать со списком фигур, хранящимся в описании игрового поля. Функция pieces для получения текущего значения этого списка уже упоминалась при описании функции collectOpportunities (см. 6). Если предположить, что для обновления информации о списке фигур имеется парная функция setPieces, то можно реализовать функции replace и remove с помощью стандартных операций работы со списками:

replace (from,piece) (to,piece') side board = let pcs = pieces side board pcs' = (to,piece'):(filter (/=(from,piece)) pcs) in setPieces side board pcs' remove coords side board = let pcs = pieces side board pcs' = filter ((/=coords).getCoords) pcs in setPieces side board pcs'

В принципе, для описания типа данных, хранящего информацию о состоянии доски, уже все готово. Информация о фигурах может храниться либо в виде списка троек (координата, фигура, цвет), либо в виде двух отдельных списков пар (координаты, фигура): в одном списке будет информация о черных фигурах, во втором — о белых. Вариант с двумя списками лучше соответствует уже написанному коду — до сих пор везде происходила обработка фигур одного конкретного цвета, и все написанные функции рассчитывают, что функция pieces будет возвращать именно список пар (координаты, фигура). А при использовании одного списка для хранения всех фигур функции pieces придется при каждом вызове отфильтровывать из него информацию о фигурах ненужного цвета.

Осталось решить вопрос с тем, как хранить информацию о координатах клеток доски. Самый простой способ — пронумеровать строки и столбцы доски, и хранить координаты в виде пар (строка, столбец):

type Coords = (Int,Int)

Тип данных, описывающий фигуру — это простое перечисление (набор констант) из двух значений: «шашка» и «дамка»:

data Piece = Checker | King

Теперь описание доски будет выглядеть так¹⁰:

data Board = Board { height :: Int , width :: Int , whites :: [(Coords,Piece)] , blacks :: [(Coords,Piece)] }

Для удобства работы с компонентами типа Board можно определить вспомогательные функции pieces, setPieces и getCoords:

pieces White = whites pieces Black = blacks setPieces White board ws = board { whites=ws } setPieces Black board bs = board { blacks=bs } getCoords (coords,p) = coords

Получившийся код находится в файле «checkers06.hs» в архиве с примерами кода.

9 Выход в «дамки» и отображение состояния доски

Теперь можно реализовать часть функций-«заглушек», которым требуется доступ к деталям реализации состояния о доске. Например, превращение шашек в «дамки» по окончании хода. Необходимо проверить, нет ли на доске шашек, стоящих на самом дальнем от игрока ряду. Для белых это ряд номер один, для черных — ряд с номером, равным высоте доски. Если такие шашки найдены — они меняются на «дамки» при помощи функции replace:

upgradeToKings board side = newBoard where kingRow White = 1 kingRow Black = height board newBoard = in case filter (upgradeableChecker (kingRow side)) pcs of (coords,Checker):_ -> replace (coords,Checker) (coords,King) side board _ -> board upgradeableChecker targetRow ((row,col),Checker) = row == targetRow upgradeableChecker _ _ = False

В выражении case использован шаблон _, сопоставляемый с произвольным выражением; таким образом реализуется семантика «для всех прочих выражений — результат такой-то». Подобный прием можно видеть и в определении функции upgradeableChecker.

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

displayBoard board = putStrLn (boardToString board) where boardToString board = unlines rows rows = [ row r | r <- [1..height board ] ] row r = [ square r c | c <- [1..width board] ] square r c = case lookup (r,c) allPieces of Just (Checker,White) -> 'w' Just (King,White) -> 'W' Just (Checker,Black) -> 'b' Just (King,Black) -> 'B' Nothing -> if isBlackSquare r c then '.' else ' ' allPieces = [ (coords,(piece,side)) | side <- [ Black, White ] , (coords,piece) <- pieces side board ] isBlackSquare r c = odd (r+c)

Получившийся код находится в файле «checkers08.hs» в архиве с примерами кода. Загрузив его в интерпретатор Haskell, можно убедиться, что функция displayBoard может отобразить доску без расставленных фигур:

Prelude> :l ./checkers08.hs
[1 of 1] Compiling Main             ( checkers08.hs, interpreted )
Ok, modules loaded: Main.
*Main> displayBoard (Board 8 8 [] [])
 . . . .
. . . . 
 . . . .
. . . . 
 . . . .
. . . . 
 . . . .
. . . . 

*Main>

10 Создание доски

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

Варианты игры в шашки отличаются как размером доски, так и количеством шашек у каждого игрока. Доска для классических (русских) шашек — размером 8×8, у каждого игрока по 12 фигур:

checkers8x8 = newBoard 8 8 12

Доска для международных шашек — 10×10, у каждого игрока по 20 фигур:

checkers10x10 = newBoard 10 10 20

Фигуры расставляются на черных клетках доски. Если иметь упорядоченный в порядке возрастания рядов список координат черных клеток, то можно сказать, что черные фигуры занимают 12 (или 20) первых клеток из этого списка, а белые — такое же количество последних:

newBoard h w numPieces = Board h w whitePieces blackPieces where coords = [ (row,column) | row <- [1..h], column <- [1..w] , isBlackSquare row column ] blackPieces = zip (take numPieces coords) (repeat Checker) whitePieces = zip (take numPieces (reverse coords)) (repeat Checker)

Определение coords использует «конструктор списка» (list comprehension, см. [5]) с предикатом, при этом в результат попадают только пары (row,column), удовлетворяющие условию isBlackSquare.

Хотя функция repeat и генерирует бесконечный список значений, результат работы zip будет ограничен длиной более короткого аргумента, и будет иметь длину numPieces.

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

getConfig = return (checkers8x8, randomComputer, randomComputer)

Получившийся код (с некоторыми сокращениями) приведен на рисунке 3. Полный текст находится в файле «checkers09.hs» в архиве с примерами кода.

Теперь можно убедиться, что функция displayBoard корректно работает для доски с расставленными фигурами:

[1 of 1] Compiling Main             ( checkers09.hs, interpreted )
Ok, modules loaded: Main.
*Main> displayBoard ( checkers8x8 )
 b b b b
b b b b 
 b b b b
. . . . 
 . . . .
w w w w 
 w w w w
w w w w 

*Main>

module Main where main = do (newBoard, playerA, playerB) <- getConfig play newBoard playerA playerB play newBoard playerA playerB = ... data Side = White | Black otherSide White = Black otherSide Black = White data MoveType = Move | Attack randomComputer Move board side = ... randomComputer Attack board side = ... availableAttacks board side = collectOpportunities board side canTake genAttackInfo where canTake = undefined genAttackInfo = undefined availableMoves board side = collectOpportunities board side canMove genMoveInfo where canMove = undefined genMoveInfo = undefined collectOpportunities board side canAct describeAction = concatMap checkDiagonals (pieces side board) where checkDiagonals (coords,piece) = concatMap (checkDirection coords piece) (validDirections piece) checkDirection coords piece direction | canAct piece squares = describeAction piece coords squares | otherwise = [] where squares = diagonal coords direction validDirections = undefined diagonal = undefined move board side (MoveInfo piece from to) = replace (from,piece) (to,piece) side board attack board side (AttackInfo piece from victim to) = remove victim (otherSide side) $ replace (from,piece) (to,piece) side board data MoveInfo = MoveInfo { piece::Piece, from::Coords, to::Coords } | AttackInfo { piece::Piece, from::Coords, victim::Coords, to::Coords} replace (from,piece) (to,piece') side board = let pcs = pieces side board pcs' = (to,piece'):(filter (/=(from,piece)) pcs) in setPieces side board pcs' remove coords side board = let pcs = pieces side board pcs' = filter ((/=coords).getCoords) pcs in setPieces side board pcs' data Piece = Checker | King deriving Eq type Coords = (Int,Int) data Board = Board { height :: Int , width :: Int , whites :: [(Coords,Piece)] , blacks :: [(Coords,Piece)] } pieces White = whites pieces Black = blacks setPieces White board ws = board { whites=ws } setPieces Black board bs = board { blacks=bs } getCoords (coords,p) = coords upgradeToKings board side = ... displayBoard board = .... isBlackSquare r c = odd (r+c) getConfig = return (checkers8x8, randomComputer, randomComputer) checkers8x8 = newBoard 8 8 12 checkers10x10 = newBoard 10 10 20 newBoard h w numPieces = Board h w whitePieces blackPieces where coords = [ (row,column) | row <- [1..h], column <- [1..w] , isBlackSquare row column ] blackPieces = zip (take numPieces coords) (repeat Checker) whitePieces = zip (take numPieces (reverse coords)) (repeat Checker) getRandom = undefined

Рис. 3: Листинг checkers09.hs

11 Диагонали

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

Так, чтобы завершить описание функции collectOpportunities, определим функции validDirections и diagonal.

Как уже говорилось ранее (см. 5), функция diagonal должна возвращать список клеток, лежащих по диагонали от данной в указанном направлении. Направление можно задавать, указывая, как именно изменяются номера строк и столбцов клеток, лежащих на диагонали — они либо уменьшаются, либо увеличиваются на единицу для каждой следующей клетки. Другими словами, диагональ, начинающаяся в клетке с координатами (row,column) и идущая в направлении (dr, dc) — это последовательность клеток с координатами (row+dr,column+dc), (row+dr+dr,column+dc+dc), и так далее, не выходящая за пределы доски:

diagonal (row,column) (dr,dc) = [ (r,c) | (r,c) <- zip rows columns , inside board r c ] where rows = take (height board) [row+dr,row+dr+dr..] columns = take (width board) [column+dc,column+dc+dc..] inside board r c = r >= 1 && c >= 1 && r <= height board && c <= width board

Определения rows и columns используют «синтаксический сахар» (..) для генерации координат диагонали. Получившиеся списки — бесконечные. Чтобы гарантировать завершение функции diagonal, списки ограничиваются при помощи функции take.

В генераторах списков (list comprehensions, см. [5]) возможно использование не только явно заданных списков, но и результатов применения функций. Например, пары координат в определении diagonal берутся из результата работы функции zip.

Диагональные направления, которые будут обрабатываться при помощи функции diagonal, генерируются функцией validDirections. Теперь уже видно, что функция validDirections должна просто возвращать список вида [(-1,1),(-1,-1),...], в зависимости от того, о какой фигуре идет речь, и какая сторона (черные или белые) делает ход.

Допустимые направления движения и взятия для шашки — вперед-влево или вперед-вправо:

validDirections Checker = [ (forward,left), (forward,right) ]

Для «дамки» добавляются еще и аналогичные движения назад-влево и назад-вправо:

validDirections King = [ (forward,left), (forward,right) , (backward, left), (backward, right) ]

Конкретные значения forward, backward, left и right изменяются в зависимости от того, с какой стороны доски смотреть на игровую ситуацию:

(forward,backward,left,right) = if side == White then (-1, 1, -1, 1) else ( 1,-1, 1,-1)

Получившийся код находится в файле «checkers10.hs» в архиве с примерами кода.

12 Реализация availableAttacks и availableMoves

Было бы неплохо проверить работоспособность функции collectOpportunities в интерпретаторе Haskell так же, как это делалось для функции displayBoard. Однако в своем нынешнем виде функция collectOpportunities неработоспособна — для генерации результата она вызывает функции, передаваемые из availableAttacks и availableMoves в качестве аргументов canAct и describeAction. Необходимо завершить реализацию функций availableAttacks и availableMoves, чтобы в collectOpportunities передавались не «заглушки» undefined, а нечто более осмысленное.

Начать можно с функций, передаваемых в качестве параметра canAct — это функции canMove и canTake. Правила ходов (со взятием и без) описываются в терминах свободных и занятых клеток доски. Предположив, что для проверки занятости конкретной клетки реализованы функции empty и hasPiece, можно приступать к написанию кода.

Шашка может сделать ход только в том случае, если непосредственно перед ней есть пустая клетка:

canMove Checker (inFront:_) = empty board inFront

«Дамка» может сделать ход, если по диагонали с ней соседствуют одна или более пустых клеток:

canMove King diagonal = not $ null $ squaresToObstacle diagonal squaresToObstacle diagonal = takeWhile (empty board) diagonal

Во всех прочих случаях ход фигуры невозможен¹²:

canMove _ _ = False

Правила выполнения ходов со взятием описываются так же просто. Шашка может выполнить взятие, если перед ней стоит фигура противника, а за этой фигурой находится пустая клетка:

canTake Checker (inFront:behindIt:_) = hasPiece board (otherSide side) inFront && empty board behindIt

«Дамка» может выполнить взятие, если перед ней 0..n пустых клеток, за которыми находится вражеская фигура, а за ней — пустая клетка. Фактически, если пропустить первые пустые клетки, можно повторно использовать правило для шашек:

canTake King diagonal = canTake Checker nearestPiece where nearestPiece = dropWhile (empty board) diagonal

Во всех прочих случаях ход со взятием невозможен:

canTake _ _ = False

После того, как возможность совершить ход (со взятием или без) подтверждена, необходимо составить описание этого хода в виде данных типа MoveInfo. Для этого в свое время были предусмотрены функции genMoveInfo и genAttackInfo.

Шашка может пойти только на ближайшее пустое поле вдоль диагонали¹³:

genMoveInfo Checker coords diagonal = [ MoveInfo { piece=Checker, from=coords, to=(head diagonal) } ]

«Дамка» может пойти на любое свободное поле диагонали, вплоть до ближайшего препятствия. Таким образом, для «дамки» необходимо генерировать список элементов MoveInfo, по одному на каждый возможный ход:

genMoveInfo King coords diagonal = map moveTo $ squaresToObstacle diagonal where moveTo square = MoveInfo { piece=King, from=coords, to=square }

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

genAttackInfo Checker coords diagonal = [ AttackInfo { piece=Checker, from=coords, victim=(diagonal!!0), to=(diagonal!!1) } ]

«Дамка» выполняет взятие, перепрыгивая через ближайшую по диагонали фигуру на любую следующую за ней пустую клетку¹⁴:

genAttackInfo King coords diagonal = map leapOverNearestPiece landingPlaces where leapOverNearestPiece square = AttackInfo { piece=King, from=coords, victim=nearestPiece, to=square } (nearestPiece:behindNearestPiece) = dropWhile (empty board) diagonal landingPlaces = takeWhile (empty board) behindNearestPiece

Получившийся код находится в файле «checkers11.hs» в архиве с примерами кода. Чтобы функции availableAttacks и availableMoves заработали, необходимо дать определение функций empty и hasPiece, но уже сейчас можно проверить, что компилятор правильно вывел типы:

Prelude> :load checkers11.hs
[1 of 1] Compiling Main             ( checkers11.hs, interpreted )
Ok, modules loaded: Main.

*Main> :type availableMoves 
availableMoves :: Board -> Side -> [MoveInfo]

*Main> :type availableAttacks
availableAttacks :: Board -> Side -> [MoveInfo]

13 Финальные штрихи

Чтобы завершить написание программы игры в шашки, осталось определить четыре функции: hasPiece, empty, isVictory и getRandom.

Проверка наличия фигуры указанного цвета в точке с указанными координатами реализуется просто. Если в списке фигур игрока есть запись с такими координатами, значит есть и фигура:

hasPiece board side coords = case lookup coords (pieces side board) of Nothing -> False _ -> True

Клетка доски считается пустой, если она не занята фигурой ни одного из игроков:

empty board coords = not (hasPiece board White coords || hasPiece board Black coords)

Игрок считается победителем, если на доске не осталось фигур противника:

isVictory side board = null $ pieces (otherSide side) board

И, наконец, «интеллект» компьютерного игрока — функция, выбирающая случайный элемент из списка:

import System.Random getRandom lst = do idx <- randomRIO (0,length lst-1) return (lst!!idx)

Получившийся код находится в файле «checkers11.hs» в архиве с примерами кода.

Теперь можно проверить правильность работы функций availableAttacks и availableMoves. Из начального положения доски для игры в русски шашки игроку доступно семь обычных ходов и ни одного хода со взятием:

Prelude> :l checkers12.hs
[1 of 1] Compiling Main             ( checkers12.hs, interpreted )
Ok, modules loaded: Main.

*Main> length (availableMoves checkers8x8 White)
7

*Main> availableAttacks checkers8x8 White
[]

Запустив программу при помощи команды «runhaskell checkers12.hs», можно увидеть сражение двух компьютерных игроков друг с другом.

На рисунке 4 можно увидеть, как взаимодействуют друг с другом все высокоуровневые функции финальной программы. Функции, определенные локально (в let- и where-блоках) не включены в диаграмму, чтобы повысить ее читаемость.

Рис. 4: Дерево вызовов функций программы checkers12.hs

14 Разбиение программного кода на модули

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

Например, можно отделить описания всех используемых структур данных и разместить их в отдельном модуле Types. Можно выделить в отдельный модуль Board все функции, работающие с состоянием доски, а в модуль Checkers — реализацию собственно игры в шашки. Если дополнительно вычленить реализацию компьютерного игрока в модуль RandomComputer, то окажется, что главный модуль программы состоит буквально из нескольких строк:

module Main where import Board (checkers8x8) import Checkers (play) import RandomComputer (randomComputer) main = do (newBoard, playerA, playerB) <- getConfig play newBoard playerA playerB getConfig = return (checkers8x8, randomComputer, randomComputer)

Подобное разбиение на модули позволит скрыть часть деталей реализации. Функции collectOpportunities, hasPiece, empty и им подобные можно не экспортировать за пределы модулей, в которых они определяются и используются. На рисунке 5 видно, как сильно упрощается в результате схема взаимодействия разных частей программы.

Рис. 5: Зависимости между модулями и перечень экспортируемых функций программы checkers13

Окончательный код программы находится в директории «checkers13» в архиве с примерами кода. Взяв его за основу, читатель может попробовать в качестве самостоятельного упражнения решить такие задачи:

Модифицировать displayBoard так, чтобы рядом с изображением доски указывались номера строк и столбцов.
Определить функцию, которая будет запрашивать с клавиатуры координаты передвигаемой фигуры, валидировать их и делать ход; затем использовать ее вместо randomComputer в вызове функции play для игры человека против компьютера.
Для варианта игры «человек против компьютера» реализовать «undo» — возможность вернуть состояние на один или несколько ходов назад.
Написать более интеллектуального компьютерного игрока, который предпочитает делать ходы, не подставляющие свои фигуры под ответный удар.

15 Заключение

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

В самом деле, легко видеть, что словесное описание функций всегда было более объемным, чем соответствующая реализация на Haskell, даже в случае сложных функций вроде collectOpportunities. Использование функций высших порядков и возможность передавать функции в качестве аргументов позволили радикально сократить количество вспомогательного кода и сосредоточиться на реализации нужной функциональности.

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

Список литературы

[1]: Bottom. Статья в Haskell Wiki, http://www.haskell.org/haskellwiki/Bottom.
[2]: Control structures. Статья в Wiki-книге Haskell, http://en.wikibooks.org/wiki/Haskell/Control_structures.
[3]: Introduction to io. Статья в Haskell Wiki, http://www.haskell.org/haskellwiki/Introduction_to_IO.
[4]: Learn you a haskell for great good. Учебник, http://learnyouahaskell.com/.
[5]: More about lists. Статья в Wiki-книге Haskell, http://en.wikibooks.org/wiki/Haskell/More_about_lists.
[6]: More on datatypes. Статья в Wiki-книге Haskell, http://en.wikibooks.org/wiki/Haskell/More_on_datatypes.
[7]: Partial application. Статья в Haskell Wiki, http://www.haskell.org/haskellwiki/Partial_application.
[8]: Yet another haskell tutorial. Учебник, http://darcs.haskell.org/yaht/yaht.pdf.
[9]: Мягкое введение в haskell. Учебник, http://www.rsdn.ru/article/haskell/haskell_part1.xml.
[10]: Bryan O’Sullivan, Donald Stewart, and John Goerzen. Real World Haskell. O’Reilly Media, Inc., 2008.
[11]: Charles Petzold. Does visual studio rot the mind? Статья в блоге, http://www.charlespetzold.com/etc/DoesVisualStudioRotTheMind.html.
[12]: Душкин Р. В. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2007.

1: Для этого язык должен быть статически типизирован, а его компилятор — обладать возможностью выведения типов выражений. Примеры подобных языков: Haskell, OCaml.
2: Haskell: в функции main используется «синтаксический сахар» под названием «do-нотация» для упрощения записи операций ввода/вывода. См. [3] и [10, глава 7].
3: Детальное описание этого примечательного факта см. в [1].
4: Автор множества книг по программированию под Windows.
5: В статье демонстрируются примеры с использованием интерпретатора ghci под OS Linux, но с таким же успехом можно использовать и любой другой интерпретатор — например, hugs — в привычной операционной среде.
6: Подобные соглашения приняты, в частности, в английском варианте игры в шашки.
7: По-английски «дамка» называется «king», и именно так она будет именоваться в коде программы.
8: Haskell: поскольку функция getPlayer определена локально в where-блоке функции play, ей непосредственно доступны все аргументы функции play и их не нужно явно передавать при вызове getPlayer.
9: Haskell: функция $ может использоваться для уменьшения количества круглых скобок в коде. (print (process (parse (read x)))) — то же самое, что и (print $ process $ parse $ read x).
10: Автору неизвестны варианты игры в шашки на прямоугольных досках, но тем не менее возможность создания прямоугольной доски была оставлена.
11: Haskell: В определениях rows, row и allPieces используется «синтаксический сахар» для определения списков, позволяющий обойтись без циклов for (см. [5], раздел «list comprehensions»).
12: Haskell: в объявлении функции canMove использовано сопоставление с образцом _, который совпадает с любым значением аргумента. Таким образом реализуется поведение «во всех прочих случаях — делать так-то».
13: Haskell: использование структур с именованными полями (record syntax, см. [6]) повышает читаемость кода.
14: Haskell: в where-блоке используется сопоставление с образцом, чтобы сразу разбить результат работы dropWhile на первый элемент списка nearestPiece и «хвост» behindNearestPiece.

Этот документ был получен из L^AT_EX при помощи H^EV^EA

Практика функционального программирования