Рубрика «c++» - 198

На Хабре недавно проскочила ещё одна статья про вычисления на шаблонах 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 интерпретатора бестипового лямбда-исчисления (плюс печеньки в виде макросов и рекурсии).Читать полностью »

Статья не о том, чем заняться, пока собирается проект.

Фраза «Шаблоны — полноценный, тьюринг-полный, язык» часто воспринимается с недоверием. Это же просто обобщающая возможность современных языков программирования, откуда там вычислительные возможности? Так думал и я. Теперь хочу переубедить остальных, попутно объясняя принципы работы шаблонов для начинающих, вроде меня.

Мое понимание шаблонов впервые пошатнулось после прочтения главы «Метапрограммирование» из книги о С++ от создателя С++ — показалось, что они действительно могут быть полноценным языком программирования внутри языка программирования. Во всяком случае, там точно есть рекурсия. Но лучший способ доказать себе что-то — попытаться сделать, что мы и сделаем.

Существует множество реализаций легендарной игры «Жизнь» Джона Конвея, безумных и не очень. Но все они имеют общий фатальный недостаток: каждая итерация Жизни вычисляется непосредственно во время работы программы. Попробуем это исправить.
Читать полностью »