Inheritance was invented as a performance hack

Inheritance was invented by the Simula language as a way to support intrusive lists, save memory, and simplify the garbage collector.

It's well known that inheritance was invented by Simula. The History of Programming Languages session on Simula tells us the motivations behind that invention. Let's take a look.

Simplifying the garbage collector

Simula created inheritance instead of using composition because it allowed their garbage collector to be simpler.

Simula had a simple reference counting and garbage collection implementation:

Unable to find such a [manual memory allocation] scheme providing sufficient programming flexibility, we implemented a reference count scheme, an idea borrowed from Weizenbaum (1962), and also added a "last resort" garbage collector.

Using reference counting and garbage collection is fine and good, but their GC was a little too simple:

A process could outlive its dynamic parent, i.e., the block instance containing the generating expression which gave rise to the process. As a result the process might access nonexisting data through its formal parameters. The remedy chosen was to forbid all kinds of call by name parameters to processes (including procedures, labels, and switches).

The problem is that one can pass a stack pointer as an argument to an object ("process", in Simula terminology) that will be returned and used after the stack frame is deallocated. That will make later use of that object unsafe: "the process might access nonexisting data".

With more sophisticated garbage collectors, such as the ones used in Lisp at the time, this is not an issue.

The simple GC implementation in Simula solved this problem and others by banning passing many things as arguments, including passing functions as arguments. In a sense, they removed the support for first-class functions which existed in ALGOL 60, which Simula was an extension of. Predictably, this reduced the expressivity of the language:

When writing simulation programs we had observed that processes often shared a number of common properties, both in data attributes and actions, but were structurally different in other respects so that they had to be described by separate declarations. [...] Parametrization could not provide enough flexibility, especially since parameters called by name, including procedure parameters, had been banned for processes (for good reasons, see Section 2.3.3).

As a result of the limitations of their GC, they weren't able to use "parametrization" (what we'd call composition) to customize classes. Instead, they had to invent inheritance.

Supporting intrusive lists

Simula's direct inspiration for inheritance was to simplify the usage of intrusive lists, a clever hack still used today which makes linked lists more efficient, though less flexible.

In the first version of Simula, before they invented inheritance and other OOP features, they supported a data structure called "sets", which were arbitrary linked lists of objects ("processes", in Simula terminology):

In retrospect the introduction of "multimembership" sets was a mistake. First the "sets" were really process sequences allowing multiple process occurrences, whereas simple process chains would have been more appropriate for most purposes. [...] There was an ever-present overhead in process referencing caused by the fact that all process pointers were directed through separately allocated "element" objects.

As usual for a traditional linked list, the linked list nodes (called "elements" in the quote) were separately allocated, increasing memory usage and causing memory fragmentation. In comparison, in an intrusive list, the list nodes are not separately allocated.

In later versions of Simula, they decided that a simpler data structure which didn't allow an object to be in multiple linked lists, and which didn't require inefficient "element" objects, would be better:

The element/set concepts were too clumsy as basic, general purpose mechanisms for list processing. Even for simulation modeling our experience showed that simple process pointers might be better, combined with an inherent set membership capability of processes, restricted to one set at a time.

They decided to replace their traditional linked lists with intrusive lists, which are much more memory-efficient and time-efficient than traditional linked lists.

However, intrusive lists require that the linked list node be part of the definition of the class that will be on the list. Traditional composition techniques would be insufficient for this, even if they were available in Simula. The Simula authors didn't know how they'd implement it, until:

The solution came suddenly, with the idea of "prefixing," in December 1966. We were thinking in terms of a toll booth on a bridge, with a queue of cars which were either trucks or buses. (This example reappears in Dahl and Nygaard, 1968.) A "stripped" list structure, consisting of a "set head" and a variable number of "links," had been written down, when we saw that both our problems could be solved by a mechanism for "gluing" each of the various processes (trucks, buses) on to a "link" to make each link-process pair one block instance.

[...]

Usually a new idea was subjected to rather violent attacks in order to test its strength. The prefix idea was the only exception. We immediately realized that we now had the necessary foundation for a completely new language approach.

In Simula, inheritence was called "prefixing"; a base class is a "prefix".

So the idea of inheritance originated in the idea of implementing an intrusive list by having objects inherit from the intrusive list node, the "link". In this way, intrusive lists, an otherwise complex performance hack, could be easily used.

Conclusion

It's certainly not bad to create features for performance reasons. And of course, Simula was genius in many other ways. They invented practically every part of modern OOP, not just inheritance; and their use of ubiquitous concurrency in objects is a particularly interesting feature that should be copied more.

But it's interesting that no-one today ever talks about inheritance as a performance feature. They talk about the code reuse and extensibility benefits.

Personally, for code reuse and extensibility, I prefer composition and modules.

from Hacker News https://ift.tt/3xyVvla