Cтраница 3
Образцы являются важным типом данных в Сноболе 4 благодаря той ключевой роли, которую играет операция сопоставления с образцом. Любая операция сопоставления с образцом управляется структурой данных типа образец. Программа, реализующая сопоставление, декодирует и интерпретирует образец, одновременно выполняя поиск соответствующей цепочки литер, указанной образцом. Детально образцы рассматриваются в следующем разделе, где мы разбираем операцию сопоставления саму по себе. Наличие образцов, как явных типов структур данных, означает, что образцы могут быть значениями переменных, элементов массивов и элементов таблиц. Во время выполнения образец представляется во внутренней форме, удобной для эффективной его интепретации программой сопоставления; обычно такой формой является связанное множество областей памяти, образующее древовидную структуру, которая отражает естественную структуру образца как набора альтернатив и конкатенации подобразцов. [31]
При представлении сред типа 3 избежать интерпретации невозможно, т.е. при использовании некоторого общего правила в процессе консультации необходимо выполнять операции сопоставления, в результате которых анализируются все экземпляры упоминаемого в правиле класса объекта. [32]
Конечно, в языке есть и простейшие арифметические операции и операции сравнения, подобные аналогичным операциям процедурных языков, но операция сопоставления несет гораздо большую смысловую нагрузку и является одним из основных понятий ПРОЛОГа. [33]
Запоминание знаний о концептуальном объекте, имеющем классификационную иерархическую структуру, легко поясняется одним ФР, однако, как было сказано выше, если операция сопоставления окончилась неуспехом, возникает необходимость поиска ФР, подобного предыдущему. Такой поиск, осуществляемый с использованием указателей различия, возможен благодаря сети ФР, которые описывают объекты, имеющие небольшие различия с данными указателями, а также благодаря образованию сети подобных ФР. [34]
С образцами в Сноболе 4 нельзя манипулировать, как с обычными структурами данных; они могут только создаваться, включаться как часть в состав более крупных образцов и использоваться в операции сопоставления с образцом. Формат в том виде, в каком он используется в операциях ввода-вывода в Фортране и в других языках, - это аналогичная образцу структура данных, применяемая только для преобразований между внешним представлением данных в файлах ввода-вывода в виде цепочек литер и их внутренним представлением в памяти. Формат, переданный операции ввода-вывода, интерпретируется ею как руководство по выполнению преобразований между внешним и внутренним представлением чисел и других данных. [35]
Следует, однако, отметить, что для сравнений в первоначальной программе можно обойтись лишь дешевыми проверками длин цепочек, в то время как при поиске в упорядоченном словаре все сравнения требуют дорогих операций сопоставления цепочек. Чтобы повысить эффективность программы, надо бы, конечно, что-то предпринять. Но с другой стороны, проведенная переделка программы иллюстрирует важный принцип отладки. Если структура программы заменяется на функционально эквивалентную, то результаты при тех же исходных данных должны оставаться неизменными. На фактический процесс сжатия организация словаря влиять не должна, только параметры сжатия должны сказываться на содержании словаря. Следовательно, убеждаясь, что результаты работы программы с простым линейным поиском и с поиском до первого совпадения совершенно одинаковы ( за исключением временной статистики), мы проверяем правильность изменений в подпрограммах, оперирующих со словарем. Это является также контролем на отсутствие ошибок в других частях программы: если бы в какой-нибудь другой подпрограмме был ляпсус, то он вполне мог бы проявиться в программах работы со словарем. А если уж результаты остаются постоянными после того, как подключается правильная программа поиска до первого совпадения, не исключено ( но вовсе и не обязательно), что скрытых ошибок, влияющих на словарь, нет. [36]
Операция сопоставления, или отождествления, осуществляется следующим образом [77, 78]: число сопоставляется только с равным ему числом; атом сопоставляется только с равным ему атомом; переменная сопоставляется с чем угодно, при этом она получает в качестве значения то, с чем она сопоставляется; структура со поставляется с другой структурой, если они имеют одинаковые имена и количества аргументов, при условии, что все их элементы попарно сопоставимы. Операция сопоставления может закончиться неудачно. В этом случае будем говорить, что ее операнды несопоставимы. [37]
Обсуждение некоторых особенностей сопоставления с образцом в Сноболе 4 покажет, как определяются образцы. Операция сопоставления в Сноболе 4 всегда применяется к структуре данных, являющейся цепочкой литер. Она пытается найти в этой цепочке одну подцепочку, свойства которой определяются образцом. [38]
Для СС, представляющей систему знаний, задается набор допустимых преобразований, переводящих исходную СС ( или ее фрагменты) в логически эквивалентную ей. Операция сопоставления выявляет все фрагменты исходной или эквивалентных ей сетей, изоморфные сети запроса. Набор допустимых преобразований для семантических сетей дополняет сети новыми связями, полученными из транзитивности фундаментальных отношений и наследования свойств, но не ограничивается этим. В зависимости от специфики решаемых задач и особенностей того или иного конкретного средства набор эквивалентных преобразований может существенно расширяться. Именно поэтому базовыми для СС называют не операции сопоставления с образцом, а гораздо более примитивные операции перехода по СС. [39]
Успешно закончившаяся операция сопоставления с образцом определяет подцепочку анализируемой цепочки, которая соответствует целиком использованному образцу. Часто бывает нужно определять подподцепочки этой подцепочки, соответствующие подэлементам образца. [40]
Операцию сопоставления вектору а вектора Ъ иногда называют умножением справа тензора на вектор. [41]
Сама операция сопоставления вектору его проекции является отображением, называемым проектированием. [42]
Операции в языках программирования вероятно лучше всего изучать, анализируя конкретные языки программирования. Джимпел [1973] рассматривает операцию сопоставления с образцом более подробно. Конструкция известного под названием SLIP расширения Фортрана ( Вейзенбаум [1963]), предназначенного для обработки списков, и язык 1PL - V ( Ньюэл [1964]) иллюстрируют ранние разработки мощных наборов операций для обработки списков. [43]
Наиболее общий подход к ускорению операции сопоставления состоит в комбинировании двух процессов: 1) процесса индексирования и 2) процесса интерпретации ( выполнения) условий правил. Процесс индексирования выполняет функции, аналогичные функциям выборки. Выше ( см. § 6.3.) было отмечено, что в простых областях индексирование может заменять операцию выборки. Простейшая форма индексирования состоит в том, что интерпретатор извлекает одну или более характеристик ( например, свойств) из каждого элемента рабочей памяти и использует их для того, чтобы выделить подмножество правил, условия которых могут быть удовлетворены. Затем интерпретатор исследует условия этих вьщеленных правил и определяет те из них, которые удовлетворяются. В более эффективных формах индексирования с каждым образцом в правиле связывается счетчик. В начале работы значения всех счетчиков равны нулю. При введении некоторого элемента в рабочую память функция индексирования определяет, какие образцы сопоставляются с этим элементом, и добавляет к их счетчикам по единице. [44]
Для обнаружения контура и проверки отдельных условий необходимо располагать лишь байтом bdr. Следовательно, каждый процессор может выполнять ряд операций сопоставления цепочек символов в асинхронном режиме, а затем должен ждать, пока все процессоры не завершат этап обработки, прежде чем продолжать исполнение алгоритма. [45]