LINUX.ORG.RU

О хвостовой рекурсии

 


3

4

Или с чем ее едят и как ее готовят? Набрел на статью в Википедии, ознакомился, сделал сравнительный замер времени выполнения для приведенного там примера. Результаты впечатлили, особенно если учесть, что тестировал я это для Scala с включенной оптимизацией.пиляторы

Собственно вопросов два.

1. Хотелось бы получше разобраться в устройстве хвосто-рекурсивных функций и их вызовов, дабы объяснить человеку, далекому от этой темы - в чем там магия?

2. Какие еще популярные ЯП и компиляторы поддерживают оптимизацию данного вида рекурсии?

Всем спасибо.

Ответ на: комментарий от anonymous

rc_ptr<B> m_b;

rc_ptr<A> m_a;

Надо либо в A либо в B использовать weak ссылку (std::weak_ptr, например), тогда тут всё будет нормально.

quasimoto ★★★★
()
Ответ на: комментарий от drBatty

я уже приводил пример.

Дай ссылку на код.

Мы сейчас про C++ или про STL разговариваем?

А при чём тут STL? Автор STL != его мнение о C++ распространяется только на STL. Кстати, как тегировать указатели в православном C++ ты так и не показал.

в смысле malloc(3) в C++? нельзя. для этого есть new.

в C++? нельзя. Зачем?

Чего бы ещё такого спросить чтобы посмеяться :)

есть dynamic_cast, этого мало?

Я не хочу RTTI. Ты ко всем потомкам опускаешь с помощью dynamic_cast? Числа тоже опускать с dynamic_cast будешь? А const стирать?

quasimoto ★★★★
()
Ответ на: комментарий от drBatty

Вот только завтра мну переклинит хранить не только длину, но и оффсет, что-бы из «xyzt» сделать «yz». Очевидно, после этой модификации твой код можно будет выкинуть на помойку

Если это твой пример, то ты не понимаешь о чём я говорю. То есть всё ещё не забудешь о *reinterpret_cast<int*>(&x), не перейдешь к рассмотрению более общего *reinterpret_cast<MirrorClass*>(&x) и, наконец, к рассмотрению проблем read-only чтения в произвольном коде private/protected полей которые видны в заголовочном объявлении.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Да, именно так! Я как раз и пытался показать, что циклы разруливаются руками при подсчете ссылок, а GC работает с циклами корректно. О weak(в Objective-C) и std::weak_ptr(в С++) я писал выше уже.

anonymous
()
Ответ на: комментарий от drBatty

Так покажи. Что-то подсказывает мне, что один из указателей у тебя будет не умным. Ну или свой костылек, имитирующий weak_ptr.

anonymous
()
Ответ на: комментарий от quasimoto

я уже приводил пример.

Дай ссылку на код.

см. выше.

Изначальный автор STL с тобой не согласен.

Мы сейчас про C++ или про STL разговариваем?

А при чём тут STL?

а я откуда знаю? ты первый про STL начал, вот и отвечай...

Автор STL != его мнение о C++ распространяется только на STL. Кстати, как тегировать указатели в православном C++ ты так и не показал.

ты не рассказал, ЗАЧЕМ их тегировать?

Я не хочу RTTI. Ты ко всем потомкам опускаешь с помощью dynamic_cast?

да

Числа тоже опускать с dynamic_cast будешь?

ЗАЧЕМ?

А const стирать?

ЗАЧЕМ?

drBatty ★★
()
Ответ на: комментарий от quasimoto

Если это твой пример, то ты не понимаешь о чём я говорю. То есть всё ещё не забудешь о *reinterpret_cast<int*>(&x), не перейдешь к рассмотрению более общего *reinterpret_cast<MirrorClass*>(&x)

не понимаю. Вот и расскажи. Желательно с примером. А то у тебя только с <int**> пример был, вот из него я и исхожу. Других примеров ты не предоставил.

drBatty ★★
()
Ответ на: комментарий от drBatty

ты первый про STL начал, вот и отвечай...

Нет, я сказал «автор STL» == Александр Степанов, альфа-редукция устраняет всякое упоминание STL, как видишь :)

Сказано было к тому, что «C++-- без ООП» это вовсе не «делим на ноль». В Java - да, там даже функцию написать нормально нельзя, так что ООП во все поля. А в C++ и без ООП есть сущности которых нет в Си, так что можно использовать подмножество C++ без ООП как замену Си. Так что «зачем это нужно в С++ в котором ООП» - нужно за тем же зачем и в си, применений полно (на вопросы ЗАЧЕМ даже и не знаешь что и отвечать - кажется, что это и так очевидно), а ООП не всегда в тему. Повторю пример про пакеты бинарного протокола, или про ELF - берём структуру описывающую какой-то его кусок, кастуем ELF в буфер, идём по буферу, находим кусок, кастуем в эту структуру, запоминаем, идём дальше, находим ещё, опять кастуем и запоминаем и т.д.

ты не рассказал, ЗАЧЕМ их тегировать?

1) Мы пишем VM, или 2) смотри код LLVM (wait, oh sh~).

да

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml, да и вообще так делать не принято. В куче проектов есть множество static и const cast-ов и ни одного dynamic.

ЗАЧЕМ?

Потому что long | (short << 63).

ЗАЧЕМ?

Потому что нужно как-то передавать const T* в ...(*)(..., T*, ...).

Ну и

У меня результат в монаде, как мне его вытащить?

ЗАЧЕМ?

У меня 15дцать вложенных монадических трансформеров, как мне их запустить?

ЗАЧЕМ?

У меня все функции тотальны, как мне сделать event loop?

ЗАЧЕМ?

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Сказано было к тому, что «C++-- без ООП» это вовсе не «делим на ноль».

ну дык и говори о том, что ты используешь НЕ C++, а некое его подмножество.

ты не рассказал, ЗАЧЕМ их тегировать?

1) Мы пишем VM, или 2) смотри код LLVM (wait, oh sh~).

ты так и не рассказал.

да и вообще так делать не принято. В куче проектов есть множество static и const cast-ов и ни одного dynamic.

есть куча говнокода, в котором есть куча говна. И что?

Потому что long | (short << 63).

нираспарсил. поподробнее пожалуйста, для тупых.

Потому что нужно как-то передавать const T* в ...(*)(..., T*, ...).

здесь нет ответа на вопрос «ЗАЧЕМ?»

У меня результат в монаде, как мне его вытащить?

а вот здесь есть: как ты его в монаду засунул, так и вытаскивай.

У меня все функции тотальны, как мне сделать event loop?

ЩИТО?

drBatty ★★
()
Ответ на: комментарий от drBatty

Желательно с примером

В том классе было одно поле int*, так что *reinterpret_cast<int**> работало, пусть будет более сложный класс:

#include <string>
#include <iostream>

class Foo {
  public:
    Foo(int n = 1, int c = '2', std::string s = "33") : n(n), c(c), s(s) {}
    int n;
  private:
    char c;
  protected:
    std::string s;
};

struct FooMirror {
    FooMirror ();
    int n;
    const char c;
    const std::string s;
};

int main()
{
    Foo foo;
    FooMirror &foo_ = reinterpret_cast<FooMirror&>(foo);

    std::cout << "Foo { n = " << foo_.n
              << "; c = " << foo_.c
              << "; s = " << foo_.s
              << " }" << std::endl;

    // foo_.c = '\n';                      <- NO WAY
    *const_cast<char*>(&foo_.c) = '\n'; // <- WE ARE FOOLS

}

теперь представим, что это (const-доступ к private/protected полям) происходит автоматически - в чём проблема?

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

теперь представим, что это (const-доступ к private/protected полям) происходит автоматически - в чём проблема?

вот проблема:

#include <string>
#include <iostream>

class Foo {
  public:
    Foo(int n = 1, int c = '2', std::string s = "33") : n(n), c(c), s(s) {}
    int n;
  private:
    char c;
  protected:
    std::string s;
};

struct FooMirror {
	int xxx;
    FooMirror ();
    int n;
    const char c;
    const std::string s;
};

int main()
{
    Foo foo;
    FooMirror &foo_ = reinterpret_cast<FooMirror&>(foo);

    std::cout << "Foo { n = " << foo_.n
              << "; c = " << foo_.c
              << "; s = " << foo_.s
              << " }" << std::endl;

    // foo_.c = '\n';                      <- NO WAY
    *const_cast<char*>(&foo_.c) = '\n'; // <- WE ARE FOOLS

}
$ ./a.out 
Foo { n = 50; c = (; s = 33 }
Ошибка сегментирования

drBatty ★★
()
Ответ на: комментарий от drBatty

ну дык и говори о том, что ты используешь НЕ C++, а некое его подмножество.

Ты тоже используешь НЕ C++, а некое его подмножество. Потому что никто не использует ВЕСЬ С++, это будет каша. Поэтому style guides и существуют.

ты так и не рассказал.

Ты так и не пошёл и не узнал _сам_ зачем это может быть нужно. Даже выше по треду есть пара примеров из LLVM.

есть куча говнокода, в котором есть куча говна. И что?

Так и запишем - ZeroMQ и Crossroads I/O - говнокод, drBatty пишет гораздо лучше, а Martin Sústrik зря сокрушается.

нираспарсил. поподробнее пожалуйста, для тупых.

Тут нужно сделать static_cast<long>(short), иначе получится не то что нужно.

здесь нет ответа на вопрос «ЗАЧЕМ?»

Это просто прелестно :)

У тебя есть const T x, потому что ты умный и ограничил тип. А потом оказалось нужным передать этот x в функцию f с типом аргумента просто T. Что делать? Нестись как джедай переписывать f (и g, и h, и объемлющий класс, и ещё один), форкать библиотеки, пинать авторов?

как ты его в монаду засунул, так и вытаскивай.

Этим ты утверждаешь, что всякая монада является комонадой. Что неправда. Большинство как раз не является. Таковое допущение тут же приводит к противоречиям.

ЩИТО?

Тотальность = терминируемость, так что тьюринг-полных программ уже не напишешь (ну, теоретически).

quasimoto ★★★★
()
Ответ на: комментарий от drBatty

int xxx;

А вот зачем под дурачка косить? Написал бы сразу ((void(*)())NULL)(); в начале main, была бы такая же не относящаяся к теме «проблема».

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Сказано было к тому, что «C++-- без ООП»

ну дык и говори о том, что ты используешь НЕ C++, а некое его подмножество.

Ты тоже используешь НЕ C++, а некое его подмножество. Потому что никто не использует ВЕСЬ С++, это будет каша. Поэтому style guides и существуют.

я использую C++ C ООП. А ты - демагог.

ты так и не рассказал.

Ты так и не пошёл и не узнал _сам_ зачем это может быть нужно. Даже выше по треду есть пара примеров из LLVM.

у тебя копипаста сломалась? ну так скопипасти, раз ещё не сломалась. А то не очень понятно, к чему ты апеллируешь...

есть куча говнокода, в котором есть куча говна. И что?

Так и запишем - ZeroMQ и Crossroads I/O - говнокод, drBatty пишет гораздо лучше, а Martin Sústrik зря сокрушается.

э...

Testimonia (свидетельства - лат.) основан на том, что иногда удобно использовать ссылку на авторитет (какой угодно), например, заявить - «еще Пантагрюэль говорил» или «как доказал Трейчке». При известной начитанности на каждый случай можно найти какую-нибудь цитату, которая наповал убьет противника.

(правила демагога. К.Чапек, №9)

Потому что long | (short << 63).

нираспарсил. поподробнее пожалуйста, для тупых.

Тут нужно сделать static_cast<long>(short), иначе получится не то что нужно.

а что нужно-то?

У тебя есть const T x, потому что ты умный и ограничил тип. А потом оказалось нужным передать этот x в функцию f с типом аргумента просто T. Что делать? Нестись как джедай переписывать f (и g, и h, и объемлющий класс, и ещё один), форкать библиотеки, пинать авторов?

нет. Передать аргумент T в функцию f(T x). Как копию. Потому как если автор ограничил _своё_ x, значит какой-то смысл в этом был. Например такой, что-бы его x НЕ передавали в какую-то функцию, которая _может_ это x изменить (чего не хочется автору класса).

как ты его в монаду засунул, так и вытаскивай.

Этим ты утверждаешь, что всякая монада является комонадой. Что неправда. Большинство как раз не является. Таковое допущение тут же приводит к противоречиям.

ЯННП

Тотальность = терминируемость, так что тьюринг-полных программ уже не напишешь (ну, теоретически).

теоретически, для тьюринг-полных программ нужна бесконечная память и бесконечный стек. А их нет. Т.ч. твои выкладки не интересны IRL.

drBatty ★★
()
Ответ на: комментарий от quasimoto

int xxx;

А вот зачем под дурачка косить? Написал бы сразу ((void(*)())NULL)(); в начале main, была бы такая же не относящаяся к теме «проблема».

при чём тут (*)? проблема int xxx к теме относится непосредственно: невозможно создать зеркальный класс, который полностью соответствует данному. Проблема в том, что данный класс автор _может_ менять в его приватных членах. Именно для того, эти приватные члены и нужны.

drBatty ★★
()
Ответ на: комментарий от drBatty

нужна бесконечная память и бесконечный стек.

У меня такое ощущение, что у тебя стек из двух ячеек - ты что-то спросишь, я отвечу и бам! переполнение стека и вложенные цитаты которые должны как бы демонстрировать абсурдность происходящего, но на самом деле - твоё непонимание :)

В этом и следующем постах целых восемь (8) непониманий. Мне на них ответить или тебе это не интересно и отвечать не стоит (ты считаешь себя всячески правым и т.п.)?

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Мне на них ответить или тебе это не интересно и отвечать не стоит (ты считаешь себя всячески правым и т.п.)?

ну ответь, если сможешь.

вот только ответов в духе

Тотальность = терминируемость, так что тьюринг-полных программ уже не напишешь (ну, теоретически).

не нужно. Лучше статью на уютном про жидкий вакуум допили.

drBatty ★★
()
Ответ на: комментарий от quasimoto

За счёт ленивости такой результат и есть. Со strict совсем хреново получается.

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

anonymous
()
Ответ на: комментарий от drBatty

Ок. Тут логика простая:

1. На счёт ООП. Несколько подобных утверждений ─ «Я использую С++ _с_ шаблонами и _без_ ООП», «Я использую С++ _с_ ООП и _без_ шаблонов», «Я использую С++ _с_ ООП, шаблонами, functional и _без_ RTTI и исключений». Можешь для себя такое утверждение составить ─ есть ведь вещи которые ты _не_ используешь (type level вычисления на шаблонах, например). Так что если я говорю «С++ без ООП» ─ нет причин удивляться и делить на ноль. Точно так же и для фразы «C++ без шаблонов» и других подобных фраз.

А почему речь про ООП? Потому что ты предлагал заменить касты структур наследованием, а это далеко не всегда возможно.

2. Непонимание в виде нежелания ткнуть на (14 * 50 / количество_сообщений_на_странице_выставленное_в_твоём_профиле_по_умолчанию_=_50), увидеть копипасты из LLVM (копипастить снова было бы издевательством), представить для чего могут быть нужны теги в DenseMapInfo, ImutAVLFactory, ImutListFactory, MemDepResult, PointerIntPair, NodeRef, ImutAVLTreeGenericIterator и за подробностями идти читать LLVM.

Тегированные указатели это, на самом деле, дальнейшее развитие идеи null указателей ─ 0 не может быть валидным виртуальным адресом, поэтому давайте сделаем его специальным значением NULL и будем использовать указатель как опциональный тип. Но сейчас все указатели выравнены по 8/16/32 байт, так что можно безопасно брать по 4/8/16 бит из указателя (на x86_64 ─ всегда 16), если известно что указатель меньше ─ брать ещё больше. И использовать это в алгоритмах (LLVM, Boost, Linux, ...), для самодельного RTTI, как теги типов в VM и рантаймах (SBCL, Factor, Guile, Racket, GHC, LuaJIT, V8, Objective-C, HotSpot, Qemu, ...).

На эту тему даже патент есть :)

3. Моё свойство A = «существует код в котором используются static и const, но не dynamic» ты ассоциировал со свойством B = «говнокод», так что любой код удовлетворяющий свойству A, следуя твоей ассоциации, будет удовлетворять и свойству B, то есть будет быдлокодом (это же элементарная логика, а никакая не демагогия). Вот ZeroMQ ─ такой код. И любой код который следует гугловсим гайдлайнам такой. Я скорее назову завязывание на RTTI быдлокодом.

4. Переполнение знаковых целых это UB, сравнения чисел разных знаков ─ не UB, но приводит к неожиданным вещам (поэтому у gcc есть -Wsign-compare), операции битовых сдвигов работают в пределах размера типа своего сдвигаемого аргумента, числа по умолчанию приводятся к int.

Из сишного стандарта:

6.3.1.3 Signed and unsigned integers

1 When a value with integer type is converted to another integer type other than _Bool, if the value can be represented by the new type, it is unchanged.

2 Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.

3 Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

6.5.8 Relational operators

[...]

3 If both of the operands have arithmetic type, the usual arithmetic conversions are performed.

Всё это заставляет использовать касты (в пуристском C++ ─ static_cast).

Примеры:

#include <cstdio>
#include <stdint.h>

const unsigned bits_in_word = 64; // check this

void guess_what(uintmax_t x, unsigned n) // or `short n', or `uint8_t n'
{
    for (unsigned i = 0; i < bits_in_word; ++i) {
#ifdef BAD
        uintmax_t y = x & (n << i);
#else
        uintmax_t y = x & (static_cast<uintmax_t>(n) << i);
#endif
        printf("%d = %lx\n", i, y);
    }
}

void comparasion_test(unsigned x)
{

    for (int i = -10; i < 10; ++i)
#ifdef BAD
        if (i > x)
#else
        if (i > static_cast<int>(x))
#endif
            printf("%d > %d\n", i, x);
        else
            printf("%d <= %d\n", i, x);
}

    guess_what(0xabcdef123456789a, 3);
    comparasion_test(1);

Ещё тут можно посмотреть, полагаю, где-нибудь понадобятся касты.

Ссылки про UB и связанные оптимизации:

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

http://nondot.org/sabre/LLVMNotes/IntegerOverflow.txt

http://www.airs.com/blog/archives/120

5. Есть причина по которой в стандарте определён const_cast ─ чтобы решать такую проблему:

void f(char *x); // external, complex

    const char *xs = "..."; // we like to be const everywhere
    f(const_cast<char*>(xs)); // maybe UB (up to seg. fault), maybe not

не по-джедайски, да. Ещё такая ситуация может быть:

void f(char *x);

void g(const char *x)
{
    f(const_cast<char*>(x));
}

    char *xs = "...";
    g(xs); // not UB, just unpure
quasimoto ★★★★
()
Ответ на: комментарий от drBatty

6. Чтобы делать замечания про монады нужно знать что это вообще такое. В интерполяции на C++ это будет:

// http://www.pik-potsdam.de/members/lincke/papers/Lincke_et_al_SCP.pdf

concept Monad<typename F> : Functor<F> {
    template <typename A> F::Apply<A> pure(A);
    template <typename A> F::Apply<A> join(F::Apply<F::Apply<A> >);
}

concept CoMonad<typename F> : Functor<F> {
    template <typename A> A run(F::Apply<A>);
    template <typename A> F::Apply<F::Apply<A> > split(F::Apply<A>);

Как пример ─ указатели это монады:

// simplified:

template <typename T> T *pure(T &x) { return &x; }

template <typename T> T *join(T **x)
{
    if (x)
        return *x;
    else
        return NULL; // NULL is still NULL and everything is ok.
}

то есть взятие адреса это тотальная операция ─ не существует объекта у которого нет адреса.

При этом указатели ─ не комонады:

template <typename T> T **split(T *&x) { return &x; }

template <typename T> T run(T *x) { return *x; } // !!!

    // pure is total
    int x = 1;
    int *xp = pure(x);

    // run is partial
    int z = run(xp);
    int *xp_ = NULL;
    // int z_ = run(xp_); // null-pointer dereference

    // split and join are total
    int **xpp = split(xp);
    xp_ = join(xpp);
    xpp = NULL;
    int *xp__ = join(xpp);

    int z_ = run(xp_);

так как операция разыменования указателя не тотальна а частична, то есть может падать при разыменовании NULL.

Другие монады не допускающие спасение значений ─ потенциально пустые контейнеры (объединения (указатели ─ как раз частный случай), списки, вектора, стеки), тьюринг-полные вычисления в окружении терминируемых вычислений, statefull вычисления в stateless окружении, STM транзакции в statefull окружении.

То есть вытащить из монады значение не всегда возможно, утверждать обратное ─ как утверждать что любой указатель можно безопасно разыменовать, или что из любого, даже пустого, контейнера всегда можно получить элемент контейнера.

7. Это заблуждение. Для любого разрешимого алгоритма можно построить машину Тьюринга с конечной лентой. Можно считать, что компиляторы это и делают, только не очень хорошо (см. дальше). Бесконечная лента только у универсальной машины Тьюринга. Точно так же можно построить машину Тьюринга конечного размера которая способна проверять доказательства в непротиворечивом языке.

IRL программы реально попадают в нетерминируемые состояния (infinite loops, deadlocks, divergences) и при этом могут не тратить стек и память больше определённого значения (практически ─ небольшого в том числе).

Теперь про компиляторы ─ квалификатор const позволяет писать программы для которых статически (на время компиляции) известно, что они не изменяют данные (иммутабельность), квалификатор pure (для C++ ─ полу-гипотетический) позволяет писать программы для которых статически известно, что при одинаковых значениях аргументов функции возвращают одинаковые результаты (ссылочная прозрачность), квалификатор total (для С++ ─ гипотетический) позволяет писать программы для которых статически известно, что они всегда отрабатывают за конечное время. В принципе могут быть и прочие возможности ─ отрабатывают за логарифмическое время, тратят логарифмическое количество памяти и т.п.

6. и 7. и были упомянуты как дальнейшее развитие твоего пуристкого отрицания нужности небезопасных даункастов ─ то есть зачем останавливаться, давай тогда чистоту, транзакционный код и тьюринг-полноту расскидаем по уровням с явными апкастами и запретим все даункасты как недоработанный говнокод.

8. Вопрос стоит так ─ «как читать приватные поля класса?», ответ ─ «для POD/SLC ─ написанием mirror класса и кастом к нему», аналогично ─ «как получить сумму чисел?» ─ «использовать операцию +». Нельзя «использовать не mirror класс для чтения приватных полей класса», так же как нельзя «использовать операцию * чтобы получить сумму чисел».

Ну и как вообще это происходит ─ автор написал библиотеку и выкатил релиз. Ты сделал ./configure && make && make install ─ в итоге в $prefix/lib у нас будет бинарник, а в $prefix/include ─ заголовки к нему. Ты читаешь заголовки и делаешь mirror класс. Что будет при изменении автором библиотеки? Он выкатит новый релиз который будет компилироваться в новый бинарник и размещать новые заголовки из которых будет писаться (если нужно) новый mirror класс. И я не то что предполагаю автоматизацию написания mirror классов, я вообще спрашиваю в чём проблемы иметь на уровне языка read-only доступ к private/protected полям класса извне (без всяких mirror и *_cast костылей).

quasimoto ★★★★
()
Ответ на: комментарий от anonymous

Код получается совершенно неэквивалентным.

Согласен, не демонстрирует преимуществ GC. Можно померить время аллокации, но это уже совсем не показатель. Где-то выше есть ссылка про джаву с комплексным сравнением из которого следует, что если памяти _много_ ─ может получится комплексно лучше (но не на много).

quasimoto ★★★★
()
Ответ на: комментарий от anonymous

Вообще-то это UB по стандарту.

Не знаю. Я бы так делать не стал :)

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Как это все указатели выравнены? Вообще-то не все. Минимальной адресуемой единицей таки является байт, а не слово. Или я уже не могу работать с отдельными элементами массива char'ов?

anonymous
()
Ответ на: комментарий от quasimoto

Разве можно на статике как-то доказать, что программа выполняется за константное время(ну или там за логорифм)? По памяти может и можно...

anonymous
()
Ответ на: комментарий от anonymous

По памяти может и можно...

Память да - была даже реализация, только сейчас не найду ссылку.

А какие проблемы с доказательством про время? То есть вопрос - в чём проблема переноса бумажного конструктивного доказательства в «статику».

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Охренеть. Реальная битва алгоритмистов. Прям зачитался :)

qqqq ★★
()
Ответ на: комментарий от quasimoto

1. На счёт ООП. Несколько подобных утверждений ─ «Я использую С++ _с_ шаблонами и _без_ ООП», «Я использую С++ _с_ ООП и _без_ шаблонов», «Я использую С++ _с_ ООП, шаблонами, functional и _без_ RTTI и исключений». Можешь для себя такое утверждение составить ─ есть ведь вещи которые ты _не_ используешь (type level вычисления на шаблонах, например). Так что если я говорю «С++ без ООП» ─ нет причин удивляться и делить на ноль. Точно так же и для фразы «C++ без шаблонов» и других подобных фраз.

я использую C++ с ООП. Иногда с шаблонами, всегда с RTTI (ибо без нег никак).

А почему речь про ООП? Потому что ты предлагал заменить касты структур наследованием, а это далеко не всегда возможно.

хорошо, пример, когда это невозможно - в студию.

Тегированные указатели это, на самом деле, дальнейшее развитие идеи null указателей ─ 0 не может быть валидным виртуальным адресом, поэтому давайте сделаем его специальным значением NULL и будем использовать указатель как опциональный тип. Но сейчас все указатели выравнены по 8/16/32 байт, так что можно безопасно брать по 4/8/16 бит из указателя (на x86_64 ─ всегда 16), если известно что указатель меньше ─ брать ещё больше. И использовать это в алгоритмах (LLVM, Boost, Linux, ...), для самодельного RTTI, как теги типов в VM и рантаймах (SBCL, Factor, Guile, Racket, GHC, LuaJIT, V8, Objective-C, HotSpot, Qemu, ...).

на самом деле, в C/C++ имеется НЁХ. Она называется

int *x = NULL;
int y = *x;
в этом коде мы видим, что указатель может быть направлен в никуда. Это НЕ странность, это RL. IRL есть вещи, которые тоже «направлены в никуда», например дата твоей смерти. Это не свойство ЯП, это свойство RL.

Если ЯП не может отразить данную «величину» (НЁХ), то этот ЯП не нужен, ибо на нём нельзя отображать процессы IRL. И не важно, что с точки зрения математиков НЁХ невычисляемая. Оно невычисляемое по своей сути. И что?

3. Моё свойство A = «существует код в котором используются static и const, но не dynamic» ты ассоциировал со свойством B = «говнокод», так что любой код удовлетворяющий свойству A, следуя твоей ассоциации, будет удовлетворять и свойству B, то есть будет быдлокодом (это же элементарная логика, а никакая не демагогия). Вот ZeroMQ ─ такой код. И любой код который следует гугловсим гайдлайнам такой. Я скорее назову завязывание на RTTI быдлокодом.

подмена понятий детектед. Не просто const, но dynamic_const<>. Тоже и про static.

ты так и не привёл примеров, где (static) будет НУЖЕН.

drBatty ★★
()
Ответ на: комментарий от quasimoto

4. Переполнение знаковых целых это UB, сравнения чисел разных знаков ─ не UB, но приводит к неожиданным вещам (поэтому у gcc есть -Wsign-compare), операции битовых сдвигов работают в пределах размера типа своего сдвигаемого аргумента, числа по умолчанию приводятся к int.

есть такая штука: процессор. Процессор делают для моделирования реальной жизни. Есть грань, где заканчивается математика, и начинается реальная жизнь. Математика это ВСЕГДА модель. В модели нет места для «целых знаковых», но позволь, ПОЧЕМУ? Может модель хуёвая? Ну что ты своим-то меряешь? На самом деле, если абстрагироваться от математики, то ВНЕЗАПНО становится понятно, что «целые» в компьютере - это НЕ целые в математике - ВСЕ действия на самом-то деле производятся по некоторому модулю M. И выход за этот модуль - есть нарушение модели. В частности выход за знаковость, например в 32х битной системе мы работаем по модулю 31 (используя int), но при переводе в 32х битность мы выходим на модуль 32, ибо unsigned суть 32х битные числа без знака, в отличие от 31х битных чисел int. О чём нас компилятор и предупреждает.

drBatty ★★
()
Ответ на: комментарий от quasimoto

Всё это заставляет использовать касты (в пуристском C++ ─ static_cast).

что тебя _заставляет_? Я могу переписать твой пример и без кастов, только ты скажи мне, ЗАСТАВЛЯЕТ-ли тебя ЧВ использовать касты?

5. Есть причина по которой в стандарте определён const_cast ─ чтобы решать такую проблему:

я НЕ вижу никаких проблем. Если ты СКАЗАЛ «const», то это const. Его НЕЛЬЗЯ изменить. В рамках ЯП.

drBatty ★★
()
Ответ на: комментарий от quasimoto

Другие монады не допускающие спасение значений ─ потенциально пустые контейнеры (объединения (указатели ─ как раз частный случай), списки, вектора, стеки), тьюринг-полные вычисления в окружении терминируемых вычислений, statefull вычисления в stateless окружении, STM транзакции в statefull окружении.

давай ты не будешь путать STL и язык программирования C++? Проблема в том, что STL это всего лишь ШАБЛОНЫ, или, дабы тебе понятнее было: макросы. Ну по типу do в CL.

IRL в самом ЯП под названием «C++» никогда не было и нет никаких контейнеров, кроме наследования. Если хочешь поспорить - спорь с реализацией этих контейнеров. Т.е. выкатывай код на своём любимом лиспе VS код на сишечке.

drBatty ★★
()
Ответ на: комментарий от drBatty

Идиот. UB это все в стандарте Си не потому, что стандарт оперирует какой-то там абстрактной математикой, а только от того, что стандарт не задает даже размеров стандартных целочисленных типов. И вообще ничего не говорит о том, какая функциональность требуется от процессора. Так что игнорировать UB исходя из каких-то своих идиотских предположений о том, на каком железе будет исполняться код, будет только Буратино.

psikh
()
Ответ на: комментарий от anonymous

Минимальной адресуемой единицей таки является байт, а не слово

Поправочка - стандарт Си не знает, что такое «байт». И это правильно. Никто тебе не гарантирует, что char будет одним байтом.

psikh
()
Ответ на: комментарий от psikh

стандарт Си не знает, что такое «байт». И это правильно. Никто тебе не гарантирует, что char будет одним байтом

3.6, 3.7.1

wota ★★
()
Ответ на: комментарий от psikh

Идиот. UB это все в стандарте Си не потому, что стандарт оперирует какой-то там абстрактной математикой, а только от того, что стандарт не задает даже размеров стандартных целочисленных типов.

не только.

drBatty ★★
()
Ответ на: комментарий от psikh

[code=c]int *x = NULL;

int y = *x;

на самом деле, в C/C++ имеется НЁХ

На винде твой говнокод трапнется.

ты любой код на своей системе запускаешь?

drBatty ★★
()
Ответ на: комментарий от psikh

Минимальной адресуемой единицей таки является байт, а не слово

Поправочка - стандарт Си не знает, что такое «байт». И это правильно. Никто тебе не гарантирует, что char будет одним байтом.

пусть будет char. Смысл высказывания от этого не меняется.

drBatty ★★
()
Ответ на: комментарий от drBatty

Идиот. Твой код некорректен. Не только потому, что UB, а еще и потому, что на некоторых платформах он трапнется.

psikh
()
Ответ на: комментарий от psikh

Идиот. Твой код некорректен. Не только потому, что UB, а еще и потому, что на некоторых платформах он трапнется.

мальчик, я знаю, что этот код не корректен. И что дальше?

drBatty ★★
()
Ответ на: комментарий от drBatty

Дальше то, что ты - идиот. Приводить такой код в защиту существования NULL глупо. Указатель может быть NULL. А вот разыменование такого указателя уже UB и некорректная операция.

psikh
()
Ответ на: комментарий от psikh

Дальше то, что ты - идиот. Приводить такой код в защиту существования NULL глупо. Указатель может быть NULL. А вот разыменование такого указателя уже UB и некорректная операция.

мальчик, а я и не разименовывал этот указатель...

drBatty ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.