Futuros e promessas - Futures and promises

Não deve ser confundido com a teoria da promessa .

Na ciência da computação , futuro , promessa , atraso e diferido referem-se a construções usadas para sincronizar a execução do programa em algumas linguagens de programação simultâneas . Eles descrevem um objeto que atua como proxy de um resultado inicialmente desconhecido, geralmente porque o cálculo de seu valor ainda não foi concluído.

O termo promessa foi proposto em 1976 por Daniel P. Friedman e David Wise, e Peter Hibbard o chamou de eventual . Um conceito de futuro um tanto semelhante foi introduzido em 1977 em um artigo de Henry Baker e Carl Hewitt .

Os termos futuro , promessa , atraso e diferido são freqüentemente usados ​​de forma intercambiável, embora algumas diferenças no uso entre futuro e promessa sejam tratadas abaixo. Especificamente, quando o uso é distinto, um futuro é uma visualização de espaço reservado somente para leitura de uma variável, enquanto uma promessa é um contêiner de atribuição único gravável que define o valor do futuro. Notavelmente, um futuro pode ser definido sem especificar qual promessa específica definirá seu valor, e diferentes promessas possíveis podem definir o valor de um determinado futuro, embora isso possa ser feito apenas uma vez para um determinado futuro. Em outros casos, um futuro e uma promessa são criados juntos e associados um ao outro: o futuro é o valor, a promessa é a função que define o valor - essencialmente o valor de retorno (futuro) de uma função assíncrona (promessa). Definir o valor de um futuro também é chamado de resolvê-lo , cumpri- lo ou vinculá- lo.

Formulários

Futuros e promessas originados na programação funcional e paradigmas relacionados (como a programação lógica ) para desacoplar um valor (um futuro) de como ele foi calculado (uma promessa), permitindo que o cálculo seja feito de forma mais flexível, notadamente paralelizando-o. Mais tarde, encontrou uso na computação distribuída , na redução da latência de viagens de ida e volta de comunicação. Mais tarde ainda, ele ganhou mais uso ao permitir a escrita de programas assíncronos no estilo direto , em vez de no estilo de passagem de continuação .

Implícito vs. explícito

O uso de futuros pode ser implícito (qualquer uso do futuro obtém automaticamente seu valor, como se fosse uma referência comum ) ou explícito (o usuário deve chamar uma função para obter o valor, como o getmétodo de java.util.concurrent.Futureem Java ). Obter o valor de um futuro explícito pode ser chamado de picada ou forçada . Futuros explícitos podem ser implementados como uma biblioteca, enquanto futuros implícitos são geralmente implementados como parte da linguagem.

O artigo original de Baker e Hewitt descreveu futuros implícitos, que são naturalmente suportados no modelo de ator de computação e em linguagens de programação puras orientadas a objetos como Smalltalk . O artigo de Friedman e Wise descreveu apenas futuros explícitos, provavelmente refletindo a dificuldade de implementar com eficiência futuros implícitos em hardware de ações. A dificuldade é que o hardware padrão não lida com futuros para tipos de dados primitivos como inteiros. Por exemplo, uma instrução add não sabe como lidar . Em linguagens puras de ator ou objeto, esse problema pode ser resolvido enviando a mensagem , que pede ao futuro para adicionar a si mesmo e retornar o resultado. Observe que a abordagem de passagem de mensagens funciona independentemente de quando termina o cálculo e que nenhuma picada / forçada é necessária. 3 + future factorial(100000)future factorial(100000)+[3]3factorial(100000)

Pipelining de promessa

O uso de futuros pode reduzir drasticamente a latência em sistemas distribuídos . Por exemplo, futuros permitem pipelining de promessa , conforme implementado nas linguagens E e Joule , que também era chamado de fluxo de chamada na linguagem Argus .

Considere uma expressão envolvendo chamadas de procedimento remoto convencionais , como: 

 t3 := ( x.a() ).c( y.b() )

que poderia ser expandido para 

 t1 := x.a();
 t2 := y.b();
 t3 := t1.c(t2);

Cada declaração precisa que uma mensagem seja enviada e uma resposta recebida antes que a próxima declaração possa prosseguir. Suponha, por exemplo, que x, y, t1, e t2estão todos localizados na mesma máquina remota. Nesse caso, duas viagens completas de ida e volta da rede para essa máquina devem ocorrer antes que a terceira instrução possa começar a ser executada. A terceira declaração causará mais uma viagem de ida e volta para a mesma máquina remota.

Usando futuros, a expressão acima pode ser escrita 

 t3 := (x <- a()) <- c(y <- b())

que poderia ser expandido para 

 t1 := x <- a();
 t2 := y <- b();
 t3 := t1 <- c(t2);

A sintaxe usada aqui é a da linguagem E, onde x <- a()significa enviar a mensagem de a()forma assíncrona para x. Todas as três variáveis ​​recebem imediatamente futuros para seus resultados, e a execução prossegue para as declarações subsequentes. Tentativas posteriores de resolver o valor de t3podem causar um atraso; no entanto, o pipelining pode reduzir o número de viagens de ida e volta necessárias. Se, como no exemplo anterior, x, y, t1, e t2estão todos localizados na mesma máquina remota, uma implementação pipeline pode calcular t3com uma ida e volta em vez de três. Como todas as três mensagens são destinadas a objetos que estão na mesma máquina remota, apenas uma solicitação precisa ser enviada e apenas uma resposta precisa ser recebida contendo o resultado. O envio t1 <- c(t2)não seria bloqueado mesmo se t1e t2estivesse em máquinas diferentes entre si, ou para xou y.

O pipelining de promessa deve ser diferenciado da passagem de mensagem assíncrona paralela. Em um sistema de apoio a passagem de mensagens paralelo, mas não pipelining, a mensagem envia x <- a()e y <- b()no exemplo acima poderia ocorrer em paralelo, mas o envio de t1 <- c(t2)teria de esperar até que ambos t1e t2tinha sido recebido, mesmo quando x, y, t1, e t2estão na mesma remoto máquina. A vantagem da latência relativa do pipelining torna-se ainda maior em situações mais complicadas que envolvem muitas mensagens.

O pipelining de promessa também não deve ser confundido com o processamento de mensagens em pipeline em sistemas de ator, onde é possível que um ator especifique e comece a executar um comportamento para a próxima mensagem antes de ter concluído o processamento da mensagem atual.

Visualizações somente leitura

Em algumas linguagens de programação, como Oz , E e AmbientTalk , é possível obter uma visão somente leitura de um futuro, que permite ler seu valor quando resolvido, mas não permite resolvê-lo:

  • Em Oz, o !!operador é usado para obter uma visualização somente leitura.
  • No E e no AmbientTalk, um futuro é representado por um par de valores chamado par promessa / resolvedor . A promessa representa a visualização somente leitura e o resolvedor é necessário para definir o valor do futuro.
  • No C ++ 11, a std::futurefornece uma visualização somente leitura. O valor é definido diretamente usando um std::promise, ou definido como o resultado de uma chamada de função usando std::packaged_taskou std::async.
  • Na API adiada do Dojo Toolkit a partir da versão 1.5, um objeto de promessa somente para o consumidor representa uma visualização somente leitura.
  • No Alice ML , os futuros fornecem uma visualização somente leitura , enquanto uma promessa contém um futuro e a capacidade de resolver o futuro
  • No .NET Framework 4.0 System.Threading.Tasks.Task<T> representa uma exibição somente leitura. A resolução do valor pode ser feita via System.Threading.Tasks.TaskCompletionSource<T>.

O suporte para visualizações somente leitura é consistente com o princípio do menor privilégio , uma vez que permite a capacidade de definir o valor como restrito aos assuntos que precisam defini-lo. Em um sistema que também suporta pipelining, o remetente de uma mensagem assíncrona (com resultado) recebe a promessa somente leitura para o resultado e o destino da mensagem recebe o resolvedor.

Futuros específicos do segmento

Algumas linguagens, como Alice ML , definem futuros que estão associados a um segmento específico que calcula o valor do futuro. Esse cálculo pode começar ansiosamente quando o futuro é criado ou preguiçosamente quando seu valor é necessário pela primeira vez. Um futuro preguiçoso é semelhante a um pensamento , no sentido de uma computação atrasada.

Alice ML também oferece suporte a futuros que podem ser resolvidos por qualquer thread e chama essas promessas . Este uso de promessa é diferente de seu uso em E conforme descrito acima . Em Alice, uma promessa não é uma visualização somente leitura e o pipelining de promessa não é compatível. Em vez disso, o pipelining acontece naturalmente para futuros, incluindo aqueles associados a promessas.

Semântica bloqueadora vs não bloqueadora

Se o valor de um futuro for acessado de forma assíncrona, por exemplo, enviando uma mensagem para ele ou esperando explicitamente por ele usando uma construção como whenem E, então não há dificuldade em atrasar até que o futuro seja resolvido antes que a mensagem possa ser recebido ou a espera é concluída. Esse é o único caso a ser considerado em sistemas puramente assíncronos, como linguagens de ator puras.

No entanto, em alguns sistemas também pode ser possível tentar acessar imediatamente ou de forma síncrona um valor futuro. Então, há uma escolha de design a ser feita:

  • o acesso pode bloquear o thread ou processo atual até que o futuro seja resolvido (possivelmente com um tempo limite). Esta é a semântica das variáveis de fluxo de dados na linguagem Oz .
  • a tentativa de acesso síncrono sempre pode sinalizar um erro, por exemplo, lançar uma exceção . Esta é a semântica das promessas remotas em E.
  • potencialmente, o acesso pode ser bem-sucedido se o futuro já estiver resolvido, mas sinalizará um erro se não estiver. Isso teria a desvantagem de introduzir o não-determinismo e o potencial para condições de corrida , e parece ser uma escolha de design incomum.

Como exemplo da primeira possibilidade, em C ++ 11 , um thread que precisa do valor de um futuro pode ser bloqueado até que esteja disponível chamando as funções de membro wait()ou get(). Você também pode especificar um tempo limite na espera usando as funções de membro wait_for()ou wait_until()para evitar o bloqueio indefinido. Se o futuro surgiu de uma chamada para, std::asyncentão uma espera de bloqueio (sem um tempo limite) pode causar a invocação síncrona da função para calcular o resultado no segmento de espera.

Construções relacionadas

Futuro é um caso particular de Evento (primitiva de sincronização) , que pode ser concluído apenas uma vez. Em geral, os eventos podem ser redefinidos para o estado inicial vazio e, portanto, concluídos quantas vezes você quiser.

Um I-var (como no idioma Id ) é um futuro com semântica de bloqueio conforme definido acima. Uma estrutura I é uma estrutura de dados que contém I-vars. Uma construção de sincronização relacionada que pode ser definida várias vezes com valores diferentes é chamada de M-var . Os M-vars suportam operações atômicas para obter ou colocar o valor atual, onde assumir o valor também define o M-var de volta ao seu estado vazio inicial .

Uma variável lógica concorrente é semelhante a um futuro, mas é atualizada por unificação , da mesma forma que as variáveis lógicas na programação lógica . Portanto, ele pode ser vinculado mais de uma vez a valores unificáveis, mas não pode ser colocado de volta em um estado vazio ou não resolvido. As variáveis ​​de fluxo de dados de Oz atuam como variáveis ​​lógicas simultâneas e também têm semântica de bloqueio, conforme mencionado acima.

Uma variável de restrição simultânea é uma generalização de variáveis ​​lógicas simultâneas para oferecer suporte à programação de lógica de restrição : a restrição pode ser reduzida várias vezes, indicando conjuntos menores de valores possíveis. Normalmente, há uma maneira de especificar uma conversão que deve ser executada sempre que a restrição for reduzida ainda mais; isso é necessário para suportar a propagação de restrições .

Relações entre a expressividade das diferentes formas de futuro

Futuros específicos de segmento ansiosos podem ser implementados diretamente em futuros não específicos de segmento, criando um segmento para calcular o valor ao mesmo tempo em que cria o futuro. Nesse caso, é desejável retornar uma visualização somente leitura para o cliente, de modo que apenas o encadeamento recém-criado seja capaz de resolver esse futuro.

Para implementar futuros específicos de thread preguiçosos implícitos (conforme fornecido por Alice ML, por exemplo) em termos de futuros não específicos de thread, é necessário um mecanismo para determinar quando o valor do futuro é necessário pela primeira vez (por exemplo, a WaitNeededconstrução em Oz). Se todos os valores forem objetos, a capacidade de implementar objetos de encaminhamento transparentes é suficiente, pois a primeira mensagem enviada ao encaminhador indica que o valor futuro é necessário.

Futuros não específicos de segmento podem ser implementados em futuros específicos de segmento, assumindo que o sistema suporte a passagem de mensagens, fazendo com que o segmento de resolução envie uma mensagem para o próprio segmento do futuro. No entanto, isso pode ser visto como uma complexidade desnecessária. Em linguagens de programação baseadas em threads, a abordagem mais expressiva parece ser fornecer uma combinação de futuros não específicos de thread, visualizações somente leitura e uma construção WaitNeeded ou suporte para encaminhamento transparente.

Estratégia de avaliação

Mais informações: Ligue para o futuro

A estratégia de avaliação de futuros, que pode ser chamada de chamada por futuro , é não determinística: o valor de um futuro será avaliado em algum momento entre quando o futuro é criado e quando seu valor é usado, mas o tempo preciso não é determinado de antemão e pode mudar de uma corrida para outra. O cálculo pode começar assim que o futuro for criado ( avaliação ansiosa ) ou apenas quando o valor for realmente necessário ( avaliação preguiçosa ), e pode ser suspenso no meio ou executado em uma execução. Uma vez que o valor de um futuro é atribuído, ele não é recalculado em acessos futuros; é como a memoização usada na chamada por necessidade .

UMA futuro preguiçoso é um futuro que deterministicamente tem semântica de avaliação preguiçosa: o cálculo do valor do futuro começa quando o valor é necessário pela primeira vez, como na chamada por necessidade. Futuros preguiçosos são úteis em linguagens cuja estratégia de avaliação não é preguiçosa por padrão. Por exemplo, noC ++ 11,esses futuros preguiçosos podem ser criados passando astd::launch::deferredpolítica de lançamento parastd::async, junto com a função para calcular o valor.

Semântica de futuros no modelo de ator

No modelo de ator, uma expressão do formulário future <Expression>é definida por como ele responde a uma Evalmensagem com o ambiente E e o cliente C da seguinte forma: A expressão futura responde à Evalmensagem enviando ao cliente C um ator F recém-criado (o proxy para o resposta de avaliar <Expression>) como um valor de retorno concomitantemente com o envio de <Expression>uma Evalmensagem com o ambiente e e cliente C . O comportamento padrão de F é o seguinte:

  • Quando F recebe uma solicitação R , ele verifica se já recebeu uma resposta (que pode ser um valor de retorno ou uma exceção lançada) de avaliação <Expression>procedendo da seguinte maneira:
    1. Se já tem uma resposta V , então
      • Se V é um valor de retorno, então ele é enviado o pedido R .
      • Se V é uma exceção, então ele é jogado para o cliente do pedido R .
    2. Se ainda não tiver uma resposta, então R é armazenada na fila de pedidos dentro da F .
  • Quando F recebe a resposta V da avaliação <Expression>, então V é armazenado em F e
    • Se V é um valor de retorno, em seguida, todas as solicitações na fila são enviados para V .
    • Se V for uma exceção, ele será enviado ao cliente para cada uma das solicitações enfileiradas.

No entanto, alguns futuros podem lidar com solicitações de maneiras especiais para fornecer maior paralelismo. Por exemplo, a expressão 1 + future factorial(n)pode criar um novo futuro que se comportará como o número 1+factorial(n). Esse truque nem sempre funciona. Por exemplo, a seguinte expressão condicional:

if m>future factorial(n) then print("bigger") else print("smaller")

suspende até que o futuro por factorial(n)responder à solicitação perguntando se mé maior do que ele.

História

As construções de futuro e / ou promessa foram implementadas pela primeira vez em linguagens de programação como MultiLisp e Act 1 . O uso de variáveis ​​lógicas para comunicação em linguagens de programação lógica concorrente foi bastante semelhante ao futuro. Eles começaram no Prolog com Freeze e IC Prolog e se tornaram um verdadeiro primitivo de simultaneidade com Linguagem Relacional, Prolog Concorrente , cláusulas de Horn guardadas (GHC), Parlog , Strand , Vulcan , Janus , Oz-Mozart , Flow Java e Alice ML . O I-var de atribuição única das linguagens de programação de fluxo de dados , originado em Id e incluído no ML simultâneo de Reppy , é muito parecido com a variável lógica simultânea.

A técnica de pipelining de promessa (usando futuros para superar a latência) foi inventada por Barbara Liskov e Liuba Shrira em 1988, e independentemente por Mark S. Miller , Dean Tribble e Rob Jellinghaus no contexto do Projeto Xanadu por volta de 1989.

O termo promessa foi cunhado por Liskov e Shrira, embora eles se referissem ao mecanismo de pipelining pelo nome de fluxo de chamada , que agora é raramente usado.

Tanto o design descrito no artigo de Liskov e Shrira, como a implementação do pipelining de promessa em Xanadu, tinham o limite de que os valores de promessa não eram de primeira classe : um argumento para, ou o valor retornado por uma chamada ou envio não poderia ser diretamente uma promessa (portanto, o exemplo de pipelining de promessa dado anteriormente, que usa uma promessa para o resultado de um envio como um argumento para outro, não seria diretamente expressável no design do fluxo de chamada ou na implementação do Xanadu). Parece que promessas e fluxos de chamadas nunca foram implementados em qualquer versão pública do Argus, a linguagem de programação usada no artigo de Liskov e Shrira. O desenvolvimento do Argus parou por volta de 1988. A implementação Xanadu do pipelining de promessa só se tornou publicamente disponível com o lançamento do código-fonte do Udanax Gold em 1999 e nunca foi explicada em nenhum documento publicado. As últimas implementações em Joule e E suportam promessas e resolvedores de primeira classe.

Várias linguagens de ator iniciais, incluindo a série Act, suportavam a passagem paralela de mensagens e o processamento de mensagens em pipeline, mas não prometiam pipelining. (Embora seja tecnicamente possível implementar o último desses recursos nos dois primeiros, não há evidências de que as linguagens da Lei o fizeram.)

Após 2000, ocorreu um grande renascimento do interesse em futuros e promessas, devido ao seu uso na capacidade de resposta de interfaces de usuário, e no desenvolvimento web , devido ao modelo de solicitação-resposta de passagem de mensagens. Diversas linguagens tradicionais agora têm suporte de linguagem para futuros e promessas, mais notavelmente popularizado por FutureTaskem Java 5 (anunciado em 2004) e as construções async / await em .NET 4.5 (anunciado em 2010, lançado em 2012) amplamente inspirado nos fluxos de trabalho assíncronos do F #, que data de 2007. Isso foi posteriormente adotado por outras linguagens, notavelmente Dart (2014), Python (2015), Hack (HHVM) e rascunhos de ECMAScript 7 (JavaScript), Scala e C ++.

Lista de implementações

Algumas linguagens de programação oferecem suporte a futuros, promessas, variáveis ​​lógicas simultâneas, variáveis ​​de fluxo de dados ou I-vars, por suporte direto a linguagem ou na biblioteca padrão.

Lista de conceitos relacionados a futuros e promessas por linguagem de programação

As linguagens que também apoiam o pipelining de promessa incluem:

Lista de implementações não padronizadas e baseadas em biblioteca de futuros

  • Para Lisp Comum :
    • Passaro preto
    • Eager Future2
    • paralelo
    • PCall
  • Para C ++:
  • Para C # e outras linguagens .NET : A biblioteca de extensões paralelas
  • Para Groovy : GPars
  • Para JavaScript :
    • Cujo.js 'when.js fornece promessas em conformidade com a especificação Promises / A + 1.1
    • O Dojo Toolkit fornece promessas e adiamentos de estilo Twisted
    • MochiKit inspirado em Twisted's Deferreds
    • O objeto adiado do jQuery é baseado no design CommonJS Promises / A.
    • AngularJS
    • node -promise
    • Q, de Kris Kowal, está em conformidade com Promises / A + 1.1
    • RSVP.js, em conformidade com Promises / A + 1.1
    • A classe de promessa da YUI está em conformidade com a especificação Promises / A + 1.0.
    • Bluebird, de Petka Antonov
    • A Biblioteca Encerramento da promessa conforma pacote com as promessas / A + especificação.
    • Consulte a lista de Promise / A + para mais implementações baseadas no design de Promise / A +.
  • Para Java :
    • JDeferred, fornece API de promessa adiada e comportamento semelhante ao objeto JQuery .Deferred
    • ParSeq fornece API de promessa de tarefa ideal para pipelining e ramificação assíncrona, mantida pelo LinkedIn
  • Para Lua :
    • O módulo cqueues [1] contém uma API Promise.
  • Para Objective-C : MAFuture, RXPromise, ObjC-CollapsingFutures, PromiseKit, objc-promessa, OAPromise,
  • Para OCaml : módulo preguiçoso implementa futuros explícitos preguiçosos
  • Para Perl : Futuro, Promessas, Reflexo, Promessa :: ES6 e Promessa :: XS
  • Para PHP : React / Promise
  • Para Python :
    • Implementação integrada
    • pythonfutures
    • Twisted's Deferreds
  • Para R :
    • futuro, implementa uma API futura extensível com futuros síncronos preguiçosos e ansiosos e (multicore ou distribuídos) assíncronos
  • Para Ruby :
    • Joia da promessa
    • joia libuv, implementa promessas
    • Gema de celulóide, implementa futuros
    • recurso futuro
  • Para ferrugem :
    • futuro-rs
  • Para Scala :
    • Biblioteca de utilitários do Twitter
  • Para Swift :
    • Estrutura assíncrona, implementa estilo C # async/ sem bloqueioawait
    • FutureKit, implementa uma versão para Apple GCD
    • FutureLib, biblioteca Swift 2 pura implementando futuros e promessas no estilo Scala com cancelamento no estilo TPL
    • Deferred, biblioteca Swift pura inspirada em OCaml's Deferred
    • BrightFutures
    • SwiftCoroutine
  • Para Tcl : tcl-promessa

Corrotinas

Futuros podem ser implementados em corrotinas ou geradores , resultando na mesma estratégia de avaliação (por exemplo, multitarefa cooperativa ou avaliação preguiçosa).

Canais

Artigo principal: Canal (programação)

Futuros podem ser facilmente implementados em canais : um futuro é um canal de um elemento, e uma promessa é um processo que envia para o canal, cumprindo o futuro. Isso permite que futuros sejam implementados em linguagens de programação simultâneas com suporte para canais, como CSP e Go . Os futuros resultantes são explícitos, pois devem ser acessados ​​por meio da leitura do canal, e não apenas da avaliação.

Veja também

Referências

links externos