Cтраница 1
Выполнение унификации и извлечение ответа вручную требуют некоторой осторожности. В частности, процесс переименования переменных в родительских предложениях ( цель которого - гарантировать, чтобы во время применения резолюции родительские предложения не имели общих переменных) нужно выполнять следующим образом. [1]
Разработчик реализации может дополнительно сократить расходы, связанные с выполнением унификации в период исполнения, надлежащим образом воспользовавшись индексированием процедур, поскольку построение индексных таблиц в период компиляции является ( неявным) частичным согласованием заголовка каждой процедуры с ожидаемым классом вызовов. Попытка унифицировать во время исполнения формальные параметры процедуры с известными фактическими параметрами начинается тогда с информации о том, что некоторое согласование уже было достигнуто благодаря выделению этой процедуры в качестве кандидата для вызова. [2]
Программист может до произвольных пределов устранять бесполезные или какие-то иные нежелательные попытки выполнения унификации путем использования оператора отсечения ( /), для реализации которого обычно требуется лишь простое обновление регистра БТВ и, быть может, нескольких ячеек ПТВ. Как правило, на операцию отсечения тратится гораздо меньше времени, чем экономится посредством устранения лишних неиспробованных кандидатов. Это справедливо, разумеется, при условии, что оператор отсечения используется в соответствии со здравым смыслом; при злоупотреблении им может произойти обратное. [3]
Удовлетворение условия восстановления ( а) зависит от соответствующих механизмов, реализуемых для выполнения унификации, и от распределения локальной и глобальной памяти. [4]
Рассмотрим теперь четыре случая, исчерпывающие все те ситуации, которые могут возникнуть непосредственно перед выполнением унификации. [5]
Допустим, что х - локальная переменная и ей еще не присвоено никакого значения; тогда полученное в результате выполнения унификации присваивание г: х ( заметим, что присваивание г: не годится) помещают в ячейку переменной г потенциально повисающий указатель на ячейку х в удаляемом фрейме. [6]
Эта оценка должна быть уравновешена тем наблюдением, что при исполнении многих программ порождаются структуры, которые в дальнейшем не участвуют ни в получении разыменованных выходных данных, ни в попытках выполнения унификации. Поэтому, выбирая между СС - и НСС-системами, следует рассмотреть вопрос о том, будет ли в предполагаемых исполнениях программ преобладать выборка структурированных данных или просто их построение. Вообще говоря, для последней категории исполнений больше подходят СС-системы, поскольку задача, состоящая в построении молекул, оказывается тривиальной ( решается очень быстро) по сравнению с задачами их разыменования или выборки в ходе выполнения унификации их глубоко расположенных компонент. [7]
Допустим, что х - глобальная переменная ( имеющая вхождения в структурированный терм); тогда, в силу соглашений относительно указателей между локальным и глобальным стеками, никакой указатель, помещаемый в ее ячейку в результате выполнения унификации, не может отсылать к удаляемому фрейму. [8]
Значительные возможности для повышения скорости исполнения логических программ заключены в реализации механизма унификации. Наиболее часто для выполнения унификации используются различные варианты алгоритма Робинсона. [9]
Из этого анализа вытекает, что для безопасного выполнения ОПВ следует устранить случаи ( 3) и ( 4), в каждом из которых переменная х является локальной. В этом случае всякий указатель на ячейку х, который в результате выполнения унификации мог бы быть присвоен ячейке г, никогда не будет повисшим, и, стало быть, ОПВ можно осуществлять, не причиняя ущерба. В противном случае, если х является локальной и имеет вхождения в заголовок процедуры Р1, то стандартное соглашение относительно унификации гарантирует, что при входе в Р1 переменной х сразу же будет присвоено какое-то значение, и поэтому случай ( 3) невозможен. [10]
Рассматриваемый метод именования может стать утомительным, когда мы имеем дело с очень сложными составными именами. Соответствующее ему имя сумма ( сумма ( А 1, А2), сумма ( В1, В2)) слишком громоздкое для написания, и, кроме того, его употребление могло бы привести к значительным затратам, связанным с хранением данных и выполнением унификации в период исполнения. В этом случае можно использовать другой возможный стиль программирования, при котором мы обходимся без структурированных имен и который делает программы более понятными. [11]
Допустим, что х - локальная переменная и присвоенное ей значение содержит указатель на удаляемый фрейм или какую-либо его ячейку. Им мог бы быть только указатель на ячейку некоторой другой переменной у из процедуры Р1 ( этот указатель не мог бы быть молекулой, поскольку ее указатель среды отсылал бы к глобальному фрейму); таким образом, если переменная у не является глобальной, то получаемое в результате выполнения унификации присваивание z: y помещает в ячейку переменной г потенциально повисающей указатель на ячейку у в удаляемом фрейме. [12]
Та неэффективность, которая еще остается, возникает главным образом из-за затрат, связанных с унификацией различных структурированных термов. Эти затраты находятся вне пределов контроля со стороны программиста; они будут определяться заложенным в интерпретаторе конкретным способом обработки термов. Разумеется, усилия, требуемые для выполнения унификации в ходе исполнения программы, могут быть в значительной степени уменьшены, если интерпретатор оказывается в состоянии проводить предварительный интеллектуальный анализ входной программы и, таким образом, выбирать способы эффективной реализации намерений программиста. Эта возможность, которая относится к общим вопросам оптимизации в период компиляции, представляется в особенности привлекательной тем, что она позволяет писать программы, основанные на термах относительно высокого уровня, зная при этом, что конкретная реализация программы будет организована так, чтобы избежать значительных расходов, связанных с доступом к данным и унификацией. Третья процедура палин была бы тогда эффективно скомпилирована в множество машинных операций, которые быстро переносили бы элемент из первого массива во второй. [13]
Название метода совместное использование структур отражает тот факт, например, что значения переменных х3 и х имеют общий входной скелет и. Очевидно, что наибольшую пользу он приносит в том случае, когда на допустимые в период исполнения объемы памяти накладываются существенные ограничения или же память слишком дорогостоящая. За получаемую экономию памяти возможно придется расплачиваться увеличением времени обработки, необходимого для выполнения унификации, поскольку интерпретатору с целью сравнения фактических и формальных параметров может потребоваться исследовать сколь угодно длинные цепочки молекул. Это наказание будет незначительным, если в ходе исполнения программы подобные унификации выполняются редко или если вычислительная машина, на которой осуществлена реализация, обеспечена высокоэффективными механизмами косвенной адресации. Первое из этих двух условий зависит от вида исполняемой программы. При исполнении некоторых программ могут строиться большие структурированные термы, и, тем не менее, на программу унификации не ложится почти никакой нагрузки, связанной с выборкой данных. В других же программах могут вообще не употребляться структурированные термы, а обрабатываться, быть может, данные, представленные в виде фактов. [14]
Эта оценка должна быть уравновешена тем наблюдением, что при исполнении многих программ порождаются структуры, которые в дальнейшем не участвуют ни в получении разыменованных выходных данных, ни в попытках выполнения унификации. Поэтому, выбирая между СС - и НСС-системами, следует рассмотреть вопрос о том, будет ли в предполагаемых исполнениях программ преобладать выборка структурированных данных или просто их построение. Вообще говоря, для последней категории исполнений больше подходят СС-системы, поскольку задача, состоящая в построении молекул, оказывается тривиальной ( решается очень быстро) по сравнению с задачами их разыменования или выборки в ходе выполнения унификации их глубоко расположенных компонент. [15]