Checken ob callable-Objekt einen state hat oder nicht?

happystudent

Nathan schrieb:

C++14 gibts schon, damit würd es zwar evtl. gehen (je nachdem, was da genau rein soll, daran arbeiten sie noch ), aber gibts nicht in C++14, hoffentlich im nächsten.

Ach so, Ok. Na dann vielleicht in nicht allzu ferner Zukunft mal.

Auf jeden Fall Danke für die Antworten

hustbaer

happystudent schrieb:

Mit internen State ist gemeint dass der Rückgabewert nicht nur vom Input abhängt.

Und was ist mit "externem state"?

int g_value = 42;
struct f6 {
    int operator()() const { return g_value++; }
};

struct f7 {
    f7(int* p) : m_p(p) {}
    int* const m_p;
    int operator()() const { return (*m_p)++; }
};

struct f8 {
    int operator()() const { return time(0); }
};

Ich denke was du meinst ist eine "pure function":
http://en.wikipedia.org/wiki/Pure_function

Und dann gibt's natürlich auch das Gegenteil, Funktoren die "pure" sind obwohl sie non-const Datenmember enthalten.
z.B. welche wo die Datenmember nur deswegen nicht const sind damit man den Funktor zuweisen kann.

happystudent

hustbaer schrieb:

Ich denke was du meinst ist eine "pure function":
http://en.wikipedia.org/wiki/Pure_function

Ja, genau das meine ich. Also eine Funktion y = f(x) die für das gleiche x auch immer das gleiche y zurückgibt.

Heißt das es gibt eine Möglichkeit die "pure-ness" einer Funktion zu überprüfen, oder war das nur eine Anmerkung?

hustbaer

War nur ne Korrektur, weil deine Beschreibung mit "internem State" falsch war (siehe meine Gegenbeispiele).

happystudent

Es wäre mal schön wenn man auf alle Informationen zugreifen könnte die der Compiler (sowieso schon) hat.

Weil zu Optimierungszwecken muss dieser ja eh checken ob eine Funktion jetzt "pure" ist oder nicht und dass man diese ja vorhandene Info nicht nutzen kann ist echt nervig...

Columbo

Ja, std::is_empty von Funktion ist false, das bedeutet has_internal_state ist true...

Nächstes mal denke ich nach, versprochen!

template <typename T>
using has_internal_state = std::integral_constant<bool, std::is_class<T>::value && !std::is_empty<T>::value>;

volkard

struct f9 {
    int const faktor;
    f9(int faktor)
    :faktor(faktor){
    }
    int operator()(int x) const {
        return x*faktor; 
    }
};

mit internal_state, aber pure. brtrifft viele std::bind-Sachen und vielleicht 50% der lamdas.

happystudent

volkard schrieb:

mit internal_state, aber pure. brtrifft viele std::bind-Sachen und vielleicht 50% der lamdas.

Richtig, der Begriff "internal_state" war hier wohl etwas irreführend.

Ich frag mich aber auch gerade ob so ein Compiler wirklich immer den Beweis erbringt ob eine Funktion pure ist oder nicht... Weil sowas zum Beispiel:

int f(int i)
{
    if (is_prime(i))
        return time(0); // impure
    return i; // pure
}

wäre ja ziemlich schwer zu checken, bzw. würde wohl einiges an Compile-Zeit brauchen (vorrausgesetzt dass alle Aufrufe von f und die entsprechenden Parameter zur Compile-Zeit bekannt sind). Wenn jetzt nie ein i übergeben wird welches die Bedingung "is_prime" erfüllt, wäre die Funktion ja pure.

Nathan

happystudent schrieb:

[...]

Naja, bei is_prime wäre das ja eventuell noch möglich, aber:

int f(int i)
{
  if (P == NP) // P und NP Mengen der Komplexitätstheorie...
   return time(0);
  return i;
}

eher nicht so.
Wenn ein Compiler schafft, das zu beweisen, ist er ziemlich gut.

Aus diesem Grund gibt es Attribute für Funktionen.
Beim GCC ist das [[gnu::pure]] bzw. [[gnu::const]] (letzteres ist das eigentliche pure, ersteres "keine Seiteneffekte, aber Wert abhängig von globalen Variablen").
Mithilfe der -Wsuggest-attribute=pure/const sieht man schön, was der Compiler als pure/const identifiziert.
Bspw.

bool is_prime(unsigned i)
{
    if (i == 1u)
        return false;
    else if (i == 2u)
        return true;
    else if (i % 2 == 0u)
        return false;
    for (auto j = 3u; j * j <= i; ++j) // kein wurzel, da sqrt offenbar nicht const...
        if (i % j == 0u)
            return false;
    return true;
}

identifiziert der als const (warning: function might be candidate for attribute 'const' if it is known to return normally [-Wsuggest-attribute=const]).
Folgenden Code, der dein f aufruft:

int g()
{
    return f(1);
}

ist auch noch const, genauso wie f(4).
Und das überrascht mich jetzt wirklich: selbst f(9), wo er in die Schleife muss, wird als const identifiziert!
Der Compiler scheint constant propagation anzuwenden und denn is_prime Aufruf wegzuoptimieren und somit auch den Aufruf zu time zu vernachlässigen.
Das heißt, die Antwort die du suchst ist: ja, macht er. Damit hätt ich jetzt wirklich nicht gerechnet...

happystudent

Nathan schrieb:

[...]

Das heißt, die Antwort die du suchst ist: ja, macht er. Damit hätt ich jetzt wirklich nicht gerechnet...

Cool, schlauer Compiler

Will gar nicht wissen wieviel Arbeit da drinnen steckt, nur um sowas vermeintlich "einfaches" zu checken