Многопоточность на … функциональных языках? (Пролог)
Когда мой друг начал изучать Пролог в школе, я высмеял его для изучения бесполезного языка. Однако он, показал мне некоторый материал, который я даже не знал возможный; я хочу знать, куда эта техника прибывает из.
Техника - это:
permutation(List) :-
isAMember(X, List),
deleteFirstElement(X, List, Substring),
% and so on
В этом коде, isAMember(X, List) функция, которая возвращает true если X находится в List. Однако до этой точки X не определяется как переменная - таким образом, программа породит набор новых потоков, один для каждого возможного значения X это делает isAMember(X, List) верный, и продолжаются оттуда.
Это позволяет нам создавать многопоточный алгоритм самым простым, самым изящным способом, которым я, возможно, когда-либо воображал возможным.
Таким образом, мой вопрос: действительно ли это является Определенным для пролога, или функция всех логичных - и/или функциональные языки? Кроме того, где я могу узнать больше удивительные методы многопоточности как это - это - конечно, будущее программирования.
4 ответа
Подмножество пролога, известного как «DataLog», ограничен чистыми логическими особенностями (без «вырезания»), а в принципе доказательство поиска может быть сделано параллельно. Однако вы должны быть осторожны, потому что семантика полного пролога вполне чувствительна к порядку, в котором производится результаты, и некоторые реальные программы пролога зависят от этого.
Ситуация в чистых функциональных языках, таких как Haskell, и Clean, немного лучше - всегда безопасна для оценки подразделений параллельно, но есть много проблем производительности. Если вы делаете экстремальные параллелизм (каждое подзренение), вы не получаете никаких достижений производительности из-за всех накладных расходов. Обеспечающие подходы в данный момент кажутся
нитями (одновременно Haskell)
данные параллельно Haskell
«Sparks» с
parиоператоры SEQ.
Параллельные функциональные вещи были в течение почти 30 лет, и люди все еще пытаются сделать его хорошо. Если вам нужна дополнительная информация, попробуйте
недавнее разбирательство симпозиума ACM на Haskell (и до этого, семинар Haskell)
работа Arvind в MIT, которая была отличной пионерской в этой области (проверьте его книгу С R. Nikhil на параллельном программировании с pH)
Isamemn (X, List) не будет создавать нити, логика для пролового пролога всего лишь настроен на рекурсировании и возвращении и вполне процедура, если вы не создаете потоки.
В случае Isamember (X, список) , вы смотрите на концепцию объединения. Эта функция объединится со всеми значениями, которые оценивают эту функцию для true, в этом случае все элементы содержащиеся в списке. И продолжайте выполнение с X.
После того, как исполнение достигло листа, он будет возвращен к самому раннему возможному «все еще Unifiable» Call (или Cut-точку, я думаю, не может вспомнить правильный термин), Скажите Isamemn (X, список) , объединит X к следующему кандидату и возобновить выполнение.
DARE Я говорю, если вы не осторожно в своей логике, вы можете легко получить переполнение стека.
Если я правильно помню свой Пролог, вы не создаете потоки, а вместо этого поочередно пытаетесь каждое возможное инстанцирование X, используя бэктрейкинг и унификацию. Это довольно последовательный процесс.
EDIT: Видимо, есть несколько экспериментальных параллельных прологов, например, Reform Prolog. Однако, насколько я могу судить, это не является нормой в реализациях Пролога.
Честно говоря, то, что вы показали, не кажется Любые отличаются от понимания списка, возможно, в сочетании с FOREACH:
foreach {x | x in List}
deleteFirstElement(x, List, Substring)
// not sure what deleteFirstElement does, so...
Как вы упоминали, что Isamemn может быть что угодно, понимание списка может быть более сложным также
foreach {x | x in List if x % 2 == 0} // ie, even elements of List
вдоль тех же строк, вы можете сделать то же самое без понимания списка
new_list = old_list.every { x | x % 2 == 0 }
которые могут быть разбиты в потоки так же просто.