Hispanopedia WikiCAL ( 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 diversas plataformas, incluyendo procesadores de un solo núcleo, procesadores multinúcleo y hardware programable . Se ha utilizado en varias áreas de aplicación, como vídeo y procesamiento, compresión y criptografía . El grupo de trabajo MPEG Reconfigurable Video Coding (RVC) [ 2 ] ha adoptado CAL como parte de sus esfuerzos de estandarización técnica .
Historia e introducción
El lenguaje de actores CAL se desarrolló en 2001 como parte del proyecto Ptolemy II en la Universidad de California, Berkeley . CAL es un lenguaje de flujo de datos diseñado para diversos dominios de aplicación, como el procesamiento multimedia, los sistemas de control, el procesamiento de redes , etc.
Otra razón común para elegir el flujo de datos es que el objetivo es una implementación paralela eficiente, algo difícil o imposible de lograr con un lenguaje de programación secuencial. Los lenguajes secuenciales son notoriamente difíciles de paralelizar en general, por lo que las implementaciones paralelas eficientes suelen requerir una guía importante por parte del usuario. Un programa de flujo de datos de CAL proporciona abstracciones sencillas, comprensibles y potentes que permiten especificar el grado de paralelismo necesario, lo que posibilita que las herramientas produzcan implementaciones sofisticadas que aprovechen la estructura concurrente de un cálculo.
Al programar en flujo de datos, el programador suele construir una descripción concurrente de un sistema computacional, a diferencia de un programa secuencial común. En lugar de centrarse en la ejecución paso a paso de un algoritmo , un programador de flujo de datos crea un sistema de entidades que se comunican de forma asíncrona, denominadas 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 adecuados entre ellos.
Características de CAL
La estructura de los actores
Los actores realizan sus cálculos en una secuencia de pasos denominada activación. En cada uno de estos pasos, un actor puede:
- Consume tokens desde sus puertos de entrada.
- Modificar su estado interno
- Produce tokens en sus puertos de salida.
En consecuencia, describir un actor implica describir su interfaz con el exterior y los puertos, la estructura de su estado interno y los pasos que puede realizar, qué hacen estos pasos (producción y consumo de tokens, y actualización del estado del actor), y cómo elegir el siguiente paso que realizará un actor . Esta sección analiza algunas de las construcciones del lenguaje CAL que abordan estos temas. Las acciones describen los sucesos que ocurren durante un paso que realiza un actor. Es correcto decir que un paso consiste en ejecutar una acción. 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:
- Define el número de tokens (para cada puerto) que se consumirán cuando se ejecute (active) una acción.
- Declara los símbolos de las variables mediante los cuales se hace referencia a los tokens consumidos por la activación de una acción dentro de dicha acción.
- Defina una condición de activación para una acción, es decir, una condición que debe cumplirse para que la acción pueda activarse.
La salida de una acción es un poco más sencilla: las expresiones de salida simplemente definen la cantidad y los valores de los tokens que se generarán en cada puerto de salida con cada activación de la acción. Se puede omitir la especificación del puerto al que se aplica un patrón de entrada o una expresión de salida si la 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 visualizar un actor es como un operador sobre flujos de datos: secuencias de tokens entran por sus puertos de entrada y salen por sus puertos de salida. Al analizar el funcionamiento de un actor, suele ser útil considerarlo como un operador sobre flujos. Los actores pueden tener parámetros . Estos actúan como constantes durante la ejecución del actor y reciben un valor concreto cuando se instancia un actor como parte de una red de actores. El objetivo principal de los parámetros de los actores es permitir a los programadores especificar familias de actores relacionados, sin tener que duplicar mucho código.
No determinismo
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 potente cuando se usa adecuadamente, pero también puede ser una fuente de errores muy problemática. Una preocupación es que el no determinismo se introduzca en un actor de forma inadvertida; es decir, que un autor crea que un actor es determinista aunque no lo sea. Uno de los objetivos clave del lenguaje CAL era permitir la descripción de actores no deterministas, al tiempo que permitía a las herramientas identificar posibles fuentes de no determinismo para poder alertar sobre ellas.
Una consecuencia clave de un actor no determinista como NDMerge es que, durante su ejecución, su salida puede depender del momento en que recibe su entrada. Si ambas colas de entrada están vacías y NDMerge está esperando una entrada, la siguiente entrada que llegue podría ser la que se copie junto a la salida. Por consiguiente, la planificación de las 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 no. En cualquier caso, es una propiedad que debe tenerse 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 se lo considera como un operador en flujos, porque esa visión abstrae 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 se conociera todo sobre el momento de llegada de los tokens y la implementación del actor, como por ejemplo:
Acciones cautelosas
La cláusula de guarda de una acción contiene un conjunto 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 con alguna entrada, y puede ser importante tener algunos de ellos en ciertos sistemas. Pero es un riesgo que puede causar problemas. En segundo lugar, las condiciones de guarda también son inconexas y exhaustivas.
Finalmente, las condiciones de guardia pueden examinar los tokens entrantes sin consumirlos. Si las condiciones son falsas o la acción no se ejecuta por algún otro motivo, y si el token no es consumido por otra acción, entonces permanece donde está y está disponible para la siguiente ejecución. (O puede permanecer allí indefinidamente, 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 según los valores (booleanos) de los tokens que llegan a su puerto de entrada S.
Actores con estado
Hasta ahora, en todos los actores, ninguna acción realizada por un actor afectaba a las acciones posteriores del mismo actor. Mediante variables de estado , las acciones pueden dejar información para las siguientes, ya sea de la misma acción o de una diferente. En la forma en que está escrito este actor, seleccionar el siguiente token de entrada y copiarlo a la salida constituye un paso atómico.
Select e IterSelect son casi equivalentes, pero no del todo. 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.
Horarios
El actor IterSelect de la sección anterior ilustró el uso del estado para controlar la selección de acciones. Esto es algo extremadamente común en la práctica, y el lenguaje CAL proporciona una sintaxis especial para este propósito en forma de programaciones. Conceptualmente, las programaciones pueden considerarse como la codificación de un patrón particular de uso de una variable de estado; no añaden nada a la expresividad del lenguaje. La razón para usar programaciones es doble:
- Por lo general, son más fáciles de usar y menos propensos a errores que el uso de variables de estado , así como de numerosas protecciones y asignaciones.
- Las herramientas pueden utilizar la información codificada en un cronograma con mayor facilidad y, por lo tanto, reconocer regularidades en el actor que podrían ayudarles a producir un código más eficiente o a realizar otros análisis que faciliten la implementación y el diseño.
Cada transición de estado consta de tres partes: el estado original, una lista de etiquetas de acción y el estado siguiente. Luego, el número 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 leído, al estado se le asignaba el valor 1 o 2. En la versión con una programación, esa modificación de estado es implícita en la estructura de la máquina de estados , y ocurre dependiendo de qué acción se active. En consecuencia, la condición que verifica el valor del token se ha movido del cuerpo de la acción a las guardas de las dos acciones etiquetadas readT y readF .
Prioridades
Mientras solo reciba entrada en uno de sus puertos, todo es inequívoco. Pero, al igual que con NDMerge, en cuanto reciba entrada en ambos puertos, podría ejecutar cualquiera de sus dos acciones, y no hay nada en la especificación del actor que lo predisponga a elegir una sobre la otra.
Ninguna de las construcciones lingüísticas existentes hasta ahora nos permitiría hacer esto. A diferencia del caso de las programaciones, que podrían considerarse azúcar sintáctico porque se reducen a elementos preexistentes del lenguaje (variables de estado, condiciones y asignaciones), esta situación requiere una verdadera extensión: prioridades de acción. La idea básica es añadir algunas desigualdades que relacionen las acciones con su precedencia de ejecución.
Al igual que en el caso de las programaciones, las etiquetas de acción se utilizan para identificar acciones a las que se hará referencia posteriormente, pero esta vez dentro de la desigualdad de prioridad. El bloque de prioridad contiene una única desigualdad de este tipo, que relaciona la configuración con la etiqueta de acción con el proceso con la misma etiqueta, otorgando prioridad a la primera sobre el segundo. Incluso esta versión sigue dependiendo en gran medida de la sincronización. En este caso, esto no tiene por qué ser un problema, y probablemente sea un requisito para que este actor cumpla su función. Pero, en general, las prioridades, especialmente cuando se utilizan como en el ejemplo anterior, deben comprenderse bien para obtener los resultados correctos. Sobre todo cuando la información sobre la sincronización de la comunicación dentro de una red es imprecisa, probablemente sea mejor considerarlas como directivas de implementación estrictas.
Declaraciones y expresiones
La sección anterior se centró principalmente en las construcciones de CAL relacionadas con conceptos específicos de los actores: entrada y salida de tokens, acciones, control de la selección de acciones , etc. Esta sección aborda los aspectos más básicos de CAL: las sentencias y expresiones utilizadas para manipular objetos de datos y expresar algoritmos (secuenciales). Esta parte del lenguaje es similar a la que se encuentra en muchos lenguajes de programación procedimentales (como C , Pascal , Java y Ada ), por lo que el enfoque se centra en áreas que podrían presentar ligeras diferencias en CAL.
Expresiones
A diferencia de lenguajes como C, CAL distingue claramente entre sentencias y expresiones. Tienen funciones y significados muy distintos, y nunca pueden usarse indistintamente. En CAL, una expresión es un fragmento de código cuyo único propósito es calcular un valor. Una expresión tiene un valor, o bien, se evalúa a 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 de su evaluación. Dado que los valores de las variables pueden cambiar con el tiempo, la misma expresión puede tener valores diferentes al evaluarse en distintos momentos.
Expresiones atómicas
Probablemente, las expresiones más fundamentales sean 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 garantizan que no modifican las variables (también decimos que no tienen efectos secundarios); por lo tanto, dentro de una expresión, múltiples referencias a la misma variable siempre producirán el mismo resultado.
expresiones compuestas simples
CAL proporciona operadores de dos tipos para construir expresiones: unarios y binarios . Un operador unario en CAL siempre es un operador prefijo, es decir, aparece antes de su único operando. Un operador binario aparece entre sus dos operandos.
Declaraciones
En cierto modo, las sentencias en CAL son lo opuesto a las expresiones: no devuelven ningún valor , pero pueden modificar los valores de las variables. Precisamente, modificar los valores de las variables es la función principal de las sentencias. Estas se ejecutan en estricto orden secuencial. Salvo que se especifique lo contrario, la ejecución de las sentencias se realiza en el orden en que aparecen en el código del programa. Esto significa que cualquier cambio en las variables producido por una sentencia puede afectar la ejecución de las sentencias posteriores.
Flujo de control
Como en la mayoría de los lenguajes de programación, existen estructuras de control de flujo para controlar el orden en que se ejecutan las instrucciones dentro de un programa. La parte de este bucle que sigue directamente a la palabra clave `foreach` es un generador, muy similar a los que se encuentran en las comprensiones de listas .
Acción
- Patrones de entrada: declaración de variables
- Guardia: especificación de las condiciones de habilitación
- Expresiones de salida: cálculo de tokens de salida
- Cuerpo: modificando el estado del actor
Referencias
- ↑ Eker, Johan; Janneck, Jörn W. (1 de diciembre de 2003). Informe del lenguaje CAL: Especificación del lenguaje de actores CAL (Informe). Memorando técnico n.º UCB/ERL M03/48. California: Universidad de California, Berkeley .
- ↑ Bhattacharyya, Shuvra S.; Eker, Johan; Janneck, Jörn W.; Lucarz, Christophe; Mattavelli, Marco; Raulet, Mickaël (2009). "Descripción general del marco de codificación de vídeo reconfigurable MPEG". Journal of Signal Processing Systems . Londres, Inglaterra: Springer .
Enlaces externos
- Lenguajes de programación de alto nivel
- Computación paralela
