-
Notifications
You must be signed in to change notification settings - Fork 9
/
chapter-5.tex
7165 lines (6457 loc) · 466 KB
/
chapter-5.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{COMPUTING-WITH-REGISTER-MACHINES}
%\markboth{Глава 5 \qquad Вычисления на регистровых машинах}{}
\thispagestyle{empty}
\epigraph{
Моя цель~--- показать, что небесная машина не некое божественное
живое существо,~а скорее часовой механизм (а тот, кто верит, что у
часов есть душа, приписывает славу творца творению),
поскольку почти все из ее многочисленных движений вызываются
простейшей материальной силой, так же, как все движения часов
вызываются весом гири.
\index{ru}{Кеплер, Иоганн||Johannes Kepler||n|}%
\index{en}{Johannes Kepler||Кеплер, Иоганн||n|}}%
{Иоганн Кеплер \\
(письмо к Герварту фон Гогенбургу, 1605)}
%MLR% указать переводчика.
Эта книга начинается с изучения процессов и с описания процессов в
терминах процедур, написанных на Лиспе. Чтобы объяснить значение этих
процедур, мы последовательно использовали несколько моделей
вычисления: подстановочную модель из
главы~\ref{BUILDING-ABSTRACTIONS-WITH-PROCEDURES}, модель с
окружениями из главы~\ref{MODULARITY-OBJECTS-AND-STATE} и
метациклический интерпретатор из главы~\ref{METALINGUISTIC-ABSTRACTION}.
Изучая последний,
мы по большей части сняли покров тайны с деталей интерпретации
лиспоподобных языков. Однако даже
метациклический интерпретатор оставляет многие вопросы без ответа,
поскольку он не проясняет механизмы управления Лисп-системы. Например,
интерпретатор не показывает, как при вычислении подвыражения удается
вернуть значение выражению, это значение использующему, или почему одни
рекурсивные процедуры порождают итеративные процессы (то есть
занимают неизменный объем памяти),~в то время как другие процедуры
порождают рекурсивные процессы. Эти вопросы остаются без ответа
потому, что метациклический интерпретатор сам по себе является
программой на Лиспе,~а следовательно, наследует управляющую структуру
нижележащей Лисп-системы. Чтобы предоставить более полное описание
управляющей структуры вычислителя Лиспа, нам нужно работать на более
элементарном уровне, чем сам Лисп.
В этой главе мы будем описывать процессы~в терминах пошаговых
операций традиционного компьютера. Такой компьютер, или
\index{ru}{регистровая машина||register machine|||}\index{en}{register machine||регистровая машина|||}{\em регистровая машина} (register machine),
последовательно выполняет \index{ru}{команда||instruction|||}\index{en}{instruction||команда|||}{\em команды} (instructions),
которые работают с ограниченным числом элементов памяти, называемых
\index{ru}{регистр||register|||}\index{en}{register||регистр|||}{\em регистрами} (registers). Типичная команда регистровой
машины применяет элементарную операцию к содержимому нескольких
регистров и записывает результат еще~в один регистр. Наши описания
процессов, выполняемых регистровыми машинами, будут очень похожи на
<<машинный язык>> обыкновенных компьютеров. Однако вместо того, чтобы
сосредоточиться на машинном языке какого-то конкретного компьютера, мы
рассмотрим несколько процедур на Лиспе и спроектируем специальную
регистровую машину для выполнения каждой из этих процедур. Таким
образом, мы будем решать задачу с точки зрения архитектора аппаратуры,
а не с точки зрения программиста на машинном языке компьютера. При
проектировании регистровых машин мы разработаем механизмы для
реализации важных программистских конструкций, таких, как рекурсия.
Кроме того, мы представим язык для описания регистровых машин. В
разделе~\ref{A-REGISTER-MACHINE-SIMULATOR} мы реализуем
программу на Лиспе, которая с помощью этих описаний имитирует
проектируемые нами машины.
Большинство элементарных операций наших регистровых машин очень
просты. Например, такая операция может складывать числа, взятые из
двух регистров, и сохранять результат~в третьем. Несложно описать
устройство, способное выполнять такие операции. Однако для работы со
списковыми структурами мы будем использовать также операции
{\tt car}, {\tt cdr} и {\tt cons},~а они требуют
сложного механизма выделения памяти. В
разделе~\ref{STORAGE-ALLOCATION-AND-GARBAGE-COLLECTION} мы изучаем
их реализацию на основе более простых операций.
В разделе~\ref{THE-EXPLICIT-CONTROL-EVALUATOR},
накопив опыт выражения простых процессов~в виде регистровых машин, мы
спроектируем машину, которая реализует алгоритм, описываемый
метациклическим интерпретатором из
раздела~\ref{THE-METACIRCULAR-EVALUATOR}. Таким образом, окажется
заполненным пробел~в нашем понимании того, как интерпретируются
выражения языка Scheme, поскольку будет представлена явная модель
механизмов управления вычислителя. В
разделе~\ref{COMPILATION} мы рассмотрим простой компилятор,
переводящий программы на Scheme~в последовательности команд,
которые можно впрямую выполнить с помощью регистров и операций
регистровой машины-вычислителя.
\section{Проектирование регистровых машин}
\label{DESIGNING-REGISTER-MACHINES}
\index{ru}{регистровая машина|проектирование||||} Чтобы спроектировать регистровую машину, требуется описать ее
\index{ru}{регистровая машина|пути данных||||}
\index{ru}{пути данных регистровой машины||data paths for register machine|||}\index{en}{data paths for register machine||пути данных регистровой машины|||}{\em пути данных} (data paths), то
есть регистры и \index{ru}{операция|в регистровой машине||||} операции,~а
\index{ru}{регистровая машина|контроллер||||}
также
\index{ru}{контроллер для регистровой машины||controller for register machine|||}
\index{en}{controller for register machine||контроллер для регистровой машины|||}
{\em контроллер} (controller), который управляет
последовательностью этих операций. Чтобы продемонстрировать
строение простой регистровой машины, рассмотрим алгоритм Евклида
для вычисления наибольшего общего делителя (НОД)
двух натуральных чисел. Как мы видели~в
разделе~\ref{GREATEST-COMMON-DIVISORS},
\index{ru}{Евклида алгоритм|||||}
\index{ru}{алгоритм|Евклида||||}
алгоритм Евклида можно
реализовать~в виде итеративного процесса, который описывается
следующей процедурой:
\index{ru}{gcd|регистровая машина|||p|}
\begin{Verbatim}[fontsize=\small]
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
\end{Verbatim}
Машина, реализующая алгоритм, должна отслеживать
два числовых значения, $a$ и $b$. Поэтому
предположим, что эти числа хранятся~в двух регистрах с такими же именами. Основные
требуемые операции~--- это проверка, не является ли содержимое регистра
{\tt b} нулем, и вычисление остатка от деления содержимого
регистра {\tt a} на содержимое регистра {\tt b}.
Операция вычисления остатка~--- сложный процесс, однако пока что
предположим, что у нас есть элементарное устройство, вычисляющее
остатки. В каждом цикле алгоритма вычисления НОД содержимое регистра
{\tt a} требуется заменить содержимым регистра {\tt b},
а содержимое регистра {\tt b} следует заменить на остаток от
деления старого содержимого {\tt a} на старое содержимое
{\tt b}. Было бы удобно, если бы можно было производить эти
замены одновременно, однако для нашей модели регистровых машин мы
предположим, что на каждом шаге можно присвоить новое значение только
одному регистру. Чтобы произвести замены, наша машина использует
третий <<временный>> регистр, который мы назовем
{\tt t}. (Сначала мы помещаем остаток~в {\tt t}, затем
помещаем содержимое {\tt b}~в {\tt a}, и наконец
переносим остаток, хранимый~в {\tt t},~в {\tt b}.)
Можно изобразить регистры и операции, требуемые нашей
машине, при помощи
\index{ru}{пути данных регистровой машины|диаграмма путей данных||||}
\index{ru}{регистровая машина|диаграмма путей данных||||}
диаграммы путей данных, показанной на
рисунке~\ref{P5.1}. Регистры ({\tt a}, {\tt b} и
{\tt t}) на этой диаграмме изображаются~в виде
прямоугольников. Каждый способ присвоить регистру значение
обозначается стрелкой, указывающей из источника данных на регистр, со
значком Х позади головки. Можно считать этот Х кнопкой, которая при
нажатии позволяет значению из источника <<перетечь>>~в указанный
регистр. Метка рядом~--- это имя для кнопки.
Имена эти произвольны, и их можно подбирать с мнемоническим
значением (например, {\tt a<-b} обозначает нажатие кнопки,
которая присваивает содержимое регистра {\tt b} регистру
{\tt a}). Источником данных для регистра может служить другой
регистр (как~в случае присваивания {\tt a<-b}), результат
операции (как~в случае присваивания {\tt t<-r}) или константа
(встроенное значение, которое нельзя изменять и которое представляется
на диаграмме путей данных~в виде треугольника со значением
внутри).
Операция, которая вычисляет значение на основе констант и
содержимого регистров, представляется на диаграмме путей данных в
виде трапеции, содержащей имя операции. Например, фигура,
обозначенная на рисунке~\ref{P5.1} как {\tt rem},
представляет операцию, вычисляющую остаток от деления содержимых
регистров {\tt a} и {\tt b}, к которым она
подсоединена. Стрелки (без кнопок) указывают из входных регистров и
констант на фигуру,~а другие стрелки связывают результат операции с
регистрами. Сравнение изображается~в виде круга, содержащего имя
теста. К примеру,~в нашей машине НОД имеется операция, которая
проверяет, не равно ли содержимое регистра {\tt b} нулю. У
\index{ru}{регистровая машина|тест||||}
\index{ru}{тест, операция~в регистровой машине||test|||}
\index{en}{test||тест, операция~в регистровой машине|||}
теста тоже есть входные стрелки, ведущие из входных регистров и
констант, но у него нет исходящих стрелок; его значение используется
контроллером,~а не путями данных. В целом, диаграмма путей данных
показывает регистры и операции, которые нужны машине, и как они должны
быть связаны. Если мы рассматриваем стрелки как провода,~а кнопки Х
как переключатели, то диаграмма путей данных оказывается очень
похожа на схему машины, которую можно было бы построить из
электронных деталей.
Для того, чтобы пути данных вычисляли НОД, нужно нажимать
кнопки~в правильной последовательности. Мы будем описывать эту
последовательность с помощью \index{ru}{контроллер для регистровой машины|диаграмма||||} \index{ru}{регистровая машина|диаграмма контроллера||||} диаграммы
контроллера, показанной на
рисунке~\ref{P5.2}. Элементы диаграммы контроллера
показывают, как следует работать с компонентами путей данных.
Прямоугольные блоки~в такой диаграмме указывают, на какие кнопки
следует нажимать,~а стрелки описывают последовательный переход от
одного шага к другому. Ромб на диаграмме обозначает выбор. Произойдет
переход по одной из двух исходящих стрелок,~в зависимости от значения
того теста~в потоке данных, имя которого указано~в ромбе. Можно
интерпретировать контроллер с помощью физической аналогии: представьте
себе, что диаграмма~--- это лабиринт,~в котором катается шарик. Когда
шарик закатывается~в прямоугольник, он нажимает на кнопку, имя которой
в прямоугольнике написано. Когда шарик закатывается~в узел выбора (например,
тест ${\tt b} = 0$), он покидает этот узел по
стрелке, которую определяет результат указанного теста. Взятые
вместе, пути данных и контроллер полностью определяют машину для
вычисления НОД. Мы запускаем контроллер (катящийся шарик)~в месте,
обозначенном {\tt start}, поместив предварительно числа в
регистры {\tt a} и {\tt b}. Когда контроллер достигает
точки, помеченной {\tt done},~в регистре {\tt a}
оказывается значение НОД.
\begin{cntrfig}
\input{xfig-mod/5-1.eepic}
\caption{Пути данных~в машине НОД.}
\label{P5.1}
\end{cntrfig}
\begin{cntrfig}
\input{xfig-mod/5-2.eepic}
%{\small начало\\
%да\\
%конец\\
%нет\\}
\caption{Контроллер машины НОД.}
\label{P5.2}
\end{cntrfig}
\begin{exercise}{5.1}\label{EX5.1}%
Спроектируйте регистровую машину для вычисления факториалов
с помощью итеративного алгоритма, задаваемого следующей процедурой.
Нарисуйте для этой машины диаграммы путей данных и контроллера.
\index{ru}{factorial|регистровая машина (итеративная)|||p|(упр.~5.1)}
\begin{Verbatim}[fontsize=\small]
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
\end{Verbatim}
\end{exercise}
\subsection{Язык для описания регистровых машин}
\label{A-LANGUAGE-FOR-DESCRIBING-REGISTER-MACHINES}
\index{ru}{регистровая машина|язык для описания||||}
Диаграммы путей данных и контроллера адекватно
представляют простые машины вроде машины НОД, но для описания сложных
машин вроде интерпретатора Лиспа они непригодны. Чтобы можно было
работать со сложными машинами, мы создадим язык, который представляет
в текстовом виде всю информацию, содержащуюся~в диаграммах путей
данных и контроллера. Начнем с нотации, которая впрямую отражает
диаграммы.
Мы определяем пути данных ({\tt data-paths}) машины, описывая регистры
({\tt registers}) и
операции ({\tt operations}). Чтобы описать регистр, мы даем
ему имя ({\tt name}) и указываем кнопки ({\tt buttons}),
которые присваивают ему значение. Каждой из этих кнопок мы даем имя
({\tt name}) и
указываем источник ({\tt source}) для данных, которые попадают~в регистр, управляемый
кнопкой. Источником может служить регистр ({\tt register}),
константа ({\tt constant}) или операция ({\tt operation}).
Для описания операции нам нужно дать ей имя и указать входы
({\tt inputs})~--- регистры или константы.
Контроллер машины мы определяем как последовательность
\index{ru}{язык регистровых машин|команды||||}
\index{ru}{команда||instruction|||}
\index{en}{instruction||команда|||}
{\em команд} (in\-struc\-ti\-ons) с
\index{ru}{метка||label|||}
\index{en}{label||метка|||}
{\em метками} (labels),
\index{ru}{label (в регистровой машине)||||p|}
\index{ru}{язык регистровых машин|\texttt{метка}||||}
которые определяют
\index{ru}{язык регистровых машин|точки входа||||}
\index{ru}{точка входа||entry point|||}
\index{en}{entry point||точка входа|||}
{\em точки входа} (entry points). Есть
следующие виды команд:
\begin{plainlist}
\item
Имя кнопки на пути данных, которую следует нажать и
присвоить регистру значение. (Это соответствует прямоугольнику на
диаграмме контроллера.)
\item
Команда {\tt test},
\index{ru}{test (в регистровой машине)||||p|}
\index{ru}{язык регистровых машин|\texttt{test}||||}
которая выполняет указанный тест.
\item
Условный переход (команда {\tt branch})
\index{ru}{branch (в регистровой машине)||||p|}
\index{ru}{язык регистровых машин|\texttt{branch}||||}
в место, определяемое
\index{ru}{язык регистровых машин|\texttt{label}||||}
меткой контроллера, на основании предыдущего
теста. ({\tt Test} и {\tt branch} вместе соответствуют
ромбу на диаграмме контроллера.) Если тест дает результат <<ложь>>, контроллер должен
выполнять следующую команду~в последовательности. В противном случае
он должен выполнять команду, которая следует за меткой.
\item
Безусловный переход (команда \index{ru}{язык регистровых машин|\texttt{goto}||||}{\tt goto}),
\index{ru}{goto (в регистровой машине)||||p|}
указывающий метку, с которой следует продолжить выполнение.
\end{plainlist}
Машина начинает работу с начала последовательности команд контроллера
и заканчивает, когда выполнение достигает конца последовательности.
Кроме тех случаев, когда переход изменяет поток управления, команды
выполняются по порядку, так, как они перечислены.
На рисунке~\ref{P5.3} изображена описанная на
нашем языке машина НОД. Этот пример служит не более чем намеком на степень
общности таких описаний, поскольку машина НОД~--- очень простой
случай: у каждого регистра всего по одной кнопке, и каждая кнопка
используется~в контроллере только один раз.
\begin{cntrfig}
{\small
\begin{Verbatim}[fontsize=\small]
(data-paths
(registers
((name a)
(buttons ((name a<-b) (source (register b)))))
((name b)
(buttons ((name b<-t) (source (register t)))))
((name t)
(buttons ((name t<-r) (source (operation rem))))))
(operations
((name rem)
(inputs (register a) (register b)))
((name =)
(inputs (register b) (constant 0))))
(controller
test-b {\em ; метка}
(test =) {\em ; тест}
(branch (label gcd-done)) {\em ; условный переход}
(t<-r) {\em ; нажатие кнопки}
(a<-b) {\em ; нажатие кнопки}
(b<-t) {\em ; нажатие кнопки}
(goto (label test-b)) {\em ; безусловный переход}
gcd-done)) {\em ; метка}
\end{Verbatim}
}\caption{Описание машины НОД.}
\label{P5.3}
\end{cntrfig}
К сожалению, такое описание неудобно читать. Чтобы понимать
команды контроллера, нам все время приходится смотреть на определения
имен кнопок и операций,~а чтобы понять, что делают операции,
приходится обращаться к определениям имен операций. Поэтому мы изменим
свой способ записи и сольем информацию из описания контроллера и описания путей
данных, так, чтобы видеть их одновременно.
В этой новой форме записи мы заменим
произвольные имена кнопок и операций на описание их поведения.
\index{ru}{язык регистровых машин|\texttt{reg}||||}
\index{ru}{язык регистровых машин|\texttt{op}||||}
\index{ru}{язык регистровых машин|\texttt{assign}|register machine language|||}
\index{en}{register machine language||язык регистровых машин|\texttt{assign}||}
То есть, вместо того, чтобы говорить (в контроллере) <<нажать кнопку
{\tt t<-r}>> и отдельно (в путях данных) <<кнопка
{\tt t<-r} присваивает регистру {\tt t} значение
операции {\tt rem}>>,~а также <<входы операции
{\tt rem}~--- это содержимое регистров {\tt a} и
{\tt b}>>, мы будем говорить (в контроллере) <<нажать кнопку,
которая присваивает регистру {\tt t} результат операции
{\tt rem} от содержимого регистров {\tt a} и
{\tt b}>>.
\index{ru}{язык регистровых машин|\texttt{const}||||}
Подобным образом, вместо <<выполнить тест
{\tt =}>> (в контроллере) и отдельно (в путях
данных) <<тест {\tt =} применяется к содержимому регистра
{\tt b} и константе 0>>, будем говорить <<выполнить тест
{\tt =} над содержимым регистра {\tt b} и константой
0>>. Описание путей данных мы будем опускать, оставляя только
последовательность команд контроллера. Таким образом, машину НОД
можно описать так:
\index{ru}{assign (в регистровой машине)||||p|}
\index{ru}{const (в регистровой машине)||||p|}
\index{ru}{op (в регистровой машине)||||p|}
\index{ru}{reg (в регистровой машине)||||p|}
\pagebreak
\begin{Verbatim}[fontsize=\small]
(controller
test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done)
\end{Verbatim}
Запись~в такой форме проще читать, чем описания на
разновидности языка, показанной на рисунке~\ref{P5.3}, но
есть у нее и недостатки:
\begin{plainlist}
\item
Для больших машин такие описания длиннее, поскольку
полные определения элементов путей данных повторяются каждый раз, как
эти элементы упоминаются~в последовательности команд контроллера. (В
примере с НОД этой проблемы не возникает, поскольку каждая операция и
каждая кнопка используются только по разу.) Более того, повторение описаний
путей данных скрывает структуру этих путей~в машине; для больших машин
становится сложно определить, сколько~в них регистров, операций и кнопок, и как
они связаны.
\item
Поскольку команды контроллера~в определении машины
похожи на выражения Лиспа, легко забыть, что это не произвольные
Лисп-выражения. Можно описывать только разрешенные операции машины.
Например, операции впрямую могут работать только с константами и
содержимым регистров,~а не с результатами других операций.
\end{plainlist}
Несмотря на указанные недостатки, мы будем использовать такой язык описания
регистровых машин на всем протяжении этой главы, поскольку нас в
большей мере будет занимать понимание работы контроллеров, чем
понимание элементов и связей~в путях данных. Следует, однако,
помнить, что проектирование путей данных~--- ключевой элемент в
разработке настоящих машин.
\begin{exercise}{5.2}%%
\label{EX5.2}%
С помощью языка регистровых машин опишите итеративную
факториал-машину из упражнения~\ref{EX5.1}.\index{ru}{factorial|регистровая машина (итеративная)|||p|(упр.~5.2)}
\sloppy
\end{exercise}
\paragraph{Действия}
\index{ru}{регистровая машина|действия||||}
Давайте теперь изменим машину НОД так, чтобы можно было
вводить числа, НОД которых мы хотим получить, и видеть результаты,
напечатанные на терминале. Мы не будем обсуждать, как построить
машину для считывания и печати,~а предположим (как и с процедурами
{\tt read} и {\tt display}~в Scheme), что эти действия
доступны как элементарные операции\footnote{Такое предположение покрывает большую и сложную
область. Обычно значительная часть реализации Лисп-систем посвящена
работе ввода и вывода.
}.
\index{ru}{read, операция регистровой машины||||p|}
{\tt Read} подобна операциям, которые мы
использовали ранее, поскольку она порождает значение, и его можно
сохранить~в регистре. Однако {\tt read} не принимает входа ни
из каких регистров; ее значение зависит от событий, происходящих за
пределами тех компонентов машины, проектированием которых мы заняты.
Мы позволим операциям нашей машины вести себя таким образом, и,
следовательно, будем рисовать {\tt read} и
изображать ее~в языке описания так же, как любую другую операцию,
вычисляющую значение.
\index{ru}{print, операция~в регистровой машине||||p|}
{\tt Print}, с другой стороны, фундаментальным
образом отличается от тех операций, которыми мы до сих пор пользовались:
она не порождает результата, который можно было бы поместить
в регистр. Хотя она и производит эффект, этот эффект не касается тех
частей машины, которые мы проектируем. Этот тип операций мы будем
называть \index{ru}{действия,~в регистровой машине||actions, in register machine|||}\index{en}{actions, in register machine||действия,~в регистровой машине|||}{\em действиями} (actions). На диаграмме путей
данных мы будем представлять действие так же, как и операции,
вычисляющие значение~--- как трапецию с именем действия. В этот
элемент входят стрелки из входов (регистров или констант). Кроме
того, мы связываем с действием кнопку. Нажатие кнопки заставляет
действие совершиться. Чтобы скомандовать контроллеру нажать кнопку
действия, мы вводим новый тип команды {\tt perform}.
\index{ru}{perform (в регистровой машине)||||p|}
\index{ru}{язык регистровых машин|\texttt{perform}||||}
Таким образом, действие по распечатке содержимого регистра {\tt a}
представляется~в последовательности контроллера командой
\begin{Verbatim}[fontsize=\small]
(perform (op print) (reg a))
\end{Verbatim}
На рисунке~\ref{P5.4} показаны пути данных и
контроллер для новой машины НОД. Вместо того, чтобы останавливать
машину после печати ответа, мы приказываем ей начать сначала, так что
она~в цикле считывает пару чисел, вычисляет их НОД и печатает
результат. Такая структура подобна управляющим циклам, которые мы
использовали~в интерпретаторах из главы~\ref{METALINGUISTIC-ABSTRACTION}.
\begin{cntrfig}
\input{xfig-mod/5-4.eepic}
\begin{Verbatim}[fontsize=\small]
(controller
gcd-loop
(assign a (op read))
(assign b (op read))
test-b
(test (op =) (reg b) (const 0)
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done
(perform (op print) (reg a))
(goto (label gcd-loop)))
\end{Verbatim}
\caption{Машина НОД, которая считывает входные числа и
печатает результат.}
\label{P5.4}
\end{cntrfig}
\subsection{Абстракция~в проектировании машин}
\label{ABSTRACTION-IN-MACHINE-DESIGN}
\index{ru}{абстракция|при проектировании регистровых машин||||}
Часто~в определении машины мы будем использовать
<<элементарные>> операции, которые на самом деле весьма сложны.
Например,~в разделах~\ref{THE-EXPLICIT-CONTROL-EVALUATOR}
и \ref{COMPILATION} мы будем рассматривать операции с
окружениями Scheme как элементарные. Такая абстракция полезна,
поскольку она позволяет нам игнорировать детали частей машины, так что
мы можем сосредоточиться на других сторонах общего плана. Однако,
хотя мы и скрываем существенную часть сложности, это не означает, что
проект машины нереалистичен. Сложные <<примитивы>> всегда можно заменить
более простыми операциями.
Рассмотрим машину НОД. В ней содержится команда, которая
вычисляет остаток от деления содержимого регистров {\tt a} и
{\tt b} и сохраняет результат~в регистре {\tt t}. Если
мы хотим построить машину НОД без использования элементарной операции
взятия остатка, нам нужно указать, как вычислять остатки с помощью
более простых операций, например, вычитания. Действительно, можно
написать на Scheme процедуру нахождения остатка таким образом:
\begin{Verbatim}[fontsize=\small]
(define (remainder n d)
(if (< n d)
n
(remainder (- n d) d)))
\end{Verbatim}
Значит, мы можем заменить операцию взятия остатка~в машине НОД
операцией вычитания и тестом-сравнением. На
рисунке~\ref{P5.5} показаны пути данных и контроллер уточненной
машины.
\pagebreak
Команда
\begin{Verbatim}[fontsize=\small]
(assign t (op rem) (reg a) (reg b))
\end{Verbatim}
в определении контроллера НОД заменяется на последовательность команд,
содержащую цикл, как показано на рисунке~\ref{P5.6}.
\begin{figure}[p]
\begin{center}
\input{xfig-mod/5-5.eepic}
%{\small начало\\
%конец
%да (2 раза)\\
%нет (2 раза)}
\caption{Пути данных и контроллер уточненной машины НОД.}
\label{P5.5}
\end{center}
\end{figure}
\begin{cntrfig}
\begin{Verbatim}[fontsize=\small]
(controller
test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (reg a))
rem-loop
(test (op <) (reg t) (reg b))
(branch (label rem-done))
(assign t (op -) (reg t) (reg b))
(goto (label rem-loop))
rem-done
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done)
\end{Verbatim}
\caption{Последовательность команд контроллера машины
НОД с рисунка~\ref{P5.5}.}
\label{P5.6}
\end{cntrfig}
\begin{exercise}{5.3}%%
\label{EX5.3}%
Спроектируйте машину для вычисления квадратных корней
методом Ньютона, как описано~в
разделе~\ref{EXAMPLE-SQUARE-ROOTS-BY-NEWTONS-METHOD}:
\index{ru}{sqrt|регистровая машина|||p|(упр.~5.3)}
\samepage
\begin{Verbatim}[fontsize=\small]
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
\end{Verbatim}
Для начала предположите, что операции {\tt good-enough?} и
{\tt improve} имеются как примитивы. Затем покажите, как
развернуть их с помощью арифметических операций. Опишите каждую из
версий машины {\tt sqrt}, нарисовав диаграмму путей данных, и
написав определение контроллера на языке регистровых машин.
\end{exercise}
\subsection{Подпрограммы}
\label{SUBROUTINES}
\index{ru}{регистровая машина|подпрограмма||||}
При проектировании машины для некоторого вычисления мы
часто предпочтем устроить так, чтобы компоненты ее разделялись
различными частями вычисления,~а не дублировались. Рассмотрим машину,
которая включает~в себя два вычисления НОД~--- одно находит НОД
содержимого регистров {\tt a} и {\tt b},~а другое НОД
содержимого регистров {\tt c} и {\tt d}. Для начала
можно предположить, что имеется элементарная операция
{\tt gcd},~а затем развернуть два экземпляра {\tt gcd} в
терминах более простых операций. На рисунке~\ref{P5.7}
показаны только части получившихся путей данных, относящиеся к НОД.
Связи с остальными частями машины опущены. Кроме того, на рисунке
показаны соответствующие сегменты последовательности команд
контроллера машины.
\begin{cntrfig}
\input{xfig-mod/5-7.eepic}
\begin{Verbatim}[fontsize=\small]
gcd-1
(test (op =) (reg b) (const 0))
(branch (label after-gcd-1))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd-1))
after gcd-1
.
.
.
gcd-2
(test (op =) (reg d) (const 0))
(branch (label after-gcd-2))
(assign s (op rem) (reg c) (reg d))
(assign c (reg d))
(assign d (reg s))
(goto (label gcd-2))
after-gcd-2
\end{Verbatim}
\caption{Части путей данных и последовательностей
команд контроллера для машины с двумя вычислениями НОД.}
\label{P5.7}
\end{cntrfig}
В этой машине два блока вычисления остатка и два блока
проверки на равенство. Если повторяющиеся компоненты сложны, как,
например, блок вычисления остатка, такое построение машины окажется
неэкономным. Можно избежать дублирования компонент путей данных, если
использовать для обоих вычислений НОД одни и те же компоненты, при
условии, что такое решение не повлияет на остальные вычисления большой
машины. Если к тому времени, как контроллер добирается до
{\tt gcd-2}, значения~в регистрах {\tt a} и
{\tt b} не нужны (или если их можно временно сохранить в
каких-то еще регистрах), то мы можем изменить машину так, чтобы она
использовала регистры {\tt a} и {\tt b},~а не
{\tt c} и {\tt d}, при вычислении второго НОД, так же
как и при вычислении первого. Так у нас получится
последовательность команд контроллера, показанная на
рисунке~\ref{P5.8}.
\begin{cntrfig}
\begin{Verbatim}[fontsize=\small]
gcd-1
(test (op =) (reg b) (const 0))
(branch (label after-gcd-1))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(goto (label gcd-1))
after-gcd-1
.
.
.
gcd-2
(test (op =) (reg b) (const 0))
(branch (label after-gcd-2))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd-2))
after-gcd-2
\end{Verbatim}
\caption{Сегменты последовательности команд
контроллера для машины, которая использует одни и те же компоненты
путей данных для двух различных вычислений НОД.}
\label{P5.8}
\end{cntrfig}
Мы удалили одинаковые компоненты путей данных (так что они
снова стали такими, как на рисунке~\ref{P5.1}), но теперь в
контроллере содержатся две последовательности команд вычисления НОД,
которые различаются только метками. Было бы лучше заменить эти две
последовательности переходами к единой последовательности~---
\index{ru}{подпрограмма,~в регистровой машине||subroutine|||}\index{en}{subroutine||подпрограмма,~в регистровой машине|||}{\em подпрограмме} (subroutine),~---~в конце которой мы
возвращаемся обратно к нужному месту~в основной последовательности
команд. Этого можно добиться так: прежде, чем перейти к
{\tt gcd}, мы помещаем определенное значение (0 или 1)~в особый
регистр, {\tt continue}.
\index{ru}{continue, регистр||||pd|}
В конце подпрограммы {\tt gcd}
мы переходим либо к {\tt after-gcd-1}, либо к
{\tt after-gcd-2},~в зависимости от значения из регистра
{\tt continue}. На рисунке~\ref{P5.9} показан
соответствующий сегмент получающейся последовательности команд
контроллера, который содержит только одну копию команд
{\tt gcd}.
\begin{cntrfig}
\begin{Verbatim}[fontsize=\small]
gcd
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd))
gcd-done
(test (op =) (reg continue) (const 0))
(branch (label after-gcd-1))
(goto (label after-gcd-2))
.
.
.
{\em ;; Прежде, чем перейти к {\tt gcd} из первого места, где}
{\em ;; он нужен, заносим 0~в регистр {\tt continue}}
(assign continue (const 0))
(goto (label gcd))
after-gcd-1
.
.
.
{\em ;; Перед вторым использованием {\tt gcd} помещаем 1~в регистр {\tt continue}.}
(assign continue (const 1))
(goto (label gcd))
after-gcd-2
\end{Verbatim}
\caption{Использование регистра {\tt continue} ради избежания повторяющейся
последовательности команд с рисунка~\ref{P5.8}.}
\label{P5.9}
\end{cntrfig}
\begin{cntrfig}
\begin{Verbatim}[fontsize=\small]
gcd
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd))
gcd-done
(goto (reg continue))
.
.
.
{\em ;; Перед вызовом {\tt gcd} заносим~в {\tt continue}}
{\em ;; метку, на которую {\tt gcd} должен вернуться.}
(assign continue (label after-gcd-1))
(goto (label gcd))
after-gcd-1
.
.
.
{\em ;; Второй вызов{\tt gcd}, с другим продолжением.}
(assign continue (label after-gcd-2))
(goto (label gcd))
after-gcd-2
\end{Verbatim}
\caption{Присваивание регистру {\tt continue} меток упрощает и обобщает
стратегию с рисунка~\ref{P5.9}.}
\label{P5.10}
\end{cntrfig}
Для маленьких задач это разумный подход, однако если бы
в последовательности команд контроллера имелось много вызовов
вычисления НОД, он стал бы неудобен. Чтобы решить, где продолжать
вычисление после подпрограммы {\tt gcd}, нам пришлось бы иметь
в контроллере тесты и переходы для всех мест, где используется
{\tt gcd}. Более мощный метод реализации подпрограмм состоит в
том, чтобы запоминать~в регистре {\tt continue} метку точки
входа~в последовательности контроллера, с которой выполнение должно
продолжиться, когда подпрограмма закончится. Реализация этой
стратегии требует нового вида связи между путями данных и контроллером
регистровой машины: должно быть возможно присвоить регистру метку в
последовательности команд контроллера таким образом, чтобы это
значение можно было из регистра извлечь и с его помощью продолжить
выполнение с указанной точки входа.
Чтобы отразить эту возможность, мы расширим команду
{\tt assign}
\index{ru}{assign (в регистровой машине)|сохранение метки~в регистре|||p|}
языка регистровых машин и позволим присваивать
регистру~в качестве значения метку из последовательности команд
контроллера (как особого рода константу). Кроме того, мы расширим
команду {\tt goto}
\index{ru}{goto (в регистровой машине)|переход на содержимое регистра|||p|}
и позволим вычислению продолжаться с точки входа,
которая описывается содержимым регистра,~а не только с точки входа,
описываемой меткой-константой. С помощью этих двух команд мы можем
завершить подпрограмму {\tt gcd} переходом~в место, хранимое в
регистре {\tt continue}. Это ведет к последовательности
команд, показанной на рисунке~\ref{P5.10}.
Машина,~в которой имеется более одной подпрограммы, могла
бы использовать различные регистры продолжения (например,
{\tt gcd-continue}, {\tt facto\-rial-con\-ti\-nue}), или же мы
могли бы для всех подпрограмм использовать один регистр
{\tt continue}. Разделение регистра экономичнее, однако
тогда требуется отслеживать случаи, когда из одной подпрограммы
({\tt sub1}) зовется другая ({\tt sub2}). Если
{\tt sub1} не сохранит значение {\tt continue} в
каком-то другом регистре, прежде чем использовать
{\tt continue} при вызове {\tt sub2}, то {\tt sub1}
не будет знать, откуда продолжать выполнение после ее конца.
Механизм, который разрабатывается~в следующем разделе для работы с
рекурсией, дает хорошее решение и для проблемы с вложенными вызовами
подпрограмм.
\subsection{Реализация рекурсии с помощью стека}
\label{USING-A-STACK-TO-IMPLEMENT-RECURSION}
\index{ru}{стек|для рекурсии~в регистровой машине||||}
\index{ru}{итеративный процесс|регистровая машина||||}
\index{ru}{рекурсивный процесс|регистровая машина||||}
\index{ru}{регистровая машина|стек||||}
При помощи описанных до сих пор механизмов мы можем
реализовать любой итеративный процесс, задав регистровую машину, в
которой имеется по регистру на каждую переменную состояния процесса.
Машина выполняет цикл контроллера, изменяя при этом состояние
регистров, до тех пор, пока не окажется выполнено некоторое условие
окончания процесса. В каждой точке последовательности команд
контроллера состояние машины (представляющее состояние итеративного
процесса) полностью определяется состоянием регистров (значением
переменных состояния).
\index{ru}{итеративный процесс|vs. рекурсивный процесс||||} \index{ru}{рекурсивный процесс|vs. итеративный процесс||||}
Однако реализация рекурсивных процессов требует
дополнительного механизма. Рассмотрим следующий рекурсивный метод
вычисления факториала, описанный нами~в
разделе~\ref{LINEAR-RECURSION-AND-ITERATION}:
\index{ru}{factorial|регистровая машина (рекурсивная)|||p|}
\begin{Verbatim}[fontsize=\small]
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
\end{Verbatim}
Как мы видим из этой процедуры, вычисление $n!$ требует
вычисления $(n-1)!$. Машина НОД, которая моделирует
процедуру
\begin{Verbatim}[fontsize=\small]
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
\end{Verbatim}
также должна была вычислять НОД других чисел, помимо начальных
значений. Однако между машиной НОД, которая сводит исходное
вычисление к вычислению другого НОД, и {\tt factorial}, в
котором нужно вычислить другой факториал как подзадачу, есть
существенная разница. В машине НОД
ответ, выдаваемый новым вычислением НОД~--- это и есть ответ на исходную
задачу. Чтобы вычислить следующий НОД, мы просто помещаем новые
аргументы во входные регистры машины и заново используем ее пути
данных, прогоняя ту же самую последовательность команд контроллера.
Когда машина заканчивает решение последней задачи НОД, исходное вычисление
также заканчивается.
В случае с факториалом (и~в любом другом рекурсивном
процессе) ответ на подзадачу-факториал не является решением общей
задачи. Значение, полученное для $(n-1)!$, требуется еще
домножить на $n$, чтобы получить окончательный ответ. Если
мы попытаемся сымитировать решение задачи НОД и решить
подзадачу-факториал, уменьшив регистр {\tt n} и запустив машину
заново, у нас больше не будет старого значения {\tt n}, на
которое можно было бы домножить результат. Для решения подзадачи нам
бы потребовалась еще одна факториальная машина. Во втором вычислении
факториала также есть подзадача-факториал, для нее требуется третья
факториальная машина, и так далее. Поскольку внутри каждой
факториальной машины содержится другая факториальная машина,~в общей
машине должно содержаться бесконечное гнездо вложенных друг~в друга
машин,~а следовательно, ее нельзя построить из заранее заданного
конечного числа деталей.
Тем не менее реализовать факториальный процесс в
виде регистровой машины можно, если использовать одни и те же
компоненты для всех встроенных ее экземпляров. ~а именно, машина,
которая вычисляет $n!$, должна использовать одни и те же
детали для работы над подзадачей вычисления $(n-1)!$,
$(n-2)!$ и так далее. Такое построение возможно,
поскольку, несмотря на то, что факториальный процесс требует для
своего вычисления неограниченное число одинаковых машин,~в каждый
момент времени только одна из этих машин активна. Когда машина
встречает рекурсивную подзадачу, она может остановить работу над
основной задачей, использовать свои физические детали для решения
подзадачи,~а затем продолжить остановленное вычисление.
Содержимое регистров внутри подзадачи будет отличаться от
их значения~в главной задаче. (В нашем случае регистр {\tt n}
уменьшается на единицу.) Чтобы суметь продолжить остановленное
вычисление, машина должна сохранить содержимое всех регистров, которые
ей понадобятся после того, как подзадача будет решена,~а затем
восстановить их, прежде чем возобновить работу. В случае с
факториалом мы сохраним старое значение {\tt n} и восстановим
его, когда закончим вычисление факториала от уменьшенного значения
регистра {\tt n}\footnote{Казалось бы, незачем сохранять старое
{\tt n}; после того, как мы его уменьшим на единицу и решим
подзадачу, можно эту единицу добавить и восстановить старое значение.
Такая стратегия работает для факториала, но~в общем случае она
работать не может, поскольку старое значение регистра не всегда можно
вычислить на основании нового.
}.
Поскольку нет никакого априорного ограничения на число вложенных
рекурсивных вызовов, нам может понадобиться хранить произвольное
число значений регистров. Значения эти требуется восстанавливать в
порядке, обратном порядку их сохранения, поскольку~в гнезде рекурсий
последняя начатая подзадача должна завершаться первой. Поэтому
требуется использовать для сохранения значений регистров
\index{ru}{стек||stack|||}\index{en}{stack||стек|||}{\em стек} (stack), или структуру
данных вида <<последним вошел, первым вышел>>. Можно расширить язык
регистровых машин и добавить~в него стек, если ввести два новых вида
команд: значения заносятся на стек командой \index{ru}{язык регистровых машин|\texttt{save}||||} \index{ru}{save (в регистровой машине)||||p|}{\tt save} и
снимаются со стека при помощи команды \index{ru}{язык регистровых машин|\texttt{restore}||||}
\index{ru}{restore (в регистровой машине)||||p|}
{\tt restore}. После
того, как последовательность значений сохранена на стеке,
последовательность команд {\tt restore} восстановит их в
обратном порядке\footnote{В
разделе~\ref{STORAGE-ALLOCATION-AND-GARBAGE-COLLECTION} мы увидим,
как стек можно реализовать на основе более элементарных операций.
}.
С помощью стека можно использовать для всех
подзадач-факториалов единую копию путей данных факториальной
машины. Имеется подобная проблема и при использовании
последовательности команд контроллера, который управляет путями
данных. Чтобы запустить новое вычисление факториала, контроллер не
может просто перейти~в начало последовательности, как~в итеративном
процессе, поскольку после решения подзадачи поиска $(n-1)!$
машине требуется еще домножить результат на $n$.
Контроллер должен остановить вычисление $n!$, решить
подзадачу поиска $(n-1)!$ и затем продолжить вычисление
$n!$. Такой взгляд на вычисление факториала приводит к
использованию механизма подпрограмм из
раздела~\ref{SUBROUTINES}, при котором контроллер с помощью
регистра {\tt continue}
\index{ru}{continue, регистр|и рекурсия|||pd|}
переходит к той части
последовательности команд, которая решает подзадачу,~а затем
продолжает с того места, где он остановился~в главной задаче. Мы можем
таким образом написать факториальную подпрограмму, которая
возвращается к точке входа, сохраненной~в регистре
{\tt continue}. При каждом вызове подпрограммы мы сохраняем и
восстанавливаем регистр {\tt continue} подобно регистру
{\tt n}, поскольку все <<уровни>> вычисления факториала
используют один и тот же регистр {\tt continue}. Так что
факториальная подпрограмма должна записать~в {\tt continue}
новое значение, когда она вызывает сама себя для решения подзадачи, но