3.5.4 Streams e Avaliação Atrasada

A função integral no final da seção anterior mostra como podemos usar streams para modelar sistemas de processamento de sinais que contêm loops de realimentação. O loop de realimentação para o somador mostrado na figura é modelado pelo fato de que o stream interno integ é definido em termos de si mesmo:

const integ = pair(initial_value,
                   () => add_streams(scale_stream(integrand, dt),
                                     integ));

A capacidade do interpretador de lidar com tal definição implícita depende do atraso resultante de embrulhar a chamada para add_streams em uma expressão lambda. Sem esse atraso, o interpretador não poderia construir integ antes de avaliar a chamada para add_streams, o que exigiria que integ já estivesse definido. Em geral, tal atraso é crucial para usar streams para modelar sistemas de processamento de sinais que contêm loops. Sem um atraso, nossos modelos teriam que ser formulados de modo que as entradas para qualquer componente de processamento de sinal fossem totalmente avaliadas antes que a saída pudesse ser produzida. Isso proibiria loops.

Infelizmente, modelos de stream de sistemas com loops podem exigir usos de atraso além do padrão de programação de stream visto até agora. Por exemplo, a figura mostra um sistema de processamento de sinais para resolver a equação diferencial $dy/dt = f(y)$ onde $f$ é uma função dada. A figura mostra um componente de mapeamento, que aplica $f$ ao seu sinal de entrada, ligado em um loop de realimentação a um integrador de maneira muito similar à dos circuitos de computador analógico que são realmente usados para resolver tais equações.

Figura 3.54: Sistema de processamento de sinais com loop de realimentação para resolver $dy/dt = f(y)$. O sinal de entrada dy/dt é integrado para produzir y, que passa por uma função de ganho f (representando a função diferencial), e retorna ao somador através de um loop de realimentação tracejado.

Assumindo que nos é dado um valor inicial $y_0$ para $y$, poderíamos tentar modelar este sistema usando a função

function solve(f, y0, dt) {
    const y = integral(dy, y0, dt);
    const dy = stream_map(f, y);
    return y;
}

Esta função não funciona, porque na primeira linha de solve a chamada para integral requer que o argumento de entrada dy seja definido, 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 stream y sem conhecer dy. De fato, integral e muitas outras operações de stream podem gerar parte da resposta dada apenas informação parcial sobre os argumentos. Para integral, o primeiro elemento do stream de saída é o initial_value especificado. Assim, podemos gerar o primeiro elemento do stream 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 tirar vantagem dessa ideia, redefiniremos integral para esperar que o stream do integrando seja um argumento atrasado. A função integral forçará o integrando a ser avaliado apenas quando for necessário para gerar mais do que o primeiro elemento do stream de saída:

function integral(delayed_integrand, initial_value, dt) {
    const integ =
        pair(initial_value,
             () => {
                 const integrand = delayed_integrand();
                 return add_streams(scale_stream(integrand, dt),
                                    integ);
             });
    return integ;
}

Agora podemos implementar nossa função solve atrasando a avaliação de dy na declaração de y:

function solve(f, y0, dt) {
    const y = integral(() => dy, y0, dt);
    const dy = stream_map(f, y);
    return y;
}

Em geral, cada chamador de integral deve agora atrasar o argumento do integrando. Podemos demonstrar que a função solve funciona aproximando $e \approx 2.718$ computando o valor em $y = 1$ da solução para a equação diferencial $dy/dt = y$ com condição inicial $y(0) = 1$:¹

stream_ref(solve(y => y, 1, 0.001), 1000);

2.716923932235896

Exercício 3.77

A função integral usada acima foi análoga à definição "implícita" do stream infinito de inteiros na seção 3.5.2. Alternativamente, podemos dar uma definição de integral que é mais como integers_starting_from (também na seção 3.5.2):

function integral(integrand, initial_value, dt) {
    return pair(initial_value,
                is_null(integrand)
                ? null
                : integral(stream_tail(integrand),
                           dt * head(integrand) + initial_value,
                           dt));
}

Quando usada em sistemas com loops, esta função tem o mesmo problema que nossa versão original de integral. Modifique a função para que ela espere o integrand como um argumento atrasado e, portanto, possa ser usada na função solve mostrada acima.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Basta adiar também o integrand nesta formulação, chamando-o quando a cauda for construída:

Exemplo de Código

function integral(delayed_integrand, initial_value, dt) {
  return pair(initial_value,
              memo(() => {
                  const integrand = delayed_integrand();
                  return is_null(integrand)
                         ? null
                         : integral(() => stream_tail(integrand),
                                    dt * head(integrand)
                                    + initial_value,
                                    dt);
              }));
}

function solve(f, y0, dt) {
  const y = integral(() => dy, y0, dt);
  const dy = stream_map(f, y);
  return y;
}

// e^1 ≈ resolvendo dy/dt = y, y(0) = 1
stream_ref(solve(y => y, 1, 0.001), 1000);

function integral(delayed_integrand, initial_value, dt) { return pair(initial_value, memo(() => { const integrand = delayed_integrand(); return is_null(integrand) ? null : integral(() => stream_tail(integrand), dt * head(integrand) + initial_value, dt); })); } function solve(f, y0, dt) { const y = integral(() => dy, y0, dt); const dy = stream_map(f, y); return y; } // e^1 ≈ resolvendo dy/dt = y, y(0) = 1 stream_ref(solve(y => y, 1, 0.001), 1000);

Código editável · Ctrl+Enter executa · Esc solta o foco

Por que funciona. Cada passo da recursão recebe o integrando ainda embrulhado (delayed_integrand) e só o abre dentro da cauda adiada — assim solve pode definir y e dy mutuamente sem que nenhum dos dois precise existir primeiro. O resultado ($\approx 2{,}7169$) aproxima $e$.

Resolvi o exercício 3.77

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^2y}{dt^2} - a\frac{dy}{dt} - by = 0$

O stream de saída, modelando $y$, é gerado por uma rede que contém um loop. Isso ocorre porque o valor de $d^2y/dt^2$ depende dos valores de $y$ e $dy/dt$ e ambos são determinados integrando $d^2y/dt^2$. O diagrama que gostaríamos de codificar é mostrado na figura.

Figura 3.78: Sistema de processamento de sinais para resolver sistemas de equações diferenciais acopladas. Dois integradores processam dy₁ e dy₂ para produzir y₁ e y₂, com multiplicadores de ganho a e b. Os loops de realimentação cruzados (tracejados) mostram como cada equação depende da solução da outra.

Escreva uma função solve_2nd que recebe como argumentos as constantes $a$, $b$ e $dt$ e os valores iniciais $y_0$ e $dy_0$ para $y$ e $dy/dt$ e gera o stream de valores sucessivos de $y$.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Seguindo o diagrama: ddy é a combinação a·dy + b·y, e dy e y são integrais encadeadas de ddy:

Exemplo de Código

function solve_2nd(a, b, y0, dy0, dt) {
  const y = integral(() => dy, y0, dt);
  const dy = integral(() => ddy, dy0, dt);
  const ddy = add_streams(scale_stream(dy, a),
                          scale_stream(y, b));
  return y;
}

// d²y/dt² = y  (a = 0, b = 1), y(0) = 1, y'(0) = 1  →  y = e^t
stream_ref(solve_2nd(0, 1, 1, 1, 0.001), 1000);

function solve_2nd(a, b, y0, dy0, dt) { const y = integral(() => dy, y0, dt); const dy = integral(() => ddy, dy0, dt); const ddy = add_streams(scale_stream(dy, a), scale_stream(y, b)); return y; } // d²y/dt² = y (a = 0, b = 1), y(0) = 1, y'(0) = 1 → y = e^t stream_ref(solve_2nd(0, 1, 1, 1, 0.001), 1000);

Código editável · Ctrl+Enter executa · Esc solta o foco

As três funções são mutuamente recursivas e nenhuma executa nada até o stream ser puxado — a rede com loop do diagrama vira, literalmente, três declarações que se referenciam. Com $a = 0, b = 1$ a solução é $e^t$, e o valor em $t = 1$ sai $\approx 2{,}717$.

Resolvi o exercício 3.78

Exercício 3.79

Generalize a função solve_2nd do exercício 3.78 para que ela possa ser usada para resolver equações diferenciais de segunda ordem gerais $d^2y/dt^2 = f(dy/dt, y)$.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

A generalização troca a combinação linear fixa por uma função arbitrária de dy e y:

Exemplo de Código

function solve_2nd_general(f, y0, dy0, dt) {
  const y = integral(() => dy, y0, dt);
  const dy = integral(() => ddy, dy0, dt);
  const ddy = stream_map_2(f, dy, y);
  return y;
}

// o caso do exercício 3.78 é a instância f = (dy, y) => a·dy + b·y:
stream_ref(solve_2nd_general((dy, y) => 0 * dy + 1 * y,
                           1, 1, 0.001),
         1000);

function solve_2nd_general(f, y0, dy0, dt) { const y = integral(() => dy, y0, dt); const dy = integral(() => ddy, dy0, dt); const ddy = stream_map_2(f, dy, y); return y; } // o caso do exercício 3.78 é a instância f = (dy, y) => a·dy + b·y: stream_ref(solve_2nd_general((dy, y) => 0 * dy + 1 * y, 1, 1, 0.001), 1000);

Código editável · Ctrl+Enter executa · Esc solta o foco

stream_map_2(f, dy(), y()) alimenta $f$ com os valores correntes de $dy/dt$ e $y$ — qualquer equação $d^2y/dt^2 = f(dy/dt, y)$, linear ou não, entra na mesma rede.

Resolvi o exercício 3.79

Exercício 3.80

Um circuito RLC em série consiste de um resistor, um capacitor e um indutor conectados em série, como mostrado na figura. Se $R$, $L$ e $C$ são a resistência, indutância e capacitância, então as relações entre voltagem ($v$) e corrente ($i$) para os três componentes são descritas pelas equações

$$\begin{align*} v_R &= i_R R \\ v_L &= L\frac{di_L}{dt} \\ i_C &= C\frac{dv_C}{dt} \end{align*}$$

e as conexões do circuito ditam as relações

$$\begin{align*} i_R &= i_L = -i_C \\ v_C &= v_L + v_R \end{align*}$$

Combinando essas equações mostra que o estado do circuito (resumido por $v_C$, a voltagem através do capacitor, e $i_L$, a corrente no indutor) é descrito pelo par de equações diferenciais

$$\begin{align*} \frac{dv_C}{dt} &= -\frac{i_L}{C} \\ \frac{di_L}{dt} &= \frac{1}{L}v_C - \frac{R}{L}i_L \end{align*}$$

O diagrama de fluxo de sinal representando este sistema de equações diferenciais é mostrado na figura.

Figura 3.80: Circuito RLC em série mostrando resistor (R), indutor (L) e capacitor (C) conectados em série com uma fonte de tensão V(t). O circuito demonstra a relação entre voltagem e corrente nos três componentes passivos fundamentais da eletrônica.

Escreva uma função RLC que recebe como argumentos os parâmetros $R$, $L$ e $C$ do circuito e o incremento de tempo $dt$. De maneira similar à função RC do exercício 3.73, RLC deve produzir uma função que recebe os valores iniciais das variáveis de estado, $v_{C_0}$ e $i_{L_0}$, e produz um par (usando pair) dos streams de estados $v_C$ e $i_L$. Usando RLC, gere o par de streams 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$ amperes e $v_{C_0} = 10$ volts.

Avaliação em ordem normal

Os exemplos nesta seção ilustram como a avaliação atrasada fornece grande flexibilidade de programação, mas os mesmos exemplos também mostram como isso pode tornar nossos programas mais complexos. Nossa nova função integral, por exemplo, nos dá o poder de modelar sistemas com loops, mas devemos agora lembrar que integral deve ser chamada com um integrando atrasado, e cada função que usa integral deve estar ciente disso. Em efeito, criamos duas classes de funções: funções ordinárias e funções que recebem argumentos atrasados. Em geral, criar classes separadas de funções nos força a criar classes separadas de funções de ordem superior também.²

Uma maneira de evitar a necessidade de duas classes diferentes de funções é fazer todas as funções receberem argumentos atrasados. Poderíamos adotar um modelo de avaliação no qual todos os argumentos para funções 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 em ordem normal, que descrevemos pela primeira vez quando introduzimos o modelo de substituição para avaliação na seção 1.1.5. Converter para avaliação em ordem normal fornece uma maneira uniforme e elegante de simplificar o uso de avaliação atrasada, e esta seria uma estratégia natural a adotar se estivéssemos preocupados apenas com o processamento de streams. Na seção 4.2, após estudarmos o avaliador, veremos como transformar nossa linguagem exatamente dessa maneira. Infelizmente, incluir atrasos em chamadas de função causa estragos com nossa capacidade de projetar programas que dependem da ordem de eventos, como programas que usam atribuição, mutam dados ou executam entrada ou saída. Mesmo um único atraso no tail de um par pode causar grande confusão, como ilustrado pelos exercícios 3.51 e 3.52. Até onde se sabe, mutabilidade e avaliação atrasada não se misturam bem em linguagens de programação.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Das leis do circuito: $\dfrac{dv_C}{dt} = -\dfrac{i_L}{C}$ e $\dfrac{di_L}{dt} = \dfrac{v_C}{L} - \dfrac{R}{L} i_L$ — duas integrais acopladas:

Exemplo de Código

function RLC(R, L, C, dt) {
  return (vC0, iL0) => {
      const vC = integral(() => dvC, vC0, dt);
      const iL = integral(() => diL, iL0, dt);
      const dvC = scale_stream(iL, -1 / C);
      const diL = add_streams(scale_stream(vC, 1 / L),
                              scale_stream(iL, -R / L));
      return pair(vC, () => iL);
  };
}

const circuit = RLC(1, 1, 0.2, 0.1);
const state = circuit(10, 0);
// primeiros valores de vC e de iL:
display(stream_ref(head(state), 0));
display(stream_ref(head(state), 1));
display(stream_ref(stream_tail(state), 0));
stream_ref(stream_tail(state), 1);

function RLC(R, L, C, dt) { return (vC0, iL0) => { const vC = integral(() => dvC, vC0, dt); const iL = integral(() => diL, iL0, dt); const dvC = scale_stream(iL, -1 / C); const diL = add_streams(scale_stream(vC, 1 / L), scale_stream(iL, -R / L)); return pair(vC, () => iL); }; } const circuit = RLC(1, 1, 0.2, 0.1); const state = circuit(10, 0); // primeiros valores de vC e de iL: display(stream_ref(head(state), 0)); display(stream_ref(head(state), 1)); display(stream_ref(stream_tail(state), 0)); stream_ref(stream_tail(state), 1);

Código editável · Ctrl+Enter executa · Esc solta o foco

RLC(1, 1, 0.2, 0.1) devolve o gerador de circuitos pedido; aplicado às condições iniciais $v_{C_0} = 10$, $i_{L_0} = 0$, produz o par de streams: $v_C$ começa em 10 e decai; $i_L$ começa em 0, sobe para 1 no passo seguinte ($di_L/dt = 10/1$ com $dt = 0{,}1$) e passa a oscilar amortecido.

Resolvi o exercício 3.80

Footnotes

1. Para completar em tempo razoável, este cálculo requer o uso da otimização de memoização da seção 3.5.1 em integral e na função add_streams usada em integral (usando a função stream_map_2_optimized como sugerido no exercício 3.50). ↩

2. Este é um pequeno reflexo, em JavaScript, das dificuldades que linguagens estaticamente tipadas convencionais como Pascal tiveram ao lidar com funções de ordem superior. Nestas linguagens, o programador tinha que especificar os tipos de dados dos argumentos e o resultado de cada função: número, valor lógico, sequência, e assim por diante. Consequentemente, não poderíamos expressar uma abstração como "mapear uma dada função sobre todos os elementos em uma sequência" por uma única função de ordem superior como stream_map. Em vez disso, precisaríamos de uma função de mapeamento diferente para cada combinação diferente de tipos de dados de argumento e resultado que possam ser especificados para uma função. Manter uma noção prática de "tipo de dados" na presença de funções de ordem superior levanta muitas questões difíceis. Uma maneira de lidar com este problema é ilustrada pela linguagem ML (Gordon, Milner e Wadsworth 1979), cujos "tipos de dados parametricamente polimórficos" incluem modelos para transformações de ordem superior entre tipos de dados. Além disso, os tipos de dados para a maioria das funções em ML nunca são explicitamente declarados pelo programador. Em vez disso, ML inclui um mecanismo de inferência de tipos que usa informação no ambiente para deduzir os tipos de dados para funções recém-definidas. Hoje, linguagens de programação estaticamente tipadas evoluíram para tipicamente suportar alguma forma de inferência de tipos assim como polimorfismo paramétrico, com graus variados de poder. Haskell acopla um sistema de tipos expressivo com poderosa inferência de tipos. ↩