#include<iostream>
using namespace std;

// lambda terms in C++, requires --std=c++14

const  auto I = [](auto x) {return x;};
const  auto K = [](auto x){ return [x](auto y) { return x; }; };
const  auto S = [](auto x){return [x](auto y){return [x,y](auto z){return x(z)(y(z));};};};

void testrealK();  // defined after main
void mutabletest();

int main() {
  cout << K(1)(2) << endl;
  auto K1 = K(1);
  auto K3 = K(3);
  cout << K1(2) << endl; // should print 1
  cout << K3(2) << endl; // should print 3

  auto SKI = S(K)(I);  // SKI reduces to I
  cout << SKI(4) << endl;

  // the term lambda x.(x x) is not a part of *typed* lambda calculus:

  auto XX = [](auto x){return x(x); }; // this unfortunately compiled
  // under C++, even though it is not typable.  The code generated for
  // this lambda is equivalent to a very generic template. Templates in
  // C++ are not typechecked until they're instantiated.

  // The following does not compile (thankfully): the compiler discovers a
  // circularity.
  // auto infinity = ([](auto x){return x(x);})([](auto x){return x(x);});
  
  //XX(XX);  // this doesn't compile either.
  
  I(I);
  K(K); // these compile, as they should.
  K(I); 
  testrealK();
  return 0;
}//main

// What is K in C++, really?  To put it another way...
template<typename A, typename B>
class realK {
private:
  struct inner_closure {
    A x;
    inner_closure(A x0) : x{x0} {} // constructor instantiates x COPIES!

    // make it look like a function via operator overloading
    A operator()(B y) { return x; } // overloads function application
  };
public:
  inner_closure operator()(A x) {return inner_closure(x); }
};

// Closures are objects.

void testrealK() {
  realK<int,string> k;
  cout << "K is really " << k << endl;
  auto k1 = k(1);
  cout << "testing k(3)(\"\"): " << k(3)("") << endl; // prints 3
}// testrealK

/*
  Essentially, a closure (a lambda term with free variables) is 
  equivalent to an instance of a class with instance variables.

  Furthermore, in this program the object is directly allocated on
  the runtime stack, and will be destroyed (by calling the
  default destructor of the class) when the current function exits.  

  Other languages such as Python, Java, Go, etc. will move the closure
  to the heap and rely on its garbage collector to prevent memory leaks.
  There's no such leak in C++ because the heap was never used.
*/

/*
  There's no assignment (memory write) in lambda calculus, but we can
  still implement all kinds of algorithms.  What does destructive assignment
  really give us?
*/

auto make_accumulator() {
  int x = 0;
  return [x](int y) mutable -> int {
    x +=y;
    return x;
  };
  // x is a kind of state variable.
}

void mutabletest() {
  auto a1 = make_accumulator();
  auto a2 = make_accumulator();
  cout << a1(2) << "   a1(2)\n";
  cout << a1(2) << "   a1(2)\n";
  cout << a1(2) << "   a1(2)\n";
  cout << a2(2) << "   a2(2)\n";
}