29

当我第一次学习 Haskell 时，我很快就喜欢上了参数多态。这是一个令人愉快的简单想法，效果非常好。整个“如果它编译它通常工作正常”的事情主要是由于参数多态性，恕我直言。

但是前几天，我发生了一些事情。我可以写成foo一个多态函数。但是当bar调用时foo，它会使用一组特定的参数类型。或者，如果bar它本身是多态的，那么它的调用者将分配明确的类型。通过归纳，似乎如果您要使用任何有效的 Haskell 程序并分析整个代码库，您就可以静态地确定整个程序中每个事物的类型。

从某种意义上说，这有点像 C++ 模板。没有运行时多态，只有编译时多态。Haskell 编译器可以选择为调用每个多态函数的每种类型生成单独的机器代码。大多数 Haskell 编译器没有，但如果你愿意，你可以实现一个。

只有当你开始添加 Haskell 扩展（ExistentialQuantification很明显）时，你才会开始获得真正的运行时多态性，其中你的值的类型不能被静态计算。

哦，是的，我的问题？

  1. 上面的说法真的正确吗？

  2. 这个属性有一个广泛使用的名称吗？

4

3 回答 3

31

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]]，依此类推。

如果禁止多态递归，那么我相信可以对程序进行静态特化。

于 2012-05-10T14:00:54.470 回答
14

是的，我也想过这个问题。基本上，这个想法是你似乎可以实现 Haskell 98，但不能实现它的一些语言扩展，使用多态多实例化而不是多态多态。

您可以通过尝试将一些 Haskell 功能实现为 C++ 库来对此有所了解（正如您所注意到的，C++ 执行多态化多态化）。你发现你可以做 Haskell 能做的所有事情，除了不可能有多态值，包括对多态函数的引用。

这看起来像，如果你有

template<typename T>
void f(T);           // f :: a -> IO ()

您可以在运行时将特定实例化的地址作为函数指针传递：

&f<int>

但您不能获取模板的地址 ( &f)。这是有道理的：模板是纯粹的编译时构造。同样有意义的是，如果您通过多实例化进行多态性，则可以拥有指向任何特定实例化的指针，但不能拥有指向多态函数本身的指针，因为在机器代码级别，没有一个。

那么 Haskell 在哪里使用多态值呢？乍一看，一个好的经验法则似乎是“任何地方你必须写一个明确的 forall”。所以PolymorphicComponents, Rank2Types, RankNTypes, 和ImpredicativeTypes是明显的禁忌。你不能把它翻译成 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 中有什么是你不能实现的吗？从您甚至需要语言扩展 ( ) 来编写 forall 的事实来看ExplicitForAll，您会认为答案是否定的。你几乎是对的，但有两个问题：类型类和多态递归。类型类通常使用字典传递来实现：每个实例声明都会产生一个函数记录，这些函数会在需要它们的地方隐式传递。

因此，例如，对于 Monad，您将拥有：

data MonadDict m = MonadDict { 
    return :: forall a. a -> m a,
    (>>=)  :: forall a b. m a -> (a -> m b) -> m b
}

那么你会看看那些foralls！您不能明确地编写它们，但是在字典传递实现中，即使在 Haskell 98 中，具有多态方法的类会导致包含多态函数的记录。如果您尝试使用多实例来实现整个事情，这显然会成为一个问题。您几乎可以不用字典传递就可以逃脱，因为如果您坚持使用 Haskell 98，实例几乎总是全局且静态已知的。每个实例都会产生一些多态函数，但是因为在编译时几乎总是知道要调用哪个函数，所以您几乎不需要在运行时传递对它们的引用（这很好，因为您不能）。权衡是您需要进行整个程序编译，否则实例不再是静态已知的：他们可能在不同的模块中。一个例外是多态递归，它实际上需要你在运行时建立一个字典。见其他答案以获取更多详细信息。即使没有类型类，多态递归也会杀死多实例化方法：请参阅关于BTrees 的评论。（此外ExistentialQuantification，具有多态方法的 *plus* 类不再可行，因为您将不得不再次开始存储指向多态函数的指针。）

于 2012-05-10T16:03:25.197 回答
8

正如您在上面所描述的，整个程序编译器利用对类型信息的全局访问来进行非常积极的优化。示例包括JHC和MLton。出于类似的原因，具有内联的 GHC 也是部分“整个程序”。其他利用全局信息的技术包括超级编译。

请注意，您可以通过将多态函数专门用于它们所使用的所有类型来大幅增加代码大小——这需要大量内联以将代码减少回正常值。管理这一点是一项挑战。

于 2012-05-10T13:28:32.057 回答