Журнал ВРМ World

Мировая история развития технологий управления эффективностью бизнеса – обзоры зарубежных публикаций

Создание декларативных мини-языков

Предлагаем вашему вниманию очередную статью нашего старого знакомого Дэвида
Мертца- стоит отметить, что эта статья уже упоминалась в прошлом номере
Журнала. Дэвид расскажет о декларативных мини-языках - библиотеках Python,
позволяющих выразить программную логику с помощью объявлений внутри программы
на Python.

Программирование как утверждение, а не как инструкция

Объектно-ориентированные и прозрачные интроспективные возможности Python позволяют легко создавать декларативные мини-языки для задач программирования. В этой статье Дэвид рассматривает не столько использование Python для интерпретации и транслирования других специализированных языков (хотя такое возможно), сколько то, как сам Питоновский код может быть удобно сведен к ряду декларативных элементов. Он покажет, как разработчики могут пользоваться декларативной технологией, чтобы четко и ясно устанавливать требования к приложениям, позволяя при этом "закулисной" структуре выполнять тяжелую работу.

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

Позвольте мне перечислить несколько языков, которые относятся к различным категориям. Многие читатели уже используют большинство этих инструментов, не задумываясь о категориальных различиях между ними. Python, C, C++, Java, Perl, Ruby, Smalltalk, Fortran, Basic, xBase - всё это просто императивные языки программирования. Некоторые из них являются объектно-ориентированными, но это всего лишь вопрос организации кода и данных, а не основного стиля программирования. В этих языках вы даете программе команды выполнить последовательность инструкций: разместить некие данные в переменную; выбрать данные обратно из переменной; исполнить группу инструкций цикла пока не выполнено некоторое условие; сделать что-либо, если что-то истинно (true). Прелесть всех этих языков заключается в том, что о них удобно думать в рамках знакомых житейских метафор. Обычная жизнь состоит из выполнения одного действия, осуществления выбора, а затем исполнения другого действия, возможно с использованием некоторых инструментов. Легко представить себе компьютер, выполняющий программу, как повара, или каменщика, или шофера.

Языки, похожие на грамматики Prolog, Mercury, SQL, XSLT, EBNF, а на самом деле и конфигурационные файлы различных форматов, - все они объявляют, что имеет место ситуация, или что применяются определенные ограничения. Функциональные языки (такие как Haskell, ML, Dylan, Ocaml, Scheme) - подобны, однако, с приданием большего значения формулированию внутренних (функциональных) отношений между программными объектами (рекурсией, списками и т.д.). Наша обычная жизнь, по крайней мере, ее описательная сторона, не имеет прямого аналога программных конструкций этих языков. Однако, для тех проблем, которые вы легко можете описывать на этих языках, декларативные описания гораздо более лаконичны и в значительно меньшей степени подвержены ошибкам по сравнению с императивными решениями. Рассмотрим, например, систему линейных уравнений:

Листинг 1. Пример системы линейных уравнений

10x + 5y - 7z + 1 = 0
17x + 5y - 10z + 3 = 0
5x - 4y + 3z - 6 = 0

Это весьма элегантная запись, которая устанавливает отношения между объектами (x, y и z). Возможно, вы сталкивались с этими фактами в различных ситуациях реальной жизни, но на самом деле нахождение x вручную, на листке бумаги - это кропотливая работа, чреватая ошибками. Но написание этих шагов на Python, возможно, еще хуже - с точки зрения отладки.

Prolog - это язык, который приближается к логике и математике. В нем вы просто записываете утверждения, которые, как вы знаете, должны быть истинны, а затем требуете, чтобы приложение делало для вас выводы. Утверждения записываются вне какой-либо определенной последовательности (так же как и у линейных уравнений отсутствует порядок следования), и программист/пользователь не имеет ни малейшего представления о том, какие шаги участвуют в получении результатов. Например:

Листинг 2. Пример на языке Prolog - family.pro

/* Adapted from sample at:
<http://www.engin.umd.umich.edu/CIS/course.des/cis479/prolog/>
This app can answer questions about sisterhood & love, e.g.
(Это приложение может ответить на вопросы о родственных отношениях
и любви, например):
# Is alice a sister of harry? 
# (Алиса - сестра Гарри?)
?-sisterof( alice, harry )
# Which of alice' sisters love wine?
# (Кому из сестер Алисы нравится вино?)
?-sisterof( X, alice ), love( X, wine)
*/
sisterof( X, Y ) :- parents( X, M, F ),
                    female( X ),
                    parents( Y, M, F ).
parents( edward, victoria, albert ).
parents( harry, victoria, albert ).
parents( alice, victoria, albert ).
female( alice ).
loves( harry, wine ).
loves( alice, wine ).

Не совсем идентично, но схоже по духу объявление грамматики EBNF (Extended Backus-Naur Form, Расширенная форма Бэкуса-Наура). Вы могли бы записать несколько следующих объявлений:

Листинг 3. Пример для EBNF

word        := alphanums, (wordpunct, alphanums)*, contraction?
alphanums   := [a-zA-Z0-9]+
wordpunct   := [-_]
contraction := "'", ("clock"/"d"/"ll"/"m"/"re"/"s"/"t"/"ve")

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

В качестве еще одного примера рассмотрим объявление типа документа, которое описывает диалект допустимых XML-документов:

Листинг 4. Объявление типа XML-документа

<!ELEMENT dissertation (chapter+)>
<!ELEMENT chapter (title, paragraph+)>
<!ELEMENT title (#PCDATA)>
<!ELEMENT paragraph (#PCDATA | figure)+>
<!ELEMENT figure EMPTY>

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

Python как интерпретатор в сравнении с Python как средой

Библиотеки Python могут использовать декларативные языки одним или двумя совершенно различными способами. Возможно, более общий подход - это разобрать и обработать непитоновские декларативные языки как данные. Приложение или библиотека может считать внешний источник (или строку, определенную внутренне, но только как "блоб"), затем определить ряд императивных шагов для выполнения, которые некоторым образом соответствуют внешним объявлениям. В сущности, эти типы библиотек являются системами, "управляемыми данными"; существует концептуальный и категориальный разрыв между декларативным языком и тем, что приложение Python делает, чтобы выполнить или использовать его объявления. К тому же, как правило, библиотеки, обрабатывающие эти идентичные объявления, реализуются также и для других языков программирования.

Все приведенные выше примеры относятся к этому первому подходу. Библиотека PyLog - это Питоновская реализация системы Prolog. Она читает Прологовский файл данных как шаблон, затем создает объекты Python для моделирования объявлений Prolog. Пример для EBNF использует специфический вариант SimpleParse, который является библиотекой Python, преобразующей эти объявления в таблицы состояний, которые могут использоваться mx.TextTools. Сам mx.TextTools - это библиотека расширений для Python, которая, будучи написана на C, исполняет код, хранимый в структурах данных Python, но имеет весьма отдалённое отношение к собственно Python. Python - это великолепная склейка для таких задач, но сами склеенные языки сильно отличаются от Python. Большинство реализаций Prolog к тому же написано на языках, отличных от Python, как и большинство парсеров для EBNF.

DTD подобен остальным примерам. Если вы используете валидирующий парсер, как xmlproc, вы можете воспользоваться DTD, чтобы проверить диалект XML-документа. Однако язык DTD "непитоновский", и xmlproc просто использует его в качестве данных, которые необходимо разобрать. Более того, валидирующие парсеры XML написаны на многих языках программирования. Подобно этому и преобразование XSLT - оно "непитоновское", а такой модуль, как ft.4xslt, просто использует Python как связующее средство.

Хотя в упомянутых выше подходах и инструментах нет ничего дурного (я постоянно их использую), было бы более элегантно - и в некоторых отношениях более выразительно - если бы сам Python мог быть декларативным языком. Тогда библиотеки, которые выполняли бы это, не требовали бы от программистов думать о двух (или более) языках при написании одного приложения. Иногда естественно и обоснованно изучить интроспективные возможности Python, чтобы реализовать "родные" объявления.

Магия интроспекции

Парсеры Spark и PLY разрешают пользователям объявлять Питоновские значения в Python, а затем используют немного магии, чтобы позволить среде исполнения Python выступать в качестве конфигуратора разбора. Рассмотрим, например, эквивалент предшествующей грамматики SimpleParse, описанный с помощью PLY. (пример для Spark почти аналогичен):

Листинг 5. Пример PLY

tokens = ('ALPHANUMS','WORDPUNCT','CONTRACTION','WHITSPACE')
t_ALPHANUMS = r"[a-zA-Z0-0]+"
t_WORDPUNCT = r"[-_]"
t_CONTRACTION = r"'(clock|d|ll|m|re|s|t|ve)"
def t_WHITESPACE(t):
    r"\s+"
    t.value = " "
    return t
import lex
lex.lex()
lex.input(sometext)
while 1:
    t = lex.token()
    if not t: break

Я написал о PLY в моей готовящейся к публикации книге "Текстовая обработка в Python" ("Text Processing in Python") и рассказывал о Spark в этой рубрике (см. Ресурсы). Не вдаваясь в подробности об этих библиотеках, замечу, что все, на что здесь следует обратить внимание, это то, что разбор (в данном примере, лексическое сканирование) непосредственно конфигурируется Питоновскими объявлениями. Просто модуль PLY знает достаточно, чтобы действовать на основании этих шаблонных описаний.

Как именно PLY выясняет, что делать, подразумевает весьма причудливое программирование на Python. На начальном этапе программист среднего уровня поймет, что можно исследовать содержимое словарей globals() и locals(). Было бы неплохо, если бы стиль объявления был слегка другим. Представьте, например, что код был бы таким:

Листинг 6. Использование пространства имен импортированного модуля

import basic_lex as _
_.tokens = ('ALPHANUMS','WORDPUNCT','CONTRACTION')
_.ALPHANUMS = r"[a-zA-Z0-0]+"
_.WORDPUNCT = r"[-_]"
_.CONTRACTION = r"'(clock|d|ll|m|re|s|t|ve)"
_.lex()

Этот стиль не стал бы ничуть менее декларативным, а модуль basic_lex гипотетически мог бы содержать что-нибудь простое вроде:

Листинг 7. basic_lex.py

def lex():
    for t in tokens:
        print t, '=', globals()[t]

Это сгенерировало бы:


% python basic_app.py
ALPHANUMS = [a-zA-Z0-0]+
WORDPUNCT = [-_]
CONTRACTION = '(clock|d|ll|m|re|s|t|ve)

PLY ухитряется проникнуть в пространство имен импортирующего модуля, используя информацию о кадре стека. Например:

Листинг 8. magic_lex.py
 
import sys
try: raise RuntimeError
except RuntimeError:
    e,b,t = sys.exc_info()
    caller_dict = t.tb_frame.f_back.f_globals
def lex():
    for t in caller_dict['tokens']:
        print t, '=', caller_dict['t_'+t]

Это производит такой же результат, как и полученный в примере basic_app.py, но с объявлениями, использующими предыдущий стиль t_TOKEN.

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

Листинг 9. polymorphic_lex

# ...determine caller_dict using RuntimeError...
from types import *
def lex():
    for t in caller_dict['tokens']:
        t_obj = caller_dict['t_'+t]
        if type(t_obj) is FunctionType:
            print t, '=', t_obj.__doc__
        else:
            print t, '=', t_obj

Разумеется, реальный модуль PLY делает кое-что более интересное, используя продемонстрированные подходы, чем эти игрушечные примеры, но и они демонстрируют некоторые задействованные технологии.

Магия наследования

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

Модуль gnosis.xml.validity - это библиотека для создания классов, которые отображаются прямо на результирующие DTD. Любой класс gnosis.xml.validity может быть создан только с аргументами, подчиняющимися ограничениям допустимости диалекта XML. На самом деле это не совсем верно; этот модуль также будет выводить правильные типы из более простых аргументов, если существует только один непротиворечивый способ "достроить" тип до корректного состояния.

Поскольку модуль gnosis.xml.validity написал я сам, я склонен считать, что его предназначение само по себе интересно. Но в этой статье я лишь хочу рассмотреть декларативный стиль, в котором создаются классы допустимости. Набор правил/классов, соответствующих предыдущему шаблону DTD, состоит из:

Листинг 10. Объявления правил gnosis.xml.validity

from gnosis.xml.validity import *
class figure(EMPTY):      pass
class _mixedpara(Or):     _disjoins = (PCDATA, figure)
class paragraph(Some):    _type = _mixedpara
class title(PCDATA):      pass
class _paras(Some):       _type = paragraph
class chapter(Seq):       _order = (title, _paras)
class dissertation(Some): _type = chapter

Вы могли бы создать экземпляры из этих объявлений используя:


ch1 = LiftSeq(chapter, ("1st Title","Validity is important"))
ch2 = LiftSeq(chapter, ("2nd Title","Declaration is fun"))
diss = dissertation([ch1, ch2])
print diss

Заметьте, как близко эти классы соответствуют предыдущему DTD. Это отображение в основном "один к одному", с тем исключением, что необходимо использовать промежуточные имена для определение числа и чередования вложенных тегов (промежуточные имена помечены начальным символом подчеркивания).

Также обратите внимание, что, будучи созданы с использованием стандартного синтаксиса Python, эти классы являются необычными (и более лаконичными) в том, что не имеют ни методов, ни данных экземпляра. Классы определяются исключительно, чтобы наследовать некую структуру, причем эта структура ограничена единственным атрибутом класса. Например, <chapter> является последовательностью других тегов, а именно: <title>, за которым следует один или более тегов <paragraph>. Но все, что нам необходимо сделать, чтобы обеспечить выполнение этого ограничение в экземпляре, это лишь объявить класс chapter.

Главная "хитрость", используемая при программировании таких родительских классов, как gnosis.xml.validity.Seq, это рассмотреть атрибут .__class__ экземпляра во время инициализации. Класс chapter не имеет собственной инициализации, поэтому вызывается метод __init__() его родителя. Но self, передаваемый в родительский __init__(), является экземпляром chapter, и он это знает. В качестве иллюстрации рассмотрим фрагмент реализации gnosis.xml.validity.Seq:

Листинг 11. Класс gnosis.xml.validity.Seq

class Seq(tuple):
    def __init__(self, inittup):
        if not hasattr(self.__class__, '_order'):
            raise NotImplementedError, \
                "Child of Abstract Class Seq must specify order"
        if not isinstance(self._order, tuple):
            raise ValidityError, "Seq must have tuple as order"
        self.validate()
        self._tag = self.__class__.__name__

Если разработчик приложения пытается создать экземпляр chapter, код реализации контролирует, что chapter был объявлен с необходимым атрибутом класса ._order, и этот атрибут является кортежем. Метод .validate() выполняет еще несколько проверок, чтобы убедиться, что объекты, с которыми был инициализирован этот экземпляр, принадлежат соответствующим классам, указанным в ._order.

Когда объявлять

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

Конечно, по крайней мере в Python, верификация или применение объявленных правил всегда сводится к процедурным проверкам. Но надлежащие место для таких процедурных проверок - это хорошо оттестированный код библиотек. Отдельные приложения должны полагаться на более простой декларативный интерфейс, обеспечиваемый библиотеками, как Spark, PLY или gnosis.xml.validity. Другие библиотеки, как xmlproc, SimpleParse или ft.4xslt, также допускают декларативный стиль, хотя без объявлений на Python (что, разумеется, уместно для их области).

Ресурсы

Об авторе

Дэвид Мертц, будучи фукианствующим Беркли, верит, что esse est denunte ("быть - это быть признанным"). Дэвид доступен по адресу: mertz@gnosis.cx, а жизнь его описана на http://gnosis.cx/publish/. Узнайте о его будущей книге "Текстовая обработка в Python" (Text Processing in Python). Присылайте свои замечания и предложения касательно этой, прошлых или будущих статей.



[1] Явная опечатка developerWorks - данная работа принадлежит перу Патрика О'Брайена (прим. пер.)

Автор: Дэвид Мертц (David Mertz), разработчик, Gnosis Software Inc.