[recovery mode] Компьютер маленького человечка
Все мы знаем машину Тьюринга и машину Поста. Это абстрактные вычислительные машины, придуманные математиками для теории алгоритмов. Компьютер маленького человечка (Little man computer) — модель компьютера, предназначенная для обучения тому, как устроен и работает компьютер. Эта модель была предложена профессором Стюартом Мэдником в 1965 году и успешно используется для обучения студентов начальных курсов как в области программирования, так и конструирования компьютеров.
Давайте посмотрим на компьютер как на небольшое почтовое отделение.В отделении есть два окошка для общения с внешним миром: в окошко INP поступают, а из окошка OUT выходят листочки с числами.Числа могут быть от 0 до 999. В отделении есть 100 почтовых ящиков, пронумерованных от 0 до 99, из них человечек может брать листочки с трехзначными числами, а также может заменять эти листочки новыми. Также у него есть простой калькулятор (аккумулятор), позволяющий складывать и вычитать трехзначные числа. При обработке чисел на калькуляторе автоматически поднимаются флажки для чисел, равных 0 и больших 0.
Оператор компьютера пишет программу на листочках и кладет их в почтовые ящики, затем устанавливает счетчик команд (PC) в 0 и нажимает кнопку «Начать работу». Внутри почтового отделения человечек обрабатывает листочки с числами, лежащие в почтовых ящиках. Опишем цикл обработки по шагам:
Выбрать число из счетчика команд. Это число — номер почтового ящика. Запомнить число из почтового ящика, номер которого получен на 1 шаге. Увеличить счетчик команд на 1. Разобрать команду (число, полученное на 2 шаге). Выполнить выборку данных из почтового ящика, если это требуется. Выполнить саму команду. Сохранить данные в почтовый ящик, если это требуется. Вернуться к шагу 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
