VM и байткод

После объявление о запуске в большой свет Protocol Buffers стали появлятся всякие критические и не очень обсуждения. Самое интересное на мой взгляд появилось в листе рассылки по Erlang'у, где вспомнили про уже существующий формат UBF.

Идея UBF в том, что мы шлем по сети не сериализованные данные, а программы, которые при исполнении на принимающей стороне порождают структуры данных, которые мы хотим передать. Программы исполняются специальной виртуальной машиной, в основе которой лежит интересная техника нумерации опкодов. Пусть наша виртуальная машина для декодирования работает на основе стека и предположим, что одной из пересылаемых структур будет список. В Scheme'е список можно записать как

    '(1 2 3 4)

Если мы хотим пересылать списки по сети в виде программы, необходимо сделать следующие опкоды:

• начало списка
• конец списка
• разделитель элементов (операция, которая будет брать два элемента с вершины стека и слеплять их в cons-cell (способ организации списков в Лиспе).
• nil

Этим опкодам можно присвоить номера 1, 2, 3 соответственно, что и делают большинство разработчиков VM, но если поступить не так и пронумеровать опкоды их ASCII кодом, используя в качестве образца для литералов какой-нибудь распространенный язык (например JavaScript или Scheme ;) ). Например так:

• Начало списка -- ( -- 0x28
• Конец списка -- ) -- 0x29
• Разделитель -- , -- 0x2C
• nil -- # -- 0x23

И получим бинарный код, который можно будет открыть в простом текстовом редакторе и почти сразу понять, что делает программа (почти сразу, потому что мы не обсуждаем как закодировать целые числа или строки или что еще у нас может быть элементом списка)

     ( #, 4, 3, 2, 1)

Список храним задом наперед, потому что списки в лиспе строятся "задом-наперед" из cons-cell'ов следующим образом:

    (1 . (2 . (3 . (4 . nil))))
    (cons 1 (cons 2 (cons 3 (cons 4 ()))))

Дальнейшие размышления на тему читайте в блоге Joe Armstrong.

Ruby loves PageRank

Довел до ума обещанный PageRank на Ruby. Забрать можно из моего гит репозитория. Код закомментирован, примеры использования в тестах. Тесты и идея взяты из этой статьи.

В кратце можно описать алгоритм так:

1. Пусть у нас есть n страниц, на каждой из которых I_j ссылок. Мы хотим оценить некую "важность" страницы, с помощью которой можно было бы сказать, какая страница "авторитетнее", на основе количества ссылок на эту статью и "важности" страниц, с которых ведут ссылки. Важность и обзовем словом PageRank.
2. Предположим, что если страница j ссылается на страницу i, то она отдает ей 1/|I_j| своей "важности".
3. Составляем матрицу ссылок следующим образом: в клетке S_i,j стоит число 1/|I_j|, если на j-ой странице есть ссылка на i-ую, 0 в противном случае.
4. У нас получается квадратная матрица, в которой по диагонали стоят нули, а сумма всех чисел в столбце равняется единице.
5. Чтобы посчитать "важность" каждой страницы необходимо найти собственный вектор V полученой матрицы H, соответствующий собственному значению 1. V_i — важность страницы i. Для этого воспользуемся простейшим итерационным методом.
6. В данном решении возникают проблемы, типа висячей страницы, которая не ссылается ни на какие другие. Такая страница перетягивает на себя всю "важность" страниц, которые на нее ссылаются. Для этого мы интерпретируем H в вероятностном аспекте, о чем говорится в статье. Также в ней рассматриваются другие проблемы. Для понимания процесса рекомендую с ней ознакомится.

Комментарии и дополнения к коду приветствуются.