More Postfix
============

Variables and Simple Functions
------------------------------

We've added a number of operators to our postfix evaluator. The basic pattern
is always the same: give it a name (that hasn't already been used), check for
that name in the ``process_token``\ 's big if-else-if statement, and then
perform the appropriate actions.

Now lets add some features that will require more thought: variables and
(simple) user-defined functions.

Here's an example of what we want to be able to do::

   --> def square = dup * .
   square: [dup *]
   --> 8 square .
   tos = 64

The first line defines the ``square`` function, and the second line shows an
example of how to use it.

Here's a function that calculates the area of a circle assuming the radius is
on the top of the stack::

   --> def circle_area = square 3.14 * .
   circle_area: [square 3.14 *]
   --> 1 circle_area .
   tos = 3.14
   --> 4.22 circle_area .
   tos = 55.9184

Notice that we are calling another user-defined function within
``circle_area``.
   
We can also use ``def`` to give values to variables, e.g.::

   --> def pi = 3.14 .
   pi: [3.14]
   --> def circle_area = square pi * .
   circle_area: [square pi *]
   

Object-oriented Programming
---------------------------

From the examples above, we can see that function definitions have this
general form::

   def name : <space-separated list of operands and operators> .

In other words, functions consist of a name and a sequence of strings. So it
is natural to represent a function's name as a ``string``, and its body as a
``vector<string>``.

*Every* function we define needs its own name ``string`` and body
``vector<string>``. The natural way to represent this in C++ is to use an
*object* that stores both a functions name and its body. In C++, we can use
``struct`` to define objects::

   struct Function {
     string name;
     vector<string> body;
   };

This defines a ``struct`` called ``Function`` that we can use like this::

   Function f;  // create a new Function object
   f.name = "square";  // set its name
   
   f.body.push_back("*");    // add some strings to the body
   f.body.push_back("dup");

We say that ``f`` is a variable of type ``Function``. Since we defined
``Function`` ourselves, we also say that ``Function`` is a **user-defined
type**. You access the name and body of ``f`` using the "."-notation, i.e.
``f.name`` is the name of ``f``, and ``f.body`` is its body.

Every time you create a new ``Function`` object, C++ reserves new memory
locations for that function's ``name`` and ``body``. That means that every
``Function`` objects has its own unique name and body::

   // ... f defined as above

   Function g;
   g.name = "twice";
   
   vector<string> vs2;
   vs2.push_back("*");
   vs2.push_back("2");
   
   g.body = vs2;

``g`` and ``f`` are both objects of type ``Function``, and both have their own
personal name and body.

We can also create a ``vector`` of ``Function`` objects like this::

   vector<Function> functions;
   functions.push_back(f);
   functions.push_back(g);

Our postfix evaluator will save user-defined functions as ``Function``
objects and store them in a ``vector<Function>``.
   
Defining your own types using structs (and classes) is one of the major
features of C++, and of **object-oriented programing** (**OOP**) in general.
Object-oriented languages let you create new types of objects.


Adding Functions to the Evaluator
---------------------------------

Now lets add the ``Function`` ``struct`` to our program. Add the
following just *before* the global variables section::

   /////////////////////////////////////////////////////////////
   //
   // structs and classes
   //
   /////////////////////////////////////////////////////////////
   
   // represents a postfix function
   struct Function {
     string name;
     vector<string> body;
   };

Then, since we will need somewhere to store the user-defined
functions, we add the variable ``functions`` to our global variables::

   // ...

   /////////////////////////////////////////////////////////////
   //
   // Global variables
   //
   /////////////////////////////////////////////////////////////
   
   string token;
   vector<double> stack;
   const string prompt = "--> ";
   vector<Function> functions;

   // ...

Next we need to add some code to ``process_token`` to recognize the
``def`` operator. Lets use this as an example to work from::

   def square = dup * .

Lets agree that a function definition in our postfix evaluator must
follow these rules:

- It must begin with ``def``.

- After ``def`` comes the name of the function (``square`` in this
  example).

- After the function names come ``=``.

- After ``=`` comes a sequence of 1 or more operators/operands. 

- It must end with a ``"."``.

Since a function definition always starts with ``def``, we need to
check for the token ``def`` in ``process_token``::

  void process_token() {

     // ...

     } else if (token == "def") {
        // ... code to handle a function definition ...
     }

     // ...

  }

Following the list of rules for a function definition, we can write
the code for processing a ``def``::

    // ...

    } else if (token == "def") {
       Function f;
       cin >> f.name;  // read the name
       string eq;
       cin >> eq;      // read the "="
    
       // read the body, i.e. all the tokens up to "."
       string t;
       cin >> t;
       while (t != ".") {
         f.body.push_back(t);
         cin >> t;
       }
   
       functions.push_back(f);
    }

    // ...

Assuming the function definition is properly formatted, then this code
stores the function as a ``Function`` object in the ``functions``
vector. For the moment we've ignored error-checking.

Lets add a couple of functions for printing the contents of a
``Function`` object in a human-readable way::

   /////////////////////////////////////////////////////////////
   //
   // Generic helper functions
   //
   /////////////////////////////////////////////////////////////
   
   // ...
   
   void print(const vector<string>& v) {
     const int n = v.size();
     if (n == 0) ;   // print nothing for an empty vector
     else if (n == 1) cout << v[0];
     else {          // n >= 2
       cout << v[0];
       for(int i = 1; i < v.size(); ++i) // note that i starts at 1
         cout << " " << v[i];
     }
   }


   // ...

   /////////////////////////////////////////////////////////////
   //
   // Program-specific helper functions
   //
   /////////////////////////////////////////////////////////////
   
   // ...
   
   void print(Function f) {
     cout << f.name << ": [";
     print(f.body);
     cout << "]";
   }
   
The helper function ``print(vector<string> v)`` takes any
``vector<string>`` and prints its contents to the screen, separating
each string with a space. ``print(Function f)`` is specific to this
program and prints a function object's name and body. The body is
wrapped in ``[`` and ``]`` to make it easier to recognize.

Notice that we've just defined two different functions with the *same*
name, ``print``. Functions can have the same name in C++ as long as
they have different parameters, as is the case here. C++ never gets
confused about which function to call because it can tell from the
type of the input parameters: ``print(x)`` is call to
``print(vector<string> v)`` if ``x`` is an object of type
``vector<string>``, and a call to ``print(Function f)`` if ``x`` is of
type ``Function``.

Now we can use ``print`` to give the user some feedback about the
function they entered::

  } else if (token == "def") {

    // ...

    // print the function as feedback for the user
    print(f);
    cout << endl;
    cout << prompt;
  }

After compiling the program, we can now type function definitions::

   --> def square = dup * .
   square: [dup *]
   --> def pi = 3.14 .
   pi: [3.14]
   --> def circle_area = square pi * .
   circle_area: [square pi *]

The next step is to get functions to execute when called.


Executing User-defined Functions
--------------------------------

Like most other programming languages, our postfix evaluator
distinguishes between *built-in* operators and *user-defined*
functions. Our built-in operators are all encoded directly into the
``process_token`` function, while all the user-defined functions are
stored in the ``functions`` vector.

Think for a moment about how an operator is recognized. Suppose we
type some string *x* into our evaluator::

  --> x .

Consider the possibilities for ``x``:

- ``x`` is a built-in operator, like ``+`` or ``pstack``, that will be
  recognized in the ``process_token`` if-else-if-statement.

- ``x`` is a number which will be recognized by the ``else`` part of
  the ``process_token`` if-statement.

- ``x`` is the name of a user-defined function.

Our program already handles the first two possibilities, and to get it
to handle the third will require some re-organization that is more
substantial than implementing a new function. We need to take care to
ensure that after implementing this change our program still works as
expected: often changes to the fundamental structure of a program end
up "breaking" code that worked fine before the change. So we will need
to thoroughly test our evaluator after getting functions working.

This requires a change to the basic logic of ``process_token`` that is
more substantial than adding a new built-in function. We need to take
care to ensure that after implementing this change our program still
works as expected: often changes to the fundamental structure of a
program end up "breaking" code that worked fine before the change. So
we will need to thoroughly test our evaluator after getting functions
working.

Lets sketch out the new logic of the new ``process_token`` in
*pseudocode* (i.e. English-like code):

- check to see if ``token`` is a built-in operator; if so do the
  action for that operator;

- if ``token`` is not a built-in operator, check if it is a
  user-defined function by searching the ``functions`` vector for a
  function name that matches ``token``; if a match is made, then "run"
  the function (see below for how to do this part);

- if ``token`` is neither a built-in operator nor a user-defined
  function, assume it is a number and push it on the stack.

Writing out logic like this is a good way to help clarify our
thinking. Plus it acts as a guide for writing the C++ code.

Once we've recognized that a token is a user-defined function, then we
execute it by processing each token in its body one at time. The body
tokens could be numbers, built-in operators, or even other
user-defined functions, and so we will need to *recursively call*
``process_token()`` to handle them.

Here is the code::

   void process_token() {
     if (token == "+") {
       double b = pop();
       double a = pop();
       push(a + b);
     } 

     // ... many else-if statements skipped ...

     } else if (token == "def") {
        // ... code for defining a function ...
     } else {

       // check to see if token is the name of a user-defined function
       for(int i = 0; i < functions.size(); ++i) {
         Function f = functions[i];
         if (token == f.name) {
           // found a matching user-defined function, so execute it
           // by processing each token in its body
           for(int j = 0; j < f.body.size(); ++j) {
             token = f.body[j];
             process_token();  // recursive call!
           }
           return;  // immediately jump out of process_token
         }
       }
   
       // we only get to this line if token matches nothing in the 
       // functions vector: we assume token is a number
       push(string_to_double(token));

     } // if

   } // process_token
   
The new code we've added here first scans through the ``functions``
vector looking to see if the current ``token`` matches the name of any
user-defined function. If so, then it execute the body of that
function by calling ``process_token`` on each token in the
body. Notice that we are calling ``process_token`` recursively,
i.e. ``process_token`` is calling itself. When you think about it,
this is exactly what we want to do because the tokens in the body of
the user-defined function could be built-in operators, user-defined
functions, or numbers.

.. note:: Recursion turns out to be a deep and interesting topic in
   computer science, and we will have more to say about it later in
   the course. For now, though, we just use it as a simple and natural
   way to solve an otherwise difficult problem.

Finally, if no user-defined function matches the token, then we
assume ``token`` is a ``double`` and push it on the stack.

Here's a sample of what we can now do with our evaluator::

   --> def square = dup * .
   square: [dup *]
   --> 5 square .
   tos = 25
   --> def pi = 3.14 .
   pi: [3.14]
   --> pi square .
   tos = 9.8596
   --> def circle_area = square pi * .
   circle_area: [square pi *]
   --> 1 circle_area .
   tos = 3.14
   --> 2 circle_area .
   tos = 12.56
   --> 

If you can live with the fact that the expressions are all in postfix
order, then we've done something quite impressive: we created a
general-purpose calculator that lets you define and use your own
functions. And none of the code we used to do it was that complex on
its own.

There's still a lot that can be done to improve this program, but we
will stop here and move on to other topics. If you are curious about
how to evaluate regular infix expressions, then take a look at
chapters 6 and 7 of the textbook.

.. note:: If you are using Linux, the ``dc`` desktop calculator can be
   run at the command-line. ``dc`` is postfix calculator with lots of
   useful features, including arbitrarily large/small integers. Type
   ``man dc`` to learn more about it.


The Final Program
-----------------

::

   #include "std_lib_cmpt125.h"
   
   
   ///////////////////////////////////////////////////////////
   //
   // structs and classes
   //
   ///////////////////////////////////////////////////////////
   
   struct Function {
     string name;
     vector<string> body;
   };
   
   ///////////////////////////////////////////////////////////
   //
   // Global variables
   //
   ///////////////////////////////////////////////////////////
   
   string token;  // the token being read in; global
   
   vector<double> stack;  // global variable
   
   const string prompt = "--> ";
   
   vector<Function> functions;  // user-defined functions
   
   ///////////////////////////////////////////////////////////
   //
   // General-purpose helper function
   //
   ///////////////////////////////////////////////////////////
   
   double string_to_double(const string& s) {
     istringstream iss(s);
     double x;
     if (!(iss >> x))
       error("conversion error");
     return x;
   }
   
   void print(const vector<string>& v) {
     const int n = v.size();
     if (n == 0) ;
     else if (n == 1) cout << v[0];
     else {
       cout << v[0];
       for(int i = 1; i < n; ++i) {
         cout << " " << v[i];
       }
     }
   }
   
   ///////////////////////////////////////////////////////////
   //
   // Program-specific helper functions
   //
   ///////////////////////////////////////////////////////////
   
   double peek() {
     if (stack.size() == 0) {
       error("Can't peek an empty stack.");
     }
     return stack.back();
   }
   
   double pop() {
     double tos = peek();
     stack.pop_back();
     return tos;
   }
   
   void push(double x) {
     stack.push_back(x);
   }
   
   void print_stack() {
     const int n = stack.size();
   
     if (n == 0) cout << "<empty stack>";
     else if (n == 1) cout << "<tos=" << peek() << ">";
     else {
       cout << "<tos=" << peek();
       for(int i = n - 2; i >= 0; --i) {
         cout << ", " << stack[i];
       }
       cout << ">\n";
     }
   }
   
   void print(Function f) {
     cout << f.name << ": [";
     print(f.body);
     cout << "]";
   }
   
   void process_token() {
       if (token == "+" ) {
         double b = pop();
         double a = pop();
         push(a + b);
       } else if (token == "*" ) {
         double b = pop();
         double a = pop();
         push(a * b);
       } else if (token == "-") {
         double b = pop();
         double a = pop();
         push(a - b);
       } else if (token == "/") {
         double b = pop();
         double a = pop();
         push(a / b);
       } else if (token == ".") {
         cout << "tos = " << peek() << endl;
         cout << prompt;
       } else if (token == "inc") {
         double b = pop();
         push(b + 1);
       } else if (token == "dec") {
         double b = pop();
         push(b - 1);
       } else if (token == "dup") {
         double b = peek();
         push(b);
       } else if (token == "pstack") {
         print_stack();
       } else if (token == "def") {
         Function f;
         cin >> f.name;
         string eq;
         cin >> eq;
         string t;
         cin >> t;
         while (t != ".") {
           f.body.push_back(t);
           cin >> t;
         }
         functions.push_back(f);
         print(f);
         cout << endl;
         cout << prompt;
       } else {
         // check if token is a user-defined function
         for(int i = 0; i < functions.size(); ++i) {
           Function f = functions[i];
           if (f.name == token) {
             //cout << "user-defined function\n";
             for(int j = 0; j < f.body.size(); ++j) {
               token = f.body[j];
               process_token();
             }
             return;  // jump out of process_token
           }
         }
   
         // assume token is a number
         stack.push_back(string_to_double(token));
       }
   }
   
   
   ///////////////////////////////////////////////////////////
   //
   // Main function
   //
   ///////////////////////////////////////////////////////////
   
   int main()
   {
     cout << "Postfix evaluator\n";
     cout << prompt;
     while (cin >> token) {
       try {
         process_token();
       } catch (runtime_error e) {
         cout << e.what() << endl;
         cout << prompt;
       }
     } // while
   } // main
   


Programming Questions
---------------------

#. Add a built-in operator called ``functions`` that lists all the
   user-defined functions. For example::

      --> functions
      square: [dup *]
      pi: [3.14]
      circle_area: [square pi *]

   If there are no user-defined functions, then ``functions`` should
   return a message saying so.

#. Modify the evaluator so that ``";"``, not ``"."``, is used to
   terminate a function definition::

      --> def square = dup * ;

#. Add code to the ``def`` part of the else-if-else statement in
   ``process_token`` that ensures that ``def`` cannot be added to the
   body of the function being defined (i.e. don't allow a function to
   be defined within a function). Throw an error message if ``def``
   appears in the function body.

#. Add code to the ``def`` part of the else-if-else statement in
   ``process_token`` that ensures that the name of a user-defined
   function *cannot* be a number or a built-in operator. Throw a
   helpful error message if the user tries to create a function with
   an illegal name.

#. Add a new built-in operator called ``help`` that returns a brief
   help message and example of how to use a particular operator. For
   example::

      --> help +
      + pops the top two elements of the stack and pushes their sum
   
      --> help dup
       dup copies the current TOS and pushes it
   
      --> help .
      . prints the current TOS
   
      --> help 3.14
      3.14 is a number

      --> help
      type help X, where X is any one of the following built-in operators:
      + - * / . pstack def [... plus all the other built-in operators ...]