Due Date: November 20, 2012 General Requirements and the Major Classes Write a p

Question

Due Date: November 20, 2012 General Requirements and the Major Classes Write a program in Java to implement certain Lisp-like functions as described below. Symbolic names representing atomic S-expressions in Lisp should be stored in a Symbol Table. The symbolTable is constructed as a Hashtable of objects called Items. Each Item has two members: a String field called name holding the name of the Item; a Node field called link that is a reference to the Node holding the current value of the name if it exists (i.e. has been assigned to this name via a setq statement). For every Item its link field is set initially to null (null pointer), and it can be changed only by performing a setq statement. The truth values, t and nil, will be treated as predefined Strings and thus, they will be stored also in the Symbol Table. List structures will be represented by lists of Nodes which are objects of the Node class. With a few exceptions all the arguments of our Lisp-like functions will be of type Node. Similarly, the results returned by these functions will be also of type Node. (Normally, our functions will have to create a new (anonymous) Node for holding the result to be returned.) This way, we can support function composition in a type-free manner because function values, regardless of their actual type, can be used as arguments in any functions since they are all wrapped into the uniform type of Node. Note that our Lisp-like functions do not have to pre-evaluate their arguments because we assume that all the arguments are fully evaluated prior to their use as arguments in our functions. The functions to be implemented should simulate the actions of the corresponding Lisp functions. For your convenience you may use the class declarations and function definitions shown in the ATTACHMENT. Functions to be Implemented The function Node quote(String name) takes a String as the argument and returns a newly created anonymous node that contains the name of the corresponding Item in the Symbol Table. So, the quote function will have to search the Symbol Table for the given name and, if it is not there yet, it must create a new Item for it and put it in the Symbol Table. The function Node setq(String name, Node p) sets the Node field of the Item named by its first argument to its second argument, which is of type Node. Again, if the name cannot be found in the Symbol Table, a new Item must be created for it which then must be put in the Symbol Table. The function Node eval(name) is a special function which does not directly correspond to a particular Lisp function. It takes a name for its argument and looks it up in the Symbol Table. If found then its value (i.e., the contents of its Node field) will be returned which, of course, may be null. The meaning of the following functions must be obvious: Node cons(p,q); Node car(p); Node couder(p); Node append(p,q) Node reverse(p); Node cutlast(p); Node atom(p); Node list-p(p); Node null-p(p); Remember that the empty list has two different representations both of which should be recognized. The arguments of the next three functions should represent only flat lists of integers: Node sum_of(p); Node product_of(p); Node max_of(p); while the arguments of Node and(p,q); Node or(p,q); Node not(p); are single nodes representing boolean values. The function Node remove(p,q); (where the node p holds an integer k) removes the k-th member of the list q. The implementation of the function Node if(p,q,r); will be is slightly different from the others, because its first argument, p, must be evaluated to see if it is true or false. If it is just a boolean constant (i.e. the string 't' or 'nil') then no further evaluation is needed. But, if it is some other string then it is assumed to be the name of a variable whose current value must be looked-up in the Symbol Table. (If it does not have a current value then we have to report an error.) The first argument of the Node member(p,q); function is arbitrary but its second argument must be a list. It checks if p occurs as a member of the list q. Finally, the Node dropall(p,q); function eliminates all the occurrences (if any) of p from the list q. Test Procedures You should thoroughly test your implementation via your main program by calling various combinations of functions and printing their results. A sample segment of such a test can be found in the ATTACHMENT. Attachment import java.util.*; import java.io.*; class Item { public String name; public Node link; public Item (String name) { this.name = name; this.link = null; } public void showit() { System.out.println(" "+this.name); } } // END OF CLASS Item class Node { public char tag; public int val; public Item ref; public Node head; public Node tail; public Node(String name) { this.tag ='S'; this.ref = Attachment.install(name); this.head = null; this.tail = null; } public Node(int number) { this.tag = 'I'; this.val = number; this.ref = null; this.head = null; this.tail = null; } public Node() { this.tag = 'L'; this.val = 0; this.ref = null; this.head = null; this.tail = null; } } // END OF CLASS Node /********************************************************************/ public class Attachment { public static Hashtable symbolTable = new Hashtable(); public static Node nil = new Node(); public static void dumpTable() { System.out.println(" The list of symbols stored in the Symbol Table:"); for (Enumeration e = symbolTable.elements(); e.hasMoreElements();) ((Item)e.nextElement()).showit(); } public static Item locate(String name) { Item temp; if (symbolTable.containsKey(name)) { temp = (Item)symbolTable.get(name); // System.out.println(" located name = "+temp.name); return ((Item)symbolTable.get(name)); } else return null; } public static Item install(String name) { Item temp; temp = locate(name); if (temp == null) { symbolTable.put(name, new Item(name)); temp = (Item)symbolTable.get(name); // System.out.println(" installed name = "+temp.name); } return temp; } public static void printList(Node p) { if (p == null) { System.out.println(" Missing argument in printList"); return; } if (p.tag == 'S') System.out.print(p.ref.name+" "); else if (p.tag == 'I') System.out.print(p.val+" "); else if (p.tag == 'L') { System.out.print(" ( "); Node t = p.head; while (t != null) { printList(t); t = t.tail; } System.out.print(") "); } } public static Node copy(Node from) { Node into = new Node(); if (from == null) return null; into.tag = from.tag; if (into.tag == 'S') into.ref = from.ref; else if (into.tag == 'I') into.val = from.val; else if (into.tag == 'L') into.head = copy(from.head); into.tail = copy(from.tail); return into; } /**********************************************************************/ public static Node cons(Node p, Node q) { Node r, s; if (p == null) { System.out.println(" first argument is missing in cons "); return null; } if (p.tail != null) { System.out.println(" illegal sibling in the first argument "); return null; } r = copy(p); s = null; if (q == null) { System.out.println(" second argument is missing in cons "); return null; } if (q.tail != null) { System.out.println(" illegal sibling in the second argument "); return null; } if (q.tag == 'L') s = copy(q); else if (q.tag == 'S') { if (q.ref.name.compareTo("nil") == 0) s = new Node(); } else { System.out.println(" second argument in cons is not a list"); return null; } r.tail = s.head; s.head = r; return s; } // END of cons /**************************************************************************/ public static void main(String argv[]) { symbolTable.put("nil", new Item("nil")); symbolTable.put("t", new Item("t")); Node a = new Node("THIS"); Node b = new Node("WILL"); Node c = new Node("BE"); Node d = new Node("FUN"); Node e = new Node("nil"); // The string "nil" as the empty list System.out.println(); printList(e); System.out.println(); printList(cons(a, e)); System.out.println(); printList(nil); System.out.println(); printList(cons(d, nil)); System.out.println(); printList(cons(c, cons(d, nil))); System.out.println(); printList(cons(b, cons(c, cons(d, nil)))); System.out.println(); printList(cons(a, cons(b, cons(c, cons(d, nil))))); System.out.println(); printList(nil); Node t = cons(d, nil); System.out.println(); printList(t); Node u = cons(c, t); System.out.println(); printList(u); Node v = cons(b, u); System.out.println(); printList(v); Node w = cons(a, v); System.out.println(); printList(w); System.out.println(); Node zero = new Node(0); Node Node(1); Node two = new Node(2); Node three = new Node(3); Node p = cons(three, nil); p = cons(two, p); p = cons(one, p); p = cons(zero, p); System.out.println(); printList(p); Node q = cons(p, w); System.out.println(); printList(q); dumpTable(); System.out.println(" Lisper Program Finished"); } // END of main } // END OF CLASS Attachment

Explanation / Answer

it easy very big deal to understand what you posted any wayy import java.util.*; import java.io.*; // To implement LISP-like List in Java to perform functions like car, cdr, cons. class Lisp { Vector v = new Vector(4,1); int i; InputStreamReader isr = new InputStreamReader(System.in); BufferedReader inData = new BufferedReader(isr); String str; //Create a LISP-Like List using VECTOR public void create() { int n; System.out.print(" Enter the Size of the list:"); //Get Input from the user...Use I/p stream reader for it... try { str = inData.readLine(); n = Integer.parseInt(str); for(i=0;i { int temp; System.out.print(" Enter the element " + (i+1) + " of the list:"); str = inData.readLine(); temp=Integer.parseInt(str); v.addElement(new Integer(temp)); } } catch (IOException e) { System.out.println("Error!"); System.exit(1); } } //Display the content of LISP-List public void display() { int n=v.size(); System.out.print("[ "); for(i=0;i { System.out.print(v.elementAt(i) + " "); } System.out.println("]"); } /* The car of a list is, quite simply, the first item in the list. For Ex: car of L.car() of a list [3 0 2 5] returns 3. Gives the CAR of LISP-List */ public void car() { System.out.println(" CAR of the List: " + v.elementAt(0)); } /* The cdr of a list is the rest of the list, that is, the cdr function returns the part of the list that follows the first item. For ex: cdr of a list [3 0 2 5] returns [0 2 5] */ public void cdr() { int n=v.size(); System.out.print(" The CDR of the List is:"); System.out.print("[ "); for(i=1;i { System.out.print(v.elementAt(i) + " "); } System.out.println("]"); } /* The cons function constructs lists. It is useful to add element to the front of the list; it is the inverse of car and cdr. For example, cons can be used to make a five element list from the four element list. For ex: adding 7 to [3 0 2 5], cons(7) gives [7 3 0 2 5] */ public void cons(int x) { v.insertElementAt(x,0); System.out.print(" The List after using CONS and adding an element:"); display(); } // Returns the length of the LISP-List public int length() { return v.size(); } } class Lisp_List { public static void main(String[] args) { Lisp a = new Lisp(); a.create(); System.out.print(" The contents of the List are:"); a.display(); a.car(); a.cdr(); a.cons(5); System.out.println(" The length of the list is " + a.length()); } } Output Enter the Size of the list:4 Enter the element 1 of the list:3 Enter the element 2 of the list:0 Enter the element 3 of the list:2 Enter the element 4 of the list:5 The contents of the List are:[ 3 0 2 5 ] CAR of the List: 3 The CDR of the List is:[ 0 2 5 ] The List after using CONS and adding an element:[ 5 3 0 2 5 ] The length of the list is 5

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.