#include<iostream>
using namespace std;

// lambda terms in C++ (2014 and later versions)
// compile with g++ --std=c++14   (required on some versions of g++)

const  auto I = [](auto x) {return x;};  // lambda x.x
const  auto K = [](auto x){ return [x](auto y) { return x; }; };  //lambda x.lambda k.s
const  auto S = [](auto x){return [x](auto y){return [x,y](auto z){return x(z)(y(z));};};};

void testrealK();

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

//requires g++ -fconcepts-ts, or std=c++20, to compile the following:
//auto FIX(auto M) { return M(FIX(M)); }

// 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
    A operator()(B y) { return x; } // overloads function application
    // my addition: print the lambda term!
    friend ostream& operator<<(ostream& out, inner_closure &ic) {
      out << "(\u03bby." << ic.x << ")"; //0x03bb is unicode for Greek lambda
      return out;
    }// printing overload
  };
public:
  inner_closure operator()(A x) {return inner_closure(x); }
  friend ostream& operator<<(ostream& out, realK<A,B>& rk) {
    out << "(\u03bbx\u03bby.x): A -> B -> A";
    return out;
  }// friendly overload
};

void testrealK() {
  realK<int,string> k;
  cout << "K is really " << k << endl;
  auto k1 = k(1);
  cout << "testing k1(\"abc\"): " << k1("abc") << endl; // prints 1
  cout << "because k1 = " << k1 << endl;
  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.
*/