Абстрактная машина -Abstract machine

Абстрактная машина — это теоретическая модель информатики , которая позволяет проводить подробный и точный анализ того, как функционирует компьютерная система. Она аналогична математической функции в том смысле, что она получает входные данные и производит выходные данные на основе предопределенных правил. Абстрактные машины отличаются от буквальных тем, что они должны работать правильно и независимо от аппаратного обеспечения . Абстрактные машины являются « машинами », потому что они позволяют выполнять программы шаг за шагом ; они « абстрактны », потому что игнорируют многие аспекты реальных ( аппаратных) машины. Типичная абстрактная машина состоит из определения с точки зрения ввода, вывода и набора допустимых операций, используемых для преобразования первого во второе. Их можно использовать как в чисто теоретических целях, так и в качестве моделей для реальных компьютерных систем. В теории вычислений абстрактные машины часто используются в мысленных экспериментах относительно вычислимости или для анализа сложности алгоритмов . Это использование абстрактных машин связано с областью теории вычислительной сложности , такой как конечные автоматы , машины Мили, автоматы с проталкиванием вниз и машины Тьюринга .


Классификация

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

Например, машина Тьюринга — одна из самых фундаментальных абстрактных машин в информатике. Это машина, которая может выполнять операции на ленте (строке символов) любой длины. Он включает инструкции как по изменению символов, так и по изменению символа, на котором он основан. Единственная команда на элементарном компьютере Тьюринга будет «преобразовать символ в 1, затем двигаться вправо», и эта машина будет выдавать только строку из 1. Эта базовая машина Тьюринга является детерминированной, однако также могут быть построены недетерминированные машины Тьюринга , которые могут выполнять несколько действий при одном и том же вводе.

Реализация абстрактной машины

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

Реализация языка программирования

Термин « машина » относится к вычислительной машине, которая представляет собой физическую машину, выполняющую алгоритмы, достаточно формализованные для того, чтобы машина «понимала». Абстрактная машина интуитивно является не чем иным, как абстракцией идеи физического компьютера. Для фактического выполнения алгоритмы должны быть должным образом формализованы с использованием конструкций, предлагаемых языком программирования . Это означает, что выполняемые алгоритмы должны быть выражены с помощью инструкций языка программирования. Синтаксис языка программирования позволяет создавать программы с использованием конечного набора конструкций, известных как инструкции. Большинство абстрактных машин совместно используют хранилище программ и состояние , которое часто включает в себя стек и регистры. В цифровых компьютерах стек — это просто блок памяти с адресным регистром, который может считать только положительные целые числа (после загрузки в него начального значения). Адресный регистр для стека известен как указатель стека, потому что его значение всегда относится к верхнему элементу стека. Программа состоит из серии инструкций с указателем стека, указывающим, какая следующая инструкция должна быть выполнена. Когда инструкция завершена, указатель стека продвигается вперед. Этот фундаментальный механизм управления абстрактной машиной также известен как цикл выполнения . Таким образом, абстрактная машина для языка программирования — это любой набор структур данных и алгоритмов, способный хранить и запускать программы, написанные на языке программирования. Он устраняет разрыв между высоким уровнем языка программирования и низким уровнем реальной машины , предоставляя промежуточный язык для компиляции . Инструкции абстрактной машины адаптированы к уникальным операциям, необходимым для реализации операций определенного исходного языка или набора исходных языков.

Императивные языки программирования

В конце 1950-х годов Ассоциация вычислительной техники (ACM) и другие союзные организации разработали множество предложений для универсального компьютерно-ориентированного языка (UNCOL) , таких как машина Конвея . Концепция UNCOL хороша, но не получила широкого распространения из-за низкой производительности генерируемого кода . Во многих областях вычислений его производительность по-прежнему будет проблемой, несмотря на разработку виртуальной машины Java в конце 1990-х годов. Algol Object Code (1964), P4-machine (1976), UCSD P-machine (1977) и Forth (1970) — некоторые из успешных абстрактных машин такого рода.

Объектно-ориентированные языки программирования

Абстрактные машины для объектно-ориентированных языков программирования часто основаны на стеке и имеют специальные инструкции доступа к полям и методам объекта . На этих машинах управление памятью часто неявно выполняется сборщиком мусора (функция восстановления памяти, встроенная в языки программирования). Smalltalk-80 (1980 г.), Self (1989 г.) и Java (1994 г.) являются примерами этой реализации.

Языки обработки строк

Язык обработки строк — это компьютерный язык, ориентированный на обработку строк, а не чисел. На протяжении десятилетий существовали языки обработки строк в виде командных оболочек , инструментов программирования , макропроцессоров и языков сценариев . Использование подходящей абстрактной машины имеет два преимущества: увеличение скорости выполнения и улучшенная переносимость. Snobol4 и ML/I — два примечательных примера ранних языков обработки строк, которые используют абстрактную машину для достижения машинной независимости.

Языки функционального программирования

Наглядное изображение кривинской машины .

Ранние абстрактные машины для функциональных языков , в том числе машина SECD (1964) и функциональная абстрактная машина Карделли (1983), определяли строгую оценку, также известную как нетерпеливая оценка или оценка по значению , в которой аргументы функции оцениваются до вызова. и именно один раз. В последние годы большинство исследований было посвящено ленивым (или вызываемым по необходимости) вычислениям , таким как G-машина (1984 г.), машина Кривина (1985 г.) и машина трех инструкций (1986 г.), в которых аргументы функций оцениваются только в случае необходимости и не более одного раза. Одна из причин заключается в том, что эффективная реализация строгой оценки теперь хорошо изучена, поэтому потребность в абстрактной машине уменьшилась.

Языки логического программирования

Исчисление предикатов (логика первого порядка) является основой языков логического программирования . Самый известный язык логического программирования — Prolog . Правила в Прологе написаны в едином формате, известном как универсально квантифицированные «условия Хорна», что означает начало вычислений, пытающихся обнаружить доказательство цели. В центре внимания большинства исследований находилась абстрактная машина Уоррена WAM (1983), ставшая стандартом де-факто в компиляции программ на Прологе. Он предоставляет инструкции специального назначения, такие как инструкции по объединению данных и инструкции потока управления, для поддержки поиска с возвратом (алгоритм поиска).

Структура абстрактной машины

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

Структура абстрактной машины

Интерпретатор должен выполнять операции, уникальные для языка , который он интерпретирует. Однако, учитывая разнообразие языков, можно определить категории операций и « механизм выполнения », общий для всех интерпретаторов. Операции интерпретатора и сопутствующие структуры данных делятся на следующие категории:

  1. Операции по обработке примитивных данных :
  2. Операции и структуры данных для управления последовательностью выполнения операций ;
  3. Операции и структуры данных для управления передачей данных ;
  4. Операции и структуры данных для управления памятью .

Операции обработки примитивных данных

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

Операции и структуры данных для управления последовательностью

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

Операции и структуры данных для управления передачей данных

Операции передачи данных используются для контроля того, как операнды и данные передаются из памяти в интерпретатор и наоборот. Эти операции имеют дело с хранилищем и порядком извлечения операндов из хранилища.

Операции и структуры данных для управления памятью

Управление памятью связано с операциями, выполняемыми в памяти для размещения данных и приложений. В абстрактной машине данные и программы могут храниться неограниченное время, а в случае с языками программирования память может выделяться или освобождаться с использованием более сложного механизма.

Иерархии абстрактных машин

Иерархия абстрактных машин

Часто используются иерархии абстрактных машин, в которых каждая машина использует функциональные возможности уровня непосредственно ниже и добавляет свои собственные дополнительные функциональные возможности для соответствия уровню непосредственно выше. Аппаратный компьютер , построенный из физических электронных устройств, может быть добавлен на самом базовом уровне. Выше этого уровня может быть введен уровень абстрактной микропрограммируемой машины . Абстрактная машина, предоставляемая операционной системой , которая реализуется программой, написанной на машинном языке , расположена непосредственно над (или непосредственно над аппаратным обеспечением , если уровень прошивки отсутствует). С одной стороны, операционная система расширяет возможности физической машины, предоставляя примитивы более высокого уровня, недоступные на физической машине (например, примитивы, воздействующие на файлы). Хост - машина формируется абстрактной машиной, заданной операционной системой, на которой язык программирования высокого уровня реализован с использованием промежуточной машины , такой как виртуальная машина Java и ее язык байт-кода. Уровень, заданный абстрактной машиной для языка высокого уровня (например, Java), обычно не является конечным уровнем иерархии. На этом этапе могут быть введены одно или несколько приложений, которые совместно предоставляют дополнительные услуги. Уровень «веб-машины», например, может быть добавлен для реализации функций, необходимых для обработки веб-коммуникаций ( протоколы связи или представление кода HTML ). Уровень « Веб-сервис » расположен выше этого уровня и предоставляет функциональные возможности, необходимые для взаимодействия веб-сервисов, как с точки зрения протоколов взаимодействия, так и поведения вовлеченных процессов. На этом уровне могут быть разработаны совершенно новые языки, которые определяют поведение так называемых «бизнес-процессов» на основе веб-сервисов (примером является язык выполнения бизнес-процессов ). Наконец, на самом высоком уровне можно найти специализированное приложение (например, Электронная коммерция ), имеющее очень специфический и ограниченный функционал.

Смотрите также

использованная литература

  1. ^ Вайсштейн, Эрик В. «Абстрактная машина» . mathworld.wolfram.com . Проверено 16 мая 2022 г. .
  2. ^ a b c d e f "Что такое абстрактная машина?" . EasyTechJunkie . Проверено 16 мая 2022 г. .
  3. ^ a b c d e f g h i j Диль, Стефан; Хартель, Питер; Сестофт, Питер (май 2000 г.). «Абстрактные машины для реализации языка программирования» . Компьютерные системы будущего поколения . 16 (7): 739–751. doi : 10.1016/S0167-739X(99)00088-6 .
  4. ^ «9.1.1: Обзор конечного автомата» . Инженерные тексты LibreText . 2021-04-29 . Проверено 31 мая 2022 г. .
  5. ^ «Что такое детерминированная система? - Определение из Techopedia» . Techopedia.com . Проверено 30 мая 2022 г. .
  6. ^ Стернс, Ричард Э. (январь 2003 г.). «Детерминированное и недетерминированное время и проблемы с нижней границей» . Журнал АКМ . 50 (1): 91–95. дои : 10.1145/602382.602409 . ISSN  0004-5411 . S2CID  2194820 .
  7. ^ Армони, Михал; Гал-Эзер, Джудит (декабрь 2007 г.). «Недетерминизм: абстрактное понятие в исследованиях информатики» . Образование в области компьютерных наук . 17 (4): 243–262. Бибкод : 2007CSEd...17..243A . дои : 10.1080/08993400701442885 . ISSN  0899-3408 . S2CID  41928460 .
  8. Гилл, Джон (декабрь 1977 г.). «Вычислительная сложность вероятностных машин Тьюринга» . Журнал SIAM по вычислительной технике . 6 (4): 675–695. дои : 10.1137/0206049 . ISSN  0097-5397 .
  9. ^ a b c d e f g h i j k l m n o Габбриелли, Маурицио; Мартини, Симоне (2010), «Абстрактные машины» , Языки программирования: принципы и парадигмы , Лондон: Springer London, стр. 1–25, doi : 10.1007/978-1-84882-914-5_1 , ISBN 978-1-84882-913-8, получено 16 мая 2022 г.
  10. ^ Бэр, Рэй; Чиен, Эндрю; Кук, Джанин; Донофрио, Дэйв; Грайдер, Гэри; Куэн, Джефф; Мур, Ширли; Шалф, Джон; Веттер, Джефф (01 февраля 2018 г.). «Оценка оборудования: модели абстрактных машин и прокси-архитектуры для экзафлопсных вычислений» . дои : 10.2172/1733300 . ОСТИ  1733300 . {{cite journal}}:Цитировать журнал требует |journal=( помощь )
  11. ^ "абстрактная машина из FOLDOC" . foldoc.org . Проверено 7 августа 2021 г. .
  12. ^ Джи, Дж .; Мелвин, SW; Патт, Ю. Н. (1986). «Реализация Prolog через микрокод VAX 8600» . Материалы 19 - го ежегодного семинара по микропрограммированию -- MICRO 19 . Нью-Йорк, Нью-Йорк, США: ACM Press: 68–74. дои : 10.1145/19551.19538 . ISBN 081860736X. S2CID  3846072 .
  13. ^ "абстрактная машина" . Оксфордский справочник . Проверено 16 мая 2022 г. .
  14. ^ Гарсия-Мартин, Хулио Мануэль; Сутиль-Мартин, Мигель (15 августа 1999 г.). «Шаблон для проектирования абстрактных машин» . doi : 10.13140/RG.2.1.3680.5203 . {{cite journal}}:Цитировать журнал требует |journal=( помощь )
  15. ^ upscfever.com (25 января 2017 г.). «Компьютерная организация и архитектура (стековая организация) — UPSC FEVER» . upscfever.com . Проверено 31 мая 2022 г. .
  16. ^ a b Тайсон, Мэтью (17 января 2020 г.). «Что такое JVM? Знакомство с виртуальной машиной Java» . ИнфоМир . Проверено 31 мая 2022 г. .
  17. ^ «Что такое объектно-ориентированное программирование (ООП)?» . ПоискАрхитектураПриложений . Проверено 31 мая 2022 г. .
  18. ^ «Соображения по проектированию языков обработки строк» , Исследование языков обработки строк , Конспект лекций по информатике, Берлин, Гейдельберг: Springer Berlin Heidelberg, vol. 205, стр. 17–37, 1985, doi : 10.1007/3-540-16041-8_2 , ISBN 978-3-540-16041-0, получено 31 мая 2022 г.
  19. ^ Хакетт, Дженнифер; Хаттон, Грэм (26 июля 2019 г.). «Вызов по необходимости — это ясновидящий вызов по значению» . Труды ACM по языкам программирования . 3 (ICFP): 1–23. дои : 10.1145/3341718 . ISSN  2475-1421 . S2CID  195782686 .
  20. ^ "Пролог | Введение" . . _ 2018-05-26 . Проверено 31 мая 2022 г. .
  21. ^ Аккаттоли, Бениамино; Баренбаум, Пабло; Мацца, Дамиано (26 ноября 2014 г.). «Дистилляция абстрактных машин» . Уведомления ACM SIGPLAN . 49 (9): 363–376. дои : 10.1145/2692915.2628154 . ISSN  0362-1340 . S2CID  234775413 .
  22. ^ Баелдунг (11 января 2018 г.). «Введение в примитивы Java | Baeldung» . www.baeldung.com . Проверено 31 мая 2022 г. .
  23. ^ «Интерпретатор» , Шаблоны проектирования архитектуры программного обеспечения на Java , публикации Ауэрбаха, 27 апреля 2004 г., doi : 10.1201/9780203496213.ch34 , ISBN 978-0-8493-2142-9, получено 31 мая 2022 г.
  24. ^ «Аппаратное обеспечение, программное обеспечение и прошивка: в чем разница?» . Спасательный трос . Проверено 31 мая 2022 г. .
  25. ^ Аккаттоли, Бениамино; Баррас, Бруно (09.10.2017). «Среды и сложность абстрактных машин» . Материалы 19-го Международного симпозиума по принципам и практике декларативного программирования . Намюр, Бельгия: ACM: 4–16. дои : 10.1145/3131851.3131855 . ISBN 978-1-4503-5291-8. S2CID  11953081 .
  26. ^ «Веб-службы» . ссылка.wolfram.com . Проверено 31 мая 2022 г. .
  27. ^ ДБ Скилликорн (2005). Основы параллельного программирования . Издательство Кембриджского университета. п. 18. ISBN 978-0-521-01856-2.

дальнейшее чтение

  • Питер ван Эмде Боас, Модели машин и моделирование , стр. 3–66, опубликовано в:
Ян ван Левен , изд. "Справочник по теоретической информатике. Том A: Алгоритмы и сложность ", MIT PRESS/Elsevier, 1990. ISBN  0-444-88071-2 (том A). QA 76.H279 1990