静态类型,多态性和专业化

Question

当我第一次学习Haskell时,我很快就开始喜欢参数多态.这是一个令人愉快的简单想法,工作得非常好.整个"如果它编译它通常工作正常"的事情主要是由于参数多态,恕我直言.

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

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

只有当你开始添加Haskell扩展(ExistentialQuantification显而易见的是)时,你才开始获得真正的运行时多态性,你可以在其中获得无法静态计算类型的值.

哦,是的,我的问题？

1. 以上陈述是否真的正确？

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

Answer 1

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]]等等.

如果禁止多态递归,那么我相信可以静态地专门化一个程序.

Answer 2

是的,我也考虑过这一点.基本上,这个想法似乎是你可以实现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任何东西,你无法实现？从你需要一个语言扩展(ExplicitForAll)甚至写一个forall 的事实判断,你会认为答案是否定的.你几乎是对的,但有两个皱纹:类型类和多态递归.类型类通常使用字典传递来实现:每个实例声明都会生成一个函数记录,这些函数会在需要的地方隐式传递.

所以对Monad来说,你会有:

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

那你看那些野蛮人吧!你不能显式地编写它们,但是在字典传递实现中,即使在Haskell 98中,具有多态方法的类也会产生包含多态函数的记录.如果你试图使用多功能实现整个事情显然会成为一个问题.你几乎可以在没有字典传递的情况下逃脱,因为如果你坚持使用Haskell 98,实例几乎总是全局的并且是静态的.每个实例都会产生一些多态函数,但是因为在编译时几乎总是知道调用哪个函数,所以几乎不需要在运行时传递对它们的引用(这很好,因为你不能).权衡是您需要进行整个程序编译,因为否则实例不再是静态知道的:它们可能位于不同的模块中.异常是多态递归,它实际上要求您在运行时构建字典.有关详细信息,请参阅其他答案.即使没有类型类,多态递归也会杀死多实例化方法:请参阅有关BTrees 的注释.(另外ExistentialQuantification*plus*带有多态方法的类不再可行,因为你必须再次开始存储指向多态函数的指针.)

Answer 3

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

请注意,您可以通过在他们使用的所有类型上专门化多态函数来大规模增加代码大小 - 然后需要大量内联将代码减少回正常值.管理这是一项挑战.