RE: Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB vector: a practical general purpose immutable sequence.

[Александр Коновалов a . v . konovalov87_AT_mail . ru]

Добрый день, Сергей!
Я прочитал статью Николаса Стуки и других товарищей. RRB-вектора были 
магистерским дипломом Николаса — в его репозитории лежит записка к диплому.
По поводу статьи. В ней рассматриваются Radix-Balanced вектора, которые на тот 
момент использовались в реализации Скалы и предлагается их улучшение — 
Relaxed-Radix-Balanced (RRB) вектора.
Radix-Balanced вектора основаны на деревьях, узлы которых представляют собой 
массивы длиной 32, в листьях лежат пользовательские значения, во внутренних 
узлах — ссылки на потомков. Все узлы, кроме самых крайних, заполнены полностью. 
Крайние левые узлы (как внутренние, так и листовые) могут содержать «пустые» 
значения в начале, крайние правые — в конце. Благодаря этой пустоте, операции с 
началом и концом выполняются за почти константное время (поскольку высота 
дерева растёт медленно и ограничена небольшим числом).
А вот конкатенация двух векторов в общем случае требует линейного времени. 
Исключение — два вектора равной длины 2N без дырок с краёв, только их можно 
сконкатенировать за константу. Да, это случай битонической сортировки :-).
Предложенное Relaxed-Radix-Balanced предлагает ради эффективности конкатенации 
использовать внутренние узлы длиной или 32, или 33 элемента. Дескать, в этом 
случае удастся обеспечить эффективную конкатенацию. Но я прочитал статью и 
описанный там алгоритм я не понял — если конкатенируются два вектора, у которых 
крайние листья не заполнены полностью, то получим новый вектор с нарушенным 
инвариантом — внутренний узел где-то в середине дерева может оказаться заполнен 
не полностью. Не говоря о том, что стоимость конкатенации равна высоте дерева, 
помноженной на m² = 32² = 1024. Для недлинных векторов (высоты не более 2) 
разницы с обычными векторами нет.
А вот задача написать интерпретатор Рефала на Скале и попробовать разные 
реализации векторов интересная. Подумаю на следующий год.
 
С уважением,
Александр Коновалов
 
From: Sergei Romanenko sergei.romanenko_AT_supercompilers.ru <refal@botik.ru> 
Sent: Friday, February 22, 2019 10:43 AM
To: Refal Botik <refal@botik.ru>
Subject: Re: Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. 
RRB vector: a practical general purpose immutable sequence.
 
Короче говоря, если использовать Vector-ы, как они реализованы в стандартной 
библиотеке Скалы, то, в случае алгоритмов типа "разделяй и властвуй" можно себе 
позволить программировать в "нагло-функциональном" стиле.
 
Хороший пример - битональная сортировка:
 
https://github.com/sergei-romanenko/spinalhdl-samples/blob/master/src/main/scala/shs/btsort_f/BitonicSortVN.scala
https://github.com/sergei-romanenko/spinalhdl-samples/blob/master/src/main/scala/shs/btsort_f/README.md
 
Режем вектор пополам, что-то рекурсивно делаем с половинками, получаем два 
новых вектора, которые склеиваем.
  def merge(up: Boolean, x: Vector[Int]): Vector[Int] = {
    // Produces a sorted list, on condition that x is bitonic.
    val l = x.length
    if (l == 1)
      return x
    val h = l / 2
    val (x1, x2) = x.splitAt(h)
    val ok = Vector.tabulate(h)(i => if (up) x1(i) <= x2(i) else x2(i) <= x1(i))
    val y1 = Vector.tabulate(h)(i => if (ok(i)) x1(i) else x2(i))
    val y2 = Vector.tabulate(h)(i => if (ok(i)) x2(i) else x1(i))
    merge(up, y1) ++ merge(up, y2)
  }
 
  def sort(up: Boolean, x: Vector[Int]): Vector[Int] = {
    val l = x.length
    require(isPow2(x.length), "x.length must be a power of 2")
    if (l <= 1)
      return x
    val h = l / 2
    val (x1, x2) = x.splitAt(h)
    val y1 = sort(up = true, x1)
    val y2 = sort(up = false, x2)
    merge(up, y1 ++ y2)
  }
И при этом ничего ужасного не происходит, поскольку конкатенация двух векторов 
из десяти элементов стоит примерно столько же, сколько и конкатенация двух 
векторов длиной по миллиону элементов. И разрезание вектора из миллиона 
элементов - тоже дешево стоит.
 
На всякий случай, обращаю внимание, что Vector - это не Array, поскольку он 
неизменяем (как и выражение в Рефале), отчего и можно утверждать, что 
манипуляции с Vector-ами - это программирование в "функциональном" стиле.
 
Понятно также, что если поручить студенту написать на Скале 
Рефал-интерпретатор, и при этом представить Рефал-выражения Vector-ами, то 
будет работать вполне сносно. Потом можно поручить студенту "закаррить" этот 
интерпретатор в соответствии с рецептами, изложенными в
*       Sergei A. Romanenko. Higher-Order Functions as a Substitute for Partial 
Evaluation (A Tutorial). In First International Workshop on Metacomputation in 
Russia (Proceedings of the first International Workshop on Metacomputation in 
Russia. Pereslavl-Zalessky, Russia, July 2-5, 2008). A. P. Nemytykh, Ed. - 
Pereslavl-Zalessky: Ailamazyan University of Pereslavl, 2008, 108 p. ISBN 
978-5-901795-12-5, pages 145-162. PDF 
<https://pat.keldysh.ru/~roman/doc/2008-Romanenko--Higher-Order_Functions_as_a_Substitute_for_Partial_Evaluation--A.Tutorial.pdf>
  slides 
<https://pat.keldysh.ru/~roman/doc/2008-Romanenko--Higher-Order_Functions_as_a_Substitute_for_Partial_Evaluation--A.Tutorial--slides.pdf>
  eLibrary <https://elibrary.ru/item.asp?id=26998070> 
и тогда получится как бы компилятор, эффективности которого будет заведомо 
достаточно для выполнения заданий из студенческого практикума.
 
А лексер/парсер лепятся элементарно с помощью парсерных комбинаторов:
 
https://github.com/sergei-romanenko/spsc-scala/blob/master/src/main/scala/spsc/SLLParsers.scala
 
Можно поручить 5-ти студентам изготовить 5 вариантов парсера для 5-ти разных 
синтаксисов Рефала (чтобы каждый мог выбирать тот вариант синтаксиса, который 
ему больше нравится).
 
СР