#include<iostream>
#include<cstdio>      /* prefer printf to cout */
#include<string>
#include<functional>  /* requires -std=c++14 */
using namespace std;

/*         MUTATBLE CLOSURES PROGRAMMING ASSIGNMENT

  We saw that C could not adequately emulate lambda calculus because it
could not create *closures,* that is, lambda terms with free variables
(unless those variables are global).  We can't even define K.  Most
modern languages allow a notation for lambda terms, including C++.
But what's more important than any kind of *syntax* for lambdas, is
the usage and management of memory underneath.

  Unlike with languages such as Python and Java, C/C++ programmers
must be keenly aware of where in memory their data are stored, and of
their LIFETIME.  The lifetime of a value is how long it's guaranteed
to be at the same location in memory.  The lifetime ends when, for
example, a value gets popped from the stack at the end of a function
call, or deleted from the heap.  The value may persist in memory
momentarily after its lifetime ends but is unusable as it will be
overwritten.

Recall that we could not create a proper closure, even an immutable one,
in C, because in

int K(int x) {
  int inner(int y) { return x; }
  return inner;
}

The value x is stored on the stack, and gets popped after K returns.  The 
function returned OUTLIVES its free variable x.  

A "closure" is just a lambda term that contains free variables.  But
these free variables also refer to values and those values must be
stored somewhere in memory.  So in an actual computer, a "closure" is
represented by a pair of pointers.  The first pointer points to the
function's source code, and the second points to an "environment".
The environment contains bindings (values) for the free variables of
the function.  We can create distinct closures from the same lambda
term.  For example, lambda y.x (as returned by K) can represent
different closures because there could be different bindings, in different
environments, for x.

Typically, languages including F# will copy the free variable x to
some location on the HEAP, where they persist after the function call.
The heap-allocated data is eventually erased by a garbage collector.
But in C/C++ we do not have (and do not want) a garbage collector.  We
therefore want to allocate our data on the stack as much as possible,
to avoid memory errors and the overhead of heap management.  By
default, C++ will always allocate its structures on the stack unless
certain keywords like `new`, `malloc` or `make_unique`, are used to
allocate structures on the heap.  It will NEVER move something to heap
behind the scenes for you.  If there's a version of C++ that does
that, then it probably also has a garbage collector, which means it's 
actually Java in disguise (and should make you vomit).

Modern C++ has made huge strides since 2011 but it stays true to its
core principle of ZERO OVERHEAD ABSTRACTION.  Otherwise it's not C++.

Lambda terms in modern C++ are different from other languages in that not
only do we have to specify the bound variables, but also how FREE variables
are to be "captured", that is to say how the environment for the closure is
formed.  We have the choice of capturing them by reference (hidden pointer) 
or by value (copy). 
*/
auto I = [](auto x) {return x;};  // lambda x.x
auto K = [](auto x){ return [x](auto y) { return x; }; }; //lambda x.lambda y.x
auto S = [](auto x){return [x](auto y){return [x,y](auto z){return x(z)(y(z));};};};
// this is lambda x.lambda y.lambda z.x z (y z)

/*
The 'auto' keyword does an adequate form of type inference.

In the lambda term returned by the K combinator, the notation [x] means that
the free variable x inside the inner lambda y.x is captured by value.
Had we written K this way:
*/
auto badK = [](auto x){ return [&x](auto y) { return x; }; };
/*
then we would have the same problem as the C program.  The free variable x
is captured by REFERENCE, but the value still gets popped from the stack.
The reference outlives the value that it refers to (a dangling reference).

You can also write [=] or [&] to capture all free vars by value, or all by
reference, respectively, or [x,&y,...] to be selective.
*/

///////// ASSIGNMENT PROGLEM 1:

// Write code to verify that, using the definitions of S K and I above,

// a. K(I) is in fact equivalent to lambda x.lambda y.y.
//    You can't see what K(I) looks like underneath but you can
//    verify that it has the expected behavior, namely K(I)(A)(B) == B
//
// b. S(K)(I) is equivalent to I.
//
// c. if SII = S(I)(I), then SII(SII) is not typable (why?)

/*
                         MUTABLE CLOSURES

  The lambda calculus is defined independently of any notion of
hardware.  But modern computers must have RAM.  We can design a
language that hides memory mutation using abstractions such as tail
recursion. So what advantages does allowing destructive assignment
directly in the language give us?  If all we do is mutate local
(bound) variables, we're not gaining much.  The fun starts when we
start mutating FREE variables.

The following F# program defines an "accumulator":

// accumulator:
let make_accumulator init =
  let mutable x = init
  fun y -> x <- x + y; x

let a1 = make_accumulator 0
let a2 = make_accumulator 0

printfn "%d" (a1 2);
printfn "%d" (a1 2);
printfn "%d" (a1 2);    // a1 itself mutates
printfn "%d" (a2 2);

First of all, it's no longer the case that a1(2)=a1(2)!!  each call will
return a different value.  The closures are now STATEFUL.  In contrast,
the lambda calculus is purely STATELESS.  The closure carries its own state
in the form of the mutating free variable.  Moreover, there can be
different "instances" of the closure (a2) that carries a separate state
from other instances.

A C++ lambda term must be marked `mutable` if it changes any of its
free variables (you can always change the bound variables).

The following function is the C++ equivalent of "make_accumulator"
*/
function<int(int)> make_accumulator() {
  int x = 0;
  return [x](int dx) mutable { x += dx; return x; };
}
/*
This time we wrote down the exact types to be clear instead of using `auto`:
function<int(int)> is the type `int -> int`.  The function returned by
make_accumulator is a mutable closure allocated on the stack.  when you do

  auto a1 = make_accumulator(); // see main below

you're binding the stack-allocated structure to the L-value a1.  The
structure with its free variables have the same lifetime as a1.
The closure returned is roughly equivalent to an instance of
*/
struct accumulator {
private:
  int x;
public:
  accumulator():x{0} {}

  // operator overloading to make it look like a function ...
  int operator ()(int dx) { x+=dx; return x;}
};
/*
By indicating which free variables to capture, how to capture them,
and whether the closure is mutable, we are dictating the contents of
this struct.  With the operator overloading of (), we can even make 
instances of the struct look like a function:

  struct accumulator a2;
  int x = a2(5);  // calls {x+=5; return x;}

You can even say that the lambda syntax is just a quicker way to build
this kind of struct.  In other words, having objects is equivalent to
having lambda closures, it's just the syntax that looks different. Indeed,
any object-oriented language already contains the essential elements 
required to implement lambda terms; it's just a matter of providing a syntax.
*/

//////// ****** ASSIGNMENT PROBLEM 2 

// Follow the example of make_accumulator and write a function

function<int()> make_toggle();

// This function should return a stateful lambda-closure that alternately
// returns 1 and 0 each time it's called:

// auto toggle = make_toggle();
// cout << toggle() << endl; // prints 0
// cout << toggle() << endl; // prints 1
// cout << toggle() << endl; // prints 0
// cout << toggle() << endl; // prints 1

// You must also show how to create different instances of toggle, each
// carrying a separate state (write a test function and call it in main).

/*
One classic example of pushing the idea of closure = object even further
is to define "bank accounts".  These closures not only contain instance
variables but multiple "methods" that are selected by an interface function.
Here's how to write it in F#:

let make_account init =
  let mutable balance = init

  let inquiry = fun x -> printfn "balance = %d" balance;

  let withdraw amt =
    if amt>0 && amt<balance then balance <- balance - amt
    else printfn "invalid transaction"

  let deposit amt =
    if amt>0 then balance <- balance + amt;
    else printfn "invalid transaction"

  let public_interface req =
    match req with
      | "inquiry" -> inquiry
      | "deposit" -> deposit
      | "withdraw" -> withdraw
      | _ -> printfn "invalid request"; fun x -> ()

  public_interface;;   // body of make_account returns the public interface
// make_account

// convenient ways to call methods 
let withdraw acc amt = (acc "withdraw" amt);
let deposit acc amt = (acc "deposit" amt);
let inquiry acc = (acc "inquiry" 0);
let ac1 = make_account 1000
let ac2 = make_account 2000
withdraw ac1 500
deposit ac2 200
inquiry ac2;;

We will try to reproduce this example in C++.  It's not as easy as we
might think.  The following compiles, but it DOESN'T REALLY WORK (run
it and see):
*/

auto newaccount = [](string name, double balance) {

  function<double()> balinquiry = [&name,&balance]() {
    printf("%s has a balance of %.2f\n",name.c_str(),balance);
    return balance;
  };
  function<void(double)> deposit = [&balance](double amt) mutable { 
    if (amt>0) balance+=amt;   
  };  // mutable means function could mutate free variables
  function<void(double)> withdraw = [&balance](double amt) mutable {
    if (amt>0 && amt<=balance) balance-=amt;
  };
  function<void(double)> dummyfun = [&balance](double x) mutable {balance+=0;};

  auto public_interface =
    [=](const string& request) {
      if (request=="deposit") {
        return deposit;
      }
      else if (request=="withdraw") {
        return withdraw;
      }
      else if (request=="inquiry") {
        balinquiry();
      }
      return dummyfun;  // this is required for type-consistency
  };
  return public_interface;
};//newaccount

int main() {
  printf("%s\n", K("abc")(9));   // prints abc

  auto a1 = make_accumulator();
  auto a2 = make_accumulator();
  cout << a1(2) << endl; // prints 2
  cout << a1(2) << endl; // prints 4
  cout << a2(1) << endl; // prints 1  

  auto myaccount = newaccount("Liang",1000);
  auto youraccount = newaccount("Student",2000);
  myaccount("inquiry");      // SHOULD print Liang has a balance of 1000
  youraccount("inquiry");    // SHOULD print Student has a balance of 2000
  myaccount("withdraw")(300);
  myaccount("deposit")(100);
  myaccount("inquiry");      // SHOULD print Liang has a balance of 800

  // add to code to main to test other parts of the assignment
}//main

/*
Compile and run this to look at the output (may have to compile with -std=c++14
option).  Can you explain the output?  What happened?

Note that the public_interface function captured the name and balance
variables by value, but the other closure-functions captured them by reference.

Your first instinct might be to change all the lambda terms to capture by
value.  Try it and see what happens.

The problem is that the withdraw and deposit functions of the same
account MUST capture the balance by reference, otherwise they will
just be modifying their own copies!  They need to change the SAME
balance.  Same goes for the balinquiry method: if it captured balance by
value then it will always return the same value.

Clearly, in order to get this to work sometimes the free vars must be 
captured by reference, while at other times they must be captured by value 
or they'll get popped from the stack.

///////////  ASSIGNMENT PROBLEM 3:

   ***  MAKE THIS PROGRAM WORK CORRECTLY.  ***

YOU ARE NOT ALLOWED to use any structs or classes, imported or
user-defined (vector, unordered_map, etc, are all structs/classes that
you can't use).  The only exception is std::string.  You must write C++
lambda terms to create closures.

Also, you may not make the functions such as withdraw/deposit gobal, or
take addtional arguments.  You can only rearrange how they're defined 
inside the newaccount function...
*/