Компьютер маленького человечка

Все мы знаем машину Тьюринга и машину Поста. Это абстрактные вычислительные машины, придуманные математиками для теории алгоритмов. Компьютер маленького человечка (Little man computer) — модель компьютера, предназначенная для обучения тому, как устроен и работает компьютер. Эта модель была предложена профессором Стюартом Мэдником в 1965 году и успешно используется для обучения студентов начальных курсов как в области программирования, так и конструирования компьютеров.


Давайте посмотрим на компьютер как на небольшое почтовое отделение.

В отделении есть два окошка для общения с внешним миром: в окошко INP поступают, а из окошка OUT выходят листочки с числами.Числа могут быть от 0 до 999. В отделении есть 100 почтовых ящиков, пронумерованных от 0 до 99, из них человечек может брать листочки с трехзначными числами, а также может заменять эти листочки новыми. Также у него есть простой калькулятор (аккумулятор), позволяющий складывать и вычитать трехзначные числа. При обработке чисел на калькуляторе автоматически поднимаются флажки для чисел, равных 0 и больших 0.

Оператор компьютера пишет программу на листочках и кладет их в почтовые ящики, затем устанавливает счетчик команд (PC) в 0 и нажимает кнопку «Начать работу». Внутри почтового отделения человечек обрабатывает листочки с числами, лежащие в почтовых ящиках. Опишем цикл обработки по шагам:

1. Выбрать число из счетчика команд. Это число — номер почтового ящика.
2. Запомнить число из почтового ящика, номер которого получен на 1 шаге.
3. Увеличить счетчик команд на 1.
4. Разобрать команду (число, полученное на 2 шаге).
5. Выполнить выборку данных из почтового ящика, если это требуется.
6. Выполнить саму команду.
7. Сохранить данные в почтовый ящик, если это требуется.
8. Вернуться к шагу 1 или остановиться, если команда равна 0.

Команды — трехзначные десятичные числа, цифра сотен определяет тип команды, а цифры десятков и единиц — номер почтового ящика.

Код команды	Тип команды	Действия
1xx	ADD	Добавить число из ящика хх к аккумулятору. Поднять флаг НОЛЬ или ПОЛОЖИТЕЛЬНОЕ ЧИСЛО. Если результат больше 999, то закончить работу с ошибкой.
2xx	SUB	Вычесть число из ящика хх из аккумулятора. Поднять флаг НОЛЬ или ПОЛОЖИТЕЛЬНОЕ ЧИСЛО. Если результат меньше 0, то аккумулятор не изменяется а флаги опускаются.
3xx	STA	Сохранить содержимое аккумулятора в ящике хх.
5xx	LDA	Загрузить число из ящика хх в аккумулятор. Поднять флаг НОЛЬ или ПОЛОЖИТЕЛЬНОЕ ЧИСЛО.
6xx	BRA	Установить счетчик команд равным xx.
7xx	BRZ	Если флаг НОЛЬ, то установить счетчик команд равным xx.
8xx	BRP	Если флаг НОЛЬ или ПОЛОЖИТЕЛЬНОЕ ЧИСЛО, то установить счетчик команд равным xx.
901	INP	Выбрать число из окошка INP и записать в аккумулятор. Поднять флаг НОЛЬ или ПОЛОЖИТЕЛЬНОЕ ЧИСЛО. Если число не попадает в диапазон от 0 до 999, то закончить работу с ошибкой.
902	OUT	Записать число из аккумулятора на листочке и положить в окошко OUT.
000	HLT	Закончить работу.

Итак, мы описали компьютер с архитектурой фон Неймана с небольшим набором команд. В модели не используется двоичное кодирование команд и это упрощает написание программ для этого компьютера — устройство компьютера можно нарисовать на доске, а программы выполнять на листке бумаги. Думаю, что в 60-х годов ХХ века многие студенты выполняли программы таким образом, но сейчас мы можем написать эмулятор такого компьютера, что я и сделал на AWK.

Исходный код эмулятора и примеры программ: GitHub.

Эмулятор запускается командой:

awk -f lmc.awk

Команды эмулятора:

LOAD ###[ ### ...] - загрузить программу в кодах
DUMP - показать содержимое памяти 
RUN - выполнить программу
ASM <имя файла> - скомпилировать программу на ассемблере и загрузить

Несколько коротких программ:

LOAD 901 902 000 - копируем число с INP в OUT, останавливаемся
LOAD 901 104 902 000 1 - добавляем 1 к числу из INP, пишем в ОUT, останавливаемся
LOAD 901 902 704 600 000 - копируем числа с INP в OUT, и прекращаем работу после печати 0

Пример запуска программы:

LOAD 901 902 0
DUMP
00: 901 902   0   0   0   0   0   0   0   0
10:   0   0   0   0   0   0   0   0   0   0
20:   0   0   0   0   0   0   0   0   0   0
30:   0   0   0   0   0   0   0   0   0   0
40:   0   0   0   0   0   0   0   0   0   0
50:   0   0   0   0   0   0   0   0   0   0
60:   0   0   0   0   0   0   0   0   0   0
70:   0   0   0   0   0   0   0   0   0   0
80:   0   0   0   0   0   0   0   0   0   0
90:   0   0   0   0   0   0   0   0   0   0
RUN
INP:100
OUT:100

Одинаковая длина и простой формат команд позволяет быстро написать ассемблер для этого компьютера. После этого можно писать длинные программы без ручного расчета адресов.

Числа Фибоначчи:

awk -f lmc.awk
asm fib.lma
00: #Print fibonacci numbers
00:     LDA ONE         #Load init values
01:     STA FIB1        #First number
02:     STA FIB2        #Second number
03:     OUT             #Print first
04:     OUT             #Print second
05: LOOP        LDA MAX         #ACC=MAX
06:     SUB FIB1        #ACC=ACC-FIB1
07:     SUB FIB2        #ACC=ACC-FIB2
08:     BRP CONT        #ACC positive ? Continue
09:     BRA END         #Negative : goto end of program
10: CONT        LDA FIB1        #ACC=FIB1
11:     ADD FIB2        #ACC=ACC+FIB2
12:     STA FIBN        #Store FIBN - next number
13:     OUT             #Print it
14:     LDA FIB2        #FIB1=FIB2
15:     STA FIB1
16:     LDA FIBN        #FIB2=FIBN
17:     STA FIB2
18:     BRA LOOP        #Next LOOP
19: END HLT
20: ONE DAT 1           #Init value
21: FIB1        DAT             #First fib number
22: FIB2        DAT             #Second fib number
23: FIBN        DAT             #Next fib number
24: MAX DAT 999         #Max computer number

Labels:
LOOP    05
MAX     24
FIB1    21
FIB2    22
FIBN    23
ONE     20
END     19
CONT    10

Xrefs:
LOOP    18
MAX     5
FIB1    1 6 10 15
FIB2    2 7 11 14 17
FIBN    12 16
ONE     0
END     9
CONT    8

LOAD 520 321 322 902 902 524 221 222 810 619 521 122 323 902 522 321 523 322 605 0 1 0 0 0 999