CAL ( Cal Actor Language ) es un lenguaje de programación de alto nivel [1] para escribir actores ( de flujo de datos ) , que son operadores con estado que transforman flujos de entrada de objetos de datos (tokens) en flujos de salida. CAL se ha compilado para una variedad de plataformas de destino, incluidos procesadores de un solo núcleo, procesadores multinúcleo y hardware programable . Se ha utilizado en varias áreas de aplicación, incluido el video y el procesamiento, la compresión y la criptografía . El grupo de trabajo MPEG Reconfigurable Video Coding (RVC) [2] ha adoptado CAL como parte de sus esfuerzos de estandarización.
El lenguaje de actores CAL se desarrolló en 2001 como parte del proyecto Ptolemy II en la Universidad de California en Berkeley . CAL es un lenguaje de flujo de datos orientado a una variedad de dominios de aplicación, como procesamiento multimedia, sistemas de control, procesamiento de redes , etc.
Otra razón común para elegir un flujo de datos es que el objetivo es una implementación paralela eficiente que sería difícil o imposible de lograr utilizando un lenguaje de programación secuencial. Los lenguajes secuenciales son notoriamente difíciles de paralelizar en general, por lo que las implementaciones paralelas eficientes generalmente requerirán una guía significativa por parte del usuario. Un programa de flujo de datos CAL proporciona abstracciones simples, comprensibles y poderosas que permiten la especificación de tanto o tan poco paralelismo como sea necesario, lo que permite que las herramientas produzcan implementaciones sofisticadas que aprovechen la estructura concurrente de un cálculo.
Al programar en flujo de datos, el programador generalmente construye una descripción concurrente de un sistema computacional, que es diferente de un programa secuencial común. En lugar de preocuparse por la ejecución paso a paso de un algoritmo , un programador de flujo de datos construye un sistema de entidades que se comunican de manera asincrónica llamadas actores. Gran parte del esfuerzo de programación se dirige a encontrar una buena factorización del problema en actores y a diseñar patrones de comunicación apropiados entre esos actores.
Los actores realizan sus cálculos en una secuencia de pasos denominados disparos. En cada uno de esos pasos:
En consecuencia, describir un actor implica describir su interfaz con el exterior, los puertos, la estructura de su estado interno, así como los pasos que puede realizar, lo que hacen estos pasos (en términos de producción y consumo de tokens y la actualización del estado del actor) y cómo elegir el paso que el actor realizará a continuación. Esta sección analiza algunas de las construcciones en el lenguaje CAL que tratan estos temas. Las acciones describen las cosas que suceden durante un paso que realiza un actor. De hecho, es preciso decir que un paso consiste en ejecutar una acción. Recordemos que cuando un actor realiza un paso, puede consumir tokens de entrada y producir tokens de salida.
Por lo tanto, los patrones de entrada hacen lo siguiente:
El lado de salida de una acción es un poco más simple: las expresiones de salida simplemente definen la cantidad y los valores de los tokens de salida que se producirán en cada puerto de salida con cada activación de la acción. Es permisible omitir la denominación explícita del puerto al que se aplica un patrón de entrada o una expresión de salida si una acción proporciona tantos patrones de entrada como puertos de entrada o expresiones de salida como puertos de salida. En tal caso, los patrones o expresiones se comparan por posición con las declaraciones de puerto.
Una forma de pensar en un actor es como un operador en flujos de datos: secuencias de tokens ingresan en él por sus puertos de entrada y secuencias de tokens lo abandonan por sus puertos de salida. Cuando se analiza el funcionamiento de un actor, a menudo resulta útil verlo como un operador en flujos. Los actores pueden tener parámetros. Actúan como constantes durante la ejecución del actor y se les asigna un valor concreto cuando se crea una instancia de un actor como parte de una red de actores. El propósito principal de los parámetros de actor es permitir a los programadores especificar familias de actores relacionados, sin tener que duplicar una gran cantidad de código.
Un actor no determinista es aquel que, para las mismas secuencias de entrada, permite más de una ejecución y más de una salida posible. El no determinismo puede ser muy poderoso cuando se utiliza adecuadamente, pero también puede ser una fuente de errores muy problemática. Una preocupación particular es que el no determinismo se pueda introducir en un actor de forma inadvertida, es decir, el autor piensa que el actor es determinista aunque no lo sea. Uno de los objetivos de diseño clave del lenguaje CAL era permitir la descripción de actores no deterministas, al mismo tiempo que se permitía que las herramientas identificaran posibles fuentes de no determinismo, de modo que pudieran advertir al usuario sobre ellas.
Una consecuencia clave de un actor no determinista como NDMerge es que durante una ejecución real, su salida puede depender del momento en que se recibe su entrada. Si ambas colas de entrada están vacías y NDMerge está esperando una entrada, entonces la entrada a la que llegue el siguiente token puede ser la que se copie junto a la salida. En consecuencia, la programación de actividades en la red de actores o las velocidades relativas de los actores que alimentan a un actor como NDMerge pueden afectar la salida del sistema. Esto puede ser deseable en ocasiones y en otras ocasiones no. En cualquier caso, es una propiedad que hay que tener en cuenta.
Una forma de ver el no determinismo del tipo que hace que un actor dependa del momento preciso de llegada de los tokens es que dicho actor solo parece no determinista si lo vemos como un operador en secuencias, porque esa visión se abstrae de las propiedades temporales de la ejecución y, por lo tanto, elimina deliberadamente la información que se utiliza para determinar la secuencia en la que se activan las acciones. Desde la perspectiva del lenguaje CAL, esto no es del todo exacto, pero, aun así, es fácil escribir actores no deterministas que no serían deterministas incluso si supiéramos todo sobre el momento preciso de los tokens y la implementación del actor, como los siguientes:
La cláusula de protección de una acción contiene una serie de expresiones que deben ser todas verdaderas para que la acción se pueda ejecutar. Para que la primera acción se pueda ejecutar, el token entrante debe ser mayor o igual a cero, en cuyo caso se enviará a la salida P. De lo contrario, esa acción no se puede ejecutar. Por el contrario, para que la segunda acción se pueda ejecutar, el token debe ser menor que cero, en cuyo caso se envía a la salida N. Una ejecución de este actor podría verse así: Un actor podría tener problemas si alguna vez encuentra un token cero, porque ninguna de sus acciones podrá ejecutarse en él.
No es ilegal escribir actores que finalicen en alguna entrada y, de hecho, puede ser importante tener algunos de ellos en algunos sistemas. Pero es un peligro del que hay que estar consciente. En segundo lugar, las condiciones de protección también son disjuntas, además de exhaustivas.
Por último, tenga en cuenta que las condiciones de guardia pueden "echar un vistazo" a los tokens entrantes sin consumirlos realmente: si las guardias resultan ser falsas o la acción no se dispara por alguna otra razón, y si el token no es consumido por otra acción, entonces permanece donde está y estará disponible para el próximo disparo. (O permanecerá allí para siempre, como en el caso del token cero frente a SplitDead , que nunca se elimina porque el actor está muerto).
El actor Select que se muestra a continuación es otro ejemplo del uso de acciones protegidas. Es similar al actor NDMerge en el sentido de que fusiona dos flujos (los que llegan a sus puertos de entrada A y B). Sin embargo, lo hace de acuerdo con los valores (booleanos) de los tokens que llegan a su puerto de entrada S.
En todos los actores hasta ahora, nada de lo que se activa una acción afectaría de ninguna manera a las activaciones posteriores de acciones del mismo actor. Al usar variables de estado, las activaciones de acciones pueden dejar información para las activaciones posteriores de la misma acción o de una diferente del mismo actor. La forma en que está escrito este actor, la selección del siguiente token de entrada y la copia real del token a la salida es un paso atómico.
Tenga en cuenta que Select e IterSelect son casi, pero no completamente, equivalentes. En primer lugar, IterSelect realiza el doble de pasos para procesar la misma cantidad de tokens. En segundo lugar, lee y, por lo tanto, consume el token de entrada S, independientemente de si hay un token de datos coincidente disponible en A o B.
El actor IterSelect de la sección anterior ilustró el uso del estado para controlar la selección de acciones. Esto es algo muy común en la práctica y el lenguaje CAL proporciona una sintaxis especial para este propósito en forma de horarios. Conceptualmente, se puede pensar en los horarios como la codificación de un patrón particular de uso de una variable de estado; no agregan nada al lenguaje en términos de expresividad. La razón para usar horarios es doble:
Cada transición de estado consta de tres partes: el estado original, una lista de etiquetas de acción y el estado siguiente. Algo que vale la pena destacar es que la cantidad de acciones ha aumentado: en lugar de las tres originales, la nueva versión con la programación ahora tiene cuatro acciones. La razón es que una acción ya no puede asignar directamente el estado sucesor, como lo hacía en el original, donde, dependiendo del valor del token, se le asignaba al estado read el valor 1 o 2. En la versión con una programación, esa modificación del estado está implícita en la estructura de la máquina de estados y ocurre según qué acción se active. En consecuencia, la condición que verifica el valor del token se ha movido desde el cuerpo de la acción a las protecciones de las dos acciones etiquetadas como readT y readF .
Mientras solo tenga entrada en uno de sus puertos de entrada, todo es inequívoco. Pero, al igual que NDMerge, tan pronto como la entrada esté disponible en ambos puertos de entrada, podría ejecutar cualquiera de sus dos acciones, y no hay nada en esa especificación de actor que lo predisponga a elegir una sobre la otra.
Ninguna de las construcciones del lenguaje que hemos utilizado hasta ahora nos permitiría hacer esto. A diferencia de lo que ocurre en este caso con las programaciones, que podrían considerarse como azúcar sintáctica porque podrían reducirse a elementos existentes del lenguaje (variables de estado, protecciones y asignaciones), esta situación requiere de hecho una verdadera extensión: las prioridades de acción. La idea básica es añadir una serie de desigualdades que relacionen las acciones con respecto a su precedencia de activación.
Al igual que en el caso de los cronogramas, utilizamos etiquetas de acción para identificar acciones a las que queremos hacer referencia más adelante, esta vez dentro de la desigualdad de prioridad. El bloque de prioridad contiene solo una de esas desigualdades, que relaciona la configuración etiquetada de acción con el proceso etiquetado, lo que le da prioridad a la primera sobre el segundo. Por supuesto, incluso esta versión sigue dependiendo en gran medida del tiempo. En este caso, eso no tiene por qué ser un problema y, de hecho, probablemente sea un requisito para que este actor realice su función. Pero, en general, es importante comprender que las prioridades, especialmente cuando se utilizan como en el ejemplo anterior, deben entenderse bien para obtener los resultados correctos. Especialmente cuando la información sobre el tiempo de la comunicación dentro de la red es vaga, probablemente sea mejor pensar en ellas como directivas de implementación sólidas.
El capítulo anterior se centró principalmente en aquellas construcciones de CAL que están relacionadas con conceptos específicos del actor: entrada y salida de tokens, acciones, control de la selección de acciones, etc. Esta sección analiza las partes más "peatonales" de CAL, las declaraciones y expresiones utilizadas para manipular objetos de datos y expresar algoritmos (secuenciales). Esta parte del lenguaje es similar a lo que se puede encontrar en muchos lenguajes de programación procedimental (como C , Pascal , Java , Ada ), por lo que nos centraremos en áreas que pueden ser ligeramente diferentes en CAL.
A diferencia de lenguajes como C, CAL hace una distinción clara entre declaraciones y expresiones. Tienen funciones y significados muy distintos y nunca se pueden usar indistintamente. Una expresión en CAL es un fragmento de código cuyo único propósito es calcular un valor. También decimos que una expresión tiene un valor o que se evalúa como un valor. Para la mayoría de las expresiones, el valor que se evalúa dependerá de los valores de una o más variables en el momento en que se evalúa la expresión. Dado que los valores de las variables pueden cambiar con el tiempo, la misma expresión puede tener valores diferentes cuando se evalúa en diferentes puntos del tiempo.
Probablemente las expresiones más fundamentales son las constantes. Otro grupo de expresiones básicas son las referencias a variables. Sintácticamente, una variable es cualquier secuencia de letras y dígitos . Una propiedad importante de las expresiones es que se garantiza que no cambiarán las variables (también decimos que no tienen efectos secundarios); en consecuencia, dentro de una expresión, múltiples referencias a la misma variable siempre producirán el mismo resultado.
CAL proporciona operadores de dos tipos para construir expresiones: unarios y binarios . Un operador unario en CAL es siempre un operador de prefijo, es decir, aparece antes de su único operando. Un operador binario aparece entre sus dos operandos.
En cierto modo, las sentencias en CAL son exactamente lo opuesto a las expresiones: no tienen un “valor de retorno”, pero pueden cambiar los valores de las variables. De hecho, cambiar los valores de las variables es el objetivo de las sentencias. Las sentencias se ejecutan en un orden secuencial estricto y, a menos que se especifique lo contrario, la ejecución de las sentencias se realiza en el orden en el que aparecen en el texto del programa, lo que significa que cualquier cambio de variable producido por una sentencia puede afectar la ejecución de sentencias posteriores.
Como en la mayoría de los demás lenguajes de programación, existen construcciones para controlar el orden en el que se ejecutan las sentencias dentro de un programa. La parte de este bucle que sigue directamente a la palabra clave ' foreach es un generador, muy parecido a los de las listas por comprensión.