Channels ▼
RSS

C/C++

Comparing Object-oriented Languages

Source Code Accompanies This Article. Download It Now.


OCT93: Comparing Object-oriented Languages

Mike is executive editor for DDJ and can be contacted through the DDJ offices or on CompuServe at 76703,4057.


While many programmers proclaim C++ to be the object-oriented language of the '90s, others find the quest for the perfect language to be elusive. In fact, deciding on the right language can be downright confusing. "Pure" OO languages like Smalltalk include a rich set of reusable classes, while hybrids such as C++ force you to roll your own. Languages such as Eiffel promote (or impose) their notion of software correctness, which is supported by the syntax of the language. Some languages are compiled, others interpreted, and a couple even provide both. Additionally, many languages are adding support for concurrency and multithreading. And while most languages are general purpose, others like Drool are context-specific. In short, there's an endless choice of options and the right language largely depends upon your specific needs.

To aid in your search, DDJ invited a number of programmers to implement a simple linked-list class in their favorite language. The linked-list was chosen because it's widely used and understood, making it easier to compare how different languages, approach a given problem. This, in effect, allows the code to speak for itself. To this end, you can examine and compare approaches in C++. Smalltalk, Eiffel, Sather, Objective-C, Parasol, Beta, Turbo Pascal, C+@, Liana, Ada, and, yes, even Drool.

Specifications and Requirements

Because most traditional compiled languages bind data elements at compile time, linked-lists are usually homogenous; that is, a given list can only store elements of a single data type. Consequently, programmers are constantly rewriting linked-list code to support new and different data types, and applications must duplicate code that manages these lists. Object-oriented languages provide run-time binding (often called "late" or "dynamic binding") which allows the binding of data elements to be deferred. This feature, which allows the creation of a heterogeneous list, lets you store different object types.

We asked our participants to create a double-ended linked-list class that's capable of handling multiple object types. The class needed to include methods for creating a new list, adding a list element to the end of the list, and printing individual list elements. Of course, a full-featured linked-list class would require methods to get the next and previous elements, get the head and tail of the list, append, delete, count elements in the list, check for an empty list, and iterators to iterate over the elements in the list. DDJ contributing editor David Betz supplied the C++ version (see Listing One, page 118), which served as an admittedly less-than-scientific specification. We asked our various programmers to duplicate the functionality of Listing One, although not necessarily the program structure or even variable names. This allowed them to approach the linked-list problem in the manner natural to each language.

Since linked-lists are well-known and widely used dynamic data structures, I won't belabor Listing One's code; however, I will point out, that Listing One declares two object types, MyNumber and MyPoint. main() constructs instances of both objects and stores them in their respective lists--numbers are stored in list1 and points are placed in list2. To demonstrate that the lists are heterogeneous, main() also places points in list1 numbers in list2, and finishes off by storing list1 in list2. Finally, the lists are printed and the program terminates.

What to Look For

It was up to the individual programmer to implement the list-manager code which, of course, depends on the facilities available in a particular language. For example, Smalltalk includes an OrderedCollection class that provides most of the functionality required for this project. Therefore, the Smalltalk version in Listing Seven, page 122, merely subclasses from class OrderedCollection, and later creates a list instance, instantiates the objects, and adds them to the list. In most languages, however, containers are not a standard part of the language. This is reflected in the number of lines of code for each language.

Table 1 illustrates this point by summarizing the number of lines of code each language used in the linked-list project. It's important to keep in mind that the line count is a deceiving number since it doesn't reflect the underlying mechanisms being executed. (Not to mention that in most cases blank lines have been deleted simply to conserve space.) Facilities such as a garbage collector, exception handlers, built-in support for collections and containers (as noted above), and inheritance mechanisms all affect the line count. In the case of automatic garbage collection, for example, the compiler allocates and manages memory, which frees the programmer from worries such as orphaned pointers, memory leaks, and the like. It also results in slightly less source code since constructors (if any) are reduced to initializers and destructors go away.

Exception handlers beef up the source code a little, but the gain is worth the pain. Exceptions provide a way of dealing with a failed execution of an instruction or routine. Without an exception handler, the failure may cause the system to terminate unpredictably. In Table 1, note that, while exceptions are provided for in Stroustrup's The annotated C++ Reference Manual (often referred to as the ARM), they're still listed as "experimental" and many C++ vendors have yet to implement them.

The most dramatic affect on line count, however, is the syntax of the language. For example, the C++ version makes use of initializers in class declarations: MyListElement() includes {data = initialData;} all on a single line within the declaration. However, the Turbo Pascal version I wrote (Listing Three, page 119) initializes data within its MyListElement Init constructor. The constructor requires a minimum of four lines of code. (Note that source code compactness does not translate into fewer instructions.) I could site other example, but you get the idea.

Programming Notes

Implementing the linked-list code in Smalltalk can be done in either of two ways. The first approach is to conduct a straightforward translation of the C++ version of Smalltalk. However, an experienced Smalltalk programmer might choose an alternative approach, which is to do the minimum necessary to sat can be done in four lines of code. The test program can be satisfied by a protocol consisting of three methods: Create a list, add an element to a list, and (recursively) print the elements of a list. Most of this behavior is already available in class Ordered-Collection, one of the standard classes in Smalltalk/V. Listing Seven, page 122, which was provided by DDJ senior technical editor Ray Valdes, shows how to subclass OrderedCollection and implement the modicum of additional behavior (the printOn: method). Of course, in a real-world setting, a link-list class would require a richer protocol. This would require additional code, as would be the case in the other languages, and would probably require building on top of the from-scratch version shown in Listing Eight, page 122, rather than subclassing OrderedCollection.

Also, notice in Table 1, that we've included Ada in the linked-list project. While not object oriented, Ada is still considered to be object based. Because Ada currently doesn't support run-time binding, List_Example in Listing Thirteen (page 124) can only handle homogenous lists. According to Mike Ruf at Rational Systems, there are ways to simulate run-time polymorphism in Ada83 (see comments in Listing Thirteen). It's also worth noting that the next Ada standard is expected to support single inheritance and run-time polymorphism.

Conclusion

As you browse the listings you'll find Robert Jervis's Parasol implementation (Listing Four, page 120), Jim Fleming's C+@ implementation (Listing Five, page 120), a Liana implementation by Jack Krupansky of Base Technology (Listing Six, page 121), an Eiffel implementation by Robert Howard of Tower Technology (Listing Nine, page 122), a Sather implementation by Stephen Omohundro of ICSI (Listing Ten, page 124), a Beta implementation from Steve Mann of MADA (Listing Eleven, page 124), and David Betz's Drool (Listing Twelve, page 124). You'll also find more coverage on each of the these languages elsewhere in this issue. In addition to the C++, Turbo Pascal, Smalltalk, and Ada listings previously mentioned in this article, Stephen Asbury of Next Computer presents an Objective-C Implementation (Listing Two, page 118).

Finally, the linked-list project is not a contest to find the best object-oriented language; rather, it's a window into the soul of each language. And while the number of lines of code may not provide a realistic comparison between languages, it is how many managers gauge programmer productivity. This, in fact, may be the poorest of measures, especially when you factor in code reuse.

Table 1:


             Garbage                  Late               Exception   Lines of
             Collection  Inheritance  Binding  Compiled  Handling    Code (approx.)
C++          No          Multiple     Yes      C         Yes          85
Objective-C  No          Single       Yes      C         No          120
Turbo Pascal No          Single       Yes      C         No          140
Parasol      No          Single       Yes      C         No           75
C+@          Yes         Multiple     Yes      C         No          110
Liana        Yes         Single       Yes      I         No           33
Smalltalk    Yes         Single       Yes      I/C       No          *44
Eiffel       Yes         Multiple     Yes      **I/C     Yes         155
Sather       Yes         Multiple     Yes      I/C       Yes          80
Beta         Yes         Single       Yes      C         Yes          55
Drool        Yes         Multiple     Yes      Byte Code No           45
Ada          No          ***None      ***No    C         Yes         125

Key object-oriented features. 1=interpreted. C=compiled.
*Line count given is for the minimal implementation; full implementation is 145 lines of code. 
**Eiffel uses its "melting ICE" technology to interpret small chunks of code for testing purposes. 
***The next Ada standard is expected to support both single inheritance and run-time binding.



_COMPARING OBJECT-ORIENTED LANGUAGES_
by Michael Floyd


[LISTING ONE]


C++ Implementation by David Betz (Dr. Dobb's Journal)


#include <iostream.h>

/* any object that will appear in a list must inherit from this class */
class MyListData {
public:
    virtual void Print(void);
};
void MyListData::Print(void)
{
    cout << "No print method!\n";
}
class MyListElement {
     MyListData *data;
     MyListElement *next;
public:
     MyListElement(MyListData *initialData) { data = initialData; next = nil; }
     friend class MyList;
};
class MyList : public MyListData {
    MyListElement *head;
    MyListElement *tail;
public:
    MyList(void) { head = tail = nil; }
    void AddToList(MyListData *data);
    void Print(void);
};
void MyList::AddToList(MyListData *data)
{
    MyListElement *newElement = new MyListElement(data);
    if (head == nil)
        head = tail = newElement;
    else {
        tail->next = newElement;
        tail = newElement;
    }
}
void MyList::Print(void)
{
    MyListElement *element;
    for (element = head; element != nil; element = element->next)
    element->data->Print();
}
class MyNumber : public MyListData {
    int value;
public:
    MyNumber(int initialValue) { value = initialValue; }
    virtual void Print(void);
};
void MyNumber::Print(void)
{
    cout << "Number: " << value << "\n";
}
class MyPoint : public MyListData {
    int x;
    int y;
public:
    MyPoint(int initialX,int initialY) { x = initialX; y = initialY; }
    virtual void Print(void);
};
void MyPoint::Print(void)
{
    cout << "Point: " << x << "," << y << "\n";
}
void main(void)
{
    MyList *list1 = new MyList;
    MyList *list2 = new MyList;
    MyNumber *n1 = new MyNumber(10);
    MyNumber *n2 = new MyNumber(20);
    MyPoint *p1 = new MyPoint(2,3);
    MyPoint *p2 = new MyPoint(4,5);
    /* build the lists */
    list1->AddToList(n1);
    list1->AddToList(n2);
    list1->AddToList(p1);
    list2->AddToList(n2);    /* an object can be in more than one list    */
    list2->AddToList(p1);    /*    at the same time                       */
    list2->AddToList(p2);
    list2->AddToList(list1); /* we can even put a list into another list */
    /* print the lists */
    cout << "list1:\n";
    list1->Print();
    cout << "list2:\n";
    list2->Print();
}


[LISTING TWO]
<a name="02df_000c">

Objective-C Implementation by Stephen Asbury (Next Computer)

#import <stdio.h>
#import <objc/Object.h>/* Include the header for the Root class */

@interface LinkedListNode:Object /* declare a node class */
{
    id value;/* a node can store an object of any class as it's
value */
    id next;
}
- setValue:newValue;
- value;
- setNext:newNext;
- next;
- print;
@end
@implementation LinkedListNode /* implement the node class */
- setValue:newValue {value = newValue; return self;}
- value {return value;}
- setNext:newNext {next = newNext; return self;}
- next {return next;}
- print
{   /* In order to allow any object to be added to the list, we first check
    * to see if the value can print, if so have it print */
    if([value respondsTo:@selector(print)] == YES) [value print];
    return self;
}
@end
@interface LinkedList:Object /* declare a linked list class */
{id tail,head;}
- addObjectToList:theObject;
- print;
@end
@implementation LinkedList /* implement the linked list class */
- init /* refine the init method of the super class */
{
    self = [super init];
    tail = head = nil;
    return self;
}
- addNodeToList:newNode /* private method used only by the object */
{
    if(head == nil)
        head = tail = newNode;
    else{
        [tail setNext:newNode];
        tail = newNode;
    }
    return self;
}
- addObjectToList:theObject
{
    id newNode = [[[LinkedListNode alloc] init]
setValue:theObject];
    [self addNodeToList:newNode];
    return self;
}
- print
{
    id element;
    for(element = head;element != nil;element = [element next])
        [element print];
    return self;
}
@end
@interface MyNumber:Object /* declare a number class */
{float value;}
- initValue:(float)aValue;
- print;
@end
@implementation MyNumber /* implement the number class */
- initValue:(float)aValue
{
    self = [super init];
    value = aValue;
    return self;
}
- print {printf("Number %f\n",value); return self;}
@end

@interface Point:Object /* declare a point class */
{float X,Y;}
- initX:(float)anX y:(float)anY;
- print;
@end
@implementation Point /* implement the point class */
- initX:(float)anX y:(float)anY
{
    self = [super init];
    X = anX;
    Y = anY;
    return self;
}
- print { printf("Point %f , %f\n",X,Y); return self; }
@end
void main(void)
{
    id list1 = [[LinkedList alloc] init];
    id list2 = [[LinkedList alloc] init];
    id number1 = [[MyNumber alloc] initValue:10];
    id number2 = [[MyNumber alloc] initValue:20];
    id point1 = [[Point alloc] initX:2 y:3];
    id point2 = [[Point alloc] initX:4 y:5];
    /* Build the Lists */
    [list1 addObjectToList:number1];
    [list1 addObjectToList:number2];
    [list1 addObjectToList:point1];
    [list2 addObjectToList:number2];/* an object can be in
multiple list */
    [list2 addObjectToList:point1];
    [list2 addObjectToList:point2];
    [list2 addObjectToList:list1];/* lists can contatin lists */
    printf("List 1\n");
    [list1 print];
    printf("List 2\n");
    [list2 print];
    exit(0);
}

<a name="02df_000d"><a name="02df_000e">
[LISTING THREE]
<a name="02df_000e">

Turbo Pascal Implementation by Michael Floyd (Dr. Dobb's Journal)

Program LListObj;

Type
  PMyListData = yListData;
  MyListData = object
     procedure Print; virtual;
  end;
  PMyListElement = yListElement;
  MyListElement = object
    Data : PMyListData;
    Next : PMyListElement;
    constructor Init(initialData: PMyListData);
  end;
  PMyList = yList;
  MyList = object(MyListData)
    Head, Tail: PMyListElement;
    constructor Init;
    procedure AddToList(var Data: PMyListData);
    procedure Print; virtual;
  end;
   PMyNumber = yNumber;
   MyNumber = object(MyListData)
      Value : Integer;
      constructor Init(initialValue: Integer);
      procedure Print; virtual;
   end;
   PMyPoint = yPoint;
   MyPoint = object(MyListData)
      X, Y: Integer;
      constructor Init(initialX, initialY: Integer);
      procedure Print; virtual;
   end;
{ MyListElement Methods }
constructor MyListElement.Init(initialData: PMyListData);
begin
   data := initialData;
   next := nil;
end;
{ MyListData Methods }
procedure MyListData.Print;
begin
   writeln('No Print Method!');
end;
{ MyList Methods }
constructor MyList.Init;
begin
   Head:= nil;
   Tail:= nil;
end;
procedure MyList.AddToList(var Data: PMyListData);
var
  Added : PMyListElement;
begin
  Added := New(PMyListElement,Init(Data));
  If Head = nil then
  begin
    Head := Added;
    Tail := Added;
  end
  Else begin
    Tail^.Next := Added;
    Tail := Added;
  end;
  Added^.Next := nil;
end;
procedure MyList.Print;
var
   Current : PMyListElement;
begin
  Current := Head;
  while Current <> nil do
  begin
      Current^.Data^.Print;
      Current := Current^.Next;
  end;
end;
{ MyNumber Methods }
constructor MyNumber.Init(initialValue: Integer);
begin
   Value := initialValue;
end;
procedure MyNumber.Print;
begin
   writeln('Number: ', Value);
end;
{ MyPoint Methods }
constructor MyPoint.Init(initialX, initialY: Integer);
begin
   X := initialX;
   Y := initialY;
end;
procedure MyPoint.Print;
begin
   writeln('Point: ', X, ',',Y);
end;
{ Main }
Var
   NumList, PointList : MyList;
   Number, Coordinates: PMyListData;
   I, J               : Integer;
Begin
   with NumList do begin      { create list of numbers }
      Init;
      For I := 1 to 5 do
      begin
        Number := New(PMyNumber, Init(I));
        AddToList(Number);
      end;
      Print;
   end;
   with PointList do begin    { create list of points }
      Init;
      For I := 1 to 5 do
      begin
        J := I + 1;
        Coordinates := New(PMyPoint, Init(I,J));
        AddToList(Coordinates);
      end;
      Print;
   end;
   NumList.AddToList(Coordinates);    { Coords can be added to Number list }
   NumList.Print;
   readln;
end.

<a name="02df_000f"><a name="02df_0010">
[LISTING FOUR]
<a name="02df_0010">

Parasol Implementation by Robert Jervis


include file;
/* any object that will appear in a list must inherit from this class */
MyListData: type    { public:
Print:  dynamic () = {
    printf("No print method!\n");
    }
};
MyList: public  type inherit MyListData {
    head:   ref MyListElement;
    tail:   ref MyListElement;
    MyListElement:  type {
    public:
        data:   ref MyListData;
        next:   ref MyListElement;
    constructor:    (initialData: ref MyListData) =
                { data = initialData; next = 0; }
    };
public:
constructor:    () = { head = tail = 0; }

AddToList:  (data: ref MyListData) = {
    newElement: ref MyListElement = new MyListElement[data];
        if  (head == 0)
                head = tail = newElement;
        else    {
                tail->next = newElement;
                tail = newElement;
        }
    }
Print:  dynamic () = {
    element:    ref MyListElement;
    for (element = head; element != 0; element = element->next)
        element->data Print();
    }
};
MyNumber:   type    inherit MyListData {
    value:  int;
public:
constructor:    (initialValue: int)  = { value = initialValue; }
Print:  dynamic () = {
    printf("Number: %d\n", value);
    }
};
MyPoint:    type    inherit MyListData {
    x:  int;
    y:  int;
public:
constructor:   (initialX: int, initialY: int) = { x = initialX; y = initialY; }
Print:  dynamic () = {
    printf("Point: %d,%d\n", x, y);
    }
};
main:   entry   () =
{
    list1:  ref MyList = new MyList[];
    list2:  ref MyList = new MyList[];
    n1: ref MyNumber = new MyNumber[10];
    n2: ref MyNumber = new MyNumber[20];
    p1: ref MyPoint = new MyPoint[2,3];
    p2: ref MyPoint = new MyPoint[4,5];
        /* build the lists */
    list1 AddToList(n1);
    list1 AddToList(n2);
    list1 AddToList(p1);
    list2 AddToList(n2);    /* an object can be in more than one list */
    list2 AddToList(p1);    /*    at the same time                    */
    list2 AddToList(p2);
    list2 AddToList(list1); /* we can even put a list into another list */
        /* print the lists */
    printf("list1:\n");
    list1 Print();
    printf("list2:\n");
    list2 Print();
}

<a name="02df_0011"><a name="02df_0012">
[LISTING FIVE]
<a name="02df_0012">

C+@ Implementation by Jim Fleming (Unir Corp.)


class MyListData {
   method print
   {
       "No print method".print;
   }
}
class MyListElement {
   inherit MyListData;
   MyListData    data;
   MyListElement next;

   class method (_) new (initialData) {
           _ = create
           _.init(initialData);
   }
   method init (idata)  {
       data = idata;
       next = nil;
   }
   method (_) data {
       _ = data;
   }
   method(_) next {
       _ = next;
   }
   method linkTo (listElement) {
       next = listElement;
   }
}
class MyList {
   MyListElement head;
   MyListElement tail;

   class method (_) new {
      _ = create;
      _.init;
   }
   method init {
      head = nil;
      tail = nil;
   }
   method addToList (data) {
      var newElement;
           newElement = MyListElement.new(data);
           if(head == nil) {
              head = newElement;
              tail = head;
           }
           else{
              tail.linkTo(newElement);
              tail = newELement;
           }
     }
     method print {
        var element;
        for (element = head; element != nil; element = element.next) {
           element.data.print;
        }
     }
}
class MyNumber {
   Integer value;
   class method (_) new (initialValue) {
      _= create;
       .init (initialValue)
    }
    method init (initialValue) {
        value = initialValue;
    }
    method print  {
       ("Number: " // value // "\n").print;
    }
}
class MyPoint  {
   Integer x;
   Integer y;
   class method (_) new (initialX,initialY) {
      _= create;
      .init(initialX,initialY);
   }
   method init (initialX,initialY) {
      x = initialX;
      y = initialY;
    }
    method print {
      ("Point: "// x // "," // y // "\n").print
    }
}
/* The following can be typed directly into command shell */
list1 = Mylist.new;
list2 = Mylist.new;
n1 = Mynumber.new(10);
n2 = Mynumber.new(20);
p1 = MyPoint.new(2,3);
p2 = MyPoint.new(4,5);

list1.addToList(n1);
list1.addToList(n2);
list1.addToList(p1);
list2.addToList(n2); /* an object can be in more than one list */
list2.addToList(p1);
list2.addToList(p2);
list2.addToList(list1); /* we can even put a list into another list */
/* print the lists */
"list1;\n".print;
list1.print;
"list2;\n".print;
list2.print;


<a name="02df_0013"><a name="02df_0014">
[LISTING SIX]
<a name="02df_0014">

Liana Implementation by Jack Krupansky (Base Technology)

class  MyList : array
{
           Print
           {
                  for (int i = 0, int n = size; i < n; i++)
                       if ((any e = this [i]).isa ("MyList"))
                                e.Print();
                       else
                                cout << e.class_name+": "+e.text+"\n";
           }
};
//-------------------------------------------
void main (void)
{
        MyList  list1 =   new   MyList;
        MyList  list2 =   new   MyList;
        int     n1 =      10;
        int     n2 =      20;
        point   p1 =      new   point (2,3);
        point   p2 =      new   point (4,5);

        /* build the lists */
        list1 << n1 << n2 << p1;

        /* an obj can be in more than one lst at same time */
        list2 << n2 << p1 << p2;

        list2 << list1; /* we can even put a list into another list  */

        /* print the lists */
        cout << "\nLIST1:\n";    list1.Print;
        cout << "\nLIST2:\n";    list2.Print;
}

<a name="02df_0015"><a name="02df_0016">
[LISTING SEVEN]
<a name="02df_0016">

Minimal Smalltalk implementation by Ray Valdes (Dr. Dobb's Journal)

OrderedCollection subclass: #MyListClass
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: ''   !
!MyListClass class methods ! !
!MyListClass methods !
printOn: aStream
    " Method to display list elements, recursing if necessary "
    aStream cr; nextPutAll:  ' ',(self class name),' '; cr.
    self do: [:c | c printOn: aStream. aStream cr ].
    ^self.
!
test
    " Program to test the linked-list class "
    |
       aList1 aList2 aNumber1 aNumber2 aPoint1 aPoint2 aMsg
    |
    aList1 := MyListClass new.
    aList2 := MyListClass new.
    aNumber1 := 10.
    aNumber2 := 20.
    aPoint1 := (2 @ 3).
    aPoint2 := (4 @ 5).
    " build the lists "
    aList1 add: aNumber1; add: aNumber2; add: aPoint1.
    " an object can be in more than one list at same time "
    aList2 add: aNumber2; add: aPoint1;      add: aPoint2.
    " we can even put a list into another list "
    aList2 add: aList1.
    " print the lists "
    aList1 printOn: Transcript.
    aList2 printOn: Transcript.
! !


<a name="02df_0017"><a name="02df_0018">
[LISTING EIGHT]
<a name="02df_0018">

Complete Smalltalk/V implementation by Ray Valdes (Dr. Dobb's Journal)

"-------------------------------------------------------------"
Object subclass: #MyListClasses
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: ''    !
!MyListClasses class methods ! !
!MyListClasses methods ! !
"-------------------------------------------------------------"
MyListClasses subclass: #TestList
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: ''    !
!TestList class methods ! !
!TestList methods !
test
    " Program to test the linked-list class "
    |
       aList1 aList2 aNumber1 aNumber2 aPoint1 aPoint2
    |
    aList1   := MyList new.
    aList2   := MyList new.
    aNumber1 := MyNumber new: 10.
    aNumber2 := MyNumber new: 20.
    aPoint1  := MyPoint  new: (2 @ 3).
    aPoint2  := MyPoint  new: (4 @ 5).
    " build the lists "
    aList1 add: aNumber1; add: aNumber2; add: aPoint1.
    " an object can be in more than one list at same time "
    aList2 add: aNumber2; add: aPoint1;      add: aPoint2.
    " we can even put a list into another list "
    aList2 add: aList1.
    " print the lists "
    aList1 print.
    aList2 print! !
"------------------------------------------------------------------"
MyListClasses subclass: #MyListElement
  instanceVariableNames: 'data next'
  classVariableNames: ''
  poolDictionaries: ''    !
!MyListElement class methods !
new: someData
   ^super new initialize: someData! !
!MyListElement methods !
initialize: someData
     data := someData.
     ^self!
next
    ^next!
next: anElement
      next := anElement.
      ^self!
print
      data print.
      ^self! !
"-------------------------------------------------------------"
MyListClasses subclass: #MyListData
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: ''    !
!MyListData class methods ! !
!MyListData methods !
print
   Transcript cr; nextPutAll: 'Must override this method'; cr.
   ^self! !
"-------------------------------------------------------------"
MyListData subclass: #MyList
  instanceVariableNames: 'head tail'
  classVariableNames: ''
  poolDictionaries: ''  !
!MyList class methods ! !
!MyList methods !
add: someData
    | anElement |
    anElement := MyListElement new: someData.
    head isNil
      ifTrue:  [ head := anElement. tail := anElement ]
      ifFalse: [ tail next: anElement.  tail := anElement].
     ^self!
print
    | anElement |
    anElement := head.
    [anElement isNil]
    whileFalse: [
        anElement print.
        anElement := anElement next .
        Transcript cr.
        ].
     ^self! !
"-------------------------------------------------------------"
MyListData subclass: #MyNumber
  instanceVariableNames: 'value'
  classVariableNames: ''
  poolDictionaries: ''    !
!MyNumber class methods !
new: aValue
    ^super new initialize: aValue! !
!MyNumber methods !
initialize: aValue
     value := aValue.
     ^self!
print
    value printOn: Transcript.
    ^self! !
"-------------------------------------------------------------"
MyListData subclass: #MyPoint
  instanceVariableNames: 'point'
  classVariableNames: ''
  poolDictionaries: '' !
!MyPoint class methods !
new: aPoint
    ^super new initialize: aPoint! !
!MyPoint methods !
initialize: aPoint
    point := aPoint.
    ^self!
print
    point printOn: Transcript.
    ^self! !


<a name="02df_0019"><a name="02df_001a">
[LISTING NINE]
<a name="02df_001a">

Eiffel Implementation by Robert Howard (Tower Technology)


class DRIVER
   -- In Eiffel, the top level driver is an object, too.
inherit
   BASIC_IO
creation
   make
feature {ANY}
   make is
     -- run this test driver
      local
     list1, list2 : MY_LIST[PRINTABLE] ;
     n1, n2 : MY_NUMBER ; -- a kind of PRINTABLE
     p1, p2 : MY_POINT ;  -- also a kinf of PRINTABLE
      do
         -- create the various objects
     !!list1 ;
     !!list2 ;
     !!n1.set( 10 ) ;
     !!n2.set( 20 ) ;
     !!p1.set( 2, 3 ) ;
     !!p2.set( 4, 5 ) ;

     list1.add_to_list( n1 ) ;
     list1.add_to_list( n2 ) ;
     list1.add_to_list( p1 ) ;
     list2.add_to_list( n2 ) ; -- objects can be in more than one list
     list2.add_to_list( p1 ) ;
     list2.add_to_list( p2 ) ;
     list2.add_to_list( list1 ) ; -- list 1 is an element of list 2

     put_string( "list1:%N" ) ;
     list1.print_self ;
     put_string( "list2:%N" ) ;
     list2.print_self ;
      end -- make
end -- DRIVER
deferred class PRINTABLE
   -- insures that 'print_self' is implemented
inherit
   BASIC_IO
feature {ANY}
   print_self is
     -- print yourself
      deferred
      end -- print_self
end -- PRINTABLE
class MY_NUMBER
   -- holds and can print an integer
inherit
   PRINTABLE
creation
   set
feature {ANY}

   value : INTEGER ;
   set( new_value : INTEGER ) is
     -- set this number
      do
     value := new_value ;
      end ; -- make
   print_self is
     -- print the value
      do
     put_string( "Number: " ) ;
     put_int( value ) ;
     put_newline ;
      end ; -- print_self
end -- MY_NUMBER
class MY_POINT
   -- holds and can print an x,y pair
inherit
   PRINTABLE
creation
   set
feature {ANY}
   x, y : INTEGER ;
   set( new_x : INTEGER; new_y : INTEGER ) is
     -- set this point
      do
     x := new_x ;
     y := new_y
      end ; -- set
   print_self is
     -- print the value
      do
     put_string( "Point: " ) ;
     put_int( x ) ;
     put_char( ',' ) ;
     put_int( y ) ;
     put_newline ;
      end ; -- print_self
end -- MY_POINT
class ELEMENT[T]
   -- holds an object reference and a
   -- single link to another ELEMENT[T]
creation
   set_data
feature {LIST}
   data : T ;
   next : ELEMENT[T] ;
   set_data( new_data : T ) is
     -- set data to the new_data
      do
     data := new_data
      end ; -- set_data
   set_next( new_next : ELEMENT[T] ) is
     -- set next to the element
      do
     next := new_next

      end ; -- set_next
end -- class ELEMENT
class LIST[T]
   -- a generic linked list class
feature {ANY}
   add_to_list( data : T ) is
     -- add to the end of the list
      local
     new_element : ELEMENT[T] ;
      do
     !!new_element.set_data( data ) ;
     if head = void
      then
        head := new_element ;
     else
        tail.set_next( new_element ) ;
     end
     tail := new_element ;
      end ; -- add_to_list
feature {NONE}
   head, tail : ELEMENT[T] ;
invariant
   tail_next_is_void: tail.next = void ;
   tail_void_when_head_void: head = void implies tail = void
end -- LIST
class MY_LIST[T->PRINTABLE]
   -- A printable list which holds printable data
inherit
   LIST[T]
   PRINTABLE
feature {ANY}
   print_self is
     -- print the list elements
      local
     el : ELEMENT[T] ;
      do
     from
        el := head
     until
        el = void
     loop
        el.data.print_self
        el := el.next ;
     end ;
      end ; -- print_self
end -- MY_LIST


<a name="02df_001b"><a name="02df_001c">
[LISTING TEN]
<a name="02df_001c">

Sather Implementation by Stephen Omhundro (ICSI)

-------------------------------------------------------------------
abstract class $MY_LIST_DATA is
   -- Data that will appear in a list must inherit this class.

   print is
      -- Print the data on OUT. Should be redefined in descendants.
      #OUT + "No print routine defined!\n" end;
end;
-------------------------------------------------------------------
class MY_LIST_ELEMENT is
   -- An element of a MY_LIST.

   attr data:$MY_LIST_DATA;
   attr next:MY_LIST_ELEMENT;
end;
-------------------------------------------------------------------
class MY_LIST is
   -- A double ended linked list.
   inherit $MY_LIST_DATA;

   private head, tail:MY_LIST_ELEMENT;

   add_to_list($MY_LIST_DATA) is
      -- Append arg to the end of self.
      new_elt::=#MY_LIST_ELEMENT(data:=arg);
      if head=void then head:=new_elt
      else tail.next:=new_elt end;
      tail:=new_elt end;

   print is
      -- Print the data held in the list on OUT.
      elt::=head;
      loop while!(elt/=void); elt.data.print;
     elt:=elt.next end end;
end;
-------------------------------------------------------------------
class MY_NUMBER is
   -- An integer value that can be held in a MY_LIST.
   inherit $MY_LIST_DATA;

   attr value:INT;

   print is
      -- Print the integer value on OUT.
      #OUT + "Number: " + value + "\n" end;
end;
-------------------------------------------------------------------
class MY_POINT is
   -- A two-dimensional point that can be held in a MY_LIST.
   inherit $MY_LIST_DATA;

   attr x,y:INT;

   print is
      -- Print the point coordinates on OUT.
      #OUT + "Point: " + x + "," + y + "\n" end;
end;
-------------------------------------------------------------------
class MY_LIST_TEST is
   -- Test of MY_LIST.

   main is
      -- Add some numbers and points to lists and print them out.
      list1::=#MY_LIST; list2::=#MY_LIST;
      n1::=#MY_NUMBER(10); n2::=#MY_NUMBER(20);
      p1::=#MY_POINT(2,3); p2::=#MY_POINT(4,5);
      -- Build the lists:
      list1.add_to_list(n1); list1.add_to_list(n2);
      list1.add_to_list(p1);
      list2.add_to_list(n2);    -- An object can be in more than one list.
      list2.add_to_list(p1); list2.add_to_list(p2);
      list2.add_to_list(list1); -- Put a list in another list.
       -- Print the lists
      #OUT + "list1:\n";
      list1.print;
      #OUT + "list2:\n";
      list2.print end;
end;


<a name="02df_001d"><a name="02df_001e">
[LISTING ELEVEN]
<a name="02df_001e">

Beta Implementation by Steve Mann (MADA)

--- program:descriptor---
(#
   MyListData: (#  Print:< (# do INNER #)  #);
   MyListElement: (#   data: yListData;  next: yListElement;   #);
   MyList: MyListData (#
       head, tail: yListElement;
   AddToList: (#
       newItem: yListData
       enter newItem[]
       do  (if head[] = NONE // TRUE then
           &MyListElement[] -> head[] -> tail[];
           newItem[] -> head.data[];
          else
           &MyListElement[]-> tail.next[] -> tail[];
           newItem[] -> tail.data[];
          if);
   #);
   Print::< (#
       element: yListElement
       do head[] -> element[];
           loop    (# while::< (# do element[] <> NONE -> value #);
       do  element.data.print; element.next[] -> element[];
   #); #); #);
   MyNumber: MyListData (#
   value: @integer;
        Print::< (# do 'Number: ' -> PutText; value -> PutInt; NewLine; #);
        enter value
    #);
   MyPoint: MyListData (#
   x, y: @integer;
        Print::< (# do  'Point: ' -> PutText;   x -> PutInt;
        ', ' -> PutText;    y -> PutInt;NewLine;
     #);
     enter (x, y)
     #);
(********************** MAIN **************************)
   list1, list2: @MyList;
   n1, n2: @MyNumber;  p1, p2: @MyPoint;
do
   10 -> n1;   20 -> n2;
   (2, 3) -> p1;   (4, 5) -> p2;

   n1[] -> list1.AddToList;n2[] -> list1.AddToList;
   p1[] -> list1.AddToList;

   n2[] -> list2.AddToList;p1[] -> list2.AddToList;
   p2[] -> list2.AddToList;list1[] -> list2.AddToList;

   'list1: ' -> PutLine;   list1.Print;
   'list2: ' -> PutLine;   list2.Print;
#)


<a name="02df_001f"><a name="02df_0020">
[LISTING TWELVE]
<a name="02df_0020">

Drool Implementation by David Betz (Dr. Dobb's Journal)


(defobject MyListElement ()
  (property next nil
            data nil))
(defobject MyList ()
  (property head nil
            tail nil))
(defmethod (MyList 'AddToList data)
  (let ((newElement (clone MyListElement 'data data))
        (tail (getp self 'tail)))
    (if tail
      (setp! tail 'next newElement)
      (setp! self 'head newElement))
    (setp! self 'tail newElement)))
(defmethod (MyList 'Print)
  (let ((element (getp self 'head)))
    (while element
      ((getp element 'data) 'Print)
      (set! element (getp element 'next)))))
(defobject MyNumber ()
  (property value 0))
(defmethod (MyNumber 'Print)
  (print "Number: " (getp self 'value) "\n"))
(defobject MyPoint ()
  (property x 0
            y 0))
(defmethod (MyPoint 'Print)
  (print "Point: " (getp self 'x) "," (getp self 'y) "\n"))
(define (main)
  (let ((list1 (clone MyList))
        (list2 (clone MyList))
        (n1 (clone MyNumber 'value 10))
        (n2 (clone MyNumber 'value 20))
        (p1 (clone MyPoint 'x 2 'y 3))
        (p2 (clone MyPoint 'x 4 'y 5)))
    (list1 'AddToList n1)
    (list1 'AddToList n2)
    (list1 'AddToList p1)
    (list2 'AddToList n2)
    (list2 'AddToList p1)
    (list2 'AddToList p2)
    (list2 'AddToList list1)
    (print "list1\n")
    (list1 'Print)
    (print "list2\n")
    (list2 'Print)))


<a name="02df_0021"><a name="02df_0022">
[LISTING THIRTEEN]
<a name="02df_0022">


Ada Implementation by Mike Ruf (Rational)

-- Ada83 does not support run-time polymorphism, so only supports homogeneous
-- lists. Ada9X will run-time polymorphism. There are ways to simulate run-time
-- polymorphism in Ada83, which is discussed in: Seidewitz, Ed,
-- "Object-Oriented Programming Through Type Extension in Ada 9X," Ada
-- Letters, Volume 11, Number 2, Mar/Apr 1991, pages 86-97. Hirasuna, Michael,
-- "Using Inheritance and Polymorphism with Ada in Government Sponsored
-- Contracts", Ada Letters, Volume 12, Number 2, Mar/Apr, 1992, pp. 43-56.
-- Mike Ruf, Rational Systems
-- This package implements a singly-linked list abstraction.
--
generic
    type Element is private;
    with procedure Print (This : Element);
package Printable_List_Generic is
    type List is private;
    function New_List return List;
    -- Returns an empty list.
    procedure Append (To_List : in out List;
                      This_Element : in Element);
    -- Propagates the Storage_Error exception if it occurs.
    procedure Print (This : in List);
    -- For each element in the list, calls the Print procedure,
    -- which is supplied as a generic formal parameter.
private
    type Node;
    type Pointer is access Node;
    type Node is
        record
            Contents : Element;
            Next : Pointer := null;
        end record;
    type List is
        record
            First : Pointer := null;
            Last : Pointer := null;
        end record;
end Printable_List_Generic;
package body Printable_List_Generic is
    function New_List return List is
    begin
        return (List'(First => null, Last => null));
    end New_List;
    procedure Append (To_List : in out List;
                      This_Element : in Element) is
       New_Node : Pointer := new Node'(Contents => This_Element, Next => null);
       -- The "next" component of the last node is always "null"
    begin
        if To_List.First = null then
            To_List.First := New_Node;
            To_List.Last := New_Node;
        else
            To_List.Last.Next := New_Node;
            To_List.Last := New_Node;
        end if;
    end Append;
    procedure Print (This : in List) is
        Current : Pointer := This.First;
    begin
        while (not (Current = null)) loop
            Print (Current.Contents);
            Current := Current.Next;
        end loop;
    end Print;
end Printable_List_Generic;

package Geometry is
    type Number is new Integer;
    procedure Print (This : Number);
    type Point is
        record
            X : Number := 0;
            Y : Number := 0;
        end record;
    procedure Print (This : Point);
end Geometry;

package body Geometry is
    procedure Print (This : Number) is
    begin
        Text_Io.Put_Line ("Number:" & Number'Image (This));
    end Print;
    procedure Print (This : Point) is
    begin
        Text_Io.Put_Line ("Point: " & Number'Image (This.X) &
                          "," & Number'Image (This.Y));
    end Print;
end Geometry;

procedure List_Example;

with Geometry;
with Printable_List_Generic;

procedure List_Example is
    package Numbers is new Printable_List_Generic (Element => Geometry.Number,
                                                   Print => Geometry.Print);
    package Points is new Printable_List_Generic (Element => Geometry.Point,
                                                  Print => Geometry.Print);
    Number_List : Numbers.List := Numbers.New_List;
    Point_List : Points.List := Points.New_List;
    N1 : Geometry.Number := 10;
    N2 : Geometry.Number := 20;
    P1 : Geometry.Point := (2, 3);
    P2 : Geometry.Point := (4, 5);
begin
    -- Build the lists
    Numbers.Append (To_List => Number_List, This_Element => N1);
    Numbers.Append (To_List => Number_List, This_Element => N2);
    --
    Points.Append (To_List => Point_List, This_Element => P1);
    Points.Append (To_List => Point_List, This_Element => P2);
    -- Print the lists
    Numbers.Print (Number_List);
    Points.Print (Point_List);
end List_Example;

------------------------------- OUTPUT  -------------------------------
Number: 10
Number: 20
Point:  2, 3
Point:  4, 5



Copyright © 1993, Dr. Dobb's Journal


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video