Все мы знаем машину Тьюринга и машину Поста. Это абстрактные вычислительные машины, придуманные математиками для теории алгоритмов. Компьютер маленького человечка (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
ссылка на оригинал статьи http://habrahabr.ru/post/257331/
Добавить комментарий