Despacho dinámico

En informática , el despacho dinámico es el proceso de seleccionar qué implementación de una operación polimórfica ( método o función) se debe llamar en tiempo de ejecución . Se emplea comúnmente en lenguajes y sistemas de programación orientada a objetos (POO) y se considera una característica fundamental de los mismos . ^{[ 1 ]}

Los sistemas orientados a objetos modelan un problema como un conjunto de objetos que interactúan y ejecutan operaciones identificadas por su nombre. El polimorfismo es el fenómeno por el cual objetos que son, en cierta medida, intercambiables, exponen una operación con el mismo nombre, pero que posiblemente difiere en su comportamiento. Por ejemplo, tanto un objeto File como un objeto Database tienen un método StoreRecord que se puede usar para escribir un registro de personal en el almacenamiento. Sus implementaciones difieren. Un programa mantiene una referencia a un objeto que puede ser un objeto File o un objeto Database . El tipo de objeto puede haber sido determinado por una configuración en tiempo de ejecución, y en esta etapa, el programa puede desconocerlo o no importarle. Cuando el programa llama a StoreRecord en el objeto, algo debe elegir qué comportamiento se ejecuta. Si se piensa en la POO como el envío de mensajes a objetos, entonces en este ejemplo el programa envía un mensaje StoreRecord a un objeto de tipo desconocido, dejando que el sistema de soporte en tiempo de ejecución distribuya el mensaje al objeto correcto. El objeto ejecuta el comportamiento que implementa. ^[²^]

El despacho dinámico contrasta con el despacho estático , en el que la implementación de una operación polimórfica se selecciona en tiempo de compilación . El propósito del despacho dinámico es aplazar la selección de una implementación apropiada hasta que se conozca el tipo en tiempo de ejecución de un parámetro (o varios parámetros).

El despacho dinámico es diferente del enlace tardío (también conocido como enlace dinámico). El enlace por nombre asocia un nombre a una operación. Una operación polimórfica tiene varias implementaciones, todas asociadas al mismo nombre. Los enlaces pueden realizarse en tiempo de compilación o (con enlace tardío) en tiempo de ejecución. Con el despacho dinámico, se elige una implementación particular de una operación en tiempo de ejecución. Si bien el despacho dinámico no implica enlace tardío, el enlace tardío sí implica despacho dinámico, ya que la implementación de una operación de enlace tardío no se conoce hasta el tiempo de ejecución.

Mecanismos

Envío único y múltiple

La elección de qué versión de un método llamar puede basarse en un solo objeto o en una combinación de objetos. El primero se llama despacho único y es compatible directamente con lenguajes orientados a objetos comunes como Smalltalk , C++ , Java , C# , Objective-C , Swift , JavaScript y Python . En estos y otros lenguajes similares, se puede llamar a un método para la división con una sintaxis que se asemeja a

dividendo . dividir ( divisor ) # dividendo / divisor

donde los parámetros son opcionales. Esto se entiende como enviar un mensaje llamado "divide" con el parámetro "dividendo" al dividendo . Se elegirá una implementación basándose únicamente en el tipo de dividendo (quizás racional , de punto flotante , matricial ), sin tener en cuenta el tipo o valor del divisor .

Por el contrario, algunos lenguajes asignan métodos o funciones según la combinación de operandos; en el caso de la división, los tipos del dividendo y del divisor determinan qué operación de división se realizará. Esto se conoce como despacho múltiple . Ejemplos de lenguajes que admiten despacho múltiple son Common Lisp , Dylan y Julia .

Mecanismos de despacho dinámico

Un lenguaje puede implementarse con diferentes mecanismos de despacho dinámico. Las opciones de mecanismos de despacho dinámico que ofrece un lenguaje modifican en gran medida los paradigmas de programación disponibles o más naturales para usar dentro de ese lenguaje.

Normalmente, en un lenguaje tipado, el mecanismo de despacho se basa en el tipo de los argumentos (generalmente en el tipo del receptor del mensaje). Los lenguajes con sistemas de tipado débiles o inexistentes suelen incluir una tabla de despacho como parte de los datos de cada objeto. Esto permite un comportamiento de instancia, ya que cada instancia puede asignar un mensaje determinado a un método independiente.

Algunos idiomas ofrecen un enfoque híbrido.

El despacho dinámico siempre conlleva una sobrecarga, por lo que algunos lenguajes ofrecen despacho estático para métodos específicos.

Implementación en C++

C++ utiliza enlace temprano y ofrece despacho dinámico y estático. La forma predeterminada de despacho es estática. Para obtener despacho dinámico, el programador debe declarar un método como virtual .

Los compiladores de C++ suelen implementar el despacho dinámico mediante una estructura de datos denominada tabla de funciones virtuales (vtable), que define la asignación de nombre a implementación para una clase determinada como un conjunto de punteros a funciones miembro. Esto es un detalle puramente de implementación, ya que la especificación de C++ no menciona las vtables. Las instancias de este tipo almacenarán un puntero a esta tabla como parte de sus datos de instancia, lo que complica los escenarios cuando se utiliza la herencia múltiple . Dado que C++ no admite el enlace tardío, la tabla virtual en un objeto C++ no se puede modificar en tiempo de ejecución, lo que limita el conjunto potencial de destinos de despacho a un conjunto finito elegido en tiempo de compilación.

La sobrecarga de tipos no produce despacho dinámico en C++, ya que el lenguaje considera que los tipos de los parámetros del mensaje forman parte del nombre formal del mensaje. Esto significa que el nombre del mensaje que ve el programador no es el nombre formal utilizado para la vinculación.

Implementación en Go, Rust y Nim

En Go , Rust y Nim se utiliza una variante más versátil del enlace temprano. Los punteros Vtable se transportan con referencias de objetos como "punteros gordos" ("interfaces" en Go, o "objetos de rasgos" en Rust ^{[ 3 ]}^{[ 4 ]} ).

Esto desacopla las interfaces compatibles de las estructuras de datos subyacentes. Cada biblioteca compilada no necesita conocer la gama completa de interfaces compatibles para usar correctamente un tipo, sino solo la disposición específica de la tabla virtual que requiere. El código puede pasar diferentes interfaces para el mismo dato a diferentes funciones. Esta versatilidad conlleva el uso de datos adicionales con cada referencia a un objeto, lo cual resulta problemático si se almacenan muchas de estas referencias de forma persistente.

El término puntero gordo simplemente se refiere a un puntero con información adicional asociada. La información adicional puede ser un puntero a tabla virtual para el despacho dinámico descrito anteriormente, pero más comúnmente es el tamaño del objeto asociado para describir, por ejemplo, una porción .

Implementación de Smalltalk

Smalltalk utiliza un despachador de mensajes basado en tipos. Cada instancia tiene un único tipo cuya definición contiene los métodos. Cuando una instancia recibe un mensaje, el despachador busca el método correspondiente en el mapa de mensajes a métodos para ese tipo y, a continuación, invoca dicho método.

Dado que un tipo puede tener una cadena de tipos base, esta búsqueda puede resultar costosa. Una implementación simple del mecanismo de Smalltalk tendría una sobrecarga significativamente mayor que la de C++, y esta sobrecarga se generaría por cada mensaje que recibe un objeto.

Las implementaciones reales de Smalltalk suelen utilizar una técnica conocida como almacenamiento en caché en línea ^{[ 5 ]} que hace que el despacho de métodos sea muy rápido. El almacenamiento en caché en línea básicamente almacena la dirección del método de destino anterior y la clase de objeto del sitio de llamada (o varios pares para el almacenamiento en caché multidireccional). El método almacenado en caché se inicializa con el método de destino más común (o simplemente el manejador de fallos de caché), según el selector de métodos. Cuando se llega al sitio de llamada del método durante la ejecución, simplemente se llama a la dirección en la caché. (En un generador de código dinámico, esta llamada es una llamada directa, ya que la dirección directa se corrige mediante la lógica de fallo de caché). El código de prólogo en el método llamado compara la clase en caché con la clase de objeto real, y si no coinciden, la ejecución se ramifica a un manejador de fallos de caché para encontrar el método correcto en la clase. Una implementación rápida puede tener varias entradas en la caché y, a menudo, solo se necesitan un par de instrucciones para que la ejecución llegue al método correcto en un fallo de caché inicial. El caso común será una coincidencia de la clase en caché, y la ejecución simplemente continuará en el método.

El almacenamiento en caché fuera de línea también puede utilizarse en la lógica de invocación de métodos, mediante la clase de objeto y el selector de método. En un diseño, la clase y el selector de método se cifran mediante una función hash y se utilizan como índice en una tabla de caché de despacho de métodos.

Dado que Smalltalk es un lenguaje reflexivo, muchas implementaciones permiten transformar objetos individuales en objetos con tablas de búsqueda de métodos generadas dinámicamente. Esto permite modificar el comportamiento de cada objeto individualmente. De esto ha surgido toda una categoría de lenguajes conocidos como lenguajes basados en prototipos , entre los que destacan Self y JavaScript . Un diseño cuidadoso del almacenamiento en caché de despacho de métodos permite que incluso los lenguajes basados en prototipos ofrezcan un despacho de métodos de alto rendimiento.

Muchos otros lenguajes de tipado dinámico, incluidos Python , Ruby , Objective-C y Groovy, utilizan enfoques similares.

Ejemplos

do

El despacho dinámico no está integrado en C como en otros lenguajes, pero aún así es posible mediante la gestión manual de los punteros a las funciones.

#include <stdio.h> #include <stdlib.h>typedef struct Pet { const char * name ; void ( * speak )( struct Pet * ); // contiene puntero a función } Pet ;Pet * createPet ( const char * name , void ( * speakFunc )( Pet * )) { Pet * pet = ( Pet * ) malloc ( sizeof ( Pet )); pet -> name = name ; pet -> speak = speakFunc ; return pet ; }void destroyPet ( Pet * pet ) { free ( pet ); }void dogSpeak ( Pet * pet ) { printf ( "%s dice '¡Guau!' \n " , pet -> name ); }void catSpeak ( Pet * pet ) { printf ( "%s dice '¡Miau!' \n " , pet -> name ); }void hablar ( Mascota * mascota ) { mascota -> hablar ( mascota ); }int main () { Pet * fido = createPet ( "Fido" , dogSpeak ); Pet * simba = createPet ( "Simba" , catSpeak );hablar ( fido ); // llama a dogSpeak() hablar ( simba ); // habla catSpeak();// limpieza; liberar recursos destroyPet ( fido ); destroyPet ( simba ); return 0 ; }

C++

importar std ;usando std :: string ;// convierte a Pet en una clase base virtual abstracta class Pet { protected : string name ; public : explicit Pet ( const string & name ) : name { name } {}virtual void speak () = 0 ; };clase Perro : público Mascota { público : explícito Perro ( const string & nombre ) : Mascota ( nombre ) {}void speak () override { std :: println ( "{} dice '¡Guau!'" , name ); } };clase Gato : público Mascota { público : explícito Gato ( const string & nombre ) : Mascota ( nombre ) {}void speak () override { std :: println ( "{} dice '¡Miau!'" , name ); } };// speak() podrá aceptar cualquier cosa que derive de Pet void speak ( Pet & pet ) { pet . speak (); }int main () { Perro fido ( "Fido" ); Gato simba ( "Simba" ); hablar ( fido ); hablar ( simba ); return 0 ; }

DO#

espacio de nombres Wikipedia.Ejemplos ;usando el sistema ;clase abstracta Mascota { cadena protegida nombre ;public Pet ( string name ) { this . name = name ; }public abstract void Speak (); }clase Perro : Mascota { público Perro ( cadena nombre ) : base ( nombre ) { }public override void Speak () { Console.WriteLine ( $ "{name} dice ' ¡ Guau!'" ); } }clase Gato : Mascota { público Gato ( cadena nombre ) : base ( nombre ) { }public override void Speak () { Console.WriteLine ( $ "{name} dice ' ¡ Miau!'" ); } }public class Main { public static void Speak ( Pet pet ) { pet . Speak (); }public static void Main () { Perro fido = new ( "Fido" ); Gato simba = new ( "Simba" ); Hablar ( fido ); Hablar ( simba ); } }

Java

paquete org.wikipedia.examples ;clase abstracta Mascota { protegido String nombre ;public Pet ( String name ) { this . name = name ; }público abstracto vacío hablar (); }clase Perro extiende Mascota { public Perro ( String nombre ) { super ( nombre ); }@Override public void speak () { System . out . printf ( "%s dice '¡Guau!'%n" , name ); } }clase Cat extiende Pet { public Cat ( String name ) { super ( name ); }@Override public void speak () { System . out . printf ( "%s dice '¡Miau!'%n" , name ); } };public class Main { public static void speak ( Pet pet ) { pet . speak (); }public static void main ( String [] args ) { Dog fido = new Dog ( "Fido" ); Cat simba = new Cat ( "Simba" ); speak ( fido ); speak ( simba ); } }

Pitón

from abc import ABC , abstractmethod from typing import Never# ABC es una clase que se usa para indicar que las clases que la extienden directamente son abstractas. class Pet ( ABC ): def __init__ ( self , name : str ) -> None : self . name = name@abstractmethod def speak ( self ) -> Never : raise NotImplementedError ( "El método abstracto debe ser implementado por las clases derivadas" )clase Perro ( Mascota ): def __init__ ( self , nombre : str ) -> Ninguno : super . __init__ ( nombre )def speak ( self ) -> None : print ( f " { self . name } dice '¡Guau!'" )clase Cat ( Mascota ): def __init__ ( self , nombre : str ) -> None : super . __init__ ( nombre )def speak ( self ) -> None : print ( f " { self . name } dice '¡Miau!'" )def speak ( pet : Pet ) -> None : # Despacha dinámicamente el método speak # pet puede ser una instancia de Dog o Cat pet . speak ()if __name__ == "__main__" : fido : Dog = Dog ( "Fido" ) speak ( fido ) simba : Cat = Cat ( "Simba" ) speak ( simba )

Óxido

rasgo Mascota { fn hablar ( & sí mismo ); }struct Perro <' a > { nombre : & ' a str }struct Cat <' a > { nombre : & ' a str }impl <' a > Perro <' a > { fn new ( nombre : & ' a str ) -> Self { Perro { nombre } } }impl <' a > Cat <' a > { fn new ( name : & ' a str ) -> Self { Cat { name } } }impl Pet <' a > for Dog <' a > { fn speak ( & self ) { println! ( "{} dice '¡Guau!'" , self . name ); } }implPet<'a>forCat<'a>{fnspeak(&self){println!("{} says 'Meow!'",self.name);}}// speak() uses dynamic dispatch and resolves the type at runtime,// for any type that implements the trait Petfnspeak(pet:&dynPet){pet.speak();}fnmain(){letfido:Dog=Dog::new("Fido");letsimba:Cat=Cat::new("Simba");speak(&fido);speak(&simba);}

References

↑Milton, Scott; Schmidt, Heinz W. (1994). Dynamic Dispatch in Object-Oriented Languages (Technical report). Vol. TR-CS-94-02. Australian National University. CiteSeerX 10.1.1.33.4292.
↑Driesen, Karel; Hölzle, Urs; Vitek, Jan (1995). "Message Dispatch on Pipelined Processors". ECOOP’95 — Object-Oriented Programming, 9th European Conference, Åarhus, Denmark, August 7–11, 1995. Lecture Notes in Computer Science. Vol. 952. Springer. CiteSeerX 10.1.1.122.281. doi:10.1007/3-540-49538-X_13. ISBN 3-540-49538-X.
↑Klabnik, Steve; Nichols, Carol (2023) [2018]. "17. Object-oriented programming features". The Rust Programming Language (2 ed.). San Francisco, California, USA: No Starch Press, Inc. pp. 375–396 [379–384]. ISBN 978-1-7185-0310-6pág. 384: Los objetos de rasgos realizan despacho dinámico […] Cuando usamos objetos de rasgos, Rust debe usar despacho dinámico. El compilador no conoce todos los tipos que podrían usarse con el código que usa objetos de rasgos, por lo que no sabe qué método implementado en qué tipo llamar. En cambio, en tiempo de ejecución, Rust usa los punteros dentro del objeto de rasgos para saber qué método llamar. Esta búsqueda genera un costo en tiempo de ejecución que no ocurre con el despacho estático. El despacho dinámico también impide que el compilador elija insertar en línea el código de un método, lo que a su vez impide algunas optimizaciones.(xxix+1+527+3 páginas)
↑ "Objetos de rasgos" . The Rust Reference . Consultado el 27 de abril de 2023 .
↑ Müller, Martin (1995). Message Dispatch in Dynamically-Typed Object-Oriented Languages (Tesis de maestría). Universidad de Nuevo México. pp. 16– 17. CiteSeerX 10.1.1.55.1782 .

Lecturas adicionales

Lippman, Stanley B. (1996). Inside the C++ Object Model . Addison-Wesley . ISBN 0-201-83454-5.
Groeber, Marcus; Di Geronimo, Jr., Edward "Ed"; Paul, Matthias R. (2002-03-02) [2002-02-24]. "Información de GEOS/NDO para RBIL62?" . Grupo de noticias : comp.os.geos.programmer . Recuperado el 2019-04-20 . […] La razón por la que Geos necesita 16 interrupciones es porque el esquema se usa para convertir llamadas a funciones entre segmentos ("lejos") en interrupciones, sin cambiar el tamaño del código. La razón por la que esto se hace es para que "algo" (el kernel) pueda engancharse a cada llamada entre segmentos hecha por una aplicación Geos y asegurarse de que los segmentos de código correctos se carguen desde la memoria virtual y se bloqueen. En términos de DOS , esto sería comparable a un cargador superpuesto , pero uno que se puede agregar sin requerir soporte explícito del compilador o la aplicación. Lo que sucede es algo así: […] 1. El compilador de modo real genera una instrucción como esta: CALL <segmento>:<desplazamiento> -> 9A <desbordamiento><desplazamientoalto><segbajo><segalto> donde <segbajo><segalto> normalmente se define como una dirección que debe corregirse en el momento de la carga dependiendo de la dirección donde se ha colocado el código. […] 2. El enlazador Geos convierte esto en otra cosa: INT 8xh -> CD 8x […] DB <segalto>,<desbordamiento>,<desplazamientoalto> […] Nótese que esto son de nuevo cinco bytes, por lo que se puede corregir "en el lugar". Ahora el problema es que una interrupción requiere dos bytes, mientras que una instrucción CALL FAR solo necesita uno. Como resultado, el vector de 32 bits (<seg><ofs>) debe comprimirse en 24 bits. […] Esto se logra mediante dos cosas: Primero, la dirección <seg> se codifica como un "manejador" del segmento, cuyo nibble más bajo siempre es cero. Esto ahorra cuatro bits. Además […] los cuatro bits restantes van al nibble bajo del vector de interrupción, creando así cualquier cosa desde INT 80h hasta 8Fh. […] El manejador de interrupciones para todos esos vectores es el mismo. "Desempaquetará" la dirección de la notación de tres bytes y medio, buscará la dirección absoluta del segmento y reenviará la llamada, después de haber realizado su tarea de carga de memoria virtual... El retorno de la llamada también pasará a través del código de desbloqueo correspondiente. […] El nibble bajo del vector de interrupción (80h–8Fh) contiene los bits 4 a 7 del identificador del segmento. Los bits 0 a 3 de un identificador de segmento son (por definición de un identificador Geos) siempre 0. […] toda la API de Geos se ejecuta a través del esquema de "superposición" […]: cuando una aplicación Geos se carga en la memoria, el cargador reemplazará automáticamente las llamadas a funciones en las bibliotecas del sistema por las llamadas correspondientes basadas en INT. De todos modos, estas no son constantes, sino que dependen del identificador asignado al segmento de código de la biblioteca.[…] Geos fue diseñado originalmente para ser convertido a modo protegido muy pronto […], con modo real Siendo solo una "opción heredada" [...] casi cada línea de código ensamblador está lista para ello [...]{{cite newsgroup}}: CS1 maint: servicio de archivado obsoleto ( enlace )
Paul, Matthias R. (2002-04-11). "Re: [ fd-dev ] ANUNCIO: CuteMouse 2.0 alpha 1" . freedos-dev . Archivado del original el 21-02-2020 . Recuperado el 21-02-2020 . [...] en caso de punteros tan dañados [...] hace muchos años Axel y yo estábamos pensando en una forma de usar *un* punto de entrada en un controlador para múltiples vectores de interrupción (ya que esto nos ahorraría mucho espacio para los múltiples puntos de entrada y el código de marco de inicio/salida más o menos idéntico en todos ellos), y luego cambiar a los diferentes manejadores de interrupción internamente. Por ejemplo: 1234h:0000h […] 1233h:0010h […] 1232h:0020h […] 1231h:0030h […] 1230h:0040h […] todos apuntan exactamente al mismo punto de entrada. Si conectas INT 21h a 1234h:0000h y INT 2Fh a 1233h:0010h, y así sucesivamente, todos pasarían por el mismo "agujero", pero aún podrías distinguirlos y ramificarte a los diferentes manejadores internamente. Piensa en un punto de entrada "comprimido" en un stub A20 para la carga de HMA . Esto funciona siempre que ningún programa comience a hacer magia de segmento:desplazamiento. […] Compáralo con el enfoque opuesto de tener múltiples puntos de entrada (quizás incluso soportando el Protocolo de compartición de interrupciones de IBM ), que consume mucha más memoria si conectas muchas interrupciones. […] Llegamos a la conclusión de que esto probablemente no sería seguro en la práctica porque nunca se sabe si otros controladores normalizan o desnormalizan los punteros, por las razones que sean. […](Nota: Algo similar a los " punteros gordos " específicamente para el direccionamiento de segmento:desplazamiento en modo real de Intel en procesadores x86 , que contiene tanto un puntero deliberadamente desnormalizado a un punto de entrada de código compartido como información para distinguir los diferentes llamadores en el código compartido. Si bien, en un sistema abierto , no se pueden descartar por completo las instancias de terceros que normalizan punteros (en otros controladores o aplicaciones) en interfaces públicas , el esquema se puede usar de forma segura en interfaces internas para evitar secuencias de código de entrada redundantes).
Bright, Walter (22 de diciembre de 2009). "El mayor error de C" . Digital Mars . Archivado del original el 8 de junio de 2022. Recuperado el 11 de julio de 2022 .
Holden, Daniel (2015). "Una biblioteca de punteros gordos" . Cello: High Level C. Archivado del original el 11 de julio de 2022. Recuperado el 11 de julio de 2022 .