Lman: Máquina Abstracta Del Cálculo Ntcc Para Programación

→

U N L → if d |= c 0 0 x d>→

LOC <(local x,c)→<(local x,c0 ) P 0 ,d∧∃x c0 > ST AR → if n ≥ 0 REP →

→γ2 0 0 ST R γγ10 →γ 0 if γ1 ≡ γ1 y γ2 ≡ γ2 1 OBS 2 →∗6→ if P =⇒(c,d) R R ≡ F (Q) Cuadro 2.2: Sem´antica de NTCC En el cuadro 2.2, la notaci´on de las reglas cumple”. P Q se lee, ¸cuando P se cumple, entonces Q se La regla T ELL adiciona c al Store d, quedando un nuevo Store d ∧ c y el proceso reducido a skip. 35 SU M escoge, no-deterministicamente, una guarda cj que pueda deducir el Store y ejecuta entonces el proceso Pj . Si se deduce lo contrario de cada una de las guardas ci ( ¬ci , ∀i∈I ), no se ejecuta ning´ un proceso Pi . Si no hay suficiente informaci´on para P deducir alg´ un ci , se suspende el proceso i∈I when ci do Pi . La regla P AR especifica que en una transici´on interna solo se reducir´a uno de los dos procesos. U N L modela la ejecuci´on de P siempre y cuando la condici´on c no sea deducida por el Store. Esto se presenta de dos formas: la primera ocurre al deducirse ¬c y la segunda es cuando el Store una vez alcanzado el estado de quietud no tiene suficiente informaci´on para deducir si c se cumple. LOC representa la propiedad de encapsulamiento creando una variable x a la que solo puede aceder el proceso P ; esto se modela ocultando a P la informaci´on de alguna x que se encuentre en el Store global mediante la cuantificaci´on existencial de esta (∃x d). A su vez P oculta al Store global la informaci´on de la variable x mediante un Store local c, el cual contendra toda la informaci´on sobre la x local. La regla ST AR activa, no-deterministicamente, el proceso P , sea en la unidad de tiempo actual o en una futura; se modela as´ı la espera de tiempo limitada, mas no definida. REP especifica la ejecuci´on de P en todos las unidades de tiempo, modelando el comportamiento infinito de un proceso. La regla ST R dice que procesos estructuralmente congruentes tienen reducciones que producen procesos congruentes. Las anteriores reglas se agrupan bajo el nombre de transiciones internas. La regla OBS dice que una transici´on observable de P , etiquetada por < c, d >, se obtiene al realizar una secuencia interna de transiciones desde la configuraci´on inicial < P, c > a la configuraci´on final < Q, d >, en la que ya no es posible hacer m´as evoluciones internas. El proceso residual R a ser ejecutado en la siguiente unidad de tiempo, es equivalente a (F (Q)) ( Futuro de Q) . Futuro de Q se obtienen eliminando de Q las sumatorias que no dispararon actividad en el intervalo actual, junto con la informaci´on local almacenada en Q y eliminado el Store actual, dejando s´olo los procesos next y unless[Val03]. 36 Es importante mencionar c´omo NTCC, al igual que TCC, introduce la programaci´on reactiva-temporal [Val03]. El ambiente estimula a un proceso Pi d´andole una entrada ci . El proceso P reacciona en una cantidad de tiempo finita al ambiente d´andole una salida c0i y evolucionando al proceso Pi+1 . Cada respuesta a estos est´ımulos definen una unidad de tiempo. Los observadores externos al proceso no observan las transiciones internas, solamente las entradas y salidas definidas. 2.4. Definiciones Recursivas Resulta conveniente especificar determinados comportamientos mediante la recursi´on. Por ´este motivo, se describir´a la forma de codificarla en NTCC. NTCC define la recursi´on de la siguiente forma [Val03]. q(x) =def Pq Donde q es el nombre de un proceso y Pq su cuerpo, que puede tener como m´aximo una ocurrencia de q, y antepuesta al operador next; lo anterior es para forzar que se tenga una respuesta de q(x) en cada unidad de tiempo, pues no se quiere que Pq haga infinitos llamados recursivos a q en la misma unidad de tiempo. Para tratar los llamados q(t), se considera a t como una variable con un valor v (el Store puede deducir que t = v), obteni´endose Pq [v/x], donde la operaci´on [v/x] denota el remplazo de toda ocurrencia de x por v. En NTCC se debe evitar que las variables que ocurren libres en Pq sean capturadas por el alcance de las variables locales. Se hace necesario entonces utilizar el alcance est´atico, con la siguiente notaci´on: q(x)[y1 , ....., yn ] =def Pq Donde y1 , ....., yn son las variables que pueden ocurrir libres en P . Se expondr´a el siguiente ejemplo para aclarar la diferencia entre alcance est´atico y din´amico [Val03]. Ejemplo 2.4 Sea q(x) =def tell(y = 1)||next(localy)(q(x)||when y do P ) 37 Si se considera alcance din´amico, en el momento que se ejecute el llamado recursivo ((localy)(q(x)||when y do P )) se asumira que el proceso tell(y = 1) hace referencia a la variable local y, lo cual no es cierto porque tell(y = 1) utiliza una variable global. Si se desea obtener la independencia de variables entre el proceso tell(y = 1) y el when y do P , es necesario utilizar alcance est´atico, mencionando las variables que pueden ocurrir libres en q(x). 2.4.1. Codificaci´ on A continuaci´on se presenta la codificaci´on para modelar recursi´on en NTCC. Un proceso q(t) que representa el primer llamado recursivo, se define de la siguiente forma: d (local q qarg)(pq(x) =def Pq q || q(t)) donde: El proceso recursivo pq(x) =def Pq q es: cq )) !(when call(q) do (local x)(x ← qarg || P siendo: - call q(t) la abreviaci´on de x = 1. - x ← t la abreviaci´on de Σv when t = v do !tell(x = v) d tell(call(q)) || tell(qarg = t) q(t): q y qarg dos variables no libres en Pq Se utilizan las variables locales q y qarg, para abolir posibles interferencias entre los llamados recursivos externos. 38 2.5. Celdas Las celdas proveen herramientas para el an´alisis y especificaci´on de estructuras de datos persistentes y variables, por lo cual es importante modelarlas en el c´alculo NTCC. Para el modelamiento de las celdas se debe asumir que el sistema de restricciones cuenta con un predicado que pueda expresar el estado de cambio de una variable; este predicado ser´a change. Definici´ on 2.5.“ Se define una celda x : (v) como una estructura x cuyo valor actual es v y que puede mantenerse o cambiar en el futuro” [Val03]. Una celda x : (v) tiene la forma: \ next x : (z) x : (z) =def tell(x = z) || unless change(x) La anterior definici´on representa una celda x, cuyo valor actual es z y, a menos que se \ = 1) x, tomar´a el mismo valor z en el pr´oximo decida cambiar este valor, (tell chage(x) instante. Adem´as de la definici´on de la celda existe otro operador utilizado. Se trata del operador \ exchg [x, y], llamado operador de intercambio (exchage). Se utiliza para asignar nuevos valores sobre las celdas. Sea exchg [x, y], v el valor actual de x y y otra celda y g(v) la funci´ on que calcula el siguiente valor de x. Se tiene: \ \ exchg [x, y] = Σv when x = v do ( tell(change(x)) || tell(change(y)) || next(x : (g(v)) || y : (v))) El uso del operador exchg [x, y] podr´a ser apreciado en la siguiente secci´on de Aplicaciones y Ejemplos. 2.6. Aplicaciones y Ejemplos Se ha mencionado anteriormente que por las propiedades reactivas-temporales, el nodeterminismo y la asincron´ıa que modela NTCC, existe un gran n´ umero de aplicaciones en las que se pueden demostrar la expresividad de ´este c´alculo, tales como: la programaci´on de dispositivos rob´oticos, la sincronizaci´on de procesos musicales y los sistemas 39 multiagentes. En esta secci´on se mostrar´an algunos ejemplos, enfatizando la aplicaci´on principal de este trabajo de tesis: Programaci´ on Concurrente de controladores RCX en dispositivos LEGO. Los ejemplos expuestos aqu´ı son tomados de [Val03]. 2.6.1. Controladores RCX: Ejemplo de Zig-Zag “Un RCX es un dispositivo programable fabricado por LEGO, con el cual se pueden crear diferentes clases de robots aut´ onomos [LP99]. La tarea de zig-zag [Fre99] consiste en que el robot-RCX se mueva aleatoriamente de izquierda a derecha con las siguientes condiciones: 1. el robot no puede ir hacia adelante si su ultima acci´ on fue ir adelante. 2. no puede girar a la derecha si su pen´ ultima acci´ on fue ir a la derecha, 3. la segunda condici´ on aplicada a la izquierda”[Val03]. La soluci´on que se plantea evita la sobre-especificaci´ on, planteando solo los aspectos que conciernen a la descripci´on de la soluci´on. Se usar´an dos celdas a1 y a2 para tener una referencia de los dos u ´ltimos movimientos que ha hecho el RCX. Adem´as, se definir´an las constantes f, r, l ∈ D − 0 para denotar los predicados f =adelante(forward), r=derecha(right), l=izquierda (left). La soluci´on es la siguiente: goF =def goR =def goL =def Zigzag =def GoZigzag =def exchf [a1 , a2 ] || tell(forward) exchr [a1 , a2 ] || tell(right) exchl [a1 , a2 ] || tell(left) !(when (a1 6= f ) do GoF + when (a2 6= r) do GoR + when (a2 6= l) do GoL) a1 : (0) || a2 : (0) || Zigzag Inicialmente las celdas a1 y a2 contendr´an valores diferentes de f , r y l, lo cual hace que se escoja no-deterministicamente la direcci´on de arranque; despu´es el RCX se dirigir´a por las condiciones 1, 2 y 3, grabando en a1 y a2 los movimientos anteriores. A continuaci´on se da un ejemplo de la funci´on exch[a1 , a2 ]: exchf [a1 , a2 ] =def P v∈f,r,l,0 when a1 = v do ( tell(change(a1 )) || tell(change(a2 )) || next( a1 : (f ) || a2 : (v))) Las dem´as operaciones exch[a1 , a2 ] (exchr [a1 , a2 ] y exchl [a1 , a2 ]) son similares a la definici´on anterior. 40 2.6.2. Sistemas Multiagentes: Presa y Predador “El juego Presa y Predador [MBD86] es muy famoso debido a que sus m´ ultiples an´ alisis desde diferentes puntos de vista [HS96], permiten representar entornos multi-agentes [SV00]. Este ejemplo puede ser modelado con m´ ultiples robots-RCX.” El juego consiste en que los predadores y la presa se mueven en un tablero toroidal; si llegan al final de ´este, salen por el otro lado del mismo. La presa y el predador se pueden mover horizontal o verticalmente, en cualquier direcci´on. Los predadores tendr´an cierta ventaja sobre su presa, ya que corren dos casillas del tablero mientras que la presa solo puede correr una. El objetivo del predador es capturar a la presa; esto ocurre cuando la presa se mueve a una posici´on entre las tres casillas que el predador puede atacar: la casilla donde se encuentra actualmente el predador, la anterior a donde se encontraba o la casilla de la mitad. El juego comienza con la presa ubicada al frente de los predadores y estos posicionados en la misma fila. El comportamiento que debe adoptar la presa para poder escapar es ejecutar un zigzag no predecible sobre el mundo, mientras que la estrategia de los predadores es cooperar entre ellos para capturar a la presa. De tal manera que, cuando un predador se encuentre frente a la presa, se declarar´a como l´ıder del ataque y los otros predadores ser´an sus cooperadores en la captura de la presa. Como consecuencia, la posici´on de l´ıder se alterna dependiendo de qui´en est´e m´as cerca de la presa. 2.6.3. Aplicaciones Musicales: Control de Improvisaci´ on Un ejemplo de las aplicaciones musicales que tiene el c´alculo NTCC es el control de improvisaci´on. Este consiste en tener un conjunto de m´ usicos m, que tocar´an un n´ umero fijo de notas (en este caso se tomar´a 3). Cada m´ usico puede escoger qu´e notas tocar, pero se le establece un tiempo que puede utilizar entre las notas del bloque. Ejemplo: sea la partitura del m´ usico 1 [5,6,2], ´esto quiere decir que entre la primera y la segunda nota tiene un espacio de 5 silencios para improvisar, entre la segunda y tercera 6 y despu´es de la tercera 2. Cuando el m´ usico termine su interpretaci´on de las tres notas correspondientes, debe esperar a la se˜ nal del conductor que le dice que todos los m´ usicos ya han terminado de tocar su bloque y el puede volver a empezar. El tiempo entre los 41 bloques consecutivos de cada m´ usico no est´a determinado, pero hay la restricci´on de que no debe demorarse m´as que la suma de todos los tiempos de las partituras de los otros m´ usicos. Los dos anteriores ejemplos se profundizan en [Val03], PHD Tesis de Frank d. Valencia. 42 ´ 3 LMAN: MAQUINA ABSTRACTA Este cap´ıtulo describe el An´alisis y la Especificaci´on formal de la M´aquina Abstracta LMAN . Se presenta la evaluaci´on de alternativas sobre la implementaci´on, seguida de la especificaci´on de la m´aquina abstracta: notaci´on, sintaxis de los procesos, las reglas de reducci´on que describen su funcionamiento y constituyen su n´ ucleo, los estados inicial y final, finalizando con un diagrama de transiciones que resume su funcionamiento. 3.1. An´ alisis A continuaci´on se muestran las consideraciones que se tomaron en la etapa del an´alisis de ´este trabajo de tesis, las cuales fueron determinantes para las siguientes etapas de dise˜ no e implementaci´on. 3.1.1. Entorno de Programaci´ on NTCC LMAN , hace parte de un flujo de implementaci´on que tiene como objetivo proveer un entorno de programaci´on aplicativa. Este entorno de programaci´on NTCC [Val03] se divide en 5 bloques funcionales(ver figura 3.1). El bloque superior VIN se encuentra en desarrollo como proyecto de grado independiente al presente[FQ04] y su objetivo es elevar el nivel de programaci´on en el c´alculo, programando en un lenguaje ic´onico. El siguiente m´odulo es el COMPILADOR NTCC-LMAN que adem´as de que act´ ua como un componente integrador entre el lenguaje visual y LMAN, permite programar NTCC en alto nivel; su dise˜ no se trata en el cap´ıtulo 5. Los u ´ltimos tres bloques hacen referencia a LMAN y la base que la soporta; ´estos bloques funcionales se tratan en el 43 siguiente cap´ıtulo que describe la m´aquina virtual. El H8/300L es el microprocesador del RCX brick y legOS es el sistema operativo que LMAN utiliza como interfaz con este microprocesador. La integraci´on del lenguaje visual, el compilador y LMAN se hace posible, dado que los tres utilizan el c´alculo NTCC base; de ´esta manera, el lenguaje visual genera c´odigo NTCC, que el compilador entiende como entrada para la generaci´on de c´ odigo de bytes LMAN. Figura 3.1: Flujo del entrono de programaci´on NTCC 3.1.2. Evaluaci´ on de Alternativas de Implementaci´ on para la M´ aquina Abstracta En el desarrollo de LMAN, m´aquina que implementa el c´alculo NTCC [Val03] para programaci´on de dispositivos rob´oticos LEGO se presentaron varias alternativas para su implementaci´on. Por ´esta raz´on, se hizo conveniente establecer una an´alisis de alternativas que permitiera decidir de manera objetiva, cual era la opci´on ´optima. Los criterios que se consideraron pertinentes para evaluar cada alternativa se describen a continuaci´on: Eficiencia en Tiempo de Ejecuci´ on: Trata el factor del tiempo en la ejecuci´on de un programa sobre la implementaci´on de la m´aquina. Manejo Sistema de Restricciones: Trata la integraci´on e interacci´on entre la m´aquina y el sistema de restricciones. Eficiencia en el Manejo de Memoria: Trata el manejo de memoria eficiente sobre la implementaci´on de la m´aquina. 44 El modo de calificaci´on de cada indicador, fue dado cuantitativamente en modo ascendente, siendo 1 la opci´on mas desfavorable y 10 la m´as conveniente. El cuadro 3.1, muestra la evaluaci´on de alternativas, posteriormente se sustenta la puntuaci´on asignada para cada una de las opciones en los criterios evaluados. Criterios/Indicadores Eficiencia Tiempo de Ejecuci´on Manejo de Sistema de Restricciones Eficiencia Manejo de Memoria Total Traductor 10 8 6 21 M´aquina Virtual 8 10 8 25 Cuadro 3.1: Evaluaci´on de Alternativas de Implementaci´on para la M´aquina Abstracta Las alternativas propuestas y su an´alisis de criterios sigue a continuaci´on. Los argumentos dados toman como referencia otras implementaciones similares a las alternativas en an´alisis.[LY97][Leg00]. Descripci´ on: • Traductor : Un traductor [AB98] como su nombre lo indica, se encarga de traducir un programa durante la etapa de compilaci´on, de un lenguaje de alto nivel a uno equivalente en un lenguaje que pueda ejecutar el computador o el dispositivo rob´otico. • M´aquina Virtual : La m´aquina virtual [Com00] es un procesador no implementado en Hardware, que act´ ua como el ejecutor notacional de un lenguaje de programaci´on particular. Eficiencia en Tiempo de Ejecuci´ on: • Traductor : Debido a que la traducci´on se realiza en tiempo de compilaci´on, el programa ser´a ejecutado directamente por el dispositivo rob´otico; luego el tiempo en ejecuci´on ser´ıa ´optimo. Valoraci´on: 10. • M´aquina Virtual : La m´aquina virtual interpreta el programa en tiempo de ejecuci´on, luego comparando con un traductor su desempe˜ no no ser´ıa el mejor. Valoraci´on: 8. Manejo Sistema de Restricciones: 45 • Traductor : Debido a que el traductor act´ ua en tiempo de compilaci´on, su integraci´on con el m´odulo del sistema de restricciones se har´ıa extensa; ya que ser´ıa necesario unir ambos bloques de c´odigo para asegurar un funcionamiento en conjunto. Valoraci´on: 8. • M´aquina Virtual : La implementaci´on de una m´aquina virtual confiere modularidad, lo cual combinado con su caracter´ıstica de interpretaci´on del programa en tiempo de ejecuci´on; posibilita la adici´on del sistema de restricciones como un m´odulo funcional, definiendo solamente una interfaz que le permita interactuar con el control de la m´aquina. Valoraci´on: 10. Eficiencia en el Manejo de Memoria: • Traductor : Un traductor combinar´ıa en tiempo de ejecuci´on el bloque de control que implementa la sem´antica operacional del c´alculo, con el c´odigo del programa a ejecutar. Esto generar´ıa que los programas traducidos fuesen de mayor tama˜ no en memoria y que posiblemente requirieran de mayores recursos mientras se realiza la traducci´on. Valoraci´on: 6. • M´aquina Virtual : La m´aquina virtual interpreta los programas en tiempo de ejecuci´on; por lo cual se separa el control de las construcciones hechas en el c´alculo. Esto permitir´ıa un manejo mas eficiente de memoria, ya que solo se consumir´ıan los recursos de ejecuci´on. Valoraci´on: 8. Como conclusi´on de las valoraciones dadas, la alternativa que se escoge para implementaci´on es una m´ aquina virtual . Una m´aquina virtual confiere modularidad a la implementaci´on, eficiencia en el manejo de memoria, adminte la integraci´on de una manera transparente del sistema de restricciones y el fundamento sobre la base formal de una m´aquina abstracta. 3.1.3. Evaluaci´ on de Alternativas de la plataforma de implementaci´ on para la M´ aquina Virtual Para implementar una m´aquina virtual sobre un dispositivo rob´otico LEGO, existen varias alternativas de plataformas de programaci´on; por este motivo se hace conveniente establecer un an´alisis para decidir objetivamente cual es la alternativa ´optima. Los criterios que se consideraron pertinentes para evaluar cada alternativa son los siguientes: 46 Eficiencia: Eval´ ua el tiempo de ejecuci´on, la gesti´on de memoria y el manejo del microprocesador. Escalabilidad y Mantenimiento: Eval´ ua las ventajas de la plataforma: facilidad de instalaci´on, lenguajes admitidos, transparencia en las actualizaciones, manejo de perif´ericos del robot. Restricciones Legales: Eval´ ua el tipo de restricciones que existen en la adquisici´on y utilizaci´on de la plataforma. Compatibilidad: Eval´ ua la portabilidad y el nivel de acceso por el usuario final a la plataforma. El modo de calificaci´on de cada indicador, fue dado cuantitativamente en modo ascendente, siendo 1 la opci´on mas desfavorable y 10 la m´as conveniente. El cuadro 3.2, muestra la evaluaci´on de alternativas, posteriormente se sustenta la puntuaci´on asignada para cada una de las opciones en los criterios evaluados. Criterios/Indicadores LEJOS (java) Eficiencia Escalabilidad y Mantenimiento Restricciones Legales Compatibilidad Total 5 10 10 7 32 BrickOS M´aquina NQC (legOS) Est´andar de (c++ y c) LEGO 8 10 9 10 1 6 10 10 10 8 7 8 36 28 33 Cuadro 3.2: Evaluaci´on de alternativas de la plataforma de implementaci´on para la M´aquina Virtual Las alternativas propuestas y su an´alisis de criterios sigue a continuaci´on. Los argumentos dados toman como referencia la documentaci´on y pruebas realizadas sobre las alternativas en an´alisis.[LY97][Leg00]. Descripci´ on: • LEJOS : Implementaci´on de la m´aquina virtual de JAVA para los robots LEGO. Permite el manejo de todos los perif´ericos del RCX, el control total de 47 los 32Kb de RAM y la programaci´on orientada a objetos en JAVA. El driver de la torre LEGO USB se encuentra bajo desarrollo (para Linux solamente). Funciona sobre Linux y Windows. [SR00]. • BrickOS : Sistema operativo de c´odigo abierto para robots LEGO, antes llamado legOS. Permite programar en lenguajes C y C++ el RCX brick, admite el manejo de todos los perif´ericos del RCX ,el control total de los 32Kb de RAM y la programaci´on orientada a objetos. El driver de la torre LEGO USB se encuentra bajo desarrollo (para Linux solamente); el driver de la torre serial ha sido desarrollado y probado en Linux. Funciona sobre Linux, Windows y MacOS. [MLNP00]. • M´aquina est´andar de LEGO: El RCX tiene un firmware original en forma de m´aquina virtual para su control. Permite el manejo de todos los perif´ericos y la programaci´on se real´ıza por medio de una interfase visual b´asica llamada RIS (Robotic Invention System) SDK que funciona solo en Windows y Mac. Esta m´aquina admite un n´ umero de variables globales de 32 y locales de 16, un n´ umero m´aximo de programas en memoria de 5, cada uno con m´aximo 10 tareas y 8 subrutinas. Tiene soporte USB y serial. [Leg00]. • NQC(Not Quite C): Es un compilador de c´odigo de bytes nativo,que utiliza la m´aquina est´andar de LEGO en su funcionamiento. Toma los programas escritos con una sintaxis b´asica muy similar al lenguaje C, de ah´ı su nombre; y los traduce al c´odigo de bytes que entiende la m´aquina virtual est´andar. Tiene limitaciones en el manejo de variables (32),no se pueden definir estructuras de datos,las subrutinas no pueden retornar valores y no admiten par´ametros. Funciona en Windows, Linux y MacOS.[Bau00]. Eficiencia: • LEJOS : La m´aquina virtual de JAVA es interpretada y maneja objetos, razones que pueden generar m´as consumo de memoria y extender el tiempo de ejecuci´on de los programas sobre el robot LEGO, tal como se ha observado en otras implementaciones de m´aquinas virtuales en JAVA ejecut´andose sobre estaciones de trabajo [AB98]. Valoraci´on: 5. • BrickOS : Se ha demostrado que la programaci´on C y C++ resulta eficiente, adicionalmente admite una programaci´on estructurada y orientada a objetos que confiere modularidad a las implementaciones. Lo anterior, en conjunto 48 con las habilidades de BrickOS para el control del hardware de robot, permiten lograr una buena combinaci´on en eficiencia. Valoraci´on: 8. • M´aquina est´andar de LEGO: la programaci´on directamente en el c´ odigo de bytes asegura un buen desempe˜ no, ya que se estar´ıa tratando directamente con las instrucciones nativas del microprocesador del RCX. Valoraci´on: 10. • NQC : Aunque la sintaxis de NQC es b´asica, su propiedad de compilar al c´odigo de bytes la hace eficiente en tiempo de ejecuci´on. No obstante el manejo de memoria no resulta tan eficiente, debido a las limitaciones del lenguaje. Valoraci´on: 9. Escalabilidad y Mantenimiento: • LEJOS : La implementaci´on de una m´aquina virtual confiere modularidad, como se ha mencionado antes; esto hace de LeJOS un sistema administrable. La programaci´on en lenguaje JAVA posibilita realizar construcciones completas y complejas. La programaci´on de los perif´ericos del RCX se realiza mediante librer´ıas, adem´as de que es posible utilizar las librer´ıas est´andar. Las actualizaciones son transparentes, ya que solo se requiere actualizar a una nueva versi´on de la m`aquina virtual, de modo que los programas siguen ejecut´andose sin modificaciones de fondo. Valoraci´on: 10. • BrickOS : Es un sistema operativo que continuamente est´a actualiz´andose en versiones. El uso del lenguaje C como herramienta de programaci´on, le confiere eficiencia a las construcciones en cuanto al control del hardware del robot y la programaci´on convencional.Aunque la instalaci´on es un poco dispendiosa, existen muchas ayudas para completarla. Es una de las plataformas m´as robustas y m´as usadas para programaci´on de robots LEGO. Valoraci´on: 10. • M´aquina est´andar de LEGO: Las actualizaciones son realizadas eventualmente y entregadas directamente por LEGO Group. Para programar utilizando ´esta m´aquina virtual se requiere un largo estudio de su arquitectura, las instrucciones y de la generaci´on del c´ odigo de bytes. Valoraci´on: 1. • NQC : Al actuar como una interfaz de alto nivel con la m´aquina virtual de LEGO, la programaci´on resulta mucho m´as manejable que el lenguaje ensamblador de la m´aquina virtual. Sin embargo, las construcciones hechas 49 en NQC, conllevan las limitaciones de su sintaxis; lo cual se convertir´ıa en un factor limitante para la implementaci´on. Valoraci´on: 4. Restricciones Legales: • Tanto LEJOS como BrickOS y NQC se han trabajado como proyectos GNU/Linux. El firmware est´andar de LEGO es propiedad de Lego Group, sin embargo su uso no est´a limitado. Valoraci´on: 10. Compatibilidad: • LEJOS : Es multiplataforma (Linux, Windows, MacOS entre otros). Su instalaci´on puede resultar compleja. Valoraci´on: 7. • BrickOS : Es multiplataforma (Linux, Windows, entre otros) y adicionalmente es compatible con otras soluciones para programaci`on de RCX como se describe los cuadros 4.2 y 4.3. Su instalaci´on puede resultar compleja. ˙ Valoraci´ on: 8. • M´aquina est´andar de LEGO: Es multiplataforma. Valoraci´on: 7. • NQC : Es multiplataforma (Linux, Windows, Mac, entre otros), su instalaci´on es relativamente sencilla. Valoraci´on: 8. Teniendo en cuenta el total para las valoraciones asignadas a las diferentes alternativas de implementaci´on; la alternativa seleccionada para implementaci´on de la m´aquina virtual es el Sistema operativo BrickOS(legOS) y el lenguaje de programaci´ on C . Esta plataforma es realmente estable, funciona como proyecto alrededor de una comunidad GNU por lo cual facilita la b´ usqueda de informaci´on y ayuda en las tareas de configuraci´on, acople y desarrollo; es multiplataforma de modo que confiere portabilidad a la soluci´on de la m´aquina virtual y permite controlar eficientemente el hardware de los robots. El uso del lenguaje de programaci´on C confiere eficiencia a la implementaci´on, admite programaci´on estructurada y cuenta con la funcionalidad necesaria para realizar la implementaci´on de la m´aquina virtual. 3.2. M´ aquina Abstracta A continuaci´on se define la m´aquina abstracta del c´alculo NTCC [Val03] para programaci´on concurrente de robots LEGO. Se presenta la especificaci´on formal, la sintaxis, la 50 definici´on de estados inicial y final, las reglas de reducci´on y el diagrama de transiciones que muestra el funcionamiento de la m´aquina abstracta. 3.2.1. Especificaci´ on formal La M´aquina Abstracta LMAN se define formalmente como sigue a continuaci´on: 3.2.1.1. Procesos Un proceso en LMAN est´a conformado por una tupla < P, B > donde P es un proceso y B es una funci´on que contiene todas las variables que puede alcanzar el proceso, siendo B el ambiente, o asociaci´on de localidades a variables: B : LOC− > V AR. 3.2.1.2. Store El Store(S) se define como una conjunci´on de todas las restricciones iniciales m´as las adicionadas al Store en el instante actual. S : c1 ∧ c2 ∧ c2 ∧ ................. ∧ cn 3.2.1.3. Colas de ejecuci´ on Las colas representan procesos concurrentes de la forma: P1 ||P2 ||P3 ||.......||P n Se define una cola C como una concatenaci´on de procesos de la forma < P, B >: C : < P1 , B1 > || < P2 , B2 > || < P3 , B3 > ||.......|| < P n, Bn > La representaci´on de una cola vac´ıa es ∅. La notaci´on C ::< P, B > representa una cola cuyo primer elemento es < P, B > y cuyo residuo de elementos es la cola C. 51 3.2.1.4. Estructura de LMAN La estructura de la m´aquina est´a dada por: <<< P, B >, CL, CA, CU >, CC, S > Donde: P : es el proceso en ejecuci´on. B: es el conjunto de variables asociadas al proceso P. CL: Es la cola de procesos listos a ejecutar. CA: Es la cola de procesos ask suspendidos por falta de informaci´on en el Store. CU : Es la cola de procesos unless. CC: Es la cola de construcci´on, donde se almacenan los procesos residuales del instante actual, que ser´an ejecutados en el siguiente o siguientes instantes de tiempo. S: Es el Store com´ un, donde se almacenan las restricciones asociadas al instante en ejecuci´on. La tupla m´as a la izquierda (< P ; B >) define un proceso en la m´aquina; la siguiente estructura (<< P ; B >; Cl; CA; CU >) define la m´aquina que se est´a ejecutando en el instante actual y la tupla m´as a la derecha (<<< P ; B >; Cl; CA; CU >; CC; S >) define la estructura utilizada para construir la m´aquina en el siguiente instante. El Store se trata como una estructura global a la definici´on de la m´aquina. En LMAN se maneja la noci´on de “planeaci´ on de m´ aquinas”. Esta noci´on implica que se construye una sola m´aquina por instante de tiempo; es decir que al final de cada instante se destruye tanto la m´aquina actual como el Store. La m´aquina para el pr´oximo instante se construye a partir de la cola CC, donde se encuentran todos los procesos residuales de la actual unidad de tiempo. 52 3.2.2. Sintaxis Los procesos que implementa la m´aquina son esencialmente los expresados en la sintaxis de NTCC. La u ´nica diferencia est´a realmente en el proceso de ejecuci´ on eventual (∗P ), que se delimita por eficiencia en la implementaci´on en un rango dado. La m´aquina considera solamente procesos primitivos del c´alculo (la excepci´on es nextn P ), pero no las construcciones derivadas que se mencionan en [Val03](p´agina 31). El cuadro 3.3 muestra la sintaxis de los procesos v´alidos en LMAN . P, Q, ... = skip Inactividad |tell(c) tell c P | i∈I when (ci ) do Pi Seleccione un Pi , si ci , i ∈ I |P ||Q Ejecucion en paralelo |Local x in P Localidad |next P Ejecute P en la siguiente unidad de tiempo |nextn P Ejecute P en la n − −esima unidad de tiempo |unless (c) next P A menos que deduzca c, ejecute next P |!P Replicacion | ? [i, j]P Retardo inf inito pero no limitado de P Cuadro 3.3: Sintaxis de LMAN Donde: c, d, ... denotan las restricciones. P, Q, A, ... representan los procesos del c´alculo. x, y, .. se utilizan para hacer referencia a las variables de los procesos. El proceso nextn P representa una abreviaci´on del proceso (next(next(...(nextP )...))), con n ocurrencias de next. El proceso ?[i, j]P modela eventualidad limitada en un intervalo entre i y j, donde j es mayor que i, de modo que, P se ejecuta en una unidad de tiempo eventual en este intervalo. La equivalencia los anteriores dos procesos con los procesos primitivos se encuentra en [Val03]. 3.2.3. Estado inicial y Final El estado inicial de la m´aquina est´a dado por la siguiente configuraci´on: 53 <<< skip, B >, CL, ∅, ∅ >, ∅, S > Donde: S es el Store inicial, B contiene todas las variables globales de la m´aquina y CL contiene todos los procesos a ejecutar. Las variables globales son visibles y modificables por todos los procesos de la m´aquina actual. El c´alculo NTCC modela sistemas reactivos, los cuales pueden permanecer inactivos por grandes periodos de tiempo y luego pueden volver a activarse. As´ı siguiendo ´esta noci´on, no se define un estado final para la m´aquina. Solo detiene su computaci´on a menos que exista un fallo funcional o un bloqueo por inconsistencias en el Store. 3.2.4. Sem´ antica Operacional: Reglas de Reducci´ on Las reglas de reducci´on de la m´aquina est´an basadas en la sem´antica operacional del c´alculo NTCC; apoy´andose en la siguiente definici´on de ESTADO y la relaci´on →: EST ADO : P x B x CL x CA x CU x CC x S →: ⊆ EST ADO x EST ADO La regla SCHED se encarga de la planeaci´on de los procesos que se encuentran en la m´aquina. Se divide en tres casos. El primer caso es cuando un proceso llega a su final (skip), por lo cual se contin´ ua con el siguiente en la cola CL. El segundo caso es cuando la cola CL se encuentra vac´ıa; entonces se procede a ejecutar los procesos de la cola CU . La tercera regla determina el paso a la siguiente unidad de tiempo y la construcci´on de una nueva m´aquina; ´esto sucede solo si las colas CL y CU se encuentran vac´ıas; lo que quiere decir, que no hay procesos que se puedan reducir. Adicionalmente, se destruye el Store anterior(S) y se crea el nuevo Store(S 0 ) el cual contiene solamente el estado inicial del ambiente. SCHED1 : <<< skip, B >, CL ::< P, B 0 >, CA, CU >, CC, S >→<<< P, B 0 >, CL, CA, CU >, CC, S > 54 SCHED2 : <<< skip, B >, ∅, CA, CU ::< P, B 0 >>, CC, S >→<<< P, B 0 >, ∅, CA, CU >, CC, S > SCHED3 : <<< skip, B >, ∅, CA, ∅ >, CC, S >→<<< skip, B 0 >, CC, ∅, ∅ >, ∅, S 0 > La regla T ELL necesita del sistema de restricciones para agregar la restricci´on c al Store, en la unidad de tiempo actual. T ELL : <<< tell(c), B >, CL, CA, CU >, CC, S >→<<< skip, B >, CL, CA, CU > CC, S ∧ c > La regla ASK presenta los siguientes cuatro casos. El primer caso (ASK1), es para la informaci´on positiva; esto quiere decir, que el ask da una respuesta afirmativa de acuerdo con la restricci´on c. El segundo caso (ASK2,1), sucede cuando el Store deduce lo contrario de uno de los ask de la sumatoria que le ha sido preguntado (¬c ), entonces elimina ese proceso particular de la sumatoria. El tercer caso (ASK2,2) es cuando P no hay m´as procesos ask en la sumatoria, entonces se elimina el proceso de la cola CL. Y finalmente, el cuarto caso (ASK3), se presenta cuando el Store no puede deducir ninguna de las opciones anteriores por ausencia de informaci´on, por lo tanto, P se suspende el procesos en la cola CA. ASK1 : <<< S |= cj ∧ j ∈ K ask c do P , B >, CL, CA, CU >, CC, S >→<<< Pj , B >, CL, CA, CU >, CC, S > k k k∈K P ASK2,1 : <<< S|=¬cj ∧j∈K P ask c do P ,B>,CL,CA,CU >,CC,S>→<<< k k k∈K k∈K−{j} ask ck do Pk ,B>,CL,CA,CU >,CC,S> P ASK2,2 : <<< K=∅ j∈K ask ck do Pk , B >, CL, CA, CU >, CC, S >→<<< skip, B >, CL, CA, CU >, CC, S > P 55 ASK3 : <<< K6=∅∧¬∃j∈k .(S|=cj ∨ S|=¬cj ) P ask c do P ,B>,CL,CA,CU >,CC,S>→<<,CL,< k k k∈K k∈K ask ck do Pk ,B>::CA,CU >,CC,S> P La regla U N LESS presenta tres casos. El primer caso es cuando hay todav´ıa procesos en la cola CL, por lo cual se pospone la ejecuci´on del proceso unless adicion´andolo a la cola CU . El segundo activa el unless solo si, CL se encuentra vac´ıa y la guarda no se deduce. Finalmente, el tercer caso considera la no activaci´on del proceso unless debido a que se cumple la guarda(c). U N LESS1 : CL6={} <<,CL,CA,CU >,CC,S>→<<,CL,CA,::CU >,CC,S> U N LESS2 : S2c <<< unless c do next P >, B, ∅, CA, CU >, CC, S >→<<< next P, B >, ∅, CA, CU >, CC, S > U N LESS3 : S |= c <<< unless c do next P, B >, ∅, CA, CU >, CC, S >→<<< skip, B >, ∅, CA, CU >, CC, S > La regla LOC permite crear variables locales al proceso P , de modo que la nueva variable solamente pueda ser vista por P ; para esto se selecciona una nueva etiqueta L del universo de posibles etiquetas Uloc que haya sido utilizada en el rango de localidades (ran(B)). LOC : L ∈ Uloc − ran(B) <<< local x in P, B >, CL, CA, CU >, CC, S >→<<< P, B + (L ← |x) >, CL, CA, CU >, CC, S > La regla N EXT 1 ejecuta el proceso en el siguiente instante de tiempo, por lo cual se adiciona a la cola CC. N EXT 1 : <<< next P, B >, CL, CA, CU >, CC, S >→<<< skip, B >, CL, CA, CU >, < P, B >:: CC, S > 56 La segunda regla de N EXT 2 sirve para manejar la abreviaci´on de nextn , que se denota (next(next......(nextP ))), n veces. N EXT 2 : n>1 <<< nextn P, B >, CL, CA, CU >, CC, S >→<<< skip, B >, CL, CA, CU >, < nextn−1 P, B >:: CC, S > La regla P AR ejecuta Q y adiciona P a la cola CL para su futura ejecuci´on. P AR : <<< (P |Q), B >, CL, CA, CU >, CC, S >→<<< Q, B >, < P, B >:: CL, CA, CU >, CC, S > La regla REP ejecuta el proceso P y crea una “copia” que es adicionada a la cola CC para ejecuci´on en los siguientes instantes. REP : <<, CL, CA, CU >, CC, S >→<<< P, B >, CL, CA, CU >, :: CC, S > Por ultimo la regla ST AR permite modelar una espera aleatoria finita de un evento, escogiendo una unidad de tiempo entre i y j para activar P . ST AR : n ∈ i..j <<< ?[i, j]P, B >, CL, CA, CU >, CC, S >→<<< skip, B >, CL, CA, CU >, < nextn P, B >:: CC, S > Las siguientes propiedades pretenden expresar la relaci´on entre la definici´on formal de la m´aquina abstracta y el c´alculo NTCC: 3.2.4.1. Conjetura 1: Correctitud de Transiciones No Observables Sea P un proceso NTCC y d un Store. Entonces en NTCC < P, d >→∗ < Q, d0 > si y solo si << skip, ∅, << P, var(P ) >, ∅, ∅ >, ∅, d >→∗ << skip, B, << Q, B 0 >>, CA, CU >, CC, d0 > 57 3.2.4.2. Conjetura 2: Correctitud de Transiciones Observables Sean R y P procesos de NTCC. Entonces: P ⇒(c,d) R si y solo si << skip, ∅, << P, var(P ) >, ∅, ∅ >, ∅, c >⇒(c,d) << skip, B, ∅, CA, ∅ >, << R, B 0 >>, d0 > Donde: V ar(p) es la asociaci´on de localidades con las variables libres de P ⇒(c,d) representa en la m´aquina, la transici´on por medio de multiples reducciones entre el inicio de una unidad de tiempo con Store c y el final de la misma con Store d. Es importante mencionar que la regla expresada en la Conjetura 2, es quien define el input-output behavior de la m´aquina con respecto a NTCC y el ambiente. El proceso que comienza en la unidad de tiempo actual P se representa como el u ´nico proceso que contiene la cola de listos (CL), tal como se define en la regla SCHED1; despu´es de presentar m´ ultiples transiciones no observables (Conjetura 1) llega a la regla SCHED3, dando como resultado un Store final d, que contiene las instrucciones para a ejecutar por el ambiente y el proceso residual R en la cola de construcci´on CC para ejecuci´on en instantes posteriores. De ´esta manera, todos los instantes en la m´aquina pueden ser modelados siguiendo el anterior comportamiento; lo cual resulta similar al comportamiento que presenta NTCC en su definici´on de input-output behavior [Val03]. 3.2.5. Diagrama de Transici´ on En la figura 3.2, se muestra el diagrama de transici´on de la m´aquina abstracta, el cual se construye con base en las reglas de reducci´on descritas anteriormente. El comportamiento del diagrama de transici´on es el siguiente: 1. Cuando el proceso en ejecuci´on llega a skip, se pasa el siguiente proceso de la cola CL para ejecuci´on(regla SCHED1). 58 Figura 3.2: Diagrama de Transici´on LMAN 2. Si se encuentra un proceso next P o nextn P en ejecuci´on se pasa a la cola CC(regla N EXT 1 y N EXT 2). 3. Si el proceso en ejecuci´on es replicaci´on (!), se deja P y se pasa !P a CC(regla REP ). 4. Cuando el proceso en ejecuci´on es when y no se puede resolver por falta de informaci´on en el Store, se encola en CA(regla ASK3). 5. Cuando el proceso en ejecuci´on es un unless y la cola CL no esta vac´ıa, el proceso se encola en CU (regla U N L1). 6. Si el proceso en ejecuci´on es un tell, los procesos suspendidos en CA se adicionan a la cola CL(regla T ELL). 7. Si la cola CL se encuentra vac´ıa, se pasan a ejecuci´on los procesos en CU (regla SCHED2). 8. Cuando CL y CU se encuentren vac´ıas, se crea una nueva m´aquina y se transfiere el contenido de CC a CL en la nueva m´aquina(regla SCHED3). 59 Se observa que el ciclo de transiciones est´a determinado por las tres reglas SCHED, que definen la forma en que se mueven los procesos en las colas: primero deben ejecutarse todos los procesos en la cola CL(SCHED1), luego los procesos en la cola CU (SCHED2) y por ultimo cuando las dos colas anteriores se encuentran vac´ıas, se construye a partir de los procesos residuales en CC(SCHED3), la nueva m´aquina para el siguiente instante de tiempo. 60 ´ 4 LMAN: MAQUINA VIRTUAL En ´este cap´ıtulo se describe la arquitectura e implementaci´on de la m´aquina virtual de NTCC para programaci´on concurrente de robots LEGO. El objetivo principal es dise˜ nar una m´aquina eficiente, modular y que provea la funcionalidad b´asica para programaci´on concurrente, particularmente sobre robots LEGO. El modelo formal presentado en el cap´ıtulo anterior provee la especificaci´on para la m´aquina virtual. Es importante notar, que en LMAN se modela adem´as de la programaci´on concurrente, la programaci´on temporal (al definir instantes de tiempo para ejecuci´on), y la programaci´on por restricciones con el uso de un Sistema de Restricciones para gestionar el almacenamiento de la informaci´on. Todos estos componentes han sido integrados en LMAN, de modo que es posible aplicarlos para programar dispositivos rob´oticos LEGO. A continuaci´on se presentan los aspectos de dise˜ no e implementaci´on de la m´aquina virtual. 4.1. Arquitectura General La m´aquina virtual de LMAN consta de cuatro bloques funcionales: memoria de programa, interfaz LEGO, interfaz STORE y controlLMAN , interactuando tal como se muestra en la figura 4.1. La memoria de programa guarda las instrucciones del programa en c´ odigo de bytes y es est´atica, es decir, que no es modificable en tiempo de ejecuci´on. La interfaz STORE es el m´odulo que permite interactuar con el Sistema de Restricciones asociado a LMAN. Este bloque funcional crea el Store donde se almacenan las restricciones durante el instante actual y luego lo destruye al final del mismo. La interfaz LEGO es el bloque encargado de manejar el ambiente externo. 61 Figura 4.1: Bloques Funcionales de LMAN ControlLMAN, act´ ua como el cerebro ejecutor de la m´aquina virtual. Este bloque es el encargado de planear m´aquinas y procesos, de ejecutar el programa almacenado en la memoria de programa, de comunicarse con la Interfaz STORE por medio de operaciones ask y tell, de comunicarse con la Interfaz LEGO para sensar el ambiente y ejecutar instrucciones sobre el robot y, finalmente, es el encargado de construir el siguiente instante, asegurando siempre continuidad en la ejecuci´on, a menos de que exista un bloqueo en el Store. Como se ha mencionado anteriormente, LMAN a diferencia de otras implementaciones de m´aquinas para c´alculos de procesos [AB98, Lop99], introduce la noci´on de Planeaci´on de M´ aquinas. Esta noci´on hace referencia a que solo debe existir una y solo una m´aquina activa por instante de tiempo; esto se representa en la figura 4.1 como una l´ınea punteada rodeando la m´aquina activa en el instante actual. De ´esta manera, aunque se define una cola de m´aquinas al interior del control, siempre existir´a una y solo una m´aquina activa por instante de tiempo. La Planeaci´ on de Procesos en LMAN hace referencia al 62 manejo de colas y registros que permiten ejecutar cada una de las instrucciones LMAN equivalentes a un proceso en NTCC. Para cada m´aquina en LMAN se definen tres registros y tres colas de procesos: PCN es el registro contador de programa, PAN es el registro utilizado para construir ´arboles sint´acticos de restricciones y PAUX es el registro auxiliar. Respecto a las colas, CL almacena los procesos listos para ejecuci´on, CA almacena los procesos ask suspendidos y CU almacenan los procesos unless que se ejecutan solo al final de cada instante. La cola CC se define externamente a la m´aquina activa, ya que almacena los procesos residuales del instante actual, que pasaran a ejecuci´on en los siguientes instantes de tiempo. LMAN ha sido dise˜ nada en bloques funcionales de modo que se confiera modularidad a la implementaci´on. El c´odigo ha sido escrito en C por eficiencia, y sigue la estructura de un kernel de sistema operativo para efectividad en la ubicaci´on de los archivos relacionados en la implementaci´on. Inicialmente, LMAN pretend´ıa ser ejecutada desde el robot LEGO, siendo almacenada en los 10K o 14K de memoria RAM destinada para el bloque del programa LEGO. Sin embargo, debido a que LMAN integra la implementaci´on de un Sistema de Restricciones param´etrico inicialmente creado para el c´alculo PiCO [CG01], el tama˜ no de la implementaci´on excedi´o el tama˜ no del espacio disponible. Por lo tanto, para suplir ´este inconveniente en la implementaci´on, se dise˜ n´o un ambiente de ejecuci´on particular para LMAN. En este ambiente de ejecuci´on, LMAN y el Sistema de Restricciones asociado corren sobre una estaci´on de trabajo, donde LMAN se comunica con el LEGO v´ıa protocolo LNP(Lego Network Protocol). En el LEGO por su parte, se ejecuta un segundo componente de LMAN que realiza dos funciones: en primer lugar, se encarga de sensar el ambiente del robot y enviarlo a la m´aquina y en segundo lugar, se encarga de recibir el resultado de la computaci´on y de ejecutarlo sobre el robot LEGO, exhibiendo las tareas programadas. Cada uno de los componentes de la arquitectura de la m´aquina virtual anteriormente mencionados y su funcionamiento, ser´an tratados en detalle en las siguientes secciones de este cap´ıtulo. 63 4.1.1. Memoria de Programa La memoria de programa es una memoria est´atica, es decir que no es modificable en tiempo de ejecuci´on. Su funci´on es almacenar el c´odigo del programa expresado en c´ odigo de bytes, por lo cual se implementa como un arreglo en memoria f´ısica. En el modelo de memoria de LMAN, no se utiliza una memoria din´ amica o de traducci´on para el manejo de variables. Tomando ventaja de la definici´on de recursi´on que confiere el c´alculo NTCC, en donde la recursi´on es reemplazada por replicaci´on “ !”, por lo cual cada llamado recursivo se extiende al siguiente instante de tiempo, y tambi´en buscando eficiencia en el desempe˜ no de la m´aquina; se delega la tarea del manejo de variables, particularmente de la generaci´on de nuevas variables y sus alcances o ligaduras, al compilador. A continuaci´on se describen cada uno de los aspectos relacionados con la memoria del programa y su implementaci´on. 4.1.1.1. Estructura de Datos La estructura de datos que representa la memoria del programa en LMAN sigue a continuaci´on: #define MAX_ARCH 1500 //memoria del programa char fp[MAX_ARCH]; 4.1.1.2. Formato de Instrucciones El cuadro 4.1 describe el formato de instrucciones utilizado en el c´ odigo de bytes de LMAN. Para fines de optimizaci´on se eligi´o un formato fijo de longitud 24 bytes, que admite 64 instrucciones de m´aquina y direccionar m´aximo 8192 l´ıneas de c´odigo. Se manejan adem´as de un opcode, dos fuentes en la definici´on de las instrucciones. 64 Opcode 6 src1 13 src2 5 Cuadro 4.1: Formato de Instrucciones de LMAN 4.1.1.3. Conjunto de Instrucciones La figura 4.2 describe el conjunto de instrucciones, opcode, src1 y src2 de LMAN. En el cuadro 4.3 se encuentran las especificaciones dadas para los campos fuentes Src1 y Src2. Obs´ervese que cada una de estas instrucciones corresponde a los procesos definidos en la sem´antica de NTCC. El uso de las instrucciones de LMAN se trata en detalle en el anexo A sobre Traducci´on de procesos NTCC a c´odigo de bytes de LMAN. 4.1.2. Interfaz STORE Con el fin de lograr que el Sistema de Restricciones asociado a LMAN se adicione param´etricamente, las restricciones son definidas como f´ ormulas–de–primer–orden (f po). Una f po es una expresi´on construida a partir de f´ormulas at´omicas combinadas con conectores l´ogicos not, and, or, y cuantificadores ∃, ∀; los ´atomos b´asicamente tienen la construcci´on de ecuaciones o inecuaciones matem´aticas. Ejemplos: (x+y > 6)∧(z = 1), x = 2 , entre otras. Teniendo en cuenta la definici´on anterior, cualquier Sistema de Restricciones que pueda expresar sus restricciones como f po, puede ser integrado a LMAN. En la actual implementaci´on ha sido acoplado el Sistema de Restricciones optimizado para el Lenguaje CORDIAL[CG01] y la M´aquina MAPICO [AB98]. LMAN usa la sint´axis que se muestra en la figura 4.4 para la especificaci´on de f po[McA92]; ´esta se toma de la definici´on usada por MAPICO[AB98] en su adici´on del Sistema de Restricciones ya mencionado[CG01]. Este sistema de restricciones de dominios finitos[CG01] usado en LMAN, contiene el P sistema de restricciones aritm´etico–modular propuesto para NTCC. est´a dado por >, <, ≤, ≥ . +, −, ∗, /, =, <>. Es param´etrico como ya se ha mencionado anteriormente; de modo que, utiliza f po como entradas representadas en estructuras de ´arbol. Se basa en el modelo de Bjorn Carlson [Car95], as´ı que utiliza la noci´on de indexicals y algoritmos de arco-consistencia en su implementaci´on. Por eficiencia, fue implementando en lenguaje C, registrandose tiempos de ejecuci´on aceptables para diversos problemas 65 Figura 4.2: Conjunto de Instrucciones de LMAN 66 Figura 4.3: Especificaci´on de Fuentes Src1 y Src2 en el dominio de concurrencia. Para el acople del sistema de restricciones con LMAN, se realizaron algunas modificaciones. Estas se describen a continuaci´on: Para asegurar equivalencia entre las estructuras para representar restricciones usadas en el sistema de restricciones y en LMAN, se modific´o la implementaci´on de ´arboles con encadenamiento sencillo, por ´arboles con encadenamiento al padre. El doble puntero se hizo necesario para asegurar consistencia en el ´arbol cuando se construye la restricci´on a partir del c´ odigo de bytes de LMAN. Al final de cada instante de tiempo, se hace necesario realizar una consulta al Store (Browse) acerca de las variables de ambiente. El resultado de ´esta consulta es enviando al LEGO para ejecuci´on. De esta manera, se adicion´o al sistema de restricciones una funci´on que consulta el estado de las variables; particularmente en LMAN se consultan solamente las variables del ambiente. Si la variable tiene un valor fijo, se env´ıa ese valor; de lo contrario, si la variable tiene asociado un rango, se realiza un selecci´on aleatoria de un valor en el rango. El valor de n para el sistema de restricciones se redefini´o en 500 (aritm´etica– m´odulo 501). De ´esta manera, es posible asignar rangos de 0 a 500. En el acople del sistema de Restricciones con LMAN, se implementaron ´arboles binarios; es decir, que los predicados y funciones deben definirse de aridad 2. No obstante, la sint`axis de f´ormulas bien formadas usada para expresar restricciones 67 en LMAN admite la definici´on de aridad n, de manera que ser´ıa posible extender su uso. Figura 4.4: Sint´axis para la especificaci´on de F´ormulas de Primer Orden en LMAN 4.1.2.1. Estructura de Datos La estructura de datos que representa la interfaz con el STORE se muestra a continuaci´on: typedef struct InterfazSTORE{ Store s; Indexicals Stamp st; int i; indextemp; }InterfazSTORE; 68 4.1.2.2. Instrucciones asociadas al Sistema de Restricciones de LMAN Las instrucciones para construir f po en LMAN se describen en la figura 4.5. Figura 4.5: Instrucciones para construcci´on de restricciones en LMAN Los posibles valores que se definen para funciones y predicados se describen a continuaci´on. El sistema de restricciones actualmente usado por LMAN, no modela conectores l´ogicos, ni rangos, ni cuantificadores. Funciones: ADD, SUBS, MULT, DIV, MOD. Pred: IGUAL, DIF, MAY, MAI(mayor o igual), MEN, MEI(menor o igual). 4.1.2.3. Construcci´ on de Restricciones en LMAN A partir de las instrucciones presentadas en la figura 4.5, se construyen las restricciones en LMAN. La siguiente restricci´on, se expresa en LMAN como un ´arbol binario de notaci´on infija (ver figura 4.6). 69 ( y + 2) = (x ? 4) – (z ÷ 6) Figura 4.6: Arbol binario infijo que representa una restricci´on en LMAN Del ´arbol de la figura 4.6, que contiene una restricci´on expresada como formula–de– primer–orden se construye la restricci´on que recibir´a el Sistema de Restricciones usado por LMAN. Teniendo en cuenta las instrucciones descritas en la figura 4.5 y asumiendo que la variable “x” tiene la etiqueta 74, “y” la etiqueta 75 y “z” la etiqueta 76; el c´odigo necesario para construir la restricci´on es el siguiente: 1 ATOM IGUAL 2 // = 2 TERMF ADD 2 // + 3 TERMV 75 0 // y 4 5 TERMC TERMF 2 SUBS 0 2 // 2 // - 6 TERMF MULT 2 // * 7 TERMV 74 0 // x 8 9 TERMC TERMF 4 DIV 0 2 // 4 // / 10 TERMV 76 0 // z 11 TERMC 6 0 // 6 Del anterior bloque de c´odigo, se aprecia c´omo la restricci´on se construye siguiendo una notaci´on infija donde primero se describe el operador y luego los t´erminos varia70 bles o constantes asociados a la operaci´on. En el Sistema de Restricciones actual las restricciones se construyen como ´arboles binarios, luego la aridad aceptada es 2. ( ari = 2).YA que LMAN acepta cualquier Sistema de Restricciones param´etrico; la sintaxis de restricciones requiere que la aridad se haga explicita como un par´ametro. (Ver figura 4.5). 4.1.3. Interfaz LEGOS Un RCX es un microcontrolador programable basado en LEGO brick con un Hitachi H8/300 como coraz´on y 32K en memoria RAM. Este puede operar simult´aneamente tres actuadores, tres sensores y un sistema IR; adicionalmente, con el RCX se incluye una bater´ıa y diferentes piezas intercambiables para crear variedad de dispositivos rob´oticos aut´onomos. Es posible programar RCX en alto nivel utilizando combinaciones de firmwares como legOS, lejOS, Lego MindStorm firmware junto con lenguajes como C, Java, NQC, entre otros. El m´odulo de la interfaz LEGOS es el encargado de la interacci´on con el ambiente, en otras palabras, es el encargado de controlar las variables asociadas al RCX. En LMAN el ambiente se define como una estructura que permite controlar los motores, los sensores, el sonido y la bater´ıa; definiendo para cada uno de estos componentes los atributos necesarios para modelar adecuadamente el comportamiento del robot. La figura 4.7 ilustra la estructura usada para modelar el ambiente y para construir el paquete de datos que se transmite entre el computador y el RCX. N´otese que ´este m´odulo permite programar el doble de dispositivos de un RCX convencional, con el fin de admitir expansiones sobre los RCX o para modelar sistemas colaborativos entre RCX. Figura 4.7: Ambiente LEGO en LMAN Al finalizar ´esta secci´on que define la interfaz LEGOS, se presenta una breve descripci´on de los dispositivos LEGOS y sus capacidades. 71 4.1.3.1. Estructura de Datos Las estructuras de datos utilizadas para modelar el ambiente LEGO se definen a continuaci´on: //entrada define el estado y el valor typedef struct { char est; char val; }entrada; //sensor define el tipo, estado y el valor de los sensores typedef struct { char tipo; char est; char val; }sensor; //soundl define el estado, la nota y la duracion de los controladores de sonido typedef struct { char est; char nt; char dur; }soundl; //se modela el ambiente LEGO typedef struct { //definicion de motores entrada mot[7]; //definicion de sensores de movimiento sensor sen[7]; //definicion de bateria entrada bat[3]; //definicion para manejo de musica soundl snd[3]; 72 }ambiente; 4.1.3.2. Ambiente LEGO En LMAN las variables son representadas por etiquetas num´ericas u ´nicas, que comienzan desde 1 y van increment´andose de uno en uno. Para modelar la interacci´on de LMAN con el ambiente, se reservan unas etiquetas fijas destinadas para definir variables de entrada, las cuales informan sobre c´omo se encuentra el ambiente y variables de salida, que contienen la informaci´on de qu´e va a ser ejecutado sobre el LEGO. Se debe de tener en cuenta, que para dar escalabilidad a la implementaci´on de LMAN, se habilitaron el doble de dispositivos de un RCX convencional. Es decir, que LMAN permite trabajar con 6 sensores, 6 motores, 2 bater´ıas y 2 manejadores de sonido. El LCD o display que permite visualizar mensajes en el LEGO no fue modelado, ya que el Sistema de Restricciones no incluye la posibilidad del manejo de cadenas. No obstante, el LCD se utiliza para visualizar mensajes de depuraci´on durante la ejecuci´on de programas. A continuaci´on se describe en detalle el uso de variables que hace LMAN. La notaci´on utilizada para las variables es may´ uscula, ya que se definen como constantes en la m´aquina virtual. 4.1.3.2.1. Variables de Entrada . Las variables de entrada comienzan en la etiqueta 1 y van hasta 34, estas se encuentran divididas de la siguiente forma: Motores: Cada uno de los 6 Motores, contiene 2 variables para indicar los atributos a continuaci´on. El total de variables de Motores es 12. Estado: Indica si est´a encendido el motor y en que direcci´on se desplazar´a. Los valores posibles: 0 Apagado, 1 Adelante, 2 Atr´as, 3 Frenar. Ejemplo: IMOTEST1 = 1, indica que el motor 1 tiene estado Adelante. Valor: Indica la velocidad que tiene el motor. Valores: 0 a 255. Ejemplo: IMOTSP1=80 indica que la velocidad del motor 1 se configura en 73 80. Sensores: Cada uno de los 6 Sensores contiene 2 variables para indicar los atributos a continuaci´on. El total de variables definidas para los sensores es 12. Tipo: Indica el tipo de sensor que se utiliza: 1 tacto, 2 luz, 3 rotacion, 4 temperatura; 5 y 6 se reservan en caso de que se adiciones m´as sensores. Estos valores deben asignarse a las constantes que definen los tipos de sensores en la interfaz LEGO. Estado: Indica si el sensor se ha habilitado o no. Valores: 1 o 0. Ejemplo: ISENEST1=1 indica que el sensor 1 se encuentra activo. Valor: Indica el valor del sensor, por ejemplo si el sensor es de tacto dice si esta oprimido o no. Ejemplo: ISENVAL1=1 para un sensor de tacto, indica que el sensor ha sido oprimido. Bater´ıas: Cada una de las 2 Bater´ıas contiene 2 variables para indicar los atributos a continuaci´on. El total de variables definidas para bater´ıas es 4. Estado: Indica si la Bater´ıa esta en funcionamiento o no. Valores: 1 o 0. Ejemplo: IBATEST1=1, indica que la bater´ıa 1 est´a en funcionamiento. Valor: Indica le nivel de energ´ıa de la Bater´ıa. Valores: 0 a 255. Ejemplo: IBATVAL1=180, indica que la bater´ıa 1 tiene un nivel de energ´ıa de 180. Sonido: Cada uno de los 2 controladores de Sonido contiene 3 variables para indicar los atributos a continuaci´on. El total de variables asociadas a los controladores de sonido es 6. Estado: Indica si est´a en funcionamiento el controlador de Sonido o no. Valores: 1 o 0. Ejemplo: ISNDEST2=1, idica que el estado del controlador 2es activo. Nota: Indica la Nota y la escala de la misma. Valores: 0 a 255. Ejemplo: ISNDNT2=55, representa la nota LA en escala 5 para el controlador 2. 74 Duraci´on: Variable opcional para delimitar el tiempo de duraci´on de la nota. Valores: 0 a 255. Ejemplo: ISNDDUR2=2, representa duraci´on de una octava para una nota ya definida en el controlador 2. 4.1.3.2.2. Variables de Salida . El manejo de las variables de salida es similar a las variables de entrada, con la diferencia que inician en la etiqueta 35 y terminan en la etiqueta 68. Para el caso de las constantes que definen las etiquetas, solo se hace el cambio de la letra inicial I (INPUT) por la O (OUTPUT). Ejemplo: Variable de Entrada: ISNDDUR1 Variable de Salida: ONDDUR1 4.1.3.2.3. Variables de Usuario . A partir de la etiqueta 69 inician las variables que pueden usar los programas de usuario. 4.1.3.3. Protocolo de comunicaciones LMAN utiliza en su funcionamiento el protocolo LNP (Lego Network Protocol ) del Sistema Operativo LegOS. Este protocolo posibilita la comunicaci´on entre varios RCX y varias estaciones de trabajo. Existe sobre los lenguajes C, Java y Python. Act´ ua como un protocolo UDP (User Datagram Protocol ), por lo cual no realiza acuso de recibo o chequeos de integridad en la recepci´on de paquetes. LNP es usado en la implementaci´on de LMAN, para suplir el inconveniente de tama˜ no en memoria, por el cual se imposibilitaba la ejecuci´on de la m´aquina desde el mismo dispositivo LEGO. Consecuentemente, se hizo necesario implementar un protocolo de entrega y recepci´on de datos que usa LNP para el env´ıo, tal como se describe a continuaci´on. El protocolo modelado no es complejo, utiliza asincron´ıa y time-out para asegurar entrega de datos. Una Bandera determina el tipo del enlace. 75 Protocolo del lado de la estaci´ on de trabajo: Ver figura 4.8 1. Se env´ıa al LEGO, la BANDERA en estado de sensar (1). 2. La estaci´on de trabajo espera la respuesta con el ambiente sensado por el RCX. 3. Si se presenta un time-out(No se recibe respuesta), se regresa al paso 1. 4. Se env´ıa al LEGO, la BANDERA en estado de ejecutar (2). Figura 4.8: Protocolo del lado de la estaci´on de trabajo en LMAN Protocolo del ladol RCX: Ver figura 4.9 1. El RCX espera la BANDERA. 2. Si el estado de la BANDERA es sensar (1), el RCX sensa el ambiente. 3. EL RCX env´ıa el ambiente sensado a la estaci´on de trabajo. 4. Si el estado de la BANDERA es ejecutar (2), el RCX captura el ambiente recibido. 5. El RCX ejecuta el ambiente. 4.1.3.4. Dispositivos Rob´ oticos LEGO El RCX 2.0 Robotics Command System (Ver figura 4.10) es un dispositivo brick programable [Gro00]. Cuenta con 3 puertos de entrada para sensores, 3 puertos de salida, 76 Figura 4.9: Protocolo del lado del RCX en LMAN cuatro botones de control, un display LCD, y un transmisor de infrarrojos. Adicionalmente, posee un microprocesador para el procesamiento de programas, una memoria interna para almacenar el firmware y los programas y un speaker para producir beeps y tonos. 4.1.3.4.1. LEGO Brick . Los puertos de sensores permiten conectar sensores de luz, tacto, rotaci´on y temperatura. Los dos u ´ltimos no se incluyen en el kit LEGO MindStorm. Los puertos de salida permiten conectar motores y otros dispositivos como luces que no se incluyen en el kit. Adicionalmente es posible conectar otros LEGO bricks. Internamente el dispositivo cuenta con 3 sensores internos: temporizador, para mantener un rastro del tiempo; un manejador de mensajes, que espera por mensajes enviados por otros RCX y por u ´ltimo, variables definidas por el usuario. Por medio de ´estos dispositivos, el robot puede moverse y reaccionar con su ambiente.El brick requiere 6 bater`ıas AA/LR6 de 1.5 voltios para su funcionamiento. La torre IR es la encargada de establecer un enlace inhal´ambrico entre la estaci´on de trabajo y el RCX. Por medio de la torre IR que utiliza se˜ nales infrarrojas para enviar mensajes, se descarga el firmware y los programas a la memoria del RCX. Para descarga la distancia sugerida entre la torre y el RCX es 10-12 cm; en condiciones ´optimas de luz se puede transmitir hasta una distancia de 30 metros usando una torre USB. 77 Figura 4.10: RCX LEGO brick 4.1.3.4.2. Firmware y lenguajes de programaci´ on . El firmware es un software especial que posibilita la comunicaci´on entre una estaci´on de trabajo y el RCX. Act´ ua como el sistema operativo del RCX. En la actualidad existen diversos m´etodos para programar RCX; los cuadros 4.2 y 4.3 resumen algunos de los m´as utilizados. 4.1.3.4.3. Modelos de Robots . Las piezas intercambiables de LEGO pueden utilizarse para construir diferentes tipos de robots, la figura 4.11 muestra algunas de las opciones m´as utilizadas. EL presente trabajo se prueba sobre un modelo Roverbot. 78 Firmware Autor Tipo Lenguajes Plataformas Descripci´ on Firmware Autor Tipo Lenguajes Plataformas Descripci´ on Firmware Autor Tipo Lenguajes Plataformas Descripci´ on BrickOS (legOS) Markus L. Noga Reemplazo de Firmware C,C++ Desarrollado sobre x86 GNU/Linux, probado sobre PPC Linux. Es portable en Cygwin-DJGPP sobre MSWindows y soportado en Mac. LegOs es un sistema operativo multitarea para el RIS (Robotics Invention System). Los programas son escritos en C,C++ compilados en la estaci´on usando gcc-cross-compiler y luego descargados al RCX para ejecuci´on. Incluye random, punto flotante, hilos con sem´aforos, y almacenamiento m´ ultiple de programas. Permite recibir y enviar datos entre estaciones windows o linux. Usa la velocidad nativa del mircroprocesador (16 MHz) y utiliza LNP como protocolo de comunicaci´on basado en transmisor de infrarrojo con el RCX. Es una poderosa alternativa para RCX. Not Quite C (NQC) Dave Baum compilador de c´odigo de bytes nativo lenguaje similar a C, llamado Not Quite C. GNU/linux, MS Windows, y Macintosh. NQC es un compilador de c´ odigo de bytes que toma programas escritos en una sint´axis similar a C y la traduce a un c´odigo de bytes que el firmware utilizado en el LEGO pueda entender. NQC tiene limitaciones en el numero de variables dispobibles que es 32, no existen estructuras de datos, las subrutinas no pueden retornar valores, solo pueden usarse variables globales y las subrutinas no admiten param´etros. Tiny VM y leJOS Jos´e Solorzano Reemplazo de firmware Java GNU/Linux, Win32. Tiny VM es una implementaci´on de la M´aquina Virtual de Java que se descarga en el RCX para sustituir el firmware estandar. Los programas para Tiny VM, pueden usar algunas librer´ıas java estandar y una librer´ıa disponible para el control de sensores y motores del LEGO. Los programas escritos en java, requieren ser compilados y luego descargados en el RCX para su ejecuci´on. leJOS es un proyecto similar realizado por el mismo autor, que incluye adiciones como soporte de punto flotante y cadenas. Cuadro 4.2: Alternativas de programaci´on de RCX 79 Firmware Autor Tipo Lenguajes Plataformas Descripci´ on Firmware Autor Tipo Lenguajes Plataformas Descripci´ on Pylnp Les Smithson Libreria de control remoto Phyton GNU/Linux. Pylnp es una libreria de control remoto que a difrencia de otras librerias, interact´ ua con legOS y no con el firmware estandar. Esto posibilita que el usuario pueda invocar funcionalidades legOS. Lego::RCX.pm John C. Quillan Remote control library Perl GNU/Linux, MS Windows y Solaris Lego::RCX.pm es una librer´ıa perl para el control remoto de el RCX utilizando la torre IR para enviar los comandos al firmware estandar para que ´este, los interprete y act´ ue. Cuadro 4.3: Alternativas de programaci´on de RCX Figura 4.11: Algunos ejemplos de modelos LEGO 80 4.1.4. ControlLMAN Con todos los m´odulos anteriores dispuestos, controlLMAN es quien se encarga de gestionar recursos, tareas y el tiempo. Cabe mencionar que el instante de tiempo definido para LMAN no se rige por un reloj expl´ıcito; el fin del instante lo define la ausencia de procesos en las colas. Es decir, que el instante termina cuando tanto la cola de procesos listos (CL) como la cola de procesos Unless(CU) se encuentran vacias. 4.1.4.1. Estructura de Datos La estructura de Datos que modela el control se muestra a continuaci´on. ColaM es la implementaci´on de colas de m´aquinas y ColaP es la implementaci´on de colas de procesos. LZumatoria es la implementaci´on de listas de guardas, donde el TAD guarda es utilizado para modelar la lista de ask del proceso guarded-choise en el c´alculo. Solo se admite un nivel en ´esta estructura, es decir que no puede definirse un proceso sumatoria dentro de otro proceso sumatoria. Las estructuras de m´aquinas y procesos se muestran a continuaci´on: typedef struct controlLMAN{ //cola de m´ aquinas, se define una m´ aquina por instante ColaM cMaquinas; //cola de construcci´ on de la m´ aquina del siguiente instante ColaP cConstruccion; //memoria del programa char fp[MAX_ARCH]; //store InterfazSTORE iStore; }ControlLMAN; typedef struct MAQUINA { int PCN; //registro contador PCN de la maquina FrameConst PAN; //registro apuntador de restricciones de la maquina FrameConst PAUX; //registro auxiliar de la m´ aquina ColaP cListos; //cola de procesos listos ColaP cAsk; //cola de procesos ask suspendidos 81 ColaP cUnless; } Maquina; //cola de procesos unless typedef struct PROCESO { int PC; FrameConst PA; //registro contador del programa //registro apuntador al arbol restricciones FrameConst PAux; //registro auxiliar int instante; //almacena instante actual, usado para reglas star y next ListaG lZumatoria; } Proceso; //guarda la lista de when asociadas a una zumatoria typedef struct GUARDA { int PC; FrameConst PA; //registro contador del programa //registro apuntador arbol restricciones char marca; //utilizada para la regla gask, ndet } Guarda; 4.1.4.2. Gesti´ on de ControlLMAN La gesti´on que realiza el control puede resumirse en la figura 4.12. ControlLMAN es quien regula la ejecuci´on de la m´aquina ”mientras no se presente un error ”, es decir que mientras existan reducciones que no generen bloqueos o errores en la m´aquina, ´esta se ejecutar´a infinitamente. El control define un nuevo instante e inicia el estado de ”Planeaci´on de M´aquinas”. En este estado y para un instante diferente al inicial, el control destruye la m´aquina y el Store anterior, crea la nueva m´aquina y Store para el instante actual; y procede a sensar el ambiente y a comentar su resultado en el Store. Si se trata del instante inicial, simplemente crea la m´aquina y el Store para comenzar la computaci´on. A continuaci´on llega al estado de Ejecuci´ on, en donde ejecuta secuencialmente las instrucciones almacenadas en la memoria de programa. En ´este estado es donde realiza la planeaci´on de procesos, que involucra la ejecuci´on de las reglas de reducci´on definidas en la m´aquina abstracta, en otras palabras, ejecuta las transiciones internas. Luego que termina la computaci´on de reglas, llega al estado PonerAmbiente, en donde pregunta al 82 Store por el estado final de las variables asociadas al ambiente y procede a enviar esta informaci´on al LEGO para su ejecuci´on. Con ´este u ´ltimo estado, finaliza el instante, es decir que se produce una transici´on observable y de nuevo el control inicia su ciclo reactivo. Figura 4.12: Gesti´on del controlLMAN 4.2. Funcionamiento de LMAN LMAN requiere como plataforma de Hardware (Ver figura 4.13) los siguientes elementos: RCX 2.0 dispuesto en un modelo de robot LEGO. Torre USB/serial. La transmisi´on v´ıa LNP ha sido probada utilizando una torre serial. Estaci´on de trabajo para la comunicaci´on y procesamiento de LMAN. El sistema ha sido probado ejecut´andose desde una estaci´on Pentium III a 930Mhz, 256KB RAM con linux Debian Woody 3.0. LMAN requiere como plataforma de Software (Ver figura 4.14) los siguientes elementos: 83 Figura 4.13: Requerimientos Hardware del Sistema LMAN Sistema operativo BrickOS, ejecutando Cross Compiler gcc y H8300binutils para controlar el microprocesador del RCX. El sistema ha sido probado para BrickOS versi´on 2.6.1. M´odulo de Comunicaci´on LNP. Driver USB/serial. LMAN incluyendo los m´odulos del Sistema de Restricciones y el Compilador asociados. Figura 4.14: Requerimientos Software del Sistema LMAN Sobre la estaci´on de trabajo se ejecutan LMAN, el Sistema de Restricciones y el Compilador. El RCX debe contener BrickOS (legOS) como firmware y el componente de LMAN dise˜ nado para sensar el ambiente y ejecutar comandos sobre el robot. Con todos estos requisitos dispuestos correctamente, el flujo de datos en el sistema se realiza tal como se muestra en la figura 4.15. 84 La entrada de datos al Sistema se produce desde el editor VINE del Lenguaje Visual VIN o desde el editor de texto gvin configurado para chequear sintaxis NTCC. As´ı, una vez construido el programa NTCC en una de estas dos herramientas y guardado con extensi´on .lmn, se compila haciendo uso del Compilador NTCC-LMAN que traduce entradas NTCC a c´odigo de bytes de LMAN, generando un archivo extensi´on .out. La m´aquina virtual toma como entrada el archivo generado por el compilador e inicia el ciclo reactivo de computaci´on mientras no se produzcan fallos de comunicaci´on o bloqueos en el Store. Si no es el instante inicial, el control crea la m´aquina y Store actuales destruyendo los anteriores, y env´ıa una se˜ nal al RCX (Bandera=1) para indicarle que debe sensar. El RCX recibe la se˜ nal y captura el estado de su mundo; empaqueta ´esta informaci´on del ambiente y la env´ıa hacia LMAN usando la torre IR y el modulo LNP. LMAN entonces, comenta ´esta informaci´on al Store y con ella inicia el procesamiento del programa y las reducciones hasta determinar el fin de la unidad de tiempo. Cuando las colas de ejecuci´on y de procesos unless se encuentran vac´ıas, el control consulta el estado final del Store, y procede a empaquetar ´esta informaci´on y enviarla al RCX(Bandera=2) para ejecuci´on; en este momento se determina el fin de la unidad de tiempo y de nuevo se da inicio al ciclo reactivo. Si entre el env´ıo de la se˜ nal de sensar(Bandera=1) y la recepci´on del paquete con la informaci´on del ambiente, la m´aquina no recibe respuesta; se genera un time–out que retorna al paso de env´ıo de se˜ nal para sensar. Si durante 5 intentos continuos la m´aquina no recibe el paquete, se aborta la ejecuci´on. En ´este momento no ha sido liberado el driver USB para legOS, por lo tanto la comunicaci´on v´ıa LNP en la actual implementaci´on se hace utilizando una torre serial. La figura 4.16 muestra el comportamiento reactivo que sigue LMAN. Cada unidad de tiempo comienza con un Store Inicial Si . Durante la unidad la m´aquina procesa con esta informaci´on como entrada y al final genera una salida que se env´ıa al robot para ejecuci´on. Este procedimiento lo realiza infinitamente mientras no exista un bloqueo en el Store o un fallo en la comunicaci´on. 85 Figura 4.15: Funcionamiento del Sistema LMAN Figura 4.16: Comportamiento reactivo del Sistema LMAN 86 5 COMPILADOR NTCC–LMAN Como ya se ha mencionado en cap´ıtulos anteriores, la implementaci´on del C´alculo NTCC define un flujo que incluye 3 m´odulos: un LENGUAJE VISUAL VIN, un COMPILADOR NTCC-LMAN y una MAQUINA ABSTRACTA LMAN para finalmente permitir programaci´on concurrente de robots LEGO MindStorm. El m´odulo del COMPILADOR NTCC–LMAN, es usado para definir una interf´az de programaci´on de alto nivel para el usuario. Por medio del editor gvin configurado para chequear sintaxis NTCC; el usuario puede construir programas usando la sintaxis propia del c´alculo, y posteriormente compilarlos para generar el c´ odigo de bytes de LMAN. En ´este punto, ya LMAN toma el c´odigo de bytes, procesa y ejecuta sobre el robot. Adicionalmente, debido a que tanto el lenguaje visual VIN ya mencionado, como el compilador utilizan la sintaxis b´asica del c´alculo, se hace posible integrarlos. De ´esta manera, el lenguaje visual genera c´odigo NTCC, que el compilador interpreta y traduce a c´ odigo de bytes de LMAN para ejecuci´on. As´ı con estos tres m´odulos dispuestos, se completa el flujo de implementaci´on de NTCC que permite al usuario programar utilizando, sea el lenguaje ic´onico, el editor NTCC o directamente en las intrucciones de la m´aquina virtual. A continuaci´on se describen las consideraciones del dise˜ no del compilador NTCCLMAN; su desarrollo no est´a considerado entre los alcances del actual trabajo de tesis. La implementaci´on de ´este, fue realizada como proyecto de semestre en el curso de compiladores en la Pontificia Universidad Javeriana–Cali por F. Rocha, J. Chal´a y M. Pab´on [RCP03]. De com´ un acuerdo con el profesor del curso se dise˜ n´o el compilador, y se motiv´o a los estudiantes continuamente para lograr una buena implementaci´on. Al finalizar el semestre se seleccion´o la mejor implementaci´on[RCP03], se acopl´o con la implementaci´on de LMAN y se realizaron las pruebas pertinentes de funcionamiento y desempe˜ no arrojando los resultados esperados en efectividad y eficiencia. 87 5.1. Sint´ axis 5.1.1. Conjunto de Caracteres El conjunto de caracteres b´asico esta formado por: Letras may´ usculas, min´ usculas, d´ıgitos y caracteres especiales: ( ) * [ > < ] ! & .. | \# = + . -\&\& / , Los identificadores de las constantes deben escribirse con letras may´ usculas y los de las variables empiezan con letras min´ usculas y pueden seguir con letras may´ usculas o min´ usculas y numeros. Debido a que LMAN interact´ ua con el robot, es necesario definir una serie de variables que manejan su ambiente. Estas act´ uan como variables globales a todo proceso en NTCC y se definen de dos tipos: de entrada anteponiendo la letra i al listado que se describe a continuaci´on, y de salida anteponiendo la letra o. Ejemplo: imot1, omot1 ... isen1, osen1 ... ivalsnd2, ovalsnd2, entre otras. mot1,mot2, ..., mot6. Identifican los motores del robot. spmot1, spmot2, ..., spmot6. Identifican las velocidades de los motores. sen1,sen2, ..., sen6. Identifican los sensores en funcionamiento. valsen1,valsen2, ..., valsen6. Identifican el estado de los sensores. bat1, bat2. Identifican las bater´ıas en funcionamiento. valbat1, valbat2. Identifican el estado de las bater´ıas. snd1, snd2. Identifican el sonido en funcionamiento. valsnd1, valsnd2. Identifican el estado del sonido activo. 88 when unless next do tell local max min in succ pred skip Cuadro 5.1: Palabras reservadas en el Compilador NTCC-LMAN Las palabras propias del c´alculo son reservadas y no pueden ser usadas como nombres definidos por el usuario; estas se muestran en el cuadro 5.1 Las variables son de tipo entero y tienen un rango definido en los n´ umeros enteros positivos de 0 a n, donde n es una constante definida previamente. Para efectos de este compilador, se tomar´a n = 500. Las variables de salida no pueden tener asignaciones directas mayores a 255, esto se debe las limitaciones de los dispositivos LEGO descritas en la secci´on Interf´ az LEGO del cap´ıtulo que describe la m´aquina virtual. Ejemplo: tell(omot1=289) no es v´alido pues es una asignaci´on directa a una variable de salida mayor a 255. Los comentarios en NTCC se efect´ uan con dos guiones adyacentes “ —- ” en cualquier posici´on de una l´ınea, y terminan con nueva l´ınea. Ejemplo: -- Proceso TELL de NTCC (tell x=5) 5.1.2. Reglas de Producci´ on En la definici´on de la sintaxis para el compilador se tienen las siguientes consideraciones: identifica el nombre de un s´ımbolo (terminal o no terminal) “→” especifica una regla de producci´on y “|” separa las reglas de producci´on que corresponden a un mismo s´ımbolo no terminal. En una regla de producci´on, los s´ımbolos que no est´an encerrados entre” <>” son palabras o s´ımbolos propios del lenguaje. Cuando la definici´on no se hace con una regla de producci´on (no lleva → ), ´esta corresponde a una descripci´on (no formal) del s´ımbolo. 89 A continuaci´on se describe las reglas de producci´on utilizadas por el compilador: 5.1.2.1. Variables y Constantes Los identificadores no declarados se asumen como variables globales. La declaraci´on de variables locales tiene la siguiente forma: < V ar dec > → local < ID list > in | ( local < ID list > ) < ID list > lista de nombres de variables La declaraci´on de constantes tiene la forma: < Const dec > →  | < const dec > const < ID constante > = < Lit int > < Lit int > literal entero < ID constante > nombre de una constante 5.1.2.2. Restricciones El Store se define como una conjunci´on l´ogica de restricciones expresadas como f´ormulas de primer orden. Las reglas para expresar restricciones como f´ormulas de primer orden siguen a continuaci´on: < Constraint > → < Expresion > < Expresion > → < Lit expresion > | < V ar ref erence > |(< Expresion >) | < Expresion > < Operador > < Expresion > | < V ar ref erence > in < Rango > |succ(< Expresion >) |pred(< Expresion >) < Rango > → < Constante > :: < Constante > |– (< Rango >) |min(< Rango >) |max(< Rango >) | < Rango > && < Rango > | < Constante > .. < Constante > 90 < V ar ref erence > → < ID variable > | < ID constante > < Lit expresion > → < Lit int > < Operador > son todos los operadores del cuadro 5.2. < ID variable > nombre de una variable < Constante > → < Lit int > | < ID constante > Los operadores para la construcci´on de restricciones se definen en el cuadro 5.2. En la definici´on del rango el s´ımbolo “::” significa uni´on, el s´ımbolo “–” significa complemento, el s´ımbolo “&&” intersecci´on, y el s´ımbolo “..” representa un rango (inicio y f´ın). Clase de Operador L´ ogico Negaci´ on Relacionales Aritm´ eticos Operador &|| Not = |! = | < | > | ≤ | ≥ +| − | ∗ |/| % Cuadro 5.2: Operadores sobre restricciones 5.1.2.3. Procesos A continuaci´on se muestran las reglas que definen los procesos NTCC:

→ when < Constraint > do P | < P > || < P > | ∗[< Constante >, < Constante >] < P > |!

| unless < Constraint > next < P > | next < Const op > < P > | (< P >) | var dec < P > |

+

| tell < Constraint > | skip < Const op > constante opcional 91 5.1.2.4. Programa Un programa est´a formado por la declaraci´on de constantes y una serie de procesos: < P rograma > → < Const dec > < P rocesos > < P rocesos > → < P > | < P rocesos > < P > Ejemplos de programas NTCC se muestran en el cap´ıtulo 7 de pruebas y ejemplos. 5.2. Sem´ antica Los chequeos sem´anticos que realiza el compilador tratan las operaciones aritm´eticas, relacionales y l´ogicas de las restricciones. Adicionalmente trata los tres puntos que se describen a continuaci´on: Gram´ atica Ambigua . Para evitar que la gram´atica definida para el compilador resultara ambigua, se realiz´o una modificaci´on a la notaci´on con par´entesis utilizada en [Val03]. Esta modificaci´on obliga que toda restricci´on debe escribirse entre par´entesis. Precedencia de Procesos . La precedencia de procesos se presenta a continuaci´on. Es importante notar, que los procesos est´an organizados seg´ un su alcance. !,*,next,unless,local ligan al mas cercano || liga al proceso mas cercano de la suma (+) Ejemplo: P + local x in next Q || R Significa: P + ((local x in (next Q)) || R) Se observa que el local x in P tambi´en se puede escribir como (local x)P Restricci´ on Sem´ antica . No pueden definirse procesos local < ID list > in ( when < Constraint > do < P > + when < Constraint > do < P > + . . . ). Lo anterior hace referencia al caso particular en que el programa NTCC incluya !!P en ciertas condiciones, lo cual generar´ıa un estado de inconsistencia en la m´aquina. Para solucionar lo anterior, se define que “!!P ∼ = !P sii P tiene un local 92 con determinismo“; es decir que, mientras no exista un proceso tipo guardedchoise en un local para P, se puede asegurar que !!P se ejecuta como !P. 5.3. Generaci´ on de C´ odigo La generaci´on de c´odigo es el paso final en la compilaci´on, en el cual se genera el archivo con la traducci´on al c´odigo de bytes de LMAN. La descripci´on de c´omo se traducen los procesos, se describe detalladamente en el Anexo A, acerca de Traducci´ on de procesos NTCC a c´odigo de bytes LMAN. El Anexo B describe todas las librerias usadas por el compilador para construir programas en c´ odigo de bytes LMAN. 93 6 Ejemplos y Pruebas En este cap´ıtulo se describen ejemplos de programaci´on y pruebas realizadas sobre la m´aquina virtual LMAN ejecutado construcciones NTCC. Como se mencion´o anteriormente en la secci´on 1.4, no conocemos alguna otra implementaci´on de un c´alculo de procesos, temporal, concurrente por restricciones validado sobre robots LEGO; por lo cual una comparaci´on entre LMAN y otras m´aquinas virtuales no ser´ıa realmente equitativa; sin embargo, en ´este cap´ıtulo se expone una comparaci´on a nivel de recursos entre LMAN, el lenguaje formal ESTEREL[MR82] y la m´aquina virtual est´andar LEGO. 6.1. Ejemplos A continuaci´on se expondr´an los ejemplos que fueron compilados usando el compilador NTCC-LMAN y ejecutados en LMAN. 6.1.1. Programa Zig-Zag El ejemplo de zig-zag fue expuesto anteriormente en el cap´ıtulo del c´alculo NTCC (ver secci´on 2.6.1), ahora se muestra su implementaci´on de acuerdo a la sint´axis valida en LMAN : Programa ZIG ZAG --Definici´ on de constantes para el programa const VEL = 50 const FWD = 1 94 const BACK = 2 const RGHT = 5 const LFT = 7 !( -- Procesos 1 y 2:Asignaci´ on de velocidades (tell (ospmot1=VEL)) || (tell (ospmot3=VEL)) || --Proceso 3: ZIG ZAG ( (when (a!=FWD) do (tell (gf=1)) ) + (when (b!=RGHT) do (tell (gr=1)) ) + (when (b!=LFT) do (tell (gl=1)) ) ) || --CELDAS --Proceso 4: Implementaci´ on de la primera celda (ca) (when (ca=1) do ( (next tell (ca=1)) || (unless (changea=1) next ( (when (a=0) do (next tell (a=0))) + 95 (when (a=FWD) do (next tell (a=FWD))) + (when (a=RGHT) do (next (tell (a=RGHT)))) + (when (a=LFT) do (next ( tell (a=LFT)))) ) ) ) ) || --Proceso 5: Implementaci´ on de la segunda celda (cb) (when (cb=1) do ( (next tell (cb=1)) || (unless (changeb=1) next ( (when (b=0) do (next tell (b=0))) + (when (b=FWD) do (next tell (b=FWD))) + (when (b=RGHT) do (next tell (b=RGHT))) + (when (b=LFT) do (next tell (b=LFT))) ) ) ) ) || --Proceso6: exchf, exchange forward. (when (exchf=1) do ( (tell (changea=1)) || (tell (changeb=1)) 96 || (next (tell (a=FWD))) || ( (when (a=0) do (next tell (b=0))) + (when (a=FWD) do (next tell (b=FWD))) + (when (a=RGHT) do (next tell (b=RGHT))) + (when (a=LFT) do (next tell (b=LFT))) ) ) ) || --Proceso7: exchr, exchange right. (when (exchr=1) do ( (tell (changea=1)) || (tell (changeb=1)) || (next (tell (a=RGHT))) || ( (when (a=0) do (next tell (b=0))) + (when (a=FWD) do (next tell (b=FWD))) + (when (a=RGHT) do (next tell (b=RGHT))) + (when (a=LFT) do (next tell (b=LFT))) ) ) ) 97 || --Proceso 8: exchl, exchange left. (when (exchl=1) do ( (tell (changea=1)) || (next (tell (a=LFT))) || (tell (changeb=1)) || ( (when (a=0) do (next tell (b=0))) + (when (a=FWD) do (next tell (b=FWD))) + (when (a=RGHT) do (next tell (b=RGHT))) + (when (a=LFT) do (next tell (b=LFT))) ) ) ) || --Procesos que determinan el movimiento y el exchange a ejecutar --Proceso 9: gf, goforward ( when (gf=1) do ( (tell (exchf=1)) || (next (tell (omot1=FWD))) || (next (tell (omot3=FWD))) ) ) || --Proceso 10: gr, goright 98 ( when (gr=1) do ( (tell (exchr=1)) || (next (tell (omot1=FWD))) || (next (tell (omot3=BACK))) ) ) || --Proceso 11: gl, goleft ( when (gl=1) do ( (tell (exchl=1)) || (next (tell (omot1=BACK))) || (next (tell (omot3=FWD))) ) ) ) || --Inicializaci´ on de celdas --Proceso 12 y 13 (tell (a=0)) || (tell (b=0)) Descripci´ on del programa: En la primera parte, los primeros dos procesos comentan restricciones sobre las velocidades en los motores uno y tres, utilizando para ello las variables de salida del ambiente de LMAN (ospmot1 = V EL, ospmot3 = V EL). 99 La segunda parte define el proceso encargado de escoger el siguiente movimiento del robot (tarea Zig-Zag) activando un proceso, esta decisi´on se representa con una sumatoria no-deterministica similar al ejemplo original de NTCC. Los siguientes cinco procesos modelan las celdas (a y b) y el proceso exchage con sus variantes; ´estas definiciones son similares a las que presenta el ejemplo dado en [Val03] para el c´alculo NTCC ; sin embargo, el programa contiene algunas modificaciones aplicadas, como lo son la generaci´on de guardas solo con los valores 0, FWD, RIGHT y LEFT. La cuarta parte, procesos nueve, diez y once, modela la ejecuci´on de los movimientos del robot; estos procesos son los encargados de asignar la direcci´on a las variables de ambiente de LMAN, que controlan la direcci´on de los motores y su estado actual(omot1, omot3). Finalmente, la u ´ltima parte es la encargada de dar valores iniciales a las celdas (a y b), en la primera unidad de tiempo para ejecutar el programa. Es importante mencionar que las guardas ejercen control sobre la ejecuci´on del bloque de procesos al cual se antepone. Con esto se modela procedimientos y la llamada de un proceso por otro; de lo contrario, todos los procesos se ejecutar´ıan concurrentemente sin control, generando un comportamiento no esperado, fallas y bloqueos en el Store. 6.1.2. Programa de Evasi´ on de Obst´ aculos El siguiente programa es la tarea de evasi´ on de obst´ aculos, que consiste ”en que el robot se mueva hacia adelante y cuando encuentre un obst´ aculo, gire en alguna direcci´on, en ´este caso hacia la izquierda, y posteriormente continu´e avanzando hacia adelante”[Val00], el objetivo de esta tarea es como su nombre lo explica, el movimiento del robot superando los obst´aculos que encuentre. ´ DE OBSTACULOS ´ PROGRAMA DE EVASION ( --Proceso 1: Run Evasion !( when (re=1) do 100 ( when (ivalsen1=1) do next tell (gb=1) || when (ivalsen3=1) do next tell (gb=1) || when (ivalsen1=0) do ( unless (ivalsen3=1) next ) || --Procesos que determinan el movimiento a ejecutar --Proceso 2: goForward when (gf=1) do ( tell (omot1=1) || tell (omot3=1) || next tell (re=1) ) || --Proceso 3: goBack when (gb=1) do ( tell (omot1=2) || tell (omot3=2) || next tell (tl=1) ) || --Proceso 4: turnLeft when (tl=1) do ( tell (omot1=1) || tell (omot3=0) || next tell (re=1) ) || 101 tell (gf=1)) --Proceso 5 y 6: Asignaci´ on de velocidades tell (ospmot1>80) || tell (ospmot3>80) || --Proceso 7: Activaci´ on del Sensor 1 tell (osen1=1) ) || --Activaci´ on del proceso Run Evasion tell (re=1) ) Descripci´ on del programa: El primer proceso re es el encargado de decidir cual es el siguiente movimiento que ejecutar´a el robot LEGO. Si alguna de las variables de ambiente de entrada que contiene LMAN para indicar los estados de los sensores 1 y 3 tiene el valor de oprimido(1); entonces el robot LEGO a detectado un obst´aculo, por lo cual retroceder´a (gb) y girar´a a la izquierda(tl), de lo contrario continuar´a su trayectoria(gf ). Los siguientes tres procesos se encargan de ejecutar los movimientos que deber´a hacer el robot LEGO, asignando el valor a las variables de ambiente de LMAN que controlan la direcci´on de los motores y su estado actual(omot1, omot3). Los procesos cuatro y cinco son los encargados de comentar las restricciones sobre las velocidades de los motores uno y tres, utilizando para ello las variables de salida del ambiente de LMAN (ospmot1 = V EL, ospmot3 = V EL). El proceso seis, se encarga de encender el sensor uno, por medio de la variable de salida del ambiente de LMAN (ospmot1 = V EL, ospmot3 = V EL). Finalmente, el ultimo proceso se encarga de iniciar la tarea de evasi´on de obst´aculos (re), en el primer instante. 102 6.1.3. Aplicaciones Musicales Para mostrar los diversos ambientes de aplicaci´on del c´alculo NTCC, se incluye ´este ejemplo que consiste en interpretar una melod´ıa en el robot LEGO. Las notas se modelan teniendo en cuenta que cada unidad de tiempo vale por una corchea, por ejemplo; para que una nota suene como negra,se debe tocar como corchea en dos unidades de tiempo consecutivas. Su implementaci´on es la siguiente: PROGRAMA CANON EN DO MAYOR --Constantes para el programa const ON = 1 const CORCHEA = 4 const BT = 38 const CC = 39 const CMC = const DC = 40 41 const DMC = 42 const EC = 43 const FC = const FMC = 44 45 const GC = 46 const GMC = 47 const AC = const AMC = 48 49 const BC = 50 const CQ = 51 const CMQ = const DQ = 52 53 const DMQ = 54 const EQ = 55 const FQ = const FMQ = 56 57 const GQ = 58 const GMQ = 59 103 const AQ = const AMQ = 60 61 const BQ 62 = ( --Proceso 1: Activaci´ on del sonido (! tell (osnd1=ON)) || --Proceso 2: Duraci´ on de la nota (! tell(osnddur=CORCHEA)) || --Proceso 3: Interpretacion de notas (next 1 || tell (ovalsnd1=GC)) (next 2 tell (ovalsnd1=GC)) || (next 3 || tell (ovalsnd1=CC)) (next 4 tell (ovalsnd1=DC)) || (next 5 tell (ovalsnd1=EC)) || (next 6 tell (ovalsnd1=FC)) || (next 7 tell (ovalsnd1=GC)) || (next 8 tell (ovalsnd1=GC)) || (next 9 tell (ovalsnd1=CC)) || (next 10 tell (ovalsnd1=CC)) || (next 11 tell (ovalsnd1=CC)) || (next 12 tell (ovalsnd1=CC)) 104 || (next 13 tell (ovalsnd1=AC)) || (next 14 tell (ovalsnd1=AC)) || (next 15 tell (ovalsnd1=FC)) || (next 16 tell (ovalsnd1=GC)) || (next 17 tell (ovalsnd1=AC)) || (next 18 tell (ovalsnd1=BC)) || (next 19 tell (ovalsnd1=CQ)) || (next 20 tell (ovalsnd1=CQ)) || (next 21 tell (ovalsnd1=CC)) || (next 22 tell (ovalsnd1=CC)) || (next 23 tell (ovalsnd1=CC)) || (next 24 tell (ovalsnd1=CC)) || (next 25 tell (ovalsnd1=FC)) || (next 26 tell (ovalsnd1=FC)) || (next 27 tell (ovalsnd1=GC)) || (next 28 tell (ovalsnd1=FC)) || (next 29 tell (ovalsnd1=EC)) || 105 (next 30 tell (ovalsnd1=DC)) || (next 31 tell (ovalsnd1=EC)) || (next 32 tell (ovalsnd1=EC)) || (next 33 tell (ovalsnd1=FC)) || (next 34 tell (ovalsnd1=EC)) || (next 35 tell (ovalsnd1=DC)) || (next 36 tell (ovalsnd1=CC)) || (next 37 tell (ovalsnd1=DC)) || (next 38 tell (ovalsnd1=DC)) || (next 39 tell (ovalsnd1=EC)) || (next 40 tell (ovalsnd1=DC)) || (next 41 tell (ovalsnd1=CC)) || (next 42 tell (ovalsnd1=BT)) || (next 43 tell (ovalsnd1=CC)) || (next 44 tell (ovalsnd1=CC)) || (next 45 tell (ovalsnd1=CC)) || (next 46 tell (ovalsnd1=CC)) ) 106 Descripci´ on del programa: El primer proceso activa en todas las unidades de tiempo el soporte de sonido en robot LEGO; mediante las variables(osnd1) de salida del ambiente de LMAN. El segundo proceso se encarga de dar la duraci´on de cada nota (en este caso una corchea) para todos los instantes; ´esto se hace mediante las variables globales de LMAN (osnddur1). Los siguientes procesos interpretan una nota de la melod´ıa en cada unidad de tiempo. 6.2. Pruebas En esta secci´on se comentan los resultados de la ejecuci´on de pruebas de los ejemplos anteriores, y se muestran los resultados de pruebas en otras caracter´ısticas de la m´aquina virtual como tolerancia a fallos y depuraci´on de errores. Finalmente, se hacen comparaciones con las m´aquina virtual est´andar de LEGO[Leg00] y el compilador de ESTEREL. 6.2.1. Etapa de pruebas de LMAN Esta etapa, fue realizada probando cada uno de los m´odulos de la m´aquina por separado y una vez superada la prueba individual de cada uno, se procedi´o a probar la m´aquina en su totalidad. En cada m´odulo de LMAN se puede encontrar un makef ile que genera un ejecutable que corresponde a la prueba individual del respectivo m´odulo. Luego de integrar cada uno de los m´odulos, se probo la m´aquina por completo ejecutando los ejemplos anteriormente expuestos en una estaci´on de trabajo con procesador pentium III a 930 Mhz, 256 Kb de memoria RAM y sistema operativo Linux Debian Woddy 3.0. Cada uno de estos ejemplos utiliza propiedades particulares del c´alculo y de la m´aquina, a continuaci´on se resaltan los detalles de la ejecuci´on de cada uno: 107 6.2.1.1. Programa Zig-Zag Entre las propiedades del c´alculo que utiliza el programa Zig-Zag se encuentran el no– P determinismo, mediante el proceso de sumatoria when cdo P , la replicaci´on infinita de procesos (!) y la comunicaci´on con el Store a trav´es del proceso tell c El programa Zig-Zag se ejecut´o en una superficie homog´enea de 80 cm, con una torre de comunicaci´on serial ubicada a 80 cm de altura y un robot LEGO modelo roverbot. La ejecuci´on del programa fue satisfactoria, con un tiempo de ejecuci´on promedio por instante de 302.5 milisegundos (ver cuadro 6.1). Durante las pruebas, no present´o problemas de comunicaci´on con la torre serial, debido a que se encontraba en un ambiente libre de obst´aculos. Programa Tiempo de Unidad (milisegundos) ZigZag 305 ZigZag 305 ZigZag 300 ZigZag 300 Promedio 302.5 Cuadro 6.1: Desempe˜ no del programa Zig-Zag 6.2.1.2. Programa de Evasi´ on de Obst´ aculos Entre las propiedades del c´alculo que se prueban en el programa de Evasi´on de Obst´aculos, se encuentran la informaci´on negativa con el unless c next P , la sincronizaci´on de procesos a trav´es del Store when c do P y la percepci´on del entorno por medio de las variables de entrada y salida del ambiente de LMAN que denotan el estado de los perif´ericos del robot LEGO (sensores). El programa de evasi´on de obst´aculos se ejecut´o en un laberinto de superficie de icopor de 60 x 30 cm , con una torre de comunicaci´on serial ubicada a 80 cm de altura y un robot LEGO modelo roverbot (Ver figura 6.1). El desempe˜ no del programa result´o satisfactorio, con un tiempo de ejecuci´on promedio por una unidad de NTCC de 287.5 milisegundos (ver cuadro 6.2), y tiempo de ejecuci´on promedio de 2893 milisegundos cuando se presentaron inconvenientes de comunicaci´on con la torre Serial. El tiempo 108 promedio de soluci´on del laberinto fue 1 minuto con 11 segundos, al evaluar este tiempo se debe tener en cuenta el retardo que ocasionado por los inconvenientes de transmisi´on. Figura 6.1: Ejecuci´on del programa Evasi´on de obst´aculos Programa Evasi´on de obst´aculos Evasi´on de obst´aculos Evasi´on de obst´aculos Evasi´on de obst´aculos Promedio Tiempo de Unidad Tiempo de Tiempo de Soluci´on (milisegundos) Unidad con Retardo (minutos) (milisegundos) 290 2893 1.18 280 2666 1.05 290 2690 1.07 290 2825 1.17 287.5 2768.5 1.11 Cuadro 6.2: Desempe˜ no del programa Evasi´on de Obst´aculos 6.2.1.3. Aplicaciones Musicales El programa de la interpretaci´on de un fragmento de Canon en Do mayor permite probar propiedades de NTCC como la noci´on de tiempo multiforme, el modelamiento en que cada unidad se considera una corchea, el retardo en la ejecuci´on de procesos, entre otros. Los procesos next i (P ), posponen la ejecuci´on de P , i unidades de tiempo. Con ´este programa, tambi´en se prueba el manejo del m´odulo de sonido del robot LEGO, usando las variables de ambiente de LMAN. 109 El programa Canon sobre el robot se ejecut´o en una superficie homog´enea de 80 cm, con una torre de comunicaci´on serial ubicada a 80 cm de altura y un robot LEGO modelo roverbot. El desempe˜ no del programa result´o aceptable con un tiempo de ejecuci´on promedio por instante de 281.25 milisegundos (ver cuadro 6.3). Durante la ejecuci´on no se presentaron problemas de comunicaci´on con la torre serial, debido a que no hubo movimiento del robot LEGO, ni obst´aculos en la comunicaci´on. Programa Tiempo de Unidad Canon 280 Canon 285 Canon 280 Canon 280 Promedio 281.25 Cuadro 6.3: Desempe˜ no del programa Canon en Do mayor 6.2.1.4. Recuperaci´ on de Errores LMAN permite recuperaci´on de errores en la transmisi´on y admite depuraci´on de errores en la ejecuci´on por medio de mensajes de error. Debido a que el protocolo de transmisi´on LNP es tipo UDP no tiene verificaci´on en la recepci´on; raz´on por la cual se hace necesario a˜ nadir un protocolo de control y recuperaci´on de errores que sea capaz de identificar si hay comunicaci´on con el RCX, y de lo contrario permita reintentar para establecer comunicaci´on. El funcionamiento del protocolo se trata en la secci´on 4.1.3.3 del cap´ıtulo 4. La depuraci´on de errores en LMAN, informa al usuario el tipo y descripci´on del error que se present´o al ejecutar un programa. Los errores m´as comunes suceden por inconsistencias en el Store, ´estado que genera un bloqueo en la m´aquina. Esta caracter´ıstica de LMAN es de gran ayuda para diagnosticar errores en el c´odigo o funcionamiento de un programa. 110 6.2.2. Comparaci´ on entre LMAN , ESTEREL y La M´ aquina est´ andar de LEGO Se har´a una comparaci´on de manejo de los recursos con la m´aquina est´andar de LEGO[Leg00] y el lenguaje formal de programaci´on deterministica ESTEREL[MR82]. Antes de iniciar la comparaci´on se dar´a una breve descripci´on de cada uno de los items a tratar: M´aquina Est´andar de LEGO: Como ya se ha mencionado en cap´ıtulos anteriores, es el firmware original del robot LEGO. Tiene capacidad de almacenar 5 programas y realizar 10 tareas y 18 subrutinas por cada uno de ellos; maneja 32 variables globales para todas las tareas y 16 locales por cada una de las tareas, permite controlar todos los perif´ericos del robot LEGO: sensores, motores, timers, LCD. ESTEREL: ESTEREL como herramienta de programaci´on, es un compilador que realiza la transformaci´on del lenguaje s´ıncrono deterministico ESTEREL[MR82] a codigo C del sistema operativo BrickOS(LegOS). Este compilador permite manejar una cantidad mayor de 10 tareas en paralelo y controla todos los perifericos del robot LEGO. El n´ umero de variables est´a limitado por la cantidad disponible de memoria que tenga el robot LEGO. A continuaci´on se realiza la comparaci´on entre LMAN, ESTEREL y la M´aquina Est´andar de LEGO, los criterios que se compararan son; expresividad, manejo de memoria de programa y manejo de tareas concurrentes. Expresividad: LMAN maneja programaci´on formal temporal, concurrente por restricciones y es no-deterministica, propiedades que le confieren un nivel m´as alto en expresividad del que maneja ESTEREL y la M´aquina est´andar de LEGO. Capacidad de Memoria: Debido a que el n´ ucleo principal de LMAN se ejecuta en una estaci´on de trabajo, la capacidad de memoria que maneja es superior a la de ESTEREL y a la m´aquina est´andar de LEGO que se ejecutan internamente desde el RCX. Esto permite ejecutar problemas complejos, que demanden nivel de procesamiento y memoria que talvez desde el LEGO no sea posible ejecutar. Si se observa de la manera anterior, la ejecuci´on del n´ ucleo de la m´aquina desde una estaci´on de trabajo, y el componente de transmisi´on adicionado en LMAN no resultaron realmente en desventaja frente a otras herramientas. 111 Manejo de tareas concurrentes: Ya que LMAN utiliza como plataforma de desarrollo y ejecuci´on el sistema operativo BrickOS(LegOS)[MLNP00] y gracias a la propiedad del c´alculo de modelar tareas concurrentes, el numero de tareas concurrentes admitidas por LMAN es n. Lo cual es superior en funcionamiento a la m´aquina est´andar de LEGO. ESTEREL admite el modelamiento de tareas concurrentes. A continuaci´on se presenta un cuadro que resume las caracter´ısticas de cada uno de los item comparados. Criterios LMAN ESTEREL Expresividad No-determninismo (formal) Limitada por hardware de la estaci´on Superior (10 o m´as procesos) Determinismo (formal) Limitada por hardware del robot LEGO Superior 10 o m´as procesos) Capacidad de Memoria Manejo de tareas concurrentes M´aquina Est´andar de LEGO Determinismo Muy limitada B´asico (10 procesos) Cuadro 6.4: comparaci´on de LMAN, ESTEREL y M´aquina est´andar de LEGOS Por las pruebas y los datos registrados en ´este cap´ıtulo, es posible concluir que la implementaci´on de LMAN que se reporta, resulta ser eficiente, robusta, tolerante a fallos y de funcionamiento en tiempo real, a pesar que los programas realizados en ella conllevan la resoluci´on de restricciones aritm´eticas y el modulo de transmisi´on de instrucciones por torre serial/USB al robot LEGO. 112 7 CONCLUSIONES Y TRABAJO FUTURO El objetivo propuesto para el presente trabajo de tesis, involucra el dise˜ no e implementaci´on de una m´aquina abstracta para el c´alculo NTCC, de modo que sea posible ejecutar construcciones NTCC sobre robots LEGO. No obstante, para proveer una funcionalidad completa, se hizo fundamental involucrar en los objetivos del proyecto, acoplar un sistema de restricciones para implementar el componente CC del c´alculo subyacente, junto con un compilador para proveer una interf´az en alto nivel de programaci´on para la m´aquina. La m´aquina LMAN resulta una implementaci´on completa y eficiente del c´alculo NTCC, que permite controlar y ejecutar en tiempo real programas escritos en NTCC sobre Robots LEGO MindStorm. Su base formal en este c´alculo le confiere la expresividad suficiente para modelar problemas complejos del mundo del robot, de una manera m´as natural y sin caer en detalles espec´ıficos en la implementaci´on. Por ejemplo, no se necesita especificar una velocidad fija para el robot, simplemente se da un rango (velocidad > 80); tampoco es necesario especificar al robot una v´ıa de acci´on determinada (cuando encuentre un obst´aculo, gire hacia la izquierda), se le deja una escogencia no–determin´ıstica de la acci´on; permite modelar problemas de la realidad como la interpretaci´on de melod´ıas, en donde se define una unidad de tiempo como un nota (un instante equivale a una corchea) y finalmente permite dar soluci´on a problemas que usan la asincron´ıa para asegurar que el robot realiza una acci´on (chequear la temperatura), en un instante de tiempo no determinado. El modelo formal presentando en forma de m´aquina abstracta, provee la especificaci´on de la m´aquina virtual para LMAN. Esta formalidad asegur´o en LMAN un dise˜ no completo y consistente, de modo que, la implementaci´on fue transparente, fluida y el 113 comportamiento de la m´aquina siempre fue el esperado. Una vez finaliz´o la etapa de implementaci´on con base en el dise˜ no formal realizado, no fue necesario realizar modificaciones de fondo al c´odigo fuente. El dise˜ no modular de LMAN act´ ua como un componente integrador. Adem´as de que combina los paradigmas de programaci´on reactiva, temporal, concurrente y por restricciones en un entorno eficiente de programaci´on para dispositivos rob´oticos LEGO, LMAN integra otros proyectos. De ´esta manera, se ha logrado acoplar a LMAN el trabajo de grado que implementa el sistema de restricciones [CG01] para el c´alculo PiCO, la gram´atica que describe formulas de primer orden descrita en el trabajo de grado de la m´aquina abstracta MAPiCO[AB98], el compilador NTCC-LMAN desarrollado como proyecto de semestre en el curso de Compiladores (PUJ) [RCP03], el trabajo de grado que implementa el lenguaje visual VIN, y por supuesto el c´alculo subyacente NTCC [Val03]. El desarrollo de LMAN alrededor de una comunidad de c´odigo abierto y de un alto nivel investigativo, agiliz´o el aprendizaje, la consecuci´on de soluciones y el desarrollo colaborativo. El contacto contin´ uo con otros grupos de investigaci´on y comunidades de desarrollo sobre Internet, fue determinante para hallar soluci´on a los problemas en implementaci´on de LMAN, principalmente en lo relacionado con el manejo de los dispositivos rob´oticos LEGO. Gracias a ´esta colaboraci´on fue posible dise˜ nar e implementar un ambiente de ejecuci´on eficiente para LMAN, utilizando un protocolo de comunicaciones, por medio del cual la m´aquina virtual se ejecuta en una estaci´on de trabajo y se comunica via infrarrojo con el dispositivo rob´otico para ejecuci´on. Como trabajo futuro, se han considerado varias actividades y recomendaciones que permitir´an afinar la implementaci´on actual. Estas pueden clasificarse en dos grupos, los cuatro primeros puntos tratan actividades y recomendaciones relacionadas con el componente formal de LMAN y las siguientes est´an relacionadas con el componente funcional. La m´aquina abstracta de LMAN modela de manera cercana el c´alculo NTCC. No obstante, para probar su correctitud es importante realizar la prueba formal de bisimilitud, desde el c´alculo hacia la m´aquina y desde la m´aquina hacia el c´alculo NTCC. Se recomienda implementar la definici´on de celdas para NTCC dada en [Val03] a 114 nivel de la m´aquina virtual. Esto reducir´ıa el c´odigo de programa necesario para modelar celdas en el c´alculo, adem´as de que actuar´ıa como una plantilla gen´erica que es posible usar en cualquier problema computacional que implique el uso de celdas. Para lograr a´ un mas eficiencia y proveer mayor expresividad en las construcciones NTCC ejecutadas sobre la m´aquina, es importante desarrollar un sistema de restricciones propio para NTCC, tal como se describe en [Val03]. Gracias a la propiedad de LMAN de definir restricciones como f´ormulas de primer orden, su acople ser´ıa casi transparente siempre y cuando el nuevo sistema de restricciones tambi´en exprese las restricciones de ´esta manera. La sint´axis de la m´aquina abstracta y consecuentemente las instrucciones de la m´aquina virtual, puede ser extendidas para modelar los procesos derivados del c´alculo NTCC. La m´aquina virtual permite definir hasta 64 instrucciones. Para futuras versiones de RCX que admitan mayores recursos de Hardware y gracias a la modularidad del dise˜ no de LMAN, se puede lograr optimizar la m´aquina de tal modo que pueda ejecutarse desde el RCX, omitiendo as´ı el m´odulo que realiza la transmisi´on. Esta optimizaci´on debe partir de un sistema de restricciones propio para aplicaciones NTCC, tal como se ha mencionado anteriormente. Con la actual implementaci´on de LMAN que permite el control del doble de dispositivos de los RCX convencionales, es posible dise˜ nar ambientes colaborativos logrando crear programas que involucren la interacci´on de dos o m´as RCX. La modularizaci´on de LMAN posibilita el acople de herramientas de simulaci´on. La interf´az LEGO actuar´ıa como el componente integrador entre el simulador y la m´aquina virtual. LMAN actualmente ha sido probada ejecut´andose sobre LINUX; es posible hacerla portable a Windows y MacOS. Adicionalmente, es importante que exista el uso del driver USB para la transmisi´on via LNP, ´esto mejorar´ıa el desempe˜ no de la transmisi´on. . En la actualidad LNP admite solamente torre serial. Finalmente con todo el paquete afinado es importante generar una herramienta de instalaci´on, que disminuya todas las tareas alrededor de la configuraci´on de LMAN para su funcionamiento. 115 Anexo A. Traducci´ on de procesos NTCC a c´ odigo de bytes de LMAN Anexo A. Traducci´on de procesos NTCC a c´odigo de bytes de LMAN Las siguientes tablas describen la construcci´on de los procesos de LMAN en el c´ odigo de bytes entrada de la M´aquina Virtual. Las instrucciones que se utilizan en ´este ap´endice, se definen en el archivo opcodes.h como constantes para un mejor entendimiento. Las construcciones descritas a continuaci´on fueron usadas para la generaci´on de c´odigo desde el compilador. A.1 Tell La instrucci´on tell < constraint > se traduce a LMAN escribiendo las instrucciones que corresponden a la restricci´on, seguidas de las instrucciones lTELL y SKIP. Ejemplo: para tell ( x > 5), se genera el c´odigo: L´ ınea Opcode Src1 Src2 1 2 ATOM TERMV MAY 74 2 3 TERMC 5 4 lTELL 5 SKIP A.2 When La instrucci´on when < constraint > do < P >, se traduce escribiendo las instrucciones que corresponden a la restricci´on, seguidas de la instrucci´on ASK que lleva como par´ametro la direcci´on de la u ´ltima instrucci´on del proceso hijo (P), finalizando con las instrucciones correspondientes al proceso P. Ejemplo: para when (x = 1) do tell (y = 0), se genera el c´odigo: L´ ınea Opcode Src1 Src2 1 ATOM IGUAL 2 2 3 TERMV TERMC 74 1 4 5 lASK ATOM 9 IGUAL 6 TERMV 75 7 TERMC 0 8 9 lTELL SKIP 2 A.3 Composici´ on Paralela La instrucci´on < P > || < P >, se traduce escribiendo la instrucci´on PAR que lleva como par´ametro la direcci´on de la primera instrucci´on del segundo proceso, seguida de las instrucciones que corresponden al primer proceso, y por u ´ltimo las instrucciones del segundo proceso. Ejemplo: para tell (x > 5) || tell (y > 1), se genera el c´odigo: L´ ınea Opcode Src1 Src2 1 2 PAR ATOM 7 MAY 2 3 TERMV 74 4 TERMC 5 5 6 lTELL SKIP 7 ATOM MAY 8 TERMV 75 9 10 TERMC lTELL 1 11 SKIP 2 A.4 Unless La instrucci´on unless < constraint > next < P >, se traduce escribiendo las instrucciones que corresponden a la restricci´on, seguidas de la instrucci´on UASK que tiene como par´ametro la direcci´on de la u ´ltima instrucci´on del proceso hijo (P), finalmente las instrucciones del proceso P. 118 Ejemplo: para unless (x > 5) next tell (y < 80), se genera el c´odigo: L´ ınea Opcode Src1 Src2 1 ATOM MAY 2 2 3 TERMV TERMC 74 5 4 UASK 9 5 ATOM MEN 6 7 TERMV TERMC 75 80 8 TELL 9 SKIP 2 A.5 Next La traducci´on de la instrucci´on next < Const op > < P >, depende de la existencia o no de la constante opcional. Cuando la constante es vac´ıa, se traduce escribiendo la instrucci´on NEXT que lleva como par´ametro la direcci´on la u ´ltima instrucci´on del proceso hijo (P), seguida de las instrucciones que corresponden al proceso P. Cuando la constante no es vac´ıa, se traduce escribiendo la instrucci´on NEXTN que lleva como par´ametro el n´ umero de instantes que deben transcurrir antes de realizar el proceso, seguida de la instrucci´on JMP que tiene como par´ametro la direcci´on de la u ´ltima instrucci´on del proceso hijo (P), y finaliza con las instrucciones que corresponden al proceso. Ejemplos: Para next ( tell (x = 1)), se genera el c´odigo: L´ ınea Opcode Src1 Src2 1 2 NEXT ATOM 6 IGUAL 2 3 TERMV 74 4 TERMC 1 5 6 TELL SKIP 119 Para next 2 ( tell ( x =1)), se genera el c´odigo: L´ ınea Opcode Src1 1 NEXTN 2 2 JMP 7 3 4 ATOM TERMV IGUAL 74 5 TERMC 1 6 TELL 7 SKIP Src2 2 A.6 Replicaci´ on La instrucci´on ! < P >, se traduce escribiendo la instrucci´on REP sin par´ametros, seguida de las instrucciones que corresponden al proceso. Ejemplo: para !tell (x > 80), se genera el c´odigo: L´ ınea Opcode Src1 Src2 1 2 REP ATOM MAY 2 3 TERMV 74 4 TERMC 80 5 6 LTELL SKIP A.7 Asincron´ıa Para traducir la instrucci´on *[< constante >, < constante >] < P >, el compilador debe generar un valor aleatorio (random) en el rango comprendido entre los valores de las dos constantes. Luego, se traduce escribiendo la instrucci´on STAR, cuyo par´ametro es el n´ umero aleatorio generado, seguida de la instrucci´on JMP que lleva la direcci´on de la u ´ltima instrucci´on del proceso hijo (P), finalizando con las instrucciones que corresponden a P. 120 Ejemplo: para * [1,7] tell (x=1), se genera el siguiente c´odigo.Se asume que el random genera el 4 (Src1 de la primera l´ınea). L´ ınea Opcode Src1 1 2 STAR JMP 4 7 3 ATOM IGUAL 4 TERMV 74 5 6 TERMC TELL 1 7 SKIP Src2 2 A.8 No determinismo Los procesos de la instrucci´on < P > + < P > + < P > . . . , tienen dos interpretaciones posibles: Si el proceso NO es un when < constraint > do < P > (es cualquiera de los otros procesos posibles), este se debe interpretar como when true do P, dado que en NTCC no existen las constantes true o false, se crea una restricci´on que siempre sea verdadera: when (0=1) do P, donde 0 es una etiqueta que siempre se comenta al Store con valor 1. Por ejemplo, si se tiene tell (a+b>5) + next tell(a=10), esto se interpretar´ıa como la instrucci´on when (1=1) do tell (a+b>5) + when (1=1) do next tell (a=10). Si el proceso es un when < constraint > do < P > se ejecuta nomalmente (evaluando la restricci´on para decidir si P se ejecuta o no). Finalmente, cada instrucci´on < P > + < P > + < P > representa una instrucci´on de la forma when < constraint > do < P > + when < constraint > do < P > + when < constraint > do < P >. La traducci´on de ´esta instrucci´on es as´ı: Cada instrucci´on when < constraint > do < P > se traduce escribiendo las instrucciones que corresponden a la restricci´on, seguidas de la instrucci´on GASK que lleva como primer par´ametro la l´ınea donde se inicia el siguiente proceso, y como segundo par´ametro 1 o 0 (1 para el primer when de la sumatoria, y 0 para 121 los when restantes), seguidos por las instrucciones del proceso hijo (P), y una instrucci´on JMP que lleva como par´ametro la direcci´on de la u ´ltima instrucci´on de todo el conjunto de procesos (en el caso del ejemplo el skip de la direcci´on 32) . Los c´odigos de los procesos se concatenan, y al final se agregan las instrucciones NDET y SKIP. Se debe tener en cuenta que para el GASK del u ´ltimo proceso, el proceso siguiente es el NDET (en el ejemplo el GASK de la l´ınea 24, tiene como par´ametro 31, l´ınea del NDET). Ejemplo: para when (x > 40) do tell(y = 1) + tell(y = 1) + when (x =1) do tell(y = 0), se genera el c´odigo: L´ ınea Opcode Src1 Src2 1 ATOM MAY 2 2 3 TERMV TERMC 74 40 4 GASK 11 1 5 ATOM IGUAL 2 6 7 TERMV TERMC 75 1 8 lTELL 9 SKIP 10 11 JMP ATOM 32 IGUAL 12 TERMV 0 13 TERMC 1 14 15 GASK ATOM 21 IGUAL 16 TERMV 75 17 TERMC 1 18 19 lTELL SKIP 20 JMP 32 21 ATOM IGUAL 2 0 2 2 122 22 23 TERMV TERMC 74 1 24 GASK 31 0 25 ATOM IGUAL 2 26 27 TERMV TERMC 75 0 28 lTELL 29 SKIP 30 31 JMP NDET 32 SKIP 32 A.9 Skip El proceso skip se usa para sincronizar en LMAN. De esta manera la mayor´ıa de procesos a excepci´on de algunos como replicaci´on (!) y paralelo (||) deben incluir como par´ametro un llamado al skip mas cercano, tal como se ha apreciado en lo ejemplos anteriores. A.10 Manejo de Rangos Aunque el Sistema de Restricciones actual no implementa rangos, en LMAN se definen, de modo que, si se adiciona un nuevo Sistema de Restricciones puedan ser utilizados en las construcciones NTCC. Los rangos se definen de la siguiente manera: x in 10.,20 < var ref erence > in < Constante > .. < Constante > Los cuales se representan con la estructura OPERACION / Variable \ RANGE / \ Inicio Fin Ejemplo: Para la restricci´on x in 10.,20, el ´arbol que expresa la restricci´on se representar´ıa: 123 IN / \ x RANGE / 10 \ 20 Lo anterior se traduce en c´odigo de bytes LMAN como sigue: (se asume que la direcci´on de x es 79): L´ ınea Opcode Src1 Src2 1 2 ATOM TERMV IN 79 2 3 TERMF RANGE 2 4 TERMC 10 5 TERMC 20 124 Anexo B. Librer´ıas para la construcci´ on de Programas en LMAN Anexo B. Librer´ıas para la construcci´on de Programas en LMAN Como resultado de la compilaci´on de NTCC a LMAN, se debe generar un archivo binario, que contendr´a el c´odigo que ejecutar´a la m´aquina virtual. Para ello, se provee un conjunto de librer´ıas necesarias para escribir este archivo de forma correcta, las cuales se describen a continuaci´on. Para escribir una l´ınea de c´odigo de m´aquina de LMAN se utiliza la funci´on: escribirLinea(OPCODE, SRC1,SRC2 ,ARCHIVO) que se encuentra definida en el m´odulo cargador (cargador.h y cargador.o) con los siguientes par´ametros: • OPCODE: Es el c´odigo de la operaci´on • SRC1: Es el primer par´ametro de la operaci´on (si no es necesario va en cero). • SRC2: Es el segundo par´ametro de la operaci´on (si no es necesario va en cero). • ARCHIVO: Es el archivo donde se va a escribir el programa. Recuerde que la precondici´on de escribirLinea es que el archivo est´e abierto en modo de escritura (Ejemplo: fopen(”lman.bin”, ”w”)). El archivo binario debe finalizar con la instrucci´on (0, 0, 0) lo cual indica que es el fin del archivo. Las librer´ıas relacionadas para la construcci´on de programas son las siguientes: • opcodes.h: contiene la definici´on de los c´odigos de operaci´on -opcodes- de LMAN. • ValueFrameConst.h: contiene la definici´on de los valores necesarios para realizar la interacci´on con el sistema de restricciones (IGUAL, DIF, MAY, ...). • varlman.h: contiene la definici´on de las variables de ambiente de LMAN tanto las de entrada como las de salida (ISENEST1, IMOTEST6). Bibliograf´ıa [AB98] M. Heredia . A. Buss. MAPiCO: M´ aquina Abstracta para el C´ alculo Pico. Tesis de Pregrado, Facultad de Ingenieria, Pontificia Universidad Javeriana. 1998. [ADQV98] G. Alvarez, J. Diaz, L. Quesada, and F. Valencia. PiCO: A calculus of concurrent constraint object for musical applications. ECAI98, Workshop of Constraint and the Arts, Brighton, England. 1998. [Bau00] D. Baum. http://www.baumfamily.org/nqc/. 2000. [Car95] B. Carlson. Compiling and Executing Finite Domain Constraints. PhD thesis, Swedish Institute of Computer Science. 1995. [CG01] A. Vasquez C. Garcia. Implementaci´ on eficiente de un sistema de dominios finitos para el lenguaje cordial. Tesis de Pregrado, Facultad de Ingenieria, Pontificia Universidad Javeriana. 2001. [Com00] r Dictionary of the Houghton Mifflin Company. The American Heritage c 2000. English Language, Fourth Edition. Copyright [FQ04] D. Fern´andez and J. Quintero. VIN: Lenguaje Visual basado en el c´ alculo NTCC. Tesis de Pregrado, Ingenier´ıa de Sistemas, Pontificia Univerisidad Javeriana. 2004. [Fre99] J. Fredslund. The assumption architecture. Progress Report, Department of Computer Science, University of Aarhus. 1999. [Gro00] LEGO Group. Constructopedia. LEGO, MindStorms, Robotics Invention System. 1999/2000. [HS96] T. Haynes and S. Sen. Evolving behavioral strtegies in predators and prey. In Proc of the IJCAI Workshop on Adaptation and Learning in Multi-Agent Systems, volume 1042 of Lecture Notes in Artificial Intelligence, pages 113126. Springer Verlag. 1996. 127 [JNO97] ˜ S. Jones, T.Nordin, and D. Oliva. C–:A portable assembly language. In Implementation of Functional Languages. 1997. [Jon92] S. Jones. Implementing Lazy Functional Languages on Stock Hardware: the Spineless Tagless g-machine. Journal of Functional Programmingd Concurrency. Preentice-Hall. 1992. [Leg00] Lego. LEGO MindStorms RCX 2.0 Firmware Command Overview,. 2000. [Lop99] L. Lopes. On the Design and Implementation of a Virtual Machine for Process Calculi. PhD Dissertation, Department of Computer Sciences, University of Porto. 1999. [LP99] H. H. Lund and L. Pagliarini. Robot soccer with LEGO mindstorms. LNCS, 1064:141-151. 1999. [LY97] T. Lindholm and F. Yellin. The Java Virtual Machine Specification. 1997. [MBD86] V. Jagannathan M. Brenda and R. Dodhiawala. On optimal cooperation of Knowledge sources - an empirial investigation. Technical REport BCSG2010-28, Boeing Advanced Techology Center. 1986. [McA92] D. McAllester. First order logic. 1992. [Mil89] R. Milner. Communication and Concurrency. 1989. [Mil99] R. Milner. Communicating and Mobile Systems: the π calculus. Cambridge University Press. 1999. ˜ [MLNP00] L. Villa M. L.Noga and P. http://brickos.sourceforge.net/. 2000. [MR] C. Mauras and M. Richard. LUSTRE Y ESTEREL synchronous languages. http://www.emn.fr/x-info/lego/. [MR82] J. Marmorat and J. Rigault. http://www-sop.inria.fr/esterel.org/. 1982. [RCP03] F. Rocha, J. Chal´a, and M. Pab´on. Compilador NTCC-LMAN. Reporte del curso de Compiladores, Pontificia Universidad Javeriana–Cali. 2003. [SJG94] V. Saraswat, R. Jagadeesan, and V. Gupta. Foundations of timed concurrent constraint programming. In Proc. Of the Ninth Annual IEEE Symposium of Logic in Computer Science. 1994. [SR00] J. Solorzano and T. Rinkens. http://lejos.sourceforge.net/index.html. 2000. [SRP91] V. Saraswat, M. Rinard, and P. Panangaden. The semantic foundations of Concurrent Constraint Programming. In ACM, Preceedings of eighteenth annual ACM symposium of Principles of programming languages. 1991. 128 [SRP03] V. Saraswat, M. Rinard, and P. Panangaden. JCC: Integrating Timed Default Concurrent Constraint Programming into java. 2003. [SV00] P. Stone and M. Veloso. Multiagent systems: A survey from a machine learning perspective. Autonomoues nRobots, 8: 345-383. 2000. [Val00] F. D. Valencia. Reactive Constraint programing. Progress Report , Department of Computer Science, University of Aarhus. 2000. [Val03] F. D. Valencia. Temporal Concurrent Constraint Programming. PhD Dissertation, Department of Computer Science, University of Aarhus. 2003. [VS91] P. Panangaden V. Saraswat, M. Rinard. The semantic foundations of concurrent constraint programming. In ACM, Prceedings of eighteenth annual ACM symposium of Principles of programming languages. 1991. [VSG96] R. Jagadeesan V. Saraswat and V. Gupta. Timed Default Concurrent Constraint Programming. J. Symbolic Computation. 1996. [War83] D. Warren. An Abstract Prolog Instruction Set. Technical Report 309, SRI International. 1983. 129