CS203, Homework 2
Option 1: Lisp Interpreter
I borrowed the C++ Tree code from the class example as a starting point for my LISP program. The Tree structure was nice because it provided classes for leaves of the tree, where identifiers end up, and internal nodes, which contain operators. The code contained classes for unary and binary operators and for integer and character identifiers. To use the structure for LISP this had to be modified. The internal nodes, namely the operator nodes were fine, but for our purposes we did not need integer nodes, and did need string nodes. I eliminated the IntNode class entirely, and modified the IdNode class. It became two classes, ListNode and AtomNode. The internal representation for ListNode is a string. It's eval() member function just returns the value of the string. The AtomNode's internal representation is a character, however, for compatibility I had to cast it into a string to return it. To get this to work properly I used the old C (char*) representation for strings there, rather than the string data type which I used otherwise. In addition to these class changes, there were a number of type changes. Particularly, the return type of the eval function had to be changed from int to string throughout the program.
My LISP program implements only a small subset of LISP. Car, cdr, eq and cons all work, although there are a few minor differences between some of them and their real function in CMU Common LISP. Cons works as expected if its left operand is an atom (i.e. a single character) and its right operand is a list. In CMUCL eq works only on atoms. In my version it will actually work on lists as well. It is implemented simply using the '==' construct which defined on strings, and therefore works on all strings. It does have a substantial problem, however. Since atoms are constrained to be single characters, NIL is not recognized as an atom. Eq does return NIL if its two operands are not equal. Unfortunately, if it is used as an operand to another operation, output will not be correct. The simplest way around this would be to use some single character (maybe 'N') as a short-hand for NIL, and eliminate it from the set of other possible characters. (Tracey suggests making another type of node, NilNode to handle this, that should also work.) Car works as expected, provided the input is correct for this subset of the language. Cdr works as expected on lists with at least two elements. Since its current implementation is based on taking a substring starting at a particular element (namely element 3) and continuing until the end of the string, it will not work if there are too few elements in the list. The easiest fix for this would be to test the length of the string containing the list, and adjust the implementation accordingly.
In addition to these variations in the function of the basic operations, my LISP subset does not require QUOTE to distinguish values to be taken as is, versus those to be evaluated. Since I have not actually implemented a parser, examples are hard coded and each piece is typed by hand. If I were to implement a parser for this small a subset, it would probably still be easier to leave QUOTE out. Atoms can be identified because they do not begin with '('. Lists to be taken as is can be identified because their first element is not one of the four defined operations.
#include <iostream.h>
#include <string>
//The code for the basic Tree structure is adapted from the
//C++ example on the class web page.
//abstract class for a node in the tree
class Node {
public:
friend class Tree;
friend ostream& operator<<(ostream&, const Tree&);
protected:
Node(){ use = 1; } //constructor
virtual void print(ostream&) = 0;
virtual ~Node() {} //virtual destructor
virtual string eval() = 0; //strings are used to represent all s_expressions
private:
int use; //reference counter
};
//core of Tree data structure
class Tree {
public:
friend class Node;
friend ostream& operator<<(ostream&, const Tree&);
Tree(char); //atoms
Tree(string); //lists
Tree(string, Tree); //unary operators
Tree(string, Tree, Tree); //binary operators
Tree(const Tree& t) { p = t.p; ++p -> use;} //copy constructor
~Tree() {if (--p ->use == 0) delete p; } //destructor, should actually loop
void operator =(const Tree& t);
string eval() {return p->eval();}
private:
Node* p; //internal representation of a Tree node
};
//Tree assignment
void Tree:: operator =(const Tree& t)
{
++t.p -> use; //update reference counter on original
if ( --p -> use == 0) //decrement reference counter on old value of left
delete p; //if nothing else refers to old value of left delete it
p = t.p; //left = right
}
//Tree output
ostream& operator <<(ostream& o, const Tree& t)
{
t.p -> print(o);
return (o);
}
//Nodes that contain lists or atoms will be subclasses of LeafNode
class LeafNode: public Node {
public:
friend class Tree;
private:
void print(ostream& o) = 0;
virtual string eval() = 0;
};
//Atoms
class AtomNode: public LeafNode {
public:
friend class Tree;
string eval() {
char* val = &name; //BAD, see note at end
return val;
}
private:
char name; //atom's name
void print(ostream& o) { o << name ;}
AtomNode(char id): name (id) {} //constructor
};
//Lists
class ListNode: public LeafNode {
public:
friend class Tree;
string eval(){ return name;}
private:
string name; //lists name (ie value)
void print(ostream& o) { o << name ;}
ListNode(string id): name (id) {} //constructor
};
//Unary operators, namely car and cdr
class UnaryNode: public Node {
public:
friend class Tree;
string eval();
private:
string op; //operator
Tree opnd; //operand
UnaryNode(string a, Tree b): op(a), opnd(b) {} //constructor
void print (ostream& o) {o << "(" << op << " " << opnd << ")";}
};
string UnaryNode::eval()
{
if (op == "car"){
return (opnd.eval().substr(1, 1)); //char at position 1 in evaluates operand
}
else {
if (op == "cdr") {
return ("(" + opnd.eval().substr(3, opnd.eval().length()-1));
//the substring starting at position 3 eliminates '(', and first atom
//only works on lists containing at least to elements
}
else {
cerr << "no operator\n" << endl; //no unary operator was given
return 0;
}
}
}
class BinaryNode: public Node {
public:
friend class Tree;
string eval();
private:
string op; //operator
Tree left; //left operand
Tree right; //right operand
BinaryNode(string a, Tree b, Tree c): op(a), left(b), right(c){} //constructor
void print (ostream& o) {o << "(" << op << " " << left << " " << right << ")";}
};
string BinaryNode::eval()
{
if (op == "eq") {
if (left.eval() == right.eval()) {
return "T";
}
else return "NIL"; //BAD because NIL should be an atom, but won't work here
}
else {
if (op == "cons") {
return ("(" + left.eval().substr(0, 1) + " " + right.eval().substr(1, right.eval().length()-1));
//works correctly if left operand is atom and right is string
}
else {
cerr << "no operator\n" << endl; //error
return 0;
}
}
}
//code for Tree constructors
Tree::Tree(char id)
{
p = new AtomNode(id);
}
Tree::Tree(string id)
{
p = new ListNode(id);
}
Tree::Tree(string op, Tree t)
{
p = new UnaryNode(op, t);
}
Tree::Tree(string op, Tree left, Tree right)
{
p = new BinaryNode(op, left, right);
}
int main()
{
//hard coded examples
Tree t1 = Tree("cons", Tree("car", Tree("(a b c)")), Tree("cons", Tree('b'), Tree("(c)")));
Tree t2 = Tree("cdr", Tree("(d e f)"));
Tree t3 = Tree("eq", Tree('a'), Tree('b'));
Tree t4 = Tree("eq", Tree('a'), Tree('a'));
cout << "t1 = " << t1 << endl;
cout << "t2 = " << t2 << endl;
cout << "t3 = " << t3 << endl;
cout << "t4 = " << t4 << endl;
cout << "t1:" << t1.eval() << endl;
cout << "t2:" << t2.eval() << endl;
cout << "t3:" << t3.eval() << endl;
cout << "t4:" << t4.eval() << endl;
}
Note: Tracey suggests
string* val = new string(name);
return val;
or
void eval(string s) {
s=string(name);
}