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

К сожалению, на практике воспользоваться преимуществами сопрограмм проблематично, поскольку традиционные языки программирования высокого уровня не обеспечивают поддержки этой концепции (причина объясняется в данной статье). Те, кто все же желает иметь такую возможность, вынуждены самостоятельно искать способ ее реализации. Например, мне доводилось писать на ассемблере модули для компилятора Pascal-2 от Oregon Software (для PDP-11), которые производили соответствующие манипуляции со стеком, подменяя адрес возврата из подпрограммы. Но подобные решения сильно привязаны к конкретным архитектурам ЭВМ и компиляторам и больше напоминают хакерские заплатки, нежели промышленное программирование.

Автору статьи, известному программисту Саймону Тэтхему, удалось найти гораздо более удачное решение, не выходящее за рамки ANSI C и по этой причине обладающее превосходной мобильностью на разные компиляторы и платформы. Причем это решение не сводится лишь к теоретическим выкладкам; оно чрезвычайно практично — автор разработал набор макросов C, собранных воедино в заголовочном файле. Читателю остается лишь скачать их и применять в своих разработках.

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

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

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

Каждый из этих фрагментов кода весьма прост и легок для понимания. Один производит литеры по одной вызовом emit(); другой потребляет литеры по одной вызовом getchar(). Если для взаимного обмена данными использовать только вызовы emit() и getchar(), легко соединить эти два фрагмента вместе таким образом, чтобы выход декомпрессора отправлялся прямо на вход парсера.

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

В данной статье я предлагаю креативное решение проблем со структурами подобного рода.

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

Разумеется, вы не должны переписывать оба фрагмента сразу; достаточно будет любого одного. Если вы перепишете декомпрессор так, чтобы он при каждом вызове возвращал одну литеру, как было показано, тогда исходный парсер может заменять вызовы getchar() вызовами decompressor(), и этого будет достаточно для счастья. Соответственно, если вы перепишете парсер так, чтобы он вызывался для каждой входной литеры, тогда исходный декомпрессор без проблем сможет вызывать parser() вместо emit(). Конечно, если вы мазохист, вы можете переписать обе эти функции как вызываемые...

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

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

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

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

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

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

Как это реализовать? Мы можем передать управление в произвольную точку функции с использованием оператора goto. Если у нас есть переменная состояния, мы можем сделать так:

Этот подход работает. У нас есть набор меток в тех точках, с которых нам может понадобиться продолжить выполнение: одна в начале, другая — после каждого оператора возврата. Имеется переменная состояния, сохраняемая между вызовами функции, которая говорит, с какой метки следует продолжить выполнение в следующий раз. Перед каждым возвратом мы обновляем переменную состояния таким образом, чтобы она указывала на правильную метку; после каждого вызова мы выясняем, куда следует перейти, в зависимости от значения этой переменной.

Впрочем, выглядит все это по-прежнему ужасно. Хуже всего здесь то, что набор меток нужно поддерживать вручную, и он должен быть согласован с начальным оператором switch. Каждый раз, когда мы добавляем новый оператор возврата, мы должны придумывать имя новой метки и добавить ее в список switch; каждый раз, когда мы удаляем оператор возврата, мы должны удалить соответствующую метку. Мы фактически увеличили трудоемкость сопровождения программы вдвое.

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

Мы можем воспользоваться этим несколько по-другому в нашем трюке с сопрограммой. Вместо того, чтобы использовать оператор switch для определения, какой из операторов goto следует выполнить, мы можем воспользоваться оператором switch для выполнения самого перехода:

Это уже выглядит многообещающе. Все, что нам теперь нужно сделать, — это составить несколько тщательно отобранных макросов, и мы сможем спрятать неприглядные детали за чем-то более благовидным:

Это уже почти то, что нам нужно. Мы можем использовать crReturn для возврата из функции таким образом, что при следующем вызове выполнение продолжится с точки, следующей за возвратом. Разумеется, мы должны придерживаться нескольких базовых правил (окружать тело функции макросами crBegin и crFinish; объявлять все локальные переменные статическими, если они должны сохранять значения после crReturn; никогда не помещать crReturn внутрь явного оператора switch). Но это все не так уж сильно нас ограничивает.

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

Впрочем, это тоже решаемо. ANSI C предоставляет специальный макрос __LINE__, который раскрывается в номер текущей строки. Теперь мы можем переписать crReturn так:

Теперь, когда у нас есть все необходимое, перепишем наши исходные фрагменты.

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

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

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

Мы получили то, к чему и стремились: переносимые средства ANSI C для передачи данных между поставщиком и потребителем без необходимости их явного переписывания как конечные автоматы. Мы добились этого, скомбинировав препроцессор C с малоиспользуемыми возможностями оператора switch для создания неявного конечного автомата.

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

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

Посмотрим. Функция, построенная из маленьких блоков вида

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

Стандарты кодирования призваны способствовать ясности. За сокрытие жизненно важных вещей вроде операторов switch, return и case внутри таинственных макросов стандарты кодирования обвинят вас в затуманивании синтаксической структуры программы и нарушения требований ясности. Но вы сделали это намеренно для того, чтобы подчеркнуть алгоритмическую структуру программы, а ведь именно она представляет наибольший интерес для читателя!

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

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

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

Это выглядит немного неуклюже, поскольку в качестве счетчика цикла вам теперь вдруг требуется использовать ctx->i там, где раньше вы использовали бы просто i; фактически все значимые переменные становятся элементами структуры контекста сопрограммы. Однако это устраняет проблемы с реентерабельностью и при этом не влияет на структуру программы.

(Разумеется, если бы C имел оператор with, как в Pascal'е, мы могли бы оформить макрос так, чтобы сделать этот уровень косвенности полностью прозрачным. Досадно. Впрочем, пользователи C++ могут сделать сопрограмму членом класса и хранить ее локальные переменные в этом классе.)

К статье приложен заголовочный файл C, который реализует этот фокус с сопрограммами в виде набора предопределенных макросов. В файле определены два набора макросов с префиксами scr и ccr. Макрос scr сделан по упрощенной технологии для случаев, когда вы можете обойтись статическими переменными; макросы ccr представляет более совершенную реентерабельную форму. Полная документация приведена в комментариях в самом файле заголовка.

(Файл заголовка распространяется по лицензии MIT, так что вы можете использовать его по своему усмотрению без ограничений. Если вы найдете что-нибудь, чего лицензия MIT не позволяет вам делать, напишите мне, и я, возможно, дам вам явное разрешение сделать это.)

Вы можете скачать файл coroutine.h по этой ссылке.

Спасибо за то, что прочли эту статью. Делитесь ей с другими и получайте удовольствие!

Обновлено 2005-03-07: Том Дафф подтвердил это в комментарии своем блоге. «Грязный способ использования операторов switch для реализации конечного автомата, управляемого прерываниями», о котором он говорит в своем начальном письме, — на самом деле тот самый трюк, который я описал здесь.

PuTTY — это клиент Telnet и SSH для Win32. Код протокола SSH содержит реальный пример использования данного трюка с сопрограммами. Насколько мне известно, это самое злостное хакерство на C, когда-либо примененное в серьезном промышленном коде.