Написание определенного для домена языка для выбора строк из таблицы

Question

Я пишу сервер, который, как я ожидаю, будет управляться многими разными людьми, а не со всеми, с которыми у меня будет прямой контакт. Серверы будут взаимодействовать друг с другом в кластере. Часть функциональности сервера включает в себя выбор небольшого подмножества строк из потенциально очень большой таблицы. Точный выбор того, какие строки выбраны, потребует некоторой настройки, и важно, чтобы человек, выполняющий кластер (например, я), обновил критерии выбора, не получив каждого администратора сервера для развертывания новой версии сервера ,

Просто написать функцию в Python на самом деле не вариант, так как никто не захочет установить сервер, который загружает и выполняет произвольный код Python во время выполнения.

Что мне нужно, это предложения по простейшему способу внедрения определенного для домена языка для достижения этой цели. Язык должен быть способен к простой оценке выражений, а также к запросам индексов таблиц и итерации по возвращенным строкам. Простота написания и чтения языка является второстепенным по сравнению с простотой ее реализации. Я также предпочел бы не писать полный оптимизатор запросов, поэтому что-то явно указывает, какие индексы для запроса были бы идеальными.

Интерфейс, с которым это придется скомпилировать, будет схожим по возможностям с тем, что экспортирует хранилище данных App Engine: вы можете запрашивать последовательные диапазоны по любому индексу в таблице (например, меньше, больше, чем, диапазон и запросы равенства), затем отфильтруйте возвращаемую строку любым логическим выражением. Вы также можете объединить несколько независимых наборов результатов.

Я понимаю, что этот вопрос звучит так же, как я прошу SQL. Однако я не хочу требовать, чтобы хранилище данных, поддерживающее эти данные, было реляционной базой данных, и я не хочу накладных расходов на попытку переопределить SQL сам. Я также имею дело только с одной таблицей с известной схемой. Наконец, никаких соединений не потребуется. Что-то намного проще было бы намного предпочтительнее.

Редактировать: Расширенное описание, чтобы прояснить некоторые заблуждения.

Answer 1

Строим DSL быть истолковано Python.

Шаг 1. Постройте классы времени и объекты времени выполнения. Эти классы будут иметь все петли курсора и операторы SQL и всю эту алгоритмическую обработку, спрятанную в своих методах. Вы будете использовать шаблоны дизайна Command и Strategy для создания этих классов. Большинство вещей - это команда, параметры и выбор - это плагины. Посмотрите на дизайн API Apache Ant Task - это хороший пример.

Шаг 2. Убедитесь, что эта система объектов действительно работает. Убедитесь, что дизайн прост и завершен. Вы тестируете объекты Command и Strategy, а затем выполняете объект Command верхнего уровня. Объекты Command будут выполнять эту работу.

На данный момент вы в основном делаете. Время выполнения - это просто конфигурация объектов, созданных из указанного домена. [Это не так просто, как кажется. Это требует некоторой осторожности, чтобы определить набор классов, которые могут быть созданы, а затем «поговорить между собой», чтобы выполнить работу вашей заявки.]

Обратите внимание, что то, что у вас будет, потребует не более чем деклараций. Что не так с процедурной? Когда вы начинаете писать DSL с процедурными элементами, вы обнаружите, что вам нужно больше и больше функций, пока вы не написали Python с другим синтаксисом. Нехорошо.

Кроме того, процедурные переводчики просто записывают. Состояние исполнения и объем ссылок просто трудно справиться.

Вы можете использовать собственный Python - и перестать беспокоиться о «выходе из песочницы». В самом деле, так вы будете тестировать все, используя короткий скрипт Python для создания ваших объектов. Python будет DSL.

[«Но подождите», вы говорите: «Если я просто использую Python, поскольку пользователи DSL могут выполнять произвольные вещи». Зависит от того, что находится на PYTHONPATH, и sys.path. Посмотрите на модуль site, чтобы узнать, что доступно.]

Простой декларативный DSL. Это всего лишь упражнение в представлении. Блок Python, который просто устанавливает значения некоторых переменных, хорош. Это то, что использует Django.

Вы можете использовать ConfigParser как язык для представления конфигурации объектов во время выполнения.

Вы можете использовать JSON или YAML в качестве языка для представления вашей конфигурации объектов во время выполнения. Готовые парсеры полностью доступны.

Вы также можете использовать XML. Труднее разрабатывать и анализировать, но он отлично работает. Людям это нравится. Вот как Ant и Maven (и множество других инструментов) используют декларативный синтаксис для описания процедур. Я не рекомендую это, потому что это многословная боль в шее. Я рекомендую просто использовать Python.

Или вы можете уйти с глубокого конца и придумать свой собственный синтаксис и написать собственный парсер.

Answer 2

Почему бы не создать язык, который, когда он «компилирует», генерирует SQL или любой язык запросов, требуемый вашим хранилищем данных?

Вы бы в основном создавали абстракцию над вашим уровнем персистентности.

Answer 3

Вы упомянули Python. Почему бы не использовать Python? Если кто-то может «ввести» выражение в вашей DSL, они могут ввести Python.

Вам понадобятся некоторые правила структуры выражения, но это намного проще, чем реализация чего-то нового.

Answer 4

Вы сказали, что никто не захочет установить сервер, который загружает и выполняет произвольный код во время выполнения. Тем не менее, это именно то, что сделает ваш DSL (в конечном итоге), поэтому, вероятно, это не так уж и важно. Если вы не делаете что-то очень специфичное с данными, то я не думаю, что DSL купит вас так много, и это сорбит пользователей, которые уже разбираются в SQL. Не стоит недооценивать размер задачи, которую вы будете выполнять.

Для ответа на ваш вопрос, однако, вам нужно будет найти грамматику для вашего языка, что-то, чтобы разобрать текст и пройти дерево, исправить код или вызвать API, который вы написали (вот почему мой комментарий что вам все равно придется отправить какой-то код).

Существует множество учебных текстов по грамматикам для математических выражений, которые вы можете найти в сети, это довольно прямолинейно.У вас может быть инструмент генератора парсеров, такой как ANTLR или Yacc, который вы можете использовать, чтобы помочь вам создать парсер (или использовать язык, такой как Lisp/Scheme, и выйти замуж за двоих). Придумать разумную грамматику SQL будет непросто. Но google 'BNF SQL' и посмотреть, что вы придумали.

Удачи.

Answer 5

Думаю, нам понадобится дополнительная информация. Сообщите мне, если какое-либо из следующих основано на неправильных предположениях.

Прежде всего, как вы указали сами, уже существует DSL для выбора строк из произвольных таблиц - он называется «SQL». Поскольку вы не хотите перерабатывать SQL, я предполагаю, что вам нужно только запрашивать из одной таблицы с фиксированным форматом.

Если это так, вам, вероятно, не нужно внедрять DSL (хотя это, безусловно, один из способов пойти); может быть проще, если вы используете объект Ориентация, чтобы создать объект Filter.

В частности, коллекция «Фильтр», которая будет содержать один или несколько объектов SelectionCriterion. Вы можете реализовать их для наследования из одного или нескольких базовых классов, представляющих типы выборов (Range, LessThan, ExactMatch, Like и т. Д.). После того, как эти базовые классы находятся на своем месте, вы можете создать унаследованные версии, соответствующие столбцу, которые соответствуют этому столбцу , Наконец, в зависимости от сложности запросов, которые вы хотите поддерживать, вы захотите реализовать какой-то соединительный клей для обработки AND и OR и NOT связей между различными критериями.

Если вам кажется, что вы можете создать простой графический интерфейс для загрузки коллекции; Я бы посмотрел на фильтрацию в Excel как на модель, если у вас нет ничего другого.

И, наконец, должно быть тривиально преобразовать содержимое этой коллекции в соответствующий SQL и передать ее в базу данных.

Однако: если вы хотите простоту, и ваши пользователи понимают SQL, вы можете просто попросить их ввести содержимое предложения WHERE и программно собрать оставшуюся часть запроса. С точки зрения безопасности, если ваш код имеет контроль над выбранными столбцами и предложением FROM, а ваши разрешения на доступ к базе данных установлены правильно, и вы выполняете некоторую проверку работоспособности строки, поступающей от пользователей, это будет относительно безопасным вариантом.

Answer 6

Это действительно звучит как SQL, но, возможно, стоит попробовать использовать SQLite, если вы хотите сохранить его простым?

Answer 7

«реализовать Domain Specific Language»

«никто не собирается хотеть установить сервер, который загружает и выполняет произвольный код Python во время выполнения»

Я хочу DSL, но я не хочу Python быть DSL. Хорошо. Как вы будете выполнять эту DSL? Какая продолжительность исполнения является приемлемым, если не Python?

Что делать, если у меня есть программа на C, которая внедряет интерпретатор Python? Это приемлемо?

И - если Python не является приемлемым временем выполнения - почему у этого есть тег Python?

Answer 8

Похоже, вы хотите создать грамматику, а не DSL. Я бы посмотрел на ANTLR, который позволит вам создать определенный синтаксический анализатор, который будет интерпретировать текст и переводить на определенные команды. ANTLR предоставляет библиотеки для Python, SQL, Java, C++, C, C# и т. Д.

Кроме того, здесь является прекрасным примером ANTLR calculation engine созданного в C#

Answer 9

Контекстно-свободная грамматика обычно имеет структуру дерева, а функциональные программы также имеют структуру дерева. Я не утверждаю, что следующее решение будет решить все ваши проблемы, но это хороший шаг в этом направлении, если вы уверены, что не хотите использовать что-то вроде 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)) 

Как вы убеждаетесь, что не имеете возможности выполнять произвольный код. Эта структура допускает все возможные функции. Ну, вы можете направить оболочку поверх нее для обеспечения безопасности, которая предоставляет фиксированный список объектов функций, которые являются приемлемыми.

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) 

Как написать assert_composition_of_allowed_funcs. Это очень сложно сделать в python, но легко в lisp. Предположим, что где - список функций, которые должны оцениваться в губах, например формат, то есть where=(operator.add, (operator.getitem, row, v1), 2) или where=(operator.mul, (operator.add, (opreator.getitem, row, v2), 2), 3).

Это позволяет написать функцию apply_lisp, которая гарантирует, что функция where состоит только из ALLOWED_FUNCS или констант, таких как 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:] ]) 

Кроме, вам также необходимо проверить наличие точных типов, потому что вы не хотите, чтобы ваши типы быть переопределены. Поэтому не используйте isinstance, используйте type in (float, int, str). О мальчик, мы столкнулись:

Десятого правила Гринспена программирования: любой достаточно сложная C или Fortran программа содержит специальную неформально-указанной ошибку охваченных медленной реализации половины Common Lisp.