// Workers AI · dad joke modeWhat did the flex machine say? I'm flexible.

For other uses, see Flex (disambiguation).

Not to be confused with FLEX (operating system) or FlexOS.

The Flex Computer System was developed by Michael Foster and Ian Currie of Royal Signals and Radar Establishment (RSRE) in Malvern, England, during the late 1970s and 1980s. It used a tagged storage scheme to implement a capability architecture, and was designed for the safe and efficient implementation of strongly typed procedures in high-level programming languages such as ALGOL 68 and Ada.

Description

The original Flex hardware was custom and microprogrammable, with an operating system, (modular) compiler, editor and filing system all written in ALGOL 68RS. The microcode enforced a tagged architecture to distinguish between different types of data and was described as providing "a protection structure equivalent to that of capability machines". The microcode was entirely responsible for storage allocation, deallocation and garbage collection. By tagging pointers, the microcode could make them "unforgeable" by program operations, and this immediately precluded a whole class of errors arising from the misuse (deliberate or accidental) of pointers, or from compiler bugs.

Memory was allocated in blocks of different types that supported only certain kinds of operation. Block types were divided into two principal groups: those concerned with procedures and those concerned with data. Procedures were described by closure blocks that referenced the code, non-locals and constants, and could only be invoked. Invocation would cause a workspace block to be allocated containing local variables and the evaluation stack for a procedure. Data would reside in dedicated blocks, with pointers only able to reference whole blocks without supplementary information. Individual data values would be accessed using a reference involving a pointer and an offset or displacement within a block. Elements in a vector would be accessed using a pointer and a displacement constrained by an upper bound, and array access would involve pointer, displacement, bounds and stride information. Blocks would contain metadata in the form of overhead words which, although appearing at the start of blocks in physical memory, would be invisible to code accessing these blocks whose offsets would be adjusted transparently to skip such overhead regions.

The whole scheme allowed abstract data types and for interfaces to privileged code to be safely implemented, as data items and the procedures permitted to access them could be bound together and the resulting capability passed freely around. The capability would grant access to the procedures, but could not be used in any way to obtain access to the code or data. Indeed, just as the operating system could employ such mechanisms to uphold its privilege and be protected from callers, procedures in user programs could similarly employ these mechanisms to act like an operating system to their own callers. Since such mechanisms were provided at the hardware level, as opposed to depending on code generated for any particular programming language, information hiding restrictions stipulated by languages such as Modula and Ada could not be circumvented by using code written in low-level or permissive languages, these purposefully not supporting such restrictions, to interface to high-level language code.

Memory blocks in Flex were garbage collected, with the collector implemented in microcode using a mark and sweep approach. This would scan the known live (or active) blocks for pointers, made easier by the presence of the tag bits distinguishing pointers from data words. Referenced blocks would then be marked as live and compaction would occur, situating the remaining live blocks at the start of the system's memory and updating the system's own records of block locations. A notable feature of Flex was the notion of firm and shaky pointers: the former causing blocks to be marked as live during collection, and the latter acting as a form of weak reference. Where all pointers to a given block were marked as shaky, such a block could be freed at the next garbage collection. Each of the shaky pointers involved would then be overwritten with a nil value Shaky pointers were also used, for example, for cached disc blocks or to provide a list or chain of spare procedure workspaces.

Garbage collection would suspend execution of code for approximately half a second in the second "laboratory model" implementation of the system with one megabyte of memory. It was a process whose duration was directly proportional to the size of the memory, increasing linearly with store size. On a two megabyte PERQ system, the measured time for garbage collection was, on average, between 1.1 and 1.5 seconds. An example scenario of "two long Algol68 compilations in parallel with normal text editing" would cause collection every 45 seconds or so, this recovering 1.2 megabytes of free memory on each occasion.

Flex supported four main forms of capabilities, these being mainstore, filestore, remote and universal capabilities. Filestore capabilities pointed to blocks on a storage device, with the filestore itself being perhaps most accurately described as a "persistent heap" that "simply defines memory which persists in some permanent form", as opposed to suggesting any kind of traditional filesystem structure. The filestore was a write-once medium, where data blocks could not be modified once written but only read back using a read-only capability. This allowed arbitrary code and data structures to be written and retrieved transparently, employing the same representation as in the memory or mainstore. Data could thus be passed safely from program to program. Filestore capabilities would be accessed by producing mainstore capabilities of the same type. Thus, a procedure defined in the filestore would be accessed via a conventional procedure, with any data retrieved from the filestore inaccessible to the caller.

Since the filestore provided a medium where blocks could only be added and not rewritten, a garbage collection process was required to reclaim free space. In all implementations of Flex up to and including PerqFlex, this process was performed offline and, in the PerqFlex implementation, reportedly took 20 minutes "on a single 35Mbyte Winchester disc containing about 25000 capabilities", typically only necessary once a week under normal usage. Such a process was non-compacting, but a compacting version of the process taking "marginally longer" involved sending live blocks to another filestore over the network. However, one consequence of this write-once filestore paradigm was that "a complete history of consistent states of the filestore" remained available between collections and that files could be "trivially" reset to their historical versions.

Remote capabilities allowed data and procedures on other machines to be accessed over a network connection, again without the application program being involved in external encodings of data, parameters or result values. Unlike mainstore and filestore capabilities, remote and universal capabilities required a formal protocol to be defined "using the kind of types found in strongly-typed programming languages". For this purpose, Flex employed a type description language based on the type system of ML and defined "flattening" and "unflattening" operations on the communicated data, these being equivalent to serialisation and deserialisation in more recent terminology. Issues of security and integrity were delegated to the specific lower-level protocols used for network communication. In practice, remote capabilities involved remote procedures since even access to data held remotely would involve the execution of code on the remote system to access the data.

Hardware

There were at least four incarnations of Flex implemented using hardware with writable microcode. The first employed 64-bit microinstructions. This was followed by a design employing 80-bit microinstructions built around the Am2900 bit-slice family, developed by RSRE as a "laboratory model" and then refined by Logica with the aim of producing a "reliably reproducible" prototype. A 24-bit processor word size was supported by this design, with 24-bit pointers referencing byte-addressed memory, although the unit of data transfer to memory was a 32-bit word consisting of four bytes. This word, augmented with tag and parity bits for each of its bytes, was constructed from four 10-bit memory devices. Integer arithmetic involved 24-bit values, whereas floating-point arithmetic involved 48-bit values.

Alongside these early implementations on dedicated hardware was another, targeting a microcoded machine known as GEMINI that had been developed by RSRE and Plessey Electronic Systems to emulate legacy systems in process control and other applications. This machine employed 48-bit microinstructions and was designed to support 16- and 32-bit computers. A subsequent implementation used the ICL PERQ and was known as PerqFlex. Due to the design of the PERQ, PerqFlex could not provide additional tag bits in the memory data path and thus incorporated a single tag bit within the 32-bit processor word to distinguish between pointers and non-pointers. This slightly impacted integers and floating-point numbers, but more seriously impacted the storage and access of boolean and character values, necessitating the introduction of special blocks or regions for packed boolean and character values.

Networking and communications

COMFLEX, a packet switching network capable of transmitting data at magnetic-disc speed, was developed alongside Flex. It made feasible the use of remote file-stores, remote capabilities, and remote procedure calls.

See also

• Royal Radar Establishment Automatic Computer
• Ten15
• PS-algol
• Rekursiv
• Intel iAPX 432

Further reading

• Martin C. Atkins: An Introduction to Ten15 - A personal retrospective. (includes a section about RSRE's Flex)