KRIEGSSPIELE!
Вы хотите отреагировать на этот пост ? Создайте аккаунт всего в несколько кликов или войдите на форум.

Техника в руках дикаря

Участников: 2

Перейти вниз

Техника в руках дикаря Empty Техника в руках дикаря

Сообщение автор Gudleifr Ср Фев 05, 2020 4:42 pm

Когда-то начал эту тему по аналогии с соседской - о написании Андроид-FORTH-скриптовой системы. Тема сначала быстро быстро превратилась в блог, а затем заглохла, дав начало некоторым далеко уводящим в сторону писаниям-размышлениям.

Краткое содержание предыдущих серий...

Если отбросить всю лабуду о всеобщей космической неотвратимости, то в сухом остатке - только наличие у меня старого (года этак 2007-го) наладонника HP iPAQ под управлением Windows Mobile. Все эти годы использовал его только для чтения и правки текстовых файлов в жутко неудобном упрощенном MS Word. Нормальных рисовалок и читалок эл.книг для него подобрать так и не смог. Но, может, его можно запрограммировать на что-то полезное?

В качестве средства программирования (после многократных проб и ошибок) нашелся старый пакет Pelles C. Этот Си-обезьянник легко запускается и лихо создает на настольном компьютере, но для наладонника пустое красивое пустое приложение ("Hello, world!")... И все. Далее следует два неприятных момента. 1) Из документации - только несколько старых примеров; 2) программировать можно только на настольном компьютере, а запускать - только на наладоннике.

Однако, наладонник имеет еще и огромный недостаток - малый размер экрана. Если разместить на нем много кнопочек и окошечек, ничего путного не влезет. Поэтому я решил ограничиться одним органом управления. По возможности универсальным. Окном редактирования текста. Итак, окно редактирования и два куцых меню, для которых наладонный Мастдай отводит место внизу экранчика.

Вот на этом я тогда и остановился. Просто потому, что оба рабочих цикла оказались слишком тормозящими: 1) цикл подготовки и переноса рабочих документов с настольной машины на наладонник и обратно и 2) цикл перекомпиляции рабочей программы. Задачи, которая бы это окупила, тогда так и не появилось.
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Сб Ноя 12, 2022 12:58 am

Опыт Pelles-программирования дал крайне неудовлетворительные результаты. Большинство текущих задач я решаю вручную, не успевая написать для них программу. Цикл программирования и отладки по-прежнему занимает слишком много времени.

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

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

2) Сильно мешает MS Word. Можно предположить два варианта построения системы. Как я описывал в "Заметках", можно постепенно преобразовывать файлы. Но для этого нужно иметь гарантии, что ни один из изменяемых файлов не открыт в родном редакторе наладонника - MS Word. Иначе информация будет непоправимо повреждена. Но Мастдай подобных гарантий не дает. Остается более неудобный вариант - извлекать кусок из MS Word в карман, править его в приложении и запихивать обратно.

3) Аналогично надо раз и навсегда решить, использовать ли системные функции Windows или их UNIX-оболочки из комплекта Pelles-C. Основные подобные функции - работы с файлами и динамическим выделением памяти. Я выбрал второй вариант (эмуляции UNIX) - так проще.

4) Смешно, но работая с интерпретаторами, я совершенно отвык от хранения текстовых строк в честных массивах. А Мастдай тут помощник плохой. В отличие от BASIC-ов, хранить данные в визуальных объектах невозможно. Надо быть готовым по любому клику считывать данные из объектов в специально выделенные буферы, обрабатывать их там, и закачивать обратно.
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор vikt144 Вс Ноя 13, 2022 2:04 am

Gudleifr пишет: Смешно, но работая с интерпретаторами, я совершенно отвык от хранения текстовых строк в честных массивах.
По-моему, это ад везде, в web , в java и прочих. Приходится разбиратся с появлением крокозябр. А у UTF еще
длинны символов разные. Найти N'ый символ в строке - адовая задача.

vikt144

Сообщения : 128
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Вс Ноя 27, 2022 12:18 am

ЛИРИЧЕСКОЕ ОТСТУПЛЕНИЕ
о том, как неумеренность в работе с символами породила идею ЭВМ пятого поколения.

Японский 11-томник по микроэлектронике
Т.9. КОМПЬЮТЕРЫ НА СБИС. Кн.2. 1988
4. ОБРАБОТКА СИМВОЛОВ
Х.ТАНАКА, М.САКАУТИ (разд.4.5)
Перевод Э.К.Николаевой

Частичное наделение ЭВМ человеческими мыслительными способностями является одной из важных задач исследований в области искусственного интеллекта. Основные трудности при этом вызывает проблема, каким образом вложить в ЭВМ возможность свободно оперировать символами подобно тому как это делает человек. Методы обработки символов составляют существенную часть этой проблемы.

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

В разд. 4.1 раскрывается связь между обработкой символов и техникой СБИС. В разд.4.2 рассматриваются основные операции системы обработки цепочек литер, являющейся одной из разновидностей обработки символов, и наиболее важные алгоритмы сравнения цепочек литер. Кроме того, описываются некоторые системы обработки естественных языков, состоящих из слов, представляющих собой последовательности из нескольких букв, и иллюстрируется их применение. В разд.4.3 рассматриваются обработка символов и механизм логического вывода в связи с логическим программированием. Раздел 4.4 посвящен архитектуре Лисп-компьютера и Пролог-компьютера, аппаратно реализующих языки обработки символов Лисп и Пролог. В разд.4.5 рассматриваются средства обработки графической информации, используемые для формирования и индикации изображений (чертежей), н техника их реализации.

4.1. ОБРАБОТКА СИМВОЛОВ И ТЕХНИКА СБИС
Связь между обработкой символов, включая числа (как при обработке графической информации, рассматриваемой в разд.4.5), и техникой СБИС поясняется в гл.2. В данном разделе рассматривается связь между обработкой символов в узком смысле (без учета чисел) и техникой СБИС.

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

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

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

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

Вторая проблема обработки символов связана с выделением основных операций. Язык программирования, предназначенный для обработки символов (называемый языком обработки символов), должен быть организован так, чтобы в него можно было ввести выделенные основные операции. Лисп и Пролог являются типичными языками обработки символов. Лисп получил наиболее широкое распространение главным образом в США, и уже накоплен богатый опыт его использования для обработки символов. Однако Лисп, как выяснилось, обладает рядом недостатков. В спецификацию языка невозможно ввести операции сравнения изображений, являющиеся основными при обработке символов, и операции логического вывода; невозможно ввести также общие понятия, называемые "объектами", эффективные в случае представления интеллекта, и т.д. Для разрешения этих трудностей ведется работа по расширению языка Лисп, разработке новых языков обработки символов, таких как Пролог и Смолток, а также по совместному развитию двух указанных направлений. Более того, все больший объем приобретают исследования, направленные на создание языков, предназначенных для параллельной обработки символов.

Третьей проблемой обработки символов является эффективное описание процедур. Вообще говоря, процедура решения той или иной задачи не определяется однозначно. Она может быть представлена различными способами. Однако обычно отдают предпочтение процедурам, требующим времени, порядок которого выражается многочленом, а не степенным показателем. Разработка эффективных процедур и алгоритмов - это большая исследовательская задача. С другой стороны, можно представить себе не универсальную ЭВМ, использующую языки Лисп и Пролог, а машину, непосредственно реализующую их аппаратными средствами. Лисп-компьютер, созданный в Массачусетском технологическом институте (МТИ), уже производится коммерчески. В конце 1983г. японской организацией по разработке компьютерной техники новых поколений (ICOT) была создана опытная модель Пролог-компьютера. Машины для обработки символов вступают уже в новую стадию развития.

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

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

Хорошо известно, что при создании сложных систем обработки символов требуются большие вычислительные мощности. Вычислительные системы с разделением времени появились в результате стремления разделить во времени вычислительную мощность одной ЭВМ и распределить ее (также во времени) между многими пользователями. Однако по мере увеличения числа пользователей и усложнения систем обработки символов становилась ясной нецелесообразность использованию одной ЭВМ с временным распределением ее мощности между большим числом пользователей. Как путь к решению возникшей проблемы в начале 1970-х гг. стала обсуждаться идея использования исследователями персональных машин для обработки символов. Первым результатом работ, развернутых в этом направлении, является Лисп-компьютер. Относительно недавно разработан рассматриваемый в подразд.4.4(в) Пролог-компьютер, в основу которого положен новый механизм вычислений. Высказываются также идеи реализации машин для обработки символов с архитектурой ненеймановского типа. Внедрение техники СБИС в область обработки символов должно привести к ускорению разработок компьютеров новой архитектуры, в которых задачи, прежде решаемые с помощью программного обеспечения, будут решаться аппаратными средствами. Поэтому исследователи, занимающиеся вопросами архитектуры, должны быть хорошо знакомы с основными идеями и проблемами программного обеспечения, а также с различными алгоритмами обработки символов. При написании разделов 4.2 и 4.3 преследовались именно эти цели.
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Пн Ноя 28, 2022 1:05 am

4.2. СИСТЕМЫ ОБРАБОТКИ ЦЕПОЧЕК ЛИТЕР
(а) ОСНОВНЫЕ ОПЕРАЦИИ ОБРАБОТКИ ЦЕПОЧЕК ЛИТЕР
Одной из разновидностей обработки символов является обработка цепочек литер. Цепочка литер представляет собой одномерный ряд из нескольких одиночных букв. Типичным языком для обработки цепочек литер является Снобол. Ниже поясняются основные операции обработки цепочек литер, представленные на языке Снобол 4. Вычислительные системы могут обрабатывать любые символьные последовательности, зрительно воспринимаемые человеком. Таким образом, цепочки литер могут иметь следующий вид:

Техника в руках дикаря Jap17510
1) Записано знаками японской азбуки "катакана".- Прим. перев.
2) Записано японскими иероглифами.- Прим. перев.

Цепочки литер заключаются в кавычки ('). В примере (IV) приведена пустая цепочка литер. Длина пустой цепочки литер равна 0.

Для обработки цепочки литер используются следующие пять основных операций.
(1) Объединение нескольких цепочек литер и создание новой цепочки литер (конкатенация цепочек литер).
(2) Сравнение двух цепочек литер (сопоставление цепочек литер).
(3) Замена одной цепочки литер на другую цепочку (замещение цепочек литер).
(4) Выборка части из некоторой цепочки литер (выборка цепочки литер).
(5) Установка курсора в нужную позицию при сканировании цепочки литер.

При выполнении операции (3) замещения цепочки литер вместо замены всей цепочки литер на абсолютно новую часто для получения новой цепочки переписывают только часть старой. Для того чтобы узнать, какой именно участок цепочки литер должен быть выбран, также необходимо сопоставление с образцом. Отсюда ясно, что наиболее важной операцией при обработке цепочек литер является операция (2) сопоставления цепочек. Операция (1) представляет собой объединение нескольких коротких цепочек литер с образованием длинной цепочки, а операция (4) в противоположность ей является операцией выделения коротких цепочек литер из длинных цепочек. Как будет показано ниже, с помощью операции замещения цепочек литер можно в нужное место одной цепочки вставлять другую цепочку, добавлять к одной цепочке другую, удалять часть цепочки литер.

Выполнение операции сопоставления двух цепочек литер требует значительных затрат времени. В подразд.4.2(б) данной главы описывается эффективный алгоритм сопоставления двух цепочек литер. Содержание операции (5) установки курсора в нужное положение очевидно, поэтому пояснение ее опускается.

(1) КОНКАТЕНАЦИЯ ЦЕПОЧЕК ЛИТЕР
Операция конкатенации цепочек литер заключается в объединении нескольких цепочек литер с образованием новой (длинной) цепочки. Например, если на языке Снобол 4 записать две отдельные цепочки литер

Техника в руках дикаря Jap17610
1) компьютер (записано знаками катаканы).- Прим. перев.
2) архитектура (записано знаками катаканы).- Прим. перев.

и задать над ними операцию

Z = X '.' Y (4.3)

то (4.3) эквивалентно

Техника в руках дикаря Jap17710
1) архитектура компьютера (записано знаками катаканы).- Прим. перев.

В языке Снобол 4 конкатенация сводится к записи цепочек литер друг за другом, как видно из (4.3), и не отражается на объединяемых цепочках литер; между ними просто оставляется один пробел. В случае использования операции конкатенации в рамках операции сопоставления цепочек литер, поясняемой ниже, для устранения разночтений допускается заключение цепочки литер в скобки. Такие формы записи, как

Техника в руках дикаря Jap17711

эквивалентны (4.3).

(2) СОПОСТАВЛЕНИЕ ЦЕПОЧЕК ЛИТЕР, ЗАМЕЩЕНИЕ ЦЕПОЧЕК ЛИТЕР, ДЕЛЕНИЕ ЦЕПОЧЕК ЛИТЕР
Операция сопоставления двух цепочек литер на языке Снобол 4 записывается в следующем виде:

<Сравниваемая цепочка литер> <Образцовая цепочка литер> (4.7)

В этом случае, если <сравниваемая цепочка литер> входит в <образцовую цепочку литер>, то сопоставление оказывается успешным. Например, если после (4.1), (4.2), (4.3) записать

Техника в руках дикаря Jap17712

то в обоих случаях сопоставление будет успешным. Но, если записать

Техника в руках дикаря Jap17713

сопоставление будет иметь отрицательный результат.

(4.8 ), (4.9), (4.10) относятся к очень простым примерам сопоставления цепочек литер. Рассмотрим теперь сопоставление более сложных цепочек.

В качестве <образцовой цепочки литер> может быть использована структурная цепочка, в которой имеется оператор, указывающий на наличие двух членов, |. Если S1 и S2 - цепочки литер или структурные цепочки литер, то можно получить новую структурную цепочку литер S3 следующим образом:

S3 = S1 | S2 (4.11)

S3 представляет собой структурную цепочку литер, для которой производится сравнение образов с какой-либо из цепочек S1, S2. Например [В этом примере в виде транскрипций записано звучание иероглифов, причем отдельным символам (иероглифам) соответствуют слоги, которые следует воспринимать как одиночные буквы буквенной последовательности.- Прим, перев.], если записать

А = 'сю' | 'кай' | 'хо' (4.12)
В = 'нин' | 'дай' (4.13)
С = (А В) | (В 'и') (4.14)

то это значит, что производится сопоставление образов С и одной из следующих восьми цепочек (обратите внимание на то, что в (4.14) осуществляется конкатенация структурных цепочек):

'сю нин' 'кай нин' 'хо нин' 'нин и' 'сю дай' 'кай дай' 'хо дай' 'дай и' (4.15)

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

'кай дай' С (4.16)

проводится сопоставление образов цепочек литер (4.15), образованных из структурной цепочки С, с образом сравниваемой цепочки 'кай дай'. Проведем это сопоставление для цепочек (4.15) слева по порядку. Сопоставление образов начинается со сравнения 'кай дай' и 'сю нин'. Поскольку различными оказываются первые символы, в качестве следующей возможной образцовой цепочки берется 'кай нин'. В этом случае имеет место совпадение по одной (первой) литере (символ 'кай'), однако вторые символы не совпадают. Поэтому теперь в качестве (образцовой цепочки литер) для сравнения берется 'кай дай'. При этом сравнение цепочек литер (4.16) оказывается успешным.

Как ясно из проведенного рассуждения, для выполнения поочередного сопоставления образов при сравнении со структурной цепочкой литер необходима обработка с применением отступа. Таким образом, для сравнения образов <сравниваемой цепочки литер> и <образцовой цепочки литер>, в состав которой включена структурная цепочка, необходим механизм эффективной обработки с применением отступа. Дело в том, что моделирование этого процесса с помощью программных средств обходится очень дорого.

Представим себе машину для обработки литер, выполняющую эту обработку аппаратными средствами. Это должна быть машина для обработки цепочек литер, в основу функционирования которой положена операция сопоставления цепочек литер. С точки зрения представления программы обработки цепочек литер сравнение цепочек, включающих структурные цепочки, было бы чрезвычайно полезной операцией. Чтобы она была отражена в архитектуре машины, предназначенной для обработки цепочек литер, аппаратные средства должны содержать механизм, выполняющий операцию сопоставления цепочек литер с помощью отступа. Очевидно, что такие аппаратные средства должны быть довольно сложными. Но благодаря прогрессу в технике СБИС появится возможность повышения эффективности выполнения операции сопоставления цепочек литер, и не только за счет того, что станет менее вероятным появление крупных неисправностей, но и за счет введения механизма, выполняющего сопоставление цепочек с использованием распараллеливания.

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

Рассмотрим следующий пример описания операции замещения цепочки литер на языке Снобол 4. После (4.1), (4.2), (4.3) выполним (4.17):

Техника в руках дикаря Jap17910
[В японской азбуке отдельные знаки представляют собой слоги, поэтому транскрипция этого слова выглядит как набор слогов. Далее пример рассматривается в русской транскрипции знаков слоговой азбуки "катакана".- Прим. перев.]

Слева от знака равенства представлена операция сопоставления цепочек литер. Если имеется в виду, что Z - <сравниваемая цепочка> - представляет собой 'ко н пю та . а ки тэ ку тя', a Y - <образцовая цепочка> - 'а ки тэ ку тя', то эта операция сопоставления успешна. При этом (4.17) выполняет перестановку цепочки литер Y, входящей в Z, вправо от знака равенства. Таким образом, Z после выполнения (4.17) заменяется на 'ко н пю та . си су тэ му'.

Рассмотрим также для примера случай, когда в Z перед выполнением (4.17) включено несколько частичных цепочек литер 'а ки тэ ку тя'. На языке Снобол 4 этот случай может быть точно представлен, если будет предусмотрен режим, при котором все 'а ки тэ ку тя' в Z будут заменены на 'си су тэ му', и режим, при котором Z будет просмотрена слева направо, и на 'си су тэ му' в Z будет заменена только 'а ки тэ ку тя', обнаруженная первой.

С помощью операции замещения цепочек литер в указанном месте некоторой цепочки может производиться вставка произвольной цепочки, добавление, удаление некоторой части цепочки. Если имеем цепочки литер

Z = 'ко н пю та . а ки тэ ку тя' (4.18)
Z '.' = '. си су тэ му .' (4.19)

то после выполнения (4.19) можно записать эквивалентное выражение

Z = 'ко н пю та . си су тэ му . а ки тэ ку тя' (4.20)

в котором цепочка литер оказалась вставленной в указанное место.

Если после выполнения (4.19) записать

Z '. си су тэ му' = '' (4.21)

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

Теперь рассмотрим пример описания на языке Снобол 4 операции выделения буквенных последовательностей. Перепишем (4.12) и (4.13):

А = 'сю'|'кай'|'хо' (4.12)
В = 'нин'|'дай' (4.13)
D = (А . X В . Y) . Z (4.22)

Если D (4.22) используется в качестве <образцовой цепочки литер>, то это выражение можно рассматривать как цепочку, в которой цепочка В стоит сразу после цепочки А. Форма записи А . Х означает, что если сопоставление производится при условии, что А включена в <сравниваемую цепочку литер>, то сравниваемая цепочка распространяется на X. После выполнения (4.12), (4.13), (4.22) выполним операцию сопоставления цепочек литер (4.23).

'бун-но сю дай то се тэн' D (4.23)

То, что операция (4.23) успешна, очевидно, так как в D из (4.23) входит часть <сравниваемой цепочки литер> 'сю дай'. При этом производится выделение из X цепочки литер 'сю', из Y - цепочки литер 'дай', из Z - цепочки литер 'сю дай'. Таким образом может быть выполнено выделение из (сравниваемой цепочки литер) заданной части цепочки.

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

(б) АЛГОРИТМЫ СОПОСТАВЛЕНИЯ ЦЕПОЧЕК ЛИТЕР
Операции сопоставления цепочек литер, даже включающих структурные последовательности, как было показано в разд.4.2(а), в конце концов сводятся к сопоставлению простых цепочек, не содержащих никаких структур. В данном разделе рассматриваются алгоритмы выполнения сопоставления простых цепочек литер, не имеющих структур.

(1) АЛГОРИТМ СОПОСТАВЛЕНИЯ ПРОСТЫХ ЦЕПОЧЕК ЛИТЕР
Алгоритм сопоставления самых простых цепочек заключается в том, что левые концы <сравниваемой цепочки литер> и <образцовой цепочки литер> располагаются точно один под другим, после чего соответствующие литеры обеих цепочек слева по порядку проверяются на совпадение. Если все соответствующие друг другу литеры цепочек совпадают, сопоставление оказывается успешным. В противном случае всю (образцовую цепочку литер) сдвигают на одну литеру вправо и повторяют проверку на совпадение (рис.4.1).

Техника в руках дикаря Jap18210
Рис.4.1. Операция сопоставления простых цепочек литер. Если сравнение не имело успеха, <образцовая цепочка литер> сдвигается на одну позицию вправо. Стрелка указывает позицию, в которой обнаружено несовпадение.

Если длину (число букв) <сравниваемой цепочки литер> обозначить через m, а длину <образцовой цепочки литер> - через n (при условии m>=n), то ясно, что при использовании этого алгоритма сопоставления цепочек в наихудшем случае придется провести проверку на совпадение n*(m-n) пар литер.

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

(2) МЕТОД КМП
[Метод назван по первым буквам фамилий авторов.- Прим. перев.]

Эффективный алгоритм сопоставления цепочек литер, названный методом КМП, был предложен Моррисом и развит Кнутом, Моррисом и Праттом.

Представим <сравниваемую цепочку литер> и <образцовую цепочку литер> в виде одномерных массивов subject[1:m] и pattern[1:n]. На рис.4.1. стрелкой указаны позиции, в которых сравнение окончилось неудачей. Сравнение окончилось неудачей в случае (а) в позиции subject[1], в случае (б) - в позиции subject[4], в случае (в) - в позиции subject[3]. Низкая эффективность алгоритма сопоставления простых цепочек литер, рассмотренного в подразд.4.2(б)(1), объясняется тем, что, например, после того как обнаруживается несовпадение в позиции subject[4] на рис.4.1,6, операцию сопоставления на следующем этапе в случае (в) приходится начинать с позиции subject[3], находящейся левее subject[4]; сравнение производится по одной литере, причем сравниваемая последовательность просматривается несколько раз в прямом и обратном направлениях.

При использовании метода КМП можно выполнять операцию сопоставления, проверяя на совпадение по одной литере элементы <равниваемой цепочки литер> только в прямом направлении - слева направо (без возвращения к началу). Поэтому в случае, когда сравнение с первой литерой <образцовой цепочки литер> оказывается успешным, а сравнение после смещения курсора сравниваемой литеры далее чем на две позиции вправо - неудачным (рис.4.1,б), можно избежать сравнения первой литеры <образцовой цепочки> и subject[3] (рис.4.1,в), сдвигая <образцовую цепочку литер> на одну позицию вправо. Например, если в случае, показанном на рис.4.1,б, перейти не к варианту (в), а к варианту (в'), сдвинув <образцовую цепочку литер> всю целиком на две позиции вправо, и обеспечить таким образом возможность сравнения первой литеры <образцовой цепочки литер> и subject[4], то можно исключить все неудачные сравнения цепочек литер с несколькими просмотрами <сравниваемой цепочки> в прямом и обратном направлениях. Метод КМП дает алгоритм, обеспечивающий исключение сравнений, и является высокоэффективным методом сравнения цепочек литер.

МЕТОД КМП
Пусть при сравнении образов subject[1:m] <сравниваемой цепочки литер> и pattern [1:n] <образцовой цепочки литер> первое неудачное сравнение оказалось между subject[k] и pattern[j]. В этом случае после элемента subject[k] обеспечивается начало следующего сравнения, причем, сдвигая <образцовую цепочку литер> на несколько позиций вправо, можно решить, осуществимо ли успешное сравнение с subject[k]. Как будет показано ниже, эта можно подсчитать иа этапе задания <образцовой цепочки литер>. Если обозначим этот этап как next[j], то операция сравнения цепочек литер, согласно методу КМП, будет описываться следующим образом:

j := k := 0
while j<=m and k<=n do begin
while j>0 and subject[k] != pattern[j] do j := next[j];
k := k+1; j := j+1;
end; (4.24)

next[1:m] можно подсчитать следующим образом. Как и вначале, сравнение производится до subject[k], и как только встречается первое неудачное сравнение с pattern[j] (рис.4.2,а), будет иметь место (4.25), (4.26):

Техника в руках дикаря Jap18410
Рис.4.2. Сопоставление <сравниваемой цепочки литер> и <образцовой цепочки литер>. Сравнение производится слева направо.
а - положение, при котором неудачное сравнение впервые имеет место между subject[k] и pattern[j]; б - положение, при котором <образцовая цепочка литер> сдвинута вправо на i позиций.

subject[k-j+1] ... subject[k-1] = pattern[1] ... pattern[j-1] (4.25)
subject[k] != pattern[j] (4.26)

Рис.4.2,б отражает случай, когда <сравниваемая цепочка литер> зафиксирована в положении, показанном на рис.4.2,а, а <образцовая цепочка литер> сдвинута вправо только на i (i<j) позиций. На рис.4.2,б видно, что в результате просмотра одной только <образцовой цепочки литер> можно решить, успешным ли будет сравнение subject[k-j+1+i] и pattern [1] и т.д. (по аналогии), subject[k-1] и pattern[j-i-1], поскольку из (4.25) следует, что

subject[k-j+1+i] = pattern[j+1] ... subject[j-1]=pattern[j-1] (4.27)

Следовательно, в положении, показанном на рис.4.2,а, сдвигая <образцовую цепочку литер> всякий раз на одну позицию вправо, можно делать заключение об успехе или неудаче сопоставления ее с соответствующей <сравниваемой цепочкой литер>, анализируя только <образцовую цепочку литер> независимо от <сравниваемой цепочки литер>.

Таким образом, начиная с момента, когда <образцовая цепочка литер> оказывается сдвинутой из положения, показанного на рис.4.2,а, на i (i<j) позиций вправо, сравнение со <сравниваемой цепочкой литер> всех букв (образцовой цепочки литер) от первой до (j-i-1)-й будет успешным, причем в случае pattern [j-i] != pattern [j] сравнение с subject[k] можно будет продолжать после сдвига всей <данной буквенной последовательности> из положения, показанного на рис.4.2,а, на i букв вправо (рис.4.2,6). В этом случае положим

next[j] = i (i<j)

Поскольку i = j,

next[j] = 0

Если <образцовая цепочка литер> задана таким образом, можно предварительно подсчитать next [1:n]. Поскольку время подсчета next[1:m] (в предположении, что next[1] = 0), должно составлять О(m), ясно, что алгоритм сопоставления цепочек литер (4.24) по методу КМП с участием next[1:m] требует времени подсчета O(m+n).

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

(3) ОПЕРАЦИЯ УНИФИКАЦИИ
Выше мы рассматривали алгоритмы сопоставления двух цепочек, отличающихся содержанием (включая переменные). Здесь же рассмотрим алгоритмы, используемые для автоматического доказательства теорем, называемого операцией унификации. Язык Пролог, который описан в подразд.4.3(6)(1), реализуется на основе операции унификации. Следовательно, Пролог-компьютер, пояснения к которому приведены в подразд. 4.4(в), служит для реализации операции унификации аппаратными средствами и создан с целью ускорения этой операции.

Как будет показано ниже, при этом рассматриваются три типа цепочек литер, представляющих собой 1) постоянные (цепочки, начинающиеся со строчных букв: boy, John и т.д.); 2) переменные (цепочки, начинающиеся с прописных букв: XY, John и т.д.) и 3) смешанные члены (представление функций: noun(X, Y), mortal(socrates) и т.д.). Все они имеют общее наименование - "члены". В смешанные члены могут входить и переменные. Аргументами функций могут быть все три выше упомянутых типа членов.

В случае когда имеется несколько членов, можно произвести такую замену входящих в них переменных, в результате которой все эти члены станут одинаковыми. Такая операция называется операцией унификации. Например, для унификации последовательностей birthday(X, [23, 11, 1968]) и birthday (John, [23, MONTH, 1968]) можно переменную X заменить на John, переменную MONTH заменить на 11 (выражение [23, MONTH, 1968] называется списком, это разновидность смешанного члена). Замены, выполняемые в этом примере, представляются следующим образом: {X<-john, MONTH<-11}.

При замене соблюдается одно ограничение. Оно заключается в том, что заменяемая переменная не может иметь места справа от стрелки, как, например, X<-f(X). Это условие называется правилом местонахождения, и если его не соблюдать, то X может стать членом неограниченной длины (например, Х => f(Х) => f(f(X)) =>...). Если все выражение, являющееся объектом унификации, обозначить через Е, то результат выполнения замены "сигма" будет выражаться как Есигма. Например, если сигма = {X<-john}, a E = birthday(X, [23, MONTH, 1968]), то Есигма = birthday(John, [23, MONTH, 1968]). Если тау = {MONTH<-11}, то [Есигма]тау = birthday(john, [23, 11, 1968]). Этот результат идентичен Емю при использовании для Е замены мю = {X<-john, MONTH<-11}. В этом случае мю называется объединением замен сигма и тау и обозначается как мю=сигма*тау. В общем случае этому можно дать следующее определение.

Если положить сигма= {Xi<-Si, ..., Xn<-Sn}, тау = {Yi<-T1, ..., Ym<-Tm}, то объединение сигма*тау представляет собой множество

{X1<-S1тау, ..., Xn<-Snтау, Yi<-T1, ..., Ym<-Tm}

при этом 1) запрещены замены, нарушающие вышеуказанное условие ограничения замен, и 2) запрещены замены Yi<-Ti, если Y1 входит в {Х1 ..., Xn}.

Прежде чем привести алгоритм выполнения операции унификации, дадим определение расходящегося множества. Расходящееся множество представляет собой совокупность членов, для которых при почленном сравнении слева направо в порядке очередности пар выражений, являющихся объектами унификации (например, простых логических выражений (human(socrates), birthday(X, [23, 11, 1984]) и т.д.), обнаружено несовпадение (первое по порядку). Например, для пары birthday(X, [23, 11, 1984]) и birthday(john, [23, MONTH, 1984]) расходящимся множеством будет {John, X}.

Теперь приведем алгоритм Чанга и Ли для операции унификации.

ОПЕРАЦИЯ УНИФИКАЦИИ
Шаг 1. Положить k = 0; обозначить множество выражений, являющихся объектами унификации, через Wk. Сделать замену сигмаk = { } (пустое множество).
Шаг 2. В случае когда множество Wk имеет единственный элемент, с помощью замены сигмаk успешно закончить операцию унификации (в таком случае замена сигмаk, приводящая к успеху, называется унификатором). В противном случае составить расходящееся множество Dk и перейти к шагу 3.
Шаг 3. Обозначить элементы множества Dk через Vk (при этом Vk должно быть переменной) и Tk, и если удовлетворяется условие ограничения замены Vk<-Tk, перейти к шагу 4. В противном случае операция унификации заканчивается неудачей.
Шаг 4. Положить сигмаk+1 = сигмаk*{Vk<-Tk}, Wk+1 = Wk*{Vk<-Tk} и перейти к шагу 5 (при этом следует помнить о том, что унифицированные элементы повторяются, поэтому в множество Wk+1 должен входить только один из них).
Шаг 5. Положить k = k+1 и перейти к шагу 2.

Обычно для множества выражений, являющихся объектами унификации, нельзя однозначно определить унификатор. Например, для пары множеств birthday(X, [23, 11, 1968]) и birthday(Y, [23, 11, 1968]) число унификаторов может быть неограниченным: {Х<-Y}, {Y<-X}, {Х<-Сэйко, Y<-Сэйко}, {X<-Y, Y<-Хироми} и т.д. Наиболее общий из этих унификаторов называется mgu (most general unifier - наиболее общий унификатор). Унификатор сигма, являющийся mgu, находится в следующей зависимости с другими произвольными унификаторами:

мю = сигма * тау

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

В заключение рассмотрим случай существования нескольких mgu. Например, в предыдущем примере оба унификатора - и {Х<-Y}, и {Y<-X} - являются mgu. В таком случае при получении логического вывода по правилу резолюций можно выбрать любой из них - известно, что результаты будут одинаковыми.

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

(в) ОБРАБОТКА ЕСТЕСТВЕННЫХ ЯЗЫКОВ
Язык, которым мы пользуемся в нашей повседневной жизни, называется естественным языком. Японский, английский, немецкий - все это примеры естественных языков. Изучением этих языков занимается наука лингвистика. С другой стороны, существуют языки программирования, которые "понимаются" компьютерами. Язык программирования является одним из искусственных языков. Современные компьютеры не достигают уровня понимания естественных языков. Однако разрабатываются всевозможные технические средства, предназначенные для обработки естестьенных языков, с разной точкой зрения на понимание естественных языков компьютерами. Виды обработки естественных языков можно в общих чертах разделять на обработку слов, состоящих из нескольких выстроенных в ряд букв (поиск в словаре, обработка морфем), обработку предложений, состоящих из нескольких выстроенных в ряд слов (синтаксическая обработка, семантическая обработка), и обработку текстов, состоящих из нескольких выстроенных в ряд предложений (обработка контекста). Названные виды обработки могут встречаться и одновременно, однако ниже для облегчения понимания мы будем рассматривать их как относительно независимые виды обработки.

(1) СОСТАВЛЕНИЕ СЛОВАРЯ
Предложения естественного языка состоят из нескольких слов. Слова объединяются в словарь. Заголовок словаря тоже представляет собой слово. Работа со словарем часто заключается в поиске в нем заданных слов. Чтобы поиск слов в словаре был эффективным, необходимо представлять себе метод составления словаря. Наиболее простым методом составления словаря является расположение слов одного за другим в порядке естественного поступления. Однако если располагать слова в порядке их естественного поступления, то при последующем поиске требуются большие затраты времени на доступ, и общая эффективность оказывается низкой. Необходим такой метод составления словаря, который позволял бы эффективно осуществлять поиск и при обработке естественного языка допускал бы простую и безошибочную обработку вариантов окончаний слов (включая фонетические изменения) и т.д. Рассмотрим метод составления словаря на основе структуры, называемой Trie-деревом [Trie - искусственно образованное слово, представляющее собой среднюю часть слова retrieval (поиск)].

Trie-дерево представляет собой структуру данных, составляющих множество буквенных последовательностей. Например, множество слов

Техника в руках дикаря Jap18910
[Множество {сидзэн (естественный), сидзэн гэнго (естественный язык), сидзэн кагаку (естественные науки), дзию (свобода), суйсоку (предположение), суйрон (вывод)} содержит не только слова, но и сочетания слов, которые в японском языке можно рассматривать как слова из нескольких иероглифов.- Прим. перев.]

может быть представлено в виде trie-дерева, показанного на рис.4.3. В представленной на рисунке trie-структуре путь от корня до листа составляет одно слово. Узлы trie-дерева расположены в порядке следования кодов символов. Для того чтобы избежать путаницы, конец слова всякий раз обозначается специальным знаком $. Узел, отмеченный знаком $, не может иметь порожденного.

Техника в руках дикаря Jap18911
Рис.4.3 пример trie-дерева

Как видно из рис.4.3, если несколько начальных букв в trie-структуре являются общими, эффективность запоминания значительно повышается. Однако в случае очень большого множества слов, входящих в словарь (например, словарь языка писателя и т.д.), требуется особая осторожность. Число ветвей, выходящих из корня trie-дерева, при этом близко к сумме букв английского алфавита и знаков японской слоговой азбуки [Японская слоговая азбука имеет две модификации - катакана и хирагана,- которые содержат 46 основных и 114 полных знаков каждая.- Прим. перев.], а всего ветвей оказывается порядка нескольких тысяч. Поэтому для такой trie-структуры необходим специальный высокоэффективный механизм выбора ветви, начиная от корня. В этом механизме мог бы использоваться какой-либо искусственный метод, например метод хэширования. Если бы число ветвей, выходящих из некорневых узлов, было существенно уменьшено, можно было бы рассчитывать на экономию объема памяти за счет представления ее в виде списка, разбитого на отдельные звенья (рис.4.4). В случае английского языка из каждого узла может выходить не более 27 ветвей, поэтому для представления узлов, включая корень, вполне подходит форма списка, разбитого на звенья.

Техника в руках дикаря Jap19010
Рис.4.4. Представление trie-структуры в виде списка, разбитого на звенья.

Итак, если словарь составлен на основе trie-структуры, то поиск в таком словаре будет осуществляться путем сравнения с символами, расположенными в узлах trie-дерева, и весь поиск будет продвигаться по "кроне" trie-структуры. Это очень удобно для обработки вариантов окончаний слов при спряжении и т.д. Об этом будет еще сказано в разделе, посвященном анализу морфем.

В другом методе, обеспечивающем анализ данных, представленных в форме древовидной структуры, используется структура В-дерева. Это разновидность сбалансированного дерева, которое имеет ту особенность, что пути от всех листьев до корня одинаковы, время доступа в наихудшем случае оказывается минимальным и вместе с тем легко осуществляются вставки и удаления. Однако с точки зрения обработки вариантов окончаний слов при их изменении по словоформам метод составления словаря на основе trie-структуры, обеспечивающий простое осуществление посимвольной обработки (сравнения), оказывается более рациональным.
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Вт Ноя 29, 2022 12:21 am

(2) ОБРАБОТКА МОРФЕМ
Наименьшие языковые единицы, из которых составляется предложение, носят название морфем. Оставив в стороне строгую теорию, рассмотрим здесь такие морфемы, как слово, префикс, суффикс.

В японском языке пробелы между словами в предложениях обычно не оставляются, символы (буквы или иероглифы) следуют друг за другом для глаза непрерывно. Следовательно, если с помощью обработки морфем не разделить предложение на отдельные слова, то окажется невозможной и последующая синтаксическая обработка (рассматриваемая в подразд.4.2(в)(3)). Отсюда ясна важность обработки морфем. Кроме того, при спряжении [В японском языке изменение окончаний слов происходит только за счет спряжения. Спряжением называется изменение слова по основам, т.е. образование пяти исходных форм; спрягаются не только глаголы, но и прилагательные. Форма существительных не изменяется.- Прим. перев.] слов возникают изменения окончаний. Спрягаемые слова, вносимые в словарь, чаще всего приводятся в нем только в заключительной форме или в форме основы, поэтому, если слово встретилось в какой-то другой словоформе, часто бывает необходимо распознавать его с помощью обработки морфемы (обработки окончания слова). Такая обработка для предложений японского языка называется автоматической сегментацией.

В английском языке между словами ставится пробел, поэтому обработка морфем оказывается сравнительно простой. Например, к обработке морфем относится восстановление happy из happier, try из tries, take из taking.

Далее рассматривается метод, с помощью которого, осуществляя обработку морфем для японского слова "У ти КО ми ма су" [Японский сложный глагол "утикому" (вбивать, вкладывать), представленный в вежливой форме, состоит из двух глаголов "уцу" (бить, ударять) и "кому" (указывает на направленность действия). Неизменяемая часть слова записывается иероглифами, изменяемая - знаками слоговой азбуки хирагана. Здесь и далее в тексте фонетическая запись иероглифа сделана прописными буквами, запись букв азбуки - строчными.- Прим. перев.] можно понять, что в данном случае представляет собой элемент этого слова "ми ма су", присоединяемый к "У ти КО". Будем считать, что словарь составлен на основе trie-структуры, и спрягаемые слова, изменяемые при спряжении, записаны в нем в форме основы (рис.4.5).

Техника в руках дикаря Jap19110
Рис.4.5. Представление японского слова "У ти КО му" B виде trie-структуры.

Если проводить сравнение для слова "У ти КО ми ма су" по одному символу, начиная с первого, продвигаясь по trie-структуре, представленной на рис.4.5, то видно, что основа слова включает только "У ти КО". В trie-дереве рис.4.5 черными кружочками помечены узлы, но в действительности в этих узлах заключена разная информация. В данном случае по виду основы слова "У ти КО" в trie-структуре можно, например, получить следующую информацию:

Часть речи - глагол, Тип спряжения - первое спряжение.

Далее, используя эту информацию, исследуем условия, при которых осуществляется соединение полученной из формы "У ти Ко ми ма су" основы "У ти КО" глагола "УтиКОму" и окончания "ми ма су", которое остается после исключения основы. Как мы уже видели, этот глагол по типу спряжения относится к первому спряжению, поэтому первый символ "ми" окончания "ми ма су" с полным правом можно отнести к окончанию слова. Таким образом, до этого места относившаяся к глаголу обработка окончания слова, образовавшегося в результате спряжения, прошла успешно. Теперь остается обработать "ма су".

Попробуем применить для формы глагола с измененным в результате спряжения окончанием грамматическое правило, в соответствии с которым в конце такой формы присоединяется вспомогательный глагол [В японском языке наиболее употребительной является так называемая нейтрально-вежливая форма глагола, когда к 2-й основе присоединяется вспомогательный глагол "масу".- Прим. перев.]. До формы "У ти - Ко ми" обработка морфемы нами уже закончена, и поскольку в результате выяснилось, что это форма глагола с измененным вследствие спряжения окончанием [2-я основа, при которой глагол в данном случае имеет окончание "ми" (в отличие от 3-й, словарной, имеющей окончание "му"), используется для образования вежливой формы.- Прим, перев.], то дальше можно предположить, что необработанная еще часть слова "ма су" является вспомогательным глаголом, и выполнить обработку морфемы для вспомогательного глагола. И в этом случае, аналогично обработке морфемы глагола, рассматриваем основу вспомогательного глагола "ма" и анализируем информацию, относящуюся к изменению окончания при сопряжении. Зная, что "ма" в данном случае является особой формой спряжения, исследуем условия соединения его с оставшейся частью "су". В заключение проведем обработку в предположении, что "су" является окончанием вспомогательного глагола "ма", и обработка морфем слова "У ти КО ми ма су" оказывается законченной.

Если обработка морфемы при движении по одному пути окажется неудачной, можно вернуться назад по trie-дереву и выбрать другую основу слова или образец для сравнения. Прохождение по trie-дереву соответствует посимвольному выполнению сравнения символов; легко видеть, что и возвращение по trie-дереву осуществляется без труда. Как было показано в подразд. 4.2(в)(1), в случае, когда использован другой метод составления словаря, не опирающийся на применение trie-структуры, описанный выше метод обработки морфем не всегда может осуществляться в его естественном виде. Но словарь можно рассматривать как простую базу данных для поиска, и если его предполагается использовать не только в случаях, требующих обработки морфем, то, очевидно, целесообразнее воспользоваться методом составления словаря, опирающимся на структуру В-дерева.

При обработке окончаний слов в английском языке также могут использоваться описанные выше методы. Однако в английском языке существует небольшое число изменяемых окончаний слов (грамматически правильных). Это -s, -es, -ies, -er, -ier, -ing, -ed и др. Поэтому в случае обнаружения одной из этих цепочек в конце слова, в отношении которого должна выполняться обработка морфем, легко восстановить исходную форму слова, исключив цепочку. Таким образом, обработку морфем можно считать эффективным методом проверки наличия в словаре слова в форме, полученной после восстановления.

Метод составления словаря, основанный на использовании trie-структуры, часто применяется в процессорах для обработки слов, содержащих систему замены букв японской слоговой азбуки на буквы английского алфавита. Этот метод может использоваться также для исправления орфографических ошибок в текстах.

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

(3) СИНТАКСИЧЕСКАЯ ОБРАБОТКА
Синтаксическая обработка называется также обработкой структуры предложения. Рассмотрим выборку морфем, составляющих предложение, после завершения обработки морфем. К синтаксической обработке относится выборка связей подлежащее/сказуемое и определение/определяемое слово, а также определение типа предложения (повествовательное, восклицательное или вопросительное) на основе использования грамматических правил и словаря. Поскольку такая обработка представляет собой исследование грамматической структуры предложения, она называется также грамматическим разбором. Результат синтаксической обработки может быть представлен также в виде структуры фразы.

Рассмотрим пример построения структуры фразы, получаемой в результате анализа предложения John saw a lady.

Техника в руках дикаря Jap19410

Структура (4.28 ) может быть представлена в виде дерева, показанного на рис.4.6. Оно называется деревом структурного
анализа (деревом грамматического разбора).

Техника в руках дикаря Jap19411
Рис.4.6. Дерево структурного анализа предложения.

Для грамматического описания часто используется контекстносвободная грамматика (context-free grammer, далее используется сокращение CFG). Ниже приведены правила CFG для структуры предложения в английском языке. Особенностью CFG является то, что в ней слева от стрелки допускается только один символ.

S -> NP VP [1]
NP -> ART N [2]
NP -> N [3]
VP -> VT NP [4]
VP -> VP PP [5]
PP -> PREP NP [6]

[Обозначения в этих правилах имеют следующий смысл. N - существительное, VT - глагол, ART - артикль, PREP - предлог, S - предложение, NP - существительное (или существительное с артиклем), VP - глагол и существительное (или глагол и существительное с артиклем, или существительное с артиклем и существительное с предлогом), PP - существительное (или существительное с артиклем) с предлогом.- Прим. перев.]

Аналогично для слов, составляющих словарь:

N -> Jonn [7]
N -> lady [8]
N -> binoculars [9]
N -> saw [10]
VT -> saw [11]
ART -> a [12]
PREP -> with [13]

Согласно исследованиям лингвистов, CFG как грамматика неполна. Однако, как показали самые последние исследования, если правила CFG дополнить программой, появится принципиальная возможность производить также обработку контекста. Такая дополненная CFG стала широко применяться. Однако для упрощения понимания мы будем рассматривать синтаксическую обработку, при которой используются правила CFG с [1] по [13] [S, NP, VP, ART, N, VT, PREP называют нетерминальными символами, a John, lady, ..., with - терминальными символами. Терминальный символ - это символ, который нельзя больше развернуть]. При синтаксической обработке применяются методы нисходящего и восходящего анализа.

(I) МЕТОД НИСХОДЯЩЕГО АНАЛИЗА
При использовании метода нисходящего анализа синтаксическую обработку осуществляют, читая правила CFG в направлении, указанном стрелкой. Например, по правилу [1] попытаемся развернуть S (предложение) для NP (существительное) и VP (глагол) и прочесть его. Пусть должно быть обработано предложение "John saw a lady"; проведем синтаксическую обработку в направлении от начала предложения к его концу. В соответствии с методом нисходящего анализа обработка начинается с символа S (предложение).

Если использовать правило [1], развертывающее S, то получится древовидная структура, показанная на рис.4.7,а. После окончания обработки от начала предложения до его конца переходим к раскрытию NP, представленного левой ветвью дерева на рис.4.7,а. Для раскрытия NP можно использовать два правила [2] и [3]. Поскольку может быть выбрано любое из этих правил, они называются недетерминированными. Стратегия начала обработки, при которой из нескольких возможностей выбирают одну подходящую, здесь названа стратегией "вглубь" (depth-first). В противоположность ей стратегия, при которой на разных этапах обработки одновременно реализуются разные возможности и обработка осуществляется для всех возможностей параллельно, называется стратегией "вширь" (breadth-first). Ниже для простоты будем рассматривать только стратегию "вглубь". Если развернем NP, выбрав, например, правило [2], получим структуру, показанную на рис.4.7,б. Затем с помощью правила [12] развернем ART, a так как это уже словарное слово, проверим, не является ли словом ART первое слово (John) предложения, которое подвергается обработке. Поскольку John, как показывает анализ с помощью правила [12], в данном случае не является ART, сравнение не имеет успеха (рис.4.7,в). Это означает, что выбор правила [2] был неудачным. В таком случае вместо правила [2] возьмем правило [3]. Эта процедура называется отступом для исправления ошибки.

Техника в руках дикаря Jap19610
Рис.4.7. Схема синтаксической обработки, основанной на нисходящем анализе с использованием стратегии "вглубь".

Результат анализа с помощью правила [3] представлен на рис. 4.7,г. Теперь надо развернуть N. Соответствие N словам из словаря описывается тремя правилами [7], [8], [9]. Если выберем правило [7], то при сравнении с первым словом John предложения, подвергаемого обработке, убедимся в совпадении слов, т.е. в данном случае сравнение оказывается успешным (рис.4.7,д). Далее развернем VP. Для этого можно использовать правила [4] и [5]. Если выберем правило [4], в результате получим. структуру, показанную на рис.4.7,е. Синтаксическая обработка по методу нисходящего анализа далее проводится аналогично, и в конце концов формируется дерево структурного анализа (рис.4.6). Таким образом, синтаксическая обработка заканчивается успешно.

Случай, описываемый правилом [5], когда непосредственно перед стрелкой и непосредственно после нее стоят одинаковые символы (в данном случае VP), называется леворекурсивным правилом. Если применить это правило при осуществлении синтаксической обработки по методу нисходящего анализа от начала предложения до его конца, можно попасть в ловушку - получится "бесконечный цикл". Поэтому использовать это правило следует осторожно. Например, если в ситуации, представленной на рис. 4.7,д, при развертывании VP вместо правила [4] используем правило [5], мы попадем именно в такую ловушку - будет бесконечно повторяться цикл, показанный на рис.4.8. Чтобы его избежать, можно воспользоваться известным методом замены леворекурсивного правила несколькими праворекурсивными. Однако пользоваться этим методом нежелательно, так как в грамматическую систему при этом вносится неестественность, нарушающая ее стройность. При использовании метода восходящего анализа, который поясняется ниже, этой проблемы не возникает.

Техника в руках дикаря Jap19710
Рис.4.8. Бесконечный цикл

(II) МЕТОД ВОСХОДЯЩЕГО АНАЛИЗА
Синтаксическую обработку по методу восходящего анализа осуществляют, читая правила CFG в сторону, противоположную направлению стрелки. Например, в соответствии с правилом [1] составляем S и читаем от NP и VP. Пусть так же, как в (I), мы имеем предложение "John saw a lady". В отличие от (I) применим здесь стратегию "вширь".

Метод восходящего анализа начинается с поиска каждого из слов предложения "John saw a lady" в словаре. Если на этапе получения последнего слова окажется завершенным дерево структурного анализа (рис.4.6) с S в корне, значит, синтаксическая обработка окажется успешно законченной.

Результат поиска в словаре слов предложения "John saw a lady" показан на рис.4.9,а. Здесь "saw" может представлять собой не одну часть речи, а несколько (правила [10], [11]). В случае применения стратегии "вширь" составляется список возможностей. Далее, исходя из того, что мы имеем N, (VT N), ART, N, выстроенные в такой последовательности, проанализируем, насколько они соответствуют символам, стоящим слева от стрелки, пользуясь правилами с [1] по [6] просматривая их справа от стрелки). Результат анализа представлен на 4.9,б.

Техника в руках дикаря Jap19810
Рис.4.9. Синтаксический анализ предложения восходящим методом и методом "вширь".

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

Выше была изложена основная идея синтаксической обработки с помощью методов нисходящего и восходящего анализа. Однако в реальных исследовательских работах по обработке естественных языков применяется упоминавшаяся выше дополненная CFG, на основе которой составлен алгоритм, синтаксической обработки, опирающийся на метод, объединяющий метод нисходящего и метод восходящего анализа. Известно, что в случае (I) применения метода нисходящего анализа и стратегии "вглубь" на вычислительные операции требуется время, зависящее от длины подвергаемого обработке предложения (числа слов) по экспоненциальному закону, а в случае (II) применения метода восходящего анализа и стратегии "вширь" требуется время, пропорциональное кубу длины предложения. Таким образом, стратегия "вширь" - это идея параллельной реализации и ее можно перенести в метод синтаксической обработки. Это имеет важный смысл. По мере прогресса техники СБИС появится, очевидно, возможность разработки и реализации в модульном виде архитектуры устройства для синтаксического анализа с встроенной функцией параллельной обработки.

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

(4) СЕМАНТИЧЕСКАЯ ОБРАБОТКА
При синтаксической обработке естественных языков встречаются неразрешимые проблемы. Например, проблема разрешения двусмысленности слов, относящихся к одинаковым частям речи, имеющим одинаковое написание, но разный смысл. Возьмем, например, глагол "фуру" [В японском языке существует много одинаково звучащих слов, смысл которых при записи буквами слоговой азбуки определить невозможно (без контекста, а часто и в контексте). Запись иероглифами всегда позволяет понять смысл.- Прим. перев.]. Он имеет смысл "идти" (о дожде, снеге) и "трясти". Но в соответствии со здравым смыслом мы определяем, что "фуру" в предложении "амэ-га фуру" (идет дождь) имеет смысл "идти". При синтаксической обработке, когда анализ осуществляется на уровне частей речи, решить этот вопрос невозможно, необходимо внести в него ясность с помощью семантической обработки. Возьмем другой пример. В результате синтаксической обработки предложения "John saw a building with binoculars" можно получить как структуру, в которой слово с предлогом "with binoculars" относится к "saw", так и структуру, в которой оно относится к "building". Но семантически вторая структура "a building with binoculars" недопустима, поэтому двусмысленность результата синтаксической обработки необходимо разрешать с помощью семантической обработки.

Таким образом, целью семантической обработки является
1) разрешение двусмысленности синтаксической обработки;
2) разрешение двусмысленности слов, имеющих одинаковое написание, но разный смысл;
3) выделение результатов семантической обработки.

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

(I) ФОРМА ОТОБРАЖЕНИЯ СЕМАНТИКИ
Наиболее распространенной формой отображения семантики является семантическая сеть. Так называются связи, которые устанавливаются между отдельными понятиями, они представляются в виде сети со стрелками. Пример семантической сети приведен на рис.4.10. На рисунке узлы, заключенные в овалы, связаны направленными стрелками с метками. Метки поясняют связи между узлами. Пунктирной линией выделена область, в которую входят узлы, непосредственно связанные с узлом see. Действительно, эта область является отображением семантики предложения John saw a building with binoculars.

Техника в руках дикаря Jap20010
Рис.4.10. Организация семантической сети.

Область, выделенную пунктирной линией, можно рассматривать и как один объект. Этот объект можно также назвать фреймом. Представление области, выделенной пунктирной линией, в виде фрейма, показано на рис.4.11. Фрейм представляет собой совокупность слотов. Слот состоит из пары "имя слота - значение слота". На рис.4.11,а имеется слот, имя которого tense, a значение past. Значения слотов, расположенных на рисунке под слотом tense = past, находятся в других фреймах, к которым направлены указатели. Такую структуру можно назвать также фреймовой сетью (следует обратить внимание на то, что имя слота в фрейме соответствует метке, присвоенной стрелке в семантической сети).

Техника в руках дикаря Jap20011
Рис. 4.11. Отображение семантики с помощью фреймов. Если считать, что фреймы а, б, в, г и т.д.- это процессоры, то все они могут рассматриваться как процессоры знаний.

agent, object, tool служат для отображения факта определенной связи объекта с некоторым событием или действием. Рассмотрение этого вопроса выходит за пределы нашей книги. Слот isa содержит указание на фрейм, относящийся к понятию, которое находится в вышестоящем узле. Поэтому смысл понятия, находящегося в вышестоящем узле, может передаваться в фрейм, расположенный под ним. Это называется наследованием знания.

Из вышеизложенного можно сделать вывод, что форма отображения семантики является частью формы представления знания. Практически исследования, относящиеся к разработке машины для скоростной обработки информации, представляющей собой знание (процессора знаний), ведутся в Массачусетском технологическом институте и основываются на рассмотрении фреймов либо как отдельных процессоров (рис.4.11), либо как единого комплекса, в котором отдельные фреймы соединяются линиями передачи сигналов. Поскольку такой комплекс сам по себе является архитектурой, в которой объединены несколько тесно связанных процессоров, он может стимулировать дальнейшее развитие техники СБИС. Устройство с такой архитектурой называется машиной связей и может считаться примером архитектуры, ориентированной на СБИС.

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

(II) ВЫЯВЛЕНИЕ СЕМАНТИКИ
Рассмотрим типичный метод выявления семантических связей. Возьмем предложение John saw a lady и выполним его семантическую обработку. Результат синтаксической обработки представлен на рис.4.6.

Для выполнения семантической обработки недостаточно записи слов, входящих в словарь, с помощью правил с [7] по [13]. В этом случае слово saw (входящее в словарь) записывается в форме, показанной на рис.4.12. Для слота agent на рис.4.12 записывается не значение, а синтаксические/семантические граничные условия возможного значения. Например, в ячейке, где должно помещаться значение слота agent, мы читаем, что подлежащим (SUBJ) должно быть слово, относящееся к категории "человек".

Техника в руках дикаря Jap20210
Рис.4.12. Запись смысла слова saw в виде фреймовой структуры.

С другой стороны, по результатам синтаксической обработки, представленным на рис.4.6, можно сделать вывод о том, что NP, расположенное под S, т.е. John, является подлежащим, a NP, расположенное под VP, т.е. a lady, является дополнением (OBJ). Используя эти результаты и рис.4.12, можно заключить, что поскольку John является подлежащим и относится к категории "человек", то John может оказаться значением слова agent на рис.4.12. В то же время a lady является дополнением и относится к категории "человек", поэтому может оказаться значением слота object на рис.4.12. Продолжая таким образом, в результате семантической обработки получим, что значение слота tool на рис.4.11 исчезнет, рис.4.12 останется в прежнем виде, а указатель фрейма (рис.4.11,в) переместится с фрейма building на фрейм lady.

Таким образом, с помощью рассмотренной выше процедуры осуществляется семантическая обработка со следующими семантическими граничными условиями: известно, что John - человек, lady - тоже человек, и это записано в слотах agent, object рис.4.12. Такая обработка может выполняться с высокой скоростью с помощью процессора знаний, о котором было упомянуто выше (реализованного на основе техники СБИС).

(5) ОБРАБОТКА КОНТЕКСТА
Выше было показано, что смысл взятого в качестве примера предложения John saw a building with binoculars не может быть понят до конца только на уровне синтаксической обработки, и был изложен метод разрешения смысловых неясностей на уровне семантической обработки. Однако, если в приведенном предложении building заменить на lady, получится предложение John saw a lady with binoculars, которое также имеет смысловую неясность - оно может иметь двоякий смысл: "Джон увидел в бинокль даму" и "Джон увидел даму с биноклем". Эта двусмысленность не может быть разрешена на уровне семантической обработки. Для разрешения этой двусмысленности необходимо знать контекст предложения. Это значит, что необходима обработка контекста.

Обработка контекста преследует следующие цели.
1) Разрешение двусмысленности результатов семантической обработки.
2) Определение указательного местоимения или другого указательного предшествующего слова (согласующей указательной связи).
3) Восстановление сокращенных слов.
4) Определение основной мысли и т.д.

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

Для определения указательного местоимения или другого предшествующего слова можно применить метод, согласно которому, например, встреченное в предшествующем предложении существительное засылается в стек, и если оно будет обнаружено в последующем предложении, то стоящее перед ним слово является искомым. Однако бывает и так, что слово, в явном виде не присутствующее в предыдущем предложении, указывается в последующем предложении (например, "Продали машину. На эти деньги поехали на Гавайи"). Для обработки естественного языка совершенно необходима обработка контекста. Таким образом, как уже было сказано, масштабность задач обработки контекста следует ограничить, например, за счет обращения к базе знаний.

(6) ПРИМЕНЕНИЕ РАЗЛИЧНЫХ ВИДОВ ОБРАБОТКИ В СИСТЕМАХ ПОНИМАНИЯ ЕСТЕСТВЕННЫХ ЯЗЫКОВ
Если объединить технические средства реализации методов обработки с (1) по (5) со средствами реализации методов логического вывода и решения проблем, можно построить систему понимания естественного языка (рис.4.13). Предложение, которое должно быть обработано (допустим, предложение, содержащее вопрос), подвергается обработке естественного языка, результаты которой передаются в систему логического вывода/решения проблем. При этом в случае обработки естественного языка из базы знаний выбираются лингвистические знания, необходимые для логического вывода/решения проблем. Результат логического вывода/решения проблем выдается в виде предложения, содержащего ответ.

Техника в руках дикаря Jap20410
Рис.4.13. Пример структуры системы понимания естественного языка.

Как показано на рис.4.13, система понимания естественного языка состоит из трех подсистем. Если назвать эти подсистемы машинами, то это:
1) машина обработки естественного языка,
2) машина базы знаний,
3) машина логического вывода.

В проекте ЭВМ пятого поколения эта система называется "интеллектуальным" интерфейсом на базе естественного языка. Как ясно из рис.4.13, систему понимания естественного языка можно рассматривать как типичную систему обработки интеллектуальной информации.

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

Из-за ограниченного объема книги более подробных объяснений не приводим. Отметим лишь, что Пролог-компьютер оснащен не только машиной логического вывода, который является основной функциональной частью этого компьютера, но и машиной обработки естественного языка и машиной базы знаний.
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Ср Ноя 30, 2022 12:25 am

4.3. МЕХАНИЗМ ЛОГИЧЕСКОГО ВЫВОДА И ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
(а) СИСТЕМА ЛОГИЧЕСКОГО ВЫВОДА
Наше мышление представляет собой процесс решения какой-либо проблемы в случае ее появления. Поскольку решение проблемы связано с необходимостью делать логический вывод, процесс мышления можно рассматривать как процесс логического вывода. Решение проблемы представляет собой цепочку логических построений. Одной из основных задач обработки символов, связанной с мышлением, является механическая перестановка звеньев цепи логического вывода в определенном порядке, и за счет этого - решение проблемы.

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

Один из основателей науки об обработке символов Дж.Пирс в качестве методов логического вывода называет метод дедукции, метод индукции, метод построения гипотезы. Методы дедукции и индукции известны издавна. Метод построения гипотезы впервые предложил Пирс. И.Фути дает следующее описание связей между этими методами в терминах, принятых в методе силлогизма.

(I) Главная посылка (rule) (все)X . human(X) -> mortal(X)
(II) Второстепенная посылка (case) human(socrates)
(III) Вывод (fact) mortal(socrates)

Главная посылка (I) читается следующим образом. "Для всех X если имеет место свойство human(X), то имеет место и свойство mortal(X)". Здесь символ (все) называется квантором общности. (все)X имеет тот смысл, что если некоторое свойство справедливо для произвольного X из множества X, существующего в рамках настоящего рассуждения, то оно справедливо для всех X. human и mortal представляют собой предикаты. Главная посылка (I) может рассматриваться как аксиома для получения вывода (III).

Дедукцией называется логический вывод, заключающийся в выведении (III) из (I) и (II). Согласно другой точке зрения, дедукция - это логический вывод, при котором вывод получается при прослеживании аксиомы (I) в направлении стрелки, поэтому такой вывод называется правосторонним логическим выводом (forward reasoning). Если считать, что получение вывода (III) является целью решения проблемы, то это название имеет тот смысл, что логический вывод производится в направлении этой цели.

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

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

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

Итак, описанная система логического вывода и рассмотренная в подразд. 4.2(в) система синтаксической обработки (методы восходящего анализа и нисходящего анализа) находятся в следующей взаимозависимости:
1) правосторонний логический вывод - метод восходящего анализа,
2) левосторонний логический вывод-метод нисходящего анализа.

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

Техника в руках дикаря Jap20710

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

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

(б) ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
При логическом программировании, которое осуществляется на языке Пролог, специально созданном для обработки символов, производится всевозможная обработка символов (решение проблем), в ходе которой процесс доказательства теорем рассматривается как процесс вычисления или процесс выполнения программы. Соответствие процесса доказательства теорем и процесса выполнения программы было установлено Р.Ковальским. В середине 60-х гг. Робинсон разработал метод автоматического доказательства теорем, называемый принципом резолюций. Посмотрим, как осуществляется программирование на языке Пролог - типичном языке логического программирования (сначала не принимая во внимание идею доказательства теорем), и разберем несколько практических примеров такого программирования. Затем проследим, как изменится программирование применительно к доказательству теорем. Работы А.Кольмеро, исследователя и разработчика языка Пролог из Марсельского университета, привлекают к себе внимание и как исследования в области обработки естественных языков. Действительно, Пролог удобен для обработки естественных языков.

(1) ПРОГРАММИРОВАНИЕ НА ПРОЛОГЕ
Прежде всего запишем компоненты программы на Прологе, используемой для проверки наличия определенного элемента в списке элементов.

member(H,[H|T]). (4.29)
member(H,[X|Т]) :- member(H,T) (4.30)

Список представляется в виде [V|W]. Прописными буквами обозначены переменные, строчными - постоянные. V представляет собой головной (один) элемент списка, W - оставшуюся часть списка за исключением головного (одного) элемента (V в языке Лисп соответствует функция CAR, W - функция CDR (см. подразд. 4.4(6)(2))).

Можно привести следующие примеры списков: [a], [a,b,c], [[a,b|,[c,d]] и т.д. Если сопоставить эти списки с записью [V|W], то будем иметь соответственно
- для [a]: V <- a, W <- []
- для [a,b,c]: V <-a, W <- [b,c]
- для [[a,b],[c,d]]: V <- [a,b], W <- [[c,d]]

Формулу (4.29) следует читать следующим образом: если головной элемент второго аргумента member и его первый аргумент представляют собой одно и то же (Н), то установлен member.

Левая часть обозначения ":-" называется головой, правая часть - телом. В логике вместо обозначения ":-" используют обозначение "<-". (4.29) имеет смысл логической формулы, в которой имеется только голова, а тело отсутствует (подробнее см. подразд.(2)). Логическая формула (4.30) имеет следующий смысл: "если member(H,T) то member(H,[Х|Т])" или "member(Н,[Х|Т]) если member(H,T)". Реализация программ на Прологе осуществляется в соответствии со второй записью этой логической формулы. Следует обратить внимание на то, что направление прочтения логической формулы в этом случае совпадает с направлением логического вывода по методу построения гипотезы (см. предыдущий подразд.4.3(а)).

Здесь member представляет собой предикат, содержащий два аргумента и имеющий значение "истина" или "ложь". Особенностью программ на языке Пролог является наличие следующих ограничений для представления логических формул (называемых также клозами): наличие в голове только одного предиката, запись в теле отдельных произвольных предикатов, разделенных обозначением "," (запятая), адекватность обозначения ",", связывающего предикаты, обозначению логической суммы (&). Приведенная выше логическая формула называется клозом Хорна (см.4.3(6)(2)).

Программа на Прологе реализует хорновский клоз, в котором голова свободна, а предикаты содержатся только в теле, т.е. целевой клоз. В этом случае обозначение ":-" заменяется на "?-". Например,

?- member(c,[a,b,c]) (4.31)

(4.31) представляет собой целевой клоз для проверки присутствия элемента с в списке [a,b,c]. Прежде чем проследить, каким образом реализуется (4.31), обратим внимание на следующий факт. Если в клозе содержатся одинаковые переменные, это указывает на идентичность этих переменных в клозе. Однако если одинаковые переменные содержатся в двух (или более) разных клозах, это не обязательно говорит об идентичности переменных в этих двух (или более) клозах. Например, тот факт, что Н, Т содержатся и в голове, и в теле (4.30), указывает на идентичность соответствующих переменных в клозе. Однако Т в (4.30) и Т в (4.29) не обязательно идентичны.

Выполнение программы на языке Пролог заключается в последовательном перемещении слева направо предикатов, содержащихся в теле целевого клоза. Основой такого выполнения программы является операция унификации, которая пояснялась в подразд.4.2(6)(3). Если возможна унификация предикатов, содержащихся в теле целевого клоза, с предикатом, содержащимся в голове клоза Хорна, входящего в программу на Прологе, то каждый предикат из тела этого клоза можно представить в виде нового целевого клоза, что и осуществляется практически в каждом подобном случае. Если же унификация оказывается невозможной, то выполняется отступ и проверяется другая возможность, т.е. делается попытка осуществления унификации с предикатом головы следующего клоза Хорна. Если все попытки унификации с предикатами всех клозов Хорна оказываются безуспешными, то считается, что реализация этого целевого клоза безуспешна. Если имеется целевой клоз слева от целевого клоза, для которого осуществлялась операция унификации, то с помощью отступа проверяется возможность унификации для предикатов этого целевого клоза (см. подразд.4.4(в)(1)). Таким образом, отступ вместе с операцией унификации является одним из основных механизмов обработки в Прологе.

При осуществлении операции унификации для (4.31) с головой (4.29) обнаруживаем, что имена предикатов одинаковы, поэтому переходим к сопоставлению первых и вторых аргументов предикатов соответственно. При унификации новых аргументов можем записать Н<-с. Далее, при унификации вторых аргументов можем записать Н<-а, Т<-[b,c] и убедиться в успешном завершении операции унификации. Однако, как легко видеть, переменная Н, которая является первым аргументом в (4.29), и переменная Н, которая входит во второй аргумент, соответствуют c и a из (4.43), и между собой не совпадают, поэтому унификация (4.31) и (4.29) оканчивается неудачей. В таком случае переходим к операции унификации (4.31) с головой (4.30). Если при этом записать Н<-а, Х<-а, Т<-[b,с], то сопоставление окажется успешным, поэтому можно переходить к реализации тела (4.30). Телом (4.30) будет

?- member(c,[b,c]) (4.31-1)

Если для (4.31-1) провести операцию, аналогичную вышеприведенной, то окажется, что унификация с (4.29) невозможна, а унификация с (4.30) заканчивается успешно. При этом будет иметь место Н'<-с, Х'<-b, Т'<-[с] (во избежание путаницы имена переменных Н, X, Т из (4.30) обозначены как Н', X', Т'). Таким образом, переходим к реализации тела (4.31-1). Им будет

?- member(c,[c]) (4.31-2)

На этот раз производим операцию унификации (4.31-2) с (4.29) и убеждаемся в ее успешности. В результате можем записать Н<-с, Т<-[]. Таким образом, реализация целевого клоза (4.31) в конце концов успешно завершилась. Схема реализации представлена на рис.4.14 в виде древовидной структуры. При этом результат выполнения (4.31) возвращается в виде ответа "да".

Техника в руках дикаря Jap21110
Рис.4.14. Схема выполнения элемента программы member(c,[a,b,c]) на языке Пролог.

Теперь рассмотрим дополнение (append) к программе на языке Пролог, записанное в виде логических формул (4.32) и (4.33) и представляющее собой в данном случае программу получения третьего аргумента путем присоединения списка, являющегося вторым аргументом, к списку, являющемуся первым аргументом.

append([],L,L). (4.32)
append([H|U],V,[H|W]) :- append(U,V,W) (4.33)

Например, если выполнить
?- append([a,b],[c],X) (4.34)

то получим

Х = [a,b,с].

Схема реализации (4.34) показана на рис.4.15. Смысл рис.4.15, очевидно, можно понять по аналогии со смыслом рис.4.14.

Техника в руках дикаря Jap21210
Рис.4.15. Схема выполнения элемента программы append([a,b],[с],X) на языке Пролог.

Только в целевом клозе (4.34) третьим аргументом оказалась переменная X. Значения этой переменной X можно определить из рис.4.15 следующим образом:

X <- [a|W]
<- [a|[b|W']] ('.' W <- [b|W'])
<- [а|[b|[с]]] ('.' W' <- [c])

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

Y = f(X1,...,Хn) (4.35)

при использовании предиката F может быть представлена в виде

F(X1,...,Хn, Y) (4.36)

В случае представления функции в виде (4.35) сразу можно понять, что входными функциями являются X1, ..., Xn, a Y - выходная функция. Если же для представления предиката используется функциональная форма (4.36), то с первого взгляда нельзя сказать, какой из аргументов является входной функцией, а какой - выходной. Поэтому

?- append(X,Y,[a,b,с])

можно реализовать, используя (4.32) и (4.33). В результате получим

Х = [], Y = [a,b,c]

Однако если после получения этого результата поставить знак ";", то в результате следующих шагов получим Х=[а], Y=[b,c]; X=[a,b], Y=[c]; X=[a,b,c], Y = []; и в конце концов возвратится ответ "нет". Интересующиеся могут убедиться в этом, разобравшись в вышеизложенных пояснениях и проследив действия, выполняемые программой.

(2) ОСНОВНОЙ МЕХАНИЗМ ВЫЧИСЛЕНИЙ НА ЯЗЫКЕ ПРОЛОГ
В программах на языке Пролог используются четыре типа клозов. Они представлены в табл.4.1.

Таблица 4.1. Четыре типа клозов
Клоз ХорнаЛогическая формулаВид программы на языке Пролог (по материалам Эдинбургского университета)
Правило выводаQ<-P1&...&РnQ:-P1,...,Рn (4.37)
Целевой клоз<-P1&...&Рn?-Р1,...,Рn (4.38)
Клоз факта или единичный клозQ<-Q. (4.39)
Пустой клоз<-?- (4.40)

Клоз "Правило вывода" имеет смысл "Q if P1 & ... & Pn" (если P1 и ... и Рn, то Q является представлением предикатов), клоз факта - смысл "безусловно установлено Q", целевой клоз - смысл "не установлено P1 и ... и Рn". Целевой клоз (4.38) эквивалентен выражению

~(P1&...&Pn)<- (4.41)

Стрелка <- в (4.40) означает противоречие.

При выполнении программы на языке Пролог задается целевой клоз (4.38), эквивалентный логической формуле (4.41), содержащей отрицание заключения, и в этой логической формуле производится доказательство теоремы методом устранения противоречий. При этом применяется метод парадокса. Автоматическое выполнение этого метода известно под названием принципа резолюций. Правило логического вывода, опирающееся на принцип резолюций, называется резолюцией. С помощью этого правила из (4.42) и (4.43) получено (4.44).

Техника в руках дикаря Jap21310

Сигма в формуле (4.44) вводится для обозначения операции унификации Q и Q' (см. 4.2(б)(3)). На рис.4.14 представление Н<-с, X<-a, T<-[b,c] является примером операции сигма. Операция унификации описана в подразд.4.2(б)(3). Наиболее общий из унификаторов, используемых в операции унификации, называется mgu. Он используется в принципе резолюции; алгоритм, который приведен в подразд. 4.2(в)(3), представляет собой алгоритм для определения mgu.

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

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Чт Дек 01, 2022 12:08 am

4.4. ЛИСП-КОМПЬЮТЕР И ПРОЛОГ-КОМПЬЮТЕР
(а) ИСТОРИЯ ЛИСП-КОМПЬЮТЕРА И ПРОЛОГ-КОМПЬЮТЕРА
В качестве типичного языка программирования для обработки символов, о которой речь шла в предыдущих разделах (языка для обработки символов), можно рассматривать язык Лисп. Этот язык разработал примерно в 1958г. Дж.Маккарти (в то время работавший в МТИ в США). Лисп наиболее широко применяется при исследовании искусственного интеллекта в США, главным образом в МТИ и Станфордском университете.

В начале 1970г. во Франции в Марсельском университете Кольмеро разработал новый язык для обработки символов - язык Пролог. Он был усовершенствован в Англии, в Эдинбургском и Лондонском университетах. С 1982г. Пролог стал применяться при проектировании ЭВМ пятого поколения в Японии, и с этого времени стал привлекать к себе большое внимание.

Что касается языка Лисп, то в 1974г. в МТИ была начата разработка Лисп-компьютера, в котором аппаратно реализовался язык Лисп. До этого Лисп применялся в системах с разделением времени, в которых дорогостоящие большие ЭВМ использовались совместно большим числом пользователей, деливших между собой машинное время. С ростом числа пользователей языка Лисп становилось ясно, что системы с разделением времени при коллективном использовании не могут в достаточной степени обеспечить машинным временем отдельных пользователей. Поэтому появилась необходимость в создании Лисп-компьютера индивидуального пользования; Однако при том уровне техники аппаратного обеспечения, который имел место в 60-х гг., появление такого компьютера было преждевременно. Лисп - язык, требующий большого объема памяти, а в то время стоимость памяти была еще чрезвычайно высока.

В начале 70-х гг. в связи с успехами в развитии техники интегральных схем появилась перспектива решения этой проблемы. Это было важным фактором, способствующим разработке Лисп-компьютера. Следует, очевидно, подробнее остановиться на причинах того, что МТИ не стал разрабатывать Лисп для индивидуальных компьютеров общего назначения, а приступил к разработке Лисп-компьютера, аппаратно реализующего язык Лисп. Разработчики должны были видеть трудности, связанные с согласованием языка Лисп с архитектурой уже существующих компьютеров общего назначения. Лисп требует, например, очень большого объема памяти, поэтому необходимо, чтобы машина имела архитектуру, в которой большое место отводится адресному пространству. Архитектура такой машины должна содержать стековый механизм, допускать обработку признаковых данных и т.д.

Этапами разработки Лисп-компьютера в МТИ была разработка CONS-компьютера, CADR-компьютера; с 1982г. Лисп-компьютер начал выпускаться как коммерческая модель. В настоящее время эту машину продают фирмы Symolics, LMI, Xerox.

История Пролог-компьютера значительно короче истории Лисп-компьютера. Можно считать, что она началась с разработки в Японии осенью 1983г. Организацией по разработке компьютерной техники новых поколений (ICOT) простых элементов аппаратного обеспечения. В последнее время выяснилось, что Пролог-компьютер имеет важное преимущество перед Лисп-компьютером - он оснащен средствами параллельной обработки (см.4.(в)(3)). Можно сказать, что Пролог-компьютер в большей степени, чем Лисп-компьютер, рассчитан на архитектуру, использующую СБИС. Благодаря последним достижениям техники СБИС можно ожидать появления Пролог-компьютера с еще более высокими эксплуатационными качествами. Исследования, преследующие эту цель, ведутся в настоящее время - в Японии и Англии.

Для реализации Лисп-компьютера и Пролог-компьютера можно указать три метода, иллюстрируемые рис.4.16. На этом рисунке ветвь [2] соответствует методу осуществления интерпретатора Лисп/Пролог непосредственно с помощью микропрограмм. Ветвь [3] относится к методу непосредственной генерации групп микрокоманд посредством компиляции программ Лисп/Пролог. Скорость выполнения, соответствующая этим трем методам, возрастает в очередности [3], [2], [1]. Однако из-за больших ограничений, накладываемых реально доступными объемами памяти с произвольной выборкой, которая должна вмещать микропрограммы, потенциальные возможности метода [3] не могут быть полностью реализованы. Метод [1] применен при реализации компьютера CADR (см.4.4(б)(3)), разработанного МТИ как разновидность Лисп-компьютера, а метод [2] - для построения компьютера PSI (см.4.4(в)(2)), разработанного ICOT в качестве одной из реализаций Пролог-компьютера.

Техника в руках дикаря Jap21610
Рис.4.16. Три метода реализации Лисп-компьютера и Пролог-компьютера.

(б) ЛИСП-КОМПЬЮТЕР
1) ОСНОВНОЙ МЕХАНИЗМ ВЫЧИСЛЕНИЙ НА ЯЗЫКЕ ЛИСП
Язык обработки символов Лисп наиболее широко используется в исследованиях в области искусственного интеллекта, главным образом в США. Он был разработан Дж.Маккарти в конце 50-х гг. Основным механизмом вычислений на языке Лисп является лямбда-исчисление (lambda calculus). Метод лямбда-исчисления был разработан А.Черчем в качестве строгой математической модели для вычисления функций и зарекомендовал себя как не уступающий по эффективности методу, реализованному в машине Тьюринга. Программа на языке Лисп составляется из лямбда-формул, записываемых, например, в виде лямбда x.f(x). х называется лямбда-переменной (связанной переменной). Выполнение программы на языке Лисп (вычисление) с помощью введения значений для х осуществляется на основе применения правил восстановления (логического вывода), называемых в методе лямбда-исчисления правилами альфа, бета, эта. Процедура изменения формулы продолжается до того момента, когда формула больше уже восстановлена быть не может. Правило бета, которое наиболее часто используется в программах на языке Лисп, записывается следующим образом.

Правило бета:

Техника в руках дикаря Jap21611

Однако оно не должно применяться в случае возникновения коллизий между связанными функциями вследствие замены x на t в f(x). Например, (лямбда x.(лямбда t.f(x)))(t) нельзя преобразовать в лямбда t.f(t).

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

(2) ОБРАБОТКА СПИСКОВ
Логической основой языка Лисп является метод лямбда-исчисления. Однако причина широкого использования языка Лисп в работах по исследованию искусственного интеллекта заключается в том, что ему присуща функция эффективной обработки списков. На языке Лисп список представляется в виде

(<e1> <e2> ... <en>)

<ei> называется атомом (целое число, переменная) или списком. Примеры списков:

(AUTHER TITLE PUBLISHER (YEAR)) (4.45)
(LAMBDA (X,Y) (CONS X Y)) (4.46)

(4.46) представляет собой лямбда-выражение, в котором X, Y являются связанными переменными. Обратим внимание на то, что и лямбда-выражение представляется списком. Представление в памяти (4.45) показано на рис.4.17. Клоз 2W называется узлом (ячейкой) Лисп.

Техника в руках дикаря Jap21710
Рис.4.17. Представление в памяти списка (AUTHER TITLE PUBLISHER (YEAR)).

Основными функциями обработки списков являются CONS, CAR, CDR.

CONS - функция с двумя аргументами. (CONS X Y) означает, что к голове списка X добавляется список Y и образуется новый список, который становится значением функции.

CAR - функция с одной переменной. (CAR X) означает, что выбирается головной элемент списка X, который становится значением функции.

CDR - функция с одной переменной. (CDR X) означает, что выбирается головной элемент списка X, а оставшаяся часть становится значением функции.

Пусть, например, имеются два списка X = HISAO, Y = (MIYAUCHI). Тогда

(CONS X Y) = (HISAO MIYAUCHI)
(CAR (CONS X Y)) = HISAO
(CDR (CONS X Y)) = (MIYAUCHI)

Кроме вышеприведенных в качестве основных функций используются основные предикаты (значения функции "истина" и "ложь"; например, если в функции (АТОМ X) X является атомом, то используется предикат "истина", в противном случае - предикат "ложь" (обычно пустой список представляется как () или NIL)), условные предложения (COND) и т.д.

(3) ПРИМЕР ЛИСП-КОМПЬЮТЕРА (КОМПЬЮТЕР CADR)
Рассмотрим компьютер CADR, разработанный в МТИ, который является типичным примером Лисп-компьютера. На рис.4.18 представлена блок-схема микропроцессора CADR. CADR реализован на основе метода, проиллюстрированного рис.4.16. Компилятор формирует 16-разрядные макрокоманды (группы). Для представления данных отводится 32 бита, для представления адреса - 24 бита. Организация памяти страничного типа; на рис.4.18 представлена область памяти, вмещающая головную часть стека памяти. Для повышения возможностей параллельного доступа к информации начальные 32 слова из страничной памяти А помещаются в страничную память М. Обе эти памяти работают по принципу кэш-памяти. При страничной организации памяти 24-битовый виртуальный адрес преобразуется в 22-битовый физический адрес, по которому происходит обращение к основной памяти. Поскольку любая из основных функций языка Лисп: CAR, CADR, CONS и др., реализуется в виде одной макрокоманды, скорость реализации функций имеет тот же порядок, что и при построении машины по способу, проиллюстрированному рис.4.16.

Техника в руках дикаря Jap21810
Рис.4.18. Структурная схема компьютера CADR.

Как следует из объяснений, приведенных в 4.4(б)(1), при реализации метода лямбда-исчисления для оценки функции f в лямбда-выражении необходимо сохранять в какой-либо форме требуемую пару "переменная - значение переменной". При оценке функции обычно готовится фрейм, в который помещается информация, относящаяся к связям переменной, и информация, относящаяся к локальной переменной, появляющейся в случае необходимости выполнения набора нескольких Лисп-программ (PROG-feature). Затем этот фрейм засылается в перевернутый стек. В связи с этим в процессоре CADR стековые операции реализованы аппаратными средствами, что позволило повысить скорость обработки. Таким образом, микропроцессор CADR имеет стековую архитектуру, основанную на использовании фреймов. (Следует обратить внимание на то, что эта архитектура отличается от стековой архитектуры Пролог-компьютера).

Пара "имя переменной - значение переменной" может быть связана двумя способами: с помощью глубокой или поверхностной связи. Эти два вида связи показаны на рис. 4.19,а и б соответственно. Фрейм делится на звено доступа и звено управления. Первое указывает условия, при которых вызывалась функция, а второе - начальный фрейм, в который необходимо возвратиться после окончания выполнения функции. Дальнейшие подробности из-за недостатка места опускаем. Заметим лишь, что, если не сказывается действие FUNARG (CLOSURE), начало обоих звеньев одинаково.

Техника в руках дикаря Jap22010
Рис.4.19. а - глубокая связь; б - поверхностная связь.

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

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

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

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

Как уже отмечалось, слово состоит из 32 бит. Из ннх 5 бит используются для размещения признака, указывающего тип данных, 24 бита - в качестве адреса виртуальной памяти. Благодаря использованию данных, которым присвоен признак, можно с высокой скоростью выяснить тип данных. В слове остается еще три бита. Из них два бита используются в качестве поля кода CDR (рис.4.20).

Техника в руках дикаря Jap22110
Рис.4.20. Формат слова компьютера CADR, Из 32 бит 8 используются в качестве признаков.

Поле кода CDR используется в случае представления списка в памяти не в виде, показанном на рис.4.17, а в сжатом виде (compressed list). Поле кода CDR состоит из двух бит. Данные, представленные в области CDR сокращенного списка, указывают на наличие какого-либо из следующих признаков: CDR-NORMAL (нормально), CDR-NEXT (следующий), CDR-NIL (нулевой), CDR-ERROR (ошибка). Признак CDR-NORMAL указывает на то, что область CDR содержит сокращенный список. Представление сокращенного списка, эквивалентного списковой структуре, показанной на рис.4.17 (CDR-NORMAL), приведено на рис.4.21.

Техника в руках дикаря Jap22210
Рис.4.21. Сокращенный список, эквивалентный представленному на рис.4.17.

Сокращенный список впервые был использован в компьютере CONS (предшествовавшем компьютеру CADR), который имел признаковую архитектуру. Однако было известно, что при использовании сокращенных списков очень трудно выполнять операцию RPLACD объединения отдельных списков при их перекраивании в ходе выполнения программы. В компьютере CONS эта проблема решалась за счет введения понятия неявного указателя, аналогичного косвенному адресу. Задание неявного указателя оcyщecтвляeтcя в поле типа данных (см. рис.4.20). Неявный указатель отличается от косвенного адреса: префиксом указателя являются данные (а не команда). Например, операцию RPLACD можно осуществлять, помещая неявный указатель списка, подлежащего объединению, в область объединения сокращенных списков. В других областях сокращенного списка все остается без изменения, поэтому при эквивалентности адресов сохраняется равнозначность функций сравнения EQ и MEMQ.

В заключение кратко коснемся Лисп-компьютера с параллельной обработкой. При анализе аргументов функций в языке Лисп возможна их параллельная оценка (пока процесс оценки не сопряжен с выполнением других действий, например, RPLACD). Эту возможность разработчики попытались положить в основу создания Лисп-компьютера с параллельной обработкой. Кроме того, делаются попытки параллельного осуществления "сбора мусора". Исследуется также связь между машинной обработкой потоков данных и обработкой списков. Однако что касается осуществимости различных видов параллельной обработки, заложенных в структуре программы, то, как показано в 4.4(в)(3), язык Пролог в этом отношении имеет преимущества перед языком Лисп. Мы не можем останавливаться на этом подробнее; заметим лишь, что предпринимаются попытки реализации метода хэширования аппаратными средствами; ведутся исследования по повышению скорости обработки списков.
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Пт Дек 02, 2022 12:25 am

(в) ПРОЛОГ-КОМПЬЮТЕР
Настоятельная потребность в создании Пролог-компьютера, так же как в свое время - Лисп-компьютера, возникла в связи с расширяющимся использованием языка Пролог в качестве языка обработки символов. Как будет показано ниже, возможность создания структуры машины, способной производить параллельную обработку, аппаратно реализующей язык Пролог, тесно связана с разработкой архитектурных принципов ЭВМ ненеймановского типа. Можно предположить, что исследования в этом направлении благодаря стремительному развитию техники СБИС еще больше ускорятся.

В ближайшее время японская организация по разработке компьютерной техники новых поколений (ICOT) должна закончить создание Пролог-компьютера, названного PSI (Personal Sequential Inference Machine). Его архитектура ориентирована на последовательную обработку. В данном разделе рассматривается архитектура Пролог-компьютера, предложенная Варреном, затем в общих чертах описывается компьютер PSI, разрабатываемый ICOT как развитие идей Варрена, и излагаются основные идеи реализации Пролог-компьютера, выполняющего параллельную обработку.

(1) БАЗОВАЯ АРХИТЕКТУРА ПРОЛОГ-КОМПЬЮТЕРА ДЛЯ ПОСЛЕДОВАТЕЛЬНОЙ ОБРАБОТКИ
В качестве меры оценки мощности Пролог-компьютера, в основу построения которого положен механизм логического вывода (логических операций), используется LIPS (Logical Instruction per Second - число логических операций (команд), выполняемых в секунду). LIPS показывает, сколько раз за одну секунду осуществляется операция, для которой используется правило логического вывода. В Пролог-компьютере принята мера оценки, показывающая, сколько раз за одну секунду осуществляется принятие решения по принципу резолюций (см. разд.4.3(б)(2)). Для Пролог-компьютера модели PSI последовательного типа, находящегося в процессе разработки ICOT, запланирована мощность 40kLIPS.

Архитектура Пролог-компьютера последовательного действия по сравнению с архитектурой Лисп-компьютера имеет характерную особенность, заключающуюся в наличии механизмов осуществления следующих вычислительных операций: (I) операции унификации, (II) операции отступа.

Остановимся на них подробнее.

(I) ОПЕРАЦИЯ УНИФИКАЦИИ
Алгоритм выполнения операции унификации приведен в подразд.4.2(б)(3); в подразд.4.3(б)(1) показано, как реализуется программа на языке Пролог с помощью операции унификации. Поскольку операция унификации является основой механизма обработки программы, на языке Пролог, Пролог-компьютер называют иногда машиной унификации. Реализация операции унификации средствами аппаратного обеспечения в Пролог-компьютере позволяет достичь значительного ускорения обработки.

Операция унификации в Пролог-компьютере осуществляется в два этапа:
(1-1). Отыскивается клоз Хорна, содержащий целевой клоз, который должен быть реализован (caller), и голову, которая должна быть с ним унифицирована (callee) (см. подразд.4.3(б)(1)).
(1-2). Осуществляется унификация для аргументов (обычно в порядке очередности, начиная с первого аргумента), относящихся к предикатам caller и callee.

Унификатор, полученный в результате унификации, можно рассматривать как связь значений переменных с именами переменных, входящих в аргументы caller и callee. Следует внимательно отнестись к тому, что при этом возможна как передача значений (установление связи) со стороны caller к переменной, находящейся на стороне callee (для унификатора на верхней строчке рис.4.15 связь устанавливается следующим образом: значения [a,b] на стороне caller разделяются и передаются переменным H и U на сторону callee, что показано схемами H<-a, U<-b), так и, наоборот, передача значений со стороны callee переменным на стороне caller (для унификатора на верхней строчке рис.4.15 связь, устанавливаемая с помощью передачи значения со стороны callee переменной X, находящейся на стороне caller, показана как X<-[a|W](<-[a|[b|W']]<-[a|[b|[с]]]<-[a,b,c]). Имеет место так называемая двунаправленная передача данных. Это одна из специфических особенностей Пролога, которой не обладают другие языки. Именно поэтому для Пролог-компьютера оказалась необходимой своя специфическая архитектура.

(II) ОПЕРАЦИЯ ОТСТУПА
Когда имеется несколько клозов Хорна с одной и той же головой, в принципе безразлично, какой клоз выбрать для реализации. В некоторых случаях оказывается возможной параллельная реализация всех клозов Хорна. Тем самым в выполнение программы на Прологе вводится недетерминированность. Пролог - язык недетерминированного программирования. (Следует обратить внимание на то обстоятельство, что в Прологе последовательного типа программа выполняется в порядке очередности, начиная с головного клоза Хорна. Поэтому, если изменить очередность Хорна, может образоваться бесконечный цикл. Именно в этом заключается смысл обязательного соблюдения очередности).

Для реализации в компьютере последовательного типа присущей программам на Прологе недетерминированности прежде всего выбирается и выполняется клоз Хорна, первый по порядку от головы, и, если результат его выполнения оказывается ложным, выбирается следующий клоз Хорна и т.д.; эта процедура повторяется до конца (исчерпания клозов). Данный механизм управления выполнением называется отступом; о нем уже упоминалось в подразд.4.2(б)(1).

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

Отступ осуществляется при помощи стекового механизма. Однако необходимо помнить, что стековый механизм в Пролог-компьютере по виду отличается от обычного, используемого, например, при вызове функции или при вызове процедуры. В случае обычного стека вызова в момент, когда caller вызывает callee, в стек засылаются условия выполнения callee (далее называемые просто фреймом), а когда результат выполнения callee возвращается из callee, фрейм callee сразу же извлекается из стека и стирается. Что же касается стекового механизма в Пролог-компьютере, то и в случае возвращения результата после упешного выполнения callee операция извлечения фрейма callee для подготовки отступа в принципе не используется. Напоминаем, что этот стековый механизм в большой степени отличается от стековой архитектуры Лисп-компьютера (рис.4.19).

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

(III) ОСНОВНОЙ МЕХАНИЗМ СТЕКА
Всякий раз, когда caller вызывает callee, фрейм для выполнения callee засылается в стек. Информация, заключенная в фрейме, делится на информацию для управления выполнением и информацию, относящуюся к переменным, входящим в callee. Рассмотрим сначала информацию для управления выполнением. Информация для управления выполнением состоит из следующих пяти компонент.
А: Адрес цели, которая должна быть выполнена следующей после успешного выполнения цели из тела нового клоза (caller).
X: Адрес нового клоза.
V: Адрес клоза, находящегося в процессе выполнения в данный момент.
VV: Адрес клоза, для которого должен быть произведен отступ. Если при неудачном выполнении клоза, находящегося в процессе выполнения в данный момент, этот клоз и голова оказываются одинаковыми и при этом существует еще невыполненный клоз, то VV = V, в противном случае производится отступ (если при этом VV < V, то FL-неопределенность).
FL: Адрес клоза, который будет выбран следующим в случае, когда выполнение клоза, находящегося в процессе выполнения в данный момент, окажется успешным (таким образом, в этом случае VV = V).
Рассмотрим в качестве примера следующую программу;

[0] ?- a(X).
[1] a(X) :- b(X),c(X),d(X),e(X).
[2] b(X).
[3] c(X) :- h(X).
[4] h(1).
h(2).
[5] d(X) :- f(X), g(X).
d(X) :- i(X).
[6] f(X) :- h(1),...
f(X) :- ...

На рис.4.22 показано состояние стека в момент вызова элемента программы [5] в позиции _8_ при выполнении программы в очередности _1_, _2_, ... Причина, по которой фрейм элемента программы [2] не засылается в стек, будет изложена позднее. Информация для управления, записанная в фрейме элемента программы [5], используется для подготовки отступа; с V1, TR будет сказано позднее.

Техника в руках дикаря Jap22610
Рис.4.22. Выполнение программы на языке Пролог: состояние стека и значения регистров.

В регистрах _X_, _V_, _VV_, предназначенных для выполнения элемента программы [5], формируются адреса, как показано на рис.4.22.

СЛУЧАЙ 1. При успешной унификации с головой элемента программы [5] на основании _8_ имеет место _VV_ = _V_, поэтому известно, что имеется еще невыполненный клоз, и на основании FL_8_ осуществляется d(X) :- i(X). Если при этом больше нет невыполненных клозов, кроме d(X) :- i(X), то из поля VV в фрейм элемента программы [5] рис.4.22 извлекается адрес первого фрейма, для которого производится отступ, и заносится в регистр _VV_. Остальные регистры сохраняют прежнее состояние. Такой отступ называется мелким отступом (рис.4.23).

Техника в руках дикаря Jap22710
Рис.4.23. Состояние стека и значения регистров сразу после осуществления мелкого отступа по отношению к ситуации, показанной на рис.4.22.

На рис.4.23 показано положение, в котором выполнение d(X) :- i(X) оказывается успешным. Если принять во внимание, что _VV_ < _V_, то в этом случае в соответствии с _VV_ имеет место так называемый глубокий отступ, и фрейм элемента программы [5] выталкивается из стека рис.4.23. При этом значение регистра _VV_ (адрес, записанный в фрейме элемента программы [4]) перемещается в регистр _V_, и одновременно с формированием в регистре _X_ значения поля X, записанного в фрейме элемента программы [4], из поля FL выбирается значение FL_5_, т.е. адрес h(2). Поскольку при этом больше не остается невыполненных клозов, относящихся к элементу программы [4], значение поля VV фрейма элемента программы [4] извлекается и заносится в регистр _VV_. При успешном выполнении h{2) элемента программы [4] должны успешно выполняться и элементы программы [3], [1] и т.д. по порядку, поэтому ясно, что успешным окажется и выполнение элемента программы [0], и, следовательно, значение поля VV фрейма элемента программы [4] при этом указывает фрейм элемента программы [0] (рис.4.24).

Техника в руках дикаря Jap22711
Рис.4.24. Состояние стека и значеиия регистров сразу после осуществления глубокого отступа по отношению к ситуации, показанной на рис.4.23.

Важно иметь в виду, что прн возникновении отступа - мелкого или глубокого - производится выталкивание информации из стека. Сравнивая рис.4.22 и 4.23, можно заключить, что в случае мелкого отступа фрейм элемента программы [5] из стека не выталкивается, но на самом деле фрейм элемента программы [5] (см. рис.4.22) при этом выталкивается, а при выполнении FL_8_ в стек засылается новый фрейм элемента программы [5] рис. 4.23. Естественно, что если при этом к исходному фрейму элемента программы [5], т.е. к переменным фрейма элемента программы [1], с помощью операции унификации привязываются значения, то они опять должны возвратиться в исходное состояние неопределенности. В этом случае используется информация поля TR (trail), размещенная в этом фрейме. В стеке TR записывается, что именно возвращается в исходное состояние неопределенности, а в поле TR записывается указатель на возвращаемую в это состояние информацию. Поле V1 рассматривается в (IV).

СЛУЧАЙ 2. Если унификация с головой элемента программы [5] на основании _8_ рис.4.22 оказывается успешной, то для выполнения элемента программы [6] фрейм элемента программы [6] засылается в стек рис.4.22. При этом в поле X фрейма элемента программы [6] формируется адрес фрейма, а в поле VV формируется значение _VV_ (рис.4.22), и таким образом осуществляется подготовка к отступу (рис.4.25).

Техника в руках дикаря Jap22810
Рис.4.25. Положение стека и значения регистров после выполнения [5] по отношению к ситуации, показанной на рис.4.22.

((IV) ЛОКАЛЬНЫЙ СТЕК И ГЛОБАЛЬНЫЙ СТЕК
Рассмотрим причину, по которой поле элемента программы [2] в правом стеке рис.4.22 не засылается в стек. Прежде всего нет другого клоза, креме [2], имеющего голову, одинаковую с [2]. Это значит, что при выполнении [2] отсутствует всякая недетерминированность, а имеет место детерминированность, и никакой необходимости в отступе нет. Таким образом, в случае возвращения при успешном исходе в позиции _3_ рис.4.22 фрейм элемента программы [2] может быть занесен в стек. Несмотря на то что он возвращается при успешном исходе в позиции _6_ рис.4.22, фрейм элемента программы [4] остается в стеке, и этим создаются хорошие условия для сравнения при подготовке отступа.

Посмотрим теперь, что получится, если вместо элемента программы [2] взять

[2]' b(foo(A,B)).

[2]' детерминирован, а с X элементом программы [2] связан комплексный член foo(A,В) (см. подразд.4.2(б)(3)). При этом в комплексный член входят переменные A, B. Если сделать так, чтобы комплексный член, включающий эти переменные, был записан в фрейме элемента программы [2], то при возвращении в позиции _3_ рис.4.22 он будет вытолкнут из стека и от него не останется следа. Но, поскольку существует возможность использования переменных A, B в c(X), d(X), e(X) клоза [1], область, обеспечиваемая для переменных A, B, должна представлять собой специально выделенное пространство памяти, организованной в виде стека, из которого они будут вытолкнуты при возвращении в позиции _3_. Это пространство памяти в дальнейшем будем называть глобальным стеком. В противоположность ему стек, описанный в подразд.(III), называется локальным стеком.

Различие между глобальным и локальным стеками заключается в том, что после выполнения детерминированного клоза выталкивание из глобального стека невозможно, а выталкивание из локального стека возможно. В случае же отступа выталкивание осуществляется из обоих стеков. В поле V1 на рис.4.22 содержится адрес соответствующего фрейма в глобальном стеке, благодаря которому возможен выбор фрейма в глобальном стеке при отступе.

(V) ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ СЛОЖНЫХ ЧЛЕНОВ
Для внутреннего представления сложных членов существует метод их оформления в виде так называемых молекул; молекула состоит из пары указателей: "скелет" и "среда". Этот метод называется методом разделения структуры. Скелет выражает структуру (синтаксис) сложного члена. На рис.4.26,а представлена структура данных, сформированных в локальном и глобальном стеках в ситуации, когда реализуется [2]' подразд.(IV) в позиции _2_ рис.4.22. X представляет собой молекулу. Это представление содержит следующую информацию. В соответствии с префиксом указателя "скелет" молекулы X именем переменной является foo, которая имеет два аргумента. Эти аргументы в соответствии с префиксом указателя "среда" молекулы X соответствуют данным #1 (Env 1) и #2 (Env2).

Техника в руках дикаря Jap23010
Рис.4.26. a - представление переменной X <- foo(А,В) с помощью метода разделения структуры; б - представление той же переменной с помощью метода копирования.

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

Оба этих метода имеют свои преимущества и недостатки. При использовании метода разделения структуры объем данных, помещаемых в глобальный стек, меньше, чем при использовании метода копирования. Однако из-за ограничений, накладываемых машиной, для представления молекул, содержащих два слова, в случае метода разделения структуры требуется добавочная память (в машине Dec10 PROLOG молекула представляется одним словом, а в машине PSI - двумя словами). Кроме того, в случае доступа к сложному члену при использовании метода разделения структуры необходимы два указателя. Таким образом, разработчики программ на Прологе должны осторожно принимать решение о выборе метода представления сложных членов, тщательно взвешивая все сильные и слабые стороны этих двух методов.

(2) ПРИМЕР ПРОЛОГ-МАШИНЫ ПОСЛЕДОВАТЕЛЬНОГО ТИПА {МАШИНА PSI)
Машина PSI, осуществляющая последовательный логический вывод и находящаяся в процессе разработки ICOT, является первым в мире Пролог-компьютером последовательного типа. Структура машины PSI показана на рис.4.27. PSI может аппаратно реализовать в виде машинных команд расширенный язык Dec10 Пролог (называемый KLO). Поскольку эти машинные команды интерпретируются в виде микропрограммы, машина реализует метод, иллюстрируемый рис.4.16. Пролог требует сравнительно большого объема памяти, поэтому в машине может быть применена основная память максимального объема 16млн. слов (40 бит/слово). Для ускорения операций унификации и отступа используется механизм динамического разделения памяти; машина имеет стековую архитектуру.

Техника в руках дикаря Jap23210
Рис.4.27. Структурная схема Пролог-компьютера фирмы ICOT.

Архитектура машины включает четыре стека. Кроме упоминавшихся в (III) и (IV) подразд.(1) локального стека, Глобального стека и стека TR имеется еще стек управления. Этот стек предназначен для работы со сложными командами управления, входящими в расширенный язык DeclO Пролог, называемый KLO. Представление сложных членов производится с помощью метода разделения структуры (рис.4.26,а). Этот метод для данного случая вполне нодходит, так как в машине PSI предполагается представлять сложные члены, доступ к которым производится не часто.

На одно слово отводится 40 бит; 32 бит предназначены для данных, 8 бит - для признаков. Благодаря применению признаков быстро осуществляется анализ типа данных, используемых в языке KLO. Использование признаков позволяет быстро обрабатывать даже данные, представленные иероглифами.

Память компьютера PSI делится на страницы емкостью 1тыс. слов; виртуальная память не используется. Поскольку таблицы всей страничной памяти обрабатываются в быстродействующем ЗУ, вычисление адреса производится за один машинный цикл.

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

Машина PSI является стековой машиной, содержащей механизм выполнения операций унификации и отступов. Она имеет архитектуру признаковой машины и аналогична машине CADR.

(3) РАБОТЫ ПО СОЗДАНИЮ ПРОЛОГ-КОМПЬЮТЕРА ПАРАЛЛЕЛЬНОГО ТИПА
Благодаря прогрессу техники СБИС появляется возможность широкомасштабной параллельной обработки, что до сих пор было недостижимо. Таким образом, сделан большой шаг в сторону снятия ограничений, накладываемых архитектурой компьютера неймановского типа, в основе которой лежала последовательная обработка, и создания компьютера ненеймановского типа. Выше указывалось, что Пролог имеет структуру, удобную для осуществления параллельной обработки. Поэтому предполагается, что можно сравнительно легко создать Пролог-компьютер параллельного типа. С этой целью были организованы научно-исследовательские работы в Японии (ICOT и Токийский университет) и в Англии (Лондонский университет). Однако исследования находятся пока на начальном этапе. Рассмотрим, как реализуется распараллеливание обработки, возможность которого заложена в языке Пролог, и поясним принципы, на которых базируется архитектура Пролог-компьютера параллельного типа.

Пролог обладает одной особенностью, о которой пока не упоминалось: программа на Прологе может быть представлена в виде И-ИЛИ-дерева. Например, программа на Прологе, приведенная в подразд.4.4(в)(1), может быть представлена в виде дерева И-ИЛИ, показанного на рис.4.28. Из рисунка видно, что ветви И представляют тело одного клоза Хорна, а ветвь ИЛИ представляет набор клозов, имеющих одну и ту же голову.

Техника в руках дикаря Jap23310
Рис.4.28. Представление программы на языке Пролог посредством дерева И-ИЛИ.

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

Как непосредственно следует из вышеприведенного пояснения, параллельную обработку можно обеспечить, ставя в соответствие каждому узлу дерева И-ИЛИ один процесс. Однако при этом приходится решать несколько проблем. Рассмотрим основные из них сначала применительно к И-параллелизму, а затем к ИЛИ-параллелизму.

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

Другой проблемой И-параллелизма является наличие общих переменных для порожденных процессов. Например, в выделенной верхней части рис.4.28 все порожденные процессы имеют общую переменную X. Проблемой является разрешение ситуации, когда получены разные результаты осуществления порожденных процессов при наличии у них общей переменной {резолюция конфликта). В общем случае это трудноразрешимая проблема. Разрабатывая метод, в соответствии с которым сначала исследуют свойства переменной, принадлежащей порожденным процессам, производят разделение порожденных процессов на группу процессов, которые должны выполняться последовательно, и группу процессов, которые могут быть выполнены параллельно; в соответствии с такой классификацией пытаются осуществить порожденные процессы. Если использовать принцип совмещения (одновременного выполнения) ветвей Пролог-программы, то группу порожденных процессов, обычно выполняемых последовательно, окажется возможным выполнять параллельно. Это третий вид параллелизма, называемого струйным параллелизмом.

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

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

Несмотря на наличие пока не решенных проблем, язык Пролог обладает четкой структурой, обеспечивающей четыре вида параллелизма: И-параллелизм, ИЛИ-параллелизм, струйный параллелизм и параллелизм операций унификации. Таким образом, по сравнению с другими языками Пролог открывает перспективу, связанную с возможностью использования принципа распараллеливания. Следует ожидать, что будут интенсивно проводиться работы, направленные на создание Пролог-компьютера параллельного типа, опирающиеся на исследование архитектуры компьютера ненеймановского типа и на прогресс техники СБИС. Таким образом, в ближайшее время ожидается появление компьютера ненеймановского типа с архитектурой, рассчитанной на применение СБИС, аналогичного машине связей, о которой было упомянуто в подразд.4.2(в). Поскольку компьютеры обоих этих типов имеют общие особенности, по мере конкретизации каждой из машин будут выявляться зависимости, характерные для них обоих. По мнению авторов книги, преимущества при этом на стороне Пролог-компьютера параллельного типа как имеющего прочную теоретическую базу. В заключение отметим необходимость проведения исследований связи Пролог-компьютера параллельного типа с машинами, осуществляющими обработку потоков данных, редактирование, а также использующих конвейерный механизм обработки и т.д. на основе достижений техники СБИС. Кроме того, необходимо учитывать повышение скорости обработки списков благодаря реализации методов хэширования аппаратными средствами Лисп-компьютера. Последние достижения в этой области исследований позволяют ожидать больших успехов.
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Сб Дек 03, 2022 12:12 am

4.5. ОБРАБОТКА ГРАФИЧЕСКОЙ ИНФОРМАЦИИ
(а) ЧТО ТАКОЕ ОБРАБОТКА ГРАФИЧЕСКОЙ ИНФОРМАЦИИ
В отличие от обработки изображений, рассмотренной в гл.3, целью которой были анализ и обработка входных изобразительных данных, задачей обработки графической информации является синтез и представление изображений (чертежей).

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

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

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

(б) СИСТЕМЫ ОБРАБОТКИ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ
(1) СУЩНОСТЬ ОБРАБОТКИ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ
Обработка графической информации сводится в основном к формированию желаемого графического изображения на экране дисплея, подобного графическому изображению объектов, показанному на рис.4.29, и к его применению. Для гибкого и оперативного осуществления этой задачи необходимо наличие следующих функциональных возможностей:
(I) Оперирование произвольными двумерными и трехмерными изображениями.
(II) Осуществление операций масштабирования (увеличения и уменьшения), параллельного переноса, поворота и др., формирование проекции (перспективного изображения) для получения эффекта стереоскопичности в случае трехмерных объектов, исключение фрагментов объектов, скрытых за другими изображениями.
(III) Представление ощущения цвета и материала на чертеже, создание тонов различной интенсивности.
(IV) Раздельная реализация функций 2 и 3 по элементам изображения (например, S1-S4 на рис.4.29).
(V) Выбор по желанию пользователя произвольного фрагмента из набора объектов и представление его в желаемом месте на экране дисплея, как это делается при работе с большими чертежами.
(VI) Инвариантность программы обработки графических изображений по отношению к типам дисплеев.

Техника в руках дикаря Jap23710
Рис.4.29. Пример изображения объектов.

Для осуществления вышеуказанных функций при обработке графических изображений обычно применяется стандартный метод, подобный представленному на рис.4.30. (В качестве стандартных методов обработки применяются такие методы, как CORE, являющийся стандартом АСМ США, GKS (Graphical Kernel System), ставший в последнее время международным стандартом и др. Эти методы в той или иной степени отличаются друг от друга, но здесь рассматриваются общие принципы, которые присущи всем этим методам).

Техника в руках дикаря Jap23711
Рис.4.30. Метод обработки графической информации.

(I) ФАЙЛ ДИСПЛЕЯ
Прежде всего сформируем полное графическое изображение объектов в пространстве координат (называемом системой координат Варда), удобном из соображений последующего использования.

Это полное графическое изображение определяется и поддерживается как база данных графического изображения, оформленная в виде файла дисплея (например, графическое изображение объектов на рис.4.29).

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

Сегменты формируются из элементов изображения, называемых примитивами. К ним относятся отрезки линий н точки, окружности, многоугольники и т.д. В основе обработки графических изображений лежит представление отдельных примитивов отрезками линий (векторами). Например, графическое изображение фрагмента S3 на рис.4.29 формируется, как показано на рис.4.31, из примитива, представляющего собой многоугольник, в котором отрезками линий связаны точки от Р1 до Р7, и примитива, представляющего собой ломаную линию, связывающую точки Р8, Р9 и Р10.

Техника в руках дикаря Jap23810
Рис.4.31. Представление графического изображения от дельного участка.

Кроме того, для описания сегментов используется информация о свойствах: при представлении сегментов добавляются указания о видимости примитива, его цвете, материале и т.д. Используя свойство видимости, можно формировать сегмент на экране дисплея или удалять его с экрана.

(II) ПРЕОБРАЗОВАНИЕ ГРАФИЧЕСКОГО ИЗОБРАЖЕНИЯ
Графическое изображение, определяемое в файле дисплея, может подвергаться преобразованиям с использованием описанных выше функциональных возможностей (II), (V) и др.

Прежде всего для получения возможности выделения только одного участка из всего графического изображения объектов приведем преобразование угла обзора ("вьюинга") следующим образом. Определим "окно" файла дисплея в координатах Варда, как показано на рис.4.32, и перенесем его в желаемое место (порт формирования изображения) экрана дисплея (при этом используется нормированная система координат устройства, в соответствии с которой поверхность экрана дисплея определяется в пределах единичного квадрата (0,0), (0,1) (1,1) (1,0)). С помощью изменения окна и порта формирования изображения можно в широких пределах варьировать представление на экране дисплея.

Техника в руках дикаря Jap23910
Рис.4.32. Преобразование изображения: а - система координат Варда; б - нормированная система устройства.

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

(III) ИНТЕРПРЕТАТОР ОТОБРАЖЕНИЯ НА ЭКРАНЕ ДИСПЛЕЯ
Для представления графических изображений используются самые разные типы дисплеев, отличающиеся друг от друга разрешающей способностью и размерами экрана (см. гл.3): дисплеи с восстановлением (обновлением) информации, растровые дисплеи, дисплеи с запоминанием, координатные графопостроительные дисплеи и др. Устройство, содержащее информацию об особенностях различных типов дисплеев, выполняет роль интерпретатора отображения на экране дисплея. Интерпретатор отображения на экране дисплея преобразует выводимое на экран изображение, представленное в нормированной системе координат устройства, независимой от типа дисплея, в изображение, описанное в системе координат конкретного дисплея. На экране растрового дисплея на этом этапе будут появляться еще и отрезки линий (векторы).

(2) ОСНОВНЫЕ ФУНКЦИИ ОБРАБОТКИ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ
При преобразованиях угла обзора и деформациях графического изображения основную роль играет преобразование координат, позволяющее выполнить масштабирование, перенос, проецирование и т.д.

(I) ПРЕОБРАЗОВАНИЕ КООРДИНАТ
Точка, являющаяся основным примитивом при отображении графического изображения на экране дисплея, представляется в двумерном случае вектором (x,y), а в трехмерном случае - вектором (x,y,z). Аналогично отрезок линии или другая совокупность точек представляется в двумерном случае как

Техника в руках дикаря Jap24010

а в трехмерном случае

Техника в руках дикаря Jap24011

Основным методом реализации масштабирования и поворота служит метод, в соответствии с которым формируется произведение матрицы Т преобразования 2*2 в двумерном случае (или 3*3 в трехмерном случае) на координаты (X,Y) исходной группы точек.

Рассмотрим применение этого метода конкретно для двумерного случая.

Техника в руках дикаря Jap24110

Координаты (X*,Y*) графического изображения после преобразования переходят в координаты {aX+bY,cX+dY), и, как показано на рис.4.33, появляется возможность с помощью матрицы преобразования Т автоматически выполнить увеличение или уменьшение размеров изображения на экране дисплея по осям x, y и поворот на угол Тета вокруг начала координат против часовой стрелки.

Техника в руках дикаря Jap24111
Рис.4.33. Примеры масштабирования и поворота.

При сложном преобразовании T1, Т2, .... Тm, включающем разные шаги масштабирования с последующим поворотом, можно провести вычисление одной матрицы Т следующим образом;

(X*,Y*) = (X,Y) * T1 * T2 * ... * Tm = (X,Y)*(Т1*T2*...*Tm) = (X,Y)Tт (4.49)

Например, матрица Tт преобразования, заключающегося в увеличении размеров в два раза по оси X, в последующем увеличении размеров в четыре раза по оси Y и заключительном повороте на 45o, вычисляется следующим образом:

Техника в руках дикаря Jap24112

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

В однородных координатах кроме действительных координатных осей X,Y,Z предполагается наличие еще одной, эквивалентной оси w, и точка, имеющая координаты (x,y,(z)), представляется в виде (wx, wy, (wz), w), где w - произвольное число ("эквивалент"), не равное 0.

Соответствие точке в действительных координатах может быть получено при делении всего выражения на эквивалент; в результате выражение принимает вид (x, y, (z), 1).

При использовании таких однородных координат преобразование координат может быть проведено совершенно аналогично вышеприведенному, за исключением того, что в двумерном случае в качестве матрицы преобразования T0 используется матрица 3*3, а в трехмерном случае - матрица 4*4.

При этом общая матрица преобразования T02(T03) для двумерного (трехмерного) случая будет иметь следующий вид:

Техника в руках дикаря Jap24210

Частичная матрица 2*2 (3*3)

Техника в руках дикаря Jap24211

подобно матрице основного преобразования соответствует таким преобразованиям, как масштабирование и поворот. Частичная матрица 1*2 (1*3) l, m, n соответствует параллельному переносу, частичная матрица 2*1 (3*1) p, q, r - проекции, s - масштабированию всего объекта в целом. Например, если использовать матрицу

Техника в руках дикаря Jap24212

то ясно, что в результате преобразования точки [wx,wy,w] в [wx+wl,wy+wm,w] = [x+l,y+m,1] будет осуществлен параллельный перенос на l по оси X и на m по оси Y.

Техника в руках дикаря Jap24310
Рис.4.34. Пример преобразования изображения. Поворот + параллельный перенос + проекция (в плоскости проекции z=0, точка наблюдення (0,0,k)).

Проецированием называют преобразование, прн котором трехмерное графическое изображение проецируется на определенную плоскость. Например, как показано на рис.4.34, используя результат вычисления матрицы р, q, r, можно механически осуществить проецирование с преобразованием тональности изображения. Прямоугольный параллелепипед, показанный на рис.4.34,а поворачивается на угол Тета вокруг оси Y и перемещается параллельным переносом в положение (0,m,n). Это тело можно рассматривать как проекцию на плоскость Z=0 при наблюдении из точки k на оси X. В таком случае матрица преобразования может быть задана в следующем виде:

Техника в руках дикаря Jap24311

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

(II) ФОРМИРОВАНИЕ ОКНА
Функция выделения из всего графического изображения объекта, определяемого в координатах Варда, необходимого фрагмента и преобразования его для отображения в порту формирования изображения называется формированием окна ("уиндоуинг"). В качестве окна в двумерном случае обычно выделяют прямоугольную область (в трехмерном случае - область, заключенную в четырехгранную пирамиду). При формировании окна необходимо выделить из файла дисплея только требуемые данные (отрезки). Функция осуществления этой операции называется ограничением. Как видно на рис.4.35, при ограничении применяется эффективный метод определения отрезков, вырезанных окном, путем проверки делением пополам. Согласно этому методу, если выяснено, внутри окна или вне его находятся оба конца (x0,y0) и (x1,y1) отрезка, относящегося к объекту, то далее проверяют, находится ли внутри окна средняя точка (x0+Dx/2,y0+Dy/2) этого отрезка, а затем, повторяя проверку последовательно для средних точек образующихся половин отрезков, выделяют часть отрезка, которая попала внутрь окна. Этот метод можно реализовать аппаратными средствами.

Техника в руках дикаря Jap24410
Рис.4.35. Функция ограничения.

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

Техника в руках дикаря Jap24510
Рис.4.36. Управление несколькими окнами.

(III) УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ И НЕВИДИМЫХ ПЛОСКОСТЕЙ
При обработке графических изображений, особенно в трехмерных случаях, важную роль играет функция удаления невидимых линий и невидимых плоскостей для придания представляемому объекту естественного вида. Это функция, воспроизводящая тот принцип, что плоскость или линия изображения фрагмента, будучи спроецированной из точки наблюдения в некоторую плоскость проекции, в другой плоскости изображения фрагмента оказывается невидимой.

Наиболее известным методом удаления невидимых линий и невидимых плоскостей является алгоритм линий сканирования (рис.4.37). В соответствии с этим методом предполагая, что точка наблюдения бесконечно удалена от оси Z (параллельная проекция), последовательно перемещают плоскость y=r в направлении оси Y до пересечения с плоскостями, являющимися объектами изображения (плоскости A, B, C на рис.4.37,а). Если распределить концы линий пересечения плоскости сканирования с изображенными плоскостями в порядке следования значений по оси X, то, как видно на рис.4.37,б, линия сканирования будет разделяться на "промежутки". Каждый промежуток будет характеризоваться тем, какие именно плоскости видны в этом промежутке из точки наблюдения. Сравнивая глубину отдельных линий пересечения в каждом из промежутков, можно определить линию с минимальной глубиной. Остальные линии, попадающие в промежуток, будут невидимыми.

Техника в руках дикаря Jap24610
Рис.4.37. Удаление невидимых линий с помощью алгоритма линий сканирования.

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

(в) РЕАЛИЗАЦИЯ ОБРАБОТКИ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ
В случае реализации набора функций обработки графической информации, приведенных на рис.4.30, выполнение их с помощью программного обеспечения любой ЭВМ общего назначения обычно приводит к большим затратам времени, в связи с чем часто оказывается невозможным удовлетворить требования к быстродействию для той или иной области применения. Поэтому в последнее время в расчете на успехи в области техники СБИС работы по созданию персонального процессора для обработки графической информации ведутся в трех направлениях.

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

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

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

Все эти направления уже рассматривались в гл.3 в связи с обработкой изображений. Остановимся на первых двух направлениях (о третьем см. гл.2).

(1) СТРУКТУРА С ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИЕЙ ФУНКЦИЙ
На данном этапе наиболее практичным направлением создания персонального процессора для обработки графической информации является структура с параллельной реализацией функций. В структуре с параллельной реализацией функций решается задача оснащения дисплея дополнительными функциями, необходимыми для обработки графической информации аппаратными средствами, дополняющими систему индикации. На рис.4.38 показана типичная структура такой системы обработки графической информации.

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

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

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

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

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

Устройство формирования векторов формирует в фреймовой памяти отрезки линий, являющиеся основными элементами изображения. В растровой системе отображения, получающей в последнее время все большее распространение (см. подразд.3.3(в)), вектор А, В формируется в виде ряда разрозненных элементов изображения (рис.4.39). На рис.4.39,а видны наклон и зигзаго-образность (джаггинг) отрезка. В последнее время часто осуществляется сглаживание джаггинга за счет использования многолучевой системы отображения и подбора частотности (рис.4.39,б).

Техника в руках дикаря Jap24910
Рис.4.39. Метод формирования векторов в растровой системе отображения. а - обычный метод; б - метод сглаживания джаггинга. Площадь соответствует частотности.

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

Кроме перечисленных устройств, при необходимости в систему включаются устройства управления обработкой невидимых плоскостей с помощью Z-буфера и несколькими окнами, а также устройство управления тоном.

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

С другой стороны, если ограничиться основными функциями обработки графической информации, такими как формирование векторов, знаков, окружностей и многоугольников, управление фреймовой памятью и др., можно уже говорить об их реализации с использованием БИС. К таким БИС, называемым БИС управления графиками, относятся созданные фирмой Thomson БИС типа THOMSON EF9365 и БИС типа мPD7220 японской фирмы "Нихон дэнки". При использовании БИС мPD7220 оказывается возможным формирование изображения одного элемента на экране растрового дисплея за 720нс.

(2) МУЛЬТИПРОЦЕССОРНАЯ СТРУКТУРА
В такой области обработки графической информации, как компьютерная мультипликация, высок удельный вес видов обработки, требующих больших затрат времени, таких как получение проекции, удаление невидимых плоскостей, затушевывание, указание материала и т.д., поэтому желательно повышение быстродействия этих операций. В персональных системах обработки графической информации, в основу которых положена мультипроцессорная структура, графическая информация, являющаяся объектом обработки, делится на несколько небольших частей, которые распределяются между соответствующими процессорами (микрокомпьютерами), производящими их обработку параллельно.

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

В экспериментальной системе LINKS-1 Осакского университета, базирующейся на этой структуре, применяются алгоритм обработки невидимых плоскостей, в котором используется идея "линий наблюдения", связывающих отдельные элементы графического изображения с точкой наблюдения, алгоритм обработки тона, алгоритм обработки представления материала. Благодаря разделению графического изображения в направлении линии сканирования при параллельной обработке с помощью структуры SIMD, содержащей 64 микрокомпьютера, достигается производительность, почти пропорциональная числу процессоров.

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

(г) ПРИМЕНЕНИЕ ОБРАБОТКИ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ
Область применения техники обработки графической информации чрезвычайно широка. Это компьютерная мультипликация и компьютерное рисование, машинное проектирование логических схем и прокладки труб и проводов, машинное проектирование/машинное изготовление дизайнерских проектов механических конструкций, составление и применение географических карт, разного рода моделирование и т.д. В этих областях наряду с основными видами обработки, которые были упомянуты выше, используются разнообразные комбинации видов обработки графической информации. Рассмотрим несколько примеров.

(1) КОМПЬЮТЕРНАЯ МУЛЬТИПЛИКАЦИЯ
Компьютерная мультипликация, находящая широкое применение при съемке мультипликационных и рекламных фильмов, представляет собой пример получения и использования движущегося изображения путем обработки графической информации. Издавна известны техника мультипликации на целлулоиде (метод, при котором на целлулоидной пластинке точка за точкой рисуют изображение и, понемногу перемещая его, снимают на пленку) и техника кукольной мультипликации (метод, при котором изготовленные куклы и другие предметы снимаются на пленку при малых последовательных перемещениях). Компьютерная мультипликация представляет собой ту же технику, реализованную машинными средствами.

При подготовке мультипликации создается трехмерная математическая модель предмета, являющегося объектом съемки, для которой последовательно выполняются различные виды обработки графической информации: параллельный перенос, масштабирование, поворот, а также затушевывание, придание ощущения материала, удаление невидимых плоскостей и т.д. Например, как показано на рис.4.40, можно создать пейзаж порта, если провести обработку "корабля" с помощью масштабирования, обработку "чаек" - параллельным переносом и поворотом, обработку фона - параллельным переносом. При этом для достижения большой оперативности создания мультипликации разрабатываются программы операций, среди которых приобрела популярность программа ANTICS.

Техника в руках дикаря Jap25110
Рис.4.40. Пример компьютерной мультипликации.

(2) МАШИННОЕ ДИЗАЙНЕРСКОЕ ПРОЕКТИРОВАНИЕ
Одним из важных аспектов применения обработки графической информации является также проектирование механических конструкций. Целью создания системы машинного проектирования является разработка метода дизайнерского проектирования, обладающего очевидными преимуществами, заключающимися в возможности быстрой конкретизации и оценки идеи проектировщика и воплощения ее в виде, доступном обозрению.
Для выполнения этих задач при использовании системы машинного проектирования в целях создания проекта формы механической конструкции, кроме рассмотренных выше основных функций обработки, требуется возможность осуществления формирования модели стереоскопического изображения (SOLID-модели), операций обработки (сложение, вычитание, объединение, пересечение и т.д.), а также операций произвольного обращения с формами криволинейных поверхностей. К числу систем, оснащенных указанными функциями, относятся известные системы СОМРАС Берлинского политехнического института, GEOMAP Токийского университета, GEOMOD фирмы SDRC (США), TIPS1 Университета Хоккайдо и др. На рис.4.41 показан пример проекта, созданного системой машинного дизайнерского проектирования.

Техника в руках дикаря Jap25210
Рис.4.41. Пример машинного дизайнерского проектирования (система MODIF, автор - доцент Токийского университета Ф.Кимура).
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Вс Дек 04, 2022 12:09 am

ПРОДОЛЖЕНИЕ ЛИРИЧЕСКОГО ОТСТУПЛЕНИЯ

ТАМ ЖЕ
Т.7. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И СХЕМОТЕХНИКА СБИС. 1988
4. АРХИТЕКТУРА СМОЛТОК-ОРИЕНТИРОВАННОГО ПРОЦЕССОРА
К.ФУТИ И Н.СУДЗУКИ
Перевод А.С.Чупахина

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

На спроектированном автором микропроцессоре "Катана" могут выполняться команды виртуальной машины Смолток-80. Это сделано для того, чтобы реализовать на нем большую систему программирования, а именно систему виртуальных отображений (the Virtual Image) Смолток-80, распространяемую фирмой "Ксерокс". С другой стороны, автором разработан компилятор для эффективной реализации системы виртуальных изображений на микропроцессоре общего назначения МС-68000.

Разговор об этом оптимизирующем компиляторе мы отложим до более удобного случая.

Виртуальная машина Смолток-80 выполняет три функции. Первая из них - функция интерпретации. Интерпретатор считывает команды языка, называемого БАЙТ-КОДОМ, и выполняет их. Следующая функция - управление объектами. Блок управления объектами создает необходимые объекты и передает их интерпретатору, а ставшие ненужными объекты собирает и использует для дальнейшей работы. Наконец, имеется система базовых операций. В нее входят операции ввода-вывода, управления процессами, а также другие базовые операции. В системе также регистрируются в качестве элементарных методов (primitive method) те операции, которые нельзя реализовать на системе Смолток (либо их реализация неэффективна) и которые реализуются в виде программ вне системы Смолток-80.

В данной главе в разд.4.1 и 4.3 рассматривается интерпретатор, а в разделе 4.2 - система управления объектами. Описания элементарных операций опущены.

4.1. СТРУКТУРА УПРАВЛЕНИЯ
Структура управления реализует последовательность, в которой должны выполняться команды языка (байт-кода) в системе Смолток-80. Система осуществляет синхронное управление, т.е. команды машинного языка считываются и выполняются последовательно, а также асинхронное управление, т.е. под воздействием внутренних или внешних сигналов происходит смена процессов и последовательность выполнения команд сильно меняется.

4.1.1. СИНХРОННОЕ УПРАВЛЕНИЕ
Синхронное управление, при котором команды языка выполняются одна за другой, определяет, какая команда должна выполняться следующей, за исключением случаев условного ветвления и посылки сообщений. Имеются три типа команд:
- команды выборки из памяти на регистр и засылки в память, которые всегда передают управление по очередному
адресу;
- команды ветвления и условного ветвления, которые передают управление по адресу, указанному в команде;
- команды посылки сообщений, которые также передают управление по адресу, указанному в команде, но с их помощью еще может осуществляться возврат.

В языке Смолток-80 почти все операции выполняются с помощью посылки сообщений. Поэтому прежде всего мы остановимся на таких важных для посылки сообщений понятиях, как контекст метода (method context) и контекст блока. Это два объекта, снабженные операционной средой.

КОНТЕКСТ МЕТОДА. При посылке сообщения создается объект, называемый контекстом метода. В него входит следующая информация:
- контекст вызова (sender);
- адрес команды;
- указатель стека;
- обрабатывающая процедура метода (объекты с байт-программами);
- получатель;
- аргументы;
- временные переменные;
- стек.

Эта информация необходима для выполнения метода. В компиляторах Алгола ее помещают в стек и называют ФРЕЙМОМ. Накапливая таким образом фреймы как объекты, можно сохранять контексты. Сохранение (retention) контекста состоит в том, что он не освобождается после того, как завершено выполнение контекста. При обычном вызове процедур контекст всегда ЗАВЕРШАЕТСЯ из вызванной процедуры в конце ее работы и необходимости в его сохранении нет. Однако при совместном выполнении процессов, работе сопрограмм и прочих сложностях в работу вовлекаются сложные механизмы, для которых недостаточно простых структур управления. Для их реализации в языке возникает необходимость в сохранении контекста. При этом также облегчается разработка отладчиков и других системных программ. Чтобы выдавать текущее состояние отлаживаемой программы, отладчик содержит ссылки на разные части контекста и осуществляет их преобразование. Если контекст организован как объект, то задача значительно упрощается. Однако сохранение контекста снижает эффективность. Важным предметом исследования является вопрос о том, как сохранить удобства, предоставляемые возможностью оформления контекста в виде объекта, и при этом не потерять эффективности.

На рис.4.1 показана структура контекста метода.

Техника в руках дикаря Jap15110
Рис.4.1. Структура контекста метода.
В системе Смолток-80 при посылке сообщения для контекстов методов создается специальный буфер, в котором накапливается вся информация, необходимая для выполнения сообщения. Контексты методов, как и другие объекты, утилизуются при "сборке мусора". Контекст блока содержит информацию, необходимую для реализации этой
функции.

КОНТЕКСТ БЛОКА. В языке Смолток-80 программы как таковые могут не выполняться; являясь параметрами операторов посылки сообщений, они могут подставляться в переменные. Эту возможность предоставляет оператор блока. Различные
операторы управления благодаря использованию блоков могут быть реализованы как сообщения. Например, оператор while
можно реализовать с помощью двух блоков следующим образом:

[x>y] whileTrue: [x <- x-l].

Аналогично при создании процессов блоки позволяют описывать программы, выполняющиеся внутри процессов. При  компиляции и выполнении такого блока создается контекст блока (block context), из блока возможен доступ ко всем временным переменным, объявленным в методах, определенных в блоке. Поэтому из контекста блока, созданного из блока, необходим доступ к контекстам методов, соответствующим методам, определенным в блоке. Кроме того, после окончания выполнения блока управление должно вернуться к некоторому контексту, и при этом должно сохраниться правильное значение указателя на контекст возврата.

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

Контекст блока содержит информацию, необходимую реализации этой функции (рис.4.2), а именно:
- контекст вызова (caller);
- адрес команды;
- указатель стека;
- число аргументов;
- начальное значение адреса команды;
- локальный контекст;
- стек.

Техника в руках дикаря Jap15210
Рис.4.2. Структура контекста блока.
Создается с целью реализации оператора блока в момент вызова метода, определенного  в операторе блока. Что касается контекста вызова, то данный контекст блока вызывался посылкой сообщения value, и прн нормальном завершении возврат происходит в оператор блока. Внутренний или локальный контекст создается прн определении оператора блока. При выполнении оператора возврата (стрелка вверх) внутри блока выполнение локального контекста завершается. Из локального контекста возможен доступ к временным переменным и параметрам. Начальное значение адреса команды запоминается, чтобы обеспечить возможность повторения несколько раз контекста блока.

Контекст вызова создается в момент вызова (активизации) блока и при вызове посылается сообщение value. При вычислениях внутри этого блока используются стек и указатель стека. Количество аргументов равно количеству параметров блока.

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

ЛОКАЛЬНЫЙ КОНТЕКСТ (home context). Он представляет собой контекст метода, определенного в блоке. В нем помещены временные переменные и формальные параметры метода, к которым может осуществляться доступ. Хранение параметров блока в локальном контексте сопряжено с некоторым риском, поскольку они представляют собой переменные, недоступные из других локальных контекстов. Однако помещение этих переменных в локальный контекст позволяет унифицировать доступ к переменным по сравнению с контекстом блока, что избавляет от необходимости создания специализированных команд. Если компилятор генерирует правильный объективный код, то неправильные обращения из локального контекста не допускаются. Даже при наличии вложенных структур возможен доступ ко всем формальным параметрам, поскольку все они помещаются в локальный контекст.

ПОСЫЛКА СООБЩЕНИЙ И ВОЗВРАТ. Смолток-80 является языком с поздним связыванием (late binding). Для позднего связывания характерно то, что в момент компиляции не происходит установления связей между посылкой сообщений и методами. Кроме того, даже для находящихся в одном и том же месте сообщений вызываемые методы в момент посылки сообщения могут быть различными.

При посылке сообщения необходимо решать вопросы, как задать его связь с методом и какую информацию передавать после того, как эта связь установлена. Алгоритм связывания при выполнении осуществляет следующие операции:
1) выталкивает из стека получателя сообщения;
2) входит в хеш-таблицу (составленную для множества методов) по селектору сообщения и классу;
3) если метод найден, то выполняет его;
4) иначе проводит поиск класса получателя в словаре классов;
5) если класс найден, то регистрирует его в хеш-таблице и затем выполняет метод;
6) иначе проводит поиск в словаре сообщений суперкласса. Переходит к шагу 4. Если суперкласса нет, то выдает сообщение об ошибке.

Структура массива методов, используемого в п.2, представлена на рис.4.3.

Техника в руках дикаря Jap15410
Рис.4.3. Структура массива методов.
При посылке сообщения происходит поиск в хеш-таблице по селектору сообщения и классу получателя. Если поиск завершается удачно, то сообщение с найденными методами н указателями примитивов выполняется. Прн неудаче происходит поиск по словарю.

Если поиск в массиве методов завершается успешно, то определяется объектный код, выполняемый с использованием обработчика метода и указателя примитива (primitive index). Указатель примитива используется, чтобы показать, используются ли примитивы при реализации данного метода, и в случае их использования указывает на объектный код примитива. Примитивы реализуются на машинном языке или на языке микрокоманд и используются для выполнения функций, не реализованных в рамках системы Смолток-80 (управление выводом, вычисления с большим быстродействием и т.д.).

Если значение указателя примитива равно нулю, то данный метод реализуется без применения примитивов, и при этом байт-программа считывается из объекта, указываемого обработчиком метода, и выполняется.

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

Техника в руках дикаря Jap15510
Рис.4.4. Словарь сообщений.
На него поступают ссылки нз класса. Словарь состоит из списков селекторов и методов. Селектор сообщения представляет собой идентификатор, т.е. объект, состоящий нз уникальной последовательности символов.

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

Вначале анализируется заголовок метода, и, если он реализован как примитив, производится выполнение этого примитива. При выполнении примитива контекст метода отсутствует. Заголовок метода рассмотрен в разд.4.2.3. Если метод реализуется не в виде примитива илн при выполнении примитива имели место ошибки, то этот метод выполняется с помощью процедуры, реализованной на языке Смолток-80. Для этого создается контекст метода (рис.4.1) в следующей последовательности:
1) создание экземпляра контекста метода;
2) подстановка в контекст метода в нужные места отправителя сообщения, значения начального адреса, начального значения указателя стека, обработчика метода;
3) копирование из стека вызывающей программы активного контекста (activeContext) получателя и значений фактических параметров;
4) помещение в активный контекст текущих значений регистров контекста (указатель команды - instructionPointer, указатель стека - stackPointer), чтение из нового контекста новых значений регистров контекста (локальный контекст - homeContext, получатель - receiver, метод - method, указатель команды - instructionPointer, указатель стека - stackPointer), изменение значений активного контекста.

При завершении выполнения метода выполняется команда возврата и происходит возврат в вызывающую программу. Существуют два способа возврата. Первый способ - возврат к отправителю сообщения, указанному в локальном контексте. Это происходит при выполнении оператора возврата (стрелка вверх) и при завершении работы метода. Второй способ - возврат к вызывающей программе, указанной в активном контексте. Это происходит при завершении работы оператора блока.

ПРИМИТИВЫ. На языке Смолток-80 не удается описать специальные команды ввода-вывода, а также методы высокого быстродействия. Такие методы зарегистрированы в таблице примитивов и вызываются из нее при посылке сообщения. Существуют два способа вызова из команд Смолток-80. Первый способ состоит в том, что, как сказано в предыдущем разделе (посылка сообщения и возврат), происходит поиск метода, и в результате поиска с помощью указателя примитива определяется место выполнения примитива. Этот способ не обеспечивает экономии во времени, необходимом на поиск метода. Второй способ применяется в случае выполнения программы, написанной в специализированной системе команд. При этом примитивы вызываются непосредственно.

Имеется 256 различных примитивов. Среди них 128 являются примитивами общего назначения.

Кроме них, существуют и специальные примитивы. Они сразу возвращают получателя или переменные экземпляра.  Указатели на них помещаются в заголовке метода.

4.1.2. АСИНХРОННОЕ УПРАВЛЕНИЕ
Для быстрого реагирования на операции ввода-вывода необходимо одновременно выполнять несколько видов деятельности. Для этой цели в системе Смолток-80 существует механизм процессов. Этот механизм передачи управления между несколькими процессами называют АСИНХРОННЫМ УПРАВЛЕНИЕМ.

Асинхронная передача управления может вызываться как внешними причинами, аналогичными сигналам прерывания по вводу-выводу, так и внутренними, когда выполняемые программы выполняют команды управления процессами. Внешние сигналы, поступающие в любой момент времени, называются АСИНХРОННЫМИ СИГНАЛАМИ, а внутренние, возникающие по завершении выполнения байт-программ,- СИНХРОННЫМИ СИГНАЛАМИ.

АСИНХРОННЫЕ СИГНАЛЫ. При поступлении сигналов прерывания по вводу-выводу необходимо запускать процессы, обрабатывающие их. Это связано с определенными трудностями, потому что прерывание происходит в произвольном месте выполнения программы. В частности, в случае когда байт-команда реализована несколькими микрокомандами, возникают трудности с переключением процессов между этими микрокомандами. Переключение процессов может происходить только как переход от одной байт-программы к другой, и при этом каждый раз выполняется процесс с максимальным приоритетом.

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

ПЕРЕКЛЮЧЕНИЕ ПРОЦЕССОВ. В случае, когда происходит прерывание текущего процесса и начинает выполняться другой, находящийся в состоянии ожидания, говорят, что происходит переключение процессов. Всякий раз, когда завершается выполнение байт-команды, происходит проверка, не возникли ли условия переключения процессов. Они возникают тогда, когда в байт-программе, выполняемой перед этим, был асинхронный сигнал и в списке семафоров имеется соответствующий семафор, либо когда в выполняемой перед этим программе имелась команда типа signal, wait, resume, suspend, запросившая переключение процесса.

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

КОМАНДЫ УПРАВЛЕНИЯ ПРОЦЕССАМИ. Переключение процессов может запрашиваться из процесса командами signal, wait, resume, suspend. По команде signal, посылаемой семафору, запускается процесс, находящийся в состоянии ожидания, если его приоритет к этому семафору выше, чем приоритет выполняющегося в настоящий момент процесса.

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

По команде resume, посылаемой семафору, запускается процесс, управляемый данным семафором, если его приоритет выше, чем приоритет выполняемого в данный момент процесса.

По команде suspend прерывается выполняющийся в данный момент процесс, затем среди ожидающих процессов выбирается и запускается на выполнение процесс с наивысшим приоритетом.

4.2. СТРУКТУРА ПАМЯТИ
В микроЭВМ, на которые ставится Смолток-80, часть основной памяти отводится под системную область. Сюда относятся интерпретатор, блок управления объектами, программы базовых операций и данные. В оставшейся области размещаются все программы, написанные на языке Смолток-80, и данные к ним. Программы в Смолтоке-80 хранятся также в форме объектов.

4.2.1. ОБЪЕКТЫ
УКАЗАТЕЛИ ОБЪЕКТОВ. Имеются 16-разрядные указатели объектов (Оор). Если значение Оор представляет собой четное число, то оно используется в качестве уникального имени крупного объекта, размещенного в информационной области. Если значение Оор - нечетное число, то им определяется экземпляр класса Smalllnteger, т.е. небольшое целое число. Таким образом, в информационной области можно разместить до 2**15 = 32768 объектов. В случае когда Оор является нечетным числом, его старшие 15 разрядов представляют собой целое число со знаком. Когда Оор, в качестве дополнения до двойки, принимает значения, равные, например, -3, -1, 1, 3, 5, то это соответствует экземплярам класса Smalllnteger: -2, -1, 0, 1, 2.

ТАБЛИЦА ОБЪЕКТОВ. Четное значение Оор является уникальным именем объекта в информационной области. Однако при этом значение его 16 разрядов не является непосредственным указателем адреса объекта. Они являются указателем в структуре данных, называемой таблицей объектов, состоящей из 65К слов (одно слово содержит 16 разрядов). В таблице объектов один объект обозначается двумя словами. Поэтому в указателе объекта, указывающем на таблицу объектов, правый крайний разряд всегда равен нулю. Значение, получаемое в результате суммирования начального адреса таблицы объектов, и значения указателя объекта являются физическими адресами точки входа в объект. Связи между этими адресами показаны на рис.4.5. Для доступа через Оор к содержимому объекта необходимо выполнить два обращения к памяти.

Техника в руках дикаря Jap15910
Рис.4.5. Обращение к объекту через указатель объекта. Поскольку указатель объекта является четным числом, он указывает на точку входа в таблицу объектов.

Таким образом, здесь введен механизм косвенных ссылок, который замедляет доступ к объектам. На это имеется несколько причин. Во-первых, длина указателя составляет всего лишь 16 разрядов, что не позволяет осуществлять адресацию больших объемов памяти. Во-вторых, даже если производится уплотнение основной памяти при работе с информационной областью, содержащей объекты, нет необходимости в изменении значений указателей объектов, что упрощает управление памятью. В-третьих, использование в языке Смолток-80 метода "сборки мусора" с подсчетом ссылок позволяет реализовать управление объектами. Этот метод утилизирует ставшие ненужными объекты после того, как на них не осталось ни одной ссылки с других объектов, однако при этом для каждого объекта необходимо иметь индивидуальный счетчик ссылок (reference count), в который записывается количество Оор, указывающих на данный объект. Если количество ссылок равно нулю, то это значит, что на данный объект никто не указывает, и он может быть утилизирован, т.е. занимаемая им память может быть освобождена. Для работы этого метода необходимо выделять место для записи количества ссылок. Поскольку существует таблица объектов, в ней можно выделить это место. Недостатком такого метода является значительное снижение быстродействия из-за двухуровневой косвенной адресации.

Каждая адресуемая единица таблицы объектов (ее называть ЗАПИСЬЮ) состоит из двух слов и указывает на один
объект. Ее структура показана на рис.4.6.

Техника в руках дикаря Jap15911
Рис.4.6. Одна адресуемая единица в таблице объектов, состоящая из слов. В начале первого слова находится восьмиразрядный счетчик, за ним - одноразрядные признаки О, Р, F, а затем следует четырехразрядное поле сегмента. Во втором слове указывается смещение адреса.

В этой записи поле счетчика используется для указания количества ссылок. Поле Р показывает, является ли содержимое объекта указателем (поле Р равно 1) или нет. В случае если содержимое объекта не является указателем, оно представляет собой массив байтов, и если при этом длина массива является нечетным числом, то поле 0 равняется 1. Значение поля F, равное 1, указывает, что данный элемент таблицы объектов не используется. Поля сегмента и смещения, сцепленные вместе, характеризуют 20-разрядный абсолютный адрес объекта.

СТРУКТУРА ОБЪЕКТА. Объект состоит из целого количества 16-разрядных слов. Первые два слова являются заголовком. Он состоит из указателя объекта, указывающего длину объекта и класс (рис.4.7). Объекты делятся на группы в зависимости от того, что содержится в них, начиная с 0-го поля до N-1-го. Одна из этих групп характерна тем, что ее поля являются указателями объектов. Такие объекты называют УКАЗАТЕЛЬНЫМИ ОБЪЕКТАМИ (pointer object). Содержимые этих полей могут подставляться в переменные в качестве указателей, однако при этом они не только могут указывать на таблицу объектов, но и являться экземплярами класса Smalllnteger, т.е. быть целыми
числами.

Техника в руках дикаря Jap16010
Рис.4.7. Структура объекта. Указана полная длина объекта, включая два слова заголовка.

Вторую группу называют САМООПРЕДЕЛЕНИЯМИ ОБЪЕКТАМИ (nonpointer object). В этом случае все поля заняты 8- или 16-разрядными значениями. Самоопределенные объекты используются для эффективного хранения последовательностей символов и побитовых отображений экрана.

Объект является указательным только в том случае, когда в таблице объектов поле P=1. С другой стороны, существуют объекты, не являющиеся ни указательными, ни самоопределенными объектами. К ним относятся методы. Подробнее об этом написано в разд.4.2.3.

СБОРКА МУСОРА. Одним из важных механизмов объектноориентированных языков является автоматическое освобождение объектов (deallocation). Деятельность по автоматическому освобождению неиспользуемых и ставших ненужными объектов и по их утилизации называется СБОРКОЙ МУСОРА, а программы, осуществляющие эту деятельность, называют СБОРЩИКАМИ МУСОРА. Для сборки мусора традиционно используется метод удаления меток. В этом методе ничего не делается до тех пор, пока имеется свободная память. Когда доступной памяти не остается, производится расстановка меток у используемых объектов (на которые имеются указатели от других используемых объектов). Затем вся область памяти очищается, и все объекты, не имеющие таких меток, собираются в один список. Этот метод характерен высокой эффективностью, однако как только начинается сборка мусора, все прочие вычисления должны прекращаться. Поэтому он малопригоден для диалоговых систем и систем реального времени. При использовании его в системах с виртуальной памятью, со страничной организацией памяти и т.д. значительно снижается эффективность их работы в связи с большим количеством обращений к диску. Существует другой метод, ориентированный на работу в реальном времени, а именно метод подсчета ссылок. При использовании этого метода для каждого объекта заводится свой собственный счетчик ссылок, в котором хранятся указатели на этот объект. При значении этого счетчика, равном нулю, ссылки со стороны других объектов на этот объект отсутствуют, и он становится мусором. При реальных вычислениях память, занимаемая объектом, утилизуется в тот момент, когда счетчик ссылок меняет свое значение с 1 на 0. Благодаря этому процесс освобождения памяти и ее утилизации равномерно распределен по времени течения вычислительного процесса, и время реакции при вычислениях в реальном времени снижается.

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

В системе Смолток-80 важное значение придается времени реакции при работе в реальном масштабе времени, и поэтому был выбран метод сборки мусора путем подсчета ссылок, однако при этом общая эффективность системы все жезначительно снизилась. Одним из важных предметов исследования является вопрос о том, как повысить эффективность системы при применении метода подсчета ссылок.
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Техника в руках дикаря Empty Re: Техника в руках дикаря

Сообщение автор Gudleifr Пн Дек 05, 2022 12:17 am

УПРАВЛЕНИЕ СВОБОДНОЙ ПАМЯТЬЮ. Поскольку данный алгоритм сборки мусора освобождает области памяти в произвольные моменты времени, свободные места в таблице указателей и в информационной области появляются в произвольных местах. Высокоэффективное выделение свободной памяти для вновь вводимых объектов требует тщательной проработки методов управления этими областями.

Трудной проблемой в управлении памятью в информационной области является то, что объекты имеют различные размеры. Поскольку свободная память сильно фрагментирована, в ней отсутствуют большие цельные области. Одним из методов управления такой памятью является объединение ее в линейный список. При запросе на память для объекта какой-либо величины производится поиск в этом линейном списке до тех пор, пока не встретится область свободной памяти больше требуемой. Такую дисциплину распределения памяти называют МЕТОДОМ ПЕРВОГО ПОДХОДЯЩЕГО (first-fit). В наихудшем случае этот метод требует времени прямо пропорционального количеству свободных областей памяти. В языке Лисп управление свободной памятью производится аналогичным образом, однако в нем размер ячейки CONS, являющейся единицей памяти, фиксирован, и такой проблемы, как в языке Смолток, нет.

Другой метод состоит в том, что области свободной памяти ранжированы по величине и образуют двоичное дерево. В том случае, когда требуется область памяти некоторой величины, время поиска может оказаться пропорциональным величине logN, где N - количество свободных областей памяти. Эту дисциплину называют МЕТОДОМ НАИЛУЧШЕГО ПОДХОДЯЩЕГО (best-fit).

Однако на практике очень часто создаются объекты малого размера. Для их ускоренного создания применяется специальный метод виртуальной машины Смолток-80. При этом методе прежде всего создается таблица из 20 слов, называемая ЗАГОЛОВКОМ СВОБОДНЫХ ОБЛАСТЕЙ. Первые 19 слов включают в себя начало списков свободных областей памяти размером 2-20 слов. Последнее слово содержит начало списка всех остальных свободных областей памяти (рис.4.8 ).

Техника в руках дикаря Jap16210
Рис.4.8. Заголовок свободных областей памяти в виде массива из 20 элементов. Массив содержит начала списков, свободных областей памяти размером 2-20, а также начало списка свободных областей всех остальных размеров.

Например, если необходимо создать объект размером 7 слов, то читается шестой элемент таблицы заголовков свободных областей, и если в нем содержится указатель на информационную область, то берется указанный элемент. При создании объектов малых размеров поиск по таблице свободных областей производится за одно обращение. Если в таблице не зарегистрировано ни одной области памяти данного размера, то читается 20-й элемент и берется область произвольного размера, от которой отделяется область в семь слов. Оставшаяся область памяти в соответствии с ее размерами регистрируется под соответствующим заголовком таблицы.

Если такое дробление будет продолжаться долго, то весь универсум знаний системы раздробится на мелкие кусочки. Такое состояние называют ФРАГМЕНТАЦИЕЙ (fragmentation). При этом оказывается невозможным создание крупных объектов.

В этом случае все множество раздробленных областей свободной памяти объединяют в одну большую область свободной памяти. Этот процесс называют УПЛОТНЕНИЕМ (compaction). При выполнении уплотнения все объекты, находящиеся в информационной области, необходимо переписать на новые места независимо от того, используются они в данный момент времени или нет. В связи с этим должны быть изменены все указатели используемых объектов, что в общем случае приводит к разработке весьма сложных алгоритмов.

Однако в системе Смолток-80 уплотнение выполняется просто, с использованием таблицы объектов. Указатели объектов (Оор) не связаны с координатами объектов в информационной области, и поэтому нет необходимости в их переписывании. Можно обойтись лишь переписыванием смещений в таблице объектов, а поскольку ссылки на перемещаемые в информационной области объекты идут только из одного места, переписывание достаточно выполнить только в одном месте.

4.2.2. КЛАССЫ
В системе Смолток-80 классы также являются объектами, и память для них организована так же, как для прочих объектов.

Информация, необходимая для объекта, называемого КЛАССОМ, находится в его суперклассе, словаре сообщений и в экземплярах. При посылке сообщения экземпляру класса необходим поиск информации, определяющей метод, требуемый сообщением, и эта информация содержится в словаре сообщений. Информация, необходимая для создания экземпляра, содержится в описании экземпляра. Структура класса и словаря сообщений показана на рис.4.9.

Техника в руках дикаря Jap16410
Рис.4.9. Структура класса и словаря сообщений. Информация, необходимая интерпретатору, содержится в суперклассе, словаре сообщений и в спецификации экземпляров.

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

Спецификация экземпляров используется в случае создания экземпляра по сообщению new или new:size. В нее входят следующие сведения четырех видов.
1. Содержат ли сегменты, отведенные для экземпляра, указатели объектов или же они содержат целые числа.
2. Единицы, адресации в сегментах экземпляров (слова или байты).
3. Имеется ли перед фиксированными сегментами экземпляра сегмент, адресуемый указателем.
4. Величина фиксированных сегментов экземпляра.

Структура спецификации экземпляра представлена на рис.4.10.

Техника в руках дикаря Jap16411
Рис. 4.10. Структура спецификатора экземпляра.

4.2.3. МЕТОДЫ
В системе Смолток-80 объектный код, сгенерированный компилятором, также хранится в информационной области в виде объекта. Такой объект представляет собой экземпляр класса CompiledMethod (откомпилированный метод). Таким образом, объектный код, хранящийся в виде объекта, также подвергается процедуре сборки мусора и уплотнения. При внесении изменений в программу и ее перетрансляции старый объектный код становится ненужным и является объектом процедуры сборки мусора. Преимущество такого хранения состоит в том, что не требуется написание специальной системы управления программами.

Структура экземпляра класса CompiledMethod (откомпилированный метод) показана на рис.4.11. Заголовок метода представляет собой указатель объекта, являющийся экземпляром класса Smalllnteger (малое целое число).

Техника в руках дикаря Jap16510
Рис.4.11. Структура экземпляра класса Compiled Method (откомпилированный метод). Программа на языке Смолток-80 представляет собой объект.

Literal frame (область литералов) содержит указатели объектов: в нее входят указатели объектов, недоступные непосредственно из байт-программы. Например, в область литералов входят селекторы сообщений, и при выполнении программы, указанной в заявке, селекторы сообщения выбираются с использованием области литералов. Область команд представляет собой массив с побайтовой адресацией. В ней содержится байт-программа.

В method header (заголовке метода) содержится информация, необходимая при создании контекста метода. Структура заголовка метода показана на рис.4.12.

Техника в руках дикаря Jap16610
Рис.4.12. Структура заголовка метода. Он представляет собой указатель объекта. Крайний правый разряд в нем равен единице. Остальные сегменты содержат информацию, необходимую для создания контекста метода.

Заголовок метода содержит 4 сегмента: "флажки", "количество временных переменных", "размер контекста", "размер области литералов".

Сегмент "флажки" указывает на тип метода и интерпретируется следующим образом:
Значение 0-4: метод не является примитивом и имеет 0-4 параметров; значение 5: метод является примитивом без параметров и в качестве результата возвращает self (получатель); значение 6: метод является примитивом без параметров, возвращает в качестве значения переменную экземпляра. В этом случае требуется информация о том, по какому адресу оно возвращается, для этого используется сегмент "число временных переменных"; значение 7: в области литералов находится расширение заголовка (второе слово от конца области литералов), оно содержит количество параметров и указатель примитива.

Структура слова расширения заголовка показана на рис.4.13.

Техника в руках дикаря Jap16611
Рис.4.13. Структура слова расширения заголовка.

Сегмент "величина контекста" в заголовке метода состоит из одного разряда. Он указывает ту величину, которая должна быть при создании контекста метода. Малые контексты представляют собой объекты размером в 20 слов, большие контексты - объекты размером в 40 слов.

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

4.3. СИСТЕМА КОМАНД
В разд.4.2.3 было показано, что программа, написанная на языке Смолток-80, после компиляции хранится как экземпляр класса CompiledMethod. В данном разделе рассматриваются форматы и семантика системы команд.

4.3.1. БАЙТ-КОД
Идея реализации персонального компьютера как специализированной машины с аппаратно реализованным языком высокого уровня впервые была воплощена Л.Петером Дойчем в Лисп-машине. В этом проекте используется система команд, в которой минимальной единицей является один байт, и поэтому ее называют байт-кодом. В дальнейшем эта система команд применялась в таких машинах с микропрограммным управлением, как Альто фирмы "Ксерокс", Дольфин (Dolphin), Дорадо (Dorado), а также в машине Perq фирмы "Три Риверс" (Three Rivers). В качестве исходных языков используются языки Лисп, Смолток, Паскаль, Меза и др.

В байт-коде имеется тенденция реализовать все команды по возможности в одном байте (при высокой частоте выполнения команд), что позволяет создавать компактный объектный код. Кроме того, если не разбивать содержимое восьми разрядов байта на сегменты с их отдельным декодированием, то один байт позволяет организовать передачу управления по 256 различным адресам с выполнением по каждому из этих адресов своих видов деятельности.

4.3.2. ФОРМАТЫ КОМАНД
Система команд или байт-код языка Смолток-80 показана в приведенной ниже табл.4.1. В ней в графе "Битовый формат" указан формат, состоящий из восьми символов, в число которых входят нули, единицы или малые латинские буквы. При этом латинские буквы означают, что на их местах должны стоять нули или единицы. В графе "Семантика" приняты следующие обозначения. Например, если в ней имеются символы: #iiii, то это - указатель значения последовательности четырех двоичных разрядов, указанных в формате команды четырьмя символами iiii. Далее, если в графе "Семантика" имеется описание вида: (a, b, c, d) [ii], то такая запись обозначает, что из четырех элементов (a, b, c, d) необходимо выбрать элемент с номером [ii]. Если ii равно 10 (двоичное), то значением этого выражения является c.

Таблица 4.1. Система команд (байт-код) языка Смолток-80
Значение. Битовый формат. Семантика
0-15. 0000iiii. Помещение в стек переменной экземпляра-получателя с номером #iiii
16-31. 0001iiii. Помещение в стек временной переменной с номером #iiii
32-63. 001iiiii. Помещение в стек литерала с номером #iiiii
64-95. 010iiiii. Помещение в стек глобальной переменной, указываемой литералом с номером #iiiii
96-103. 01100iii. Выталкивание из стека и помещение вытолкнутого значения в переменную экземпляра-получателя с номером #iii
104-111. 01101iii. Выталкивание из стека н помещение вытолкнутого значения во временную переменную с номером #iii
112-119. 01110iii. Помещение в стек специального значения (получатель, true, false, nil, -1, 0, 1, 2) [iii]
120-123. 011110ii. Возврат из метода с возвращением специального значения (получатель, true, false, nil) [ii]
124-125. 0111110i. Возвращение верхушки стека в качестве значения (метод, блок) [i]
126-127. . Не используется
128. 10000000 jjkkkkkk. Помещение в стек (переменной экземпляра получателя, временной переменной, литерала, глобальной переменной, указываемой литералом) [jj] с номером #kkkkkk
129. 10000001 jjkkkkkk. Помещение верхушки стека в (переменную экземпляра-получателя, временную переменную, литерал, глобальную переменную, указываемую литералом) [jj] с номером #kkkkkk
130. 10000010 jjkkkkkk. Выталкивание из стека верхушки н помещение этого значения в (переменную экземпляра-получателя, временную переменную, литерал, глобальную переменную, указываемую литералом) [jj] с
номером #kkkkkk
131. 10000011 jjjkkkkk. Вызов метода с jjj параметрами с использованием селектора сообщения, находящегося в области литералов под номером #kkkkk
132. 10000100 jjjjjjjj kkkkkkkk. Вызов метода с jjjjjjjj параметрами с использованием селектора сообщения, находящегося в области литералов под номером #kkkkkkkk
133. 10000101 jjjkkkkk. Вызов метода с jjj параметрами с использованием селектора сообщения, находящегося в области литералов под номером #kkkkk
134. 10000110 jjjjjjjj kkkkkkkk. Вызов метода с jjjjjjjj параметрами с использованием селектора сообщений, находящегося в области литералов под номером #kkkkkkkk
135. 10000111. Выталкивание из стека
136. 10001000. Копирование верхушки стека
137. 10001001. Помещение в стек активного контекста
138-143. . Не используются
144-151. 10010iii. Переход по адресу iii+1
152-159. 10011iii. Выталкивание нз стека, переход к iii+1 при значении false вытолкнутой верхушки
160-167. 10100iii jjjjjjjj. Переход по адресу (iii-4)*256+jjjjjjjj
168-171. 101010ii jjjjjjjj. Выталкивание из стека, переход на ii*256+jjjjjjjj при значении true вытолкнутой верхушки
172-175. 101011ii jjjjjjjj. Выталкивание из стека, переход на ii*256+jjjjjjjj при значении false вытолкнутой верхушки
176-191. 1011iiii. Посылка заявки на вычисления #iiii
192-207. 1100iiii. Посылка специальной заявки #iiii
208-223. 1101iiii. Вызов метода без параметров с использованием селектора сообщений, находящегося в области литералов под номером #iiii
224-239. 1110iiii. Вызов метода с одним параметром с использованием селектора сообщения, находящегося в области литералов под номером #iiii
240-255. 1111iiii. Вызов метода с двумя параметрами с использованием селектора сообщений, находящегося в
области литералов под номером #iiii

4.3.3. СЕМАНТИКА КОМАНД
Рассмотрим на примере виртуальной машины семантику команд байт-кода, описанного в предыдущем разделе.

1) Проталкивание в стек переменных экземпляра-получателя. Переменные экземпляра фиксируются для каждого экземпляра, и в каждом объекте для них отводится область памяти. Данная команда проталкивает в стек считанные переменные экземпляра, в частности получателя. Ее работа показана на рис. 4.14. Команда реализуется байт-кодами 0-15, 128.

Техника в руках дикаря Jap16910
Рис.4.14. Помещение в стек переменной экземпляра с номером i. Толстая стрелка от получателя к объекту - еще один этап косвенного доступа, обусловленного наличием указателей объектов; штрихованная стрелка - направление копирования данных; тонкая стрелка - значение указателя (задается до начала выполнения команды); пунктирная стрелка - значение указателя после выполнения команды.

2) Проталкивание в стек временной переменной. Временные переменные представляют собой переменные, создаваемые в момент вызова метода. Область памяти для них выделяется в контексте. Работа данной группы команд, реализуемой байт-кодами 16-31, 128, показана на рис.4.15.

Техника в руках дикаря Jap17010
Рнс.4.15. Помещение в стек временной переменной с номером i. Из рисунка видно, что активный контекст и контекст вызывающей программы различны, когда активный контекст является экземпляром контекста блока, и совпадают, когда активный контекст является экземпляром контекста метода.

3) Проталкивание символов в стек. Символ - это селектор сообщения или константа с объектным указателем. По этой команде в стек проталкивается указатель, имеющийся в части символа. Действие этой команды показано на рис.4.16. Она реализуется байт-кодами 32-63, 128.

Техника в руках дикаря Jap17110
Рис.4.16. Помещение в стек символа с номером i.

4) Проталкивание в стек глобальной переменной, указываемой литералом. Область, в которую помещаются глобальные переменные, адресуется из области литералов. В данной команде вначале определяется указатель области литералов, а затем производится помещение в стек значения глобальной переменной, размещенного в двух словах объекта, называемого связыванием, на который указывает этот указатель. Работа этой группы команд, реализуемой байт-кодами 64-95, 128, показана на рис.4.17.

Техника в руках дикаря Jap17210
Рис.4.17. Помещение в стек глобальной переменной, адресуемой i-м литералом.

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

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

7) Проталкивание в стек специального значения. Команда помещает в стек следующие значения: значение получателя, true, false, nil, -1, 0, 1, 2. Реализуется байт-кодами 112-119.

8 ) Возврат из метода с возвращением специального значения. Данная группа команд выполняет возврат из метода с возвращением одного из специальных значений: получатель, true, false, nil. Вначале контекст, адресуемый из сегмента отправителя возвращаемого контекста, делается очередным активным контекстом, и в него помещается специальное значение. Функция реализуется байт-кодами 120-123.

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

10) Возврат верхушки стека в качестве значения из блока. Верхушка стека контекста, исполняемого в данный момент, принимается за значение, возвращаемое из блока. Эта команда выполняется при выполнении оператора, для которого невозможен возврат после выполнения последнего оператора блока. Возврат происходит в то место, откуда был активизирован блок. Эта функция выполняется командой 125 байт-кода.

11) Вызов метода с использованием селектора СООБЩЕНИЯ, находящегося в области литералов. Команда производит поиск
селектора сообщения, начиная со словаря для класса получателя. Если поиск успешен, то производится вызов соответствующего метода. (На самом деле предусмотрен ускоренный метод поиска с использованием буфера методов.) Данная функция реализуется командами байт-кода: 131, 132, 134, 208-255.

12) Вызов метода из суперкласса с использованием селектора сообщения, находящегося в области литералов. Команда начинает поиск селектора сообщения суперкласса класса, в котором определен выполняемый в данный момент метод. Данная функция реализована байт-кодом 133.

13) Выталкивание из стека и копирование верхушки стека. Команда выталкивания из стека делает его на один элемент
меньше. Операция копирования состоит в помещении в стек значения, равного верхушке стека. Эти функции реализуются кодами 135, 136.

14) Помещение в стек активного контекста. Команда помещает в поля текущего контекста значения регистров и затем
помещает в стек указатель этого контекста. Команда реализуется байт-кодом 137.

15) Команды перехода и условного перехода. Реализуются байт-кодами 144-175.

16) Посылка заявки на вычисления. Команда реализует арифметические операции "+" и "-". Если получатель не является целым числом, то выполняются действия, аналогичные обычной посылке заявки. Реализуется байт-кодами 176-191.

17) Посылка специальной заявки. В языке Смолток могут использоваться сообщения, реализованные как примитивы на языках, внешних по отношению к языку Смолток. Среди них. есть такие списочные операторы, как at:, at: put: и т.д. Данная, функция реализуется байт-кодами 192-207.

КОНЕЦ ЛИРИЧЕСКОГО ОТСТУПЛЕНИЯ
Gudleifr
Gudleifr
Admin

Сообщения : 3219
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Вернуться к началу

- Похожие темы

 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения