readme.html

parser in C++~~~~~~~~~~~~

  <li><tt>Cell(const int i)</tt> constructs an int cell, i.e., a leaf node
    that holds the int value <tt>i</tt></li>
  <li><tt>Cell(const double d)</tt> constructs a double cell, i.e., a leaf
    node that holds a double value <tt>d</tt></li>
  <li><tt>Cell(const char* const s)</tt> constructs a symbol cell, i.e., a
    leaf node that holds the symbol name <tt>s</tt></li>
  <li><tt>Cell(Cell* const my_car, Cell* const my_cdr)</tt> constructs a cons
    cell, i.e., an internal node that holds two pointers <tt>my_car</tt> and
    <tt>my_cdr</tt></li>
</ul>

<p>Other than these constructors, you'll need to implement these public
member functions:</p>
<ul>
  <li><tt>bool is_int() const</tt> returns true iff <tt>this</tt> is an int
    cell</li>
  <li><tt>bool is_double() const</tt> returns true iff <tt>this</tt> is a
    double cell</li>
  <li><tt>bool is_symbol() const</tt> returns true iff <tt>this</tt> is a
    symbol cell</li>
  <li><tt>bool is_cons() const</tt> returns true iff <tt>this</tt> is a cons
    cell</li>
</ul>
<ul>
  <li><tt>int get_int() const</tt> returns the value in this int cell (error
    if <tt>this</tt> is not an int cell)</li>
  <li><tt>double get_double() const</tt> returns the value in this double
    cell (error if <tt>this</tt> is not a double cell)</li>
  <li><tt>string get_symbol() const</tt> returns the symbol name in this
    symbol cell (error if <tt>this</tt> is not a symbol cell)</li>
  <li><tt>Cell* get_car() const</tt> returns the car pointer of this cons
    cell (error if <tt>this</tt> is not a cons cell)</li>
  <li><tt>Cell* get_cdr() const</tt> returns the cdr pointer of this cons
    cell (error if <tt>this</tt> is not a cons cell)</li>
</ul>
<ul>
  <li><tt>void print(ostream&amp; os) const</tt> prints the subtree rooted at
    this cell, in s-expression notation</li>
</ul>

<p>In <tt>Cell.cpp</tt> you'll also need to define this global constant, that
was declared as an extern in <tt>cons.hpp</tt> (and in <tt>Cell.hpp</tt>
too):</p>
<ul>
  <li><tt>Cell* const nil</tt> is the value for a null pointer, which we
    consider equivalent to an empty list.</li>
</ul>

<p>Hint: depending on your approach, you could choose either to implement
<tt>nil</tt> as the C++ <tt>NULL</tt> value (the pointer to address zero), or
as some unique dummy <tt>Cell*</tt> value (known as a <em>sentinel</em>, as
you should learn in COMP171). If you don't know what this means yet, then
don't worry and just implement <tt>nil</tt> as the C++ <tt>NULL</tt> value,
exactly as in the dummy version of <tt>Cell.cpp</tt> that we give you. The
following sections discuss how <tt>nil</tt> is used.</p>

<h3>Some background on the cons list ADT</h3>

<p>The abstract data type (ADT) that the parser author chose to use is a
traditional <a
href="http://en.wikipedia.org/wiki/Lisp_programming_language#Conses_and_lists"><em>cons
list</em></a> ADT dating back to around 1958. This ADT only requires a nil or
NULL constant representing an empty list (which can be written <tt>()</tt>
using s-expression notation), plus only three essential core operations <a
href="http://en.wikipedia.org/wiki/Cons"><em>cons</em></a>, <a
href="http://en.wikipedia.org/wiki/Car_and_cdr"><em>car</em></a> and <a
href="http://en.wikipedia.org/wiki/Car_and_cdr"><em>cdr</em></a>:</p>
<ul>
  <li><a href="http://en.wikipedia.org/wiki/Cons"><em>cons</em></a>
    constructs a new list with a given car value and cdr list. For example: 
    <ul>
      <li><tt>cons(1, nil)</tt> returns <tt>(1)</tt></li>
      <li><tt>cons(1, cons(2, nil))</tt> returns <tt>(1 2)</tt></li>
      <li><tt>cons(1, cons(2, cons(3, nil)))</tt> returns <tt>(1 2
      3)</tt></li>
      <li><tt>cons(cons(1, cons(2, nil)), cons(3, nil))</tt> returns <tt>((1
        2) 3)</tt></li>
    </ul>
  </li>
  <li><a href="http://en.wikipedia.org/wiki/Car_and_cdr"><em>car</em></a>
    gives the value of the head node of the list. For example: 
    <ul>
      <li><tt>car(cons(1, nil))</tt> returns <tt>1</tt></li>
      <li><tt>car(cons(cons(1, nil), nil))</tt> returns <tt>(1)</tt></li>
      <li><tt>car(cons(cons(1, cons(2, nil)), cons(3, nil)))</tt> returns
        <tt>(1 2)</tt></li>
    </ul>
  </li>
  <li><a href="http://en.wikipedia.org/wiki/Car_and_cdr"><em>cdr</em></a>
    (pronounced "could-er" or "cudder") gives the list after the head node.
    For example: 
    <ul>
      <li><tt>cdr(cons(1, cons(2, cons(3, nil))))</tt> returns <tt>(2
      3)</tt></li>
      <li><tt>cdr(cons(cons(1, cons(2, nil)), cons(3, nil)))</tt> returns
        <tt>(3)</tt></li>
    </ul>
  </li>
</ul>

<p>Building up large trees this way can get a bit tedious, so in practice
typically people also define equivalent shorthand functions. Mathematically
speaking, such functions are not really necessary, and exist only for the
sake of convenience. For example,</p>
<ul>
  <li><a
    href="http://en.wikipedia.org/wiki/Lisp_programming_language#Conses_and_lists"><em>list</em></a>
    builds a new list containing the operands. For example: 
    <ul>
      <li><tt>list(1)</tt> is shorthand for <tt>cons(1, nil)</tt> and returns
        <tt>(1)</tt></li>
      <li><tt>list(1, 2, 3)</tt> is shorthand for <tt>cons(1, cons(2, cons(3,
        nil)))</tt> and returns <tt>(1 2 3)</tt></li>
      <li><tt>list(list(1, 2), 3)</tt> is shorthand for <tt>cons(cons(1,
        cons(2, nil)), cons(3, nil))</tt> and returns <tt>((1 2) 3)</tt></li>
    </ul>
  </li>
</ul>

<p>To keep your life simple, you are <em>not</em> required to implement
<tt>list</tt> even though we'll use it in written examples later.</p>

<h3>Implementing the cons list ADT</h3>

<p>How do you implement the cons list ADT? In fact there exist many different
implement approaches.</p>

<p>You've decided to use the most traditional approach, which is to use a
singly linked list data structure (recall Lab 2). This is the most natural
and intuitively obvious way to implement the cons list ADT. As explained in
<a
href="http://en.wikipedia.org/wiki/Scheme_programming_language#Lists">Wikipedia</a>:</p>

<p>Specifically, each node in the linked list is a cons cell, also called a
pair. As the name pair implies, a cons cell consists of two values: the first
one is the <tt>car</tt>, and the second is the <tt>cdr</tt>. For <tt>list(1,
2, 3)</tt>, there are three cons cells, or pairs. The first cons cell has the
number 1 in the first slot, and a pointer to the second cons cell in the
second. The second cons cell has the number 2 in the first slot, and a
pointer to the third cons cell in the second slot. The third cons cell has
the number 3 in the first slot and a NULL constant in the second slot. The
NULL constant is usually represented by <tt>()</tt>. The cons function
constructs these cons cells, which is why <tt>cons(1, list(2, 3))</tt> gives
the list <tt>(1 2 3)</tt>. <!-- If both of the arguments are not lists, then a pair is created,
  usually represented with a dot. For example, (cons 1 2) gives (1 . 2),
  where the cons cell consists of 1 and 2 in its slots instead of a pointer
  to another cons cell in its second slot. -->
 </p>

<p>Here's a picture of the linked list to hold <tt>((1 2) 3)</tt>, using
what's known as box-and-pointer notation. Notice how it naturally matches the
exact structure of <tt>cons(cons(1, cons(2, nil)), cons(3, nil))</tt>.
There's one box for each <tt>cons</tt>, and two <tt>nil</tt> pointers.</p>
<img src="boxandpointer.jpg" /> 

<p>In this assignment, cells can hold four kinds of values: int, double,
symbol, and cons. You need a way to store any of these types of values in
your cells. How do you do this efficiently?</p>

<p>The obvious naive way is just to have four data members:</p>
<pre>class Cell {
  // ...
  int int_m;
  double double_m; 
  char* symbol_m;
  ConsPair conspair_m;
};</pre>

<p>But this is a terribly inefficient waste of memory. Any instance of a
<tt>Cell</tt> will only be using one of these data members. So a better way
is to use a <em>union</em>:</p>
<pre>class Cell {
  // ...
  union {
    int int_m;
    double double_m; 
    char* symbol_m;
    ConsPair conspair_m;
  };
};</pre>

<p>Unions exist in both C and C++. A union is sort of like a struct, except
that a struct provides memory space to simultaneously store all its members,
whereas a union provides memory space to store only one of its members at a
time. So this way, we won't waste memory space.</p>

<p>The only problem is: when you're using a union, how do you know
<em>which</em> of the data members is the valid one? C++ won't tell you; it
is your program's own responsibility to keep track of this. If you don't, you
can easily create horrible bugs. For example:</p>

<p><tt>Cell* c = new Cell;</tt><br />
<tt>c-&gt;double_m = 2.718;</tt><br />
<tt>cout &lt;&lt; c-&gt;int_m;</tt> <i>// whoops! will print out a garbage
int</i><br />
<tt>cout &lt;&lt; c-&gt;symbol_m;</tt> <i>// whoops! will either seg fault or
do wildly unpredictable things</i></p>

<p>To keep track of which member in the union is currently valid, you should
use what's known as a <em>tagged union</em> or <em>discriminated union</em>
approach:</p>
<pre>class Cell {
  // ...
  enum TypeTag {type_int, type_double, type_symbol, type_conspair};
  TypeTag tag_m;
  union {
    int int_m;
    double double_m; 
    char* symbol_m;
    ConsPair conspair_m;
  };
};</pre>

<p>Now you can write your code so that you make sure that the <tt>tag_m</tt>
always holds an up-to-date value indicating which of the union members is
valid at the current time.</p>

<h3>Evaluating the expression tree</h3>

<p>After you've gotten the parser to store the expression into your real tree
data structure (your concrete implementation of the cons list ADT), now you
need to write a function that evaluates it.</p>

<p>To do this, you merely need to perform a depth-first traversal starting
from the root. As you complete each subtree, the evaluator should return the
value resulting from evaluating the sub-expression stored in that subtree. By
the time you finish the entire traversal, you will be back at the root---so
the evaluator should return the value resulting from evaluating the entire
expression.</p>

<p>The problem is: what is the <em>type</em> that should be returned by your
evaluator function?</p>

<p>It would seem that this depends on the type of the operands---remember,
from the introduction:</p>

<p><tt>(+ 2 3 4 5)</tt> should return the int <tt>14</tt><br />
<tt>(+ 2 3.5)</tt> should return the double <tt>5.5</tt><br />
<tt>(+ (+ 3 -1) 3.5)</tt> should return the double <tt>5.5</tt><br />
<tt>(if 5 7 8.3)</tt> should return the int <tt>7</tt><br />
<tt>(if 0 7 8.3)</tt> should return the double <tt>8.3</tt><br />
<tt>(if (+ 2 3) (+ 4 3) (+ 6 2.3))</tt> should return the int <tt>7</tt><br />
<tt>(if (+ 2 -2) (+ 4 3) (+ 6 2.3))</tt> should return the double
<tt>8.3</tt><br />
<tt>(+ 1 (if (+ 2 -2) (+ 4 3) (+ 6 2.3)))</tt> should return the double
<tt>9.3</tt><br />
<tt>(ceiling 4.7)</tt> should return the int <tt>5</tt><br />
<tt>(ceiling -4.7)</tt> should return the int <tt>-4</tt></p>

<p>But C++ won't let us write a function that returns different types
depending on the result!</p>

<p>To solve this problem, we'll re-use your <tt>Cell</tt> implementation.
Remember, <tt>Cell</tt> already gives us a way to store different types of
values in the same class type, by using a tagged union. So your function
evaluator should return a <tt>Cell*</tt> that points to a <tt>Cell</tt>
holding the value resulting from evaluating the expression:</p>
<ul>
  <li><tt>Cell* eval(Cell* const c)</tt> returns the value resulting from
    evaluating the expression tree whose root is pointed to by <tt>c</tt>
    (error if <tt>c</tt> is not a well-formed expression)</li>
</ul>

<p>You'll find this declaration in the header file <tt>eval.hpp</tt>, which