Здравствуйте, kov_serg, Вы писали:

Pzz>>Я к тому, что каждому инструменту свое применение.
_>Категорически поддерживаю. Растраивает только то что раньше C++ можно было применить куда угодно,
_>а теперь С++(n+1) уже даже на winxp не работает

Работает — используй GCC или Clang, либо настрой MSVS 2015 соответствующим образом — там ЕМНИП загвоздка с используемой версией SDK.

_>и это видимо не предел.

Не надо сгущать краски — это лишь особенность Windows SDK — соответственно и у C те же самые проблемы
C++17, который официально ещё даже не вышел, уже работает даже не древнем железе типа Commodore 64:
https://www.youtube.com/watch?v=zBkNBP00wJE

LVV>>http://www.pdfbooksplanet.org/tags/Chris+Weed/
К>Жалко, что она выложена на какие-то жлобские файлохранилища.
К>Варез? (украдено у амазона?)
Мне знакомый аспирант презентовал.
Могу прислать. На какой ящик?
К>Вся вода — в коде.
К>Читать по сто раз один и тот же паттерн хвостовой рекурсии — тоскливо.
Повторение — мать учения...

LVV>Неистово рекомендую!

Лаптев, эти говно-книги можно читать до бесконечности. Программировать надо а не создавать себе искуственные трудности а затем героически их преодолевать.

_>Вот что меня настораживает так это такие книги. Они решают искуственные проблемы искуствееными методами. И все рады как это круто.

+1.

_>C++ идёт неведомо куда, он создаёт всё новые и новые трудности которые потом пытается преодолеть.

+1 но только он уже там.

Вообще спасибо за сказанное. Понимание оного отличает инженеров от неинженеров.

LVV>>Неистово рекомендую!
ОК>Лаптев, эти говно-книги можно читать до бесконечности. Программировать надо а не создавать себе искуственные трудности а затем героически их преодолевать.
С вами все понятно: че тут думать — трясти надо...

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, kov_serg, Вы писали:

Pzz>>>Я к тому, что каждому инструменту свое применение.
_>>Категорически поддерживаю. Растраивает только то что раньше C++ можно было применить куда угодно,
_>>а теперь С++(n+1) уже даже на winxp не работает
_>>и это видимо не предел.

EP>Работает — используй GCC или Clang, либо настрой MSVS 2015 соответствующим образом — там ЕМНИП загвоздка с используемой версией SDK.

Вы видимо не в курсе. Вы можете использовать любую SDK. Он работать всё равно не будет.
Линковщик специально не хочет генерировать исполняемые файлы под winxp. И без плясок с бубном в виде editbin не пашет.
Visual Studio 97 win9x+ (в win7 уже не пашет, с надписью имеются известные проблемы и падает при открытии проекта)
Visual Studio 2003 winnt+
Visual Studio 2005,2008 winxp+
Visual Studio 2010-2015 win7+
clang win7+
mingw win7+ -- полностью зависит от msvcrt.dll которая win7+, своих статических библиотек нет. И не будет политика партии запрещает.
cygwin win7+ -- старых репозиториев нет, те что в архивах там нет C++11

http://louis.steelbytes.com/vs2008_vs_win40.html
https://supportxpdotcom.wordpress.com/2012/03/28/what-makes-apps-developed-with-visual-c-11-beta-not-run-on-windows-xp

Если даже вы скажете линковщику хочу winxp от ответит отказом.

/SUBSYSTEM:WINDOWS,4.0 /OSVERSION:4.0 => warning LNK4010: invalid subsystem version number 4.00; default subsystem version assumed
/SUBSYSTEM:WINDOWS,5.01 /OSVERSION:5.1 => warning LNK4010: invalid subsystem version number 5.01; default subsystem version assumed

Пока только editbin помогает, но и его вылечат.
Так что все новые и модные фичи потихоньку выдавливают старые версии винды. С технической стороны никаких проблем
может только с реализацией многопоточности в C++11 на conditional_variables, но можно костыль прикрутить
или просто не многопоточность. Но нет.

Так что, скоро будет только Win10+ к бабке не ходи. Ах да и comodor64.

EP>Не надо сгущать краски — это лишь особенность Windows SDK — соответственно и у C те же самые проблемы
EP>C++17, который официально ещё даже не вышел, уже работает даже не древнем железе типа Commodore 64:
EP>https://www.youtube.com/watch?v=zBkNBP00wJE
Дык при желании можно сделать любую целевую платформу на llvm, но это вам придётся делать самому.
Бинарный код оно генерит, и он спокой но мог бы работать. Но он искуственно сделано так что бы он не работал.
И телеметрия которая появилась в 15 студии — вы просили — нате. Вобщем выглядит это очень весело.
Даже какой нибуть ср$#@й PHP будет хотель win7+. Почему, как вы думаете? Кому-то ведь это надо.

Так что просто попробуйте сами собрать консольный hello_world с лямбдами в 2015 студии и запустить в виртуалке на winxp и прифигеете.

Здравствуйте, мыщъх, Вы писали:

М>а есть _универсальный_ рецепт для си (си++) ?

Его ни для какого языка нет. Дадут тебе платформу, где всей памяти меньше необходимого, и приплыли.

Здравствуйте, Олег К., Вы писали:

LVV>>Неистово рекомендую!

ОК>Лаптев, эти говно-книги можно читать до бесконечности. Программировать надо а не создавать себе искуственные трудности а затем героически их преодолевать.

Им не программировать, им учить (читай — мучить) студентов сиплюсплюсом, который все хочет превратиться в Хаскель.

Здравствуйте, kov_serg, Вы писали:

EP>>Работает — используй GCC или Clang, либо настрой MSVS 2015 соответствующим образом — там ЕМНИП загвоздка с используемой версией SDK.

_>Вы видимо не в курсе. Вы можете использовать любую SDK. Он работать всё равно не будет.
_>Линковщик специально не хочет генерировать исполняемые файлы под winxp. И без плясок с бубном в виде editbin не пашет.
_>Visual Studio 97 win9x+ (в win7 уже не пашет, с надписью имеются известные проблемы и падает при открытии проекта)
_>Visual Studio 2010-2015 win7+

А что, в 2015 Студии Platform toolset уже нет?

	В VS2013 их есть

и оно под ХР таки работает.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, cures, Вы писали:

C>>Здравствуйте, _hum_, Вы писали:

__>>>так не всегда же к хвостовой можно свети — это раз. а во-вторых, если нет гарантии, то код подойдет только для баловства.

C>>К хвостовой сводятся только элементарные циклы, это не очень интересно.
S>CPS же

интересно, спасибо. только по прочтению я все же так и не понял,

существует ли алгоритм преобразования любой чистой рекурсивной функции в функцию с хвостовой рекурсией, причем с ростом накладных расходов на стек у преобразованной функции не более O(размер всех аргументов)?

иными словами, можно ли ожидать, что хороший компилятор (гипотетически) при необходимости всегда может сам преобразовать любую рекурсию в хвостовую?

Здравствуйте, LaptevVV, Вы писали:

LVV>Понятная даже начинающим.

Кстати насчёт понятности.
Вот, например, реализация рекурсивных лямбд.

Внезапная императивность.
1) Создаётся пустая обёртка,
2) затем её копия (!) захватывается лямбдой,
3) затем эту лямбду присваивают исходному (!) экземпляру.

Почему? Ну, мне* понятно, почему. Потому же, почему в ML есть разница между let и let rec.
Только в С++ let rec почти отсутствует, и вот именно здесь мы налетаем на illformed с типами, а если бы не налетели, то налетели бы на undefined со значением.
*) потому что я не начинающий

Внезапные голые указатели на стековые переменные.
Вот тут уже у меня мозг заскрипел. Надо отслеживать корректность времени жизни всех экземпляров обёртки — как оригинального, так и захваченных во всех копиях лямбды.
Ну, скрестим пальцы, что там всё хорошо.

shared_ptr на функцию, скопировавшую лямбду, захватившую обёртку. Что там с кольцевыми ссылками? Мамой клянус?

Наконец, абсолютная беззащитность перед некорректным использованием — как следствие императивности.
Действительно, — стоит нам не присвоить лямбду, или перепутать порядок использования, — и привет.

func_wrapper<void()> f;
switch(rand()%3) {
case 0:
  foo(f,f);
  break;
case 1:
  f = [f]() {};
  foo(f,f);
  break;
case 2:
  foo(f = [f](){}, f);
};

Мне кажется, что вот такие вещи просто обязательно надо раскрывать.


Ну и наконец, старый приём с Y-комбинатором. Собственно, let rec в ML именно так и устроен.

const auto fib = [](int n) {
  const auto f = [](auto&& g, int n) -> int { return n<2 ? n : g(g,n); };  // тип результата невозможно вывести, поэтому указываем явно
  return f(f,n);
};

Здравствуйте, LaptevVV, Вы писали:

К>>Варез? (украдено у амазона?)
LVV>Мне знакомый аспирант презентовал.
LVV>Могу прислать. На какой ящик?

Думаешь, мне богиня программирования нашептала во сне отдельные страницы этой книжки?
Или я всё-таки побрил Оккама и скачал целиком с варезохранилища, попутно заметив ссылку на амазон?

К>>Вся вода — в коде.
К>>Читать по сто раз один и тот же паттерн хвостовой рекурсии — тоскливо.
LVV>Повторение — мать учения...

Ну, методически, оно верно.

Продолжаю вдумчивое чтение.
Вот с мемоизатором комбинатор неподвижной точки удалось сделать. Но как!

struct MyFib { // это важно! именованный класс, а не посторонняя абы какая функция

  // именованный класс потребовался для ручного решения неподвижной точки типа
  int operator()(memoizer<int(int),MyFib>& m, int x) const { 
    return x < 2 ? x : m(x-1) + m(x-2);
  }

  // хотя можно было и отдать это компилятору (но всё равно изолировать через класс)
  template<class M>
  int operator(M&& m, int x) const {.....}

  // раз уж знаем про мемоизатор, то почему бы не сделать членом?
  // раз уж членом, то вспомним про mutable (в книжке забыли)
};
auto my_fib = memoize<int(int)>(MyFib);

Между тем, есть же возможность мемоизировать голые функции

// вот почему нам нужна изоляция через имя: иначе отхватываем рекурсивный тип мемоизатора
int fib_(memoizer<int(int), int(memoizer<int(int), memoizer<.....>)> m, int x) {
  return x<2 ? x : m(x-1) + m(x-2);
}

// попробуем через шаблон:
template<class M> int fib_(M&& m, int x) {.....}
auto fib = memoize<int(int)>(fib_); // так тоже нельзя, шаблон - не первоклассная сущность

// зато предобъявление хорошо работает!
int fib_(int);
auto fib = memoize_nonrecursive<int(int)>(fib_); // первая версия мемоизатора, без неподвижной точки
int fib_(int x) { return x < 2 ? x : fib(x-1) + fib(x-2); }

// то же самое можно и с классом
struct Fib {
  mutable memoizer_nonrecursive_member<int(int),Fib> m_; // сделаем ещё одну версию мемоизатора
  Fib() : m_(wrap{},this) {} // трюк с инициализацией указателем на несозданного самого себя
        { m_.setup(this);  } // (или двухфазную инициализацию сделать...)
  int operator(int x) const {.....};
} fib;

// полиморфные лямбды - в отличие от шаблонов, имеют конкретный тип!
// просто у них operator() шаблонный
auto fib_ = [](auto&& m, int x) -> int { return x < 2 ? x : m(x-1) + m(x-2); };
auto fib = memoize_recursive<int(int)>(fib_);
// или, в одну строку
auto fib = memoize_recursive<int(int)>([](auto&& m, int x) {....});

Ну и кстати уж, комбинатор не мемоизирующей неподвижной точки — делается так же, как мемоизирующий, только выкинуть лишнюю начинку.

auto fib = fix<int(int)>([](auto&& f, int x) {.....});

Вдогонку про мемоизацию.
С ней связан ряд проблем.

1. Побочные эффекты. Надо сразу договориться, что мемоизируемая функция чиста по входам, и нам пофиг на её побочные плоды.
Ну и тут просто грех не вспомнить ещё об одном декораторе: трассировщике.

Домашнее задание для читателей книги:
— написать декоратор, печатающий входы и результаты вычислений

auto p = memoize(trace("fib", [](auto&& f, int x) {...}));
p(5);

печатает        подразумевается
fib(5) = ... // fib(3)+fib(4)
fib(3) = ... // fib(1)+fib(2)
fib(1) = ...
fib(1) = 1
fib(2) = ... // fib(0)+fib(1)
fib(0) = ...
fib(0) = 0
fib(2) = 1
fib(3) = 2
fib(4) = ... // fib(2)+fib(3)
fib(4) = 3
fib(5) = 5

— декоратор, делающий отступ на глубину рекурсии

fib(5) = ... // fib(3)+fib(4)
  fib(3) = ... // fib(1)+fib(2)
    fib(1) = ...
    fib(1) = 1
    fib(2) = ... // fib(0)+fib(1)
      fib(0) = ...
      fib(0) = 0
    fib(2) = 1
  fib(3) = 2
  fib(4) = ... // fib(2)+fib(3)
  fib(4) = 3
fib(5) = 5

Какие есть способы пропихнуть величину отступа в функцию? (Я навскидку могу предложить три способа, два из которых допиливают мемоизатор, а один — только трассировщика).

2. Управление кэшем. Чтобы он не рос бесконечно, надо предпринимать меры по его очистке.
Это может быть как внешняя операция, строго между вызовами, так и автоматизированная внутренняя, прямо по ходу рекурсивного вызова функции.
(То есть, мы соглашаемся на очень долгую работу функции, но противимся тому, чтобы она случайно выжрала всю память. Время-то у нас — неограниченный ресурс).

3. Зацикливание. Хороший мемоизатор может проверить, что функция не зациклилась.
Для этого надо вести журнал ожидаемых, но ещё не выполненных действий.

4. Многопоточность. Это не только синхронизация доступа к кэшу, но и независимая диагностика зацикливаний для каждого потока отдельно.

Книга — трэш. На серию блог постов с натяжкой потянет.

> Each recursive algorithm was run vs. the STL implementation on a long sequence in a
> vector, list, and set. The following chart shows which algorithm was faster when run with
> a large number of iterations.

Афтар не написал ни каким компилятором, ни на какой платформе, ни с какими флагами оптимизации компилировал, не приводит ни одной тестовой программы, и даже количественых результатов тестов нет, только same/recursive/STL.

U>Афтар не написал ни каким компилятором, ни на какой платформе, ни с какими флагами оптимизации компилировал, не приводит ни одной тестовой программы, и даже количественых результатов тестов нет, только same/recursive/STL.
Написал. Пункт содержания Compiler

Книжка шикарная настолько, что Кодт ее конкретно разбирает...

Здравствуйте, LaptevVV, Вы писали:

LVV>http://www.pdfbooksplanet.org/tags/Chris+Weed/
LVV>Функциональное программирование на С++.
LVV>Chris Weed.
LVV>Всего 100 с небольшим страниц, но написано шикарно!

10x a lot !

Здравствуйте, _hum_, Вы писали:

__>так а это разве правильно — рекурсивная форма алгоритмов на с++? или уже появилась возможность контроля размера стека?

Иногда полезнее не думать о том, правильно что-то или неправильно.
Иногда полезнее просто сделать хоть как-то. "Хоть как-то" -- это означает не тяп-ляп,
а "любая реализация алгоритма".
Это не значит, что программист халтурит. Просто есть такие алгоритмы, которые можно сформулировать
только так, а не иначе.