Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет kouzdra ([info]kouzdra) в [info]programming
@ 2005-11-18 12:35:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Реализация вызова метода в 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


(Добавить комментарий)


[info]potan
2005-11-18 12:59 (ссылка)
А чем плох подход из Haskell - передавать vtbl отдельным параметром?
OCamlовскую систему объектов это бы покрыло.

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2005-11-18 13:21 (ссылка)
Все равно остается проблема, как из нее выбрать метод, не зная структуры объекта.
В Haskell ее просто каждый раз при передаче в другой контекст собирают заново (динамически).
Это можно, но существенно менее эффективно и кучу жрет:

допусти у нас есть x: < a: int, b: int, c:int > и соотвественон - табличка с тремя методами.
Мы должны его передать туда, где требуется
[Error: Irreparable invalid markup ('<a:int,>') in entry. Owner must fix manually. Raw contents below.]

Все равно остается проблема, как из нее выбрать метод, не зная структуры объекта.
В Haskell ее просто каждый раз при передаче в другой контекст собирают заново (динамически).
Это можно, но существенно менее эффективно и кучу жрет:

допусти у нас есть x: < a: int, b: int, c:int > и соотвественон - табличка с тремя методами.
Мы должны его передать туда, где требуется <a:int, b: int>, то есть - надо создать новую
табличку на два метода, перекопировать туда все и передать ее вместе с объектом.

Остается еще проблема сохранения объекта в структурах данных, Haskell-ное решение видимо пройдет, но
будет довольно сложным.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]potan
2005-11-18 14:34 (ссылка)
Да, действительно, преобразование типов делается сложнее...

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-18 14:51 (ссылка)
Возможно есть и более серьезные (неразрешимые) проблемы связанные с полиморфизмом -
например - как реализовать функцию

let apply f x = f x

Если в реальном вызове - x - объект, а f - хочет объект. Но apply-то про это
ничего не знает.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]potan
2005-11-18 15:29 (ссылка)
Haskell такое ест.
Хотя у него классы "более статические".

Похоже все это актуально и для решетчатого наследовния. Интересно, дойдут у меня когда-нибудь руки его реализовать...

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-18 15:34 (ссылка)
У него нет subtyping'a. Так что боюсь, что это не переносится.

(Ответить) (Уровень выше)


[info]polytheme
2005-11-18 15:03 (ссылка)
что-то я прикинул, это p больно быстро растет при случайном равномерном распределении k методов по таблице с N полями. примерно как (k/e)^k. или вся фишка в том, что они кучкуются, т.е. таблица собирается не по алфавиту, а как-то специально ?

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2005-11-18 15:08 (ссылка)
У тебя что-то странное - p всегда <= N (потому что N просто подходит)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]polytheme
2005-11-18 15:31 (ссылка)
ну да, это приближение при малых k: k^k<N. я имел в виду, что большая таблица получается. рассуждал я так : посмотрим, с какой вероятностью подойдет модуль l. если N велико(или кратно l), то это вероятность того, что k шаров, разложенных по l ячейкам, не попадут вдвоем в одну ячейку. это (l!/(k!*(l-k)!))/l^k. если l = Ak, где A-это некоторая константа, то, применяя формулу Стирлинга(забивая на корень из 2*pi*n и прочую мелочь), получаем (Ak)^(Ak)/(k^k*((A-1)k)^((A-1)k)*(Ak)^k)=(A/(A-1))^((A-1)k)*1/k^k,
что примерно равно 1/(k/e)^k. соответственно, если считать разные модули независимыми (что неверно, но не думаю, что это очень сильно влияет), вопрос встает так : сколько раз нужно умножить (1-1/(k/e)^k) на себя, чтобы получить маленькое число - вероятность, что все эти модули плохими не окажутся. это примерно (k/e)^k.
впрочем, есть натяжки(с независимостью модулей), я, пожалуй, проведу компьютерный эксперимент.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-18 15:36 (ссылка)
Там есть еще одна натяжка - реально надо минимизировать не p, а наибольший модуль. Не думаю, чтобы это сильно влияло, но...

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]polytheme
2005-11-18 16:14 (ссылка)
эксперимент говорит, что не все так плохо, для N=10000
при k=100 получается среднее p=1000, а
при k=10 вообще 25.

так что или это rand() - такой хороший датчик случайных чисел,
или что-то тут не так и здесь вам не тут ...

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2005-11-18 16:45 (ссылка)
Я прошелся полным перебором:
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

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]polytheme
2005-11-18 18:00 (ссылка)
я увеличил N до 1000000, но p так и осталось 963 при k=100. так что, видимо, моя асимптотика если и верная, то для очень больших k(и N соответственно). для реального же проекта N в районе от 10000 до 100000 (при использовании библиотек), а вот k у большого класса может быть и 100 (но это редкость). в этом случае наблюдается удесятерение виртуальной таблицы, а вот для среднего k=10 - всего лишь удвоение (упятерение в редких плохих случаях).

так что похоже это и правда работает.

(Ответить) (Уровень выше)


[info]kouzdra
2005-11-18 16:46 (ссылка)
Если интеерсно - программка:
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] ]

(Ответить) (Уровень выше)


[info]qwerty
2005-11-18 22:46 (ссылка)
А науку про идеальные хэш-функции применять не пробовал?

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2005-11-19 13:11 (ссылка)
Не пробовали вроде.

(Ответить) (Уровень выше)


[info]qwerty
2005-11-19 00:41 (ссылка)
Еще, кстати, интересно решение этой задачи в случае, если деление/взятие остатка медленные.

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2005-11-19 13:11 (ссылка)
Там в принципе не очень важно, какой хэш. Важно, чтобы более или менее легко подбирался.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]qwerty
2005-11-19 19:44 (ссылка)
Со степенями двойки (наложением маски) фокус вряд ли пройдет.

(Ответить) (Уровень выше)


[info]qwerty
2005-11-20 10:51 (ссылка)
Кстати, есть и другой способ пожатия этих табличек - глобальная раскраска сигнатур так, чтобы в каждой табличке все цвета были уникальны. Если бы типовой анализ не гарантировал корректности, то для всех неправильных, но возможных в данном месте типов (есть на то DFA) входы в табличке забиваются одной и той же функцией выдачи ошибки динамики типов. Но это все, конечно, не для инкрементного программирования.

(Ответить) (Уровень выше)

Вопрос ребром
[info]tristes_tigres
2005-11-19 04:16 (ссылка)
Скажите, а если честно, положа руку на сердце: кому-нибудь вообще нужны языки программирования, отличные от С и Fortran ?

(Ответить) (Ветвь дискуссии)

Re: Вопрос ребром
[info]polter
2005-11-19 05:04 (ссылка)
мне, а что?

(Ответить) (Уровень выше)

Re: Вопрос ребром
[info]qwerty
2005-11-19 09:24 (ссылка)
Нужны, нужны - мне, чтобы с них трансляторы писать.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Вопрос ребром
[info]tristes_tigres
2005-11-20 00:50 (ссылка)
> Нужны, нужны - мне, чтобы с них трансляторы писать.

Так я и подозревал.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Вопрос ребром
[info]qwerty
2005-11-20 04:18 (ссылка)
Не я первый начал :-)

(Ответить) (Уровень выше)

Re: Вопрос ребром
[info]kouzdra
2005-11-19 11:33 (ссылка)
Знаете - кому нужен фортран я как раз не очень представляю. Я уж не помню когда его последний
раз встречал. Кобол - и то живее.

А вообще - нужны конечно. Даром, что ли MS к себе половину функциональщиков переменали. И использует,
кстати, по назначению.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Вопрос ребром
[info]tristes_tigres
2005-11-20 00:49 (ссылка)
> Знаете - кому нужен фортран я как раз не очень представляю.
> Я уж не помню когда его последний раз встречал. Кобол - и то живее.

Прискорбная неинформированность. Fortran - это наверно единственный язык, где
"code reuse" существует не на уровне академических деклараций.

> А вообще - нужны конечно. Даром, что ли MS к себе половину функциональщиков
> переменали. И использует, кстати, по назначению.

А, то-то у них в MS такие замечательные программные продукты получаются.

(Ответить) (Уровень выше)

Re: Вопрос ребром
[info]qwerty
2005-11-20 04:20 (ссылка)
Физики до сих пор многое на Фортране считают. Его оптимизировать и автоматически распараллеливать легче, поэтому код немного лучше.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Вопрос ребром
[info]tristes_tigres
2005-11-21 01:51 (ссылка)

Дело не столько в этом, хотя Fortran (особенно Fortran 90) действительно разрабатывался с учётом вопросов оптимизации, да и кодировать алгоритмы на нём просто намного удобнее. Самое главное, что любой, кто занимается какими-нибудь вычислениями, не сможет обойтись без стандартных библиотек, написанных Fortran-е.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Вопрос ребром
[info]qwerty
2005-11-21 04:52 (ссылка)
Чем на Фортране удобнее писать, чем на Ц, мне не понять. Очень многие библиотеки существуют и в сишном варианте. Если есть исходники, довольно просто написать конвертор из Фортрана в Ц. Кроме коммон-блоков, я никаких сложностей не вижу. Да он уж наверняка кем-нибудь давно написан.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Вопрос ребром
[info]tristes_tigres
2005-11-22 01:52 (ссылка)
Чем на Фортране удобнее писать, чем на Ц, мне не понять.

Нет комплексных чисел, нет многомерных массивов, все массивы индексируются с нуля, невозможно узнать размер динамически размещённого массива, да и размещён ли он вообще, и так далее.

В Fortran 90 сложение частей двух массивов пишется так :

A(6:10,1:3) = B(1:5,4:6) + 3.0*C(1:5,1:3)

А теперь перепишите на C

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: Вопрос ребром
[info]qwerty
2005-11-22 09:39 (ссылка)
Иш ты, понавставляли в Фортран конструкций памяти Алгола-68. Последний раз я на нем в 1985 программировал, тогда динамически отводимых массивов и вырезок в нем не было.

На ЦПП переписать это можно (завести массивы с паспортами и вырезками), и даже выглядеть будет похоже, но машинный код получится сильно хуже. Не потому, конечно, что разработчики фортрановского стандарта как-то особенно были эффективностью озабочены, а потому, что ЦПП более универсален. Соответствующими конструкциями его вручную расширить можно, да вот только компилятор в процессе трансляции инвариантов этих конструкций знать не будет и потому будет вынужден предполагать худший случай.

Насчет Ц и Фортана выяснили. Но как жить без ассемблера и на чем писать скрипты для обработки текстов?

(Ответить) (Уровень выше)

Re: Вопрос ребром
[info]qwerty
2005-11-21 06:34 (ссылка)
Насчет комплексирования программ, писанных на Ц и Фортране, - многие компиляторы поддерживают extern "fortran".

(Ответить) (Уровень выше)