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

Cтраница 2

Примитивные операции, используемые абстрактной машиной, могут быть разделены на 4 класса: операции со стеком и дампом, создание и изменение вершин графа ( и, таким образом, графов), вызов функций и возврат из них, а также вычисление применений примитивных функций. Каждая такая операция представлена макросом в коде G-машины, генерированном компилятором; эти макросы образуют набор команд абстрактной машины, который может быть реализован на любом компьютере, обладающем соответствующими языковыми средствами. Например, макроинструкции PUSH и SLIDE требуют применения команд с индексированием. Таким образом, промежуточный язык, основанный на макросах, является мобильным и может быть реализован на выбранном компьютере с помощью обычных языков программирования или машинного языка. [16]

Пример недетерминированного конечного автомата. [17]

Недетерминированный конечный автомат - это абстрактная машина, которая читает символы из входной цепочки и решает, допустить или отвергнуть эту цепочку. Автомат имеет несколько состояний и всегда находится в одном из них Он может изменить состояние, перейдя из одного состояния в другое. [18]

Ниже описан важный частный случай абстрактной машины, называемой абстрактной машиной с размеченной памятью тт. [19]

Рабин предложил использовать сети в качестве абстрактных машин, слабо вычисляющих полиномы. Недетер-минированност, результата работы машины отражает недетерминированность функционирования сети Петри. [20]

Отношение правило-исключение на множестве выводов. [21]

Интересно сопоставить К-машину с существующими типами реальных и абстрактных машин. Машины Тьюринга и Поста, существующие ЭВМ и алгоритмические языки программирования - все они, по существу, реализуют любые преобразования информации в виде последовательности элементарных операций. Эта элементарность как раз и не позволяет естественным образом обобщать и модифицировать используемые правила преобразования информации. Поэтому уделом таких машин остаются алгоритмические процедуры. [22]

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

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

Совокупность множества Е и описанного в-алгорифма называется абстрактной машиной с размеченной памятью. [25]

Простейшей моделью для изучения неадаптивных алгоритмов сортировки является абстрактная машина, которая способна осуществлять доступ к данным только с помощью операций сравнения-обмена. Сеть сортировки построена из атомарных модулей сравнения-обмена ( compare-exchange modules) или компараторов ( comparators), которые соединены между собой линиями связи таким образом, что становится возможным выполнение полной сортировки общего вида. [26]

В предыдущей главе была рассмотрена основанная на использовании стеков абстрактная машина для вычисления функциональных выражений, написанных в соответствии с нотацией А-исчисления. Как мы видели, эта машина наиболее удобна для реализации вычислений аппликативного порядка, соответствующих вызовам по значению Расширение области применения машины с целью поддерживать вызовы по необходимости требует введения дополнительных структур для явного представления задержек В этой главе будет рассмотрен совсем другой подход к вычислению лямбда-выражений, при котором мы допускаем представление выражений в виде графов, а не в виде линейных текстовых строк. Результирующая модель вычислений по очевидным причинам называется редукцией графов. Одно очевидное преимущество заключается в том, что в графовом представлении легко выразить разделение; нам не нужна дополнительная структура, такая, как контекст, для запоминания связей ( разделяемых) переменных, поскольку на ( разделяемый) подграф можно ссылаться любое число раз с помощью указателей. Второе преимущество данного представления в том, чю вычисление нормального порядка в этом случае легко представляется и относительно эффективно реализуется. Все это делает редукцию графов особенно естественным инструментом Для поддержки вызовов по необходимости и, следовательно, ленивого вычисления в функциональных языках. [27]

Программно-управляемую машину можно называть универсальной, если моделируемая ею абстрактная машина с размеченной памятью является универсальной. [28]

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

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

Страницы: 1 2 3 4