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

import List

all_bits max n = all [] max 0 n where 
    all hd max _ 0 = [hd]
    all hd max i n | i == max   = []
                   | otherwise  = (all (i:hd) max (i+1) (n-1))++(all hd max (i+1) n)

min_p l = head [ p  | p <- [length l..], (not . dups . sort . map (`mod` p)) l  ] where
    dups [] = False
    dups [_] = False
    dups (a:b:c) | a == b = True
                 | otherwise = dups (b:c)


mid l = sum (map (fromInteger . toInteger) l) / ((fromInteger . toInteger) (length l))

main = mapM_ putStrLn [ "N=" ++ show n ++ " k=" ++ show k ++ 
                        "  p=" ++ ((show . mid . map min_p . sort) (all_bits n k)) 
                        | n <- [10, 20, 30], k <- [2..6] ]