Cây LINQ có phải là cây thích hợp không?

Question

Các cây biểu hiện LINQ có đúng các cây thích hợp không, như trong đồ thị (hướng hoặc không, wikipedia dường như không đồng ý) mà không có chu kỳ? Gốc của cây biểu thức từ biểu thức C# sau đây là gì?

cây

(string s) => s.Length 

Biểu thức trông như thế này, với "->" biểu thị tên của thuộc tính của nút nút khác có thể truy cập thông qua.

 ->Parameters[0] 
Lambda---------Parameter(string s) 
    \    /
    \->Body  /->Expression 
     \   /
     Member(Length) 

Khi sử dụng ExpressionVisitor để truy cập LambdaExpression, ParameterExpression được truy cập hai lần. Có cách nào để sử dụng ExpressionVisitor để truy cập LambdaExpression sao cho tất cả các nút được truy cập chính xác một lần và theo thứ tự cụ thể, nổi tiếng (đặt hàng trước, theo thứ tự, đặt hàng, v.v.)?

Answer 1

Sắp xếp, có. "Thân cây" thực tế (nếu bạn muốn) của một LambdaExpression là .Body; các tham số là siêu dữ liệu cần thiết về cấu trúc của cây (và những gì nó cần), nhưng .Parameters ở trên cùng (đường chấm chấm của bạn) không thực sự là một phần của biểu đồ chức năng của cây - chỉ khi các nút đó được sử dụng sau này trong cơ thể thực sự của cây mà chúng thú vị, thay thế giá trị.

ParameterExpression được truy cập hai lần là điều cần thiết, để người khác có thể trao đổi thông số nếu muốn - ví dụ: để tạo toàn bộ số LambdaExpression mới với cùng số tham số. loại).

Đơn đặt hàng sẽ khá ổn định nhưng phải được xem là chi tiết triển khai. Ví dụ: được cung cấp một nút chẳng hạn như Add(A,B), nó sẽ không tạo ra sự khác biệt ngữ nghĩa nào cho dù tôi truy cập vào số A -first và B -ngày đầu tiên.

Answer 2

Chỉ cần thêm một chút để câu trả lời đúng của Marc:

Are LINQ cây biểu chỉ đạo các đồ thị mà không chu kỳ?

Trước hết, có, một cây biểu thức là một DAG - một biểu đồ tuần hoàn hướng.

Chúng tôi biết chúng là tuần hoàn bởi vì cây biểu thức là không thay đổi và do đó phải được xây dựng từ những chiếc lá. Trong tình huống như vậy không có cách nào để tạo chu kỳ bởi vì tất cả các nút trong chu kỳ sẽ phải được phân bổ lần cuối và rõ ràng điều đó sẽ không xảy ra.

Vì các phần không thay đổi nên cụm từ "cây" không thực sự là cây. Như Marc đã chỉ ra, bạn bắt buộc phải sử dụng tham chiếu cho tham số; đó là cách chúng tôi xác định khi nào một tham số được khai báo được sử dụng. Nó hơi kỳ lạ, mặc dù hợp pháp, để tái sử dụng các bộ phận khác nữa. Ví dụ, nếu bạn muốn biểu diễn cây biểu thức cho phần thân của (int x)=>(x + 1) * (x + 1), bạn có thể tạo một cây biểu thức cho (x + 1) và sau đó tạo một nút nhân, trong đó cả hai con đều là cây biểu thức đó.

Khi sử dụng ExpressionVisitor để truy cập LambdaExpression, ParameterExpression được truy cập hai lần. Có cách nào để sử dụng ExpressionVisitor để truy cập LambdaExpression sao cho tất cả các nút được truy cập chính xác một lần và theo thứ tự cụ thể, nổi tiếng (đặt hàng trước, theo thứ tự, đặt hàng, v.v.)?

ExpressionVisitor là lớp trừu tượng. Bạn có thể làm cho phiên bản cụ thể của riêng bạn của nó có ngữ nghĩa bạn thích. Ví dụ, bạn có thể ghi đè phương thức Lượt truy cập sao cho nó duy trì một HashSet của các nút đã thấy và không gọi Accept trên các nút mà nó đã chấp nhận trước đó.