9

我一直在尝试在 Scala 中编码一个关系代数（据我所知，它是最先进的类型系统之一），但似乎没有找到一种方法来达到我想要的位置。

由于我对编程语言设计的学术领域没有那么丰富的经验，所以我真的不知道要寻找什么功能。

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

一些要求： 元组是一个函数，将名称从一组静态定义的元组有效名称映射到名称指定类型的值。让我们将此名称类型称为设置域。

关系是一组具有相同域的元组，因此任何元组的范围在集合中都是唯一的

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

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

Tuple 中的 vals、vars 和 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 必须是可用的。层层叠叠的样板是不可接受的。

4

2 回答 2

6

What your asking for is to be able to structurally define a type as the difference of two other types (the original relation and the projection definition). I honestly can't think of any language which would allow you to do that. Types can be structurally cumulative (A with B) since A with B is a structural sub-type of both A and B. However, if you think about it, a type operation A less B would actually be a supertype of A, rather than a sub-type. You're asking for an arbitrary, contravariant typing relation on naturally covariant types. It hasn't even been proven that sort of thing is sound with nominal existential types, much less structural declaration-point types.

I've worked on this sort of modeling before, and the route I took was to constraint projections to one of three domains: P == T, P == {F} where F in T, P == {$_1} where $_1 anonymous. The first is where the projection is equivalent to the input type, meaning it is a no-op (SELECT *). The second is saying that the projection is a single field contained within the input type. The third is the tricky one. It is saying that you are allowing the declaration of some anonymous type $_1 which has no static relationship to the input type. Presumably it will consist of fields which delegate to the input type, but we can't enforce that. This is roughly the strategy that LINQ takes.

Sorry I couldn't be more helpful. I wish it were possible to do what you're asking, it would open up a lot of very neat possibilities.

于 2008-10-04T17:04:32.190 回答
0

我想我已经决定只使用正常的设施来收集项目部分的地图。客户端只需指定一个功能[T<:Tuple](t:T) => P

使用一些java技巧来获取PI类应该能够使用反射来实现查询逻辑。

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

作为奖励，我也许可以让 API 与 Scalas 特殊的 for 语法一起使用。

于 2008-10-07T21:42:46.980 回答