재귀 함수를 지원하는 자동 메모

Question

블로그 게시물 Automatic Memoization in c++0x은 기존 기능의 메모 버전을 생성하는 기능을 제공합니다. 블로그 포스트 및 관련 코드는 이전에 stackoverflow (예 : What does this C++11 code do?)에서 논의되었지만, 이러한 솔루션 중 어느 것도 재귀 함수를 올바르게 메모 할 수있는 완전히 보편적 인 메모를 제공 할 수 없습니다.

std::function<int (int)> f; 
int fib(int n) { 
    if (n < 2) return n; 
    return f(n-1) + f(n-2); 
} 

int main(void) { 
    f = memoize(std::function<int (int)>(fib)); 
} 

그러나 :

물론, 이런 식으로 뭔가를 사용하여 재귀 호출을 변경하는 트릭이있다 (우리는 이미 자리에 memoize라는 블로그 게시물에서 제시 한 바와 같이 memoizer이 가정) 이것은 우리가 기억하고 싶은 기능에 대한 접근이 여전히 필요하기 때문에 적절한 해결책보다 일시적인 해결책이라고 생각합니다. 적절한 솔루션은 일부 라이브러리에 정의 된 기능을 포함하여 모든 기능을 완전히 메모 할 수 있어야합니다. 그러나 그러한 솔루션을 만드는 것은 가능하기 때문에 내 도달 범위를 넘어선 것입니다. 따라서 다음과 같이 묻습니다.

진정한 보편적 인 메모 기능이 가능합니까?
은 어떻게 그러한 위업을 달성 할 수 있습니까?

그리고 이것이 가능하지 않은 경우 위의 방법을 일반화하는 방법이 적어도 있습니다. (컴파일되지 유효한 C는지지 않습니다 ++)의 라인을 따라 뭔가 : this_func 클래스의 this 포인터하지만 기능과 유사 뭔가

int fib(int n){ 
    if (n < 2) return n; 
    return this_func(n-1) + this_func(n-2); 
} 

. [편집 :이 아마 여전히 문제로 고통 것 this_func 포인터가 대신 fib를 가리키는 것 memoized fib]

Answer 1

내 생각 엔 정의 행동의 범위 내에서 최대한 거기에 있기 때문에 이것이 불가능하다는 것이다 재귀 호출을 추상화 할 방법이 없습니다. 사실, 당신이 제공 한 글로벌 변수 버전보다 훨씬 더 나은 것을 생각할 수 없습니다.

전역 변수는 첫 번째 인수로 재귀하는 기능을 추가하는 것보다 더 강력한 추상화 지점을 제공하는 한 가지 분명한 아이디어 : 그럼

int fib(std::function<int (int)> rec, int n) 
{ 
    if (n < 2) return n; 
    return rec(n - 1) + rec(n - 2); 
} 

, 당신은을 통과하여 memoize 기능을 수정할 수 있습니다 memoized 버전을 첫 번째 인수에 넣으면 모든 것이 제대로 작동합니다. 이 트릭은 체계와 같은 (유니티 형/유형화되지 않은) 함수형 언어에서 동일한 목표를 성취하는 데 자주 사용됩니다.

그러나이 종류의 속임수는 무한한 형식을 가지고 있기 때문에 C++에는 존재할 수 없다고 생각하는 "Y combinator"에 의존합니다.

Answer 2

... 도움이 될 수 있습니다 다음,하지만 여전히 해킹이며, 그것은 추한 :

int fib(void* f, int n) 
{ 
    if (n < 2) return n; 
    auto this_func = *reinterpret_cast<std::function<int (void*, int)>*>(f); 
    return this_func(f, n - 1) + this_func(f, n - 2); 
} 


int main(int argc, char *argv[]) 
{ 
    std::function<int (void*, int n)> fib1 = &fib; 
    std::cout << fib1(reinterpret_cast<void*>(&fib1), 5) << std::endl; 

    auto f = memoize(fib1); 
    std::cout << f(reinterpret_cast<void*>(&f), 5) << std::endl; 

    return 0; 
} 

내가 올바른 서명 이후 void*를 사용하는 것은 재귀 - 캐시 요구로/

Answer 3

함수 호출을 통해 공유되도록하려면 인수로 인수를 전달하거나 그렇지 않으면 공유해야합니다.그것을 공유하는 한 가지 방법은 함수 객체를 사용하고 있습니다 :

struct fib 
{ 
    std::map<std::tuple<int>, int> cache; 

    int operator()(int n) 
    { 
     if(n < 2) return n; 

     auto memoize = [this](int p) 
     { 
      auto i = cache.find(p); 
      if(i == cache.end()) i = cache.insert({p, (*this)(p)}).first; 
      return i->second; 
     }; 

     return memoize(n-1) + memoize(n-2); 
    } 
}; 

당신이 memoize 부분을 인수 분해 할 수 있습니다 곳.

memoized 함수를 인수로 전달하는 임시 수명이있는 트릭도 있습니다. 이 같은은 다음 recurse const& (그리고 안) 내부 map의 일부가 될 수 없습니다로

struct recurse // possibly a class template 
{ 
    std::function<int(int, recurse const&)> f; // possibly `mutable` 

    template<class T> 
    recurse(T&& p) : f(memoize(decltype(f){p})) 
    {} 

    int operator()(int x) const 
    { 
     return f(x, *this); 
    } 
}; 

int fib(int n, recurse const& f); 

int fib(int n, recurse const& f = {fib}) 
{ 
    if(n < 2) return n; 
    return f(n-1) + f(n-2); // or `fib(n-1, f) + fib(n-2, f)` 
} 

그러나, 이것은 memoize의 변화를 필요로한다.

_{N.B. 그러한 const&도 평생 확장을 위해 && 일 수 있지만 아직 이동 의미로 인해 혼란스러워 할 수 있습니다.}