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

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

В Метод ASM практичный и научно обоснованный системная инженерия метод, устраняющий разрыв между двумя сторонами разработки системы:

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

Метод основан на трех основных концепциях:

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

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

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

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

История

Концепция ASM связана с Юрий Гуревич, которые впервые предложили его в середине 1980-х годов как способ улучшить Тезис Тьюринга что каждый алгоритм является смоделированный соответствующим Машина Тьюринга. Он сформулировал ASM Диссертация: каждый алгоритм, не важно как Абстрактные, пошагово подражал с помощью соответствующего ASM. В 2000 году Гуревич аксиоматизированный понятие последовательных алгоритмов и доказал для них тезис ASM. Грубо говоря, аксиомы таковы: состояния - это структуры, переход состояния включает только ограниченную часть состояния, и все инвариантный под изоморфизмы конструкций. (Структуры можно рассматривать как алгебры, что объясняет оригинальное название развивающиеся алгебры для ASM.) Аксиоматизация и характеризация последовательных алгоритмов были расширены на параллельно и интерактивные алгоритмы.

В 1990-х усилиями сообщества был разработан метод ASM с использованием ASM для формальная спецификация и анализ (верификация и валидация ) из компьютерное железо и программного обеспечения. Исчерпывающие спецификации ASM для языки программирования (в том числе Пролог, C, и Ява ) и языки дизайна (UML и SDL ) были разработаны. Подробный исторический отчет можно найти в AsmBook (Глава 9) или вэта статья.

Доступен ряд программных инструментов для выполнения и анализа ASM.

Публикации

Книги

Поведенческие модели для промышленных стандартов

инструменты

(в историческом порядке с 2000 г.)

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

  • Ю. Гуревич, Развивающиеся алгебры 1993: руководство по липари, Э. Бёргер (ред.), Спецификация и методы проверки, Oxford University Press, 1995, 9-36. (ISBN  0-19-853854-5)
  • Э. Бёргер и Р. Штерк, Абстрактные государственные машины: метод проектирования и анализа систем высокого уровня, Springer-Verlag, 2003. (ISBN  3-540-00702-4)
  • Р. Штерк, Й. Шмид и Э. Бёргер, Java и виртуальная машина Java: определение, проверка, проверка, Springer-Verlag, 2001. (ISBN  3-540-42088-6)
  • Ю. Гуревич, Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы, Транзакции ACM по вычислительной логике 1 (1) (июль 2000 г.), 77-111.

внешние ссылки