Programação baseada em fluxo - Flow-based programming

Paradigmas de programação

Na programação de computadores , a programação baseada em fluxo ( FBP ) é um paradigma de programação que define aplicativos como redes de processos de "caixa preta" , que trocam dados através de conexões predefinidas por passagem de mensagem , onde as conexões são especificadas externamente aos processos. Esses processos de caixa preta podem ser reconectados indefinidamente para formar diferentes aplicativos sem ter que ser alterado internamente. O FBP é, portanto, naturalmente orientado para o componente .

FBP é uma forma particular de programação de fluxo de dados com base em buffers limitados, pacotes de informações com tempos de vida definidos, portas nomeadas e definição separada de conexões.

Introdução

A programação baseada em fluxo define aplicativos usando a metáfora de uma "fábrica de dados". Ele vê um aplicativo não como um processo único e sequencial, que começa em um ponto no tempo e, em seguida, faz uma coisa por vez até que seja concluído, mas como uma rede de processos assíncronos que se comunicam por meio de fluxos de blocos de dados estruturados, chamados de "pacotes de informação" (IPs). Nesta visualização, o foco está nos dados do aplicativo e nas transformações aplicadas a eles para produzir as saídas desejadas. A rede é definida externamente aos processos, como uma lista de conexões que é interpretada por um software, normalmente denominado de "escalonador".

Os processos se comunicam por meio de conexões de capacidade fixa. Uma conexão é anexada a um processo por meio de uma porta , que possui um nome acordado entre o código do processo e a definição da rede. Mais de um processo pode executar o mesmo trecho de código. A qualquer momento, um determinado IP só pode ser "pertencente" a um único processo ou estar em trânsito entre dois processos. As portas podem ser simples ou do tipo array, conforme usado, por exemplo, para a porta de entrada do componente Collate descrito abaixo. É a combinação de portas com processos assíncronos que permite que muitas funções primitivas de processamento de dados de longa duração, como Sort, Merge, Summarize, etc., sejam suportadas na forma de caixas pretas de software .

Como os processos FBP podem continuar em execução enquanto tiverem dados para trabalhar e em algum lugar para colocar sua saída, os aplicativos FBP geralmente são executados em menos tempo decorrido do que os programas convencionais e fazem uso ideal de todos os processadores em uma máquina, sem necessidade de programação especial Para alcançar isto.

A definição de rede geralmente é diagramática e é convertida em uma lista de conexão em alguma linguagem ou notação de nível inferior. FBP é frequentemente uma linguagem de programação visual neste nível. As definições de rede mais complexas têm uma estrutura hierárquica, sendo construídas a partir de sub-redes com conexões "pegajosas". Muitas outras linguagens / tempos de execução baseados em fluxo são construídos em torno de linguagens de programação mais tradicionais, o exemplo mais notável é RaftLib, que usa operadores C ++ do tipo iostream para especificar o gráfico de fluxo.

O FBP tem muito em comum com a linguagem Linda por ser, na terminologia de Gelernter e Carriero, uma "linguagem de coordenação": é essencialmente independente da linguagem. De fato, dado um escalonador escrito em uma linguagem de nível suficientemente baixo, os componentes escritos em diferentes linguagens podem ser ligados entre si em uma única rede. O FBP, portanto, se presta ao conceito de linguagens específicas de domínio ou "minilínguas".

O FBP exibe "acoplamento de dados", descrito no artigo sobre o acoplamento como o tipo mais frouxo de acoplamento entre os componentes. O conceito de acoplamento flexível, por sua vez, está relacionado ao de arquiteturas orientadas a serviços , e o FBP se encaixa em vários critérios para tal arquitetura, embora em um nível mais refinado do que a maioria dos exemplos dessa arquitetura.

O FBP promove um estilo funcional de alto nível de especificações que simplificam o raciocínio sobre o comportamento do sistema. Um exemplo disso é o modelo de fluxo de dados distribuídos para especificar e analisar construtivamente a semântica de protocolos multipartidários distribuídos.

História

A Programação Baseada em Fluxo foi inventada por J. Paul Morrison no início dos anos 1970 e inicialmente implementada em software para um banco canadense. O FBP em seu início foi fortemente influenciado por algumas linguagens de simulação da IBM do período, em particular GPSS , mas suas raízes remontam ao artigo seminal de Conway sobre o que ele chamou de co-rotinas .

O FBP passou por uma série de mudanças de nome ao longo dos anos: a implementação original foi chamada de AMPS (Advanced Modular Processing System). Um grande aplicativo no Canadá entrou em operação em 1975 e, a partir de 2013, está em uso contínuo de produção, funcionando diariamente, por quase 40 anos. Como a IBM considerou as idéias por trás do FBP "muito parecidas com uma lei da natureza" para serem patenteáveis, ela, em vez disso, colocou os conceitos básicos do FBP em domínio público, por meio de um Boletim de Divulgação Técnica , "Sistema de Programação de Tarefas Modulares e Intercaladas com Resposta a Dados" , em 1971. Um artigo que descreve seus conceitos e experiência de uso foi publicado em 1978 no IBM Research IBM Systems Journal sob o nome de DSLM. Uma segunda implementação foi feita como um projeto conjunto da IBM Canadá e IBM Japão, sob o nome "Data Flow Development Manager" (DFDM), e foi brevemente comercializada no Japão no final dos anos 80 sob o nome "Data Flow Programming Manager".

Geralmente, os conceitos eram referidos na IBM como "Fluxo de Dados", mas esse termo foi considerado muito geral e, por fim, o nome "Programação Baseada em Fluxo" foi adotado.

Do início dos anos 80 a 1993, J. Paul Morrison e o arquiteto da IBM, Wayne Stevens, refinaram e promoveram os conceitos por trás do FBP. Stevens escreveu vários artigos descrevendo e apoiando o conceito de FBP e incluiu material sobre ele em vários de seus livros. Em 1994, Morrison publicou um livro descrevendo o FBP e fornecendo evidências empíricas de que o FBP levou a tempos de desenvolvimento reduzidos.

Conceitos

O diagrama a seguir mostra as principais entidades de um diagrama FBP (além dos Pacotes de Informações). Esse diagrama pode ser convertido diretamente em uma lista de conexões, que pode então ser executada por um mecanismo apropriado (software ou hardware).

Diagrama FBP simples

A, B e C são processos que executam componentes de código. O1, O2 e as duas INs são portas que conectam as conexões M e N aos seus respectivos processos. É permitido que os processos B e C executem o mesmo código, então cada processo deve ter seu próprio conjunto de armazenamento de trabalho, blocos de controle, etc. Quer compartilhem ou não o código, B e C são livres para usar a mesma porta nomes, já que os nomes das portas têm significado apenas nos componentes que os referenciam (e no nível da rede, é claro).

M e N são o que costumamos ser chamados de " buffers limitados " e têm uma capacidade fixa em termos do número de IPs que podem conter a qualquer momento.

O conceito de portas é o que permite que um mesmo componente seja utilizado em mais de um local da rede. Em combinação com uma capacidade de parametrização, chamada Initial Information Packets (IIPs), as portas fornecem ao FBP a capacidade de reutilização de componentes, tornando o FBP uma arquitetura baseada em componentes . O FBP, portanto, exibe o que Raoul de Campo e Nate Edwards, da IBM Research , denominaram modularidade configurável .

Pacotes de informação ou IPs são alocados no que pode ser chamado de "espaço IP" (assim como as tuplas de Linda são alocadas no "espaço tupla"), e têm um tempo de vida bem definido até que sejam descartados e seu espaço seja recuperado - em FBP isso deve ser uma ação explícita por parte de um processo de propriedade. IPs que viajam por uma determinada conexão (na verdade, são seus "identificadores" que viajam) constituem um "fluxo", que é gerado e consumido de forma assíncrona - esse conceito, portanto, tem semelhanças com o conceito de contras preguiçosas descrito no artigo de 1976 de Friedman e Wise.

Os IPs são geralmente blocos de dados estruturados - alguns IPs, no entanto, podem não conter nenhum dado real, mas são usados ​​simplesmente como sinais. Um exemplo disso são os "IPs de suporte", que podem ser usados ​​para agrupar IPs de dados em padrões sequenciais dentro de um fluxo, chamados de "subfluxos". Os subfluxos podem, por sua vez, ser aninhados. Os IPs também podem ser encadeados para formar "árvores de IP", que viajam pela rede como objetos únicos.

O sistema de conexões e processos descritos acima pode ser "ramificado" para qualquer tamanho. Durante o desenvolvimento de um aplicativo, processos de monitoramento podem ser adicionados entre pares de processos, processos podem ser "explodidos" em sub-redes ou simulações de processos podem ser substituídas pela lógica de processo real. O FBP, portanto, se presta à prototipagem rápida .

Esta é realmente uma imagem de linha de montagem de processamento de dados: os IPs que viajam por uma rede de processos podem ser pensados ​​como widgets que viajam de uma estação para outra em uma linha de montagem. As "máquinas" podem ser facilmente reconectadas, retiradas da linha para reparo, substituídas e assim por diante. Curiosamente, essa imagem é muito semelhante à do equipamento de registro de unidade usado para processar dados antes dos dias dos computadores, exceto que os baralhos de cartas tinham de ser carregados manualmente de uma máquina para outra.

As implementações de FBP podem ser não preemptivas ou preemptivas - as implementações anteriores tendiam a ser não preemptivas (mainframe e linguagem C), enquanto a implementação Java mais recente (veja abaixo) usa a classe Java Thread e é preemptiva.

Exemplos

"Problema do telegrama"

Os componentes do FBP freqüentemente formam pares complementares. Este exemplo usa dois desses pares. O problema descrito parece muito simples conforme descrito em palavras, mas na verdade é surpreendentemente difícil de realizar usando a lógica processual convencional. A tarefa, chamada de "Problema do Telegrama", originalmente descrita por Peter Naur , é escrever um programa que aceite linhas de texto e gere linhas de saída contendo o maior número de palavras possível, onde o número de caracteres em cada linha não exceda um certo comprimento. As palavras não podem ser divididas e assumimos que nenhuma palavra é maior do que o tamanho das linhas de saída. Isso é análogo ao problema de quebra de linha em editores de texto.

Na lógica convencional, o programador descobre rapidamente que nem as estruturas de entrada nem de saída podem ser usadas para conduzir a hierarquia de chamadas do fluxo de controle . No FBP, por outro lado, a própria descrição do problema sugere uma solução:

  • "palavras" são mencionadas explicitamente na descrição do problema, portanto, é razoável para o designer tratar as palavras como pacotes de informação (IPs)
  • no FBP não há uma única hierarquia de chamadas, portanto, o programador não fica tentado a forçar um subpadrão da solução a ser o nível superior.

Aqui está a solução mais natural no FBP (não há uma única solução "correta" no FBP, mas parece um ajuste natural):

O "problema do telegrama" de Peter Naur

onde DC e RC representam "DeCompose" e "ReCompose", respectivamente.

Conforme mencionado acima, os Pacotes de Informações Iniciais (IIPs) podem ser usados ​​para especificar informações paramétricas, como o comprimento de registro de saída desejado (exigido pelos dois componentes mais à direita) ou nomes de arquivo. IIPs são blocos de dados associados a uma porta na definição de rede que se tornam IPs "normais" quando um "recebimento" é emitido para a porta relevante.

Atualização em lote

Este tipo de programa envolve passar um arquivo de "detalhes" (alterações, adições e exclusões) contra um "arquivo mestre" e produzir (pelo menos) um arquivo mestre atualizado e um ou mais relatórios. Os programas de atualização são geralmente muito difíceis de codificar usando código de procedimento síncrono, pois dois (às vezes mais) fluxos de entrada devem ser mantidos sincronizados, embora possa haver mestres sem detalhes correspondentes, ou vice-versa.

Estrutura canônica de "atualização em lote"

No FBP, um componente reutilizável (Collate), baseado na ideia de registro de unidade de um Collator, torna a escrita desse tipo de aplicativo muito mais fácil, pois Collate mescla os dois fluxos e insere IPs de colchetes para indicar níveis de agrupamento, simplificando significativamente a lógica downstream. Suponha que um stream ("mestres" neste caso) consista em IPs com valores-chave de 1, 2 e 3, e os IPs do segundo stream ("detalhes") tenham valores-chave de 11, 12, 21, 31, 32, 33 e 41, onde o primeiro dígito corresponde aos valores da chave mestra. Usando colchetes para representar IPs de "colchetes", o fluxo de saída agrupado será o seguinte: 

( m1 d11 d12 ) ( m2 d21 ) ( m3 d31 d32 d33 ) (d41)

Como não havia mestre com valor 4, o último grupo é composto por um único detalhe (mais colchetes).

A estrutura do fluxo acima pode ser descrita sucintamente usando uma notação semelhante a BNF , como 

{ ( [m] d* ) }*

Collate é uma caixa preta reutilizável que só precisa saber onde estão os campos de controle em seus IPs de entrada (mesmo isso não é estritamente necessário, pois os processos do transformador podem ser inseridos a montante para colocar os campos de controle em locais padrão) e podem de fato ser generalizados a qualquer número de fluxos de entrada e qualquer profundidade de aninhamento de colchetes. Collate usa uma porta do tipo array para entrada, permitindo um número variável de fluxos de entrada.

Processos de multiplexação

A programação baseada em fluxo suporta a multiplexação de processos de uma forma muito natural. Como os componentes são somente leitura, qualquer número de instâncias de um determinado componente ("processos") pode ser executado de forma assíncrona entre si.

Exemplo de multiplexação

Quando os computadores geralmente tinham um único processador, isso era útil quando havia muita E / S acontecendo; agora que as máquinas geralmente têm vários processadores, isso está começando a se tornar útil quando os processos também exigem muito da CPU. O diagrama nesta seção mostra um único processo de "Balanceador de carga" distribuindo dados entre três processos, rotulados S1, S2 e S3, respectivamente, que são instâncias de um único componente, que por sua vez alimenta um único processo em um "primeiro a chegar , primeiro a ser servido ".

Rede interativa simples

Esquema da aplicação interativa geral

Neste esquema geral, as solicitações (transações) provenientes dos usuários entram no diagrama no canto superior esquerdo e as respostas são retornadas no canto inferior esquerdo. Os "back ends" (no lado direito) comunicam-se com sistemas em outros sites, por exemplo, usando CORBA , MQSeries , etc. As conexões cruzadas representam pedidos que não precisam ir para os back-ends ou pedidos que precisam percorrer a rede mais de uma vez antes de ser devolvida ao usuário.

Como diferentes solicitações podem usar diferentes back-ends e podem exigir diferentes quantidades de tempo para os back-ends (se usados) processá-los, deve-se fazer uma provisão para relacionar os dados retornados às transações de solicitação apropriadas, por exemplo, hash tables ou caches.

O diagrama acima é esquemático no sentido de que o aplicativo final pode conter muitos mais processos: os processos podem ser inseridos entre outros processos para gerenciar caches, exibir o tráfego de conexão, monitorar a taxa de transferência, etc. Além disso, os blocos no diagrama podem representar "sub-redes" - pequenas redes com uma ou mais conexões abertas.

Comparação com outros paradigmas e metodologias

Jackson Structured Programming (JSP) e Jackson System Development (JSD)

Artigos principais: Jackson Structured Programming and Jackson System Development

Essa metodologia assume que um programa deve ser estruturado como uma única hierarquia procedural de sub-rotinas. Seu ponto de partida é descrever a aplicação como um conjunto de "linhas principais", com base nas estruturas de dados de entrada e saída. Uma dessas "linhas principais" é então escolhida para conduzir todo o programa, e as outras precisam ser "invertidas" para transformá-las em sub-rotinas (daí o nome "inversão de Jackson"). Isso às vezes resulta no que é chamado de "conflito", exigindo que o programa seja dividido em vários programas ou corrotinas. Ao usar o FBP, esse processo de inversão não é necessário, pois cada componente do FBP pode ser considerado uma "linha principal" separada.

FBP e JSP compartilham o conceito de tratar um programa (ou alguns componentes) como um analisador de um fluxo de entrada.

No trabalho posterior de Jackson , Jackson System Development (JSD), as ideias foram desenvolvidas ainda mais.

Em JSD, o design é mantido como um design de rede até o estágio final de implementação. O modelo é então transformado em um conjunto de processos sequenciais para o número de processadores disponíveis. Jackson discute a possibilidade de executar diretamente o modelo de rede existente antes desta etapa, na seção 1.3 de seu livro (grifo adicionado):

A especificação produzida no final da etapa System Timing é, em princípio, capaz de execução direta. O ambiente necessário conteria um processador para cada processo, um dispositivo equivalente a um buffer ilimitado para cada fluxo de dados e alguns dispositivos de entrada e saída onde o sistema está conectado ao mundo real. Esse ambiente poderia, é claro, ser fornecido por um software adequado rodando em uma máquina suficientemente poderosa. Às vezes, essa execução direta da especificação será possível e pode até ser uma escolha razoável.

O FBP foi reconhecido por MA Jackson como uma abordagem que segue seu método de "decomposição de programas em processos sequenciais que se comunicam por um mecanismo semelhante a uma co-rotina"

Programação Aplicativa

Artigo principal: Linguagem de programação aplicável

WB Ackerman define uma linguagem aplicativo como aquela que faz todo o seu processamento por meio de operadores aplicados a valores. A linguagem de aplicativo mais antiga conhecida foi LISP.

Um componente FBP pode ser considerado como uma função que transforma seu (s) fluxo (s) de entrada em seu (s) fluxo (s) de saída. Essas funções são então combinadas para fazer transformações mais complexas, conforme mostrado aqui:

Duas funções alimentando um

Se rotularmos os fluxos, como mostrado, com letras minúsculas, o diagrama acima pode ser representado sucintamente da seguinte forma: 

c = G(F(a),F(b));

Assim como na notação funcional, F pode ser usado duas vezes porque só funciona com valores e, portanto, não tem efeitos colaterais, no FBP duas instâncias de um determinado componente podem ser executadas simultaneamente entre si e, portanto, os componentes FBP não devem ter efeitos colaterais qualquer. A notação funcional pode claramente ser usada para representar pelo menos uma parte de uma rede FBP.

Surge então a questão de saber se os próprios componentes FBP podem ser expressos usando notação funcional. WH Burge mostrou como expressões de fluxo podem ser desenvolvidas usando um estilo aplicativo recursivo de programação, mas este trabalho foi em termos de (fluxos de) valores atômicos. No FBP, é necessário ser capaz de descrever e processar blocos de dados estruturados (IPs FBP).

Além disso, a maioria dos sistemas aplicativos pressupõe que todos os dados estão disponíveis na memória ao mesmo tempo, enquanto os aplicativos FBP precisam ser capazes de processar fluxos de dados de longa execução enquanto ainda usam recursos finitos. Friedman e Wise sugeriram uma maneira de fazer isso adicionando o conceito de "contras preguiçosas" ao trabalho de Burge. Isso removeu a exigência de que ambos os argumentos dos "contras" estivessem disponíveis no mesmo instante. "Contras preguiçosas" não constrói realmente um fluxo até que ambos os seus argumentos sejam realizados - antes disso, ele simplesmente registra uma "promessa" de fazer isso. Isso permite que um stream seja realizado dinamicamente pela frente, mas com um back end não realizado. O final do fluxo permanece irrealizado até o final do processo, enquanto o início é uma sequência cada vez maior de itens.

Linda

Artigo principal: Linda

Muitos dos conceitos do FBP parecem ter sido descobertos independentemente em diferentes sistemas ao longo dos anos. Linda, mencionada acima, é uma delas. A diferença entre as duas técnicas é ilustrada pela técnica de balanceamento de carga da "escola de piranhas" de Linda - no FBP, isso requer um componente "balanceador de carga" extra que roteia as solicitações para o componente em uma lista que tem o menor número de IPs esperando para ser processado. Claramente, FBP e Linda estão intimamente relacionados, e um poderia ser facilmente usado para simular o outro.

Programação orientada a objetos

Artigo principal: Programação orientada a objetos

Um objeto em OOP pode ser descrito como uma unidade semi-autônoma que compreende informações e comportamento. Os objetos se comunicam por meio de "chamadas de método", que são essencialmente chamadas de sub-rotina, feitas indiretamente por meio da classe à qual pertence o objeto receptor. Os dados internos do objeto só podem ser acessados ​​por meio de chamadas de métodos, portanto, esta é uma forma de ocultação de informações ou "encapsulamento". O encapsulamento, no entanto, é anterior à OOP - David Parnas escreveu um dos artigos seminais sobre ele no início dos anos 70 - e é um conceito básico em computação. O encapsulamento é a própria essência de um componente FBP, que pode ser considerado uma caixa preta , realizando alguma conversão de seus dados de entrada em seus dados de saída. No FBP, parte da especificação de um componente são os formatos de dados e estruturas de fluxo que ele pode aceitar e aqueles que irá gerar. Isso constitui uma forma de projeto por contrato . Além disso, os dados em um IP só podem ser acessados ​​diretamente pelo processo de propriedade atual. O encapsulamento também pode ser implementado no nível da rede, fazendo com que os processos externos protejam os internos.

Um artigo de C. Ellis e S. Gibbs distingue entre objetos ativos e objetos passivos. Objetos passivos compreendem informações e comportamento, conforme declarado acima, mas eles não podem determinar o tempo desse comportamento. Os objetos ativos, por outro lado, podem fazer isso. Em seu artigo, Ellis e Gibbs afirmam que os objetos ativos têm muito mais potencial para o desenvolvimento de sistemas sustentáveis ​​do que os objetos passivos. Um aplicativo FBP pode ser visto como uma combinação desses dois tipos de objeto, onde os processos FBP corresponderiam a objetos ativos, enquanto os IPs corresponderiam a objetos passivos.

Modelo de ator

Artigo principal: modelo de ator

O FBP considera o Ator de Carl Hewitt como um processo assíncrono com 2 portas: uma para mensagens de entrada e outra para sinais de controle. Um sinal de controle é emitido pelo próprio ator após cada rodada de execução. O objetivo deste sinal é evitar a execução paralela do corpo do ator e assim permitir o acesso aos campos do objeto ator sem sincronização.

Veja também

Referências

links externos