实现关系代数的语言特性

Question

我一直在尝试用Scala编写关系代数(据我所知，Scala拥有最高级的类型系统之一)，但似乎找不到我想要的方法。

由于我在编程语言设计的学术领域没有太多经验，我真的不知道该寻找什么功能。

那么，要实现静态验证的关系代数，需要哪些语言特性，以及哪些语言具有这些特性？

一些要求:元组是一个函数，用于将静态定义的元组有效名称集中的名称映射到名称指定的类型的值。让我们称其为name-type，设置域名。

关系是具有相同域的元组的集合，使得任何元组的范围在该集合中是唯一的

到目前为止，这个模型可以很容易地在Scala中建模，只需

trait Tuple
trait Relation[T<Tuple] extends Set[T]

Tuple中的vals、vars和defs是上面定义的name-type集合。但是在Tuple中应该有两个相同名称的defs。另外，vars和impure defs可能也应该受到限制。

现在到了棘手的部分：

两个关系的连接是这样一种关系，其中元组的域是来自操作数元组的域的并集。使得只有对于它们的域的交集具有相同范围的元组才被保留。

def join(r1:Relation[T1],r2:Relation[T2]):Relation[T1 with T2]

应该能行得通。

关系的投影是其中元组的域是操作数元组域的子集的关系。

def project[T2](r:Relation[T],?1):Relation[T2>:T]

这就是我不确定是否有可能找到解决方案的地方。你认为如何？定义项目需要哪些语言特性？

当然，上面暗示的是API必须是可用的。一层层的样板是不能接受的。

Answer 1

您所要求的是能够在结构上将一个类型定义为两个其他类型(原始关系和投影定义)的差异。老实说，我想不出任何一种语言可以让你这样做。类型可以是结构累积的(A with B)，因为A with B是A和B的结构子类型。然而，如果你仔细想想，类型操作A less B实际上是A的超类型，而不是子类型。您要求在自然协变类型上建立任意的逆变类型关系。甚至还没有证明这类事情对于名义存在类型是合理的，更不用说结构声明点类型了。

我以前做过这种建模，我采用的方法是将约束投影到三个域中的一个：P == T，P == {F} where F in T，P == {$_1} where $_1 anonymous。第一个是投影与输入类型等价的地方，这意味着它是一个无操作(SELECT *)。第二种说法是，投影是包含在输入类型中的单个字段。第三个是棘手的问题。这意味着您允许声明某个匿名类型$_1，该类型与输入类型没有静态关系。假设它将由委托给输入类型的字段组成，但我们不能强制这样做。这大致就是LINQ采取的策略。

抱歉，我帮不上忙了。我希望有可能做到你所要求的，这将打开许多非常巧妙的可能性。

Answer 2

我想我已经决定只使用普通的工具来为项目部分收集地图。客户端只需指定一个函数[T<:Tuple](t:T) => P

通过一些java技巧来获得P类，我应该能够使用反射来实现查询逻辑。

对于连接，我可能会使用DynamicProxy来实现映射函数。

作为额外的好处，我也许能够让API能够与Scalas的特殊for-语法一起使用。