9.3 Inductive Data Types

An inductive data type is an aggregate data type that refers to itself. In other words, the type being defined is one of the constituent types of the type being defined. A node in a singly linked list is a classical example of an inductive data type. The node contains some value and a pointer to the next node, which is also of the same node type:

Technically, this example type is not an inductive data type because the type being defined (struct node_tag) is not a member of itself. Rather, this type contains a pointer to a value of its type (struct node_tag*). This discrepancy highlights a key difference between a compiled language and an interpreted language. C is a compiled language, so, when the compiler encounters the preceding code, it must generate low-level code that allocates enough memory to store a value of type struct node_tag. To determine the number of bytes to allocate, the compiler must sum the constituent parts. An int is four bytes and a pointer (to any type) is also four bytes. Therefore, the compiler generates code to allocate eight bytes. Had the compiler encountered the following definition, which is a pure inductive data type because a struct node_tag contains a field of type struct node_tag, it would have no way of determining statically (i.e., before run-time) how much memory to allocate for the variable head:

While the recursion must end somewhere (because the memory of a computer is finite), there is no way for the compiler to know in advance how much memory is required. C, and other compiled languages, address this problem by using pointers, which are always a consistent size irrespective of the size of the data to which they point. In contrast, interpreted languages do not encounter this problem because an interpreter only operates at run-time—a point at which the size of data type is known or can be grown or shrunk. Moreover, in some languages, including Scheme, all denoted values are references to literal values, and references are implicitly dereferenced when used. A denoted value is the value to which a variable refers. For instance, if x = 1, the denotation of x is the value 1. In Scheme, since all denoted values are references to literal values, the denotation of x is a reference to the value 1. The following C program demonstrates that in C all denoted values are not references, and includes an example of explicit pointer dereferencing (line 15):

We cannot write an equivalent Scheme program. Since all denoted values are references in Scheme, it is not possible to distinguish between a denoted value that is a literal and a denoted value that is a reference:

Similarly, in Java, all denoted values except primitive types are references. In other words, in Java, unlike in C++, it is not possible to refer to an object literally. All objects must be accessed through a reference. However, since Java, like Scheme, also has implicit dereferencing, the fact that all objects are accessed through a reference is transparent to the programmer. Therefore, languages such as Java and Scheme enjoy the efficiency of manipulating memory through references (which is fast) while shielding the programmer from the low-level details of (manipulating) memory, which are requisite in C and C++. For instance, consider the following two equivalent programs—the first in C++ and the second in Java:

This C++ program demonstrates accessing an object through a non-pointer value (i.e., directly through itself; line 25), through a pointer with implicit dereferencing (line 29), and through a pointer with explicit dereferencing (line 34). Now consider the same program written in Java:

This Java program demonstrates object access through a pointer with implicit dereferencing (lines 18 and 20). In short, it is natural to create pure inductive data types in languages where all denoted values are references (e.g., Scheme and Java for all non-primitives).