Utilizando a Programação Visual no Modelo de Máquina
Geométrica
Renata S. Reiser, Marcos B. Cardoso, Graçaliz P. Dimuro
Universidade Católica de Pelotas, Escola de Informática - NAPI,
Pelotas, Brazil, 402
e
Antônio C. R. Costa
Universidade Federal do Rio Grande do Sul, Instituto de Informática - PPGC
Porto Alegre, Brazil, 15064
{mbcardo,reiser,rocha}@atlas.ucpel.tche.br
Abstract
This paper presents an experiment concerning the formal specification of visual languages, namely the specification of a visual language for the Geometric Machine model, denoted by GMVL. The language provides graphic
representations for computational processes interpreted in the ordered structure of that model. The specification follows the approach proposed in the GENGED project, developed in the T. U. Berlin. The visual language supports a
visual alphabet and a visual grammar. A process constructor is represented by a graph transformation related to a rule
application in the the visual grammar. In the same way, (possibly partial, recursive or infinite) processes are represented by typed graphs in the visual alphabet, including concurrent and non-deterministic processes. The syntactical
levels in the GMVL-syntax includes an abstract syntax, related to the logical level of the graphic structures, and a
concrete syntax, concerned with the graphical layout.
Keywords: Visual Languages, Concurrence, Non-Determinism, Parallel Programming, Geometric Machine Model
Resumo
Este trabalho apresenta uma experiência na especificação formal de uma linguagem de programação visual, denominada Linguagem Visual para a Máquina Geométrica, indicada por LVMG. A linguagem provê representações
gráficas para os processos computacionais interpretados na estrutura ordenada deste modelo. A especificação segue a
abordagem proposta no projeto GENGED, desenvolvido em T. U. Berlin. A linguagem visual suporta um alfabeto visual e uma gramática visual. Um construtor de processo é representado por uma transformação de grafos ralacionada
a uma regra de aplicação na gramática visual. De forma análoga, processos (possivelmente infinitos e recursivamente
definidos) são representados por grafos tipados in alfabeto visual, incluindo interpretação para concorrência sı́ncrona
e não-determinı́stica. Os nı́veis sintáticos na sintaxe LVMG incluem uma sintaxe abstrata, relacionada com o nı́vel
lógica das estruturas gráficas, e uma sintaxe concreta, referente ao layout gráfico.
Palavras chaves: Linguagens Visuais, Concorrência, Não-determinismo, Programação Paralela, Modelo de Máquina
Geométrica
1 Introdução
Considerando-se as vantagens da programação visual na modelagem de sistemas concorrentes e distribuı́dos, o objetivo
deste trabalho foi a especificação formal da Linguagem Visual para a Máquina Geométrica (LVMG). O trabalho segue
a abordagem proposta no projeto GENGED [2] e inclui a especificação do alfabeto visual e da gramática visual
para a linguagem LVMG com ênfase nas construções recursivas. Para tal, são consideradas dois tipos de sintaxe:
a sintaxe abstrata, responsável pela estruturação lógica das expressões gráfica (diagramas) da linguagem visual e a
sintaxe concreta, orientando a definição do layout de cada expressão para manipulação do usuário. Neste sentido, os
resultados apresentados constituem-se na primeira etapa para definição de um ambiente visual de programação para o
modelo de Máquina Geométrica (MG)[7, 8] capaz de prover interpretação para processos computacionais, envolvendo
paralelismo e não-determinismo.
Embora a descrição textual de expressões visuais ou diagramas seja sempre uma tarefa difı́cil devido sua estrutura
gráfica, seu poder de expressão constitui-se numa poderosa ferramenta para compreensão e construção de sistemas
complexos. Alguns dos importantes benefı́cios do uso das representações visuais/espaciais em modelo computacionais
que envolvam programação paralela, como o caso do modelo GM são: o número de argumentos (aridade) envolvidos
na definição dos processos algébricos, as (possı́veis) definições recursivas dos construtores, a composição funcional, as
computações paralelas e não-determinı́sticas relacionadas com a sincronização de processos, e finalmente, a definição
espacial dos processos e estados computacionais sobre um espaço geométrico. Entende-se que tais caracterı́sticas
sejam relevantes para tornar a programação no modelo MG mais acessı́vel aos usuários em geral, possibilitando
sua aplicação na Computação Cientı́fica, em especial na Matemática Intervalar [9, 10], justificando-se seu estudo e
utilização.
Em analogia a construção da estrutura ordenada do modelo MG fundamentada na Teoria dos Domı́nios [1], o
desenvolvimento da correspondente linguagem visual utiliza conceitos e fundamentos da Álgebra dos Processos [6] e
da Teoria dos Grafos [11]. Os processos (incluindo os elementares) são representados por grafos consistindo de nodos
e arestas, aos quais são associados atributos e conexões e os construtores de processos (produto seqüencial e paralelo,
soma determinı́stica e não-determinı́stica) são representados por transformações de grafos.
Como fundamentação, apresenta-se na próxima seção um resumo do modelo MG, onde são descritos os tipos de
processos computacionais modelados e as principais caracterı́sticas do domı́nio indutivo onde estão representados.
Na subseção 2.2, apresenta-se uma breve descrição da linguagem textual induzida pelas representações obtidas na
estrutura ordenada do modelo MG. A seguir, na subseção 2.3 mostra-se como é definida uma LV, de acordo com o
sugerido na literatura [5]. A especificação da LVMG está dividido em duas etapas apresentadas nas seções 3 e 4,
respectivamente. A especificação do alfabeto envolve a especificação de sı́mbolos e a especificação de conexões. Na
Especificação da Gramática são construı́das as regras que definem a gramática visual. Estas duas etapas formalizam a
Especificação do Editor Gráfico da linguagem LVMG, responsável pelo layout do ambiente visual para programação
no modelo MG, veja Figura 5. Neste trabalho, estão inseridos exemplos incluindo a representação de construtores
recursivas relacionados com a estrutura temporal e espacial do modelo MG.
2 Fundamentação
2.1
O Modelo de Máquina Geométrica
No modelo de Máquina Geométrica, a memória e os processos computacionais possivelmente infinitos, são rotuldados
por posições de um espaço geométrico e modelam estruturas matriciais multi-dimensionais. Neste modelo é possı́vel
representar, além da construção temporal, a construção espacial responsável pela modelagem da concorrência sı́ncrona
e do conflito de acesso à memória.
A estrutura ordenada do modelo MG é definida por espaços coerentes, domı́nios algébricos introduzidos por Girard [4] na busca de fundamentação para a lógica linear. Em especial, a interpretação dos processos é definida pelo
Espaço Coerente dos Processos Computacionais (D∞ ), cuja construção indutiva é construı́da em nı́veis e obtida a
partir do conjunto de processos elementares, pela aplicação sucessiva de operadores representando os construtores de
processos.
Seguindo a metodologia proposta por Scott [12], cada nı́vel da construção está identificado por um subespaço,
representando processos cujas execuções estão limitadas apenas na construção temporal. Isto se justifica porque cada
subespaço reconstrói todos os objetos do nı́vel anterior, preservando suas propriedades e relações, além de construir os
2
novos objetos. Compatı́vel com a abordagem algébrica, o relacionamento entre os nı́veis é expresso por funções lineares denominadas imersões e projeções, interpretanto os construtores de processos e seus destrutores, respectivamente.
Pelo procedimento de completação, assegura-se a existência do menor ponto fixo para equações recursivas definidas
pela composição infinita destes morfismos.
De forma análoga, no Espaço Coerente de Estados Computacionais (S) obtém-se interpretação para estados
computacionais não-determinı́sticos, representados por conjuntos de traços lineares de funções lineares definidas do
Espaço Coerentes de Posições (I) para o Espaço Coerente de Valores (V).
Em [7], interpretações construı́das por prefixação (ou sufixação) comprovam que este modelo é compatı́vel com
a diversidade dos construtores. Além disso, uma generalização do modelo é obtida com a introdução da Máquina
Geométrica Distribuı́da (MGD), baseada na análise da construção dos ordinais transfinitos como seqüências generalizadas de números naturais.
A versão intervalar do modelo MG é apresentada em [9] e denominada Máquina Geométrica Intervalar (MGI). Os
estados, processos e testes computacionais são definidos tomando valores no conjunto dos números reais extendidos e
rotulados por posições do espaço euclidiano tridimensional. O conjunto dos intervalos de reais define os conjuntos de
dados de entrada e de saı́da do modelo MGI. Para representação dos estados computacionais considera-se a construção
dos reais computáveis utilizando o Espaço Coerente Bi-estruturado de Intervalos Racionais apresentada em [3]. Uma
linguagem de programação textual é introduzida em [10] para prover semântica a algoritmos que executam operações
aritméticas intervalares.
2.2 A Linguagem Textual para o Modelo MG
Com base nas interpretações obtidas sobre o espaço coerente D∞ , obtem-se uma linguagem de programação textual,
indicada por L(D∞ ), para implementação de algoritmos paralelos e não-determinı́sticos
no modelo MG.
S
Seja K o conjunto dos sı́mbolos constantes dado pela união K = IP IT , onde IP e IT denotam o conjunto dos
sı́mbolos representando processos elementares e os testes booleanos interpretados em D∞ , respectivamente. Além
disso, seja FOp = {Id, k , |, · , + } o conjunto dos sı́mbolos representando os construtores de processos em D∞ ,
onde
(i) Id ∈ IP é o processo identidade.
(ii) k, |, · : IP × IP → IP são sı́mbolos binários representando o produto paralelo, a soma não-determinı́stica e o
produto seqüencial;
(iii) + : IP × IP × IT → IP é um sı́mbolo de aridade 3 representando a soma determinı́stica, onde ∀b ∈ IT ,
+b : IP × IP → IP .
O conjunto das expressões da linguagem L(D∞ ) induzida pelas interpretações em D∞ é definido por:
(i) Variáveis e os sı́mbolos constantes descritos acima são expressões da linguagem L(D∞ ).
(ii) se ∗ ∈ {k , | , · , +b } e t0 , t1 , . . . , tn , tn+1 , . . . b ∈ L(D∞ ) então ∗0i=n+1 (ti ) = tn+1 ∗ tn ∗ . . . ∗ t0 e
n+1
∗i=0
(ti ) = t0 ∗ . . . ∗ tn ∗ tn+1 são expressões da linguagem L(D∞ ) (finitas na construção temporal de D∞ );
(iii) se ∗ ∈ {k , | , · , +b } e t0 , t1 , . . . , tn , tn+1 , . . . ∈ L(D∞ ) então ∗∞
n=0 tn = t0 ∗ t1 ∗ . . . ∗ tn+1 ∗ . . . é uma
expressão na linguagem L(D∞ ) (infinita na construção temporal de D∞ ).
Diz-se que cada expressão da linguagem L(D∞ ) é a representação de um processo em D∞ , ou ainda, o processo é
a interpretação de sua correspondente expressão textual na linguagem L(D∞ ). O mesmo pode ser considerado quando
diagramas são consideramos como as expressões gráficas para LVMG.
Numa abordagem uni-dimensional, na Figura 1(a) mostra-se a representação de um processo elementar dk ∈ IP
que executa a ação identificada por d rotulada por k. Na Figura 1(b) tem-se a representação gráfica do processo
identidade, indicado pela expressão Skip ∈ IP , no qual o estado de entrada coincide com o estado de saı́da. A
abordagem não-determinı́stica do modelo força a optar-se por um tratamento não-tradicional dos testes computacionais. Para cada texte booleano t ∈ IT (graficamente representado na Figura 1(c)) capaz de textar um estado determinı́stico s, consideram-se duas formas distintas de textes para um estado não-determinı́stico s: uma forma existential
(t∃ (s) ≡ ∃s ∈ s . t(s)) e uma forma universal (t ∀ (s) ≡ ∀s ∈ s . t(s)), respectivamente representados na Figura
3
Figura 1: Processo elementar, processo identidade e testes computacionais
1(d)(e). Ambas as formas coincidem com a forma simples de texte t quando s é representado um conjunto unitário identificando um estado determinı́stico em S.
Considerando-se os processos elementares dk e el e teste b, apresenta-se as representações gráficas para os processos resultantes da aplicação dos construtores do conjunto IOp do modelo MG. Primeiramente, na Figura 2(a), tem-se
o produto seqüencial dk · el . Então este produto seqüencial primeiro executa d colocando o resultado na posição k e
após o seu término, inicia a execução do processo e relativo à posição l. Na Figura 2(b), a direita do processo seqüencial, está representado a soma determinı́stica dk +b el , representando uma escolha: executa-se o processo elementar
dk se o teste b é verdadeiro, senão executa-se o processo elementar el . A soma não-determinı́stica | dk , ek | executada
entre os processos elementares mutuamente exclusivos (ou conflitantes) na posição k de memória, está representada
na Figura 2(c). E por fim, na Figura 2(d) apresenta-se o produto paralelo k dk , el k entre os processos elementares
concorrentes, com k 6= l, representando a execução simultânea dos correspondentes processos.
Figura 2: Construtores de processos aplicados a processos elementares
No caso geral, dois processos são mutuamente exclusivos sempre que existir no mı́nimo uma mesma posição de
memória afetada por ambos. Neste sentido, a arbitrariedade da escolha constitui-se na principal caracterı́stica da soma
não-determinı́stica de processos.
A construção indutiva e ordenada do modelo MG garante a representação de processos parciais e facilitam a
interpretação semântica associada à transição de estados que define um processo computacional. A Figura 3 mostra alguns processos parciais, finitos na construção temporal, representados no modelo MG e relacionados com os
construtores do conjunto IOp cuja expressão textual é dada por dk · Skip, dk +b Skip, k dk , Skip k e | dk , Skip |,
respectivamente.
Figura 3: Objetos parciais representados no modelo MG
Além destes, o modelo MG admite representação para processos infinitos no sentido temporal e espacial, expressos
k
k
recursivamente na linguagem L(D∞ ) pelas expressões ·∞
, k∞
(Veja Figuras 4(a)(b)).
k=0 d
k=0 d
Figura 4: Objetos parciais representados no modelo MG
4
2.3
Linguagens Visuais
As linguagens visuais são usadas em muitas áreas de aplicação, incluindo aprendizagem de conhecimento, aplicações
de técnicas de programação para não-programadores, adaptação de programas padronizados e o desenvolvimento de
interfaces gráficas para usuários. Além destes, as linguagens visuais são utilizadas para desenvolvimento de programas
computacionais, especialmente aqueles destinados à análise e desenvolvimento de sistemas. Exemplos bem conhecidos para especificação e modelagem de uma linguagem visual (LV) podem ser encontrados em [5]. A definição de
uma LV consiste na construção de um alfabeto visual (AV) e uma gramática visual (GV), produzindo a especificação
da linguagem visual. Dada uma especificação, uma linguagem visual é um conjunto de todos os diagramas (expressões
da linguagem) que podem ser derivados da aplicação das regras gramaticais a um diagrama inicial. De acordo com o
conteúdo de uma especificação de LV se constrói o editor de alfabeto e o editor de gramática. A partir da definição da
LV usando estes editores, uma especificação é gerada por um editor gráfico, responsável pela construção de diagramas
sintáticos dirigidos (regras gramaticais). Veja a Figura 5.
Figura 5: Especificação do ambiente para da LV para processos no modelo MG
São considerados dois tipos de sintaxe para construção do alfabeto e da gramática de uma LV. A sintaxe abstrata,
responsável pela estrutura lógica das expressões da linguagem e representadas por diagramas especiais definidos por
grafos dirigidos. A sintaxe concreta, orientando a definição do layout de cada diagrama, para manipulação do usuário.
Nesta abordagem, o alfabeto visual é representado por um grafo, e a gramática visual é representada por uma gramática
de grafos. Um alfabeto visual estabelece um conjunto de sı́mbolos e conexões utilizados na especificação de uma
linguagem visual, ou seja, define o vocabulário de uma LV. A construção de cada sı́mbolo do alfabeto consiste na
construção de um grafo onde os nodos e arestas estão relacionados por atributos e conexões. Uma gramática visual é
representada por uma gramática de grafos que consistem de um diagrama inicial e um conjunto finito de regras que
geram outros diagramas da linguagem visual que no caso, representam os processos modelados pelo modelo MG.
2.4
Teoria dos Grafos
Um grafo é dado por dois conjuntos disjuntos, que determinam os objetos do grafo: o conjunto de nodos do grafo,
indicados neste trabalho por retângulos e o conjunto de arcos (arestas) dirigidos geralmente visualizados como flechas.
Todo grafo é construı́do sobre um grafo de tipos, considerando-se operações sobre estes tipos, de acordo com uma
especificação algébrica. Os objetos de um grafo podem possuir atributos que são utilizados para armazenar dados
(propriedades como nome e posição) relacionados com estes objetos(processos).
Neste texto, um atributo será um nodo do grafo denotado por um retângulo arredondado, da mesma forma que um
arco de atributo é denotado por uma flecha que conecta o nodo atributo com seu tipo (conjunto). Em particular, quando
os grafos estão instanciados, o arco de atributo conecta o atributo com seu valor corrente. Um relacionamento entre
dois grafos constitui-se numa transformação (morfismo) de grafos compatı́vel com os tipos e a estrutura previamente
definidos, mapeando os nodos e arcos do primeiro grafo em nodos e arcos do segundo grafo, respectivamente. Neste
caso, pode-se definir uma transformação de grafos por um par de morfismos (possivelmente parciais): o morfismo
definido sobre os nodos e o outro, definido sobre os arcos dirigidos. As transformações de grafos definem as regras
para a manipulação de grafos, que mostram os aspectos dinâmicos na construção dos processos representados no
modelo MG. As definições fundamentadas na Teoria dos Grafos apresentadas ao longo deste relatório foram baseadas
nas referências [11].
5
3 Especificação do Alfabeto para a LVMG
A seguir, são apresentados os grafos associados aos testes, processos elementares e identidade no alfabeto visual (AV).
3.1
Processo Identidade
O grafo que representa o processo identidade na LV para o modelo MG possui um nodo (objeto-processo) representado por uma seta na sintaxe concreta, e um nodo atributo-ação responsável por sua identificação nominal, conforme
mostra a Figura 6. O atributo-ação é identificado pela palavra Skip que pertence a um conjunto Σ de palavras e sua
representação é um retângulo com as extremidades arredondadas com dois arcos (conexões): o primeiro com origem
no nodo-atributo e que se liga ao conjunto Σ e o outro com origem no nodo-atributo e com destino no objeto-processo.
Na sintaxe concreta, a função de inclusão é indicada por um arco tracejado e nomeado incl ação, onde o nome do
atributo é mapeado para a sua localização no diagrama de representação do processo identidade e próximo a ele fica
uma especificação quanto ao tamanho e ao nome da fonte utilizada.
3.2
Processo Elementar
Onde processo elementar constitue-se sı́mbolos do AV definido como um grafo. Para a representação gráfica de um
processo elementar no AV considera-se primeiramente a sintaxe abstrata.
Nesta construção, os atributos de um processo elementar são caracterizados pela posição e ação e constituemse em objetos-atributo do objeto-processo e compõem o grafo que representa um processo elementar. O atributoposição é determinado pelo rótulo que pertence a um conjunto de rótulos e sua representação é um retângulo com
as extremidades arredondadas. De forma análoga, o atributo-ação é identificado por uma palavra que pertence a Σ e
sua representação é também um retângulo com as extremidades arredondadas. Cada objeto-atributo têm dois arcos
(n-ação, n-pos):
1. o primeiro com origem no nodo-atributo se liga ao conjunto que define seu nome;
2. o outro com origem no nodo-atributo e com destino no objeto-processo elementar.
Na Sintaxe Concreta o diagrama de representação do processo elementar é identificado por um retângulo com duas
conexões laterais e dividido em partes. Nas duas divisões centrais colocam-se as correspondentes posições e ações.
Esta tarefa é formalizada pelas funções de inclusão, indicadas por arcos tracejados e nomeadas incl pos e incl ação.
As funções de inclusão mapeiam os nomes dos atributos a sua localização no diagrama de representação do processo
elementar. Próximo a elas fica uma declaração do tamanho e do nome da fonte utilizada, conforme mostra a Figura 7.
Figura 6: Representação do Processo Identidade
Figura 7: Representação do Processo Elementar
6
3.3
Testes Computacionais
Da mesma forma são construı́das as especificações dos grafos que identificam os testes computacionais. Nas Figuras
8 e 9tem-se a especificação para os testes universal e existencial, respectivamente.
Figura 8: Teste Computacional Universal
3.4
Figura 9: Teste Computacional Existencial
Processo Seqüencial
O objeto-processo seqüencial resulta da aplicação do construtor produto seqüencial. A Figura 10 mostra o grafo do
tipo processo seqüencial.
Figura 10: Representação de processo seqüencial
Figura 11: Representação de processo recursivo seqüencial
Pela sintaxe abstrata, o diagrama de representação do produto seqüencial é definido sempre que se puder explicitar
os dois objetos e os conectores que o constroem. Tanto o primeiro (identificado por um objeto-processo acrescido do
conector “para”) quanto o segundo fator (identificado por um objeto-processo acrescido do conector “de”) são subgrafos gerados pela LV representando processos parciais ou elementos do alfabeto visual. Na sintaxe concreta o produto
seqüencial é representado por dois nodos onde eles se concatenam formando um novo processo. O diagrama é composto também pelas funções de inclusão, de dois argumentos, identificados neste caso pelas expressões incluir nome e
comb desl. A especificação completa de um processo seqüencial instanciado à processos elementares, está explicitada
na Figura 12.
3.5
Processo Recursivo Seqüencial
A especificação no AV de um processo recursivo sequencial é construı́da de forma análoga e está apresentada na
Figura 11.
7
Figura 12: Processo seqüencial instanciado a processos elementares
3.6
Processo Seqüencial Parcial
O grafo que modela um produto seqüencial parcial é representado por dois sub-grafos onde um deles é sempre o
Processo Identidade Skip. Neste casos, reduz-se a representação, sendo o processo seqüencial parcial representado
por um grafo que possui um subgrafo representando um objeto-processo (subgrafo gerados pela LV representando
processos ou elementos do alfabeto visual) e uma conexão (sub-entendida como o Processo Identidade). Pela sintaxe
abstrata, o diagrama de representação do processo seqüencial parcial é definido sempre que se puder explicitar um dos
objetos e o conector. Neste caso, quando o
1. objeto-processo é acrescido do conector “para” tem-se a representação do processo seqüencial parcial à direita;
e
2. objeto-processo é acrescido do conector “de” tem-se a representação do processo seqüencial parcial à esquerda.
Na sintaxe concreta as transformações são definidas por funções unárias: as funções deslocamento (desl dir e desl esq)
e as funções de inclusão (inclui ndir e inclui nesq). Os diagramas apresentados nas Figuras 13 e 14 representam
processos seqüenciais parciais à direita e à esquerda, respectivamente.
Figura 13: Processo seqüencial parcial à direita
Figura 14: Processo seqüencial parcial à esquerda
Os processos seqüenciais parciais podem ser definidos como processos seqüenciais sempre que um dos fatores é o
Processo Identidade.
3.7
Processo Produto Paralelo
O grafo do tipo produto paralelo identifica processos concorrentes e está representado na Figura 15. Pela sintaxe
abstrata, o diagrama de representação de um processo concorrente é definido sempre que se puder explicitar os dois
objetos-processo, as correspondentes posições de memória afetadas pelas suas execuções e os conectores que o constroem. Tanto o primeiro objeto (identificado por um objeto-processo acrescido do conector “fator inf”) quanto o
segundo (identificado por um objeto-processo acrescido do conector “fator sup”) são subgrafos gerados pela LV.
8
Figura 16: Representação de processo recursivo produto paFigura 15: Representação de processo produto paralelo
ralelo
Na sintaxe concreta, o diagrama para processos concorrentes consiste num grafo formado por dois subgrafos. O
grafo do tipo processo concorrente possue um objeto-atributo, representados por uma janela, indicando o conjunto
de posições de memória afetadas quando da execução de cada processo representado no diagrama. Veja na Figura
15, a janela Υ(k p, q k). Cada subgrafo representa um objeto-processo, localizado graficamente entre barras grifadas,
verticais e paralelas. A especificação do diagrama é completada pela composição das funções de dois argumentos que
retornam um argumento: inserepp e incluipp nome. O grafo que representa o produto paralelo só pode ser construı́do
quando Υ(p) e Υ(q) são conjuntos são disjuntos (caracterizando processos são concorrentes). Na Figura 17, está
representado um processo concorrente instanciado a processos elementares com os objetos-atributo e as conexões
desta instância, pode se observar também a concorrência pelo dk e el onde Γ(dk )=k, Γ(el )=l e k6=l.
Logo a seguir apresenta-se outros exemplos de instâncias aplicadas a processos concorrentes. No caso da Figura 17,
supõe-se que os conjuntos Υ(du · ep ) = {u, p} e Υ(dt · el ) = {t, l} são disjuntos.
Figura 17: Processo paralelo instanciado a processos seqüenciais
3.8
Processos Recursivo Produto Paralelo
A especificação de um processo recursivo produto paralelo é obtido da mesma forma e está representada na Figura 16.
Neste caso, considera-se que o conjunto de posições de memória é construı́do pelo conjunto dos naturais extendidos.
3.9
Processos Produto Paralelo Parcial
O grafo que modela um produto paralelo parcial é representado por dois sub-grafos onde um deles é sempre o Processo
Identidade representado pela expressão Skip. Neste caso, reduz-se a representação, sendo o processo concorrente
9
parcial representado por um diagrama que possui dois subgrafos: um destes subgrafos representa um objeto-processo
(subgrafo gerados pela LV representando processos obtidos por aplicação de construtores ou elementos do alfabeto
visual); outro representa o Processo Identidade. Estes subgrafos também estão graficamente limitados por barras
grifadas, verticais e paralelas. Pela sintaxe abstrata, o diagrama de representação do processo concorrente parcial é
definido sempre que se puder explicitar um dos objetos e o conector que o constroem. Neste caso, tem-se
1. o objeto-processo acrescido do conector “fator sup” representa do processo concorrente parcial superior;
2. o objeto-processo acrescido do conector “fator inf” representa do processo concorrente parcial inferior.
Na sintaxe concreta as transformações são definidas por funções unárias, no caso funções inspp sup e inspp inf e as
funções nomepp sup e nomepp inf. Considera-se que Γ(Skip) = , ou seja, o Processo Identidade é sempre concorrente com os demais processos computacionais. Os diagramas apresentados nas Figuras 18 e 19 que representam
processos concorrentes parciais superior e inferior, respectivamente.
Figura 18: Processo concorrente Parcial Superior
4
Figura 19: Processo concorrente parcial inferior
Especificação da Gramática da LVMG
Nesta seção apresenta-se as especificações da gramática que define as regras de construção dos processos na LVMG.
4.1
Especificação da Regra de Construção do Produto Seqüencial
A regra de construção do produto seqüencial é dividida em duas etapas, identificadas como a preparação e a realização.
Cada etapa é modelada por uma transformação entre subgrafos definidos no vocabulário da LVMG.
Na preparação tem-se a construção dos grafos que modelam os dois produto seqüencial parciais, um à direita e
outro à esquerda, sendo cada um deles representado por dois sub-grafos onde um deles é sempre o Processo Identidade.
Esta etapa define uma restrição (condição previamente satisfeita) para aplicação do produto seqüencial. Na etapa de
realização ocorre a execução propriamente dita da regra, apresentando o como resultado o novo grafo representando
o produto seqüencial. Esta segunda etapa só ocorre entre dois objetos-processo resultantes da etapa de preparação, e
torna explı́cita a fase de conclusão desta regra gramatical, conforme mostra a construção gráfica apresentada na Figura
20. As funções de dois argumentos que retornam um argumento e estão envolvidas na especificação desta etapa são:
inclui nome e comb desl.
4.2
Especificação da Regra de Construção de Processos Recursivos
A regra de construção de processos recursivos cujas especificações foram apresentadas nas Subseções 3.8 e 3.5 é
construı́da também em duas etapas, preparação e realização. As Figuras 21 e 22 ilustram a construção da etapa de
realização da regra de construção dos respectivos processos.
10
Figura 20: Regra gramatical para a construção de um processo seqüencial
Figura 21: Processo concorrente parcial superior
4.3
Figura 22: Processo concorrente parcial inferior
Especificação da Regra de Construção do Produto Paralelo
A seguir, apresenta-se a transformação de grafos que formaliza a regra gramatical para o construtor produto paralelo,
também definida em duas etapas. Na preparação, a sintaxe abstrata para os processos concorrentes são representados
por subgrafos identificados pelos arcos de conexão: fator sup e fato inf.
Na sintaxe concreta o produto paralelo é representado por diagramas restringidos por barras verticais paralelas entre os quais estão dois objetos-processo sobrepostos. Estas sobreposições, na sintaxe concreta, são identificados pelas
funções: nomepp sup, nomepp inf (identificando o processo) e inspp sup, inspp inf (inserindo o processo). Na Figura
23, mostram-se os objetos e as conexões envolvidos na transformação dos grafos desta subetapa e apresentam-se os
correspondentes morfismos envolvidos na gramática. Na sintaxe concreta a transformação é definida pela composição
das funções que nomeiam (nomepp sup e nomepp inf) com a função incluipp resultando na função incluipp nomeia).
Assim também é definida a função combpp insp. O diagrama de representação para a regra geral do processo paralelo
está representado logo a seguir, na Figura 23 apresentando ambas as etapas que tornam explı́cita a composição que
gera a regra de construção de processos concorrentes..
Figura 23: Regra gramatical para a construção de um processo paralelo
11
Conclusão
O modelo GM é uma máquina abstrata, com memória infinita e tempo de acesso constante , desenvolvida com o
objetivo de prover uma análise semântica para computações (parciais) de algoritmos (recursivos) da cientı́fica envolvendo concorrência e não-determinismo, com ênfase especial em aplicações envolvendo Matemática Intervalar,
Processos Estocásticos e Autômatos Celulares. A linguagem de programação induzida pela estrutura ordenada do modelo MG mostra que objetos (conjuntos coerentes) do espaço coerente D∞ interpretando processos representados por
expressões textual na linguagem L(D∞ ) podem ser facilmente transcritos por diagramas na correspondente linguagem visual. Da mesma forma, funções lineares definidas sobre o espaço coerente D∞ interpretando construtores de
processos em L(D∞ ) podem ser facilmente transcritos por transformações de grafos em LVMG. Neste sentido, pela
Programação Visual, é possı́vel usufruir de todas as potencialidades do modelo computacional MG. Sua construção
indutiva modelando a estrutura temporal e sua especificação espacial responsável pela sincronização de posições de
memória justificam a especificação apresentada neste trabalho.
Agradecimento
Este trabalho foi parcialmente financiado pelas agências brasileiras CTINFO/CNPq e FAPERGS.
Referências
[1] Abramsky S. and Jung, A. Domain Theory. On Handbook of Logic in Computer Science. Clarendon Press.
(1994).
[2] Bardohl, R. and Ermel C. Visual Specification and Parsing of a Statechart Variant using GENGED. On Symposium on Visual Languages and Formal Methods. Italy. (September, 2001), pp. 5-7.
[3] Dimuro, G. P. , Costa A. C. R. and Claudio D. M. A Coherence Space of Rational Intervals for a Construction of
IR. Reliable Computing. Vol 6, No. 2, (2000), pp. 139-178.
[4] Girard, J. -Y. Linear logic. Theoretical Computer Science, Vol 1, (1987), pp. 187-212.
[5] Marriott, K. and Meyer, B. Visual Language Theory. Springer. (1998).
[6] Milner, R. Communication and Concurrency. Prentice Hall: Engl. Cliffs. (1990).
[7] Reiser, R. H. S., Costa A. C. R. and Dimuro, G. P. First steps in the construction of the Geometric Machine. On
Tendências em Matemática Aplicada e Computacional Vol 1, No. 3, (2002), pp. 183-192.
[8] Reiser, R. H. S. The Geometric Machine - a model for concurrence and non-determinism based on coherence
spaces. Porto Alegre: CPGCC/UFRGS, (2002), 240 p.
[9] Reiser, R. H. S. , Costa, A. C. R. and Dimuro, G. P. A programming language for the Inteval Geometric Machine
Model. On Eletronic Notes in Theoretical Computer Science. vol 84, (2003), 12p.
[10] Reiser, R. H. S., Costa A. C. R. and Dimuro, G. P. The Interval Geometric Machine. On Tendências em Matemática Aplicada e Computacional Vol 1, No. 3, (2003), 10 p.
[11] Rozenberg, G. Graph Grammars and Computing by Graph Transformations. Vol 1, (1997).
[12] Scott, D. Some definitional suggestions for automata theory. On Journal of Computer and System Sciences. Vol
1, (1967), pp.187-212.
[13] Scott, D. The lattice of flow diagrams. On Lecture Notes in Mathematics. Springer Verlag. (1971), pp.311-372.
12