Languages HW5

CS4250: Programming Languages

HW5: Eric Buckley – 18148800

12.8) Two problems with abstract data types ameliorated by inheritance are ease of customization and the lack of an organizing taxonomy. Without inheritance, an abstract type must either be modified directly (which may not even be possible in the case where the type is defined in a third-party library) or copied to a new data type and modified, which breaks down the generality of the type. By inheriting the type, derived objects benefit from the common functionality, but are free to augment or override aspects which do not match the application.

Inheritance also provides taxonomy of objects within the model. This is more than mere organization; it specifies what types of operations can or must be supported by which objects. A method that operates on the parent class, should also work on any derived class. Methods and properties of the parent class should also be offered by derived classes. This allows for more general (or even generic) routines to be written which operate on abstract classes higher in the derivation tree to consistently apply operations to related objects.

12.12) A subclass has an “is-a” relationship with its parent class when the subclass represents a more specific case of the parent class. For example, a class of Pane could be a subclass of ScreenObject where the former gave specific implementations of virtual methods for displaying and resizing the object on the screen. While this is the most common Parent-Subclass relationship, it is certainly not the only one. For example, a business object may inherit from an output class to pick up display routines, even though it is in no way a special case of an output device. Many architects believe that interfaces are a better way of handling such situations.

12.16) The primary reason for requiring that all Java objects descend (directly or indirectly) from the root class object is that this enforces the ability to handle any object in a generic sense. For example all objects implicitly have a ToString() method, which is useful in exception handlers where the handler may have little or no information about the nature of the object throwing the exception. Likewise, any object can be placed in a generic container of objects. Implicit methods, such as dereferencing and garbage collection also can be written at the level of the single root object, rather than having to define them for each object type that has no parent.

12.21) Objective-C protocols and Java interfaces serve much the same function and, in practical terms, their use is very similar. Perhaps the most significant difference is the fact that interfaces can be used to type an object. Any object that implements an interface can be cast as an object of that type and passed as parameters or assigned to variables that are typed as the interface itself, rather than a class that implements that interface. This greatly simplifies writing generic routines such as storing, sorting, and searching objects where the underlying structure of the object is irrelevant to the operation as long as the interface can provide enough information to carry out the task.

12.24) C# does, in fact, support non-static nested classes that act like inner classes in Java. The difference is that the reference to the parent class has to be explicitly declared as in the following example:

class OuterClass {

 string s;

 // ...

 class InnerClass {

  OuterClass o_;

  public InnerClass(OuterClass o) { o_ = o; }

  public string GetOuterString() { return o_.s; }

 }

 void SomeFunction() {

  InnerClass i = new InnerClass(this);

  i.GetOuterString();

 }

}

The only difference between this and a Java inner class is that in Java, the reference to the enclosing class, o_,  is both created and applied implicitly. C# commentator Raymond Chen (who provides the above example in his blog on msdn.com) refers to the implicit reference as “syntactic sugar”. It serves a purpose, but the C# design team felt that, since the same effect could be achieved with the explicit declaration, there was no need to make a special scoping rule via an implicit (and unseen) reference.

As for the ability of the enclosing class to access the members of the inner class directly, that is also available in C# by simply making all the members public. This does not violate the nested scoping rules since, as with Java, no aspect of a nested class can be accessed outside of the enclosing class.

15.5) The following Scheme function returns the number of zeroes in a simple list.

(define (zeroes aList)

(cond

((null? aList) 0)

(else (+ (if (= 0 (car aList)) 1 0) (zeros (cdr aList))))

))

The first condition handles an empty list and terminates the recursion. The second condition modifies the count based on the first item of the list and then adds the number of zeroes in the remainder of the list. The function is technically not tail recursive, but most interpreters would be able to optimize this into a loop since it is only a simple arithmetic operation and not a bona fide function call being applied to the recursive result.

15.11) To write a Scheme function that returns the reverse of a simple list, we could simply write a helper function that appends an element to end of a list and then append the head of the list to the reverse of the tail. However, such a function would be very inefficient for a large list since it would involve 2 levels of deep recursion. Instead, we write a helper that builds the reversed list on the way down the recursion by moving the head of the source list to the head of the target list and then returns the completed list from the deepest point.

(define (rev2 source target)

(cond

((null? source) target)

(else (rev2 (cdr source) (cons (car source) target)))

))

This function is tail-recursive, so it should be optimized into a loop. The primary function is then a simple call to the helper, initializing the target list to an empty list.

(define (reverse aList)(rev2 aList '()))

16.7) List representation is similar between Prolog and functional languages such as Scheme and Lisp. However, the processing of lists is fundamentally different. While functional languages specify operations on lists, such as head (CAR) and tail (CDR), Prolog specifies patterns which the list needs to match in order for the predicate to continue towards a goal. This could include matching the entire list, some of its contents, or just the head or tail. The actual breaking and combining of the list is then done by the inference engine as needed to match patterns, rather than specified directly by the programmer.

16.2Prog) Given the Prolog predicates

parent(P, X).     %indicates P is a parent of X

female(X).        %indicates X is female

The following rule determines if X is a sister of Y:

sister(X, Y) :- parent(P, X), parent(P, Y), female(X), (X \== Y).

While the above clause demonstrates the logic, is very efficient, and returns properly when both parameters are bound, it returns duplicates when one or both are unbound and the parent relationship is given for both parents of X and Y. To get around this, the built-in setof/3 predicate can be used to first generate a list of parents common to both and continue only if the list is non-empty:

sisterNoDups(X, Y) :- setof(P, (parent(P, X), parent(P, Y)), _),

female(X), (X \== Y).

As setof/3 fails when the empty set is returned in the third position, this will have the same logical effect as the first two clauses of sister/2, but will not return duplicate rows since the set of parents is being requested once from a single clause, so there will be no backtracking on the first clause and the dups are eliminated.

16.3Prog) The following Prolog rules bind the maximum value in a list to the first parameter. The function fails (returns “no”) on an empty list. The first predicate is the terminating condition. The following two bind either the head or the max of the tail to the result, depending on which is greater.

listmax(Max, [Max]).

listmax(H, [H|T]) :- listmax(TailMax, T), TailMax < H.

listmax(TailMax, [H|T]) :- listmax(TailMax, T), TailMax >= H.