- PVSM.RU - https://www.pvsm.ru -

Dagaz: Факториал — это просто!

imageСкриптинг — пожалуй наиболее важная (хотя и не самая сложная) часть задуманного мной проекта [1]. Для того, чтобы всё заработало, мне потребуется язык общего назначения, с переменными, условным выполнением, циклами и исключениями. Мне не требуется что-то сложное, вроде анонимных функций [2] или замыканий [3]. Скорее всего, мне не пригодится даже рекурсия [4], во всяком случае, пока, для неё не нашлось применений, ни в одном из моих case [5]-ов. В этом языке совсем не будет синтаксического сахара [6], поскольку все задачи метапрограмирования возьмёт на себя XSLT [7]. В общем, этот язык будет прост настолько, насколько это возможно, но… не проще. 

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

Определение ''доски''

   (board
      (grid (dimensions "A_J" "1")
            (direction (name forward)   1 0)
            (direction (name backward) -1 0)
      )
      (grid (dimensions "A_J" "2")
            (direction (name forward)  -1 0)
            (direction (name backward)  1 0)
      )
      (grid (dimensions "A_K" "3")
            (direction (name forward)   1 0)
            (direction (name backward) -1 0)
      )
      (grid (dimensions "a_d"))
      (link (name forward)  (J1 J2) (A2 A3) (K3 K3))
      (link (name backward) (J2 J1) (A3 A2) (K3 K3))
      (zone (name rebirth)  (positions F2))
      (zone (name protect)  (positions F3 G3 H3 I3 J3))
      (zone (name beauty)   (positions F3))
      (zone (name water)    (positions G3))
      (zone (name truth)    (positions H3))
      (zone (name ra)       (positions I3))
      (zone (name stop)     (positions F3 K3))
      (zone (name end)      (positions K3))
      (zone (name dices)    (positions a b c d))
   )

Это определение — своего рода «карта» настольной игры и оно может быть очень сложным. Именно для разбора таких иерархических структур мне понадобился XPath [9], что, в свою очередь, привело к необходимости использования XML [10], для внутреннего представления скрипта в памяти. Разбор таких структур многословен [11], но довольно прямолинеен. Код [12] — другое дело.

(define (factorial n a)
  (if (<= n 1)
     a
   else
     (factorial (- n 1) (* a n))
  )
)

(define (factorial n)
  (factorial n 1)
)

(define main
  (set! out (factorial 5))
)

Надеюсь, вы его узнали. Да, здесь вычисляется значение факториала [13], с использованием «хвостовой рекурсии», и нет, я не собираюсь заниматься оптимизацией «хвостовой рекурсии». Как я уже говорил, мне и рекурсия то вряд ли понадобится. Тем, кто вдруг не знает, что такое «хвостовая рекурсия» и зачем её может понадобиться оптимизировать, я рекомендую почитать эту замечательную книгу [14].

Этот код — просто компактный тест, максимально покрывающий весь интересующий меня, в данный момент, функционал. В нём используется условный оператор, вызовы и определения функций, перегрузка [15] и работа с параметрами. Поскольку операторы ввода/вывода в языке не предусмотрены (они и не потребуются), в тесте, вывод будет эмулироваться присвоением итогового значения «переменной» out.

Кстати говоря

Сложность выбранного теста вполне себя оправдала. Вычисляя факториал трёх я обратил внимание на то, что полученное значение «2» несколько отличается от ожидаемого. Расследование этой ситуации привело к следующему фиксу [16]. Я вполне мог не заметить эту ошибку, используя более простой тест.

Можно заметить, что все управляющие конструкции языка являются функциями, в том смысле, что они всегда возвращают некое значение [17]. Например, результатом выполнения последовательности [18] выражений является результат последнего выполненного выражения. Отдельно стоит упомянуть об исключениях [19]:

(define dice-drop
   (check (in-zone? dices))
   (check is-empty?)
   drop-pieces
   add-move
)

В любой момент, может быть выполнена проверка истинности некоего булевского выражения. В случае, если полученное значение окажется ложным, выполнение должно быть немедленно прервано. Мне неизвестен инструмент, более подходящий для этой задачи, чем исключения. CheckExpression [20] вычисляет значение своего аргумента в булевском контексте и «бросает» CheckException [21], при нарушении условия (очевидно, что эта функция будет возвращать истинное значение всегда, если только до возврата значения вообще дойдёт дело).

Значения аргументов функций будут вычисляться строго [22], до передачи управления функциям. Тотальной "ленивости [23]" вычислений не будет, но такие функции как if [24], and [25] или or [26] будут вычислять значения своих аргументов лишь при необходимости. Для вызова произвольных функций (определённых в теле скрипта), предназначена конструкция ApplyExpression [27]. Полученные значения аргументов представляют собой ни что иное, как локальные переменные, область видимости которых ограничена вызываемой функцией. Доступ ко всем переменным осуществляется через интерфейс IEnvironment [28], передаваемый каждому вычисляемому выражению:

public interface IEnvironment {
	...
	void   letValue(String name, IValue value) throws EvaluationException;
	void   setValue(String name, IValue value) throws EvaluationException;
	IValue getValue(String name, boolean isQuoted) throws ValueNotFoundException;
	...
}

Используя этот интерфейс, можно создавать локальные переменные (функцией let [29]), изменять их значение (функцией set! [30]), а также получать значение по имени. Для последней [31] их этих операций, специальной функции не предусмотрено. Любой атом [32], не являющийся строковым или числовым литералом, будет рассматриваться как обращение к переменной (или параметру функции), при условии того, что в скрипте не была определена функция с тем же именем и арностью [33].

Подробности для любознательных

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

(define dice-drop
   ...
   (drop-pieces)
   (add-move)
)

Я посчитал подобную запись излишне громоздкой. Кроме того, возникла проблема с внутренним представлением [7] подобных структур в XML. Другой не реализованной возможностью является вычисление имени вызываемой функции:

((if (< a b) "+" else "-") a b)

В любом случае, я не считаю, что использование подобных конструкций необходимо.

С целью максимального упрощения языка, я не стал реализовывать оператор QUOTE [34] явно (поэтому написать Quine [35] на этом языке вряд ли удастся). Цитирование в языке есть, но оно неявное. Например, такие выражения как let и set! «знают», что первый аргумент вычислять не надо (за это отвечает переопределённый метод IExpression.isQuoted [36]). Таким образом, первый аргумент, в этих выражениях, воспринимается как имя переменной, а не попытка получения её значения.

Ещё больше подробностей

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

(define (piece-move direction)
   (check up)
   (check direction)
   ...
)
...
(moves 
   (piece-move north)
   (piece-move south)
   (piece-move east)
   (piece-move west)
   ...
)

Подобный код будет встречаться очень часто. Здесь, атомы north, south, east и west должны интерпретироваться как имена направлений, но лишь при условии, что такие направления на доске определены (в противном случае, это обращение к переменным). Таким образом, параметр direction будет содержать строку с именем соответствующего направления.

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

Но что произойдёт при обращении к параметру direction? Если не предпринимать дополнительных действий, будет получено не пустое строковое значение, которое, в булевском контексте, будет интерпретировано как true. Это явно не то, чего бы нам хотелось. Чтобы исправить ситуацию, модуль, предоставляющий доступ к состоянию расчёта хода, должен проверить не является ли полученная строка именем позиции или направления. Если это так, операция get должна быть выполнена повторно и уже её результат должен быть возвращён в точку вызова. Это является хорошей иллюстрацией тезиса о том, что упрощение языка может вести к усложнению его реализации.

С учётом всего сказанного выше, кодогенерация становится довольно тривиальной [37]. Требуется лишь найти определения функций в XML и рекурсивно построить иерархии соответствующих им выражений. Сами выражения создаются ExpressionFactory [38], что позволяет легко расширять список поддерживаемых системных функций (вплоть до реализации новых конструкций языка).

Разумеется, это не конец пути. Чтобы от такого скриптинга была польза, необходимо связать его с навигацией в игровом пространстве и изменением состояния расчёта хода. Потребуется определить массу системных функций, работающих в терминах предметной области, таких как is-friend? или is-empty?. Наконец, для реализации генератора ходов, потребуется реализовать возможность недетерминированных вычислений [39]. По сравнению со всеми этими вещами, факториал — это действительно просто.

Автор: GlukKazan

Источник [40]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/programmirovanie/78758

Ссылки в тексте:

[1] проекта: http://habrahabr.ru/post/242547/

[2] анонимных функций: https://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%BE%D0%BD%D0%B8%D0%BC%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F

[3] замыканий: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BC%D1%8B%D0%BA%D0%B0%D0%BD%D0%B8%D0%B5_%28%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%29

[4] рекурсия: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F#.D0.92_.D0.BF.D1.80.D0.BE.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B8

[5] case: https://github.com/GlukKazan/Dagaz/tree/master/src/drf

[6] синтаксического сахара: https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D1%81%D0%B0%D1%85%D0%B0%D1%80

[7] XSLT: http://habrahabr.ru/post/245849/

[8] пример: https://github.com/GlukKazan/Dagaz/blob/master/src/drf/senet.drf

[9] XPath: https://ru.wikipedia.org/wiki/XPath

[10] XML: https://ru.wikipedia.org/wiki/XML

[11] многословен: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/parser/BoardConfigurator.java

[12] Код: https://github.com/GlukKazan/Dagaz/blob/master/src/java/tests/scripting/drf/factorial.drf

[13] факториала: https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB

[14] эту замечательную книгу: http://newstar.rinet.ru/~goga/sicp/sicp.pdf

[15] перегрузка: https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D0%B3%D1%80%D1%83%D0%B7%D0%BA%D0%B0_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D0%B4%D1%83%D1%80_%D0%B8_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9

[16] фиксу: https://github.com/GlukKazan/Dagaz/commit/f5064b98e3e8a950f4b6fc4aa3486f52d7995995

[17] значение: https://github.com/GlukKazan/Dagaz/blob/master/src/java/api/src/main/java/com/gluk/dagaz/api/rules/runtime/IValue.java

[18] последовательности: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/SeqExpression.java

[19] исключениях: https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B0_%D0%B8%D1%81%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D0%B9

[20] CheckExpression: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/CheckExpression.java

[21] CheckException: https://github.com/GlukKazan/Dagaz/blob/master/src/java/api/src/main/java/com/gluk/dagaz/api/exceptions/CheckException.java

[22] строго: https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D1%80%D0%B0%D1%82%D0%B5%D0%B3%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F#.D0.90.D0.BF.D0.BF.D0.BB.D0.B8.D0.BA.D0.B0.D1.82.D0.B8.D0.B2.D0.BD.D1.8B.D0.B9_.D0.BF.D0.BE.D1.80.D1.8F.D0.B4.D0.BE.D0.BA

[23] ленивости: https://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BD%D0%B8%D0%B2%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F

[24] if: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/IfExpression.java

[25] and: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/AndExpression.java

[26] or: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/OrExpression.java

[27] ApplyExpression: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/ApplyExpression.java

[28] IEnvironment: https://github.com/GlukKazan/Dagaz/blob/master/src/java/api/src/main/java/com/gluk/dagaz/api/rules/runtime/IEnvironment.java

[29] let: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/LetExpression.java

[30] set!: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/SetExpression.java

[31] последней: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/GetExpression.java

[32] атом: http://www.cardarmy.ru/proekt/lisp/art2.htm

[33] арностью: https://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%BD%D0%BE%D1%81%D1%82%D1%8C

[34] QUOTE: https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D1%81%D0%BF#.D0.91.D0.B0.D0.B7.D0.BE.D0.B2.D1.8B.D0.B5_.D1.81.D0.B8.D0.BC.D0.B2.D0.BE.D0.BB.D1.8B.2C_.D0.BE.D0.BF.D0.B5.D1.80.D0.B0.D1.82.D0.BE.D1.80.D1.8B_.D0.B8_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8

[35] Quine: https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B0%D0%B9%D0%BD_%28%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%29

[36] IExpression.isQuoted: https://github.com/GlukKazan/Dagaz/blob/master/src/java/api/src/main/java/com/gluk/dagaz/api/rules/runtime/IExpression.java

[37] тривиальной: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/parser/CodeConfigurator.java

[38] ExpressionFactory: https://github.com/GlukKazan/Dagaz/blob/master/src/java/rules/src/main/java/com/gluk/dagaz/rules/runtime/ExpressionFactory.java

[39] недетерминированных вычислений: http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%B4%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F

[40] Источник: http://habrahabr.ru/post/247263/