Многопоточность на... функциональных языках? (Пролог)

Question

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

Техника такая:

permutation(List) :-
    isAMember(X, List),
    deleteFirstElement(X, List, Substring),
    % and so on

В этом коде isAMember(X, List) это функция, которая возвращает true, если X в List, Однако до этого момента X не определяется как переменная, поэтому программа создаст кучу новых потоков, по одному на каждое возможное значение X что делает isAMember(X, List) правда и дальше оттуда.

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

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

Answer 1

Подмножество Prolog, известное как "Datalog", ограничено чисто логическими функциями (без "вырезки"), и в принципе поиск доказательства может выполняться параллельно. Однако вы должны быть осторожны, потому что семантика полного Пролога весьма чувствительна к порядку, в котором получены результаты, и некоторые реальные программы Пролог зависят от этого.

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

• Threads (Concurrent Haskell)

• Data Parallel Haskell

• "Искры" с par а также seq операторы.

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

• Недавние материалы Симпозиума ACM по Haskell (и до этого семинар по Haskell)

• Работа Арвинда в Массачусетском технологическом институте, который был великим пионером в этой области (посмотрите его книгу с Р. Нихилом о параллельном программировании с pH)

Answer 2

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

РЕДАКТИРОВАТЬ: Очевидно, есть некоторые экспериментальные параллельные прологи, например, Reform Prolog. Однако, насколько я могу судить, это не является нормой в реализациях Пролога.

Answer 3

Честно говоря, то, что вы показали, ничем не отличается от понимания списка, возможно, в сочетании с foreach:

foreach {x | x in List}
    deleteFirstElement(x, List, Substring) 
    // not sure what deleteFirstElement does, so...

Как вы упоминали, что isAMember может быть чем угодно, понимание списка может быть более сложным

foreach {x | x in List if x % 2 == 0} // ie, even elements of List

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

new_list = old_list.every { x | x % 2 == 0 }

которые можно легко разбить на нити.

Answer 4

isAMember(X, List) не будет создавать потоки, логика пролога просто сильно зависит от рекурсии и обратного отслеживания и является достаточно процедурной, если вы явно не создаете потоки.

В случае isAMember(X, List)Вы смотрите на концепцию объединения. эта функция объединится со всеми значениями, которые оценивают эту функцию как true, в этом случае все элементы, содержащиеся в списке. И приступить к выполнению с X.

Как только выполнение достигнет листа, оно вернется к самому раннему возможному вызову, который все еще не определен (или я думаю, что точка отсечения не может вспомнить правильный термин), скажем, isAMember(X, List), объединит X со следующим кандидатом и возобновит выполнение.

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