CAL Актерский язык - CAL Actor Language

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

CAL (в Cal Актерский язык) это язык программирования высокого уровня[1] для записи (поток данных ) актеры, которые являются операторами с сохранением состояния, которые преобразуют входные потоки объектов данных (токенов) в выходные потоки. CAL была скомпилирована для различных целевых платформ, включая одноядерные процессоры, многоядерные процессоры и программируемые оборудование. Он использовался в нескольких областях применения, в том числе видео и обработка, сжатие и криптография. В MPEG Реконфигурируемое кодирование видео (РВК)[2] рабочая группа приняла CAL как часть своих усилий по стандартизации.

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

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

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

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

CAL особенности

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

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

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

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

Поэтому шаблоны ввода делают следующее:

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

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

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

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

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

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

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

Охраняемые действия

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

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

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

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

Актеры с государством

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

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

Расписания

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

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

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

Приоритеты

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

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

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

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

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

Выражения

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

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

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

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

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

Заявления

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

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

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

Действие

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

Вспомогательные инструменты

Фреймворк OpenDF

Открытый компилятор RVC-CAL

использованная литература

  1. ^ Отчет о языке CAL: спецификация языка исполнителя CAL, Йохан Экер и Йорн В. Яннек, Технический меморандум № UCB / ERL M03 / 48, Калифорнийский университет, Беркли, Калифорния, 94720, США, 1 декабря 2003 г.
  2. ^ Обзор реконфигурируемой инфраструктуры кодирования видео MPEG, Шувра С. Бхаттачарья, Йохан Экер, Йорн В. Яннек, Кристоф Лукарц, Марко Маттавелли, Микаэль Раулет, Журнал систем обработки сигналов, 2009, Springer

внешние ссылки