Язык актера CAL

Язык актера CAL

Парадигма	Поток данных
Впервые появился	2001
Платформа	Независимый от платформы
Расширения имен файлов	.cal, .xdf
Основные реализации
Открытый компилятор RVC-CAL , платформа OpenDF

CAL ( Cal Actor Language ) — язык программирования высокого уровня. для записи ( dataflow ) акторов , которые представляют собой операторы с состоянием, преобразующие входные потоки объектов данных (токенов) в выходные потоки. Клиентская лицензия CAL скомпилирована для различных целевых платформ, включая одноядерные процессоры, многоядерные процессоры и программируемое оборудование . Он использовался в нескольких областях применения, включая видео и обработку, сжатие и криптографию . MPEG ) Реконфигурируемое кодирование видео (RVC рабочая группа приняла CAL в рамках своих усилий по стандартизации.

История и введение

Язык актеров CAL был разработан в 2001 году в рамках проекта Ptolemy II в Калифорнийском университете в Беркли . CAL — это язык потока данных, ориентированный на различные области приложений, такие как обработка мультимедиа, системы управления, сетевая обработка и т. д.

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

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

Возможности клиентской лицензии

Состав актеров

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

• 1. актор может потреблять токены из своих входных портов,
• 2. он может изменить свое внутреннее состояние,
• 3. он может создавать токены на своих выходных портах.

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

Таким образом, шаблоны ввода выполняют следующие действия:

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

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

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

Недетерминизм

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

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

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

Защищенные действия

Предложение защиты действия содержит ряд выражений, все из которых должны быть истинными, чтобы действие можно было запустить. и в этом случае он будет отправлен на выход P. Чтобы первое действие было активным, входящий токен должен быть больше или равен нулю , В противном случае это действие не может сработать. И наоборот, чтобы второе действие было активным, токен должен быть меньше нуля, и в этом случае он отправляется на выход N. Запуск этого актера может выглядеть следующим образом: Актер может столкнуться с проблемой, если он когда-либо столкнется с нулевой токен, потому что ни одно из его действий не сможет сработать на нем.

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

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

Актер Select ниже — еще один пример использования защищенных действий. Он похож на актера NDMerge в том смысле, что он объединяет два потока (те, которые приходят на его входные порты A и B). Однако он делает это в соответствии с (логическими) значениями токенов, поступающих на его S. входной порт

Действующие лица с государством

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

Обратите внимание, что Select и IterSelect почти, но не полностью эквивалентны. Прежде всего, IterSelect делает в два раза больше шагов, чтобы обработать одинаковое количество токенов. доступен ли соответствующий токен данных на A или B. Во-вторых, он фактически считывает и, следовательно, потребляет входной токен S независимо от того ,

Расписания

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

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

Каждый переход состояний состоит из трех частей: исходное состояние, список тегов действий и следующее состояние. Стоит отметить, что количество действий увеличилось — вместо первоначальных трех в новой версии с расписанием теперь четыре действия. Причина в том, что действие больше не может напрямую назначать состояние-преемник, как это было в оригинале, где в зависимости от значения состояния чтения токена присваивалось либо значение 1, либо 2. В версии с расписанием это Модификация состояния неявно заложена в структуру конечного автомата и происходит в зависимости от того, какое действие срабатывает. Соответственно, условие, проверяющее значение токена, переместилось из тела действия в защиту двух действий с тегами readT и readF .

Приоритеты

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

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

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

Заявления и выражения

Предыдущая глава была сосредоточена главным образом на тех конструкциях CAL, которые связаны с концепциями, специфичными для актеров, — ввод и вывод токенов, действия, управление выбором действий и т. д. В этом разделе обсуждаются более «пешеходные» части CAL, операторы и выражения, используемые для манипулирования объектами данных и выражения (последовательных) алгоритмов. Эта часть языка похожа на то, что можно найти во многих процедурных языках программирования (таких как C , Pascal , Java , Ada ), поэтому мы сосредоточимся на областях, которые могут немного отличаться в CAL.

Выражения

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

Атомарные выражения

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

Простые составные выражения

CAL предоставляет операторы двух типов для построения выражений: унарные и двоичные . Унарный оператор в CAL всегда является префиксным оператором, т. е. он появляется перед своим единственным операндом. Бинарный оператор возникает между двумя операндами.

Заявления

В некотором смысле операторы в CAL являются полной противоположностью выражений: они не имеют «возвращаемого значения», но могут изменять значения переменных. Действительно, в изменении значений переменных и заключается весь смысл операторов. Операторы выполняются в строгом последовательном порядке, и, если не указано иное, выполнение операторов продолжается в том порядке, в котором они появляются в тексте программы, а это означает, что любые изменения переменных, производимые оператором, могут повлиять на выполнение последующих операторов.

Поток управления

Как и в большинстве других языков программирования, существуют конструкции для управления порядком выполнения операторов в программе. Часть этого цикла, которая следует непосредственно за ключевым словом ' foreach, представляет собой генератор, очень похожий на генератор списков.

Действие

• Шаблоны ввода: объявление переменных
• Охрана: определение благоприятных условий
• Выходные выражения: вычисление выходных токенов
• Тело: изменение состояния актера