Làm cách nào để triển khai thuật toán hợp nhất bằng ngôn ngữ như Java hoặc C#?

Question

Tôi đang làm việc thông qua sách giáo khoa AI của mình mà tôi nhận được và tôi đã gặp vấn đề bài tập về nhà cuối cùng cho phần của mình:

"Thực hiện Thuật toán thống nhất được nêu ở trang 69 bằng ngôn ngữ bạn chọn."

Trên trang 69, bạn đã pseudo-code sau cho các thuật toán thống nhất:

function unify(E1, E2); 
    begin 
     case 
      both E1 and E2 are constants or the empty list: 
       if E1 = E2 then return {} 
       else return FAIL; 
      E1 is a variable: 
       if E1 occurs in E2 then return FAIL 
       else return {E2/E1} 
      E2 is a variable 
       if E2 occurs in E1 then FAIL 
        else return {E1/E2} 
      either E1 or E2 are empty then return FAIL 
      otherwise: 
       begin 
        HE1 := first element of E1; 
        HE2 := first element of E2; 
        SUBS1 := unify(HE1, HE2); 
        if SUBS1 := FAIL then return FAIL; 
        TE1 := apply(SUBS1, rest of E1); 
        TE2 := apply(SUBS1, rest of E2); 
        SUBS2 := unify(TE1, TE2); 
        if SUBS2 = FAIL then return FAIL; 
         else return composition(SUBS1, SUBS2) 
       end 
      end 
     end 

Bây giờ, tôi hiểu được những khái niệm chung của thống nhất đất nước nhưng tôi hoàn toàn không có ý tưởng làm thế nào tôi thậm chí sẽ bắt đầu thực hiện điều này bằng ngôn ngữ như Java hoặc C#.

Tôi thậm chí không chắc chắn chữ ký của phương thức sẽ trông như thế nào. Loại biến nào sẽ mất? Tôi khá chắc chắn tôi cần phải trả lại danh sách để đại diện cho cấu trúc tính toán vị ngữ nhưng đó là một đoán.

Ví dụ, khi nó nói "E1 là một biến", tốt, nếu tôi chuyển nó vào phương pháp hợp nhất, làm thế nào nó có thể là bất cứ điều gì nhưng? Tôi có thể kiểm tra null nhưng điều đó sẽ khác với "danh sách trống"?

Bất cứ ai có thể giúp tôi hoặc chỉ cho tôi đúng hướng để triển khai thuật toán Unificaiton trong C# hoặc Java?

Answer 1

Cách tốt nhất để thể hiện các biến thể loại là thừa kế. Ví dụ, một chuỗi các biểu thức vẫn chỉ là một biểu thức. Một danh sách trống sẽ được biểu diễn bằng một vùng chứa có độ dài bằng không trong đối tượng chuỗi. Do đó, trả về null có thể chấp nhận được cho lỗi, mà tôi chỉ ra bằng '?'. Tôi không chắc chắn nếu C# thực sự có một '?', Nhưng sẽ nhận được sự trôi dạt.

abstract class Expression { ... } 
class Atom : Expression { ... } 
class Variable : Expression { ... } 
class Sequence : Expression { List <Expression> ... } 

Expression? unify (Expression e1, Expression e2) { ... } 

EDIT: Danh sách có thể thay đổi. Xem here. Phương ngữ Vala của tôi về C# hỗ trợ điều này (hiện tại), nhưng tôi không tin.

Answer 2

Các biến mà bạn sẽ sử dụng khi triển khai thuật toán có lẽ là những gì bạn có thể gọi là biến số. Chúng là các biến trong chương trình của bạn mô tả một biến (hoặc hằng số, hoặc danh sách, vv) trong một số chương trình khác. Như vậy bạn cần sử dụng một biến cho bạn biết loại đối tượng (ví dụ: biến, hằng số) và giá trị của đối tượng. Bạn có thể làm điều này thông qua kế thừa như Samuel Danielson đã đề xuất, hoặc thông qua một số loại đối tượng Biến thể nếu ngôn ngữ của bạn cung cấp một hoặc một lớp biến thể có thể mô tả bất kỳ loại biến nào (ví dụ: thông qua một enum mô tả loại và nhiều trường được nhập, trong đó chỉ có một trường hợp lệ, phụ thuộc vào loại).

Answer 3

"... là một biến" có nghĩa là để kiểm tra các loại của biến. Nếu loại E1 là một giá trị biến (tức là không phải của danh sách loại và không phải là một giá trị không đổi), thì hãy làm một cái gì đó.

Answer 4

Đối với bất kỳ ai quan tâm, tôi đã tìm thấy cùng một thuật toán tại http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html với ngữ cảnh nhiều hơn một chút.

Hãy nhìn vào dòng đầu tiên:

function unify(E1, E2) 

E1 và E2 là những biểu hiện: hoặc danh sách, các biến, hoặc hằng số. Theo phong cách OOP truyền thống, chúng tôi sẽ tạo một lớp cơ sở trừu tượng Expression và lấy các lớp khác từ nó như List, Variable hoặc Constant. Tuy nhiên theo ý kiến ​​của tôi, điều này là quá mức cần thiết. Tôi đã thực hiện điều này trong C# bằng cách sử dụng từ khóa dynamic.

Câu hỏi tiếp theo là câu trả lời là gì? Danh sách các liên kết có thể được triển khai dưới dạng Dictionary<string, Object>.

Dưới đây là một đoạn trích từ việc triển khai C# triển khai từ thư viện có tên là Jigsaw mà tôi đang phát triển để dạy cách triển khai ngôn ngữ C#.

public static Dictionary<string, object> Unify(dynamic e1, dynamic e2) 
{ 
    if ((IsConstant(e1) && IsConstant(e2))) 
    { 
     if (e1 == e2) 
      return new Dictionary<string,object>(); 
     throw new Exception("Unification failed"); 
    } 

    if (e1 is string) 
    { 
     if (e2 is List && Occurs(e1, e2)) 
      throw new Exception("Cyclical binding"); 
     return new Dictionary<string, object>() { { e1, e2 } }; 
    } 

    if (e2 is string) 
    { 
     if (e1 is List && Occurs(e2, e1)) 
      throw new Exception("Cyclical binding"); 
     return new Dictionary<string, object>() { { e2, e1 } }; 
    } 

    if (!(e1 is List) || !(e2 is List)) 
     throw new Exception("Expected either list, string, or constant arguments"); 

    if (e1.IsEmpty || e2.IsEmpty) 
    { 
     if (!e1.IsEmpty || !e2.IsEmpty) 
      throw new Exception("Lists are not the same length"); 

     return new Dictionary<string, object>(); 
    } 

    var b1 = Unify(e1.Head, e2.Head); 
    var b2 = Unify(Substitute(b1, e1.Tail), Substitute(b1, e2.Tail)); 

    foreach (var kv in b2) 
     b1.Add(kv.Key, kv.Value); 
    return b1; 
} 

Bạn có thể tìm phần còn lại của mã thuật toán trực tuyến tại http://code.google.com/p/jigsaw-library/source/browse/trunk/Unifier.cs. Không phải trong ví dụ này, lớp List thực sự là một danh sách kiểu Lisp mà tôi đã triển khai cho thư viện.