Practice with SCHEME objects

1. Encapsulation-protecting object state (data) behind an abstraction barrier. Define a SCHEME object, named make-rat, which creates an object representing a rational number. Recall that when we introduced pairs, we discussed a representation of rationals using a SCHEME pair. Here, your rational numbers will be represented with objects. Your rational object should expose the following capabilities for a rational number: get numerator, get denominator, get reciprocal, add, subtract, and multiply . Thus, your object should expose the following methods in its dispatcher:
(define (make-rat a b)
...
(lambda (method)
(cond ((eq? method 'numer) getnumer)
((eq? method 'denom) get- denom)
((eq? method 'reciprocal) reciprocal)
((eq? method ' add) add)
((eq? method 'sub) sub)
((eq? method ' mult) mult)))))
Note, your rational number object should represent rationals in reduced form. You may find SCHEME builtin function (gcd a b), which computes the greatest common divisor of its two arguments a and b, useful.
2. Define a SCHEME object— call it basic-set— that maintains an (initially empty) set of numbers. Your object should have methods that correspond to
empty, which should return #t if the set is empty, and #f otherwise;

insert, which should insert a new element into the set; and

delete, which should delete a particular element from the set; and

element?, which should determine if a given element is in the set.

Implement the set as a standard SCHEME list, and return a dispatcher that provides access to your methods,as we have done in class, via a token.

Thus, your object should behave as follows:

> (define newset (basic - set))
> ((newset' empty))
#t
> ((newset' insert) 2)
> ((newset 'element?) 2)
#t
> ((newset ' delete) 2)
> ((newset ' empty))
#t
3. Defifine a SCHEME object — call it stat - set — that maintains an (initially empty) set of numbers along with several statistics pertaining to the set. Your object should have methods that correspond to
  • empty, which should return #t if the set is empty, and #f otherwise;
  • insert, which should insert a new element into the set;
  • element?, which should determine if a given element is in the set;
  • largest, which should return the largest element in the set;
  • smallest, which should return the smallest element in the set;
  • size, which should return the size of the set; and
  • average, which should return the average of the elements in the set.
Note that your set does not need to implement delete. Implement the set as a standard SCHEME list, and return a dispatcher that provides access to your methods, as we have done in class, via a token.

Important amplifification. Your stat - set methods that implement largest, smallest, size, and average, should use only a constant amount of computation to determine their return value: specififically, the amount of time they take to return should not depend on the size of the set. (Thus you cannot scan the list to determine its length, or the maximum element of the list. )

How is this possible? One strategy is to set up some“private variables”in your object called, e.g. current - max, current - min, current -length, etc. These variables should maintain, at all times, the current values of these quantities. When a new number is inserted, you will have to update your list (that maintains the set) and, in addition, update each of these statistics appropriately .

I think that the easiest way to“maintain”the current average is to actually maintain the current sum of all the elements in the set, and — when the user asks for the average — return the sum divided by the current size.

Incidentally, why didn’t we ask you to implement the delete operation?

4. Using the conventional set notation {1, 2, 2} and {1, 2} denote the same set (which contains the numbers 1 and 2 and no others): specififically, as far as a set is concerned, an element either appears or it does not — there is no notion of an object appearing more than once. A multiset is like a set in which elements can appear more than once. People often use the same “ set style ” notation for multisets: e. g . , {1, 2, 2} denotes the multiset in which 1 appears once and 2 appears twice. Of course, as multisets {1, 2, 2} and {1, 2} are different.

Notice that to maintain a multiset (of numbers, say), one needs to keep track of how many times each number appears in the set (which could be zero) . 

Consider the representation of a multiset as a sorted list of pairs, where the fifirst part of each pair represents an integer, and the second represents the number of times it appears (a non - negative integer) . Thus the multiset {1, 2, 2, 3, 8, 8} would be represented as the list ((1 . 1) (2 . 2) (3 . 1) (8 . 2)) .  (Note that numbers which do not appear at all in the multiset do not have a pair in the list. )

Define a multiset object, which provides the methods:
• empty, which should return \#t if the multiset is empty, and \#f otherwise;
• insert, which should insert a new element into the set; of course, if the element already exists in the multiset, the number of times it appears in the set should increase;
• multiplicity?, which should return the number of times a given element appears in the multiset (it should return 0 if the element does not appear at all);
• delete, which should delete one appearance of a particular element from a multiset; and

• delete - all, which remove all appearances of an element in a multiset. 

2Stack Applications

5. In this problem you will defifine an object that implements the Stack abstract data type using a list to store the elements. When the object is created, it starts as an empty stack.

To implement the stack, the object will initially create an empty list, which it will store the elements of the stack. The stack contents are then maintained with the following convention: to represent the stack containing the elements e1, e2 , . . . , en (where e1 is the top of the stack and en is the bottom of the stack) the list will contain the elements as shown in Figure 1, just below. Observe that the bottom element of the stack ’

(e1 e2 e3 . . . ek )

Figure 1: Layout of a stack in a list.

is always at the end of the list. The top element of the stack can be accessed at the front of the list. To place a new element on the top of the stack, one needs only add it to the front of the list. Popping an element off the top of the stack is handled by returning the appropriate element (take particular care to ensure you are returning the proper value when using destructive assignment) and “ removing ” that element from the front of the list. Your object should expose methods for 

empty? Returns a Boolean value (\#t or \#f) depending on whether the stack is empty .

push Pushes a new element onto the top of the stack.

pop Pops off the top element from the stack and returns it.

top Returns the value of the top of the stack (without changing the contents of the stack).

Thus, your object should have the form:(define (make-stack)

(let (...) ;; internal stack variables

(define (empty?)...) ;; stack methods
(define (push x)...)
(define (pop)...)
(define (top)...)

(define (dispatcher ...)...) ;;the dispatcher

dispatcher))
6.(Evaluation of Postfix Expressions) Given a list of operands and operators that represent a postfix expression, one can use a stack to evaluate the postfix expression. Its true! The algorithm to do this is as
follows:
Algorithm 1 Evaluate Postfix Expression
repeat
if operand at front of input string then
push operand onto stack

else

pop stack to remove operands

apply operator to operand(s)
push result onto stack
end if
until input string is empty
For example, to evaluate the expression “ 23 15 + ” we would:
(a) Push 23 onto the stack
(b) Push 15 onto the stack
(c)“+”is an operator, so
i. Pop second operand (note the operands are popped in reverse order)
ii. Pop first operand
iii. Apply the operator (in this case, addition)
iv. Push the result back onto the stack

(d) Once the expression has been evaluated, the result is on the top of the stack.

Define a SCHEME function, named (eval - postfix p), that will take a postfifix expression (stored in a list of integers representing operands and characters representing operators), evaluate that expression, and

return the result.
Your function should support the operations of addition (#\+), subtraction (#\ - ), multiplication (#\*), division(#\/), and exponentiation(#\^).

You may want to work incrementally by starting with a function that takes a character representing an operator and can pop two operands off of a stack, evaluate the operator and push the result back on the stack. Next you can add a function that evaluates a postfifix expression by pushing operands onto the stack and evaluating operators when encountered. Note, you may want to use the number? function to determine whether an item in the list is an operand or an operator.

2019-11-20