Jump to content

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

(Перенаправлено с абстрактного компьютера )

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

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

[ редактировать ]

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

Запуск машины Тьюринга

машины Тьюринга являются одними из самых фундаментальных абстрактных машин в информатике. Например, [ 2 ] Эти машины выполняют операции с лентой (строкой символов) любой длины. Их инструкции предусматривают как модификацию символов, так и изменение символа, на котором в данный момент находится указатель машины. Например, элементарная машина Тьюринга могла иметь одну команду «преобразовать символ в 1, затем двигаться вправо», и эта машина выдавала бы только строку из единиц. [ 8 ] Эта базовая машина Тьюринга является детерминированной; однако недетерминированные машины Тьюринга , которые могут выполнять несколько действий при одних и тех же входных данных. также могут быть построены [ 2 ]

Выполнение

[ редактировать ]

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

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

[ редактировать ]

Абстрактная машина интуитивно представляет собой просто абстракцию идеи физического компьютера. [ 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 ]

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

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

[ редактировать ]

Абстрактная машина должна содержать операции для управления примитивными типами данных, такими как строки и целые числа. [ 9 ] Например, целые числа почти повсеместно считаются базовым типом данных как для физических абстрактных машин, так и для абстрактных машин, используемых во многих языках программирования . Машина выполняет необходимые арифметические операции , такие как сложение и умножение, за один временной шаг. [ 21 ]

Последовательное управление

[ редактировать ]

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

Контроль передачи данных

[ редактировать ]

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

Управление памятью

[ редактировать ]

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

Иерархии

[ редактировать ]
Иерархия абстрактных машин

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

См. также

[ редактировать ]
  1. ^ Вайсштейн, Эрик В. «Абстрактная машина» . mathworld.wolfram.com . Проверено 16 мая 2022 г.
  2. ^ Jump up to: а б с д и ж «Что такое абстрактная машина?» . EasyTechJunkie . Проверено 16 мая 2022 г.
  3. ^ Jump up to: а б с д и ж г час я дж Диль, Стефан; Хартель, Питер; Сестофт, Питер (май 2000 г.). «Абстрактные машины для реализации языков программирования» . Компьютерные системы будущего поколения . 16 (7): 739–751. дои : 10.1016/S0167-739X(99)00088-6 .
  4. ^ «9.1.1: Обзор конечного автомата» . Инженерные библиотеки LibreTexts . 29 апреля 2021 г. Проверено 31 мая 2022 г.
  5. ^ «Что такое детерминированная система? - Определение из Techopedia» . Techopedia.com . 29 августа 2019 года . Проверено 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 Journal по вычислительной технике . 6 (4): 675–695. дои : 10.1137/0206049 . ISSN   0097-5397 .
  9. ^ Jump up to: а б с д и ж г час я дж к л м Габбриелли, Маурицио; Мартини, Симона (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 .
  11. ^ «абстрактная машина от FOLDOC» . Foldoc.org . Проверено 7 августа 2021 г.
  12. ^ Ну и дела, Дж.; Мелвин, Юго-Запад; Патт, Ю.Н. (1986). «Реализация Пролога через микрокод VAX 8600» . Материалы 19-го ежегодного семинара по микропрограммированию . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 68–74. дои : 10.1145/19551.19538 . ISBN  081860736X . S2CID   3846072 .
  13. ^ «абстрактная машина» . Оксфордский справочник . Проверено 16 мая 2022 г.
  14. ^ Гарсиа-Мартин, Хулио Мануэль; Сутил-Мартин, Мигель (15 августа 1999 г.). «Абстрактная машина: образец проектирования абстрактных машин» (PDF) . Труды по шаблонным языкам программ '99 .
  15. ^ upscfever.com (25 января 2017 г.). «Компьютерная организация и архитектура (стековая организация) — UPSC FEVER» . upscfever.com . Проверено 31 мая 2022 г.
  16. ^ «Что такое объектно-ориентированное программирование (ООП)?» . Архитектура приложения поиска . Проверено 31 мая 2022 г.
  17. ^ «Аспекты проектирования языков обработки строк» , Исследование языков обработки строк , Конспект лекций по информатике, том. 205, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 17–37, 1985, doi : 10.1007/3-540-16041-8_2 , ISBN  978-3-540-16041-0 , получено 31 мая 2022 г.
  18. ^ Хакетт, Дженнифер; Хаттон, Грэм (26 июля 2019 г.). «Призыв по нужде – это ясновидящий призыв по значению» . Труды ACM по языкам программирования . 3 (ICFP): 1–23. дои : 10.1145/3341718 . ISSN   2475-1421 . S2CID   195782686 .
  19. ^ «Пролог | Введение» . Гики для Гиков . 26 мая 2018 г. Проверено 31 мая 2022 г.
  20. ^ Аккаттоли, Бениамино; Баренбаум, Пабло; Мацца, Дамиано (26 ноября 2014 г.). «Дистилляция абстрактных машин» . Уведомления ACM SIGPLAN . 49 (9): 363–376. дои : 10.1145/2692915.2628154 . ISSN   0362-1340 . S2CID   234775413 .
  21. ^ баелдунг (11 января 2018 г.). «Введение в примитивы Java | Baeldung» . www.baeldung.com . Проверено 31 мая 2022 г.
  22. ^ «Интерпретатор» , «Шаблоны проектирования архитектуры программного обеспечения на 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 г.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: cd97e075372aca9c3909f89dab9eda3f__1714534560
URL1:https://arc.ask3.ru/arc/aa/cd/3f/cd97e075372aca9c3909f89dab9eda3f.html
Заголовок, (Title) документа по адресу, URL1:
Abstract machine - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)