Viết một ngôn ngữ cụ thể tên miền để chọn các hàng từ một bảng

Question

Tôi đang viết một máy chủ mà tôi mong muốn được điều hành bởi nhiều người khác nhau, không phải tất cả những người mà tôi sẽ liên hệ trực tiếp. Các máy chủ sẽ liên lạc với nhau trong một cụm. Một phần chức năng của máy chủ liên quan đến việc chọn một tập con nhỏ các hàng từ một bảng có khả năng rất lớn. Lựa chọn chính xác những hàng được chọn sẽ cần điều chỉnh và điều quan trọng là người dùng có thể chạy cụm (ví dụ, bản thân mình) để cập nhật tiêu chí lựa chọn mà không cần mỗi quản trị viên máy chủ triển khai phiên bản mới của máy chủ .

Chỉ cần viết hàm bằng Python không thực sự là một tùy chọn, vì không ai muốn cài đặt máy chủ tải xuống và thực thi mã Python tùy ý khi chạy.

Điều tôi cần là các đề xuất về cách đơn giản nhất để triển khai Ngôn ngữ cụ thể theo miền để đạt được mục tiêu này. Ngôn ngữ cần phải có khả năng đánh giá biểu thức đơn giản, cũng như truy vấn các chỉ mục bảng và lặp qua các hàng được trả về. Dễ viết và đọc ngôn ngữ là thứ yếu để dễ thực hiện nó. Tôi cũng không muốn viết một trình tối ưu hóa toàn bộ truy vấn, vì vậy một cái gì đó chỉ định rõ ràng các chỉ mục nào để truy vấn sẽ là lý tưởng.

Giao diện sẽ phải biên dịch này sẽ tương tự với khả năng xuất dữ liệu của App Engine: Bạn có thể truy vấn các dãy tuần tự trên bất kỳ chỉ mục nào trên bảng (ví dụ: nhỏ hơn, lớn hơn, phạm vi và truy vấn bình đẳng), sau đó lọc hàng trả về bởi bất kỳ biểu thức boolean nào. Bạn cũng có thể ghép nối nhiều tập kết quả độc lập với nhau.

Tôi nhận thấy câu hỏi này nghe rất giống với tôi đang yêu cầu SQL. Tuy nhiên, tôi không muốn yêu cầu kho dữ liệu sao lưu dữ liệu này là một cơ sở dữ liệu quan hệ, và tôi không muốn chi phí của việc cố gắng tự thực hiện lại SQL. Tôi cũng đang đối phó với chỉ một bảng duy nhất với một lược đồ đã biết. Cuối cùng, không cần tham gia. Một cái gì đó đơn giản hơn nhiều sẽ là thích hợp hơn.

Chỉnh sửa: Mô tả mở rộng để xóa một số quan niệm sai lầm.

Answer 1

Xây dựng một DSL để được giải thích bởi Python.

Bước 1. Tạo các lớp và đối tượng thời gian chạy. Các lớp này sẽ có tất cả các vòng lặp con trỏ và câu lệnh SQL và tất cả các thuật toán xử lý đó được giấu đi trong các phương thức của chúng. Bạn sẽ sử dụng nhiều các mẫu thiết kế Command và Strategy để tạo các lớp này. Hầu hết mọi thứ là một lệnh, các tùy chọn và lựa chọn là các chiến lược trình cắm thêm. Hãy xem thiết kế API Task của Apache Ant - đây là một ví dụ điển hình.

Bước 2. Xác thực rằng hệ thống đối tượng này thực sự hoạt động. Hãy chắc chắn rằng thiết kế đơn giản và đầy đủ. Bạn đang kiểm tra sẽ xây dựng các đối tượng Command và Strategy, và sau đó thực thi đối tượng Command cấp cao nhất. Các đối tượng Command sẽ thực hiện công việc.

Tại thời điểm này, bạn đã hoàn thành phần lớn. Thời gian chạy của bạn chỉ là cấu hình của các đối tượng được tạo từ miền trên. [Điều này là không dễ dàng như nó âm thanh. Nó đòi hỏi một số chăm sóc để xác định một tập hợp các lớp học có thể được khởi tạo và sau đó "nói chuyện với nhau" để làm công việc của ứng dụng của bạn.]

Lưu ý rằng những gì bạn sẽ có yêu cầu không có gì nhiều hơn khai báo. Có gì sai với thủ tục? Một trong những bạn bắt đầu viết một DSL với các yếu tố thủ tục, bạn thấy rằng bạn cần nhiều tính năng hơn và nhiều hơn nữa cho đến khi bạn đã viết Python với cú pháp khác nhau. Không tốt.

Hơn nữa, trình thông dịch ngôn ngữ thủ tục đơn giản là khó viết. Trạng thái thực thi và phạm vi tham chiếu đơn giản là khó quản lý.

Bạn có thể sử dụng Python gốc - và đừng lo lắng về việc "thoát khỏi hộp cát". Thật vậy, đó là cách bạn sẽ kiểm tra mọi thứ, sử dụng một kịch bản Python ngắn để tạo các đối tượng của bạn. Python sẽ là DSL.

["Nhưng chờ", bạn nói, "Nếu tôi chỉ đơn giản sử dụng Python khi người DSL có thể thực hiện những điều tùy ý." Phụ thuộc vào những gì trên PYTHONPATH và sys.path. Xem mô-đun site để biết cách kiểm soát những gì có sẵn.]

DSL khai báo là đơn giản nhất. Nó hoàn toàn là một bài tập trong biểu diễn. Một khối Python chỉ đơn thuần đặt giá trị của một số biến là tốt đẹp. Đó là những gì Django sử dụng.

Bạn có thể sử dụng ConfigParser làm ngôn ngữ đại diện cho cấu hình đối tượng thời gian chạy của mình.

Bạn có thể sử dụng JSON hoặc YAML làm ngôn ngữ đại diện cho cấu hình đối tượng thời gian chạy của bạn. Các trình phân tích cú pháp làm sẵn hoàn toàn có sẵn.

Bạn cũng có thể sử dụng XML. Khó thiết kế và phân tích cú pháp hơn, nhưng nó hoạt động tốt. Mọi người thích nó. Đó là cách Ant và Maven (và nhiều công cụ khác) sử dụng cú pháp khai báo để mô tả các thủ tục. Tôi không khuyên bạn nên nó, bởi vì đó là một nỗi đau dài dòng ở cổ. Tôi khuyên bạn chỉ nên sử dụng Python.

Hoặc, bạn có thể đi sâu và tạo ra cú pháp của riêng mình và viết trình phân tích cú pháp của riêng bạn.

Answer 2

Tại sao không tạo ra một ngôn ngữ khi nó "biên dịch" nó tạo ra SQL hoặc bất kỳ ngôn ngữ truy vấn nào mà kho dữ liệu của bạn yêu cầu?

Bạn sẽ cơ bản tạo ra một trừu tượng trên lớp kiên trì của mình.

Answer 3

Bạn đã đề cập đến Python. Tại sao không sử dụng Python? Nếu ai đó có thể "nhập" một biểu thức trong DSL của bạn, họ có thể gõ bằng Python.

Bạn sẽ cần một số quy tắc về cấu trúc của biểu thức, nhưng điều đó dễ hơn rất nhiều so với triển khai một cái gì đó mới.

Answer 4

Bạn cho biết sẽ không có ai muốn cài đặt máy chủ tải xuống và thực thi mã tùy ý khi chạy. Tuy nhiên, đó là chính xác những gì DSL của bạn sẽ làm (cuối cùng) vì vậy có lẽ không có nhiều sự khác biệt. Trừ khi bạn đang làm một cái gì đó rất cụ thể với các dữ liệu sau đó tôi không nghĩ rằng một DSL sẽ mua cho bạn nhiều và nó sẽ làm thất vọng những người dùng đã thành thạo trong SQL. Đừng đánh giá thấp kích thước của tác vụ bạn sẽ thực hiện.

Tuy nhiên, để trả lời câu hỏi của bạn, bạn cần phải đưa ra một ngữ pháp cho ngôn ngữ của mình, thứ gì đó để phân tích văn bản và đi bộ trên cây, phát ra mã hoặc gọi API mà bạn đã viết. rằng bạn vẫn sẽ phải gửi một số mã).

Có rất nhiều văn bản giáo dục về ngữ pháp cho các biểu thức toán học mà bạn có thể tham khảo trên mạng, điều đó khá thẳng về phía trước.Bạn có thể có một công cụ trình tạo trình phân tích cú pháp như ANTLR hoặc Yacc mà bạn có thể sử dụng để giúp bạn tạo trình phân tích cú pháp (hoặc sử dụng một ngôn ngữ như Lisp/Scheme và kết hôn với cả hai). Việc xây dựng một ngữ pháp SQL hợp lý sẽ không dễ dàng. Nhưng google 'BNF SQL' và xem những gì bạn nghĩ ra.

Chúc bạn may mắn.

Answer 5

Tôi nghĩ chúng ta sẽ cần thêm một chút thông tin tại đây. Hãy cho tôi biết nếu bất kỳ điều nào sau đây dựa trên các giả định không chính xác.

Trước hết, như bạn đã chỉ ra chính mình, đã tồn tại một DSL để chọn các hàng từ các bảng tùy ý-- nó được gọi là "SQL". Vì bạn không muốn tạo lại SQL, tôi giả định rằng bạn chỉ cần truy vấn từ một bảng duy nhất với định dạng cố định.

Nếu trường hợp này xảy ra, có thể bạn không cần triển khai DSL (mặc dù đó chắc chắn là một cách để thực hiện); nó có thể dễ dàng hơn, nếu bạn quen với Object Orientation, để tạo một đối tượng Filter.

Cụ thể hơn, bộ sưu tập "Bộ lọc" sẽ chứa một hoặc nhiều đối tượng SelectionCriterion. Bạn có thể thực hiện chúng để kế thừa từ một hoặc nhiều lớp cơ sở đại diện cho các kiểu lựa chọn (Range, LessThan, ExactMatch, Like, v.v.) Một khi các lớp cơ sở này được đặt ra, bạn có thể tạo các phiên bản kế thừa cụ thể cho cột phù hợp với cột đó . Cuối cùng, tùy thuộc vào độ phức tạp của các truy vấn bạn muốn hỗ trợ, bạn sẽ muốn thực hiện một số loại keo kết nối để xử lý các liên kết AND và OR và NOT giữa các tiêu chí khác nhau.

Nếu bạn cảm thấy thích, bạn có thể tạo GUI đơn giản để tải lên bộ sưu tập; Tôi sẽ xem xét việc lọc trong Excel như là một mô hình, nếu bạn không có bất cứ điều gì khác trong tâm trí.

Cuối cùng, sẽ không quan trọng để chuyển đổi nội dung của Bộ sưu tập này thành SQL tương ứng và chuyển nó vào cơ sở dữ liệu.

Tuy nhiên: nếu những gì bạn đang theo dõi là đơn giản và người dùng của bạn hiểu SQL, bạn có thể yêu cầu họ nhập nội dung của mệnh đề WHERE và lập trình xây dựng phần còn lại của truy vấn. Từ quan điểm bảo mật, nếu mã của bạn có quyền kiểm soát các cột được chọn và mệnh đề FROM, và quyền cơ sở dữ liệu của bạn được đặt đúng và bạn thực hiện kiểm tra sanity trên chuỗi từ người dùng, đây sẽ là một lựa chọn tương đối an toàn.

Answer 6

Nó thực sự giống như SQL, nhưng có lẽ nó có giá trị để thử sử dụng SQLite nếu bạn muốn giữ nó đơn giản?

Answer 7

"thực hiện một miền ngôn ngữ cụ thể"

"không ai sẽ muốn cài đặt một máy chủ tải và thực thi mã Python tùy ý trong thời gian chạy"

Tôi muốn có một DSL nhưng tôi không muốn Python để trở thành DSL đó. Đuợc. Làm thế nào bạn sẽ thực hiện DSL này? Thời gian chạy nào là có thể chấp nhận được nếu không phải là Python?

Điều gì sẽ xảy ra nếu tôi có chương trình C xảy ra khi nhúng trình thông dịch Python? Điều đó có được chấp nhận không?

Và - nếu Python không phải là thời gian chạy có thể chấp nhận - tại sao thẻ này có thẻ Python?

Answer 8

Có vẻ như bạn muốn tạo ngữ pháp không phải là DSL. Tôi sẽ xem xét ANTLR sẽ cho phép bạn tạo một trình phân tích cụ thể sẽ diễn giải văn bản và dịch sang các lệnh cụ thể. ANTLR cung cấp các thư viện cho Python, SQL, Java, C++, C, C#, v.v.

Ngoài ra, đây là một ví dụ tốt của một ANTLR calculation engine tạo ra trong C#

Answer 9

Ngữ pháp không có bối cảnh thường có một cấu trúc giống cây và các chương trình chức năng cũng có cấu trúc giống cây. Tôi không tuyên bố sau đây sẽ giải quyết tất cả các vấn đề của bạn, nhưng nó là một bước tiến tốt nếu bạn chắc chắn rằng bạn không muốn sử dụng một cái gì đó như SQLite3.

from functools import partial 
def select_keys(keys, from_): 
    return ({k : fun(v, row) for k, (v, fun) in keys.items()} 
      for row in from_) 

def select_where(from_, where): 
    return (row for row in from_ 
      if where(row)) 

def default_keys_transform(keys, transform=lambda v, row: row[v]): 
    return {k : (k, transform) for k in keys} 

def select(keys=None, from_=None, where=None): 
    """ 
    SELECT v1 AS k1, 2*v2 AS k2 FROM table WHERE v1 = a AND v2 >= b OR v3 = c 

    translates to 

    select(dict(k1=(v1, lambda v1, r: r[v1]), k2=(v2, lambda v2, r: 2*r[v2]) 
     , from_=table 
     , where= lambda r : r[v1] = a and r[v2] >= b or r[v3] = c) 
    """ 
    assert from_ is not None 
    idfunc = lambda k, t : t 
    select_k = idfunc if keys is None else select_keys 
    if isinstance(keys, list): 
     keys = default_keys_transform(keys) 
    idfunc = lambda t, w : t 
    select_w = idfunc if where is None else select_where 
    return select_k(keys, select_w(from_, where)) 

Làm cách nào để đảm bảo rằng bạn không cung cấp cho người dùng khả năng thực thi mã tùy ý. Khung công tác này thừa nhận tất cả các chức năng có thể có. Vâng, bạn có thể phải một wrapper trên nó cho an ninh mà lộ một danh sách cố định của các đối tượng chức năng được chấp nhận.

ALLOWED_FUNCS = [ operator.mul, operator.add, ...] # List of allowed funcs 

def select_secure(keys=None, from_=None, where=None): 
    if keys is not None and isinstance(keys, dict): 
     for v, fun keys.values: 
      assert fun in ALLOWED_FUNCS 
    if where is not None: 
     assert_composition_of_allowed_funcs(where, ALLOWED_FUNCS) 
    return select(keys=keys, from_=from_, where=where) 

Cách viết assert_composition_of_allowed_funcs. Nó rất khó để làm điều đó trong python nhưng dễ dàng trong lisp. Giả sử rằng danh sách các hàm được đánh giá trong môi như định dạng tức là where=(operator.add, (operator.getitem, row, v1), 2) hoặc where=(operator.mul, (operator.add, (opreator.getitem, row, v2), 2), 3).

Điều này giúp bạn có thể viết hàm apply_lisp đảm bảo rằng hàm where chỉ được tạo thành từ ALLOWED_FUNCS hoặc các hằng số như float, int, str.

def apply_lisp(where, rowsym, rowval, ALLOWED_FUNCS): 
    assert where[0] in ALLOWED_FUNCS 
    return apply(where[0], 
      [ (apply_lisp(w, rowsym, rowval, ALLOWED_FUNCS) 
      if isinstance(w, tuple) 
      else rowval if w is rowsym 
      else w if isinstance(w, (float, int, str)) 
      else None) for w in where[1:] ]) 

Ngoài ra, bạn cũng sẽ cần phải kiểm tra các loại chính xác vì bạn không muốn ghi đè loại của mình. Vì vậy, không sử dụng isinstance, sử dụng type in (float, int, str). Oh boy, chúng tôi đã chạy vào:

Greenspun của X Rule của Lập trình: bất kỳ đủ phức tạp C hoặc chương trình Fortran chứa quảng cáo hoc chính thức chỉ định bug-ridden thực hiện chậm của một nửa của Common Lisp.