Checken ob callable-Objekt einen state hat oder nicht?

happystudent

Hallo,

gibt es eine Möglichkeit herauszufinden ob ein callable Objekt (also ein Objekt das den operator() definiert hat) einen internen State hat? Mit internen State ist gemeint dass der Rückgabewert nicht nur vom Input abhängt.

Ich stelle mir das in etwa so vor:

#include <iostream>

int f1() { return 1; }

int f2() { static int i = 0; return i += 1; }

int global_i = 0;
int f3(){ return global_i += 1; }

struct f4 {
	int operator()() { return 1; }
};

struct f5 {
	int operator()() { return m_i += 1; }
	int m_i = 0;
};

int main()
{
    std::cout << std::boolalpha;
    std::cout << has_internal_state<f1>::value << '\n'; // false
    std::cout << has_internal_state<f2>::value << '\n'; // true
    std::cout << has_internal_state<f3>::value << '\n'; // true
    std::cout << has_internal_state<f4>::value << '\n'; // false
    std::cout << has_internal_state<f5>::value << '\n'; // true
}

Geht das irgendwie?

Nathan

Nein, nicht generisch und nicht zur Compile-Time.
Einfach in die Spezifikation schreiben, dass der Funktor keinen state - in deinem Sinne - haben darf.

Columbo

also ein Objekt das den operator() definiert hat

Nein, ein Objekt dass als "Name" eines Funktionsaufrufs fungieren kann. Sonst wäre ja eine Funktion gar nicht callable. Oder ein Funktionszeiger.

Wie wärs mit diesem Trait:

template <typename T>
using has_internal_state = std::is_empty<T>;

Das prüft ob ein Typ eine nicht-leere Klasse ist (siehe hier).

Ob eine Funktion intern eine statische Variable beherbergt ist leider nicht festzustellen.

Nathan

Arcoth schrieb:

also ein Objekt das den operator() definiert hat

Wie wärs mit diesem Trait:
template <typename T>
using has_internal_state = std::is_empty<T>;
Das prüft ob ein Typ eine nicht-leere Klasse ist (siehe hier).

Aber auch nur wenn std::is_class<T>::true, ansonsten wäre eine Funktion ja verboten.
Und das sollteste du noch negieren, eine std::is_empty == true entspricht ja has_internal_state == false.

happystudent

Arcoth schrieb:

Wie wärs mit diesem Trait:
template <typename T>
using has_internal_state = std::is_empty<T>;
Das prüft ob ein Typ eine nicht-leere Klasse ist (siehe hier).

Ne das reicht leider nicht, aber Danke für den Vorschlag.

Arcoth schrieb:

Ob eine Funktion intern eine statische Variable beherbergt ist leider nicht festzustellen.

Nathan schrieb:

Nein, nicht generisch und nicht zur Compile-Time.
Einfach in die Spezifikation schreiben, dass der Funktor keinen state - in deinem Sinne - haben darf.

Mist, das hatte ich befürchtet.

Hätte da gerne eine Fehlermeldung zur Compile-Zeit gehabt

volkard

Wenns Deine Klassen sind, kannste es mit const andeuten.

struct f5 {
    int operator()(int a,int b) const { return a+5*b; }
};

Columbo

Aber auch nur wenn std::is_class<T>::true, ansonsten wäre eine Funktion ja verboten.

Das wird selbstverständlich schon von std::is_empty geprüft. Siehe https://gcc.gnu.org/onlinedocs/gcc/Type-Traits.html unter __is_empty .

Und das sollteste du noch negieren, eine std::is_empty == true entspricht ja has_internal_state == false.

Ups, ja.

happystudent

volkard schrieb:

Wenns Deine Klassen sind, kannste es mit const andeuten.
struct f5 {
    int operator()(int a,int b) const { return a+5*b; }
};

Das Problem ist dass es meistens keine Klassen sind sondern Funktionen (da sie ja eh keinen State haben dürfen der den Output verändert werden Funktoren nur selten benutzt).

Aber ich hab mal gelesen dass in C++14 Compile-Time Reflection kommen soll, würde es dann damit gehen? Dann wüsste ich wenigstens dass ich es in der Zukunft machen kann

Nathan

Arcoth schrieb:

Aber auch nur wenn std::is_class<T>::true, ansonsten wäre eine Funktion ja verboten.

Das wird selbstverständlich schon von std::is_empty geprüft. Siehe https://gcc.gnu.org/onlinedocs/gcc/Type-Traits.html unter __is_empty .

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

happystudent schrieb:

Das Problem ist dass es meistens keine Klassen sind sondern Funktionen (da sie ja eh keinen State haben dürfen der den Output verändert werden Funktoren nur selten benutzt).

Falls du den GCC nutzt kannst du dafür [[gnu::pure]] und [[gnu::const]] verwenden.

Aber ich hab mal gelesen dass in C++14 Compile-Time Reflection kommen soll, würde es dann damit gehen? Dann wüsste ich wenigstens dass ich es in der Zukunft machen kann

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.

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