by chubot | 2025-05-06 23:57:09+00:00
Good question -- at first I thought we would use an arena, at least for the parser. But we ended up writing a garbage collector for the subset of C++ we generate!

That was completed in 2023: Pictures of a Working Garbage Collector

https://www.oilshell.org/blog/2023/01/garbage-collector.html

https://news.ycombinator.com/item?id=34350260

There are two reasons to have a GC:

(1) The AST (aka "lossless syntax tree") is actually GRAPH - it is useful to share nodes.

I think graphs are fairly common for ASTs. Once a node can have multiple parents, then ownership becomes less clear, and errors using arenas can easily cause memory safety bugs.

For example, in Rust, I think you start using Rc<T> and so forth, which is automatic memory management at runtime.

(2) YSH is part of Oils, and it has nested dicts and lists like Python and JavaScript.

Once you have nested dicts and lists, you need GC. We actually have the GC at the "meta-level", and that (somewhat surprisingly) saves a ton of code and bugs.

It's like writing a Python/Ruby interpreter in Java or Go, and re-using the platform GC, rather than writing one specific to your language.

In particular, we don't have GC rooting, ownership, or anything like Py_INCREF/DECREF littered all over the codebase. This makes our implementation like an executable spec!

And that makes it very easy to contribute -- you write typed Python, and it's as fast as shells written in C. I think it's the best of both worlds

---

Something I've pointed out over the years, and which many people find illuminating, is

- bash doesn't have nested maps and arrays -- it only has flat ones. Therefore it doesn't need GC

- awk too - it doesn't need GC, because its data structures are limited - https://news.ycombinator.com/item?id=28785732

- make and cmake too.

I put all these "weak glue" languages in the "string-ish" category. In contrast, YSH gains A LOT of power from having real data structures, and that requires GC.

(Writing a GC was the hardest part of the project -- I think sh/awk/make/cmake left it out for a reason! Even nushell has no GC I believe. fish lacks a GC too.)

YSH has more of the power of Python/JS/Ruby, which if you look at it historically, did "replace" shell and awk for a huge set of problems. (Guido van Rossum specifically mentioned the "hole" between shell and C as a motivation for Python.)

Garbage Collection Makes YSH Different - https://www.oilshell.org/blog/2024/09/gc.html

---

On a different note, if anyone really wants a shell buildable with the Rust toolchain, it would be worthwhile to TRANSLATE Oils to Rust. This will definitely work, because Oils is translated to C++ (completed in early 2024).

You would have to write the runtime, which is around 4K lines for the garbage collector, and 4K lines for the OS bindings. That's a lot easier than writing a bash-compatible shell.

That is, Oils has about 8K lines of hand-written C++ code. Compare with bash which is 162K+ lines of C written from scratch -- it's 20x less.

I think 8K lines of unsafe code is also comparable to Rust binaries. e.g. prior to ~2018, Rust binaries used dlmalloc by default, which is 20-30K lines of C code.

(What's important is that almost all PRs modify safe code only -- it is very easy to review typed Python)

This would be a fun exercise for anybody interested in writing a GC in Rust (which is a hard challenge, with many nontrivial choices). You can write a GC, and get a shell for free, etc.

---

Also, Brush and nushell are different projects ... Oils has both things -- OSH and YSH -- compatible and new

So you actually get 2 shells for free by doing that :-P The "executable spec" strategy took a long time, but it actually worked!