- 31 декабря 2001 г.
Основанные на генераторах конечные автоматы и сопрограммы
Мы возобновляем рубрику "Язык программирования Python" и предлагаем вашему вниманию две статьи хорошо знакомого нам Дэвида Мертца. В первой статье речь пойдет о конечных автоматах и сопрограммах, по образному выражению самого автора, "экзотическом" механизме управления потоками данных.
Простые генераторы, которые были представлены в Python 2.2, могут использоваться для упрощения конечных автоматов (state machines) и моделирования сопрограмм. В одной из предыдущих статей была представлена абстрактная модель обработки с помощью конечного автомата. С этого момента введение простых генераторов предоставило еще больше естественных парадигм для описания автоматов. Сопрограммы - это "экзотический" механизм управления потоками данных, который возможен в очень немногих из широко используемых языков (даже в Python, который не является Stackless). Однако, новые генераторы Python подводят нас почти прямо к сопрограммам; оставшиеся несколько шагов можно сэмулировать. Объяснение соответствующих понятий сопровождается примерами кода.
Что такое Python?
Python - свободно доступный, интерпретируемый язык программирования высокого уровня, разработанный Гвидо ван Россумом (Guido van Rossum). Он объединяет ясный синтаксис с мощной (но необязательно) объектно-ориентированной семантикой. Python может быть установлен на любой платформе и обеспечивает прекрасную совместимость при переходе с одной платформы на другую.
Введение
Чтобы овладеть новыми генераторами Python 2.2, требуется некоторое время. Даже написав статью о простых генераторах, я не мог утверждать, что полностью понимаю их суть. В этой статье представлены некоторые дополнительные модели для использования генераторов, и я надеюсь, что мы с читателями постигнем мышление "возобновляемых функций" (resumable functions).
Простые генераторы очень полезны. Помимо того, что они предлагают более естественные пути выражения потока управления для определенного класса задач, генераторы позволяют решать многие задачи значительно эффективнее. На Python вызов функции довольно дорог; среди прочих факторов, нужно время для обработки списка аргументов функции (в частности, необходимо анализировать позиционные параметры и параметры по умолчанию). К тому же, инициализация объекта кадра занимает несколько установочных шагов (по словам Тима Питерса [Tim Peters] на comp.lang.python, более 100 строк на С; сам я не изучал исходники Python). Возобновление генератора, с другой стороны, весьма дешево; аргументы уже проанализированы, а объект кадра просто ожидает возобновления (практически не нужно дополнительной инициализации). Разумеется, если скорость столь важна, не следует использовать динамический язык, транслируемый в байткод; но даже если скорость не главное, быстрее - лучше, чем медленнее.
Пересматривая конечные автоматы
В статье о конечных автоматах я ввел класс 'StateMachine', который позволял пользователям добавлять столько обработчиков состояния, сколько требуется для данного автомата. В этой модели одно или несколько состояний определяются как конечные состояния, и единственное состояние - как начальное (это можно сконфигурировать, вызывая методы класса). Каждый обработчик располагал определенной требуемой структурой; обработчик выполнял ряд действий, затем возвращался в цикл в метод 'StateMachine .run()' с признаком, показывающим следующее требуемое состояние. Также, использовалась переменная 'cargo', чтобы одно состояние могло передавать некоторую (необработанную) информацию в следующее состояние.
Типичным применением представленного мною класса 'StateMachine' была бы обработка входных данных с помощью состояний. Например, средство обработки текста (Txt2Html), который я использую, читает строки из файла; каждая строка должна быть обработана особым образом, в зависимости от того, к какой категории она принадлежит. Однако, часто требуется взглянуть на контекст, обеспечиваемый непосредственно предшествующими строками, чтобы определить, к какой категории относится текущая строка (и как ее необходимо обрабатывать). Реализация этого процесса, построенного вокруг класса 'StateMachine', могла бы определить обработчик 'A', который некоторое время читает строки и обрабатывает их в 'А'-образной манере. Через некоторое время выполняется условие, согласно которому следующая группа строк должна обрабатываться обработчиком 'B'. 'A' передает управление обратно в цикл '.run()' с указанием на переход в состояние 'B' - вместе с любой дополнительной строкой (строками), которую 'A' не смог обработать надлежащим образом, а 'B' должен, перед тем, как прочитать дополнительные строки. В конце концов, какой-то обработчик передает свое управление в некоторое состояние, которое установлено как конечное, и обработка останавливается.
Для конкретного образца кода, приведенного в предыдущей статье, я использовал упрощенное приложение. Вместо обработки строк я обрабатывал поток чисел, которые были произведены итерационной функцией. Каждый обработчик состояния просто выводил те числа, которые были в пределах желаемого числового диапазона (вместе с сообщениями о рабочем состоянии). Когда число в этом потоке передавалось в отличный диапазон, другой обработчик принимал "обработку". В данной статье мы рассмотрим другой способ реализации обработки этого же числового потока с помощью генераторов (с некоторыми дополнительными возможностями и нововведениями). Однако, более сложный генератор, вероятно, имел бы дело с чем-нибудь более похожим на входные потоки, о которых упоминалось в предыдущем параграфе. Стоит вернуться к прыдыдущей версии конечного автомата, вот сокращенная версия его кода:
# File: statemachine_test.py #
from statemachine import StateMachine
def ones_counter(val):
print "ONES State: ",
while 1:
if val <= 0 or val >=
30:
newState
= "Out_of_Range" ; break
elif 20 <= val < 30:
newState
= "TWENTIES"; break
elif 10 <= val < 20:
newState
= "TENS"; break
else:
print "
@ %2.1f+" % val,
val = math_func(val)
print " >>"
return (newState, val)
# ... other handlers ...
def math_func(n):
from math import sin
return abs(sin(n))*31
if __name__== "__main__":
m = StateMachine()
m.add_state("ONES", ones_counter)
m.add_state("TENS", tens_counter)
m.add_state("TWENTIES", twenties_counter)
m.add_state("OUT_OF_RANGE", None, end_state=1)
m.set_start("ONES")
m.run(1)За более подробной информацией о импортируемом классе 'StateMachine' и о работе его методов обращайтесь к предыдущей статье.
Использование генераторов
Полная версия нашего конечного автомата, основанная на генераторе, несколько длиннее примеров, которые я обычно привожу в статьях. Однако, приведенный ниже пример является целым приложением, не требующим для поддержки отдельно импортируемого модуля statemachine. В целом, эта версия короче версии, основанной на классе (и мы увидим, что она делает дополнительно кое-что очень мощное).
# File: stategen_test.py #
from __future__ import generators
import sys
def math_gen(n): # Iterative function becomes a generator
from math import sin
while 1:
yield n
n = abs(sin(n))*31
# Jump targets not state-sensitive, only to simplify example
def jump_to(val):
if 0 <= val < 10: return 'ONES'
elif 10 <= val < 20: return 'TENS'
elif 20 <= val < 30: return 'TWENTIES'
else: return 'OUT_OF_RANGE'
def get_ones(iter):
global cargo
while 1:
print "\nONES State: ",
while
jump_to(cargo)=='ONES':
print
"@ %2.1f " % cargo,
cargo =
iter.next()
yield (jump_to(cargo),
cargo)
def get_tens(iter):
global cargo
while 1:
print "\nTENS State: ",
while
jump_to(cargo)=='TENS':
print
"#%2.1f " % cargo,
cargo =
iter.next()
yield (jump_to(cargo),
cargo)
def get_twenties(iter):
global cargo
while 1:
print "\nTWENTIES State: ",
while
jump_to(cargo)=='TWENTIES':
print
"*%2.1f " % cargo,
cargo =
iter.next()
yield (jump_to(cargo),
cargo)
def exit(iter):
jump = raw_input('\n\n[co-routine for jump?]
').upper()
print "...Jumping into middle of", jump
yield (jump, iter.next())
print "\nExiting from exit()..."
sys.exit()
def scheduler(gendct, start):
global cargo
coroutine = start
while 1:
(coroutine, cargo) =
gendct[coroutine].next()
if __name__ == "__main__":
num_stream = math_gen(1)
cargo = num_stream.next()
gendct = {'ONES' : get_ones(num_stream),
'TENS'
: get_tens(num_stream),
'TWENTIES'
: get_twenties(num_stream),
'OUT_OF_RANGE':
exit(num_stream) }
scheduler(gendct, jump_to(cargo))
Стоит сделать несколько замечаний касательно наших конечных автоматов, основанных на генераторах. Первое - скорее внешнего характера. Мы создали 'stategen_test.py' так, чтобы использовать только функции, а не классы - генераторы, по крайней мере на мой взгляд, воспринимаются гораздо более в контексте функционального, а не объектно-ориентированного программирования. Но при желании можно было бы легко обернуть эту же общую модель в один или несколько классов.
Основная функция в нашем примере - 'scheduler()', которая является весьма общей, будучи значительно короче, чем класс 'StateMachine' в предыдущей модели. Функция 'scheduler()' требует в качестве аргумента словарь объектов генератора-итератора ("воплощенные" генераторы). Строковые имена, даваемые каждому генератору, могут быть какими угодно; литеральные имена генераторных функций - очевидный выбор, но я использовал в этом примере для имен заглавные буквы. Функция 'scheduler()' принимает также в качестве аргумента "начальное состояние", хотя, возможно, при желании значение по умолчанию можно было бы выбирать автоматически.
Каждый "запланированный" генератор подчиняется простым соглашениям. Каждый генератор работает некоторое время, затем выдает пару, которая содержит желаемую команду перехода (jump) и некоторое "содержимое" ("cargo") - точно так, как в предыдущей модели. Ни один генератор не помечается специально как "конечное состояние". Взамен мы позволяем каждому генератору возбудить исключение, чтобы выйти из 'scheduler()', а именно: генератор возбудит исключение 'StopIteration', если этот генератор выполнится до конца или доберется до оператора 'return'. Это, или любое другое, исключение при желании можно легко перехватить. В нашем случае, чтобы завершить приложение, мы используем 'sys.exit()' в коде генератора 'exit()'.
Еще два замечания по этому коду. Вместо итерационной функции для генерации числовой последовательности в приведенном выше примере используется гораздо более очевидный циклический генератор. Этому генератору не нужно постоянно передавать обратно "последнее значение", он просто выдает (бесконечный/произвольный) поток чисел при каждом последующем вызове. Это чудесная, хотя и скромная иллюстрация генератора. Пример также выделяет таблицу переходов из состояния в состояние в отдельную функцию. В реальной программе команды перехода из одного состояния в другое (state transition jumps) были бы более зависимыми от контекста и, вероятно, определялись бы в коде генераторов. Этот подход упрощает данный пример. Если бы стоило, мы могли бы сделать его еще проще, синтезировав функции генератора из одной фабрики функций; но в общем случае каждый генератор не настолько похож на остальные, чтобы это было выполнимо.
Сопрограммы и полусопрограммы
Внимательные читатели должны заметить, что мы невольно забрались в более мощные структуры управления потоками данных, чем предполагалось в начале. В приведенном примере присутствует нечто большее, чем просто конечный автомат. Приведенная выше модель, в сущности, общая система для сопрограмм. Большинству читателей, возможно, потребуются немного исходной информации.
Сопрограмма - это набор программной функциональности, который допускает произвольное ветвление в другие контексты управления и произвольное возобновление потока из точки ветвления. Подпрограммы, распространенные во многих языках программирования, являются исключительно ограниченным частным случаем общих сопрограмм. В подпрограмму входят только из фиксированной точки наверху, и выходят только один раз (ее невозможно возобновить). Также, подпрограмма всегда передает управление обратно в вызывающую процедуру. В сущности, каждая сопрограмма представляет вызываемое продолжение (continuation), хотя добавление нового слова необязательно вносит ясность для того, кто его не знает. Иллюстрация, приведенная в "Искусстве компоновки" ("The Art of Assembly") Рэндала Хайда (Randall Hyde), играет существенную роль в объяснении сопрограмм:
Рис. 1. Две сопрограммы в действии
Посмотрите ресурсы в общей дискуссии Хайда, она хороша. Несмотря на отрицательные ассоциации, можно заметить, что пресловутый оператор 'goto' также во многих языках допускает произвольное ветвление, хотя и в менее структурированном контексте, приводящем к коду в стиле "блюда спагетти".
Генераторы Python 2.2+ делают большой шаг на пути к сопрограммам. То есть, генераторы - в отличие от функций/подпрограмм - возобновляемы и могут выдавать значения посреди многочисленных вызовов. Однако, генераторы Python - это всего лишь то, что Дональд Кнут (Donald Knuth) описывает как "полусопрограммы". Генератор возобновляем передавать управление где угодно - но он может выполнить ветвление только обратно в непосредственный контекст вызова. Точнее, контекст генератора (как любой контекст) может сам вызывать другие генераторы или функции - и даже рекурсивно сам себя - но каждый конечный возврат должен пройти через линейную иерархию контекстов возврата. Генераторы Python не предусматривают обычное сопрограммное использование "Производителей" ("Producers") и "Потребителей" ("Consumers"), которые свободно возобновляются в середине друг друга.
К счастью, полнофункциональные сопрограммы довольно легко моделируются генераторами Python. Элементарный способ - функция 'scheduler()', точно такая же, как в вышеприведенном примере. Фактически, конечные автоматы являются гораздо более общей моделью структуры сопрограмм. Адаптация к этой модели преодолевает незначительные ограничения, все еще присутствующие в генераторах Python (и предоставляет неосторожным программистам всю мощь спагетти кода).
Код stategen в действии
Чтобы точно понять, что происходит в коде 'stategen_test.py', проще всего запустить его:
# Running STATEGEN (with manual jump control) #
% python stategen_test.py
ONES State: @ 1.0
TWENTIES State: *26.1 *25.3
ONES State: @ 4.2
TWENTIES State: *26.4 *29.5 *28.8
TENS State: #15.2 #16.3 #16.0
ONES State: @ 9.5 @ 3.8
TENS State: #18.2 #17.9
TWENTIES State: *24.4
TENS State: #19.6
TWENTIES State: *21.4
TENS State: #16.1 #12.3
ONES State: @ 9.2 @ 6.5 @ 5.7
TENS State: #16.7
TWENTIES State: *26.4 *30.0
[co-routine for jump?] twenties
...Jumping into middle of TWENTIES
TWENTIES State:
TENS State: #19.9
TWENTIES State: *26.4 *29.4 *27.5 *22.7
TENS State: #19.9
TWENTIES State: *26.2 *26.8
Exiting from exit()...
Эти выходные данные в основном подобны рассмотренным ранее в 'statemachine_test.py'. Каждая строка результатов представляет поток управления, проведенный в одном отдельном обработчике состояния или генераторе; контекст потока объявляется в начале строки. Однако, вместо того, чтобы просто снова *вызывать* функцию обработчика, эта версия генератора *возобновляет* исполнение (в пределах цикла) всякий раз, когда другая сопрограмма передает в нее управление. При условии, что тела всех сопрограмм 'get_*()' целиком содержатся в бесконечных циклах, эта различие менее очевидно.
Чтобы понять, что по сути отлично в 'stategen_test.py', посмотрите, что происходит в генераторе 'exit()'. При первом вызове этого генератора-итератора адресат перехода получается от пользователя (что является простым случаем событийно-управляемого ветвления, которое может использовать реальное приложение). Однако, когда 'exit()' вызывается во второй раз, он находится в более поздней точке контекста управления - выводится сообщение о выходе и вызывается 'sys.exit()'. Пользователь в примере мог бы также перейти прямо в "out_of_range", который вышел бы, не переходя к другому обработчику (но выполнил бы рекурсивный переход в тот же самый генератор).
Заключение
Как я дал понять во введении, я ожидаю, что моя сопрограммная версия конечного автомата работает значительно быстрее, чем представленная ранее версия на классе с обратными вызовами. Возобновление генератора-итератора будет особенно эффективно. Этот отдельный пример настолько прост, что его производительность вряд ли стоит тестировать, но я буду рад читательским откликам с конкретными результатами.
Но любое ускорение, которое может быть достигнуто с помощью представляемой мною "модели сопрограмм", затмевается поразительно общими управляющими структурами, которые она предоставляет. Некоторые читатели в конференции comp.lang.python интересовались, насколько общими являются новые генераторы Python. Мне кажется, что доступность описанной структуры определяет ответ: "настолько общие, насколько можно пожелать"! И, как и большинство питоновских штучек, их обычно гораздо проще программировать, чем понимать . Попробуйте мою модель; думаю, вы найдете ее полезной.
Ресурсы
В начале этой статьи я представил абстрактную модель для широкого класса конечных автоматов на Python. Эта идея - пробный камень, опираясь на который я объясняю следующие понятия:
http://www-106.ibm.com/developerworks/library/python-state.html
В интервью с создателем Stackless Python Кристианом Тисмером (Christian Tismer) мы кратко коснулись сопрограмм, а также других экзотических управляющих структур, таких как продолжения, микронити и генераторы. До того, как в Python 2.2 были введены генераторы, некоторые из этих вопросов были освещены в этой статье:
http://www-106.ibm.com/developerworks/library/l-pyth7.html
Самый свежий и близкий материал - моя попытка в альфа-период Python 2.2 ввести итераторы и простые генераторы:
http://www-106.ibm.com/developerworks/library/l-pycon.html
В некоторых статьях рассказывается о функциональном программировании на Python. При условии наличия некоторого ощущения генераторов с точки зрения функционального программирования стоит взглянуть на эти статьи:
http://www-106.ibm.com/developerworks/linux/library/l-prog.html
http://www-106.ibm.com/developerworks/linux/library/l-prog2.html
http://www-106.ibm.com/developerworks/linux/library/l-prog3.html
В "Искусстве компоновки" Рэндала Хайда также содержится введение в сопрограммы (даже для Компоновки):
http://webster.cs.ucr.edu/Page_asm/ArtofAssembly/ch19/CH19-6.html#HEADING6-1
Об авторе
Подобно Ницше, Дэвид хотел бы написать, что это - размышления старого филолога, но это была бы явная ложь. Однако, возможно, его (безвозмездно продвигаемая прямо здесь) ожидаемая книга "Текстовая обработка в Python" (Text Processing in Python) будет когда-нибудь ошибочно принята за кибернетический вариант филологии. Дэйвид доступен по адресу: mertz@gnosis.cx, а жизнь его описана на http://gnosis.cx/publish/. Присылайте свои замечания и предложения касательно этой, прошлых или будущих статей.
Автор: Дэвид Мертц (David Mertz), Functor, Gnosis Software, Inc