Маленький человечек-компьютер

Компьютер Little Man , созданная доктором Стюартом Мэдником (LMC) — учебная модель компьютера в 1965 году. ^[1] LMC обычно используется для обучения студентов, поскольку он моделирует простой компьютер с архитектурой фон Неймана , который обладает всеми основными функциями современного компьютера. Его можно запрограммировать в машинном коде (хотя и в десятичном, а не в двоичном формате) или ассемблерном коде. ^[2]^[3]^[4]

Модель LMC основана на концепции маленького человечка, запертого в закрытой почтовой комнате (аналог компьютера в этом сценарии). В одном конце комнаты есть 100 почтовых ящиков ( память ), пронумерованных от 0 до 99, каждый из которых может содержать трехзначную инструкцию или данные (в диапазоне от 000 до 999). Кроме того, на другом конце есть два почтовых ящика с надписью INBOX и OUTBOX , которые используются для приема и вывода данных. В центре комнаты находится рабочая зона, содержащая простой калькулятор с двумя функциями (сложение и вычитание), известный как аккумулятор , и сбрасываемый счетчик, известный как программный счетчик. Счетчик программ хранит адрес следующей инструкции, которую Маленький Человечек выполнит. Этот счетчик программ обычно увеличивается на 1 после выполнения каждой инструкции, что позволяет маленькому человечку последовательно выполнять программу. Инструкции ветвления итерации (циклы) и структуры условного позволяют включать в программу программирования. Последнее достигается путем установки счетчика программ на непоследовательный адрес памяти, если выполняется определенное условие (обычно значение, хранящееся в аккумуляторе, равно нулю или положительному).

Согласно архитектуре фон Неймана , любой почтовый ящик (обозначающий уникальную ячейку памяти) может содержать либо инструкцию, либо данные. Поэтому необходимо позаботиться о том, чтобы счетчик программ не достиг адреса памяти, содержащего данные, иначе Маленький Человечек попытается воспринять это как инструкцию. Этим можно воспользоваться, записав в почтовые ящики инструкции, предназначенные для интерпретации как кода, для создания самомодифицирующегося кода. Чтобы использовать LMC, пользователь загружает данные в почтовые ящики, а затем дает сигнал «Маленькому человечку» начать выполнение, начиная с инструкции, хранящейся по нулевому адресу памяти. Сброс счетчика программ на ноль фактически перезапускает программу, хотя и в потенциально другом состоянии.

Цикл исполнения [ править ]

Чтобы выполнить программу, человечек выполняет следующие действия:

Проверьте счетчик программ на наличие номера почтового ящика, содержащего инструкцию программы (т. е. ноль в начале программы).
Получите инструкцию из почтового ящика с этим номером. Каждая инструкция содержит два поля: код операции (указывает операцию, которую необходимо выполнить) и поле адреса (указывает, где найти данные для выполнения операции).
Увеличьте счетчик программ (чтобы он содержал номер почтового ящика следующей инструкции)
Расшифруйте инструкцию. Если инструкция использует данные, хранящиеся в другом почтовом ящике, используйте поле адреса, чтобы найти номер почтового ящика для данных, с которыми она будет работать, например «получить данные из почтового ящика 42»).
Получить данные (из входа, аккумулятора или почтового ящика с адресом, определенным на шаге 4)
Выполнить инструкцию на основе заданного кода операции
Разветвить или сохранить результат (в выходных данных, аккумуляторе или почтовом ящике с адресом, определенным на шаге 4).
Вернитесь к счетчику программ, чтобы повторить цикл или остановиться.

Команды [ править ]

Хотя LMC действительно отражает фактическую работу двоичных процессоров, простота десятичных чисел была выбрана, чтобы минимизировать сложность для студентов, которым может быть неудобно работать с двоичными/ шестнадцатеричными числами .

Инструкция [ править ]

Некоторые симуляторы LMC программируются напрямую с использованием трехзначных числовых инструкций, а некоторые используют трехбуквенные мнемонические коды и метки. В любом случае набор инструкций намеренно очень ограничен (обычно около десяти инструкций), чтобы упростить понимание. Если LMC использует мнемонические коды и метки, то при сборке программы они преобразуются в трехзначные числовые инструкции.

В таблице ниже показан типичный набор числовых команд и эквивалентные мнемонические коды.

Инструкции
Числовой код	Мнемонический код	Инструкция	Описание
1хх	ДОБАВЛЯТЬ	ДОБАВЛЯТЬ	Добавьте значение, хранящееся в почтовом ящике xx, к любому значению, которое в данный момент находится в аккумуляторе (калькуляторе). Примечание: содержимое почтового ящика не изменяется, а действия аккумулятора (калькулятора) не определяются для инструкций сложения, вызывающих суммы, превышающие 3 цифры. Как и в случае с ВЫЧИТАНИЕМ, можно установить отрицательный флаг при переполнении.
2хх	СУБ	ВЫЧИТАТЬ	Вычтите значение, хранящееся в почтовом ящике xx, из любого значения, которое в данный момент находится в аккумуляторе (калькуляторе). Примечание: содержимое почтового ящика не изменяется, а действия аккумулятора не определяются для инструкций вычитания, вызывающих отрицательные результаты, однако будет установлен отрицательный флаг, чтобы 7xx (BRZ) и 8xx (BRP). можно было использовать правильно.
3хх	СТА	МАГАЗИН	Сохраните содержимое аккумулятора в почтовом ящике xx (деструктивно). Примечание: содержимое аккумулятора (калькулятора) не изменяется (неразрушающее), а содержимое почтового ящика заменяется независимо от того, что там находилось (разрушающее).
5хх	LDA	НАГРУЗКА	Загрузите значение из почтового ящика xx (неразрушающий метод) и введите его в аккумулятор (разрушающий метод).
6хх	ХОРОШИЙ	ВЕТВИТЬ ВСЕГДА (безусловно)	Установите программный счетчик по заданному адресу (значение xx). То есть значение в почтовом ящике xx будет следующей выполняемой инструкцией.
7хх	БРЗ	РАЗВЕТВЛЕНИЕ ЕСЛИ НОЛЬ ( условно )	Если аккумулятор (калькулятор) содержит значение 000, установите счетчик программы на значение xx. В противном случае ничего не делайте. Учитывается ли отрицательный флаг, не определено. Когда команда SUBTRACT опустошает аккумулятор, этот флаг устанавливается, после чего аккумулятор становится неопределенным, потенциально равным нулю, что приводит к неопределенному поведению BRZ при опустошении аккумулятора. Предлагаемое поведение — разветвление, если аккумулятор равен нулю и отрицательный флаг не установлен. Примечание: поскольку программа хранится в памяти, все данные и инструкции программы имеют одинаковый формат адреса/места.
8хх	БРП	РАЗВЕТВЛЕНИЕ ЕСЛИ ПОЛОЖИТЕЛЬНО (условно)	Если аккумулятор (калькулятор) равен 0 или положителен, установите счетчик программы на значение xx. В противном случае ничего не делайте. Поскольку ячейки памяти LMC могут хранить значения только от 0 до 999, эта инструкция зависит исключительно от отрицательного флага, установленного при опустошении команды SUBTRACT и, возможно, при переполнении при ADD (неопределено). Примечание: поскольку программа хранится в памяти, все данные и инструкции программы имеют одинаковый формат адреса/места.
901	ИЯФ	ВХОД	Перейдите в папку «Входящие», получите значение от пользователя и поместите его в аккумулятор (калькулятор). Примечание. Это приведет к перезаписи любого значения, которое было в аккумуляторе (разрушающее действие).
902	ВНЕ	ВЫХОД	Скопируйте значение из аккумулятора (калькулятора) в папку «ИСХОДЯЩИЕ». Примечание: содержимое аккумулятора не изменяется (неразрушающе).
000	HLT/COB	ОСТАНОВКА/КОФЕ-БРЕЙК	Прекратить работу/завершить программу.
	ЧТО	ДАННЫЕ	Это инструкция ассемблера , которая просто загружает значение в следующий доступный почтовый ящик. DAT также можно использовать вместе с метками для объявления переменных. Например, DAT 984 сохранит значение 984 в почтовом ящике по адресу инструкции DAT.

Примеры [ править ]

Использование числовых кодов инструкций [ править ]

Эта программа (инструкции с 901 по 000 ) написана только с использованием числовых кодов. Программа принимает на вход два числа и выводит разницу. Обратите внимание, что выполнение начинается в почтовом ящике 00 и заканчивается в почтовом ящике 07. Недостатки программирования LMC с использованием числовых кодов команд обсуждаются ниже.

Почтовый ящик	Числовой код	Операция	Комментарии
00	901	Аккумулятор = Входящие	ВВЕДИТЕ первое число, войдите в калькулятор (стирая все, что там было)
01	308	Почтовый ящик 08 = Аккумулятор	СОХРАНИТЕ текущее значение калькулятора (чтобы подготовиться к следующему шагу…)
02	901	Аккумулятор = Входящие	ВВЕДИТЕ второе число, войдите в калькулятор (стирая все, что там было)
03	309	Почтовый ящик 09 = Аккумулятор	СОХРАНИТЕ текущее значение калькулятора (опять же, чтобы подготовиться к следующему шагу…)
04	508	Аккумулятор = Почтовый ящик 08	(Теперь, когда оба значения ВХОДА СОХРАНЕНЫ в почтовых ящиках 08 и 09…) ЗАГРУЗИТЬ первое значение обратно в калькулятор (стирая все, что там было)
05	209	Аккумулятор = Аккумулятор — Почтовый ящик 09	ВЫЧИТАЙТЕ второе число из текущего значения калькулятора (которое только что было установлено на первое число)
06	902	Исходящие = накопитель	ВЫВОД результата калькулятора в OUTBOX
07	000	Останавливаться	ОСТАНОВИТЕ БМО

Использование мнемоники и меток [ править ]

Язык ассемблера — это язык программирования низкого уровня, в котором вместо числовых кодов команд используются мнемоники и метки. Хотя LMC использует только ограниченный набор мнемоник, удобство использования мнемоники для каждой инструкции становится очевидным из языка ассемблера той же программы, показанного ниже - программисту больше не требуется запоминать набор анонимных числовых кодов, и он может теперь программа с набором более запоминающихся мнемонических кодов. Если мнемоника представляет собой инструкцию, которая включает адрес памяти ( либо инструкцию ветвления, либо загрузку/сохранение данных ), то для обозначения адреса памяти используется метка.

INP
STA FIRST
INP
STA SECOND
LDA FIRST
SUB SECOND
OUT
HLT
FIRST DAT
SECOND DAT

Этикетки [ править ]

Без меток программисту придется вручную рассчитывать почтовых ящиков ( памяти адреса ). В примере с числовым кодом , если новая инструкция должна быть вставлена перед последней инструкцией HLT, то эта инструкция HLT переместится с адреса 07 на адрес 08 (маркировка адреса начинается с адреса 00). Предположим, что пользователь ввел 600 в качестве первого ввода. Инструкция 308 будет означать, что это значение будет сохранено по адресу 08 и перезапишет инструкцию 000 (HLT). Поскольку 600 означает «перейти к почтовому ящику с адресом 00», программа вместо остановки застрянет в бесконечном цикле.

Чтобы обойти эту трудность, большинство языков ассемблера ( включая LMC ) комбинируют мнемонику с метками . Метка — это просто слово, которое используется либо для обозначения адреса памяти, где хранится инструкция или данные, либо для ссылки на этот адрес в инструкции.

Когда программа собрана:

Метка слева от мнемоники инструкции преобразуется в адрес памяти, по которому хранится инструкция или данные. т.е. запуск цикла INP
Метка справа от мнемоники инструкции принимает значение адреса памяти, упомянутого выше. т.е. запуск петли BRA
Метка в сочетании с оператором DAT работает как переменная: она обозначает адрес памяти, по которой хранятся данные. т.е. один DAT 1 или номер 1 DAT

В на ассемблере примере , где используются мнемоники и метки, если новая инструкция была вставлена перед последней инструкцией HLT, то адрес, помеченный как FIRST, теперь будет находиться в ячейке памяти 09, а не в 08, и инструкция STA FIRST будет преобразована в 309 (STA 09), а не 308 (STA 08) при сборке программы.

Таким образом, этикетки используются для:

определить конкретную инструкцию как цель для инструкции BRANCH.
определить ячейку памяти как именованную переменную (используя DAT) и, при необходимости, загрузить данные в программу во время сборки для использования программой (это использование не очевидно, пока не будет учтено, что нет способа добавить 1 к счетчику. Можно было бы попросите пользователя ввести 1 вначале, но было бы лучше загрузить это во время сборки, используя один DAT 1 )

Пример [ править ]

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

     INP
     OUT      // Initialize output 
LOOP BRZ QUIT // Label this memory address as LOOP. If the accumulator value is 0, jump to the memory address labeled
              // QUIT
     SUB ONE  // Subtract the value stored at address ONE from the accumulator
     OUT
     BRA LOOP // Jump (unconditionally) to the memory address labeled LOOP
QUIT HLT      // Label this memory address as QUIT
ONE  DAT 1    // Store the value 1 in this memory address, and label it ONE (variable declaration)

Программа, приведенная ниже, примет введенные пользователем данные, возведет их в квадрат, выведет ответ и затем повторит. Ввод нуля завершит программу.
( Примечание: ввод, результатом которого является значение больше 999, будет иметь неопределенное поведение из-за ограничения LMC на 3-значное число ).

START   LDA ZERO     // Initialize for multiple program run
        STA RESULT
        STA COUNT
        INP          // User provided input
        BRZ END      // Branch to program END if input = 0
        STA VALUE    // Store input as VALUE
LOOP    LDA RESULT   // Load the RESULT
        ADD VALUE    // Add VALUE, the user provided input, to RESULT
        STA RESULT   // Store the new RESULT
        LDA COUNT    // Load the COUNT
        ADD ONE      // Add ONE to the COUNT
        STA COUNT    // Store the new COUNT
        SUB VALUE    // Subtract the user provided input VALUE from COUNT
        BRZ ENDLOOP  // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP
        BRA LOOP     // Branch to LOOP to continue adding VALUE to RESULT
ENDLOOP LDA RESULT   // Load RESULT
        OUT          // Output RESULT
        BRA START    // Branch to the START to initialize and get another input VALUE
END     HLT          // HALT - a zero was entered so done!
RESULT  DAT          // Computed result (defaults to 0)
COUNT   DAT          // Counter (defaults to 0)
ONE     DAT 1        // Constant, value of 1
VALUE   DAT          // User provided input, the value to be squared (defaults to 0)
ZERO    DAT          // Constant, value of 0 (defaults to 0)

Примечание. Если после оператора DAT нет данных, то по адресу памяти сохраняется значение по умолчанию 0.

В приведенном выше примере [BRZ ENDLOOP] зависит от неопределенного поведения, поскольку COUNT-VALUE может быть отрицательным, после чего значение ACCUMULATOR становится неопределенным, в результате чего BRZ либо разветвляется, либо нет (ACCUMULATOR может быть нулевым или округленным). Чтобы сделать код совместимым со спецификацией, замените:

        ...
        LDA COUNT    // Load the COUNT
        ADD ONE      // Add ONE to the COUNT
        STA COUNT    // Store the new COUNT
        SUB VALUE    // Subtract the user provided input VALUE from COUNT
        BRZ ENDLOOP  // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP
        ...

со следующей версией, которая оценивает VALUE-COUNT вместо COUNT-VALUE, гарантируя, что аккумулятор никогда не опустеет:

        ...
        LDA COUNT    // Load the COUNT
        ADD ONE      // Add ONE to the COUNT
        STA COUNT    // Store the new COUNT
        LDA VALUE    // Load the VALUE
        SUB COUNT    // Subtract COUNT from the user provided input VALUE
        BRZ ENDLOOP  // If zero (VALUE has been added to RESULT by VALUE times), branch to ENDLOOP
        ...

Другой пример — quine , печатающий собственный машинный код (вывод исходного кода невозможен, поскольку буквы не могут быть выведены):

LOAD LDA 0     // Load position 0 into the accumulator. This line will be modified on each loop to load the next lines into the accumulator
     OUT       // Output the accumulator's value. The accumulator's value will be the line that was just loaded
     SUB ONE   // Subtract 1 from the value in the accumulator. This is so we can do the BRZ in the next step to see if we are on the last line in the program
     BRZ ONE   // If the previous subtraction has made the accumulator 0 (which means we had the value 001 in the accumulator), then branch to position ONE
     LDA LOAD  // Load the LOAD position into the accumulator, this is in preparation to increment the address digits for this position
     ADD ONE   // Increment the position digits for the LOAD line. The value currently in the accumulator would, if read as an instruction, load the next line into the accumulator, compared to the last line loaded
     STA LOAD  // Store the newly incremented LOAD line back in the LOAD position
     BRA LOAD  // Return to the beginning of the loop
ONE  DAT 1     // The variable ONE. If read as an instruction, this will be interpreted as HLT/COB and will end the program

Этот куайн работает с использованием самомодифицирующегося кода . Позиция 0 увеличивается на единицу в каждой итерации, выводя код этой строки, пока код, который она выводит, не станет равным 1, после чего он переходит в позицию ONE. Значение в позиции ONE имеет 0 в качестве кода операции, поэтому оно интерпретируется как инструкция HALT/COB.

См. также [ править ]

КАРТОННОЕ Иллюстративное пособие по вычислениям (еще одна учебная модель)
ТИС-100 (видеоигра)
Human Resource Machine — компьютерная игра, на которую сильно повлиял LMC.
Бумажный компьютер WDR
Диги-Комп I
Little Man Stack Machine — расширение LMC со специальными инструкциями по стеку.
Питера Хиггинсона Онлайн-эмулятор LMC .

Ссылки [ править ]

^ «Маленький человек-компьютер» . Государственный университет Иллинойса . 1 мая 2000 года. Архивировано из оригинала 27 февраля 2009 года . Проверено 8 марта 2009 г.
^ Юрчик, В.; Осборн, Х. (2001). «Толпа маленьких человечков-компьютеров: средства обучения визуальным компьютерным симуляторам». Материалы зимней конференции по моделированию 2001 г. (кат. № 01CH37304) . Том. 2. п. 1632. дои : 10.1109/WSC.2001.977496 . ISBN 0-7803-7307-3 . S2CID 18907923 .
^ Юрчик, В.; Брамбо, Л. (2001). «Сетевой компьютерный симулятор маленького человечка». Материалы тридцать второго технического симпозиума SIGCSE по компьютерному образованию - SIGCSE '01 . п. 204. дои : 10.1145/364447.364585 . ISBN 1581133294 . S2CID 14794750 .
^ Осборн, Х.; Юрчик, В. (2002). «Образовательный диапазон визуального моделирования парадигмы компьютерной архитектуры Little Man». 32-я ежегодная выставка «Границы образования» . стр. S4G–S19. дои : 10.1109/FIE.2002.1158742 . ISBN 0-7803-7444-4 . S2CID 10324295 .

Внешние ссылки [ править ]

Симуляторы [ править ]

Онлайн [ править ]

[1] «Маленький человек-компьютер» . Государственный университет Иллинойса . 1 мая 2000 года. Архивировано из оригинала 27 февраля 2009 года . Проверено 8 марта 2009 г.

[2] Юрчик, В.; Осборн, Х. (2001). «Толпа маленьких человечков-компьютеров: средства обучения визуальным компьютерным симуляторам». Материалы зимней конференции по моделированию 2001 г. (кат. № 01CH37304) . Том. 2. п. 1632. дои : 10.1109/WSC.2001.977496 . ISBN 0-7803-7307-3 . S2CID 18907923 .

[3] Юрчик, В.; Брамбо, Л. (2001). «Сетевой компьютерный симулятор маленького человечка». Материалы тридцать второго технического симпозиума SIGCSE по компьютерному образованию - SIGCSE '01 . п. 204. дои : 10.1145/364447.364585 . ISBN 1581133294 . S2CID 14794750 .

[4] Осборн, Х.; Юрчик, В. (2002). «Образовательный диапазон визуального моделирования парадигмы компьютерной архитектуры Little Man». 32-я ежегодная выставка «Границы образования» . стр. S4G–S19. дои : 10.1109/FIE.2002.1158742 . ISBN 0-7803-7444-4 . S2CID 10324295 .

[1]

[2]

[3]

[4]