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

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

5 голосов
/ 01 февраля 2010

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

Техника такова: 

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

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

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

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

Ответы [ 4 ]

9 голосов
/ 01 февраля 2010

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

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

  • Threads (Concurrent Haskell)

  • Data Parallel Haskell

  • «Искры» с операторами par и seq.

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

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

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

3 голосов
/ 01 февраля 2010

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

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

0 голосов
/ 02 февраля 2010

Честно говоря, то, что вы показали, ничем не отличается от понимания списка, возможно, в сочетании с 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 }

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

0 голосов
/ 01 февраля 2010

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

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

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

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

...