Сплав (язык спецификации) - Alloy (specification language)

В Информатика и программная инженерия, Сплав является декларативным язык спецификации для выражения сложных структурных ограничений и поведения в программная система. Alloy предоставляет простой инструмент структурного моделирования на основе логика первого порядка.[1] Сплав ориентирован на создание микромодели которые затем могут быть автоматически проверены на правильность. Характеристики сплава можно проверить с помощью анализатора сплава.

Хотя Alloy разработан с учетом автоматического анализа, Alloy отличается от многих языков спецификаций, предназначенных для модельная проверка тем, что он позволяет определять бесконечные модели. Анализатор сплавов разработан для выполнения проверок в ограниченном объеме даже на бесконечных моделях.

Язык и анализатор Alloy разработаны командой под руководством Дэниел Джексон на Массачусетский Институт Технологий в Соединенные Штаты.

История и влияние

Первая версия языка Alloy появилась в 1997 году. Это была довольно ограниченная объектное моделирование язык. Последующие итерации языка "добавлены кванторы, выше арность связи, полиморфизм, подтип, и подписи ».[2]

Математические основы языка находились под сильным влиянием Обозначение Z, а синтаксис of Alloy больше обязана таким языкам, как Язык объектных ограничений.

Анализатор сплавов

Анализатор сплавов.

Анализатор сплавов был специально разработан для поддержки так называемых «облегченных формальных методов». Таким образом, он предназначен для обеспечения полностью автоматизированного анализа, в отличие от интерактивное доказательство теорем методы, обычно используемые с языками спецификаций, подобными Alloy. Первоначально разработка анализатора была вдохновлена ​​автоматическим анализом, предоставленным модельные шашки. Однако проверка моделей плохо подходит для моделей, которые обычно разрабатываются в Alloy, и в результате ядро ​​Анализатора в конечном итоге было реализовано как средство поиска моделей, построенное на логический SAT-решатель.[1]

Начиная с версии 3.0, анализатор сплавов включал в себя встроенный искатель моделей на основе SAT, основанный на стандартном SAT-решателе. Однако, начиная с версии 4.0, Analyzer использует поисковик моделей Kodkod, для которого Analyzer действует как интерфейс. Оба искателя моделей по сути переводят модель, выраженную в реляционная логика в соответствующий логическая логика формулу, а затем вызовите готовый SAT-решатель для булевой формулы. В случае, если решающая программа находит решение, результат преобразуется обратно в соответствующую привязку констант к переменным в реляционной логической модели.[3]

Чтобы гарантировать, что проблема поиска модели разрешимый, Alloy Analyzer выполняет поиск модели в ограниченном объеме, состоящем из определенного пользователем конечного числа объектов. Это ограничивает универсальность результатов, выдаваемых анализатором. Однако разработчики Alloy Analyzer оправдывают решение работать в ограниченных объемах обращением к гипотеза малого масштаба: что большая часть ошибок может быть обнаружена путем тестирования программы для всех тестовых входных данных в небольшом объеме.[4]

Структура модели

Модели Alloy являются реляционными по своей природе и состоят из нескольких различных типов утверждений:[1]

  • Подписи определить словарь модели путем создания новых наборов
сиг Объект{} определяет подпись Объект
сиг Список {глава: одинокий Узел} определяет подпись Список который содержит поле голова типа Узел и множественность одинокий - это устанавливает наличие связи между Списокпесок Узелтак, что каждый Список связан не более чем с одной головой Узел
  • Факты это ограничения, которые, как предполагается, всегда выполняются
  • Предикаты являются параметризованными ограничениями и могут использоваться для представления операций
  • Функции выражения, возвращающие результаты
  • Утверждения предположения о модели

Поскольку Alloy является декларативным языком, на значение модели не влияет порядок операторов.

Рекомендации

  1. ^ а б c Джексон, Дэниел (2006). Программные абстракции: логика, язык и анализ. MIT Press. ISBN  978-0-262-10114-1.
  2. ^ «FAQ по сплавам». Архивировано из оригинал 7 июня 2007 г.. Получено 7 марта 2013.
  3. ^ Torlak, E .; Деннис, Г. (апрель 2008 г.). «Кодкод для пользователей сплавов» (PDF). Первый семинар по сплавам ACM. Портланд, штат Орегон. Архивировано из оригинал (PDF) на 2010-06-22. Получено 2009-04-19.
  4. ^ Андони, Александр; Данилюк, Думитру; Хуршид, Сарфраз; Маринов, Дарко (2002). «Оценка гипотезы малого объема». CiteSeerX  10.1.1.8.7702. Цитировать журнал требует | журнал = (помощь)

внешняя ссылка