Реализация вызова метода в 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

N=10 k=2  p=2.533333333333333
N=10 k=3  p=4.066666666666666
N=10 k=4  p=5.6
N=10 k=5  p=7.119047619047619
N=10 k=6  p=8.347619047619048
N=20 k=2  p=2.642105263157895
N=20 k=3  p=4.366666666666666
N=20 k=4  p=6.1781217750258
N=20 k=5  p=7.999613003095975
N=20 k=6  p=9.779282765737873
N=30 k=2  p=2.6758620689655173
N=30 k=3  p=4.484729064039409
N=30 k=4  p=6.396861886517059
N=30 k=5  p=8.408109132247063