我通读了维基百科上关于存在类型的文章。我认为它们之所以被称为存在类型是因为存在操作符(∃)。但我不知道这有什么意义。有什么区别

T = ∃X { X a; int f(X); }

and

T = ∀x { X a; int f(X); }

?


当前回答

似乎我来晚了一点,但无论如何,这篇文档增加了关于存在类型是什么的另一种观点,尽管不是特别的语言不可知,这样应该更容易理解存在类型:http://www.cs.uu.nl/groups/ST/Projects/ehc/ehc-book.pdf(第8章)

The difference between a universally and existentially quantified type can be characterized by the following observation: The use of a value with a ∀ quantified type determines the type to choose for the instantiation of the quantified type variable. For example, the caller of the identity function “id :: ∀a.a → a” determines the type to choose for the type variable a for this particular application of id. For the function application “id 3” this type equals Int. The creation of a value with a ∃ quantified type determines, and hides, the type of the quantified type variable. For example, a creator of a “∃a.(a, a → Int)” may have constructed a value of that type from “(3, λx → x)”; another creator has constructed a value with the same type from “(’x’, λx → ord x)”. From a users point of view both values have the same type and are thus interchangeable. The value has a specific type chosen for type variable a, but we do not know which type, so this information can no longer be exploited. This value specific type information has been ‘forgotten’; we only know it exists.

其他回答

我画了这个图。我不知道它是否严谨。但如果有帮助的话,我很高兴。

Research into abstract datatypes and information hiding brought existential types into programming languages. Making a datatype abstract hides info about that type, so a client of that type cannot abuse it. Say you've got a reference to an object... some languages allow you to cast that reference to a reference to bytes and do anything you want to that piece of memory. For purposes of guaranteeing behavior of a program, it's useful for a language to enforce that you only act on the reference to the object via the methods the designer of the object provides. You know the type exists, but nothing more.

看到的: 抽象类型有存在类型,MITCHEL和PLOTKIN http://theory.stanford.edu/~jcm/papers/mitch-plotkin-88.pdf

当有人定义一个通用类型∀X时,他们是在说:你可以插入任何你想要的类型,我不需要知道任何类型来完成我的工作,我只会不透明地将它称为X。

当有人定义存在类型∃X时,他们在说:我将在这里使用我想要的任何类型;你不会知道任何关于类型的信息,所以你只能模糊地把它称为X。

通用类型让你可以这样写:

void copy<T>(List<T> source, List<T> dest) {
   ...
}

复制函数不知道T是多少,但它不需要知道。

存在类型可以让你这样写:

interface VirtualMachine<B> {
   B compile(String source);
   void run(B bytecode);
}

// Now, if you had a list of VMs you wanted to run on the same input:
void runAllCompilers(List<∃B:VirtualMachine<B>> vms, String source) {
   for (∃B:VirtualMachine<B> vm : vms) {
      B bytecode = vm.compile(source);
      vm.run(bytecode);
   }
}

列表中的每个虚拟机实现都可以有不同的字节码类型。runAllCompilers函数不知道字节码类型是什么,但它不需要知道;它所做的就是将字节码从VirtualMachine.compile传递到VirtualMachine.run。

Java类型通配符(例如:List<?>)是存在类型的一种非常有限的形式。

更新:忘了说你可以用通用类型来模拟存在类型。首先,包装通用类型以隐藏类型参数。第二,反向控制(这有效地交换了上面定义中的“你”和“我”部分,这是存在和共相之间的主要区别)。

// A wrapper that hides the type parameter 'B'
interface VMWrapper {
   void unwrap(VMHandler handler);
}

// A callback (control inversion)
interface VMHandler {
   <B> void handle(VirtualMachine<B> vm);
}

现在,我们可以让VMWrapper调用我们自己的VMHandler,它有一个通用类型的句柄函数。最终效果是一样的,我们的代码必须将B视为不透明的。

void runWithAll(List<VMWrapper> vms, final String input)
{
   for (VMWrapper vm : vms) {
      vm.unwrap(new VMHandler() {
         public <B> void handle(VirtualMachine<B> vm) {
            B bytecode = vm.compile(input);
            vm.run(bytecode);
         }
      });
   }
}

虚拟机实现示例:

class MyVM implements VirtualMachine<byte[]>, VMWrapper {
   public byte[] compile(String input) {
      return null; // TODO: somehow compile the input
   }
   public void run(byte[] bytecode) {
      // TODO: Somehow evaluate 'bytecode'
   }
   public void unwrap(VMHandler handler) {
      handler.handle(this);
   }
}

似乎我来晚了一点,但无论如何,这篇文档增加了关于存在类型是什么的另一种观点,尽管不是特别的语言不可知,这样应该更容易理解存在类型:http://www.cs.uu.nl/groups/ST/Projects/ehc/ehc-book.pdf(第8章)

The difference between a universally and existentially quantified type can be characterized by the following observation: The use of a value with a ∀ quantified type determines the type to choose for the instantiation of the quantified type variable. For example, the caller of the identity function “id :: ∀a.a → a” determines the type to choose for the type variable a for this particular application of id. For the function application “id 3” this type equals Int. The creation of a value with a ∃ quantified type determines, and hides, the type of the quantified type variable. For example, a creator of a “∃a.(a, a → Int)” may have constructed a value of that type from “(3, λx → x)”; another creator has constructed a value with the same type from “(’x’, λx → ord x)”. From a users point of view both values have the same type and are thus interchangeable. The value has a specific type chosen for type variable a, but we do not know which type, so this information can no longer be exploited. This value specific type information has been ‘forgotten’; we only know it exists.

类型参数的所有值都存在一个通用类型。存在类型仅适用于满足存在类型约束的类型参数值。

例如,在Scala中,表示存在类型的一种方法是抽象类型,它被限制在某个上界或下界。

trait Existential {
  type Parameter <: Interface
}

同样,受约束的通用类型是存在类型,如下例所示。

trait Existential[Parameter <: Interface]

任何使用站点都可以使用接口,因为存在的任何可实例化子类型必须定义必须实现接口的类型Parameter。

在Scala中,存在类型的退化情况是一种抽象类型,它永远不会被引用,因此不需要由任何子类型定义。这在Scala中有效地简化了List[_]和List<?Java中的>。

我的回答受到Martin Odersky关于统一抽象类型和存在类型的建议的启发。随附的幻灯片有助于理解。