Accidental complexity in "friendly" main program, a mini case study

General
1

If you need quick hands-on experience with accidental complexity, just try reproducing a computational experiment paper, which I unfortunately did recently, and very likely you will find these extremely helpful features:

  • The main program finds the dataset by name and parses it, so you don’t need to worry about paths and file types.
  • The main program puts the results in a pre-configured well-known path, so their evaluation code can find it.
  • The main program finishes the experiment and calls evaluation code, so I don’t need to know where the evaluation code is.

Of course, all of these features were buggy. When I ran into bugs, I needed to look at all the implementation details the author imagined I could skip. In the end, we could have been better off writing documentation for the core functions, instead of writing a “friendly” main program.

But why do people keep writing “friendly” main programs? A great amount of accidental complexity is repeated in every program not because of programmer incompetence, but systemic reasons. The following important problems are not adequately solved by the UNIX operating system/programming environment.

Persistence

Persistence is already a widely agreed requirement of substrates.

If the main program does not include unnecessary I/O code, the convention is to use standard input and output. Standard output is not persisted and also dangerous (control characters). Standard output is by default unreliable: it scrolls too far, breaks the terminal, and is not saved.

But we also have shell redirection, and it has none of these adverse effects. Why are people not using it? I can only guess: maybe the shell is not “proactive” enough; users want the shell to save the output first, then let them consider other options. This way they have one fewer thing to worry about. (Feel free to share your theory.)

In conclusion, if there is only one output stream, a mandatory --output-file argument is just unnecessary complexity. We should simply modify the shell to persist what the user wants. Although uncommon in practice, this can still be done with more output streams.

Of course, my previously proposed nonlinear operating system should be a systematic solution to this problem.

File Types

If the operating system is a programming language, each variable is a “file” which already has a type. This is not true for the UNIX file, which is always a byte array. So, the main program needs to write file type abstraction code.

On one hand, this “programming language as OS” stops making sense if you have byte arrays everywhere like a regular filesystem. It really is necessary to have typed variables everywhere. If the abstraction layer is present, the serialized presentation is not important at all. Are we ready to demote serialized representation? Let the runtime take over all serialization?

On the other hand, it is conceptually sound to have binary formats, as long as the user knows the format. You can always build abstractions on top. Untyped filesystems are successful because they care no more about bytes. Additionally, the byte array file can be used with any abstraction implementation, while a variable of a certain type can only be backed by a single abstraction implementation. Are we ready to lose this flexibility?

My suggestion: Have a type-agnostic kernel, and allow multiple independent abstraction views of one underlying data.

Core Function Discovery

The main program can only be as helpful as its help message, which shows the core (business logic) functions I can call, and what I need to do to be routed to each core function. Without a main program, how will I discover the core functions?

Let’s consider static analysis. We can get a dependency graph of the functions. The unused functions (no other code calls them) are definitely entry points. But some used functions can also be entry points.

The ordering of the functions can also be exploited. The author has usually decided to order them in a certain meaningful way. Many IDEs reorder functions lexically in a context, which is really detrimental to function discovery.

In general, since this is quite subjective, I think no one but the author must indicate the core functions. For example, they can annotate core functions to be displayed with more importance. They can also write a literate example program that calls all core functions.

Note: I did not mention “exports” because I still want to be able to call the helpers. They just need to be very unimportant when I initially explore the code.

2

The last point, “Core Function Discovery”, has a lot to do with UI. UIs try to make it easy to discover things, by having things where the user expects.

If this is the case, we should really be writing READMEs instead of main programs.

3

This maybe not a highly relevant anecdote, but something I’ve been thinking about while tinkering this week.

I discovered that the Fish shell wraps cd with a Fish function to implement directory history. The wrapper simply persists a history stack using shell variables (see the source by runing funced cd or look here).

I use a tool that does a computationally intensive task. Power-users of the tool know that internally work is done in two stages, the first is computationally intensive and the second stage is both that and network intensive. After the first stage an estimate can be made of how much work the second stage is. Unfortunately most users use the one-shot porcelain binary and power-users come up with a manual or custom solution if they want more control.

What I can do is recreate the interface of the porcelain program as a Fish wrapper but using the techniques I found in cd I get extra features like interrupting and resuming work using state history at almost zero marginal cost. A huge benefit is that I can run funced to examine the wrapper whereas for the porcelain main program I need to navigate some C++ codebase.

It makes me suspect that there are many cases where the friendly main program is a premature composition that would be better as a shell script that users can study and modify. 9FRONT is doing this right (see 9fs) but Linux not so much (think mount).

4 Likes
4

A provocative question: why do we expect a porcelain in every software project?

Given users are already able to compose the programs, like in your case.

1 Like
5

My answer is: the diversity of users. Power users want scriptable tools that they tie together themselves. Occasional and inexperienced users want a specialized UI with discoverable functionality.

6

The diversity of users means the diversity of experience levels, workflows, goals, and environments. So, the developer is expected to cover many such common situations. Of course.

Let me shift the focus to discovery.

Must there be a single porcelain entry point? (I’m looking at you, apps.) As discussed above, we probably want multiple entry points.

Consider:

  • FFMPEG, which has the entry points ffmpeg, ffplay, ffprobe.
  • ImageMagick 6, which has the entry points convert, identify, mogrify, and more. In version 7 we no longer have these separately.
  • Gradle, which has system-wide and in-project wrapper (./gradlew) distribution formats.
  • BusyBox, which provides a large number of utilities in one binary. I put this last, because each entry point leads to a very different core function, unlike most of the above.

These do not have to be multi-call like BusyBox. ffmpeg will just load the core library and do encoding, and ffplay will just load the core library and play something. ffmpeg and ffplay can be separate wrappers without sharing anything but the core dynamic library. They perfectly satisfy two demands, while removing subcommand routing.

That is, given users can discover the different commands. If multiple entry points are extracted to the system level, the system must responsibly offer discovery features. But the package manager does not tell users what commands are contained, what man pages are contained, or even show any documentation, when they install a package. The user is forced to discover by guessing the command name, and trying --help. This is the gap!

Also imagine if apps can have more than one icon on the home screen. Don’t we remove a ton of UI code that only routes the user to real features? In fact, this is supported by Android, but app stores don’t like it.

1 Like
7

I’ve certainly seen these concerns in academic projects. Doubly so when done by students who move on.

Using stdin/stdout + README suggesting redirctions has a major weakness: Files don’t describe their provenance.
When people exchange some inputs + precomputed outputs, it’s hard to be sure what command(s) were [can be] run to [re]produce them. And user-chosen names (latest-2_good.preprocessed-copy) make this worse…

Hence the temptation to hardcode in/out file name conventions. If done well (e.g
out = in.suffix), it makes data discoverable — but comes at cost of composability.

  • main.sh script keeps thes clearer than main.py etc. Costs: (A) now you have a polyglot project, which demands more from the people involved. (B) It’s more OS-specific? WSL half-solved this, now bash is universal enough. (C) Writing porcelain wrappers is more (buggy) code than calling Python etc. directly.

  • Makefile can be even better! But fewer yet speak it well.

What the Unix substrate still lacks is a shell notebook/spreadsheet, where derived files come with provenance. You could call it “madesialzed execution”.
Not necessarily an OS problem. A good convention/format + good UI could solve this(?). Decades after make, we’re still iterating on what that looks like, within Unix…

  • Technically jupyter has bash notebooks. Never seen them used. Github/gitlab rendering READMEs & notebooks OOTB is great! I miss both in file managers…
  • For looped/distributed long-running commands, GNU parallel has a format for restating which is handy (though idiosyncratic).
  • GitHub - apenwarr/redo: Smaller, easier, more powerful, and more reliable than make. An implementation of djb's redo. · GitHub is better than Makefile for encoding “this is what already run + dependencies”. Nobody heard of it.
  • Nix & Bazel are programmer-grade hermetic reproducibility, where exact code used is tracked as well. but apparaently to heavy for casual users?
  • Dockerfiles did achieve wide semi-casual use :tada:
    • Earthly attempted a more Docker-ish bazel. rip.
  • There were a bunch if “git for data” projects but I lost track…
2 Likes
9

Even if you use author-determined names, the right value behind that name must be immutable to be satisfactory. This is the mutability problem all again.

I have considered that in a separate topic, History as a First-class Citizen, which is all about built-in provenance.

10

All those issues look sooo familiar - from teaching scientific workflows. There is no lack of workflow engines (and I just discovered another on in your post, redo), but they are all file-based with neither GUI support nor any development or deployment tooling. Jupyter is huge, fragile, and doesn’t play well with the Unix ecosystem (not even version control), so I don’t expect it to become popular in this space.

The challenge I see here is the “Unix philosophy” of small composable tools vs. the desire for integrated UIs. Maybe all that Unix lacks is a UI toolkit that everybody can agree on, ensuring composability.

1 Like
11

On the other hand, it is conceptually sound to have binary formats, as long as the user knows the format. You can always build abstractions on top. Untyped filesystems are successful because they care no more about bytes. Additionally, the byte array file can be used with any abstraction implementation, while a variable of a certain type can only be backed by a single abstraction implementation. Are we ready to lose this flexibility?

This is why I’ve been thinking for a long time about a programming language which, like Unix (and perhaps like REBOL or Red) is based entirely on persistent “byte arrays” rather than “objects” as its single datatype. Where pointers to arrays are opaque unforgeable security capabilities, but indexes into arrays are guessable. (A trivial/degenerate case of such a system - and perhaps still the easiest to implement in terms of having a very simple and easy to reason about storage allocator - is the Lisp CONS cell, which is a two-element array. The semantics of Lisp lists are subtly and annoyingly different from Unix files/streams, though: if a file were a list, you could only read it starting from its end, not from its beginning).

I think such a language could work BUT, it would need the ability (enforced somehow in the runtime, VM, or “OS kernel” - these could all be the same thing on a sufficiently small OS) to mark byte arrays as “of a certain type” (when stored on “trusted local storage”, ie, something that can’t be changed by an attacker), so that any code accessing this array can be certain it is of the right type. This type judgement could be a function, but it might need to be more than just a function, in that it might need to resolve to a printable/parseable name (that doesn’t clash with other names in a namespace), and it might need to be decomposable by user code at runtime (in a way that functions stored as opaque pointers generally aren’t) into at least conjunctions/disjunctions (AND and OR; set union/intersection; sum and product types, etc) of other types.

I think it is very hard to mark a file or a byte array as of a certain type, if that file/array is both mutable and write-accessible by any function or process. It is very easy to mark a file/array if it is immutable. Marking a file/array by restricting it to only being written to by a single function or process can work, as in object-oriented programming, BUT, if enforced at an OS level, this can make debugging and repair very difficult and sometimes impossible.

A useful feature in an OS with persistent byte-arrays as its storage mechanism, might be an operation that both validates/marks an array as of a certain type (by evaluating a function that returns “true” within a certain timeout period), and then makes the array read-only but deletable. A directory/folder that contains references to subarrays could also be validated in a similar way, up to a volume root. To delete a subfolder from a validated array, you would need to delete the parent array.

If we want the arrays to *really * just be byte arrays, then any subarray references would have to be security capabilities. 32-byte SHA256 hashes are, I think, currently considered acceptable as capabilities, but 16-byte GUIDs/UUIDs are not. If we only care about typing for read-only arrays, and don’t need typed-but-mutable array support, then SHA hashes would be fine. At 32 bytes per reference, we’d not want to be storing lots of tiny arrays much smaller than that. (ie, two-cell Lisp conses would be extremely impractical). And I guess we’d still need some kind of unforgeable security capability as handles for the mutable files/arrays: probably 32 bytes of cryptographically random numbers. And then you’ve got to deal with having a source of hardware entropy which is super annoying, especially for tiny virtual machines. And of course the constant computational overhead of all those cryptographic operations.

Or more practically, we could require an OS persistent-storage layer which just trusts its local storage (for efficiency) and has some magic (ie not exposed to user code) way of handling persistent pointers in its files/arrays, so they’re not quite byte arrays but “byte or opaque pointer” arrays. Perhaps with a word size as big as a pointer needs to be on a machine as big as a modern desktop (maybe 64 bits), plus a way of reading/writing an array as bytes but only if it contains no pointers. Then you’d only pull out the full cryptographic hash or random-number thing if you needed to transmit a whole read-only, validated file/array across untrusted wire or storage.

It might be interesting to see just how far “strictly typed persistent data, but only of read-only/immutable data elements, with mutability allowed for untyped arrays/objects/files” could get us in a combined programming language / OS.

2 Likes
12

My approach is this:

Store the byte array as one thing.

Store the abstracted interpretation as the following expression:

apply(abstraction-layer, byte-array)

where abstraction-layer has type byte-array -> A, so the whole expression has type A.

If you have only the byte array, you don’t know the type. If you have both the array and this expression, then you do, and the high-level data is not allocated until you evaluate the expression.

This way, we can even use multiple abstraction layers, unlike your singleton annotation design.

1 Like
13

If you have only the byte array, you don’t know the type. If you have both the array and this expression, then you do, and the high-level data is not allocated until you evaluate the expression.

That’s a potentially useful idea, yes. It could be very helpful to separate out the validating/marking a byte array as of a certain shape/type, from the array itself, so that you could have different views into the same array. As for example Javascript does with its “buffers vs views” implementation of Typed Arrays.

But what I’m saying is that you would still want a byte array that has such a high-level view or abstraction layer attached, to either NOT be mutable, or to severely restrict mutability, and restrict it to the most restrictive combination of all attached views / abstraction layers. Otherwise any one abstraction layer could make a change that destroys the type-guarantees / assumptions of any of the others. And if you do have multiple views, how exactly do you coordinate between them, and make sure that every change satisfies all invariants?

Object-oriented systems solve this by only allowing one thing, the class, to mutate an object, with the assumption (not always a correct assumption!) that any change that a class’s mutator method does to its underlying data, is by definition “correct” , satisfying all relevant invariants. (Even if the invariants that a class guarantees are never anywhere formally defined; and even if the class definition changes over time: and for data stored in persistent objects in an operating system or database, there ARE going to be changes in the class or schema definitions over time! With much resulting pain.)

My weird and half-baked suggestion here is: what if we threw away all forms of mutation except for completely unrestricted mutation of at least toplevel-untyped arrays (so not just byte arrays, but arrays of pointers as well - so that we can “freeze” smaller chunks of validated data and not have to completely reparse them any time we reconfigure them into different datasets). And then we no longer have a very complex object system but just a very simple division of “mutable scratch data, vs typed immutable data”. So you can get mutability where you absolutely need it, which is often very local and temporary anyway, but anything you’re passing around for longer than one place, you freeze it and make it typeful.

This might be an unhelpful idea, but I wonder if it might be slightly better than “everything is immutable” which gets problematic for efficiency, vs “everything is a typeful mutable object, but the semantics are very unclear around what actually an object is, particularly if it mutates and is longer-lived than its class definitions, or has many super/subclasses”. A mutable untyped array has very simple semantics, and an immutable array with type information attached (including supertypes) is almost as simple.

This two-part division though probably doesn’t cover “objects as processes” which might be the most important use of them, in OOP extended to the OS level. And a process can’t be “frozen” or be immutable (though its code can and should be). I suppose it’s still possible to have, say, an array in which some elements are mutable and some are immutable, and a process would be one of those, but it would be nicer to have even stronger guarantees on behaviour.

(There are many things I like about OOP design principles, but one thing that always makes me uneasy is, a class is usually defined purely by the name and shape of the messages it receives and emits, which might even be clustered together into “interfaces” or “traits”. But these interfaces/traits do not generally come with invariants which can be guaranteed. So an object in modern OOP systems tends to have a crisp shell but is squishy inside. Squishy in a way that specifically means - for persistent OS-level data, which never “shuts down” and with class definitions that can change at any time while the data remains live - that it can change at any time into something that hates you and wants to destroy you. While remaining perfectly compliant to its interface definitions. I’d like this internal shape-changing to not be a thing, somehow, if possible.)

1 Like
14

I don’t quite understand this. Can you elaborate?