06.05.2015 21:05
OnoIt 20 23538 Источник
Все мы знаем машину Тьюринга и машину Поста. Это абстрактные вычислительные машины, придуманные математиками для теории алгоритмов. Компьютер маленького человечка (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

Комментарии (20)


  1. MichaelBorisov
    07.05.2015 00:49
    #8408249

    Неплохо, неплохо. Почти минималистский процессор получился. Я так понимаю, что разность поведения при переполнении сложения и вычитания сделана для возможности сравнения произвольных чисел?


    1. OnoIt Автор
      07.05.2015 10:42
      #8408517

      Да, но диапазон чисел ограничен — 0..999.


  1. Pinsky
    07.05.2015 11:08
    #8408539

    Нужно сделать компилятор(ассемблер) и аппаратную реализацию.


    1. OnoIt Автор
      07.05.2015 11:27
      #8408581

      Ассемблер написал. Полагаю, что модель на VHDL или Verilog будет небольшая, но лучше будет перейти на двоичное кодирование.


      1. shpaker
        08.05.2015 08:17
        #8409705

        Да вроде видел такое здесь github.com/PAntoine/Little-Man-Computer


    1. igordata
      07.05.2015 11:38
      #8408603
      +2

      Шутки шутками, а мне вот интересно, сколько нужно транзисторов для реализации этого процессора?..


      1. mambet
        07.05.2015 11:47
        #8408625

        Зачем транзисторов — тогда уж ключей: даёшь процессор на пневмореле!


        1. OnoIt Автор
          07.05.2015 12:07
          #8408657

          Реле ненадежные и медленные. А на лампах будет много электричества есть.


          1. optimizer
            08.05.2015 10:17
            #8409831

            да, в реле жучки могут застревать


      1. Pinsky
        07.05.2015 12:27
        #8408679

        имхо на мелкой логике, в принципе, подъемно)


        1. igordata
          07.05.2015 16:43
          #8409051

          Не ну кто-то разок вроде реализовал проц на транзисторах. Не могу нагуглить к сожалению.


          1. Pinsky
            07.05.2015 18:39
            #8409207

            hackaday.io/project/665-4-bit-computer-built-from-discrete-transistors


            1. igordata
              10.05.2015 01:12
              #8411481

              Круто, спасибо. Хотя я помню что-то большее, чем этот, но суть и масштаб ясны.


              1. Pinsky
                12.05.2015 10:41
                #8413025

                Не единственный подобный проект.


  1. ilrandir
    07.05.2015 11:42
    #8408615
    -5

    Что мешает использовать ассемблер, ограничившись только описанными командами? Редакторов для него дофига, можно сохранять в .com файлы, чтобы проще и даже замутить вывод через int 21. Эмуляторов доса — вагон. Зачем придумывать ассемблер заново?


    1. OnoIt Автор
      07.05.2015 12:04
      #8408651
      +4

      Ассемблер для каждого типа процессоров свой. Названия команд могут совпадать.

      А если посмотреть на год создания модели, то станет ясно, что .com файлы и int 21 будут придуманы через 15 лет.


      1. ilrandir
        07.05.2015 16:00
        #8408953
        -5

        Поэтому вы решили создать еще один велосипед? Ассемблер, в тех командах, которые описаны выше, фактически одинаковый для всех процессоров. int 21 я добавил как простой и понятный способ вывести результат на экран, не придумывая еще один велосипед. Выучив этот псевдоассемблер вам все-равно придется переучиваться под реальный, зачем это делать, если можно тренироваться на реальной модели?


        1. Pinsky
          07.05.2015 16:06
          #8408963

          А кому нужен сейчас int 21h?

          Сейчас ассемблер под DOS носит не менее академический характер, нежели подобные псевдопроцессоры


          1. ilrandir
            11.05.2015 16:13
            #8412353
            -1

            Вы хотите предложить новый int21?


            1. Pinsky
              12.05.2015 10:37
              #8413017

              sysenter/syscall