Generic Programming in Other Languages

In Smalltalk, variables are typeless and values carry the types, so one data structure or subroutine can serve any type of data.

Programming

Why One Routine Can Serve Many Types

Most of the programming you have likely done so far has involved writing a routine for a particular kind of data. A routine that adds up a list of integers may not be the routine you would write for a list of dates. Generic programming asks a different question: can one piece of code serve many data types without being rewritten for each of them?

Smalltalk is a language where, according to its source material, essentially all programming is generic. It was one of the very first object-oriented languages and never reached the popularity of Java or C++, yet many of the ideas found in those languages came from it. Two features make this generality possible: variables that carry no type, and values that are all objects. This article traces how each feature works, follows a single routine through several types, and then examines what the flexibility costs.

Variables Without Types

In Smalltalk, variables are typeless and values carry the types. A data value does have a type: 42 is an integer and 'hello' is a string. But a variable is only a name that can refer to a value, and it does not carry a type of its own. Any variable can therefore hold data of any type, and the same is true of parameters.

The consequence for routines is direct. A subroutine accepts parameter values of any type, and a data structure can hold values of any type. Nothing in the name of a variable tells you whether it will hold an integer or a string tomorrow. The type belongs to the value that is currently referred to, not to the name.

In the real world

The source gives a concrete payoff. Once you have defined a binary tree data structure in Smalltalk, you can use that same tree for binary trees of integers, strings, dates, or data of any other type. There is simply no need to write new code for each data type.

Tracing One Name Across Two Values

How does one variable change what it refers to over time, and where does the type information live when the variable has no declared type?

This picture is a teaching model, not a literal account of how any particular implementation stores things. Its point is the division of labour the source describes. The name x does not change its declared type, because it has none. What changes is the value it refers to. The integer 42 carries the information that it is an integer, and the string 'hello' carries the information that it is a string. The name simply points to whichever value is current.

Worked example

Following the Type Through a Reassignment

A variable x is first given the value 42 and later given the value 'hello'. What type does x have at each moment, and what decides it?

1
Step 1: assign 42
The name x now refers to the value 42. The value is an integer, because the source says 42 is an integer.
2
Step 2: reassign to 'hello'
The name x now refers to the value 'hello'. Nothing about the name itself has to be declared or changed to allow this.
3
Step 3: ask what type x is
The answer comes from the value currently referred to, which is a string. The type was never stored on the name.

Result

x is an integer at step 1 and a string at step 3. The type is carried by the value, while the variable is only a name that can refer to any value.

Every Value Is an Object

The second feature is that all data values are objects, and all operations on objects are defined by methods in a class. The source stresses that this holds even for types that Java treats as primitive, such as integers. When the plus operator adds two integers, the work is performed by calling a method in the integer class. Other operators, such as the less-than operator, work the same way.

This is what makes operators extensible. When you define a new class, you may define a plus operator for it. From then on, objects of that class can be added by writing a plus b, just as if you were adding numbers. The meaning of the operator is supplied by whichever class the operands belong to, not by a fixed rule built into the language.

Key point

Operators are not special. Plus and less-than are supplied by the classes they belong to. A routine that uses an operator therefore works on any type for which that operator is defined, which removes the need to write a separate routine for each type.

Sending Plus to Different Receivers

Put the two features together and the payoff appears in ordinary algorithms. Suppose you write a subroutine that uses the plus operator to add up the items in a list. Because the subroutine only asks each item to respond to plus, it can be applied to a list of integers. It can also be applied, automatically, to a list of any other data type for which plus is defined.

When one subroutine calls the same operator on different values, what steps happen at run time to pick the right behavior for each type?

The diagram shows the same message, plus, going to two different receivers. The routine does not contain a branch that says if the item is an integer then do this, otherwise do that. It sends the message, and each receiver supplies the behavior from its own class. The source describes the same idea in terms of the less-than operator: a sorting routine that uses less-than works on any type for which less-than is defined, so no separate sorting routine is needed for each type.

Worked example

Summing a Mixed List

A list holds the integers 3 and 4, followed by an item from a custom class that defines its own plus. The summing routine adds all the items. What does the routine need to know about each item?

1
Step 1: take the first item
The routine asks the integer 3 to respond to plus. The integer class supplies the method, so the addition is performed by the integer class.
2
Step 2: take the next item
The routine asks the integer 4 to respond to plus in the same way, with the same code.
3
Step 3: take the custom item
The routine sends the same plus message to the custom object. The custom class supplies its own meaning for plus, and the routine does not need to change.

Result

The routine needs only one fact about each item: that it answers to plus. It does not need to know which type each item belongs to.

MEDIUM

Before reading the next section, consider the summing routine from the one above. It works for integers and for the custom class because each item answers to plus. Now imagine a list that contains an item from a class that defines no plus operator at all. Predict what the summing routine would have to rely on in order to handle that item, and what you would expect to go wrong.

Hints

Ask what the routine knows about each item before it sends the message.
Think about where the meaning of plus is supposed to come from for each item.

Your attempt (not saved)

Mistakes Beginners Make with Generic Routines

Common mistake
Believing that a variable has a fixed type
What it looks like
Assigning 42 to x and then 'hello' to x, and assuming x must still be an integer.
Why it fails
The source says variables are typeless. A variable is a name that can refer to a value of any type, and the type belongs to the value currently referred to.
Do this instead
Ask what type the current value is, not what type the name was once given.
Common mistake
Thinking the routine checks types for you
What it looks like
Expecting the summing routine to refuse a list of items it cannot add, before it runs.
Why it fails
The source says the flexibility removes the checks that would otherwise guard against misuse, and no compiler can check the types ahead of time.
Do this instead
Make sure every item actually supports the operators the routine uses, and test with realistic data.
Common mistake
Assuming an operator works on every type
What it looks like
Using plus on objects from a class that never defined plus.
Why it fails
An operator works only for types whose classes define it. The meaning of plus is supplied by the class of the operands.
Do this instead
Check that the class defines the operator before relying on it.

The Price of Flexibility

The source is direct about the downside. This freedom makes it easier to write programs, but it makes it harder to write programs that are correct and robust. The flexibility that lets one routine serve many types also removes the checks that would otherwise guard against misuse. Because no compiler can check the types ahead of time, a type mistake is not caught before the program runs. It shows up only when the program executes the operation on the wrong kind of value.

Question	Typeless language such as Smalltalk	Statically typed language
Where is the type of a value known?	On the value itself at run time	Declared or inferred ahead of time for the program
When is a wrong-type operation caught?	At run time, when the operation is attempted	Before the program runs, if the checker can see the problem
What does one routine serve?	Any type for which the operator is defined	Only the types the routine was written or declared for
What does the programmer gain?	Ease of writing and reuse across types	Earlier detection of type mistakes

The trade-off between run-time flexibility and checking before the program runs. The statically typed column describes the general contrast; the source itself only states the typeless side.

Checking Your Understanding of Types