Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения



Скачать 104.09 Kb.
Дата19.01.2013
Размер104.09 Kb.
ТипДокументы
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения.
Основные цели данного подхода:

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

― построенные модели абстрактных машин должны быть использованы в течение всего жизненного цикла прогр обесп,

― средство разработки быстрых прототипов ― постепенным уточнением

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

Рассмотрим основную идею, заложенную в понятие абстрактной машины Гуревича.

Предположим сначала, что рассматривается случай последовательных алгоритмов. Это означает, что время изменяется последовательно, алгоритм начинает свою работу в некотором начальном состоянии S0 и продолжает свою работу, проходя последовательно состояния S1, S2 и т.д., причем на каждом шаге выполняется ограниченное количество работы. Каждое состояние алгоритма может быть представлено (алгебраической) структурой― некоторым множеством с отношениями и функциями.

Таким образом, выполнение алгоритма представляется в виде последовательности описанных структур.

Необходимо также указать, как происходит переход из состояния Si в состояние Si+1. Для того чтобы совершить такой переход, выполняется некоторое ограниченное количество изменений в состоянии Si.

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

Введем в рассмотрение математические объекты алгебры (или структуры) ― множества с функциями и операциями или функциями и отношениями. Модифицированные подходящим образом структуры называются состояниями.

Зафиксируем используемые базовые синтаксические конструкции

(сигнатуру) ― конечный набор функциональных имен (символов) ― функторов, и счетный набор переменных.

Каждому функциональному имени сопоставляется некоторое число аргументов или размерность. Пара (функциональное имя f, число аргументов n), называется функтором и обозначается f/n.

Конечное множество функторов называется словарем.

Для обозначения словарей обычно используется греческая буква γ.


Некоторые функторы особым образом помечаются ― как имена отношений

(предикатные символы), как статические имена или как то и другое.

Имена функций с областью значений {true, false} трактуются как имена отношений (предикатов).

Предполагается, что каждый словарь содержит следующие логические имена функций (и отношений): символ равенства /2, нульместные функциональные имена true, false, undef или , предикат Bool/1 и имена обычных булевских операций.

Все указанные предопределенные имена, включая символ undef, по определению считаются статическими.

Определим понятие состояния абстрактной машины подразумевается состояние вычислений.

Пусть даны непустое множество X, словарь  и интерпретация функциональных имен из  ― некоторое отображение I :   {X X}, такое, что каждому n-местному функтору ставится в соответствие некоторая всюду определенная n-местная функция. Тогда пара (X,I)

называется состоянием S некоторой ASM над словарем  (с интерпретацией I).

Пусть далее Voc(S)  .

Множество X называется базисным множеством или суперуниверсумом состояния S и обозначается BaseSet(S). Подмножества X называются универсумами, элементы X также называются элементами S.

Функции, интерпретирующие функторы из , называются базисными функциями S.

Если f ― функтор, то fS (иногда fI) обозначает его интерпретацию (базисную функцию) в состоянии S.

Базисные нульместные функции иногда называются также выделенными элементами

Положим в качестве области определения базисной n-местной функции f множество Dom(f) всех кортежей x размерности n, таких, что f( x ) ≠undef (подчеркнем еще раз, что undef ― обычный элемент суперуниверсума).

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

непересекающегося с другими универсумами, и некоторого способа выбора этих элементов.

Определим резерв состояния S как множество, содержащее все элементы S, такие, что

― каждое базисное отношение, за исключением равенства, при вычислении порождает false, если хотя бы один аргумент принадлежит резерву;

―каждая базисная функция (не отношение) при вычислении порождает undef, если хотя бы один аргумент принадлежит резерву;

―множества значений базисных функций не содержат элементов резерва.

Далее мы будем предполагать, что каждое состояние имеет бесконечный резерв.

Правила перехода

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

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

Так, добавление элементов к суперуниверсуму можно обойти с помощью универсума Reserve. Для расширения некоторого универсума U за счет нового элемента поместим некоторый резервный элемент a в U. Реализовать это можно, присвоив новые значения U и

Reserve: U(a) : true и Reserve(a) : false.

Для удаления (добавления) некоторого элемента a из универсума (в универсум) U

достаточно установить U(a) false (true).

Предположим, что некоторый алгоритм реализуется программой, которая время от времени создает новые функции. На новые функции можно смотреть как на данные. Например, можно ввести универсум F всех одноместных операций на некотором универсуме U.

Далее, можно определить двуместную базисную (универсальную) функцию Apply, такую, что

fFuU Apply(f, u)  f(u).

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

Правила перехода

Команды или инструкции определяемого языка спецификаций называются правилами перехода или просто правилами. Единственным простейшим правилом является правило локального изменения функции или замещения или просто замещение состояния S: f (t ) :  t0,

где f ― (нестатический) функтор некоторой базисной функции, все элементы кортежа t и t0 ― основные термы(не содержат переменнных) и все функторы правила принадлежат словарю состояния S.

Смысл данного правила заключается в следующем. Сначала одновременно вычисляются t0 и все термы кортежа t , т.е. ValS( t0 ) и ValS( t ). Затем значение fS(ValS( t )) устанавливается в ValS( t0 ). Это значит, что если fS не имела значения в точке ValS( t ), то она его приобретет, иначе старое значение будет заменено новым. В любом случае этим значением станет

ValS( t0 ).

Следующее правило ― охраняемое (условное) замещение:

if b then u endif или fi

где b охраняющее условие ― булевский терм, и u ― замещение.

В принципе условное замещение является избыточной формой правила. Достаточно ввести логическую функцию Cond(x,y,z), интерпретируемую в любом состоянии следующим образом:



Тогда приведенное выше условное замещение вида (2) будет иметь тот же эффект, что и безусловное вида:
Однако считается, что последняя запись менее наглядна (но более точна).

Еще одна допустимая форма условного замещения имеет вид:

if b then u1 else u2 fi

Последняя форма по определению эквивалентна множеству из двух условных замещений вида if b then u1 fi if b then u2 fi

что в свою очередь является частным случаем правила вида

R1

R2



Rn

― произвольного конечного множества замещений (здесь все Ri ― простые или условные замещения).

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

Приведенные выше две формы правила условного замещения непосредственно обобщаются. Пусть k ― натуральное число, b0, …, bk ― булевские термы и C0, …, Ck ― конечные множества правил, тогда правилами являются и следующие две формы:

if b0 then C0

elseif b1 then C1



elseif bk then Ck

[else Ck+1]

fi

Программа ASM ― это конечное множество правил перехода.

Выполнение программы осуществляет интерпретатор абстрактной машины.

Выполнение начинается в одном из (любом) состояний машины, которое объявляется начальным. Завершение работы машины происходит в заключительном состоянии. Заключительным считается любое состояние, в котором выполняется условие завершения ― любое фиксированное до начала работы машины условие вида Val(t1 = t2) = true

Пример. Стековая машина

Приведем пример ASM, моделирующей работу стека. Построим машину, вычисляющую выражение, заданное в обратной польской записи (RPN). Например, выражение

(1 + 2) * (5 + 6)

в RPN имеет вид

1 2 + 5 6 + *

В рассматриваемом примере речь может идти не только об арифметических операциях над множеством целых чисел.

Пусть имеется непустое множество Data и непустое множество Oper всюду определенных (для простоты) бинарных операций над Data.

Например, Data может быть множеством целых, а Oper может быть {+, *}. Предположим, что выражение в RPN задается в виде списка, элементами которого являются операнды (данные) или операторы.

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

переменных легко выявляются из контекста.

Помимо уже упомянутых универсумов Data и Oper нам потребуются нульместные функции Arg1 и Arg2 ― выделенные элементы Data.

Для манипулирования операциями из Oper нужна функция Apply/3, такая, что Apply(f,x,y) = f(x,y) для всех f из Oper и всех x, y из Data.

Для управления вводом определяется универсум List всех списков, построенных из данных и операторов. Вводятся базисные функции Head и Tail над списками, наделяемые обычными свойствами. Если L ― список, то Head(L) ― первый элемент списка и Tail(L) ― хвост (оставшаяся часть) списка. Выделенный элемент EmptyList имеет обычный смысл.

F ― выделенный (текущий) список. Сначала F содержит входное выражение.

Наконец, вводится универсум Stack всех стеков данных с обычными операциями Push: DataStackStack,

Pop: StackStack, Top: StackData.

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

Приведем правила перехода определяемой машины:

if Data(Head(F)) then

S := Push(Head(F), S)

F := Tail(F)

endif

if Oper(Head(F)) then

if Arg1= undef then

Arg1 := Top(S)

S := Pop(S)

elseif Arg2 = undef then

Arg2 := Top(S)

S := Pop(S)

else S := Push(Apply(Head(F), Arg1, Arg2), S)

F := Tail(F)

Arg1 = undef

Arg2 = undef

endif

endif

Пример. Машина Тьюринга

Введем три непустых конечных универсума ASM ― Control, Char и Displacement(смещение), универсум FinalStateControl. Пусть InitialState и CurrentState ― выделенные элементы Control, Blank ― выделенный элемент Char.

Еще один универсум, Tape ― бесконечное счетное множество; его элементы называются ячейками. Head ― динамический выделенный элемент. Move ― (возможно, частичная) функция: TapeDisplacementTape.

Определим еще несколько дополнительных функций. Динамическая функция TapeCont отображает ячейки ленты в символы: TapeChar, функции NewState, NewChar и Shift отображают декартово произведение ControlChar в Control, Char и Displacement

соответственно. Потребуем, чтобы условие TapeCont(c) = Blank выполнялось для всех ячеек c, за исключением, быть может, конечного подмножества.

Определим правила перехода машины:

CurrentState := NewState(CurrentState, TapeCont(Head))

TapeCont(Head) := NewChar(CurrentState, TapeCont(Head))

Head := Move(Head,Shift(CurrentState, TapeCont(Head))

Как обычно, на каждом шаге работы машины все правила выполняются одновременно.

Условие завершения работы машины ― CurerntStateFinalState.

Похожие:

Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения icon6 Основные понятия и определения теории абстрактных авто­матов (лекция №9)
Этот класс устройств определяется тем, что значение выходов зависит не только от входных значений, но и от текущего состояния устройства....
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconЛекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет
Алфавиты, конструктивные объекты, их примеры. Понятие алгоритма, вычислимые функции. Формализация понятия алгоритма: частично-рекурсивные...
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconНайти функцию, полученную из функции и по схеме примитивной рекурсии
Проверить работу машины Тьюринга с некоторым набором значений аргументов. Написать формулу числовой функции f (0,…,6 – внутренние...
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconРеферат по дисциплине «Дискретная математика»
Программа для машины Тьюринга записывается в таблицу. Строки –это символы внутреннего алфавита состояний машины Тьюринга. Столбцы...
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconТема урока: Устройство швейной машины с ручным приводом. Раздел Технология изготовления швейных изделий. Тема Устройство швейной машины с ручным приводом. Цели : Ознакомить с историей создания швейной машины
Развивать интерес к истории, к профессии оператора швейного оборудова­ния, развивать умение в подготовке машины к работе. Воспитание...
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconПрограмма дисциплины по кафедре «Строительные и дорожные машины» Строительная механика и металлические конструкции
Утверждена научно-методическим советом университета по направлению 190000 — Транспортные средства для специальности 170900 (190205....
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconОписание устройства основных органов швейной машины, кинематические схемы. Все швейные машины делятся на специальные
Специальные машины выполняют только одну определенную технологическую операцию: выполнение петель, пришив пуговиц и т д. На универсальных...
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconЗадача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой
Понятие графа, основные определения (вершины, ребра, дуги, ориентированные и неориентированные графы, простой граф, петли, кратные...
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconТепловые машины 21 века
Доказана универсальность формулы для максимального кпд реальной тепловой машины 3
Машины абстрактных состояний. Основные идеи, мотивировки. Понятие состояния машины и связанные с ним определения. Правила перехода. Примеры применения iconДата выпуска машины Марка машины

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org