Интерпретация во время компиляции, или Альтернативное понимание лямбд в C++11
22 мин
На Хабре недавно проскочила ещё одна статья про вычисления на шаблонах C++ от HurrTheDurr. В комментариях к ней лично я увидел вызов:> С каждым новым релизом количество способов нетривиально вывихнуть себе мозг при помощи С++ продолжает увеличиваться)
> > Особенно, если не менять подход к реализации игрового поля и продолжать пытаться все вычисления выполнять не над константами, а над типами.
А так ли сложно будет написать универсальный вычислитель на типах, более удобный для программирования, чем клеточный автомат? Как оказалось, несложно; я в 30 раз больше времени потратил на эту статью, чем на написание и отладку собственно кода вычислителя.
Чуть раньше AveNat опубликовала введение в лямбда-исчисление в двух частях, так что вдохновение пришло мгновенно. Хотелось, чтобы можно было (образно) писать так:
#include <iostream>
#include <LC/kernel.h>
#include <LC/church_numerals.h>
int main()
{
// Представление натуральных чисел в виде лямбда-абстракций
typedef ChurchEncode<2> Two; // 2 = λfx.f (f x)
typedef ChurchEncode<3> Three; // 3 = λfx.f (f (f x))
// * = λab.λf.a (b f)
typedef Lambda<'a', Lambda<'b', Lambda<'f',
Apply<Var<'a'>, Apply<Var<'b'>, Var<'f'> > >
> > > Multiply;
// Вычисление (* 2 3)
typedef Eval<Apply<Apply<Multiply, Two>, Three>> Output;
// Переход обратно от лямбда-абстракций к натуральным числам
typedef ChurchDecode<Output> Result;
std::cout << Result::value;
}
А на выходе получать такое:
ilammy@ferocity ~ $ gcc cpp.cpp
ilammy@ferocity ~ $ ./a.out
6
Статья получилась несколько великоватой, так как мне хотелось рассказать обо всех интересных штуках, которые здесь используются. И ещё она требует базового набора знаний о лямбда-исчислении. Приведённых выше обзоров, среднего знания C++ (с шаблонами), и здравого смысла должно быть достаточно для понимания содержимого.
Под катом находится очередное прокомментированное конструктивное доказательство Тьюринг-полноты шаблонов C++ в виде compile-time интерпретатора бестипового лямбда-исчисления (плюс печеньки в виде макросов и рекурсии).
