haskell functional-programming dynamic-dispatch

Despacho dinámico en Haskell



functional-programming dynamic-dispatch (4)

¿Tal vez necesita una coincidencia de patrón ADT plus?

data Animal = Dog {dogName :: String} | Cat {catName :: String} | Unicorn say :: Animal -> String say (Dog {dogName = name}) = "Woof Woof, my name is " ++ name say (Cat {catName = name}) = "Meow meow, my name is " ++ name say Unicorn = "Unicorns do not talk"

Los programas escritos, por ejemplo, Java, dependen mucho del despacho dinámico. ¿Cómo se expresan dichos programas en lenguajes funcionales como Haskell? En otras palabras, ¿cuál es la forma de Haskell de expresar la idea debajo del "despacho dinámico"?

Es sorprendente la frecuencia con la que no se necesita un despacho dinámico , solo polimorfismo.

Por ejemplo, si va a escribir una función que clasifique todos los datos en una lista, quiere que sea polimórfica. (Es decir, no desea tener que volver a implementar esta función para cada tipo, a mano. Eso sería malo.) Pero en realidad no necesita nada dinámico ; usted sabe en tiempo de compilación lo que está realmente en la lista o listas que quiere ordenar. Por lo tanto, en este caso, no necesita buscar el tipo de tiempo de ejecución en absoluto.

En Haskell, si solo quieres mover cosas y no necesitas saber o importar qué tipo es, puedes usar el llamado "polimorfismo paramétrico", que es más o menos como los genéricos de Java o las plantillas de C ++. Si necesita poder aplicar una función a los datos (por ejemplo, para ordenar los datos, necesita comparaciones de órdenes), puede pasar la función para hacer eso como un argumento. Alternativamente, Haskell tiene algo parecido a una interfaz Java, y puede decir "esta función de clasificación acepta cualquier tipo de datos que implemente esta interfaz".

Hasta ahora, no hay despacho dinámico , solo estático. Tenga en cuenta también que dado que puede pasar funciones como argumentos, puede hacer el "envío" manualmente.

Si realmente necesita el despacho dinámico real, puede usar "tipos existenciales", o puede usar la biblioteca Data.Dynamic y trucos similares.

La respuesta es engañosamente simple: funciones de orden superior. Un objeto con métodos virtuales en un lenguaje OO no es más que un registro glorificado de funciones junto con algún estado local. En Haskell puede usar registros de funciones directamente y almacenar el estado local en sus cierres.

Más concretamente, un objeto OO consiste en:

  • Un puntero (vptr) a un vtable (tabla de método virtual), que contiene implementaciones para los métodos virtuales de la clase del objeto. En otras palabras, un montón de indicadores de función; un registro de funciones. En particular, cada función tiene un parámetro oculto que es el objeto en sí, que se pasa implícitamente.
  • Los datos miembros del objeto (el estado local)

Gran parte del tiempo, todo el edificio de objetos y funciones virtuales se siente como una elaborada solución para la falta de apoyo para los cierres.

Por ejemplo, considere la interfaz de Comparator de Java:

public interface Comparator<T> { int compare(T o1, T o2); // virtual (per default) }

Y supongamos que desea usarlo para ordenar una lista de cadenas basadas en los caracteres enésimo de las cadenas (suponiendo que son lo suficientemente largas). Definirías una clase:

public class MyComparator implements Comparator<String> { private final int _n; MyComparator(int n) { _n = n; } int compare(String s1, String s2) { return s1.charAt(_n) - s2.charAt(_n); } }

Y luego lo usas:

Collections.sort(myList, new MyComparator(5));

En Haskell lo harías así:

sortBy :: (a -> a -> Ordering) -> [a] -> [a] myComparator :: Int -> (String -> String -> Ordering) myComparator n = /s1 s2 -> (s1 !! n) `compare` (s2 !! n) -- n is implicitly stored in the closure of the function we return foo = sortBy (myComparator 5) myList

Si no estás familiarizado con Haskell, así es como se vería en una especie de pseudo Java: (Voy a hacer esto una vez)

public void <T> sortBy(List<T> list, Ordering FUNCTION(T, T) comparator) { ... } public (Ordering FUNCTION(String, String)) myComparator(int n) { return FUNCTION(String s1, String s2) { return s1[n].compare(s2[n]); } } public void foo() { sortBy(myList, myComparator(5)); }

Tenga en cuenta que no definimos ningún tipo. Todo lo que utilizamos son funciones. En ambos casos, la "carga útil" que pasamos a la función de clasificación fue una función que toma dos elementos y da su orden relativo. En un caso, esto se logró definiendo un tipo implementando una interfaz, implementando su función virtual de la manera apropiada y pasando un objeto de ese tipo; en el otro caso, simplemente aprobamos una función directamente. En ambos casos, almacenamos un entero interno en lo que pasamos a la función de clasificación. En un caso, esto se hizo agregando un miembro de datos privados a nuestro tipo, en el otro simplemente haciendo referencia a él en nuestra función, haciendo que se conserve en el cierre de la función.

Considere el ejemplo más elaborado de un widget con controladores de eventos:

public class Widget { public void onMouseClick(int x, int y) { } public void onKeyPress(Key key) { } public void paint() { } ... } public class MyWidget extends Widget { private Foo _foo; private Bar _bar; MyWidget(...) { _foo = something; _bar = something; } public void onMouseClick(int x, int y) { ...do stuff with _foo and _bar... } }

En Haskell podrías hacerlo así:

data Widget = Widget { onMouseClick :: Int -> Int -> IO (), onKeyPress :: Key -> IO (), paint :: IO (), ... } constructMyWidget :: ... -> IO Widget constructMyWidget = do foo <- newIORef someFoo bar <- newIORef someBar return $ Widget { onMouseClick = /x y -> do ... do stuff with foo and bar ..., onKeyPress = /key -> do ..., paint = do ... }

Note nuevamente que después del Widget inicial, no definimos ningún tipo. Solo escribimos una función para construir un registro de funciones y almacenar cosas en sus cierres. Lo cual, la mayoría de las veces, es también la única razón para definir una subclase en un idioma OO. La única diferencia con nuestro ejemplo anterior es que en lugar de una función hay múltiples, que en el caso de Java están codificadas simplemente al poner más de una función en la interfaz (y sus implementaciones), y en Haskell al pasar un registro de funciones en lugar de una sola función. (Podríamos haber pasado un registro que contiene una sola función en el ejemplo anterior, pero no tuvimos ganas).

(Vale la pena señalar que la mayoría de las veces no es necesario el envío dinámico. Si solo desea ordenar una lista según el orden predeterminado para el tipo, entonces simplemente debe usar sort :: Ord a => [a] -> [a] , que usa la instancia de Ord definida para el tipo dado, que se selecciona estáticamente).

Despacho dinámico basado en el tipo

Una diferencia entre el enfoque de Java y el anterior de Haskell es que con el enfoque de Java, el comportamiento de un objeto (a excepción de su estado local) está determinado por su tipo (o menos caritativamente, cada implementación requiere un nuevo tipo). En Haskell estamos haciendo nuestros registros de funciones de la manera que queramos. La mayoría de las veces esto es una victoria pura (flexibilidad ganada, nada perdido), pero supongamos que por algún motivo lo queremos de la manera Java. En ese caso, el camino a seguir, como se menciona en otras respuestas, es clases de tipos y existenciales.

Para continuar con nuestro ejemplo de Widget , supongamos que queremos que siga la implementación de un Widget de su tipo (para requerir un nuevo tipo para cada implementación). Definimos una clase de tipo para asignar el tipo a su implementación:

-- the same record as before, we just gave it a different name data WidgetImpl = WidgetImpl { onMouseClick :: Int -> Int -> IO (), onKeyPress :: Key -> IO (), paint :: IO (), ... } class IsWidget a where widgetImpl :: a -> WidgetImpl data Widget = forall a. IsWidget a => Widget a sendClick :: Int -> Int -> Widget -> IO () sendClick x y (Widget a) = onMouseClick (widgetImpl a) x y data MyWidget = MyWidget { foo :: IORef Foo, bar :: IORef Bar } constructMyWidget :: ... -> IO MyWidget constructMyWidget = do foo_ <- newIORef someFoo bar_ <- newIORef someBar return $ MyWidget { foo = foo_, bar = bar_ } instance IsWidget MyWidget where widgetImpl myWidget = WidgetImpl { onMouseClick = /x y -> do ... do stuff with (foo myWidget) and (bar myWidget) ..., onKeyPress = /key -> do ..., paint = do ... }

Es un poco incómodo que tengamos una clase solo para obtener un registro de las funciones, que luego tenemos que quitar las funciones por separado. Solo lo hice de esta manera para ilustrar aspectos separados de clases de tipos: también son solo registros glorificados de funciones (que usamos a continuación) junto con algo de magia donde el compilador inserta el registro apropiado basado en el tipo inferido (que usamos arriba y continúe usando a continuación). Simplifiquemos

class IsWidget a where onMouseClick :: Int -> Int -> a -> IO () onKeyPress :: Key -> a -> IO () paint :: a -> IO () ... instance IsWidget MyWidget where onMouseClick x y myWidget = ... do stuff with (foo myWidget) and (bar myWidget) ... onKeyPress key myWidget = ... paint myWidget = ... sendClick :: Int -> Int -> Widget -> IO () sendClick x y (Widget a) = onMouseClick x y a -- the rest is unchanged from above

Este estilo a menudo lo adoptan las personas que provienen de los lenguajes de OO, porque es más familiar y más cercano a un mapeo de uno a uno por la forma en que lo hacen los lenguajes de OO. Pero para la mayoría de los propósitos, es más elaborado y menos flexible que el enfoque descrito en la primera sección. La razón es que si lo único significativo de los diversos widgets es la forma en que implementan las funciones de widgets, entonces no tiene sentido hacer tipos, instancias de la interfaz para esos tipos y luego abstraer el tipo subyacente de nuevo al ponerlos en una envoltura existencial: es más sencillo pasar las funciones directamente.

Una ventaja que se me ocurre es que, aunque Haskell no tiene subtipado, tiene "subclases" (probablemente mejor referido como subinterfaz o subconstricción). Por ejemplo, podrías hacer:

class IsWidget a => IsWidgetExtra a where ...additional methods to implement...

y luego con cualquier tipo para el que tenga IsWidgetExtra , también puede usar los métodos de IsWidget sin problemas. La única alternativa con el enfoque basado en registros es tener registros dentro de los registros, lo que implica un ajuste manual y desenvolver los registros internos. Pero esto solo sería ventajoso si quisieras emular explícitamente la jerarquía de clases profundas de un lenguaje OO, que a su vez solo harías si quisieras complicarte la vida. (Tenga en cuenta también que Haskell no tiene ninguna forma incorporada de IsWidget dinámicamente desde IsWidget a IsWidgetExtra . Pero existe ifcxt )

(¿Qué pasa con las ventajas del enfoque basado en registros? Además de no tener que definir un nuevo tipo cada vez que quiera hacer algo nuevo, los registros son simples cosas de nivel de valor, y los valores son mucho más fáciles de manipular que los tipos. Podría , por ejemplo, escribe una función que toma un Widget como argumento y crea un Widget nuevo basado en él, con algunas cosas diferentes y otras igual. Esto es algo así como la creación de subclases de un parámetro de plantilla en C ++, apenas menos confuso. )

Glosario

  • Función de orden superior: una función que toma otras funciones como argumentos (o las devuelve como resultados)

  • Grabar: struct (clase con miembros de datos públicos y nada más). También conocido como un diccionario.

  • Cierre: los lenguajes funcionales (y muchos otros) le permiten definir funciones locales (funciones dentro de funciones, lambdas) que hacen referencia a cosas en el alcance en el sitio de definición (por ejemplo, los argumentos de la función externa) que usted normalmente esperaría para mantenerse cerca, pero están, en el "cierre" de la función. Alternativamente, si tiene una función como plus que toma dos ints y devuelve un int, puede aplicarlo a un solo argumento, digamos 5 , y el resultado será una función que toma un int y devuelve un int, agregando 5 a it - en ese caso, el 5 también se almacena en el cierre de la función resultante. (En otros contextos, "cierre" también se usa a veces para indicar "una función con cierre").

  • Tipo de clase: no es lo mismo que una clase en un idioma OO. Algo así como una interfaz, pero también muy diferente. Mira aquí .

EDITAR 29-11-14: Aunque creo que el kernel de esta respuesta sigue siendo esencialmente correcto (los HOF en Haskell corresponden a los métodos virtuales en OOP), mis juicios de valor han crecido un poco desde que lo escribí. En particular, ahora creo que ni el enfoque de Haskell ni el de OOP es estrictamente "más fundamental" que el otro. Vea este comentario de reddit .