-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-24.html
703 lines (511 loc) · 123 KB
/
book-Z-H-24.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:ops="http://www.idpf.org/2007/ops">
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta http-equiv="Content-Type: text/html; charset=utf-8"/>
<title>Estrutura e Interpretação de Programas de Computador</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title="default"/>
</head>
<body>
<a name="%_sec_3.5" id="%_sec_3.5"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.5">3.5 Fluxos</a></h2><p>
<a name="%_idx_3726" id="%_idx_3726"/>Adquirimos um bom entendimento da atribuição como uma ferramenta na modelagem, bem como uma apreciação dos problemas complexos que a atribuição suscita. É hora de perguntar se poderíamos ter resolvido de uma maneira diferente, a fim de evitar alguns desses problemas. Nesta seção, exploramos uma abordagem alternativa para modelar o estado, com base nas estruturas de dados chamadas <em>fluxos</em>. Como veremos, os fluxos podem atenuar parte da complexidade do estado de modelagem.</p><p>Voltaremos e revisar de onde vem essa complexidade. Em uma 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 variação de tempo no mundo real com variação de tempo no computador. Implementamos a variação de tempo dos estados dos objetos de modelo no computador com atribuições para as variáveis locais dos objetos de modelo.</p><p>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 assunto em termos de funções matemáticas. Podemos descrever o comportamento variável do tempo de uma quantidade <em>x</em> em função do tempo <em>x</em>(<em>t</em>) Se nos concentrarmos <em>x</em> instante a instante, pensamos nisso como uma quantidade variável. No entanto, se nos concentrarmos em todo o histórico de valores no tempo, não enfatizamos a mudança – a função em si não muda.<a name="call_footnote_Temp_442" href="#footnote_Temp_442" id="call_footnote_Temp_442"><sup><small>52</small></sup></a></p><p>Se o tempo é medido em etapas discretas, podemos modelar uma função de tempo como uma sequência (possivelmente infinita). Nesta seção, veremos como modelar mudanças em termos de sequências que representam os históricos de tempo dos sistemas que são modelados. Para isso, introduzimos novas estruturas de dados chamadas <em>fluxos</em>. 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 na seção <a href="book-Z-H-15.html#%_sec_2.2.1">2.2.1</a>) não revela totalmente o poder do processamento de fluxo. Como alternativa, apresentamos a técnica de <a name="%_idx_3730" id="%_idx_3730"/><em>avaliação atrasada</em>, o que nos permite representar sequências muito grandes (até infinitas) como fluxos.</p><p>O processamento de fluxo nos permite modelar sistemas que possuem estado sem nunca usar dados de atribuição ou mutáveis. Isso possui implicações importantes, tanto teóricas quanto práticas, pois podemos construir modelos que evitam os inconvenientes inerentes à introdução de atribuições. Por outro lado, a estrutura de fluxo levanta dificuldades por si só, e a questão de qual técnica de modelagem leva a sistemas mais modulares e de manutenção mais fácil permanece em aberto.</p><p>
<a name="%_sec_3.5.1" id="%_sec_3.5.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.5.1">3.5.1 Os fluxos são listas atrasadas</a></h3><p>
<a name="%_idx_3732" id="%_idx_3732"/>Como vimos na seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>, sequências podem servir como interfaces padrão para combinar módulos de programa. Formulamos abstrações poderosas para manipular sequências, como <tt>map</tt>, <tt>filter</tt> e <tt>accumulate</tt>, que capturam uma ampla variedade de operações de maneira sucinta e elegante.</p><p>Infelizmente, se representamos sequências como listas, essa elegância é comprada pelo preço de uma ineficiência severa em relação ao tempo e espaço exigidos por nossos cálculos. 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 etapa do processo.</p><p>Para ver por que isso é verdade, compararemos dois programas para calcular a soma de todos os números primos em um intervalo. O primeiro programa é escrito no estilo iterativo padrão:<a name="call_footnote_Temp_443" href="#footnote_Temp_443" id="call_footnote_Temp_443"><sup><small>53</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3734" id="%_idx_3734"/>(define (sum-primes a b)<br/>
(define (iter count accum)<br/>
(cond ((> count b) accum)<br/>
((prime? count) (iter (+ count 1) (+ count accum)))<br/>
(else (iter (+ count 1) accum))))<br/>
(iter a 0))<br/></tt></p><p/><p>O segundo programa executa o mesmo cálculo usando as operações de sequência da seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>:</p><p>
</p><p/><p><tt><a name="%_idx_3736" id="%_idx_3736"/>(define (sum-primes a b)<br/>
(accumulate +<br/>
0<br/>
(filter prime? (enumerate-interval a b))))<br/></tt></p><p/><p/><p>Ao executar o cálculo, o primeiro programa precisa armazenar apenas a soma que é acumulada. Por outro lado, o filtro no segundo programa não pode fazer nenhum teste até <tt>enumerate-interval</tt> ter construído uma lista completa dos números no intervalo. O filtro gera outra lista, que por sua vez é passada para <tt>accumulate</tt> antes de ser recolhido para formar uma soma. Esse armazenamento intermediário grande não é necessário para o primeiro programa, que podemos considerar como enumerando o intervalo de forma incremental, adicionando cada primo à soma à medida que ele é gerado.</p><p>A ineficiência no uso de listas se torna 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</p><p>
</p><p/><p><tt>(car (cdr (filter prime?<br/>
(enumerate-interval 10000 1000000))))<br/></tt></p><p/><p>Essa expressão encontra o segundo primo, mas a sobrecarga computacional é escandalosa. Construímos uma lista de quase um milhão de números inteiros, filtramos essa lista testando cada elemento quanto à primalidade e depois ignoramos quase todo o resultado. Em um estilo de programação mais tradicional, intercalamos a enumeração e a filtragem e paramos quando atingimos o segundo primo.</p><p>Os fluxos são uma ideia inteligente que permite usar manipulações de sequência sem incorrer nos custos de manipulação de sequências como listas. Com os 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 construirá automaticamente apenas o suficiente para produzir a parte necessária, preservando a ilusão de que o fluxo inteiro existe. Em outras palavras, apesar de escrevermos programas como se estivéssemos processando sequências completas, projetamos nossa implementação de fluxo para intercalar de forma automática e transparente a construção do fluxo com seu uso.</p><p>Na superfície, os fluxos são apenas listas com nomes diferentes para os procedimentos que os manipulam. Existe um construtor, <a name="%_idx_3738" id="%_idx_3738"/><tt>cons-stream</tt> e dois seletores, <a name="%_idx_3740" id="%_idx_3740"/><tt>stream-car</tt> e <a name="%_idx_3742" id="%_idx_3742"/><tt>stream-cdr</tt>, que satisfazem as restrições</p>
<p>
<code>(stream-car (cons-stream x y)) = x</code><br/>
<code>(stream-cdr (cons-stream x y)) = y</code>
</p>
<p>Há um objeto distinguível, <a name="%_idx_3744" id="%_idx_3744"/><a name="%_idx_3746" id="%_idx_3746"/><a name="%_idx_3748" id="%_idx_3748"/><tt>the-empty-stream</tt>, que não pode ser o resultado de qualquer operação <tt>cons-stream</tt> e que pode ser identificado com o predicado <a name="%_idx_3750" id="%_idx_3750"/><tt>stream-null?</tt>.<a name="call_footnote_Temp_444" href="#footnote_Temp_444" id="call_footnote_Temp_444"><sup><small>54</small></sup></a> Assim, podemos criar e usar fluxos, da mesma maneira que podemos criar e usar listas, para representar dados agregados organizados em uma sequência. Em particular, podemos criar análogos de fluxo das operações da lista do capítulo 2, como <tt>list-ref</tt>, <tt>map</tt> e <tt>for-each</tt>:<a name="call_footnote_Temp_445" href="#footnote_Temp_445" id="call_footnote_Temp_445"><sup><small>55</small></sup></a>
</p><p/><p><tt><a name="%_idx_3758" id="%_idx_3758"/>(define (stream-ref s n)<br/>
(if (= n 0)<br/>
(stream-car s)<br/>
(stream-ref (stream-cdr s) (- n 1))))<br/><a name="%_idx_3760" id="%_idx_3760"/>(define (stream-map proc s)<br/>
(if (stream-null? s)<br/>
the-empty-stream<br/>
(cons-stream (proc (stream-car s))<br/>
(stream-map proc (stream-cdr s)))))<br/><a name="%_idx_3762" id="%_idx_3762"/>(define (stream-for-each proc s)<br/>
(if (stream-null? s)<br/>
'done<br/>
(begin (proc (stream-car s))<br/>
(stream-for-each proc (stream-cdr s)))))<br/></tt></p><p/><p>
<tt>Stream-for-each</tt> é útil para visualizar fluxos:</p><p/><p><tt><a name="%_idx_3764" id="%_idx_3764"/>(define (display-stream s)<br/>
(stream-for-each display-line s))<br/><br/><a name="%_idx_3766" id="%_idx_3766"/>(define (display-line x)<br/>
(newline)<br/>
(display x))<br/></tt></p><p/><p/><p>Para tornar a implementação do fluxo de forma automática e transparente intercalar a construção de um fluxo com seu uso, providenciaremos o <tt>cdr</tt> de um fluxo a ser avaliado quando acessado pelo procedimento <tt>stream-cdr</tt>, e não quando o fluxo é construído por <tt>cons-stream</tt>. Essa opção de implementação é uma reminiscência de nossa discussão sobre números racionais na seção <a href="book-Z-H-14.html#%_sec_2.1.2">2.1.2</a>, onde vimos que podemos optar por implementar números racionais para que a redução do numerador e do denominador para os termos mais baixos seja realizada no momento da construção ou no momento da seleção. As duas implementações de número racional produzem a mesma abstração de dados, mas a escolha afeta a eficiência. Existe uma relação semelhante entre fluxos e listas comuns. Como uma abstração de dados, os fluxos são os mesmos que as listas. A diferença é o tempo em que os elementos são avaliados. Com listas comuns, tanto o <tt>car</tt> e a <tt>cdr</tt> são avaliados no momento da construção. Com fluxos, o <tt>cdr</tt> é avaliado no momento da seleção.</p><p>
<a name="%_idx_3768" id="%_idx_3768"/><a name="%_idx_3770" id="%_idx_3770"/>Nossa implementação de fluxos será baseada em uma forma especial chamada <tt>delay</tt>. Avaliando <tt>(delay <<em>exp</em>>)</tt> não avalia a expressão <<em>exp</em>>, mas retorna uma chamada <a name="%_idx_3772" id="%_idx_3772"/><em>objeto atrasado</em>, que podemos considerar uma “promessa” de avaliar <<em>exp</em>> em algum momento futuro. Como companheiro de <tt>delay</tt>, existe um procedimento chamado <a name="%_idx_3774" id="%_idx_3774"/><tt>force</tt> que pega um objeto atrasado como argumento e executa a avaliação – com efeito, forçando o <tt>delay</tt> cumprir sua promessa. Veremos abaixo como <tt>delay</tt> e <tt>force</tt> pode ser implementado, mas primeiro vamos usá-los para construir fluxos.</p><p>
<a name="%_idx_3776" id="%_idx_3776"/><a name="%_idx_3778" id="%_idx_3778"/><tt>Cons-stream</tt> é uma forma especial definida para que</p><p>
</p><p/><p><tt>(cons-stream <<em>a</em>> <<em>b</em>>)<br/></tt></p><p/><p>é equivalente a</p><p>
</p><p/><p><tt>(cons <<em>a</em>> (delay <<em>b</em>>))<br/></tt></p><p/><p>O que isso significa é que construiremos fluxos usando pares. No entanto, em vez de colocar o valor do restante do fluxo no <tt>cdr</tt> do par, prometeremos calcular o restante, se isso for solicitado. <tt>Stream-car</tt> e <tt>stream-cdr</tt> agora pode ser definido como procedimentos:</p><p>
</p><p/><p><tt><a name="%_idx_3780" id="%_idx_3780"/>(define (stream-car stream) (car stream))<br/><br/><a name="%_idx_3782" id="%_idx_3782"/>(define (stream-cdr stream) (force (cdr stream)))<br/></tt></p><p/><p>
<tt>Stream-car</tt> seleciona o <tt>car</tt> do par; <tt>stream-cdr</tt> seleciona o <tt>cdr</tt> do par e avalia a expressão atrasada encontrada lá para obter o restante do fluxo.<a name="call_footnote_Temp_446" href="#footnote_Temp_446" id="call_footnote_Temp_446"><sup><small>56</small></sup></a>
<a name="%_sec_Temp_447" id="%_sec_Temp_447"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_447">A implementação do fluxo em ação</a></h4><p>Para ver como essa implementação se comporta, analisaremos a computação principal “ultrajante” que vimos acima, reformulada em termos de fluxos:</p><p>
</p><p/><p><tt>(stream-car<br/>
(stream-cdr<br/>
(stream-filter prime?<br/>
(stream-enumerate-interval 10000 1000000))))<br/></tt></p><p/><p>Veremos que ele realmente funciona com eficiência.</p><p>Começamos chamando <tt>stream-enumerate-interval</tt> com os argumentos 10.000 e 1.000.000. <tt>Stream-enumerate-interval</tt> é o fluxo analógico de <tt>enumerate-interval</tt> (seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>):</p><p>
</p><p/><p><tt><a name="%_idx_3788" id="%_idx_3788"/>(define (stream-enumerate-interval low high)<br/>
(if (> low high)<br/>
the-empty-stream<br/>
(cons-stream<br/>
low<br/>
(stream-enumerate-interval (+ low 1) high))))<br/></tt></p><p/><p>e assim o resultado retornado por <tt>stream-enumerate-interval</tt>, formado pelo <tt>cons-stream</tt>, é<a name="call_footnote_Temp_448" href="#footnote_Temp_448" id="call_footnote_Temp_448"><sup><small>57</small></sup></a></p><p>
</p><p/><p><tt>(cons 10000<br/>
(delay (stream-enumerate-interval 10001 1000000)))<br/></tt></p><p/><p>Isso é, <tt>stream-enumerate-interval</tt> retorna um fluxo representado como um par cujo <tt>car</tt> é 10.000 e cuja <tt>cdr</tt> é uma promessa de enumerar mais do intervalo, se solicitado. Esse fluxo agora é filtrado para números primos, usando o fluxo analógico do procedimento <tt>filter</tt> (seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>):</p><p>
</p><p/><p><tt><a name="%_idx_3790" id="%_idx_3790"/>(define (stream-filter pred stream)<br/>
(cond ((stream-null? stream) the-empty-stream)<br/>
((pred (stream-car stream))<br/>
(cons-stream (stream-car stream)<br/>
(stream-filter pred<br/>
(stream-cdr stream))))<br/>
(else (stream-filter pred (stream-cdr stream)))))<br/></tt></p><p/><p>
<tt>Stream-filter</tt> testa o <tt>stream-car</tt> do fluxo (o <tt>car</tt> do par, que é 10.000). Como isso não é primo, <tt>stream-filter</tt> examina o <tt>stream-cdr</tt> do seu fluxo de entrada. A chamada para <tt>stream-cdr</tt> força a avaliação do atraso <tt>stream-enumerate-interval</tt>, que agora retorna</p><p>
</p><p/><p><tt>(cons 10001<br/>
(delay (stream-enumerate-interval 10002 1000000)))<br/></tt></p><p/><p>
<tt>Stream-filter</tt> agora olha para o <tt>stream-car</tt> deste fluxo, 10.001, vê que isso também não é primo, força outro <tt>stream-cdr</tt> e assim por diante, até <tt>stream-enumerate-interval</tt> produz o número 10.007 principal, <tt>stream-filter</tt>, de acordo com sua definição, retorna</p><p>
</p><p/><p><tt>(cons-stream (stream-car stream)<br/>
(stream-filter pred (stream-cdr stream)))<br/></tt></p><p/><p>que neste caso é</p><p>
</p><p/><p><tt>(cons 10007<br/>
(delay<br/>
(stream-filter<br/>
prime?<br/>
(cons 10008<br/>
(delay<br/>
(stream-enumerate-interval 10009<br/>
1000000))))))<br/></tt></p><p/><p>Este resultado agora é passado para <tt>stream-cdr</tt> na nossa expressão original. Isso força o atraso <tt>stream-filter</tt>, que por sua vez continua forçando o atraso <tt>stream-enumerate-interval</tt> até encontrar o próximo primo, que é 10.009. Finalmente, o resultado passou para <tt>stream-car</tt> na nossa expressão original é</p><p>
</p><p/><p><tt>(cons 10009<br/>
(delay<br/>
(stream-filter<br/>
prime?<br/>
(cons 10010<br/>
(delay<br/>
(stream-enumerate-interval 10011<br/>
1000000))))))<br/></tt></p><p/><p>
<tt>Stream-car</tt> retorna 10.009 e o cálculo está completo. Apenas tantos números inteiros foram testados quanto à primalidade necessários para encontrar o segundo prime, e o intervalo foi enumerado apenas na medida do necessário para alimentar o filtro do prime.</p><p>Em geral, podemos pensar na avaliação atrasada como <a name="%_idx_3792" id="%_idx_3792"/>programação “orientada por demanda”, em que cada estágio do processo de fluxo é ativado apenas o suficiente para satisfazer o próximo estágio. O que fizemos é <a name="%_idx_3794" id="%_idx_3794"/>dissociar a ordem real dos eventos no cálculo da estrutura aparente de nossos procedimentos. Escrevemos procedimentos como se os fluxos existissem “de uma só vez” quando, na realidade, o cálculo é realizado de forma incremental, como nos estilos de programação tradicionais.</p><p>
<a name="%_sec_Temp_449" id="%_sec_Temp_449"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_449">Implementando <tt>delay</tt> e <tt>force</tt></a></h4><p>
<a name="%_idx_3796" id="%_idx_3796"/>Apesar <tt>delay</tt> e <tt>force</tt> pode parecer operações misteriosas, sua implementação é realmente bastante direta. <tt>Delay</tt> devemos empacotar uma expressão para que ela possa ser avaliada posteriormente sob demanda, e podemos fazer isso simplesmente tratando a expressão como o corpo de um procedimento. <tt>Delay</tt> pode ser uma forma especial tal que</p><p>
</p><p/><p><tt>(delay <<em>exp</em>>)<br/></tt></p><p/><p>é açúcar sintático para</p><p>
</p><p/><p><tt>(lambda () <<em>exp</em>>)<br/></tt></p><p/><p>
<tt>Force</tt> simplesmente chama o procedimento (sem argumentos) produzido por <tt>delay</tt>, para que possamos implementar <tt>force</tt> como procedimento:</p><p>
</p><p/><p><tt><a name="%_idx_3798" id="%_idx_3798"/>(define (force delayed-object)<br/>
(delayed-object))<br/></tt></p><p/><p/><p>
<a name="%_idx_3800" id="%_idx_3800"/><a name="%_idx_3802" id="%_idx_3802"/>Esta implementação é suficiente para <tt>delay</tt> e <tt>force</tt> funcionar como anunciado, mas há uma otimização importante que podemos incluir. Em muitas aplicações, acabamos forçando o mesmo objeto atrasado várias vezes. Isso pode levar a uma ineficiência grave em programas recursivos que envolvem fluxos. (Veja exercício <a href="#%_thm_3.57">3.57</a>). A solução é criar objetos atrasados para que, na primeira vez em que sejam forçados, eles armazenem o valor calculado. Forçamentos subsequentes simplesmente retornarão o valor armazenado sem repetir o cálculo. Em outras palavras, implementamos <tt>delay</tt> como um procedimento memoizado de finalidade especial semelhante ao descrito no exercício <a href="book-Z-H-22.html#%_thm_3.27">3.27</a>. Uma maneira de conseguir isso é usar o procedimento a seguir, que usa 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. Nas avaliações subsequentes, ele simplesmente retorna o resultado.</p><p>
</p><p/><p><tt><a name="%_idx_3804" id="%_idx_3804"/>(define (memo-proc proc)<br/>
(let ((already-run? false) (result false))<br/>
(lambda ()<br/>
(if (not already-run?)<br/>
(begin (set! result (proc))<br/>
(set! already-run? true)<br/>
result)<br/>
result))))<br/></tt></p><p/><p>
<tt>Delay</tt> é então definido para que <tt>(delay <<em>exp</em>>)</tt> é equivalente a</p><p>
</p><p/><p><tt>(memo-proc (lambda () <<em>exp</em>>))<br/></tt></p><p/><p>e <tt>force</tt> é como definido anteriormente.<a name="call_footnote_Temp_450" href="#footnote_Temp_450" id="call_footnote_Temp_450"><sup><small>58</small></sup></a></p><p>
</p><p><a name="%_thm_3.50" id="%_thm_3.50"/>
<b>Exercício 3.50.</b> Complete a seguinte definição, que generaliza <tt>stream-map</tt> para permitir procedimentos que levam múltiplos argumentos, análogos a <tt>map</tt> na seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a> nota de rodapé<a href="book-Z-H-15.html#footnote_Temp_166">12</a>.</p><p>
</p><p/><p><tt><a name="%_idx_3824" id="%_idx_3824"/>(define (stream-map proc . argstreams)<br/>
(if (<<em>??</em>> (car argstreams))<br/>
the-empty-stream<br/>
(<<em>??</em>><br/>
(apply proc (map <<em>??</em>> argstreams))<br/>
(apply stream-map<br/>
(cons proc (map <<em>??</em>> argstreams))))))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.51" id="%_thm_3.51"/>
<b>Exercício 3.51.</b> <a name="%_idx_3826" id="%_idx_3826"/>Para examinar mais de perto a avaliação atrasada, usaremos o procedimento a seguir, que simplesmente retorna seu argumento após a impressão:</p><p>
</p><p/><p><tt>(define (show x)<br/>
(display-line x)<br/>
x)<br/></tt></p><p/><p>O que o interpretador imprime em resposta à avaliação de cada expressão na seguinte sequência?<a name="call_footnote_Temp_453" href="#footnote_Temp_453" id="call_footnote_Temp_453"><sup><small>59</small></sup></a></p><p>
</p><p/><p><tt>(define x (stream-map show (stream-enumerate-interval 0 10)))<br/>
(stream-ref x 5)<br/>
(stream-ref x 7)<br/></tt></p><p/><p>
</p><p>
</p><p><a name="%_thm_3.52" id="%_thm_3.52"/>
<b>Exercício 3.52.</b> <a name="%_idx_3830" id="%_idx_3830"/>Considere a sequência de expressões</p><p>
</p><p/><p><tt>(define sum 0)<br/>
(define (accum x)<br/>
(set! sum (+ x sum))<br/>
sum)<br/>
(define seq (stream-map accum (stream-enumerate-interval 1 20)))<br/>
(define y (stream-filter even? seq))<br/>
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))<br/>
seq))<br/>
(stream-ref y 7)<br/>
(display-stream z)<br/></tt></p><p/><p>Qual é o valor de <tt>sum</tt> após cada uma das expressões acima ser avaliada? Qual é a resposta impressa para avaliar as expressões <tt>stream-ref</tt> e <tt>display-stream</tt>? Essas respostas difeririam se tivéssemos implementado <tt>(delay <<em>exp</em>>)</tt> simplesmente como <tt>(lambda () <<em>exp</em>>)</tt> sem usar a otimização fornecida pelo <tt>memo-proc</tt> ? Explique.</p><p/><p>
<a name="%_sec_3.5.2" id="%_sec_3.5.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.5.2">3.5.2 Fluxos infinitos</a></h3><p>
<a name="%_idx_3832" id="%_idx_3832"/>Vimos como apoiar a ilusão de manipular fluxos como entidades completas, embora, na realidade, calculemos apenas o fluxo necessário para acessar. Podemos explorar essa técnica para representar sequências eficientemente 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 números inteiros positivos:</p><p>
</p><p/><p><tt><a name="%_idx_3834" id="%_idx_3834"/>(define (integers-starting-from n)<br/>
(cons-stream n (integers-starting-from (+ n 1))))<br/><br/><a name="%_idx_3836" id="%_idx_3836"/>(define integers (integers-starting-from 1))<br/></tt></p><p/><p>Isso faz sentido, pois <tt>integers</tt> será um par cujo <tt>car</tt> é 1 e cujo <tt>cdr</tt> é uma promessa de produzir os números inteiros começando com 2. Este é um fluxo infinitamente longo, mas em um dado momento podemos examinar apenas uma parte finita dele. Assim, nossos programas nunca saberão que todo o fluxo infinito não existe.</p><p>Usando <tt>integers</tt> podemos definir outros fluxos infinitos, como o fluxo de números inteiros que não são divisíveis por 7:</p><p>
</p><p/><p><tt><a name="%_idx_3838" id="%_idx_3838"/>(define (divisible? x y) (= (remainder x y) 0))<br/>
(define no-sevens<br/>
(stream-filter (lambda (x) (not (divisible? x 7)))<br/>
integers))<br/></tt></p><p/><p>Então, podemos encontrar números inteiros não divisíveis por 7 simplesmente acessando elementos desse fluxo:</p><p>
</p><p/><p><tt>(stream-ref no-sevens 100)<br/><i>117</i><br/></tt></p><p/><p>
</p><p>Em analogia com <tt>integers</tt>, podemos definir o fluxo infinito de números de Fibonacci:</p><p>
</p><p/><p><tt>(define (fibgen a b)<br/>
(cons-stream a (fibgen b (+ a b))))<br/><a name="%_idx_3840" id="%_idx_3840"/>(define fibs (fibgen 0 1))<br/></tt></p><p/><p>
<tt>Fibs</tt> é um par cujo <tt>car</tt> é 0 e cuja <tt>cdr</tt> é uma promessa para avaliar <tt>(fibgen 1 1)</tt>. Quando avaliamos este <tt>(fibgen 1 1)</tt> atrasado, ele produzirá um par cujo <tt>car</tt> é 1 e cujo <tt>cdr</tt> é uma promessa para avaliar <tt>(fibgen 1 2)</tt>, e assim por diante.</p><p>
<a name="%_idx_3842" id="%_idx_3842"/>Para dar uma olhada em um fluxo infinito mais emocionante, podemos generalizar o <tt>no-sevens</tt> exemplo para construir o fluxo infinito de números primos, usando um método conhecido como <a name="%_idx_3844" id="%_idx_3844"/><em>crivo de Eratóstenes</em>.<a name="call_footnote_Temp_455" href="#footnote_Temp_455" id="call_footnote_Temp_455"><sup><small>60</small></sup></a> Começamos com os números inteiros começando com 2, que é o primeiro primo. Para obter o restante dos números primos, começamos por filtrar os múltiplos de 2 do restante dos números inteiros. Isso deixa um fluxo começando com 3, que é o próximo prime. Agora filtramos os múltiplos de 3 do restante 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 números primos por um processo de peneiração, descrito a seguir: Para peneirar um fluxo <tt>S</tt>, forme um fluxo cujo primeiro elemento seja o primeiro elemento de <tt>S</tt> e o restante é obtido filtrando todos os múltiplos do primeiro elemento de <tt>S</tt> fora do resto <tt>S</tt> e peneirar o resultado. Este processo é prontamente descrito em termos de operações de fluxo:</p><p>
</p><p/><p><tt><a name="%_idx_3852" id="%_idx_3852"/>(define (sieve stream)<br/>
(cons-stream<br/>
(stream-car stream)<br/>
(sieve (stream-filter<br/>
(lambda (x)<br/>
(not (divisible? x (stream-car stream))))<br/>
(stream-cdr stream)))))<br/><br/><a name="%_idx_3854" id="%_idx_3854"/>(define primes (sieve (integers-starting-from 2)))<br/></tt></p><p/><p>Agora, para encontrar um primo específico, precisamos apenas solicitá-lo:</p><p>
</p><p/><p><tt>(stream-ref primes 50)<br/><i>233</i><br/></tt></p><p/><p/><p>É interessante contemplar o sistema de processamento de sinais criado por <tt>sieve</tt>, mostrado no <a name="%_idx_3856" id="%_idx_3856"/>“diagrama de Henderson” na figura <a href="#%_fig_3.31">3.31</a>.<a name="call_footnote_Temp_456" href="#footnote_Temp_456" id="call_footnote_Temp_456"><sup><small>61</small></sup></a> O fluxo de entrada alimenta um “un <tt>cons</tt>er” que separa o primeiro elemento do fluxo do restante do fluxo. O primeiro elemento é usado para construir um filtro de divisibilidade, através do qual o restante é passado, e a saída do filtro é alimentada para outra caixa do crivo. Então o primeiro elemento original <tt>cons</tt>é aplicado na saída do crivo interna para formar o fluxo de saída. Assim, não apenas o fluxo é infinito, mas o processador de sinais também é infinito, pois o crivo contém um crivo dentro dele.</p><p>
<a name="%_fig_3.31" id="%_fig_3.31"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-35.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.31:</b> O crivo de primos é visto como um sistema de processamento de sinais.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_sec_Temp_457" id="%_sec_Temp_457"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_457">Definindo fluxos implicitamente</a></h4><p>
<a name="%_idx_3860" id="%_idx_3860"/>Os fluxos <tt>integers</tt> e <tt>fibs</tt> acima foram definidos especificando os procedimentos de “geração” que calculam explicitamente os elementos do fluxo, um por um. Uma maneira alternativa de especificar fluxos é tirar proveito da avaliação atrasada para definir fluxos implicitamente. Por exemplo, a expressão a seguir define o fluxo <tt>ones</tt> para ser um fluxo infinito de unidades:</p><p>
</p><p/><p><tt><a name="%_idx_3862" id="%_idx_3862"/>(define ones (cons-stream 1 ones))<br/></tt></p><p/><p>Isso funciona como a definição de um procedimento recursivo: <tt>ones</tt> é um par cujo <tt>car</tt> é 1 e cuja <tt>cdr</tt> é uma promessa para avaliar <tt>ones</tt>. Avaliando o <tt>cdr</tt> nos dá novamente um 1 e uma promessa de avaliar <tt>ones</tt>, e assim por diante.</p><p>Podemos fazer algo mais interessantes manipulando fluxos com operações como <tt>add-streams</tt>, que produz a soma elementar de dois fluxos fornecidos:<a name="call_footnote_Temp_458" href="#footnote_Temp_458" id="call_footnote_Temp_458"><sup><small>62</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3864" id="%_idx_3864"/>(define (add-streams s1 s2)<br/>
(stream-map + s1 s2))<br/></tt></p><p/><p>Agora podemos definir os números inteiros da seguinte maneira:</p><p>
</p><p/><p><tt><a name="%_idx_3866" id="%_idx_3866"/>(define integers (cons-stream 1 (add-streams ones integers)))<br/></tt></p><p/><p>Isso define <tt>integers</tt> para ser um fluxo cujo primeiro elemento é 1 e o restante é a soma de <tt>ones</tt> e <tt>integers</tt>. Assim, o segundo elemento de <tt>integers</tt> é 1 mais o primeiro elemento de <tt>integers</tt> ou 2; o terceiro elemento de <tt>integers</tt> é 1 mais o segundo elemento de <tt>integers</tt>, ou 3; e assim por diante. Essa definição funciona, pois, a qualquer momento, é suficiente o fluxo de <tt>integers</tt> foi gerado para que possamos alimentá-lo novamente na definição para produzir o próximo número inteiro.</p><p>Podemos definir os números de Fibonacci no mesmo estilo:</p><p>
</p><p/><p><tt><a name="%_idx_3868" id="%_idx_3868"/>(define fibs<br/>
(cons-stream 0<br/>
(cons-stream 1<br/>
(add-streams (stream-cdr fibs)<br/>
fibs))))<br/></tt></p><p/><p>Esta definição diz que <tt>fibs</tt> é um fluxo começando com 0 e 1, de modo que o restante do fluxo possa ser gerado adicionando <tt>fibs</tt> para si mesmo deslocado por um lugar:</p><p>
</p><table border="0"><tr><td valign="top"/><td valign="top"/><td valign="top">1 </td><td valign="top">1 </td><td valign="top">2 </td><td valign="top">3 </td><td valign="top">5 </td><td valign="top">8 </td><td valign="top">13 </td><td valign="top">21 </td><td valign="top"><tt>...</tt> = <tt>(stream-cdr fibs)</tt></td></tr><tr><td valign="top"/><td valign="top"/><td valign="top">0 </td><td valign="top">1 </td><td valign="top">1 </td><td valign="top">2 </td><td valign="top">3 </td><td valign="top">5 </td><td valign="top"> 8 </td><td valign="top">13 </td><td valign="top"><tt>...</tt> = <tt>fibs</tt></td></tr><tr><td valign="top">0 </td><td valign="top">1 </td><td valign="top">1 </td><td valign="top">2 </td><td valign="top">3 </td><td valign="top">5 </td><td valign="top">8 </td><td valign="top">13 </td><td valign="top">21 </td><td valign="top">34 </td><td valign="top"><tt>...</tt> = <tt>fibs</tt></td></tr><tr><td valign="top"/></tr></table><p>
<tt>Scale-stream</tt> é outro procedimento útil na formulação de tais definições de fluxo. Isso multiplica cada item em um fluxo por uma dada constante:</p><p>
</p><p/><p><tt><a name="%_idx_3870" id="%_idx_3870"/>(define (scale-stream stream factor)<br/>
(stream-map (lambda (x) (* x factor)) stream))<br/></tt></p><p/><p>Por exemplo,</p><p>
</p><p/><p><tt>(define double (cons-stream 1 (scale-stream double 2)))<br/></tt></p><p/><p>produz o fluxo de potências de 2: 1, 2, 4, 8, 16, 32, <tt>…</tt>.</p><p>Uma definição alternativa do fluxo de números primos pode ser dada começando com os números inteiros e filtrando-os testando a primalidade. Precisaremos do primeiro primo, 2, para começar:</p><p>
</p><p/><p><tt><a name="%_idx_3872" id="%_idx_3872"/>(define primes<br/>
(cons-stream<br/>
2<br/>
(stream-filter prime? (integers-starting-from 3))))<br/></tt></p><p/><p>Essa definição não é tão direta quanto parece, pois testaremos se um número <em>n</em> é um primo verificando se <em>n</em> é divisível por um primo (não por qualquer número inteiro) menor ou igual a √<em>n</em>:</p><p>
</p><p/><p><tt><a name="%_idx_3874" id="%_idx_3874"/>(define (prime? n)<br/>
(define (iter ps)<br/>
(cond ((> (square (stream-car ps)) n) true)<br/>
((divisible? n (stream-car ps)) false)<br/>
(else (iter (stream-cdr ps)))))<br/>
(iter primes))<br/></tt></p><p/><p>Esta é uma definição recursiva, pois <tt>primes</tt> é definido em termos de <tt>prime?</tt> predicado, que em si usa um de fluxo de <tt>primes</tt>. A razão pela qual esse procedimento funciona é que, a qualquer momento, um número suficiente de fluxos de <tt>primes</tt> foi gerado para testar a primalidade dos números que precisamos verificar a seguir. Ou seja, para cada <em>n</em> testamos primalidade, <em>n</em> não é primo (nesse caso, já é gerado um primo que o divide) ou <em>n</em> é primo (nesse caso, já é gerado um primo – ou seja, um primo menor que <em>n</em> – isso é maior que √<em>n</em>)<a name="call_footnote_Temp_459" href="#footnote_Temp_459" id="call_footnote_Temp_459"><sup><small>63.</small></sup></a>
</p><p><a name="%_thm_3.53" id="%_thm_3.53"/>
<b>Exercício 3.53.</b> Sem executar o programa, descreva os elementos do fluxo definidos por</p><p/><p><tt>(define s (cons-stream 1 (add-streams s s)))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.54" id="%_thm_3.54"/>
<b>Exercício 3.54.</b> Definir um procedimento <a name="%_idx_3886" id="%_idx_3886"/><a name="%_idx_3888" id="%_idx_3888"/><a name="%_idx_3890" id="%_idx_3890"/><tt>mul-streams</tt>, semelhante a <tt>add-streams</tt>, que produz o produto elementar de seus dois fluxos de entrada. Use isso junto com o fluxo de <tt>integers</tt> para concluir a seguinte definição do fluxo cujo <em>n</em>ésimo elemento (contando de 0) é <em>n</em> + 1 fatorial:</p><p/><p><tt>(define factorials (cons-stream 1 (mul-streams <<em>??</em>> <<em>??</em>>)))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.55" id="%_thm_3.55"/>
<b>Exercício 3.55.</b> Definir um procedimento <a name="%_idx_3892" id="%_idx_3892"/><tt>partial-sums</tt> que toma como argumento um fluxo <em>S</em> e retorna o fluxo cujos elementos são <em>S</em><sub>0</sub>, <em>S</em><sub>0</sub> + <em>S</em><sub>1</sub>, <em>S</em><sub>0</sub> + <em>S</em><sub>1</sub> + <em>S</em><sub>2</sub>, <tt>…</tt>. Por exemplo, <tt>(partial-sums integers)</tt> deve ser o fluxo 1, 3, 6, 10, 15, <tt>…</tt>.</p><p/><p>
</p><p><a name="%_thm_3.56" id="%_thm_3.56"/>
<b>Exercício 3.56.</b> Um problema famoso, levantado pela primeira vez por <a name="%_idx_3894" id="%_idx_3894"/>R. Hamming, é enumerar, em ordem crescente sem repetições, todos os números inteiros positivos sem fatores primos que não sejam 2, 3 ou 5. Uma maneira óbvia de fazer isso é simplesmente testar cada número inteiro, por sua vez, para verificar se há outros fatores além de 2, 3 e 5. Mas isso é muito ineficiente, pois, à medida que os números inteiros aumentam, cada vez menos eles se encaixam no requisito. Como alternativa, chamaremos o fluxo de números necessário <tt>S</tt> e observe os seguintes fatos sobre o assunto.</p><p/><ul><li><tt>S</tt> começa com 1.<p>
</p></li><li>Os elementos de <tt>(scale-stream S 2)</tt> também são elementos de <tt>S</tt>.<p>
</p></li><li>O mesmo vale para <tt>(scale-stream S 3)</tt> e <tt>(scale-stream 5 S)</tt>.<p>
</p></li><li>Estes são todos os elementos de <tt>S</tt>.</li></ul><p/><p>
<a name="%_idx_3896" id="%_idx_3896"/>Agora tudo o que precisamos fazer é combinar elementos dessas fontes. Para isso, definimos um procedimento <tt>merge</tt> que combina dois fluxos ordenados em um fluxo de resultados ordenados, eliminando repetições:</p><p>
</p><p/><p><tt><a name="%_idx_3898" id="%_idx_3898"/>(define (merge s1 s2)<br/>
(cond ((stream-null? s1) s2)<br/>
((stream-null? s2) s1)<br/>
(else<br/>
(let ((s1car (stream-car s1))<br/>
(s2car (stream-car s2)))<br/>
(cond ((< s1car s2car)<br/>
(cons-stream s1car (merge (stream-cdr s1) s2)))<br/>
((> s1car s2car)<br/>
(cons-stream s2car (merge s1 (stream-cdr s2))))<br/>
(else<br/>
(cons-stream s1car<br/>
(merge (stream-cdr s1)<br/>
(stream-cdr s2)))))))))<br/></tt></p><p/><p>Em seguida, o fluxo necessário pode ser construído com <tt>merge</tt>, do seguinte modo:</p><p>
</p><p/><p><tt>(define S (cons-stream 1 (merge <<em>??</em>> <<em>??</em>>)))<br/></tt></p><p/><p>Preencha as expressões ausentes nos locais marcados <<em>??</em>> acima.</p><p/><p>
</p><p><a name="%_thm_3.57" id="%_thm_3.57"/>
<b>Exercício 3.57.</b> <a name="%_idx_3900" id="%_idx_3900"/>Quantas adições são realizadas quando computamos o <em>n</em> ésimo número de Fibonacci usando a definição de <tt>fibs</tt> com base no procedimento <tt>add-streams</tt>? Mostre que o número de adições seria exponencialmente maior se tivéssemos implementado <tt>(delay <<em>exp</em>>)</tt> simplesmente como <tt>(lambda () <<em>exp</em>>)</tt>, sem usar a otimização fornecida pelo procedimento <tt>memo-proc</tt> descrito na seção <a href="#%_sec_3.5.1">3.5.1</a>.<a name="call_footnote_Temp_465" href="#footnote_Temp_465" id="call_footnote_Temp_465"><sup><small>64</small></sup></a>
</p><p/><p>
</p><p><a name="%_thm_3.58" id="%_thm_3.58"/>
<b>Exercício 3.58.</b> Faça uma interpretação do fluxo calculado pelo seguinte procedimento:</p><p>
</p><p/><p><tt>(define (expand num den radix)<br/>
(cons-stream<br/>
(quotient (* num radix) den)<br/>
(expand (remainder (* num radix) den) den radix)))<br/></tt></p><p/><p>
<a name="%_idx_3906" id="%_idx_3906"/><a name="%_idx_3908" id="%_idx_3908"/>(<tt>Quotient</tt> é uma primitiva que retorna o quociente inteiro de dois inteiros). Quais são os elementos sucessivos produzidos por <tt>(expand 1 7 10)</tt> ? O que é produzido por <tt>(expand 3 8 10)</tt> ?</p><p/><p>
</p><p><a name="%_thm_3.59" id="%_thm_3.59"/>
<b>Exercício 3.59.</b> <a name="%_idx_3910" id="%_idx_3910"/><a name="%_idx_3912" id="%_idx_3912"/>Na seção <a href="book-Z-H-18.html#%_sec_2.5.3">2.5.3</a> vimos como implementar um sistema aritmético polinomial representando polinômios como listas de termos. De maneira semelhante, podemos trabalhar com <em>série de potência</em>, tal como</p><p>
<a name="%_idx_3914" id="%_idx_3914"/></p><p/><div align="left"><img src="images/ch3-Z-G-36.gif" border="0"/></div><p/><p>
<a name="%_idx_3916" id="%_idx_3916"/></p><p/><div align="left"><img src="images/ch3-Z-G-37.gif" border="0"/></div><p/><p>
<a name="%_idx_3918" id="%_idx_3918"/></p><p/><div align="left"><img src="images/ch3-Z-G-38.gif" border="0"/></div><p/><p>representado como fluxos infinitos. Representaremos a série <em>a</em><sub>0</sub> + <em>a</em><sub>1</sub><em>x</em> + <em>a</em><sub>2</sub><em>x</em><sup>2</sup> + <em>a</em><sub>3</sub><em>x</em><sup>3</sup> + <tt>···</tt> como o fluxo cujos elementos são os coeficientes <em>a</em><sub>0</sub>, <em>a</em><sub>1</sub>, <em>a</em><sub>2</sub>, <em>a</em><sub>3</sub>, <tt>…</tt>.</p><p>
</p><p/><p><a name="%_idx_3920" id="%_idx_3920"/><a name="%_idx_3922" id="%_idx_3922"/>a. A integral da série <em>a</em><sub>0</sub> + <em>a</em><sub>1</sub><em>x</em> + <em>a</em><sub>2</sub><em>x</em><sup>2</sup> + <em>a</em><sub>3</sub><em>x</em><sup>3</sup> + <tt>···</tt> é a série</p><p/><div align="left"><img src="images/ch3-Z-G-39.gif" border="0"/></div><p>Onde <em>c</em> é qualquer constante. Defina um procedimento <a name="%_idx_3924" id="%_idx_3924"/><tt>integrate-series</tt> que toma como entrada um fluxo <em>a</em><sub>0</sub>, <em>a</em><sub>1</sub>, <em>a</em><sub>2</sub>, <tt>…</tt> representando uma série de potências e retorna o fluxo <em>a</em><sub>0</sub>, (1/2)<em>a</em><sub>1</sub>, (1/3)<em>a</em><sub>2</sub>, <tt>…</tt> dos coeficientes dos termos não constantes da integral da série. (Como o resultado não possui termo constante, ele não representa uma série de potências; quando usamos <tt>integrate-series</tt>, usaremos <tt>cons</tt> na constante apropriada).</p><p>
</p><p/><p>b. A função <em>x</em> ⟼ <em>e</em><sup><em>x</em></sup> é sua própria derivada. Isso implica que <em>e</em><sup><em>x</em></sup> e a integral de <em>e</em><sup><em>x</em></sup> são da mesma série, exceto pelo termo constante, que é <em>e</em><sup>0</sup> = 1. Assim, podemos gerar a série para <em>e</em><sup><em>x</em></sup> como</p><p/><p><tt>(define exp-series<br/>
(cons-stream 1 (integrate-series exp-series)))<br/></tt></p><p/><p>Mostre como gerar as séries para seno e cosseno, começando pelos fatos de que a derivada de seno é cosseno e a derivada de cosseno é negativa de seno:</p><p/><p><tt>(define cosine-series<br/>
(cons-stream 1 <<em>??</em>>))<br/>
(define sine-series<br/>
(cons-stream 0 <<em>??</em>>))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.60" id="%_thm_3.60"/>
<b>Exercício 3.60.</b> <a name="%_idx_3926" id="%_idx_3926"/><a name="%_idx_3928" id="%_idx_3928"/><a name="%_idx_3930" id="%_idx_3930"/><a name="%_idx_3932" id="%_idx_3932"/>Com séries de potências representadas como fluxos de coeficientes como no exercício <a href="#%_thm_3.59">3.59</a>, a adição de séries é implementada por <tt>add-streams</tt>. Conclua a definição do seguinte procedimento para multiplicar séries:</p><p/><p><tt>(define (mul-series s1 s2)<br/>
(cons-stream <<em>??</em>> (add-streams <<em>??</em>> <<em>??</em>>)))<br/></tt></p><p/><p>Você pode testar seu procedimento verificando se <em>s</em><em>i</em><em>n</em><sup>2</sup><em>x</em> + <em>c</em><em>o</em><em>s</em><sup>2</sup><em>x</em> = 1, usando a série do exercício <a href="#%_thm_3.59">3.59</a>.</p><p/><p>
</p><p><a name="%_thm_3.61" id="%_thm_3.61"/>
<b>Exercício 3.61.</b> Seja <em>S</em> ser uma série de potência (exercício <a href="#%_thm_3.59">3.59</a>) cujo termo constante é 1. Suponha que queremos encontrar a série de potências 1/<em>S</em>, ou seja, a série <em>X</em> de tal modo que <em>S</em> · <em>X</em> = 1. Escreva <em>S</em> = 1 + <em>S</em><sub><em>R</em></sub> onde <em>S</em><sub><em>R</em></sub> é a parte de <em>S</em> após o termo constante. Então podemos resolver para <em>X</em> do seguinte modo:</p><p/><div align="left"><img src="images/ch3-Z-G-40.gif" border="0"/></div><p>Em outras palavras, <em>X</em> é a série de potências cujo termo constante é 1 e cujos termos de ordem superior são dados pelo negativo de <em>S</em><sub><em>R</em></sub> vezes <em>X</em>. Use essa ideia para escrever um procedimento <tt>invert-unit-series</tt> que calcula 1/<em>S</em> para uma série de potência <em>S</em> com termo constante 1. Você precisará usar <tt>mul-series</tt> do exercício <a href="#%_thm_3.60">3.60</a>.</p><p/><p>
</p><p><a name="%_thm_3.62" id="%_thm_3.62"/>
<b>Exercício 3.62.</b> <a name="%_idx_3934" id="%_idx_3934"/><a name="%_idx_3936" id="%_idx_3936"/><a name="%_idx_3938" id="%_idx_3938"/>Use os resultados dos exercícios <a href="#%_thm_3.60">3.60</a> e <a href="#%_thm_3.61">3.61</a> definir um procedimento <tt>div-series</tt> que divide duas séries de potência. <tt>Div-series</tt> deve funcionar para 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 <tt>div-series</tt> deve sinalizar um erro). Mostre como usar <tt>div-series</tt> com o resultado do exercício <a href="#%_thm_3.59">3.59</a> para gerar <a name="%_idx_3940" id="%_idx_3940"/>a série de potências para tangente.</p><p>
<a name="%_sec_3.5.3" id="%_sec_3.5.3"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.5.3">3.5.3 Explorando o paradigma de fluxo</a></h3><p>
</p><p>Fluxos com avaliação atrasada podem ser uma ferramenta de modelagem poderosa, fornecendo muitos dos benefícios do estado local e da atribuição. Além disso, eles evitam alguns dos embaraços teóricos que acompanham a introdução da atribuição em uma linguagem de programação.</p><p>
<a name="%_idx_3942" id="%_idx_3942"/>A abordagem de fluxo pode ser esclarecedora, pois nos permite criar sistemas com limites de módulo diferentes dos sistemas organizados em torno da atribuição a variáveis de estado. Por exemplo, podemos pensar em uma série temporal (ou sinal) inteira 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.</p><p>
<a name="%_sec_Temp_471" id="%_sec_Temp_471"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_471">Formulando iterações como processos de fluxo</a></h4><p>
<a name="%_idx_3944" id="%_idx_3944"/>Na seção <a href="book-Z-H-11.html#%_sec_1.2.1">1.2.1</a>, introduzimos processos iterativos, que prosseguem atualizando variáveis de estado. Agora sabemos que podemos representar o estado como um fluxo de valores “atemporal”, e não como um conjunto de variáveis a serem atualizadas. Adotaremos essa perspectiva ao revisitar o procedimento de raiz quadrada da seção <a href="book-Z-H-10.html#%_sec_1.1.7">1.1.7</a>. Lembre-se de que a ideia é gerar uma sequência de suposições cada vez melhores para a raiz quadrada de <em>x</em> aplicando repetidamente o procedimento que melhora as suposições:</p><p>
</p><p/><p><tt>(define (sqrt-improve guess x)<br/>
(average guess (/ x guess)))<br/></tt></p><p/><p/><p>
<a name="%_idx_3946" id="%_idx_3946"/>No nosso original procedimento <tt>sqrt</tt>, fizemos essas suposições como os valores sucessivos de uma variável de estado. Em vez disso, podemos gerar um fluxo infinito de palpites, começando com um palpite inicial de 1:<a name="call_footnote_Temp_472" href="#footnote_Temp_472" id="call_footnote_Temp_472"><sup><small>65</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3948" id="%_idx_3948"/>(define (sqrt-stream x)<br/>
(define guesses<br/>
(cons-stream 1.0<br/>
(stream-map (lambda (guess)<br/>
(sqrt-improve guess x))<br/>
guesses)))<br/>
guesses)<br/>
(display-stream (sqrt-stream 2))<br/><i>1.</i><br/><i>1.5</i><br/><i>1.4166666666666665</i><br/><i>1.4142156862745097</i><br/><i>1.4142135623746899</i><br/><tt>...</tt></tt></p><p/><p>Podemos gerar mais e mais termos do fluxo para obter palpites cada vez melhores. Se quisermos, podemos escrever um procedimento que continue gerando termos até que a resposta seja boa o suficiente. (Veja exercício <a href="#%_thm_3.64">3.64</a>).</p><p>
<a name="%_idx_3950" id="%_idx_3950"/><a name="%_idx_3952" id="%_idx_3952"/><a name="%_idx_3954" id="%_idx_3954"/><a name="%_idx_3956" id="%_idx_3956"/><a name="%_idx_3958" id="%_idx_3958"/><a name="%_idx_3960" id="%_idx_3960"/>Outra iteração que podemos tratar da mesma maneira é gerar uma aproximação para π, com base nas séries alternadas que vimos na seção <a href="book-Z-H-12.html#%_sec_1.3.1">1.3.1</a>:</p><p>
</p><p/><div align="left"><img src="images/ch3-Z-G-41.gif" border="0"/></div><p/><p>Primeiro, geramos o fluxo de somandos da série (os recíprocos dos números ímpares, com sinais alternados). Em seguida, tomamos o fluxo de somas de mais e mais termos (usando o procedimento <tt>partial-sums</tt> do exercício <a href="#%_thm_3.55">3.55</a>) e redimensione o resultado em 4:</p><p/><p><tt>(define (pi-summands n)<br/>
(cons-stream (/ 1.0 n)<br/>
(stream-map - (pi-summands (+ n 2)))))<br/><a name="%_idx_3962" id="%_idx_3962"/>(define pi-stream<br/>
(scale-stream (partial-sums (pi-summands 1)) 4))<br/>
(display-stream pi-stream)<br/><i>4.</i><br/><i>2.666666666666667</i><br/><i>3.466666666666667</i><br/><i>2.8952380952380956</i><br/><i>3.3396825396825403</i><br/><i>2.9760461760461765</i><br/><i>3.2837384837384844</i><br/><i>3.017071817071818</i><br/><tt>...</tt></tt></p><p/><p>Isso nos dá um fluxo de aproximações cada vez melhores para π, embora as aproximações convergem bastante lentamente. Oito termos da sequência ligam o valor de π entre 3,284 e 3,017.</p><p>
<a name="%_idx_3964" id="%_idx_3964"/>Até agora, nosso uso da abordagem do fluxo de estados não é muito diferente da atualização de 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 <a name="%_idx_3966" id="%_idx_3966"/><em>acelerador de sequência</em> que converte uma sequência de aproximações em uma nova sequência que converge para o mesmo valor que o original, apenas mais rapidamente.</p><p>Um desses aceleradores, devido ao matemático suíço do século XVIII <a name="%_idx_3968" id="%_idx_3968"/>Leonhard Euler, funciona bem com sequências que são somas parciais de séries alternadas (série de termos com sinais alternados). Na técnica de Euler, se <em>S</em><sub><em>n</em></sub> é o <em>n</em> ésimo termo da sequência da soma original, a sequência acelerada tem termos</p><p/><div align="left"><img src="images/ch3-Z-G-42.gif" border="0"/></div><p>Assim, se a sequência original é representada como um fluxo de valores, a sequência transformada é dada por</p><p>
</p><p/><p><tt><a name="%_idx_3970" id="%_idx_3970"/>(define (euler-transform s)<br/>
(let ((s0 (stream-ref s 0)) <em>; <em>S</em><sub><em>n</em>-1</sub></em><br/>
(s1 (stream-ref s 1)) <em>; <em>S</em><sub><em>n</em></sub></em><br/>
(s2 (stream-ref s 2))) <em>; <em>S</em><sub><em>n</em>+1</sub></em><br/>
(cons-stream (- s2 (/ (square (- s2 s1))<br/>
(+ s0 (* -2 s1) s2)))<br/>
(euler-transform (stream-cdr s)))))<br/></tt></p><p/><p/><p>Podemos demonstrar a aceleração de Euler com nossa sequência de aproximações para π:</p><p>
</p><p/><p><tt>(display-stream (euler-transform pi-stream))<br/><i>3.166666666666667</i><br/><i>3.1333333333333337</i><br/><i>3.1452380952380956</i><br/><i>3.13968253968254</i><br/><i>3.1427128427128435</i><br/><i>3.1408813408813416</i><br/><i>3.142071817071818</i><br/><i>3.1412548236077655</i><br/><tt>...</tt></tt></p><p/><p/><p>Melhor ainda, podemos acelerar a sequência acelerada, e recursivamente, e assim por diante. Ou seja, criamos um fluxo de fluxos (uma estrutura que chamaremos de <a name="%_idx_3972" id="%_idx_3972"/><em>tableau</em>) em que cada fluxo é a transformação do anterior:</p><p>
</p><p/><p><tt><a name="%_idx_3974" id="%_idx_3974"/>(define (make-tableau transform s)<br/>
(cons-stream s<br/>
(make-tableau transform<br/>
(transform s))))<br/></tt></p><p/><p>O tableau possui a forma</p><p>
</p><p/><div align="left"><img src="images/ch3-Z-G-43.gif" border="0"/></div><p>Finalmente, formamos uma sequência, pegando o primeiro termo em cada linha do tableau:</p><p>
</p><p/><p><tt><a name="%_idx_3976" id="%_idx_3976"/>(define (accelerated-sequence transform s)<br/>
(stream-map stream-car<br/>
(make-tableau transform s)))<br/></tt></p><p/><p/><p>Podemos demonstrar esse tipo de “super aceleração” da sequência π:</p><p>
</p><p/><p><tt>(display-stream (accelerated-sequence euler-transform<br/>
pi-stream))<br/><i>4.</i><br/><i>3.166666666666667</i><br/><i>3.142105263157895</i><br/><i>3.141599357319005</i><br/><i>3.1415927140337785</i><br/><i>3.1415926539752927</i><br/><i>3.1415926535911765</i><br/><i>3.141592653589778</i><br/><tt>...</tt></tt></p><p/><p>O resultado é impressionante. Tomar oito termos da sequência produz o valor correto de π a 14 casas decimais. Se tivéssemos usado apenas a sequência π original, precisaríamos calcular na ordem de 10<sup>13</sup> termos (ou seja, expandir a série o suficiente para que os termos individuais sejam inferiores a 10<sup>-13</sup>) para obter tanta precisão! Poderíamos ter implementado essas técnicas de aceleração sem o uso de fluxos. Mas a formulação do fluxo é particularmente elegante e conveniente, pois toda a sequência de estados está disponível para nós como uma estrutura de dados que pode ser manipulada com um conjunto uniforme de operações.</p><p>
</p><p><a name="%_thm_3.63" id="%_thm_3.63"/>
<b>Exercício 3.63.</b> Louis Reasoner pergunta por que o procedimento <tt>sqrt-stream</tt> não foi escrito da seguinte maneira mais direta, sem a variável local <tt>guesses</tt>:</p><p/><p><tt>(define (sqrt-stream x)<br/>
(cons-stream 1.0<br/>
(stream-map (lambda (guess)<br/>
(sqrt-improve guess x))<br/>
(sqrt-stream x))))<br/></tt></p><p/><p>Alyssa P. Hacker responde que esta versão do procedimento é consideravelmente menos eficiente, pois executa computação redundante. Explique a resposta de Alyssa. As duas versões ainda diferem em eficiência se nossa implementação de <tt>delay</tt> usado apenas <tt>(lambda () <<em>exp</em>>)</tt> sem usar a otimização fornecida pelo <tt>memo-proc</tt> (seção <a href="#%_sec_3.5.1">3.5.1</a>)?</p><p/><p>
</p><p><a name="%_thm_3.64" id="%_thm_3.64"/>
<b>Exercício 3.64.</b> Escreva um procedimento <a name="%_idx_3978" id="%_idx_3978"/><tt>stream-limit</tt> que toma como argumento 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 determinada tolerância</p><p/><p><tt><a name="%_idx_3980" id="%_idx_3980"/>(define (sqrt x tolerance)<br/>
(stream-limit (sqrt-stream x) tolerance))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.65" id="%_thm_3.65"/>
<b>Exercício 3.65.</b> <a name="%_idx_3982" id="%_idx_3982"/>Use a série</p><p/><div align="left"><img src="images/ch3-Z-G-44.gif" border="0"/></div><p>para calcular três sequências de aproximações ao logaritmo natural de 2, da mesma maneira que fizemos acima para π. Com que rapidez essas sequências convergem?</p><p>
<a name="%_sec_Temp_476" id="%_sec_Temp_476"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_476">Infinitos fluxos de pares</a></h4><p>
<a name="%_idx_3984" id="%_idx_3984"/><a name="%_idx_3986" id="%_idx_3986"/><a name="%_idx_3988" id="%_idx_3988"/>Na seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>, vimos como o paradigma de sequência lida com laços aninhados tradicionais como processos definidos em sequências de pares. Se generalizarmos essa técnica para fluxos infinitos, podemos escrever programas que não são facilmente representados como laços, pois o “loop” deve variar sobre um conjunto infinito.</p><p>
<a name="%_idx_3990" id="%_idx_3990"/>Por exemplo, suponha que queremos generalizar o procedimento <tt>prime-sum-pairs</tt> da seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a> para produzir o fluxo de pares de <em>todos</em> inteiros (<em>i</em>,<em>j</em>) com <em>i</em><u><</u><em>j</em> de tal modo que <em>i</em> + <em>j</em> é primo. E se <tt>int-pairs</tt> é a sequência de todos os pares de números inteiros (<em>i</em>,<em>j</em>) com <em>i</em><u><</u><em>j</em>, nosso fluxo obrigatório é simplesmente <a name="call_footnote_Temp_477" href="#footnote_Temp_477" id="call_footnote_Temp_477"><sup><small>66.</small></sup></a></p><p>
</p><p/><p><tt>(stream-filter (lambda (pair)<br/>
(prime? (+ (car pair) (cadr pair))))<br/>
int-pairs)<br/></tt></p><p/><p/><p>Nosso problema, então, é produzir o fluxo <tt>int-pairs</tt>. De maneira mais geral, suponha que tenhamos dois fluxos <em>S</em> = (<em>S</em><sub><em>i</em></sub>) e <em>T</em> = (<em>T</em><sub><em>j</em></sub>) e imagine a matriz retangular infinita</p><p/><div align="left"><img src="images/ch3-Z-G-45.gif" border="0"/></div><p>Queremos gerar um fluxo que contenha todos os pares na matriz que se encontrem na diagonal ou acima dela, ou seja, os pares</p><p/><div align="left"><img src="images/ch3-Z-G-46.gif" border="0"/></div><p>(Se levarmos ambos <em>S</em> e <em>T</em> para ser o fluxo de números inteiros, esse será o fluxo desejado <tt>int-pairs</tt>).</p><p>Chame o fluxo geral de pares <tt>(pairs S T)</tt> e considere que ele é composto de três partes: o par (<em>S</em><sub>0</sub>,<em>T</em><sub>0</sub>), o restante dos pares na primeira linha e os pares restantes:<a name="call_footnote_Temp_478" href="#footnote_Temp_478" id="call_footnote_Temp_478"><sup><small>67</small></sup></a>
</p><p/><div align="left"><img src="images/ch3-Z-G-47.gif" border="0"/></div><p>Observe que a terceira peça nesta decomposição (pares que não estão na primeira linha) são (recursivamente) os pares formados a partir de <tt>(stream-cdr S)</tt> e <tt>(stream-cdr T)</tt>. Observe também que a segunda peça (o restante da primeira linha) é</p><p/><p><tt>(stream-map (lambda (x) (list (stream-car s) x))<br/>
(stream-cdr t))<br/></tt></p><p/><p>Assim, podemos formar nosso fluxo de pares da seguinte maneira:</p><p/><p><tt>(define (pairs s t)<br/>
(cons-stream<br/>
(list (stream-car s) (stream-car t))<br/>
(<<em>combine-in-some-way</em>><br/>
(stream-map (lambda (x) (list (stream-car s) x))<br/>
(stream-cdr t))<br/>
(pairs (stream-cdr s) (stream-cdr t)))))<br/></tt></p><p/><p/><p>
<a name="%_idx_3992" id="%_idx_3992"/>Para concluir o procedimento, precisamos escolher uma maneira de combinar os dois fluxos internos. Uma ideia é usar o fluxo analógico do procedimento <tt>append</tt> da seção <a href="book-Z-H-15.html#%_sec_2.2.1">2.2.1</a>:</p><p>
</p><p/><p><tt><a name="%_idx_3994" id="%_idx_3994"/>(define (stream-append s1 s2)<br/>
(if (stream-null? s1)<br/>
s2<br/>
(cons-stream (stream-car s1)<br/>
(stream-append (stream-cdr s1) s2))))<br/></tt></p><p/><p>Isso não é adequado para fluxos infinitos, no entanto, pois ele pega todos os elementos do primeiro fluxo antes de incorporar o segundo fluxo. Em particular, se tentarmos gerar todos os pares de números inteiros positivos usando</p><p>
</p><p/><p><tt>(pairs integers integers)<br/></tt></p><p/><p>nosso fluxo de resultados primeiro tentará percorrer todos os pares com o primeiro número inteiro igual a 1 e, portanto, nunca produzirá pares com qualquer outro valor do primeiro número inteiro.</p><p>Para lidar com fluxos infinitos, precisamos criar uma ordem de combinação que garanta que todos os elementos sejam alcançados se deixarmos que nosso programa seja executado por tempo suficiente. Uma maneira elegante de conseguir isso é com o seguinte procedimento <tt>interleave</tt>:<a name="call_footnote_Temp_479" href="#footnote_Temp_479" id="call_footnote_Temp_479"><sup><small>68</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_4000" id="%_idx_4000"/>(define (interleave s1 s2)<br/>
(if (stream-null? s1)<br/>
s2<br/>
(cons-stream (stream-car s1)<br/>
(interleave s2 (stream-cdr s1)))))<br/></tt></p><p/><p>Uma vez que <tt>interleave</tt> recebe elementos alternadamente dos dois fluxos, todos os elementos do segundo fluxo acabam encontrando seu caminho no fluxo intercalado, mesmo que o primeiro fluxo seja infinito.</p><p>Assim, podemos gerar o fluxo de pares necessário como</p><p/><p><tt><a name="%_idx_4002" id="%_idx_4002"/>(define (pairs s t)<br/>
(cons-stream<br/>
(list (stream-car s) (stream-car t))<br/>
(interleave<br/>
(stream-map (lambda (x) (list (stream-car s) x))<br/>
(stream-cdr t))<br/>
(pairs (stream-cdr s) (stream-cdr t)))))<br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_3.66" id="%_thm_3.66"/>
<b>Exercício 3.66.</b> Examine o fluxo <tt>(pairs integers integers)</tt>. Você pode fazer algum comentário geral sobre a ordem em que os pares são colocados no fluxo? Por exemplo, quantos pares precedem o par (1,100)? o par (99,100)? o par (100,100)? (Se você pode fazer declarações matemáticas precisas aqui, tanto melhor. Mas sinta-se à vontade para dar respostas mais qualitativas se você estiver atolado).</p><p/><p>
</p><p><a name="%_thm_3.67" id="%_thm_3.67"/>
<b>Exercício 3.67.</b> Modifique o procedimento <tt>pairs</tt> para que <tt>(pairs integers integers)</tt> produza o fluxo de <em>todos</em> pares de inteiros (<em>i</em>,<em>j</em>) (sem a condição <em>i</em> <u><</u> <em>j</em>). Dica: você precisará misturar em um fluxo adicional.</p><p/><p>
</p><p><a name="%_thm_3.68" id="%_thm_3.68"/>
<b>Exercício 3.68.</b> Louis Reasoner acha que construir um fluxo de pares de três partes é desnecessariamente complicado. Em vez de separar o par (<em>S</em><sub>0</sub>,<em>T</em><sub>0</sub>) do restante dos pares da primeira linha, ele propõe trabalhar com toda a primeira linha, da seguinte maneira:</p><p/><p><tt>(define (pairs s t)<br/>
(interleave<br/>
(stream-map (lambda (x) (list (stream-car s) x))<br/>
t)<br/>
(pairs (stream-cdr s) (stream-cdr t))))<br/></tt></p><p/><p>Isto funciona? Considere o que acontece se avaliarmos <tt>(pairs integers integers)</tt> usando a definição de Louis de <tt>pairs</tt>.</p><p/><p>
</p><p><a name="%_thm_3.69" id="%_thm_3.69"/>
<b>Exercício 3.69.</b> Escreva um procedimento <tt>triples</tt> que leva três fluxos infinitos, <em>S</em>, <em>T</em> e <em>u</em> e produz o fluxo de triplas (<em>S</em><sub><em>i</em></sub>,<em>T</em><sub><em>j</em></sub>,<em>u</em><sub><em>k</em></sub>) de tal modo que <em>i</em><u><</u><em>j</em><u><</u><em>k</em>. Usar <tt>triples</tt> para gerar o fluxo de todas <a name="%_idx_4004" id="%_idx_4004"/>triplos pitagóricas de números inteiros positivos, ou seja, as triplas (<em>i</em>,<em>j</em>,<em>k</em>) de tal modo que <em>i</em><u><</u><em>j</em> e <em>i</em><sup>2</sup> + <em>j</em><sup>2</sup> = <em>k</em><sup>2</sup>.</p><p/><p>
</p><p><a name="%_thm_3.70" id="%_thm_3.70"/>
<b>Exercício 3.70.</b> <a name="%_idx_4006" id="%_idx_4006"/><a name="%_idx_4008" id="%_idx_4008"/>Seria bom poder gerar fluxos nos quais os pares aparecem em alguma ordem útil, e não na ordem que resulta de um <em>Ad hoc</em> processo de intercalação. Podemos usar uma técnica semelhante ao procedimento <tt>merge</tt> do exercício <a href="#%_thm_3.56">3.56</a>, se definirmos uma maneira de dizer que um par de números inteiros é “menor que” outro. Uma maneira de fazer isso é definir uma “função de ponderação” <em>W</em>(<em>i</em>,<em>j</em>) e estipule que (<em>i</em><sub>1</sub>,<em>j</em><sub>1</sub>) é menos do que (<em>i</em><sub>2</sub>,<em>j</em><sub>2</sub>) se <em>W</em>(<em>i</em><sub>1</sub>,<em>j</em><sub>1</sub>) <<em>W</em>(<em>i</em><sub>2</sub>,<em>j</em><sub>2</sub>) Escreva um procedimento <tt>merge-weighted</tt> isso é como <tt>merge</tt>, exceto que <tt>merge-weighted</tt> leva um argumento adicional <tt>weight</tt>, que é um procedimento que calcula o peso de um par e é usado para determinar a ordem em que os elementos devem aparecer no fluxo mesclado resultante.<a name="call_footnote_Temp_485" href="#footnote_Temp_485" id="call_footnote_Temp_485"><sup><small>69</small></sup></a> Usando isso, generalize <tt>pairs</tt> para um procedimento <tt>weighted-pairs</tt> que utiliza dois fluxos, 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</p><p>
</p><p/><p>a. o fluxo de todos os pares de números inteiros positivos (<em>i</em>,<em>j</em>) com <em>i</em><u><</u><em>j</em> ordenado de acordo com a soma <em>i</em> + <em>j</em></p><p>
</p><p/><p>b. o fluxo de todos os pares de números inteiros positivos (<em>i</em>,<em>j</em>) com <em>i</em><u><</u><em>j</em>, onde nem <em>i</em> nem <em>j</em> é divisível por 2, 3 ou 5 e os pares são ordenados de acordo com a soma 2 <em>i</em> + 3 <em>j</em> + 5 <em>i</em><em>j</em>.</p><p/><p>
</p><p><a name="%_thm_3.71" id="%_thm_3.71"/>
<b>Exercício 3.71.</b> <a name="%_idx_4010" id="%_idx_4010"/>Números que podem ser expressos como a soma de dois cubos de mais de uma maneira são chamados às vezes <em>Números Ramanujan</em>, em homenagem ao matemático Srinivasa Ramanujan.<a name="call_footnote_Temp_487" href="#footnote_Temp_487" id="call_footnote_Temp_487"><sup><small>70</small></sup></a> 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 gerar apenas o fluxo de pares de números inteiros (<em>i</em>,<em>j</em>) ponderada de acordo com a soma <em>i</em><sup>3</sup> + <em>j</em><sup>3</sup> (veja exercício <a href="#%_thm_3.70">3.70</a>), procure no fluxo por dois pares consecutivos com o mesmo peso. Escreva um procedimento para gerar os números Ramanujan. O primeiro número desse tipo é 1.729. Quais são os próximos cinco?</p><p/><p>
</p><p><a name="%_thm_3.72" id="%_thm_3.72"/>
<b>Exercício 3.72.</b> De maneira semelhante ao exercício <a href="#%_thm_3.71">3.71</a> 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).</p><p>
<a name="%_sec_Temp_489" id="%_sec_Temp_489"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_489">Fluxos como sinais</a></h4><p>
<a name="%_idx_4018" id="%_idx_4018"/><a name="%_idx_4020" id="%_idx_4020"/>Iniciamos nossa discussão sobre fluxos descrevendo-os como análogos computacionais dos “sinais” nos sistemas de processamento de sinais. De fato, 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 <a name="%_idx_4022" id="%_idx_4022"/><em>integrador</em> ou <em>somador</em> que, para um fluxo de entrada <em>x</em> = (<em>x</em><sub><em>i</em></sub>), um valor inicial <em>C</em> e um pequeno incremento <em>d</em><em>t</em>, acumula a soma</p><p/><div align="left"><img src="images/ch3-Z-G-48.gif" border="0"/></div><p>e retorna o fluxo de valores <em>S</em> = (<em>S</em><sub><em>i</em></sub>) O seguinte procedimento <tt>integral</tt> lembra a definição de “estilo implícito” do fluxo de números inteiros (seção <a href="#%_sec_3.5.2">3.5.2</a>):</p><p>
</p><p/><p><tt><a name="%_idx_4024" id="%_idx_4024"/>(define (integral integrand initial-value dt)<br/>
(define int<br/>
(cons-stream initial-value<br/>
(add-streams (scale-stream integrand dt)<br/>
int)))<br/>
int)<br/></tt></p><p/><p/><p>
<a name="%_fig_3.32" id="%_fig_3.32"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-49.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.32:</b> O procedimento <tt>integral</tt> visto como um sistema de processamento de sinal.</div></caption><tr><td>
</td></tr></table></div><p/><p>A figura <a href="#%_fig_3.32">3.32</a> é uma imagem de um sistema de processamento de sinal que corresponde ao procedimento <tt>integral</tt>. O fluxo de entrada é dimensionado por <em>d</em><em>t</em> e passou por um adicionador, cuja saída é retornada pelo mesmo adicionador. A auto-referência na definição de <tt>int</tt> é refletido na figura pelo laço de retroalimentação que conecta a saída do somador a uma das entradas.</p><p>
</p><p><a name="%_thm_3.73" id="%_thm_3.73"/>
<b>Exercício 3.73.</b> <a name="%_fig_3.33" id="%_fig_3.33"/></p><p/><div align="left"><table width="100%"><tr><td><div align="center"> <img src="images/ch3-Z-G-50.gif" border="0"/><em>v</em> = <em>v</em><sub>0</sub> + (1/<em>C</em>) ∫<sub>0</sub><sup><em>t</em></sup><em>i</em><em>d</em><em>t</em> + <em>R</em><em>i</em> </div>
<p/><p><img src="images/ch3-Z-G-51.gif" border="0"/></p></td></tr><caption align="bottom"><div align="left"><b>Figura 3.33:</b> Um circuito RC e o diagrama de fluxo de sinal associado.</div></caption><tr><td>
<a name="%_idx_4026" id="%_idx_4026"/>
</td></tr></table></div><p>
<a name="%_idx_4028" id="%_idx_4028"/><a name="%_idx_4030" id="%_idx_4030"/><a name="%_idx_4032" id="%_idx_4032"/>Podemos modelar circuitos elétricos usando fluxos para representar os valores de correntes ou tensões em uma sequência de vezes. Por exemplo, suponha que tenhamos um <em>Circuito RC</em> consistindo de um resistor de resistência <em>R</em> e um capacitor de capacitância <em>C</em> em série. A resposta de tensão <em>v</em> do circuito para uma corrente injetada <em>i</em> é determinada pela fórmula na figura <a href="#%_fig_3.33">3.33</a>, cuja estrutura é mostrada pelo diagrama de fluxo de sinal que o acompanha.</p><p>Escreva um procedimento <tt>RC</tt> que modela esse circuito. <tt>RC</tt> deve tomar como entradas os valores de <em>R</em>, <em>C</em> e <em>d</em><em>t</em> e deve retornar um procedimento que tome como entradas um fluxo representando a corrente <em>i</em> e um valor inicial para a tensão do capacitor <em>v</em><sub>0</sub> e produz como saída o fluxo de tensões <em>v</em>. Por exemplo, você deve poder usar <tt>RC</tt> modelar um circuito RC com <em>R</em> = 5 ohms, <em>C</em> = 1 farad e uma etapa de 0,5 segundo avaliando <tt>(define RC1 (RC 5 1 0.5))</tt>. Isso define <tt>RC1</tt> como um procedimento que utiliza um fluxo que representa a sequência temporal das correntes e uma tensão inicial do capacitor e produz a corrente de saída das tensões.</p><p>
</p><p><a name="%_thm_3.74" id="%_thm_3.74"/>
<b>Exercício 3.74.</b> <a name="%_idx_4034" id="%_idx_4034"/><a name="%_idx_4036" id="%_idx_4036"/>Alyssa P. Hacker projeta um sistema para processar sinais provenientes de sensores físicos. Uma característica importante que ela deseja produzir é um sinal que descreve a <em>cruzamentos de zero</em> 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 em caso contrário. (Suponha que o sinal de uma entrada 0 seja positivo). Por exemplo, um sinal de entrada típico com seu sinal de cruzamento de zero associado seria</p><p/><p><tt><tt>…</tt>1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4 <tt>…</tt><tt>…</tt> 0 0 0 0 0 -1 0 0 0 0 1 0 0 <tt>…</tt></tt></p><p/><p>No sistema da Alyssa, o sinal do sensor é representado como um fluxo <tt>sense-data</tt> e o fluxo <tt>zero-crossings</tt> é o fluxo correspondente de cruzamentos zero. Alyssa primeiro escreve um procedimento <tt>sign-change-detector</tt> que usa 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 cruzamento de zero da seguinte maneira:</p><p>
</p><p/><p><tt>(define (make-zero-crossings input-stream last-value)<br/>
(cons-stream<br/>
(sign-change-detector (stream-car input-stream) last-value)<br/>
(make-zero-crossings (stream-cdr input-stream)<br/>
(stream-car input-stream))))<br/><br/>
(define zero-crossings (make-zero-crossings sense-data 0))<br/></tt></p><p/><p>A chefe de Alyssa, Eva Lu Ator, passa e sugere que esse programa é aproximadamente equivalente ao seguinte, que usa a versão generalizada de <tt>stream-map</tt> do exercício <a href="#%_thm_3.50">3.50</a>:</p><p>
</p><p/><p><tt>(define zero-crossings<br/>
(stream-map sign-change-detector sense-data <<em>expression</em>>))<br/></tt></p><p/><p>Conclua o programa fornecendo as <<em>expression</em>>.</p><p>
</p><p><a name="%_thm_3.75" id="%_thm_3.75"/>
<b>Exercício 3.75.</b> <a name="%_idx_4038" id="%_idx_4038"/><a name="%_idx_4040" id="%_idx_4040"/><a name="%_idx_4042" id="%_idx_4042"/><a name="%_idx_4044" id="%_idx_4044"/>Infelizmente, o detector de cruzamento de zero de Alyssa em exercício <a href="#%_thm_3.74">3.74</a> prova ser insuficiente, pois o sinal ruidoso do sensor leva a cruzamentos de zero espúrios. Lem E. Tweakit, especialista em hardware, sugere que Alyssa suavize o sinal para filtrar o ruído antes de extrair os cruzamentos de zero. Alyssa segue seu conselho e decide extrair os cruzamentos zero do sinal construído calculando a média de cada valor dos dados dos sentidos 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 maneira:</p><p>
</p><p/><p><tt>(define (make-zero-crossings input-stream last-value)<br/>
(let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))<br/>
(cons-stream (sign-change-detector avpt last-value)<br/>
(make-zero-crossings (stream-cdr input-stream)<br/>
avpt))))<br/></tt></p><p/><p>Isso não implementa corretamente o plano de Alyssa. Encontre o erro que o Louis instalou e corrija-o sem alterar a estrutura do programa. (Dica: você precisará aumentar o número de argumentos para <tt>make-zero-crossings</tt>).</p><p>
</p><p><a name="%_thm_3.76" id="%_thm_3.76"/>
<b>Exercício 3.76.</b> <a name="%_idx_4046" id="%_idx_4046"/><a name="%_idx_4048" id="%_idx_4048"/><a name="%_idx_4050" id="%_idx_4050"/><a name="%_idx_4052" id="%_idx_4052"/>Eva Lu Ator critica a abordagem de Louis no exercício <a href="#%_thm_3.75">3.75</a>. O programa que ele escreveu não é modular, pois mistura a operação de suavização com a extração com cruzamento de zero. Por exemplo, o extrator não deve ser trocado se Alyssa encontrar uma maneira melhor de condicionar seu sinal de entrada. Ajude Louis escrevendo um procedimento <tt>smooth</tt> que recebe um fluxo como entrada e produz um fluxo no qual cada elemento é a média de dois elementos sucessivos do fluxo de entrada. Então use <tt>smooth</tt> como um componente para implementar o detector de cruzamento de zero em um estilo mais modular.</p><p>
<a name="%_sec_3.5.4" id="%_sec_3.5.4"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.5.4">3.5.4 Fluxos e avaliação atrasada</a></h3><p>
<a name="%_idx_4054" id="%_idx_4054"/><a name="%_idx_4056" id="%_idx_4056"/>O procedimento <tt>integral</tt> no final da seção anterior mostra como podemos usar fluxos para modelar sistemas de processamento de sinal que contêm <a name="%_idx_4058" id="%_idx_4058"/>loops de retroalimentação. O laço de retroalimentação para o somador mostrado na figura <a href="#%_fig_3.32">3.32</a> é modelado pelo fato de que <tt>integral</tt>é <a name="%_idx_4060" id="%_idx_4060"/>o fluxo interno de <tt>int</tt> é definido em termos de si mesmo:</p><p>
</p><p/><p><tt>(define int<br/>
(cons-stream initial-value<br/>
(add-streams (scale-stream integrand dt)<br/>
int)))<br/></tt></p><p/><p>A capacidade do interpretador de lidar com essa definição implícita depende de <tt>delay</tt> que é incorporado em <tt>cons-stream</tt>. Sem esse <tt>delay</tt>, o interpretador não pôde construir <tt>int</tt> antes de avaliar os dois argumentos para <tt>cons-stream</tt>, o que exigiria que <tt>int</tt> já esteja definido. Em geral, <tt>delay</tt> é crucial para o uso de fluxos para modelar sistemas de processamento de sinal que contêm laços. Sem <tt>delay</tt>, nossos modelos precisariam ser formulados para que as entradas de qualquer componente de processamento de sinal fossem avaliadas completamente antes que a saída pudesse ser produzida. Isso proibiria laços.</p><p>Infelizmente, modelos de fluxo de sistemas com laços podem exigir o uso de <tt>delay</tt> além do <tt>delay</tt> “oculto” fornecido por <tt>cons-stream</tt>. Por exemplo, figura <a href="#%_fig_3.34">3.34</a> mostra um sistema de processamento de sinal para resolver a <a name="%_idx_4062" id="%_idx_4062"/>equação diferencial <em>d</em><em>y</em>/<em>d</em><em>t</em> = <em>f</em>(<em>y</em>) Onde <em>f</em> é uma determinada função. A figura mostra um componente de mapeamento, que aplica <em>f</em> ao seu sinal de entrada, ligado em um laço de realimentação a um integrador de maneira muito semelhante à dos circuitos analógicos de computador que são realmente usados para resolver essas equações.</p><p>
<a name="%_fig_3.34" id="%_fig_3.34"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-52.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.34:</b> Um “circuito analógico de computador” que resolve a equação <em>d</em><em>y</em>/<em>d</em><em>t</em> = <em>f</em>(<em>y</em>)</div></caption><tr><td>
<a name="%_idx_4064" id="%_idx_4064"/>
</td></tr></table></div><p/><p>Supondo que recebemos um valor inicial <em>y</em><sub>0</sub> para <em>y</em>, poderíamos tentar modelar esse sistema usando o procedimento</p><p>
</p><p/><p><tt><a name="%_idx_4066" id="%_idx_4066"/>(define (solve f y0 dt)<br/>
(define y (integral dy y0 dt))<br/>
(define dy (stream-map f y))<br/>
y)<br/></tt></p><p/><p>Este procedimento não funciona, pois na primeira linha de <tt>solve</tt> a chamada para <tt>integral</tt> requer que a entrada <tt>dy</tt> definido, o que não ocorre até a segunda linha de <tt>solve</tt>.</p><p>Por outro lado, a intenção de nossa definição faz sentido, pois podemos, em princípio, começar a gerar o <tt>y</tt> transmitir sem saber <tt>dy</tt>. De fato, <tt>integral</tt> e muitas outras operações de fluxo possuem propriedades semelhantes às de <tt>cons-stream</tt>, pois podemos gerar parte da resposta, fornecendo apenas informações parciais sobre os argumentos. Para <tt>integral</tt>, o primeiro elemento do fluxo de saída é o <tt>initial-value</tt> especificado. Assim, podemos gerar o primeiro elemento do fluxo de saída sem avaliar o integrando <tt>dy</tt>. Uma vez que conhecemos o primeiro elemento de <tt>y</tt>, a <tt>stream-map</tt> na segunda linha de <tt>solve</tt> pode começar a trabalhar para gerar o primeiro elemento de <tt>dy</tt>, que produzirá o próximo elemento de <tt>y</tt>, e assim por diante.</p><p>Para tirar proveito dessa ideia, redefiniremos <tt>integral</tt> para esperar o fluxo do integrando seja um <a name="%_idx_4068" id="%_idx_4068"/><a name="%_idx_4070" id="%_idx_4070"/><a name="%_idx_4072" id="%_idx_4072"/><em>argumento atrasado</em>. <tt>Integral</tt> usará <tt>force</tt> no integrando a ser avaliado apenas quando for necessário gerar mais do que o primeiro elemento do fluxo de saída:</p><p>
</p><p/><p><tt><a name="%_idx_4074" id="%_idx_4074"/>(define (integral delayed-integrand initial-value dt)<br/>
(define int<br/>
(cons-stream initial-value<br/>
(let ((integrand (force delayed-integrand)))<br/>
(add-streams (scale-stream integrand dt)<br/>
int))))<br/>
int)<br/></tt></p><p/><p>Agora podemos implementar nosso procedimento <tt>solve</tt> adiando a avaliação de <tt>dy</tt> na definição de <tt>y</tt>:<a name="call_footnote_Temp_494" href="#footnote_Temp_494" id="call_footnote_Temp_494"><sup><small>71</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_4076" id="%_idx_4076"/>(define (solve f y0 dt)<br/>
(define y (integral (delay dy) y0 dt))<br/>
(define dy (stream-map f y))<br/>
y)<br/></tt></p><p/><p>Em geral, todo chamador de <tt>integral</tt> deve agora aplicar <tt>delay</tt> no argumento do integrando. Podemos demonstrar que o procedimento <tt>solve</tt> funciona aproximando <a name="%_idx_4078" id="%_idx_4078"/><em>e</em> ≈ 2,718 calculando o valor em <em>y</em> = 1 da solução da equação diferencial <em>d</em><em>y</em>/<em>d</em><em>t</em> = <em>y</em> com condição inicial <em>y</em>(0) = 1:</p><p>
</p><p/><p><tt>(stream-ref (solve (lambda (y) y) 1 0.001) 1000)<br/><i>2.716924</i></tt></p><p/><p/><p>
</p><p><a name="%_thm_3.77" id="%_thm_3.77"/>
<b>Exercício 3.77.</b> O procedimento <tt>integral</tt> usado acima era análogo à definição “implícita” do fluxo infinito de números inteiros na seção <a href="#%_sec_3.5.2">3.5.2</a>. Como alternativa, podemos dar uma definição de <tt>integral</tt> isso é mais como <tt>integers-starting-from</tt> (também na seção <a href="#%_sec_3.5.2">3.5.2</a>):</p><p>
</p><p/><p><tt><a name="%_idx_4080" id="%_idx_4080"/>(define (integral integrand initial-value dt)<br/>
(cons-stream initial-value<br/>
(if (stream-null? integrand)<br/>
the-empty-stream<br/>
(integral (stream-cdr integrand)<br/>
(+ (* dt (stream-car integrand))<br/>
initial-value)<br/>
dt))))<br/></tt></p><p/><p>Quando usado em sistemas com laços, esse procedimento possui o mesmo problema que nossa versão original do <tt>integral</tt>. Modifique o procedimento para que ele espere o <tt>integrand</tt> como um argumento atrasado e, portanto, pode ser usado no procedimento <tt>solve</tt> mostrado acima.</p><p/><p>
</p><p><a name="%_thm_3.78" id="%_thm_3.78"/>
<b>Exercício 3.78.</b> <a name="%_fig_3.35" id="%_fig_3.35"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-53.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.35:</b> Diagrama de fluxo de sinais para a solução de uma equação diferencial linear de segunda ordem.</div></caption><tr><td>
</td></tr></table></div><p>
<a name="%_idx_4082" id="%_idx_4082"/>Considere o problema de projetar um sistema de processamento de sinais para estudar a equação diferencial linear de segunda ordem homogênea</p><p/><div align="left"><img src="images/ch3-Z-G-54.gif" border="0"/></div><p>O fluxo de saída, modelagem <em>y</em>, é gerado por uma rede que contém um laço. Isso ocorre, pois o valor de <em>d</em><sup>2</sup><em>y</em>/<em>d</em><em>t</em><sup>2</sup> depende dos valores de <em>y</em> e <em>d</em><em>y</em>/<em>d</em><em>t</em> e ambos são determinados integrando <em>d</em><sup>2</sup><em>y</em>/<em>d</em><em>t</em><sup>2</sup>. O diagrama que gostaríamos de codificar é mostrado na figura <a href="#%_fig_3.35">3.35</a>. Escreva um procedimento <tt>solve-2nd</tt> que toma como argumentos as constantes <em>a</em>, <em>b</em> e <em>d</em><em>t</em> e os valores iniciais <em>y</em><sub>0</sub> e <em>d</em><em>y</em><sub>0</sub> para <em>y</em> e <em>d</em><em>y</em>/<em>d</em><em>t</em> e gera o fluxo de valores sucessivos de <em>y</em>.</p><p/><p>
</p><p><a name="%_thm_3.79" id="%_thm_3.79"/>
<b>Exercício 3.79.</b> <a name="%_idx_4084" id="%_idx_4084"/>Generalize o procedimento <tt>solve-2nd</tt> do exercício <a href="#%_thm_3.78">3.78</a> para que possa ser usado para resolver equações diferenciais gerais de segunda ordem <em>d</em><sup>2</sup><em>y</em>/<em>d</em><em>t</em><sup>2</sup> = <em>f</em>(<em>d</em><em>y</em>/<em>d</em><em>t</em>, <em>y</em>)</p><p/><p>
</p><p><a name="%_thm_3.80" id="%_thm_3.80"/>
<b>Exercício 3.80.</b> <a name="%_idx_4086" id="%_idx_4086"/><a name="%_idx_4088" id="%_idx_4088"/><a name="%_idx_4090" id="%_idx_4090"/>Um <em>circuito RLC série</em> consiste em um resistor, um capacitor e um indutor conectados em série, como mostrado na figura <a href="#%_fig_3.36">3.36</a>. E se <em>R</em>, <em>L</em> e <em>C</em> são a resistência, indutância e capacitância, as relações entre a tensão (<em>v</em>) e atual (<em>i</em>) para os três componentes são descritos pelas equações</p><p/><div align="left"><img src="images/ch3-Z-G-55.gif" border="0"/></div><p>
</p><p>e as conexões do circuito ditam as relações</p><p/><div align="left"><img src="images/ch3-Z-G-56.gif" border="0"/></div><p>A combinação dessas equações mostra que o estado do circuito (resumido em <em>v</em><sub><em>C</em></sub>, a tensão no capacitor e <em>i</em><sub><em>L</em></sub>, a corrente no indutor) é descrita pelo par de equações diferenciais</p><p/><div align="left"><img src="images/ch3-Z-G-57.gif" border="0"/></div><p>O diagrama de fluxo de sinal que representa este sistema de equações diferenciais é mostrado na figura <a href="#%_fig_3.37">3.37</a>.<a name="%_fig_3.36" id="%_fig_3.36"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-58.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.36:</b> Um circuito RLC em série.</div></caption><tr><td>
</td></tr></table></div><p>
<a name="%_fig_3.37" id="%_fig_3.37"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-59.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.37:</b> Um diagrama de fluxo de sinal para a solução de um circuito RLC em série.</div></caption><tr><td>
</td></tr></table></div><p/><p>Escreva um procedimento <tt>RLC</tt> que toma como argumentos os parâmetros <em>R</em>, <em>L</em> e <em>C</em> do circuito e o incremento de tempo <em>d</em><em>t</em>. De maneira semelhante à do procedimento <tt>RC</tt> do exercício <a href="#%_thm_3.73">3.73</a>, <tt>RLC</tt> deve produzir um procedimento que aceite os valores iniciais das variáveis de estado, <em>v</em><sub><em>C</em><sub>0</sub></sub> e <em>i</em><sub><em>L</em><sub>0</sub></sub> e produz um par (usando <tt>cons</tt>) dos fluxos de estados <em>v</em><sub><em>C</em></sub> e <em>i</em><sub><em>L</em></sub>. Usando <tt>RLC</tt>, gere o par de fluxos que modela o comportamento de um circuito RLC em série com <em>R</em> = 1 ohm, <em>C</em> = 0,2 farad, <em>L</em> = 1 henry, <em>d</em><em>t</em> = 0,1 segundo e valores iniciais <em>i</em><sub><em>L</em><sub>0</sub></sub> = 0 amperes e <em>v</em><sub><em>C</em><sub>0</sub></sub> = 10 volts.</p><p>
</p><p>
<a name="%_sec_Temp_499" id="%_sec_Temp_499"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_499">Avaliação de ordem normal</a></h4><p>
<a name="%_idx_4092" id="%_idx_4092"/><a name="%_idx_4094" id="%_idx_4094"/>Os exemplos nesta seção ilustram como o uso explícito de <tt>delay</tt> e <tt>force</tt> fornece excelente flexibilidade de programação, mas os mesmos exemplos também mostram como isso pode tornar nossos programas mais complexos. Nosso novo procedimento <tt>integral</tt>, por exemplo, nos dá o poder de modelar sistemas com laços, mas agora devemos lembrar que <tt>integral</tt> deve ser chamado com um integrando atrasado e todos os procedimentos que usam <tt>integral</tt> deve estar ciente disso. Com efeito, criamos duas classes de procedimentos: procedimentos comuns e procedimentos que levam argumentos atrasados. Em geral, a criação de classes de procedimentos separadas nos obriga a criar classes separadas de procedimentos de ordem superior.<a name="call_footnote_Temp_500" href="#footnote_Temp_500" id="call_footnote_Temp_500"><sup><small>72</small></sup></a></p><p>Uma maneira de evitar a necessidade de duas classes diferentes de procedimentos é fazer com que todos os procedimentos tomem argumentos atrasados. Poderíamos adotar um modelo de avaliação no qual 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 a avaliação de ordem normal, descrita pela primeira vez quando introduzimos o modelo de substituição para avaliação na seção <a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>. A conversão para avaliação em ordem normal fornece uma maneira uniforme e elegante de simplificar o uso de avaliação atrasada, e essa seria uma estratégia natural a ser adotada se estivéssemos preocupados apenas com o processamento em fluxo. Na seção <a href="book-Z-H-27.html#%_sec_4.2">4.2</a>, depois de estudarmos o avaliador, veremos como transformar nossa linguagem dessa maneira. Infelizmente, a inclusão de atrasos nos procedimentos causa estragos em nossa capacidade de projetar programas que dependem da ordem dos eventos, como programas que usam atribuição, modificam dados ou executam entrada ou saída. Até o único <tt>delay</tt> em <tt>cons-stream</tt> pode causar grande confusão, como ilustrado pelos exercícios <a href="#%_thm_3.51">3.51</a> e <a href="#%_thm_3.52">3.52</a>. Tanto quanto se sabe, a mutabilidade e a avaliação atrasada não se misturam bem nas linguagens de programação, e a criação de maneiras de lidar com as duas ao mesmo tempo é uma área ativa de pesquisa.<a name="%_sec_3.5.5" id="%_sec_3.5.5"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.5.5">3.5.5 Modularidade de programas funcionais e modularidade de objetos</a></h3><p>
<a name="%_idx_4116" id="%_idx_4116"/><a name="%_idx_4118" id="%_idx_4118"/>Como vimos na seção <a href="book-Z-H-20.html#%_sec_3.1.2">3.1.2</a>, um dos principais benefícios da introdução de atribuição é que podemos aumentar a modularidade de nossos sistemas encapsulando ou ocultando partes do estado de um grande sistema em variáveis locais. Os modelos de fluxo podem fornecer uma modularidade equivalente sem o uso de atribuição. Como uma <a name="%_idx_4120" id="%_idx_4120"/><a name="%_idx_4122" id="%_idx_4122"/>ilustração, podemos reimplementar a estimativa de Monte Carlo de π, que examinamos na seção <a href="book-Z-H-20.html#%_sec_3.1.2">3.1.2</a>, do ponto de vista do processamento de fluxo.</p><p>O principal problema de modularidade era que desejávamos ocultar o estado interno de um gerador de números aleatórios de programas que usavam números aleatórios. Começamos com um procedimento <tt>rand-update</tt>, cujos valores sucessivos forneceram nosso suprimento de números aleatórios e o usaram para produzir um gerador de números aleatórios:</p><p>
</p><p/><p><tt>(define rand<br/>
(let ((x random-init))<br/>
(lambda ()<br/>
(set! x (rand-update x))<br/>
x)))<br/></tt></p><p/><p/><p>Na formulação de fluxo, não há gerador de números aleatórios <em>per se</em>, apenas um fluxo de números aleatórios produzidos por chamadas sucessivas para <tt>rand-update</tt>:</p><p>
</p><p/><p><tt><a name="%_idx_4124" id="%_idx_4124"/><a name="%_idx_4126" id="%_idx_4126"/>(define random-numbers<br/>
(cons-stream random-init<br/>
(stream-map rand-update random-numbers)))<br/></tt></p><p/><p>Usamos isso para construir o fluxo de resultados do experimento Cesàro realizado em pares consecutivos no fluxo de <tt>random-numbers</tt>:</p><p>
</p><p/><p><tt><a name="%_idx_4128" id="%_idx_4128"/>(define cesaro-stream<br/>
(map-successive-pairs (lambda (r1 r2) (= (gcd r1 r2) 1))<br/>
random-numbers))<br/><br/><a name="%_idx_4130" id="%_idx_4130"/>(define (map-successive-pairs f s)<br/>
(cons-stream<br/>
(f (stream-car s) (stream-car (stream-cdr s)))<br/>
(map-successive-pairs f (stream-cdr (stream-cdr s)))))<br/></tt></p><p/><p>O <tt>cesaro-stream</tt> agora é alimentado a um procedimento <tt>monte-carlo</tt>, que produz um fluxo de estimativas de probabilidades. Os resultados são então convertidos em um fluxo de estimativas de π. Esta versão do programa não precisa de um parâmetro informando quantas tentativas executar. Melhores estimativas de π (com a realização de mais experimentos) são obtidas olhando mais para o fluxo de <tt>pi</tt>:</p><p>
</p><p/><p><tt><a name="%_idx_4132" id="%_idx_4132"/>(define (monte-carlo experiment-stream passed failed)<br/>
(define (next passed failed)<br/>
(cons-stream<br/>
(/ passed (+ passed failed))<br/>
(monte-carlo<br/>
(stream-cdr experiment-stream) passed failed)))<br/>
(if (stream-car experiment-stream)<br/>
(next (+ passed 1) failed)<br/>
(next passed (+ failed 1))))<br/><br/>
(define pi<br/>
(stream-map (lambda (p) (sqrt (/ 6 p)))<br/>
(monte-carlo cesaro-stream 0 0)))<br/></tt></p><p/><p>
<a name="%_idx_4134" id="%_idx_4134"/>Existe uma modularidade considerável nessa abordagem, pois ainda podemos formular um procedimento <tt>monte-carlo</tt> que pode lidar com experimentos arbitrários. No entanto, não há atribuição ou estado local.</p><p>
</p><p><a name="%_thm_3.81" id="%_thm_3.81"/>
<b>Exercício 3.81.</b> <a name="%_idx_4136" id="%_idx_4136"/>Exercício <a href="book-Z-H-20.html#%_thm_3.6">3.6</a> discutiu a generalização do gerador de números aleatórios para permitir que se reinicie a sequência de números aleatórios, de modo a 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 <tt>generate</tt>, gerar, um novo número aleatório ou para usar <tt>reset</tt> na 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.</p><p/><p>
</p><p><a name="%_thm_3.82" id="%_thm_3.82"/>
<b>Exercício 3.82.</b> <a name="%_idx_4138" id="%_idx_4138"/><a name="%_idx_4140" id="%_idx_4140"/><a name="%_idx_4142" id="%_idx_4142"/>Refaça o exercício <a href="book-Z-H-20.html#%_thm_3.5">3.5</a> na integração de Monte Carlo em termos de fluxos. A versão do fluxo de <tt>estimate-integral</tt> não terá um argumento dizendo quantas tentativas executar. Em vez disso, produzirá um fluxo de estimativas com base em sucessivamente mais tentativas.</p><p/><p>
<a name="%_sec_Temp_503" id="%_sec_Temp_503"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_503">Uma visão de programação funcional do tempo</a></h4><p>
<a name="%_idx_4144" id="%_idx_4144"/><a name="%_idx_4146" id="%_idx_4146"/>Voltemos agora às questões dos objetos e do estado levantados no início deste capítulo e os examinemos sob uma nova luz. Introduzimos objetos de atribuição e 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 local e usamos atribuição para modificar essas variáveis. Modelamos o comportamento temporal dos objetos no mundo pelo comportamento temporal dos objetos computacionais correspondentes.</p><p>Agora vimos que os fluxos fornecem uma maneira alternativa de modelar objetos com o estado local. Podemos modelar uma quantidade variável, como o estado local de algum objeto, usando um fluxo que represente o histórico de estados sucessivos. Em essência, representamos o tempo explicitamente, usando fluxos, para dissociar o tempo em nosso mundo simulado da sequência de eventos que ocorrem durante a avaliação. De fato, devido à presença de <tt>delay</tt> pode haver pouca relação entre o tempo simulado no modelo e a ordem dos eventos durante a avaliação.</p><p>Para contrastar essas duas abordagens de modelagem, reconsideraremos a implementação de um “processador de retirada” que <a name="%_idx_4148" id="%_idx_4148"/>monitora o saldo em uma conta bancária. Na seção <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a> implementamos uma versão simplificada desse processador:</p><p>
</p><p/><p><tt><a name="%_idx_4150" id="%_idx_4150"/>(define (make-simplified-withdraw balance)<br/>
(lambda (amount)<br/>
(set! balance (- balance amount))<br/>
balance))<br/></tt></p><p/><p>Chamadas para <tt>make-simplified-withdraw</tt> produzir objetos computacionais, cada um com uma variável de estado local <tt>balance</tt> que é diminuído por chamadas sucessivas ao objeto. O objeto leva um <tt>amount</tt> como argumento e retorna o novo saldo. Podemos imaginar o usuário de uma conta bancária digitando uma sequência de entradas para esse objeto e observando a sequência de valores retornados mostrados em uma tela de exibição.</p><p>Como alternativa, podemos modelar um processador de retirada como um procedimento que usa como entrada um saldo e um fluxo de valores a serem retirados e produz o fluxo de saldos sucessivos na conta:</p><p>
</p><p/><p><tt><a name="%_idx_4152" id="%_idx_4152"/>(define (stream-withdraw balance amount-stream)<br/>
(cons-stream<br/>
balance<br/>
(stream-withdraw (- balance (stream-car amount-stream))<br/>
(stream-cdr amount-stream))))<br/></tt></p><p/><p>
<tt>Stream-withdraw</tt> implementa uma função matemática bem definida cuja saída é totalmente determinada por sua entrada. Suponha, no entanto, que a entrada <tt>amount-stream</tt> é o fluxo de valores sucessivos digitados pelo usuário e o fluxo de saldos resultante é exibido. Então, da perspectiva do usuário que digita valores e assistindo aos resultados, o processo de fluxo possui o mesmo comportamento que o objeto criado por <tt>make-simplified-withdraw</tt>. No entanto, com a versão do fluxo, não há atribuição, variável de estado local e, consequentemente, nenhuma das dificuldades teóricas que encontramos <a name="%_idx_4154" id="%_idx_4154"/>na seção <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a>. No entanto, o sistema possui estado!</p><p>Isso é realmente notável. Apesar de <tt>stream-withdraw</tt> implementar uma função matemática bem definida, cujo comportamento não muda, a percepção do usuário aqui é a de interagir com um sistema que possui um estado de 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.<a name="call_footnote_Temp_504" href="#footnote_Temp_504" id="call_footnote_Temp_504"><sup><small>73</small></sup></a></p><p>Do ponto de vista de uma parte de um processo complexo, as outras partes parecem mudar com o tempo. Eles ocultaram o estado local variável em tempo. Se desejamos escrever programas que modelam esse tipo de decomposição natural em nosso mundo (como o vemos do ponto de vista como parte desse mundo) com estruturas em nosso computador, criamos objetos computacionais que não são funcionais – eles devem mudar com o tempo. Modelamos o estado com variáveis de estado local e modelamos as mudanças de estado com atribuições para essas variáveis. Ao fazer isso, reduzimos o tempo de execução de um modelo de computação no mundo em que fazemos parte e, assim, obtemos “objetos” em nosso computador.</p><p>Modelar com objetos é poderoso e intuitivo, principalmente, pois 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 vários processos. A possibilidade de evitar esses problemas estimulou o desenvolvimento de <a name="%_idx_4158" id="%_idx_4158"/><a name="%_idx_4160" id="%_idx_4160"/><em>linguagens de programação funcional</em>, que não incluem nenhuma disposição 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 <a name="%_idx_4162" id="%_idx_4162"/><a name="%_idx_4164" id="%_idx_4164"/>atraente para lidar com sistemas concorrentes.<a name="call_footnote_Temp_505" href="#footnote_Temp_505" id="call_footnote_Temp_505"><sup><small>74</small></sup></a></p><p>Por outro lado, se olharmos atentamente, também podemos ver problemas relacionados ao tempo se infiltrando em modelos funcionais. 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 permita contas bancárias conjuntas. Em um sistema convencional usando atribuição e objetos, modelaríamos o fato de Peter e Paul compartilharem uma conta, solicitando que Peter e Paul enviassem suas solicitações de transação para o mesmo objeto de conta bancária, como vimos na seção <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a>. Do ponto de vista do fluxo, onde não há “objetos” <em>per se</em>, 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. Dessa forma, poderíamos modelar o fato de Peter e Paul terem uma conta bancária conjunta, mesclando o fluxo de solicitações de transação de Peter com o fluxo de solicitações de Paul e alimentando o resultado ao processo de fluxo de conta bancária, conforme mostrado na figura <a href="#%_fig_3.38">3.38</a>.</p><p>
<a name="%_fig_3.38" id="%_fig_3.38"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-60.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.38:</b> Uma conta bancária conjunta, modelada pela fusão de dois fluxos de solicitações de transação.</div></caption><tr><td>
<a name="%_idx_4176" id="%_idx_4176"/></td></tr></table></div><p/><p>
<a name="%_idx_4178" id="%_idx_4178"/>O problema com esta formulação está na noção de <em>mesclagem</em>. Não é necessário mesclar os dois fluxos simplesmente aceitando alternadamente uma solicitação de Peter e uma solicitação de Paul. Suponha que Paul acesse a conta apenas muito raramente. Dificilmente poderíamos forçar Peter a esperar Paul acessar a conta antes que ele pudesse emitir uma segunda transação. No entanto, essa mesclagem é implementada, e deve intercalar os dois fluxos de transação de alguma forma que seja restringida pelo “tempo real”, conforme percebido por Peter e Paul, no sentido de que, se Peter e Paul se encontrarem, eles podem concordar que certas transações foram realizadas. processados antes da reunião e outras transações foram processadas após a reunião.<a name="call_footnote_Temp_506" href="#footnote_Temp_506" id="call_footnote_Temp_506"><sup><small>75</small></sup></a> Esta é precisamente a mesma restrição com a qual tivemos que lidar na seção <a href="book-Z-H-23.html#%_sec_3.4.1">3.4.1</a>, onde descobrimos a necessidade de introduzir sincronização explícita para garantir uma ordem “correta” de eventos no processamento concorrente de objetos com estado. Assim, na tentativa de suportar o estilo funcional, a necessidade de mesclar entradas de diferentes agentes reintroduz os mesmos problemas que o estilo funcional deveria eliminar.</p><p>Começamos este capítulo com o objetivo de construir modelos computacionais cuja estrutura corresponde à nossa percepção do mundo real que tentamos modelar. Podemos modelar o mundo como uma coleção de objetos separados, com limite de tempo e em interação com o estado, ou podemos modelar o mundo como uma unidade única, atemporal e sem estado. Cada visão possui vantagens poderosas, mas nenhuma delas é completamente satisfatória. Uma grande unificação ainda está por surgir.<a name="call_footnote_Temp_507" href="#footnote_Temp_507" id="call_footnote_Temp_507"><sup><small>76</small></sup></a>
</p><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_442" href="#call_footnote_Temp_442" id="footnote_Temp_442"><sup><small>52</small></sup></a> Os físicos às vezes adotam essa visão introduzindo as <a name="%_idx_3728" id="%_idx_3728"/>“linhas do universo” de partículas como um dispositivo para raciocinar sobre movimento. Também já mencionamos (seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>) que essa é a maneira natural de pensar em sistemas de processamento de sinal. Exploraremos as aplicações dos fluxos para processar o sinal na seção <a href="#%_sec_3.5.3">3.5.3</a>.</p><p><a name="footnote_Temp_443" href="#call_footnote_Temp_443" id="footnote_Temp_443"><sup><small>53</small></sup></a> Suponha que temos um predicado <tt>prime?</tt> (por exemplo, como na seção <a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>) que testa a primalidade.</p><p><a name="footnote_Temp_444" href="#call_footnote_Temp_444" id="footnote_Temp_444"><sup><small>54</small></sup></a> Na implementação do MIT, <a name="%_idx_3752" id="%_idx_3752"/><a name="%_idx_3754" id="%_idx_3754"/><a name="%_idx_3756" id="%_idx_3756"/><tt>the-empty-stream</tt> é o mesmo que a lista vazia <tt>'()</tt> e <tt>stream-null?</tt> é o mesmo que <tt>null?</tt>.</p><p><a name="footnote_Temp_445" href="#call_footnote_Temp_445" id="footnote_Temp_445"><sup><small>55</small></sup></a> Isso deve incomodá-lo. O fato de definirmos procedimentos semelhantes para fluxos e listas indica que perdemos alguma abstração subjacente. Infelizmente, para explorar essa abstração, precisaremos exercer um controle mais refinado sobre o processo de avaliação do que atualmente. Discutiremos esse ponto ainda mais no final da seção <a href="#%_sec_3.5.4">3.5.4</a>. Na seção <a href="book-Z-H-27.html#%_sec_4.2">4.2</a>, desenvolveremos uma estrutura que unifica listas e fluxos.</p><p><a name="footnote_Temp_446" href="#call_footnote_Temp_446" id="footnote_Temp_446"><sup><small>56</small></sup></a> Apesar de <tt>stream-car</tt> e <a name="%_idx_3784" id="%_idx_3784"/><a name="%_idx_3786" id="%_idx_3786"/><tt>stream-cdr</tt> poderem ser definidos como procedimentos, <tt>cons-stream</tt> deve ser uma forma especial. E se <tt>cons-stream</tt> era um procedimento, então, de acordo com nosso modelo de avaliação, avaliar <tt>(cons-stream <<em>a</em>> <<em>b</em>>)</tt> causaria automaticamente <<em>b</em>> a ser avaliado, que é precisamente o que não queremos que aconteça. Pela mesma razão, <tt>delay</tt> deve ser uma forma especial, embora <tt>force</tt> pode ser um procedimento comum.</p><p><a name="footnote_Temp_448" href="#call_footnote_Temp_448" id="footnote_Temp_448"><sup><small>57</small></sup></a> Os números mostrados aqui realmente não aparecem na expressão atrasada. O que realmente aparece é a expressão original, em um ambiente no qual as variáveis estão ligadas aos números apropriados. Por exemplo, <tt>(+ low 1)</tt> com <tt>low</tt> ligado a 10.000 realmente aparece onde <tt>10001</tt> é mostrado.</p><p><a name="footnote_Temp_450" href="#call_footnote_Temp_450" id="footnote_Temp_450"><sup><small>58</small></sup></a> Existem muitas implementações possíveis de fluxos que não sejam as descritas nesta seção. A avaliação atrasada, que é a chave para tornar os fluxos práticos, era inerente à <a name="%_idx_3806" id="%_idx_3806"/><a name="%_idx_3808" id="%_idx_3808"/>Algol 60's <em>chamada por nome</em> método de passagem de parâmetro. O uso desse mecanismo para implementar fluxos foi descrito pela primeira vez por <a name="%_idx_3810" id="%_idx_3810"/>Landin (1965). A avaliação atrasada de fluxos foi introduzida no Lisp por <a name="%_idx_3812" id="%_idx_3812"/><a name="%_idx_3814" id="%_idx_3814"/>Friedman e Wise (1976). Na sua implementação, <tt>cons</tt> sempre atrasa a avaliação de seus argumentos, para que as listas se comportem automaticamente como fluxos. A otimização de memoização também é conhecida como <a name="%_idx_3816" id="%_idx_3816"/><a name="%_idx_3818" id="%_idx_3818"/><a name="%_idx_3820" id="%_idx_3820"/><a name="%_idx_3822" id="%_idx_3822"/><em>chamada por necessidade</em>. A comunidade Algol se referiria aos nossos objetos atrasados originais como <em>thunks de chamada por nome</em> e para as versões otimizadas como <em>thunks de acordo com a necessidade</em>.</p><p><a name="footnote_Temp_453" href="#call_footnote_Temp_453" id="footnote_Temp_453"><sup><small>59</small></sup></a> Exercícios como <a href="#%_thm_3.51">3.51</a> e <a href="#%_thm_3.52">3.52</a> são valiosos para testar nossa compreensão de como <tt>delay</tt> trabalho. Por outro lado, misturar a avaliação atrasada com a impressão – e, pior ainda, com a atribuição - é extremamente confuso, e os instrutores dos cursos de linguagens de computador tradicionalmente atormentavam seus alunos com perguntas de exame, como as desta seção. Desnecessário dizer que escrever programas que dependem dessas sutilezas é <a name="%_idx_3828" id="%_idx_3828"/>odioso estilo de programação. Parte do poder do processamento de fluxo é que ele nos permite ignorar a ordem em que os eventos realmente acontecem em nossos programas. Infelizmente, é precisamente isso que não podemos nos dar na presença de uma atribuição, o que nos força a nos preocupar com tempo e mudança.</p><p><a name="footnote_Temp_455" href="#call_footnote_Temp_455" id="footnote_Temp_455"><sup><small>60</small></sup></a> Eratóstenes, um século III <font size="-2">A</font>.<font size="-2">C</font>. <a name="%_idx_3846" id="%_idx_3846"/><a name="%_idx_3848" id="%_idx_3848"/>O filósofo grego alexandrino é famoso por fornecer a primeira estimativa precisa da circunferência da Terra, que ele calculou observando sombras lançadas ao meio-dia no dia do solstício de verão. O método do crivo de Eratóstenes, embora antigo, formou a base para crivos de hardware para fins especiais que, até recentemente, eram as ferramentas mais poderosas existentes para localizar primos grandes. Desde os anos 70, no entanto, esses métodos foram substituídos por consequências das <a name="%_idx_3850" id="%_idx_3850"/>técnicas probabilísticas discutidas na seção <a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>.</p><p><a name="footnote_Temp_456" href="#call_footnote_Temp_456" id="footnote_Temp_456"><sup><small>61</small></sup></a> Nomeamos esses números após <a name="%_idx_3858" id="%_idx_3858"/>Peter Henderson, que foi a primeira pessoa a nos mostrar diagramas desse tipo como uma maneira de pensar sobre o processamento de fluxo. Cada linha sólida representa um fluxo de valores sendo transmitidos. A linha tracejada de <tt>car</tt> a <tt>cons</tt> e a <tt>filter</tt> indica que esse é um valor único e não um fluxo.</p><p><a name="footnote_Temp_458" href="#call_footnote_Temp_458" id="footnote_Temp_458"><sup><small>62</small></sup></a> Isso usa a versão generalizada do <tt>stream-map</tt> do exercício <a href="#%_thm_3.50">3.50</a>.</p><p><a name="footnote_Temp_459" href="#call_footnote_Temp_459" id="footnote_Temp_459"><sup><small>63</small></sup></a> Este último ponto é muito sutil e se baseia no fato de que <em>p</em><sub><em>n</em>+1</sub><u><</u><em>p</em><sub><em>n</em></sub><sup>2</sup>. (Aqui, <em>p</em><sub><em>k</em></sub> denota o <em>k</em> ésimo primo). Estimativas como essas são muito difíceis de estabelecer. A prova antiga de <a name="%_idx_3876" id="%_idx_3876"/>Euclides que existe um número infinito de números primos mostra que <em>p</em><sub><em>n</em>+1</sub><u><</u><em>p</em><sub>1</sub><em>p</em><sub>2</sub><tt>···</tt><em>p</em><sub><em>n</em></sub> + 1, e nenhum resultado substancialmente melhor foi comprovado até 1851, quando o matemático russo PL Chebyshev estabeleceu <a name="%_idx_3878" id="%_idx_3878"/><a name="%_idx_3880" id="%_idx_3880"/><a name="%_idx_3882" id="%_idx_3882"/><a name="%_idx_3884" id="%_idx_3884"/>aquele <em>p</em><sub><em>n</em>+1</sub><u><</u> 2<em>p</em><sub><em>n</em></sub> para todos <em>n</em>. Esse resultado, originalmente conjecturado em 1845, é conhecido como <em>postulado de Bertrand</em>. Uma prova pode ser encontrada na seção 22.3 de Hardy e Wright 1960.</p><p><a name="footnote_Temp_465" href="#call_footnote_Temp_465" id="footnote_Temp_465"><sup><small>64</small></sup></a> Este exercício mostra como a chamada por necessidade está intimamente relacionada à <a name="%_idx_3902" id="%_idx_3902"/><a name="%_idx_3904" id="%_idx_3904"/>memoização comum, conforme descrito no exercício <a href="book-Z-H-22.html#%_thm_3.27">3.27</a>. Nesse exercício, usamos a atribuição para construir explicitamente uma tabela local. Nossa otimização de fluxo de acordo com a necessidade por chamada cria efetivamente essa tabela automaticamente, armazenando valores nas partes previamente forçadas do fluxo.</p><p><a name="footnote_Temp_472" href="#call_footnote_Temp_472" id="footnote_Temp_472"><sup><small>65</small></sup></a> Não podemos usar <tt>let</tt> para ligar a variável local <tt>guesses</tt>, pois o valor de <tt>guesses</tt> depende de <tt>guesses</tt> em si. Exercício <a href="#%_thm_3.63">3.63</a> aborda por que queremos uma variável local aqui.</p><p><a name="footnote_Temp_477" href="#call_footnote_Temp_477" id="footnote_Temp_477"><sup><small>66</small></sup></a> Como na seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>, representamos um par de números inteiros como uma lista em vez de um par Lisp.</p><p><a name="footnote_Temp_478" href="#call_footnote_Temp_478" id="footnote_Temp_478"><sup><small>67</small></sup></a> Veja exercício <a href="#%_thm_3.68">3.68</a> para ter uma ideia de por que escolhemos essa decomposição.</p><p><a name="footnote_Temp_479" href="#call_footnote_Temp_479" id="footnote_Temp_479"><sup><small>68</small></sup></a> A declaração precisa da propriedade necessária na ordem da combinação é a seguinte: Deve haver uma função <em>f</em> de dois argumentos, de modo que o par correspondente ao elemento <em>i</em> do primeiro fluxo e elemento <em>j</em> do segundo fluxo aparecerá como número do elemento <em>f</em>(<em>i</em>,<em>j</em>) do fluxo de saída. O truque de usar <tt>interleave</tt> para conseguir isso nos foi mostrado por <a name="%_idx_3996" id="%_idx_3996"/>David Turner, que o empregou na linguagem <a name="%_idx_3998" id="%_idx_3998"/>KRC (Turner, 1981).</p><p><a name="footnote_Temp_485" href="#call_footnote_Temp_485" id="footnote_Temp_485"><sup><small>69</small></sup></a> Exigiremos que a função de ponderação seja tal que o peso de um par aumente à medida que avançamos ao longo de uma linha ou descemos ao longo de uma coluna da matriz de pares.</p><p><a name="footnote_Temp_487" href="#call_footnote_Temp_487" id="footnote_Temp_487"><sup><small>70</small></sup></a> Para citar o obituário de G. H. Hardy de <a name="%_idx_4012" id="%_idx_4012"/><a name="%_idx_4014" id="%_idx_4014"/><a name="%_idx_4016" id="%_idx_4016"/>Ramanujan (Hardy, 1921): “Foi o Sr. Littlewood (acredito) que observou que 'todo número inteiro positivo era um de seus amigos'. Lembro-me de uma vez ir vê-lo quando ele estava deitado doente em Putney. Eu andara de táxi nº 1729 e observei que o número me parecia um tanto monótono e que esperava que não fosse um presságio desfavorável. “Não”, respondeu ele, é um número muito interessante; é o menor número expressável como a soma de dois cubos de duas maneiras diferentes”. O truque de usar pares ponderados para gerar os números de Ramanujan nos foi mostrado por Charles Leiserson.</p><p><a name="footnote_Temp_494" href="#call_footnote_Temp_494" id="footnote_Temp_494"><sup><small>71</small></sup></a> Não é garantido que este procedimento funcione em todas as implementações do Scheme, embora para qualquer implementação exista uma variação simples que funcione. O problema possui a ver com diferenças sutis na maneira como as implementações do Scheme lidam com definições internas. (Veja a seção <a href="book-Z-H-26.html#%_sec_4.1.6">4.1.6</a>).</p><p><a name="footnote_Temp_500" href="#call_footnote_Temp_500" id="footnote_Temp_500"><sup><small>72</small></sup></a> Essa é uma pequena reflexão, em Lisp, das dificuldades que linguagens convencionais fortemente tipadas como <a name="%_idx_4096" id="%_idx_4096"/><a name="%_idx_4098" id="%_idx_4098"/><a name="%_idx_4100" id="%_idx_4100"/><a name="%_idx_4102" id="%_idx_4102"/><a name="%_idx_4104" id="%_idx_4104"/>Pascal tem de lidar com procedimentos de ordem superior. Nessas linguagens, o programador deve especificar os tipos de dados dos argumentos e o resultado de cada procedimento: número, valor lógico, sequência e assim por diante. Consequentemente, não conseguimos expressar uma abstração como “mapear um determinado procedimento <tt>proc</tt> sobre todos os elementos em uma sequência” por um único procedimento de ordem superior, como <tt>stream-map</tt>. Em vez disso, precisaríamos de um procedimento de mapeamento diferente para cada combinação diferente de tipos de dados de argumento e resultado que possam ser especificados para um <tt>proc</tt>. Manter uma noção prática de “tipo de dados” na presença de procedimentos de ordem superior levanta muitos problemas difíceis. Uma maneira de lidar com esse problema é ilustrada pela linguagem ML <a name="%_idx_4106" id="%_idx_4106"/><a name="%_idx_4108" id="%_idx_4108"/><a name="%_idx_4110" id="%_idx_4110"/><a name="%_idx_4112" id="%_idx_4112"/>(Gordon, Milner e Wadsworth 1979), cujos “tipos de dados polimórficos” incluem modelos para transformações de ordem superior entre tipos de dados. Além disso, os tipos de dados para a maioria dos procedimentos no ML nunca são declarados explicitamente pelo programador. Em vez disso, o ML inclui um mecanismo de <a name="%_idx_4114" id="%_idx_4114"/><em>dedução de tipo</em> que usa informações no ambiente para deduzir os tipos de dados para procedimentos recém-definidos.</p><p><a name="footnote_Temp_504" href="#call_footnote_Temp_504" id="footnote_Temp_504"><sup><small>73</small></sup></a> Da mesma forma, na física, quando observamos uma partícula em movimento, dizemos que a posição (estado) da partícula está mudando. No entanto, da perspectiva da partícula, <a name="%_idx_4156" id="%_idx_4156"/>linha do universo no espaço-tempo, não há mudanças envolvidas.</p><p><a name="footnote_Temp_505" href="#call_footnote_Temp_505" id="footnote_Temp_505"><sup><small>74</small></sup></a> John Backus, o inventor de Fortran, deu alta <a name="%_idx_4166" id="%_idx_4166"/><a name="%_idx_4168" id="%_idx_4168"/><a name="%_idx_4170" id="%_idx_4170"/><a name="%_idx_4172" id="%_idx_4172"/><a name="%_idx_4174" id="%_idx_4174"/>visibilidade à programação funcional quando recebeu o prêmio ACM Turing em 1978. Seu discurso de aceitação (Backus 1978) defendeu fortemente a abordagem funcional. Uma boa visão geral da programação funcional é dada em Henderson 1980 e em Darlington, Henderson e Turner 1982.</p><p><a name="footnote_Temp_506" href="#call_footnote_Temp_506" id="footnote_Temp_506"><sup><small>75</small></sup></a> Observe que, para quaisquer dois fluxos, geralmente há mais de uma <a name="%_idx_4180" id="%_idx_4180"/><a name="%_idx_4182" id="%_idx_4182"/>ordem aceitável de intercalação. Assim, tecnicamente, “mesclar” é uma relação e não uma função – a resposta não é uma função determinística das entradas. Já mencionamos (nota de rodapé<a href="book-Z-H-23.html#footnote_Temp_411">39</a>) que o não determinismo é essencial ao lidar com a concorrência. A relação de mesclagem ilustra o mesmo não determinismo essencial, da perspectiva funcional. Na seção <a href="book-Z-H-28.html#%_sec_4.3">4.3</a>, veremos o não-determinismo de outro ponto de vista.</p><p><a name="footnote_Temp_507" href="#call_footnote_Temp_507" id="footnote_Temp_507"><sup><small>76</small></sup></a> O modelo de objetos aproxima o mundo dividindo-o em partes separadas. O modelo funcional não modulariza ao longo dos limites do objeto. O modelo de objeto é útil quando <a name="%_idx_4184" id="%_idx_4184"/>o estado não compartilhado dos “objetos” é muito maior que o estado que eles compartilham. Um exemplo de um local em que o ponto de vista do objeto falha é <a name="%_idx_4186" id="%_idx_4186"/>mecânica quântica, onde pensar algo como partículas individuais leva a paradoxos e confusões. Unificar a visão do objeto com a visão funcional pode ter pouco a ver com programação, mas com questões epistemológicas fundamentais.</p></div>
</body>
</html>