编写领域特定语言来从表中选择行

Question

我正在编写一个服务器，我希望它由许多不同的人运行，但并不是所有我都会直接接触的人。 服务器将在集群中相互通信。 服务器的部分功能涉及从可能非常大的表中选择一小部分行。 选择哪些行的确切选择将需要一些调整，并且重要的是运行集群的人（例如我自己）可以更新选择标准，而无需让每个服务器管理员部署新版本的服务器。

简单地用 Python 编写函数并不是一个真正的选择，因为没有人会想要安装一个在运行时下载并执行任意 Python 代码的服务器。

我需要的是关于实现领域特定语言以实现此目标的最简单方法的建议。 该语言需要能够进行简单的表达式求值，以及查询表索引和迭代返回的行。 编写和阅读语言的难易程度仅次于实现语言的难易程度。 我也不想编写整个查询优化器，因此明确指定要查询的索引的东西将是理想的。

必须编译的接口在功能上与 App Engine 数据存储区导出的功能类似：您可以查询表上任何索引的顺序范围（例如，小于、大于、范围和相等查询） ，然后通过任何布尔表达式过滤返回的行。 您还可以将多个独立的结果集连接在一起。

我意识到这个问题听起来很像我在问 SQL。 但是，我不想要求支持此数据的数据存储是关系数据库，并且我不希望自己尝试重新实现 SQL 的开销。 我还只处理一个具有已知模式的表。 最后，不需要加入。 更简单的东西会更好。

编辑：扩展描述以消除一些误解。

Answer 1

听起来你想创建一个语法而不是 DSL。 我会研究 ANTLR ，它允许您创建一个特定的解析器来解释文本并转换为特定的命令。 ANTLR 提供了 Python、SQL、Java、C++、C、C# 等库。

另外，这里是 ANTLR 的一个很好的示例 计算引擎

Answer 2

构建由 Python 解释的 DSL。

步骤 1. 构建运行时类和对象。 这些类将所有游标循环和 SQL 语句以及所有算法处理隐藏在它们的方法中。 您将大量使用 命令 和 构建这些类的策略设计模式。 大多数东西都是命令，选项和选择是插件策略。 看看 Apache Ant 的 Task API 的设计——这是一个很好的例子。

步骤 2. 验证该对象系统是否确实有效。 确保设计简单且完整。 您的测试将构造 Command 和 Strategy 对象，然后执行顶级 Command 对象。 命令对象将完成这项工作。

至此，您已基本完成。 您的运行时只是从上述域创建的对象的配置。 [这并不像听起来那么容易。 需要小心地定义一组可以实例化的类，然后“它们之间进行对话”来完成应用程序的工作。]

请注意，您所需要的只是声明。 程序上有什么问题吗？ 当您开始使用过程元素编写 DSL 时，您会发现需要越来越多的功能，直到您使用不同的语法编写 Python。 不好。

此外，过程语言解释器很难编写。 执行状态和引用范围很难管理。

您可以使用本机 Python，而不必再担心“脱离沙箱”。 事实上，这就是您对所有内容进行单元测试的方式，使用简短的 Python 脚本来创建对象。 Python 将成为 DSL。

[“但是等等”，你说，“如果我简单地使用 Python 作为 DSL，人们就可以执行任意的事情。” 取决于 PYTHONPATH 和 sys.path 上的内容。 查看 site 模块，了解控制可用内容的方法。]

声明性 DSL最简单。 这完全是一种代表性的练习。 仅设置某些变量值的 Python 块很好。 这就是 Django 所使用的。

您可以使用 ConfigParser 作为表示运行时配置的语言对象。

您可以使用 JSON 或 YAML 作为表示对象运行时配置的语言。 现成的解析器是完全可用的。

您也可以使用 XML。 设计和解析比较困难，但效果很好。 人们喜欢它。 这就是 Ant 和 Maven（以及许多其他工具）使用声明性语法来描述过程的方式。 我不推荐它，因为它是一个冗长的脖子痛。 我建议简单地使用Python。

或者，您可以深入研究并发明自己的语法并编写自己的解析器。

Answer 3

我想我们需要更多的信息。 如果以下任何内容基于错误的假设，请告诉我。

首先，正如您自己指出的，已经存在一种用于从任意表中选择行的 DSL——它称为“SQL”。 由于您不想重新发明 SQL，因此我假设您只需要从具有固定格式的单个表进行查询。

如果是这种情况，您可能不需要实现 DSL（尽管这肯定是一种方法）； 如果您习惯于面向对象，那么创建 Filter 对象可能会更容易。

更具体地说，是一个包含一个或多个 SelectionCriterion 对象的“Filter”集合。 您可以实现这些以从表示选择类型的一个或多个基类（Range、LessThan、ExactMatch、Like 等）继承。一旦这些基类就位，您就可以创建适合该列的特定于列的继承版本。 最后，根据您想要支持的查询的复杂性，您将需要实现某种连接胶来处理各种条件之间的 AND、OR 和 NOT 链接。

如果您愿意，您可以创建一个简单的 GUI 来加载集合； 如果您没有其他想法，我会将 Excel 中的过滤视为模型。

最后，将此 Collection 的内容转换为相应的 SQL，并将其传递到数据库应该很简单。

但是：如果您追求的是简单性，并且您的用户了解 SQL，您可以简单地要求他们输入 WHERE 子句的内容，并以编程方式构建查询的其余部分。 从安全角度来看，如果您的代码可以控制所选的列和 FROM 子句，并且您的数据库权限设置正确，并且您对来自用户的字符串进行了一些健全性检查，那么这将是一个相对安全的选项。

Answer 4

“实现领域特定语言”

“没有人会想要安装在运行时下载并执行任意 Python 代码的服务器”

我想要一个 DSL，但我不希望 Python 成为那个 DSL。 好的。 您将如何执行此 DSL？ 如果不是 Python，什么运行时可以接受？

如果我有一个 C 程序恰好嵌入了 Python 解释器怎么办？ 这是可以接受的吗？

而且——如果 Python 不是可接受的运行时——为什么它有一个 Python 标签？

Answer 5

为什么不创建一种语言，在“编译”时生成 SQL 或数据存储区所需的任何查询语言？

您基本上会在持久层上创建一个抽象。

Answer 6

你提到了Python。 为什么不使用Python？ 如果有人可以在您的 DSL 中“输入”表达式，那么他们就可以输入 Python。

您需要一些关于表达式结构的规则，但这比实现新的东西容易得多。

Answer 7

您说没有人会想要安装在运行时下载并执行任意代码的服务器。 然而，这正是您的 DSL（最终）要做的事情，因此可能没有太大区别。 除非你正在对数据做一些非常具体的事情，否则我认为 DSL 不会给你带来那么多好处，而且它会让已经精通 SQL 的用户感到沮丧。 不要低估您将要承担的任务的规模。

然而，要回答你的问题，你需要为你的语言想出一个语法，一些东西来解析文本并遍历树，发出代码或调用你编写的API（这就是为什么我评论说你是仍然需要发送一些代码）。

网上有很多关于数学表达式语法的教育文本，您可以参考，这相当简单。 您可能有像 ANTLR 或 Yacc 这样的解析器生成器工具，可以用来帮助您生成解析器（或者使用像 Lisp/Scheme 这样的语言并将两者结合起来）。 提出合理的 SQL 语法并不容易。 但是谷歌一下“BNF SQL”，看看你能得到什么。

祝你好运。

Answer 8

这听起来确实像 SQL，但如果您想保持简单，也许值得尝试使用 SQLite？

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 是要以类似格式进行计算的函数列表，即 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 一半的错误缠身，执行缓慢。