Why Sponsor Oil? | blog | oilshell.org

A Sketch of the Biggest Idea in Software Architecture

2022-03-12 (Last updated 2022-05-25)

This post was called Backlog: Software Architecture until I edited it and saw a coherent theme emerge.

It elaborates on narrow waists: an idea in #software-architecture that relates to networking, operating systems, language design, compilers, and distributed systems.

Another title I considered is An Overview of Software Composition at Runtime. That is, you can contrast these two styles of building software out of parts:

  1. Fine-grained static types, build-time composition, static linking, APIs, and version numbers
  2. Coarse-grained "waists", runtime composition, ABIs, IPC, and versionless protocols

Many programmers are familiar with the first style. This post is about the second style, which you see at large scales and long time horizons.

This post is long and dense with links, so you may want to read it in multiple sittings. Let me know what you think in the comments! I especially welcome references to similar material.

Table of Contents
Background
Motivating Design Questions
What Is a Narrow Waist?
Precisely Defining "The Unix Philosophy"
Characteristics of Narrow Waists
Fallacies
Related Ideas
Examples and Elaboration
The Web Evolved In A Versionless Manner
Bytes and Text Are Essential Narrow Waists
Slogan: Text Is The Only Thing You Can Agree On
CSV, JSON, HTML - Tables, Records, Documents
Tradeoffs Between Dynamic and Static Types (FAQ)
Refinements
Projection to Waists
Emulation of Waists
Extension of Waists
Composition Between Waists
Addition of Waists
Hierarchy Among Waists
Call to Action
Jon Postel Made the Internet's Waist Narrow
Conclusion
Appendices
The Lambda Calculus Is a Narrow Waist
Wiki, Zulip

Background

I'm happy that there was great discussion on the last post, The Internet Was Designed With a Narrow Waist:

I wrote about abstract ideas, but readers understood and applied them. And a reader answered my question about the history of the narrow waist, which I repeat in the Call to Action below.

On the other hand, there were a few responses that exhibited exactly the misconceptions I want to push back on. In particular, the lack of consideration for tradeoffs:

To be convincing about this, I would dive into examples: show code, analyze existing designs, and propose new designs. I collected a great deal of material on the wiki and in Zulip.

But I probably shouldn't spend months writing and arguing about #software-architecture. It's better to build something with the principles I'm espousing.

So I'm squeezing many topics into this single post. I state the main points, with some justification.

Update: I want to expand the project, as mentioned in November. We now have a Github Sponsors account, and I'm waiting for a response to a NLNet grant application.

Motivating Design Questions

To be concrete, here are some questions that these ideas will help us with:

  1. Should shells have two tiers?

  2. Is JSON the new narrow waist for shell?

  3. How can we design a better distributed OS?

  4. Is Docker designed well? How could it be improved?

So I believe the ideas below are relevant to the biggest forces and developments in the industry. I'm glad that Docker is being "refactored away" into something more Unix-y on two fronts: into OCI by Red Hat and others, and out of Kubernetes. (Related: Docker's Second Death)

What Is a Narrow Waist?

Most readers understood the last post: I borrowed the narrow waist term from networking and extended it to software.

But it's become clear to me that not all narrow waists are alike. It's worth distinguishing these categories, and more:

  1. Small, simple mechanisms like the Internet Protocol, UTF-8, and JSON.
  2. Language standards like POSIX shell, JavaScript, and C++.
  3. "Accidental" waists like Win32 and x86.
  4. APIs like LLVM. As the home page says, LLVM isn't a virtual machine. It's really a software library that changes with each release, requiring consumers to change their code. This makes it different than the other narrow waists, which are more about runtime composition.
  5. ... ?

So it's worth being more specific, and the posts below will refine definitions and explore related concepts.

The clearest objection I see to the narrow waist idea is that a narrow waist is simply a standard! Standards enable interoperability.

But standards have to come from somewhere. A narrow waist may or may not become a standard. Also, LLVM is not a standard, and isn't intended to be one.

The hourglass metaphor also suggests why the idea is powerful, and what to aim for. You want something small that interfaces with many other things.

Precisely Defining "The Unix Philosophy"

I spent a week drafting a post called Diagrams of Three Narrow Waists in Unix. The first sentence is:

Have you heard vague claims about "the Unix Philosophy", and are you confused or skeptical about it?

This is a valuable post, because surprisingly the narrow waist idea says something new and more specific about Unix! I justify this with references, including the classic ones on this Wikipedia page.

I have diagrams of these 3 narrow waists:

  1. Processes
  2. File Descriptors
  3. Tree-Shaped Namespaces of unstructured data (file systems)

The diagrams show that Unix uses multiple narrow waists to achieve dynamic and extensible polymorphism.

The file descriptor case shows both sides of the tradeoff. You don't statically know what syscalls are valid on a descriptor. You also don't know what errors you'll get! I re-learned this lesson with:

Nevertheless, the polymorphic design of file descriptors makes Unix compose, and is one reason why shell is powerful! I give examples in the post.

Go addresses this problem with single function interfaces like Reader and Writer, and more generally the -er pattern. Here's an interesting quote:

It would be nice if Haskell had [open polymorphism], possibly using Go as a model.

Philip Wadler: Featherweight Go

More:

This post isn't done, but it's the one I want to publish the most.

Characteristics of Narrow Waists

In software, the most important characteristic of a narrow waist is that it reduces an O(M x N) code explosion, allowing interoperability and code reuse.

I also realized that there are two distinct senses of the word "narrow":

  1. In terms of architectural connection (topology).
  2. In terms of the size of the concept.

So this issue deserves some more thought, and perhaps more terminology.

Here are more ways to characterize narrow waists:

  1. They are compromises. They make systems economical and possible, not necessarily optimal.
  2. They arise through a mix of explicit design and implicit evolution.
  3. The design can be done well or poorly. The evolution can be guided or haphazard.

Regarding evolution:

  1. Narrow waists can last for decades, usually evolving in a versionless manner.
  2. But narrow waists can also move!
  3. They're subject to extreme economic pressure and network effects. For example:
  4. The downside of inertia is that narrow waists can inhibit innovation.
  5. Narrow waists are often overextended to new applications.

Some recent narrow waists include Docker / OCI, the Language Server Protocol, and WebAssembly. I should be more specific about their varying degrees of success with respect to design and user adoption. For example, I think WebAssembly is useful, but less general than what's been recently claimed. It's a deep compromise which involves winners and losers.

Fallacies

Here are some common objections to the idea.

(1) Textual data is hard to manipulate with programs.

This is not an objection to the narrow waist principle! The main claims of the principle are about interoperability and economy of implementation.

I want to make a Simple vs. Easy argument. Narrow waists are simple in Rich Hickey's terms (not "complected"), but not necessarily easy to use. For example, Unix shell can be hard to learn, but its power results in a small, extensible operating system.

(2) The web is really messy, and thus unreliable.

I make a strong Messy vs. Stable distinction. Messy systems aren't necessarily unreliable. Quite the contrary — the need for stability is the cause of the mess! Continuous backward compatibility (like the the many iterations of CSS) makes a mess, but keeps the system working.

This relates to another concept I've been having a hard time describing: versionless evolution, which I describe below.

Related Ideas

We can understand the narrow waist more precisely by relating it to these ideas:

  1. Metcalfe's Law states that the value of a network is proportional to N2, where N is the number of nodes.
  2. The Internet Protocol follows the End-to-End Principle and it's a narrow waist.

Examples and Elaboration

Let's apply these principles to real world systems. Again, I claim the narrow waist is the most important idea in software architecture, because it describes the biggest and longest-lived systems.

The Web Evolved In A Versionless Manner

I'd like to elaborate on the "versionless" property of many narrow waists. You can contrast two philosophies of versioning:

  1. Version numbers that indicate breaking changes, e.g. Semantic Versioning.
  2. Continuous backward compatibility, i.e. versionless evolution.

For example, the web doesn't have incompatible versions, and JSON was explicitly designed by Doug Crockford to be versionless.

History proves this rule. In Don't Break X, I mentioned that XHTML and ECMAScript 4 both tried to break the web with radical changes, but they failed because of the inertia of narrow waists.

In contrast, HTML5 and ECMAScript 5 evolved the web in a compatible way. We should study and disseminate the history of the web avoid repeating mistakes we get "stuck with".


Here's a good way of thinking about versionless evolution:

Relaxing a requirement should be a compatible change. Strengthening a promise should be a compatible change.

— Rich Hickey in Maybe Not (2018, YouTube)

Examples:

Bytes and Text Are Essential Narrow Waists

I have a recurring debate about "text vs. fine-grained types", mostly with people who are frustrated with ad hoc, incorrect #parsing in shell.

I think that a shell with support for JSON, QSN, QTT and HTML will address this problem. It will reduce the amount of parsing in shell programs, and make it correct.

I also claim that parsing is an O(M + N) problem, while types can create O(M × N) problems — and often do.

To give more color on that, here's an important comment which I mentioned in January, June, July, and August:

I make the M × N argument, and use concrete examples like IntelliJ and WebAssembly's text format:

You have M formats and N operations, and writing M × N tools is infeasible, even for the entire population of programmers in the world.

I also note the tradeoff:

It's not an absolute; in reality people do try to fill out every cell in the M × N grid [in certain domains]. They get partway there, and there are some advantages to that for sure.

I also quote Rust designer Graydon Hoare on text. While his "rant" is mostly about the information density of text, it also touches on the wide range of operations that text supports.

[Text] can be compared, diffed, clustered, corrected, summarized and filtered algorithmically. It permits multiparty editing. It permits branching conversations, lurking, annotation, quoting, reviewing, summarizing, structured responses, exegesis, even fan fic. The breadth, scale and depth of ways people use text is unmatched by anything.

I note a problematic M × N explosion in code generated by protocol buffers (as opposed to source code).

For example, equality becomes schema-dependent rather than generic. This is worth it in many systems, but it's a tradeoff.

Slogan: Text Is The Only Thing You Can Agree On

Here are two variations of a slogan. It's meant to drive home the point of text as a narrow waist.

The lowest common denominator between a PowerShell, Elvish, Rash, and nushell script is a Bourne shell script (and eventually an Oil script).

This is because each alternative shell chooses a different kind of structured data as its narrow waist (.NET objects, tree-structured data, Racket data structures, and tables, respectively). Text is the most structured format they all agree on, and shell is the language of coarse-grained composition with text.

I predict that this will be a real thing, and isn't theoretical! I have no doubt that there are already bash scripts invoking PowerShell scripts out there, and more complex agglomerations will arise as alternative shells become popular.

It doesn't mean those shells aren't worth using, or more potentially more convenient. But it highlights the need for a better Bourne-style shell.

and

A second phrasing:

The lowest common denominator between a Common Lisp, Clojure, and Racket program is a Bourne shell script (and eventually an Oil script).

Again, these languages are similar, but have incompatible data models. (It's not just the compound data structures; Clojure's notion of numbers and strings is borrowed from the JVM.)

These two slogans are really another way of phrasing a slogan from the last post:

Unix is equally inconvenient for every programmer, and that's a good thing.

CSV, JSON, HTML - Tables, Records, Documents

The full title of this post is:

CSV, JSON, and HTML are Different Because Tables, Records, and Documents Are Different

This is again pushing back on the notion that JSON is "the" new narrow waist of shell. Tables and documents are essential structures in software, and expressing them in JSON is awkward.

I can give examples of this, e.g.

{"name": "alice", "age": 42}
{"name": "bob", "age": 43}

and

 ["a", {"href": "/home"}, ["anchor text"]]

This framing comes from the paper Unifying Tables, Objects, and Documents (Meijer and Schulte, 2003), but the technical details differ.

Tradeoffs Between Dynamic and Static Types (FAQ)

Text as a narrow waist is at odds with fine-grained, static types. My goal is to highlight tradeoffs, and analyze situations where each style is natural and efficient.

Many programmers seem to think there is no tradeoff — or at least they say that on the Internet. I believe that when they create working systems they often use the dynamic, coarse-grained view!

This recent comment links to typical responses, which by now form a FAQ:

Here's a related, fantastic video which I want to signal-boost:

I don't know the F# language, but it apparently has a very Clojure-like view of data, despite being statically typed. The "type provider" mechanism addresses the problem of types that are only available runtime, e.g. in SQL schemas, or implicitly in JSON and CSV files.

Overall, the fallacy is that we use dynamic typing when we're "too lazy to write down the types". There are many useful programs that aren't 100% statically typed, and I claim this trend is increasing. (Slogan: Poorly Factored Software is Eating the World.)

The real issues are scale in space and time, heterogeneity, and extensibility!

Refinements

In the discussion of the extensibility post, I said that I'm getting at theory and guidelines for runtime composition and versionless evolution. Shell is about software composition at runtime, as opposed composition via static linking.

So in addition to the Perlis-Thompson Principle, narrow waists, and O(M × N) code explosions, here are some more concepts that are worth exploring.

Projection to Waists

I need a name for the idea of code reuse by changing the representation of data to a narrow waist. Examples:

  1. The /proc file system projects kernel metadata onto the narrow waist of the file system.
  2. Any system that uses FUSE is also like this, e.g. Michael Greenberg's File File System projects JSON onto a virtual file system. This allows reuse of tools like cd and ls.
  3. The gron tool projects tree-like JSON onto the narrow waist of "lines of text". This allows reuse of tools like grep and awk.

Notice that JSON is a narrow waist, but it's been projected onto two others: the file system, and lines of text. Which one is appropriate (if any) depends on what set of tools helps you solve a particular problem.

Emulation of Waists

This is the most straightforward one. As mentioned above, there's a big incentive for Windows to emulate Linux, and vice versa. The platform gets thousands and thousands of applications "for free".

Another example is when Illumos borrowed FreeBSD's Linux syscall ABI emulation in order to run user-uploaded Docker containers. This is dynamic, runtime composition with ABIs, not static composition by compiling code against kernel APIs expressed as C header files.

Extension of Waists

I think "waist extension" is a good term for the following ideas:

Composition Between Waists

Unix has multiple waists: processes, file descriptors, file systems, lines of text, unstructured text, and bytes. Each of them allows M × N things to compose, but they also must compose amongst themselves.

"A few things that compose" is tantamount to the Perlis-Thompson Principle. When I started this series, I wasn't sure if this term and "narrow waist" were necessary — maybe they're both tantamount to "simplicity".

But after working through examples, I see them as distinct but related. So it would be nice to write more clearly about how narrow waists relate. This seems like a distinct style of long-lived architecture.

Again, let me know if you have references. I don't want to write about ideas that other people have already explained, or invent new terms when there are existing ones.

Addition of Waists

It's common to create a new, larger narrow waist out of existing smaller ones.

For example, the Language Server Protocol uses JSON-RPC for notifications and responses.

In turn, JSON-RPC is built on top of JSON and a transport like TCP/IP or pipes.

Hierarchy Among Waists

There's a clear hierarchy among data representations in Unix, which affects which operations are valid:

Call to Action

Jon Postel Made the Internet's Waist Narrow

After a very helpful reader e-mail, I added an appendix to the last post. I want to transcribe the first 10 minutes of the video of Van Jacobsen. He describes the role of Jon Postel as Internet specification editor — specifically, his relentless, decades-long drive for minimalism in the Internet's design:

This narrow waist is not something that God gives you. It's something that you make. It's hard engineering.

and

We unfortunately don't have a lot of Jon Postel's in the world. It would be nice to get one on nearly every project.

This reminds me of the sentiments by Ken Thompson quoted in Unix Shell: History and Trivia. They share a taste for minimalism that unlocks enormous functionality.

I also enjoyed reading these memorials:

The point is that people have to behave differently to create valuable, interoperable systems!

Conclusion

After more than a year of circling these #software-architecture topics, I feel pretty good about them. They've informed Oil's design and will continue to. It helps to be precise about definitions and support claims with examples.

I hope this outline was also useful to you. I wish I could have written a shorter post, but I didn't have time :-)

And again, please send related references. They will help with future articles on these ideas. (I was surprised that the history of the narrow waist in networking is not well documented or agreed upon.)


Now I want to switch gears to something more "tactical": translating Oil to C++! That has been on hold for a full year, since the last milestone in March 2021.

I also want to expand the project. Please donate to my new Github Sponsors page if you think we need a new, principled shell. I'll ask for donations again in upcoming blog posts. All of the money will go to contributors and "employees", not to me!

Appendices

The Lambda Calculus Is a Narrow Waist

This a "fun" post to help us with the definition. It's based on this quote from chapter 5 of Types and Programming Languages:

[The importance of the lambda calculus] arises from the fact that it can be viewed simultaneously as a simple programming language in which computations can be described and as a mathematical object about which rigorous statements can be proved.

Wiki, Zulip

This post was long, but there are still important things I left out. As mentioned in the Motivating Design Questions section, these ideas relate to the design of foundational cloud software like Docker and Kubernetes.

But I want Oil to be in better shape before I continue writing about these topics. For now here are my Wiki pages and Zulip links. (I really wish I had a single brainstorming and research app.)

I also mentioned the #containers Zulip stream in December. Here is a (sloppily sketched) overview thread: