-
Notifications
You must be signed in to change notification settings - Fork 9
/
chapter-4.tex
8446 lines (7446 loc) · 530 KB
/
chapter-4.tex
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
\chapter{Метаязыковая абстракция}
\label{METALINGUISTIC-ABSTRACTION}%
%\markboth{Глава 4 \qquad Метаязыковая абстракция}{}
\thispagestyle{empty}
\epigraph{
\ldots Именно в словах кроется магия~--- в таких, как
<<абракадабра>>, <<Сезам, откройся>> и проч.,~--- но магические слова
из одной истории перестают быть таковыми в следующей. Настоящая магия
состоит в том, чтобы понять, когда и для чего слово сработает; трюк в
том, чтобы выучить трюк.
\ldots А слова эти состоят из букв нашего алфавита: пара
дюжин закорючек, которые мы способны черкнуть пером. Вот где ключ\ldots!
И сокровище тоже, если только мы сумеем его заполучить! Как
будто\ldots как будто ключ к сокровищу и {\em есть} само
сокровище!\index{ru}{Барт,~Джон||John Barth||n|}\index{en}{John
Barth||Барт,~Джон||n|}\index{ru}{Лапицкий, Виктор||||n|}}
{Джон Барт. \\ <<Химера>> \\ (Перевод Виктора Лапицкого)}
Исследуя науку проектирования программ, мы видели,
что программисты-эксперты управляют сложностью своих программ при
помощи тех же общих методик, какими пользуются проектировщики всех
сложных систем. Они сочетают элементарные единицы, получая при этом
составные объекты, с помощью абстракции составных объектов формируют
строительные блоки высших порядков, и при этом с целью сохранения
модульности выбирают наиболее удобный общий взгляд на структуру
системы. Демонстрируя эти методы, мы использовали Лисп как язык для
описания процессов и для построения вычислительных объектов данных, и
процессы~--- для моделирования сложных явлений реального мира. Однако по
мере того, как мы сталкиваемся со все более сложными задачами, мы
обнаруживаем, что Лиспа, да и любого заранее заданного языка
программирования, недостаточно для наших нужд. Чтобы эффективнее
выражать свои мысли, постоянно приходится обращаться к новым
языкам. Построение новых языков является мощной стратегией управления
сложностью в инженерном проектировании; часто оказывается, что можно
расширить свои возможности работы над сложной задачей, приняв новый
язык, позволяющий нам описывать (а следовательно, и обдумывать)
задачу новым способом, используя элементы, методы их сочетания и
механизмы абстракции, специально подогнанные под стоящие перед нами
проблемы\footnote{Та же самая идея встречается во всех областях техники.
Например, у инженеров-элек\-т\-рон\-щи\-ков существует множество языков для
описания схем. Два из них~--- это язык электрических
{\em сетей} и язык электрических {\em систем}. Язык
сетей делает акцент на физическом моделировании устройств в терминах
дискретных электрических элементов. Элементарными объектами этого
языка являются элементарные электрические компоненты~--- резисторы,
конденсаторы, катушки индуктивности и транзисторы, задаваемые через
физические переменные: напряжение и ток. Описывая схемы на языке
сетей, инженер озабочен физическими характеристиками своего проекта.
Элементами системного языка, напротив, являются модули обработки
сигнала, например, фильтры и усилители. Существенно только
функциональное поведение модулей, и сигналами манипулируют безотносительно
к тому, в виде какого напряжения или тока они реализуются физически.
Язык систем построен на языке сетей, в том смысле, что элементы систем
обработки сигнала состоят из электрических схем. Однако здесь
инженера интересует крупномасштабная организация электрических
устройств, решающая определенную задачу; их физическая совместимость
подразумевается. Такая послойная организация языков служит еще одним
примером уровневого метода проектирования, проиллюстрированного в
разделе~\ref{EXAMPLE-A-PICTURE-LANGUAGE} на примере языка
описания изображений.}.
Программирование изобилует языками.\index{ru}{машинный язык|vs.
высокоуровневый язык||||} Есть физические
языки, например, языки машинных кодов для конкретных компьютеров.
Основным вопросом для них является представление данных и управления
через отдельные биты памяти и машинные команды. Пишущий программы на
машинном языке озабочен тем, чтобы при помощи данной аппаратуры
создать системы и инструменты для эффективной реализации вычисления
при ограниченных ресурсах. \index{ru}{высокоуровневый язык vs. машинный язык|||||}Языки высокого уровня, возводимые поверх
машинных, скрывают вопросы конкретной реализации данных в виде набора
битов и представления программ как последовательности машинных
команд. В этих языках присутствуют средства комбинации и
абстракции, например определения функций, которые подходят для более
крупномасштабной организации систем.
\index{ru}{метаязыковая абстракция||metalinguistic
abstraction|||}\index{en}{metalinguistic abstraction||метаязыковая
абстракция|||}{\em Метаязыковая абстракция} (metalinguistic abstraction),
то есть построение новых языков, играет важную роль во всех отраслях
инженерного проектирования.\index{ru}{абстракция|метаязыковая||||}
Для компьютерного программирования она
особенно важна, поскольку в программировании мы можем не только
формулировать новые языки, но и реализовывать их через построение
вычислителей. \index{ru}{вычислитель||evaluator|||}\index{en}{evaluator||вычислитель|||}{\em Вычислитель} (evaluator) (или
\index{ru}{интерпретатор||interpreter|||}\index{en}{interpreter||интерпретатор|||}{\em интерпретатор} (interpreter)) для языка
программирования~--- это процедура, которая, будучи примененной к
выражению языка, производит действия, необходимые для вычисления этого
выражения.
Без преувеличения можно сказать, что самая основополагающая
идея в программировании такова:
\begin{quote}
Вычислитель, который определяет значение выражений в
языке программирования~--- всего лишь обычная программа.
\end{quote}
С этой мыслью приходит и новое представление о себе самих:
мы начинаем видеть в себе разработчиков языков, а не
просто пользователей языков, придуманных другими.
На самом деле, почти любую программу можно рассматривать как
вычислитель для какого-то языка. Например, система работы с
многочленами из раздела~\ref{EXAMPLE-SYMBOLIC-ALGEBRA}
заключает в себе правила арифметики многочленов и реализует их в
терминах операций над данными в списочной форме. Если мы дополним
эту
систему процедурами для чтения и печати многочленов, то перед нами
окажется ядро специализированного языка для решения задач
символьной математики. И программа моделирования цифровой логики из
раздела~\ref{A-SIMULATOR-FOR-DIGITAL-CIRCUITS}, и программа
распространения ограничений из
раздела~\ref{PROPAGATION-OF-CONSTRAINTS} содержат свои
собственные языки, со своими примитивами, средствами их комбинирования
и абстракции. С этой точки зрения, техника работы с
крупномасштабными компьютерными системами сливается с техникой
создания новых компьютерных языков, и вся
\index{ru}{информатика||computer science|||}\index{en}{computer
science||информатика|||}информатика~--- не более (но и не менее), чем
наука о построении подходящих языков описания.
Сейчас мы начинаем обзор методов, которые позволяют создавать
одни языки на основе других. В этой главе в качестве основы мы будем
использовать Лисп, \index{ru}{Lisp (Лисп)|удобство для написания
вычислителей||||}и вычислители будем реализовывать как процедуры
на Лиспе. Лисп особенно хорошо подходит для этой задачи благодаря
своей способности представлять символические выражения и обрабатывать
их. Первый шаг к пониманию того, как реализуются языки, мы сделаем,
построив вычислитель для самого Лиспа. Язык, реализуемый нашим
интерпретатором, будет подмножеством диалекта Лиспа Scheme, которым мы
пользуемся в этой книге. Несмотря на то, что интерпретатор, описанный в
этой главе, написан для конкретного диалекта Лиспа, он содержит
основную структуру вычислителя для любого языка, ориентированного на
выражения и предназначенного для написания программ для
последовательной машины. (На самом деле, глубоко внутри большинства
языковых процессоров содержится маленький интерпретатор <<Лиспа>>.) Этот
интерпретатор несколько упрощен для удобства и наглядности обсуждения, и
некоторые детали, которые важно было бы включить в Лисп-систему
промышленного качества, здесь были оставлены за рамками изложения. Тем не
менее, этот простой интерпретатор способен выполнить большинство программ
из данной книги.\footnote{Самое важное, чего не хватает в нашем
интерпретаторе,~---
это механизмов, обрабатывающих ошибки и поддерживающих отладку. Более
подробное обсуждение вычислителей можно найти в книге
Friedman, Wand, and Haynes 1992, которая содержит обзор\index{ru}{Фридман,
Дэниел~П.||Daniel~P. Friedman||n|п}\index{en}{Daniel~P. Friedman||Фридман,
Дэниел~П.||n|п}\index{ru}{Хейнс, Кристофер~Т.||Christopher~T.
Haynes||n|п}\index{en}{Christopher~T. Haynes||Хейнс,
Кристофер~Т.||n|п}\index{ru}{Ванд, Митчелл||Mitchell
Wand||n|п}\index{en}{Mitchell Wand||Ванд, Митчелл||n|п}
языков программирования на примере последовательности интерпретаторов,
написанных на Scheme.}
Важное преимущество, которое нам дает вычислитель, доступный в виде
программы на Лиспе, состоит в том, что мы можем реализовывать
альтернативные правила вычисления, описывая их как модификации
программы вычислителя. В частности, мы можем извлечь из этой
способности немалую выгоду, добиваясь более полного контроля над тем, как
в вычислительных моделях реализуется понятие времени. Этому вопросу была
специально посвящена глава~\ref{MODULARITY-OBJECTS-AND-STATE}. Там мы смягчили
некоторые сложности работы с состоянием и присваиваниями, при помощи
потоков отделив представление времени во внешнем мире от времени
внутри компьютера. Однако программы, работающие с потоками, иногда
бывали излишне громоздки, поскольку их ограничивал аппликативный порядок
вычисления, принятый в Scheme. В
разделе~\ref{VARIATIONS-ON-A-SCHEME-LAZY-EVALUATION} мы изменим
язык и получим более изящный подход в виде интерпретатора с
\index{ru}{нормальный порядок вычислений||normal-order
evaluation|||}\index{en}{normal-order evaluation||нормальный порядок
вычислений|||}{\em нормальным порядком вычисления} (normal-order
evaluation).
В разделе~\ref{VARIATIONS-ON-A-SCHEME-NONDETERMINISTIC-COMPUTING}
язык меняется более радикально, и выражения получают
не одно единственное значение, а множество. В этом языке
\index{ru}{недетерминистские вычисления||non\-de\-ter\-mi\-nis\-tic
computing|||}\index{en}{nondeterministic computing||недетерминистские
вычисления|||}{\em недетерминистских
вычислений} (nondeterministic computing) становится естественным порождать
все возможные значения выражения, а затем искать среди них те, которые
удовлетворяют определенным ограничениям. Если описывать это в терминах
вычисления и времени, то время как будто
разветвляется на множество <<возможных будущих>>, и мы ищем среди них
подходящие временные линии. При работе с недетерминистским интерпретатором
отслеживание множества значений и поиск осуществляются автоматически
встроенными механизмами языка.
В разделе~\ref{LOGIC-PROGRAMMING} мы реализуем язык
\index{ru}{логическое программирование||logic
programming|||}\index{en}{logic programming||логическое
программирование|||}{\em логического
программирования} (logic programming), в котором знание выражается в терминах
отношений, а не в терминах вычислений со входами и выходами. Несмотря
на то, что язык при этом оказывается сильно отличным от Лиспа, как,
впрочем, и от любого привычного языка, мы увидим, что интерпретатор
для языка логического программирования имеет, в сущности, ту же
структуру, что и интерпретатор Лиспа.
\section{Метациклический интерпретатор}
\label{THE-METACIRCULAR-EVALUATOR}%
\index{ru}{метациклический интерпретатор для Scheme|||||}Наш интерпретатор
Лиспа будет реализован как программа на
Лиспе. Может показаться, что размышления о выполнении Лисп-программ
при помощи интерпретатора, который сам написан на Лиспе, составляют
порочный круг. Однако вычисление есть процесс, так что вполне
логично описывать процесс вычисления с помощью Лиспа~--- в конце
концов, это наш инструмент для описания процессов\footnote{Даже с учетом
этого, остаются важные стороны процесса
вычисления, которые в нашем интерпретаторе не проясняются. Самая
важная из них~--- точные механизмы того, как одни процедуры вызывают
другие и возвращают значения процедурам, которые их вызвали. Эти
вопросы мы рассмотрим в
главе~\ref{COMPUTING-WITH-REGISTER-MACHINES}, где мы
исследуем процесс вычисления более внимательно, реализуя
вычислитель как простую регистровую машину.}.
Интерпретатор, написанный на языке, который он сам реализует,
называется
\index{ru}{вычислитель|метациклический||||}\index{ru}{метациклический
интерпретатор для Scheme||metacircular evaluator for
Scheme|||}\index{en}{metacircular evaluator for Scheme||метациклический
интерпретатор для Scheme|||}{\em метациклическим} (metacircular).
\index{ru}{модель вычисления с окружениями|и метациклический
интерпретатор||||} В сущности,
метациклический интерпретатор является
\index{ru}{метациклический интерпретатор для Scheme|модель вычислений с
окружениями||||}формулировкой на языке Scheme модели вычислений
с окружениями, описанной в
разделе~\ref{THE-ENVIRONMENT-MODEL-OF-EVALUATION}. Напомним, что в этой
модели было две основные части:
\begin{plainlist}
\item
Чтобы выполнить комбинацию (составное выражение, не
являющееся особой формой), нужно вычислить его подвыражения и затем
применить значение подвыражения-оператора к значениям
подвыражений-операндов.
\item
Чтобы применить составную процедуру к набору
аргументов, нужно выполнить тело процедуры в новом окружении. Для
того, чтобы построить это окружение, нужно расширить окружение
объекта-процедуры кадром, в котором формальные параметры процедуры
связаны с аргументами, к которым процедура применяется.
\end{plainlist}
Эти два правила описывают сущность процесса вычисления,
основной цикл, в котором выражения, которые требуется выполнить в
окружении, сводятся к процедурам, которые нужно применить к
аргументам, а те, в свою очередь, сводятся к новым выражениям,
которые нужно выполнить в новых окружениях, и так далее, пока мы не
доберемся до символов, чьи значения достаточно найти в окружении,
и элементарных процедур, которые применяются напрямую
(см.~рис.~\ref{P4.1})\footnote{Если нам
дается возможность применять примитивы, то что
остается сделать для реализации интерпретатора?
\index{ru}{метациклический интерпретатор для Scheme|задача||||п}Задача
интерпретатора состоит не в том, чтобы определить примитивы языка, а в
том, чтобы обеспечить связующие элементы~--- средства комбинирования и
абстракции,~--- которые превращают набор примитивов в язык. А
именно:
\begin{plainlist}
\item
Интерпретатор позволяет работать с вложенными
выражениями. Например, чтобы вычислить значение выражения
{\tt (+ 1 6)}, достаточно применения примитивов, но этого
недостаточно для работы с выражением {\tt (+ 1 (* 2 3))}. Сама
по себе элементарная процедура {\tt +} способна работать только
с числами, и если передать ей аргумент~--- выражение {\tt (* 2
3)}, она сломается. Одна из важных задач интерпретатора
--- устроить вычисление так, чтобы
{\tt (* 2 3)} свелось к значению 6, прежде чем оно будет
передано {\tt +} как аргумент.
\item
Интерпретатор позволяет использовать
переменные. Например, элементарная процедура сложения не знает, как
работать с выражениями вроде {\tt (+ x 1)}. Нам нужен
интерпретатор, чтобы следить за переменными и получать их значения,
прежде чем запускать элементарные процедуры.
\item
Интерпретатор позволяет определять составные
процедуры. При этом нужно хранить определения процедур, знать, как
эти определения используются при вычислении выражений, и обеспечивать
механизм, который позволяет процедурам принимать аргументы.
\item
Интерпретатор дает особые формы, вычисляющиеся
иначе, чем вызовы процедур.
\end{plainlist}%
}.
Этот цикл вычисления будет построен в виде взаимодействия двух
основных процедур интерпретатора, {\tt eval} и
{\tt apply}, описанных в
разделе~\ref{THE-CORE-OF-THE-EVALUATOR}
(см.~рис.~\ref{P4.1}).
Реализация интерпретатора будет зависеть от процедур,
определяющих
\index{ru}{синтаксис||syntax|||}\index{en}{syntax||синтаксис|||}{\em
синтаксис} (syntax) выполняемых выражений.
\index{ru}{метациклический интерпретатор для Scheme|абстракция
данных||||}При помощи абстракции данных мы сделаем интерпретатор
независимым от представления языка. К примеру, вместо того, чтобы
окончательно решать, что присваивание выражается в виде списка, в
котором первым элементом стоит символ {\tt set!}, мы пользуемся
абстрактным предикатом {\tt assignment?}, чтобы распознавать
присваивание, и абстрактными селекторами
{\tt assignment-variable} и {\tt assignment-value},
чтобы обращаться к его частям. Реализация выражений будет подробно
рассмотрена в разделе~\ref{REPRESENTING-EXPRESSIONS}.
Имеются также операции, описанные в
разделе~\ref{EVALUATOR-DATA-STRUCTURES}, которые определяют
представление процедур и окружений. Например,
{\tt make-proce\-dure} порождает составные процедуры, %HERE315
{\tt lookup-variable-value} извлекает значения переменных, а
{\tt apply-primitive-procedure} применяет элементарную
процедуру к указанному списку аргументов.
\begin{cntrfig}
\input{xfig-mod/4-1.eepic}
%{\small процедура, аргументы\\
%выражение, окружение}
\caption{\index{ru}{метациклический интерпретатор для Scheme|цикл \texttt{eval}--\texttt{apply}||||}
Цикл {\tt eval}--{\tt apply}
раскрывает сущность компьютерного языка.}
\label{P4.1}%
\end{cntrfig}
\subsection{Ядро интерпретатора}
\label{THE-CORE-OF-THE-EVALUATOR}%
Процесс вычисления можно описать как взаимодействие двух
процедур: \index{ru}{метациклический интерпретатор для
Scheme|\texttt{eval} и \texttt{apply}||||}{\tt eval} и {\tt apply}.
\paragraph{Eval}
Процедура {\tt eval}\index{ru}{eval (метациклическая)||||p|}
в качестве аргументов принимает
выражение и окружение. Она относит выражение к одному из возможных
классов и управляет его выполнением. {\tt Eval} построена как
разбор случаев в зависимости от синтаксического
типа выполняемого выражения. Для того, чтобы процедура была
достаточно общей, определение типа выражения мы формулируем абстрактно,
не связывая себя никакой конкретной
\index{ru}{метациклический интерпретатор для Scheme|представление
выражений||||}реализацией различных типов выражений. Для каждого типа
выражений имеется предикат, который
распознает этот тип, и абстрактные
\index{ru}{метациклический интерпретатор для Scheme|абстракция
данных||||}средства для выбора его частей. Такой
\index{ru}{абстрактный синтаксис|в метациклическом интерпретаторе|abstract
syntax|||}\index{en}{abstract syntax||абстрактный синтаксис|в
метациклическом интерпретаторе||}{\em абстрактный синтаксис} (abstract syntax)
позволяет легко видеть, как можно изменить синтаксис языка и
использовать тот же самый интерпретатор, но только с другим набором
синтаксических процедур.
\medskip
{\em Элементарные выражения}
\begin{plainlist}
\item
\index{ru}{выражение|самовычисляющееся||||}\index{ru}{самовычисляющееся
выражение||self-evaluating expression|||}\index{en}{self-evaluating
expression||самовычисляющееся выражение|||}Для самовычисляющихся
выражений, например, чисел, {\tt eval} возвращает само выражение.
\item
{\tt Eval} должен находить значения переменных, просматривая окружение.
\end{plainlist}
\medskip
{\em Особые формы}
\begin{plainlist}
\item
Для выражений с кавычкой ({\tt quote}),
{\tt eval} возвращает само закавыченное выражение.
\item
Присваивание переменной (или ее определение) должно
вызвать {\tt eval} рекурсивно, чтобы вычислить новое значение,
которое требуется связать с переменной. Окружение нужно
модифицировать, изменяя (или создавая) связывание для
переменной.
\item
Выражение {\tt if} требует специальной
обработки своих частей: если предикат истинен, нужно выполнить
следствие; если нет, альтернативу.
\item
Выражение {\tt lambda} требуется
преобразовать в процедуру, пригодную к применению. Для этого нужно
упаковать параметры и тело {\tt lambda}-выраже\-ния вместе
с окружением, в котором оно вычисляется.
\item
Выражение {\tt begin} требует выполнения
своих подвыражений в том порядке, как они появляются.
\item
Разбор случаев ({\tt cond}) преобразуется во вложенные
выражения {\tt if} и затем вычисляется.
\end{plainlist}
\medskip
{\em Комбинации}
\begin{plainlist}
\item
Для применения процедуры {\tt eval} должна
рекурсивно вычислить операцию и операнды комбинации. Получившиеся
процедура и аргументы передаются {\tt apply}, которая распоряжается
собственно применением процедуры.
\end{plainlist}
Вот определение {\tt eval}:
\begin{Verbatim}[fontsize=\small]
(define (eval exp env)\index{ru}{eval (метациклическая)||||pd|}
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((begin? exp)
(eval-sequence (begin-actions exp) env))
((cond? exp) (eval (cond->if exp) env))
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Неизвестный тип выражения -- EVAL" exp))))
\end{Verbatim}
Ясности ради, {\tt eval} реализована как
\index{ru}{разбор случаев|vs. стиль, управляемый
данными||||}\index{ru}{программирование, управляемое данными|vs. разбор
случаев||||}перебор альтернатив через {\tt cond}. Недостаток этой
реализации~--- наша
процедура обрабатывает только несколько указанных типов выражений, и,
не меняя определение {\tt eval}, новые типы добавить нельзя. В
большинстве реализаций Лиспа распределение выражений по типам сделано
в стиле, управляемом данными. Это дает пользователю возможность добавлять
новые типы выражений, которые {\tt eval} будет способен
распознать, не меняя само определение {\tt eval}.
(См.~упражнение~\ref{EX4.3}.)
\paragraph{Apply}
Процедура {\tt apply} принимает два аргумента:
процедуру и список аргументов, к которым ее надо
применить. {\tt Apply} делит процедуры на два класса: для
применения примитивов она зовет {\tt
apply-primitive-procedure};\index{ru}{apply-primitive-procedure||||p|}
составные процедуры она
применяет, по очереди вычисляя выражения, составляющие тело
процедуры. Окружение, в котором вычисляется тело составной процедуры,
получается из базового окружения, хранящегося в
процедуре, добалением кадра, где параметры процедуры связываются с
аргументами, к которым процедура применяется. Вот определение
{\tt apply}:
\begin{Verbatim}[fontsize=\small]
(define (apply procedure arguments)\index{ru}{apply (метациклическая)||||pd|}
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error
"Неизвестный тип процедуры -- APPLY" procedure))))
\end{Verbatim}
\paragraph{Аргументы процедур}
Обрабатывая применение процедуры, {\tt eval}
получает список аргументов, к которым процедуру надо
применить, при помощи {\tt list-of-values}. Процедура
{\tt list-of-values} в качестве аргумента берет список
операндов комбинации. Она вычисляет каждый аргумент и возвращает
список соответствующих значений\footnote{Ветку {\tt application?} в {\tt eval}
можно было бы упростить, используя {\tt map} (и постановив, что
{\tt operands} возвращает список) вместо того, чтобы писать
явным образом процедуру {\tt list-of-values}. Мы решили не
использовать здесь {\tt map}, чтобы подчеркнуть, что\index{ru}{процедура
высшего порядка|в метациклическом
интерпретаторе||||п}\index{ru}{метациклический интерпретатор для
Scheme|процедура высшего порядка||||п}
интерпретатор можно написать без обращения к процедурам высших
порядков (а следовательно, его можно написать на языке, в котором нет
таких процедур), притом, что язык, поддерживаемый интерпретатором, содержит
процедуры высших порядков.}.
\begin{Verbatim}[fontsize=\small]
(define (list-of-values exps env)\index{ru}{list-of-values||||pd|}
(if (no-operands? exps)
'()
(cons (eval (first-operand exps) env)
(list-of-values (rest-operands exps) env))))
\end{Verbatim}
\paragraph{Условные выражения}
Процедура {\tt eval-if} вычисляет предикатную
часть выражения {\tt if} в данном окружении. Если результат
истинен, {\tt eval-if} выполняет следствие, если нет, ---
альтернативу:
\begin{Verbatim}[fontsize=\small]
(define (eval-if exp env)\index{ru}{eval-if (метациклическая)||||pd|}
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))
\end{Verbatim}
Использование {\tt true?} в {\tt eval-if}
подчеркивает вопрос о связи между
\index{ru}{метациклический интерпретатор для Scheme|реализуемый язык vs.
язык реализации||||}реализуемым языком и языком
реализации. Выражение {\tt if-predicate} выполняется в
реализуемом языке, и, следовательно, результат его является значением
этого языка. Предикат интерпретатора {\tt true?} переводит это
значение в значение, которое может быть проверено выражением
{\tt if} в языке реализации: метациклическое представление
истины может не совпадать с ее представлением в нижележащей Scheme\footnote{В
нашем случае, язык реализации и реализуемый язык
совпадают. Размышления о значении {\tt true?} расширяют наше сознание
безотносительно к материальной сущности истины.\index{ru}{самосознание,
повышение уровня||expansion of consciousness|||п}\index{en}{expansion of
consciousness||самосознание, повышение уровня|||п}}.
\paragraph{Последовательности}
Процедура {\tt eval-sequence} вызывается из
{\tt apply} для выполнения последовательности выражений в теле
процедуры, а также из {\tt eval} для обработки
последовательности выражений в выражении {\tt begin}. Она
принимает в виде аргументов последовательность выражений и окружение,
и выполняет выражения в том порядке, в котором они ей даны.
Возвращаемое значение совпадает со значением последнего выражения.
\begin{Verbatim}[fontsize=\small]
(define (eval-sequence exps env)\index{ru}{eval-sequence||||pd|}
(cond ((last-exp? exps) (eval (first-exp exps) env))
(else (eval (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))
\end{Verbatim}
\paragraph{Присваивания и определения}
Следующая процедура обрабатывает присваивание
переменным. При помощи {\tt eval} она находит значение,
которое требуется присвоить, и передает переменную и получившееся
значение в процедуру {\tt set-variable-value!} для включения в
текущее окружение.
\begin{Verbatim}[fontsize=\small]
(define (eval-assignment exp env)\index{ru}{eval-assignment||||pd|}
(set-variable-value! (assignment-variable exp)
(eval (assignment-value exp) env)
env)
'ok)
\end{Verbatim}
Определения переменных обрабатываются сходным образом\footnote{Эта
реализация {\tt define} не учитывает один
тонкий вопрос в обработке внутренних определений, хотя в большинстве
случаев работает правильно. В чем состоит проблема и как ее
решить, мы увидим в разделе~\ref{INTERNAL-DEFINITIONS-CH4}.}:
\begin{Verbatim}[fontsize=\small]
(define (eval-definition exp env)\index{ru}{eval-definition||||pd|}
(define-variable! (definition-variable exp)
(eval (definition-value exp) env)
env)
'ok)
\end{Verbatim}
В качестве возвращаемого значения для присваивания или определения мы
выбрали символ {\tt ok}\footnote{Как мы упоминали при введении {\tt define} и
{\tt set!}, их значения в Scheme зависят от реализации~--- то
есть автор реализации имеет право выбрать такое значение, какое он хочет.}.
\begin{exercise}{4.1}\label{EX4.1}%
\index{ru}{метациклический интерпретатор для Scheme|порядок вычисления операндов||||(упр.~4.1)}%
\index{ru}{порядок вычисления|в метациклическом интерпретаторе||||(упр.~4.1)}%
Заметим, что мы не можем сказать, вычисляет ли
метациклический интерпретатор операнды слева направо или справа
налево. Порядок вычисления наследуется от нижележащего Лиспа: если аргументы
{\tt cons} в процедуре {\tt list-of-values} вычисляются
слева направо, то и операнды в {\tt list-of-values} будут
вычисляться слева направо. Если же вычисление аргументов {\tt cons}
происходит справа налево, то и {\tt list-of-values} будет
вычислять операнды справа налево.
Напишите версию {\tt list-of-values}, которая
вычисляет операнды слева направо, вне зависимости от порядка
вычислений в нижележащем Лиспе. Напишите также версию, которая
вычисляет операнды справа налево.
\end{exercise}
\subsection{Представление выражений}
\label{REPRESENTING-EXPRESSIONS}%
\index{ru}{метациклический интерпретатор для Scheme|синтаксис
интерпретируемого языка||||}\index{ru}{метациклический интерпретатор для
Scheme|представление выражений||||}Интерпретатор напоминает программу
\index{ru}{метациклический интерпретатор для Scheme|и символьное
дифференцирование||||}символьного дифференцирования, описанную в
разделе~\ref{EXAMPLE-SYMBOLIC-DIFFERENTIATION}. Обе программы
работают с символьными выражениями. В обеих результат
работы с составным выражением определяется рекурсивной обработкой
частей выражения и сочетанием частичных результатов, причем способ
сочетания зависит от типа выражения. И там, и там мы
использовали
\index{ru}{абстракция данных|||||}абстракцию данных, чтобы отделить общие
правила работы от
деталей того, как представлены выражения. Для программы
дифференцирования это означало, что одна и та же процедура взятия
производной могла работать с алгебраическими выражениями в префиксной,
инфиксной или какой-либо другой записи. Для интерпретатора это
означает, что синтаксис языка определяется исключительно процедурами,
которые классифицируют выражения и выделяют их части.
Вот описание синтаксиса нашего языка:
\begin{plainlist}
\item
К самовычисляющимся объектам относятся только числа
и строки:
\begin{Verbatim}[fontsize=\small]
(define (self-evaluating? exp) \index{ru}{self-evaluating?||||pd|}
(cond ((number? exp) true)
((string? exp) true)
(else false)))
\end{Verbatim}
\item
Переменные представляются в виде символов:
\begin{Verbatim}[fontsize=\small]
(define (variable? exp) (symbol? exp)) \index{ru}{variable?||||pd|}
\end{Verbatim}
\item
Выражения с кавычкой имеют форму {\tt (quote
\textit{$\langle$закавыченное-вы\-ра\-же\-ние$\rangle$})}:
\begin{Verbatim}[fontsize=\small]
(define (quoted? exp) \index{ru}{quoted?||||pd|}
(tagged-list? exp 'quote))
(define (text-of-quotation exp) (cadr exp)) \index{ru}{text-of-quotation||||pd|}
\end{Verbatim}
{\tt Quoted?} определена посредством процедуры
{\tt tagged-list?}, которая распознает списки, начинающиеся с
указанного символа\footnote{В разделе~\ref{QUOTATION} упоминается,
что интерпретатор рассматривает закавыченное
выражение как список, начинающийся с {\tt quote}, даже если
выражение напечатано через знак кавычки. Например, выражение
{\tt 'a} будет выглядеть для интерпретатора как {\tt (quote
a)}. См.~упражнение~\ref{EX2.55}.}:
\begin{Verbatim}[fontsize=\small]
(define (tagged-list? exp tag) \index{ru}{tagged-list?||||pd|}
(if (pair? exp)
(eq? (car exp) tag)
false))
\end{Verbatim}
\item
Присваивания имеют форму
{\tt (set! \textit{$\langle$переменная$\rangle$} \textit{$\langle$выражение$\rangle$})}:
\begin{Verbatim}[fontsize=\small]
(define (assignment? exp)\index{ru}{assignment?||||pd|}
(tagged-list? exp 'set!))
(define (assignment-variable exp) (cadr exp))\index{ru}{assignment-variable||||pd|}
(define (assignment-value exp) (caddr exp))\index{ru}{assignment-value||||pd|}
\end{Verbatim}
\item
Определения имеют вид
\begin{Verbatim}[fontsize=\small]
(define \textit{$\langle$переменная$\rangle$} \textit{$\langle$значение$\rangle$})
\end{Verbatim}
или
\begin{Verbatim}[fontsize=\small]
(define (\textit{$\langle$переменная$\rangle$} \textit{$\langle$параметр${}_{\mbox{1}}$$\rangle$} ... \textit{$\langle$параметр${}_{\mbox{n}}$$\rangle$})
\textit{$\langle$тело$\rangle$})
\end{Verbatim}
Вторая форма (стандартное определение процедуры) является
\index{ru}{синтаксический сахар|\texttt{define}||||}синтаксическим сахаром
для\index{ru}{define (особая форма)|синтаксический сахар|||p|}
\begin{Verbatim}[fontsize=\small]
(define \textit{$\langle$переменная$\rangle$}
(lambda (\textit{$\langle$параметр${}_{\mbox{1}}$$\rangle$} ... \textit{$\langle$параметр${}_{\mbox{n}}$$\rangle$})
\textit{$\langle$тело$\rangle$}))
\end{Verbatim}
Соответствующие синтаксические процедуры выглядят так:
\begin{Verbatim}[fontsize=\small]
(define (definition? exp)\index{ru}{definition?||||pd|}
(tagged-list? exp 'define))
(define (definition-variable exp)\index{ru}{definition-variable||||pd|}
(if (symbol? (cadr exp))
(cadr exp)
(caadr exp)))
(define (definition-value exp)\index{ru}{definition-value||||pd|}
(if (symbol? (cadr exp))
(caddr exp)
(make-lambda (cdadr exp)
(cddr exp))))
\end{Verbatim}
\item
{\tt Lambda}-выражения являются списками,
которые начинаются с символа {\tt lambda}:
\begin{Verbatim}[fontsize=\small]
(define (lambda? exp) (tagged-list? exp 'lambda))\index{ru}{lambda?||||pd|}
(define (lambda-parameters exp) (cadr exp))\index{ru}{lambda-parameters||||pd|}
(define (lambda-body exp) (cddr exp))\index{ru}{lambda-body||||pd|}
\end{Verbatim}
Мы приводим также конструктор для {\tt lambda}-выражений. Он
используется в вышеприведенной процедуре
{\tt definition-value}:
\begin{Verbatim}[fontsize=\small]
(define (make-lambda parameters body)\index{ru}{make-lambda||||pd|}
(cons 'lambda (cons parameters body)))
\end{Verbatim}
\item
Условные выражения начинаются с {\tt if} и
имеют предикат, следствие и (необязательную) альтернативу. Если в
выражении нет части-альтер\-на\-ти\-вы, мы указываем в ее качестве
{\tt false}\footnote{Значение выражения {\tt if} в случае,
когда предикат ложен, а альтернатива отсутствует, в Scheme не
определено; здесь мы решили сделать его ложным. Мы будем поддерживать
переменные {\tt true} и {\tt false} в выполняемых
выражениях путем связывания их в глобальном окружении.
См.~раздел~\ref{RUNNING-THE-EVALUATOR-AS-A-PROGRAM}.}.
\begin{Verbatim}[fontsize=\small]
(define (if? exp) (tagged-list? exp 'if))\index{ru}{if?||||pd|}
(define (if-predicate exp) (cadr exp))\index{ru}{if-predicate||||pd|}
(define (if-consequent exp) (caddr exp))\index{ru}{if-consequent||||pd|}
(define (if-alternative exp)\index{ru}{if-alternative||||pd|}
(if (not (null? (cdddr exp)))
(cadddr exp)
'false))
\end{Verbatim}
Мы предоставляем также конструктор для {\tt if}-выражений. Его будет
использовать процедура {\tt cond->if} для преобразования
выражений {\tt cond} в выражения {\tt if}:
\begin{Verbatim}[fontsize=\small]
(define (make-if predicate consequent alternative)\index{ru}{make-if||||pd|}
(list 'if predicate consequent alternative))
\end{Verbatim}
\item
{\tt Begin} упаковывает последовательность
выражений в одно выражение. В синтаксические операции над
выражениями {\tt begin} мы включаем извлечение самой
последовательности из выражения {\tt begin}, а также селекторы,
которые возвращают первое выражение и остаток выражений в
последовательности\footnote{Эти селекторы для списка выражений, а также
соответствующие им селекторы для списка операндов, не предназначаются для
абстракции данных. Они введены в качестве мнемонических имен для
основных списковых операций, чтобы легче было понимать вычислитель с
явным управлением из
раздела~\ref{THE-EXPLICIT-CONTROL-EVALUATOR}.}.
\begin{Verbatim}[fontsize=\small]
(define (begin? exp) (tagged-list? exp 'begin))\index{ru}{begin?||||pd|}
(define (begin-actions exp) (cdr exp))\index{ru}{begin-actions||||pd|}
(define (last-exp? seq) (null? (cdr seq)))\index{ru}{list-exp?||||pd|}
(define (first-exp seq) (car seq))\index{ru}{first-exp||||pd|}
(define (rest-exps seq) (cdr seq))\index{ru}{rest-exps||||pd|}
\end{Verbatim}
Кроме того, мы даем конструктор {\tt sequence->exp} (для
использования в процедуре {\tt cond->if}), который преобразует
последовательность в единое выражение, используя, если надо,
{\tt begin}:
\begin{Verbatim}[fontsize=\small]
(define (sequence->exp seq)\index{ru}{sequence->exp||||pd|}
(cond ((null? seq) seq)
((last-exp? seq) (first-exp seq))
(else (make-begin seq))))
(define (make-begin seq) (cons 'begin seq))\index{ru}{make-begin||||pd|}
\end{Verbatim}
\item
Вызов процедуры~--- это любое составное
выражение, не попадающее ни в один из перечисленных типов. Его
{\tt car}~--- это оператор, а {\tt cdr}~--- список операндов:
\begin{Verbatim}[fontsize=\small]
(define (application? exp) (pair? exp))\index{ru}{application?||||pd|}
(define (operator exp) (car exp))\index{ru}{operator||||pd|}
(define (operands exp) (cdr exp))\index{ru}{operands||||pd|}
(define (no-operands? ops) (null? ops))\index{ru}{no-operands?||||pd|}
(define (first-operand ops) (car ops))\index{ru}{first-operand||||pd|}
(define (rest-operands ops) (cdr ops))\index{ru}{rest-operands||||pd|}
\end{Verbatim}
\end{plainlist}
\paragraph{Производные выражения}
\index{ru}{метациклический интерпретатор для Scheme|производные
выражения||||}\index{ru}{метациклический интерпретатор для Scheme|особые
формы как производные выражения||||}\index{ru}{особая форма|как
производное выражение в интерпретаторе||||}Некоторые особые формы языка
можно определить через
выражения, включающие другие особые формы, вместо того, чтобы
задавать их напрямую. Как пример рассмотрим
{\tt cond}, который можно реализовать как гнездо выражений
{\tt if}. Например, задачу вычисления выражения
\begin{Verbatim}[fontsize=\small]
(cond ((> x 0) x)
((= x 0) (display 'zero) 0)
(else (- x)))
\end{Verbatim}
можно свести к задаче вычисления следующего выражения, состоящего из
форм {\tt if} и {\tt begin}:
\begin{Verbatim}[fontsize=\small]
(if (> x 0)
x
(if (= x 0)
(begin (display 'zero)
0)
(- x)))
\end{Verbatim}
Такая реализация обработки {\tt cond} упрощает интерпретатор,
поскольку она уменьшает количество особых форм, для которых требуется
явно описывать процесс вычисления.
Мы включаем в интерпретатор синтаксические процедуры,
которые определяют доступ к частям выражения {\tt cond}, а
также процедуру {\tt cond->if}, которая преобразует выражения
{\tt cond} в выражения {\tt if}. Анализ случаев
начинается с {\tt cond} и состоит из списка ветвей-вариантов вида
предикат-действие. Вариант считается умолчательным, если его предикатом
является символ {\tt else}\footnote{Значение выражения {\tt cond}, когда все
предикаты ложны, а вариант по умолчанию {\tt else}
отсутствует, в языке Scheme не определено; здесь мы решили сделать его
ложным.}.
\begin{Verbatim}[fontsize=\small]
(define (cond? exp) (tagged-list? exp 'cond))\index{ru}{cond?||||pd|}
(define (cond-clauses exp) (cdr exp))\index{ru}{cond-clauses||||pd|}
(define (cond-else-clause? clause)\index{ru}{cond-else-clause?||||pd|}
(eq? (cond-predicate clause) 'else))
(define (cond-predicate clause) (car clause))\index{ru}{cond-predicate||||pd|}
(define (cond-actions clause) (cdr clause))\index{ru}{cond-actions||||pd|}
(define (cond->if exp)\index{ru}{cond->if||||pd|}
(expand-clauses (cond-clauses exp)))
(define (expand-clauses clauses)\index{ru}{expand-clauses||||pd|}
(if (null? clauses)
'false {\em ; нет ветви{\tt else}}
(let ((first (car clauses))
(rest (cdr clauses)))
(if (cond-else-clause? first)
(if (null? rest)
(sequence->exp (cond-actions first))
(error "Ветвь ELSE не последняя -- COND->IF"
clauses))
(make-if (cond-predicate first)
(sequence->exp (cond-actions first))
(expand-clauses rest))))))
\end{Verbatim}
Выражения (вроде {\tt cond}), которые мы желаем
реализовать через синтаксические преобразования, называются
\index{ru}{производные выражения в интерпретаторе||derived
expressions|||}\index{en}{derived expressions||производные выражения в
интерпретаторе|||}{\em производными} (derived expressions). Выражения
{\tt let} также являются производными
(см.~упражнение~\ref{EX4.6})\footnote{Практические
Лисп-системы предоставляют механизм, который
дает пользователю возможность добавлять новые производные выражения и
определять их значения через синтаксические преобразования,
не внося изменений в вычислитель. Такое преобразование, определяемое
пользователем, называется
\index{ru}{макрос||macro|||п}\index{en}{macro||макрос|||п}{\em макрос}
(macro). Добавить простой механизм для определения макросов легко,
однако в получающемся языке возникают сложные проблемы конфликта
имен. Множество исследований посвящено поиску механизмов
определения макросов, в которых такие проблемы не возникают. См.,
например,
Kohlbecker 1986, Clinger and Rees 1991
и Hanson 1991.\index{ru}{Кольбеккер, Юджин Эдмунд, мл.||Eugene Edmund
Kohlbecker Jr.||n|п}\index{en}{Eugene Edmund Kohlbecker Jr.||Кольбеккер,
Юджин Эдмунд, мл.||n|п}\index{ru}{Клингер, Уильям||William
Clinger||n|п}\index{en}{William Clinger||Клингер,
Уильям||n|п}\index{ru}{Рис, Джонатан~А.||Jonathan~A.
Rees||n|п}\index{en}{Jonathan~A. Rees||Рис,
Джонатан~А.||n|п}\index{ru}{Хансон, Кристофер~П.||Cristopher~P.
Hanson||n|п}\index{en}{Cristopher~P. Hanson||Хансон, Кристофер~П.||n|п}}.
\begin{exercise}{4.2}%
\label{EX4.2}%
\index{ru}{метациклический интерпретатор для Scheme|комбинации (применение
процедур)||||(упр.~4.2)}Хьюго Дум хочет переупорядочить ветви
{\tt eval} так, чтобы ветвь для вызова процедур располагалась
перед веткой для присваивания. Он утверждает, что при этом интерпретатор
станет эффективнее: поскольку в программах обычно больше вызовов
процедур, чем присваиваний, определений и~т.~д., его усовершенствованный
{\tt eval} обычно будет рассматривать меньше вариантов, чем
исходный, при распознавании типа выражения.
\begin{plainenum}
\item
Что за ошибка содержится в плане Хьюго? (Подсказка:
что сделает его интерпретатор с выражением {\tt (define x 3)}?)
\item
\index{ru}{метациклический интерпретатор для Scheme|синтаксис
интерпретируемого языка||||(упр.~4.2)}Хьюго расстроен, что его план не
сработал. Он готов пойти на любые жертвы, чтобы позволить интерпретатору
распознавать вызовы процедур до того, как он проверяет все остальные
типы выражений. Помогите ему, изменив синтаксис интерпретируемого
языка так, чтобы вызовы процедур начинались с символа
{\tt call}. Например, вместо {\tt (factorial 3)} нам
теперь придется писать {\tt (call factorial 3)}, а вместо
{\tt (+ 1 2)}~--- {\tt (call + 1 2)}.
\end{plainenum}
\end{exercise}
\begin{exercise}{4.3}%
\label{EX4.3}%
Перепишите {\tt eval}
\index{ru}{программирование, управляемое данными|в метациклическом
интерпретаторе||||(упр.~4.3)}\index{ru}{eval (метациклическая)|управляемая
данными|||p|(упр.~4.3)}\index{ru}{метациклический интерпретатор для
Scheme|\texttt{eval}, управляемая данными||||(упр.~4.3)}так, чтобы
диспетчеризация происходила в стиле, управляемом данными.
Сравните результат с
дифференцированием, управляемым данными, из
упражнения~\ref{EX2.73}. (Можно использовать {\tt car}
составного выражения в качестве типа этого выражения, так как это
хорошо сочетается с синтаксисом, реализованным в этом разделе.)
\end{exercise}