Composition of Small Languages: Rethinking an "Operating System" for the Edge

Abstract#

This research project intends to identify novel expressive composition primitives that dissolve the divide between middleware and operating system in pervasive information infrastructures, with a focus on resilience – especially security, usability, and adaptive evolvability – and expressiveness through the stacking of dynamic domain-specific languages.

Context#

With advances in hardware enabling increasingly sophisticated software, devices considered embedded now commonly run UNIX-like operating systems. Current software engineering methods reasonably allow for design, implementation, and operation of dependable systems, albeit at high cost when sufficient guarantees are required.

Problem#

Software today is bloated. Our stack is cheap, fast, and full of features. It is also full of cruft, vulnerabilities, and we barely understand the innards anymore. With increasing need to operate at massive horizontal scale over unreliable and hostile networks, while satisfying ever higher user requirements and cost pressure to deliver more features in less time, the resulting emergent nature of such systems causes a significant drop in dependability and security [1].

Flaws in underlying abstractions and tools are papered over with more of the same. Gradually, the production and nurturing of the entire stack turns into an end itself instead a of a means toward an end [2].

Such complexity begets permanent faults, as they were embedded at design time. Because of the gradual change in responsibilities and shifting context of layers, the complexity incurred by performance optimizations which had been necessary on previous hardware now stands in the way. Common systems programming languages are focused on machine performance while lacking in safety and expressive power needed to describe the behavior of pervasive systems: prevalent mutable state together with its distribution over unreliable networks, weak language support for explicit consistency vs. availability decisions, and little ability to accommodate changes especially at runtime hinder prevention and tolerance of faults.

Relevance#

We need novel specification and design methods which focus on dependability and resilience aspects of large scale distributed systems, especially to prevent human-made fault classes that occur during development, and to securely deal with malicious faults at runtime. Such systems need to be late-bound, evolvable, and adaptive to enable maintenance and repairs at runtime, and they cannot separate the concept of dependability from security [3].

Alan Kay's research group led one exceptional project with the goal of creating a minimal and understandable personal computing environment in less than 20,000 lines of code: STEPS [4, 5] bootstraps, from bare metal, an operating system with support for vector graphics, sound, networking, a full user space including universal document editing capabilities and a hypertext browser. Contrast their achievement to the tens of millions of lines of code [6] that comprise just the kernel of common operating systems today.

The proposed endeavor is a rendition of similar ideas, albeit much simpler [7] and with a different focus as the system's intended placement on embedded devices does not require graphics or document authoring capabilities. The entire stack may benefit from removing accumulated complexity throughout the layers.

Goals#

The grand vision is to rethink the basic concepts of computing and programming for a world of distributed and embedded systems. Expressiveness, dynamism, and security are favored over performance or machine optimizations.

One intent is to find abstractions that reduce and avoid state wherever possible [8]. Plain data structures replace Kay's objects [9] in the small. Objects as actors passing messages and keeping state – when coupled with a mechanism for fault tolerance as seen in Erlang/OTP [10] – appear to naturally belong towards the edge of the system, i.e. as gatekeepers for peripherals [11] and to communicate with other nodes over the network. This tenet stems from the observation that objects generally do not compose as trivially as data or pure functions do [12]. Instead of coupling state with behavior while attempting to hide all of that inside an "object", the system will decidedly be built on the primacy of plain data structures, preferably immutable [13, 14], with pure functions operating on them in the small. Plain but rich data structures [15] such as maps, sets, vectors, tagged literals, and keywords as a higher-level "lowest common denominator" instead of byte streams are the system's attempt to remove barriers of cooperation between worlds of processes, nodes and languages.

The pervasive embrace of dynamic languages seems to be at odds with the state of the art in language security research, as their focus lies mostly on static typing [16], yet Laprie noticed a dissociation between resilience and stability and writes: "a system can be very resilient and still fluctuate greatly, i.e., have low stability" and that "low stability seems to introduce high resilience" [17].

The proposed ideas include a willingness to trade away performance optimizations in return for almost everything else – simplicity, security, conciseness, aesthetics, introspectability, late binding, developer ergonomics, etc. There will be no compilation and the resulting system will likely not run well on today's embedded hardware.

Questions#

Where do faults and vulnerabilities occur? What are better metrics [18] to assess security in software? How and where to slice the stack? Where to demarcate between operating system and middleware [19]? Do we even need a distinction [20]? How much of what can be removed at each layer, from the hardware up [21]? What does it take to execute an understandable specification? Can we separate meaning from optimization? How do data, state, process, and effects [22] interplay? Are there simpler primitives [23] that could collectively provide a run time system? What abstractions compose cleanly and reliably even in higher layers [24], and are abstractions even the path towards understandability [2]? In what ways can we fit an object capability security model with delegation of authority [25] within the functionality vs. safetytradeoff in order to achieve safe composition and reuse of untrusted functions? How can we keep the benefits of maximum visibility into the lower layers and the ability to quickly reconfigure late-bound parts of the underlying operating system?

Originality#

The proposed research follows the spirit of discovery which led to ambitious working systems such as STEPS [5], Mu [2] and Lisp Machines [26] while borrowing strategies from a vast body of past work.

Some of the ideas to be combined include Kay's "extreme late-binding of all things" [27] that allows gradual refinement and experimentation on a running system. Metalinguistic abstraction [28] creates a tower of interpreters [29, 30] whereby each domain-specific language [31] sits on the language below it, all of which are expressed in homoiconic forms [32]. Ultimately, the whole tower should strive to read as an executable specification, where meaning is separate from optimization [33, 8]. From Smalltalk [34] the project takes its focus on messaging [35] and combines it with mechanisms for fault tolerance [10] from Erlang/OTP [36].

Other ideas include the primacy of plain data and algebraic effects expressed as data as seen in idiomatic Clojure [15], the parsimony and composability of Forth [37], and the programmatic availability of abstractions [20], meaning there is little distinction between process and operating system [38]. The project takes its ideas on security from various work on object capabilities [39, 40], the E language [41, 42], and security models of operating systems such as Multics [43], Minix [44], and KeyKOS [45].

Method#

The proposed research will be based on iterative cycles of experimentation and construction of a minimal and understandable working system. Starting a conversation with the machine [46] and experimenting with its building blocks is supposed to lead towards the goal of identifying simpler building blocks which compose to form a useful runtime system. Having a small and understandable working model together with the ability to adaptively experiment with and evolve at runtime seems like a useful artifact to study.

References