В связи с отсутствием времени, интернета и компьютера в ближайшем будущем
решил показать вам свои поделки.
Compile-time template library (сttl) — это небольшая экспериментальная
библиотечка шаблонов, не зависящая от каких-либо сторонних библиотек
(эпизодически boost::preprocessor, можно безболезненно открутить). Но
библиотекой это назвать довольно трудно, поскольку в основном это идеи,
возможно еще сырые, но заслуживающие внимания и критики общественности.
А может быть и нет, посмотрим. Причины, которые толкают меня на показ
объективно сырого кода будут объяснены в дальнейшем. А пока...
В составе присутсвуют:
cttl::lambda - реализация лямбда-нотации для шаблонных функций (да,
существует boost::mpl, погодите ругаться). Используется примерно так:
typedef plus<
mul<num<2>, mul<_1, _1> > ,
minus<mul<num<3>, _2>, num<4> >
> expr;
cout << lambda<expr, num<1>, num<2> >::result::value << endl; // 4
Ничего особенного, пять плэйсхолдеров и немного функций(пусть будут
метафункции).
cttl::bind — работает почти как лямбда, но не производит вычисления
выражений,- просто заменяет параметры в дереве:
typedef bind<plus<_1, num<2> >, num<4> >::result r;
//r == plus<num<4>, num<2> >
cttl::typelist — список типов. Отличительная особенность-компактность
реализации: preprocessed файл на 64 типа (именно столько шаблонных
параметров поддерживает vc7.1) занимет около 4 кб.
Но все это рабочие инструменты, необходимые для весьма интересной вещи —
обобщенной рекурсии. Для ясности пару примеров:
'Классический' факториал:
template<int n>
struct Factorial {
enum { value = n * Factorial<n-1>::value };
};
template<>
struct Factorial<0> {
enum { value = 1 };
};
Простой пример. Вызов функцией самой себя и специализация для завершения.
Но большинство рекурсивных функций на шаблонах не страдают простотой и
изяществом (хотя это субъективно).
cttl::recursion не поддерживает явное задание результатов отдельных итераций,
а реализует следующий принцип — указывается первый тип, функция
перехода между типами, критерий остановки и тело рекурсии. Значение рекурсии автоматически вычис
сяется, используя исходные данные. Т.е. используя cttl::recursion
невозможно задать отдельное значение (0=>1 для факториала). Этот класс исполь
зуется только для обобщение самого понятия рекурсии, а критерий остановки
задается явно, с использованием предиката для применения к каждому типу(значению).
Вариант факториала с использованием cttl::recursion:
typedef recursion_starter<
rec::params<num<5> > // начальное значение
,equal<rec::item, num<0> > // условие завершения
,minus<rec::item, num<1> > // переход к следующему элементу
,mul<rec::item, rec::current> // f(n)=n*f(n-1)
>::result r;
cout << r::current::value << endl; // 120
сущность rec::item представляет собой текущий итерируемый элемент (по очереди 4,3,2,1)
rec::current — результат рекурсии на каждом шаге ( 5, 20, 60, 120, 120)
еще есть rec::index представляющий из себя номер итерации
все эти 'заменители' можно использовать внутри любой из трех функций.
Это был пример 'чистой' рекурсии. Что значит 'чистая' ? В рассмативаемом контексте
это значит что для _пяти_ значений 5,4,3,2,1 тело функции было вызвано 4 раза.
Так же существует итерационный режим использования, при котором тело функции
задается посредством второго параметра(так как функция перехода в данном примере
вычислялась 5 раз), а функция перехода — четвертым. Такой режим используется для
работы со списками типов, при необходимости обработки каждого элемента в списке
//Теперь вычислим длину списка:
typedef typelist<int, char, float> my_list;
typedef recursion_starter<
rec::params<my_list>
,equal<rec::current, null_list>
,rec::index // возвращаем номер итерации
,next<rec::current> // итерируемся здесь
>::result r3;
cout << r3::index::value << endl; //3
// вычисление длины списка другим способом
typedef recursion_starter<
rec::params<my_list, num<0> >
,equal<rec::current, null_list >
,plus<rec::item, num<1> >
,next<rec::current>
>::result r4;
cout << r4::item::value << endl; //3
//еще несколько функций:
// получение элемента списка по индексу (нумерация с 1)
// аналог TypeAt Александреску
typedef typelist<int, char, float, double, long> my_list1;
typedef recursion_starter<
rec::params<my_list1>
,equal<rec::index, num<1+3> > // нужен третий - четвертый не обрабатывается
,rec::current
,next<rec::current>
>::result r5;
// list<float, list<double, list<ling, null_list> > >
cout << typeid(r5::item).name() << endl << endl;
// получение суммарного рамера типов из списка
typedef recursion_starter<
rec::params<typelist<int, char, float>, num<0> > // num<0> используется в качестве аргумента
// plus для последней итерации
,equal<rec::current, null_list >
,plus<rec::item, sizeof_<get_type<rec::current> > >
,next<rec::current>
>::result r6;
cout << r6::item::value << endl; //9
cout << sizeof(int)+sizeof(char)+sizeof(float) << endl; //9
// начинается самое интересное
// Обращение(реверс) списка
typedef recursion_starter<
rec::params<typelist<int, char, float>, null_list >
,equal<get_type<rec::current>, null_list>
,list<get_type<rec::current>, rec::item> // list на самом деле является метафункцией :)
,next<rec::current>
>::result r7;
// list<float, list<char, list<int, null_list > > >
std::cout << typeid(r7::item).name() << std::endl;
// К каждому элементу списка можно применить какую-нибудь метафункцию(любую)...
// например, сделать все типы указателями...
typedef recursion_starter<
rec::params<r7::item, null_list >
,equal<get_type<rec::current>, null_list>
,list<ref<get_type<rec::current> >, rec::item>
,next<rec::current>
>::result r8;
// list<int*, list<char*, list<float*, null_list > > >
std::cout << typeid(r8::item).name() << std::endl;
Текущая реализация при создании списка автоматически переставляет его элементы,
поэтому приходится применять рекурсию дважды, хотя теоретически это возможно исправить.
Последние примеры демонстрируют всю(?) силу применяемого подхода и показывают
как можно логично и главное достаточно просто и прозрачно реализовать некоторые
алгоритмы для работы с шаблонами в compile-time.
К сожалению мне физически не хватило времени(буквально на днях вступаю в ряды РА)
для полировки этих шаблонов, поэтому весьма вероятно наличие ошибок и недоработок
(в частности в итерационном режиме некорректно обрабатывается rec::index в случае наличия менее
двух элементов). Из недоработок — recursion_starter не пригоден для использования
внутри lambd'ы, хотя это можно сделать без особых усилий, используя bind, который первоначально для этого и создавался.
Исходники прилагаются.
PS. Это не велосипеды, это 4fun.
Здравствуйте, Юрий Жмеренецкий, Вы писали:
ЮЖ>Но все это рабочие инструменты, необходимые для весьма интересной вещи —
ЮЖ>обобщенной рекурсии. Для ясности пару примеров:
В функциональном программировании есть понятие обобщенной рекурсии, имя ему — fold (свертка?).
В boost::mpl fold и его родственники
имеются.
Вычисление факториала с помощью fold (хотя есть мнение, что вычисление факториала упростить невозможно, только усложнить):
#include <boost/mpl/fold.hpp>
#include <boost/mpl/range_c.hpp>
#include <boost/mpl/arithmetic.hpp>
using namespace boost::mpl;
template <int N>
struct factorial : fold<
range_c<int, 1, N+1>
,int_<1>
,times<_1, _2> >::type {
};
#include <iostream>
int main(int argc, char* argv[]) {
std::cout << factorial<4>::value;
return 0;
}
Если посмотреть на исходники алгоритмов MPL, можно увидеть, что (почти?) все они реализованы в с помощью метафункций семейства fold.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Здравствуйте, Dmi_3, Вы писали:
D_>Вот пример кода вычисляющего простые числа а не факториал.
хъ
D_>Я не ставил целью уменьшать размер кода но
D_>аналогичный код реалтайма лишь немного короче.
D_>Было бы интересно посмотреть реализацию с использованием Вашей библиотеки.
Ок...
Решение 'в лоб':
Сначала вспомогательная функция
// is_div(n,m) - проверка факта делимости n на m.
// is_div(9,2) - false
// is_div(9,3) - true
// Работает так:
// Если число m является делителем n то cуммируя некоторое число раз
// m с самим собой получим n, если же результат больше n - значит n не делится на m
template<class, class>
struct is_div
{
template<class n, class m>
struct apply
{
typedef typename lambda<
recursion<
rec::params<num<0> >
,greater_eq<rec::current, plus<n, m> >
,equal<rec::current, n>
,plus<rec::current, m>
>
>::result::item result;
};
};
// Проверка числа на простоту. Медленный вариант, т.к.
// сначала вычисляется количество делителей числа
typedef num<33> n;
typedef typename lambda<
recursion<
rec::params<num<2> , num<0> >
,equal<rec::current, plus<cttl::div<_1, num<2> >, num<1> > >
,plus<is_div<n, rec::current>, rec::item>
,plus<rec::current, num<1> >
>
,n
>::result::item divisors_count; // количество делителей
// result = (divisors_count == 0)
typedef typename lambda<equal<divisors_count, num<0> > >::result result;
// Проверка числа на простоту. Улучшенный вариант
// Если число составное, тест останавливается на первом делителе
typedef num<47> n;
typedef typename lambda<
recursion<
rec::params<num<2> , num<0> >
// Остановится если
,logical_or<
//1) текущий элемент == n/2+1 (проверили n/2 чисел, результат не найден)
equal<rec::current, plus<cttl::div<_1, num<2> >, num<1> > >
//2) или найден делитель
,equal<is_div<_1, rec::current>, true_value >
>
// если число простое, то произойдет остановка по первой причине(см.выше)
// проверим, что дошли до конца
,equal<rec::current, cttl::div<minus<n, num<1> >, num<2> > >
// переход к следующему
,plus<rec::current, num<1> >
>
,n
>::result::item result;
Еще пара функций. Можно, например, получить список всех делителей числа.
Возврещается typelist.
typedef num<48> n;
typedef typename lambda<
recursion<
rec::params<num<2> , null_list >
,equal<rec::current, plus<cttl::div<_1, num<2> >, num<1> > >
,meta_if<equal<is_div<_1, rec::current>, true_value >
,list<rec::current, rec::item>
,rec::item
>
,plus<rec::current, num<1> >
>
,n
>::result::item result;
// список простых чисел до n
typedef num<20> n;
typedef typename lambda<
recursion< rec::params<num<1> , null_list >
,equal<rec::current, n>
,meta_if<equal<is_prime_opt<rec::current>, true_value >
,list<rec::current, rec::item>
,rec::item>
,plus<rec::current, num<1> >
>
,n
>::result::item result;
