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