Ein Weg zur Lazy Evaluation in C++

Question

Also beantwortete ich eine Frage über faule Bewertung (here, meine Antwort ist Overkill für diesen Fall, aber die Idee scheint interessant) und es ließ mich darüber nachdenken, wie faul Auswertung in C++ getan werden könnte . Ich hatte einen Weg gefunden, aber ich war mir nicht sicher, welche Fallstricke dabei auftraten. Gibt es andere Möglichkeiten, eine faule Bewertung zu erreichen? Wie könnte das geschehen? Was sind die Fallstricke und dieses und andere Designs?

Hier ist meine Idee:

#include <iostream> 
#include <functional> 
#include <memory> 
#include <string> 

#define LAZY(E) lazy<decltype((E))>{[&](){ return E; }} 

template<class T> 
class lazy { 
private: 
    typedef std::function<std::shared_ptr<T>()> thunk_type; 
    mutable std::shared_ptr<thunk_type> thunk_ptr; 
public: 
    lazy(const std::function<T()>& x) 
     : thunk_ptr(
      std::make_shared<thunk_type>([x](){ 
       return std::make_shared<T>(x()); 
      })) {} 
    const T& operator()() const { 
     std::shared_ptr<T> val = (*thunk_ptr)(); 
     *thunk_ptr = [val](){ return val; }; 
     return *val; 
    } 
    T& operator()() { 
     std::shared_ptr<T> val = (*thunk_ptr)(); 
     *thunk_ptr = [val](){ return val; }; 
     return *val; 
    } 
}; 

void log(const lazy<std::string>& msg) { 
    std::cout << msg() << std::endl; 
} 

int main() { 
    std::string hello = "hello"; 
    std::string world = "world"; 
    auto x = LAZY((std::cout << "I was evaluated!\n", hello + ", " + world + "!")); 
    log(x); 
    log(x); 
    log(x); 
    log(x); 
    return 0; 
} 

Einige Dinge, die ich in meinem Design besorgt war.

• decltype hat einige seltsame Regeln. Hat meine Verwendung von decltype irgendwelche Probleme? Ich fügte zusätzliche Klammern um das E im LAZY-Makro hinzu, um sicherzustellen, dass einzelne Namen fair behandelt wurden, wie Referenzen wie vec [10]. Gibt es andere Dinge, die ich nicht vertrete?
• In meinem Beispiel gibt es viele Ebenen der Indirektion. Es scheint, dass dies vermeidbar sein könnte.
• Ist dies korrekt memoizing das Ergebnis, so dass egal, was oder wie viele Dinge Bezug auf den faulen Wert, wird es nur einmal bewerten (dieser bin ich ziemlich zuversichtlich, aber faule Auswertung plus Tonnen von geteilten Zeigern könnte mich werfen Schleife)

Was sind Ihre Gedanken?

Answer 1

• Möglicherweise möchten Sie thunk_type haben und sich darauf als separate Objekte beziehen. Im Moment wird die Kopie von lazy<T> nichts von der Ursprungsbewertung erhalten. Aber in diesem Fall erhalten Sie zusätzlichen indirekten Zugriff.
• Manchmal können Sie die Umhüllung in std :: function loswerden, indem Sie einfach Vorlagen verwenden.
• Ich bin nicht sicher, dass Wert shared_ptr sein muss. Vielleicht sollte der Anrufer das entscheiden.
• Sie werden bei jedem Zugriff neue Verschlüsse herstellen.

Betrachten nächste Änderung:

template<typename F> 
lazy(const F& x) : 
    thunk_ptr([&x,&this](){ 
    T val = (*x)(); 
    thunk_ptr = [val]() { return val; }; 
    return val; 
    }) 
{} 

Oder alternative Implementierung könnte wie folgt aussehen:

template<typename F> 
auto memo(const F &x) -> std::function<const decltype(x()) &()> { 
    typedef decltype(x()) return_type; 
    typedef std::function<const return_type &()> thunk_type; 
    auto thunk_ptr = std::make_shared<thunk_type>(); 
    auto *thunk_cptr = thunk_ptr.get(); 

    // note that this lambda is called only from scope which holds thunk_ptr 
    *thunk_ptr = [thunk_cptr, &x]() { 
     auto val = std::move(x()); 
     auto &thunk = *thunk_cptr; 
     thunk = [val]() { return val; }; 
     // at this moment we can't refer to catched vars 
     return thunk(); 
    }; 

    return [thunk_ptr]() { return (*thunk_ptr)(); }; 
}; 

Answer 2

Ja, was Sie haben, ist faul. Übergeben Sie einfach eine Funktion, die das Argument anstelle des Arguments berechnet. Nach der Auswertung wird das Objekt durch den berechneten Wert ersetzt. Das ist es im Grunde, und ja, so implementiert, mit Referenzzählern, es ist ziemlich teuer.

Memoization ist ein alter Begriff, der oft das Ergebnis einer Funktion enthält. Keine moderne Sprache tut das (vielleicht PROLOG), es ist extrem teuer. Voll-Lazyness (nie eine Sache zweimal zu berechnen) wird im Prozess des Lambda-Liftings erreicht, das die Beseitigung von freien Variablen ist (indem man sie als Argumente verwendet). Beim vollständig faulen Lambda-Lifting werden die maximalen freien Ausdrücke aufgehoben (x ist frei, so dass ein Vorkommen von sqrt x durch ein neues Argument sqrtx ersetzt wird). Es gibt auch die sogenannte optimale Reduktion.

Ich glaube nicht, dass es andere Möglichkeiten gibt, es zu tun. Warum ist es in einer faulen funktionalen Sprache wie Haskell viel schneller? Nun, im Grunde, keine Referenz gezählte Zeiger, dann gibt es strenge Analyse (strikt ist das Gegenteil von faul), die der Compiler im Voraus wissen, dass einige Dinge streng evaluiert werden streng, unboxing Werte, die streng ausgewertet werden und sind von bekannten Maschinentyp ... ganz zu schweigen von anderen typischen funktionalen Programmiersprachenoptimierungen ... Aber im Wesentlichen betrachtet man, wenn man sich die Implementierung einer Graphreduktionsmaschine anschaut, wenn man sich anschaut, wie sich der Stack entwickelt, im Grunde, dass man Funktionen weitergibt der Stapel statt Argumente, und das ist es im Grunde.

Nun, in diesen Maschinen wird der Knoten, der das Argument berechnet, mit seinem Wert überschrieben. So fehlt Ihnen vielleicht eine Optimierung, die aber in einem typensicheren Kontext nicht möglich wäre.

Angenommen, alle "Knoten" sind Unterklassen einer Master-Oberklasse, genannt "Knoten", die nur eine virtuelle Funktion hatte, die den Wert berechnet ... dann könnte sie von einem anderen "überschrieben" werden, der den bereits berechneten Wert zurückgeben würde .Dieses Ding, mit Funktionszeigern, ist der Grund, warum sie sagen, dass die STG-Maschine von Haskell "Tagless" (die spinlose taglose G-Maschine) ist, da sie die Datenelemente nicht kennzeichnet, sondern einen Funktionszeiger verwendet, der entweder berechnet oder zurückgibt der Wert.

Ich glaube nicht, dass es in C++ nicht annähernd so effizient wie in Haskell gemacht werden kann ... es sei denn, wir fangen an, C++ völlig anders zu implementieren (könnte und sollte getan werden). Wir sind an so komplexe Prologs und Epilogs gewöhnt und komplizierte Aufrufkonventionen, etc ... Funktionsaufruf ist zu bürokratisch in C/C++.

Nun, das Buch zu lesen, wenn Sie sich faul fühlen, ist definitiv "Die Implementierung von funktionalen Programmiersprachen" von Simon Peyton-Jones. Die moderne Implementierung ist jedoch in dem frei verfügbaren Artikel "Implementieren von funktionalen Sprachen auf Lager Hardware: Die Spineless Tagless G-Maschine" beschrieben, die sehr schön zu lesen ist über die Implementierung Optimierungen, aber die andere ist zu lesen die Grundlagen.

Answer 3

Hier ist ein weiterer Aspekt der Faulheit ist das für mich nötig war.

// REMARK: Always use const for lazy objects. Any, even const operation coming from ValueType called over Lazy<ValueType> freezes it. 
template < typename ValueType > 
struct Lazy 
{ 
    typedef ValueType    Value; 
    typedef std::function<Value()> Getter; 

    Lazy(const Value& value = Value()) 
     : m_value(value) 
    { } 

    Lazy(Value&& value) 
     : m_value(value) 
    { } 

    Lazy(Lazy& other) 
     : Lazy(const_cast<const Lazy&>(other)) 
    { } 

    Lazy(const Lazy& other) = default; 
    Lazy(  Lazy&& other) = default; 
    Lazy& operator = (const Lazy& other) = default; 
    Lazy& operator = (  Lazy&& other) = default; 


    template < typename GetterType, 
       typename = typename std::enable_if<std::is_convertible<GetterType,Getter>::value>::type > 
    Lazy(GetterType&& getter) 
     : m_pGetter(std::make_shared<Getter>(std::move(getter))) 
    { } 

    void Freeze() 
    { 
     if (m_pGetter) 
     { 
      m_value = (*m_pGetter)(); 
      m_pGetter.reset(); 
     } 
    } 

    operator Value() const 
    { 
     return m_pGetter ? (*m_pGetter)() : m_value; 
    } 

    operator Value&() 
    { 
     Freeze(); 
     return m_value; 
    } 

private: 
    Value     m_value; 
    std::shared_ptr<Getter> m_pGetter; 
}; 

Mit Nutzung wie folgt aus:

template < typename VectorType, 
      typename VectorIthValueGetter = std::function<typename VectorType::const_reference (const size_t)> 
     > 
static auto MakeLazyConstRange(const VectorType& vector) 
    -> decltype(boost::counting_range(Lazy<size_t>(), Lazy<size_t>()) | boost::adaptors::transformed(VectorIthValueGetter())) 
{ 
    const Lazy<size_t> bb(0) ; 
    const Lazy<size_t> ee([&]() -> size_t { return vector.size(); }); 
    const VectorIthValueGetter tt([&] (const size_t i) -> typename VectorType::const_reference { return vector[i]; }); 
    return boost::counting_range(bb, ee) | boost::adaptors::transformed(tt); 
} 

und später:

std::vector<std::string> vv; 
boost::any_range<const std::string&, boost::forward_traversal_tag, const std::string&, int> 
    rr = MakeLazyConstRange(vv); 

vv.push_back("AA"); 
vv.push_back("BB"); 
vv.push_back("CC"); 
vv.push_back("DD"); 

for (const auto& next : rr) 
    std::cerr << "---- " << next << std::endl; 

Answer 4

Die Boost Phoenix Bibliothek lazyness implementiert, unter anderem Feinheiten der FP aber ich habe nicht nicht verwendet mich Ich bin nicht sicher, wie gut es mit C++ 11 spielt, oder vielleicht hat es es zumindest teilweise zum 2011 Standard gemacht.

http://www.boost.org/doc/libs/1_43_0/libs/spirit/phoenix/doc/html/index.html

Answer 5

In meiner Implementierung der Klasse faul, ich habe ging durch eine wenig andere Art und Weise - Lambda-Funktion nicht Wert zurückgibt, nimmt es als Parameter. Es hilft, einige Vorteile zu erzielen:

Gespeicherte Zeit beim Aufrufen von Move Constructor für gekapselten Typ (wenn Initialize-Funktion Ergebnis zurückgibt).

Kopierkonstruktor und Zuweisungsoperator für gekapselten Typ sind nicht erforderlich (nur wenn Sie es für Lazy-Typ tun wollen).

Auch diese Version sollte Thread Safe sein (bitte korrigieren Sie mich, wenn ich etwas falsch gemacht habe). Eine Anforderung, die immer noch übrig ist - Standardkonstruktor.

#pragma once 
#include <mutex> 
#include <atomic> 
#include <functional> 

template <typename T> 
struct Lazy 
{ 
    using value_type = T; 

    Lazy() : mInitializer(nullptr) {} 

    Lazy(const std::function<void(T&)>& initializer) 
     : mInitializer(std::move(initializer)) 
     , mInitFlag(false) 
    { } 

    Lazy(const Lazy& other) 
     : mInitializer(other.mInitializer) 
     , mInitFlag(other.mInitFlag.load()) 
     , mValue(other.mValue) 
    { } 

    Lazy(Lazy&& other) 
     : mInitializer(std::move(other.mInitializer)) 
     , mInitFlag(other.mInitFlag.load()) 
     , mValue(std::move(other.mValue)) 
    { } 

    Lazy& operator=(const std::function<void(T&)>& initializer) 
    { 
     mInitFlag.store(false); 
     mInitializer = initializer; 
     return *this; 
    }; 

    Lazy& operator=(const Lazy& rhs) 
    { 
     if (this != &rhs) 
     { 
      std::lock_guard<std::mutex> lock(mMutex); 

      mInitializer = rhs.mInitializer; 
      mInitFlag = rhs.mInitFlag.load(); 
      if (mInitFlag) { 
       mValue = rhs.mValue; 
      } 
     } 
     return *this; 
    }; 

    Lazy& operator=(Lazy&& rhs) 
    { 
     if (this != &rhs) 
     { 
      std::lock_guard<std::mutex> lock(mMutex); 

      mInitializer = std::move(rhs.mInitializer); 
      mInitFlag = rhs.mInitFlag.load(); 
      if (mInitFlag) { 
       mValue = std::move(rhs.mValue); 
      } 
     } 
     return *this; 
    }; 

    inline operator T&()    { return get(); } 
    inline operator const T&() const { return get(); } 

    inline T& get()    { return const_cast<T&>(_getImpl()); } 
    inline const T& get() const { return _getImpl(); } 

private: 
    const T& _getImpl() const 
    { 
     if (mInitializer != nullptr && mInitFlag.load() == false) 
     { 
      std::lock_guard<std::mutex> lock(mMutex); 
      if (mInitFlag.load() == false) 
      { 
       mInitializer(mValue); 
       mInitFlag.store(true); 
      } 
     } 
     return mValue; 
    } 

    mutable std::mutex mMutex; 
    std::function<void(T&)> mInitializer; 
    mutable std::atomic_bool mInitFlag; 
    mutable T mValue; // Value should be after mInitFlag due initialization order 
}; 

Nutzungs Beispiel:

using ValuesList = std::vector<int>; 
Lazy<ValuesList> lazyTest = [](ValuesList& val) { val.assign({1, 2, 3, 4, 5}); }; 
const Lazy<ValuesList> lazyTestConst = lazyTest; 

ValuesList& value = lazyTest; 
const ValuesList& cvalue = lazyTestConst;