Week 9 - Chaps 11-12 - Generics, More on Arrays


Strongly vs. Weakly Typed Languages

When we speak of how strongly "typed" a language is, we are talking about how strict the language is with its storage classes.

Strongly Typed

This kind of language will insist that you specify what kind of data it is storing: i.e. character, integer, float, string, reference, etc. Furthermore, a variable declared to be a certain data type can only hold data of that type, you can't mix-and-match. C++, Ada, and Java are all examples of strongly-typed languages.

Weakly Typed

This kind of language is much more flexible about the data that you store in your variables. BASIC, JavaScript, and Perl are examples of weakly-typed languages. This type of language has to be a lot smarter about how it converts values from one format to another (i.e. deciding whether to concatenate or add based on the type of the variable), and will often feature a different set of functions / operators to perform operations on different data types.

Type and Generic Code

The whole type issue comes to bear when we try to write generic code that can be reused for a variety of different data structures and types. The best examples of such generic code are sorting a list and searching for items in a list.

Example: Let's say we wanted to sort an array of scalars, be they integers, floats, characters, or strings. In a weakly typed language, This wouldn't be a problem, because the same code would probably work. This hunk of JavaScript code shows this idea at work.

In a strongly typed language, you can't make this kind of generic code without some additional language feature that allows you to work around or deal with the constraints of strong typing. The above JavaScript example wouldn't work in a strong typed language because the comparison (and possibly iteration) operations would be illegal.

And in fact, as much as we might otherwise love weakly typed languages, generic code breaks down when we start doing something that operates on a non-scalar data structure like a record or have to search through a non-list structure like a tree or a graph.

So, let's look at some approaches to...

Making Reusable Code in a Strongly Typed Language

Here's the way various object-oriented languages tackle this problem:

Java uses casting. In Java, all objects decend from a single base class (named, appropriately enough 'Object'). Therefore, the data types used in ADT classes (like Vectors) are references to Object. When you store / retrieve stuff into a Java ADT, you simply cast or un-cast the thing you're storing. This is possible because there is a method in the Object class called .getClass() which will report the kind of class it is, then you can cast it.

C++ uses templates. C++ allows you to make objects that do not inherit from a common ancestor. Moreover, you can also write non-OO code in C++. Therefore, C++ uses templates to make generic routines. This works well both in theory and in practice, the STL (Standard Template Library) being a shining example of useful, reusable code.

Ada uses generics which are very similar to templates in C++. The point here is that Generics in Ada exist to help you work around some of the restrictions imposed by its strong typing language.

Ada Stuff

Unconstrained Arrays

(p. 520) Basically, when the textbook talks about an "Unconstrained Array", it is talking about an array of some pre-declared type whose dimensions can be specified when a variable of the array type is declared.

Declaration (p. 521) The "box operator" makes unconstrained arrays possible. If it helps. think of the box operator as being similar to void * in C. You've already run into this with Strings in earlier chapters (most notably, chapter 9). Examples follow. Note that the usual assignment / exceptions rules apply. Syntax Summary p. 523.

Array Attributes (p. 521) Ada arrays have attributes that can tell you thier length, upper / lower bound and range. This is the sort of thing that a good OO language should do. And yes, this works for "normal" arrays as well as unconstrained arrays as this code sample shows. Why was this valuable information not mentioned in chapter 9? I dunno, it's a mystery.

Example For a good example of how to use an unconstrained array of records, including the neat attribute stuff, look at the example program that spans from p. 521-523.

More on Slicing (p. 524) Slicing in Ada is really quite cool. Look at the line at the top of p. 524 that shows how to find the max value within just a subset of an array. Neat-o.


(p. 529) These are like templates in C++. I actually think that this is done pretty well in Ada. The sample code on p. 529 shows a case to be made for generics with the infamous "swap values" problem. Generics can be used in a wide range of situations.

Generic Type Parameters (p. 530) Take a look at p. 530-531 for an example of a generic swap procedure which takes arbitrary parameter values. Note the use of in / out modes. Now, look at the test (aka "driver") program that "instantiates" new versions of the Swap_Generic procedure. Note how you "new" a different package for doing swaps on a per-data type basis. (This is just like you learned how to do for I/O with enumerated types.)

Generic Functions (bottom of p. 532, interestingly titled "Generic Subprogram Parameters") This is basically the same as function pointers in C. Look at the type-specific "Maximum" function at the top of p. 533 and compare and contrast with the generic "Maximum" function on pages 533-534. The instantiation that follows shows how you can supply a generic function for performing an operation. The test (again, "driver") program that follows shows how you could actually make a Minimum function from the generic definition.

Generic Array Parameters (bottom of p. 535) On p. 536-537 you'll find an example of a program which finds the maximum element in an array of any type. Note the use of the box operator in two different contexts. (Remember, think "void *".) This also takes a generic function. The declaration that you need to use to "instantiate" one of these generic functions is a bit more involved (about 3/4ths of the way down p. 536).

Generic Packages Are also possible, but not discussed much in this chapter. We will probably go over them when we discuss tagged types in chapter 16.

Example Look also at the generic sort procedure that spans p. 537-543. This example brings a lot of the aforementioned principles together. This program will be useful for you in your assignment.

Syntax Summary p. 543. Summarizes lots of generic things.

Multidimensional Arrays

Declaration (p. 557) Good news: This is remarkably straightforward. See the example at the bottom of p. 557 and note that they simply put two ranges in the parentheses. Syntax Summary p. 558.

Element Access (Subscripting) (middle of p. 558) Note how they just comma-seperate the indicies to get at a particular element with TicTacToe(2,3). (The equivalent C code would be tic_tac_toe[1][2].)

Aggregate Assignment (middle of p. 560) It's a lot like aggregate assignment for a single array and it's remarkably compact and simple.

Example Look at the sample code at the top of p. 561 for an example on how to use TYPE enumerations to iterate through elements in a multidimensional array.

Variant Records

(p. 567) These are kind of similar to union structs in C. More accurately, they're like variant records in Pascal.

Declaration: Quick answer: use CASE statements in the record. Have a look at the sample code that starts at the bottom of p. 567 and continues to p. 568 for an example of how to declare a variant record. Syntax Summary p. 571-572.

Displaying a Variant Reord Sample code on p. 570 shows how to do it. More CASE statements.

The important thing to remember about variant records is that they allow you to have more flexible structures, whose exact fields can be determined at run-time. The advantage to this is that it saves memory by packing more variables into less memory. This feature was added to Ada because the language was designed (in part) for real-time or embedded systems where available memory is limited.

Note that this is not how you do "inheritance" in Ada in the traditional sense. Chapter 16 will show a slightly better way to do inheritance.

Chapter Summaries: ch 12 p. 553-554, ch 13 p. 586-587.

Assignment 8

Write a function which implements a generic searching algorithm for finding an element in an array. It should be able to take an array of variable length, holding a caller-specified value. The generic function should return an index in the array where the first element is found. Hint: Be lazy; just make a linear search, it's easiest.

Test making three different "instances" of this function for finding:

You should be able to squeeze this all into one file by having the generic function declared between the PROCEDURE and BEGIN lines. Call it assn8.adb.

I'll be looking for the use of unconstrained arrays (i.e. one declared with the <> box operator) and a generic function.

This assignment is due on October 31st, '01. The night of Exam number 2. (Happy Halloween)