Как Concurrent является Prolog?

Ответ 1

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

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

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

• все существующие решения для параллелизации имеют по меньшей мере некоторые издержки производительности для межпоточной связи.

• Пролог обычно используется для высокоуровневых, глубоко рекурсивных задач, таких как обход графика, доказательство теоремы и т.д. Параллелизация на современных машинах может (в идеале) добиться ускорения n для некоторой константы n но он не может превратить метод нежизнеспособного рекурсивного решения в жизнеспособный, поскольку для этого потребуется экспоненциальное ускорение. Напротив, числовые проблемы, которые обычно решаются программистами Fortran и C, обычно имеют высокую, но вполне конечную стоимость вычислений; это стоит усилий распараллеливания, чтобы превратить 10-часовую работу в 1-часовую работу. Напротив, включение программы, которая может выглядеть примерно на 6 движений вперед, в одну, которая может (в среднем) смотреть 6.5 ходов вперед, не является столь же убедительной.

Ответ 2

Являются ли современные компиляторы/интерпретаторы Prolog неотъемлемо * параллельными? Какие? По умолчанию используется concurrency?

Нет. Параллельное логическое программирование явилось основной целью компьютерной программы 5-го поколения в Японии в 1980-х годах; ожидалось, что варианты Prolog будут "легко" распараллеливаться на массивно параллельном оборудовании. Усилия в основном не удались, потому что автоматический concurrency просто нелегко. Сегодня компиляторы Prolog имеют тенденцию предлагать библиотеки потоков, в которых программа должна вручную контролировать количество concurrency.

Чтобы узнать, почему распараллеливание Prolog так же сложно, как и любой другой язык, рассмотрите две основные структуры управления, которые предлагает язык: соединение (AND, последовательное выполнение) и дизъюнкция (OR, выбор с обратным отсчетом). Скажем, у вас есть конструкция AND, такая как

p(X) :- q(X), r(X).

и вы хотите запускать q(X) и r(X) параллельно. Затем, что произойдет, если q частично объединяет X, скажем, привязывая его к f(Y). r должен знать об этом привязке, поэтому либо вы должны сообщить об этом, либо вам нужно дождаться завершения обоих конъюнктов; то вы можете потерять время, если один из них потерпит неудачу, если вы, опять же, не попросите их синхронизировать связь. Это дает накладные расходы, и это сложно сделать правильно. Теперь для OR:

p(X) :- q(X).
p(X) :- r(X).

Здесь есть конечное количество вариантов выбора (Prolog, конечно, допускает бесконечно много вариантов), поэтому вы хотите запустить оба из них параллельно. Но тогда, если удастся? Другая ветвь вычисления должна быть приостановлена ​​и ее состояние сохранено. Сколько из этих состояний вы собираетесь сэкономить сразу? Столько, сколько есть процессоров, кажется разумным, но тогда вам нужно позаботиться о том, чтобы не создавать вычисления, которые не вписываются в память. Это означает, что вам нужно угадать, насколько велико состояние вычисления, то, что пролог скрывает от вас, поскольку он абстрагируется от таких деталей реализации, как процессоры и память; это не C.

Другими словами, автоматическая распараллеливание жесткая. 5-й проект "Генерал-компьютер" обошел некоторые проблемы, разработав языки с фиксированным выбором, то есть диалоги Prolog без обратного отслеживания. При этом они радикально изменили язык. Следует отметить, что параллельный язык Erlang является ответвлением Prolog, и он тоже торгуется в обратном направлении для чего-то, что ближе к функциональному программированию. По-прежнему требуется руководство пользователя, чтобы знать, какие части программы можно безопасно запускать одновременно.

Ответ 3

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

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

Вы можете найти список систем Prolog, которые многопоточны здесь:

Операционная система и веб-функции

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

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

Некоторые существующие слои даже допускают парадигмы параллелизма высокого уровня в автономном режиме Prolog. Например, Logtalk имеет некоторые конструкции, которые сопоставляются с различными целевыми системами Prolog.

Теперь перейдем к приостановленным целям. Из старых систем Prolog (поскольку Prolog II, 1982, на самом деле), мы знаем freeze/2 команды или блокировки. Эти конструкции заставляют цель не расширяться существующими предложениями, а вместо этого накладывать спальный список. Цель может быть позже проснута. Поскольку выполнение цели не является непосредственным, но только когда оно пробуждается, приостановленные цели иногда рассматриваются как параллельные цели, но лучшим понятием для этой формы parallelism будут сопрограммы.

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

Обзор систем Prolog

С наилучшими пожеланиями

Ответ 4

Из быстрого поиска в Google кажется, что парадигма параллельного логического программирования была лишь основой для нескольких исследовательских языков и больше не активно развивается. Я видел утверждения о том, что параллельная логика легко сделать в системе Mozart/Oz.

Ответ 5

В 80-х/90-х годах была большая надежда на испечение parallelism на язык (что делает его "по сути" параллельным), в частности в контексте проекта пятого поколения. Даже специальные аппаратные конструкции были изучены для реализации "Parallel Inference Machine" (PIM) (аналогично специальному оборудованию для машин LISP в лагере "функционального программирования" ). Аппаратные усилия были отменены из-за постоянного улучшения готовых процессоров, и усилия по программному обеспечению были прекращены из-за чрезмерной сложности компилятора, отсутствия спроса на трудно реализуемые высокоуровневые функции и, вероятно, отсутствие выигрыша: parallelism, который выглядит прозрачная и элегантно эксплуатируемая на уровне языка, как правило, означает дорогостоящую межпроцессную коммуникацию и транзакционную блокировку "под капотом".

Хорошее чтение об этом -

"Деволюция языков параллельного логического программирования"

Эван Тик, март 1994 года. Появился в "Журнале программирования логики, специальном выпуске десятой годовщины, 1995". Файл Postscript, связанный с ним, завершен, в отличие от PDF, который вы получаете в Elsevier.

Автор говорит:

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

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

Главное, что я хочу сделать в этой статье, это то, что параллельная логика языки программирования развивались с момента их создания, около десяти лет назад, из-за следующего tatonnement:

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

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

Деэволюционная история начинается с Concurrent Prolog (глубокие стражи, атомная унификация; переменные с записью только для чтения для синхронизация) и после ряда сокращений (например: GHC (синхронизация ввода-вывода), Parlog (безопасный), FCP (плоский), Fleng (нет охранники), Янус (ограниченное сообщение), Странд (назначение довольно чем выходная унификация)), и заканчивается на данный момент PCN (плоская защита, неатомические присвоения синхронизации ввода-вывода и явно определенные переменные переменные). Эта и другая терминология определяется как статья продолжается.

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

Ответ 6

ECLiPSe-CLP, язык "в основном обратно совместимый с Prolog", поддерживает OR- parallelism, хотя "эта функциональность в настоящее время не поддерживается активно из-за других приоритетов".

[1,2] документ OR- (и AND -) parallelism в ECLiPSe-CLP.

Однако я пытался заставить его работать некоторое время, используя код из репозитория ECLiPSe-CLP, но я его не понял.

• [1] http://eclipseclp.org/reports/book.ps.gz
• [2] http://eclipseclp.org/doc/bips/kernel/compiler/parallel-1.html