Đa luồng trong ... ngôn ngữ chức năng? (Prolog)

Question

Khi bạn tôi bắt đầu học Prolog ở trường, tôi đã vui vẻ với anh ấy vì đã học một ngôn ngữ vô dụng. Tuy nhiên, anh ấy đã cho tôi xem một số thứ mà tôi chưa từng biết; Tôi muốn biết kỹ thuật này đến từ đâu.

Kỹ thuật này là thế này:

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

Trong mã này, isAMember(X, List) là một hàm trả về true nếu X là trong List. Tuy nhiên, đến thời điểm này, X không được định nghĩa là biến - do đó chương trình sẽ sinh ra một chuỗi các chuỗi mới, một cho mỗi giá trị có thể là X, làm cho isAMember(X, List) true, và tiếp tục từ đó.

Điều này cho phép chúng tôi tạo thuật toán đa luồng theo cách đơn giản, thanh lịch nhất mà tôi có thể tưởng tượng nhất có thể.

Vì vậy, câu hỏi của tôi là: Tính năng Prolog cụ thể, hoặc một tính năng của tất cả các ngôn ngữ logic và/hoặc chức năng? Ngoài ra, tôi có thể tìm hiểu thêm về các kỹ thuật đa luồng tuyệt vời như thế này - đây chắc chắn là tương lai của lập trình.

Answer 1

Tập hợp con của Prolog được gọi là "Datalog" bị hạn chế đối với các tính năng lôgic thuần túy (không "cắt"), và về nguyên tắc, tìm kiếm bằng chứng có thể được thực hiện song song. Tuy nhiên bạn phải cẩn thận vì ngữ nghĩa của Prolog đầy đủ khá nhạy cảm với thứ tự mà kết quả được tạo ra, và một số chương trình Prolog thực sự phụ thuộc vào điều này.

Tình huống trong các ngôn ngữ chức năng thuần túy như Haskell và Clean là tốt hơn một chút — luôn an toàn để đánh giá các biểu thức con song song — nhưng có nhiều thách thức về hiệu suất. Nếu bạn làm cực đoan song song (tất cả các subexpression) bạn không nhận được bất kỳ lợi ích hiệu suất vì tất cả các chi phí.Các cách tiếp cận đầy hứa hẹn vào lúc này dường như là

• Chủ đề (Concurrent Haskell)

• dữ liệu song song Haskell

• "Sparks" với par và seq nhà khai thác.

Công cụ chức năng song song đã tồn tại gần 30 năm và mọi người vẫn đang cố gắng làm cho nó hoạt động tốt. Nếu bạn muốn biết thêm thông tin, hãy thử

• thủ tục tố tụng gần đây của Hội nghị chuyên đề ACM trên Haskell (và trước đó, hội thảo Haskell)

• Công việc của Arvind tại MIT, là người tiên phong vĩ đại trong này khu vực (xem cuốn sách của ông với R. Nikhil về lập trình song song với pH)

Answer 2

Nếu tôi nhớ chính xác Prolog của mình, bạn không tạo chuỗi, nhưng thay vào đó, mỗi phiên bản X có thể được thử lần lượt, bằng cách sử dụng backtracking và unification. Nó khá là nối tiếp.

EDIT: Rõ ràng có một số prologs song song thử nghiệm trên mạng, ví dụ, Cải cách Prolog. Tuy nhiên, đây không phải là chuẩn mực trong việc triển khai Prolog, theo như tôi có thể nói.

Answer 3

isAMember(X, List) sẽ không tạo chủ đề, prolog logic chỉ dựa trên đệ quy và lùi lại và khá thủ tục trừ khi bạn tạo chủ đề một cách rõ ràng.

Trong trường hợp isAMember(X, List), bạn đang xem khái niệm hợp nhất. hàm đó sẽ hợp nhất với tất cả các giá trị đánh giá hàm đó thành true, trong trường hợp này, tất cả các phần tử có trong danh sách. Và tiếp tục thực hiện với X.

Khi thực hiện đã đạt đến một chiếc lá, nó sẽ quay trở lại cuộc gọi "vẫn không thể nhận được" sớm nhất có thể (hoặc điểm cắt, tôi nghĩ, không thể nhớ cụm từ chính xác) , nói isAMember(X, List), sẽ hợp nhất X với ứng cử viên tiếp theo và tiếp tục thực hiện.

Tôi dám nói, nếu bạn không cẩn thận trong logic của mình, bạn có thể dễ dàng nhận được tràn ngăn xếp.

Answer 4

Thành thực mà nói, những gì bạn đã thể hiện dường như không có gì khác biệt từ một hiểu danh sách, có thể kết hợp với một foreach:

012.

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

Như bạn nói rằng isAMember có thể là bất cứ điều gì, Danh sách Hiểu có thể phức tạp hơn cũng

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

Dọc theo đường cùng, bạn có thể làm điều tương tự mà không cần danh sách hiểu

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

mà có thể được chia thành các chủ đề dễ dàng.