Why Sponsor Oils? | blog | oilshell.org

Oil Is Being Implemented "Middle Out"

The term "middle out" makes me laugh, but let's save humor for the end of this post.

First, I want to explain an issue that has confused many readers: the strategy of implementing a shell in Python, then semi-automatically translating it to C++.

For example, Nix contributors asked questions about this, and December's Language FAQs answered some of them. I also wrote Why Is it Written In Python? in 2019. Summary:

• We want a short, correct, and maintainable shell interpreter. This goal has largely been achieved (#metrics).
• This strategy also let us gracefully "morph" this interpreter into the new Oil language.

But I haven't written much about the C++ translation, other than a few posts mentioning our #mycpp tool (e.g. Progress in C++).

So this post uses the term "middle out" to explain it. I also repeat that I need help with this part of the project, so I'm collecting donations to pay a compiler engineer (not me). I show evidence that it absolutely can be done, including a plot of progress over the years.

Language-Oriented Programming is "Middle Out"

I was surprised to find this term in a computer science paper*:

It describes a method for "organizing the development of a large software system":

1. Start by developing a formally specified, domain-oriented, very high-level language which is well-suited to developing "this kind of program"
2. Implement the system using this "middle level" language
3. Implement a compiler or translator or interpreter for the language

The abstract continues:

The “middle out” development style is compared and contrasted with the more usual “top down”, “bottom up” and “outside in” development methods.

* I can't find many citations to it, but it's still interesting.

Oil Is Expressed With DSLs

"Middle out" is how Oil is being developed! Our approach is more iterative, but clearly similar:

1. Through experimentation, I found that Python, Zephyr ASDL, and regular languages can compactly represent a shell interpreter.
2. We've been implementing the shell in this set of metalanguages.
3. Now we have the task of translating this code to C++.
   • As evidence that this will work, I usually point to Oil's Parser is 160x-200x Faster Than It Was 2 Years Ago (January 2020). I show recent updates below.

The idea behind this approach is exhaustive recognition and representation of shell's elaborate syntax and semantics.

It's been a consistent advantage over 5 years. For example, I described November's Oil 0.9.5 release as The Triumph of Lexer Modes because the technique helped me with tricky syntax issues like typed arguments to Oil procs, and extended globs in OSH.

Size of Oil's Two Halves < Size of Bash

Is this a roundabout strategy? It's not obvious, but it actually makes the system smaller, as noted in the 2019 FAQ. You get leverage if the "middle language" matches the problem domain well.

The updated line counts for translation show that:

• The shell is implemented in less than 40K lines of code.
• The code generators are less than 11K lines of code.
• We have about 5K lines of hand-written C++ code, including the garbage-collected runtime and OS bindings.

The slogan I use is that bash is implemented with at least 142K lines of "groveling through backslashes and braces one at a time" in C. Oil is implemented in a completely different style, and future posts could show examples.

So despite the addition of the new Oil language, Oil is many times smaller than bash in terms of its source code.

For more color, the appendix mentions that The Implementation Language of Shell Has Always Been a Problem, with historical evidence.

Plot: Progress in Two Directions

This plot shows development progress through 80 releases of Oil, representing nearly 6 years of work!

1. The blue line is step 2 above. We're implementing dozens of shell features (aliases, process substitution, printf, ...) with Python-based DSLs.
2. The red line is step 3 above. We're translating this high-level interpreter to fast C++.

In other words, the blue line goes from the "middle languages" up to shell, and the red line goes down to C++.

We're implementing Oil middle out!

Caveats

Does it look like Oil is almost done? The red line is converging on the blue line.

Not quite. Here's a summary of caveats I've mentioned in the past:

1. The garbage collector works on small examples, but it it's not yet hooked up to oil-native. That is, the blue line tests the dumb_alloc variant, an interpreter that doesn't reclaim any memory. This obviously needs to be fixed.
2. These spec tests measure OSH only. None of the tests for the Oil language pass under oil-native.
3. Finishing the translation will involve a long tail of fixes. I expect the progress to slow down as the red line converges on the blue line.

However, we don't slide backwards. I like implementing a feature in Python and having it work "for free" in fast C++. The "middle out" strategy is pleasant in this respect!

Fallow Period

The gray rectangle highlights that the red line barely went up for a year — from summer 2020 to summer 2021.

What was I doing then? Working on the other 6 parts of the project, including the Oil language and the garbage collector. A sample of work:

• Big Changes to the Oil Language (October 2020)
• More Changes to Oil's Syntax (November)
• Proposed Changes to Oil's Syntax
• Changes to Shell Runtime Semantics
• Release of Oil 0.8.8 (March 2021)
• Oil Doesn't Require Quoting Everywhere (April)
• Release of Oil 0.8.9
• Notes on the HotOS Unix Shell Panel (June) describes important work on the headless shell. This simultaneously reduces the scope of the project and opens it up to contribution and extension.
• Recent Progress on the Oil Language
• Release of Oil 0.8.12 (July)

So clearly the project is bottlenecked and should be parallelized. We need someone to work on the bottom half of the project while we work on the top half. These are largely separate tasks, requiring different skills.

(We've had several new contributors recently, who I'll acknowledge in release notes.)

Oil 0.9.9 Made a Big Leap

After another fallow period, I resumed work on translation last week. This generally involves a mix of the following:

• Adding type annotations to our Python code.
• Refactoring it so that type annotations are possible.
• Enhancing or fixing mycpp so that it generates the desired C++ code.
• Enhancing or fixing the C++ runtime and OS bindings.

In less than 4 days, we went from 1137 passing tests in Oil 0.9.8 to 1487 — the big leap in the red line. This is huge progress toward the blue line, which sits at 1774. I then released Oil 0.9.9.

Making these tests pass involved only 6 or 7 fixes, almost all in C++ code. One example is simply removing assert(0) stubs I had put in for library calls like posix::write() and posix::strerror(). The next post could show more details.

So recent progress gives me additional confidence that this approach will work.

Compiler Engineer Wanted

I just updated this page:

• https://github.com/oilshell/oil/wiki/Compiler-Engineer-Job

Here's a summary of skills sought, in order of importance:

1. Hard-won C++ experience, including knowledge of portability.
2. Understanding of garbage collectors.
3. Comfort with a test-driven and terminal-based workflow. We need to make the red line go up!
4. Understanding of static type systems.
5. Python. (This can likely be learned on the job.)

General attributes:

1. You should be a finisher. This is a project that needs a solid engineer. It's not a research project!
2. Good communication skills. We should be able to talk and write about technical designs and coding strategies.
3. You should be generally interested in the goals of the Oil project. If you want to use Oil in the future, this work should be fun!

Funding In Progress

I'm mentioning this job "softly" because it's not fully funded yet. We were recently approved for Github Sponsors, and I'm waiting to hear back on an NLnet grant application (after a short round of questions).

My goal is to find the best person (or people) for the job, regardless of their compensation requirements. I've set the Github sponsors goal at $25K / month, but I need your feedback on whether that can be achieved, and how it should be allocated.

One possibility is to spend $5K or so on "bounties" to make the red line go up. Perhaps the best candidate will emerge out of that process.

I also want to hire a technical writer, but let's do one thing at a time.

Five Ways You Can Help

I don't enjoy administrative work like fundraising and hiring. I prefer improving Oil (#project-updates) and writing technical blog posts (e.g. #parsing).

So honestly I would like to "offload" some of this work to users and readers. If you want a new shell, this could be one of the best uses of your time!

(1) Tell Your Friends and Coworkers About the Project.

This blog has several thousand technical readers, but there are millions of people who use shell.

• Maybe your coworker is struggling with shell and YAML, and would be interested in reading about a new shell.
• Do anyone you know that fits the description of the compiler engineer?

(2) Help Raise Funds

• Point your friends and coworkers to our Github sponsors page. Explain in your own words why it's worthwhile — but only IF you think it's worthwhile.
• Share blog posts you like on social media, since I generally don't.
  • I probably should improve our profiles, and we need a logo.
• Tell me what I'm doing wrong! Especially if you have experience with similar fundraising.

(3) Donate to Help Pay the Compiler Engineer

Are you employed in the software industry? Do you spend more than an hour a month with shell? Then it's possible that donating $25/month or $100/month will pay for itself in the future by saving you time.

You can get a sponsor badge on your Github profile for just $10/month.

Remember, Oil is our upgrade path from bash to a better language and runtime. It's the only such project out of dozens of alternative shells.

I also set up $200/month and $2000/month tiers if you'd like your logo to appear on this website.

(4) Apply For the Job

If you have the time and the skills, you should apply!

Please contact me at andy@oilshell.org or on Zulip. It may take awhile to find the right person, but introducing yourself never hurts.

If you can make one new spec test pass (with my help), then you'll jump to the front of the queue. This is a very mechanical process. Start with the README.md and Contributing.

(5) Contribute to Oil's Code

I hope that you will keep contributing to the top half of Oil's code even if we meet our $25K/month goal.

Readers have offered to send me donations in the past, but I've declined. The reason is that I want to keep all contributors on equal footing. I don't want there to be "two tiers".

For the same reason, even with this fundraising project, I'm not personally accepting any money. Think of me as a "coordinator".

I'm accepting the reality that we need a specialized skill set that's not likely to show up in volunteer contributions. The garbage collector and type system work requires "global" and concentrated design knowledge.

In other words, I want to wall off the paid part of the project:

• Work on the lower half can be paid for. It may last for a year or two.
• The top half is a collaborative open source project run by volunteers, and I hope it will last a long time.

What Doesn't Help

The last section described 5 ways you can help. At the risk of being negative, I will insert a rude slogan here: Uninformed back-seat driving doesn't help get the shell done! Let me elaborate on this :-)

This is the first time I've called our strategy "middle out", but I've covered the similar topics in the past, including during an early "wrong turn". (Summary: OPy won't be fast enough, and we won't reuse any part of the Python interpreter.)

But here's what often happens when I write about Oil's implementation: commenters derail the thread by proposing solutions that they haven't tried.

For example, when I set up the oil-dev@ mailing list in 2017 (now Zulip), one of the first messages was "Ewww C++" (yes really).

This annoyed me, but now I see it more positively. What I hear now is I'm interested in contributing to Oil but I don't know C++. So it's a form of interest that's low effort, but flattering.

Another comment I often get is: Why not PyPy or Cython?

I've answered these questions in past threads, and will try to write detailed posts on them in the future. Some relevant issues are:

• Build-time and runtime dependencies. Shell has an unusual place in the OS.
• System bootstrapping, and the hardware view of narrow waists. You may be biased toward the software view.
• Python's runtime
• Go's threaded runtime
• fork(), libc, signals
• Graph data structures and memory management
• Algebraic data types, variants as types
• ... and more

Notes for the curious: Why Isn't Oil Written in Rust, D, Nim, etc.? (Zulip)

More things to keep in mind:

• I arrived at this approach after a lot of experimentation, feedback, and positive signals (like the spec tests above).
• The goal is to avoid writing much C or C++ by hand. In contrast, all POSIX-compatible shells are hand-written in C (bash, dash, zsh, busybox, ...).

You could say that the job of the compiler engineer is to work on the unsafe core of the project. An implementation of a garbage collector is inherently unsafe because its job is largely to manipulate raw memory.

But the interpreter that uses it must be 100% statically typed (with MyPy) before it can be translated to C++. And the generated C++ is memory safe by virtue of garbage collection. It's impossible to express bugs like use-after-free or double-free in the source language!

So please refrain from low effort comments until I write those posts. I will simply reply with a link to this section.

On the other hand:

• I thought I would be able to finish this project by myself, and I feel bad that I can't. I need to ask for help. But it's better for users if the project has more hands in it.
• I appreciate ideas based on concrete experience, and many readers have helped in the past. The appendix mentions that I want to specifically thank many of the 51 contributors over the years. This project is fun because it involves a lot of learning.
• I don't claim this is the only way to do it. I have a rather strict view of the design requirements that you may not share. So I encourage parallel efforts outside Oil's codebase. This has been attempted, and isn't theoretical!

Conclusion

To summarize:

• I want to work on the top half of Oil — the language design, builtins, interactive shell, and documentation.
• I want you to donate money to pay someone to work on the bottom half of Oil.
  • The goal is to raise $25K/month. This is the compensation of one engineer at a "big tech" company in Silicon Valley (where I used to work). I'm not sure we need to pay this much, but I don't want the solution to be constrained by money. I want to be respectful of both sides as the "coordinator".
  • I will try to facilitate this with blog posts, but I'm not sure it will work. So I also want you to think about what you can do to make it happen. You might have the right skills or know people with them! This could be even more helpful than donating.

Does this post make sense? I expect it will help some readers understand the project, but others will still question the motivation. I agree it's somewhat unusual, but as I wrote recently: if you want a different result, you have to do something different.

Please ask questions in the comments, and feel free to make suggestions about fundraising, which I know little about. I'll use my answers to inform future blog posts.

Appendices

HBO's Silicon Valley

"Middle Out" is also used to describe the compression algorithm by fictional Silicon Valley startup Pied Piper (2014).

This is where I first heard the term. I thought it was invented by writers — a play on the common computer science terms "top-down" and "bottom-up". But then I found it in Ward's 1994 paper on Language-Oriented Programming!

You can think of it either way :-)

More Writing on "Middle Out" and Translation

As mentioned, I want to write a FAQ about implementation alternatives:

• Why C++? Why not Rust, Go, D, Nim, etc.?
• Why not PyPy or Cython?
  • The short answer is that each of the dozens of Python compilers has a hard tradeoff between how much code they understand and how fast the output is. mycpp is at the extreme right of the spectrum: it understands a very limited subset of Python, but the output is fast and predictable.
• Why not use LLVM or Boehm GC?

More on the implementation:

• Shell's Implementation Language Has Always Been a Problem
  • This post is based on a 2015 talk by Bourne Shell creator Stephen Bourne. Issues: longjmp() control flow, memory management, signals, and more.
  • And a quote about Lisp and exceptions in the bash source code.
• Open Source Is Long Distance Collaboration Over Long Time Frames
  • mycpp is a hybrid between the recent mypyc compiler and the old Shed Skin compiler.
  • Zephyr ASDL, OPy, and more
• Zulip: Implementation Language FAQ

And:

• Thanks for Years of Oil Contributions. Contributors have come and gone, but they've moved the project forward in important ways, and taught me things I didn't know.
• Zulip: Fundraising Blog Topics