Xref: utzoo comp.lang.misc:7052 comp.object:2875
Newsgroups: comp.lang.misc,comp.object
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!batcomputer!cornell!rochester!kodak!islsun!cok
From: cok@islsun.Kodak.COM (David Cok)
Subject: Re: CHALLENGE: typing and reusability (was: Re: blip)
Message-ID: <1991Mar26.005805.1914@kodak.kodak.com>
Sender: news@kodak.kodak.com
Organization: Eastman Kodak Co., Rochester, NY
References: <1991Mar20.214231.3411@neon.Stanford.EDU> <jls.669591628@rutabaga> <1991Mar22.210725.29448@neon.Stanford.EDU>
Date: Tue, 26 Mar 91 00:58:05 GMT

In article <1991Mar22.210725.29448@neon.Stanford.EDU> hoelzle@neon.Stanford.EDU (Urs Hoelzle) writes:

	[ discussion of static and dynamic typing ]
>======================  example ==============================
>Assume the following types:
>
>type List = generic list; understands (among others)
>	     'concatenate': returns a new [generic] list which is the 
>		concatenation of the two argument lists"
>	     'do': takes a procedure with one argument and applies it
>	        to all elements of the list (i.e. a generic iterator)
>
>type FooType = "object that understands 'foo'"
>
>type A = some random application type, understands (among others)
>	 'foo' and 'display'
>              
>type B = some other application type (completely unrelated to A), also
>	 understands (among others) 'foo' and 'display'
>
>Also assume that there exists a procedure someProc(l:List of FooType)
>which iterates through the list and may send 'foo' to some of its
>elements.
>
>VAR listA: "list of objects of type A"
>VAR listB: "list of objects of type B"
>VAR listC: "see below"
>
>Now, the program you're writing has to do:
>
>listA := ...  // some computation to fill the list
>listB := ...  // some computation to fill the list
>
>listC := listA.concatenate(listB);	// make a new list containing As and Bs
>
>someProc(listC);			// do the "foo thing" to the list
>
>listC.do(display);			// display all elements of the list
>
>======================  end of example =========================
>
>** So, would everybody who does *NOT* believe that dynamically-typed       **
>** languages can achieve greater reusability than today's statically-typed **
>** languages PLEASE post a solution to this (written in his/her favorite   **
>** programming language)???                                                **
>
>To avoid misunderstandings, please note that the above example *is*
>type-safe in an abstract sense: no 'message not understood' error can
>occur because all elements of listC understand both 'foo' (which may
>be sent by someProc) and 'display'.  However, I claim that this piece
>of code won't type-check in Ada, C++, Eiffel, ...
>
>
>-Urs
>
>
>-- 
>------------------------------------------------------------------------------
>Urs Hoelzle                                            hoelzle@cs.stanford.EDU
>Center for Integrated Systems, CIS 42, Stanford University, Stanford, CA 94305

I'm not claiming to dispute that dynamically-typed languages can achieve 
greater resuability (nor that using gotos can lead to more compact code !).
However, I do prefer static typing where it works and am interested in 
discovering how to make it work better.  In any case Hoelzle's programming 
challenge could not be resisted.  So given that one wanted to (had to?) use C++,
here is a (partial) solution which compiles and runs on my Sun C++ 2.0 (on a 
Sparc).  The classes involved have enough detail to make them run, and little 
more.  At the end there are some comments about what I
could and could not make work (in C++) and what that says about static typing.
Better C++ programmers may have improvements.

The example below seems also to be a nice natural use of multiple inheritance.

// Just to keep it interesting we'll assume that classes A and B are
// derived from some other, unrelated base classes. 

#include <stream.h>

class BaseA {
private:
	int basea;
public:
	BaseA(int a): basea(a) {}
	virtual void display() { cout << ">>> BaseA "<<basea<<"\n"; }
};

class BaseB {
private:
	int baseb;
public:
	BaseB(int a): baseb(a) {}
	virtual void display() { cout <<">>> BaseB "<<baseb<<"\n";}
};

// We want a list of A's and B's.  The defining characteristic of what
// is on the list is that methods display and foo apply to it.  So define
// a class with those properties.  There are also lists of things which just
// have foo applied to them.  So

class Fooable {
public:
	virtual void foo() = 0;
};

class FooDisplayable: public Fooable {
public:
	virtual void display() = 0;
	virtual void foo() = 0; // Sun C++ 2.0 requires this redeclaration
};
// This typedef defines FooDisplayable_mfcn_ptr as a ptr to a member fcn of
// FooDisplayable which takes no arguments and returns void.
typedef void (FooDisplayable::*FooDisplayable_mfcn_ptr)();
typedef void (Fooable::*Fooable_mfcn_ptr)();

// Now for the lists.  This would be a template, except that my compiler
// does not yet support templates.  So I'll make it template-like.  Also,
// the list element class ought to be nested.

// We have lists of Fooable things and FooDisplayable things

#define ELEMENT_TYPE Fooable
#define List(E_TYPE) List_of_Fooable
#define Listel(E_TYPE) Listel_of_Fooable
#define ListIter(E_TYPE) ListIter_of_Fooable
// If ## worked in the preprocessor, I'd do the above as
// #define List(E_TYPE) List_of ## E_TYPE
// but since that is not implemented, we'll have to do it by hand

class Listel(ELEMENT_TYPE) {
	friend class List(ELEMENT_TYPE);
	friend class ListIter(ELEMENT_TYPE);
	friend List(ELEMENT_TYPE) operator + (List(ELEMENT_TYPE) ,
							 List(ELEMENT_TYPE) ) ;
private:
	Listel(ELEMENT_TYPE) * next;
	ELEMENT_TYPE *	        valuep;

	Listel(ELEMENT_TYPE)(Listel(ELEMENT_TYPE)* ptr, ELEMENT_TYPE* v):
			next(ptr), valuep(v) {}
};

class List(ELEMENT_TYPE) {
	friend class Listel(ELEMENT_TYPE);
	friend class ListIter(ELEMENT_TYPE);
	friend List(ELEMENT_TYPE) operator + (List(ELEMENT_TYPE) ,
							 List(ELEMENT_TYPE) ) ;
private:
	Listel(ELEMENT_TYPE) *ptr;
public:
	List(ELEMENT_TYPE)(): ptr(0) {}
	List(ELEMENT_TYPE)(Listel(ELEMENT_TYPE)* p): ptr(p) {} 
	virtual void push(ELEMENT_TYPE* v) { ptr = new Listel(ELEMENT_TYPE)(ptr,v); }

	// Could do a parallel thing for non-member functions as well,
	// but I'll just write it for member functions:

	virtual void doit(Fooable_mfcn_ptr f) {
		Listel(ELEMENT_TYPE)* p;
		p = ptr;
		while (p!=0) {
			(p->valuep->*f)();
			p=p->next;
		}
	}

	friend void operator>> (Fooable_mfcn_ptr f,List(ELEMENT_TYPE) l)
		{ l.doit(f); } // niftier syntax
};

class ListIter(ELEMENT_TYPE) {
private:
	Listel(ELEMENT_TYPE) * pos;
public:
	ListIter(ELEMENT_TYPE)(List(ELEMENT_TYPE) list): pos(list.ptr) {}
	virtual void operator++() { if (pos != 0) pos = pos->next;}
	virtual ELEMENT_TYPE* value() { return pos->valuep;}
	virtual int	atend() { return (pos==0); }
};

List(ELEMENT_TYPE) operator + (List(ELEMENT_TYPE) a, List(ELEMENT_TYPE) b) {
		// a real implementation would probably need to
		// make copies of a and b, but I won't bother
	Listel(ELEMENT_TYPE)* p;
	p = a.ptr;
	while (p->next != 0) p = p->next;
	p->next = b.ptr;
	return List(ELEMENT_TYPE)(a.ptr);
}

#undef ELEMENT_TYPE
#undef List
#undef Listel
#undef ListIter

// Reuse the same template for a list of FooDisplayables
#define ELEMENT_TYPE FooDisplayable
#define List(E_TYPE) List_of_FooDisplayable
#define Listel(E_TYPE) Listel_of_FooDisplayable
#define ListIter(E_TYPE) ListIter_of_FooDisplayable

class Listel(ELEMENT_TYPE) {
	friend class List(ELEMENT_TYPE);
	friend class ListIter(ELEMENT_TYPE);
	friend List(ELEMENT_TYPE) operator + (List(ELEMENT_TYPE) ,
							 List(ELEMENT_TYPE) ) ;
private:
	Listel(ELEMENT_TYPE) * next;
	ELEMENT_TYPE *	        valuep;

	Listel(ELEMENT_TYPE)(Listel(ELEMENT_TYPE)* ptr, ELEMENT_TYPE* v):
			next(ptr), valuep(v) {}
};

class List(ELEMENT_TYPE) {
	friend class Listel(ELEMENT_TYPE);
	friend class ListIter(ELEMENT_TYPE);
	friend List(ELEMENT_TYPE) operator + (List(ELEMENT_TYPE) ,
							 List(ELEMENT_TYPE) ) ;
private:
	Listel(ELEMENT_TYPE) *ptr;
public:
	List(ELEMENT_TYPE)(): ptr(0) {}
	List(ELEMENT_TYPE)(Listel(ELEMENT_TYPE)* p): ptr(p) {} 
	virtual void push(ELEMENT_TYPE* v) { ptr = new Listel(ELEMENT_TYPE)(ptr,v); }

	// Could do a parallel thing for non-member functions as well,
	// but I'll just write it for member functions:

	virtual void doit(FooDisplayable_mfcn_ptr f) {
		Listel(ELEMENT_TYPE)* p;
		p = ptr;
		while (p!=0) {
			(p->valuep->*f)();
			p=p->next;
		}
	}

	friend void operator>> (FooDisplayable_mfcn_ptr f,List(ELEMENT_TYPE) l)
		{ l.doit(f); } // niftier syntax
};

class ListIter(ELEMENT_TYPE) {
private:
	Listel(ELEMENT_TYPE) * pos;
public:
	ListIter(ELEMENT_TYPE)(List(ELEMENT_TYPE) list): pos(list.ptr) {}
	virtual void operator++() { if (pos != 0) pos = pos->next;}
	virtual ELEMENT_TYPE* value() { return pos->valuep;}
	virtual int	atend() { return (pos==0); }
};

List(ELEMENT_TYPE) operator + (List(ELEMENT_TYPE) a, List(ELEMENT_TYPE) b) {
		// a real implementation would probably need to
		// make copies of a and b, but I won't bother
	Listel(ELEMENT_TYPE)* p;
	p = a.ptr;
	while (p->next != 0) p = p->next;
	p->next = b.ptr;
	return List(ELEMENT_TYPE)(a.ptr);
}

#undef ELEMENT_TYPE
#undef List
#undef Listel
#undef ListIter

// Now for classes A and B
// The only change made to these classes over what they would have been
// is the addition of the inheritance from FooDisplayable

class A: public BaseA, public FooDisplayable {
private:
	int	inta;
public:
	A(int a): BaseA(a+100), inta(a) {}
	virtual void display() {cout<<"class A "<<inta<<"\n"; BaseA::display();}
	virtual void foo() { cout <<"foo in class A "<<inta<<"\n"; }
};

class B: public BaseB, public FooDisplayable {
private:
	int	intb;
public:
	B(int b): BaseB(b+1000), intb(b) {}
	virtual void display() {cout<<"class B "<<intb<<"\n"; BaseB::display();}
	virtual void foo() { cout <<"foo in class B "<<intb<<"\n"; }
};


// Now the program to use all this.

//	This routine does foo on every other element of the list
void someProc(List_of_Fooable& list) {
	ListIter_of_Fooable iter(list); // would be ListIter<Fooable>
	int	i = 0;
	Fooable_mfcn_ptr f = &Fooable::foo;
	Fooable* v;

	while (! iter.atend()) {
		i=1-i; 
		if (i==0) { v=iter.value(); (v->*f)(); }
		iter++;
	}
}

main()
{
	List_of_FooDisplayable listA,listB,listC; // would be List<FooDisplayable>

	// put together some A's

	int i;
	for (i=0; i<3; i++) listA.push(new A(i));

	// put together a list of B's

	for (i=10; i<14; i++) listB.push(new B(i));

	// concatenate the lists

	listC = listA + listB;

	// apply operations to the list

	// someProc(listC);  // Whoops!!! see discussion below
	someProc(*(List_of_Fooable *)&listC); //this works but is an unsafe cast

	listC.doit(&FooDisplayable::display);
	&FooDisplayable::foo >> listC ; // alternate syntax

}		

There are two parts to this problem.  

PART 1:

The first problem is having classes A and B
which have some common behavior and making a list of things which have that
shared behavior.  This was fairly easily accomplished by the multiple
inheritance mechanism used above in the example:  Declare a class with the
requisite virtual functions, declare lists of such classes, and make sure that
classes A and B are inherited from these classes (as well as whatever 
inheritance they already had).  If a programmer did not
have source code access to A and B, one could still create classes MyA (MyB) 
which inherited from both A (B) and FooDisplayable.  The programmer would have 
to use MyA and MyB everywhere instead of A and B (at least where things might 
be put on the list) and A and B would have had to declare display and foo 
virtual.

What was the cost of having static typing?
Assuming that the List stuff was in a library, and classes A and B
were needed anyway, the only cost to wanting to reuse the List code for this
special list was adding the class FooDisplayable and adding the multiple
inheritance into each class which needs to be in the list.  What did it buy
us?  Knowing at compile time that nothing was inadvertently added to the list
which would not know about foo or display.  In this case I'll take the static
typing direction.

Although the solution above works fine, I myself would prefer one like the one
given that did not require source code access to A and B.  It is possible to
do that within the context of a statically typed language like C++ since the
compiler can check wherever some T* (for some class T) is being used where
a FooDisplayable* is wanted whether T has methods foo and display, but I'd
better continue that discussion in comp.lang.c++ .  

PART 2:

The second problem, which I do not have a solution to, is that in the context
of the program above, a List_of_FooDisplayable is not a List_of_Fooable
(so the commented out call of someProc does not typecheck without casting), 
although semantically anything that can be done to the latter can be done to 
the former.  The simple expedient of adding List_of_Fooable as a base class to
the definition of List_of_FooDisplayable will let the program typecheck (as well
as removing the possibility of a template), but it then will not work.  One may
not be able to answer the question of when a X* can be used for a Y* for 
general classes, but the question restricted to generic types might be more 
relevant and answerable:

	Given  that  X* is a Y*  (X is derived from Y)
	and a template class List,
	when may a List<X> be used in place of a List<Y>?

I'd be interested in discussion or literature references (or pointers!) on this.

By the way, I used a List of Fooables in the program above rather than a list
of Footypes as suggested in the problem statement.  Consider this situation:
	Footype has member foo and other things
	someProc takes an argument of list of Footype and does (only) foo to it
	someProc is called with a List_of_Displayable
As the original poster pointed out, this will not give any runtime message
errors in a dynamically typed system.  However, I'd maintain that it is a bad
use of dynamic typing.  The only thing that prevents errors is the semantic
knowledge that someProc only does foo and not anything else that Footype allows.
If someProc were modified later by someone who did not know that it was applied
to a FooDisplayable list, errors would result.  By making the list element type
Fooable, one captures the type requirement that only foo is applied to elements
of this list, and makes the resulting design somewhat more modular.  The 
remaining problem is then the one of the last paragraph,
namely that the type system is not sophisticated enough to know that there is
an obvious implicit conversion from List<FooDisplayable> to List<Fooable>. 

David R. Cok
Eastman Kodak Company
cok@Kodak.COM

>>>>> Compiling takes too long. I want runtime syntax checking! <<<<<