ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
Расширение абстрактной машины для выполнения альтернатив ЛП Команда Пояснение ALT выбор подходящего варианта. ESC выход из тупиковой ситуации. 130 Таб л иц а 3 4 Определение команд ЛП Формат регистров Результат s e (ALT c1 c2 . c) d r → s e (c1 . c) (c . d) ((s e (c2 . c) d) . r) s e (ESC) d Nil → Nil e (Esc) d Nil s‟ e‟ (ESC) d‟ ((s e (c2 . c) d) . r) → s e (c2 . c) d r 6.2. Основы Представление вариантов в чем-то подобно определению ветвлений, но без предикатов, управляющих выбором ветви, что по реализации напоминает вариантные записи или объединения в обычных ЯВУ. В некоторых языках, например, учебно-игрового характера, можно указать вероятность выбора варианта. В языках логического и генетического программирования считают возможным прямой перебор вариантов, сопоставляемых с образцами, и организацию возвратов при неудачном выборе. Обычно понятие алгоритма и программы связывают с детерминированными процессами. Однако эти понятия не очень усложнятся, если допустить недетерминизм, ограниченный конечным числомвариантов, так что в каждый момент времени из них существует только один вариант. В любом выражении можно выполнить разметку ветвей на нормальные и тупиковые. Тупики можно связать с различными тэгами и выставить ловушки на заданные тэги. При попадании в тупик формируется значение всей структуры, размещенной внутри ловушки. Используя тупикии ловушки, можно организовать перебор вариантов до первого беступикового варианта или собрать все беступиковые варианты. Второе можно сделать, используя отображения (map), а первое допускает метод первого подходящего, чо можно реализовать как слегка модифицированный evcon с добавочной ловушкой на прерывание при достижении успеха. Более сложно обеспечить равновероятность выборавариантов. Наиболее серьезно возможность такой реализации рассматривалась в проекте языка SETL. Похожие механизмы используются в языках, ориентированных на конструирование игр, таких как Grow, в которых можно в качестве условия срабатывания команды указать вероятность. В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто 131 формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств атома в языке Lisp. Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле. 6.3. Язык декларативного программирования Prolog Prolog является наиболее известным языком логического программирования общего назначения, ассоциируемый с проблемами искусственного интеллекта и компьютерной лингвистики. Он базируется на логике первого порядка и в отличие от обычных языков программирования приоритетно использует декларативность. Логическая программа выражается в терминах отношений, представляемых как факты и правила. Применялся для автоматизации доказательств теорем и разработки экспертных систем, включая лингвистические процессоры для естественных языков. Выполнение логической программы понимается как ответ на запрос над системой отношений. Отношения и запросы конструируются из термов и клауз. Язык программирования Prolog предложен в 1972 году А. Колмерауэром. ( Alain Colmerauer ), процедурную интерпретацию языка выполнил Р. Ковальский (Robert Kowalski) и дал еѐ описание в 1973 году, опубликованное в 1974 году. Практичность языка резко возросла благодаря созданию Д. Уорреном (David Warren) компилятора в 1977 году, что приблизило скорость символьной обработки к эффективности языка Lisp. Существует Pure Prolog в качестве семантического базиса языка, удобного для изучения основных механизмов Prolog-машины. Итеративные алгоритмы можно программировать как рекурсивные функции. Prolog-машина ищет ответ на запрос в имеющейся системе отношений и, если находит, то сообщает его. Опубликованы алгоритмы мета-интерпретатора для языка Pure Prolog, показывающие его самоприменимость и расширяемость. Определение Примечание Factorial (N, F) Factorial (0, 1) Factorial (x+1, F) ← F := Factorial (x, y) * (x + 1) Функция реализуется двумя клаузами: – констатация, что от 0 – значение 1; – декларация отношения между значениями функции на соседних числах 132 Пример 34. Вычисление факториала Определение Примечание partition([], _, [], []). partition([X|Xs], Pivot, Smalls, Bigs) :- ( X @< Pivot -> Smalls = [X|Rest], partition(Xs, Pivot, Rest, Bigs) ; Bigs = [X|Rest], partition(Xs, Pivot, Smalls, Rest) ). quicksort([]) --> []. quicksort([X|Xs]) --> { partition(Xs, X, Smaller, Bigger) }, quicksort(Smaller), [X], quicksort(Bigger). Разбиение на участки Запуск сортировки Пример 35. Быстрая сортировка Определение Примечание maplist(_P, [], []). maplist(P, [X1|X1s], [X2|X2s]) :- call(P, X1, X2), maplist(P, X1s, X2s). Отображать нечего Можно выделить начало Вызов от первого Отображение остального Пример 36. Отображение Определение Примечание mi1(true). mi1((A,B)) :- mi1(A), mi1(B). mi1(Goal) :- Goal \= true, Goal \= (_,_), clause(Goal, Body), mi1(Body). Равноправие вариантов. Продвижение к цели Пример 37. Расширяемый скелет Prolog-интерпретатора. Определение Примечание provable(true, _) :- !. Доказуемость 133 provable((G1,G2), Defs) :- !, provable(G1, Defs), provable(G2, Defs). provable(BI, _) :- predicate_property(BI, built_in), !, call(BI). provable(Goal, Defs) :- member(Def, Defs), copy_term(Def, Goal-Body), provable(Body, Defs). Варианты. Встроенные свойства. Движение к цели. Пример 38. Выводимость цели. Обобщение интерпретатора В определении функции provable(Goal, Defs)вырабатывается истина, если цель Goal выводима по отношению к Defs, представленным списком клауз в форме Head-Body. Полная реализация бектрекинга требует детерминированного накопления результатов. Отдельная альтернатива представляется как список целей и ветвей, которые могут использоваться как список альтернатив. Определение Примечание mi_backtrack_([[]-G|_], G). mi_backtrack_(Alts0, G) :- resstep_(Alts0, Alts1), mi_backtrack_(Alts1, G). Других вариантов нет. Перебор других вариантов. Пример 39. Бэктрекинг. Возвраты при неудачном выборе клаузы Если ни одна цель не доказана, то выбирается решение из внутренней очереди. Вторая клауза описывает вычисление. Существуют версии языка, приспособленные к работе с функциями высших порядков ( HiLog , λProlog ) и с модулями. Стандарт ISO языка Prolog поддерживает компиляцию, хвостовую рекурсию, индексирование термов, хэширование, обработку таблиц. Яркая реклама ЛП в рамках японского проекта компьютерных систем 5- го поколения утихла по мере прогресса элементной базы. Несмотря на широкое использование языка в научных исследованиях и образовании, логическому программированию пока не удалось внести существенный вклад в компьютерную индустрию. Весьма вероятно, что причина кроется в том, что любое производство предпочитает достаточно изученные задачи, а сильная сторона ЛП проявляется на классе недоопределѐнных задач. 134 Принято считать, что однозначное решение задачи в виде четкого алгоритма над хорошо организованными структурами и упорядоченными данными – результат аккуратной, тщательной работы, пытливого и вдумчивого изучения класса задач и требований к их решению. Эффективные и надежные программы в таких случаях – естественное вознаграждение. Однако в ряде случаев природа задач требует свободного выбора одного из вариантов – выбор произвольного элемента множества, вероятности события при отсутствии известных закономерностей, псевдослучайные изменения в игровых обстановках и сценариях, поиск первого подходящего адреса для размещения блока данных в памяти, лингвистический анализ при переводе документации и художественных текстов и т. д. При отсутствии предпочтений все допустимые варианты равноправны, поэтому технология их отладки и обработки должна обеспечивать формально равные шансы вычисления таких вариантов (похожая проблема характерна для организации обслуживания в сетях и выполнения заданий операционными системами. Все узлы и задания сети должны быть потенциально достижимы, если нет формального запрета на оперирование ими.). 6.4. Функциональная модель ЛП Первые реализации ЛП были выполнены на языке Lisp, поэтому основные механизмы можно рассмотреть как обработку списков. По смыслу выбор варианта похож на выбор произвольного элемента множества: { a | b | c } = э { a, b, c } Чтобы такое понятие промоделировать обычными средствами, нужны дополнительные примитивы. Например, при определении функции, выбирающей произвольный элемент списка, в какой-то момент L становится пустым списком, и его разбор оказывается невозможным, тогда действует вариант ESC. Чтобы определитьвыбор произвольного элемента из списка L , можно представить рекурсивное выражение вида: (любой L) = { (CAR L) | (любой (CDR L)) } По смыслу выбор варианта похож на выбор произвольного элемента множества: 135 { a | b | c } = э { a, b, c } Чтобы такое понятие промоделировать обычными средствами, нужны дополнительные примитивы с меньшей степенью организованности, чем вектора или множества. Уточнѐнную схему выбора произвольного элемента списка можно представить формулой вида: Определение Примечание (любой L) = { (car L) | (любой (cdr L)) | ESC } Множество из первого элемента списка, выбора любого из оставшихся элементов списка и тупика Пример 40. Тупик как равноправный вариант Более ясное определение имеет вид: Определение Примечание (любой L) = { (CAR L) | (любой (CDR L)) | (if (nl L) ESC) } Выбор тупикового варианта возможен лишь при отсутствии других Пример 41. В какой-то момент L становится пустым списком, и его разбор оказывается невозможным. Тогда действует ESC Другие построения, характерные для теории множеств: { x | P(X) } – множество элементов, обладающих свойством P Определение Примечание (F L) = {(if (P ( CAR L )) (CONS ( CAR L) (F ( CDR L))) ) | (if (nl L) ESC) } Соединяются в список по проверке предиката Тупик Пример 42. Выбор элементов списка, удовлетворяющих предикату Определение, данное в этом примере, недостаточно, т. к. порождаемые варианты элементов, удовлетворяющих заданному свойству, существуют в разные моменты времени и могут не существовать одновременно. Чтобы иметь все варианты одновременно, требуется еще один примитив ALL , обеспечивающий накопление всех реально осуществимых вариантов. 136 Определение Примечание (F L) = (ALL {(if (P ( CAR L )) (CONS ( CAR L) (F ( CDR L)) ) ) | (if (nl L) ESC) } ) Специальная форма для накопления всех результатов. Пример 43. Множество всех элементов списка, удовлетворяющих предикату Определение Примечание (ALL ( LAMBDA (x y) { (if (= x y) x) | ESC }) ( любой A) (любой B) ) Форма выбора элементов пересечения Перебор элементов двух множеств в произвольном порядке Пример 44. Пересечение множеств A и B Определение Примечание (if (not a) NIL b) a & b Пример 45. b вычисляется лишь при истинном a, что результативно, но не всегда соответствует интуитивным ожиданиям (логика, предложенная в свое время Маккарти, позволяет добиться высокой эффективности). Математически более надежны варианты, исключающие зависимость от порядка перебора: Определение Примечание (ALL( LAMBDA x { (if (not x) NIL ) | ESC }) {a | b} ) Если a и b оба истины, то получается ESC Пример 46. Такое значение отличается от NIL тем, что работает как истина Аналогичная проблема возникает при построении ветвлений. Определение Примечание ( (LAMBDA L {(COND ((eval(caar L)AL) (eval(cadr L)AL) )) | ESC }) ( любой ((p1 e1) (p2 e2) ... ) ) ) Снятие зависимости от порядка записи Пример 47. (cond (p1 e1) (p2 e2 ) ... ) Поддержка вариантов, каждый из которых может понадобиться при построении окончательного результата, находит практическое применение 137 при организации высокопроизводительных вычислений. Например, мультиоперации можно организовать с исключением зависимости от порядка отдельных операций в равносильных формулах. Определение Примечание ((LAMBDA (x y z) {(if (< (+ x y) K) (+ (+ x y) z)) | ESC} ) {(a b c) | (b c a) | (c a b)} ) Обеспечение максимальной вычислимости Пример 48. a+b+c = (a+b)+c = a+(b+c) = (a+c)+b – профилактика переполнения 6.5. Модели недетерминизма Необходимая для такого стиля работы инструментальная поддержка обеспечивается в GNU Clisp механизмом обработки событий throw-catch, для которого следует задать примерно такое взаимодействие. Определение Примечание (DEFUN vars (xl)(catch 'ESC (COND ((null xl)(escape)) ((CAR xl) (CONS (CAR xl)(vars (CDR xl)))) )) ) (DEFUN escape () (throw 'ESC NIL)) перебор вариантов до первого тупика vars not NIL сигнал о попадании в тупик (print(vars ())) (print(vars '(a))) (print(vars '(a b c))) (print(vars (list 'a 'b (vars ()) 'c))) Демонстрация Пример 49. Механизм обработки событий throw-catch как модель недетерминизма вариантов Следует отметить неисчерпаемый ряд задач, при решении которых удобно используются недетерминизм. 1. Обоснование упорядочений в традиционных алгоритмах. Выделяется доалгоритмический уровень, на котором просто анализируются таблицы возможных решений и постепенно вырабатываются комплекты упорядочивающих условий и предикатов. 2. Переформулировка задач и переопределение алгоритмов с целью исключения необоснованных упорядочений – одна из типовых задач оптимизации, особенно при переходе от обычных программ к 138 параллельным. Приходится выяснять допустимость независимого исполнения всех ветвей и управляющих их выбором предикатов. 3. Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах (многопроцессорная машина Тьюринга и т.п.). 4. Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность. 5. Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskell и др. 6. Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками. 7. Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах. 8. Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т. п. 9. Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т. п. В истории ЛП можно выделить ряд специфических линий: – абдуктивное логическое программирование; – металогическое программирование; – логическое программирование в ограничениях; – параллельное логическое программирование (FGCS – японский проект 5-го поколения компьютерных систем); – индуктивное логическое программирование; – линейное логическое программирование; – объектно-ориентированное логическое программирование; – транзакционное логическое программирование. 139 6.6. Спецификация Таб л иц а 3 5 Парадигматическая характеристика языков логического программирования Параметр Конкретика эксплуатационная прагматика ЯП Неопределенные постановки задач. Эмпирическое накопление рецептов, достаточное для решения некоторых практических задач. регистры абстрактной машины S E C D R S – стек промежуточных результатов. E – стек локальных переменных. C – стек основной программы. D – дамп для защиты и восстановления данных. R – стек для перебора вариантов. Результат – заключение об успехе-неудаче вывода цели. категории команд абстрактной машины Кроме типов команд, характерных для ФП: - выбор варианта; - восстановление контекста при переборе вариантов. реализационная прагматика В дополнение к ФП обработка разностных списков, отслеживание низкого приоритета тупиков и сечений. Вместо произвольного выбора варианта реально варианты перебираются в порядке представления. парадигматическая специфика Расширение класса решаемых задач использованием недетерминированных моделей. 140 ЛЕКЦИЯ 7. ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ При переходе к практическому программированию обычно возникают проблемы, связанные с изменением отношения к постановке задачи и оценке методов еѐ решения в процессе подготовки, отладки и эксплуатации программы. Прежде всего, необходимость в целостном решении полной задачи «с нуля» теперь встречается достаточно редко. Как правило, необходимо учитывать, что отчасти задача или похожие задачи уже имеют готовые решения. Их надо найти, изучить и выбрать фрагменты, наиболее подходящие для конструирования практичного решения нужной задачи. Обычно сложные задачи декомпозируются на модули, разрабатываемые отдельно, но функционировать модулям предстоит совместно. Кроме того, снижение трудозатрат на создание программ достигается программированием многократно используемых компонентов, условия применения которых заранее не известны. Решение таких проблем требует углубленного анализа структур данных и логики вычислений, обоснованного выбора методов обработки данных и декомпозиции программы на удобно комплексируемые фрагменты. Объектно-ориентированное программирование (ООП) в настоящее время – самый популярный подход к решению этих проблем для широкого класса задач, не требующих предельно жестких эксплуатационных характеристик. ООП рассматривает информационный процесс как частичную обработку объектов посредством реагирования на события с помощью методов, выбираемых в зависимости от типа обрабатываемых данных. Центральный момент – структурирование множества частных методов, используемых в программе, в соответствии с иерархией классов объектов, обрабатываемых этими методами, в предположении, что определяемые в программе построения могут локально видоизменяться при сохранении основных общих схем информационного процесса. Это позволяет выполнять модификации программы объявлением новых подклассов и дописыванием методов обработки объектов отдельных классов без радикальных изменений в ранее отлаженном тексте программы. Связь методов с классами объектов позволяет вводить одноименные методы над разными классами объектов (полиморфизм), что упрощает логику управления: на уровне текста программы можно не распознавать принадлежность классу – это сделает система программирования. Именно так обычно реализовано сложение и другие операции, одинаково изображаемые для чисел, строк, векторов, множеств и т. п. Основной принцип – выбор метода в зависимости от типа данных. 141 Сборка программы из автономно развивающихся компонентов опирается на формулировку достигаемой ими цели, понимание которой гарантирует не только корректность полученного результата, но и рациональность его использования. Формулировать цели частей программы – процесс нетривиальный. В его основе лежат различные подходы к классификации понятий. Для демонстрации преимуществ ООП следует рассматривать задачи, решение которых требует более одного шага. Первый шаг – программирование ядра программы или его комплектация из готовых модулей с оформлением иерархии классов объектов, содержащих первичный комплект методов. Второй и последующие шаги – развитие иерархии классов и/или перегрузка методов. Задачи, постановки которых допускают более одного сценария развития, потребуют ещѐ одного специального шага: определение абстрактных/виртуальных классов в качестве точек варьирования возможного развития постановки задачи. 7.1. Общее представление ООП объединяет в рамках единой методики организации программ классификацию на базе таких понятий как класс объектов, структура данных и тип значений. Тип значений обычно отражает спектр основных низкоуровневых реализационных средств, учет которых обеспечивает эффективность кода программы, получаемого при компиляции. Структура данных обеспечивает конструктивность построений, гарантирует ясный доступ к частям, из которых выстроено данное любой сложности. Класс объектов характеризуется понятным контекстом, в котором предполагается их корректная обработка. Обычно контекст содержит определения структуры объектов и их свойства. Текст программы одновременно представляет и динамику управления процессами и схему информационных потоков, порождаемых при исполнении программы. Кроме того, последовательность написания программы и ее модификации по мере уточнения решаемой задачи могут соответствовать логике, существенно отличающейся и от логики процесса выбора системных и реализационных решений и от логики применения реализованных решений. Обычно программирование скрывает сложность таких деталей управления процессами путем сведения его к общим функциям, преобразующим любые аргументы в определенные результаты. Модификации программы при развитии решаемой задачи нередко осуществляются непосредственно ручной переработкой текста программы и определений входящих в нее функций. 142 При анализе задач, решаемых в терминах объектов, некоторая деятельность описывается так, что постепенно продумывается все, что можно делать с объектом данного класса. Потом в программе достаточно лишь упоминать методы обработки объекта. Если методов много, то они структурированы по иерархии классов, что позволяет автоматизировать выбор конкретного метода. На каждом уровне иерархии можно немного варьировать набор методов и структуру объектов. Таким образом, описание программы декомпозируется на интерфейс и реализацию, причем интерфейс скрывает сложность реализации так, что можно обозревать лишь необходимый для использования минимум средств работы с объектом. Исходная гипотеза при программировании работы с объектами: объект не изменен, если на него не было воздействий из программы. Однако реальность зачастую требует понимания и учета более сложных обстоятельств, что может существенно продлить время жизни программы или ее компонентов. В таком случае удобно предоставлять объектам большую свободу, сближающую их с понятием субъекта, описание которого содержит все, что он может делать. Программа может давать ему команды-сообщения и получать ответы-результаты. Фактически субъектом является суперкласс, объединяющий классы объектов, обрабатываемые одноименными методами, т. е. функциями одного семейства. Так, при организации сложения можно считать, что существует суперкласс «слагаемые», которое умеют складываться с другими слагаемыми. При этом они используют семейство функций – методов, реализующих сложение. В зависимости от полноты семейства результат может быть получен или не получен. Семейство легко пополняется добавлением одноименных функций с новыми комбинациями типов параметров. Дальнейшее развитие подходов к декомпозиции программ связано с выделением отдельных аспектов и шагов при решении сложных задач. Понятие аспекта связано с различием точек зрения, позволяющим описывать решение всей задачи, но отражать в описании только видимые детали. По мере изменения точек зрения могут проступать новые детали до тех пор, пока дальнейшая детализация не утрачивает смысл, т. е. улучшение трудно заметить или цена его слишком высока. Так, представление символьной информации в Lisp-е выделено в отдельный аспект, независимый от распределения памяти, вычисление значений четко отделено от компиляции программ, понятие связывания имен с их определениями и свойствами не зависит от выбора механизмов реализации контекстов исполнения конструкций программы. 143 Разработка сложной программы может рассматриваться как последовательность шаговпроцесса раскрутки программ, оправданным в тех случаях, когда целостное решение задачи не может гарантировать получение приемлемого результата в нужный срок – это влечет за собой непредсказуемо большие трудозатраты. Удобный подход к организации программ «отдельная работа отдельно программируется и отдельно выполняется» успешно показал себя при развитии операционной системы UNIX как работоспособный принцип декомпозиции программ. Но существуют задачи, например, реализация систем программирования, в которых прямое следование такому принципу может противоречить требованиям к производительности. Возможен компромисс «отдельная работа программируется отдельно, а выполняется взаимосвязано с другими работами», что требует совмещения декомпозиции программ с методами сборки – комплексации или интеграции программ из компонентов. Рассматривая комплексацию как еще одну «отдельную» работу, описываемую, например, в терминах управления процессами, можно констатировать, что эта работа больше определяет требования к уровню квалификации программиста, чем объем программирования. При достаточно объективной типизации данных и процессов, возникающих при декомпозиции и сборке программ определенного класса, строят библиотеки типовых компонентов и разрабатывают компонентные технологии разработки программных продуктов – Corba, COM/DCOM, UML и т. п. Одна из проблем применения таких компонентов – их обширность. Таким образом, ООП может отражать эволюцию подходов к организации структур данных на уровне задач и программ их решения, исходя из парадигмы императивно-процедурного программирования. От попыток реализации математически корректных абстрактных типов данных произошел практичный переход к технически простому статическому контролю типов данных при разработке и применении расширяемых программ. Расширение программы выполняется декларативно, а выбор нужного варианта при исполнении функций, обладающих неединственным определением, – в зависимости от типа данных. Введены дополнительные механизмы: инкапсуляция, уточнение типов данных при компиляции и выбор обработчиков данных, управляемый типами данных. Механизмы ООП обеспечивают наследование свойств по иерархии классов объектов и так называемый «дружественный» доступ к произвольным классам. Расширение программ при объектно- ориентированном подходе к программированию выглядит как простое дописывание новых определений. Библиотеки типов данных и методов их 144 обработки легко вписываются в более общие системы. Спецификация интерфейсов в принципе может быть сопровождена верификацией реализации компонент. Возможна факторизация программ на компоненты и рефакторизация программных компонент в стиле экстремального программирования. ООП структурирует множество частных методов, используемых в программе, в соответствии с иерархией классов объектов, обрабатываемых этими методами, реализуемыми с помощью функций и процедур, в предположении, что определяемые в программе построения могут локально видоизменяться при сохранении основных общих схем информационной обработки. Это позволяет выполнять модификации объявлением новых подклассов и дописыванием методов обработки объектов отдельных классов без радикальных изменений в ранее отлаженном тексте программы. 7.2. Абстрактная машина АС включает в себя аналоги ИП, ФП и ЛП с добавлением выбора метода в зависимости от класса объектов. АМ для языков ООП можно базировать на АМ для процедурно- императивных языков стандартного прикладного программирования. Абстрактная машина для ОО-языка по структуре похожа на объединение машин для ФП и ИОП: AMO = < RO, SCO>, где SCO= S – стек операндов и результатов вычислений. E – значения локальных переменных при вызовах функций. C – текущий стек программы. D – дамп, обеспечивающий восстановление контекста программы при выходе из метода. M – общая память, хранящая константы, методы и объекты с их сигнатурами. Обозначения: <[cm], ts> – код метода, таблица символов 145 Представление класса содержит сведения о числе констант и информацию о них, флаги доступа к полям объектов класса, ссылки на объект и суперкласс, число полей и информацию о них, число методов и информацию о них. Сигнатура представляется символьной характеристикой полей объекта или параметров метода. Значения реализованы как структура данных с тегами, задающими тип элемента данных. Классы, поля и методы не являются значениями и хранятся без тэга. Таб л иц а 3 6 |