静态类型，多态和专业化 [英] Static types, polymorphism and specialization

问题描述

当我第一次了解Haskell时，我很快就喜欢参数多态。这是一个非常简单的想法，效果惊人。整个如果它编译它通常是正确的事情主要是由于参数多态性，恕我直言。

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

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

c $ c>是显而易见的）你是否开始获得真正的 run-time 多态性，其中有值的谁的类型不能被静态计算。

哦，是的，我的问题？

1. 以上陈述是否正确？




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

Haskell（没有扩展名）允许多态递归，并且这个特性本身使得静态地将一个程序专门化为一个完全单形的程序是不可能的。这是一个打印N深嵌套列表的程序，其中N是一个命令行参数：



  import System 
 
 foo ::显示a => Int  - > a  - > IO（）
 foo 0 x = print x 
 foo nx = foo（n-1）[x] 
 
 main = do [num_lists]<  -  getArgs 
第一次调用 foo   

code>， a 的类型为 Int 。在下一个递归调用中，它的类型是 [Int] ，然后是 [[Int]] ，依此类推。





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




When I first learned Haskell, I very quickly came to love parametric polymorphism. It's a delightfully simple idea that works astonishingly well. The whole "if it compiles it usually works right" thing is mostly due to parametric polymorphism, IMHO.

But the other day, something occurred to me. I can write foo as a polymorphic function. But when bar calls foo, it will do so with a specific set of argument types. Or, if bar itself is polymorphic, then its caller will assign definite types. By induction, it seems that if you were to take any valid Haskell program and analyse the entire codebase, you can statically determine the type of every single thing in the entire program.

This, in a sense, is a bit like C++ templates. There is no run-time polymorphism, only compile-time polymorphism. A Haskell compiler could choose to generate separate machine code for every type at which each polymorphic function is called. Most Haskell compilers don't, but you could implement one if you wanted to.

Only if you start adding Haskell extensions (ExistentialQuantification is the obvious one) do you start to get real run-time polymorphism, where you have values who's type cannot be statically computed.

Oh, yeah, my question?

1. Are the statements above actually correct?

2. Is there a widely-used name for this property?

解决方案

Haskell (with no extensions) permits polymorphic recursion, and this feature alone makes it impossible to statically specialize a program to a completely monomorphic one. Here is a program that will print an N-deep nested list, where N is a command-line parameter:

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

In the first call to foo, a has type Int. In the next recursive call, it has type [Int], then [[Int]], and so forth.

If polymorphic recursion is prohibited, then I believe it's possible to statically specialize a program.

这篇关于静态类型，多态和专业化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！