Абстрактная машина
В информатике абстрактная машина — это теоретическая модель, позволяющая провести подробный и точный анализ функционирования компьютерной системы. [1] Она похожа на математическую функцию в том, что она получает входные данные и производит выходные данные на основе заранее определенных правил. Абстрактные машины отличаются от обычных машин тем, что от них ожидается правильная работа и независимо от аппаратного обеспечения . [2] Абстрактные машины являются « машинами шаг за шагом », потому что они позволяют выполнять программы ; они « абстрактны », поскольку игнорируют многие аспекты реальных ( аппаратных ) машин. [3] Типичная абстрактная машина состоит из определения ввода, вывода и набора допустимых операций, используемых для превращения первого во второе. Их можно использовать по чисто теоретическим причинам, а также в качестве моделей для реальных компьютерных систем. [2] В теории вычислений абстрактные машины часто используются в мысленных экспериментах, касающихся вычислимости или для анализа сложности алгоритмов . [3] Такое использование абстрактных машин имеет фундаментальное значение для области теории сложности вычислений , таких как конечные автоматы , машины Мили , автоматы с выталкиванием вниз и машины Тьюринга . [4]
Классификация [ править ]
Абстрактные машины обычно делятся на два типа в зависимости от количества операций, которые они могут выполнять одновременно в любой момент: детерминированные абстрактные машины и недетерминированные абстрактные машины . [2] Детерминированная . абстрактная машина — это система, в которой определенное начальное состояние или условие всегда дает одни и те же результаты В том, как входные данные преобразуются в выходные, нет случайности или различий. [5] Напротив, недетерминированная абстрактная машина может предоставлять разные выходные данные для одного и того же ввода при разных исполнениях. [2] В отличие от детерминированного алгоритма, который дает один и тот же результат для одних и тех же входных данных независимо от количества итераций, недетерминированный алгоритм использует разные пути для получения разных выходных данных. [6] Недетерминированные алгоритмы полезны для получения приблизительных ответов, когда получение точного решения с использованием детерминированного подхода затруднено или дорого. [7]
Например, машины Тьюринга являются одними из наиболее фундаментальных абстрактных машин в информатике. [2] Эти машины выполняют операции с лентой (строкой символов) любой длины. Их инструкции предусматривают как модификацию символов, так и изменение символа, на котором в данный момент находится указатель машины. Например, элементарная машина Тьюринга могла иметь одну команду «преобразовать символ в 1, затем двигаться вправо», и эта машина выдавала бы только строку из единиц. [8] Эта базовая машина Тьюринга является детерминированной; однако также могут быть построены недетерминированные машины Тьюринга , которые могут выполнять несколько действий при одних и тех же входных данных. [2]
Реализация [ править ]
Любая реализация абстрактной машины в случае физической реализации (аппаратной ) использует какое-то физическое устройство (механическое или электронное) для выполнения инструкций языка программирования . Однако абстрактная машина также может быть реализована в программном обеспечении или встроенном программном обеспечении на уровнях между абстрактной машиной и базовым физическим устройством. [9]
- Аппаратная реализация . Непосредственная реализация абстрактной машины в аппаратном обеспечении заключается в использовании физических устройств, таких как память , арифметические и логические схемы , шины и т. д., для реализации физической машины, машинный язык которой совпадает с языком программирования . После постройки такую машину будет практически трудно изменить. [9] ЦП конструкцию можно рассматривать как конкретную аппаратную реализацию абстрактной машины, в частности, процессора . [10]
- Моделирование с использованием программного обеспечения . Реализация абстрактной машины с помощью программного обеспечения влечет за собой написание программ на другом языке для реализации структур данных и алгоритмов, необходимых абстрактной машине. Это обеспечивает максимальную гибкость, поскольку программы, реализующие абстрактные машинные конструкции, можно легко изменить. [9] Абстрактная машина, реализованная как программная симуляция или для которой существует интерпретатор , называется виртуальной машиной . [11]
- Эмуляция с использованием встроенного ПО . Реализация встроенного ПО находится между аппаратной и программной реализацией. Он состоит из микрокодового моделирования структур данных и алгоритмов для абстрактных машин. [9] Микрокод позволяет программисту писать машинные инструкции без необходимости изготовления электрических схем . [12]
Реализация языка программирования [ править ]
Абстрактная машина интуитивно представляет собой просто абстракцию идеи физического компьютера. [13] Для фактического выполнения алгоритмы должны быть должным образом формализованы с использованием конструкций, предлагаемых языком программирования . Это означает, что выполняемые алгоритмы должны быть выражены с использованием инструкций языка программирования. [3] Синтаксис языка программирования позволяет создавать программы с использованием конечного набора конструкций, известных как инструкции. Большинство абстрактных машин имеют общее хранилище программ и состояние , которое часто включает в себя стек и регистры. [9] [14] В цифровых компьютерах стек — это просто блок памяти с адресным регистром, который может считать только положительные целые числа (после загрузки в него начального значения). Адресный регистр стека называется указателем стека, поскольку его значение всегда относится к верхнему элементу стека. [15] Программа состоит из серии инструкций с указателем стека , указывающим следующую команду, которую необходимо выполнить. Когда инструкция завершена, указатель стека перемещается вперед. Этот фундаментальный механизм управления абстрактной машиной также известен как цикл выполнения . [3] Таким образом, абстрактная машина для языка программирования — это любая совокупность структур данных и алгоритмов, способных хранить и запускать программы, написанные на этом языке программирования. Он устраняет разрыв между высоким уровнем языка программирования и низким уровнем реальной машины, обеспечивая промежуточный этап компиляции языка . Инструкции абстрактной машины адаптированы к уникальным операциям, необходимым для реализации операций определенного исходного языка или набора исходных языков. [9]
Императивные языки [ править ]
В конце 1950-х годов Ассоциация вычислительной техники (ACM) и другие родственные организации разработали множество предложений по универсальному компьютерно-ориентированному языку (UNCOL) , например, машину Конвея . Концепция UNCOL хороша, но она не получила широкого распространения из-за плохой производительности генерируемого кода . Во многих областях вычислений его производительность по-прежнему будет проблемой, несмотря на разработку виртуальной машины Java в конце 1990-х годов. Объектный код Алгола (1964 г.), P4-машина (1976 г.), P-машина UCSD (1977 г.) и Forth (1970 г.) - некоторые успешные абстрактные машины такого типа. [3]
Объектно-ориентированные языки [ править ]
Абстрактные машины для объектно-ориентированных языков программирования часто основаны на стеке и имеют специальные инструкции доступа к полям и методам объекта . В этих машинах управление памятью часто неявно выполняется сборщиком мусора (функция восстановления памяти, встроенная в языки программирования). [16] Smalltalk-80 (1980), Self (1989) и Java (1994) являются примерами этой реализации. [3]
Языки обработки строк [ править ]
Язык обработки строк — это компьютерный язык, который фокусируется на обработке строк, а не чисел. существовали языки обработки строк в виде командных оболочек , инструментов программирования , макропроцессоров и языков сценариев . На протяжении десятилетий [17] Использование подходящей абстрактной машины имеет два преимущества: повышенную скорость выполнения и улучшенную переносимость. Snobol4 и ML/I — два примечательных примера ранних языков обработки строк, которые используют абстрактную машину для достижения машинной независимости. [3]
Языки функционального программирования [ править ]
Ранние абстрактные машины для функциональных языков , включая машину SECD (1964) и функциональную абстрактную машину Карделли (1983), определяли строгую оценку, также известную как нетерпеливая оценка или оценка по вызову . [3] в котором аргументы функции оцениваются перед вызовом и ровно один раз. В последнее время большинство исследований было посвящено ленивой оценке (или оценке по мере необходимости) . [18] такие как G-машина (1984 г.), машина Кривина (1985 г.) и машина с тремя инструкциями (1986 г.), в которых аргументы функции оцениваются только в случае необходимости и не более одного раза. Одна из причин заключается в том, что эффективная реализация строгой оценки теперь хорошо понята, поэтому необходимость в абстрактной машине уменьшилась. [3]
Логические языки [ править ]
Исчисление предикатов (логика первого порядка) является основой языков логического программирования . Самый известный язык логического программирования — Пролог . Правила в Прологе написаны в едином формате, известном как «предложения Хорна» с универсальной количественной оценкой, что означает начало вычислений, направленных на обнаружение доказательства цели. Абстрактная машина Уоррена WAM (1983), [3] который стал фактическим стандартом компиляции программ на Прологе, был в центре внимания большинства исследований. Он предоставляет инструкции специального назначения, такие как инструкции по объединению данных и инструкции потока управления для поддержки обратного отслеживания (алгоритма поиска). [19]
Структура [ править ]
Общая абстрактная машина состоит из памяти и интерпретатора . Память используется для хранения данных и программ, а интерпретатор — это компонент, выполняющий инструкции, включенные в программы. [9]
Интерпретатор должен выполнять операции, уникальные для языка, который он интерпретирует. Однако, учитывая разнообразие языков, можно определить категории операций и « механизм выполнения », общий для всех интерпретаторов. Операции интерпретатора и сопутствующие структуры данных делятся на следующие категории: [9] [20]
- Операции по обработке примитивных данных :
- Операции и структуры данных для управления последовательностью выполнения операций ;
- Операции и структуры данных для управления передачей данных ;
- Операции и структуры данных для управления памятью .
Обработка примитивных данных [ править ]
Абстрактная машина должна содержать операции для управления примитивными типами данных, такими как строки и целые числа. [9] Например, целые числа почти повсеместно считаются базовым типом данных как для физических абстрактных машин, так и для абстрактных машин, используемых во многих языках программирования . Машина выполняет необходимые арифметические операции , такие как сложение и умножение, за один временной шаг. [21]
Последовательность управления [ править ]
Операции и структуры «управления последовательностью» позволяют управлять потоком выполнения программных инструкций. При выполнении определенных условий необходимо изменить типичный последовательный порядок выполнения программы. [9] Поэтому интерпретатор использует структуры данных (например, те, которые используются для хранения адреса следующей выполняемой команды), которые изменяются операциями, отличными от тех, которые используются для манипулирования данными (например, операциями по обновлению адреса следующей выполняемой команды). ). [22]
Контроль передачи данных [ править ]
Операции передачи данных используются для управления тем, как операнды и данные передаются из памяти в интерпретатор и наоборот. Эти операции связаны с хранилищем и порядком извлечения операндов из хранилища. [9]
Управление памятью [ править ]
Управление памятью связано с операциями, выполняемыми в памяти для размещения данных и приложений. В абстрактной машине данные и программы могут храниться неопределенно долго, а в случае языков программирования память может выделяться или освобождаться с использованием более сложного механизма. [9]
Иерархии [ править ]
 | Этот раздел в значительной степени или полностью опирается на один источник . ( январь 2023 г. ) |
Часто используются абстрактные иерархии машин, в которых каждая машина использует функциональность уровня, расположенного непосредственно ниже, и добавляет собственные дополнительные функции для соответствия уровню непосредственно выше. Аппаратный компьютер , состоящий из физических электронных устройств, может быть добавлен на самом базовом уровне. абстрактный уровень микропрограммной машины Выше этого уровня может быть введен . Абстрактная машина, поставляемая операционной системой , которая реализована программой, написанной на машинном языке , расположена непосредственно над аппаратным обеспечением (или непосредственно над аппаратным обеспечением , если прошивки там нет уровня ). С одной стороны, операционная система расширяет возможности физической машины, предоставляя примитивы более высокого уровня, недоступные на физической машине (например, примитивы, действующие с файлами). Хост -машина представляет собой абстрактную машину, заданную операционной системой, на которой язык программирования высокого уровня реализован с использованием промежуточной машины , такой как виртуальная машина Java и ее язык байт-кода. Уровень, заданный абстрактной машиной для язык высокого уровня (например, Java) обычно не является последним уровнем иерархии. На этом этапе могут быть представлены одно или несколько приложений, которые вместе предоставляют дополнительные услуги. Например, можно добавить уровень «веб-машины» для реализации функций, необходимых для управления веб-коммуникациями ( протоколы связи или представление HTML-кода ). Уровень « Веб-сервис » расположен выше этого уровня и обеспечивает функциональные возможности, необходимые для взаимодействия веб-сервисов, как с точки зрения протоколов взаимодействия, так и поведения задействованных процессов. На этом уровне могут быть разработаны совершенно новые языки, определяющие поведение так называемых «бизнес-процессов» на основе веб-сервисов (примером является язык выполнения бизнес-процессов ). Наконец, на самом высоком уровне можно найти специализированное приложение (например, «Электронная коммерция» ), имеющее весьма специфичный и ограниченный функционал. [9]
См. также [ править ]
- Абстрактная интерпретация - Подход к статическому анализу программ
- Массовая синхронная параллель — модель для разработки параллельных алгоритмов.
- Дискретное время — основы моделирования переменных, которые изменяются с течением времени.
- Таксономия Флинна - Классификация компьютерных архитектур
- Формальные модели вычислений – способность эффективно решать проблемы.
- Модель вычислений - математическая модель, описывающая, как вычисляется выходной сигнал функции с учетом входных данных.
- Параллельная машина с произвольным доступом – абстрактный компьютер для разработки параллельных алгоритмов. , стандартная модель де-факто.
- SECD-машина - цель виртуальной и абстрактной машины для компилятора языка функционального программирования.
- Пространство состояний — набор всех возможных значений системы.
Ссылки [ править ]
- ^ Вайсштейн, Эрик В. «Абстрактная машина» . mathworld.wolfram.com . Проверено 16 мая 2022 г.
- ^ Перейти обратно: а б с д Это ж «Что такое абстрактная машина?» . EasyTechJunkie . Проверено 16 мая 2022 г.
- ^ Перейти обратно: а б с д Это ж г час я дж Диль, Стефан; Хартель, Питер; Сестофт, Питер (май 2000 г.). «Абстрактные машины для реализации языков программирования» . Компьютерные системы будущего поколения . 16 (7): 739–751. дои : 10.1016/S0167-739X(99)00088-6 .
- ^ «9.1.1: Обзор конечного автомата» . Инженерные свободные тексты . 29 апреля 2021 г. Проверено 31 мая 2022 г.
- ^ «Что такое детерминированная система? - Определение из Techopedia» . Techopedia.com . 29 августа 2019 года . Проверено 30 мая 2022 г.
- ^ Стернс, Ричард Э. (январь 2003 г.). «Детерминированное и недетерминированное время и проблемы с нижней границей» . Журнал АКМ . 50 (1): 91–95. дои : 10.1145/602382.602409 . ISSN 0004-5411 . S2CID 2194820 .
- ^ Армони, Михал; Галь-Эзер, Джудит (декабрь 2007 г.). «Недетерминизм: абстрактное понятие в исследованиях информатики» . Компьютерное образование . 17 (4): 243–262. Бибкод : 2007CSEd...17..243A . дои : 10.1080/08993400701442885 . ISSN 0899-3408 . S2CID 41928460 .
- ^ Гилл, Джон (декабрь 1977 г.). «Вычислительная сложность вероятностных машин Тьюринга» . SIAM Journal по вычислительной технике . 6 (4): 675–695. дои : 10.1137/0206049 . ISSN 0097-5397 .
- ^ Перейти обратно: а б с д Это ж г час я дж к л м Габбриелли, Маурицио; Мартини, Симона (2010), «Абстрактные машины» , Языки программирования: принципы и парадигмы , Лондон: Springer London, стр. 1–25, doi : 10.1007/978-1-84882-914-5_1 , ISBN 978-1-84882-913-8 , получено 16 мая 2022 г.
- ^ Баир, Рэй; Чиен, Эндрю; Кук, Джанин; Донофрио, Дэйв; Грайдер, Гэри; Кун, Джефф; Мур, Ширли; Шальф, Джон; Веттер, Джефф (01 февраля 2018 г.). Оценка оборудования: абстрактные модели машин и прокси-архитектуры для экзафлопсных вычислений (технический отчет). Управление научно-технической информации Министерства энергетики США. дои : 10.2172/1733300 . ОСТИ 1733300 .
- ^ «абстрактная машина от FOLDOC» . Foldoc.org . Проверено 7 августа 2021 г.
- ^ Ну и дела, Дж.; Мелвин, Юго-Запад; Патт, Ю.Н. (1986). «Реализация Пролога через микрокод VAX 8600» . Материалы 19-го ежегодного семинара по микропрограммированию . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 68–74. дои : 10.1145/19551.19538 . ISBN 081860736X . S2CID 3846072 .
- ^ «абстрактная машина» . Оксфордский справочник . Проверено 16 мая 2022 г.
- ^ Гарсиа-Мартин, Хулио Мануэль; Сутиль-Мартин, Мигель (15 августа 1999 г.). «Абстрактная машина: образец проектирования абстрактных машин» (PDF) . Труды по шаблонным языкам программ '99 .
- ^ upscfever.com (25 января 2017 г.). «Компьютерная организация и архитектура (стековая организация) — UPSC FEVER» . upscfever.com . Проверено 31 мая 2022 г.
- ^ «Что такое объектно-ориентированное программирование (ООП)?» . Архитектура приложения поиска . Проверено 31 мая 2022 г.
- ^ «Аспекты проектирования языков обработки строк» , Исследование языков обработки строк , Конспект лекций по информатике, том. 205, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 17–37, 1985, doi : 10.1007/3-540-16041-8_2 , ISBN 978-3-540-16041-0 , получено 31 мая 2022 г.
- ^ Хакетт, Дженнифер; Хаттон, Грэм (26 июля 2019 г.). «Призыв по нужде – это ясновидящий призыв по значению» . Труды ACM по языкам программирования . 3 (ICFP): 1–23. дои : 10.1145/3341718 . ISSN 2475-1421 . S2CID 195782686 .
- ^ «Пролог | Введение» . Гики для Гиков . 26 мая 2018 г. Проверено 31 мая 2022 г.
- ^ Аккаттоли, Бениамино; Баренбаум, Пабло; Мацца, Дамиано (26 ноября 2014 г.). «Дистилляция абстрактных машин» . Уведомления ACM SIGPLAN . 49 (9): 363–376. дои : 10.1145/2692915.2628154 . ISSN 0362-1340 . S2CID 234775413 .
- ^ баелдунг (11 января 2018 г.). «Введение в примитивы Java | Baeldung» . www.baeldung.com . Проверено 31 мая 2022 г.
- ^ «Интерпретатор» , «Шаблоны проектирования архитектуры программного обеспечения на Java» , Auerbach Publications, 27 апреля 2004 г., doi : 10.1201/9780203496213.ch34 , ISBN 978-0-8493-2142-9 , получено 31 мая 2022 г.
Дальнейшее чтение [ править ]
- Питер ван Эмде Боас, Модели машин и моделирование, стр. 3–66, появляются в:
- Ян ван Леувен , изд. «Справочник по теоретической информатике. Том A: Алгоритмы и сложность» , MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (том А). КА 76.H279 1990 г.
- Стефан Диль, Питер Хартель и Питер Сестофт, Абстрактные машины для реализации языков программирования , Компьютерные системы будущего, Том. 16(7), Эльзевир, 2000.
- Вернер Клюге (2006). Абстрактные вычислительные машины: взгляд на лямбда-исчисление . Спрингер. ISBN 978-3-540-27359-2 .