GHC是否使用存在类型的动态分派? [英] Does GHC use dynamic dispatch with existential types?

问题描述

下面的代码是否使用了C ++或Java所理解的动态调度?

据我了解，在最后一行，编译器可能无法在编译时知道要调用(==)的哪个实现，但是代码可以编译并产生正确的结果.有人可以解释一下，这背后是什么样的实现方式(例如vptr)?

  {-#语言存在量化#-}数据值= A整数数据ForallFunc =全部a.等式=>永远(价值-> a)unpackA(A int)= intequalTest ::值->值->ForallFunc->布尔equityTest arg1 arg2(全部拆包器)=令a1 =解包arg1a2 =解压arg2 ina1 == a2 

解决方案

大致是.

当您使用 bounded 存在量化时，即，当量化的类型变量受到某种约束时， C a =>... ，然后GHC将在构造函数中存储一些指针，记住 C a 的方法，以便以后在该构造函数上进行模式匹配时可以访问它们.

通常使用单个指针，就像在许多OOP实现中指向 vtable 的 vptr 一样.编译器也可以直接存储指向方法的指针，从而避免间接调用.我认为当类型类中只有一个方法时，这是由GHC完成的.当方法很少(例如两种)时，也可以使用它-这将使每个值的内存占用量更大，但访问速度更快.

因此，编译代码很容易，就像用 Eq 字典替换了约束，并列出了其方法一样.那就是:

 数据EqDict a = EqDict{eq :: a-> a-> Bool，新:: :: a-> a-> Bool}数据ForallFunc =全部a.Forall EqDict(值-> a)unpackA(A int)= intequalTest ::值->值->ForallFunc->布尔equalTest arg1 arg2(Forall eqDict解包器)=令a1 =解包arg1a2 =解压arg2 ineq eqDict a1 a2 

当然，通过提供所需的 == ，/= 的实现，可以粗略地编译一个构造函数调用 Forall someFunction .功能，它们的特定类型将通过存在性量化抽象出来.

Does the following bit of code use dynamic dispatch as it's understood in C++ or Java?

As I understand, at the last line, compiler cannot possibly know at compile time which implementation of (==) to call, yet the code compiles and produces correct results. Can someone please explain, what kind of implementation (vptr, for example) lies behind this?

{-# LANGUAGE ExistentialQuantification #-}

data Value = A Int

data ForallFunc = forall a. Eq a => Forall (Value -> a) 

unpackA (A int) = int

equalityTest :: Value -> Value -> ForallFunc -> Bool            
equalityTest arg1 arg2 (Forall unpacker) =
  let a1 = unpacker arg1
      a2 = unpacker arg2 in
    a1 == a2

解决方案

Roughly, yes.

When you use a bounded existential quantification, i.e. when the quantified type variable is restricted by some constraint C a => ... then GHC will store some pointer(s) inside the constructor, remembering the methods of C a so that they can be accessed later on, when you pattern match on that constructor.

Usually a single pointer is used, much like a vptr to a vtable in many OOP implementations. The compiler could also instead store the pointers to the methods directly, avoiding the indirection. I think this is done by GHC when there's only one method in the type class. It might also be used when there are very few, say two, methods -- this would make the memory footprint of each value larger, but faster to access.

So, compiling your code is rouhgly done as if the constraint is replaced with an Eq dictionary, listing its methods. That is:

data EqDict a = EqDict
   { eq  :: a->a->Bool
   , new :: a->a->Bool }

data ForallFunc = forall a. Forall EqDict (Value -> a) 

unpackA (A int) = int

equalityTest :: Value -> Value -> ForallFunc -> Bool            
equalityTest arg1 arg2 (Forall eqDict unpacker) =
  let a1 = unpacker arg1
      a2 = unpacker arg2 in
    eq eqDict a1 a2

Of course, compiling a constructor call Forall someFunction is compiled, roughly, by providing the implementation for the needed ==, /= functions, on their specific type which will be abstracted away by the existential quantification.

这篇关于GHC是否使用存在类型的动态分派?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！