-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-29.html
1064 lines (782 loc) · 151 KB
/
book-Z-H-29.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
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<?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_4.4" id="%_sec_4.4"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_4.4">4.4 Programação lógica</a></h2><p>
<a name="%_idx_5028" id="%_idx_5028"/>
<a name="%_idx_5030" id="%_idx_5030"/><a name="%_idx_5032" id="%_idx_5032"/><a name="%_idx_5034" id="%_idx_5034"/><a name="%_idx_5036" id="%_idx_5036"/>No capítulo 1, enfatizamos que a ciência da computação lida com o conhecimento imperativo (como), enquanto a matemática lida com o conhecimento declarativo (o que é). De fato, as linguagens de programação exigem que o programador expresse conhecimento de uma forma que indique os métodos passo a passo para resolver problemas específicos. Por outro lado, as linguagens de alto nível fornecem, como parte da implementação da linguagem, uma quantidade substancial de conhecimento metodológico que libera o usuário da preocupação com inúmeros detalhes de como uma computação especificada progredirá.</p><p>A maioria das linguagens de programação, incluindo Lisp, é organizada em torno da computação dos valores das funções matemáticas. Linguagens orientadas a expressões (como Lisp, Fortran e Algol) capitalizam o “trocadilho” de que uma expressão que descreve o valor de uma função também pode ser interpretada como um meio de calcular esse valor. Por esse motivo, a maioria das linguagens de programação é fortemente influenciada por cálculos unidirecionais (cálculos com entradas e saídas bem definidas). Existem, no entanto, linguagens de programação radicalmente diferentes que relaxam esse viés. Vimos um exemplo na seção <a href="book-Z-H-22.html#%_sec_3.3.5">3.3.5</a>, onde os objetos de computação eram restrições aritméticas. Em um sistema de restrição, a direção e a ordem de cálculo não são tão bem especificadas; ao realizar um cálculo, o sistema deve, portanto, fornecer um conhecimento mais detalhado do “como fazer” do que seria o caso de um cálculo aritmético comum. Isso não significa, no entanto, que o usuário esteja totalmente liberado da responsabilidade de fornecer conhecimento imperativo. Existem muitas redes de restrições que implementam o mesmo conjunto de restrições, e o usuário deve escolher no conjunto de redes matematicamente equivalentes uma rede adequada para especificar uma computação específica.</p><p>O avaliador não determinístico do programa da seção <a href="book-Z-H-28.html#%_sec_4.3">4.3.</a> também se afasta da visão de que a programação é sobre a construção de algoritmos para calcular funções unidirecionais. Em uma linguagem não determinística, as expressões podem ter mais de um valor e, como resultado, o cálculo é <a name="%_idx_5038" id="%_idx_5038"/>lidar com relações e não com funções de valor único. A programação lógica estende essa ideia combinando uma visão relacional da programação com um tipo poderoso de correspondência de padrões simbólicos chamada <em>unificação</em>.<a name="call_footnote_Temp_645" href="#footnote_Temp_645" id="call_footnote_Temp_645"><sup><small>58</small></sup></a></p><p>
<a name="%_idx_5070" id="%_idx_5070"/><a name="%_idx_5072" id="%_idx_5072"/>Essa abordagem, quando funciona, pode ser uma maneira muito poderosa de escrever programas. Parte do poder vem do fato de que um único fato “o que é” pode ser usado para resolver vários problemas diferentes que teriam componentes diferentes de “como fazer”. Como exemplo, considere a operação <a name="%_idx_5074" id="%_idx_5074"/><tt>append</tt>, que recebe duas listas como argumentos e combina seus elementos para formar uma única lista. Em uma linguagem processual como Lisp, poderíamos definir <tt>append</tt> em termos do construtor de lista básico <tt>cons</tt>, como fizemos na seção <a href="book-Z-H-15.html#%_sec_2.2.1">2.2.1</a>:</p><p>
</p><p/><p><tt>(define (append x y)<br/>
(if (null? x)<br/>
y<br/>
(cons (car x) (append (cdr x) y))))<br/></tt></p><p/><p>Esse procedimento pode ser considerado como uma tradução para o Lisp das duas regras a seguir, a primeira abordando o caso em que a primeira lista está vazia e a segunda tratando o caso de uma lista não vazia, que é uma <tt>cons</tt> de duas partes:</p><p>
</p><p/><ul><li>Para qualquer lista <tt>y</tt>, a lista vazia e <tt>y</tt><tt>append</tt> formar <tt>y</tt>.<p>
</p></li><li>Para qualquer <tt>u</tt>, <tt>v</tt>, <tt>y</tt> e <tt>z</tt>, <tt>(cons u v)</tt> e <tt>y</tt><tt>append</tt> formar <tt>(cons u z)</tt> e se <tt>v</tt> e <tt>y</tt> <tt>append</tt> formar <tt>z</tt>.<a name="call_footnote_Temp_646" href="#footnote_Temp_646" id="call_footnote_Temp_646"><sup><small>59</small></sup></a>
</li></ul><p/><p>Usando o procedimento <tt>append</tt>, podemos responder a perguntas como</p><blockquote>Encontre o <tt>append</tt> do <tt>(a b)</tt> e <tt>(c d)</tt>.</blockquote><p>Mas as mesmas duas regras também são suficientes para responder aos seguintes tipos de perguntas, que o procedimento não pode responder:</p><p>
</p><blockquote>Encontre uma lista <tt>y</tt> aquele <tt>append</tt> s com <tt>(a b)</tt> para produzir <tt>(a b c d)</tt>.<p>Encontre todo <tt>x</tt> e <tt>y</tt> aquele <tt>append</tt> formar <tt>(a b c d)</tt>.</p></blockquote><p>
<a name="%_idx_5076" id="%_idx_5076"/><a name="%_idx_5078" id="%_idx_5078"/>Numa linguagem de programação lógica, o programador escreve um <tt>append</tt> “Procedimento” declarando as duas regras sobre <tt>append</tt> dado anteriormente. O conhecimento de “como fazer” é fornecido automaticamente pelo interpretador para permitir que este único par de regras seja usado para responder aos três tipos de perguntas sobre <tt>append</tt>.<a name="call_footnote_Temp_647" href="#footnote_Temp_647" id="call_footnote_Temp_647"><sup><small>60</small></sup></a></p><p>As linguagens de programação lógica contemporânea (incluindo a que implementamos aqui) possuem deficiências substanciais, pois seus métodos gerais de “como fazer” podem levá-los a laços infinitos espúrios ou outro comportamento indesejável. A programação lógica é um campo ativo de pesquisa em ciência da computação.<a name="call_footnote_Temp_648" href="#footnote_Temp_648" id="call_footnote_Temp_648"><sup><small>61</small></sup></a></p><p>No início deste capítulo, exploramos a tecnologia de implementação de interpretadores e descrevemos os elementos essenciais para um interpretador para uma linguagem do tipo Lisp (de fato, para um interpretador para qualquer linguagem convencional). Agora, aplicaremos essas ideias para discutir um interpretador para uma linguagem de programação lógica. Chamamos essa <a name="%_idx_5090" id="%_idx_5090"/>linguagem de <em>linguagem de consulta</em>, pois é muito útil para recuperar informações de bancos de dados, formulando <a name="%_idx_5092" id="%_idx_5092"/><em>consultas</em>, ou perguntas, expressas na linguagem. Mesmo que a linguagem de consulta seja muito diferente da Lisp, acharemos conveniente descrever a linguagem em termos da mesma estrutura geral que usamos desde o início: como uma coleção de elementos primitivos, com meios de combinação que nos permitem combine elementos simples para criar elementos mais complexos e meios de abstração que nos permitam considerar elementos complexos como unidades conceituais únicas. Um interpretador para uma linguagem de programação lógica é consideravelmente mais complexo que um interpretador para uma linguagem como Lisp. No entanto, veremos <a name="%_idx_5094" id="%_idx_5094"/>que nosso interpretador de linguagem de consulta contém muitos dos mesmos elementos encontrados no interpretador da seção <a href="book-Z-H-26.html#%_sec_4.1">4.1</a>. Em particular, haverá uma parte “eval” que classifica expressões de acordo com o tipo e uma parte “apply” que implementa o mecanismo de abstração da linguagem (procedimentos no caso do Lisp e <em>regras</em> no caso de programação lógica). Além disso, um papel central é desempenhado na implementação por uma estrutura de dados de quadro, que determina a correspondência entre símbolos e seus valores associados. Um aspecto adicional interessante de nossa implementação em linguagem de consulta é que fazemos uso substancial de fluxos, que foram introduzidos no capítulo 3.<a name="%_sec_4.4.1" id="%_sec_4.4.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_4.4.1">4.4.1 Recuperação dedutiva de informação</a></h3><p>
<a name="%_idx_5096" id="%_idx_5096"/>
<a name="%_idx_5098" id="%_idx_5098"/>A programação lógica é excelente ao fornecer interfaces para bancos de dados para recuperação de informações. A linguagem de consulta que implementaremos neste capítulo foi projetada para ser usada dessa maneira.</p><p>Para ilustrar o que o sistema de consulta faz, mostraremos como ele pode ser usado para gerenciar a base de dados de registradores de pessoal para <a name="%_idx_5100" id="%_idx_5100"/>Microshaft, uma próspera empresa de alta tecnologia na área de Boston. A linguagem fornece acesso orientado a padrões para informações pessoais e também pode tirar proveito das regras gerais para fazer deduções lógicas.</p><p>
<a name="%_sec_Temp_649" id="%_sec_Temp_649"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_649">Uma base de dados de amostra</a></h4><p>
<a name="%_idx_5102" id="%_idx_5102"/>
<a name="%_idx_5104" id="%_idx_5104"/><a name="%_idx_5106" id="%_idx_5106"/>A base de dados de pessoal da Microshaft contém <em>asserções</em> sobre o pessoal da empresa. Aqui estão as informações sobre Ben Bitdiddle, o assistente de computador residente:</p><p>
</p><p/><p><tt>(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))<br/>
(job (Bitdiddle Ben) (computer wizard))<br/>
(salary (Bitdiddle Ben) 60000)<br/></tt></p><p/><p>Cada asserção é uma lista (neste caso, uma tripla) cujos elementos podem ser listas.</p><p>Como assistente residente, Ben é responsável pela divisão de computadores da empresa e supervisiona dois programadores e um técnico. Aqui estão as informações sobre eles:</p><p>
</p><p/><p><tt>(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78))<br/>
(job (Hacker Alyssa P) (computer programmer))<br/>
(salary (Hacker Alyssa P) 40000)<br/>
(supervisor (Hacker Alyssa P) (Bitdiddle Ben))<br/>
(address (Fect Cy D) (Cambridge (Ames Street) 3))<br/>
(job (Fect Cy D) (computer programmer))<br/>
(salary (Fect Cy D) 35000)<br/>
(supervisor (Fect Cy D) (Bitdiddle Ben))<br/>
(address (Tweakit Lem E) (Boston (Bay State Road) 22))<br/>
(job (Tweakit Lem E) (computer technician))<br/>
(salary (Tweakit Lem E) 25000)<br/>
(supervisor (Tweakit Lem E) (Bitdiddle Ben))<br/></tt></p><p/><p>Há também um estagiário programador, supervisionado por Alyssa:</p><p/><p><tt>(address (Reasoner Louis) (Slumerville (Pine Tree Road) 80))<br/>
(job (Reasoner Louis) (computer programmer trainee))<br/>
(salary (Reasoner Louis) 30000)<br/>
(supervisor (Reasoner Louis) (Hacker Alyssa P))<br/></tt></p><p/><p>Todas essas pessoas estão na divisão de computadores, conforme indicado pela palavra <tt>computer</tt> como o primeiro item em suas descrições de cargo.</p><p>Ben é um funcionário de alto nível. Seu supervisor é a grande roda da empresa:</p><p>
</p><p/><p><tt>(supervisor (Bitdiddle Ben) (Warbucks Oliver))<br/>
(address (Warbucks Oliver) (Swellesley (Top Heap Road)))<br/>
(job (Warbucks Oliver) (administration big wheel))<br/>
(salary (Warbucks Oliver) 150000)<br/></tt></p><p/><p/><p>Além da divisão de computadores supervisionada por Ben, a empresa possui uma divisão de contabilidade, composta por um contador principal e seu assistente:</p><p>
</p><p/><p><tt>(address (Scrooge Eben) (Weston (Shady Lane) 10))<br/>
(job (Scrooge Eben) (accounting chief accountant))<br/>
(salary (Scrooge Eben) 75000)<br/>
(supervisor (Scrooge Eben) (Warbucks Oliver))<br/>
(address (Cratchet Robert) (Allston (N Harvard Street) 16))<br/>
(job (Cratchet Robert) (accounting scrivener))<br/>
(salary (Cratchet Robert) 18000)<br/>
(supervisor (Cratchet Robert) (Scrooge Eben))<br/></tt></p><p/><p>Há também uma secretária para a grande roda:</p><p>
</p><p/><p><tt>(address (Aull DeWitt) (Slumerville (Onion Square) 5))<br/>
(job (Aull DeWitt) (administration secretary))<br/>
(salary (Aull DeWitt) 25000)<br/>
(supervisor (Aull DeWitt) (Warbucks Oliver))<br/></tt></p><p/><p/><p>O banco de dados também contém afirmações sobre quais tipos de trabalhos podem ser realizados por pessoas que possuem outros tipos de trabalhos. Por exemplo, um assistente de computador pode fazer os trabalhos de um programador de computador e de um técnico de computador:</p><p>
</p><p/><p><tt>(can-do-job (computer wizard) (computer programmer))<br/>
(can-do-job (computer wizard) (computer technician))<br/></tt></p><p/><p>Um programador de computador poderia preencher um estagiário:</p><p/><p><tt>(can-do-job (computer programmer)<br/>
(computer programmer trainee))<br/></tt></p><p/><p>
<a name="%_idx_5108" id="%_idx_5108"/>Além disso, como é sabido,</p><p/><p><tt>(can-do-job (administration secretary)<br/>
(administration big wheel))<br/></tt></p><p/><p>
<a name="%_sec_Temp_650" id="%_sec_Temp_650"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_650">Consultas simples</a></h4><p>
<a name="%_idx_5110" id="%_idx_5110"/>A linguagem de consulta permite que os usuários recuperem informações da base de dados, fazendo consultas em resposta à solicitação do sistema. Por exemplo, para encontrar todos os programadores de computador, pode-se dizer</p><p>
</p><p/><p><tt><i>;;; Query input:</i><br/>
(job ?x (computer programmer))<br/></tt></p><p/><p>O sistema responderá com os seguintes itens:</p><p>
</p><p/><p><tt><i>;;; Query results:</i><br/>
(job (Hacker Alyssa P) (computer programmer))<br/>
(job (Fect Cy D) (computer programmer))<br/></tt></p><p/><p/><p>
<a name="%_idx_5112" id="%_idx_5112"/>A consulta de entrada especifica que procuramos entradas no banco de dados que correspondam a um determinado <em>padronizar</em>. Neste exemplo, o padrão especifica entradas que consistem em três itens, dos quais o primeiro é o símbolo literal <tt>job</tt>, o segundo pode ser algo e o terceiro é a lista literal <tt>(computer programmer)</tt>. “Algo” que possa ser o segundo item na lista correspondente é especificado por uma <a name="%_idx_5114" id="%_idx_5114"/><em>variável de padrão</em>, <tt>?x</tt>. A forma geral de uma variável padrão é um símbolo, considerado o nome da variável, precedido por um ponto de interrogação. Veremos abaixo por que é útil especificar nomes para variáveis padrão em vez de apenas colocar <tt>?</tt> em padrões para representar “algo”. O sistema responde a uma consulta simples, mostrando todas as entradas na base de dados que correspondem ao padrão especificado.</p><p>Um padrão pode ter mais de uma variável. Por exemplo, a consulta</p><p/><p><tt>(address ?x ?y)<br/></tt></p><p/><p>listará todos os endereços dos funcionários.</p><p>Um padrão não pode ter variáveis; nesse caso, a consulta simplesmente determina se esse padrão é uma entrada no banco de dados. Nesse caso, haverá uma correspondência; caso contrário, não haverá correspondências.</p><p>A mesma variável padrão pode aparecer mais de uma vez em uma consulta, especificando que o mesmo “algo” deve aparecer em cada posição. É por isso que as variáveis possuem nomes. Por exemplo,</p><p>
</p><p/><p><tt>(supervisor ?x ?x)<br/></tt></p><p/><p>encontra todas as pessoas que se supervisionam (embora não exista essa afirmação em nosso banco de dados de amostra).</p><p>A pergunta</p><p/><p><tt>(job ?x (computer ?type))<br/></tt></p><p/><p>corresponde a todas as entradas de trabalho cujo terceiro item é uma lista de dois elementos cujo primeiro item é <tt>computer</tt>:</p><p>
</p><p/><p><tt>(job (Bitdiddle Ben) (computer wizard))<br/>
(job (Hacker Alyssa P) (computer programmer))<br/>
(job (Fect Cy D) (computer programmer))<br/>
(job (Tweakit Lem E) (computer technician))<br/></tt></p><p/><p>Este mesmo padrão <em>não</em> corresponde</p><p/><p><tt>(job (Reasoner Louis) (computer programmer trainee))<br/></tt></p><p/><p>porque o terceiro item na entrada é uma lista de três elementos e o terceiro item do padrão especifica que deve haver dois elementos. Se quisermos alterar o padrão para que o terceiro item possa ser qualquer lista que comece com <tt>computer</tt>, poderíamos especificar<a name="%_idx_5116" id="%_idx_5116"/><a name="call_footnote_Temp_651" href="#footnote_Temp_651" id="call_footnote_Temp_651"><sup><small>62</small></sup></a></p><p>
</p><p/><p><tt>(job ?x (computer . ?type))<br/></tt></p><p/><p>Por exemplo,</p><p/><p><tt>(computer . ?type)<br/></tt></p><p/><p>corresponde aos dados</p><p>
</p><p/><p><tt>(computer programmer trainee)<br/></tt></p><p/><p>com <tt>?type</tt> como a lista <tt>(programmer trainee)</tt>. Igualmente combina os dados</p><p>
</p><p/><p><tt>(computer programmer)<br/></tt></p><p/><p>com <tt>?type</tt> como a lista <tt>(programmer)</tt>, e corresponde aos dados</p><p>
</p><p/><p><tt>(computer)<br/></tt></p><p/><p>com <tt>?type</tt> como a lista vazia <tt>()</tt>.</p><p>Podemos descrever o processamento de consultas simples da linguagem de consulta da seguinte maneira:</p><p>
</p><p/><ul><li>O sistema encontra todas as atribuições para variáveis na consulta <a name="%_idx_5118" id="%_idx_5118"/>padrão que <em>satisfazer</em> o padrão – ou seja, todos os conjuntos de valores para as variáveis, de modo que, se as variáveis do padrão forem <a name="%_idx_5120" id="%_idx_5120"/><em>instanciado com</em> (substituído por) os valores, o resultado está no banco de dados.<p>
</p></li><li>O sistema responde à consulta listando todas as instanciações do padrão de consulta com as atribuições de variáveis que a satisfazem.</li></ul><p/><p>Observe que, se o padrão não tiver variáveis, a consulta será reduzida para determinar se esse padrão está no banco de dados. Nesse caso, a atribuição vazia, que não atribui valores a variáveis, satisfaz esse padrão para esse banco de dados.</p><p>
</p><p><a name="%_thm_4.55" id="%_thm_4.55"/>
<b>Exercício 4.55.</b> Faça consultas simples que recuperam as seguintes informações do banco de dados:</p><p>
</p><p/><p>a. todas as pessoas supervisionadas por Ben Bitdiddle;</p><p>
</p><p/><p>b. os nomes e empregos de todas as pessoas na divisão contábil;</p><p>
</p><p/><p>c. os nomes e endereços de todas as pessoas que vivem em Slumerville.</p><p>
<a name="%_sec_Temp_653" id="%_sec_Temp_653"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_653">Consultas compostas</a></h4><p>
<a name="%_idx_5122" id="%_idx_5122"/>Consultas simples formam as operações primitivas da linguagem de consulta. Para formar operações compostas, a linguagem de consulta fornece meios de combinação. Algo que torna a linguagem de consulta uma linguagem de programação lógica é que os meios de combinação refletem os meios de combinação usados na formação de expressões lógicas: <tt>and</tt>, <tt>or</tt> e <tt>not</tt>. (Aqui <tt>and</tt>, <tt>or</tt> e <tt>not</tt> não são as primitivas do Lisp, mas operações integradas na linguagem de consulta).</p><p>
<a name="%_idx_5124" id="%_idx_5124"/>Podemos usar <tt>and</tt> a seguir para encontrar os endereços de todos os programadores de computador:</p><p>
</p><p/><p><tt>(and (job ?person (computer programmer))<br/>
(address ?person ?where))<br/></tt></p><p/><p>A saída resultante é</p><p/><p><tt>(and (job (Hacker Alyssa P) (computer programmer))<br/>
(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78)))<br/>
(and (job (Fect Cy D) (computer programmer))<br/>
(address (Fect Cy D) (Cambridge (Ames Street) 3)))<br/></tt></p><p/><p>
<a name="%_idx_5126" id="%_idx_5126"/>Em geral,</p><p/><p><tt>(and <<em>query<sub>1</sub></em>> <<em>query<sub>2</sub></em>> <tt>...</tt> <<em>query<sub><em>n</em></sub></em>>)<br/></tt></p><p/><p>é satisfeito por todos os conjuntos de valores para as variáveis padrão que satisfazem simultaneamente <<em>query<sub>1</sub></em>> <tt>…</tt> <<em>query<sub><em>n</em></sub></em>>.</p><p>Quanto às consultas simples, o sistema processa uma consulta composta localizando todas as atribuições às variáveis de padrão que atendem à consulta e exibindo instanciações da consulta com esses valores.</p><p>
<a name="%_idx_5128" id="%_idx_5128"/>Outro meio de construir consultas compostas é através de <tt>or</tt>. Por exemplo,</p><p>
</p><p/><p><tt>(or (supervisor ?x (Bitdiddle Ben))<br/>
(supervisor ?x (Hacker Alyssa P)))<br/></tt></p><p/><p>encontrará todos os funcionários supervisionados por Ben Bitdiddle ou Alyssa P. Hacker:</p><p>
</p><p/><p><tt>(or (supervisor (Hacker Alyssa P) (Bitdiddle Ben))<br/>
(supervisor (Hacker Alyssa P) (Hacker Alyssa P)))<br/>
(or (supervisor (Fect Cy D) (Bitdiddle Ben))<br/>
(supervisor (Fect Cy D) (Hacker Alyssa P)))<br/>
(or (supervisor (Tweakit Lem E) (Bitdiddle Ben))<br/>
(supervisor (Tweakit Lem E) (Hacker Alyssa P)))<br/>
(or (supervisor (Reasoner Louis) (Bitdiddle Ben))<br/>
(supervisor (Reasoner Louis) (Hacker Alyssa P)))<br/></tt></p><p/><p>Em geral,</p><p/><p><tt>(or <<em>query<sub>1</sub></em>> <<em>query<sub>2</sub></em>> <tt>...</tt> <<em>query<sub><em>n</em></sub></em>>)<br/></tt></p><p/><p>é satisfeito por todos os conjuntos de valores para as variáveis padrão que satisfazem, pelo menos, um dos <<em>query<sub>1</sub></em>> <tt>…</tt> <<em>query<sub><em>n</em></sub></em>>.</p><p>
<a name="%_idx_5130" id="%_idx_5130"/>Consultas compostas também podem ser formadas com <tt>não</tt>. Por exemplo,</p><p/><p><tt>(and (supervisor ?x (Bitdiddle Ben))<br/>
(not (job ?x (computer programmer))))<br/></tt></p><p/><p>encontra todas as pessoas supervisionadas por Ben Bitdiddle que não são programadores de computador. Em geral,</p><p>
</p><p/><p><tt>(not <<em>query<sub>1</sub></em>>)<br/></tt></p><p/><p>é satisfeito por todas as atribuições para as variáveis de padrão que não satisfazem <<em>query<sub>1</sub></em>>.<a name="call_footnote_Temp_654" href="#footnote_Temp_654" id="call_footnote_Temp_654"><sup><small>63</small></sup></a></p><p>
<a name="%_idx_5132" id="%_idx_5132"/>O formulário final de combinação é chamado <tt>lisp-value</tt>. Quando <tt>lisp-value</tt> é o primeiro elemento de um padrão, especifica que o próximo elemento é um predicado Lisp a ser aplicado ao restante dos elementos (instanciados) como argumentos. Em geral,</p><p>
</p><p/><p><tt>(lisp-value <<em>predicate</em>> <<em>arg<sub>1</sub></em>> <tt>...</tt> <<em>arg<sub><em>n</em></sub></em>>)<br/></tt></p><p/><p>será atendido por atribuições para as variáveis de padrão para as quais <<em>predicate</em>> aplicado ao instanciado <<em>arg<sub>1</sub></em>> <tt>…</tt> <<em>arg<sub><em>n</em></sub></em>> é verdade. Por exemplo, para encontrar todas as pessoas cujo salário é superior a $30.000, poderíamos escrever <a name="call_footnote_Temp_655" href="#footnote_Temp_655" id="call_footnote_Temp_655"><sup><small>64</small></sup></a></p><p>
</p><p/><p><tt>(and (salary ?person ?amount)<br/>
(lisp-value > ?amount 30000))<br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_4.56" id="%_thm_4.56"/>
<b>Exercício 4.56.</b> Formule consultas compostas que recuperam as seguintes informações:</p><p>
</p><p/><p>a. os nomes de todas as pessoas supervisionadas por Ben Bitdiddle, com seus endereços;</p><p>
</p><p/><p>b. todas as pessoas cujo salário é inferior ao de Ben Bitdiddle, com o salário e o salário de Ben Bitdiddle;</p><p>
</p><p/><p>c. todas as pessoas supervisionadas por alguém que não está na divisão de computadores, com o nome e o cargo do supervisor.</p><p>
</p><p>
<a name="%_sec_Temp_657" id="%_sec_Temp_657"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_657">Regras</a></h4><p>
<a name="%_idx_5136" id="%_idx_5136"/>
<a name="%_idx_5138" id="%_idx_5138"/>Além das consultas primitivas e compostas, a linguagem de consulta fornece meios para abstrair consultas. Estes são dados por <em>regras</em>. A regra</p><p>
</p><p/><p><tt><a name="%_idx_5140" id="%_idx_5140"/>(rule (lives-near ?person-1 ?person-2)<br/>
(and (address ?person-1 (?town . ?rest-1))<br/>
(address ?person-2 (?town . ?rest-2))<br/>
(not (same ?person-1 ?person-2))))<br/></tt></p><p/><p>especifica que duas pessoas moram próximas uma da outra se moram na mesma cidade. O final <tt>not</tt> Esta cláusula impede a regra de dizer que todas as pessoas vivem perto de si. o <tt>same</tt> relação é definida por uma regra muito simples:<a name="call_footnote_Temp_658" href="#footnote_Temp_658" id="call_footnote_Temp_658"><sup><small>65</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_5142" id="%_idx_5142"/>(rule (same ?x ?x))<br/></tt></p><p/><p/><p>A regra a seguir declara que uma pessoa é uma “roda” em uma organização se ela supervisiona alguém que por sua vez é um supervisor:</p><p>
</p><p/><p><tt><a name="%_idx_5144" id="%_idx_5144"/>(rule (wheel ?person)<br/>
(and (supervisor ?middle-manager ?person)<br/>
(supervisor ?x ?middle-manager)))<br/></tt></p><p/><p/><p>A forma geral de uma regra é</p><p/><p><tt>(rule <<em>conclusion</em>> <<em>body</em>>)<br/></tt></p><p/><p>onde <<em>conclusion</em>> é um padrão e <<em>body</em>> é qualquer consulta.<a name="call_footnote_Temp_659" href="#footnote_Temp_659" id="call_footnote_Temp_659"><sup><small>66</small></sup></a> Podemos pensar em uma regra como representando um grande (até infinito) conjunto de asserções, ou seja, todas as instanciações da conclusão da regra com atribuições variáveis que satisfazem o corpo da regra. Quando descrevemos consultas simples (padrões), dissemos que uma atribuição às variáveis satisfaz um padrão se o padrão instanciado estiver no banco de dados. Mas o padrão não precisa estar explicitamente no banco de dados como uma afirmação. Isto <a name="%_idx_5148" id="%_idx_5148"/>pode ser uma asserção implícita implicada por uma regra. Por exemplo, a consulta</p><p/><p><tt>(lives-near ?x (Bitdiddle Ben))<br/></tt></p><p/><p>resulta em</p><p/><p><tt>(lives-near (Reasoner Louis) (Bitdiddle Ben))<br/>
(lives-near (Aull DeWitt) (Bitdiddle Ben))<br/></tt></p><p/><p>Para encontrar todos os programadores de computador que moram perto de Ben Bitdiddle, podemos perguntar</p><p/><p><tt>(and (job ?x (computer programmer))<br/>
(lives-near ?x (Bitdiddle Ben)))<br/></tt></p><p/><p/><p>
<a name="%_idx_5150" id="%_idx_5150"/>Como no caso de procedimentos compostos, as regras podem ser usadas como partes de outras regras (como vimos na regra <tt>lives-near</tt> acima) ou mesmo ser definido recursivamente. Por exemplo, a regra</p><p/><p><tt><a name="%_idx_5152" id="%_idx_5152"/>(rule (outranked-by ?staff-person ?boss)<br/>
(or (supervisor ?staff-person ?boss)<br/>
(and (supervisor ?staff-person ?middle-manager)<br/>
(outranked-by ?middle-manager ?boss))))<br/></tt></p><p/><p>diz que uma pessoa da equipe é superada por um chefe da organização se o chefe for o supervisor da pessoa ou (recursivamente) se o supervisor da pessoa for superada pelo chefe.</p><p>
</p><p><a name="%_thm_4.57" id="%_thm_4.57"/>
<b>Exercício 4.57.</b> Defina uma regra que diga que a pessoa 1 pode substituir a pessoa 2 se a pessoa 1 fizer o mesmo trabalho que a pessoa 2 ou alguém que fizer o trabalho da pessoa 1 também puder fazer o trabalho da pessoa 2 e se a pessoa 1 e a pessoa 2 não forem a mesma pessoa. Usando sua regra, faça consultas que encontrem o seguinte:</p><p>a. todas as pessoas que podem substituir o Cy D. Fect;</p><p>b. todas as pessoas que podem substituir alguém que é pago mais do que são, com os dois salários.</p><p/><p>
</p><p><a name="%_thm_4.58" id="%_thm_4.58"/>
<b>Exercício 4.58.</b> Defina uma regra que diga que uma pessoa é uma “figura importante” em uma divisão se ela trabalha na divisão, mas não possui um supervisor que trabalhe na divisão.</p><p/><p>
</p><p><a name="%_thm_4.59" id="%_thm_4.59"/>
<b>Exercício 4.59.</b> Ben Bitdiddle perdeu uma reunião a mais. Temendo que seu hábito de esquecer as reuniões lhe custasse o trabalho, Ben decide fazer algo a respeito. Ele adiciona todas as reuniões semanais da empresa ao banco de dados Microshaft, afirmando o seguinte:</p><p/><p><tt>(meeting accounting (Monday 9am))<br/>
(meeting administration (Monday 10am))<br/>
(meeting computer (Wednesday 3pm))<br/>
(meeting administration (Friday 1pm))<br/></tt></p><p/><p>Cada uma das afirmações acima é para uma reunião de uma divisão inteira. Ben também adiciona uma entrada para a reunião em toda a empresa, que abrange todas as divisões. Todos os funcionários da empresa participam dessa reunião.</p><p/><p><tt>(meeting whole-company (Wednesday 4pm))<br/></tt></p><p/><p>
</p><p>
</p><p/><p>a. Na sexta-feira de manhã, Ben deseja consultar o banco de dados para todas as reuniões que ocorrem naquele dia. Que consulta ele deve usar?</p><p>
</p><p/><p>b. Alyssa P. Hacker não se impressiona. Ela acha que seria muito mais útil poder solicitar suas reuniões especificando seu nome. Então ela cria uma regra que diz que as reuniões de uma pessoa incluem todos <tt>whole-company</tt> reuniões mais todas as reuniões da divisão dessa pessoa. Preencha o corpo da regra de Alyssa.</p><p/><p><tt>(rule (meeting-time ?person ?day-and-time)<br/>
<<em>rule-body</em>>)<br/></tt></p><p/><p/><p>c. Alyssa chega ao trabalho na quarta-feira de manhã e se pergunta quais reuniões ela deve comparecer naquele dia. Tendo definido a regra acima, que consulta ela deve fazer para descobrir isso?</p><p/><p>
</p><p><a name="%_thm_4.60" id="%_thm_4.60"/>
<b>Exercício 4.60.</b> <a name="%_idx_5154" id="%_idx_5154"/>Ao dar a consulta</p><p/><p><tt>(lives-near ?person (Hacker Alyssa P))<br/></tt></p><p/><p>Alyssa P. Hacker é capaz de encontrar pessoas que moram perto dela, com quem ela pode ir trabalhar. Por outro lado, quando ela tenta encontrar todos os pares de pessoas que moram perto, consultando</p><p>
</p><p/><p><tt>(lives-near ?person-1 ?person-2)<br/></tt></p><p/><p>ela nota que cada par de pessoas que moram perto uma da outra é listado duas vezes; por exemplo,</p><p>
</p><p/><p><tt>(lives-near (Hacker Alyssa P) (Fect Cy D))<br/>
(lives-near (Fect Cy D) (Hacker Alyssa P))<br/></tt></p><p/><p>Por que isso acontece? Existe uma maneira de encontrar uma lista de pessoas que moram perto uma da outra, na qual cada par aparece apenas uma vez? Explique.</p><p/><p>
<a name="%_sec_Temp_664" id="%_sec_Temp_664"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_664">Lógica como programas</a></h4><p>
<a name="%_idx_5156" id="%_idx_5156"/>Podemos considerar uma regra como um tipo de implicação lógica: <em>E se</em> uma atribuição de valores para variáveis padrão satisfaz o corpo, <em>então</em> satisfaz a conclusão. Consequentemente, podemos considerar a linguagem de consulta como tendo a capacidade de executar <em>deduções lógicas</em> com base nas regras. Como exemplo, considere a operação <tt>append</tt> descrita no início da seção <a href="#%_sec_4.4">4.4.</a>. Como dissemos, <tt>append</tt> pode ser caracterizado pelas duas regras a seguir:</p><p>
</p><p/><ul><li>Para qualquer lista <tt>y</tt>, a lista vazia e <tt>y</tt><tt>append</tt> formar <tt>y</tt>.<p>
</p></li><li>Para qualquer <tt>u</tt>, <tt>v</tt>, <tt>y</tt> e <tt>z</tt>, <tt>(cons u v)</tt> e <tt>y</tt><tt>append</tt> formar <tt>(cons u z)</tt> se <tt>v</tt> e <tt>y</tt> <tt>append</tt> formar <tt>z</tt>.</li></ul><p/><p>Para expressar isso em nossa linguagem de consulta, definimos duas regras para uma relação</p><p/><p><tt>(append-to-form x y z)<br/></tt></p><p/><p>que podemos interpretar como “<tt>x</tt> e <tt>y</tt> <tt>append</tt> formar <tt>z</tt>”:</p><p>
</p><p/><p><tt><a name="%_idx_5158" id="%_idx_5158"/>(rule (append-to-form () ?y ?y))<br/>
(rule (append-to-form (?u . ?v) ?y (?u . ?z))<br/>
(append-to-form ?v ?y ?z))<br/></tt></p><p/><p>
<a name="%_idx_5160" id="%_idx_5160"/>A primeira regra não possui corpo, o que significa que a conclusão vale para qualquer valor de <tt>?y</tt>. Observe como a segunda regra faz uso de <a name="%_idx_5162" id="%_idx_5162"/>notação de cauda pontilhada para nomear o <tt>car</tt> e <tt>cdr</tt> de uma lista.</p><p>Dadas essas duas regras, podemos formular consultas que calculam o <tt>append</tt> de duas listas:</p><p/><p><tt><i>;;; Query input:</i><br/>
(append-to-form (a b) (c d) ?z)<br/><i>;;; Query results:</i><br/>
(append-to-form (a b) (c d) (a b c d))<br/></tt></p><p/><p>O que é mais impressionante, podemos usar as mesmas regras para fazer a pergunta “Qual lista, quando <tt>append</tt> ed para <tt>(a b)</tt>, rendimentos <tt>(a b c d)</tt>?” Isto se faz do seguinte modo:</p><p/><p><tt><i>;;; Query input:</i><br/>
(append-to-form (a b) ?y (a b c d))<br/><i>;;; Query results:</i><br/>
(append-to-form (a b) (c d) (a b c d))<br/></tt></p><p/><p>Também podemos pedir todos os pares de listas que <tt>append</tt> formar <tt>(a b c d)</tt>:</p><p/><p><tt><i>;;; Query input:</i><br/>
(append-to-form ?x ?y (a b c d))<br/><i>;;; Query results:</i><br/>
(append-to-form () (a b c d) (a b c d))<br/>
(append-to-form (a) (b c d) (a b c d))<br/>
(append-to-form (a b) (c d) (a b c d))<br/>
(append-to-form (a b c) (d) (a b c d))<br/>
(append-to-form (a b c d) () (a b c d))<br/></tt></p><p/><p/><p>O sistema de consulta pode parecer exibir um pouco de inteligência ao usar as regras para deduzir as respostas às consultas acima. Na verdade, como veremos na próxima seção, o sistema segue um algoritmo bem determinado para desvendar as regras. Infelizmente, embora o sistema funcione de maneira impressionante no <tt>append</tt> Nesse caso, os métodos gerais podem quebrar em casos mais complexos, como veremos na seção <a href="#%_sec_4.4.3">4.4.3</a>.</p><p>
</p><p><a name="%_thm_4.61" id="%_thm_4.61"/>
<b>Exercício 4.61.</b> As regras a seguir implementam um <tt>next-to</tt> relação que encontra elementos adjacentes de uma lista:</p><p/><p><tt><a name="%_idx_5164" id="%_idx_5164"/>(rule (?x next-to ?y in (?x ?y . ?u)))<br/><br/>
(rule (?x next-to ?y in (?v . ?z))<br/>
(?x next-to ?y in ?z))<br/></tt></p><p/><p>Qual será a resposta às seguintes perguntas?</p><p/><p><tt>(?x next-to ?y in (1 (2 3) 4))<br/><br/>
(?x next-to 1 in (2 1 3 1))<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_4.62" id="%_thm_4.62"/>
<b>Exercício 4.62.</b> <a name="%_idx_5166" id="%_idx_5166"/>Defina regras para implementar a operação <tt>last-pair</tt> do exercício <a href="book-Z-H-15.html#%_thm_2.17">2.17</a>, que retorna uma lista que contém o último elemento de uma lista não vazia. Verifique suas regras em consultas como <tt>(last-pair (3) ?x)</tt>, <tt>(last-pair (1 2 3) ?x)</tt> e <tt>(last-pair (2 ?x) (3))</tt>. Suas regras funcionam corretamente em consultas como <tt>(last-pair ?x (3))</tt> ?</p><p/><p>
</p><p><a name="%_thm_4.63" id="%_thm_4.63"/>
<b>Exercício 4.63.</b> <a name="%_idx_5168" id="%_idx_5168"/><a name="%_idx_5170" id="%_idx_5170"/>A seguinte base de dados (veja Gênesis 4) rastreia a genealogia dos descendentes de Ada até Adão, por meio de Caim:</p><p>
</p><p/><p><tt>(son Adam Cain)<br/>
(son Cain Enoch)<br/>
(son Enoch Irad)<br/>
(son Irad Mehujael)<br/>
(son Mehujael Methushael)<br/>
(son Methushael Lamech)<br/>
(wife Lamech Ada)<br/>
(son Ada Jabal)<br/>
(son Ada Jubal)<br/></tt></p><p/><p>Formule regras como “Se <em>S</em> é filho de <em>F</em> e <em>F</em> é filho de <em>G</em>, então <em>S</em> é neto de <em>G</em>” e se <em>W</em> é a esposa de <em>M</em> e <em>S</em> é filho de <em>W</em>, então <em>S</em> é filho de <em>M</em>”(Que era supostamente mais verdadeiro nos tempos bíblicos do que hoje) que permitirá que o sistema de consulta encontre o neto de Caim; os filhos de Lameque; os netos de Matusalém. (Veja exercício <a href="#%_thm_4.69">4.69</a> para algumas regras deduzir relacionamentos mais complicados).</p><p>
<a name="%_sec_4.4.2" id="%_sec_4.4.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_4.4.2">4.4.2 Como o sistema de consulta funciona</a></h3><p>
<a name="%_idx_5172" id="%_idx_5172"/>Na seção <a href="#%_sec_4.4.4">4.4.4</a> apresentaremos uma implementação do interpretador de consultas como uma coleção de procedimentos. Nesta seção, fornecemos uma visão geral que explica a estrutura geral do sistema, independentemente dos detalhes de implementação de baixo nível. Após descrever a implementação do interpretador, estaremos em posição de entender algumas de suas limitações e algumas das maneiras sutis pelas quais as operações lógicas da linguagem de consulta diferem das operações da lógica matemática.</p><p>Deveria ser aparente que o avaliador de consultas deve realizar algum tipo de pesquisa para comparar consultas com fatos e regras no banco de dados. Uma maneira de fazer isso seria implementar o sistema de consulta como um programa não determinístico, usando o avaliador <tt>amb</tt> da seção <a href="book-Z-H-28.html#%_sec_4.3">4.3.</a> (veja exercício <a href="#%_thm_4.78">4.78</a>) Outra possibilidade é gerenciar a pesquisa com o auxílio de fluxos. Nossa implementação segue esta segunda abordagem.</p><p>O sistema de consulta está organizado em torno de duas operações centrais chamadas <em>correspondência de padrões</em> e <em>unificação</em>. Primeiro descrevemos a correspondência de padrões e explicamos como essa operação, com a organização das informações em termos de fluxos de quadros, nos permite implementar consultas simples e compostas. A seguir, discutiremos a unificação, uma generalização da correspondência de padrões necessária para implementar regras. Por fim, mostramos como o interpretador de consulta inteiro se encaixa por meio de um procedimento que classifica expressões de maneira análoga à <tt>eval</tt> classifica expressões para o interpretador descrito na seção <a href="book-Z-H-26.html#%_sec_4.1">4.1</a>.</p><p>
<a name="%_sec_Temp_668" id="%_sec_Temp_668"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_668">Correspondência de padrões</a></h4><p>
<a name="%_idx_5174" id="%_idx_5174"/><a name="%_idx_5176" id="%_idx_5176"/>O <em>combinador de padrões</em> é um programa que testa se algum dado se encaixa em um padrão especificado. Por exemplo, a lista de dados <tt>((a b) c (a b))</tt> corresponde ao padrão <tt>(?x c ?x)</tt> com a variável padrão <tt>?x</tt> obrigado a <tt>(a b)</tt>. A mesma lista de dados corresponde ao padrão <tt>(?x ?y ?z)</tt> com <tt>?x</tt> e <tt>?z</tt> ambos ligados a <tt>(a b)</tt> e <tt>?y</tt> obrigado a <tt>c</tt>. Também corresponde ao padrão <tt>((?x ?y) c (?x ?y))</tt> com <tt>?x</tt> obrigado a <tt>a</tt> e <tt>?y</tt> obrigado a <tt>b</tt>. No entanto, ele não corresponde ao padrão <tt>(?x a ?y)</tt>, pois esse padrão especifica uma lista cujo segundo elemento é o símbolo <tt>a</tt>.</p><p>
<a name="%_idx_5178" id="%_idx_5178"/><a name="%_idx_5180" id="%_idx_5180"/>O correspondente de padrão usado pelo sistema de consulta toma como entradas um padrão, um dado e um <em>quadro, Armação</em> que especifica ligações para várias variáveis de padrão. Ele verifica se o dado corresponde ao padrão de forma consistente com as ligações já existentes no quadro. Nesse caso, ele retornará o quadro fornecido incrementado por quaisquer ligações que possam ter sido determinadas pela correspondência. Caso contrário, indica que a correspondência falhou.</p><p>Por exemplo, usando o padrão <tt>(?x ?y ?x)</tt> combinar <tt>(a b a)</tt> dado um quadro vazio retornará um quadro especificando que <tt>?x</tt> é obrigado a <tt>a</tt> e <tt>?y</tt> é obrigado a <tt>b</tt>. Tentando a correspondência com o mesmo padrão, o mesmo dado e um quadro especificando que <tt>?y</tt> é obrigado a <tt>a</tt> vai falhar. Tentando a partida com o mesmo padrão, o mesmo dado e um quadro no qual <tt>?y</tt> é obrigado a <tt>b</tt> e <tt>?x</tt> não ligado retornará o quadro fornecido incrementando por uma ligação de <tt>?x</tt> para <tt>a</tt>.</p><p>
<a name="%_idx_5182" id="%_idx_5182"/>O correspondente de padrões é todo o mecanismo necessário para processar consultas simples que não envolvem regras. Por exemplo, para processar a consulta</p><p>
</p><p/><p><tt>(job ?x (computer programmer))<br/></tt></p><p/><p>examinamos todas as asserções na base de dados e selecionamos aquelas que correspondem ao padrão em relação a um quadro inicialmente vazio. Para cada correspondência encontrada, usamos o quadro retornado pela correspondência para instanciar o padrão com um valor para <tt>?x</tt>.<a name="%_sec_Temp_669" id="%_sec_Temp_669"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_669">Fluxos de quadros</a></h4><p>
<a name="%_idx_5184" id="%_idx_5184"/><a name="%_idx_5186" id="%_idx_5186"/>O teste de padrões em relação aos quadros é organizado através do uso de fluxos. Dado um único quadro, o processo de correspondência percorre as entradas do banco de dados uma a uma. Para cada entrada da base de dados, o correspondente gera um símbolo especial indicando que a correspondência falhou ou uma extensão do quadro. Os resultados de todas as entradas do banco de dados são coletados em um fluxo, que é passado por um filtro para eliminar as falhas. O resultado é um fluxo de todos os quadros que estendem o quadro fornecido por meio de uma correspondência com alguma afirmação na base de dados.<a name="call_footnote_Temp_670" href="#footnote_Temp_670" id="call_footnote_Temp_670"><sup><small>67</small></sup></a></p><p>Em nosso sistema, uma consulta obtém um fluxo de quadros de entrada e executa a operação correspondente acima para cada quadro no fluxo, conforme indicado na figura <a href="#%_fig_4.4">4.4.</a>. Ou seja, para cada quadro no fluxo de entrada, a consulta gera um novo fluxo que consiste em todas as extensões desse quadro por correspondências às asserções no banco de dados. Todos esses fluxos são combinados para formar um fluxo enorme, que contém todas as extensões possíveis de cada quadro no fluxo de entrada. Esse fluxo é a saída da consulta.</p><p>
<a name="%_fig_4.4" id="%_fig_4.4"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch4-Z-G-4.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 4.4:</b> Uma consulta processa um fluxo de quadros.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_idx_5194" id="%_idx_5194"/>Para responder a uma consulta simples, usamos a consulta com um fluxo de entrada que consiste em um único quadro vazio. O fluxo de saída resultante contém todas as extensões do quadro vazio (ou seja, todas as respostas à nossa consulta). Esse fluxo de quadros é então usado para gerar um fluxo de cópias do padrão de consulta original com as variáveis instanciadas pelos valores em cada quadro, e este é o fluxo que é finalmente impresso.</p><p>
<a name="%_sec_Temp_671" id="%_sec_Temp_671"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_671">Consultas compostas</a></h4><p>
<a name="%_idx_5196" id="%_idx_5196"/>A verdadeira elegância da implementação do fluxo de quadros é evidente quando lidamos com consultas compostas. O processamento de consultas compostas utiliza a capacidade do nosso correspondente para exigir que uma correspondência <a name="%_idx_5198" id="%_idx_5198"/>seja consistente com um quadro especificado. Por exemplo, para lidar com o <tt>and</tt> de duas consultas, como</p><p>
</p><p/><p><tt>(and (can-do-job ?x (computer programmer trainee))<br/>
(job ?person ?x))<br/></tt></p><p/><p>(informalmente, “Encontre todas as pessoas que podem fazer o trabalho de um estagiário de programador de computador”), primeiro encontramos todas as entradas que correspondem ao padrão</p><p>
</p><p/><p><tt>(can-do-job ?x (computer programmer trainee))<br/></tt></p><p/><p>Isso produz um fluxo de quadros, cada um dos quais contém uma ligação para <tt>?x</tt>. Em seguida, para cada quadro no fluxo, encontramos todas as entradas que correspondem</p><p>
</p><p/><p><tt>(job ?person ?x)<br/></tt></p><p/><p>de maneira consistente com a ligação especificada para <tt>?x</tt>. Cada correspondência produzirá um quadro contendo ligações para <tt>?x</tt> e <tt>?person</tt>. o <tt>and</tt> de duas consultas pode ser visualizada como uma combinação de séries das duas consultas de componente, conforme mostrado na figura <a href="#%_fig_4.5">4.5</a>. Os quadros que passam pelo primeiro filtro de consulta são filtrados e estendidos ainda mais pela segunda consulta.</p><p>
<a name="%_fig_4.5" id="%_fig_4.5"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch4-Z-G-5.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 4.5:</b> a combinação <tt>and</tt> de duas consultas é produzida operando no fluxo de quadros em série.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_idx_5200" id="%_idx_5200"/>A figura <a href="#%_fig_4.6">4.6</a> mostra o método análogo para calcular o <tt>or</tt> de duas consultas como uma combinação paralela das duas consultas de componentes. O fluxo de entrada de quadros é estendido separadamente por cada consulta. Os dois fluxos resultantes são então mesclados para produzir o fluxo de saída final.</p><p>
<a name="%_fig_4.6" id="%_fig_4.6"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/ch4-Z-G-6.gif" border="0"/></td></tr><caption align="bottom"><div align="left"><b>Figura 4.6:</b> a combinação <tt>or</tt> de duas consultas é produzida operando no fluxo de quadros em paralelo e mesclando os resultados.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_idx_5202" id="%_idx_5202"/>Mesmo a partir dessa descrição de alto nível, é evidente que o processamento de consultas compostas pode ser lento. Por exemplo, como uma consulta pode produzir mais de um quadro de saída para cada quadro de entrada e cada consulta em um <tt>and</tt> obtém seus quadros de entrada da consulta anterior, uma consulta <tt>and</tt> pode, na pior das hipóteses, ter que executar uma série de correspondências exponenciais no número de consultas (consulte o exercício <a href="#%_thm_4.76">4.76</a>)<a name="call_footnote_Temp_672" href="#footnote_Temp_672" id="call_footnote_Temp_672"><sup><small>68</small></sup></a> Embora os sistemas para lidar apenas com consultas simples sejam bastante práticos, é extremamente difícil lidar com consultas complexas.<a name="call_footnote_Temp_673" href="#footnote_Temp_673" id="call_footnote_Temp_673"><sup><small>69</small></sup></a></p><p>
<a name="%_idx_5204" id="%_idx_5204"/>Do ponto de vista do fluxo de quadros, o <tt>not</tt> de algumas consultas atua como um filtro que remove todos os quadros para os quais a consulta pode ser atendida. Por exemplo, dado o padrão</p><p>
</p><p/><p><tt>(not (job ?x (computer programmer)))<br/></tt></p><p/><p>tentamos, para cada quadro no fluxo de entrada, produzir quadros de extensão que satisfaçam <tt>(job ?x (computer programmer))</tt>. Removemos do fluxo de entrada todos os quadros para os quais essas extensões existem. O resultado é um fluxo que consiste apenas nos quadros em que a ligação para <tt>?x</tt> não satisfaz <tt>(job ?x (computer programmer))</tt>. Por exemplo, ao processar a consulta</p><p>
</p><p/><p><tt>(and (supervisor ?x ?y)<br/>
(not (job ?x (computer programmer))))<br/></tt></p><p/><p>a primeira cláusula irá gerar quadros com ligações para <tt>?x</tt> e <tt>?y</tt>. A cláusula <tt>not</tt> filtrará esses itens removendo todos os quadros nos quais a ligação para <tt>?x</tt> satisfaz a restrição de que <tt>?x</tt> é um programador de computador.<a name="call_footnote_Temp_674" href="#footnote_Temp_674" id="call_footnote_Temp_674"><sup><small>70</small></sup></a></p><p>
<a name="%_idx_5206" id="%_idx_5206"/>o <tt>lisp-value</tt> Um formulário especial é implementado como um filtro semelhante nos fluxos de quadros. Usamos cada quadro no fluxo para instanciar quaisquer variáveis no padrão e, em seguida, aplicamos o predicado Lisp. Removemos do fluxo de entrada todos os quadros para os quais o predicado falha.<a name="%_sec_Temp_675" id="%_sec_Temp_675"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_675">Unificação</a></h4><p>
<a name="%_idx_5208" id="%_idx_5208"/><a name="%_idx_5210" id="%_idx_5210"/>Para manipular regras na linguagem de consulta, precisamos encontrar as regras cujas conclusões correspondem a um determinado padrão de consulta. As conclusões das regras são como asserções, exceto que elas podem conter variáveis; portanto, precisaremos de uma generalização da correspondência de padrões – chamada <em>unificação</em> – em que o “padrão” e o “dado” podem conter variáveis.</p><p>Um unificador pega dois padrões, cada um contendo constantes e variáveis, e determina se é possível atribuir valores às variáveis que tornarão os dois padrões iguais. Nesse caso, ele retorna um quadro contendo essas ligações. Por exemplo, unificar <tt>(?x a ?y)</tt> e <tt>(?y ?z a)</tt> irá especificar um quadro no qual <tt>?x</tt>, <tt>?y</tt> e <tt>?z</tt> todos devem estar ligados a <tt>a</tt>. Por outro lado, unificar <tt>(?x ?y a)</tt> e <tt>(?x b ?y)</tt> falhará, pois não há valor para <tt>?y</tt> que pode tornar os dois padrões iguais. (Para que os segundos elementos dos padrões sejam iguais, <tt>?y</tt> teria de ser <tt>b</tt>; no entanto, para que os terceiros elementos sejam iguais, <tt>?y</tt> teria de ser <tt>a</tt>). O unificador usado no sistema de consulta, como o correspondente de padrões, pega um quadro como entrada e realiza unificações consistentes com esse quadro.</p><p>O algoritmo de unificação é a parte tecnicamente mais difícil do sistema de consulta. Com padrões complexos, a realização da unificação pode parecer exigir dedução. Para unificar <tt>(?x ?x)</tt> e <tt>((a ?y c) (a b ?z))</tt>, por exemplo, o algoritmo deve inferir que <tt>?x</tt> deveria estar <tt>(a b c)</tt>, <tt>?y</tt> deveria estar <tt>b</tt> e <tt>?z</tt> deveria estar <tt>c</tt>. Podemos pensar nesse processo como resolver um conjunto de equações entre os componentes do padrão. Em geral, essas são equações simultâneas, que podem exigir manipulação substancial para serem resolvidas.<a name="call_footnote_Temp_676" href="#footnote_Temp_676" id="call_footnote_Temp_676"><sup><small>71</small></sup></a> Por exemplo, unificar <tt>(?x ?x)</tt> e <tt>((a ?y c) (a b ?z))</tt> pode ser pensado como especificando as equações simultâneas</p><p>
</p><p/><p><tt>?x = (a ?y c)<br/>
?x = (a b ?z)<br/></tt></p><p/><p>Essas equações implicam que</p><p>
</p><p/><p><tt>(a ?y c) = (a b ?z)<br/></tt></p><p/><p>que por sua vez implica que</p><p>
</p><p/><p><tt>a = a, ?y = b, c = ?z,<br/></tt></p><p/><p>e daí que</p><p>
</p><p/><p><tt>?x = (a b c)<br/></tt></p><p/><p/><p>
<a name="%_idx_5212" id="%_idx_5212"/><a name="%_idx_5214" id="%_idx_5214"/>Em uma correspondência de padrão bem-sucedida, todas as variáveis de padrão ficam ligadas e os valores aos quais estão ligadas contêm apenas constantes. Isso também se aplica a todos os exemplos de unificação que vimos até agora. Em geral, no entanto, uma unificação bem-sucedida pode não determinar completamente os valores das variáveis; algumas variáveis podem permanecer independentes e outras podem estar ligadas a valores que contêm variáveis.</p><p>Considere a unificação de <tt>(?x a)</tt> e <tt>((b ?y) ?z)</tt>. Podemos deduzir que <tt>?x = (b ?y)</tt> e <tt>a = ?z</tt>, mas não podemos resolver mais <tt>?x</tt> ou <tt>?y</tt>. A unificação não falha, pois é certamente possível igualar os dois padrões atribuindo valores a <tt>?x</tt> e <tt>?y</tt>. Como essa correspondência não restringe os valores <tt>?y</tt> pode assumir, nenhuma ligação para <tt>?y</tt> é colocado no quadro de resultados. A correspondência, no entanto, restringe o valor de <tt>?x</tt>. Qualquer que seja o valor <tt>?y</tt> tem, <tt>?x</tt> devemos ser <tt>(b ?y)</tt>. Uma ligação de <tt>?x</tt> para o padrão <tt>(b ?y)</tt> é assim colocado no quadro. Se um valor para <tt>?y</tt> é determinado posteriormente e adicionado ao quadro (por uma correspondência ou unificação de padrão necessária para ser consistente com esse quadro), o limite anteriormente ligado <tt>?x</tt> irá se referir a este valor.<a name="call_footnote_Temp_677" href="#footnote_Temp_677" id="call_footnote_Temp_677"><sup><small>72</small></sup></a>
<a name="%_sec_Temp_678" id="%_sec_Temp_678"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_678">Aplicando regras</a></h4><p>
<a name="%_idx_5216" id="%_idx_5216"/>A unificação é a chave para o componente do sistema de consulta que faz inferências a partir de regras. Para ver como isso é realizado, considere processar uma consulta que envolva a aplicação de uma regra, como</p><p>
</p><p/><p><tt>(lives-near ?x (Hacker Alyssa P))<br/></tt></p><p/><p>Para processar essa consulta, primeiro usamos o procedimento de correspondência de padrão comum descrito acima para verificar se há alguma afirmação na base de dados que corresponda a esse padrão. (Não haverá nenhum nesse caso, uma vez que nossa base de dados não inclui afirmações diretas sobre quem mora perto de quem). O próximo passo é tentar unificar o padrão de consulta com a conclusão de cada regra. Descobrimos que o padrão se une à conclusão da regra</p><p>
</p><p/><p><tt>(rule (lives-near ?person-1 ?person-2)<br/>
(and (address ?person-1 (?town . ?rest-1))<br/>
(address ?person-2 (?town . ?rest-2))<br/>
(not (same ?person-1 ?person-2))))<br/></tt></p><p/><p>resultando em um quadro especificando que <tt>?person-2</tt> é obrigado a <tt>(Hacker Alyssa P)</tt> e essa <tt>?x</tt> deve estar ligado a (ter o mesmo valor que) <tt>?person-1</tt>. Agora, em relação a esse quadro, avaliamos a consulta composta fornecida pelo corpo da regra. As correspondências bem-sucedidas estenderão esse quadro fornecendo uma ligação para <tt>?person-1</tt> e, consequentemente, um valor para <tt>?x</tt>, que podemos usar para instanciar o padrão de consulta original.</p><p>Em geral, o avaliador de consulta usa o seguinte método para aplicar uma regra ao tentar estabelecer um padrão de consulta em um quadro que especifica ligações para algumas das variáveis de padrão:</p><p>
</p><p/><ul><li>Unifique a consulta com a conclusão da regra para formar, se for bem-sucedida, uma extensão do quadro original.<p>
</p></li><li>Em relação ao quadro estendido, avalie a consulta formada pelo corpo da regra.</li></ul><p/><p>
<a name="%_idx_5218" id="%_idx_5218"/>Observe como isso é semelhante ao método para aplicar um procedimento no avaliador <tt>eval</tt>/<tt>apply</tt> para Lisp:</p><p/><ul><p>
</p><li>Ligue os parâmetros do procedimento aos seus argumentos para formar um quadro que estenda o ambiente do procedimento original.<p>
</p></li><li>Em relação ao ambiente estendido, avalie a expressão formada pelo corpo do procedimento.</li></ul><p/><p>A semelhança entre os dois avaliadores não deve surpreender. Assim como as definições de procedimento são os meios de abstração no Lisp, as definições de regra são os meios de abstração na linguagem de consulta. Em cada caso, desenrolamos a abstração criando ligações apropriadas e avaliando o corpo da regra ou procedimento relativo a elas.</p><p>
<a name="%_sec_Temp_679" id="%_sec_Temp_679"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_679">Consultas simples</a></h4><p>
<a name="%_idx_5220" id="%_idx_5220"/>Vimos anteriormente nesta seção como avaliar consultas simples na ausência de regras. Agora que vimos como aplicar regras, podemos descrever como avaliar consultas simples usando regras e asserções.</p><p>Dado o padrão de consulta e um fluxo de quadros, produzimos, para cada quadro no fluxo de entrada, dois fluxos:</p><p>
</p><p/><ul><li>um fluxo de quadros estendidos obtido pela correspondência do padrão com todas as asserções na base de dados (usando o correspondente do padrão), e<p>
</p></li><li>um fluxo de quadros estendidos, obtido aplicando todas as regras possíveis (usando o unificador).<a name="call_footnote_Temp_680" href="#footnote_Temp_680" id="call_footnote_Temp_680"><sup><small>73</small></sup></a>
</li></ul><p/><p>O acréscimo desses dois fluxos produz um fluxo que consiste em todas as maneiras pelas quais o padrão fornecido pode ser satisfeito de maneira consistente com o quadro original. Esses fluxos (um para cada quadro no fluxo de entrada) agora são todos combinados para formar um fluxo grande, que, portanto, consiste em todas as maneiras pelas quais qualquer um dos quadros no fluxo de entrada original pode ser estendido para produzir uma correspondência com o padrão especificado.<a name="%_sec_Temp_681" id="%_sec_Temp_681"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_681">O avaliador da consulta e o laço do controlador</a></h4><p>
<a name="%_idx_5226" id="%_idx_5226"/>Apesar da complexidade das operações correspondentes, o sistema é organizado como um avaliador para qualquer linguagem. O procedimento que coordena as operações correspondentes é chamado <a name="%_idx_5228" id="%_idx_5228"/><a name="%_idx_5230" id="%_idx_5230"/><tt>qeval</tt> e desempenha um papel análogo ao do procedimento <tt>eval</tt> para Lisp. <tt>Qeval</tt> toma como entradas uma consulta e um fluxo de quadros. Sua saída é um fluxo de quadros, correspondendo a correspondências bem-sucedidas ao padrão de consulta, que estendem algum quadro no fluxo de entrada, conforme indicado na figura <a href="#%_fig_4.4">4.4.</a>. Como <tt>eval</tt>, <tt>qeval</tt> classifica os diferentes tipos de expressões (consultas) e despacha para um procedimento apropriado para cada um. Existe um procedimento para cada formulário especial (<tt>and</tt>, <tt>or</tt>, <tt>not</tt> e <tt>lisp-value</tt>) e um para consultas simples.</p><p>
<a name="%_idx_5232" id="%_idx_5232"/><a name="%_idx_5234" id="%_idx_5234"/>O laço do controlador, que é análogo ao procedimento <tt>driver-loop</tt> para os outros avaliadores neste capítulo, lê as consultas do terminal. Para cada consulta, ele chama <tt>qeval</tt> com a consulta e um fluxo que consiste em um único quadro vazio. Isso produzirá o fluxo de todas as correspondências possíveis (todas as extensões possíveis para o quadro vazio). Para cada quadro no fluxo resultante, ele instancia a consulta original usando os valores das variáveis encontradas no quadro. Esse fluxo de consultas instanciadas é então impresso.<a name="call_footnote_Temp_682" href="#footnote_Temp_682" id="call_footnote_Temp_682"><sup><small>74</small></sup></a></p><p>
<a name="%_idx_5240" id="%_idx_5240"/><a name="%_idx_5242" id="%_idx_5242"/>O controlador também verifica o comando especial <tt>assert!</tt>, que indica que a entrada não é uma consulta, mas uma asserção ou regra a ser adicionada ao banco de dados. Por exemplo,</p><p>
</p><p/><p><tt>(assert! (job (Bitdiddle Ben) (computer wizard)))<br/>
(assert! (rule (wheel ?person)<br/>
(and (supervisor ?middle-manager ?person)<br/>
(supervisor ?x ?middle-manager))))<br/></tt></p><p/><p>
<a name="%_sec_4.4.3" id="%_sec_4.4.3"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_4.4.3">4.4.3 A lógica da programação é lógica matemática?</a></h3><p>
<a name="%_idx_5244" id="%_idx_5244"/><a name="%_idx_5246" id="%_idx_5246"/>Os meios de combinação usados na linguagem de consulta podem parecer, a princípio, idênticos às operações <tt>and</tt>, <tt>or</tt> e <tt>not</tt> lógica matemática, e a aplicação das regras da linguagem de consulta é de fato realizada através de um método legítimo de <a name="%_idx_5248" id="%_idx_5248"/>inferência.<a name="call_footnote_Temp_683" href="#footnote_Temp_683" id="call_footnote_Temp_683"><sup><small>75</small></sup></a> Porém, essa identificação da linguagem de consulta com lógica matemática não é realmente válida, pois a linguagem de consulta fornece uma <a name="%_idx_5252" id="%_idx_5252"/><em>estrutura de controle</em> que interpreta as declarações lógicas processualmente. Geralmente, podemos tirar proveito dessa estrutura de controle. Por exemplo, para encontrar todos os supervisores de programadores, podemos formular uma consulta em uma das duas formas logicamente equivalentes:</p><p>
</p><p/><p><tt>(and (job ?x (computer programmer))<br/>
(supervisor ?x ?y))<br/></tt></p><p/><p>ou</p><p/><p><tt>(and (supervisor ?x ?y)<br/>
(job ?x (computer programmer)))<br/></tt></p><p/><p>
<a name="%_idx_5254" id="%_idx_5254"/>Se uma empresa tiver muito mais supervisores do que programadores (o caso usual), é melhor usar o primeiro formulário do que o segundo, pois a base de dados deve ser varrida para cada resultado intermediário (quadro) produzido pela primeira cláusula do <tt>and</tt>.</p><p>
<a name="%_idx_5256" id="%_idx_5256"/><a name="%_idx_5258" id="%_idx_5258"/>O objetivo da programação lógica é fornecer ao programador técnicas para decompor um problema computacional em dois problemas separados: “o que” deve ser calculado e “como” isso deve ser calculado. Isso é conseguido selecionando um subconjunto das instruções da lógica matemática que é poderoso o suficiente para ser capaz de descrever algo qualquer que alguém queira computar, mas fraco o suficiente para ter uma interpretação processual controlável. A intenção aqui é que, por um lado, um programa especificado em uma linguagem de programação lógica seja um programa eficaz que possa ser executado por um computador. O controle (“como” calcular) é efetuado usando a ordem de avaliação da linguagem. Deveríamos ser capazes de organizar a ordem das cláusulas e a ordem dos subobjetivos em cada cláusula para que o cálculo seja feito em uma ordem considerada eficaz e eficiente. Ao mesmo tempo, devemos ser capazes de ver o resultado da computação (“o que” computar) como uma simples consequência das leis da lógica.</p><p>Nossa linguagem de consulta pode ser considerada apenas um subconjunto processualmente interpretável da lógica matemática. Uma afirmação representa um fato simples (uma proposição atômica). Uma regra representa a implicação que a conclusão da regra mantém para os casos em que o corpo da regra mantém. Uma regra possui uma interpretação processual natural: para estabelecer a conclusão da regra, estabeleça o corpo da regra. Regras, portanto, especificam cálculos. No entanto, como as regras também podem ser consideradas declarações da lógica matemática, podemos justificar qualquer “inferência” realizada por um programa de lógica, afirmando que o mesmo resultado pode ser obtido trabalhando inteiramente dentro da lógica matemática.<a name="call_footnote_Temp_684" href="#footnote_Temp_684" id="call_footnote_Temp_684"><sup><small>76</small></sup></a></p><p>
<a name="%_sec_Temp_685" id="%_sec_Temp_685"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_685">Laços infinitos</a></h4><p>
<a name="%_idx_5260" id="%_idx_5260"/>Uma consequência da interpretação processual dos programas lógicos é que é possível construir programas irremediavelmente ineficientes para resolver certos problemas. Um caso extremo de ineficiência ocorre quando o sistema entra em laço infinito ao fazer deduções. Como um exemplo simples, suponha que montamos uma base de dados de casamentos famosos, incluindo</p><p>
<a name="%_idx_5262" id="%_idx_5262"/></p><p/><p><tt>(assert! (married Minnie Mickey))<br/></tt></p><p/><p>Se agora perguntarmos</p><p>
</p><p/><p><tt>(married Mickey ?who)<br/></tt></p><p/><p>não receberemos resposta, pois o sistema não sabe que se <em>A</em> é casado com <em>B</em>, então <em>B</em> é casado com <em>A</em>. Então, afirmamos a regra</p><p>
</p><p/><p><tt>(assert! (rule (married ?x ?y)<br/>
(married ?y ?x)))<br/></tt></p><p/><p>e novamente consultar</p><p>
</p><p/><p><tt>(married Mickey ?who)<br/></tt></p><p/><p>Infelizmente, isso conduzirá o sistema em um laço infinito, da seguinte maneira:</p><p>
</p><p/><ul><li>O sistema descobre que a regra <tt>married</tt> é aplicável; isto é, a conclusão da regra <tt>(married ?x ?y)</tt> unifica com sucesso o padrão de consulta <tt>(married Mickey ?who)</tt> para produzir um quadro em que <tt>?x</tt> é obrigado a <tt>Mickey</tt> e <tt>?y</tt> é obrigado a <tt>?who</tt>. Portanto, o interpretador passa a avaliar o corpo da regra <tt>(married ?y ?x)</tt> nesse quadro – com efeito, para processar a consulta <tt>(married ?who Mickey)</tt>.<p>
</p></li><li>Uma resposta aparece diretamente como uma afirmação no banco de dados: <tt>(married Minnie Mickey)</tt>.<p>
</p></li><li>A regra <tt>married</tt> também é aplicável; portanto, o interpretador avalia novamente o corpo da regra, que desta vez é equivalente a <tt>(married Mickey ?who)</tt>.</li></ul><p/><p>O sistema está agora em um laço infinito. De fato, se o sistema encontrará a resposta simples <tt>(married Minnie Mickey)</tt> antes de entrar no laço depende dos detalhes da implementação relativos à ordem em que o sistema verifica os itens no banco de dados. Este é um exemplo muito simples dos tipos de laços que podem ocorrer. Coleções de regras inter-relacionadas podem levar a laços muito mais difíceis de antecipar, e a aparência de um laço pode depender da ordem das cláusulas em um <tt>and</tt> (veja exercício <a href="#%_thm_4.64">4.64</a>) ou em detalhes de baixo nível relativos à ordem em que o sistema processa consultas.<a name="call_footnote_Temp_686" href="#footnote_Temp_686" id="call_footnote_Temp_686"><sup><small>77</small></sup></a>
<a name="%_sec_Temp_687" id="%_sec_Temp_687"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_687">Problemas com <tt>not</tt></a></h4><p>
<a name="%_idx_5266" id="%_idx_5266"/>
<a name="%_idx_5268" id="%_idx_5268"/>Outra peculiaridade no sistema de consulta diz respeito <tt>not</tt>. Dada a base de dados da seção <a href="#%_sec_4.4.1">4.4.1</a>, considere as duas consultas a seguir:</p><p>
</p><p/><p><tt>(and (supervisor ?x ?y)<br/>
(not (job ?x (computer programmer))))<br/>
(and (not (job ?x (computer programmer)))<br/>
(supervisor ?x ?y))<br/></tt></p><p/><p>Essas duas consultas não produzem o mesmo resultado. A primeira consulta começa localizando todas as entradas no banco de dados que correspondem <tt>(supervisor ?x ?y)</tt> e filtra os quadros resultantes removendo aqueles nos quais o valor de <tt>?x</tt> satisfaz <tt>(job ?x (computer programmer))</tt>. A segunda consulta começa filtrando os quadros recebidos para remover aqueles que podem satisfazer <tt>(job ?x (computer programmer))</tt>. Como o único quadro de entrada está vazio, ele verifica a base de dados para ver se há algum padrão que satisfaça <tt>(job ?x (computer programmer))</tt>. Como geralmente existem entradas deste formulário, a cláusula <tt>not</tt> filtra o quadro vazio e retorna um fluxo vazio de quadros. Consequentemente, toda a consulta composta retorna um fluxo vazio.</p><p>O problema é que nossa implementação de <tt>not</tt> realmente pretende servir como um filtro de valores para as variáveis. Se um a cláusula <tt>not</tt>é processada com um quadro nos quais algumas das variáveis permanecem independentes (como <tt>?x</tt> no exemplo acima), o sistema produzirá resultados inesperados. Problemas semelhantes ocorrem com o uso de <a name="%_idx_5270" id="%_idx_5270"/><tt>lisp-value</tt> – o predicado Lisp não pode funcionar se alguns de seus argumentos não forem ligadas. Veja o exercício <a href="#%_thm_4.77">4.77</a>.</p><p>Existe também uma maneira muito mais séria de como o <tt>not</tt> da linguagem de consulta difere da <tt>not</tt> da lógica matemática. Em lógica, interpretamos a afirmação “não <em>P</em>” significa que <em>P</em> não é verdade. No sistema de consulta, no entanto, “não <em>P</em>” significa que <em>P</em> não é dedutível do conhecimento no banco de dados. Por exemplo, dada a base de dados de pessoal da seção <a href="#%_sec_4.4.1">4.4.1</a>, o sistema deduziria com satisfação todos os tipos de <tt>not</tt> declarações, como que Ben Bitdiddle não é fã de beisebol, que não chove lá fora e que 2 + 2 não é 4.<a name="call_footnote_Temp_688" href="#footnote_Temp_688" id="call_footnote_Temp_688"><sup><small>78</small></sup></a> Em outras palavras, o <tt>not</tt> linguagens de programação lógicas reflete a chamada <a name="%_idx_5272" id="%_idx_5272"/><em>suposição do mundo fechado</em> que todas as informações relevantes foram incluídas no banco de dados.<a name="call_footnote_Temp_689" href="#footnote_Temp_689" id="call_footnote_Temp_689"><sup><small>79</small></sup></a>
</p><p><a name="%_thm_4.64" id="%_thm_4.64"/>
<b>Exercício 4.64.</b> <a name="%_idx_5276" id="%_idx_5276"/>Louis Reasoner exclui por engano a regra <tt>outranked-by</tt> (seção <a href="#%_sec_4.4.1">4.4.1</a>) da base de dados. Quando ele percebe isso, ele rapidamente o reinstala. Infelizmente, ele faz uma pequena alteração na regra e a digita como</p><p>
</p><p/><p><tt>(rule (outranked-by ?staff-person ?boss)<br/>
(or (supervisor ?staff-person ?boss)<br/>
(and (outranked-by ?middle-manager ?boss)<br/>
(supervisor ?staff-person ?middle-manager))))<br/></tt></p><p/><p>Logo após Louis digitar essas informações no sistema, DeWitt Aull aparece para descobrir quem supera Ben Bitdiddle. Ele emite a consulta</p><p>
</p><p/><p><tt>(outranked-by (Bitdiddle Ben) ?who)<br/></tt></p><p/><p>Depois de responder, o sistema entra em um laço infinito. Explique o porquê.</p><p/><p>
</p><p><a name="%_thm_4.65" id="%_thm_4.65"/>
<b>Exercício 4.65.</b> <a name="%_idx_5278" id="%_idx_5278"/>Cy D. Fect, ansioso pelo dia em que ele subirá na organização, faz uma consulta para encontrar todas as rodas (usando a regra <tt>wheel</tt> da seção <a href="#%_sec_4.4.1">4.4.1</a>):</p><p>
</p><p/><p><tt>(wheel ?who)<br/></tt></p><p/><p>Para sua surpresa, o sistema responde</p><p>
</p><p/><p><tt><i>;;; Query results:</i><br/>
(wheel (Warbucks Oliver))<br/>
(wheel (Bitdiddle Ben))<br/>
(wheel (Warbucks Oliver))<br/>
(wheel (Warbucks Oliver))<br/>
(wheel (Warbucks Oliver))<br/></tt></p><p/><p>Por que Oliver Warbucks está listado quatro vezes?</p><p/><p>
</p><p><a name="%_thm_4.66" id="%_thm_4.66"/>
<b>Exercício 4.66.</b> <a name="%_idx_5280" id="%_idx_5280"/>Ben generalizou o sistema de consulta para fornecer estatísticas sobre a empresa. Por exemplo, para encontrar os salários totais de todos os programadores de computador, um será capaz de dizer</p><p>
</p><p/><p><tt>(sum ?amount<br/>
(and (job ?x (computer programmer))<br/>
(salary ?x ?amount)))<br/></tt></p><p/><p>Em geral, o novo sistema de Ben permite expressões da forma</p><p>
</p><p/><p><tt>(accumulation-function <<em>variable</em>><br/>
<<em>query pattern</em>>)<br/></tt></p><p/><p>Onde <tt>accumulation-function</tt> pode ser algo como <tt>sum</tt>, <tt>average</tt> ou <tt>maximum</tt>. Ben argumenta que deve ser muito fácil implementar isso. Ele simplesmente alimentará o padrão de consulta para <tt>qeval</tt>. Isso produzirá um fluxo de quadros. Ele passará esse fluxo através de uma função de mapeamento que extrai o valor da variável designada de cada quadro no fluxo e alimenta o fluxo resultante de valores para a função de acumulação. Assim que Ben conclui a implementação e está prestes a testá-la, Cy passa, ainda intrigado com o resultado da consulta <tt>wheel</tt> no exercício <a href="#%_thm_4.65">4.65</a>. Quando Cy mostra a resposta do sistema, Ben geme: “Oh, não, meu esquema de acumulação simples não funcionará!”</p><p>O que Ben acabou de perceber? Descreva um método que ele pode usar para salvar a situação.</p><p/><p>
</p><p><a name="%_thm_4.67" id="%_thm_4.67"/>
<b>Exercício 4.67.</b> <a name="%_idx_5282" id="%_idx_5282"/><a name="%_idx_5284" id="%_idx_5284"/>Crie uma maneira de instalar um detector de laço no sistema de consulta para evitar os tipos de laços simples ilustrados no texto e no exercício <a href="#%_thm_4.64">4.64</a>. A ideia geral é que o sistema mantenha algum tipo de histórico de sua cadeia de deduções atual e não comece a processar uma consulta na qual já está trabalhando. Descreva que tipo de informação (padrões e quadros) está incluída neste histórico e como a verificação deve ser feita. (Depois de estudar os detalhes da implementação do sistema de consulta na seção <a href="#%_sec_4.4.4">4.4.4</a>, você pode modificar o sistema para incluir seu detector de laço).</p><p/><p>
</p><p><a name="%_thm_4.68" id="%_thm_4.68"/>
<b>Exercício 4.68.</b> <a name="%_idx_5286" id="%_idx_5286"/>Defina regras para implementar a operação <tt>reverse</tt> do exercício <a href="book-Z-H-15.html#%_thm_2.18">2.18</a>, que retorna uma lista que contém os mesmos elementos que uma determinada lista na ordem inversa. (Dica: use <tt>append-to-form</tt>). Suas regras podem responder a ambos <tt>(reverse (1 2 3) ?x)</tt> e <tt>(reverse ?x (1 2 3))</tt> ?</p><p/><p>
</p><p><a name="%_thm_4.69" id="%_thm_4.69"/>
<b>Exercício 4.69.</b> Começando com a base de dados e as regras que você formulou no exercício <a href="#%_thm_4.63">4.63</a>, crie uma regra para adicionar “grandes” a um relacionamento de neto. Isso deve permitir ao sistema deduzir que Irad é o bisneto de Adão, ou que Jabal e Jubal são os tataravós de Adão. (Dica: represente o fato sobre Irad, por exemplo, como <tt>((great grandson) Adam Irad)</tt>. Escreva regras que determinem se uma lista termina na palavra <tt>grandson</tt>. Use isso para expressar uma regra que permita derivar o relacionamento <tt>((great . ? rel)? x? y)</tt>, Onde <tt>?rel</tt> é uma lista que termina em <tt>grandson</tt>). Verifique suas regras em consultas como <tt>((great grandson) ?g ?ggs)</tt> e <tt>(?relationship Adam Irad)</tt>.</p><p>
<a name="%_sec_4.4.4" id="%_sec_4.4.4"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4">4.4.4 Implementando o sistema de consulta</a></h3><p>
</p><p>Seção <a href="#%_sec_4.4.2">4.4.2</a> descreveu como o sistema de consulta funciona. Agora, preenchemos os detalhes apresentando uma implementação completa do sistema.</p><p>
<a name="%_sec_4.4.4.1" id="%_sec_4.4.4.1"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4.1">4.4.4.1 O laço do controlador e a instanciação</a></h4><p>
</p><p>
<a name="%_idx_5288" id="%_idx_5288"/><a name="%_idx_5290" id="%_idx_5290"/>O laço do controlador para o sistema de consulta lê repetidamente as expressões de entrada. Se a expressão for uma regra ou asserção a ser adicionada ao banco de dados, as informações serão adicionadas. Caso contrário, a expressão será assumida como uma consulta. O controlador passa essa consulta para o avaliador <tt>qeval</tt> com um fluxo de quadros inicial que consiste em um único quadro vazio. O resultado da avaliação é um fluxo de quadros gerados satisfazendo a consulta com valores variáveis encontrados no banco de dados. Esses quadros são usados para formar um novo fluxo que consiste em cópias da consulta original, na qual as variáveis são instanciadas com valores fornecidos pelo fluxo de quadros, e esse fluxo final é impresso no terminal:</p><p>
</p><p/><p><tt><a name="%_idx_5292" id="%_idx_5292"/>(define input-prompt ";;; Query input:")<br/>
(define output-prompt ";;; Query results:")<br/><a name="%_idx_5294" id="%_idx_5294"/>(define (query-driver-loop)<br/>
(prompt-for-input input-prompt)<br/>
(let ((q (query-syntax-process (read))))<br/>
(cond ((assertion-to-be-added? q)<br/>
(add-rule-or-assertion! (add-assertion-body q))<br/>
(newline)<br/>
(display "Assertion added to data base.")<br/>
(query-driver-loop))<br/>
(else<br/>
(newline)<br/>
(display output-prompt)<br/>
(display-stream<br/>
(stream-map<br/>
(lambda (frame)<br/>
(instantiate q<br/>
frame<br/>
(lambda (v f)<br/>
(contract-question-mark v))))<br/>
(qeval q (singleton-stream '()))))<br/>
(query-driver-loop)))))<br/></tt></p><p/><p>
<a name="%_idx_5296" id="%_idx_5296"/>Aqui, como nos outros avaliadores deste capítulo, usamos uma sintaxe abstrata para as expressões da linguagem de consulta. A implementação da sintaxe da expressão, incluindo o predicado <tt>assertion-to-be-added?</tt> e o seletor <tt>add-assertion-body</tt>, é fornecido na seção <a href="#%_sec_4.4.4.7">4.4.4.7</a>. <tt>Add-rule-or-assertion!</tt> é definido na seção <a href="#%_sec_4.4.4.5">4.4.4.5</a>.</p><p>Antes de fazer qualquer processamento em uma expressão de entrada, o laço do controlador a transforma sintaticamente em um formulário que torna o processamento mais eficiente. Isso envolve mudar a<a name="%_idx_5298" id="%_idx_5298"/><a name="%_idx_5300" id="%_idx_5300"/>representação do padrão de variáveis. Quando a consulta é instanciada, quaisquer variáveis que permanecem independentes são transformadas de volta na representação de entrada antes de serem impressas. Essas transformações são realizadas pelos dois procedimentos <tt>query-syntax-process</tt> e <tt>contract-question-mark</tt> (seção <a href="#%_sec_4.4.4.7">4.4.4.7</a>)</p><p>
<a name="%_idx_5302" id="%_idx_5302"/>Para instanciar uma expressão, a copiamos, substituindo quaisquer variáveis na expressão por seus valores em um determinado quadro. Os próprios valores são instanciados, pois podem conter variáveis (por exemplo, se <tt>?x</tt> no <tt>exp</tt> é obrigado a <tt>?y</tt> como resultado da unificação e <tt>?y</tt> por sua vez, está ligado a 5). A ação a ser tomada se uma variável não puder ser instanciada é fornecida por um argumento processual para <tt>instantiate</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_5304" id="%_idx_5304"/>(define (instantiate exp frame unbound-var-handler)<br/>
(define (copy exp)<br/>
(cond ((var? exp)<br/>
(let ((binding (binding-in-frame exp frame)))<br/>
(if binding<br/>
(copy (binding-value binding))<br/>
(unbound-var-handler exp frame))))<br/>
((pair? exp)<br/>
(cons (copy (car exp)) (copy (cdr exp))))<br/>
(else exp)))<br/>
(copy exp))<br/></tt></p><p/><p>Os procedimentos que manipulam ligações são definidos na seção <a href="#%_sec_4.4.4.8">4.4.4.8</a>.</p><p>
<a name="%_sec_4.4.4.2" id="%_sec_4.4.4.2"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4.2">4.4.4.2 O avaliador</a></h4><p>
</p><p>
<a name="%_idx_5306" id="%_idx_5306"/>O procedimento <tt>qeval</tt>, chamado pelo <tt>query-driver-loop</tt>, é o avaliador básico do sistema de consulta. Ele toma como entrada uma consulta e um fluxo de quadros e retorna um fluxo de quadros estendidos. Ele identifica formulários especiais por um <a name="%_idx_5308" id="%_idx_5308"/>envio orientado a dados usando <tt>get</tt> e <tt>put</tt>, assim como fizemos na implementação de operações genéricas no capítulo 2. Qualquer consulta que não seja identificada como um formulário especial é considerada uma consulta simples, a ser processada por <tt>simple-query</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_5310" id="%_idx_5310"/>(define (qeval query frame-stream)<br/>
(let ((qproc (get (type query) 'qeval)))<br/>
(if qproc<br/>
(qproc (contents query) frame-stream)<br/>
(simple-query query frame-stream))))<br/></tt></p><p/><p>
<tt>Type</tt> e <tt>contents</tt>, definido na seção <a href="#%_sec_4.4.4.7">4.4.4.7</a>, implemente a sintaxe abstrata dos formulários especiais.</p><p>
<a name="%_sec_Temp_696" id="%_sec_Temp_696"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_696">Consultas simples</a></h4><p>
<a name="%_idx_5312" id="%_idx_5312"/>O procedimento <tt>simple-query</tt> lida com consultas simples. Ele usa como argumento uma consulta simples (um padrão) junto com um fluxo de quadros e retorna o fluxo formado estendendo cada quadro por todas as correspondências da consulta na base de dados.</p><p>
</p><p/><p><tt><a name="%_idx_5314" id="%_idx_5314"/>(define (simple-query query-pattern frame-stream)<br/>
(stream-flatmap<br/>
(lambda (frame)<br/>
(stream-append-delayed<br/>
(find-assertions query-pattern frame)<br/>
(delay (apply-rules query-pattern frame))))<br/>
frame-stream))<br/></tt></p><p/><p/><p>Para cada quadro no fluxo de entrada, usamos <tt>find-assertions</tt> (seção <a href="#%_sec_4.4.4.3">4.4.4.3</a>) para combinar o padrão com todas as asserções no banco de dados, produzindo um fluxo de quadros estendidos e usamos <tt>apply-rules</tt> (seção <a href="#%_sec_4.4.4.4">4.4.4.4</a>) para aplicar todas as regras possíveis, produzindo outro fluxo de quadros estendidos. Esses dois fluxos são combinados (usando <tt>stream-append-delayed</tt>, seção <a href="#%_sec_4.4.4.6">4.4.4.6</a>) para fazer um fluxo de todas as maneiras pelas quais o padrão fornecido pode ser satisfeito de forma consistente com o quadro original (consulte o exercício <a href="#%_thm_4.71">4.71</a>) Os fluxos para os quadros de entrada individuais são combinados usando <tt>stream-flatmap</tt> (seção <a href="#%_sec_4.4.4.6">4.4.4.6</a>) para formar um grande fluxo de todas as maneiras pelas quais qualquer um dos quadros no fluxo de entrada original pode ser estendido para produzir uma correspondência com o padrão fornecido.<a name="%_sec_Temp_697" id="%_sec_Temp_697"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_697">Consultas compostas</a></h4><p>
<a name="%_idx_5316" id="%_idx_5316"/>
<a name="%_idx_5318" id="%_idx_5318"/>Consultas <tt>And</tt> são tratadas como ilustrado na figura <a href="#%_fig_4.5">4.5</a> pelo procedimento <tt>conjoin</tt>. <tt>Conjoin</tt> toma como entradas os conjuntos e o fluxo de quadros e retorna o fluxo de quadros estendidos. Primeiro, <tt>conjoin</tt> processa o fluxo de quadros para encontrar o fluxo de todas as extensões de quadro possíveis que satisfazem a primeira consulta na conjunção. Em seguida, usando isso como o novo fluxo de quadros, aplica-se recursivamente <tt>conjoin</tt> para o restante das consultas.</p><p>
</p><p/><p><tt><a name="%_idx_5320" id="%_idx_5320"/>(define (conjoin conjuncts frame-stream)<br/>
(if (empty-conjunction? conjuncts)<br/>
frame-stream<br/>
(conjoin (rest-conjuncts conjuncts)<br/>
(qeval (first-conjunct conjuncts)<br/>
frame-stream))))<br/></tt></p><p/><p>A expressão</p><p/><p><tt>(put 'and 'qeval conjoin)<br/></tt></p><p/><p>estabelece <tt>qeval</tt> enviar para <tt>conjoin</tt> quando um <tt>and</tt> formulário é encontrado.</p><p>
<a name="%_idx_5322" id="%_idx_5322"/><tt>Or</tt> consultas são tratadas de maneira semelhante, como mostra a figura <a href="#%_fig_4.6">4.6</a>. Os fluxos de saída para os vários disjuntores do <tt>or</tt> são calculados separadamente e mesclados usando o procedimento <tt>interleave-delayed</tt> da seção <a href="#%_sec_4.4.4.6">4.4.4.6</a>. (Veja exercícios <a href="#%_thm_4.71">4.71</a> e <a href="#%_thm_4.72">4.72</a>).</p><p>
</p><p/><p><tt><a name="%_idx_5324" id="%_idx_5324"/>(define (disjoin disjuncts frame-stream)<br/>
(if (empty-disjunction? disjuncts)<br/>
the-empty-stream<br/>
(interleave-delayed<br/>
(qeval (first-disjunct disjuncts) frame-stream)<br/>
(delay (disjoin (rest-disjuncts disjuncts)<br/>
frame-stream)))))<br/>
(put 'or 'qeval disjoin)<br/></tt></p><p/><p>Os predicados e seletores para a sintaxe de conjuntos e disjuntos são fornecidos na seção <a href="#%_sec_4.4.4.7">4.4.4.7</a>.</p><p>
<a name="%_sec_Temp_698" id="%_sec_Temp_698"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_698">Filtros</a></h4><p>
<a name="%_idx_5326" id="%_idx_5326"/><tt>Not</tt> é tratado pelo método descrito na seção <a href="#%_sec_4.4.2">4.4.2</a>. Tentamos estender cada quadro no fluxo de entrada para satisfazer a consulta que é negada e incluímos um determinado quadro no fluxo de saída apenas se não puder ser estendido.</p><p>
</p><p/><p><tt><a name="%_idx_5328" id="%_idx_5328"/>(define (negate operands frame-stream)<br/>
(stream-flatmap<br/>
(lambda (frame)<br/>
(if (stream-null? (qeval (negated-query operands)<br/>
(singleton-stream frame)))<br/>
(singleton-stream frame)<br/>
the-empty-stream))<br/>
frame-stream))<br/>
(put 'not 'qeval negate)<br/></tt></p><p/><p/><p>
<a name="%_idx_5330" id="%_idx_5330"/><tt>Lisp-value</tt> é um filtro semelhante a <tt>not</tt>. Cada quadro no fluxo é usado para instanciar as variáveis no padrão, o predicado indicado é aplicado e os quadros para os quais o predicado retorna falso são filtrados para fora do fluxo de entrada. Um erro ocorre se houver variáveis de padrão não ligadas.</p><p>
</p><p/><p><tt><a name="%_idx_5332" id="%_idx_5332"/>(define (lisp-value call frame-stream)<br/>
(stream-flatmap<br/>
(lambda (frame)<br/>
(if (execute<br/>
(instantiate<br/>
call<br/>
frame<br/>
(lambda (v f)<br/>
(error "Unknown pat var -- LISP-VALUE" v))))<br/>
(singleton-stream frame)<br/>
the-empty-stream))<br/>
frame-stream))<br/>
(put 'lisp-value 'qeval lisp-value)<br/></tt></p><p/><p/><p>
<tt>Execute</tt>, que aplica o predicado aos argumentos, deve aplicar <tt>eval</tt> à expressão de predicado para obter o procedimento a ser aplicado. No entanto, ele não deve avaliar os argumentos, pois eles já são os argumentos reais, não expressões cuja avaliação (em Lisp) produzirá os argumentos. Observe que <tt>execute</tt> é implementado usando <a name="%_idx_5334" id="%_idx_5334"/><tt>eval</tt> e <tt>apply</tt> do sistema Lisp subjacente.</p><p>
</p><p/><p><tt>(define (execute exp)<br/>
(apply (eval (predicate exp) user-initial-environment)<br/>
(args exp)))<br/></tt></p><p/><p/><p>O formulário <tt>always-true</tt> especial fornece uma consulta sempre satisfeita. Ele ignora seu conteúdo (normalmente vazio) e simplesmente passa por todos os quadros no fluxo de entrada. <tt>Always-true</tt> é usado pelo seletor <tt>rule-body</tt> (seção <a href="#%_sec_4.4.4.7">4.4.4.7</a>) <a name="%_idx_5336" id="%_idx_5336"/>fornecer corpos para regras que foram definidas sem corpos (ou seja, regras cujas conclusões são sempre satisfeitas).</p><p>
</p><p/><p><tt><a name="%_idx_5338" id="%_idx_5338"/>(define (always-true ignore frame-stream) frame-stream)<br/>
(put 'always-true 'qeval always-true)<br/></tt></p><p/><p>Os seletores que definem a sintaxe de <tt>not</tt> e <tt>lisp-value</tt> são dados na seção <a href="#%_sec_4.4.4.7">4.4.4.7</a>.</p><p>
<a name="%_sec_4.4.4.3" id="%_sec_4.4.4.3"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4.3">4.4.4.3 Localizando asserções por correspondência de padrões</a></h4><p>
</p><p>
<a name="%_idx_5340" id="%_idx_5340"/><a name="%_idx_5342" id="%_idx_5342"/><tt>Find-assertions</tt>, chamado por <tt>simple-query</tt> (seção <a href="#%_sec_4.4.4.2">4.4.4.2</a>), leva como entrada um padrão e um quadro. Ele retorna um fluxo de quadros, cada um estendendo o dado por uma correspondência de banco de dados do padrão especificado. Usa <tt>fetch-assertions</tt> (seção <a href="#%_sec_4.4.4.5">4.4.4.5</a>) para obter um fluxo de todas as asserções no banco de dados que devem ser verificadas quanto à correspondência com o padrão e o quadro. A razão para <tt>fetch-assertions</tt> aqui é que geralmente podemos aplicar testes simples que eliminam muitas das entradas na base de dados do pool de candidatos para uma correspondência bem-sucedida. O sistema ainda funcionaria se eliminássemos <tt>fetch-assertions</tt> e simplesmente verificamos um fluxo de todas as asserções no banco de dados, mas o cálculo seria menos eficiente, pois precisaríamos fazer muito mais chamadas para o correspondente.</p><p>
</p><p/><p><tt><a name="%_idx_5344" id="%_idx_5344"/>(define (find-assertions pattern frame)<br/>
(stream-flatmap (lambda (datum)<br/>
(check-an-assertion datum pattern frame))<br/>
(fetch-assertions pattern frame)))<br/></tt></p><p/><p/><p>
<tt>Check-an-assertion</tt> toma como argumento um padrão, um objeto de dados (asserção) e um quadro e retorna um fluxo de um elemento contendo o quadro estendido ou <tt>the-empty-stream</tt> se a partida falhar.</p><p>
</p><p/><p><tt>(define (check-an-assertion assertion query-pat query-frame)<br/>
(let ((match-result<br/>
(pattern-match query-pat assertion query-frame)))<br/>
(if (eq? match-result 'failed)<br/>
the-empty-stream<br/>
(singleton-stream match-result))))<br/></tt></p><p/><p>O correspondente de padrão básico retorna o símbolo <tt>failed</tt> ou uma extensão do quadro fornecido. A ideia básica do combinador é verificar o padrão em relação aos dados, elemento por elemento, acumulando ligações para as variáveis do padrão. Se o padrão e o objeto de dados forem iguais, a correspondência será bem-sucedida e retornamos o quadro de ligações acumuladas até o momento. Caso contrário, se o padrão for uma variável, estenderemos o quadro atual ligando a variável aos dados, desde que isso seja consistente com as ligações já existentes no quadro. Se o padrão e os dados forem pares, corresponderemos (recursivamente) ao <tt>car</tt> do padrão contra o <tt>car</tt> dos dados para produzir um quadro; neste quadro, então combinamos o <tt>cdr</tt> do padrão contra o <tt>cdr</tt> dos dados. Se nenhum desses casos for aplicável, a correspondência falha e retornamos o símbolo <tt>failed</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_5346" id="%_idx_5346"/>(define (pattern-match pat dat frame)<br/>
(cond ((eq? frame 'failed) 'failed)<br/>
((equal? pat dat) frame)<br/>
((var? pat) (extend-if-consistent pat dat frame))<br/>
((and (pair? pat) (pair? dat))<br/>
(pattern-match (cdr pat)<br/>
(cdr dat)<br/>
(pattern-match (car pat)<br/>
(car dat)<br/>
frame)))<br/>
(else 'failed)))<br/></tt></p><p/><p/><p>Aqui está o procedimento que estende um quadro adicionando uma nova ligação, se isso for consistente com as ligações já existentes no quadro:</p><p>
</p><p/><p><tt><a name="%_idx_5348" id="%_idx_5348"/>(define (extend-if-consistent var dat frame)<br/>
(let ((binding (binding-in-frame var frame)))<br/>
(if binding<br/>
(pattern-match (binding-value binding) dat frame)<br/>
(extend var dat frame))))<br/></tt></p><p/><p>Se não houver ligação para a variável no quadro, basta adicionar a ligação da variável aos dados. Caso contrário, combinamos, no quadro, os dados com o valor da variável no quadro. Se o valor armazenado contiver apenas constantes, como deve ter sido armazenado durante a correspondência de padrões por <tt>extend-if-consistent</tt>, a correspondência simplesmente testa se os valores armazenados e os novos são os mesmos. Nesse caso, ele retorna o quadro não modificado; caso contrário, retorna uma indicação de falha. O valor armazenado pode, no entanto, conter variáveis padrão se ele foi armazenado durante a unificação (consulte a seção <a href="#%_sec_4.4.4.4">4.4.4.4</a>) A correspondência recursiva do padrão armazenado com os novos dados incluirá ou verificará as ligações para as variáveis nesse padrão. Por exemplo, suponha que tenhamos um quadro no qual <tt>?x</tt> é obrigado a <tt>(f ?y)</tt> e <tt>?y</tt> é ilimitado e queremos incrementar esse quadro ligado a <tt>?x</tt> para <tt>(f b)</tt>. Olhamos <tt>?x</tt> e achar que é obrigado a <tt>(f ?y)</tt>. Isso nos leva a igualar <tt>(f ?y)</tt> contra o novo valor proposto <tt>(f b)</tt> no mesmo quadro. Eventualmente, essa correspondência estende o quadro adicionando uma ligação de <tt>?y</tt> para <tt>b</tt>. <tt>?X</tt> permanece ligado a <tt>(f ?y)</tt>. Nunca modificamos uma ligação armazenada e nunca armazenamos mais de uma ligação para uma determinada variável.</p><p>Os procedimentos usados pelo <tt>extend-if-consistent</tt> para manipular ligações são definidas na seção <a href="#%_sec_4.4.4.8">4.4.4.8</a>.</p><p>
<a name="%_sec_Temp_699" id="%_sec_Temp_699"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_699">Padrões com caudas pontilhadas</a></h4><p>
<a name="%_idx_5350" id="%_idx_5350"/>Se um padrão contiver um ponto seguido por uma variável de padrão, a variável de padrão corresponderá ao restante da lista de dados (em vez do próximo elemento da lista de dados), exatamente como seria de esperar com a notação de cauda pontilhada descrita no exercício <a href="book-Z-H-15.html#%_thm_2.20">2.20</a>. Embora o combinador de padrões que acabamos de implementar não procure pontos, ele se comporta como queremos. Isso ocorre, pois o Lisp <tt>read</tt> primitivo, usado por <tt>query-driver-loop</tt> para ler a consulta e representá-la como uma estrutura de lista, trata os pontos de uma maneira especial.</p><p>
<a name="%_idx_5352" id="%_idx_5352"/><a name="%_idx_5354" id="%_idx_5354"/>Quando <tt>read</tt> vê um ponto, em vez de tornar o próximo item o próximo elemento de uma lista (o <tt>car</tt> de um <tt>cons</tt> de quem <tt>cdr</tt> será o restante da lista) faz com que o próximo item seja o <tt>cdr</tt> da estrutura da lista. Por exemplo, a estrutura da lista produzida por <tt>read</tt> para o padrão <tt>(computer ?type)</tt> poderia ser construído avaliando a expressão <tt>(cons 'computer (cons '?type '()))</tt> e isso para <tt>(computador. ?tipo)</tt> poderia ser construído avaliando a expressão <tt>(cons 'computer '?type)</tt>.</p><p>Assim, como <tt>pattern-match</tt> compara recursivamente <tt>car</tt> areia <tt>cdr</tt> s de uma lista de dados e de um padrão com um ponto, ele eventualmente corresponde à variável após o ponto (que é um <tt>cdr</tt> do padrão) em uma sub-lista da lista de dados, ligando a variável a essa lista. Por exemplo, combinando o padrão <tt>(computador. ?tipo)</tt> contra <tt>(computer programmer trainee)</tt> vai combinar <tt>?type</tt> contra a lista <tt>(programmer trainee)</tt>.<a name="%_sec_4.4.4.4" id="%_sec_4.4.4.4"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4.4">4.4.4.4 Regras e unificação</a></h4><p>
</p><p>
<a name="%_idx_5356" id="%_idx_5356"/><tt>Apply-rules</tt> é a regra análoga de <tt>find-assertions</tt> (seção <a href="#%_sec_4.4.4.3">4.4.4.3</a>) Ele assume como entrada um padrão e um quadro e forma um fluxo de quadros de extensão aplicando regras a partir do banco de dados. <tt>Stream-flatmap</tt> mapas <tt>apply-a-rule</tt> no fluxo de regras possivelmente aplicáveis (selecionadas por <tt>fetch-rules</tt>, seção <a href="#%_sec_4.4.4.5">4.4.4.5</a>) e combina os fluxos de quadros resultantes.</p><p>
</p><p/><p><tt><a name="%_idx_5358" id="%_idx_5358"/>(define (apply-rules pattern frame)<br/>
(stream-flatmap (lambda (rule)<br/>
(apply-a-rule rule pattern frame))<br/>
(fetch-rules pattern frame)))<br/></tt></p><p/><p/><p>
<tt>Apply-a-rule</tt> aplica regras usando o método descrito na seção <a href="#%_sec_4.4.2">4.4.2</a>. Primeiro, ele incrementa seu quadro de argumentos, unificando a conclusão da regra com o padrão no quadro fornecido. Se for bem-sucedido, ele avalia o corpo da regra nesse novo quadro.</p><p>Antes de tudo isso acontecer, no entanto, o programa renomeia todas as variáveis na regra com novos nomes exclusivos. A razão para isso é impedir que as variáveis para aplicações de regras diferentes se confundam. Por exemplo, se duas regras usam uma variável chamada <tt>?x</tt>, cada um pode adicionar uma ligação para <tt>?x</tt> ao quadro quando aplicado. Estes dois <tt>?x</tt> não possuem nada a ver um com o outro, e não devemos nos deixar enganar ao pensar que as duas ligações devem ser consistentes. Em vez de renomear variáveis, poderíamos criar uma estrutura de ambiente mais inteligente; no entanto, a abordagem de renomeação que escolhemos aqui é a mais direta, mesmo que não seja a mais eficiente. (Consulte o exercício <a href="#%_thm_4.79">4.79</a>). Aqui está o procedimento <tt>apply-a-rule</tt>:</p><p>
</p><p/><p><tt>(define (apply-a-rule rule query-pattern query-frame)<br/>
(let ((clean-rule (rename-variables-in rule)))<br/>
(let ((unify-result<br/>
(unify-match query-pattern<br/>
(conclusion clean-rule)<br/>
query-frame)))<br/>
(if (eq? unify-result 'failed)<br/>
the-empty-stream<br/>
(qeval (rule-body clean-rule)<br/>
(singleton-stream unify-result))))))<br/></tt></p><p/><p>Os seletores <tt>rule-body</tt> e <tt>conclusion</tt> que extraem partes de uma regra são definidas na seção <a href="#%_sec_4.4.4.7">4.4.4.7</a>.</p><p>Geramos nomes de variáveis exclusivos, associando um identificador exclusivo (como um número) a cada aplicação de regra e combinando esse identificador com os nomes de variáveis originais. Por exemplo, se o identificador da aplicação de regra for 7, poderemos alterar cada <tt>?x</tt> na regra de <tt>?x-7</tt> e cada <tt>?y</tt> na regra de <tt>?y-7</tt>. (<tt>Make-new-variable</tt> e <tt>new-rule-application-id</tt> estão incluídos nos procedimentos de sintaxe na seção <a href="#%_sec_4.4.4.7">4.4.4.7</a>).</p><p>
</p><p/><p><tt>(define (rename-variables-in rule)<br/>
(let ((rule-application-id (new-rule-application-id)))<br/>
(define (tree-walk exp)<br/>
(cond ((var? exp)<br/>
(make-new-variable exp rule-application-id))<br/>
((pair? exp)<br/>
(cons (tree-walk (car exp))<br/>
(tree-walk (cdr exp))))<br/>
(else exp)))<br/>
(tree-walk rule)))<br/></tt></p><p/><p>
<a name="%_idx_5360" id="%_idx_5360"/><a name="%_idx_5362" id="%_idx_5362"/>O algoritmo de unificação é implementado como um procedimento que recebe como entrada dois padrões e um quadro e retorna o quadro estendido ou o símbolo <tt>failed</tt>. O unificador é como o correspondente de padrões, exceto que é simétrico – variáveis são permitidas nos dois lados da correspondência. <tt>Unify-match</tt> é basicamente o mesmo que <tt>pattern-match</tt>, exceto que há um código extra (marcado como “<tt>***</tt>”Abaixo) para lidar com o caso em que o objeto no lado direito da partida é uma variável.</p><p>
</p><p/><p><tt><a name="%_idx_5364" id="%_idx_5364"/>(define (unify-match p1 p2 frame)<br/>
(cond ((eq? frame 'failed) 'failed)<br/>
((equal? p1 p2) frame)<br/>
((var? p1) (extend-if-possible p1 p2 frame))<br/>
((var? p2) (extend-if-possible p2 p1 frame)) <em>; ***</em><br/>
((and (pair? p1) (pair? p2))<br/>
(unify-match (cdr p1)<br/>
(cdr p2)<br/>
(unify-match (car p1)<br/>
(car p2)<br/>
frame)))<br/>
(else 'failed)))<br/></tt></p><p/><p/><p>Na unificação, como na correspondência unilateral de padrões, queremos aceitar uma extensão proposta do quadro apenas se for consistente com as ligações existentes. O procedimento <tt>extend-if-possible</tt> usado na unificação é o mesmo que o <tt>extend-if-consistent</tt> usado na correspondência de padrões, exceto por duas verificações especiais, marcadas como “<tt>***</tt>” no programa abaixo. No primeiro caso, se a variável que tentamos corresponder não estiver ligada, mas o valor com o qual tentamos corresponder for uma variável (diferente), é necessário verificar se o valor está ligado e se portanto, para corresponder ao seu valor. Se ambas as partes da partida não forem ligadas, podemos ligar uma à outra.</p><p>A segunda verificação trata das tentativas de ligar uma variável a um padrão que inclui essa variável. Tal situação pode ocorrer sempre que uma variável é repetida nos dois padrões. Considere, por exemplo, unificar os dois padrões <tt>(?x ?x)</tt> e <tt>(?y <<em>expression involving <tt>?y</tt></em>>)</tt> em um quadro onde ambos <tt>?x</tt> e <tt>?y</tt> são ilimitados. Primeiro <tt>?x</tt> é comparado com <tt>?y</tt>, fazendo uma ligação de <tt>?x</tt> para <tt>?y</tt>. Em seguida, o mesmo <tt>?x</tt> corresponde à expressão dada que envolve <tt>?y</tt>. Desde a <tt>?x</tt> já está ligado a <tt>?y</tt>, isso resulta em correspondência <tt>?y</tt> contra a expressão. Se pensarmos no unificador como encontrar um conjunto de valores para as variáveis de padrão que tornam os padrões iguais, então esses padrões implicam instruções para encontrar um <tt>?y</tt> de tal modo que <tt>?y</tt> é igual à expressão que envolve <tt>?y</tt>. Não existe um método geral para resolver essas equações, por isso rejeitamos essas ligações; estes casos são reconhecidos pelo predicado <tt>depends-on?</tt>.<a name="call_footnote_Temp_700" href="#footnote_Temp_700" id="call_footnote_Temp_700"><sup><small>80</small></sup></a> Por outro lado, não queremos rejeitar tentativas de ligar uma variável a si mesma. Por exemplo, considere unificar <tt>(?x ?x)</tt> e <tt>(?y ?y)</tt>. A segunda tentativa de ligar <tt>?x</tt> para <tt>?y</tt> partidas <tt>?y</tt> (o valor armazenado de <tt>?x</tt>) contra <tt>?y</tt> (o novo valor de <tt>?x</tt>) Isso é resolvido pelo <tt>equal?</tt> cláusula de <tt>unify-match</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_5370" id="%_idx_5370"/>(define (extend-if-possible var val frame)<br/>
(let ((binding (binding-in-frame var frame)))<br/>
(cond (binding<br/>
(unify-match<br/>
(binding-value binding) val frame))<br/>
((var? val) <em>; ***</em><br/>
(let ((binding (binding-in-frame val frame)))<br/>
(if binding<br/>
(unify-match<br/>
var (binding-value binding) frame)<br/>
(extend var val frame))))<br/>
((depends-on? val var frame) <em>; ***</em><br/>
'failed)<br/>
(else (extend var val frame)))))<br/></tt></p><p/><p/><p>
<tt>Depends-on?</tt> é um predicado que testa se uma expressão proposta para ser o valor de uma variável padrão depende da variável Isso deve ser feito em relação ao quadro atual, pois a expressão pode conter ocorrências de uma variável que já possui um valor que depende da nossa variável de teste. A estrutura de <tt>depends-on?</tt> é uma simples caminhada recursiva na árvore, na qual substituímos os valores das variáveis sempre que necessário.</p><p>
</p><p/><p><tt>(define (depends-on? exp var frame)<br/>
(define (tree-walk e)<br/>
(cond ((var? e)<br/>
(if (equal? var e)<br/>
true<br/>
(let ((b (binding-in-frame e frame)))<br/>
(if b<br/>
(tree-walk (binding-value b))<br/>
false))))<br/>
((pair? e)<br/>
(or (tree-walk (car e))<br/>
(tree-walk (cdr e))))<br/>
(else false)))<br/>
(tree-walk exp))<br/></tt></p><p/><p>
<a name="%_sec_4.4.4.5" id="%_sec_4.4.4.5"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4.5">4.4.4.5 Mantendo a base de dados</a></h4><p>
<a name="%_idx_5372" id="%_idx_5372"/>
<a name="%_idx_5374" id="%_idx_5374"/><a name="%_idx_5376" id="%_idx_5376"/>Um problema importante no projeto de linguagens de programação lógica é o de organizar para que o menor número possível de entradas irrelevantes do banco de dados seja examinado na verificação de um determinado padrão. Em nosso sistema, além de armazenar todas as asserções em um grande fluxo, armazenamos todas as asserções cujas <tt>car</tt> s são símbolos constantes em fluxos separados, em uma tabela indexada pelo símbolo. Para buscar uma asserção que possa corresponder a um padrão, primeiro verificamos se o <tt>car</tt> do padrão é um símbolo constante. Nesse caso, retornamos (para serem testados usando o matcher) todas as asserções armazenadas que possuem o mesmo <tt>car</tt>. Se o padrão é <tt>car</tt> não é um símbolo constante, retornamos todas as asserções armazenadas. Métodos mais inteligentes também podem tirar proveito das informações no quadro, ou tentar também otimizar o caso em que o <tt>car</tt> do padrão não é um símbolo constante. Evitamos criar nossos critérios para indexação (usando o <tt>car</tt>, manipulando apenas o caso de símbolos constantes) no programa; em vez disso, recorremos a predicados e seletores que incorporam nossos critérios.</p><p>
</p><p/><p><tt>(define THE-ASSERTIONS the-empty-stream)<br/><a name="%_idx_5378" id="%_idx_5378"/>(define (fetch-assertions pattern frame)<br/>
(if (use-index? pattern)<br/>
(get-indexed-assertions pattern)<br/>
(get-all-assertions)))<br/>
(define (get-all-assertions) THE-ASSERTIONS)<br/>
(define (get-indexed-assertions pattern)<br/>
(get-stream (index-key-of pattern) 'assertion-stream))<br/></tt></p><p/><p>
<tt>Get-stream</tt> procura um fluxo na tabela e retorna um fluxo vazio se nada estiver armazenado lá.</p><p>
</p><p/><p><tt>(define (get-stream key1 key2)<br/>
(let ((s (get key1 key2)))<br/>
(if s s the-empty-stream)))<br/></tt></p><p/><p/><p>As regras são armazenadas da mesma forma, usando o <tt>car</tt> da conclusão da regra. As conclusões das regras são padrões arbitrários, no entanto, portanto diferem das afirmações em que podem conter variáveis. Um padrão cuja <tt>car</tt> Um símbolo constante pode corresponder a regras cujas conclusões começam com uma variável, bem como regras cujas conclusões possuem o mesmo <tt>car</tt>. Portanto, ao buscar regras que possam corresponder a um padrão cuja <tt>car</tt> é um símbolo constante, buscamos todas as regras cujas conclusões começam com uma variável e aquelas cujas conclusões possuem o mesmo <tt>car</tt> como o padrão. Para esse fim, armazenamos todas as regras cujas conclusões começam com uma variável em um fluxo separado em nossa tabela, indexado pelo símbolo <tt>?</tt>.</p><p>
</p><p/><p><tt>(define THE-RULES the-empty-stream)<br/><a name="%_idx_5380" id="%_idx_5380"/>(define (fetch-rules pattern frame)<br/>
(if (use-index? pattern)<br/>
(get-indexed-rules pattern)<br/>
(get-all-rules)))<br/>
(define (get-all-rules) THE-RULES)<br/>
(define (get-indexed-rules pattern)<br/>
(stream-append<br/>
(get-stream (index-key-of pattern) 'rule-stream)<br/>
(get-stream '? 'rule-stream)))<br/></tt></p><p/><p/><p>
<tt>Add-rule-or-assertion!</tt> é usado por <tt>query-driver-loop</tt> para adicionar asserções e regras ao banco de dados. Cada item é armazenado no índice, se apropriado, e em um fluxo de todas as asserções ou regras no banco de dados.</p><p>
</p><p/><p><tt><a name="%_idx_5382" id="%_idx_5382"/>(define (add-rule-or-assertion! assertion)<br/>
(if (rule? assertion)<br/>
(add-rule! assertion)<br/>
(add-assertion! assertion)))<br/>
(define (add-assertion! assertion)<br/>
(store-assertion-in-index assertion)<br/>
(let ((old-assertions THE-ASSERTIONS))<br/>
(set! THE-ASSERTIONS<br/>
(cons-stream assertion old-assertions))<br/>
'ok))<br/>
(define (add-rule! rule)<br/>
(store-rule-in-index rule)<br/>
(let ((old-rules THE-RULES))<br/>
(set! THE-RULES (cons-stream rule old-rules))<br/>
'ok))<br/></tt></p><p/><p/><p>Para realmente armazenar uma asserção ou uma regra, verificamos se ela pode ser indexada. Nesse caso, armazenamos no fluxo apropriado.</p><p>
</p><p/><p><tt>(define (store-assertion-in-index assertion)<br/>
(if (indexable? assertion)<br/>
(let ((key (index-key-of assertion)))<br/>
(let ((current-assertion-stream<br/>
(get-stream key 'assertion-stream)))<br/>
(put key<br/>
'assertion-stream<br/>
(cons-stream assertion<br/>
current-assertion-stream))))))<br/>
(define (store-rule-in-index rule)<br/>
(let ((pattern (conclusion rule)))<br/>
(if (indexable? pattern)<br/>
(let ((key (index-key-of pattern)))<br/>
(let ((current-rule-stream<br/>
(get-stream key 'rule-stream)))<br/>
(put key<br/>
'rule-stream<br/>
(cons-stream rule<br/>
current-rule-stream)))))))<br/></tt></p><p/><p/><p>Os procedimentos a seguir definem como o índice do banco de dados é usado. Um padrão (uma asserção ou uma conclusão de regra) será armazenado na tabela se começar com uma variável ou um símbolo constante.</p><p>
</p><p/><p><tt>(define (indexable? pat)<br/>
(or (constant-symbol? (car pat))<br/>
(var? (car pat))))<br/></tt></p><p/><p>A chave sob a qual um padrão é armazenado na tabela é <tt>?</tt> (se começar com uma variável) ou o símbolo constante com o qual começa.</p><p>
</p><p/><p><tt>(define (index-key-of pat)<br/>
(let ((key (car pat)))<br/>
(if (var? key) '? key)))<br/></tt></p><p/><p>O índice será usado para recuperar itens que podem corresponder a um padrão se o padrão começar com um símbolo constante.</p><p>
</p><p/><p><tt>(define (use-index? pat)<br/>
(constant-symbol? (car pat)))<br/></tt></p><p/><p/><p>
</p><p><a name="%_thm_4.70" id="%_thm_4.70"/>
<b>Exercício 4.70.</b> Qual é o objetivo do <tt>let</tt> ligações nos procedimentos <tt>add-assertion!</tt> e <tt>add-rule!</tt> ? O que haveria de errado com a seguinte implementação do <tt>add-assertion!</tt> ? Dica: lembre-se da definição do fluxo infinito de ones na seção <a href="book-Z-H-24.html#%_sec_3.5.2">3.5.2</a>: <tt>(define ones (cons-stream 1 ones))</tt>.</p><p>
</p><p/><p><tt>(define (add-assertion! assertion)<br/>
(store-assertion-in-index assertion)<br/>
(set! THE-ASSERTIONS<br/>
(cons-stream assertion THE-ASSERTIONS))<br/>
'ok)<br/></tt></p><p/><p>
</p><p>
<a name="%_sec_4.4.4.6" id="%_sec_4.4.4.6"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4.6">4.4.4.6 Operações de fluxo</a></h4><p>
<a name="%_idx_5384" id="%_idx_5384"/>O sistema de consulta usa algumas operações de fluxo que não foram apresentadas no capítulo 3.</p><p>
<tt>Stream-append-delayed</tt> e <tt>interleave-delayed</tt> são como <tt>stream-append</tt> e <tt>interleave</tt> (seção <a href="book-Z-H-24.html#%_sec_3.5.3">3.5.3</a>), exceto que eles aceitam um argumento atrasado (como o procedimento <tt>integral</tt> na seção <a href="book-Z-H-24.html#%_sec_3.5.4">3.5.4</a>) Isso adia o laço em alguns casos (consulte o exercício <a href="#%_thm_4.71">4.71</a>)</p><p>
</p><p/><p><tt><a name="%_idx_5386" id="%_idx_5386"/>(define (stream-append-delayed s1 delayed-s2)<br/>
(if (stream-null? s1)<br/>
(force delayed-s2)<br/>
(cons-stream<br/>
(stream-car s1)<br/>
(stream-append-delayed (stream-cdr s1) delayed-s2))))<br/><a name="%_idx_5388" id="%_idx_5388"/>(define (interleave-delayed s1 delayed-s2)<br/>
(if (stream-null? s1)<br/>
(force delayed-s2)<br/>
(cons-stream<br/>
(stream-car s1)<br/>
(interleave-delayed (force delayed-s2)<br/>
(delay (stream-cdr s1))))))<br/></tt></p><p/><p/><p>
<tt>Stream-flatmap</tt>, que é usado em todo o avaliador de consultas para mapear um procedimento em um fluxo de quadros e combinar os fluxos resultantes de quadros, é o fluxo analógico do procedimento <tt>flatmap</tt> introduzido para listas comuns na seção <a href="book-Z-H-15.html#%_sec_2.2.3">2.2.3</a>. Ao contrário do comum <tt>flatmap</tt> no entanto, acumulamos os fluxos com um processo de intercalação, em vez de simplesmente anexá-los (consulte os exercícios <a href="#%_thm_4.72">4.72</a> e <a href="#%_thm_4.73">4.73</a>)</p><p>
</p><p/><p><tt><a name="%_idx_5390" id="%_idx_5390"/>(define (stream-flatmap proc s)<br/>
(flatten-stream (stream-map proc s)))<br/><a name="%_idx_5392" id="%_idx_5392"/>(define (flatten-stream stream)<br/>
(if (stream-null? stream)<br/>
the-empty-stream<br/>
(interleave-delayed<br/>
(stream-car stream)<br/>
(delay (flatten-stream (stream-cdr stream))))))<br/></tt></p><p/><p/><p>O avaliador também usa o seguinte procedimento simples para gerar um fluxo que consiste em um único elemento:</p><p>
</p><p/><p><tt><a name="%_idx_5394" id="%_idx_5394"/>(define (singleton-stream x)<br/>
(cons-stream x the-empty-stream))<br/></tt></p><p/><p>
<a name="%_sec_4.4.4.7" id="%_sec_4.4.4.7"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4.7">4.4.4.7 Procedimentos de sintaxe de consulta</a></h4><p>
<a name="%_idx_5396" id="%_idx_5396"/>
<tt>Type</tt> e <tt>contents</tt>, usado por <tt>qeval</tt> (seção <a href="#%_sec_4.4.4.2">4.4.4.2</a>), especifique que um formulário especial seja identificado pelo símbolo em sua <tt>car</tt>. Eles são os mesmos que os procedimentos <tt>type-tag</tt> e <tt>contents</tt> na seção <a href="book-Z-H-17.html#%_sec_2.4.2">2.4.2</a>, exceto pela mensagem de erro.</p><p>
</p><p/><p><tt>(define (type exp)<br/>
(if (pair? exp)<br/>
(car exp)<br/>
(error "Unknown expression TYPE" exp)))<br/>
(define (contents exp)<br/>
(if (pair? exp)<br/>
(cdr exp)<br/>
(error "Unknown expression CONTENTS" exp)))<br/></tt></p><p/><p/><p>Os procedimentos a seguir, usados pelo <tt>query-driver-loop</tt> (na seção <a href="#%_sec_4.4.4.1">4.4.4.1</a>), especifique que regras e asserções sejam adicionadas ao banco de dados por expressões do formulário <tt>(afirmar! <<em>rule-or-assertion</em>>):</tt></p><p>
</p><p/><p><tt>(define (assertion-to-be-added? exp)<br/>
(eq? (type exp) 'assert!))<br/>
(define (add-assertion-body exp)<br/>
(car (contents exp)))<br/></tt></p><p/><p/><p>Aqui estão as definições de sintaxe para o <tt>and</tt>, <tt>or</tt>, <tt>not</tt> e <tt>lisp-value</tt> formulários especiais (seção <a href="#%_sec_4.4.4.2">4.4.4.2</a>):</p><p>
</p><p/><p><tt>(define (empty-conjunction? exps) (null? exps))<br/>
(define (first-conjunct exps) (car exps))<br/>
(define (rest-conjuncts exps) (cdr exps))<br/>
(define (empty-disjunction? exps) (null? exps))<br/>
(define (first-disjunct exps) (car exps))<br/>
(define (rest-disjuncts exps) (cdr exps))<br/>
(define (negated-query exps) (car exps))<br/>
(define (predicate exps) (car exps))<br/>
(define (args exps) (cdr exps))<br/></tt></p><p/><p/><p>Os três procedimentos a seguir definem a sintaxe das regras:</p><p>
</p><p/><p><tt>(define (rule? statement)<br/>
(tagged-list? statement 'rule))<br/>
(define (conclusion rule) (cadr rule))<br/>
(define (rule-body rule)<br/>
(if (null? (cddr rule))<br/>
'(always-true)<br/>
(caddr rule)))<br/></tt></p><p/><p/><p>
<a name="%_idx_5398" id="%_idx_5398"/><a name="%_idx_5400" id="%_idx_5400"/><tt>Query-driver-loop</tt> (seção <a href="#%_sec_4.4.4.1">4.4.4.1</a>) chamadas <tt>query-syntax-process</tt> transformar variáveis padrão na expressão, que possuem a forma <tt>?symbol</tt>, no formato interno <tt>(? symbol)</tt>. Ou seja, um padrão como <tt>(job ?x ?y)</tt> é representado internamente pelo sistema como <tt>(job (? x) (? y))</tt>. Isso aumenta a eficiência do processamento da consulta, pois significa que o sistema pode verificar se uma expressão é uma variável padrão, verificando se o <tt>car</tt> da expressão é o símbolo <tt>?</tt>, em vez de precisar extrair caracteres do símbolo. A transformação da sintaxe é realizada pelo seguinte procedimento:<a name="call_footnote_Temp_702" href="#footnote_Temp_702" id="call_footnote_Temp_702"><sup><small>81</small></sup></a></p><p>
</p><p/><p><tt>(define (query-syntax-process exp)<br/>
(map-over-symbols expand-question-mark exp))<br/><a name="%_idx_5412" id="%_idx_5412"/>(define (map-over-symbols proc exp)<br/>
(cond ((pair? exp)<br/>
(cons (map-over-symbols proc (car exp))<br/>
(map-over-symbols proc (cdr exp))))<br/>
((symbol? exp) (proc exp))<br/>
(else exp)))<br/>
(define (expand-question-mark symbol)<br/>
(let ((chars (symbol->string symbol)))<br/>
(if (string=? (substring chars 0 1) "?")<br/>
(list '?<br/>
(string->symbol<br/>
(substring chars 1 (string-length chars))))<br/>
symbol)))<br/></tt></p><p/><p/><p>Depois que as variáveis são transformadas dessa maneira, as variáveis em um padrão são listas começando com <tt>?</tt>, e os símbolos constantes (que precisam ser reconhecidos para indexação da base de dados, seção <a href="#%_sec_4.4.4.5">4.4.4.5</a>) são apenas os símbolos.</p><p>
</p><p/><p><tt>(define (var? exp)<br/>
(tagged-list? exp '?))<br/>
(define (constant-symbol? exp) (symbol? exp))<br/></tt></p><p/><p/><p>Variáveis exclusivas são construídas durante a aplicação da regra (na seção <a href="#%_sec_4.4.4.4">4.4.4.4</a>) através dos seguintes procedimentos. O identificador exclusivo para uma aplicação de regra é um número, que é incrementado toda vez que uma regra é aplicada.</p><p>
</p><p/><p><tt>(define rule-counter 0)<br/>
(define (new-rule-application-id)<br/>
(set! rule-counter (+ 1 rule-counter))<br/>
rule-counter)<br/>
(define (make-new-variable var rule-application-id)<br/>
(cons '? (cons rule-application-id (cdr var))))<br/></tt></p><p/><p/><p>Quando <tt>query-driver-loop</tt> instancia a consulta para imprimir a resposta, converte todas as variáveis de padrão não encadernadas de volta ao formato correto para impressão, usando</p><p>
</p><p/><p><tt>(define (contract-question-mark variable)<br/>
(string->symbol<br/>
(string-append "?" <br/>
(if (number? (cadr variable))<br/>
(string-append (symbol->string (caddr variable))<br/>
"-"<br/>
(number->string (cadr variable)))<br/>
(symbol->string (cadr variable))))))<br/></tt></p><p/><p>
<a name="%_sec_4.4.4.8" id="%_sec_4.4.4.8"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_4.4.4.8">4.4.4.8 Quadros e ligações</a></h4><p>
</p><p>
<a name="%_idx_5414" id="%_idx_5414"/><a name="%_idx_5416" id="%_idx_5416"/>Os quadros são representados como listas de ligações, que são pares de valores variáveis:</p><p>
</p><p/><p><tt>(define (make-binding variable value)<br/>
(cons variable value))<br/>
(define (binding-variable binding)<br/>
(car binding))<br/>
(define (binding-value binding)<br/>
(cdr binding))<br/>
(define (binding-in-frame variable frame)<br/>
(assoc variable frame))<br/>
(define (extend variable value frame)<br/>
(cons (make-binding variable value) frame))<br/></tt></p><p/><p>
</p><p><a name="%_thm_4.71" id="%_thm_4.71"/>
<b>Exercício 4.71.</b> Louis Reasoner se pergunta por que os procedimentos <tt>simple-query</tt> e <tt>disjoin</tt> (seção <a href="#%_sec_4.4.4.2">4.4.4.2</a>) são implementados usando explícita operações <tt>delay</tt>, em vez de serem definidas da seguinte maneira:</p><p>
</p><p/><p><tt>(define (simple-query query-pattern frame-stream)<br/>
(stream-flatmap<br/>
(lambda (frame)<br/>
(stream-append (find-assertions query-pattern frame)<br/>
(apply-rules query-pattern frame)))<br/>
frame-stream))<br/>
(define (disjoin disjuncts frame-stream)<br/>
(if (empty-disjunction? disjuncts)<br/>
the-empty-stream<br/>
(interleave<br/>
(qeval (first-disjunct disjuncts) frame-stream)<br/>
(disjoin (rest-disjuncts disjuncts) frame-stream))))<br/></tt></p><p/><p>Você pode dar exemplos de consultas em que essas definições mais simples levariam a um comportamento indesejável?</p><p/><p>
</p><p><a name="%_thm_4.72" id="%_thm_4.72"/>
<b>Exercício 4.72.</b> Por que <tt>disjoin</tt> e <tt>stream-flatmap</tt> intercalar os fluxos em vez de simplesmente anexá-los? Dê exemplos que ilustram por que a intercalação funciona melhor. (Dica: por que usamos <tt>interleave</tt> na seção <a href="book-Z-H-24.html#%_sec_3.5.3">3.5.3</a>?)</p><p/><p>