haskell - qué - lenguajes fuertemente y débilmente tipados

Tipos estáticos, polimorfismo y especialización.

Question

Cuando aprendí Haskell por primera vez, me enamoré rápidamente del polimorfismo paramétrico. Es una idea deliciosamente simple que funciona sorprendentemente bien. Todo el asunto de "si compila generalmente funciona bien" se debe principalmente al polimorfismo paramétrico, IMHO.

Pero el otro día, algo se me ocurrió. Puedo escribir foo como una función polimórfica. Pero cuando la bar llama a foo , lo hará con un conjunto específico de tipos de argumentos. O, si la bar sí es polimórfica, su llamador asignará tipos definidos. Por inducción, parece que si tomara cualquier programa de Haskell válido y analizara la base de código completa , puede determinar estáticamente el tipo de cada cosa en todo el programa.

Esto, en cierto sentido, es un poco como las plantillas de C ++. No hay polimorfismo en tiempo de ejecución , solo polimorfismo en tiempo de compilación . Un compilador de Haskell podría elegir generar un código de máquina separado para cada tipo al que se llama cada función polimórfica. La mayoría de los compiladores de Haskell no lo hacen, pero podrías implementar uno si quisieras.

Solo si comienza a agregar extensiones de Haskell ( ExistentialQuantification es la más obvia), comienza a obtener un polimorfismo real en tiempo de ejecución , donde tiene valores cuyo tipo no se puede calcular de manera estática.

Oh, sí, mi pregunta?

1. ¿Son las afirmaciones anteriores realmente correctas?

2. ¿Hay un nombre ampliamente utilizado para esta propiedad?

Answer 1

Haskell (sin extensiones) permite la recursión polimórfica, y esta característica por sí sola hace que sea imposible especializar estáticamente un programa a uno completamente monomórfico. Aquí hay un programa que imprimirá una lista anidada N-deep, donde N es un parámetro de línea de comando:

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

En la primera llamada a foo , a tiene tipo Int . En la siguiente llamada recursiva, tiene el tipo [Int] , luego [[Int]] , etc.

Si la recursión polimórfica está prohibida, entonces creo que es posible especializar estáticamente un programa.

Answer 2

Sí, he pensado en esto también. Básicamente, la idea es que parece que podrías implementar Haskell 98, pero no algunas de las extensiones de lenguaje para él, usando polimorfismo por multiinstanciación en lugar de polimorfismo por boxeo.

Puede obtener una idea de esto al tratar de implementar algunas características de Haskell como bibliotecas de C ++ (como se nota, C ++ hace polimorfismo por multiinstalación). Lo que encuentras es que puedes hacer todo lo que Haskell puede hacer, excepto que es imposible tener valores polimórficos, que incluyen referencias a funciones polimórficas.

Lo que parece es que si tienes

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

puede tomar la dirección de una instanciación particular para pasar como un puntero de función en tiempo de ejecución:

&f<int>

pero no puede tomar la dirección de una plantilla ( &f ). Esto tiene sentido: las plantillas son una construcción puramente en tiempo de compilación. También tiene sentido que si está haciendo polimorfismo por multiinstanciación, puede tener un puntero a cualquier instancia en particular, pero no puede tener un puntero a la función polimórfica en sí, porque a nivel de código de máquina, no hay ninguna.

Entonces, ¿dónde utiliza Haskell los valores polimórficos? A primera vista, parece que una buena regla general es "en cualquier lugar en el que tenga que escribir un forall explícito". Por lo tanto, los Rank2Types PolymorphicComponents , los Rank2Types , los RankNTypes y los ImpredicativeTypes son obvios. No puedes traducir esto a C ++:

data MkList = MkList (forall a. a -> [a])
singleton = MkList (/x -> [x])

Por otro lado, ExistentialQuantification es factible en al menos algunos casos: significa tener una clase sin plantilla con un constructor de plantilla (o más generalmente, una clase cuyo constructor está basado en más cosas que la clase en sí).

Si en Haskell tienes:

data SomeShow = forall a. Show a => SomeShow a
instance Show SomeShow where show (SomeShow a) = show a

Puedes implementar esto en C ++ como:

// 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();
}

En ambos idiomas tiene un tipo no polimórfico con un constructor polimórfico.

Así que hemos demostrado que hay algunas extensiones de lenguaje que puedes implementar y otras que no, pero ¿qué hay del otro lado de la moneda: hay algo en Haskell 98 que no puedes implementar? A juzgar por el hecho de que necesita una extensión de lenguaje ( ExplicitForAll ) para incluso escribir un forall, usted pensaría que la respuesta es no. Y casi tendrías razón, pero hay dos arrugas: clases de tipos y recursión polimórfica. Las clases de tipo se implementan normalmente mediante el uso de pases de diccionarios: cada declaración de instancia genera un registro de funciones, que se transfieren implícitamente donde sea necesario.

Entonces para Monad, por ejemplo, tendrías:

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

Bueno, ¿podrías mirar esos foralls? No se pueden escribir explícitamente, pero en las implementaciones de pases de diccionarios, incluso en Haskell 98, las clases con métodos polimórficos dan como resultado registros que contienen funciones polimórficas. Lo que si intentas implementar todo usando el multiinstantion obviamente será un problema. Casi puede escapar sin pasar el diccionario porque, si se adhiere a Haskell 98, las instancias son casi siempre globales y estáticamente conocidas. Cada instancia da como resultado algunas funciones polimórficas, pero dado que la llamada de una llamada casi siempre se conoce en el momento de la compilación, casi nunca es necesario pasar referencias a ellas en tiempo de ejecución (lo cual es bueno, porque no se puede). La desventaja es que necesita hacer una compilación de todo el programa, porque de lo contrario las instancias ya no se conocen de forma estática: podrían estar en un módulo diferente. Y la excepción es la recursión polimórfica, que prácticamente requiere que construyas un diccionario en tiempo de ejecución. Vea la otra respuesta para más detalles sobre eso. La recursión polimórfica mata el enfoque de multiinstanciación incluso sin clases de tipo: vea el comentario sobre BTree s. (También las clases ExistentialQuantification * plus * con métodos polimórficos ya no son factibles, ya que tendrías que comenzar a almacenar nuevamente los punteros a las funciones polimórficas).

Answer 3

Los compiladores de todo el programa aprovechan el acceso global a la información de tipo para realizar optimizaciones muy agresivas, como se describe anteriormente. Los ejemplos incluyen JHC y MLton . GHC con inline es también parcialmente "programa completo", por razones similares. Otras técnicas que aprovechan la información global incluyen la súper compilación .

Tenga en cuenta que puede aumentar enormemente el tamaño del código al especializar las funciones polimórficas en todos los tipos en los que se utilizan; esto requiere una fuerte incorporación para reducir el código a los valores normales. Manejar esto es un reto.