Hello,

I am trying to understand what exactly generics are. I read the wiki page, but there are lot's of code examples and very few explanations. Can someone explain it to me in a (relatively) simple way?

What problem is it trying to solve?

And how do generics relate to interfaces?

thanks,

Felipe Monteiro de Carvalho

I had the same problem for a few years. It took me a few months/years to first diagnose "what the fudge" templates/generics actually were, and what problem they exactly solved. All the information about generics is pretty non-real world and non-case study on the internet. It is also hyped by programmers who again seem to show no real world or case studies. But I can see how they can be useful in theory, nevertheless.

I'm not going to give you a technical explanation on what they are, because someone else can do that (and I don't have experience with generics, so I'm not qualified to do so).

Here is a vague non-technical explanation:
Basically generics helps you save some Typing and syntax in your units. You can address several things at once with the same Type. Supposedly, this encourages code reuse. You can address and create things via a shortcut syntax sort of way.

Myself, I won't be using generics any time in the next few months/year.. as I still have a lot of experience in the non-generic programming world to gain, before I even think about generics. Unless of course, I find a Delphi/freepascal unit or package that uses generics, then I will make an effort to learn generics.

Hi,

Am Dienstag, den 08.11.2005, 18:10 -0200 schrieb Felipe Monteiro de Carvalho:

It makes types parametrizable.

For example, if you write a list class, traditional delphi has TList. However, this TList can only contain TObject, no double/integer/... . Moreover, you can put objects of *differing* (i.e. unrelated) classes in the same list, which is most of the time a bad bad idea.

Excuse me for resorting to an example again, but it's just easiest to see:

1) without generics

type
  TAppleList = TList;
  TApple = class
  end;
  TOrange = class
  end;
var
  apples: TAppleList;
  apple: TApple;
begin
  apples.Add(TApple.Create); // works
  apples.Add(TOrange.Create); // works, and is stupid
  apple := apples[0]; // compile error
  apple := apples[1]; // compile error
  apple := apples[0] as TApple; // manual cast, works
  apple := apples[1] as TApple; // compiles, breaks at runtime
end;

Generic types, on the other hand, define just the TList, but do not fix the contained type in it, but leave it as a parameter to specify later.

2) with generics

type
  TListItem = generic(T) record
    Data: T;
    Next: TListItem(T);
  end;
  PListItem = ^generic(T) TListItem(T);
  TList = generic(T) class
  private
     fHead: PListItem(T);
     fTail: PListItem(T);
  published
     procedure Add(Item: T);
  end;
procedure TList.Add(Item: T);
var
  node: PListItem(T);
begin
  New(node);
  node^.Data := Item;
  node^.Next := nil;
  if Assigned(fTail) then begin
    fTail^.Next := node;
  end else begin
    fHead := node;
  end;
  fTail := node;
end;
type
  TApple = class
  end;
  TOrange = class
  end;
  TAppleList = TList(TApple);
var
  apples: TAppleList;
  apple: TApple;
begin
  apples.Add(TApple.Create); // works
  apples.Add(TOrange.Create); // compile error
  apple := apples[0]; // works
  apple := apples[1]; // not applicable
  apple := apples[0] as TApple; // works, but unneccessary
  apple := apples[1] as TApple; // not applicable
end;

And how do generics relate to interfaces?

interfaces in pascal are mostly runtime-bound.
Generics are mostly resolved at compile time.
Otherwise quite similar, with the exception that there is no "mother of everyone" class, that is, a class which is the base class of all other types, also of i.e. Integer.

i.e.
Integer = class(TAll, IUnknown);
Double = class(TAll, IUnknown);
Boolean = class(TAll, IUnknown);
TObject = class(TAll, IUnknown);
TFoo = class(TObject);

note that I'm not advertising that there should be one, just noting the facts.

The fact being, if there were one, interfaces would do the same as generics, one, interfaces do nearly the same as generics (just don't work for simple types), but still work only at runtime (at huge "cost").

Doing stuff at runtime slows the program down, and also note that the more you do at runtime, the more stuff the compiler has to compile in at each place just in case something x or y happens at runtime, at every place.
Worse, if the language is not really designed for stuff to be determined at runtime (i.e. late bound stuff), it sucks. Therefore you have to add "as TApple". Because the language just doesn't expect that you want it to automagically upcast back to what it was.

If it were a language designed for stuff to be determined at runtime too (late bound), from the line

apple := apples[0];
it would automagically generate (invisible for the programmer, but in
the executable):
  var
    temp: TObject;
  temp := apples[0];
  if apple is TApple then
    apple := temp as TApple
  else
    raise ETypeError.Create...;

that is, it would add code for "runtime type inference".

(Note that the "is TApple" and "as TApple" are the destination type of the variable "apple", i.e. the compiler still wouldn't know what type is _in_ the list, it just knows you _want_ to have an TApple. If you instead specified orange: TOrange; and accessed: orange := apples[0];, fine, it will cast to TOrange, "you asked for it, you get it")

Which would be a little better than now, but slower.

(as a side note, note the only reason why anybody bothers with type safe compiled languages is strong type checking, that is total _compile time_ strong type checking, also known as "if it compiles, it works (mostly)". If it weren't for that advantage (ok, and the speed advantage when done right), nobody would use strongly typed languages)

Generics, therefore, move the complexity into the type checker of the compiler instead, the benefit being generation of faster code, compile-time (automatically) verifyable code, but at the cost of a larger executable size.

thanks, Felipe Monteiro de Carvalho

I hope I didn't commit major blunders in the explaination, but it should be about right :)

cheers,
Danny

The Very Big Advantage (Tm), is that you get syntax checking, while still using a type diversely. That's impossible to do (at compile-time) without generics.

Probably the best example of this is something like TList:

Without generics:

TOrange = class ... end;
TApple  = class ... end;
var
  T: TList;
begin
  T := TList.Create();
  T.Add(TApple.Create());
  T.Add(TOrange.Create());
  // Whoops, what was that? Now our program might crash.
end;

Of course, we could create a specialized TAppleList that only accepts Apples, but that's boring and hard work. A much cleaner way is generics:

var
  T: TList<TApple>;
begin
  T := TList<TApple>.Create();
  T.Add(TApple.Create());
  T.Add(TOrange.Create());
  // This wont compile! The problem is prevented at compile-time!
end;

I hope that answers your question as to why it's a good idea :-)

Sort of, but I don't see why people use TApple and TOrange examples all the time ;-) I mean when was the last time you actually programmed a software application that was organizing Apples and Oranges? I use things like strings, databases, integers, FTP, CGI, stringlists, etc. Sure apples and oranges can represent a sort of metaphor for ANYTHING, but I'd prefer just to cut straight to the real world example instead.

I guess the real world examples are hard to display unless you have actually used generics in a software program, and you are willing to offer code snippets from the program.

I wish for example, I could see someone using something more real world such as:

-----BEGIN OF CASE STUDY-----
(just a fake one)

---Description---
I used generics in my FTP uploader software application and it prevented an error for me.

---Code examples---
Here are some code examples taken right from my real world ftp application written in C++. Since Pascal doesn't have generics currently, this example is in C++ only to help you see why they are useful in an existing software application.
..............
......insert code here ....
..............

---Conclusion---
My executable size is now 1400KB whereas before when not using generics it was 1340KB. The 60KB gain was not a big deal. My conclusion is that generics offer significant advantages, but they shouldn't be used in some situations.

If Pascal implements generics I estimate my executable will be about 1400KB too, and the syntax will be as follows if I was to convert my C++ application to Pascal using generics:
......
...insert code here...
.....

---Other notes:---
Generics don't work well in the following situations: A)....using a type diversely can cause issues when... .... B).....abusing generics could cause issues if you if... ... C).....generally they shouldn't be used if.... ...

-----END OF CASE STUDY-----

However, I suppose I'm idealistic and too much of a real world guy some times. Case studies can be perfect if you have software program already in existence, or if you can create a small demo program that is fully functional and actually does something real on the computer. I helps more easily prove the advantages of a certain programming. paradigm. Then there are video case studies, but I won't get in to those since those are more to do with demonstrating visual advantages of GUI's and software features.

I assume that when ever you wrote some piece of software you needed a list of something, say a list of integers and a list of objects. (at least I need them a lot)

you can solve this in various ways.

1) -------------------
you can use an instance of TList and use a lot of casting. I guess you understand this is pretty unsafe. It requires a lot of dicipline from you as programmer (and from your co coders)

example 1a (objects in a list):

list := TList.Create;
obj := TMyObject.Create;
list.add(obj);
obj := TMyObject.Create;
list.add(obj);
if you need an object form yuor list, you need
obj := TObject(List[1]); //unsafe cast.

example 1b (integers in a list):

list := TList.Create;
list.add(Pointer(someint));    //typecast needed to add
list.add(Pointer(anotherint));
if you need an integer form yuor list, you need
yourint := Integer(List[1]); //unsafe cast.

2) -------------------
To make things safer, you can create dedicated classes for them with TList as base class. Since you need specific tipes, you need to override all methods where TList uses a pointer.
This means write a wrapper for Add, Insert, IndexOf, Get, Set, etc. This means a lot of coding

TMyIntList.Add(value: Integer)
begin
   inherited Add (Pointer(Value));
end;

etc.

3) -------------------

Use generics.
Now you code your TList<T> once like (I assume some syntax here)

type
   TList<_T> is class(TObject)
     procedure Add(item: _T);
     ....
   end;

Now, when you need a list of intgers, you can declare it as

type
   TMyIntList = TList<integer>;
...
list := TMyIntList.Create;
list.Add(someInt);

or even when you need a list of TSomeObject:

type
   TMySomeObjectList = TList<TSomeObject>;
...
list := TMySomeObjectList.Create;
obj := TSomeObject.Create;
list.Add(obj);

-------
You understand now ? I only defined/coded one generic list class, and I can use it to store all kinds of types in a typesafe manner. The advantage is that I can reuse the (in this case) list code, so I only have to solve problems in one place, it reduces time, since I don't have to copy/paste/find/replace existing classes etc.

I guess the real world examples are hard to display unless you have actually used generics in a software program, and you are willing to offer code snippets from the program.

I cannot give you a real world generic example, since it doesn't exist yet for delphi. And thats where I write programs with. And yes, I've coded several similar list with all different types.

Marc

perfect!

I´m starting to like generics, specially for this:

Sounds very pascal to do compile time checkings. This increases the efficiency of the programmer, diminishing the errors.

Hello all,
I didn't discuss about this idea but now I would say something. Is it really important, to integrate templates support into compiler? Maybe an external preprocessing utility should be better? I think, an integrated complex preprocessor can slow the compiling process very much even if a source code doesn't contain these syntax extensions. Very rapid compiling was always a great pascal advantage over c++. This "improvement" can kill this advantage.

I didn't discuss about this idea but now I would say something. Is it really important, to integrate templates support into compiler?

Yes. Otherwise they are no templates.

Maybe an external preprocessing utility should be better?

IMHO this can't be done. E.g. the avoiding of multiple instantiation of the same code using the type system requires this.

I think, an integrated complex preprocessor can slow the compiling process very much even if a source code doesn't contain these syntax extensions. Very rapid compiling was always a great pascal advantage over c++. This "improvement" can kill this advantage.

An external preprocessor is a nono.

Op Wed, 9 Nov 2005, schreef Pavel V. Ozerski:

Ok, lets put it blunt. It is absolutely not important to have templates at all. We've been able to develop top class code of the best kind without templates.

There's a big risk involved with templates; code bloat. Namely, with templates, you can instantiate classes without realising that you are adding tens of kilobytes of code.

I.e. in C++ if you instantiate a vector<class_a *>, vector<class_b *>, vector<class_c *>, you have three implementations of the vector in your code, which are all an array of pointers! Surely Pascal's Tcollection/Tlist is much more efficient.

But...

Templates can save typing. People are demanding them, because there is a hype. Lack of templates is seen as a deficiency of Pascal against C++.

So we should support them.

Daniël

Daniël Mantione wrote

Ok, lets put it blunt. It is absolutely not important to have templates at all. We've been able to develop top class code of the best kind without templates.

That is true. Yet I really like the type-safety of templates. Advantages include:
- you have to type less type casts
- in an IDE like Lazarus you can directly use code completion (result of the previous item)
- less potential bugs due to storing an object of the 'wrong' class in a container

It will speed up the development process in complex applications where you need all kinds of containers all the time. And it's cool. And type casts look like hacks :) So perhaps generics can be characterized as a hype, but I think the real advatages of generics are apparent.

I also like dynamic arrays. (Note that they weren't available in FPC in the past.) They make things type-safer too.

People were asking for case studies in this thread. Well, I'm creating a report generator. This is more or less an example of the above mentioned 'complex software where you need all kinds of containers all the time'. For example:
- I'd be very happy to replace all TLists by TList<specific type>s.
- Also, adding caches (hash tables) would be a lot easier. Caches can for example prevent you from including the same resource (image, font) multiple times in the output file. Motto: No more type casts, only CTRL+Space :)

(Ok, maybe I'm exaggerating a little bit, but don't you agree generics /are/ useful?)

Won't the compiler sometimes be able to handle this smarter? When the code generated for vector<TClassA> and vector<TClassB> is equivalent, we only need to include it once in the resulting executable, right? The only thing is we have to see when this situation occurs.

Things can go wrong when for example
- an overloaded method or operator is called on T
- a method of T is called (but this is no problem when it concerns the same (virtual) method for the actual type parameters under consideration)
- class of T is used
- RTTI info is requested for T

But if I am correct, this is in general not the case for container classes like vector<T> (or: TList<T>).

Templates can save typing. People are demanding them, because there is a hype. Lack of templates is seen as a deficiency of Pascal against C++.

Somehow people from the well known ACM programming contest seem to see Pascal as a 'deficiency' itself:

From "The Rules of the 2005 ICPC Regional Contests" (http://icpc.baylor.edu/icpc/regionals/About.htm):

"The programming languages of the regional contest will include C/C++. Additional programming languages may be used. The programming languages of the 2006 World Finals are Java, C/C++, and Pascal. Prior to the World Finals, the judges will have solved all problems in Java and C/C++, but not necessarily in Pascal. Pascal is a legacy language that is provided at the World Finals as a courtesy to the teams that are still dependent on it. Pascal will no longer be available starting with the 2007 World Finals."

I think that indeed C++'s STL and Java 1.5 rule over Pascal at the moment for programming contests. Perhaps generics & a nice container library using generics can help getting Pascal back (but I don't know all the considerations of the ACM World Finals' organisers!)

Regards,

Bram

Op Wed, 9 Nov 2005, schreef Bram Kuijvenhoven:

Daniël Mantione wrote: (Ok, maybe I'm exaggerating a little bit, but don't you agree generics /are/ useful?)

Certainly I do agree. However, they *will* be used to introduce the bloated programming I described. I don't think we should be happy with that.

Won't the compiler sometimes be able to handle this smarter? When the code generated for vector<TClassA> and vector<TClassB> is equivalent, we only need to include it once in the resulting executable, right? The only thing is we have to see when this situation occurs.

These tricks have been used in some C++ compilers with very limited success. The problem is that class_a has a different virtual methods/constructors/destructors than class b, so the code to be generated for them will be different, even though they are still just basically arrays of pointers.

But if I am correct, this is in general not the case for container classes like vector<T> (or: TList<T>).

Check code generated by the C++ compiler. I did it a lot last year to reduce my binaries. Reducing the code size meant removing usage of the STL, as all vectors etc. appeared in the object code in tenfolds.

No. Pascal is not a deficient language in any way; it has way more usefull features than C++ has. What will save it is good, very good development tools and good, very good libraries.

If you think templates will save Pascal, or it will die without, that is a very naive thought. The most used language is stil standard C. Why?

Daniël

You are right, unfortunately it will be used in that way too.

If a class only uses the :=, = and  operators on the generic type, the code could be the same for all specializations for classes, or am I mistaking here? (The only problem is RTTI perhaps.)

Is there a problem with C++ that they can't use this? Or am I just overlooking something? (that is of course not unlikely) Can you give an example please?

You are right that good libraries and development tools are *very* important for the future of Pascal. Generics support is not the most important thing for that. (Though I think it is at least quite important) And you are right, Pascal definitely has some advantages over C++.

For algorithm programming contests, perhaps XML or compression libraries are not so important. Generics (and a corresponding container library) can help a lot there though. On the other hand, use for programming contests doesn't measure to what extent a language is 'alive' - e.g. PHP is a popular language, but not used at the ACM contests (ok, it is a scripting language, but still).

BTW I'd like to help writing a container library, but plan to wait for Generics support first.

Bram

Only when they are the same operations.

This is why .NET uses interfaces with these operators in. Then they only need one code instance per interface instead of per class. But they can instantiate and kill that code runtime (JIT).

Op Wed, 9 Nov 2005, schreef Bram Kuijvenhoven:

In C++ an assignment involves calling a copy constructor. If a type has no copy constructor (i.e. a struct), believe it or not, it gets a constructor automatically.

It is also possible to get automatic destructors. Don't know how, but it happens.

This means that all template methods that use assignments or new, destroy, etc. need a call to a different constructor/destructor, depending on the template type.

Important for a programming contest is the ability to build datastructures, i.e. building trees and graphs in PHP can be a challenge. Performance is bad. That is why PHP is not used.

Having some data structures readily available is an advantage, and this advantage can be implemented with templates.

However, coding in Pascal isn't , it's fast. Standard input is way more simple that Java for example. Usage of sets can save a load of memory compares to C programmers that use arrays of bytes, not to mention that memory constraint are a real punishment for Java programmers.

BTW I'd like to help writing a container library, but plan to wait for Generics support first.

It can take a while until the development version is stabilized. Not sure if that is a good idea. Enjoy FPC's new language features in the meantime; they aren't used a lot unfortunately :(

Daniël

Agreed. I have a 2000 lines unit containing type safe lists that would become 300-400 lines using Generics.

Lets first get basic things working before thinking about optimization. The whole generic thing is not as easy to implement as you can describe it in normal words.

Just my two cents worth:

To me generics should essentially make FPC a typeless language. i.e. everthing is an object and you just pass messages between objects, ala Smalltalk. How it is implemented is a moot point because at the top level you shouldn't be able to see the implementation of the objects.

The one thing that does concern me is why implement generics if you fail to implement the late binding of the objects which to me is the greatest gain of generic programming.

Feel free to shoot me down in flames as I have not been following this discussion fully to understand all of its details

John

This sounds to me more something for an Objective Pascal language mode (not really surprising, since Objective-C is largely based on Smalltalk).

Jonas

John Briggs wrote

The one thing that does concern me is why implement generics if you fail to implement the late binding of the objects which to me is the greatest gain of generic programming.

Speed.

What is "late binding" exactly ? What are you binding ?

Micha

Oops! I didn't proof read my reply ...gain of object oriented programming.

Early binding is occurs in C++; where the objects are bound at compile time. Objects in Objective C and Smalltalk have late binding as the binding occurs at runtime.

Objects in Object Pascal and FPC can be bound either early or late depending on how they are declared (virtual for late binding). (Oops takes foot out of mouth and replaces it with other foot).

Perhaps a clearer definition:
Static Objects are data typed at compile time. Early Dynamic Objects are data typed at run time. Late

John

Hi,

no, more typesafe, rather.

i.e. everthing is an object and you just pass messages between objects, ala Smalltalk.

No

How it is implemented is a moot point because at the top level you shouldn't be able to see the implementation of the objects.

Depends on what you mean by "see"

The one thing that does concern me is why implement generics if you fail to implement the late binding of the objects which to me is the greatest gain of generic programming.

Can you explain that some more?

cheers,
Danny

Micha Nelissen wrote

What is "late binding" exactly ? What are you binding ?

Late binding means that the compiler doesn't have to be able to figure out at compile time whether or not a particular object understands a particular message (aka has a method with a particular name), or where this message is located in the VMT (so if you have two independent class hierarchies which implement method FOO, you can still use obj.foo() and get the correct method called in both cases).

In case the compiler knows the type, the implementation is the same as with regular OOP languages. If it doesn't, then the method call happens via some kind of hashtable lookup with caching.

Jonas