-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-22.html
980 lines (746 loc) · 119 KB
/
book-Z-H-22.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
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
<?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.3" id="%_sec_3.3"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.3">3.3 Modelando com dados mutáveis</a></h2><p>
<a name="%_idx_3128" id="%_idx_3128"/>O capítulo 2 tratou dos dados compostos como um meio para construir objetos computacionais que possuem várias partes, a fim de modelar objetos do mundo real que possuem vários aspectos. Nesse capítulo, introduzimos a disciplina de abstração de dados, segundo a qual as estruturas de dados são especificadas em termos de construtores, que criam objetos de dados e seletores, que acessam as partes dos objetos de dados compostos. Mas agora sabemos que há outro aspecto dos dados que o capítulo 2 não abordou. O desejo de modelar sistemas compostos por objetos que mudam de estado nos leva à necessidade de modificar objetos de dados compostos, bem como construir e selecionar a partir deles. Para modelar objetos compostos com mudança de estado, projetaremos abstrações de dados para incluir, além de seletores e construtores, operações chamadas <a name="%_idx_3130" id="%_idx_3130"/><em>mutadores</em>, que modificam objetos de dados. Por exemplo, modelar um sistema bancário exige que alteremos os saldos das contas. Assim, uma estrutura de dados para representar contas bancárias pode admitir uma operação</p><p>
</p><p/><p><tt>(set-balance! <<em>account</em>> <<em>new-value</em>>)<br/></tt></p><p/><p>que altera o saldo da conta designada para o novo valor designado. Os objetos de dados para os quais os mutadores estão definidos são conhecidos como <em>objetos de dados mutáveis </em>.</p><p>O capítulo 2 introduziu os pares como uma “cola” de uso geral para sintetizar dados compostos. Começamos esta seção definindo mutadores básicos para pares, para que os pares possam servir como blocos de construção para a construção de objetos de dados mutáveis. Esses mutadores aumentam bastante o poder representacional dos pares, permitindo construir estruturas de dados diferentes das sequências e árvores com as quais trabalhamos na seção <a href="book-Z-H-15.html#%_sec_2.2">2.2</a>. Também apresentamos alguns exemplos de simulações nas quais sistemas complexos são modelados como coleções de objetos com o estado local.</p><p>
<a name="%_sec_3.3.1" id="%_sec_3.3.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.3.1">3.3.1 Estrutura da lista mutável</a></h3><p>
<a name="%_idx_3132" id="%_idx_3132"/><a name="%_idx_3134" id="%_idx_3134"/>
<a name="%_idx_3136" id="%_idx_3136"/><a name="%_idx_3138" id="%_idx_3138"/>As operações básicas dos pares - <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt> – podem ser usadas para construir a estrutura da lista e selecionar partes da estrutura da lista, mas eles são incapazes de modificar a estrutura da lista. O mesmo vale para as operações de lista que usamos até agora, como <tt>append</tt> e <tt>list</tt>, pois elas podem ser definidas em termos de <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt>. Para modificar estruturas de lista, precisamos de novas operações.</p><p>
<a name="%_fig_3.12" id="%_fig_3.12"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-13.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.12:</b> Lista <tt>x</tt>: <tt>((a b) c d)</tt> e <tt>y</tt>: <tt>(e f)</tt>.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_fig_3.13" id="%_fig_3.13"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-14.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.13:</b> Efeito de <tt>(set-car! x y)</tt> nas listas da figura <a href="#%_fig_3.12">3.12</a>.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_fig_3.14" id="%_fig_3.14"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-15.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.14:</b> Efeito de <tt>(define z (cons y (cdr x)))</tt> nas listas da figura <a href="#%_fig_3.12">3.12</a>.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_fig_3.15" id="%_fig_3.15"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-16.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.15:</b> Efeito de <tt>(set-cdr! x y)</tt> nas listas da figura <a href="#%_fig_3.12">3.12</a>.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_idx_3140" id="%_idx_3140"/><a name="%_idx_3142" id="%_idx_3142"/><a name="%_idx_3144" id="%_idx_3144"/><a name="%_idx_3146" id="%_idx_3146"/>Os mutadores primitivos para pares são <tt>set-car!</tt> e <tt>set-cdr!</tt>. <tt>Set-car!</tt> recebe dois argumentos, o primeiro dos quais deve ser um par. Ele modifica esse par, substituindo o ponteiro <tt>car</tt> por um ponteiro para o segundo argumento de <tt>set-car!</tt>.<a name="call_footnote_Temp_349" href="#footnote_Temp_349" id="call_footnote_Temp_349"><sup><small>16</small></sup></a></p><p>Como exemplo, suponha que <tt>x</tt> esteja ligado à lista <tt>((a b) c d)</tt> e <tt>y</tt> à lista <tt>(e f)</tt> como ilustrado na figura <a href="#%_fig_3.12">3.12</a>. Avaliando a expressão <tt>(set-car! x y)</tt> modifica o par ao qual <tt>x</tt> está ligado, substituindo seu <tt>car</tt> pelo valor de <tt>y</tt>. O resultado da operação é mostrado na figura <a href="#%_fig_3.13">3.13</a>. A estrutura <tt>x</tt> foi modificada e agora seria impressa como <tt>((e f) c d)</tt>. Os pares que representam a lista <tt>(a b)</tt>, identificados pelo ponteiro que foi substituído, agora são desanexados da estrutura original.<a name="call_footnote_Temp_350" href="#footnote_Temp_350" id="call_footnote_Temp_350"><sup><small>17</small></sup></a></p><p>Compare a figura <a href="#%_fig_3.13">3.13</a> com a figura <a href="#%_fig_3.14">3.14</a>, que ilustra o resultado da execução de <tt>(define z (cons y (cdr x)))</tt> com <tt>x</tt> e <tt>y</tt> ligados às listas originais da figura <a href="#%_fig_3.12">3.12</a>. A variável <tt>z</tt> agora está ligada a um novo par criado pela operação <tt>cons</tt>; a lista à qual <tt>x</tt> está ligada permanece inalterada.</p><p>A operação <tt>set-cdr!</tt> é semelhante a <tt>set-car!</tt>. A única diferença é que o ponteiro <tt>cdr</tt> do par, em vez do ponteiro <tt>car</tt>, é substituído. O efeito da execução de <tt>(set-cdr! x y)</tt> nas listas da figura <a href="#%_fig_3.12">3.12</a> é mostrado na figura <a href="#%_fig_3.15">3.15</a>. Aqui, o ponteiro <tt>cdr</tt> de <tt>x</tt> foi substituído pelo ponteiro para <tt>(e f)</tt>. Além disso, a lista <tt>(c d)</tt>, que costumava ser o <tt>cdr</tt> de <tt>x</tt>, agora é desanexada da estrutura.</p><p>
<a name="%_idx_3158" id="%_idx_3158"/><tt>Cons</tt> cria uma nova estrutura de lista criando novos pares, enquanto <tt>set-car!</tt> e <tt>set-cdr!</tt> modificam os pares existentes. De fato, poderíamos implementar <tt>cons</tt> em termos dos dois mutadores, junto com o procedimento <tt>get-new-pair</tt>, que retorna um novo par que não faz parte de nenhuma lista existente estrutura. Obtemos o novo par, configuramos seus ponteiros <tt>car</tt> e <tt>cdr</tt> para os objetos designados e retornamos o novo par como resultado dos <tt>cons</tt>. <a name="call_footnote_Temp_351" href="#footnote_Temp_351" id="call_footnote_Temp_351"><sup><small>18</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3160" id="%_idx_3160"/>(define (cons x y)<br/>
(let ((new (get-new-pair)))<br/>
(set-car! new x)<br/>
(set-cdr! new y)<br/>
new))<br/></tt></p><p/><p>
</p><p><a name="%_thm_3.12" id="%_thm_3.12"/>
<b>Exercício 3.12.</b> <a name="%_idx_3162" id="%_idx_3162"/>O procedimento a seguir para anexar listas foi introduzido na 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_3164" id="%_idx_3164"/>(define (append x y)<br/>
(if (null? x)<br/>
y<br/>
(cons (car x) (append (cdr x) y))))<br/></tt></p><p/><p>
<tt>Append</tt> forma uma nova lista, sucessivamente aplicando <tt>cons</tt> nos elementos de <tt>x</tt> em <tt>y</tt>. O procedimento <tt>append!</tt> é semelhante ao <tt>append</tt>, mas é um mutador e não um construtor. Ele anexa as listas unindo-as, modificando o par final de <tt>x</tt> para que seu <tt>cdr</tt> seja agora <tt>y</tt>. (É um erro chamar <tt>append!</tt> com um <tt>x</tt> vazio).</p><p>
</p><p/><p><tt><a name="%_idx_3166" id="%_idx_3166"/>(define (append! x y)<br/>
(set-cdr! (last-pair x) y)<br/>
x)<br/></tt></p><p/><p>Aqui <tt>last-pair</tt> é um procedimento que retorna o último par em seu argumento:</p><p>
</p><p/><p><tt><a name="%_idx_3168" id="%_idx_3168"/>(define (last-pair x)<br/>
(if (null? (cdr x))<br/>
x<br/>
(last-pair (cdr x))))<br/></tt></p><p/><p>Considere a interação</p><p>
</p><p/><p><tt>(define x (list 'a 'b))<br/>
(define y (list 'c 'd))<br/>
(define z (append x y))<br/>
z<br/><i>(a b c d)</i><br/>
(cdr x)<br/>
<<em>response</em>><br/>
(define w (append! x y))<br/>
w<br/><i>(a b c d)</i><br/>
(cdr x)<br/>
<<em>response</em>><br/></tt></p><p/><p>Quais são as <<em>response</em>>s ausentes? Desenhe diagramas de caixa e ponteiro para explicar sua resposta.</p><p/><p>
</p><p><a name="%_thm_3.13" id="%_thm_3.13"/>
<b>Exercício 3.13.</b> <a name="%_idx_3170" id="%_idx_3170"/>Considere o procedimento <tt>make-cycle</tt> a seguir, que usa o procedimento <tt>last-pair</tt> definido no exercício <a href="#%_thm_3.12">3.12</a>:</p><p>
</p><p/><p><tt><a name="%_idx_3172" id="%_idx_3172"/>(define (make-cycle x)<br/>
(set-cdr! (last-pair x) x)<br/>
x)<br/></tt></p><p/><p>Desenhe um diagrama de caixa e ponteiro que mostre a estrutura <tt>z</tt> criada por</p><p>
</p><p/><p><tt>(define z (make-cycle (list 'a 'b 'c)))<br/></tt></p><p/><p>O que acontece se tentarmos calcular <tt>(last-pair z)</tt>?</p><p/><p>
</p><p><a name="%_thm_3.14" id="%_thm_3.14"/>
<b>Exercício 3.14.</b> O procedimento a seguir é bastante útil, embora obscuro:</p><p>
</p><p/><p><tt><a name="%_idx_3174" id="%_idx_3174"/>(define (mystery x)<br/>
(define (loop x y)<br/>
(if (null? x)<br/>
y<br/>
(let ((temp (cdr x)))<br/>
(set-cdr! x y)<br/>
(loop temp x))))<br/>
(loop x '()))<br/></tt></p><p/><p>
<tt>Loop</tt> usa a variável “temporária” <tt>temp</tt> para manter o valor antigo do <tt>cdr</tt> de <tt>x</tt>, pois <tt>set-cdr!</tt> na próxima linha destrói o <tt>cdr</tt>. Explique o que <tt>mystery</tt> faz em geral. Suponha que <tt>v</tt> seja definido por <tt>(define v (list 'a 'b 'c 'd))</tt>. Desenhe o diagrama de caixa e ponteiro que representa a lista à qual <tt>v</tt> está ligado. Suponha que agora avaliamos <tt>(define w (mystery v))</tt>. Desenhe diagramas de caixa e ponteiro que mostrem as estruturas <tt>v</tt> e <tt>w</tt> após avaliar esta expressão. O que seria impresso como os valores de <tt>v</tt> e <tt>w</tt>?</p><p>
<a name="%_sec_Temp_355" id="%_sec_Temp_355"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_355">Compartilhamento e identidade</a></h4><p>
<a name="%_idx_3176" id="%_idx_3176"/><a name="%_idx_3178" id="%_idx_3178"/>
<a name="%_idx_3180" id="%_idx_3180"/><a name="%_idx_3182" id="%_idx_3182"/>Mencionamos na seção <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a> as questões teóricas de “igualdade” e “mudança” levantadas pela introdução da atribuição. Esses problemas surgem na prática quando pares individuais são <em>compartilhados</em> entre diferentes objetos de dados. Por exemplo, considere a estrutura formada por</p><p>
</p><p/><p><tt>(define x (list 'a 'b))<br/>
(define z1 (cons x x))<br/></tt></p><p/><p>Conforme mostrado na figura <a href="#%_fig_3.16">3.16</a>, <tt>z1</tt> é um par cujo <tt>car</tt> e <tt>cdr</tt> apontam para o mesmo par <tt>x</tt>. Esse compartilhamento de <tt>x</tt> pelo <tt>car</tt> e <tt>cdr</tt> de <tt>z1</tt> é uma consequência da maneira direta pela qual <tt>cons</tt> é implementado. Em geral, o uso de <tt>cons</tt> para construir listas resultará em uma estrutura interligada de pares, na qual muitos pares individuais são compartilhados por muitas estruturas diferentes.</p><p>
<a name="%_fig_3.16" id="%_fig_3.16"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-17.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.16:</b> A lista <tt>z1</tt> formada por <tt>(cons x x)</tt>.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_fig_3.17" id="%_fig_3.17"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-18.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.17:</b> A lista <tt>z2</tt> formada por <tt>(cons (list 'a 'b) (list 'a 'b))</tt>.</div></caption><tr><td>
</td></tr></table></div><p/><p>Ao contrário da figura <a href="#%_fig_3.16">3.16</a>, a figura <a href="#%_fig_3.17">3.17</a> mostra a estrutura criada por</p><p>
</p><p/><p><tt>(define z2 (cons (list 'a 'b) (list 'a 'b)))<br/></tt></p><p/><p>Nesta estrutura, os pares nas duas listas <tt>(a b)</tt> são distintos, embora os símbolos reais sejam compartilhados.<a name="call_footnote_Temp_356" href="#footnote_Temp_356" id="call_footnote_Temp_356"><sup><small>19</small></sup></a></p><p>Quando considerados como uma lista, <tt>z1</tt> e <tt>z2</tt> representam “a mesma” lista, <tt>((a b) a b)</tt>. Em geral, o compartilhamento é completamente indetectável se operarmos em listas usando apenas <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt>. Entretanto, se permitirmos mutadores na estrutura da lista, o compartilhamento se tornará significativo. Como um exemplo da diferença que o compartilhamento pode fazer, considere o procedimento a seguir, que modifica o <tt>car</tt> da estrutura à qual ele é aplicado:</p><p>
</p><p/><p><tt>(define (set-to-wow! x)<br/>
(set-car! (car x) 'wow)<br/>
x)<br/></tt></p><p/><p>Mesmo que <tt>z1</tt> e <tt>z2</tt> sejam “a mesma” estrutura, a aplicação de <tt>set-to-wow!</tt> a eles gera resultados diferentes. Com <tt>z1</tt>, alterar o <tt>car</tt> também altera o <tt>cdr</tt>, pois em <tt>z1</tt> o <tt>car</tt> e o <tt>cdr</tt> são o mesmo par. Com <tt>z2</tt>, o <tt>car</tt> e o <tt>cdr</tt> são distintos, portanto <tt>set-to-wow!</tt> modifica apenas o <tt>car</tt>:</p><p>
</p><p/><p><tt>z1<br/><i>((a b) a b)</i><br/><br/>
(set-to-wow! z1)<br/><i>((wow b) wow b)</i><br/><br/>
z2<br/><i>((a b) a b)</i><br/><br/>
(set-to-wow! z2)<br/><i>((wow b) a b)</i><br/></tt></p><p/><p/><p>Uma maneira de detectar o compartilhamento em estruturas de lista é usar o predicado <a name="%_idx_3186" id="%_idx_3186"/><a name="%_idx_3188" id="%_idx_3188"/><tt>eq?</tt>, que introduzimos na seção <a href="book-Z-H-16.html#%_sec_2.3.1">2.3.1</a> como uma maneira de teste se dois símbolos são iguais. De maneira mais geral, <tt>(eq? x y)</tt> testa se <tt>x</tt> e <tt>y</tt> são o mesmo objeto (ou seja, se <tt>x</tt> e <tt>y</tt> são iguais como ponteiros). Assim, com <tt>z1</tt> e <tt>z2</tt>, conforme definido nas figuras <a href="#%_fig_3.16">3.16</a> e <a href="#%_fig_3.17">3.17</a>, <tt>(eq? (car z1) (cdr z1))</tt> é verdadeiro e <tt>(eq? (car z2) (cdr z2))</tt> é falso.</p><p>
<a name="%_idx_3190" id="%_idx_3190"/>Como será visto nas seções a seguir, podemos explorar o compartilhamento para estender bastante o repertório de estruturas de dados que podem ser representadas por pares. Por outro lado, o compartilhamento também pode ser perigoso, pois as modificações feitas nas estruturas também afetam outras estruturas que compartilham as partes modificadas. As operações de mutação <tt>set-car!</tt> e <tt>set-cdr!</tt> devem ser usadas com cuidado; a menos que tenhamos um bom entendimento de como nossos objetos de dados são compartilhados, a mutação pode ter resultados imprevistos.<a name="call_footnote_Temp_357" href="#footnote_Temp_357" id="call_footnote_Temp_357"><sup><small>20</small></sup></a></p><p>
</p><p><a name="%_thm_3.15" id="%_thm_3.15"/>
<b>Exercício 3.15.</b> Desenhe diagramas de caixa e ponteiro para explicar o efeito de <tt>set-to-wow!</tt> nas estruturas <tt>z1</tt> e <tt>z2</tt> acima.</p><p/><p>
</p><p><a name="%_thm_3.16" id="%_thm_3.16"/>
<b>Exercício 3.16.</b> Ben Bitdiddle decide escrever um procedimento para contar o número de pares em qualquer estrutura de lista. “É fácil”, ele argumenta. “O número de pares em qualquer estrutura é o número no <tt>car</tt> mais o número no <tt>cdr</tt> mais um para contar o par atual”. Então, Ben escreve o seguinte procedimento:</p><p>
</p><p/><p><tt><a name="%_idx_3192" id="%_idx_3192"/>(define (count-pairs x)<br/>
(if (not (pair? x))<br/>
0<br/>
(+ (count-pairs (car x))<br/>
(count-pairs (cdr x))<br/>
1)))<br/></tt></p><p/><p>Mostre que este procedimento não está correto. Em particular, desenhe diagramas de caixa e ponteiro representando estruturas de lista compostas de exatamente três pares para os quais o procedimento de Ben retornaria 3; retornaria 4; retornaria 7; nunca retornaria.</p><p/><p>
</p><p><a name="%_thm_3.17" id="%_thm_3.17"/>
<b>Exercício 3.17.</b> Crie uma versão correta do procedimento <tt>count-pairs</tt> do exercício <a href="#%_thm_3.16">3.16</a> que retorne o número de pares distintos em qualquer estrutura. (Dica: percorra a estrutura, mantendo uma estrutura de dados auxiliar usada para acompanhar quais pares já foram contados).</p><p/><p>
</p><p>
</p><p><a name="%_thm_3.18" id="%_thm_3.18"/>
<b>Exercício 3.18.</b> <a name="%_idx_3194" id="%_idx_3194"/>Escreva um procedimento que examine uma lista e determine se ela contém um ciclo, ou seja, se um programa que tentou encontrar o fim da lista usando sucessivas <tt>cdr</tt> s entraria em um laço infinito. O exercício <a href="#%_thm_3.13">3.13</a> construiu essas listas.</p><p/><p>
</p><p><a name="%_thm_3.19" id="%_thm_3.19"/>
<b>Exercício 3.19.</b> Refaça o exercício <a href="#%_thm_3.18">3.18</a> usando um algoritmo que ocupa apenas uma quantidade constante de espaço. (Isso requer uma ideia muito inteligente).</p><p>
<a name="%_sec_Temp_363" id="%_sec_Temp_363"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_363">Mutação é apenas atribuição</a></h4><p>
<a name="%_idx_3196" id="%_idx_3196"/><a name="%_idx_3198" id="%_idx_3198"/><a name="%_idx_3200" id="%_idx_3200"/><a name="%_idx_3202" id="%_idx_3202"/>Quando introduzimos dados compostos, observamos na seção <a href="book-Z-H-14.html#%_sec_2.1.3">2.1.3</a> que os pares podem ser representados puramente em termos de procedimentos:</p><p>
</p><p/><p><tt><a name="%_idx_3204" id="%_idx_3204"/>(define (cons x y)<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'car) x)<br/>
((eq? m 'cdr) y)<br/>
(else (error "Undefined operation -- CONS" m))))<br/>
dispatch)<br/><a name="%_idx_3206" id="%_idx_3206"/>(define (car z) (z 'car))<br/><a name="%_idx_3208" id="%_idx_3208"/>(define (cdr z) (z 'cdr))<br/></tt></p><p/><p>A mesma observação é verdadeira para dados mutáveis. Podemos implementar objetos de dados mutáveis como procedimentos usando a atribuição e o estado local. Por exemplo, podemos estender a implementação do par acima para lidar com <tt>set-car!</tt> e <tt>set-cdr!</tt> de maneira análoga à maneira como implementamos contas bancárias usando <tt>make-account</tt> na seção <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>:</p><p>
</p><p/><p><tt><a name="%_idx_3210" id="%_idx_3210"/>(define (cons x y)<br/>
(define (set-x! v) (set! x v))<br/>
(define (set-y! v) (set! y v))<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'car) x)<br/>
((eq? m 'cdr) y)<br/>
((eq? m 'set-car!) set-x!)<br/>
((eq? m 'set-cdr!) set-y!)<br/>
(else (error "Undefined operation -- CONS" m))))<br/>
dispatch)<br/><a name="%_idx_3212" id="%_idx_3212"/>(define (car z) (z 'car))<br/><a name="%_idx_3214" id="%_idx_3214"/>(define (cdr z) (z 'cdr))<br/><a name="%_idx_3216" id="%_idx_3216"/>(define (set-car! z new-value)<br/>
((z 'set-car!) new-value)<br/>
z)<br/><a name="%_idx_3218" id="%_idx_3218"/>(define (set-cdr! z new-value)<br/>
((z 'set-cdr!) new-value)<br/>
z)<br/></tt></p><p/><p/><p>A atribuição é tudo o que é necessário, teoricamente, para explicar o comportamento de dados mutáveis. Assim que admitimos <tt>set!</tt> para a nossa linguagem, levantamos todos os problemas, não apenas de atribuição, mas de dados mutáveis em geral.<a name="call_footnote_Temp_364" href="#footnote_Temp_364" id="call_footnote_Temp_364"><sup><small>21</small></sup></a></p><p>
</p><p><a name="%_thm_3.20" id="%_thm_3.20"/>
<b>Exercício 3.20.</b> Desenhe diagramas de ambiente para ilustrar a avaliação da sequência de expressões</p><p>
</p><p/><p><tt>(define x (cons 1 2))<br/>
(define z (cons x x))<br/>
(set-car! (cdr z) 17)<br/>
(car x)<br/><i>17</i><br/></tt></p><p/><p>usando a implementação processual dos pares dados acima. (Compare o exercício <a href="book-Z-H-21.html#%_thm_3.11">3.11</a>).</p><p>
<a name="%_sec_3.3.2" id="%_sec_3.3.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.3.2">3.3.2 Representando filas</a></h3><p>
<a name="%_idx_3220" id="%_idx_3220"/>Os mutadores <tt>set-car!</tt> e <tt>set-cdr!</tt> nos permitem usar pares para construir estruturas de dados que não podem ser construídas com <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt> sozinho. Esta seção mostra como usar pares para representar uma estrutura de dados chamada fila. A seção <a href="#%_sec_3.3.3">3.3.3</a> mostrará como representar estruturas de dados chamadas tabelas.</p><p>Uma <em>fila</em> é uma sequência na qual os itens são inseridos em uma extremidade (chamada <a name="%_idx_3222" id="%_idx_3222"/><em>traseira</em> da fila) e excluídos da outra extremidade (a <a name="%_idx_3224" id="%_idx_3224"/><em>frente</em>). A figura <a href="#%_fig_3.18">3.18</a> mostra uma fila inicialmente vazia na qual os itens <tt>a</tt> e <tt>b</tt> são inseridos. Em seguida, <tt>a</tt> é removido, <tt>c</tt> e <tt>d</tt> são inseridos e <tt>b</tt> é removido. Como os itens são sempre removidos na ordem em que são inseridos, às vezes uma fila é chamada de buffer <a name="%_idx_3226" id="%_idx_3226"/><em>FIFO</em> (first in, first out), (primeiro a entrar, primeiro a sair), em português.</p><p>
<a name="%_fig_3.18" id="%_fig_3.18"/></p><p/><div align="left"><table width="100%"><tr><td><table border="0"><tr><td valign="top">Operação</td><td valign="top">Fila resultante</td></tr><tr><td valign="top"><tt>(define q (make-queue))</tt> </td><td valign="top"/></tr><tr><td valign="top"><tt>(insert-queue! q 'a)</tt> </td><td valign="top"><tt>a</tt></td></tr><tr><td valign="top"><tt>(insert-queue! q 'b)</tt> </td><td valign="top"><tt>a b</tt></td></tr><tr><td valign="top"><tt>(delete-queue! q)</tt> </td><td valign="top"><tt>b</tt></td></tr><tr><td valign="top"><tt>(insert-queue! q 'c)</tt> </td><td valign="top"><tt>b c</tt></td></tr><tr><td valign="top"><tt>(insert-queue! q 'd)</tt> </td><td valign="top"><tt>b c d</tt></td></tr><tr><td valign="top"><tt>(delete-queue! q)</tt> </td><td valign="top"><tt>c d</tt>
</td></tr></table></td></tr><caption align="bottom"><div align="left"><b>Figura 3.18:</b> Operações da fila.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_idx_3228" id="%_idx_3228"/><a name="%_idx_3230" id="%_idx_3230"/>Em termos de abstração de dados, podemos considerar uma fila conforme definido pelo seguinte conjunto de operações:</p><p/><ul><li>um construtor: <br/><a name="%_idx_3232" id="%_idx_3232"/><tt>(make-queue)</tt><br/> retorna uma fila vazia (uma fila que não contém itens).<p>
</p></li><li>dois seletores: <br/><a name="%_idx_3234" id="%_idx_3234"/><tt>(empty-queue? <<em>queue</em>>)</tt><br/> testa se a fila está vazia. <br/><a name="%_idx_3236" id="%_idx_3236"/><tt>(front-queue <<em>queue</em>>)</tt><br/> retorna o objeto na frente da fila, sinalizando um erro se a fila estiver vazia; isso não modifica a fila.<p>
</p></li><li>dois mutadores: <br/><a name="%_idx_3238" id="%_idx_3238"/><tt>(insert-queue! <<em>queue</em>> <<em>item</em>>)</tt><br/> insere o item na parte traseira da fila e retorna a fila modificada como seu valor. <br/><a name="%_idx_3240" id="%_idx_3240"/><tt>(delete-queue! <<em>queue</em>>)</tt><br/> remove o item na frente da fila e retorna a fila modificada como seu valor, sinalizando um erro se a fila estiver vazia antes da exclusão.</li></ul><p/><p>Como uma fila é uma sequência de itens, certamente poderíamos representá-la como uma lista comum; a frente da fila seria o <tt>car</tt> da lista, inserir um item na fila equivaleria a acrescentar um novo elemento ao final da lista e excluir um item da fila seria apenas tomando o <tt>cdr</tt> da lista. No entanto, essa representação é ineficiente, pois, para inserir um item, precisamos varrer a lista até chegar ao fim. Como o único método que temos para varrer uma lista é por sucessivas operações <tt>cdr</tt>, essa varredura requer θ(<em>n</em>) etapas para uma lista de <em>n</em> itens. Uma modificação simples na representação da lista supera essa desvantagem ao permitir que as operações da fila sejam implementadas de forma que exijam etapas θ(1); isto é, para que o número de etapas necessárias seja independente do comprimento da fila.</p><p>A dificuldade com a representação da lista decorre da necessidade de varrer para encontrar o final da lista. A razão pela qual precisamos varrer é que, embora a maneira padrão de representar uma lista como uma cadeia de pares prontamente nos forneça um ponteiro para o início da lista, ela não nos fornece um ponteiro facilmente acessível para o final. A modificação que evita a desvantagem é representar a fila como uma lista, com um ponteiro adicional que indica o par final na lista. Dessa forma, quando formos inserir um item, podemos consultar o ponteiro traseiro e evitar a varredura da lista.</p><p>Uma fila é representada, então, como um par de ponteiros, <tt>front-ptr</tt> e <tt>rear-ptr</tt>, que indicam, respectivamente, o primeiro e o último pares em uma lista comum. Como queremos que a fila seja um objeto identificável, podemos usar <tt>cons</tt> para combinar os dois ponteiros. Assim, a própria fila será os <tt>cons</tt> dos dois ponteiros. A figura <a href="#%_fig_3.19">3.19</a> ilustra essa representação.</p><p>
<a name="%_fig_3.19" id="%_fig_3.19"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-19.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.19:</b> Implementação de uma fila como uma lista com ponteiros dianteiro e traseiro.</div></caption><tr><td>
</td></tr></table></div><p/><p>Para definir as operações da fila, usamos os seguintes procedimentos, que permitem selecionar e modificar os ponteiros frontal e traseiro de uma fila:</p><p>
</p><p/><p><tt><a name="%_idx_3242" id="%_idx_3242"/>(define (front-ptr queue) (car queue))<br/><a name="%_idx_3244" id="%_idx_3244"/>(define (rear-ptr queue) (cdr queue))<br/><a name="%_idx_3246" id="%_idx_3246"/>(define (set-front-ptr! queue item) (set-car! queue item))<br/><a name="%_idx_3248" id="%_idx_3248"/>(define (set-rear-ptr! queue item) (set-cdr! queue item))<br/></tt></p><p/><p/><p>Agora podemos implementar as operações da fila real. Consideraremos que uma fila está vazia se o ponteiro da frente for a lista vazia:</p><p>
</p><p/><p><tt><a name="%_idx_3250" id="%_idx_3250"/>(define (empty-queue? queue) (null? (front-ptr queue)))<br/></tt></p><p/><p>O construtor <tt>make-queue</tt> retorna, como uma fila inicialmente vazia, um par cujo <tt>car</tt> e <tt>cdr</tt> são a lista vazia:</p><p>
</p><p/><p><tt><a name="%_idx_3252" id="%_idx_3252"/>(define (make-queue) (cons '() '()))<br/></tt></p><p/><p>Para selecionar o item na frente da fila, retornamos o <tt>car</tt> do par indicado pelo ponteiro frontal:</p><p>
</p><p/><p><tt><a name="%_idx_3254" id="%_idx_3254"/>(define (front-queue queue)<br/>
(if (empty-queue? queue)<br/>
(error "FRONT called with an empty queue" queue)<br/>
(car (front-ptr queue))))<br/></tt></p><p/><p/><p>Para inserir um item em uma fila, seguimos o método cujo resultado é indicado na figura <a href="#%_fig_3.20">3.20</a>. Primeiro, criamos um novo par cujo <tt>car</tt> é o item a ser inserido e cujo <tt>cdr</tt> é a lista vazia. Se a fila estava inicialmente vazia, definimos os ponteiros dianteiro e traseiro da fila para esse novo par. Caso contrário, modificamos o par final na fila para apontar para o novo par e também configuramos o ponteiro traseiro para o novo par.</p><p>
<a name="%_fig_3.20" id="%_fig_3.20"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-20.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.20:</b> Resultado do uso de <tt>(insert-queue! q 'd)</tt> na fila da figura <a href="#%_fig_3.19">3.19</a>.</div></caption><tr><td>
</td></tr></table></div><p/><p>
</p><p/><p><tt><a name="%_idx_3256" id="%_idx_3256"/>(define (insert-queue! queue item)<br/>
(let ((new-pair (cons item '())))<br/>
(cond ((empty-queue? queue)<br/>
(set-front-ptr! queue new-pair)<br/>
(set-rear-ptr! queue new-pair)<br/>
queue)<br/>
(else<br/>
(set-cdr! (rear-ptr queue) new-pair)<br/>
(set-rear-ptr! queue new-pair)<br/>
queue)))) <br/></tt></p><p/><p/><p>Para excluir o item na frente da fila, apenas modificamos o ponteiro frontal para que agora aponte para o segundo item da fila, que pode ser encontrado seguindo o ponteiro <tt>cdr</tt> do primeiro item (veja a figura <a href="#%_fig_3.21">3.21</a>):<a name="call_footnote_Temp_366" href="#footnote_Temp_366" id="call_footnote_Temp_366"><sup><small>22</small></sup></a></p><p>
<a name="%_fig_3.21" id="%_fig_3.21"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-21.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.21:</b> Resultado do uso de <tt>(delete-queue! q)</tt> na fila da figura <a href="#%_fig_3.20">3.20</a>.</div></caption><tr><td>
</td></tr></table></div><p/><p>
</p><p/><p><tt><a name="%_idx_3258" id="%_idx_3258"/>(define (delete-queue! queue)<br/>
(cond ((empty-queue? queue)<br/>
(error "DELETE! called with an empty queue" queue))<br/>
(else<br/>
(set-front-ptr! queue (cdr (front-ptr queue)))<br/>
queue))) <br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_3.21" id="%_thm_3.21"/>
<b>Exercício 3.21.</b> Ben Bitdiddle decide testar a implementação da fila descrita acima. Ele digita os procedimentos para o interpretador Lisp e passa a testá-los:</p><p>
</p><p/><p><tt>(define q1 (make-queue))<br/>
(insert-queue! q1 'a)<br/><i>((a) a)</i><br/>
(insert-queue! q1 'b)<br/><i>((a b) b)</i><br/>
(delete-queue! q1)<br/><i>((b) b)</i><br/>
(delete-queue! q1)<br/><i>(() b)</i><br/></tt></p><p/><p>“Está tudo errado!” Ele reclama. “A resposta do interpretador mostra que o último item é inserido na fila duas vezes. E quando eu apago os dois itens, o segundo <tt>b</tt> ainda está lá, então a fila não está vazia, mesmo que deva estar”. Eva Lu Ator sugere que Ben não entendeu o que está acontecendo. “Não é que os itens entrem na fila duas vezes”, explica ela. “É que a impressora Lisp padrão não sabe como entender a representação da fila. Se você quiser ver a fila impressa corretamente, precisará definir seu próprio procedimento de impressão para as filas”. Explique do que Eva Lu está falando. Em particular, mostre por que os exemplos de Ben produzem os resultados impressos que eles produzem. Defina um procedimento <a name="%_idx_3260" id="%_idx_3260"/><tt>print-queue</tt> que recebe uma fila como entrada e imprime a sequência de itens na fila.</p><p/><p>
</p><p><a name="%_thm_3.22" id="%_thm_3.22"/>
<b>Exercício 3.22.</b> <a name="%_idx_3262" id="%_idx_3262"/>Em vez de representar uma fila como um par de ponteiros, podemos construir uma fila como um procedimento com o estado local. O estado local consistirá em ponteiros para o início e o fim de uma lista comum. Portanto, o procedimento <tt>make-queue</tt> terá o formato</p><p>
</p><p/><p><tt>(define (make-queue)<br/>
(let ((front-ptr <tt>...</tt>)<br/>
(rear-ptr <tt>...</tt>))<br/>
<<em>definitions of internal procedures</em>><br/>
(define (dispatch m) <tt>...</tt>)<br/>
dispatch))<br/></tt></p><p/><p>Conclua a definição de <tt>make-queue</tt> e forneça implementações das operações da fila usando esta representação.</p><p/><p>
</p><p><a name="%_thm_3.23" id="%_thm_3.23"/>
<b>Exercício 3.23.</b> <a name="%_idx_3264" id="%_idx_3264"/><a name="%_idx_3266" id="%_idx_3266"/>Um <em>deque</em> (“double-ended queue” ou “fila dupla”, em português) é uma sequência na qual os itens podem ser inseridos e excluídos na frente ou na parte traseira. As operações no deques são o construtor <tt>make-deque</tt>, o predicado <tt>empty-deque?</tt>, os seletores <tt>front-deque</tt> e <tt>rear-deque</tt> e mutadores <tt>front-insert-deque!</tt>, <tt>rear-insert-deque!</tt>, <tt>front-delete-deque!</tt> e <tt>rear-delete-deque!</tt>. Mostre como representar deques usando pares e forneça implementações das operações.<a name="call_footnote_Temp_370" href="#footnote_Temp_370" id="call_footnote_Temp_370"><sup><small>23</small></sup></a> Todas as operações devem ser realizadas em θ(1) etapas.</p><p>
<a name="%_sec_3.3.3" id="%_sec_3.3.3"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.3.3">3.3.3 Representando tabelas</a></h3><p>
<a name="%_idx_3268" id="%_idx_3268"/>
<a name="%_idx_3270" id="%_idx_3270"/>Quando estudamos várias maneiras de representar conjuntos no capítulo 2, mencionamos na seção <a href="book-Z-H-16.html#%_sec_2.3.3">2.3.3</a> a tarefa de manter uma tabela de registradores indexados pela identificação de chaves. Na implementação da programação orientada a dados na seção <a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>, fizemos amplo uso de tabelas bidimensionais, nas quais as informações são armazenadas e recuperadas usando duas chaves. Aqui vemos como criar tabelas como estruturas de lista mutáveis.</p><p>
<a name="%_idx_3272" id="%_idx_3272"/>Primeiro, consideramos uma tabela unidimensional, na qual cada valor é armazenado em uma única chave. Implementamos a tabela como uma lista de registradores, cada um dos quais, é implementado como um par que consiste em uma chave e o valor associado. Os registradores são colados para formar uma lista por pares cujos <tt>car</tt> s apontam para registradores sucessivos. Esses pares de colagem são chamados de <a name="%_idx_3274" id="%_idx_3274"/><em>espinha dorsal</em> da tabela. Para ter um lugar que podemos mudar quando adicionamos um novo registrador à tabela, construímos a tabela como uma <a name="%_idx_3276" id="%_idx_3276"/><a name="%_idx_3278" id="%_idx_3278"/><em>lista com cabeçalho</em>. Uma lista com cabeçalho possui um par de espinha dorsal especial no início, que contém um “registrador” fictício – nesse caso, o símbolo escolhido arbitrariamente <tt>*table*</tt>. A figura <a href="#%_fig_3.22">3.22</a> mostra o diagrama de caixa e ponteiro para a tabela</p><p>
</p><p/><p><tt>a: 1<br/>
b: 2<br/>
c: 3<br/></tt></p><p/><p/><p>
<a name="%_fig_3.22" id="%_fig_3.22"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-22.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.22:</b> Uma tabela representada como uma lista com cabeçalho.</div></caption><tr><td>
</td></tr></table></div><p/><p>Para extrair informações de uma tabela, usamos o procedimento <tt>lookup</tt>, que recebe uma chave como argumento e retorna o valor associado (ou falso se não houver valor armazenado sob essa chave). <tt>Lookup</tt> é definida em termos da operação <tt>assoc</tt>, que espera uma chave e uma lista de registradores como argumentos. Observe que <tt>assoc</tt> nunca vê o registrador fictício. <tt>Assoc</tt> retorna o registrador que possui a chave fornecida como <tt>car</tt>. <a name="call_footnote_Temp_371" href="#footnote_Temp_371" id="call_footnote_Temp_371"><sup><small>24</small></sup></a> <tt>Lookup</tt> verifica se o registrador resultante retornado por <tt>assoc</tt> não é falso e retorna o valor (o <tt>cdr</tt>) do registrador.</p><p>
</p><p/><p><tt><a name="%_idx_3280" id="%_idx_3280"/>(define (lookup key table)<br/>
(let ((record (assoc key (cdr table))))<br/>
(if record<br/>
(cdr record)<br/>
false)))<br/><a name="%_idx_3282" id="%_idx_3282"/>(define (assoc key records)<br/>
(cond ((null? records) false)<br/>
((equal? key (caar records)) (car records))<br/>
(else (assoc key (cdr records)))))<br/></tt></p><p/><p/><p>Para inserir um valor em uma tabela sob uma chave especificada, primeiro usamos <tt>assoc</tt> para verificar se já existe um registrador na tabela com essa chave. Caso contrário, formamos um novo registrador aplicando <tt>cons</tt> na chave com o valor e o inserimos no início da lista de registradores da tabela, após o registrador fictício. Se já existe um registrador com essa chave, definimos o <tt>cdr</tt> desse registrador com o novo valor designado. O cabeçalho da tabela fornece um local fixo para modificar para inserir o novo registrador.<a name="call_footnote_Temp_372" href="#footnote_Temp_372" id="call_footnote_Temp_372"><sup><small>25</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3284" id="%_idx_3284"/>(define (insert! key value table)<br/>
(let ((record (assoc key (cdr table))))<br/>
(if record<br/>
(set-cdr! record value)<br/>
(set-cdr! table<br/>
(cons (cons key value) (cdr table)))))<br/>
'ok)<br/></tt></p><p/><p/><p>Para construir uma nova tabela, simplesmente criamos uma lista contendo o símbolo <tt>*table*</tt>:</p><p>
</p><p/><p><tt><a name="%_idx_3286" id="%_idx_3286"/>(define (make-table)<br/>
(list '*table*))<br/></tt></p><p/><p>
<a name="%_sec_Temp_373" id="%_sec_Temp_373"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_373">Tabela bidimensionais</a></h4><p>
<a name="%_idx_3288" id="%_idx_3288"/>Em uma tabela bidimensional, cada valor é indexado por duas chaves. Podemos construir uma tabela como uma tabela unidimensional na qual cada chave identifica uma subtabela. A figura <a href="#%_fig_3.23">3.23</a> mostra o diagrama de caixa e ponteiro para a tabela</p><p/><p><tt>math:<br/>
+: 43<br/>
-: 45<br/>
*: 42<br/>
letters:<br/>
a: 97<br/>
b: 98<br/></tt></p><p/><p>que possui duas subtabelas. (As subtabelas não precisam de um símbolo de cabeçalho especial, pois a chave que identifica a subtabela serve a esse propósito).</p><p>
<a name="%_fig_3.23" id="%_fig_3.23"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-23.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.23:</b> Uma tabela bidimensional.</div></caption><tr><td>
</td></tr></table></div><p/><p>Quando procuramos um item, usamos a primeira cheva para identificar a subtabela correta. Em seguida, usamos a segunda chave para identificar o registrador na subtabela.</p><p>
</p><p/><p><tt><a name="%_idx_3290" id="%_idx_3290"/>(define (lookup key-1 key-2 table)<br/>
(let ((subtable (assoc key-1 (cdr table))))<br/>
(if subtable<br/>
(let ((record (assoc key-2 (cdr subtable))))<br/>
(if record<br/>
(cdr record)<br/>
false))<br/>
false)))<br/></tt></p><p/><p/><p>Para inserir um novo item em um par de chaves, usamos <tt>assoc</tt> para verificar se há uma subtabela armazenada sob a primeira chave. Caso contrário, criamos uma nova subtabela que contém o registrador único (<tt>key-2</tt>, <tt>value</tt>) e o inserimos na tabela abaixo da primeira chave. Se já existe uma subtabela para a primeira chave, inserimos o novo registrador nessa subtabela, usando o método de inserção para tabelas unidimensionais descritas acima:</p><p>
</p><p/><p><tt><a name="%_idx_3292" id="%_idx_3292"/>(define (insert! key-1 key-2 value table)<br/>
(let ((subtable (assoc key-1 (cdr table))))<br/>
(if subtable<br/>
(let ((record (assoc key-2 (cdr subtable))))<br/>
(if record<br/>
(set-cdr! record value)<br/>
(set-cdr! subtable<br/>
(cons (cons key-2 value)<br/>
(cdr subtable)))))<br/>
(set-cdr! table<br/>
(cons (list key-1<br/>
(cons key-2 value))<br/>
(cdr table)))))<br/>
'ok)<br/></tt></p><p/><p>
<a name="%_sec_Temp_374" id="%_sec_Temp_374"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_374">Criando tabelas locais</a></h4><p>
<a name="%_idx_3294" id="%_idx_3294"/>As operações <tt>lookup</tt> e <tt>insert!</tt> definidas acima levam a tabela como argumento. Isso nos permite usar programas que acessam mais de uma tabela. Outra maneira de lidar com várias tabelas é ter procedimentos separados de <tt>lookup</tt> e <tt>insert!</tt> para cada tabela. Podemos fazer isso representando uma tabela processualmente, como um objeto que mantém uma tabela interna como parte de seu estado local. Quando enviada uma mensagem apropriada, esse “objeto de tabela” fornece o procedimento com o qual operar na tabela interna. Aqui está um gerador para tabelas bidimensionais representadas desta maneira:</p><p>
</p><p/><p><tt><a name="%_idx_3296" id="%_idx_3296"/>(define (make-table)<br/>
(let ((local-table (list '*table*)))<br/>
(define (lookup key-1 key-2)<br/>
(let ((subtable (assoc key-1 (cdr local-table))))<br/>
(if subtable<br/>
(let ((record (assoc key-2 (cdr subtable))))<br/>
(if record<br/>
(cdr record)<br/>
false))<br/>
false)))<br/>
(define (insert! key-1 key-2 value)<br/>
(let ((subtable (assoc key-1 (cdr local-table))))<br/>
(if subtable<br/>
(let ((record (assoc key-2 (cdr subtable))))<br/>
(if record<br/>
(set-cdr! record value)<br/>
(set-cdr! subtable<br/>
(cons (cons key-2 value)<br/>
(cdr subtable)))))<br/>
(set-cdr! local-table<br/>
(cons (list key-1<br/>
(cons key-2 value))<br/>
(cdr local-table)))))<br/>
'ok) <br/>
(define (dispatch m)<br/>
(cond ((eq? m 'lookup-proc) lookup)<br/>
((eq? m 'insert-proc!) insert!)<br/>
(else (error "Unknown operation -- TABLE" m))))<br/>
dispatch))<br/></tt></p><p/><p/><p>Usando <tt>make-table</tt>, poderíamos implementar as operações <tt>get</tt> e <tt>put</tt> usadas na seção <a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a> para programação orientada a dados, como segue:</p><p>
</p><p/><p><tt><a name="%_idx_3298" id="%_idx_3298"/>(define operation-table (make-table))<br/><a name="%_idx_3300" id="%_idx_3300"/>(define get (operation-table 'lookup-proc))<br/><a name="%_idx_3302" id="%_idx_3302"/>(define put (operation-table 'insert-proc!))<br/></tt></p><p/><p>
<tt>Get</tt> usa como argumentos duas chaves, e <tt>put</tt> usa como argumentos duas chaves e um valor. Ambas as operações acessam a mesma tabela local, que é encapsulada dentro do objeto criado pela chamada para <tt>make-table</tt>.</p><p><a name="%_thm_3.24" id="%_thm_3.24"/>
<b>Exercício 3.24.</b> <a name="%_idx_3304" id="%_idx_3304"/><a name="%_idx_3306" id="%_idx_3306"/>Nas implementações da tabela acima, as chaves são testadas quanto à igualdade usando <tt>equal?</tt> (chamado por <tt>assoc</tt>). Esse nem sempre é o teste apropriado. Por exemplo, podemos ter uma tabela com teclas numéricas na qual não precisamos de uma correspondência exata com o número que estamos procurando, mas apenas um número com alguma tolerância. Crie um construtor de tabela <tt>make-table</tt> que use como argumento um procedimento <tt>same-key?</tt> que será usado para testar a “igualdade” de chaves. <tt>Make-table</tt> deve retornar um procedimento <tt>dispatch</tt> que pode ser usado para acessar os procedimentos apropriados de <tt>lookup</tt> e <tt>insert!</tt> para uma tabela local.</p><p/><p>
</p><p><a name="%_thm_3.25" id="%_thm_3.25"/>
<b>Exercício 3.25.</b> <a name="%_idx_3308" id="%_idx_3308"/>Generalizando tabelas unidimensionais e bidimensionais, mostre como implementar uma tabela na qual os valores são armazenados sob um número arbitrário de chaves e diferentes valores podem ser armazenados sob diferentes números de chaves. Os procedimentos <tt>lookup</tt> e <tt>insert!</tt> devem ter como entrada uma lista de chaves usadas para acessar a tabela.</p><p/><p>
</p><p><a name="%_thm_3.26" id="%_thm_3.26"/>
<b>Exercício 3.26.</b> <a name="%_idx_3310" id="%_idx_3310"/><a name="%_idx_3312" id="%_idx_3312"/>Para pesquisar uma tabela conforme implementada acima, é necessário verificar a lista de registradores. Esta é basicamente a representação de lista não ordenada da seção <a href="book-Z-H-16.html#%_sec_2.3.3">2.3.3</a>. Para tabelas grandes, pode ser mais eficiente estruturar a tabela de uma maneira diferente. Descreva uma implementação de tabela em que os registradores (chave, valor) sejam organizados usando uma árvore binária, assumindo que as chaves possam ser ordenadas de alguma maneira (por exemplo, numericamente ou alfabeticamente). (Compare o exercício <a href="book-Z-H-16.html#%_thm_2.66">2.66</a> do capítulo 2).</p><p/><p>
</p><p><a name="%_thm_3.27" id="%_thm_3.27"/>
<b>Exercício 3.27.</b> <a name="%_idx_3314" id="%_idx_3314"/><a name="%_idx_3316" id="%_idx_3316"/><a name="%_idx_3318" id="%_idx_3318"/><a name="%_idx_3320" id="%_idx_3320"/><em>Memoização</em> (também chamada de <em>tabulação</em>) é uma técnica que permite que um procedimento registre, em uma tabela local, valores que foram computados anteriormente. Essa técnica pode fazer uma grande diferença no desempenho de um programa. Um procedimento memoizado mantém uma tabela na qual os valores de chamadas anteriores são armazenados usando como chaves os argumentos que produziram os valores. Quando o procedimento memoizado é solicitado a calcular um valor, ele primeiro verifica a tabela para ver se o valor já existe e, nesse caso, apenas retorna esse valor. Caso contrário, ele calcula o novo valor da maneira comum e o armazena na tabela. Como exemplo de memoização, lembre-se da seção <a href="book-Z-H-11.html#%_sec_1.2.2">1.2.2</a> do processo exponencial para calcular os números de Fibonacci:</p><p>
</p><p/><p><tt><a name="%_idx_3322" id="%_idx_3322"/>(define (fib n)<br/>
(cond ((= n 0) 0)<br/>
((= n 1) 1)<br/>
(else (+ (fib (- n 1))<br/>
(fib (- n 2))))))<br/></tt></p><p/><p>A versão memoizada do mesmo procedimento é</p><p>
</p><p/><p><tt><a name="%_idx_3324" id="%_idx_3324"/>(define memo-fib<br/>
(memoize (lambda (n)<br/>
(cond ((= n 0) 0)<br/>
((= n 1) 1)<br/>
(else (+ (memo-fib (- n 1))<br/>
(memo-fib (- n 2))))))))<br/></tt></p><p/><p>onde o memoizador é definido como</p><p/><p><tt><a name="%_idx_3326" id="%_idx_3326"/>(define (memoize f)<br/>
(let ((table (make-table)))<br/>
(lambda (x)<br/>
(let ((previously-computed-result (lookup x table)))<br/>
(or previously-computed-result<br/>
(let ((result (f x)))<br/>
(insert! x result table)<br/>
result))))))<br/></tt></p><p/><p>Desenhe um diagrama do ambiente para analisar o cálculo de <tt>(memo-fib 3)</tt>. Explique por que <tt>memo-fib</tt> calcula o <em>n</em> ésimo número de Fibonacci em uma série de etapas proporcionais a <em>n</em>. O esquema ainda funcionaria se tivéssemos simplesmente definido <tt>memo-fib</tt> como <tt>(memoize fib)</tt>?</p><p>
<a name="%_sec_3.3.4" id="%_sec_3.3.4"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.3.4">3.3.4 Um simulador para circuitos digitais</a></h3><p>
<a name="%_idx_3328" id="%_idx_3328"/>Projetar sistemas digitais complexos, como computadores, é uma importante atividade de engenharia. Os sistemas digitais são construídos interconectando elementos simples. Embora o comportamento desses elementos individuais seja simples, as redes deles podem ter um comportamento muito complexo. A simulação por computador dos projetos de circuitos propostos é uma ferramenta importante usada pelos engenheiros de sistemas digitais. Nesta seção, projetamos um sistema para realizar simulações de lógica digital. Este sistema tipifica um tipo de programa chamado <a name="%_idx_3330" id="%_idx_3330"/><a name="%_idx_3332" id="%_idx_3332"/><em>simulação orientada a eventos</em>, na qual ações (“eventos”) acionam outros eventos que acontecem posteriormente, que por sua vez acionar mais eventos e assim por diante.</p><p>Nosso modelo computacional de um circuito será composto de objetos que correspondem aos componentes elementares dos quais o circuito é construído. Existem <a name="%_idx_3334" id="%_idx_3334"/><em>fios</em>, que carregam <a name="%_idx_3336" id="%_idx_3336"/><a name="%_idx_3338" id="%_idx_3338"/><em>sinais digitais</em>. Um sinal digital pode a qualquer momento ter apenas um dos dois valores possíveis, 0 e 1. Existem também vários tipos de <a name="%_idx_3340" id="%_idx_3340"/><em>caixas de função</em> que conectam fios que transportam sinais de entrada a outros fios de saída. Tais caixas produzem sinais de saída calculados a partir de seus sinais de entrada. O sinal de saída é <a name="%_idx_3342" id="%_idx_3342"/>atrasado por um tempo que depende do tipo da caixa de função. Por exemplo, um <a name="%_idx_3344" id="%_idx_3344"/><em>inversor</em> é uma caixa de função primitiva que inverte sua entrada. Se o sinal de entrada de um inversor mudar para 0, um atraso no inversor depois o inversor alterará seu sinal de saída para 1. Se o sinal de entrada de um inversor mudar para 1, um atraso no inversor depois o inversor alterará seu sinal de saída para 0. Desenhamos um inversor simbolicamente, como na figura <a href="#%_fig_3.24">3.24</a>. Uma <a name="%_idx_3346" id="%_idx_3346"/><em>porta and</em>, também mostrado na figura <a href="#%_fig_3.24">3.24</a>, é uma caixa de função primitiva com duas entradas e uma saída. Ele direciona seu sinal de saída para um valor que é <a name="%_idx_3348" id="%_idx_3348"/><em>and lógico</em> das entradas. Ou seja, se ambos os sinais de entrada se tornarem 1, um tempo de atraso da porta e mais tarde a porta and forçará seu sinal de saída a 1; caso contrário, a saída será 0. Uma <a name="%_idx_3350" id="%_idx_3350"/><em>porta or</em> é uma caixa de função primitiva de duas entradas semelhante que direciona seu sinal de saída para um valor que é <a name="%_idx_3352" id="%_idx_3352"/><em>or lógico</em> do entradas. Ou seja, a saída se tornará 1 se, pelo menos, um dos sinais de entrada for 1; caso contrário, a saída se tornará 0.</p><p>
<a name="%_fig_3.24" id="%_fig_3.24"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-24.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.24:</b> Funções primitivas no simulador de lógica digital.</div></caption><tr><td>
</td></tr></table></div><p/><p>Podemos conectar funções primitivas juntas para construir funções mais complexas. Para fazer isso, conectamos as saídas de algumas caixas de função às entradas de outras caixas de função. Por exemplo, o circuito <a name="%_idx_3354" id="%_idx_3354"/><a name="%_idx_3356" id="%_idx_3356"/><em>meio-somador</em> mostrado na figura <a href="#%_fig_3.25">3.25</a> consiste em uma porta or, duas portas and e um inversor. É preciso dois sinais de entrada, A e B, e possui dois sinais de saída, S e C. S se tornará 1 sempre que precisamente um de A e B for 1, e C se tornará 1 sempre que A e B forem 1. Podemos ver pela figura que, devido aos atrasos envolvidos, os resultados podem ser gerados em momentos diferentes. Muitas das dificuldades no projeto de circuitos digitais surgem desse fato.</p><p>
<a name="%_fig_3.25" id="%_fig_3.25"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-25.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.25:</b> Um circuito de meio somador.</div></caption><tr><td>
</td></tr></table></div><p/><p>Agora construiremos um programa para modelar os circuitos lógicos digitais que queremos estudar. O programa construirá objetos computacionais modelando os fios, os quais “reterão” os sinais. As caixas de função serão modeladas por procedimentos que reforçam os relacionamentos corretos entre os sinais.</p><p>
<a name="%_idx_3358" id="%_idx_3358"/>Um elemento básico da nossa simulação será um procedimento <tt>make-wire</tt>, que constrói fios. Por exemplo, podemos construir seis fios da seguinte maneira:</p><p>
</p><p/><p><tt>(define a (make-wire))<br/>
(define b (make-wire))<br/>
(define c (make-wire))<br/><br/>
(define d (make-wire))<br/>
(define e (make-wire))<br/>
(define s (make-wire))<br/></tt></p><p/><p>Anexamos uma caixa de função a um conjunto de fios chamando um procedimento que constrói esse tipo de caixa. Os argumentos para o procedimento construtor são os fios a serem anexados à caixa. Por exemplo, dado que podemos construir portas and, portas or e inversores, podemos conectar o semi-somador mostrado na figura <a href="#%_fig_3.25">3.25</a>:</p><p>
</p><p/><p><tt>(or-gate a b d)<br/><i>ok</i><br/><br/>
(and-gate a b c)<br/><i>ok</i><br/><br/>
(inverter c e)<br/><i>ok</i><br/><br/>
(and-gate d e s)<br/><i>ok</i><br/></tt></p><p/><p/><p>Melhor ainda, podemos nomear explicitamente essa operação definindo um procedimento <tt>half-adder</tt> que constrói esse circuito, considerando os quatro fios externos a serem conectados ao semi-somador:</p><p>
</p><p/><p><tt><a name="%_idx_3360" id="%_idx_3360"/>(define (half-adder a b s c)<br/>
(let ((d (make-wire)) (e (make-wire)))<br/>
(or-gate a b d)<br/>
(and-gate a b c)<br/>
(inverter c e)<br/>
(and-gate d e s)<br/>
'ok))<br/></tt></p><p/><p>A vantagem de fazer essa definição é que podemos usar <tt>half-adder</tt> como um bloco de construção na criação de circuitos mais complexos. A figura <a href="#%_fig_3.26">3.26</a>, por exemplo, mostra um <a name="%_idx_3362" id="%_idx_3362"/><a name="%_idx_3364" id="%_idx_3364"/><em>somador completo</em> composto por dois semi-aditivos e uma porta or.<a name="call_footnote_Temp_379" href="#footnote_Temp_379" id="call_footnote_Temp_379"><sup><small>26</small></sup></a> Podemos construir um somador completo da seguinte maneira:</p><p>
</p><p/><p><tt><a name="%_idx_3366" id="%_idx_3366"/>(define (full-adder a b c-in sum c-out)<br/>
(let ((s (make-wire))<br/>
(c1 (make-wire))<br/>
(c2 (make-wire)))<br/>
(half-adder b c-in s c1)<br/>
(half-adder a s sum c2)<br/>
(or-gate c1 c2 c-out)<br/>
'ok))<br/></tt></p><p/><p>Tendo definido <tt>full-adder</tt> como procedimento, agora podemos usá-lo como um bloco de construção para criar circuitos ainda mais complexos. (Por exemplo, consulte exercício <a href="#%_thm_3.30">3.30</a>).</p><p>
<a name="%_fig_3.26" id="%_fig_3.26"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-26.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.26:</b> Um circuito de somador completo.</div></caption><tr><td>
</td></tr></table></div><p/><p>Em essência, nosso simulador nos fornece as ferramentas para construir uma linguagem de circuitos. Se adotarmos a perspectiva geral sobre linguagens com a qual abordamos o estudo do Lisp na seção <a href="book-Z-H-10.html#%_sec_1.1">1.1</a>, podemos dizer que as caixas de função primitivas formam os elementos primitivos da linguagem, que as caixas de ligação juntas fornecem um meio de combinação e que especificar padrões de fiação como procedimentos serve como um meio de abstração.</p><p>
<a name="%_sec_Temp_380" id="%_sec_Temp_380"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_380">Caixas de função primitivas</a></h4><p>
<a name="%_idx_3368" id="%_idx_3368"/>As caixas de função primitivas implementam as “forças” pelas quais uma mudança no sinal em um fio influencia os sinais em outros fios. Para criar caixas de função, usamos as seguintes operações nos fios:</p><p>
</p><p/><ul><li><tt>(get-signal <<em>wire</em>>)</tt><br/><a name="%_idx_3370" id="%_idx_3370"/>retorna o valor atual do sinal no fio.<p>
</p></li><li><tt>(set-signal! <<em>wire</em>> <<em>new value</em>>)</tt><br/><a name="%_idx_3372" id="%_idx_3372"/>altera o valor do sinal no fio para o novo valor.<p>
</p></li><li><tt>(add-action! <<em>wire</em>> <<em>procedure of no arguments</em>>)</tt><br/><a name="%_idx_3374" id="%_idx_3374"/>afirma que o procedimento designado deve ser executado sempre que o sinal no fio mudar de valor. Tais procedimentos são os veículos pelos quais as alterações no valor do sinal no fio são comunicadas a outros fios.</li></ul><p>
<a name="%_idx_3376" id="%_idx_3376"/>Além disso, faremos uso de um procedimento <tt>after-delay</tt> isso demora um tempo e um procedimento a ser executado e executa o procedimento especificado após o atraso especificado.</p><p>Usando esses procedimentos, podemos definir as funções primitivas da lógica digital. Para conectar uma entrada a uma saída através de um inversor, usamos <tt>add-action!</tt> para associar ao fio de entrada um procedimento que será executado sempre que o sinal no fio de entrada mudar de valor. O procedimento calcula o <tt>logical-not</tt> do sinal de entrada e depois de um <tt>inverter-delay</tt>, define o sinal de saída para esse novo valor:</p><p>
</p><p/><p><tt><a name="%_idx_3378" id="%_idx_3378"/>(define (inverter input output)<br/>
(define (invert-input)<br/>
(let ((new-value (logical-not (get-signal input))))<br/>
(after-delay inverter-delay<br/>
(lambda ()<br/>
(set-signal! output new-value)))))<br/>
(add-action! input invert-input)<br/>
'ok)<br/><a name="%_idx_3380" id="%_idx_3380"/>(define (logical-not s)<br/>
(cond ((= s 0) 1)<br/>
((= s 1) 0)<br/>
(else (error "Invalid signal" s))))<br/></tt></p><p/><p/><p>Uma porta and é um pouco mais complexa. O procedimento de ação deve ser executado se alguma das entradas da porta mudar. Ele calcula o <tt>logical-and</tt> (usando um procedimento análogo ao <tt>logical-not</tt>) dos valores dos sinais nos fios de entrada e configura uma alteração no novo valor que ocorrerá no fio de saída após um <tt>and-gate-delay</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_3382" id="%_idx_3382"/>(define (and-gate a1 a2 output)<br/>
(define (and-action-procedure)<br/>
(let ((new-value<br/>
(logical-and (get-signal a1) (get-signal a2))))<br/>
(after-delay and-gate-delay<br/>
(lambda ()<br/>
(set-signal! output new-value)))))<br/>
(add-action! a1 and-action-procedure)<br/>
(add-action! a2 and-action-procedure)<br/>
'ok)<br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_3.28" id="%_thm_3.28"/>
<b>Exercício 3.28.</b> <a name="%_idx_3384" id="%_idx_3384"/>Defina uma porta or como uma caixa de função primitiva. Seu <tt>or-gate</tt> construtor deve ser semelhante ao <tt>and-gate</tt>.</p><p/><p>
</p><p><a name="%_thm_3.29" id="%_thm_3.29"/>
<b>Exercício 3.29.</b> <a name="%_idx_3386" id="%_idx_3386"/>Outra maneira de construir uma porta or é como um dispositivo lógico digital composto, construído a partir de portas e inversores. Defina um procedimento <tt>or-gate</tt> que realiza isso. Qual é o tempo de atraso da porta or em termos de <tt>and-gate-delay</tt> e <tt>inverter-delay</tt>?</p><p/><p>
</p><p><a name="%_thm_3.30" id="%_thm_3.30"/>
<b>Exercício 3.30.</b> A figura <a href="#%_fig_3.27">3.27</a> mostra um <a name="%_idx_3388" id="%_idx_3388"/><a name="%_idx_3390" id="%_idx_3390"/><em>somador de transporte de ondulação</em> formado amarrando junto <em>n</em> adicionadores completos. Essa é a forma mais simples de somador paralelo para adicionar dois números binários de <em>n</em> bits. As entradas A<sub>1</sub>, A<sub>2</sub>, A<sub>3</sub>, <tt>…</tt>, A<sub><em>n</em></sub> e B<sub>1</sub>, B<sub>2</sub>, B<sub>3</sub>, <tt>…</tt>, B<sub><em>n</em></sub> são os dois números binários a serem adicionados (cada A<sub><em>k</em></sub> e B<sub><em>k</em></sub> é 0 ou 1). O circuito gera S<sub>1</sub>, S<sub>2</sub>, S<sub>3</sub>, <tt>…</tt>, S<sub><em>n</em></sub>, a <em>n</em> bits da soma e C, o transporte da adição. Escreva um procedimento <tt>ripple-carry-adder</tt> que gera esse circuito. O procedimento deve tomar como argumentos três listas de <em>n</em> fios cada – o A<sub><em>k</em></sub>, o B<sub><em>k</em></sub>, e o S<sub><em>k</em></sub> – e também outro fio C. A principal desvantagem do somador de transporte de ondulação é a necessidade de aguardar a propagação dos sinais de transporte. Qual é o atraso necessário para obter a saída completa de um somador de transporte de ondulação de <em>n</em> bits, expresso em termos de atrasos para portas and, portas or e inversores?</p><p/><p>
<a name="%_fig_3.27" id="%_fig_3.27"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-27.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.27:</b> Um adicionador de transporte de ondulação números de <em>n</em> bits.</div></caption><tr><td>
</td></tr></table></div><p>
<a name="%_sec_Temp_384" id="%_sec_Temp_384"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_384">Representando fios</a></h4><p>
<a name="%_idx_3392" id="%_idx_3392"/>Um fio em nossa simulação será um objeto computacional com duas variáveis de estado local: <tt>signal-value</tt> (inicialmente considerado 0) e uma coleção de <tt>action-procedures</tt> para ser executado quando o sinal mudar de valor. Implementamos a ligação, usando o estilo de passagem de mensagens, como <a name="%_idx_3394" id="%_idx_3394"/>uma coleção de procedimentos locais, com um procedimento <tt>dispatch</tt> que seleciona a operação local apropriada, assim como fizemos com o objeto simples de conta bancária na seção <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>:</p><p>
</p><p/><p><tt><a name="%_idx_3396" id="%_idx_3396"/>(define (make-wire)<br/>
(let ((signal-value 0) (action-procedures '()))<br/>
(define (set-my-signal! new-value)<br/>
(if (not (= signal-value new-value))<br/>
(begin (set! signal-value new-value)<br/>
(call-each action-procedures))<br/>
'done))<br/>
(define (accept-action-procedure! proc)<br/>
(set! action-procedures (cons proc action-procedures))<br/>
(proc))<br/>
(define (dispatch m)<br/>
(cond ((eq? m 'get-signal) signal-value)<br/>
((eq? m 'set-signal!) set-my-signal!)<br/>
((eq? m 'add-action!) accept-action-procedure!)<br/>
(else (error "Unknown operation -- WIRE" m))))<br/>
dispatch))<br/></tt></p><p/><p>O procedimento local <tt>set-my-signal!</tt> testa se o novo valor do sinal altera o sinal no fio. Nesse caso, ele executa cada um dos procedimentos de ação, usando o seguinte procedimento <tt>call-each</tt>, que chama cada um dos itens em uma lista de procedimentos sem argumento:</p><p>
</p><p/><p><tt><a name="%_idx_3398" id="%_idx_3398"/>(define (call-each procedures)<br/>
(if (null? procedures)<br/>
'done<br/>
(begin<br/>
((car procedures))<br/>
(call-each (cdr procedures)))))<br/></tt></p><p/><p>O procedimento local <tt>accept-action-procedure!</tt> adiciona o procedimento especificado à lista de procedimentos a serem executados e, em seguida, executa o novo procedimento uma vez. (Veja exercício <a href="#%_thm_3.31">3.31</a>).</p><p>Com o procedimento local <tt>dispatch</tt> configurado conforme especificado, podemos fornecer os seguintes procedimentos para acessar as operações locais nos fios:<a name="call_footnote_Temp_385" href="#footnote_Temp_385" id="call_footnote_Temp_385"><sup><small>27</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3404" id="%_idx_3404"/>(define (get-signal wire)<br/>
(wire 'get-signal))<br/><a name="%_idx_3406" id="%_idx_3406"/>(define (set-signal! wire new-value)<br/>
((wire 'set-signal!) new-value))<br/><a name="%_idx_3408" id="%_idx_3408"/>(define (add-action! wire action-procedure)<br/>
((wire 'add-action!) action-procedure))<br/></tt></p><p/><p/><p>Os fios, que possuem sinais que variam no tempo e podem ser conectados de forma incremental aos dispositivos, são típicos de objetos mutáveis. Os modelamos como procedimentos com variáveis de estado local que são modificadas por atribuição. Quando um novo fio é criado, um novo conjunto de variáveis de estado é alocado (pela expressão <tt>let</tt> em <tt>make-wire</tt>) e um novo procedimento <tt>dispatch</tt> é construído e retornado, capturando o ambiente com as novas variáveis de estado.</p><p>Os fios são compartilhados entre os vários dispositivos que foram conectados a eles. Assim, uma alteração feita por uma interação com um dispositivo afetará todos os outros dispositivos conectados ao fio. O fio comunica a alteração aos vizinhos chamando os procedimentos de ação fornecidos quando as conexões foram estabelecidas.<a name="%_sec_Temp_386" id="%_sec_Temp_386"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_386">A agenda</a></h4><p>
<a name="%_idx_3410" id="%_idx_3410"/>O único objeto necessário para concluir o simulador é <tt>after-delay</tt>. A ideia aqui é que mantemos uma estrutura de dados, chamada <em>agenda</em>, que contém uma programação do que deve ser feito. As seguintes operações são definidas para agendas:</p><p>
</p><p/><ul><li><a name="%_idx_3412" id="%_idx_3412"/><tt>(make-agenda)</tt><br/> retorna uma nova agenda vazia.<p>
</p></li><li><a name="%_idx_3414" id="%_idx_3414"/><tt>(empty-agenda? <<em>agenda</em>>)</tt><br/> é verdadeiro se a agenda especificada estiver vazia.<p>
</p></li><li><a name="%_idx_3416" id="%_idx_3416"/><tt>(first-agenda-item <<em>agenda</em>>)</tt><br/> retorna o primeiro item da agenda.<p>
</p></li><li><a name="%_idx_3418" id="%_idx_3418"/><tt>(remove-first-agenda-item! <<em>agenda</em>>)</tt><br/> modifica a agenda removendo o primeiro item.<p>
</p></li><li><a name="%_idx_3420" id="%_idx_3420"/><tt>(add-to-agenda! <<em>time</em>> <<em>action</em>> <<em>agenda</em>>)</tt><br/> modifica a agenda adicionando o procedimento de ação fornecido para ser executado no horário especificado.<p>
</p></li><li><a name="%_idx_3422" id="%_idx_3422"/><tt>(current-time <<em>agenda</em>>)</tt><br/> retorna o tempo atual da simulação.</li></ul><p/><p>A agenda específica que usamos é indicada por <tt>the-agenda</tt>. O procedimento <tt>after-delay</tt> adiciona novos elementos à <tt>the-agenda</tt>:</p><p>
</p><p/><p><tt><a name="%_idx_3424" id="%_idx_3424"/>(define (after-delay delay action)<br/>
(add-to-agenda! (+ delay (current-time the-agenda))<br/>
action<br/>
the-agenda))<br/></tt></p><p/><p/><p>A simulação é conduzida pelo procedimento <tt>propagate</tt>, que opera em <tt>the-agenda</tt>, executando cada procedimento na agenda em sequência. Em geral, à medida que a simulação é executada, novos itens serão adicionados à agenda e <tt>propagate</tt> continuará a simulação enquanto houver itens na agenda:</p><p>
</p><p/><p><tt><a name="%_idx_3426" id="%_idx_3426"/>(define (propagate)<br/>
(if (empty-agenda? the-agenda)<br/>
'done<br/>
(let ((first-item (first-agenda-item the-agenda)))<br/>
(first-item)<br/>
(remove-first-agenda-item! the-agenda)<br/>
(propagate))))<br/></tt></p><p/><p>
</p><p>
<a name="%_sec_Temp_387" id="%_sec_Temp_387"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_387">Uma simulação de amostra</a></h4><p>
<a name="%_idx_3428" id="%_idx_3428"/><a name="%_idx_3430" id="%_idx_3430"/>O procedimento a seguir, que coloca uma “sonda” em um fio, mostra o simulador em ação. A sonda diz ao fio que, sempre que seu sinal mudar de valor, ele deve imprimir o novo valor do sinal, junto com a hora atual e um nome que identifique o fio:</p><p>
</p><p/><p><tt><a name="%_idx_3432" id="%_idx_3432"/>(define (probe name wire)<br/>
(add-action! wire<br/>
(lambda () <br/>
(newline)<br/>
(display name)<br/>
(display " ")<br/>
(display (current-time the-agenda))<br/>
(display " New-value = ")<br/>
(display (get-signal wire)))))<br/></tt></p><p/><p/><p>Começamos iniciando a agenda e especificando atrasos para as caixas de função primitivas:</p><p>
</p><p/><p><tt>(define the-agenda (make-agenda))<br/>
(define inverter-delay 2)<br/>
(define and-gate-delay 3)<br/>
(define or-gate-delay 5)<br/></tt></p><p/><p>Agora, definimos quatro fios, colocando sondas em dois deles:</p><p>
</p><p/><p><tt>(define input-1 (make-wire))<br/>
(define input-2 (make-wire))<br/>
(define sum (make-wire))<br/>
(define carry (make-wire))<br/>
(probe 'sum sum)<br/><i>sum 0 New-value = 0</i><br/>
(probe 'carry carry)<br/><i>carry 0 New-value = 0</i><br/></tt></p><p/><p>Em seguida, conectamos os fios em um circuito semi-somador (como na figura <a href="#%_fig_3.25">3.25</a>), configuramos o sinal na <tt>input-1</tt> para 1 e executamos a simulação:</p><p>
</p><p/><p><tt>(half-adder input-1 input-2 sum carry)<br/><i>ok</i><br/>
(set-signal! input-1 1)<br/><i>done</i><br/>
(propagate)<br/><i>sum 8 New-value = 1</i><br/><i>done</i><br/></tt></p><p/><p>O sinal <tt>sum</tt> muda para 1 no tempo 8. Agora somos oito unidades de tempo desde o início da simulação. Neste ponto, podemos definir o sinal <tt>input-2</tt> para 1 e permita a propagação dos valores:</p><p>
</p><p/><p><tt>(set-signal! input-2 1)<br/><i>done</i><br/>
(propagate)<br/><i>carry 11 New-value = 1</i><br/><i>sum 16 New-value = 0</i><br/><i>done</i><br/></tt></p><p/><p>O <tt>carry</tt> muda para 1 no tempo 11 e o <tt>sum</tt> muda para 0 no horário 16.</p><p><a name="%_thm_3.31" id="%_thm_3.31"/>
<b>Exercício 3.31.</b> <a name="%_idx_3434" id="%_idx_3434"/>O procedimento interno <tt>accept-action-procedure!</tt> definido em <tt>make-wire</tt> especifica que quando um novo procedimento de ação é adicionado a uma ligação, o procedimento é executado imediatamente. Explique por que essa iniciação é necessária. Em particular, rastreie o exemplo do meio adicionador nos parágrafos acima e diga como a resposta do sistema seria diferente se tivéssemos definido <tt>accept-action-procedure!</tt> Como</p><p>
</p><p/><p><tt>(define (accept-action-procedure! proc)<br/>
(set! action-procedures (cons proc action-procedures)))<br/></tt></p><p/><p>
</p><p/><p>
<a name="%_sec_Temp_389" id="%_sec_Temp_389"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_389">Implementando a agenda</a></h4><p>
<a name="%_idx_3436" id="%_idx_3436"/>Por fim, fornecemos detalhes da estrutura de dados da agenda, que contém os procedimentos agendados para execução futura.</p><p>A agenda é composta de <a name="%_idx_3438" id="%_idx_3438"/><em>segmentos de tempo</em>. Cada segmento de tempo é um par que consiste em um número (a hora) e uma <a name="%_idx_3440" id="%_idx_3440"/>fila (veja exercício <a href="#%_thm_3.32">3.32</a>) que mantém os procedimentos que estão programados para serem executados durante esse segmento de tempo.</p><p>
</p><p/><p><tt><a name="%_idx_3442" id="%_idx_3442"/>(define (make-time-segment time queue)<br/>
(cons time queue))<br/><a name="%_idx_3444" id="%_idx_3444"/>(define (segment-time s) (car s))<br/><a name="%_idx_3446" id="%_idx_3446"/>(define (segment-queue s) (cdr s))<br/></tt></p><p/><p>Operaremos nas filas do segmento de tempo usando as operações de fila descritas na seção <a href="#%_sec_3.3.2">3.3.2</a>.</p><p>
<a name="%_idx_3448" id="%_idx_3448"/>A agenda em si é uma tabela unidimensional de segmentos de tempo. Difere das tabelas descritas na seção <a href="#%_sec_3.3.3">3.3.3.</a> em que os segmentos serão classificados em ordem crescente de tempo. Além disso, armazenamos a <a name="%_idx_3450" id="%_idx_3450"/><em>hora atual</em> (ou seja, o horário da última ação que foi processada) no início da agenda. Uma agenda recém-construída não possui segmentos de tempo e possui um horário atual de 0:<a name="call_footnote_Temp_390" href="#footnote_Temp_390" id="call_footnote_Temp_390"><sup><small>28</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3456" id="%_idx_3456"/>(define (make-agenda) (list 0))<br/><a name="%_idx_3458" id="%_idx_3458"/>(define (current-time agenda) (car agenda))<br/><a name="%_idx_3460" id="%_idx_3460"/>(define (set-current-time! agenda time)<br/>
(set-car! agenda time))<br/><a name="%_idx_3462" id="%_idx_3462"/>(define (segments agenda) (cdr agenda))<br/><a name="%_idx_3464" id="%_idx_3464"/>(define (set-segments! agenda segments)<br/>
(set-cdr! agenda segments))<br/><a name="%_idx_3466" id="%_idx_3466"/>(define (first-segment agenda) (car (segments agenda)))<br/><a name="%_idx_3468" id="%_idx_3468"/>(define (rest-segments agenda) (cdr (segments agenda)))<br/></tt></p><p/><p/><p>Uma agenda está vazia se não tiver segmentos de tempo:</p><p/><p><tt><a name="%_idx_3470" id="%_idx_3470"/>(define (empty-agenda? agenda)<br/>
(null? (segments agenda)))<br/></tt></p><p/><p>
</p><p>Para adicionar uma ação a uma agenda, primeiro verificamos se a agenda está vazia. Nesse caso, criamos um segmento de tempo para a ação e o instalamos na agenda. Caso contrário, verificamos a agenda, examinando o tempo de cada segmento. Se encontrarmos um segmento para o horário designado, adicionaremos a ação à fila associada. Se chegarmos a um tempo posterior àquele para o qual somos designados, inseriremos um novo segmento de tempo na agenda logo antes dele. Se chegarmos ao final da agenda, precisamos criar um novo segmento de tempo no final.</p><p>
</p><p/><p><tt><a name="%_idx_3472" id="%_idx_3472"/>(define (add-to-agenda! time action agenda)<br/>
(define (belongs-before? segments)<br/>
(or (null? segments)<br/>
(< time (segment-time (car segments)))))<br/>
(define (make-new-time-segment time action)<br/>
(let ((q (make-queue)))<br/>
(insert-queue! q action)<br/>
(make-time-segment time q)))<br/>
(define (add-to-segments! segments)<br/>
(if (= (segment-time (car segments)) time)<br/>
(insert-queue! (segment-queue (car segments))<br/>
action)<br/>
(let ((rest (cdr segments)))<br/>
(if (belongs-before? rest)<br/>
(set-cdr!<br/>
segments<br/>
(cons (make-new-time-segment time action)<br/>
(cdr segments)))<br/>
(add-to-segments! rest)))))<br/>
(let ((segments (segments agenda)))<br/>
(if (belongs-before? segments)<br/>
(set-segments!<br/>
agenda<br/>
(cons (make-new-time-segment time action)<br/>
segments))<br/>
(add-to-segments! segments))))<br/></tt></p><p/><p/><p>O procedimento que remove o primeiro item da agenda exclui o item na frente da fila no primeiro segmento. Se essa exclusão deixar o segmento de tempo vazio, removemos-o da lista de segmentos:<a name="call_footnote_Temp_391" href="#footnote_Temp_391" id="call_footnote_Temp_391"><sup><small>29</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3478" id="%_idx_3478"/>(define (remove-first-agenda-item! agenda)<br/>
(let ((q (segment-queue (first-segment agenda))))<br/>
(delete-queue! q)<br/>
(if (empty-queue? q)<br/>
(set-segments! agenda (rest-segments agenda)))))<br/></tt></p><p/><p/><p>O primeiro item da agenda é encontrado no início da fila no primeiro segmento de tempo. Sempre que extraímos um item, também atualizamos o horário atual:<a name="call_footnote_Temp_392" href="#footnote_Temp_392" id="call_footnote_Temp_392"><sup><small>30</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_3480" id="%_idx_3480"/>(define (first-agenda-item agenda)<br/>
(if (empty-agenda? agenda)<br/>
(error "Agenda is empty -- FIRST-AGENDA-ITEM")<br/>
(let ((first-seg (first-segment agenda)))<br/>
(set-current-time! agenda (segment-time first-seg))<br/>
(front-queue (segment-queue first-seg)))))<br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_3.32" id="%_thm_3.32"/>
<b>Exercício 3.32.</b> Os procedimentos a serem executados durante cada segmento de tempo da agenda são mantidos em uma fila. Assim, os procedimentos para cada segmento são chamados na ordem em que foram adicionados à agenda (primeiro a entrar, primeiro a sair). Explique por que esse ordem deve ser usada. Em particular, rastreie o comportamento de uma porta and cujas entradas mudam de 0,1 para 1,0 no mesmo segmento e diga como o comportamento seria diferente se armazenássemos os procedimentos de um segmento em uma lista comum, adicionando e removendo procedimentos apenas em a frente (último a entrar, primeiro a sair).</p><p>
<a name="%_sec_3.3.5" id="%_sec_3.3.5"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_3.3.5">3.3.5 Propagação de restrições</a></h3><p>
<a name="%_idx_3482" id="%_idx_3482"/><a name="%_idx_3484" id="%_idx_3484"/>Os programas de computador são tradicionalmente organizados como cálculos unidirecionais, que executam operações com argumentos pré-especificados para produzir os resultados desejados. Por outro lado, frequentemente modelamos sistemas em termos de relações entre quantidades. Por exemplo, um modelo matemático de uma estrutura mecânica pode incluir as informações de que a deflexão <em>d</em> de uma haste de metal está relacionada à força <em>F</em> na haste, o comprimento <em>L</em> da haste, a área de seção transversal <em>A</em>, e o módulo de elasticidade <em>E</em> através da equação</p><p/><div align="left"><img src="images/ch3-Z-G-28.gif" border="0"/></div><p>Essa equação não é unidirecional. Dadas quatro quantidades, podemos usá-lo para calcular a quinta. Contudo, traduzir a equação para uma linguagem de computador tradicional nos forçaria a escolher uma das quantidades a serem calculadas em termos das outras quatro. Assim, um procedimento para calcular a área <em>A</em> não pôde ser usado para calcular a deflexão <em>d</em>, mesmo que os cálculos de <em>A</em> e <em>d</em> surgem da mesma equação.<a name="call_footnote_Temp_394" href="#footnote_Temp_394" id="call_footnote_Temp_394"><sup><small>31</small></sup></a></p><p>
<a name="%_idx_3508" id="%_idx_3508"/>Nesta seção, esboçamos o projeto de uma linguagem que nos permite trabalhar em termos de relações. Os elementos primitivos da linguagem são <a name="%_idx_3510" id="%_idx_3510"/><a name="%_idx_3512" id="%_idx_3512"/><em>restrições primitivas</em>, que afirmam que certas relações se mantêm entre quantidades. Por exemplo, <tt>(adder a b c)</tt> especifica que as quantidades <em>a</em>, <em>b</em>, e <em>c</em> deve estar relacionado pela equação <em>a</em> + <em>b</em> = <em>c</em>, <tt>(multiplier x y z)</tt> expressa a restrição <em>x</em><em>y</em> = <em>z</em>, e <tt>(constant 3.14 x)</tt> diz que o valor de <em>x</em> deve ser 3,14.</p><p>Nossa linguagem fornece um meio de combinar restrições primitivas para expressar relações mais complexas. Combinamos restrições construindo <a name="%_idx_3514" id="%_idx_3514"/><em>redes de restrição</em>, nas quais as restrições são unidas por <a name="%_idx_3516" id="%_idx_3516"/><em>conectores</em>. Um conector é um objeto que “mantém” um valor que pode participar de uma ou mais restrições. Por exemplo, sabemos que a relação entre as temperaturas de Fahrenheit e Celsius é</p><p>
</p><p/><div align="left"><img src="images/ch3-Z-G-29.gif" border="0"/></div><p/><p>Essa restrição pode ser pensada como uma rede que consiste em somador primitivo, multiplicador e restrições constantes (figura <a href="#%_fig_3.28">3.28</a>) Na figura, vemos à esquerda uma caixa multiplicadora com três terminais, rotulados <em>m</em>1 <em>m</em>2 e <em>p</em>. Eles conectam o multiplicador ao restante da rede da seguinte maneira: <em>m</em>1 terminal está conectado a um conector <em>C</em>, que manterá a temperatura Celsius. O terminal <em>m</em>2 está vinculado a um conector <em>w</em>, que também está vinculado a uma caixa constante que contém 9. O terminal <em>p</em>, que a caixa multiplicadora o restringe como produto de <em>m</em>1 e <em>m</em>2, está ligado ao terminal <em>p</em> de outra caixa multiplicadora, cuja <em>m</em>2 está conectado a uma constante 5 e cuja <em>m</em>1 está conectado a um dos termos em uma soma.</p><p>
<a name="%_fig_3.28" id="%_fig_3.28"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch3-Z-G-30.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 3.28:</b> A relação 9<em>C</em> = 5 (<em>F</em> - 32) expressa como uma rede de restrição.</div></caption><tr><td>
</td></tr></table></div><p/><p>A computação por essa rede ocorre da seguinte maneira: Quando um conector recebe um valor (pelo usuário ou por uma caixa de restrição à qual está ligado), ele desperta todas as restrições associadas (exceto a restrição que acabou de despertá-lo) para informe-os de que possui um valor. Cada caixa de restrição despertada pesquisa seus conectores para verificar se há informações suficientes para determinar um valor para um conector. Nesse caso, a caixa define esse conector, que desperta todas as restrições associadas e assim por diante. Por exemplo, na conversão entre Celsius e Fahrenheit, <em>W</em>, <em>x</em>, e <em>y</em> são definidos imediatamente pelas caixas constantes como 9, 5 e 32, respectivamente. Os conectores despertam os multiplicadores e o somador, que determinam que não há informações suficientes para prosseguir. Se o usuário (ou alguma outra parte da rede) definir <em>C</em> para um valor (digamos 25), o multiplicador mais à esquerda será despertado e definirá <em>u</em> para 25,9 = 225. Então <em>u</em> desperta o segundo multiplicador, que define <em>v</em> para 45, e <em>v</em> desperta o somador, que define <em>F</em> para 77.</p><p>
<a name="%_sec_Temp_395" id="%_sec_Temp_395"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_395">Usando o sistema de restrição</a></h4><p>Para usar o sistema de restrição para realizar o cálculo de temperatura descrito acima, primeiro criamos dois conectores, <tt>C</tt> e <tt>F</tt>, chamando o construtor <tt>make-connector</tt> e link <tt>C</tt> e <tt>F</tt> em uma rede apropriada:</p><p>
</p><p/><p><tt>(define C (make-connector))<br/>
(define F (make-connector))<br/>
(celsius-fahrenheit-converter C F)<br/><i>ok</i><br/></tt></p><p/><p>O procedimento que cria a rede é definido da seguinte maneira:</p><p>
</p><p/><p><tt><a name="%_idx_3518" id="%_idx_3518"/>(define (celsius-fahrenheit-converter c f)<br/>
(let ((u (make-connector))<br/>
(v (make-connector))<br/>
(w (make-connector))<br/>
(x (make-connector))<br/>
(y (make-connector)))<br/>
(multiplier c w u)<br/>
(multiplier v x u)<br/>
(adder v y f)<br/>
(constant 9 w)<br/>
(constant 5 x)<br/>
(constant 32 y)<br/>
'ok))<br/></tt></p><p/><p>Este procedimento cria os conectores internos <tt>u</tt>, <tt>v</tt>, <tt>w</tt>, <tt>x</tt> e <tt>y</tt> e liga-os como mostrado na figura <a href="#%_fig_3.28">3.28</a> usando os construtores de restrição primitiva <tt>adder</tt>, <tt>multiplier</tt> e <tt>constant</tt>. Assim como no simulador de circuito digital da seção <a href="#%_sec_3.3.4">3.3.4</a>, expressar essas combinações de elementos primitivos em termos de procedimentos fornece automaticamente à nossa linguagem um meio de abstração para objetos compostos.</p><p>Para assistir a rede em ação, podemos colocar sondas nos conectores <tt>C</tt> e <tt>F</tt>, usando um procedimento <tt>probe</tt> semelhante ao que usamos para monitorar os fios na seção <a href="#%_sec_3.3.4">3.3.4</a>. A colocação de uma sonda em um conector fará com que uma mensagem seja impressa sempre que o conector receber um valor:</p><p>
</p><p/><p><tt>(probe "Celsius temp" C)<br/>
(probe "Fahrenheit temp" F)<br/></tt></p><p/><p>Em seguida, definimos o valor de <tt>C</tt> para 25. (O terceiro argumento para <tt>set-value!</tt> diz a <tt>C</tt> que esta diretiva vem do <tt>user</tt>).</p><p>
</p><p/><p><tt>(set-value! C 25 'user)<br/><i>Probe: Celsius temp = 25</i><br/><i>Probe: Fahrenheit temp = 77</i><br/><i>done</i><br/></tt></p><p/><p>A sonda ligada em <tt>C</tt> desperta e relata o valor. <tt>C</tt> também propaga seu valor através da rede, conforme descrito acima. Isso define <tt>F</tt> como 77, que é relatado pela sonda em <tt>F</tt>.</p><p>Agora podemos tentar definir <tt>F</tt> para um novo valor, digamos 212:</p><p>
</p><p/><p><tt>(set-value! F 212 'user)<br/><i>Error! Contradiction (77 212)</i><br/></tt></p><p/><p>O conector reclama que sentiu uma contradição: seu valor é 77 e alguém tenta configurá-lo para 212. Se realmente queremos reutilizar a rede com novos valores, podemos dizer <tt>C</tt> esquecer seu antigo valor:</p><p>
</p><p/><p><tt>(forget-value! C 'user)<br/><i>Probe: Celsius temp = ?</i><br/><i>Probe: Fahrenheit temp = ?</i><br/><i>done</i><br/></tt></p><p/><p>
<tt>C</tt> descobre que o <tt>user</tt>, que definiu seu valor originalmente, agora recolhe esse valor, então <tt>C</tt> concorda em perder seu valor, como mostra a sonda, e informa o restante da rede desse fato. Essas informações acabam se propagando para <tt>F</tt>, que agora descobre que não possui motivos para continuar acreditando que seu próprio valor é 77. Portanto, <tt>F</tt> também renuncia ao seu valor, conforme mostrado pela sonda.</p><p>Agora isso <tt>F</tt> não possui valor, podemos defini-lo como 212:</p><p>
</p><p/><p><tt>(set-value! F 212 'user)<br/><i>Probe: Fahrenheit temp = 212</i><br/><i>Probe: Celsius temp = 100</i><br/><i>done</i><br/></tt></p><p/><p>Esse novo valor, quando propagado pela rede, força <tt>C</tt> ter um valor de 100, e isso é registrado pela sonda em <tt>C</tt>. Observe que a mesma rede é usada para calcular <tt>C</tt> dado <tt>F</tt> e calcular <tt>F</tt> dado <tt>C</tt>. Essa não direcionalidade da computação é a característica distintiva dos sistemas baseados em restrições.</p><p>
<a name="%_sec_Temp_396" id="%_sec_Temp_396"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_396">Implementando o sistema de restrições</a></h4><p>O sistema de restrição é implementado por meio de objetos procedimentais com estado local, de maneira muito semelhante ao simulador de circuito digital da seção <a href="#%_sec_3.3.4">3.3.4</a>. Embora os objetos primitivos do sistema de restrição sejam um pouco mais complexos, o sistema geral é mais simples, pois não há preocupação com agendas e atrasos lógicos.</p><p>
<a name="%_idx_3520" id="%_idx_3520"/>As operações básicas nos conectores são as seguintes:</p><p/><ul><li><a name="%_idx_3522" id="%_idx_3522"/><tt>(has-value? <<em>connector</em>>)</tt><br/> informa se o conector possui um valor.<p>
</p></li><li><a name="%_idx_3524" id="%_idx_3524"/><tt>(get-value <<em>connector</em>>)</tt><br/> retorna o valor atual do conector.<p>
</p></li><li><a name="%_idx_3526" id="%_idx_3526"/><tt>(set-value! <<em>connector</em>> <<em>new-value</em>> <<em>informant</em>>)</tt><br/> indica que o informante está solicitando ao conector que defina seu valor para o novo valor.<p>
</p></li><li><a name="%_idx_3528" id="%_idx_3528"/><tt>(forget-value! <<em>connector</em>> <<em>retractor</em>>)</tt><br/> informa ao conector que o retrator está solicitando que ele esqueça seu valor.<p>
</p></li><li><a name="%_idx_3530" id="%_idx_3530"/><tt>(connect <<em>connector</em>> <<em>new-constraint</em>>)</tt><br/> diz ao conector para participar da nova restrição.</li></ul><p/><p>Os conectores se comunicam com as restrições por meio dos procedimentos <tt>inform-about-value</tt>, que informa à restrição fornecida que o conector possui um valor e <tt>inform-about-no-value</tt>, que informa a restrição de que o conector perdeu seu valor.</p><p>
<tt>Adder</tt> constrói uma restrição de somador entre conectores de somandos <tt>a1</tt> e <tt>a2</tt> e um <tt>sum</tt> conector. Um somador é implementado como um procedimento com o estado local (o procedimento <tt>me</tt> abaixo):</p><p>
</p><p/><p><tt><a name="%_idx_3532" id="%_idx_3532"/>(define (adder a1 a2 sum)<br/>
(define (process-new-value)<br/>
(cond ((and (has-value? a1) (has-value? a2))<br/>
(set-value! sum<br/>
(+ (get-value a1) (get-value a2))<br/>
me))<br/>
((and (has-value? a1) (has-value? sum))<br/>
(set-value! a2<br/>
(- (get-value sum) (get-value a1))<br/>
me))<br/>
((and (has-value? a2) (has-value? sum))<br/>
(set-value! a1<br/>
(- (get-value sum) (get-value a2))<br/>
me))))<br/>
(define (process-forget-value)<br/>
(forget-value! sum me)<br/>
(forget-value! a1 me)<br/>
(forget-value! a2 me)<br/>
(process-new-value))<br/>
(define (me request)<br/>
(cond ((eq? request 'I-have-a-value) <br/>
(process-new-value))<br/>
((eq? request 'I-lost-my-value) <br/>
(process-forget-value))<br/>
(else <br/>
(error "Unknown request -- ADDER" request))))<br/>
(connect a1 me)<br/>
(connect a2 me)<br/>
(connect sum me)<br/>
me)<br/></tt></p><p/><p>
<tt>Adder</tt> conecta o novo somador aos conectores designados e o retorna como seu valor. O procedimento <tt>me</tt>, que representa o somador, atua como um despacho para os procedimentos locais. As seguintes “interfaces de sintaxe” (consulte a nota de rodapé<a href="#footnote_Temp_385">27</a> na seção <a href="#%_sec_3.3.4">3.3.4</a>) são usados em conjunto com o despacho:</p><p>
</p><p/><p><tt><a name="%_idx_3534" id="%_idx_3534"/>(define (inform-about-value constraint)<br/>
(constraint 'I-have-a-value))<br/><a name="%_idx_3536" id="%_idx_3536"/>(define (inform-about-no-value constraint)<br/>
(constraint 'I-lost-my-value))<br/></tt></p><p/><p>O procedimento local do adicionador <tt>process-new-value</tt> é chamado quando o somador é informado de que um de seus conectores possui um valor. O somador primeiro verifica se ambos <tt>a1</tt> e <tt>a2</tt> possui valores. Se sim, diz <tt>sum</tt> para definir seu valor como a soma dos dois suplementos. O argumento <tt>informant</tt> para <tt>set-value!</tt> é <tt>me</tt>, que é o próprio objeto adicionador. E se <tt>a1</tt> e <tt>a2</tt> ambos não tiverem valores, o somador verifica se talvez <tt>a1</tt> e <tt>sum</tt> tenham valores. Nesse caso, define-se <tt>a2</tt> para a diferença desses dois. Finalmente, se <tt>a2</tt> e <tt>sum</tt> tiverem valores, isso fornece ao somador informações suficientes para definir <tt>a1</tt>. Se for dito ao adicionador que um de seus conectores perdeu um valor, ele solicitará que todos os conectores agora percam seus valores. (Somente os valores definidos por esse somador são realmente perdidos). Em seguida, ele é executado <tt>process-new-value</tt>. O motivo desta última etapa é que um ou mais conectores ainda podem ter um valor (ou seja, um conector pode ter um valor que não foi originalmente definido pelo somador) e esses valores podem precisar ser propagados de volta através do somador.</p><p>Um multiplicador é muito semelhante a um somador. Ele definirá sua <tt>product</tt> para 0 se um dos fatores for 0, mesmo que o outro fator não seja conhecido.</p><p>
</p><p/><p><tt><a name="%_idx_3538" id="%_idx_3538"/>(define (multiplier m1 m2 product)<br/>
(define (process-new-value)<br/>
(cond ((or (and (has-value? m1) (= (get-value m1) 0))<br/>
(and (has-value? m2) (= (get-value m2) 0)))<br/>
(set-value! product 0 me))<br/>
((and (has-value? m1) (has-value? m2))<br/>
(set-value! product<br/>
(* (get-value m1) (get-value m2))<br/>
me))<br/>
((and (has-value? product) (has-value? m1))<br/>
(set-value! m2<br/>
(/ (get-value product) (get-value m1))<br/>
me))<br/>
((and (has-value? product) (has-value? m2))<br/>
(set-value! m1<br/>
(/ (get-value product) (get-value m2))<br/>
me))))<br/>
(define (process-forget-value)<br/>
(forget-value! product me)<br/>
(forget-value! m1 me)<br/>
(forget-value! m2 me)<br/>
(process-new-value))<br/>
(define (me request)<br/>
(cond ((eq? request 'I-have-a-value)<br/>
(process-new-value))<br/>
((eq? request 'I-lost-my-value)<br/>
(process-forget-value))<br/>
(else<br/>
(error "Unknown request -- MULTIPLIER" request))))<br/>
(connect m1 me)<br/>
(connect m2 me)<br/>
(connect product me)<br/>
me)<br/></tt></p><p/><p>O construtor do <tt>constant</tt> simplesmente define o valor do conector designado. Qualquer mensagem <tt>I-have-a-value</tt> ou <tt>I-lost-my-value</tt> enviada para a caixa constante produzirá um erro.</p><p>
</p><p/><p><tt><a name="%_idx_3540" id="%_idx_3540"/>(define (constant value connector)<br/>
(define (me request)<br/>
(error "Unknown request -- CONSTANT" request))<br/>
(connect connector me)<br/>
(set-value! connector value me)<br/>
me)<br/></tt></p><p/><p>Por fim, uma sonda imprime uma mensagem sobre a configuração ou a desativação do conector designado:</p><p>
</p><p/><p><tt><a name="%_idx_3542" id="%_idx_3542"/>(define (probe name connector)<br/>
(define (print-probe value)<br/>
(newline)<br/>
(display "Probe: ")<br/>
(display name)<br/>
(display " = ")<br/>
(display value))<br/>
(define (process-new-value)<br/>
(print-probe (get-value connector)))<br/>
(define (process-forget-value)<br/>
(print-probe "?"))<br/>
(define (me request)<br/>
(cond ((eq? request 'I-have-a-value)<br/>
(process-new-value))<br/>
((eq? request 'I-lost-my-value)<br/>
(process-forget-value))<br/>
(else<br/>
(error "Unknown request -- PROBE" request))))<br/>
(connect connector me)<br/>
me)<br/></tt></p><p/><p/><p>
<a name="%_sec_Temp_397" id="%_sec_Temp_397"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_397">Representando conectores</a></h4><p>
<a name="%_idx_3544" id="%_idx_3544"/>Um conector é representado como um objeto processual com variáveis de estado local <tt>value</tt>, o valor atual do conector; <tt>informant</tt>, o objeto que define o valor do conector; e <tt>constraints</tt>, uma lista das restrições nas quais o conector participa.</p><p>
</p><p/><p><tt><a name="%_idx_3546" id="%_idx_3546"/>(define (make-connector)<br/>
(let ((value false) (informant false) (constraints '()))<br/>
(define (set-my-value newval setter)<br/>
(cond ((not (has-value? me))<br/>
(set! value newval)<br/>
(set! informant setter)<br/>
(for-each-except setter<br/>
inform-about-value<br/>
constraints))<br/>
((not (= value newval))<br/>
(error "Contradiction" (list value newval)))<br/>
(else 'ignored)))<br/>
(define (forget-my-value retractor)<br/>
(if (eq? retractor informant)<br/>
(begin (set! informant false)<br/>
(for-each-except retractor<br/>
inform-about-no-value<br/>
constraints))<br/>
'ignored))<br/>
(define (connect new-constraint)<br/>
(if (not (memq new-constraint constraints))<br/>
(set! constraints <br/>
(cons new-constraint constraints)))<br/>
(if (has-value? me)<br/>
(inform-about-value new-constraint))<br/>
'done)<br/>
(define (me request)<br/>
(cond ((eq? request 'has-value?)<br/>
(if informant true false))<br/>
((eq? request 'value) value)<br/>
((eq? request 'set-value!) set-my-value)<br/>
((eq? request 'forget) forget-my-value)<br/>
((eq? request 'connect) connect)<br/>
(else (error "Unknown operation -- CONNECTOR"<br/>
request))))<br/>
me))<br/></tt></p><p/><p/><p>O procedimento local do conector <tt>set-my-value</tt> é chamado quando há uma solicitação para definir o valor do conector. Se o conector não tiver atualmente um valor, ele definirá seu valor e lembrará como <tt>informant</tt> a restrição que solicitou o valor a ser definido.<a name="call_footnote_Temp_398" href="#footnote_Temp_398" id="call_footnote_Temp_398"><sup><small>32</small></sup></a> Em seguida, o conector notificará todas as restrições participantes, exceto a restrição que solicitou que o valor fosse definido. Isso é realizado usando o seguinte iterador, que aplica um procedimento designado a todos os itens de uma lista, exceto um dado:</p><p>
</p><p/><p><tt><a name="%_idx_3548" id="%_idx_3548"/>(define (for-each-except exception procedure list)<br/>
(define (loop items)<br/>
(cond ((null? items) 'done)<br/>
((eq? (car items) exception) (loop (cdr items)))<br/>
(else (procedure (car items))<br/>
(loop (cdr items)))))<br/>
(loop list))<br/></tt></p><p/><p/><p>Se um conector é solicitado a esquecer seu valor, ele executa o procedimento local <tt>forget-my-value</tt>, que primeiro verifica se a solicitação é proveniente do mesmo objeto que definiu o valor originalmente. Nesse caso, o conector informa suas restrições associadas sobre a perda do valor.</p><p>O procedimento local <tt>connect</tt> adiciona a nova restrição designada à lista de restrições, se ainda não estiver nessa lista. Então, se o conector tiver um valor, ele informa a nova restrição desse fato.</p><p>O procedimento do conector <tt>me</tt> serve como despacho para outros procedimentos internos e também representa o conector como um objeto. Os procedimentos a seguir fornecem uma interface de sintaxe para o envio:</p><p>
</p><p/><p><tt><a name="%_idx_3550" id="%_idx_3550"/>(define (has-value? connector)<br/>
(connector 'has-value?))<br/><a name="%_idx_3552" id="%_idx_3552"/>(define (get-value connector)<br/>
(connector 'value))<br/><a name="%_idx_3554" id="%_idx_3554"/>(define (set-value! connector new-value informant)<br/>
((connector 'set-value!) new-value informant))<br/><a name="%_idx_3556" id="%_idx_3556"/>(define (forget-value! connector retractor)<br/>
((connector 'forget) retractor))<br/><a name="%_idx_3558" id="%_idx_3558"/>(define (connect connector new-constraint)<br/>
((connector 'connect) new-constraint))<br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_3.33" id="%_thm_3.33"/>
<b>Exercício 3.33.</b> Usando multiplicador primitivo, somador e restrições constantes, defina um procedimento <a name="%_idx_3560" id="%_idx_3560"/><tt>averager</tt> que leva três conectores <tt>a</tt>, <tt>b</tt> e <tt>c</tt> como entradas e estabelece a restrição de que o valor de <tt>c</tt> é a média dos valores de <tt>a</tt> e <tt>b</tt>.</p><p/><p>
</p><p><a name="%_thm_3.34" id="%_thm_3.34"/>
<b>Exercício 3.34.</b> <a name="%_idx_3562" id="%_idx_3562"/>Louis Reasoner quer construir um squarer, um dispositivo de restrição com dois terminais, de modo que o valor do conector <tt>b</tt> no segundo terminal sempre será o quadrado do valor <tt>a</tt> no primeiro terminal. Ele propõe o seguinte dispositivo simples feito de um multiplicador:</p><p>
</p><p/><p><tt>(define (squarer a b)<br/>
(multiplier a a b))<br/></tt></p><p/><p>Há uma falha séria nessa ideia. Explique.</p><p/><p>
</p><p><a name="%_thm_3.35" id="%_thm_3.35"/>
<b>Exercício 3.35.</b> <a name="%_idx_3564" id="%_idx_3564"/>Ben Bitdiddle diz a Louis que uma maneira de evitar problemas no exercício <a href="#%_thm_3.34">3.34</a> é definir um squarer como uma nova restrição primitiva. Preencha as partes ausentes no esboço de Ben para obter um procedimento para implementar essa restrição:</p><p>
</p><p/><p><tt>(define (squarer a b)<br/>
(define (process-new-value)<br/>
(if (has-value? b)<br/>
(if (< (get-value b) 0)<br/>
(error "square less than 0 -- SQUARER" (get-value b))<br/>
<<em>alternative1</em>>)<br/>
<<em>alternative2</em>>))<br/>
(define (process-forget-value) <<em>body1</em>>)<br/>
(define (me request) <<em>body2</em>>)<br/>
<<em>rest of definition</em>><br/>
me)<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_3.36" id="%_thm_3.36"/>
<b>Exercício 3.36.</b> Suponha que avaliemos a seguinte sequência de expressões no ambiente global:</p><p>
</p><p/><p><tt>(define a (make-connector))<br/>
(define b (make-connector))<br/>
(set-value! a 10 'user)<br/></tt></p><p/><p>Em algum momento durante a avaliação de <tt>set-value!</tt>, a seguinte expressão do procedimento local do conector é avaliada:</p><p>
</p><p/><p><tt>(for-each-except setter inform-about-value constraints)<br/></tt></p><p/><p>Desenhe um diagrama de ambiente mostrando o ambiente em que a expressão acima é avaliada.</p><p/><p>
</p><p><a name="%_thm_3.37" id="%_thm_3.37"/>
<b>Exercício 3.37.</b> O procedimento <tt>celsius-fahrenheit-converter</tt> é complicado quando comparado com um estilo de definição mais orientado à expressão, como</p><p>
</p><p/><p><tt><a name="%_idx_3566" id="%_idx_3566"/>(define (celsius-fahrenheit-converter x)<br/>
(c+ (c* (c/ (cv 9) (cv 5))<br/>
x)<br/>
(cv 32)))<br/>
(define C (make-connector))<br/>
(define F (celsius-fahrenheit-converter C))<br/></tt></p><p/><p>Aqui <tt>c+</tt>, <tt>c*</tt>, etc. são as versões de “restrição” das operações aritméticas. Por exemplo, <tt>c+</tt> usa dois conectores como argumentos e retorna um conector relacionado a eles por uma restrição de somador:</p><p>
</p><p/><p><tt>(define (c+ x y)<br/>
(let ((z (make-connector)))<br/>
(adder x y z)<br/>
z))<br/></tt></p><p/><p>Defina procedimentos análogos <tt>c-</tt>, <tt>c*</tt>, <tt>c/</tt> e <tt>cv</tt> (valor constante) que nos permitem definir restrições compostas como no exemplo do conversor acima.<a name="call_footnote_Temp_404" href="#footnote_Temp_404" id="call_footnote_Temp_404"><sup><small>33</small></sup></a>
</p><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_349" href="#call_footnote_Temp_349" id="footnote_Temp_349"><sup><small>16</small></sup></a> <tt>Set-car!</tt> e <tt>set-cdr!</tt> retornam <a name="%_idx_3148" id="%_idx_3148"/><a name="%_idx_3150" id="%_idx_3150"/><a name="%_idx_3152" id="%_idx_3152"/><a name="%_idx_3154" id="%_idx_3154"/>valores dependentes da implementação. Como <tt>set!</tt>, eles devem ser usados apenas para seus efeitos.</p><p><a name="footnote_Temp_350" href="#call_footnote_Temp_350" id="footnote_Temp_350"><sup><small>17</small></sup></a> Vimos a partir disso que as operações de mutação nas listas podem criar “lixo” que não faz parte de nenhuma estrutura acessível. Veremos na seção <a href="book-Z-H-33.html#%_sec_5.3.2">5.3.2</a> que os sistemas de gerenciamento de memória Lisp incluem um <a name="%_idx_3156" id="%_idx_3156"/><em>coletor de lixo</em>, que identifica e recicla o espaço de memória usado por pares desnecessários.</p><p><a name="footnote_Temp_351" href="#call_footnote_Temp_351" id="footnote_Temp_351"><sup><small>18</small></sup></a> <tt>Get-new-pair</tt> é uma das operações que devem ser implementadas como parte do gerenciamento de memória necessário por uma implementação Lisp. Discutiremos isso na seção <a href="book-Z-H-33.html#%_sec_5.3.1">5.3.1</a>.</p><p><a name="footnote_Temp_356" href="#call_footnote_Temp_356" id="footnote_Temp_356"><sup><small>19</small></sup></a> Os dois pares são distintos, pois cada chamada para <tt>cons</tt> retorna um novo par. Os símbolos são compartilhados; no Scheme existe um símbolo único com qualquer <a name="%_idx_3184" id="%_idx_3184"/>nome. Como o Scheme não oferece uma maneira de modificar um símbolo, esse compartilhamento é indetectável. Observe também que o compartilhamento é o que nos permite comparar símbolos usando <tt>eq?</tt>, que simplesmente verifica a igualdade de ponteiros.</p><p><a name="footnote_Temp_357" href="#call_footnote_Temp_357" id="footnote_Temp_357"><sup><small>20</small></sup></a> As sutilezas de lidar com o compartilhamento de objetos de dados mutáveis refletem os problemas subjacentes de “igualdade” e “mudança” levantados na seção <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a>. Mencionamos lá que admitir mudanças em nossa linguagem requer que um objeto composto tenha uma “identidade” que seja algo diferente das peças em que é composto. No Lisp, consideramos essa “identidade” como a qualidade testada pelo <tt>eq?</tt>, ou seja, pela igualdade de ponteiros. Como na maioria das implementações do Lisp, um ponteiro é essencialmente um endereço de memória, “resolvemos o problema” de definir a identidade dos objetos, estipulando que um objeto de dados “em si” é a informação armazenada em um determinado conjunto de locais de memória no computador. Isso é suficiente para programas Lisp simples, mas dificilmente é uma maneira geral de resolver a questão da “igualdade” nos modelos computacionais.</p><p><a name="footnote_Temp_364" href="#call_footnote_Temp_364" id="footnote_Temp_364"><sup><small>21</small></sup></a> Por outro lado, do ponto de vista da implementação, a atribuição exige que modifiquemos o ambiente, que é uma estrutura de dados mutável. Assim, a atribuição e a mutação são equipotentes: cada uma pode ser implementada em termos da outra.</p><p><a name="footnote_Temp_366" href="#call_footnote_Temp_366" id="footnote_Temp_366"><sup><small>22</small></sup></a> Se o primeiro item for o item final na fila, o ponteiro da frente será a lista vazia após a exclusão, que marcará a fila como vazia; não precisamos nos preocupar em atualizar o ponteiro traseiro, que ainda apontará para o item excluído, pois <tt>empty-queue?</tt> olha apenas para o ponteiro da frente.</p><p><a name="footnote_Temp_370" href="#call_footnote_Temp_370" id="footnote_Temp_370"><sup><small>23</small></sup></a> Cuidado para não fazer o interpretador tentar imprimir uma estrutura que contenha ciclos. (Veja exercício <a href="#%_thm_3.13">3.13</a>).</p><p><a name="footnote_Temp_371" href="#call_footnote_Temp_371" id="footnote_Temp_371"><sup><small>24</small></sup></a> Porque <tt>assoc</tt> usa <tt>equal?</tt>, ele pode reconhecer teclas que são símbolos, números ou estrutura de lista.</p><p><a name="footnote_Temp_372" href="#call_footnote_Temp_372" id="footnote_Temp_372"><sup><small>25</small></sup></a> Assim, o primeiro par da espinha dorsal é o objeto que representa a tabela “em si”; isto é, um ponteiro para a tabela é um ponteiro para este par. Esse mesmo par da espinha dorsal sempre inicia a tabela. Se não organizarmos dessa maneira, <tt>insert!</tt> precisaria retornar um novo valor para o início da tabela ao adicionar um novo registrador.</p><p><a name="footnote_Temp_379" href="#call_footnote_Temp_379" id="footnote_Temp_379"><sup><small>26</small></sup></a> Um somador completo é um elemento básico do circuito usado na adição de dois números binários. Aqui A e B são os bits nas posições correspondentes nos dois números a serem adicionados e C<sub><em>i</em><em>n</em></sub> é o bit de transporte do local de adição à direita. O circuito gera SUM, que é o bit de soma na posição correspondente, e C<sub><em>o</em><em>u</em><em>t</em></sub>, que é o bit de transporte a ser propagado para a esquerda.</p><p><a name="footnote_Temp_385" href="#call_footnote_Temp_385" id="footnote_Temp_385"><sup><small>27</small></sup></a> Esses procedimentos são simplesmente açúcar sintático que permitem <a name="%_idx_3400" id="%_idx_3400"/><a name="%_idx_3402" id="%_idx_3402"/>usarmos a sintaxe processual comum para acessar os procedimentos locais dos objetos. É impressionante que possamos trocar o papel de “procedimentos” e “dados” de uma maneira tão simples. Por exemplo, se escrevermos <tt>(wire 'get-signal)</tt> pensamos em <tt>wire</tt> como um procedimento chamado com a mensagem <tt>get-signal</tt> como entrada. Como alternativa, escrever <tt>(get-signal wire)</tt> nos encoraja a pensar em <tt>wire</tt> como um objeto de dados que é a entrada para um procedimento <tt>get-signal</tt>. A verdade é que, em uma linguagem na qual podemos lidar com procedimentos como objetos, não há diferença fundamental entre “procedimentos” e “dados” e podemos escolher nosso açúcar sintático para nos permitir programar em qualquer estilo que escolhemos.</p><p><a name="footnote_Temp_390" href="#call_footnote_Temp_390" id="footnote_Temp_390"><sup><small>28</small></sup></a> A agenda é uma <a name="%_idx_3452" id="%_idx_3452"/><a name="%_idx_3454" id="%_idx_3454"/>lista encabeçada, como as tabelas na seção <a href="#%_sec_3.3.3">3.3.3.</a>, mas como a lista é encabeçada pelo tempo, não precisamos de um cabeçalho fictício adicional (como o <tt>*table*</tt> símbolo usado com tabelas).</p><p><a name="footnote_Temp_391" href="#call_footnote_Temp_391" id="footnote_Temp_391"><sup><small>29</small></sup></a> Observe que a expressão <tt>if</tt> neste procedimento não possui a expressão <<em>alternative</em>>. Tal “declaração <tt>if</tt> de um braço” <a name="%_idx_3474" id="%_idx_3474"/><a name="%_idx_3476" id="%_idx_3476"/>é usada para decidir se deve fazer algo, em vez de selecionar entre duas expressões. A expressão <tt>if</tt> retornará um valor não especificado se o predicado for falso e não houver <<em>alternative</em>>.</p><p><a name="footnote_Temp_392" href="#call_footnote_Temp_392" id="footnote_Temp_392"><sup><small>30</small></sup></a> Dessa forma, o horário atual sempre será o horário da ação processada mais recentemente. Armazenar esse horário no início da agenda garante que ele ainda estará disponível, mesmo que o segmento de tempo associado tenha sido excluído.</p><p><a name="footnote_Temp_394" href="#call_footnote_Temp_394" id="footnote_Temp_394"><sup><small>31</small></sup></a> A propagação de restrições apareceu pela primeira vez no incrivelmente prospectivo <a name="%_idx_3486" id="%_idx_3486"/>Sistema SKETCHPAD<a name="%_idx_3488" id="%_idx_3488"/> de Ivan Sutherland (1963). Um belo sistema de propagação de restrições baseado na <a name="%_idx_3490" id="%_idx_3490"/>linguagem Smalltalk foi desenvolvida por <a name="%_idx_3492" id="%_idx_3492"/>Alan Borning (1977) em <a name="%_idx_3494" id="%_idx_3494"/>Centro de Pesquisa Xerox Palo Alto. Sussman, Stallman e Steele <a name="%_idx_3496" id="%_idx_3496"/><a name="%_idx_3498" id="%_idx_3498"/><a name="%_idx_3500" id="%_idx_3500"/><a name="%_idx_3502" id="%_idx_3502"/><a name="%_idx_3504" id="%_idx_3504"/><a name="%_idx_3506" id="%_idx_3506"/>aplicaram a propagação de restrições à análise de circuitos elétricos (Sussman e Stallman, 1975; Sussman e Steele, 1980). O TK! Solver (Konopasek e Jayaraman 1984) é um extenso ambiente de modelagem baseado em restrições.</p><p><a name="footnote_Temp_398" href="#call_footnote_Temp_398" id="footnote_Temp_398"><sup><small>32</small></sup></a> O <tt>setter</tt> pode não ser uma restrição. No nosso exemplo de temperatura, usamos <tt>user</tt> como o <tt>setter</tt>.</p><p><a name="footnote_Temp_404" href="#call_footnote_Temp_404" id="footnote_Temp_404"><sup><small>33</small></sup></a> O formato orientado às expressões é conveniente, pois evita a necessidade de nomear as expressões intermediárias em um cálculo. Nossa formulação original da <a name="%_idx_3568" id="%_idx_3568"/><a name="%_idx_3570" id="%_idx_3570"/><a name="%_idx_3572" id="%_idx_3572"/><a name="%_idx_3574" id="%_idx_3574"/><a name="%_idx_3576" id="%_idx_3576"/>linguagem de restrição é complicada da mesma maneira que muitas linguagens são complicadas ao lidar com operações em dados compostos. Por exemplo, se quisermos calcular o produto (<em>a</em> + <em>b</em>) · (<em>c</em> + <em>d</em>), onde as variáveis representam vetores, poderíamos trabalhar em “estilo imperativo”, usando procedimentos que definem os valores dos argumentos de vetor designados, mas não retornam vetores como valores:</p><p/><p><tt>(v-sum a b temp1)<br/>
(v-sum c d temp2)<br/>
(v-prod temp1 temp2 answer)<br/></tt></p><p/><p>Como alternativa, poderíamos lidar com expressões, usando procedimentos que retornam vetores como valores e, assim, evitamos mencionar explicitamente <tt>temp1</tt> e <tt>temp2</tt>:</p><p/><p><tt>(define answer (v-prod (v-sum a b) (v-sum c d)))<br/></tt></p><p/><p>Como o Lisp nos permite retornar objetos compostos como valores de procedimentos, podemos transformar nossa linguagem de restrição de estilo imperativa em um estilo orientado a expressão, como mostrado neste exercício. Em linguagens empobrecidas no manuseio de objetos compostos, como Algol, Basic e Pascal (a menos que alguém use explicitamente variáveis de ponteiro Pascal), geralmente fica-se preso ao estilo imperativo ao manipular objetos compostos. Dada a vantagem do formato orientado à expressão, pode-se perguntar se há alguma razão para implementar o sistema em estilo imperativo, como fizemos nesta seção. Uma razão é que a linguagem de restrição não orientada a expressão fornece um identificador para objetos de restrição (por exemplo, o valor do procedimento <tt>adder</tt>), bem como nos objetos do conector. Isso é útil se desejarmos estender o sistema com novas operações que se comunicam diretamente com restrições, em vez de apenas indiretamente através de operações em conectores. Embora seja fácil implementar o estilo orientado à expressão em termos da implementação imperativa, é muito difícil fazer o inverso.</p></div>
</body>
</html>