Houri,Avshalom,Shapiro,Ehud Y. Method for concurrent logic program (Перевод)

Перевод статьи: Method for concurrent logic program

Авторы: Houri, Avshalom, Shapiro, Ehud Y.

Оригинал статьи: http://www.patentstorm.us/patents/4775934/fulltext.html

Введение.

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

Требования

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

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

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

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

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

2. Требование 1 в идентификации того же самого процесса предотвращает сбрасывание адреса к заказанной информации относительно процесса.

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

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

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

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

4. Требования 3 предотвращает повторную идентификацию того же самого процесса, сбрасывая описанный косвенный адрес.

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

- убирание из очереди процесса;

- попытка уменьшить очередь, используя выражения;

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

- обеспечение в каждом отчете доступа к косвенному адресу к информации относительно процесса;

6. Требования 5 предотвращает повторную идентификацию того же самого процесса, сбрасывая косвенный адрес.

Описание

Данный подход позволяет управлять логической программой и, в частности управлять приостановленными процессами в логической программе.

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

A если B1 и B2 и... и BN

Это определение требует, чтобы аксиомы состояли только из утверждений (то есть, A), отрицания (то есть, не A) и значения (то есть, если B1 и B2 и... и BN), первая часть выражения (то есть, A) будет упоминаться как заголовок или следствие выражения и остатка (то есть, B1... BN) как тело или хвост или условие или антецедент. Мы будем именовать утверждения и отрицания как факты и к значениям как правила, и любой из них может упоминаться как выражение или аксиома.

Логические языки программирования этого типа включают последовательный Пролог, PARLOG, Осторожные Формулы Хорна, и Параллельный Пролог. Обширный материал был издан на логическом программировании и на этих языках программирования. См., например, R. A. Kowalski, Логика для Решения задач (Elsevier Северная Голландия, 1979); D. H. D. Уоррен, "Абстрактный Набор команд Пролога", Техническое примечание 309 (SRI Международный 1983); C. J. Hogger, Введение в Программирование Логики (Академическое издание 1984); W. F. Clocksin и C. S. Mellish, Программирующий в Прологе (Springer-Verlag, 2-ой редактор 1984); T. Conlon, Изучение МикроПролога (Addison-Уэсли 1985); K. Ueda, "Осторожные Формулы Хорна", Технический КОНЦЕРН Отчета ICOT 103 (1985); E. Shapiro "Пролог Concurent: Доклад о достигнутых результатах" Технический Отчет CS86-10, Институт Weizmann, Израиль (1985); U. Барон, "Распределенная Реализация Плоского Параллельного Пролога," Тезис, департамент. из Прикладной Математики, Института Weizmann, Израиль (1986); L. Стерлинг и E. Shapiro, Искусство Пролога: Расширенные Методики Программирования, (Массачуссетский технологический институт 1986).

Ковальски понял, что Формулы Хорна могли читаться и декларативно, говоря, что A - истина если B1 и B2 и... и BN истина, и процедурно, говоря, что, чтобы доказать цель (или выполнить процедуру A или решить проблему A) можно доказать подцели (или выполнить подпрограммы или решить подпроблемы), B1 и B2 и... и BN. Ковальски, Логика для Решения задач (Эльсивер Северная Голландия 1979).

Например, следующая программа идентифицирует объекты X, которые появляются в обоих списках Ll и L2 (то есть, перечислите пересечение):

пересекитесь (X, Ll, L2): - участник (X, Ll) и участник (X, L2). участник (X, [X|Xs]).

участник (X, [Y|Ys]): - участник (X, Ys).

Читайте декларативно, первые чтения аксиомы: X находится в пересечении списка Ll и L2, если X член списка Ll, и X член списка L2. Читайте процедурно, первые чтения аксиомы: чтобы найти X в пересечении списков Ll и L2, найдите X, который является членом Ll и также членом L2. Термин [X|Xs] является стандартным примечанием списка, обозначающим список, первый элемент которого X и чьи остающиеся элементы - Xs. Аксиомы, определяющие "участника", читают: X член списка, первый элемент которого X, и X член списка [Y|Ys], если X член Ys. Определение членства в списке - рекурсивный объясненный процесс, например, в Главе 5 Изучения МикроПролога. От способности проникновения в суть Ковальски была получена вычислительная модель для логических программ. Эта модель основана на следующих принципах:

Логическая программа - конечное множество универсально определенных количественно аксиом.

Выполнение - доказательство экзистенциального оператора от программы.

Основная процедура доказательства недетерминирована.

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

Например, в программе пересечения списка, положить L1 = [2,4,6,8,10,12] и L2 = [3,6,9,12,15]. Если мы тогда стремимся доказать цель: действительно там существует X таким образом что: пересекитесь (X, [2,4,6,8,10,12], [3,6,9,12,15]), логическая программа будет идентифицировать каждого члена списка L1 и стремиться установить, что такой участник идентичен члену списка L2. Выводы для этой цели будут X=6 и X=12, который основные шаги вычисления логической процедуры доказательства программы (1) объединение цели с заголовком выражения и (2) его сокращение к (или замена) подцели, определенные в теле выражения. Процедура объединения - специализированная форма Робинсона, s принцип разрешающей способности. Робинсон, "Машинно-ориентированная Логика, Основанная на Принципе Разрешающей способности", Журнал ACM. издание 12, стр 23-41 (1965). Объединение двух списков вовлекает значения обнаружения, которыми можно заменить для переменных в списках, чтобы сделать два списка идентичными. См., например, Хоггер, Введение в Логическое Программирование, с.217 (Академическое издание 1984). Обычная логическая задача программы состоит в том, чтобы удовлетворить конъюнкцию нерешенных целей, осуществляя поиск в базе данных, чтобы определить местонахождение фактов, которые объединят с целью. Различные логические языки программирования приближают предшествующую модель и отличаются главным образом таким образом, в котором создано доказательство цели.

Аксиомы логического языка программирования встроены из выражений. Выражение - или константа, переменная или структура. Константы называют определенные объекты или отношения. Функция переменных как местоимения, в которых они представляют объект, который нельзя назвать. Структура - единственный объект, который состоит из коллекции других объектов. Это написано в форме: f (a, b, c), где f называют функтором или предикатом и выражениями в круглых скобках, названы компонентами или параметрами. Факт написан как структура, определяющая отношения между двумя или более объектами. В такой структуре отношения написаны как функтор или предикат, и объекты написаны как компоненты или параметры. Таким образом факту "Джон нравится Мэри", может быть написан как: нравится (Джон, Мэри). У типичного запроса к базе данных будет форма:? - f (a, X), где X переменная, представляющая искавший информация. Когда не известно, что замещает эта переменная, переменная унифицирована. Когда переменная действительно замещает объект, она унифицирована.

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

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

Например, база данных может включить факты:

любит (Джон, Мэри)

любит (Роберт, Сьюзен)

любит (Майкл, Мэри)

любит (Пол, wendy)

любит (Джон, wendy)

любит (Майкл, Сьюзен)

любит (Роберт, wendy)

любит (Роберт, Мэри)

Если запрос:

? - любит (X, Мэри) и любит (X, wendy),

программа перерывает базу данных, чтобы найти первого человека, которому нравится Мэри. Первый факт указывает, что Джону нравится Мэри, и переменная X проиллюстрирована Джону. Чтобы удовлетворить вторую подцель, программа тогда выясняет, если Джону нравится Wendy. Это определяет местонахождение этого факта в базе данных и сообщает что X=john в удовлетворении запроса. Программа тогда сбрасывает переменную и ищет кого - то еще, кому нравятся Мэри и Wendy. Это определяет местонахождение факта, что Майклу нравится Мэри, и переменная X инициализирована Майклом. Однако, дальнейший поиск базы данных не определяет местонахождение факта, что Майклу нравится Wendy. Соответственно, программа обратный проход к факту, что Майкл любит Мэри, разынициализировав переменную и возобновляет поиск других фактов, касающихся того, кому нравится Мэри. Затем находит факт, что Роберт любит Мэри и инициализирует переменную X Робертом. Затем определяет местонахождение факта, что Роберт любит Wendy и сообщает что X=robert в удовлетворении запроса. В этом пункте сделан поиск.

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

Большая база данных и сложная конъюнкция целей наложат значительное бремя поиска на любой доступный серийный компьютер с архитектурой Фон-Неймана. Поэтому желательно выполнить такой поиск базы данных параллельно.

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

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

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

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

У осторожного выражения есть форма:

A:-G1, G2... Gm |B1, B2..., Bn; m, n .. 0

Передающийся оператор, |, отделяет правую сторону правила в защиту, G1, G2... Gm, и тело, B1, B2..., Bn. Декларативно, это читается точно так же как конъюнкция: A - истина, если Г и B's - истина. Процедурно это сокращение процесса A1, используя такие выражения приостанавливает до A1, является унифицируемыми с A. Начиная с доходов сокращения параллельно, это может читаться процедурно как: чтобы решить A, сначала решите защиту, Gi, параллельно и, в случае успеха, решите цели в теле, Bj, параллельно. Таким образом, чтобы удовлетворить цель A, защита 11 выражения в процедуре для, чьи заголовки объединяют с A, пробуют параллельно; и когда защита преуспевает, эта защита передает. Цели в теле выражения тогда выполняются параллельно.

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

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

РЕЗЮМЕ

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

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

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

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

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