3.5Fluxos

Nós ganhamos uma boa compreensão da atribuição como uma ferramenta na modelagem, assim como uma apreciação dos problemas complexos que a atribuição levanta. É hora de perguntar se poderíamos ter feito as coisas de uma maneira diferente, para evitar alguns desses problemas. Nesta seção, exploramos uma abordagem alternativa para modelar estado, baseada em estruturas de dados chamadas fluxos. Como veremos, os fluxos podem mitigar parte da complexidade de modelar estados.

Vamos recuar e revisar de onde essa complexidade vem. Na tentativa de modelar fenômenos do mundo real, tomamos algumas decisões aparentemente razoáveis: modelamos objetos do mundo real com estado local por objetos computacionais com variáveis locais. Identificamos a variação temporal no mundo real com a variação temporal no computador. Implementamos a variação temporal dos estados dos objetos do modelo no computador com atribuições às variáveis locais dos objetos do modelo.

Existe outra abordagem? Podemos evitar identificar o tempo no computador com o tempo no mundo modelado? Devemos fazer o modelo mudar com o tempo para modelar fenômenos em um mundo em mudança? Pense sobre o problema em termos de funções matemáticas. Podemos descrever o comportamento variante no tempo de uma quantidade $x$ como uma função do tempo $x(t)$. Se nos concentrarmos em $x$ instante a instante, pensamos nela como uma quantidade em mudança. No entanto, se nos concentrarmos em toda a história temporal de valores, não enfatizamos a mudança — a função em si não muda.¹⁸⁰

Se o tempo for medido em passos discretos, então podemos modelar uma função temporal como uma sequência (possivelmente infinita). Nesta seção, veremos como modelar mudanças em termos de sequências que representam as histórias temporais dos sistemas sendo modelados. Para isso, introduzimos novas estruturas de dados chamadas fluxos. De um ponto de vista abstrato, um fluxo é simplesmente uma sequência. No entanto, descobriremos que a implementação direta de fluxos como listas (como em 2.2.1) não revela totalmente o poder do processamento de fluxos. Como alternativa, introduzimos a técnica de avaliação atrasada, que nos permite representar sequências muito grandes (mesmo infinitas) como fluxos.

O processamento de fluxos nos permite modelar sistemas que têm estado sem nunca usar atribuição ou dados mutáveis. Isso tem implicações importantes, tanto teóricas quanto práticas, porque podemos construir modelos que evitam as desvantagens inerentes à introdução de atribuição. Por outro lado, o framework de fluxos levanta dificuldades próprias, e a questão de qual técnica de modelagem leva a sistemas mais modulares e mais facilmente mantidos permanece em aberto.

3.5.1Fluxos São Listas Atrasadas

Como vimos em 2.2.3, sequências podem servir como interfaces padrão para combinar módulos de programas. Formulamos abstrações poderosas para manipular sequências, como map, filter e accumulate, que capturam uma variedade de operações de uma maneira que é tanto sucinta quanto elegante.

Infelizmente, se representarmos sequências como listas, essa elegância é obtida ao preço de uma severa ineficiência em relação ao tempo e espaço necessários para nossas computações. Quando representamos manipulações em sequências como transformações de listas, nossos programas devem construir e copiar estruturas de dados (que podem ser enormes) a cada passo de um processo.

Para ver por que isso é verdade, vamos comparar dois programas para calcular a soma de todos os números primos em um intervalo. O primeiro programa é escrito em estilo iterativo padrão:¹⁸¹

(define (sum-primes a b)
  (define (iter count accum)
    (cond ((> count b) accum)
          ((prime? count)
           (iter (+ count 1)
                 (+ count accum)))
          (else (iter (+ count 1) accum))))
  (iter a 0))

O segundo programa realiza a mesma computação usando as operações de sequência de 2.2.3:

(define (sum-primes a b)
  (accumulate 
   +
   0
   (filter prime? (enumerate-interval a b))))

Na execução da computação, o primeiro programa precisa armazenar apenas a soma sendo acumulada. Em contraste, o filtro no segundo programa não pode fazer nenhum teste até que enumerate-interval tenha construído uma lista completa dos números no intervalo. O filtro gera outra lista, que por sua vez é passada para accumulate antes de ser colapsada para formar uma soma. Esse armazenamento intermediário grande não é necessário pelo primeiro programa, que podemos pensar como enumerando o intervalo incrementalmente, adicionando cada primo à soma à medida que é gerado.

A ineficiência no uso de listas torna-se dolorosamente aparente se usarmos o paradigma de sequência para calcular o segundo primo no intervalo de 10.000 a 1.000.000 avaliando a expressão:

(car (cdr 
      (filter 
       prime?
       (enumerate-interval 10000 1000000))))

Esta expressão encontra o segundo primo, mas a sobrecarga computacional é absurda. Construímos uma lista de quase um milhão de inteiros, filtramos essa lista testando cada elemento para primalidade e então ignoramos quase todo o resultado. Em um estilo de programação mais tradicional, intercalaríamos a enumeração e a filtragem, e pararíamos quando atingíssemos o segundo primo.

Fluxos são uma ideia inteligente que permite usar manipulações de sequência sem incorrer nos custos de manipular sequências como listas. Com fluxos, podemos alcançar o melhor dos dois mundos: podemos formular programas elegantemente como manipulações de sequência, enquanto atingimos a eficiência da computação incremental. A ideia básica é organizar a construção de um fluxo apenas parcialmente e passar a construção parcial para o programa que consome o fluxo. Se o consumidor tentar acessar uma parte do fluxo que ainda não foi construída, o fluxo automaticamente construirá apenas o suficiente para produzir a parte necessária, preservando assim a ilusão de que o fluxo inteiro existe. Em outras palavras, embora escrevamos programas como se estivéssemos processando sequências completas, projetamos nossa implementação de fluxo para intercalar automaticamente e transparentemente a construção do fluxo com seu uso.

Na superfície, fluxos são apenas listas com nomes diferentes para os procedimentos que as manipulam. Há um construtor, cons-stream, e dois seletores, stream-car e stream-cdr, que satisfazem as restrições:

(stream-car (cons-stream x y)) = x
(stream-cdr (cons-stream x y)) = y

Há um objeto distinguível, the-empty-stream, que não pode ser o resultado de nenhuma operação cons-stream, e que pode ser identificado com o predicado stream-null?.¹⁸² Assim, podemos criar e usar fluxos, da mesma forma que podemos criar e usar listas, para representar dados agregados dispostos em uma sequência. Em particular, podemos construir análogos de fluxo das operações de lista do Capítulo 2, como list-ref, map e for-each:¹⁸³

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream 
       (proc (stream-car s))
       (stream-map proc (stream-cdr s)))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin 
        (proc (stream-car s))
        (stream-for-each proc 
                         (stream-cdr s)))))

Stream-for-each é útil para visualizar fluxos:

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))

Para fazer a implementação do fluxo intercalar automaticamente e transparentemente a construção de um fluxo com seu uso, organizaremos para que o cdr de um fluxo seja avaliado quando for acessado pelo procedimento stream-cdr em vez de quando o fluxo for construído por cons-stream. Essa escolha de implementação é reminiscente de nossa discussão sobre números racionais em 2.1.2, onde vimos que podemos escolher implementar números racionais de modo que a redução do numerador e denominador para termos mais baixos seja realizada no momento da construção ou no momento da seleção. As duas implementações de números racionais produzem a mesma abstração de dados, mas a escolha tem um efeito na eficiência. Há uma relação semelhante entre fluxos e listas ordinárias. Como uma abstração de dados, fluxos são iguais a listas. A diferença é o momento em que os elementos são avaliados. Com listas ordinárias, tanto o car quanto o cdr são avaliados no momento da construção. Com fluxos, o cdr é avaliado no momento da seleção.

Nossa implementação de fluxos será baseada em uma forma especial chamada delay. Avaliar (delay ⟨exp⟩) não avalia a expressão ⟨exp⟩, mas retorna um objeto chamado objeto atrasado, que podemos pensar como uma “promessa” de avaliar ⟨exp⟩ em algum momento futuro. Como companheiro de delay, há um procedimento chamado force que toma um objeto atrasado como argumento e realiza a avaliação — efetivamente forçando o delay a cumprir sua promessa. Veremos abaixo como delay e force podem ser implementados, mas primeiro vamos usá-los para construir fluxos.

Cons-stream é uma forma especial definida de modo que:

(cons-stream ⟨a⟩ ⟨b⟩)

é equivalente a:

(cons ⟨a⟩ (delay ⟨b⟩))

O que isso significa é que construiremos fluxos usando pares. No entanto, em vez de colocar o valor do resto do fluxo no cdr do par, colocaremos lá uma promessa de calcular o resto se ele for solicitado. Stream-car e stream-cdr podem agora ser definidos como procedimentos:

(define (stream-car stream) 
  (car stream))

(define (stream-cdr stream) 
  (force (cdr stream)))

Stream-car seleciona o car do par; stream-cdr seleciona o cdr do par e avalia a expressão atrasada encontrada lá para obter o resto do fluxo.¹⁸⁴

A implementação do fluxo em ação

Para ver como essa implementação se comporta, vamos analisar a computação “extravagante” de primos que vimos acima, reformulada em termos de fluxos:

(stream-car 
 (stream-cdr
  (stream-filter 
   prime? (stream-enumerate-interval 
           10000 1000000))))

Veremos que isso realmente funciona de forma eficiente.

Começamos chamando stream-enumerate-interval com os argumentos 10.000 e 1.000.000. Stream-enumerate-interval é o análogo de fluxo de enumerate-interval (2.2.3):

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1)
                                  high))))

e, portanto, o resultado retornado por stream-enumerate-interval, formado pelo cons-stream, é¹⁸⁵

(cons 10000
      (delay 
        (stream-enumerate-interval 
         10001 
         1000000)))

Ou seja, stream-enumerate-interval retorna um fluxo representado como um par cujo car é 10.000 e cujo cdr é uma promessa de enumerar mais do intervalo se solicitado. Este fluxo é agora filtrado para primos, usando o análogo de fluxo do procedimento filter (2.2.3):

(define (stream-filter pred stream)
  (cond ((stream-null? stream) 
         the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream 
          (stream-car stream)
          (stream-filter 
           pred
           (stream-cdr stream))))
        (else (stream-filter 
               pred 
               (stream-cdr stream)))))

Stream-filter testa o stream-car do fluxo (o car do par, que é 10.000). Como isso não é primo, stream-filter examina o stream-cdr de seu fluxo de entrada. A chamada para stream-cdr força a avaliação do stream-enumerate-interval atrasado, que agora retorna:

(cons 10001
      (delay 
        (stream-enumerate-interval 
         10002 
         1000000)))

Stream-filter agora olha para o stream-car deste fluxo, 10.001, vê que isso também não é primo, força outro stream-cdr, e assim por diante, até que stream-enumerate-interval produza o primo 10.007, onde stream-filter, de acordo com sua definição, retorna:

(cons-stream 
 (stream-car stream)
 (stream-filter pred (stream-cdr stream)))

que neste caso é:

(cons 10007
      (delay
        (stream-filter
         prime?
         (cons 10008
               (delay
                 (stream-enumerate-interval 
                  10009 1000000))))))

Este resultado é agora passado para stream-cdr em nossa expressão original. Isso força o stream-filter atrasado, que por sua vez continua forçando o stream-enumerate-interval atrasado até encontrar o próximo primo, que é 10.009. Finalmente, o resultado passado para stream-car em nossa expressão original é:

(cons 10009
      (delay
        (stream-filter
         prime?
         (cons 10010
               (delay
                 (stream-enumerate-interval 
                  10011 1000000))))))

Stream-car retorna 10.009, e a computação está completa. Apenas tantos inteiros foram testados para primalidade quanto foram necessários para encontrar o segundo primo, e o intervalo foi enumerado apenas o suficiente para alimentar o filtro de primos.

Em geral, podemos pensar na avaliação atrasada como programação “orientada por demanda”, onde cada estágio no processo de fluxo é ativado apenas o suficiente para satisfazer o próximo estágio. O que fizemos foi desacoplar a ordem real dos eventos na computação da estrutura aparente de nossos procedimentos. Escrevemos procedimentos como se os fluxos existissem “todos de uma vez” quando, na realidade, a computação é realizada incrementalmente, como em estilos de programação tradicionais.

Implementando delay e force

Embora delay e force possam parecer operações misteriosas, sua implementação é realmente bastante direta. Delay deve empacotar uma expressão para que ela possa ser avaliada posteriormente sob demanda, e podemos realizar isso simplesmente tratando a expressão como o corpo de um procedimento. Delay pode ser uma forma especial tal que:

(delay ⟨exp⟩)

é açúcar sintático para:

(lambda () ⟨exp⟩)

Force simplesmente chama o procedimento (sem argumentos) produzido por delay, então podemos implementar force como um procedimento:

(define (force delayed-object)
  (delayed-object))

Esta implementação é suficiente para delay e force funcionarem como anunciado, mas há uma otimização importante que podemos incluir. Em muitas aplicações, acabamos forçando o mesmo objeto atrasado muitas vezes. Isso pode levar a uma ineficiência séria em programas recursivos envolvendo fluxos. (Veja Exercício 3.57.) A solução é construir objetos atrasados de modo que, na primeira vez que forem forçados, armazenem o valor que foi calculado. Forçamentos subsequentes simplesmente retornarão o valor armazenado sem repetir a computação. Em outras palavras, implementamos delay como um procedimento memoizado especializado, semelhante ao descrito em Exercício 3.27. Uma maneira de realizar isso é usar o seguinte procedimento, que toma como argumento um procedimento (sem argumentos) e retorna uma versão memoizada do procedimento. A primeira vez que o procedimento memoizado é executado, ele salva o resultado calculado. Em avaliações subsequentes, ele simplesmente retorna o resultado.

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

Delay é então definido de modo que (delay ⟨exp⟩) seja equivalente a:

(memo-proc (lambda () ⟨exp⟩))

e force é como definido anteriormente.¹⁸⁶

Exercício 3.50: Complete a seguinte definição, que generaliza stream-map para permitir procedimentos que tomam múltiplos argumentos, análogo a map em 2.2.1, Nota de rodapé 78.

(define (stream-map proc . argstreams)
  (if (⟨??⟩ (car argstreams))
      the-empty-stream
      (⟨??⟩
       (apply proc (map ⟨??⟩ argstreams))
       (apply stream-map
              (cons proc 
                    (map ⟨??⟩ 
                         argstreams)))))

Exercício 3.51: Para dar uma olhada mais de perto na avaliação atrasada, usaremos o seguinte procedimento, que simplesmente retorna seu argumento após imprimi-lo:

(define (show x)
  (display-line x)
  x)

O que o interpretador imprime em resposta à avaliação de cada expressão na seguinte sequência?¹⁸⁷

(define x 
  (stream-map 
   show 
   (stream-enumerate-interval 0 10)))

(stream-ref x 5)
(stream-ref x 7)

Exercício 3.52: Considere a sequência de expressões:

(define sum 0)

(define (accum x)
  (set! sum (+ x sum))
  sum)

(define seq 
  (stream-map 
   accum 
   (stream-enumerate-interval 1 20)))

(define y (stream-filter even? seq))

(define z 
  (stream-filter 
   (lambda (x) 
     (= (remainder x 5) 0)) seq))

(stream-ref y 7)
(display-stream z)

Qual é o valor de sum após cada uma das expressões acima ser avaliada? Qual é a resposta impressa à avaliação das expressões stream-ref e display-stream? Essas respostas difeririam se tivéssemos implementado (delay ⟨exp⟩) simplesmente como (lambda () ⟨exp⟩) sem usar a otimização fornecida por memo-proc? Explique.

3.5.2Fluxos Infinitos

Vimos como apoiar a ilusão de manipular fluxos como entidades completas, embora, na realidade, computemos apenas o suficiente do fluxo conforme necessário para acessar. Podemos explorar essa técnica para representar sequências de forma eficiente como fluxos, mesmo que as sequências sejam muito longas. O que é mais impressionante, podemos usar fluxos para representar sequências que são infinitamente longas. Por exemplo, considere a seguinte definição do fluxo de inteiros positivos:

(define (integers-starting-from n)
  (cons-stream 
   n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))

Isso faz sentido porque integers será um par cujo car é 1 e cujo cdr é uma promessa de produzir os inteiros começando com 2. Este é um fluxo infinitamente longo, mas em qualquer momento dado podemos examinar apenas uma porção finita dele. Assim, nossos programas nunca saberão que o fluxo infinito inteiro não está lá.

Usando integers podemos definir outros fluxos infinitos, como o fluxo de inteiros que não são divisíveis por 7:

(define (divisible? x y) (= (remainder x y) 0))
(define no-sevens
  (stream-filter (lambda (x) 
                   (not (divisible? x 7)))
                 integers))

Então podemos encontrar inteiros não divisíveis por 7 simplesmente acessando elementos deste fluxo:

(stream-ref no-sevens 100)
117

Em analogia com integers, podemos definir o fluxo infinito de números de Fibonacci:

(define (fibgen a b)
  (cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))

Fibs é um par cujo car é 0 e cujo cdr é uma promessa de avaliar (fibgen 1 1). Quando avaliamos esse (fibgen 1 1) atrasado, ele produzirá um par cujo car é 1 e cujo cdr é uma promessa de avaliar (fibgen 1 2), e assim por diante.

Para uma visão de um fluxo infinito mais emocionante, podemos generalizar o exemplo no-sevens para construir o fluxo infinito de números primos, usando um método conhecido como crivo de Eratóstenes.¹⁸⁸ Começamos com os inteiros começando com 2, que é o primeiro primo. Para obter o resto dos primos, começamos filtrando os múltiplos de 2 do resto dos inteiros. Isso deixa um fluxo começando com 3, que é o próximo primo. Agora filtramos os múltiplos de 3 do resto deste fluxo. Isso deixa um fluxo começando com 5, que é o próximo primo, e assim por diante. Em outras palavras, construímos os primos por um processo de peneiração, descrito da seguinte forma: Para peneirar um fluxo S, forme um fluxo cujo primeiro elemento é o primeiro elemento de S e o resto do qual é obtido filtrando todos os múltiplos do primeiro elemento de S do resto de S e peneirando o resultado. Este processo é prontamente descrito em termos de operações de fluxo:

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? 
                   x (stream-car stream))))
           (stream-cdr stream)))))

(define primes 
  (sieve (integers-starting-from 2)))

Agora, para encontrar um primo específico, precisamos apenas pedir por ele:

(stream-ref primes 50)
233

É interessante contemplar o sistema de processamento de sinais configurado por sieve, mostrado no “diagrama de Henderson” em Figura 3.31.¹⁸⁹ O fluxo de entrada alimenta um “desconstrutor” que separa o primeiro elemento do fluxo do resto do fluxo. O primeiro elemento é usado para construir um filtro de divisibilidade, através do qual o resto é passado, e a saída do filtro é alimentada para outra caixa de peneira. Então, o primeiro elemento original é consado na saída da peneira interna para formar o fluxo de saída. Assim, não apenas o fluxo é infinito, mas o processador de sinal também é infinito, porque a peneira contém uma peneira dentro dela.

Definindo fluxos implicitamente

Os fluxos integers e fibs acima foram definidos especificando procedimentos “geradores” que explicitamente computam os elementos do fluxo um por um. Uma maneira alternativa de especificar fluxos é aproveitar a avaliação atrasada para definir fluxos implicitamente. Por exemplo, a seguinte expressão define o fluxo ones como um fluxo infinito de uns:

(define ones (cons-stream 1 ones))

Isso funciona de forma semelhante à definição de um procedimento recursivo: ones é um par cujo car é 1 e cujo cdr é uma promessa de avaliar ones. Avaliar o cdr nos dá novamente um 1 e uma promessa de avaliar ones, e assim por diante.

Podemos fazer coisas mais interessantes manipulando fluxos com operações como add-streams, que produz a soma elemento a elemento de dois fluxos dados:¹⁹⁰

(define (add-streams s1 s2) 
  (stream-map + s1 s2))

Agora podemos definir os inteiros da seguinte forma:

(define integers 
  (cons-stream 1 (add-streams ones integers)))

Isso define integers como um fluxo cujo primeiro elemento é 1 e o resto do qual é a soma de ones e integers. Assim, o segundo elemento de integers é 1 mais o primeiro elemento de integers, ou 2; o terceiro elemento de integers é 1 mais o segundo elemento de integers, ou 3; e assim por diante. Essa definição funciona porque, em qualquer ponto, o suficiente do fluxo integers foi gerado para que possamos alimentá-lo de volta na definição para produzir o próximo inteiro.

Podemos definir os números de Fibonacci no mesmo estilo:

(define fibs 
  (cons-stream 
   0 (cons-stream
      1 (add-streams 
         (stream-cdr fibs) fibs))))

Esta definição diz que fibs é um fluxo começando com 0 e 1, tal que o resto do fluxo pode ser gerado adicionando fibs a si mesmo deslocado por um lugar:

    1 1 2 3 5  8 13 21 … = (stream-cdr fibs)
    0 1 1 2 3  5  8 13 … = fibs
0 1 1 2 3 5 8 13 21 34 … = fibs

Scale-stream é outro procedimento útil na formulação de tais definições de fluxo. Isso multiplica cada item em um fluxo por uma constante dada:

(define (scale-stream stream factor)
  (stream-map
   (lambda (x) (* x factor))
   stream))

Por exemplo,

(define double 
  (cons-stream 1 (scale-stream double 2)))

produz o fluxo de potências de 2: 1, 2, 4, 8, 16, 32, ….

Uma definição alternativa do fluxo de primos pode ser dada começando com os inteiros e filtrando-os testando para primalidade. Precisaremos do primeiro primo, 2, para começar:

(define primes
  (cons-stream
   2 (stream-filter 
      prime? (integers-starting-from 3))))

Esta definição não é tão direta quanto parece, porque testaremos se um número $n$ é primo verificando se $n$ é divisível por um primo (não por qualquer inteiro) menor ou igual a $\sqrt{n}$:

(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) true)
          ((divisible? n (stream-car ps)) false)
          (else (iter (stream-cdr ps)))))
  (iter primes))

Esta é uma definição recursiva, já que primes é definido em termos do predicado prime?, que por sua vez usa o fluxo primes. A razão pela qual este procedimento funciona é que, em qualquer ponto, o suficiente do fluxo primes foi gerado para testar a primalidade dos números que precisamos verificar a seguir. Ou seja, para cada $n$ que testamos para primalidade, ou $n$ não é primo (nesse caso, há um primo já gerado que o divide) ou $n$ é primo (nesse caso, há um primo já gerado — ou seja, um primo menor que $n$ — que é maior que $\sqrt{n}$).¹⁹¹

Exercício 3.53: Sem executar o programa, descreva os elementos do fluxo definido por:

(define s (cons-stream 1 (add-streams s s)))

Exercício 3.54: Defina um procedimento mul-streams, análogo a add-streams, que produz o produto elemento a elemento de seus dois fluxos de entrada. Use isso junto com o fluxo de integers para completar a seguinte definição do fluxo cujo $n^{\text{th}}$ elemento (contando a partir de 0) é $n+1$ fatorial:

(define factorials 
  (cons-stream 1 (mul-streams ⟨??⟩ ⟨??⟩)))

Exercício 3.55: Defina um procedimento partial-sums que toma como argumento um fluxo $S$ e retorna o fluxo cujos elementos são $S_0$, $S_0+S_1$, $S_0+S_1+S_2,\dots <!--\; \dots \; -->$. Por exemplo, (partial-sums integers) deve ser o fluxo 1, 3, 6, 10, 15, ….

Exercício 3.56: Um famoso problema, levantado pela primeira vez por R. Hamming, é enumerar, em ordem crescente sem repetições, todos os inteiros positivos que não têm fatores primos além de 2, 3 ou 5. Uma maneira óbvia de fazer isso é simplesmente testar cada inteiro para ver se ele tem algum fator além de 2, 3 e 5. Mas isso é muito ineficiente, pois, à medida que os inteiros ficam maiores, menos e menos deles se encaixam no requisito. Como alternativa, vamos chamar o fluxo necessário de números S e observar os seguintes fatos sobre ele.

• S começa com 1.
• Os elementos de (scale-stream S 2) também são elementos de S.
• O mesmo é verdade para (scale-stream S 3) e (scale-stream S 5).
• Esses são todos os elementos de S.

Agora, tudo o que temos que fazer é combinar elementos dessas fontes. Para isso, definimos um procedimento merge que combina dois fluxos ordenados em um fluxo de resultado ordenado, eliminando repetições:

(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream 
                   s1car 
                   (merge (stream-cdr s1) 
                          s2)))
                 ((> s1car s2car)
                  (cons-stream 
                   s2car 
                   (merge s1 
                          (stream-cdr s2))))
                 (else
                  (cons-stream 
                   s1car
                   (merge 
                    (stream-cdr s1)
                    (stream-cdr s2)))))))))

Então, o fluxo necessário pode ser construído com merge, da seguinte forma:

(define S (cons-stream 1 (merge ⟨??⟩ ⟨??⟩)))

Preencha as expressões ausentes nos lugares marcados ⟨??⟩ acima.

Exercício 3.57: Quantas adições são realizadas quando calculamos o $n^{\text{th}}$ número de Fibonacci usando a definição de fibs baseada no procedimento add-streams? Mostre que o número de adições seria exponencialmente maior se tivéssemos implementado (delay ⟨exp⟩) simplesmente como (lambda () ⟨exp⟩), sem usar a otimização fornecida pelo procedimento memo-proc descrito em 3.5.1.¹⁹²

Exercício 3.58: Dê uma interpretação do fluxo computado pelo seguinte procedimento:

(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) 
           den 
           radix)))

(Quotient é um primitivo que retorna o quociente inteiro de dois inteiros.) Quais são os elementos sucessivos produzidos por (expand 1 7 10)? O que é produzido por (expand 3 8 10)?

Exercício 3.59: Em 2.5.3 vimos como implementar um sistema de aritmética de polinômios representando polinômios como listas de termos. De maneira similar, podemos trabalhar com séries de potências, como $$\begin{array}{rcl}{e}^x& =& 1+x+\frac{1}{2}{x}^2+\frac{1}{3\cdot <!--\; \cdot \; -->2}{x}^3+\frac{1}{4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->2}{x}^4+\dots <!--\; \dots \; -->,\\ \cos <!--\; \; -->x& =& 1-<!--\; -\; -->\frac{1}{2}{x}^2+\frac{1}{4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->2}{x}^4-<!--\; -\; -->\dots <!--\; \dots \; -->,\\ \sin <!--\; \; -->x& =& x-<!--\; -\; -->\frac{1}{3\cdot <!--\; \cdot \; -->2}{x}^3+\frac{1}{5\cdot <!--\; \cdot \; -->4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->2}{x}^5-<!--\; -\; -->\dots <!--\; \dots \; -->\end{array}$$ representadas como fluxos infinitos. Representaremos a série $a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots <!--\; \dots \; -->$ como o fluxo cujos elementos são os coeficientes $a_0$, $a_1$, $a_2$, $a_3$, ….

1. A integral da série $a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots <!--\; \dots \; -->$ é a série $$c+a_{0}x+\frac{1}{2}{a}_1{x}^2+\frac{1}{3}{a}_2{x}^3+\frac{1}{4}{a}_3{x}^4+\dots <!--\; \dots \; -->,$$ onde $c$ é qualquer constante. Defina um procedimento integrate-series que recebe como entrada um fluxo $a_0$, $a_1$, $a_2$, … representando uma série de potências e retorna o fluxo $a_0$, $\frac{1}{2}{a}_1$, $\frac{1}{3}{a}_2$, … de coeficientes dos termos não constantes da integral da série. (Como o resultado não tem termo constante, ele não representa uma série de potências; quando usamos integrate-series, vamos cons na constante apropriada.)
2. A função $x\mapsto <!--\; \mapsto \; -->e^x$ é sua própria derivada. Isso implica que $e^x$ e a integral de $e^x$ são a mesma série, exceto pelo termo constante, que é $e^0=1$. Assim, podemos gerar a série para $e^x$ como

   (define exp-series
               (cons-stream 
                1 (integrate-series exp-series)))

   Mostre como gerar as séries para seno e cosseno, começando dos fatos que a derivada do seno é o cosseno e a derivada do cosseno é o negativo do seno:

   (define cosine-series 
               (cons-stream 1 ⟨??⟩))
             
             (define sine-series
               (cons-stream 0 ⟨??⟩))

Exercício 3.60: Com séries de potências representadas como fluxos de coeficientes como em Exercício 3.59, adicionar séries é implementado por add-streams. Complete a definição do seguinte procedimento para multiplicar séries:

(define (mul-series s1 s2)
            (cons-stream ⟨??⟩ (add-streams ⟨??⟩ ⟨??⟩)))

Você pode testar seu procedimento verificando que ${\sin }^2<!--\; \; -->x+{\cos }^2<!--\; \; -->x=1,$ usando as séries de Exercício 3.59.

Exercício 3.61: Seja $S$ uma série de potências (Exercício 3.59) cujo termo constante é 1. Suponha que queremos encontrar a série de potências $1/S$, isto é, a série $X$ tal que $SX=1$. Escreva $S=1+S_R$ onde $S_R$ é a parte de $S$ após o termo constante. Então podemos resolver para $X$ da seguinte forma: $$\begin{array}{rcl}S\cdot <!--\; \cdot \; -->X& =& 1,\\ (1+S_R)\cdot <!--\; \cdot \; -->X& =& 1,\\ X+S_R\cdot <!--\; \cdot \; -->X& =& 1,\\ X& =& 1-<!--\; -\; -->S_R\cdot <!--\; \cdot \; -->X.\end{array}$$ Em outras palavras, $X$ é a série de potências cujo termo constante é 1 e cujos termos de ordem superior são dados pelo negativo de $S_R$ vezes $X$. Use essa ideia para escrever um procedimento invert-unit-series que calcula $1/S$ para uma série de potências $S$ com termo constante 1. Você precisará usar mul-series de Exercício 3.60.

Exercício 3.62: Use os resultados de Exercício 3.60 e Exercício 3.61 para definir um procedimento div-series que divide duas séries de potências. Div-series deve funcionar para quaisquer duas séries, desde que a série do denominador comece com um termo constante diferente de zero. (Se o denominador tiver um termo constante zero, então div-series deve sinalizar um erro.) Mostre como usar div-series junto com o resultado de Exercício 3.59 para gerar a série de potências para a tangente.

3.5.3Explorando o Paradigma de Fluxos

Fluxos com avaliação atrasada podem ser uma ferramenta poderosa de modelagem, fornecendo muitos dos benefícios do estado local e da atribuição. Além disso, eles evitam alguns dos emaranhados teóricos que acompanham a introdução da atribuição em uma linguagem de programação.

A abordagem de fluxos pode ser esclarecedora porque nos permite construir sistemas com diferentes limites de módulos do que sistemas organizados em torno da atribuição a variáveis de estado. Por exemplo, podemos pensar em uma série temporal inteira (ou sinal) como um foco de interesse, em vez dos valores das variáveis de estado em momentos individuais. Isso torna conveniente combinar e comparar componentes de estado de diferentes momentos.

Formulando iterações como processos de fluxo

Na seção 1.2.1, introduzimos processos iterativos, que prosseguem atualizando variáveis de estado. Sabemos agora que podemos representar o estado como um fluxo "atemporal" de valores, em vez de como um conjunto de variáveis a serem atualizadas. Vamos adotar essa perspectiva ao revisitar o procedimento de raiz quadrada de 1.1.7. Lembre-se de que a ideia é gerar uma sequência de melhores e melhores palpites para a raiz quadrada de $x$ aplicando repetidamente o procedimento que melhora os palpites:

(define (sqrt-improve guess x)
            (average guess (/ x guess)))

Em nosso procedimento sqrt original, fizemos esses palpites serem os valores sucessivos de uma variável de estado. Em vez disso, podemos gerar o fluxo infinito de palpites, começando com um palpite inicial de 1:¹⁹³

(define (sqrt-stream x)
            (define guesses
              (cons-stream 
               1.0 (stream-map
                    (lambda (guess)
                      (sqrt-improve guess x))
                    guesses)))
            guesses)
          
          (display-stream (sqrt-stream 2))
          1.
          1.5
          1.4166666666666665
          1.4142156862745097
          1.4142135623746899
          …
          

Podemos gerar mais e mais termos do fluxo para obter palpites cada vez melhores. Se quisermos, podemos escrever um procedimento que continua gerando termos até que a resposta seja boa o suficiente. (Veja Exercício 3.64.)

Outra iteração que podemos tratar da mesma forma é gerar uma aproximação para $\mathrm{\pi <!--\; \pi \; -->}$, baseada na série alternada que vimos em 1.3.1: $$\frac{\mathrm{\pi <!--\; \pi \; -->}}{4}=1-<!--\; -\; -->\frac{1}{3}+\frac{1}{5}-<!--\; -\; -->\frac{1}{7}+\dots <!--\; \dots \; -->.$$ Primeiro geramos o fluxo de termos da série (os recíprocos dos inteiros ímpares, com sinais alternados). Então pegamos o fluxo de somas de mais e mais termos (usando o procedimento partial-sums de Exercício 3.55) e escalamos o resultado por 4:

(define (pi-summands n)
            (cons-stream 
             (/ 1.0 n)
             (stream-map - (pi-summands (+ n 2)))))
          
          (define pi-stream
            (scale-stream 
             (partial-sums (pi-summands 1)) 4))
          
          (display-stream pi-stream)
          4.
          2.666666666666667
          3.466666666666667
          2.8952380952380956
          3.3396825396825403
          2.9760461760461765
          3.2837384837384844
          3.017071817071818
          …
          

Isso nos dá um fluxo de aproximações cada vez melhores para $\mathrm{\pi <!--\; \pi \; -->}$, embora as aproximações convirjam de forma bastante lenta. Oito termos da sequência limitam o valor de $\mathrm{\pi <!--\; \pi \; -->}$ entre 3.284 e 3.017.

Até agora, nosso uso da abordagem de fluxo de estados não é muito diferente de atualizar variáveis de estado. Mas os fluxos nos dão a oportunidade de fazer alguns truques interessantes. Por exemplo, podemos transformar um fluxo com um acelerador de sequência que converte uma sequência de aproximações em uma nova sequência que converge para o mesmo valor que a original, só que mais rápido.

Um desses aceleradores, devido ao matemático suíço do século XVIII Leonhard Euler, funciona bem com sequências que são somas parciais de séries alternadas (séries de termos com sinais alternados). Na técnica de Euler, se $S_n$ é o $n^{\text{th}}$ termo da sequência de soma original, então a sequência acelerada tem termos $$S_{n+1}-<!--\; -\; -->\frac{(S_{n+1}-<!--\; -\; -->S_n{)}^2}{S_{n-<!--\; -\; -->1}-<!--\; -\; -->2S_n+S_{n+1}}.$$ Assim, se a sequência original é representada como um fluxo de valores, a sequência transformada é dada por

(define (euler-transform s)
            (let ((s0 (stream-ref s 0))     ; Sₙ₋₁
                  (s1 (stream-ref s 1))     ; Sₙ
                  (s2 (stream-ref s 2)))    ; Sₙ₊₁
              (cons-stream 
               (- s2 (/ (square (- s2 s1))
                        (+ s0 (* -2 s1) s2)))
               (euler-transform (stream-cdr s)))))

Podemos demonstrar a aceleração de Euler com nossa sequência de aproximações para $\mathrm{\pi <!--\; \pi \; -->}$:

(display-stream 
           (euler-transform pi-stream))
          3.166666666666667
          3.1333333333333337
          3.1452380952380956
          3.13968253968254
          3.1427128427128435
          3.1408813408813416
          3.142071817071818
          3.1412548236077655
          …
          

Podemos até acelerar a sequência acelerada, e recursivamente acelerar essa, e assim por diante. Ou seja, criamos um fluxo de fluxos (uma estrutura que chamaremos de tableau) em que cada fluxo é a transformação do precedente:

(define (make-tableau transform s)
            (cons-stream 
             s
             (make-tableau
              transform
              (transform s))))

O tableau tem a forma $$\begin{array}{cccccc}{s}_{00}& s_{01}& s_{02}& s_{03}& s_{04}& \dots <!--\; \dots \; -->\\ & s_{10}& s_{11}& s_{12}& s_{13}& \dots <!--\; \dots \; -->\\ & & s_{20}& s_{21}& s_{22}& \dots <!--\; \dots \; -->\\ & & & \dots <!--\; \dots \; -->& & \end{array}$$ Finalmente, formamos uma sequência tomando o primeiro termo em cada linha do tableau:

(define (accelerated-sequence transform s)
            (stream-map stream-car
                        (make-tableau transform s)))

Podemos demonstrar esse tipo de "super-aceleração" da sequência de $\mathrm{\pi <!--\; \pi \; -->}$:

(display-stream 
           (accelerated-sequence euler-transform
                                 pi-stream))
          4.
          3.166666666666667
          3.142105263157895
          3.141599357319005
          3.1415927140337785
          3.1415926539752927
          3.1415926535911765
          3.141592653589778
          …
          

O resultado é impressionante. Tomando oito termos da sequência, obtemos o valor correto de $\mathrm{\pi <!--\; \pi \; -->}$ com 14 casas decimais. Se tivéssemos usado apenas a sequência original de $\mathrm{\pi <!--\; \pi \; -->}$, precisaríamos calcular da ordem de ${10}^{13}$ termos (ou seja, expandindo a série o suficiente para que os termos individuais sejam menores que ${10}^{-<!--\; -\; -->13}$) para obter essa precisão!

Poderíamos ter implementado essas técnicas de aceleração sem usar fluxos. Mas a formulação de fluxos é particularmente elegante e conveniente porque a sequência inteira de estados está disponível para nós como uma estrutura de dados que pode ser manipulada com um conjunto uniforme de operações.

Exercício 3.63: Louis Reasoner pergunta por que o procedimento sqrt-stream não foi escrito da seguinte forma mais direta, sem a variável local guesses:

(define (sqrt-stream x)
            (cons-stream 
             1.0
             (stream-map (lambda (guess)
                           (sqrt-improve guess x))
                         (sqrt-stream x))))

Alyssa P. Hacker responde que esta versão do procedimento é consideravelmente menos eficiente porque realiza computação redundante. Explique a resposta de Alyssa. As duas versões ainda difeririam em eficiência se nossa implementação de delay usasse apenas (lambda () ⟨exp⟩) sem usar a otimização fornecida por memo-proc (3.5.1)?

Exercício 3.64: Escreva um procedimento stream-limit que recebe como argumentos um fluxo e um número (a tolerância). Ele deve examinar o fluxo até encontrar dois elementos sucessivos que diferem em valor absoluto por menos que a tolerância e retornar o segundo dos dois elementos. Usando isso, poderíamos calcular raízes quadradas até uma dada tolerância por

(define (sqrt x tolerance)
            (stream-limit (sqrt-stream x) tolerance))

Exercício 3.65: Use a série $$\ln <!--\; \; -->2=1-<!--\; -\; -->\frac{1}{2}+\frac{1}{3}-<!--\; -\; -->\frac{1}{4}+\dots <!--\; \dots \; -->$$ para calcular três sequências de aproximações para o logaritmo natural de 2, da mesma forma que fizemos acima para $\mathrm{\pi <!--\; \pi \; -->}$. Quão rapidamente essas sequências convergem?

Fluxos infinitos de pares

Em 2.2.3, vimos como o paradigma de sequência lida com loops aninhados tradicionais como processos definidos em sequências de pares. Se generalizarmos essa técnica para fluxos infinitos, então podemos escrever programas que não são facilmente representados como loops, porque o "looping" deve variar sobre um conjunto infinito.

Por exemplo, suponha que queremos generalizar o procedimento prime-sum-pairs de 2.2.3 para produzir o fluxo de pares de todos os inteiros $(i,j)$ com $i\le <!--\; \le \; -->j$ tal que $i+j$ é primo. Se int-pairs é a sequência de todos os pares de inteiros $(i,j)$ com $i\le <!--\; \le \; -->j$, então o fluxo necessário é simplesmente¹⁹⁴

(stream-filter 
           (lambda (pair)
             (prime? (+ (car pair) (cadr pair))))
           int-pairs)

Nosso problema, então, é produzir o fluxo int-pairs. Mais geralmente, suponha que temos dois fluxos $S=(S_i)$ e $T=(T_j)$, e imagine o array retangular infinito $$\begin{array}{cccc}(S_0,T_0)& (S_0,T_1)& (S_0,T_2)& \dots <!--\; \dots \; -->\\ (S_1,T_0)& (S_1,T_1)& (S_1,T_2)& \dots <!--\; \dots \; -->\\ (S_2,T_0)& (S_2,T_1)& (S_2,T_2)& \dots <!--\; \dots \; -->\\ \dots <!--\; \dots \; -->& & & \end{array}$$ Queremos gerar um fluxo que contenha todos os pares no array que estão na diagonal ou acima dela, ou seja, os pares $$\begin{array}{cccc}(S_0,T_0)& (S_0,T_1)& (S_0,T_2)& \dots <!--\; \dots \; -->\\ & (S_1,T_1)& (S_1,T_2)& \dots <!--\; \dots \; -->\\ & & (S_2,T_2)& \dots <!--\; \dots \; -->\\ & & & \dots <!--\; \dots \; -->\end{array}$$ (Se tomarmos ambos $S$ e $T$ como o fluxo de inteiros, então isso será nosso fluxo desejado int-pairs.)

Chame o fluxo geral de pares (pairs S T), e considere que ele é composto de três partes: o par $(S_0,T_0)$, o resto dos pares na primeira linha, e os pares restantes:¹⁹⁵ $$\begin{array}{cccc}(S_0,T_0)& (S_0,T_1)& (S_0,T_2)& \dots <!--\; \dots \; -->\\ & (S_1,T_1)& (S_1,T_2)& \dots <!--\; \dots \; -->\\ & & (S_2,T_2)& \dots <!--\; \dots \; -->\\ & & & \dots <!--\; \dots \; -->\end{array}$$ Observe que a terceira peça nesta decomposição (pares que não estão na primeira linha) é (recursivamente) os pares formados a partir de (stream-cdr S) e (stream-cdr T). Além disso, note que a segunda peça (o resto da primeira linha) é

(stream-map (lambda (x) 
                        (list (stream-car s) x))
                      (stream-cdr t))

Assim, podemos formar nosso fluxo de pares da seguinte forma:

(define (pairs s t)
            (cons-stream
             (list (stream-car s) (stream-car t))
             (⟨combine-in-some-way⟩
              (stream-map (lambda (x) 
                            (list (stream-car s) x))
                          (stream-cdr t))
              (pairs (stream-cdr s)
                     (stream-cdr t)))))

Para completar o procedimento, devemos escolher alguma forma de combinar os dois fluxos internos. Uma ideia é usar o análogo de fluxo do procedimento append de 2.2.1:

(define (stream-append s1 s2)
            (if (stream-null? s1)
                s2
                (cons-stream 
                 (stream-car s1)
                 (stream-append (stream-cdr s1) s2))))

Isso é inadequado para fluxos infinitos, no entanto, porque ele pega todos os elementos do primeiro fluxo antes de incorporar o segundo fluxo. Em particular, se tentarmos gerar todos os pares de inteiros positivos usando

(pairs integers integers)

nosso fluxo de resultados primeiro tentará percorrer todos os pares com o primeiro inteiro igual a 1 e, portanto, nunca produzirá pares com qualquer outro valor do primeiro inteiro.

Para lidar com fluxos infinitos, precisamos elaborar uma ordem de combinação que garanta que cada elemento será eventualmente alcançado se deixarmos nosso programa rodar o tempo suficiente. Uma maneira elegante de realizar isso é com o seguinte procedimento interleave:¹⁹⁶

(define (interleave s1 s2)
            (if (stream-null? s1)
                s2
                (cons-stream 
                 (stream-car s1)
                 (interleave s2 (stream-cdr s1)))))

Como interleave pega elementos alternadamente dos dois fluxos, todo elemento do segundo fluxo eventualmente encontrará seu caminho no fluxo intercalado, mesmo que o primeiro fluxo seja infinito.

Podemos, portanto, gerar o fluxo necessário de pares como

(define (pairs s t)
            (cons-stream
             (list (stream-car s) (stream-car t))
             (interleave
              (stream-map (lambda (x) 
                            (list (stream-car s) x))
                          (stream-cdr t))
              (pairs (stream-cdr s) (stream-cdr t)))))

Exercício 3.66: Examine o fluxo (pairs integers integers). Você pode fazer algum comentário geral sobre a ordem em que os pares são colocados no fluxo? Por exemplo, aproximadamente quantos pares precedem o par (1, 100)? o par (99, 100)? o par (100, 100)? (Se você puder fazer afirmações matemáticas precisas aqui, tanto melhor. Mas sinta-se à vontade para dar respostas mais qualitativas se você se sentir sobrecarregado.)

Exercício 3.67: Modifique o procedimento pairs para que (pairs integers integers) produza o fluxo de todos os pares de inteiros $(i,j)$ (sem a condição $i\le <!--\; \le \; -->j$). Dica: Você precisará misturar um fluxo adicional.

Exercício 3.68: Louis Reasoner pensa que construir um fluxo de pares a partir de três partes é desnecessariamente complicado. Em vez de separar o par $(S_0,T_0)$ do resto dos pares na primeira linha, ele propõe trabalhar com a primeira linha inteira, da seguinte forma:

(define (pairs s t)
            (interleave
             (stream-map
              (lambda (x) 
                (list (stream-car s) x))
              t)
             (pairs (stream-cdr s)
                    (stream-cdr t))))

Isso funciona? Considere o que acontece se avaliamos (pairs integers integers) usando a definição de pairs de Louis.

Exercício 3.69: Escreva um procedimento triples que recebe três fluxos infinitos, $S$, $T$, e $U$, e produz o fluxo de triplas $(S_i,T_j,U_k)$ tal que $i\le <!--\; \le \; -->j\le <!--\; \le \; -->k$. Use triples para gerar o fluxo de todas as triplas pitagóricas de inteiros positivos, ou seja, as triplas $(i,j,k)$ tais que $i\le <!--\; \le \; -->j$ e $i^2+j^2=k^2$.

Exercício 3.70: Seria bom poder gerar fluxos em que os pares aparecem em alguma ordem útil, em vez de na ordem que resulta de um processo de intercalação ad hoc. Podemos usar uma técnica semelhante ao procedimento merge do Exercício 3.56, se definirmos uma maneira de dizer que um par de inteiros é “menor que” outro. Uma maneira de fazer isso é definir uma “função de ponderação” $W(i,j)$ e estipular que $(i_1,j_1)$ é menor que $(i_2,j_2)$ se $W(i_1,j_1)<W(i_2,j_2)$. Escreva um procedimento merge-weighted que é semelhante a merge, exceto que merge-weighted recebe um argumento adicional weight, que é um procedimento que calcula o peso de um par, e é usado para determinar a ordem em que os elementos devem aparecer no fluxo resultante.¹⁹⁷ Usando isso, generalize pairs para um procedimento weighted-pairs que recebe dois fluxos, junto com um procedimento que calcula uma função de ponderação, e gera o fluxo de pares, ordenados de acordo com o peso. Use seu procedimento para gerar

1. o fluxo de todos os pares de inteiros positivos $(i,j)$ com $i\le <!--\; \le \; -->j$ ordenados de acordo com a soma $i+j$,
2. o fluxo de todos os pares de inteiros positivos $(i,j)$ com $i\le <!--\; \le \; -->j$, onde nem $i$ nem $j$ é divisível por 2, 3 ou 5, e os pares são ordenados de acordo com a soma $2i+3j+5ij$.

Exercício 3.71: Números que podem ser expressos como a soma de dois cubos de mais de uma maneira são às vezes chamados de números de Ramanujan, em homenagem ao matemático Srinivasa Ramanujan.¹⁹⁸ Fluxos ordenados de pares fornecem uma solução elegante para o problema de calcular esses números. Para encontrar um número que pode ser escrito como a soma de dois cubos de duas maneiras diferentes, precisamos apenas gerar o fluxo de pares de inteiros $(i,j)$ ponderados de acordo com a soma $i^3+j^3$ (veja Exercício 3.70), então procure no fluxo por dois pares consecutivos com o mesmo peso. Escreva um procedimento para gerar os números de Ramanujan. O primeiro desses números é 1,729. Quais são os próximos cinco?

Exercício 3.72: De maneira semelhante ao Exercício 3.71, gere um fluxo de todos os números que podem ser escritos como a soma de dois quadrados de três maneiras diferentes (mostrando como eles podem ser escritos dessa forma).

Fluxos como sinais

Começamos nossa discussão sobre fluxos descrevendo-os como análogos computacionais dos “sinais” em sistemas de processamento de sinais. Na verdade, podemos usar fluxos para modelar sistemas de processamento de sinais de maneira muito direta, representando os valores de um sinal em intervalos de tempo sucessivos como elementos consecutivos de um fluxo. Por exemplo, podemos implementar um integrador ou somador que, para um fluxo de entrada $x=(x_i)$, um valor inicial $C$, e um pequeno incremento $dt$, acumula a soma $$S_i=C+\underset{j=1}{\overset{i}{\sum <!--\; \sum \; -->}}{x}_{j}dt$$ e retorna o fluxo de valores $S=(S_i)$. O seguinte procedimento integral é reminiscente da definição de “estilo implícito” do fluxo de inteiros (3.5.2):

(define (integral integrand initial-value dt)
              (define int
                (cons-stream 
                 initial-value
                 (add-streams (scale-stream integrand dt)
                              int)))
              int)

Figura 3.32 é uma imagem de um sistema de processamento de sinais que corresponde ao procedimento integral. O fluxo de entrada é escalado por $dt$ e passado por um somador, cuja saída é passada de volta pelo mesmo somador. A autorreferência na definição de int é refletida na figura pelo loop de feedback que conecta a saída do somador a uma das entradas.

Exercício 3.73: Podemos modelar circuitos elétricos usando fluxos para representar os valores de correntes ou tensões em uma sequência de tempos. Por exemplo, suponha que temos um circuito RC consistindo de um resistor de resistência $R$ e um capacitor de capacitância $C$ em série. A resposta de tensão $v$ do circuito a uma corrente injetada $i$ é determinada pela fórmula na Figura 3.33, cuja estrutura é mostrada pelo diagrama de fluxo de sinais.

Escreva um procedimento RC que modela esse circuito. RC deve receber como entradas os valores de $R$, $C$, e $dt$ e deve retornar um procedimento que recebe como entradas um fluxo representando a corrente $i$ e um valor inicial para a tensão do capacitor $v_0$ e produz como saída o fluxo de tensões $v$. Por exemplo, você deve ser capaz de usar RC para modelar um circuito RC com $R$ = 5 ohms, $C$ = 1 farad, e um passo de tempo de 0,5 segundos por avaliação de (define RC1 (RC 5 1 0.5)). Isso define RC1 como um procedimento que recebe um fluxo representando a sequência temporal de correntes e uma tensão inicial do capacitor e produz o fluxo de saída de tensões.

Exercício 3.74: Alyssa P. Hacker está projetando um sistema para processar sinais vindos de sensores físicos. Uma característica importante que ela deseja produzir é um sinal que descreve os cruzamentos por zero do sinal de entrada. Ou seja, o sinal resultante deve ser $+1$ sempre que o sinal de entrada mudar de negativo para positivo, $-<!--\; -\; -->1$ sempre que o sinal de entrada mudar de positivo para negativo, e $0$ caso contrário. (Assuma que o sinal de um $0$ de entrada é positivo.) Por exemplo, um sinal de entrada típico com seu sinal de cruzamento por zero associado seria

… 1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4 …
              … 0 0  0  0  0   -1   0  0  0   0   1  0 0 …

No sistema de Alyssa, o sinal do sensor é representado como um fluxo sense-data e o fluxo zero-crossings é o fluxo correspondente de cruzamentos por zero. Alyssa primeiro escreve um procedimento sign-change-detector que recebe dois valores como argumentos e compara os sinais dos valores para produzir um $0$, $1$, ou $-<!--\; -\; -->1$ apropriado. Ela então constrói seu fluxo de cruzamentos por zero da seguinte forma:

(define (make-zero-crossings
                       input-stream last-value)
                (cons-stream
                 (sign-change-detector 
                  (stream-car input-stream) 
                  last-value)
                 (make-zero-crossings 
                  (stream-cdr input-stream)
                  (stream-car input-stream))))
              
              (define zero-crossings 
                (make-zero-crossings sense-data 0))

O chefe de Alyssa, Eva Lu Ator, passa por perto e sugere que este programa é aproximadamente equivalente ao seguinte, que usa a versão generalizada de stream-map do Exercício 3.50:

(define zero-crossings
                (stream-map sign-change-detector 
                            sense-data 
                            ⟨expression⟩))

Complete o programa fornecendo a ⟨expressão⟩ indicada.

Exercício 3.75: Infelizmente, o detector de cruzamentos por zero de Alyssa em Exercício 3.74 prova ser insuficiente, porque o sinal ruidoso do sensor leva a cruzamentos por zero espúrios. Lem E. Tweakit, um especialista em hardware, sugere que Alyssa suavize o sinal para filtrar o ruído antes de extrair os cruzamentos por zero. Alyssa aceita seu conselho e decide extrair os cruzamentos por zero do sinal construído pela média de cada valor dos dados do sensor com o valor anterior. Ela explica o problema ao seu assistente, Louis Reasoner, que tenta implementar a ideia, alterando o programa de Alyssa da seguinte forma:

(define (make-zero-crossings 
                       input-stream last-value)
                (let ((avpt 
                       (/ (+ (stream-car input-stream) 
                             last-value) 
                          2)))
                  (cons-stream 
                   (sign-change-detector avpt last-value)
                   (make-zero-crossings 
                    (stream-cdr input-stream) avpt))))

Isso não implementa corretamente o plano de Alyssa. Encontre o bug que Louis instalou e corrija-o sem alterar a estrutura do programa. (Dica: Você precisará aumentar o número de argumentos para make-zero-crossings.)

Exercício 3.76: Eva Lu Ator tem uma crítica ao abordagem de Louis no Exercício 3.75. O programa que ele escreveu não é modular, porque mistura a operação de suavização com a extração de cruzamentos por zero. Por exemplo, o extrator não deveria ter que ser alterado se Alyssa encontrar uma maneira melhor de condicionar seu sinal de entrada. Ajude Louis escrevendo um procedimento smooth que recebe um fluxo como entrada e produz um fluxo em que cada elemento é a média de dois elementos sucessivos do fluxo de entrada. Em seguida, use smooth como um componente para implementar o detector de cruzamentos por zero de uma maneira mais modular.

3.5.4Fluxos e Avaliação Atrasada

O procedimento integral no final da seção anterior mostra como podemos usar fluxos para modelar sistemas de processamento de sinais que contêm loops de feedback. O loop de feedback para o somador mostrado na Figura 3.32 é modelado pelo fato de que o fluxo interno int de integral é definido em termos de si mesmo:

(define int
                (cons-stream 
                 initial-value
                 (add-streams 
                  (scale-stream integrand dt) int)))

A capacidade do interpretador de lidar com tal definição implícita depende do delay que é incorporado ao cons-stream. Sem esse delay, o interpretador não poderia construir int antes de avaliar ambos os argumentos para cons-stream, o que exigiria que int já estivesse definido. Em geral, delay é crucial para usar fluxos para modelar sistemas de processamento de sinais que contêm loops. Sem delay, nossos modelos teriam que ser formulados de forma que as entradas para qualquer componente de processamento de sinais fossem totalmente avaliadas antes que a saída pudesse ser produzida. Isso proibiria loops.

Infelizmente, modelos de fluxo de sistemas com loops podem exigir usos de delay além do delay “oculto” fornecido por cons-stream. Por exemplo, Figura 3.34 mostra um sistema de processamento de sinais para resolver a equação diferencial $dy/dt=f(y)$ onde $f$ é uma dada função. A figura mostra um componente de mapeamento, que aplica $f$ ao seu sinal de entrada, ligado em um loop de feedback a um integrador de uma maneira muito semelhante aos circuitos de computadores analógicos que são realmente usados para resolver tais equações.

Assumindo que temos um valor inicial $y_0$ para $y$, poderíamos tentar modelar este sistema usando o procedimento

(define (solve f y0 dt)
                (define y (integral dy y0 dt))
                (define dy (stream-map f y))
                y)

Este procedimento não funciona, porque na primeira linha de solve a chamada para integral requer que a entrada dy seja definida, o que não acontece até a segunda linha de solve.

Por outro lado, a intenção de nossa definição faz sentido, porque podemos, em princípio, começar a gerar o fluxo y sem conhecer dy. De fato, integral e muitas outras operações de fluxo têm propriedades semelhantes às de cons-stream, no sentido de que podemos gerar parte da resposta dada apenas informações parciais sobre os argumentos. Para integral, o primeiro elemento do fluxo de saída é o initial-value especificado. Assim, podemos gerar o primeiro elemento do fluxo de saída sem avaliar o integrando dy. Uma vez que conhecemos o primeiro elemento de y, o stream-map na segunda linha de solve pode começar a trabalhar para gerar o primeiro elemento de dy, que produzirá o próximo elemento de y, e assim por diante.

Para aproveitar essa ideia, vamos redefinir integral para esperar que o integrando seja um argumento atrasado. Integral irá forçar o integrando a ser avaliado apenas quando for necessário gerar mais do que o primeiro elemento do fluxo de saída:

(define (integral
                         delayed-integrand initial-value dt)
                  (define int
                    (cons-stream 
                     initial-value
                     (let ((integrand 
                            (force delayed-integrand)))
                       (add-streams 
                        (scale-stream integrand dt)
                        int))))
                  int)

Agora podemos implementar nosso procedimento solve atrasando a avaliação de dy na definição de y:¹⁹⁹

(define (solve f y0 dt)
                  (define y (integral (delay dy) y0 dt))
                  (define dy (stream-map f y))
                  y)

Em geral, todo chamador de integral deve agora atrasar o argumento do integrando. Podemos demonstrar que o procedimento solve funciona aproximando $e\approx <!--\; \approx \; -->2.718$ ao calcular o valor em $y=1$ da solução para a equação diferencial $dy/dt=y$ com a condição inicial $y(0)=1$:

(stream-ref 
                 (solve (lambda (y) y) 1 0.001) 1000)
                2.716924

Exercício 3.77: O procedimento integral usado acima era análogo à definição “implícita” do fluxo infinito de inteiros em 3.5.2. Alternativamente, podemos dar uma definição de integral que é mais parecida com integers-starting-from (também em 3.5.2):

(define (integral
                         integrand initial-value dt)
                  (cons-stream 
                   initial-value
                   (if (stream-null? integrand)
                       the-empty-stream
                       (integral 
                        (stream-cdr integrand)
                        (+ (* dt (stream-car integrand))
                           initial-value)
                        dt))))

Quando usado em sistemas com loops, este procedimento tem o mesmo problema que nossa versão original de integral. Modifique o procedimento para que ele espere o integrand como um argumento atrasado e, portanto, possa ser usado no procedimento solve mostrado acima.

Exercício 3.78: Considere o problema de projetar um sistema de processamento de sinais para estudar a equação diferencial linear homogênea de segunda ordem $$\frac{d^{2}y}{d{t}^2}-<!--\; -\; -->a\frac{dy}{dt}-<!--\; -\; -->by=0.$$ O fluxo de saída, modelando $y$, é gerado por uma rede que contém um loop. Isso ocorre porque o valor de $d^{2}y/d{t}^2$ depende dos valores de $y$ e $dy/dt$ e ambos são determinados por integração de $d^{2}y/d{t}^2$. O diagrama que gostaríamos de codificar é mostrado em Figura 3.35. Escreva um procedimento solve-2nd que recebe como argumentos as constantes $a$, $b$, e $dt$ e os valores iniciais $y_0$ e $d{y}_0$ para $y$ e $dy/dt$ e gera o fluxo de valores sucessivos de $y$.

Exercício 3.79: Generalize o procedimento solve-2nd do Exercício 3.78 para que ele possa ser usado para resolver equações diferenciais de segunda ordem gerais $d^{2}y/d{t}^2=f(dy/dt,y)$.

Exercício 3.80: Um circuito RLC em série consiste em um resistor, um capacitor e um indutor conectados em série, como mostrado em Figura 3.36. Se $R$, $L$, e $C$ são a resistência, indutância e capacitância, então as relações entre a tensão $(v)$ e corrente $(i)$ para os três componentes são descritas pelas equações $$\begin{array}{rcl}{v}_R& =& i_{R}R,\\ v_L& =& L\frac{d{i}_L}{dt},\\ i_C& =& C\frac{d{v}_C}{dt},\end{array}$$ e as conexões do circuito ditam as relações $$\begin{array}{rcl}{i}_R& =& i_L=-<!--\; -\; -->i_C,\\ v_C& =& v_L+v_R.\end{array}$$ Combinando essas equações, mostra-se que o estado do circuito (resumido por $v_C$, a tensão no capacitor, e $i_L$, a corrente no indutor) é descrito pelo par de equações diferenciais $$\begin{array}{rcl}\frac{d{v}_C}{dt}& =& -<!--\; -\; -->\frac{i_L}{C},\\ \frac{d{i}_L}{dt}& =& \frac{1}{L}{v}_C-<!--\; -\; -->\frac{R}{L}{i}_L.\end{array}$$ O diagrama de fluxo de sinal que representa esse sistema de equações diferenciais é mostrado em Figura 3.37.

Escreva um procedimento RLC que recebe como argumentos os parâmetros $R$, $L$, e $C$ do circuito e o incremento de tempo $dt$. De uma maneira semelhante à do procedimento RC do Exercício 3.73, RLC deve produzir um procedimento que recebe os valores iniciais das variáveis de estado, $v_{C_0}$ e $i_{L_0}$, e produz um par (usando cons) dos fluxos de estados $v_C$ e $i_L$. Usando RLC, gere o par de fluxos que modela o comportamento de um circuito RLC em série com $R$ = 1 ohm, $C$ = 0.2 farad, $L$ = 1 henry, $dt$ = 0.1 segundo, e valores iniciais $i_{L_0}$ = 0 amps e $v_{C_0}$ = 10 volts.

Avaliação de ordem normal

Os exemplos nesta seção ilustram como o uso explícito de delay e force fornece grande flexibilidade de programação, mas os mesmos exemplos também mostram como isso pode tornar nossos programas mais complexos. Nosso novo procedimento integral, por exemplo, nos dá o poder de modelar sistemas com loops, mas agora devemos lembrar que integral deve ser chamado com um integrando atrasado, e todo procedimento que usa integral deve estar ciente disso. Na prática, criamos duas classes de procedimentos: procedimentos ordinários e procedimentos que recebem argumentos atrasados. Em geral, criar classes separadas de procedimentos nos força a criar classes separadas de procedimentos de ordem superior também.²⁰⁰

Uma maneira de evitar a necessidade de duas classes diferentes de procedimentos é fazer com que todos os procedimentos recebam argumentos atrasados. Poderíamos adotar um modelo de avaliação em que todos os argumentos para procedimentos são automaticamente atrasados e os argumentos são forçados apenas quando são realmente necessários (por exemplo, quando são exigidos por uma operação primitiva). Isso transformaria nossa linguagem para usar avaliação de ordem normal, que descrevemos pela primeira vez quando introduzimos o modelo de substituição para avaliação em 1.1.5. Converter para avaliação de ordem normal fornece uma maneira uniforme e elegante de simplificar o uso de avaliação atrasada, e essa seria uma estratégia natural a adotar se estivéssemos preocupados apenas com o processamento de fluxos. Em 4.2, depois de estudarmos o avaliador, veremos como transformar nossa linguagem exatamente dessa maneira. Infelizmente, incluir atrasos em chamadas de procedimentos causa estragos com nossa capacidade de projetar programas que dependem da ordem dos eventos, como programas que usam atribuição, mutação de dados ou realizam entrada ou saída. Mesmo o único delay em cons-stream pode causar grande confusão, como ilustrado por Exercício 3.51 e Exercício 3.52. Até onde se sabe, mutabilidade e avaliação atrasada não se misturam bem em linguagens de programação, e desenvolver maneiras de lidar com ambos ao mesmo tempo é uma área ativa de pesquisa.

3.5.5Modularidade de Programas Funcionais e Modularidade de Objetos

Como vimos em 3.1.2, um dos principais benefícios de introduzir atribuição é que podemos aumentar a modularidade de nossos sistemas ao encapsular, ou “esconder,” partes do estado de um grande sistema dentro de variáveis locais. Modelos de fluxo podem fornecer uma modularidade equivalente sem o uso de atribuição. Como ilustração, podemos reimplementar a estimação de Monte Carlo de $\mathrm{\pi <!--\; \pi \; -->}$, que examinamos em 3.1.2, a partir de um ponto de vista de processamento de fluxo.

A questão chave de modularidade era que queríamos esconder o estado interno de um gerador de números aleatórios de programas que usavam números aleatórios. Começamos com um procedimento rand-update, cujos valores sucessivos forneciam nosso suprimento de números aleatórios, e usamos isso para produzir um gerador de números aleatórios:

(define rand
                  (let ((x random-init))
                    (lambda ()
                      (set! x (rand-update x))
                      x)))

Na formulação de fluxo, não há um gerador de números aleatórios per se, apenas um fluxo de números aleatórios produzido por chamadas sucessivas a rand-update:

(define random-numbers
                  (cons-stream random-init
                               (stream-map rand-update 
                                           random-numbers)))

Usamos isso para construir o fluxo de resultados do experimento de Cesàro realizado em pares consecutivos no fluxo random-numbers:

(define cesaro-stream
                  (map-successive-pairs
                   (lambda (r1 r2) (= (gcd r1 r2) 1))
                   random-numbers))
                
                (define (map-successive-pairs f s)
                  (cons-stream
                   (f (stream-car s) 
                      (stream-car (stream-cdr s)))
                   (map-successive-pairs 
                    f (stream-cdr (stream-cdr s)))))

O cesaro-stream é agora alimentado a um procedimento monte-carlo, que produz um fluxo de estimativas de probabilidades. Os resultados são então convertidos em um fluxo de estimativas de $\mathrm{\pi <!--\; \pi \; -->}$. Esta versão do programa não precisa de um parâmetro informando quantas tentativas realizar. Estimativas melhores de $\mathrm{\pi <!--\; \pi \; -->}$ (de realizar mais experimentos) são obtidas ao olhar mais longe no fluxo pi:

(define (monte-carlo experiment-stream 
                                     passed 
                                     failed)
                  (define (next passed failed)
                    (cons-stream
                     (/ passed (+ passed failed))
                     (monte-carlo
                      (stream-cdr experiment-stream) 
                      passed 
                      failed)))
                  (if (stream-car experiment-stream)
                      (next (+ passed 1) failed)
                      (next passed (+ failed 1)))))
                
                (define pi
                  (stream-map
                   (lambda (p) (sqrt (/ 6 p)))
                   (monte-carlo cesaro-stream 0 0)))

Há considerável modularidade nesta abordagem, porque ainda podemos formular um procedimento monte-carlo geral que pode lidar com experimentos arbitrários. No entanto, não há atribuição ou estado local.

Exercício 3.81: Exercício 3.6 discutiu a generalização do gerador de números aleatórios para permitir que se reinicie a sequência de números aleatórios para produzir sequências repetíveis de números “aleatórios”. Produza uma formulação de fluxo desse mesmo gerador que opera em um fluxo de entrada de solicitações para gerar um novo número aleatório ou para reiniciar a sequência para um valor especificado e que produz o fluxo desejado de números aleatórios. Não use atribuição em sua solução.

Exercício 3.82: Refazer Exercício 3.5 sobre integração de Monte Carlo em termos de fluxos. A versão de fluxo de estimate-integral não terá um argumento informando quantas tentativas realizar. Em vez disso, produzirá um fluxo de estimativas baseadas em sucessivamente mais tentativas.

Uma visão de programação funcional do tempo

Vamos agora retornar às questões de objetos e estado que foram levantadas no início deste capítulo e examiná-las sob uma nova luz. Introduzimos atribuição e objetos mutáveis para fornecer um mecanismo para construção modular de programas que modelam sistemas com estado. Construímos objetos computacionais com variáveis de estado locais e usamos atribuição para modificar essas variáveis. Modelamos o comportamento temporal dos objetos no mundo pelo comportamento temporal dos objetos computacionais correspondentes.

Agora vimos que os fluxos fornecem uma maneira alternativa de modelar objetos com estado local. Podemos modelar uma quantidade em mudança, como o estado local de algum objeto, usando um fluxo que representa a história temporal dos estados sucessivos. Em essência, representamos o tempo explicitamente, usando fluxos, de modo que desacoplamos o tempo em nosso mundo simulado da sequência de eventos que ocorrem durante a avaliação. De fato, devido à presença de delay, pode haver pouca relação entre o tempo simulado no modelo e a ordem dos eventos durante a avaliação.

Para contrastar essas duas abordagens de modelagem, vamos reconsiderar a implementação de um “processador de saque” que monitora o saldo em uma conta bancária. Em 3.1.3 implementamos uma versão simplificada de tal processador:

(define (make-simplified-withdraw balance)
                  (lambda (amount)
                    (set! balance (- balance amount))
                    balance))

Chamadas para make-simplified-withdraw produzem objetos computacionais, cada um com uma variável de estado local balance que é decrementada por chamadas sucessivas ao objeto. O objeto recebe um amount como argumento e retorna o novo saldo. Podemos imaginar o usuário de uma conta bancária digitando uma sequência de entradas para tal objeto e observando a sequência de valores retornados exibidos em uma tela.

Alternativamente, podemos modelar um processador de saque como um procedimento que recebe como entrada um saldo e um fluxo de valores para sacar e produz o fluxo de saldos sucessivos na conta:

(define (stream-withdraw balance amount-stream)
                  (cons-stream
                   balance
                   (stream-withdraw 
                    (- balance (stream-car amount-stream))
                    (stream-cdr amount-stream))))

Stream-withdraw implementa uma função matemática bem definida cuja saída é totalmente determinada por sua entrada. Suponha, no entanto, que a entrada amount-stream seja o fluxo de valores sucessivos digitados pelo usuário e que o fluxo resultante de saldos seja exibido. Então, da perspectiva do usuário que está digitando valores e observando resultados, o processo de fluxo tem o mesmo comportamento que o objeto criado por make-simplified-withdraw. No entanto, com a versão de fluxo, não há atribuição, nenhuma variável de estado local e, consequentemente, nenhuma das dificuldades teóricas que encontramos em 3.1.3. No entanto, o sistema tem estado!

Isso é realmente notável. Mesmo que stream-withdraw implemente uma função matemática bem definida cujo comportamento não muda, a percepção do usuário aqui é de interagir com um sistema que tem um estado em mudança. Uma maneira de resolver esse paradoxo é perceber que é a existência temporal do usuário que impõe estado ao sistema. Se o usuário pudesse se afastar da interação e pensar em termos de fluxos de saldos em vez de transações individuais, o sistema pareceria sem estado.²⁰¹

Do ponto de vista de uma parte de um processo complexo, as outras partes parecem mudar com o tempo. Elas têm estado local oculto que varia com o tempo. Se desejamos escrever programas que modelam esse tipo de decomposição natural em nosso mundo (como o vemos do nosso ponto de vista como parte desse mundo) com estruturas em nosso computador, fazemos objetos computacionais que não são funcionais—eles devem mudar com o tempo. Modelamos estado com variáveis de estado locais, e modelamos as mudanças de estado com atribuições a essas variáveis. Ao fazer isso, fazemos o tempo de execução de uma computação modelar o tempo no mundo do qual fazemos parte, e assim obtemos “objetos” em nosso computador.

Modelar com objetos é poderoso e intuitivo, em grande parte porque isso corresponde à percepção de interagir com um mundo do qual fazemos parte. No entanto, como vimos repetidamente ao longo deste capítulo, esses modelos levantam problemas espinhosos de restringir a ordem dos eventos e de sincronizar múltiplos processos. A possibilidade de evitar esses problemas estimulou o desenvolvimento de linguagens de programação funcional, que não incluem nenhum provisionamento para atribuição ou dados mutáveis. Em tal linguagem, todos os procedimentos implementam funções matemáticas bem definidas de seus argumentos, cujo comportamento não muda. A abordagem funcional é extremamente atraente para lidar com sistemas concorrentes.²⁰²

Por outro lado, se olharmos de perto, podemos ver problemas relacionados ao tempo surgindo em modelos funcionais também. Uma área particularmente problemática surge quando desejamos projetar sistemas interativos, especialmente aqueles que modelam interações entre entidades independentes. Por exemplo, considere mais uma vez a implementação de um sistema bancário que permite contas conjuntas. Em um sistema convencional usando atribuição e objetos, modelaríamos o fato de que Pedro e Paulo compartilham uma conta fazendo com que ambos enviem suas solicitações de transação para o mesmo objeto de conta bancária, como vimos em 3.1.3. Do ponto de vista de fluxo, onde não há “objetos” per se, já indicamos que uma conta bancária pode ser modelada como um processo que opera em um fluxo de solicitações de transação para produzir um fluxo de respostas. Assim, poderíamos modelar o fato de que Pedro e Paulo têm uma conta bancária conjunta mesclando o fluxo de solicitações de transação de Pedro com o fluxo de solicitações de Paulo e alimentando o resultado ao processo de fluxo de conta bancária, como mostrado em Figura 3.38.

O problema com essa formulação está na noção de mesclagem. Não adianta mesclar os dois fluxos simplesmente alternando uma solicitação de Pedro e uma solicitação de Paulo. Suponha que Paulo acesse a conta apenas muito raramente. Dificilmente poderíamos forçar Pedro a esperar que Paulo acessasse a conta antes que ele pudesse emitir uma segunda transação. No entanto, tal mesclagem é implementada, ela deve intercalar os dois fluxos de transação de alguma forma que seja restrita pelo “tempo real” percebido por Pedro e Paulo, no sentido de que, se Pedro e Paulo se encontrarem, eles podem concordar que certas transações foram processadas antes do encontro, e outras transações foram processadas após o encontro.²⁰³ Esta é exatamente a mesma restrição que tivemos que lidar em 3.4.1, onde encontramos a necessidade de introduzir sincronização explícita para garantir uma ordem “correta” de eventos no processamento concorrente de objetos com estado. Assim, em uma tentativa de apoiar o estilo funcional, a necessidade de mesclar entradas de diferentes agentes reintroduz os mesmos problemas que o estilo funcional pretendia eliminar.

Começamos este capítulo com o objetivo de construir modelos computacionais cuja estrutura corresponda à nossa percepção do mundo real que estamos tentando modelar. Podemos modelar o mundo como uma coleção de objetos separados, limitados pelo tempo, interagindo com estado, ou podemos modelar o mundo como uma única unidade atemporal, sem estado. Cada visão tem vantagens poderosas, mas nenhuma visão é completamente satisfatória. Uma grande unificação ainda não surgiu.²⁰⁴