Эмулятор РАМ-машины


    РАМ-машина — абстрактная вычислительная машина, обладающая полнотой по Тьюрингу, и принадлежащая классу регистровых машин. Она эквивалентна универсальной машине Тьюринга, при этом более наглядна и удобна в доказательстве корректности алгоритмов. В этом топике я расскажу, как она устроена и приложу ссылки на работающую имплементацию эмулятора РАМ-машины с некоторыми интересными примерами.

    Абстрактная модель РАМ-машины (RAM: Random Access Machine) предполагает наличие бесконечного набора регистров, каждый из которых способен хранить целое число любой длины. Индекс регистра может быть любым целым числом (в т.ч. отрицательным). Программа для РАМ-машины — конечный набор инструкций, модифицирующих регистры памяти; можно смотреть на это как на очень простой ассемблер. Изучение машины начнем с рассмотрения набора команд.

    HALT


    Самая простая инструкция, приказывающая машине остановить выполнение по ее достижению.

    READ


    Машина должна поддерживать ввод-вывод, и операция READ предназначена для ввода числа с клавиатуры (или другого потока, однако, не стоит забывать что мы имеем дело с абстрактной моделью, где главное обеспечить ввод данных для алгоритма, чтобы можно было решить массовую задачу). Число вводится в регистр [0], этот регистр и дальше будем считать «особенным».

    WRITE


    Выводит (на экран) число, хранящееся в [0]. Больше никаких аргументов.

    LOAD x / [x] / [[x]]


    Более хитрая инструкция — записывает в [0] произвольное значение. Значение может быть задано константно: LOAD 5, например. Или скопировано из другой ячейки: LOAD [3] — здесь значение из третьего регистра копируется в нулевой. Или же с помощью двойной адресации: LOAD [[3]] — в «ноль» попадет число из регистра, на который «ссылается» третий регистр. Таким образом, видно, что машина поддерживает косвенную адресацию.

    STORE [x] / [[x]]


    Записывает значение из [0] в заданную ячейку. Доступна либо прямая адресация: STORE [1], либо косвенная: STORE [[1]].

    NEG


    Обращает знак числа в [0]. Соответственно -3 будет заменено на 3, ноль знака не имеет.

    LSHIFT x / [x] / [[x]]


    Выполняет побитовый сдвиг влево числа в [0] на указанный аргумент; доступна константа, прямой адрес, косвенный адрес. Например LSHFIT [[3]] умножит значение в [0] на двойку в степени значения регистра, на который ссылается [3].

    RSHIFT x / [x] / [[x]]


    Выполняет побитовый правый сдвиг, аргументы и смысл аналогичны LSHIFT. Классическая модель не допускает использование знаковых чисел в качестве аргументов LSHIFT/RSHIFT.

    ADD x / [x] / [[x]]


    Прибавляет к [0] значение, указанное аргументом функции. Доступна константа, прямая адресация, косвенная.

    Ну и напоследок, пригодится для организации циклов и условий:

    JUMP метка


    Безусловный переход на указанную строку кода или метку.

    JG метка


    Переход на указанную метку, если значение в нулевом регистре строго положительное.

    Вот и все!

    А как же другие арифметические операции? Да, классическая модель не предполагает избыточных инструкций, поэтому их придется реализовывать через сложение. В качестве небольшой головоломки предлагаю реализовать:
    • умножение m на n (быстрее чем за O(max(m,n)));
    • квадрат m (быстрее чем за O(m));
    • степень m (быстрее чем за O(m * log(m)));
    • корень произвольной степени (вспомнить метод Ньютона).

    Более сложной задачей можно считать доказательство оценки сложности и корректности реализации каждого метода (но здесь это куда проще, чем на машине Тьюринга).

    Одним из простейших свойств машины является легкость обнаружения deadlock-состояния (стабильного бесполезного состояния): если при переходе к той же метке значения регистров остались прежними — то мы «зависли».

    Прилагаю пример простейшей программы (надеюсь, самоочевидной), которая суммирует N чисел введенных с клавиатуры (другие примеры в архиве с исполняемым файлом эмулятора):



    Для некоторого разнообразия (если честно, изначально, чтобы «повеселить» детишек в школе) я добавил несколько примитивов (точка и линия) для рисования графических элементов, которыми можно создать что-нибудь забавное. Например:

    image

    Скачать имплементацию можно по этой ссылке, а исходники — здесь. К качеству исходников, как и к языку, на котором они написаны (да, это Delphi) не стоит сильно придираться, я их писал уже много лет назад и сам удивлен, что все работает. Реализация поддерживает длинную арифметику и эмулирует бесконечное число регистров, однако мы знаем, что память физической машины не безгранична :)

    Удачи в попытках!
    Поделиться публикацией

    Похожие публикации

    Комментарии 17
      +2
      Бедные дети. Когда я был 8-ми классником, моих одноклассников приводил в уныние даже QBASIC, а такое может вообще оттолкнуть от изучения предмета и значительно понизить успеваемость по предмету.

      Или под словосочетанием «детишки в школе» Вы имели в виду аудиторию хабра? :)
        +2
        Нет-нет, самые настоящие детишки в школе. Только школа специализированная с «отклонением» в сторону математики, а класс девятый. Те же ребята под выпуск писали довольно сложные трехмерные движки на C++ и Delphi.

        Тут конечно сыграло роль, что к началу курса теории алгоритмической сложности у них уже был некоторый математический аппарат, пределы умели считать уже, так что большинство могло доказать корректность реализации корня, например.
          0
          Это в Питере? Подскажите пожалуйста номер школы, или ее название, свое чадо попытаюсь туда пристроить.
            0
            В Питере. ответил в личку.
              0
              *Подумал про себя «так и создаются судьбы»
                +2
                На самом деле я в 9 классе программировал лучше своего учителя, и кучу вещей, которые дали буст моей карьере, я узнал не в институте и тем более не в школе, а на своих ошибках, некоторые из которых мог бы избежать. Поэтому хочется чтобы мой ребенок не испытывал таких ограничений и имел больше возможностей для развития.
          0
          Ну не знай, я на спекртуме на асме начинал программить и было все в ажуре.
            +2
            Спектрум — очень простая машина, и чтобы под него программировать, не надо обладать хорошей теоретической базой.
              +1
              Раньше выбирать не приходилось, сам на ZX начинал. Главное — желание.
              +1
              Кстати, по опыту, языки вроде BASIC или Pascal куда хуже воспринимаются детьми — слишком много вещей для запоминания (заучивания, а это не все любят/могут). Плюс — сразу научить писать аккуратно (то же именование переменных) невозможно, а переучивать сложно.
              • НЛО прилетело и опубликовало эту надпись здесь
                0
                Интересная машина.
                Умножение у меня получилось на одну команду длиннее, зато использовано только 3 ячейки (кроме главной)
                  0
                  имеется в виду «быстрое» умножение? у меня короче, чем в 19 строк (не считая I/O) не получается…
                  0
                  Да, через сдвиги. Но у меня ввод переплетен с инициализацией:

                  LOAD 0
                  STORE [3]
                  READ
                  STORE [2]
                  READ
                  и дальше главный цикл.

                  Если перемножать уже записанные [1] на [2] и получить результат в [3], то будет тоже 19 команд.
                    +2
                    Я делал что-то подобное. У меня была дипломная работа, в которой я использовал подобную машину, и автоматически, с помощью генетических алгоритмов, составлял для нее программы. Цель такой написанной компьютером программы была — отсортировать массив. Фитнес-функцией для генетического алгоритма была функция, считающая степень отсортированности массива, путем сложения разностей соседних элементов.

                    Эх… были же времена! Кто заинтересовался, вот ссылка на мою дипломную работу: andyceo.ruware.com/blog/andyceo/ispolzovanie-geneticheskikh-algoritmov-v-probleme-avtomaticheskogo-napisaniya-programm

                    Там пояснительная записка и исходники, на delphi. Да, тогда я писал на Паскале :) Можно сразу скачать бинарники и запустить, под Windows XP пойдут без проблем, а в -nix системах успешно используется Wine.
                      0
                      правда только зависание это не deadlock (а скорее starvation), но в целом интересно… можно даже прокинуть «мостик» в формам представления программы в виде single-state-assignment
                        0
                        спасибо, что поделились столь ценной информацией. Времена меняются, а темы дипломов не так быстро=)

                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                        Самое читаемое