Despacho dinâmico

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

Em ciência da computação , despacho dinâmico é o processo de selecionar qual implementação de uma operação polimórfica ( método ou função) chamar em tempo de execução . É comumente empregado e considerado uma característica principal de linguagens e sistemas de programação orientada a objetos (OOP). [1]

Os sistemas orientados a objetos modelam um problema como um conjunto de objetos interativos que executam operações referidas pelo nome. Polimorfismo é o fenômeno em que objetos um tanto intercambiáveis ​​expõem uma operação de mesmo nome, mas possivelmente com comportamento diferente. Como exemplo, um objeto File e um objeto Database possuem um método StoreRecord que pode ser usado para gravar um registro de pessoal no armazenamento. Suas implementações diferem. Um programa contém uma referência a um objeto que pode ser um objeto File ou um objeto Database . O que pode ter sido determinado por uma configuração de tempo de execução e, neste estágio, o programa pode não saber ou se importar com qual. Quando o programa chama StoreRecordno objeto, algo precisa escolher qual comportamento será encenado. Se alguém pensar em OOP como o envio de mensagens para objetos, neste exemplo o programa envia uma mensagem StoreRecord para um objeto de tipo desconhecido, deixando para o sistema de suporte em tempo de execução despachar a mensagem para o objeto correto. O objeto decreta qualquer comportamento que ele implementa. [2]

O despacho dinâmico contrasta com o despacho estático , no qual a implementação de uma operação polimórfica é selecionada em tempo de compilação . A finalidade do despacho dinâmico é adiar a seleção de uma implementação apropriada até que o tipo de tempo de execução de um parâmetro (ou vários parâmetros) seja conhecido.

O despacho dinâmico é diferente da vinculação tardia (também conhecida como vinculação dinâmica). A associação de nome associa um nome a uma operação. Uma operação polimórfica tem várias implementações, todas associadas ao mesmo nome. As ligações podem ser feitas em tempo de compilação ou (com ligação tardia) em tempo de execução. Com o despacho dinâmico, uma implementação específica de uma operação é escolhida em tempo de execução. Embora o despacho dinâmico não implique ligação tardia, a vinculação tardia implica despacho dinâmico, uma vez que a implementação de uma operação de ligação tardia não é conhecida até o tempo de execução. [ citação necessária ]

Despacho único e múltiplo

A escolha de qual versão de um método chamar pode ser baseada em um único objeto ou em uma combinação de objetos. O primeiro é chamado de despacho único e é suportado diretamente por linguagens orientadas a objetos comuns, como Smalltalk , C++ , Java , C# , Objective-C , Swift , JavaScript e Python . Nessas linguagens e similares, pode-se chamar um método de divisão com sintaxe que se assemelha a

dividendo . divide ( divisor )   # dividendo / divisor

onde os parâmetros são opcionais. Isso é considerado como o envio de uma mensagem chamada divide com divisor de parâmetro para dividendo . Será escolhida uma implementação baseada apenas no tipo do dividendo (talvez racional , ponto flutuante , matriz ), desconsiderando o tipo ou valor do divisor .

Por outro lado, algumas linguagens despacham métodos ou funções com base na combinação de operandos; no caso de divisão, os tipos de dividendo e divisor juntos determinam qual operação de divisão será realizada. Isso é conhecido como despacho múltiplo . Exemplos de linguagens que suportam despacho múltiplo são Common Lisp , Dylan e Julia .

Mecanismos dinâmicos de despacho

Uma linguagem pode ser implementada com diferentes mecanismos dinâmicos de despacho. As escolhas do mecanismo de despacho dinâmico oferecido por uma linguagem alteram em grande parte os paradigmas de programação que estão disponíveis ou são mais naturais de usar dentro de uma determinada linguagem.

Normalmente, em uma linguagem tipada, o mecanismo de despacho será executado com base no tipo dos argumentos (mais comumente com base no tipo do receptor de uma mensagem). Linguagens com sistemas de digitação fracos ou inexistentes geralmente carregam uma tabela de despacho como parte dos dados do objeto para cada objeto. Isso permite o comportamento da instância, pois cada instância pode mapear uma determinada mensagem para um método separado.

Algumas linguagens oferecem uma abordagem híbrida.

O despacho dinâmico sempre incorrerá em uma sobrecarga, portanto, algumas linguagens oferecem despacho estático para métodos específicos.

Implementação C++

C++ usa ligação antecipada e oferece despacho dinâmico e estático. A forma padrão de envio é estática. Para obter o despacho dinâmico, o programador deve declarar um método como virtual .

Os compiladores C++ normalmente implementam o despacho dinâmico com uma estrutura de dados chamada tabela de função virtual (vtable) que define o mapeamento de nome para implementação para uma determinada classe como um conjunto de ponteiros de função de membro. (Isso é puramente um detalhe de implementação; a especificação C++ não menciona vtables.) As instâncias desse tipo armazenarão um ponteiro para essa tabela como parte de seus dados de instância. Isso é complicado quando a herança múltipla é usada. Como o C++ não suporta ligação tardia, a tabela virtual em um objeto C++ não pode ser modificada em tempo de execução, o que limita o conjunto potencial de destinos de expedição a um conjunto finito escolhido em tempo de compilação.

A sobrecarga de tipo não produz despacho dinâmico em C++, pois a linguagem considera os tipos dos parâmetros da mensagem como parte do nome formal da mensagem. Isso significa que o nome da mensagem que o programador vê não é o nome formal usado para vinculação.

Implementação de Go e Rust

Em Go , Rust e Nim , uma variação mais versátil de encadernação antecipada é usada. Ponteiros Vtable são carregados com referências de objeto como 'ponteiros gordos' ('interfaces' em Go, ou 'trait objects' em Rust). [ citação necessária ]

Isso dissocia as interfaces suportadas das estruturas de dados subjacentes. Cada biblioteca compilada não precisa conhecer toda a gama de interfaces suportadas para usar corretamente um tipo, apenas o layout vtable específico que elas exigem. O código pode passar diferentes interfaces para o mesmo dado para diferentes funções. Essa versatilidade vem à custa de dados extras com cada referência de objeto, o que é problemático se muitas dessas referências forem armazenadas de forma persistente.

O termo ponteiro gordo refere-se simplesmente a um ponteiro com informações adicionais associadas. As informações adicionais podem ser um ponteiro vtable para despacho dinâmico descrito acima, mas é mais comum o tamanho do objeto associado para descrever, por exemplo, uma fatia . [ citação necessária ]

Implementação do Smalltalk

Smalltalk usa um despachante de mensagens baseado em tipo. Cada instância possui um único tipo cuja definição contém os métodos. Quando uma instância recebe uma mensagem, o dispatcher procura o método correspondente no mapa de mensagem para método para o tipo e, em seguida, invoca o método.

Como um tipo pode ter uma cadeia de tipos básicos, essa pesquisa pode ser cara. Uma implementação ingênua do mecanismo do Smalltalk parece ter uma sobrecarga significativamente maior do que a do C++ e essa sobrecarga seria incorrida para cada mensagem que um objeto recebe.

Implementações reais do Smalltalk geralmente usam uma técnica conhecida como cache inline [3]que torna o envio de métodos muito rápido. O cache inline basicamente armazena o endereço do método de destino anterior e a classe de objeto do site de chamada (ou vários pares para cache multidirecional). O método em cache é inicializado com o método de destino mais comum (ou apenas o manipulador de falta de cache), com base no seletor de método. Quando o site de chamada do método é alcançado durante a execução, ele apenas chama o endereço no cache. (Em um gerador de código dinâmico, essa chamada é uma chamada direta, pois o endereço direto é corrigido pela lógica de falta de cache.) O código de prólogo no método chamado compara a classe em cache com a classe de objeto real e, se eles não corresponderem , a execução desvia para um manipulador de falta de cache para encontrar o método correto na classe. Uma implementação rápida pode ter várias entradas de cache e geralmente leva apenas algumas instruções para obter a execução do método correto em uma falha de cache inicial. O caso comum será uma correspondência de classe em cache e a execução continuará no método.

O cache fora de linha também pode ser usado na lógica de invocação de método, usando a classe de objeto e o seletor de método. Em um projeto, o seletor de classe e método é hash e usado como um índice em uma tabela de cache de despacho de método.

Como Smalltalk é uma linguagem reflexiva, muitas implementações permitem transformar objetos individuais em objetos com tabelas de pesquisa de métodos geradas dinamicamente. Isso permite alterar o comportamento do objeto por objeto. Uma categoria inteira de linguagens conhecidas como linguagens baseadas em protótipos cresceu a partir disso, sendo as mais famosas Self e JavaScript . O design cuidadoso do cache de despacho de método permite que até linguagens baseadas em protótipo tenham despacho de método de alto desempenho.

Muitas outras linguagens tipadas dinamicamente, incluindo Python , Ruby , Objective-C e Groovy usam abordagens semelhantes.

Exemplo em Python

class  Cat : 
    def  speak ( self ): 
        print ( "Miau" )

class  Dog : 
    def  speak ( self ): 
        print ( "Woof" )


def  speak ( pet ): 
    # Despacha dinamicamente o método speak 
    # pet pode ser uma instância de Cat ou Dog 
    pet . falar ()

gato  =  gato () 
fala ( gato ) 
cachorro  =  cachorro () 
fala ( cachorro )

Exemplo em C++

#include <iostream> 

// torna Pet uma classe base virtual abstrata 
class  Pet { 
público :
    virtual void falar () = 0 ;    
};

class  Dog : public Pet {    
público :
    void falar () substituir  
    {
        std :: cout << "Uau! \n " ;  
    }
};

class  Cat : public Pet {    
público :
    void falar () substituir  
    {
        std :: cout << "Miau! \n " ;  
    }
};

// speak() poderá aceitar qualquer coisa derivada de Pet 
void speak ( Pet & pet )  
{
    animal de estimação . falar ();
}

int principal () 
{
    cão fido ; 
    Gato simba ; 
    falar ( fido );
    falar ( simba );
    retorna 0 ; 
}

Veja também

Referências

  1. ^ Milton, Scott; Schmidt, Heinz W. (1994). Despacho Dinâmico em Linguagens Orientadas a Objetos (Relatório Técnico). Vol. TR-CS-94-02. Universidade Nacional Australiana. CiteSeerX  10.1.1.33.4292 .
  2. ^ Driesen, Karel; Hölzle, Urs; Vitek, janeiro (1995). "Envio de mensagens em processadores em pipeline". ECOOP'95 — Programação Orientada a Objetos, 9ª Conferência Européia, Åarhus, Dinamarca, 7 a 11 de agosto de 1995 . Notas de aula em Ciência da Computação. Vol. 952. Springer. CiteSeerX 10.1.1.122.281 . doi : 10.1007/3-540-49538-X_13 . ISBN  3-540-49538-X.
  3. ^ Müller, Martin (1995). Despacho de Mensagens em Linguagens Orientadas a Objetos de Tipo Dinâmico (Tese de Mestrado). Universidade do Novo México. págs. 16–17. CiteSeerX 10.1.1.55.1782 . 

Leitura adicional

  • Lippman, Stanley B. (1996). Dentro do modelo de objeto C++ . Addison-Wesley . ISBN 0-201-83454-5.
  • Groeber, Marcus; Di Geronimo, Jr., Edward "Ed"; Paul, Matthias R. (2002-03-02) [2002-02-24]. "Informações GEOS/NDO para RBIL62?" . Grupo de notíciascomp.os.geos.programmer . Arquivado do original em 2019-04-20 . Recuperado 2019-04-20 . […] A razão pela qual o Geos precisa de 16 interrupções é porque o esquema é usado para converter chamadas de função entre segmentos ("far") em interrupções, sem alterar o tamanho do código. A razão disso é feito para que "algo" (o kernel) possa se conectar a cada chamada entre segmentos feita por um aplicativo Geos e certificar-se de que os segmentos de código apropriados sejam carregados da memória virtual e bloqueados.Em termos gerais, isso seria comparável a um carregador de sobreposição , mas que pode ser adicionado sem exigir suporte explícito do compilador ou do aplicativo. O que acontece é algo assim: […] 1. O compilador de modo real gera uma instrução assim: CALL <segment>:<offset>-> 9A <offlow><offhigh><seglow><seghigh> com <seglow><seghigh> normalmente sendo definido como um endereço que deve ser fixado em tempo de carregamento dependendo do endereço onde o código foi colocado. […] 2. O vinculador Geos transforma isso em outra coisa: INT 8xh -> CD 8x […] DB <seghigh>,<offlow>,<offhigh> […] Observe que isso é novamente cinco bytes, então pode ser fixado "no lugar". Agora o problema é que uma interrupção requer dois bytes, enquanto uma instrução CALL FAR precisa apenas de um. Como resultado, o vetor de 32 bits (<seg><ofs>) deve ser compactado em 24 bits. […] Isso é obtido por duas coisas: primeiro, o endereço <seg> é codificado como um "handle" para o segmento, cujo nibble mais baixoé sempre zero. Isso economiza quatro bits. Além disso […] os quatro bits restantes vão para o nibble baixo do vetor de interrupção, criando assim qualquer coisa de INT 80h a 8Fh. […] O manipulador de interrupção para todos esses vetores é o mesmo. Ele "descompactará" o endereço da notação de três bytes e meio, procurará o endereço absoluto do segmento e encaminhará a chamada, depois de ter feito o carregamento da memória virtual... O retorno da chamada também passar pelo código de desbloqueio correspondente. […] O nibble baixo do vetor de interrupção (80h–8Fh) contém os bits 4 a 7 do identificador de segmento. Os bits 0 a 3 de um identificador de segmento são (por definição de um identificador Geos) sempre 0. […] todas as APIs Geos são executadas através do esquema "overlay" […]: quando um aplicativo Geos é carregado na memória, o carregador substituirá automaticamente as chamadas para funções nas bibliotecas do sistema pelas chamadas correspondentes baseadas em INT. De qualquer forma, eles não são constantes, mas dependem do handle atribuído ao segmento de código da biblioteca. […] Geos foi originalmente destinado a ser convertido paramodo protegido muito cedo […], com o modo real sendo apenas uma "opção herdada" […] quase todas as linhas de código assembly estão prontas para isso […]
  • Paul, Matthias R. (2002-04-11). "Re: [fd-dev] ANÚNCIO: CuteMouse 2.0 alpha 1" . freedos-dev . Arquivado a partir do original em 21/02/2020 . Recuperado 2020-02-21 .[…] no caso de tais ponteiros mutilados […] muitos anos atrás, Axel e eu estávamos pensando em uma maneira de usar *um* ponto de entrada em um driver para vários vetores de interrupção (já que isso nos pouparia muito espaço para o vários pontos de entrada e o código de enquadramento de inicialização/saída mais ou menos idêntico em todos eles) e, em seguida, alterne para os diferentes manipuladores de interrupção internamente. Por exemplo: 1234h:0000h […] 1233h:0010h […] 1232h:0020h […] 1231h:0030h […] 1230h:0040h […] todos apontam exatamente para o mesmo ponto de entrada. Se você conectar INT 21h em 1234h:0000h e INT 2Fh em 1233h:0010h, e assim por diante, todos eles passarão pela mesma "brecha", mas você ainda poderá distinguir entre eles e ramificar para os diferentes manipuladores internamente. Pense em um "comprimido"carregando. Isso funciona desde que nenhum programa comece a fazer mágicas segment:offset. […] Compare isso com a abordagem oposta de ter vários pontos de entrada (talvez até suportando o Interrupt Sharing Protocol da IBM ), que consome muito mais memória se você ligar muitas interrupções. […] Chegamos ao resultado de que isso provavelmente não seria salvo na prática, porque você nunca sabe se outros drivers normalizam ou desnormalizam ponteiros, por quais motivos nunca. […](NB. Algo semelhante a " ponteiros gordos " especificamente para o segmento de modo real da Intel : endereçamento de deslocamento em processadores x86 , contendo um ponteiro deliberadamente desnormalizado para um ponto de entrada de código compartilhado e algumas informações para ainda distinguir os diferentes chamadores no Embora, em um sistema aberto , instâncias de terceiros de normalização de ponteiro (em outros drivers ou aplicativos) não possam ser descartadas completamente em interfaces públicas , o esquema pode ser usado com segurança em interfaces internas para evitar sequências de código de entrada redundantes.)
  • Bright, Walter (2009-12-22). "O maior erro de C" . Marte Digital . Arquivado a partir do original em 2022-06-08 . Recuperado 2022-07-11 . [1]
  • Holden, Daniel (2015). "Uma biblioteca de ponteiros gordos" . Violoncelo: Alto Nível C . Arquivado a partir do original em 2022-07-11 . Recuperado 2022-07-11 .