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

Question

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

Методика такова:

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

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

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

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

Answer 1

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

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

• Темы (Concurrent Haskell)

• Data Parallel Haskell

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

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

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

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

Answer 2

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

EDIT: По-видимому, есть некоторые экспериментальные параллельные прологи, например, Reform Prolog. Однако, насколько я могу судить, это не является нормой в реализации Prolog.

Answer 3

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

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

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

Dare Я говорю, если вы не осторожны в своей логике, вы можете легко получить переполнение стека.

Answer 4

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

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 } 

который может быть разбит на потоки так же просто.