Реализация вызова метода в O'Caml На самом деле идея простая, но красивая.
В чем пробелма: с точки зрения статического контроля типов, объект может выступать
под любым типом, которому соотвествует его сигнатура (то есть - наличествуют
заданные методы и их типы подходят). В месте, где происходит вызов метода,
компилятор ничего не знает про тип самого объекта. Он обычно не знает, что такой тип
вообще существует.
В месте, где создается объект, компилятор как правило ничего не знает о том, что
где-то этот объект будет использоваться с конкретной сигнатурой. В отличие от
языков, где иерархия основана на наследовании все предки в месте создания объекта
известны, O'Caml базируется на отношинее subtyping'a.
Понятно, что можно в объекте держать таблицу методов с именами и динамически искать их.
Но это как-то не очень. Цикл устраивать. Потому делается так (решение подходит и к реализации
записей с subtyping'ом по включению набора полей):
Все имена методов нумеруются глобально по всей программе. Это может делать линкер, в
O'Caml это делается динамически при запуске программы. Далее в качестве VMT можно использовать
таблицу длины n_meth, где n_meth - количество имен методов. В пустующие клетки не записывается
ничего, в остальные - адреса функций.
Вызов делается просто - по номеру метода берется соотвествующий адрес и вызывается. Статическй
контроль гарантирует, что метод с данным именем/номером будет.
Идея хороша всем, кроме того, что n_meth может быть довольно большим (напирмер 1000), а заводить для каждого класса
(пусть 200 классов) табличку в 1000 слов несколько накладно - даже тут уже получится мегабайт. Это при
весьма умеренных n_meth и числе классов. Опять же - понятно, что таблики будут почти пустые.
Потому они поджимаются довольно простым методом: для сильно разреженной таблицы с n объектами обычно можно подобрать
немного большее число p, такое, что для любого момера k элемента в табличке, k mod p будет однозначно
определять k (среди присутсвующих в таблице гнезд). То есть - такое простенькое безконфоликтное хэширование.
Далее - в начало таблицы записывается подобранное p, а адреса методов располагаются в позиция по модулю
p. Вызов метода соотвественное делается просто - берется остаток от деления номера метода на p из таблицы
и вызывается то, что лежит по адресу.
Придумал это
Didier Rémy в 1992 года:
Efficient Representation of Extensible Records. In Proceedings of the 1992 workshop on ML and its Applications, page 12, San Francisco, USA, June 1992