21 May 2023

Protel, the The PRocedure Oriented Type Enforcing Language, and the operating system SOS (for the Digital Multiplex Switch, DSM-100) that was built with it, give us an interesting snapshot of the early history of software engineering (as opposed to programming, and as opposed to computing science: programming integrated over time). Naturally, my focus is on the safety affordances of the language, but the Nortel engineers had a whole lot of modern design going on.

The language was in use starting in 1975, so it’s almost as old as C, and also used for systems programming. It’s a familiar ALGOL derivative. The official papers I could find (so far) are short and serve only to tantalize:

• Protel: a high level language for telephony by Foxall, Joliat, Kamel, and Miceli, 1979
• Experience With A Modular Typed Language: Protel by Cashin, Joliat, Kamel, and Lasker (local copy), 1981

I also found some useful reminiscences from a former Nortel engineer, Frazer Clement:

• Protel I
• Protel II
• What Is SOS?
• What Is SOS? Part II
• What Is SOS? Part III

There are more (offline, sadly) citations at The York University Computer Museum. Searching the web for some of the citations can get you closer, but the holy grails that I haven’t found yet are H. Johnson, “PROTEL: A programming Language for Large Real-Time Applications” (1984); and Protel Technical Notes, BNR, Language Development Group; issues: vol. 1, nr. 1 – 7, 1980.

The broad view these sources provide of Protel and SOS is of a type-checked and spatially memory-safe systems programming language, compiled into dynamically linkable and swappable shared objects, which all run as real-time, pre-emptively scheduled threads in a single shared address space.

The systems ran with volatile storage as their primary storage, rather than treating volatile storage as a fast cache for non-volatile storage. Instead, production systems had redundant power supplies and battery-backed power, and used an explicit delineation of memory types for reliability and recovery. Certain memories were explicitly temporary, while others would be restored from disk or tape only in escalated outages. See Clement, especially “Multiple memory types”.

Protel’s type system was somewhat richer than C; from Foxall, et al.:

TYPE digit-value, terminal-id {0 TO 9}
    status_condition {busy, idle, blocked, ready},
    out_of_service BOOL,
    protocol_ptr PTR TO status_condition;

TYPE digit_register TABLE [0 TO 19] OF digit_value,
    special_feature SET {abbreviated_dial, add_on,
                  call_transfer, do_not_disturb},
    time_interval
       STRUCT
          amount {0 TO 255},
          unit {ten_ms, secs, mins, hours}
       ENDSTRUCT;

I find ranged integers notable; even now, we have to roll our own, but I suspect their ergonomic definition could have prevented many bugs.

Foxall, et al. describe descriptors:

A descriptor consists of two parts: a descriptor part and a table part. The descriptor part contains the table element count, the size of these elements, and a pointer to the base of the table part. The table part contains the elements of the current array. At execution time a descriptor may be made to point at any table of the correct type. This results in modification of the element count and pointer fields of the descriptor part.

The area type seems to provide a form of abstract class inheritance via C-union-like structured type punning:

TYPE daddy AREA (6 * byte-width)
   i integer
ENDAREA;

TYPE son AREA REFINES daddy
   t TABLE [0 TO 15] OF BOOL
ENDAREA;

TYPE daughter AREA REFINES daddy
   j integer,
   k BOOL
ENDAREA;

I don’t see discussion of down-casting safety with areas, though. As for C unions and C++ without RTTI, areas may be unsafe.

Protel also had function types:

TYPE get_channel PROC (terminal terminal_id)
     RETURNS integer;
TYPE transfer PROC (REF t time_interval,
     UPDATES feature_table DESC OF BOOL);

Early Modern Engineering

Although that method of operation is different from what we use now, we can see from these sources that Protel, SOS, and the DSM-100 embodied very early forms of what we now consider a baseline for modern software engineering and site reliability engineering culture. Some examples:

• A complete suite of language support tooling (the Protel Library System, PLS and PLS-II), including a source code control system (SCCS)/software configuration management system (SCM). From Cashin, et al.:

  In a production environment, however, the need for parallel support of both old and new software is a fact of life. Therefore, a successor, PLS-II, was designed to simplify the handling of multiple versions of both source code and system structure. A tool called source manager, similar in spirit to SCCS [DHM 78], is used to simplify maintenance and reduce storage for nearly identical source versions. Compatible lineups of system versions are maintained in the PLS database which refers to the named issues kept by source manager.

• Recognition of interfaces as executable, enforceable documentation and automated discovery of dependencies at compile- and run-time (Cashin, et al., “Interfaces as Documentation”).

• Technical structures aligned with social structures (“Modularity as a Project Manager’s Tool”, Cashin et al.). This is perhaps more arguable and more fluid, now.

• Recognition of the need to ‘shift bugs left’, preferably discovering them during type-checking (Cashin, et al.):

  By performing strict type checking on intermodule references, we have found that many of the errors which, in other languages, would have been detected at run time are flagged by the compiler. This permits easy repair early in the development process when bugs can be fixed cheaply.

• The familiar pain of long compilation times, exacerbated by thorough type checking, in section “Building Systems”, Cashin et al. But: “We feel that the difficulty inherent in this process is preferable to the mammoth debugging sessions which are required when analogous changes are made to programs written in more loosely typed languages.”

• Access control enforced by the type system (as seen in the JVM and the .NET CLR, for example) (Cashin, et al.):

  We have found multiple interfaces to be an extremely useful concept. They allow the separation of module functions by user. Thus, functions intended for general users may be separated from those intended for more ‘privileged’ users. For example, a file system may have a general user interface which supports operations such as OPEN, CLOSE, GET and PUT. A second, more privileged, interface may support operations which are only used by maintenance and audit software.

• Dynamic configuration via function pointers (which Cashin, et al. call “procedure variables”; see “Modularity as a Tool for Flexible Configuration”). This includes the possibility of selecting implementations at run-time:

  Since interface specifications allow a clear distinction between what a module provides and how it provides it, it is possible to design a single interface and several implementations for the same module. Any of these implementations can then be used transparently in different system configurations.

• Recognition of the complexity of dependency management, even in purely 1st-party codebases (see “Type Transitivity” in Cashin, et al.).

• An early form of semantic versioning. From “Configuration Control” in Cashin, et al.:

  A version code consists of two parts: A major number that is incremented when non-upwards compatible changes are made and a minor number incremented when upwards compatible changes are made. Many, but by no means all, interface changes are upwards compatible. The check used for consistency is as follows: when a module is loaded, the major number of each module in its USES list is compared with that of the version of the module already existing in the system. If they are not equal, the configuration is inconsistent. If they are, then compare the minor numbers. If the minor number in the USES list is greater than that of an existing module then it is possible that the module to be loaded relies on features not yet implemented in the existing module and the configuration is inconsistent.

• Early understanding of Hyrum’s Law. From Cashin, et al.: “Although implementation sections are hidden from the outside world, there is a fundamental problem in ensuring that an implementation change has not altered the semantics of the interface, even when there is no direct change to the interface itself. The detailed implications of changes to all users requires careful consideration which is not encouraged by the knowledge that most changes really are well hidden and do not compromise system integrity.”

• The DESC (“descriptor”) type was what we now call span or slice: A pointer to a (sub-)region of elements, together with the number of elements in that (sub-)region. This provided spatial safety — the bounds were checked. They also recognized that built-in mechanisms for safety can yield efficiency improvements. From Clement:

  A Protel DESCriptor is used to refer to a range of elements in an array of <type>. It is used in the same way [as] an array — with a subs[c]ript as an lvalue or rvalue to an expression (though the usual meaning of those terms is confused by the Gozinta operator!). The compiler is aware of the of the slice being DESCribed, and by inference the size of the elements. In the storage allocated to the DESC itself, it stores a pointer to the zeroth element and an upperbound in terms of elements. In this way it can provide bounds checking on accesses through the DESC. When an out-of-bounds exception is hit, the actual upperbound and the supplied subscript are available in the exception report, often allowing debugging straight from the trace. The array slice abstraction can be a nice way to deal with zero-copy in a protocol stack.

  Thus it would seem that Canadian telecommunications systems programming language designers were, as usual, more polite than their cousins a little to the south.

• An A/B update scheme not entirely unlike what we now use in e.g. Android and ChromiumOS; see the “One Night(mare) Process” in Clement.

Musings

I used to think (and so did the designers of Microsoft’s Singularity operating system, so at least I was in good company) that language safety could obviate protected memory (as mediated by a privileged supervisor). Clearly, the SOS designers were hoping for that, too, and like the Singularity designers they really wanted to get rid of the over head of context switching and virtual memory. (The overhead is amazingly high! We’ve just come to accept it as normal, which really puts micro-performance concerns into perspective.)

Similarly, it’s obvious (even to me) now that memory protection alone can never suffice: untrustworthy programs can call and corrupt a program even from outside its protection zone (and even, of course, from other machines entirely). Add to that side-channels and the practical difficulty of maximally reducing the privilege of programs in real-world systems, and you have a recipe for sadness.

Having no memory protection does make language safety paramount — clearly, we must have at least one of language safety and protected memory. But we also know that there will always be unavoidable zones of language un-safety, even if they are few and small. (Although it’s worth noting that, according to Foxall, et al., “Furthermore, it was decided that PROTEL should be the only implementation language — no assembly language was provided for DMS-100.”) In the end, even Singularity had to provide virtual memory protection. I do think, though, that strong language safety provides trustworthiness that can allow us to reduce the proliferation of memory protected address spaces, and hence to regain some efficiency.

Here’s a simple example of scripting in the DSM-100 shell — it was still in use at least as late as 2012:

And, finally, your moment of Zen (Cashin, et al.):

Rather than increasing complexity by allowing module nesting as in ADA, our experience leads us to believe that even our current structure may be more complex than necessary. Instead, it may be sufficient to have a structure consisting of a linear chain of interface sections and a single implementation section. This would increase the efficiency of the support system since symbolic information would no longer need to be placed in implementation section object files thus eliminating the need for a linker.