Perlis Thompson Principle - oilshell/oil GitHub Wiki

UNDER CONSTRUCTION

The Perlis-Thompson Principle is an idea in software architecture. It's arguably the most important one, because it explains the evolution and scaling of the largest and longest-lived software systems, like Unix and the Web. It also suggests where they fall short.

I wrote many blog posts that mention it, starting in July 2021.

Eventually it converged more on narrow waists, a very related concept. These are the two best posts:

and this is a survey post:

More Background:

Definitions

Here's a literal summary of what Perlis and Thompson said:

Write software where everything is an X (e.g. a string, pointer, cons cell, table, vector, window, etc.)

They say to use a single data structure, or single notion. However I think that is too absolute, and there are caveats.

Here's a revised, short definition of the principle:

Software with fewer concepts composes, scales, and evolves more easily.

Here's a long definition:

Consider using fewer concepts, data structures, and types in foundational software like programming languages and operating systems.

This style allows for more composition and ad hoc reuse. It scales in multiple dimensions. It evolves gracefully (and messily) over decades.

When introducing a new concept, define a way to reduce it to an existing concept.

Key Concepts / Terms / Slogans

  • "Everything is an X"
  • Writing O(M + N) code instead of O(M * N). Huge difference!
  • Coding the Perimeter vs. Coding the Area (from the Unix vs. Google video)

The "Narrow Waist": A Special Case of the Perlis-Thompson Principle

What Is it? What are other names for it?

A software ecosystem that uses a narrow waist is following the Perlis-Thompson Principle in a particular way. The narrow waist idea relates to data: data structures, interchange formats, and network protocols. The Perlis-Thompson principle is arguably more general and refers to "concepts" like Unix processes and Emacs buffers that aren't quite data.

It's also known as:

  • Thin Waist
  • Hourglass Model
  • Lowest Common Denominator
  • Networking Terms: "Distinguished Layer" or "Spanning Layer"

Prominent Examples of Narrow Waists

This idea spans operating systems, networking, and programming languages.

  • TCP/IP is a narrow waist between physical issues like wired/wireless and application protocols like the web, e-mail, IRC, Usenet, etc.
    • The narrow waist of the Internet has arguably moved to HTTP over time, with e-mail, chat, Usenet-style discussions all migrating to web apps
  • An operating system API like POSIX is a narrow waist between applications and hardware
    • Win32. Related: WINE is the most stable ABI for Linux games!
  • LLVM is a narrow waist between programming languages and computer architectures
  • Byte streams / Unix-style text are a narrow waist between storage/networking abstractions and application-specific schemas
  • Pandoc is a narrow waist between document formats. Instead of writing O(N^2) document converters, you design an IR, and write N translators to the IR, and N translators from the IR.
  • SQL is a Narrow Waist (Jamie Brandon)

Unix Philosophy and Narrow Waists

Unix and shell are centered around:

  • Byte streams / Files
  • File Descriptors
  • File Systems
  • Processes
  • New: OCI Containers (derived from Docker). This is a new narrow waist.
    • It is a live concept! Just like the narrow waist of the Internet moved from TCP/IP to HTTP.

What Isn't a Narrow Waist?

Just to show the the concept isn't vacuous, here are things that are not narrow waists:

  • No: MS Word files or Excel spreadsheets. These formats are too complicated, to the point that they're tied to specific applications. On the other hand, a CSV file is a narrow waist -- you export it from Excel so you can read it into other applications.
    • CSV is also an example of a bad narrow waist. Not all narrow waists are well designed! Sometimes they just evolve. JSON is a better one that was explicitly designed.
  • No: JPEG. It's optimized for small size and display. To support other operations, like various kinds of editing, it's converted to a format that's easier to work with.
  • No: the monolithic "Docker". But OCI images (derived from Docker) are.

Examples of "Projection" Onto a Narrow Waist

  • If your website is served as JavaScript code that executes and renders a page, then it can't be indexed by a search engine. So what webmasters do is render it as text, "projecting" it on to the narrow waist that search engines understand.
  • Greenberg's FFS (file file system)
    • And most software that uses FUSE. It borrows the Unix command toolset for a different data structure.

Related

  • "Desugaring" in compilers. Design an IR that has fewer concepts that your language reduces to. This simplifies the back end of the compiler and aids reasoning about correectness. (I recall Walter Bright of D saying that Andrei Alexandrescu really pushed for more desugaring in the semantics of in D 2.0, the second version of the D language.)
  • UTF-8! UTF-8 cleverly uses the 8th bit and "reduces" to ASCII. Go has a single string type because it's based on UTF-8, while Python has both str and unicode types. The latter design causes composition issues, like when interfacing with OS paths.
    • Ken Thompson invented UTF-8 so it's no coincidence that it obeys the Perlis-Thompson principle :)

Examples of M x N Code Explosions

See M by N Code Explosions

Textbook References (TODO)

  • TODO: There should be a networking textbook that talks about narrow waists / hourglass
  • TODO: There should also be a compiler textbook. I know I've seen a diagram of IRs as a waist between programming languages and CPU architectures.

Not sure about OS textbooks, but the concept definitely applies there too.

Links on Narrow Waists

  • HTTP: An Evolvable Narrow Waist For a Future Internet (PDF, 2010). This and Van Jacobsen's Named Data Networking introduced me to the concept of a narrow waist. (Even though it's in both networking and compiler textbooks.)
  • My HN Comment on the Kubernetes-Multics analogy (2021): I trace the narrow waist to Kleinrock via Brewer, but there might be a more original reference
  • Unix vs. Google (2016): a video by Kevin Greer. Has visualizations of Unix vs. Multics: coding the area vs. coding the perimeter. O(M * N) problems.
  • Always Bet on Text (Graydon Hoare, 2014). 196 HN Comments.
    • Text is everything. My thoughts on this are quite absolute: text is the most powerful, useful, effective communication technology ever, period.
    • It can be indexed and searched efficiently, even by hand. It can be translated. It can be produced and consumed at variable speeds. It is asynchronous. It can be compared, diffed, clustered, corrected, summarized and filtered algorithmically. It permits multiparty editing.
    • This is a restatement of what Perlis said: It's better to have 100 functions on 1 data structure than 10 functions and 10 data structures.
  • On the Hourglass Model CACM July 2019. An attempt at formalizing ("Hourglass lemma", "Hourglass theorem", "deployment scalability" i.e. Unix and Internet becoming ubiquitous). Talks about supporting layers on the bottom and supported applications on the top. Talks about Unix process creation (which I think is true but could be better explained). Good to see people thinking about this but I think a "literary" treatment will generate more insights.

The Networking Community Explicitly Thinks In Terms of the Narrow Waist / Hourglass

It doesn't appear that the operating systems community does! And definitely not the "cloud" operating system vendors.

Links on The Perlis-Thompson Principle in General

Common threads here: either "everything is an X", or explicit nonlinear codebase scaling problems -- O(M * N) or O(N^2).

I've been thinking about this for a long time!

Special Cases

  • Uniform Interface Constraint of REST is arguably an instance of the Perlis-Thompson principle. Instead of many different styles of API, your system can use one kind of API with generic operations. (Google's architectural guidance to its engineers moved toward REST in later years.)
  • What Color Is your Function? Is a Perlis-Thompson Argument. If you have two different kinds of function, then you have the problem of composing them.

Counterpoints / Fallacies

The Perlis-Thompson Principle goes against the intuition of many programmers. They are weighing the tradeoffs from a code perspective, not a systems perspective. Those perspectives can lead to opposite conclusions.

  • A Case Against Text Protocols (2020). My "Unix text as a narrow waist" comment argues against a common misunderstanding. Text is the reason we have good tools. As an example, it doesn't make sense to make an WASM editor and WASM version control system. Instead the binary WASM format is projected on to text, and we use text editors and SCMs like git.
  • On the Missed Opportunities of Static Types (2021). There is a tradeoff: more types give you some easy safety checks, but can inhibit composition!
  • FFI Fallacy on the Vale Programming Language (2020)
    • People who advocate "standardized" RPC systems are often attached to a similar fallacy.
    • A function in C is not a function in Python is not a function in Rust. You need a lowest common denominator, or you require O(N^2) glue. I remember someone actually writing to write a specific R-Java bridge rather than using IPC.
  • Programmer's Critique of Missing Structure of Operating Systems (2020). A long article lamenting the repetitiveness of parsing a plethora of data formats. It's reaching toward ideas like a single-level store.
    • My response: This could be done in an "application framework". The problem is nobody can agree on the lowest common denominator. There's no reason to think that putting more code in the kernel will solve this problem.
    • An operating system has two "sides": one part faces the hardware, and one part faces applications. He wants the OS to do more work for applications. I think a tighter goal for the operating system is to proivde a minimal abstraction to virtualize and share hardware, while providing safety and isolation. It should make applications "possible"; making applications "easy" and factoring into shared libraries is a separate job.
  • Shells Should Shell Out (2021). I question the two-tiered design of PowerShell, Elvish, and nushell. cmdlets aren't processes. They need semantic rules to convert between internal and external representations.
    • Argument: The lowest common denominator between a PowerShell script and an Elvish script is a Bourne shell script :) Byte streams are the lowest common denominator.

Related Pages