Рекурсия

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

Рассмотрим простой долговечный объект — часы, функционирование которых состоит в том, чтобы тикать.

aЧАСЫ = {тик}.

Теперь рассмотрим объект, который вначале издает единственный «тик», а затем ведет себя в точности как ЧАСЫ

(тик ЧАСЫ).

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

ЧАСЫ = (тик ЧАСЫ).

Это уравнение можно развертывать простой заменой в правой части уравнения члена ЧАСЫ на равное ему выражение (тик ЧАСЫ) столько раз, сколько нужно, при этом возможность для дальнейшего развертывания сохраняется. Мы эффективно описали потенциально бесконечное поведение объекта ЧАСЫ, как

тик тик тик …

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

Утверждение 3.1.Если F(Х) — предваренное выражение, содержащее имя процесса X, а V — алфавит X, то уравнение Х = F(Х) имеет единственное решение в алфавите V.

Иногда обозначают это решение выражением

mХ: V.F(Х).

Пример 3.2.Простой торговый автомат, полностью удовлетворяющий спрос на шоколадки:

ТАП = (мон (шок ТАП)).

Решение этого уравнения может быть записано в виде:

ТАП = mХ: {мон, шок}.(мон (шок X)).

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

Выбор

Используя префиксы и рекурсию, можно описывать объекты, обладающие только одной возможной линией поведения. Однако поведение многих объектов зависит от окружающей их обстановки. Например, торговый автомат может иметь различные щели для 1- и 2-пенсовых монет; выбор одного из двух событий в этом случае предоставлен покупателю.

Если х и y - различные события, то (х P | у Q) описывает объект, который сначала участвует в одном из событий x, у, где a(х P | у Q) = aP,x, y aР и aР = aQ. Последующее же поведение объекта описывается процессом Р, если первым произошло событие х, или Q, если первым произошло событие y.

Пример 3.3. Процесс копирования состоит из следующих событий:

вв.0 — считывание нуля из входного канала,

вв.1 — считывание единицы из входного канала,

выв.0 — запись нуля в выходной канал,

выв.1 — запись единицы в выходной канал.

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

КОПИБИТ=mХ: (вв.0 выв.0 X | вв.1 выв.1 X).

Определение выбора легко обобщить на случай более чем двух альтернатив. В общем случае если В - некоторое множество событий, а Р(х) - выражение, определяющее процесс для всех различных х из В, то запись (х: В Р(х)) определяет процесс, который сначала предлагает на выбор любое событие у из В, а затем ведет себя как Р(у).