静态类型，多态和专业化
当我第一次了解Haskell时，我很快就喜欢参数多态。 这是一个非常简单的想法，效果惊人。 整个“如果它编译它通常工作正常”的事情主要是由于参数多态性，恕我直言。
但有一天，我发生了一些事情。 我可以将foo写成多态函数。 但是当bar调用foo ，它会使用一组特定的参数类型。 或者，如果bar本身是多态的，那么它的调用者将分配确定的类型。 通过归纳，看起来如果您要采用任何有效的Haskell程序并分析整个代码库，您可以静态确定整个程序中每一件事的类型。
这在某种意义上，有点像C ++模板。 没有运行时多态，只有编译时多态。 Haskell编译器可以选择为每个类型生成单独的机器代码，每个类型都调用每个多态函数。 大多数Haskell编译器不会，但是如果你愿意，你可以实现一个。
只有当你开始添加Haskell扩展（ ExistentialQuantification是显而易见的扩展），你是否开始获得真正的运行时多态，在那里你有值的谁的类型不能静态计算。
哦，是的，我的问题？
上述表述是否正确？
这个属性是否有广泛使用的名称？
Haskell（没有扩展名）允许多态递归，并且这个特性本身使得静态地将程序专门化为完全单形的程序是不可能的。 这是一个打印N层嵌套列表的程序，其中N是一个命令行参数：
import System
foo :: Show a => Int -> a -> IO ()
foo 0 x = print x
foo n x = foo (n-1) [x]
main = do [num_lists] <- getArgs
foo (read num_lists) 0
在第一次调用foo ， a类型为Int 。 在下一次递归调用中，它具有类型[Int] ，然后是[[Int]] ，等等。
如果禁止多态递归，那么我相信可以静态地专门化一个程序。
是的，我也想过这个。 基本上，这个想法是，你似乎可以实现Haskell 98，但不是它的一些语言扩展，使用多态多种实例而不是多元逐个装箱。
通过尝试将一些Haskell特性实现为C ++库（如您注意到的，C ++可以实现多态多工），您可以了解这一点。 你发现你可以做Haskell可以做的所有事情，除了不可能有多态值，其中包括多态函数的引用。
这看起来像是如果你有
template<typename T>
void f(T); // f :: a -> IO ()
您可以将特定实例的地址作为函数指针在运行时传递：
&f<int>
但你无法获取模板的地址（ &f ）。 这是有道理的：模板是纯粹的编译时构造。 同样有意义的是，如果你通过多实例化来实现多态，你可以有一个指向任何特定实例的指针，但是你不能有一个指向多态函数本身的指针，因为在机器代码级别上没有指针。
那么Haskell在哪里使用多态值？ 乍一看，似乎一个好的经验法则是“任何地方你必须写明确书面”。 所以PolymorphicComponents ， Rank2Types ， RankNTypes和ImpredicativeTypes是显而易见的no-nos。 你不能把它翻译成C ++：
data MkList = MkList (forall a. a -> [a])
singleton = MkList (x -> [x])
另一方面， ExistentialQuantification至少在某些情况下是可行的：它意味着拥有一个带有模板构造函数的非模板类（或者更一般地说，是一个构造函数的模板比类本身更多的类）。
如果在Haskell中你有：
data SomeShow = forall a. Show a => SomeShow a
instance Show SomeShow where show (SomeShow a) = show a
你可以在C ++中实现：
// a function which takes a void*, casts it to the given type, and
// calls the appropriate show() function (statically selected based
// on overload resolution rules)
template<typename T>
String showVoid(void *x)
{
show(*(T*)x);
}
class SomeShow
{
private:
void *m_data;
String (*m_show)(void*); // m_show :: Any -> String
public:
template<typename T>
SomeShow(T x)
: m_data(new T(x)) // memory management issues here, but that's orthogonal
, m_show(&showVoid<T>)
{
}
String show()
{
// alternately we could declare the top-level show() as a friend and
// put this there
return m_show(m_data);
}
};
// C++ doesn't have type classes per se, but it has overloading, which means
// that interfaces are implicit: where in Haskell you would write a class and
// instances, in C++ you just write a function with the same name for each type
String show(SomeShow x)
{
return x.show();
}
在这两种语言中，您都有一个带多态构造函数的非多态类型。
所以我们已经证明，你可以实现一些语言扩展，有些你不能，但硬币的另一面呢：Haskell 98中有什么是你无法实现的？ 根据你需要语言扩展（ ExplicitForAll ）甚至写入全部的事实来判断，你会认为答案是否定的。 你几乎是正确的，但有两个折痕：类型和多态递归。 类型类通常使用字典传递来实现：每个实例声明都会生成一个函数记录，这些函数会在需要的地方隐式传递。
因此，对于Monad来说，您可能会：
data MonadDict m = MonadDict {
return :: forall a. a -> m a,
(>>=) :: forall a b. m a -> (a -> m b) -> m b
}
那么你会看看那些争吵！ 你不能明确地写出它们，但是在字典传递实现中，即使在Haskell 98中，具有多态方法的类也会导致包含多态函数的记录。 如果你试图用multiinstantion实现整个事情显然会成为一个问题。 如果你坚持使用Haskell 98，那么你几乎可以在没有字典传递的情况下离开，实例几乎总是全局的并且是静态的。 每个实例都会导致一些多态函数，但是由于在编译时几乎总是知道要调用哪一个函数，所以几乎不需要在运行时将它们传递给它们（这很好，因为你不能）。 权衡是你需要进行全程序编译，因为否则实例不再是静态已知的：它们可能位于不同的模块中。 多态递归是个例外，它实际上要求你在运行时建立一个字典。 有关更多详情，请参阅其他答案。 即使没有类型类型，多态递归也会杀死多实例方法：请参阅有关BTree的注释。 （另外ExistentialQuantification * plus *具有多态方法的类不再可行，因为您将不得不再次开始存储指向多态函数的指针。）
如上所述，整个程序编译器利用全局访问类型信息进行非常积极的优化。 例子包括JHC和MLton。 带有内联的GHC也是部分“整个程序”，原因类似。 其他利用全球信息的技术还包括超级编译。
请注意，您可以通过在所有类型中专门使用多态函数来大幅增加代码大小 - 然后需要大量内联以将代码还原为正常值。 管理这是一个挑战。
链接地址: http://www.djcxy.com/p/43207.html