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

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

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

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

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

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

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

/* 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, Расширенная форма Бэкуса-Наура). Вы могли бы записать несколько следующих объявлений:

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

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

В качестве еще одного примера рассмотрим объявление типа документа, которое описывает диалект допустимых 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 почти аналогичен):

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(). Было бы неплохо, если бы стиль объявления был слегка другим. Представьте, например, что код был бы таким:

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 гипотетически мог бы содержать что-нибудь простое вроде:

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 ухитряется проникнуть в пространство имен импортирующего модуля, используя информацию о кадре стека. Например:

 
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) регулярных выражений вместе с действующим кодом. Некий контроль типов обеспечивает полиморфное поведение:

# ...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, состоит из:

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:

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 (что, разумеется, уместно для их области).

Ресурсы

• Скачайте Питоновскую реализацию Prolog PyLog.
• Скачайте модуль SimpleParse с SourceForge.
• Прочтите статьи Дэвида о SimpleParse и Spark опубликованные в рубрике developerWorks: "Разбор с модулем SimpleParse" ("Parsing with the SimpleParse module") и "Грамматический разбор с использованием модуля Spark" ("Parsing with the Spark module").
• Узнайте больше о gnosis.xml.validity из статьи Дэвида "Вопросы XML: Реализация допустимости с библиотекой gnosis.xml.validity" ("XML Matters: Enforcing validity with the gnosis.xml.validity library").
• Дэвид также рассматривает SimpleParse и PLY в черновом варианте своей будущей книги "Текстовая обработка в Python" (Text Processing in Python).
• Познакомьтесь с современной точкой зрения о Расширенной форме Бэкуса - Наура (Extended Backus-Naur Form), заглянув на O'Reilly's xml.com, и с более классическим взглядом по этому вопросу в Бесплатном он-лайн словаре по вычислительной технике (The Free On-Line Dictionary of Computing, Foldoc).
• Совсем позабыли о Prolog? Откройте заново его чудеса и радости на GNU Prolog (текущая версия 1.2.16). Никогда не слышали о Prolog? Сначала прочтите определение Foldoc, а затем направляйтесь в пункт "скачать".
• Выясните все об языках, которые упоминались в этой и других статьях, изучив страницу "Языки программирования", принадлежащую Гансу-Вольфгангу Лоидлю (Hans-Wolfgang Loidl) из Мюнхенского университета.
• Познакомьтесь с xmlproc: бесплатный валидирующий парсер xml, написанный на Python. Углубите свои знания о парсерах: валидирующих и невалидирующих - в виртуальной библиотеке Web Developer.
• Прочтите другие статьи Дэвида, опубликованные на developerWorks:
  • "Руководство по интроспекции в Python" (Guide to Python introspection)^[1];
  ;
  • "Функциональное программирование на языке Python" ("Functional programming in Python, Part 1");
  • "Еще о функциональном программировании на Python" ("Functional programming in Python, Part 2").
• Ресурсы для разработчиков Linux в зоне Linux developerWorks.