Очередной перевод идиомы (на самом деле, не совсем идиомы, чуть ниже поймете почему) с сайта Idiomatic D, в котором показан довольно интересный код, который смело можно отнести в раздел невменяемого программирования из-за очень нестандартного подхода автора к решению совсем нетривиальной задачи.
Я хочу познакомить вас с этим шедевром программистской мысли, который реально удивит вас тем, что можно создать генератор псевдослучайных чисел на стадии компиляции.
В январе 2016 года анонимный программист опубликовал на форуме как доказательство концепции (Proof-of-concept) хитрый генератор случайных чисел, работающий на стадии компиляции:
/+ CTRNG
Proof-Of-Concept Генератор псевдослучаных чисел на этапе компиляции
Пожалуйста, никогда не делайте ничего подобного !
Дурачась с метапрограммированием в D, я наткнулся на интересный сценарий.
Мне пришло в голову, что возможно, проведя некоторую работу я смогу получить
функционирующий на стадии компиляции генератор случайных чисел, несмотря на ограничения
D в метапрограммировании для поддержания детерминированности некоторых вещей.
Некоторые из них могут показаться вам очевидными, некоторые - интересными, является ли
они ошибками, я не знаю. Возможно, все это бесполезно, если не пытаться саботировать
кодовую базу
Примечание: все это разработано специально с минимальной зависимостью от других
модулей (даже стандартных), поэтому некоторые вещи реализованы неидиоматическим
(читай: странным) путем.
+/
/+
Шаг 1
Нам нужно нечто, для использования в качестве зерна. К счастью, в D есть ключевое слово
__TIMESTAMP__, которое сообщает о времени начала сборки в следующем формате:
Wed Jan 20 18:04:41 2016
Конкретное содержимое функции не имеет значения.
Важно лишь то, что на вход функции попадает временная метка, а на выходе получается большое
число без знака.
Можете спокойно относится к этой реализации, так как она не имеет значения. Имеет смысл лишь то, что
таким способом мы можем получить псевдослучайное зерно на этапе компиляции.
Можно было бы аккуратно разобрать временную метку, но все это - хак, так почему
бы не сделать его еще более хакерским ?
+/
ulong timestampToUlong(string stamp)
{
ulong result;
foreach_reverse(c; stamp)
{
result += c;
result *= 10;
}
return result;
}
/+
Шаг 2
Далее, нам потребуется возможность отслеживания некоторого состояния. D разработан
таким образом, чтобы конструкции времени компиляции не могли иметь используемого постоянного
состояния. Так что, этот шаг займет некоторое время.
Для начала нам нужно что-то, что мы можем запросить, что может дать разные результаты
в разное время, когда мы называем это (например, нечистым). Для этого у нас есть следующее
шаблонное перечисление. Это явная константа, дающая количество членов верхнего уровня
в текущем модуле.
Однако это число может изменяться по мере разрешения других шаблонов и миксинов.
Технически каждый экземпляр отличается, но поскольку грязные детали скрыты внутри значения
параметра по умолчанию, его можно использовать так, как если бы оно всегда было одинаковым.
+/
enum counter(size_t x = [__traits(allMembers, mixin(__MODULE__))].length)=x;
/+
Шаг 3.
Чтобы шаг 2 работал, нам также нужна возможность добавлять элементы между использованиями
`counter`. Они должны иметь уникальные имена, поэтому нам понадобится способ генерировать
имена. Шаг 2 уже дал нам источник увеличения чисел, поэтому мы можем тривиально генерировать
имена, основываясь на значении `counter`.
Итак, мы определяем метод для получения строки, содержащей новое уникальное объявление,
которое мы можем использовать в `mixin ()`.
+/
char[] member(ulong x)
{
char[] buf = "void[0] _X0000000000000000;".dup;
enum mapping = "0123456789abcdef";
foreach_reverse(i; buf.length-17 .. buf.length-1)
{
buf[i] = mapping[x & 0xf];
x >>= 4;
}
return buf;
}
/+
Шаг 4.
Это простая обертка, объединяющая `member` и `counter` под одним именем, что немного
упрощает приращение счетчика.
+/
mixin template next()
{
mixin(member(counter!()));
}
/+
Шаг 5
Наконец, мы определяем простой XorShift64* RNG.
На самом деле у нас нет произвольного изменяемого состояния (пока?), так что это зависит
от того, что компилятор D кеширует предыдущие экземпляры шаблона:
Во-первых - это специализация, представляющая наше семя.
Во-вторых, как обрабатываются все последующие экземпляры xorShift, снова используя преимущества
изменения параметров по умолчанию.
+/
template xorShift(size_t x = counter!())
{
static if(x == 0)
{
enum xorShift = timestampToUlong(__TIMESTAMP__);
}
else
{
// Имя предыдущего результата для уменьшения синтаксического шума
enum y = xorShift!(x-1);
enum xorShift = 0x2545_f491_4f6c_dd1dUL
* (((y ^ (y >> 12)) ^ ((y ^ (y >> 12)) << 25)) ^ (((y ^ (y >> 12)) ^ ((y ^ (y >> 12)) << 25)) >> 27));
}
}
/+
Теперь давайте используем это !
+/
// Два экземпляра xorShift приводят к одному значению
static assert(xorShift!() == xorShift!());
// Тем не менее, мы можем сохранить одно значение,
enum a = xorShift!();
// ... обновляем значение,
mixin next;
// ... и сохраняем другое значение,
enum b = xorShift!();
// ... и они не одинаковы.
static assert(a != b);
/+
Более того, поскольку у нас есть начальное время, все они будут отличаться каждый раз,
когда вы компилируете этот код.
+/
pragma(msg, a);
pragma(msg, b);
mixin next;
/+
Примечание переводчика: орел или решка на этапе компиляции
+/
mixin template headsOrTails(size_t x)
{
static if(x % 2 == 0)
{
pragma(msg, "Heads!");
}
else
{
pragma(msg, "Tails!");
}
}
mixin headsOrTails!(xorShift!());
/+
Заключение
Это действительно простое доказательство концепции.
«Лучшая» версия могла бы использовать реализацию счетчика с рекурсивным сканированием, которая
искала бы символы, помеченные определенным пользовательским атрибутом, чтобы позволить
продвижение состояния ГСЧ внутри структур и тому подобное.
Но опять же, весь этот код - зло, и я не буду больше ничего с ним делать.
+/
void main()
{
// Не вставляйте ничего сюда !
}
Результат:
14647582835942007962LU 17274775622522094364LU Heads!
Как говорится, без комментариев, мы лишь взяли на себя смелость перевести и несколько переработать комментарии автора.
