C311 script11.txt -- 11/11/96

---

		  OBJECT-ORIENTED PROGRAMMING (CONTINUED)

---

CODE REUSE

  DELIGATION: a class passes on a message if it does not deal with it

    very dynamic: hard to predict behavior

+++

    Scheme OOP using deligation

	(define make-bounded-stack
	  (lambda ()
	    (let ((bound 10) (stack (make-stack)))
	      (lambda (message)
		(case message
		  ((push!) (if (< ((stack 'local-pushed)) bound)
			       (stack 'push!)
			       (error "Bounded stack: bound exceeded")))
		  ((set-bound!) (lambda (x) (set! bound x)))
		  (else (stack message)))))))

+++

  INHERITANCE: which method will be invoked by a given message is
  determined at class creation time.

---

INHERITANCE

  new classes may add new behavior or state

  method overriding (modifying inherited behavior) is generally possible
  by declaring a method with the same name as an inherited method

  single inheritance: only one immediate ancestor; e.g. Java, Ada95,
      Smalltalk (usually) 

  multiple inheritance: multiple ancestors possible; e.g. C++, CLOS

    creates many problems

      If two inherited classes each define a method or variable of the same
      name, which one does the name denote in the subclass?

        In C++, such a reference must include a superclass that
        disambiguates the reference. 

      If a base class B is a subclass of classes C and D inherited by E,
      does an instance of E contain one or two copies of B's instance variables?

             B                          B   B
            / \                         |   |
        If C   D , is this the same as  C   D ?
            \ /                          \ /
             E                            E

        In C++, yes unless B is declared to be a VIRTUAL BASE CLASS.

---

  Java inheritance

    class declaration syntax: after class name, may insert "extends ClassName"
  
    method final modifier: can't be overwridden

    class final modifier: cannot be a superclass

    abstract method modifier: body not defined (a semicolon)

      Overriding of method identifier with a method definition is 
      required before the method can be used.

    abstract class modifier

      contains one or more abstract methods

      cannot be instantiated

      The only point in abstract classes (or methods) is to increase the
      power of polymorphism.

---

POLYMORPHISM in OOP

  A polymorphic method (or function) may be passed arguments of more than
  one type.

  Several kinds of polymorphism are used in OOP:

    dynamic typing (e.g. in Smalltalk, CLOS, Scheme)

    SUBTYPING via inheritance and interfaces

      This form of polymorphism is the most important for a statically-typed
      OOP language.

    GENERIC PROCEDURES (e.g. in CLOS) 

    METHOD OVERLOADING (e.g. in Java, C++): multiple methods in a class
    with the same name, with selection based on argument types

---

Java (slightly simplified) INTERFACE DECLARATION syntax

  similar to class declaration except

    keyword 'interface' instead of 'class'

    body contains

      no static initializers

      only variables with constants as initializer expressions
      and which have only the implicit modifiers static and final 

      methods declarations with abstract body (just a semicolon)          
      and which have only the implicit modifiers public and abstract

Java class declaration syntax: after class name, may insert

  "implements InterfaceName,+" (one or more InterfaceNames separated by comas)

  class effectively has several types: it's own name and each InterfaceName

+++

C++: fully abstract classes (having only abstract methods) may be used
as interfaces.

---

SUBTYPING

  is more general than inheritance

    If A inherits B (A is a subclass of B), then A is a subtype of B.

    But with interfaces, if A is a subtype of B, 
    it may not be a subclass of B.

    Subtyping is more flexible: necessary for databases where structure
    outlives implementation.

    "Multiple inheritance" of interfaces is not a problem.

    Binary methods, which operate on the internal structure of two objects
    that are of the same class, generally require implementation inheritance.

  Java interface declaration syntax: after interface name, may insert
    "extends InterfaceName,*"

  C++: this effect may be obtained by mulitple-inheritance of virtual 
    base classes.

---

  Java example: 

    public class Test3 {
      public static void main(String args[]) {
	print(new One());
	print(new Two());
      }
      static void print(Num n) {
	System.out.println(n.value());
      }
    }
    interface Num {
      int value();
    }
    interface NextNum extends Num {
      int next();
    }
    class One implements Num {
      public int value() {
	return 1;
      }
    }
    class Two implements NextNum {
      public int value() {
	return 2;
      }
      public int next() {
	return 3;
      }
    }

---

STATIC METHOD BINDING: methods are looked up in the method environment of
the class that indicates the known class of the object.

DYNAMIC METHOD BINDING: methods are looked up in the method environment of
the class that created the instance that receives the method-name message.

< picture on board >

Can't tell the difference unless the method was overridden and is being
invoked with a known class "below" the overriding.

When there is a difference, you usually want dynamic method binding.

  Static method binding is the default in C++.

    Declare all methods to be virtual (dynamically bound) unless you
    are sure you want it to be static.

    If methods are not virutal, trouble is often not created until
    the class is reused.

Static method bindings can be resolved at compile time in a statically
typed language.

Dynamic method bindings can be resolved with one level of indirection in a
method table using an offset computed at compile time (in a statically
typed language).

In dynamically typed languages, caching of the last method access at each
call cite dramatically reduces method lookup overhead (e.g. in Smalltalk
and CLOS).

---

SCHEME-- : a small extension of Scheme to demonstrate OO programming.

Instances are represented as alists of method bindings.

In a method body, THIS refers to the current object and
SUPER refers to the parents subobject.


(CALL name instance-exp arg ...) ==>

  (LET ((instance instance-exp))
    ((LOOKUP-METHOD name instance) instance arg ...))


LOOKUP-METHOD does a standard alist lookup.

+++

(CALL name SUPER arg ...) ==>

  ((LOOKUP-METHOD name instance) THIS arg ...))

---

(METHOD formals body ...) ==>

  (LAMBDA (THIS . formals) body ...)

+++

(CLASS formals
  ((instance-var instance-var-exp))
  super-exp
  ((method-name method-exp) ...)) ==>

  (LAMBDA formals
    (LETREC* ((instance-var instance-var-exp) ...)
      (LET ((SUPER super-exp))
        (APPEND
          (LIST (CONS method-name method-exp) ...)
          SUPER))))


LETREC* is like LETREC, but always evaluates declaration expressions
in the order of their appearance.

+++

The thunk <OBJECT> returns the empty list representing the subobject of
the root class.

---

The implementation follows, using the DEFINE-SYNTAX mechanism for defining
the syntactic extensions indicated above using ==>.  (You are not
responsible for this implementation technology.)

> (begin
    (define-syntax call
      (lambda (x)
	(syntax-case x (super)
	  ((_ name super arg ...)
	   (syntax ((lookup-method 'name super) this arg ...)))
	  ((_ name instance-exp arg ...)
	   (syntax (let ((instance instance-exp))
		     ((lookup-method 'name instance) instance arg ...)))))))
    (define lookup-method
      (lambda (name instance)
	(let ((x (assq name instance)))
	  (if (pair? x)
	    (cdr x)
	    (error 'call "Bad Method: ~s" name)))))
    (define-syntax method
      (lambda (x)
	(syntax-case x ()
	  ((_ formals body0 body1 ...)
	   (with-syntax ((this (datum->syntax-object (syntax _) 'this)))
	     (syntax (lambda (this . formals) body0 body1 ...)))))))
    (define-syntax letrec*
      (lambda (x)
	(syntax-case x ()
	  ((_ ((var exp) ...) body0 body1 ...)
	   (syntax (let ((var '*) ...)
		     (set! var exp) ...
		     body0 body1 ...))))))
    (define-syntax class
      (lambda (x)
	(syntax-case x ()
	  ((_ formals
	     ((instance-var instance-var-exp) ...)
	     super-exp
	     ((method-name method-exp) ...))
	   (with-syntax ((super (datum->syntax-object (syntax _) 'super)))
	     (syntax
	       (lambda formals
		 (letrec* ((instance-var instance-var-exp) ...)
		   (let ((super super-exp))
		     (append
		       (list (cons 'method-name method-exp) ...)
		       super))))))))))
    (define <object>
      (lambda ()
	'())))

> (define c
    (class (class-param) ((inst-var 3)) (<object>)
      ((method1 (method (meth-param)
		  (set! inst-var class-param)
		  (call method2 this (+ 1 meth-param))))
       (method2 (method (x) (+ inst-var x))))))

> (define inst (c 1))

> (list
    (call method2 inst 2)
    (call method1 inst 1))
(5 3)

> (define d
    (class () () (c 2)
      ((method1 (method () (call method1 super 4))))))

> (call method1 (d))
7

---

Now we demonstrate virtual methods.

> (define a
    (class () () (<object>)
      ((f (method () (call v this)))
       (v (method () 1)))))

> (define b
    (class () () (a)
      ((v (method () 2)))))

> (call f (b))
2

---

The last example in Java:

    public class Virtual {
      public static void main(String args []) {
	System.out.println((new B()).f());
      }
    }
    class A {
      int f() { 
	return this.v();
      }
      int v() {
	return 1;
      }
    }
    class B extends A {
      int v() {
	return 2;
      }
    }

---

The last example in C++, with static methods for comparison.

    #include <iostream.h>

    class A {
    public:
      void f() { 
	cout << "virtual " << (*this).v()
	     << " static " << (*this).s() << endl;
      }
    protected:
      virtual int v() { return 1; }
      static int s() { return 1; }
    };

    class B : public A {
      int v() { return 2; }
      int s() { return 2; }
    };

    int main() {
      (*(new B())).f(); // prints "virtual 2 static 1"
      return 0;
    }

---

  CASTING to move type up or down the inheritance chain (from an object to
  the root of the inheritance tree)

    WIDENING: move to a supertype (towards the root)

    NARROWING: move to a subtype (away from the root)

---

END

---