对函数子类型感到困惑 [英] Confused about function subtyping

问题描述

我正在学习一门编程语言课程，而当一个函数是另一个函数的子类型时"的答案与我很不合常理.

I'm taking a course on programming languages and the answer to "when is a function a sub type of another function" is very counter-intuitive to me.

为了澄清:假设我们具有以下类型关系:

To clarify: suppose that we have the following type relation:

bool<int<real

为什么函数(real->bool)是(int->bool的子类型)?不应该这样吗?

Why is the function (real->bool) a subtype of (int->bool)? Shouldn't it be the other way around?

我希望子类型函数的标准是:如果f2可以接受f1可以接受的任何参数，并且f1仅返回f2返回的值，则f1是f2的子类型.显然有f1可以取值，但f2不能取值.

I would expect the criteria for sub typing functions to be: f1 is a subtype of f2 if f2 can take any argument that f1 can take, and f1 returns only values that f2 returns. There clearly are values that f1 can take, but f2 can't.

推荐答案

以下是函数子类型化的规则:

Here's the rule for function sub-typing:

参数类型必须是协变的，返回类型必须是协变的.

协变量==保留结果参数类型的"A是B的子类型"层次结构.

Co-variant == preserves the "A is a subtype of B" hierarchy for the type of the results parameter.

相反变量== 反转(反对")arguments参数的类型层次结构.

Contra-variant == reverses ("goes against") the type hierarchy for the arguments parameter.

因此，在您的示例中:

f1:  int  -> bool
f2:  bool -> bool

我们可以安全地断定f2是f1的子类型.为什么?因为(1)仅查看两个函数的参数类型，我们看到"bool是int的子类型"的类型层次实际上是协变的.它保留int和bool之间的类型层次结构. (2)仅查看两个函数的结果类型，我们就会发现逆方差得到了维持.

We can safely conclude that f2 is a subtype of f1. Why? Because (1) looking at just the argument types for both functions, we see that the type hierarchy of "bool is a subtype of int" is in fact co-variant. It preserves the type hierarchy between ints and bools. (2) looking at just the results types for both functions, we see that contra-variance is upheld.

采用另一种方式(我认为该主题的简单英语方式):

Put another way (the plain English way I think about this subject):

相反的参数:我的呼叫者可以传递比我所需的更多，但这没关系，因为我只使用需要使用的东西." 协变量返回值:我可以返回比调用者要求更多的 ，但这没关系，他/她将只使用他们需要的东西，而忽略其余部分"

contra-variant arguments: "my caller can pass in more than I require, but that's okay, because I'll use only what I need to use." co-variant return values: "I can return more than the caller requires, but that's okay, he/she will just use what they need, and will ignore the rest"

让我们看看另一个例子，使用所有都是整数的结构:

Let's look at another examples, using structs where everything is an integer:

f1:  {x,y,z} -> {x,y}
f2:  {x,y}   -> {x,y,z}

所以在这里，我们再次断言f2是f1的子类型(它是).查看两个函数的参数类型(并使用<符号表示是"的子类型)，则如果f2< f1是{x，y，z}< {x，y}?答案是肯定的. {x，y，z}与{x，y}协变.也就是说，在定义结构{x，y，z}时，我们从{x，y}结构继承"，但添加了第三个成员z.

So here again, we're asserting that f2 is a subtype of f1 (which it is). Looking at the argument types for both functions (and using the < symbol to denote "is a subtype of"), then if f2 < f1, is {x,y,z} < {x,y} ? The answer is yes. {x,y,z} is co-variant with {x,y}. i.e. in defining the struct {x,y,z} we "inherited" from the {x,y} struct, but added a third member, z.

查看两个函数的返回类型，如果f2< f1，那么{x，y}> {x，y，z}是吗?答案是肯定的. (请参见上面的逻辑).

Looking at the return types for both functions, if f2 < f1, then is {x,y} > {x,y,z}? The answer again is yes. (See above logic).

考虑这一点的第三种方法是假设f2< f1，然后尝试各种投射方案，并查看是否一切正常.示例(伪代码):

Yet a third way to think about this, is to assume f2 < f1, then try various casting scenarios, and see if everything works. Example (psuedo-code):

   F1 = f1;
   F2 = f2;
   {a,b}   = F1({1,2,3});  // call F1 with a {x,y,z} struct of {1,2,3};  This works.
   {a,b,c} = F2({1,2});    // call F2 with a {x,y} struct of {1,2}.  This also works.

   // Now take F2, but treat it like an F1.  (Which we should be able to do, 
   // right?  Because F2 is a subtype of F1).  Now pass it in the argument type 
   // F1 expects.  Does our assignment still work?  It does.
   {a,b} = ((F1) F2)({1,2,3});

这篇关于对函数子类型感到困惑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！