How can we do this from within the LÖVE app? So there's nothing to install?

This is a story about a hundred lines of code that do it. I'm probably not the first to discover the trick, but I hadn't seen it before and it feels a bit magical.

Read more ]]> http://akkartik.name/post/freewheeling Tue, 23 May 2023 09:03:45 PDT http://akkartik.name/post/freewheeling A 15-minute manifesto (video and transcript) on lessons learned trying to build situated software for a year. ]]> http://akkartik.name/post/roundup22 Thu, 29 Dec 2022 17:56:32 PST http://akkartik.name/post/roundup22 Over the course of 2022, I've found myself gradually programming in a certain way that has been working really well. Here, let me show you a few examples, see if you can spot the pattern:

1. A plain-text editor where you can also draw line drawings.

   

   Minimal dependencies, easy to build, runs anywhere you can install apps without asking permission, thoroughly tested, designed above all to reward curiosity about its internals.

2. A different way to draw polygons. Old way:

   

   New way:

   

   First of a sprawling family tree of over a dozen forks of the original editor.

   

   (Image drawn using itself, of course.)

3. The Pong fork. Baking the editing environment into other apps for a self-contained curiosity-rewarding/forking experience.

   (Notice the extensible graphical logs. It takes very little code to augment debug-by-print. This work stemmed from the Handmade Network Wheel Reinvention Jam)

4. Using the editing environment to debug the editing environment. (More tools should support a command palette; it's the best of commandline and GUI worlds.)

   

5. Pivot: making changes to programs as they run. They maintain state even after a crash (the red error on the left).

6. LuaML, a box model over an infinite 2D surface that you can pan and zoom without restriction. Built in the live style, of course.

   (You can edit each text widget, and scrolling within a widget pans the whole surface. This took me a couple of tries to boil down to a reasonably elegant implementation.)

7. Pulling LuaML “into the left window,” the editing environment.

I've found myself calling these freewheeling apps to myself. They're freewheeling in two ways. First, they're easy to get started with so you can be off doing your thing. Second, they stay freewheeling over time. They don't cramp your style with constraints after you've gotten suckered into adopting them.

Replace “I” with yourself, dear reader. These apps should work anywhere (except mobile platforms), be easy to try out, easy to edit in place, and easy to subvert if you dislike a design choice. I'm going to continue improving the hacking experience, and I want to support forks in staying up to date with my changes. Unfortunately they require a little bit of programming experience for now (particularly git), but it should all seem pretty familiar regardless of what languages and tools you've used in the past. And if they don't, feel free to reach out. I welcome questions.

Coda

A lot of the bang here comes from the stack I'm using: the Lua programming language and the LÖVE game engine for Lua. You don't have to use Lua and LÖVE to be freewheeling, I think, any parsimonious stack designed to be portable and easy to build will do. But if you have another candidate that meets those criteria, I'd like to see it.

Regardless, the first Peter Hamilton I read, Pandora's Star, still sticks with me for a motif that didn't come together until right at the end: the Silfen Paths. In this universe humanity has portals that can span light years, often conveying train service between star systems, but there are occasional legends of an older interstellar network by an ancient alien civilization. Needless to say, our intrepid protagonist manages to get on this network. And suffers years of privation and amazing adventures (while everyone else in the novel is moving the story forward) before coming out the other end. Unlike the portals created by humans, the Silfen paths don't contain abrupt transitions between two points in space. Things blend together more gradually. Also unlike portals, the Silfen Paths aren't in the traveller's control. Instead, to go forth on the paths is to open oneself to the new, the unexpected. Extreme heat and cold. Danger. The occasional prancing Silfen who'll happen upon you and help you out, but who doesn't quite seem to get the idea of “home,” or that you're trying to get there, before outpacing you again, inevitably leaving you behind to find your own path through the maze.

If I could go back in time and give my younger self a message, it would be to spend more time reading linearly through guided documentation. After growing up falling asleep on textbooks, the interactive and random-access nature of computers was a great learning aid. And yet, somewhere along the way, I started to rely far too much on the crutch of just Googling for my immediate problem. Many times I prematurely dismissed painstakingly written documentation while bemoaning how poorly documented everything was. Everything wasn't set up just right for me — because it can't ever be. And by taking too often the easy portal out, I was being inefficient with the opportunities for learning that were coming my way. Just because they seemed inefficient for my task at the time, something seemingly all-important that I forgot about the next day as I went dancing on my way.

I consider rereading Pandora's star every once in a while. I'm sure it'll happen eventually. But I'm equally sure I'll skip all the interminable interludes about the Silfen Paths, now that I know where they end. Just reading about someone so out of control is more than my pampered, twentieth-century, low-attention-span, summer-child self can handle. It almost got me to give up on the book the first time around. And yet, I cherish my one time walking the Silfen Paths in my imagination. I did learn something.

For an eternal-seeming few years fifteen years ago, there was a frequent debate about the value of comments in a blog. On one side: blogs are meant to be interactive! On the other: why do I need teenagers tramping through my homestead? If you have something to say, get your own damn blog! With the perspective of hindsight, it's apparent who inherited the earth. Blogs largely are the preserve of the few, and even the few committed bloggers that remain have to go out to find readers on the street, the curbside, the microblog, where everything is a comment. You can't get others to read you without giving them the opportunity to appropriate you with a pin, a bookmark or a retweet.

Have we noticed yet that our blogs are now just as disintermediated from our readers as the mainstream newspapers whose disintermediation we celebrated? “Comments are dead,” blogs proclaimed. But comments didn't die, they became the whole platform.

It's a grave decision, where you draw boundaries between pages on a website. Every link is a portal, a beginning, an opportunity for a search engine or microblogger to start a cowpath. With that in mind, I'm trying something new, the guided tour for Mu. Ironically, it atomizes my previous docs by linking repeatedly into anchors in the middle of pages. Proceed if you dare. ]]> http://akkartik.name/post/neighborhood Sun, 13 Jun 2021 14:54:27 PDT http://akkartik.name/post/neighborhood My goal for Mu is software that is accountable to the people it affects. But it's been difficult to talk to people about Mu's goals because of the sheer number of projects that use similar words but lead to very different priorities and actions. Some of these I like to be associated with, some not so much.

if you care about making software accountable

There are two ways to describe the provenance of software: in terms of the people who made it or checked it out, and in terms of its internals. The two ways are often described with similar-sounding words.

On one hand, trust chaining is a way to transform trust in one person into trust in another.

Trust chaining is also used to transform trust in people into trust in artifacts. Performing arithmetic on an artifact to verify a trust relationship such as "person X owns this signature".

On the other hand, proofs convey an argument to a reader and let the reader assess how objective and ironclad it is without needing to trust the author.

Automated proofs can be checked by a computer, but are still amenable to human readers. (Beyond automated proofs, zero-knowledge proofs are more about verification. Conveying ownership of artifacts rather than objectivity of knowledge. That way lie ideas like proof of work. I want to exclude these from my preferred notion of 'proof'. Let me know if you can think of a clearer word than 'proof' for my desired category.)

Trusted computing uses trust chaining to shackle a software stack to some distant server running some arbitrary software. (more details)

Reproducible builds are about getting some arbitrary set of software to generate deterministic output given identical input. The build recipe acts as a proof that a binary was generated from it.

Bootstrappable builds are about making all the software needed for a program available for auditing. Including all the software needed to build it, and all the software needed to build that, and so on. The build recipe acts as a proof that source code for the entire supply chain is available for auditing.

(Bootstrapping is about getting a compiler to build its own source code. Such a similar term, so anthithetical to bootstrappable builds.)

Collaborative code review is about getting people to sign off on software packages once source code is available. There's no proof here, but it becomes possible to verify that some people inspected sources and found no major issues.

Problems in this category:

• people make mistakes; I want to verify not just what people think, but why
• stacks currently grow complex faster than attempts to make them auditable
• auditability doesn't help answer people's questions about why a piece of software does something seemingly questionable

Even so:

• some auditability is a vast improvement over none
• auditability is vastly more important for the lowest levels of the stack, where it's more tractable to obtain

if you care about bringing software closer to the people it affects

Minimalism is about building simple programs with as little code as possible, starting from some arbitrary set of software. (example example example)

Malleable software or end-user programming is about building programs to be as easy to change as they are to use. Building atop some arbitrary set of software.

Problems in this category:

• things (example) are often not minimal or simple if you get into details (example)
• to permit open-ended changes you have to take control of more and more of the stack (example)
• minimal software has a constant temptation to grow less minimal over time (example)

Even so:

• they can deliver a great deal of capability even if they're not perfect

editorializing

I care about software that is accountable to the people it affects. Both sides matter.

The word 'trust' provides cover for a large amount of bad behavior. A trusted platform module provides trust to large companies about the hardware their "intellectual property" runs on. It does not provide trust to the individual people whose computers it inhabits.

Proofs work better than some cryptographic sign-off. If a trust relationship is found to have a problem, it must be revoked wholesale. Repeated revocations reduce confidence. If a proof is found to have a problem, it's usually easy to patch. There are enough details to determine if things are improving.

Trust relationships can change. Habits can be hard to change. That contrast implies that the result of an audit cannot be binary. It is untenable to tell people to stop using software that grows abusive. When software does something a person dislikes, they should be able to 1. find the sources, 2. build the sources, 3. modify the sources at any level of granularity, and 4. feel confident in the results of their actions.

It's important that this be an incremental process. Minor tweaks in response to minor dissatisfactions aren't just first-world problems. Going through all four steps for something minor creates confidence that one will be prepared when major changes are needed.

Size matters. It can take surprisingly little code to lose this property of incremental accountability.

The number of zones of ownership matters. You can make incrementally accountable software by relying on others, but not too many others. Minimizing the dependency tree may well be more important than minimizing lines of code.

Mu is reproducible, auditable and almost entirely incrementally accountable (property 3. above hasn't been stress-tested much and so remains a work in progress). I flatter myself that it's difficult to ask "why" questions in the form of code changes without triggering a failing test or other error message that answers them.

However, Mu too has problems:

• I have to do without many things at the moment: network support, concurrency, files, pointing device, performance, etc., etc.
• it's unclear if this way leads to any program anybody else would find useful enough to want to modify

Even so:

• if it's hard to create incrementally accountable software, perhaps we shouldn't be relying on software so much

Conclusion

It's worth thinking about different pieces of software in terms of what you give up when using them. Some points of comparison:

• Most software: Memory safety (either directly or in build dependencies), reproducible builds, auditable builds, incremental accountability.
• The suckless school: Memory safety, reproducible builds, auditable builds, incremental accountability.
• Rust: reproducible builds, auditable builds, incremental accountability.
• bootstrappable: Memory safety, incremental accountability.
• Uxn: Memory safety, large screen, lots of RAM, reproducible builds. (Incremental accountability seems less important when programs are so tiny.)
• Mu on Linux: Graphics, some memory safety and incremental accountability (Linux dependency), portability
• Mu: Networking, concurrency, files, performance, portability.

Thank you for reading. Here's a screenshot of a Mu program I made for my kids today: "chessboard with rainbows".

(This post was inspired by Ribbonfarm's periodic maps.)

comments

  

Tristan Kromer #BlackLivesMatter, 2021-07-04: I notice you never use the word transparency. Does the program make clear to the user what it is doing at all times?

This is a little different from auditable. Eg, I would prefer a webcam hardwired with a light to show when it is powered on vs a webcam where I could inspect it to determine the status, but that requires my curiosity and effort.   

  

Kartik Agaram, 2021-07-04: It's a good question. I was enamored with 'transparency' a year ago but dropped it because of associations with stuff like https://www.computer.org/csdl/magazine/cs/2017/01/mcs2017010005/13rRUxC0SLw. People often use 'transparency' to mean 'invisible,' which is the opposite of what I mean. So it's been challenging to carve out an unpolluted term.

The distinction you make is also important. A device can only have a limited number of lights and dials, and I don't have much to contribute regarding what to use them for. It feels like a plenty hard problem just to provide all the data somewhere so that others can decide what to highlight.

  

Anonymous, 2021-09-04: I liked "habitable" http://akkartik.name/post/habitability.   

  

Anonymous, 2021-09-04: PS: Similar ontological analysis from earlier this year: https://news.ycombinator.com/item?id=25458080   

  

Kartik Agaram, 2021-09-04: Thanks! That's a good point.

Is that comment by you? I just want to clarify that http://akkartik.name/post/habitability is not written by me. It's a long quote from an essay by Richard Gabriel.   

  

Anonymous, 2021-09-13: > Is that comment by you?

Yes.

> /post/habitability is [...] a long quote from an essay by Richard Gabriel

Yes, but it's a nice descriptor.

Or maybe we should be bold enough to synthesize our own word. "hactile software"? (*hack* + *tactile* = *hactile*; something that exhibits the quality is said to have *hactility*) Too corny?   

  

Kartik Agaram, 2021-09-13: :) I love that you brought up tactile. Here's something from Mu's Readme several iterations ago:

> Trading off notational convenience for tests may seem regressive, but I suspect high-level languages aren't particularly helpful in understanding large codebases. No matter how good a notation is, it can only let you see a tiny fraction of a large program at a time. Logs, on the other hand, can let you zoom out and take in an entire *run* at a glance, making them a superior unit of comprehension. If I'm right, it makes sense to prioritize the right *tactile* interface for working with and getting feedback on large programs before we invest in the *visual* tools for making them concise.

(From November 2014 to March 2016)   

Kartik Agaram, 2021-09-13: Last week's exchange has had me mulling an update to this post. In particular, I now see Mu's neighborhood as more pronouncedly bilobed, between habitability and auditability. (I think both benefit from increased tactility?)

In the process, I was also reminded of another fount of neighbors on the habitability side: the literature on tailorable software in the 90's, as described in chapter 2 of Philip Tchernavskij's thesis.

It seems to me that modern computers trap people in a vicious cycle. Compatibility guarantees breed complexity over time as the world changes. Complexity is managed by introducing layers of abstraction. Abstractions introduce new compatibility guarantees. Over the decades this vicious cycle leads to even professional programmers understanding only a tiny fraction of the software infrastructure that runs their computers. As a result, our world is increasingly captured by software that is unaccountable to people.

For several years now I've had a vision for a computer that allows anyone to audit its inner workings, where any operation can be decomposed strictly into a parsimonious combination of simpler operations, terminating without cyclic dependencies or circular reasoning at some ground level. Ideally it would do this in a way that rewards curiosity, leading to a virtuous cycle where an order of magnitude more people grow to understand how their computer works as they use it.

Nowhere in this picture are compatibility guarantees, version numbers or forced upgrades. At any point your computer should be internally consistent and free of known historical accidents. Even if this means upgrades are more work and so more infrequent, and that our computers must be slower. Or do less. That seems like a worthwhile trade for a more sustainable world.

At the start of 2020 the state of the Mu computer looked like this:

The blue stack on the left was my current computer, without changes. The stack on the right was a better computer using some existing pieces (blue) and some new pieces (red). The arrow between the stacks was like a wormhole between worlds. I was using the existing world to build the new world, but the idea was for the new world to be self-sufficient once it was set up.

At the end of 2020, more details of the picture are becoming clear:

I now have a self-sufficient computer in the middle stack that can rebuild itself without needing much mainstream software. Since its focus is on building itself, the currency of the realm is streams of text. An existing Linux kernel provides clean primitives for operating on streams of text over stdin/stdout. Beyond that the Mu computer fends for itself. It even has a shell, though it doesn't look anything like Unix has taught us to expect:

It's a live-updating postfix environment entirely in text mode that shows the top-level evolution of your computation (including side-effects in little fake screens) at a glance, where you can drill down into any function call when you need more details. Check out the 15 two-minute demos I made in 2020.

I don't represent size and complexity in my pictures above. The mainstream stack running on our computers contains hundreds of millions of lines of code, and would look like a ball of spaghetti if we zoomed into the connections between levels. The middle stack requires twelve million lines for the Linux kernel, but aside from that weighs in at 50k lines of straight-line dependencies, most of them mapping to individual instructions of machine code, two thirds of which are comments or automated tests. (It does a lot less, of course. The goal is to start with a sustainable stack and then preserve sustainability properties as we thoughtfully add functionality.) Finally, the final and most nascent stack on the right gets rid of the twelve million lines of Linux, and can do even less at the moment. All it can do is draw pixels on the screen and process keystrokes.

• No wifi, no networking.
• No file system yet, just sectors on a local disk.
• No multitouch, no touchscreen, no mouse, not even any shift key support yet.
• No graphics acceleration, no fonts, no way to print text.
• No virtual memory, no GC, not even any memory reclamation yet.

But it's a start. A moderately sized screen, a keyboard, gigabytes of RAM and a guarantee of memory-safety. Let's see where 2021 leads.

(Initial revision on Mastodon.) ]]> http://akkartik.name/post/convivial-computing Sun, 15 Mar 2020 22:23:46 PDT http://akkartik.name/post/convivial-computing Over the last few months I've written up in one place the entire argument for—and comprehensive description of—what I've been working on since 2014. It will be published in the proceedings of the Convivial Computing Salon. From the call for submissions:

In Tools for Conviviality [1973], Ivan Illich said, “I choose the term ‘conviviality’ to designate the opposite of industrial productivity… Tools foster conviviality to the extent to which they can be easily used, by anybody, as often or as seldom as desired, for the accomplishment of a purpose chosen by the user… People need new tools to work with rather than tools that work ‘for’ them.”

We were promised bicycles for the mind, but we got aircraft carriers instead. We believe Illich’s critique of the damage to society from technology escalation offers a fresh perspective from which to discuss the pathologies of modern software development, and to seek better alternatives.

An inspiring theme. My response: “Bicycles for the mind have to be see-through.” Get it? When I look over at my bicycle I can see right through its frame. I can take in at a glance how the mechanism works, how the pedals connect up with the wheels, and how the wheels connect up with the brakes. And yet, when we try to build bicycles for the mind, we resort to “hiding” and “abstraction”. I think this analogy has a lot more power than we credit, a lot more wisdom to impart if we only let it in. I think conviviality requires tools with exposed mechanisms that reward curiosity.

I've been trying to falsify this hypothesis for 6 years. There are still large gaps to investigate, but so far it's holding up. Read on → [pdf; 25 pages] ]]> http://akkartik.name/post/mu-2019-2 Tue, 15 Oct 2019 15:18:14 PDT http://akkartik.name/post/mu-2019-2 In the previous post, I described what my new hobbyist computing stack looks like today, and how the design decisions seemed to accumulate inevitably from a small set of axiomatic goals. In this post I describe some (far more speculative) future plans for Mu and try to articulate how the design process continues to seem pre-ordained.

(Many of the sections below outline constraints before describing a design that mostly fits them. This flow is inspired by Christopher Alexander's “Notes on the synthesis of form”.)

To recap, I plan 3 levels of languages for Mu:

• Level 1 (SubX): just the processor's instruction set with some syntax sugar
• Level 2 (Mu): a memory-safe language
• Level 3 (TBD): an expressive high-level language

So far Mu has just level 1 (described in the prequel). After writing 30k LoC in level 1, the thing I miss most is the safety of a higher-level language. In particular, memory safety. I repeatedly make the following kinds of errors:

1. I allocate local variables on the stack but forget to clean them up before returning.

2. I accidentally clobber a register in a function without first saving the caller's version of it.

3. I accidentally clobber memory outside the bounds of an array.

4. I accidentally continue to hold on to a heap allocation after I've freed it.

The first two are problems that C solves. The latter two are not. Accordingly, level 2 will have some similarity with C but also major differences. Like C's original goals, it's intended to be easy to translate to native machine code. Unlike C, however:

• It is intended to remain easy to translate over time. C compilers have optimization passes that have grown ever more complex and sophisticated over time in a search for higher performance. Mu is intended to never have an optimizer.

• It is intended to always be built out of lower level languages. This imposes some tight constraints on the number of features it can have.

• Performance is not a priority. I want to make it safe before I make it fast. In particular, to keep the translation simple, I'm willing to use run-time checks for things like out-of-bounds memory access.

• To keep the translation simple, I give up mathematical notation. You won't be able to say things like `a + b*c` (that C compilers then need CSE to optimize).

Since the compiler won't optimize code, not just in the initial phase but ever, the language should allow the programmer complete control over performance. It won't let you write utterly unsafe code (bump down to machine code for that), but it shouldn't introduce gratuitous overheads when emitting machine code. C started out simple to translate, but gained declarative keywords like inline and register over time. I want to push much harder than C on being easy to translate. For the most part there should be a 1-to-1 mapping between statements and x86 instructions. Just with more safety.

‘Compiling’ feels too pompous a word for this process. Let's call it just ‘translating’ instead. And it turns out to be surprisingly constraining. If you start out with the goals stated above about the target instruction set and how parsimonious the translation process needs to be, there seems to be exactly one core language you can end up with.

Ingredients

As hinted above, the language has to be exclusively statement-oriented. While I prefer the syntax of purely expression-oriented languages, that's something to build higher up in Mu. Not having to translate expressions to statements avoids the need to detect common sub-expressions and so on.

I said above that I want instructions to map 1:1 to instructions. The x86 instruction set doesn't allow instructions to access more than one memory location. The simplest way to work with this restriction is to make registers explicit in our code, so that they're a constant consideration for the programmer. Mu will be a manually register-allocated language. It will still check your register allocation and flag an error if multiple variables overlap on the same register. But it's up to the programmer to manage registers and spill to memory when necessary. The good news: the programmer can really optimize register use when it matters.

x/eax # variable x is stored in register eax
x # variable x is stored in memory

The language will specify types of variables. The translator need only compare the input and output types of each statement in isolation.

Types allow restrictions to instructions to support memory safety. For example, `add` can be restricted to numbers, `index` to arrays, and `get` to records (structs). All three may emit the same instruction in machine code, but the logical semantics allow us to forbid arbitrary pointer arithmetic.

In addition to types, variables can also specify their storage location: whether they're allocated on a register, on the stack or on the data segment. The skeleton of the translator starts to take shape now: after parsing and type-checking, a simple dispatch loop that decides what instruction to emit based on both the operation and where the operands are stored.

The one feature I miss most when programming in machine code is the ability to declare a struct/record type and access record fields rather than numeric offsets. Mu will have user-defined types.

While most Mu code will be translated 1:1 into binary, there will be a handful of situations where instructions are inserted without any counterpart in the sources. The list so far:

• Stack management. When I declare local variables I'd like them to be automatically popped off the stack when exiting scope.
• Checking array bounds. Every index into an array compares with its length. To make this check convenient, all array start with their lengths in Mu.
• Checking pointers into the heap. Heap allocations can be reclaimed, and we want to immediately flag dereferences to stale pointers after they've been reclaimed.

This is the hazy plan. Still lots of details to work out.

Milestones

Here's an outline of the broad milestones planned for Mu's eponymous level-2 language:

• Parse core syntax into some intermediate representation.
• Code-generate just instructions with integer operands, for starters.
• Variable declarations and scopes.
• User-defined types.
• Address types. We probably need them. How to make them safe?
• Addresses on the heap, and how to detect when they're reclaimed.

I'll sketch out the first three in this post, and then go off to build the language with just integers. Once I'm done with it I'll flesh out the rest.

Core syntax

As I said in the previous post, machine code for any processor consists of linear sequences of instructions. These instructions uniformly consist of an operation and some number of operands. Conceptually:

op o1, o2, …

Different processors impose constraints on these operands. In x86 most instructions can take at most two operands. At most one of them can lie in memory, and at most operand can be written to. The constraints are independent; instructions may write to either memory or registers.

Machine code usually requires multiple primitive instructions to perform a call to a user-defined function. It seems useful for primitive operations and calls to user-defined functions to have a uniform syntax.

It would be nice to be able to see at a glance which operands of an instruction are read or written.

Conventional Assembly languages use order to distinguish the output parameter. However they don't support a syntax for function calls.

One potential syntax may be:

o1, o2, … ← op i1, i2, …

However, this scheme doesn't admit a clean place for operands that are both read and written. (We'll call them ‘inout’ operands, extrapolating from ‘input’ and ‘output’.) Inout operands are common in x86 machine code, where you can have at most two operands:

• Add operand o1 to o2;
• subtract o1 from o2;
• compute the bitwise `AND` of o1 and o2, and store the result in o1;
• …and so on.

User-defined functions can also have inout operands. It would be nice to highlight them uniformly.

It would also be nice to see at a glance which operands are in registers, and which are in memory.

However, specifying both input/output and reg/mem properties explicitly for every single operand seems excessive, both for the implementor and for users.

Function calls can pass inputs and outputs either on the stack or in registers. Typically the stack holds only input or inout operands. You could move the return address down to make some extra room to write outputs to. But these stack manipulations take up instructions, and calls would lose a core symmetry: it's easy and useful to check that the amount of data pushed before a call matches the amount of data popped off after.

Function calls can return results in registers, but callers must always know precisely which registers are being written. Separating output registers gives a sense of flexibility that is false.

Finally, registers can't hold types larger than a single word. Larger types need memory, and often they need to allocate this memory. If we assume memory management is manual, it makes functions more self-contained and easy to test if they don't do their own memory allocation. Instead the predominant idiom in C and Assembly is for the caller to be responsible for allocating space for results. The callee simply writes into this space.

That's a lot of constraints, and quite heterogenous! Putting them all together, it seems to me they point toward only one solution:

• Give up on separating inputs from outputs in the general case. C is wise here.

• Highlight output registers of function calls. These are just for documentation and error-checking. As we saw above, you can't mix and match arbitrary registers into the outputs of a call. But it's still nice for the reader to be able to tell at a glance which registers are being modified where, and for the translator to detect when the wrong output register is assumed in a call.

  fn factorial n : int → result/eax : int [
     …
  ]
  # call
  x/eax ← factorial 20  # ok
  x/ecx ← factorial 20  # error
  

• Highlight output registers of primitives:

  x/eax ← copy y
  

  Unlike function calls, primitive instructions can usually write to any register.

• Put inout registers of primitive instructions only on the output. For example adding y to x when x is a register:

  x/eax ← add y
  

• Other than registers, memory addresses written to are really inout. Never put them on the output side. The above two instructions when the destination is not a register:

  copy-to x, y/ecx
  add-to x, y/ecx
  copy-bytes-to x, y # function call
  

  The -to suffix helps indicate which operand is written. It also seems to suggest a convention of putting outputs first. You could use a -from suffix and keep outputs clearly at the end. But what if you have multiple inputs? It seems more common to have a single output.

Code generation

Once we've parsed a core syntax we need to emit code for each instruction. Function calls are straightforward, given pre-existing syntax sugar. In Mu:

o1, o2 <- f i1, i2

In machine code with syntax sugar:

(f i1 i2) # output registers are implied

In machine code without syntax sugar:

push i2
push i1
call f
add 8 bytes to esp

Since each operand is in a separate instruction, it is free to live in a register or memory.

Now for primitives. I'll show a quick sketch of how we translate add instructions to x86 opcodes based on the storage type of their operands. Other instructions will follow similar logic.

The x86 instruction set operates on registers, memory or literals. Data in registers is addressed directly. Data in the stack is accessed in offsets of the stack pointer: `*(esp+n)` where `n` is usually a static value. Global variables are accessed as labels (32-bit addresses). We also capitalize global variables by convention.

Each add instruction takes two operands. Here are the opcodes (and optional sub-opcodes) we care about, from the Intel manual (with optional sub-opcode or subop after the slash):

                                           

	← Source operand →
Destination Operand ↓	Literal	Register	Local	Global
Register	81 /0	01	03	03
Local	81 /0	01	X	X
Global	81 /0	01	X	X

Alternatively, showing where operands are stored (destination first):

reg += literal ⇒ 81 0/subop %reg literal/imm32
stack += literal ⇒ 81 0/subop *(esp+offset) literal/imm32
Global += literal ⇒ 81 0/subop *Global literal/imm32
reg += reg2 ⇒ 01 %reg reg2/r32
stack += reg2 ⇒ 01 *(esp+offset) reg2/r32
Global += reg2 ⇒ 01 *Global reg2/r32
reg += stack ⇒ 03 *(esp+offset) reg/r32
reg += Global ⇒ 03 *Global reg/r32

Other binary operations get translated similarly. (For details on the metadata after slashes, see the section on “Error-checking” in the previous post and the project Readme.)

Variable declarations

Mu needs to be able to declare friendly names for locations in memory or register. How would they work? Again, we'll start with some goals/constraints:

• We'd like to be able to attach types to registers or memory locations, so that errors in writing incompatible values to them can be quickly caught.

• Registers can only hold a word-sized type.

• We shouldn't have to explicitly deallocate variables when exiting a scope.

• We'd like to allocate vars close to their use rather than at the top of a function. Ideally we'd like to support scopes in blocks rather than just for entire function bodies.

• We'd like to be able to exit early and automatically clean up.

• We'd like to avoid unnecessary shadowing. If a variable isn't used anymore it shouldn't need to be restored.

Here's a declaration for a local variable with a type:

var x : int

This gets translated to (⇒)

subtract 4 from esp

You can also initialize a variable with 0's:

var x : int ← 0

⇒

push 0

Variables on the stack (offsets from esp) have a single type for their entire lifetimes.

If you're allocating a variable to a register, you can also turn any instruction writing to a single register into an initialization:

var x/ecx : int ← copy y

It's also fine to read from a register and write to a conceptually new variable in the same register:

var opcode/ecx : int ← and inst/ecx 0xff

While register variables have a single type for their entire lifetimes, it's totally fine for a register to be used by multiple variables of distinct types in a single function or block. Put another way, register variables tend to have shorter lifetimes than variables on the stack.

Variable declarations interact with Mu's {} blocks. Here's a variable allocated on the stack:

{
var x : int ← 0
…
}

This gets translated to (⇒) the following level-1 pseudocode:

{
push 0
…
add 4 to esp
}

Similarly, a variable allocated to a register:

{
var x/ecx : int ← copy y
…
}

⇒

{
push ecx # spill register
ecx ← copy y
…
pop to ecx # restore register
}

(This approach fits a calling convention where all registers are saved by the callee rather than the caller.)

Variables don't always need to be shadowed; sometimes they're safe to clobber. Rather than taking on responsibilities of analyzing lifetimes, Mu provides a single simple rule: the first variable in a register shadows previous values, and subsequent variables to the same register in the same block clobber:

{
var x/ecx : int ← copy y
var z/ecx : int ← …A…
…B…
}

⇒

{
push ecx
ecx ← copy y
ecx ← …A…
…B…
pop to ecx
}

To shadow, create a new inner block.

Early exits should also clean up any variables in a block.

{
var x/ecx : int ← copy y
break-if …A…
…B…
}

⇒

{
push ecx
ecx ← copy y
{
break-if …A…
…B…
}
pop to ecx
}

Early returns are more complicated, because we may need to unwind multiple blocks. The Mu translator is responsible for tracking the size of the stack frame at any point, and updating the stack appropriately before returning.

{
var x/ecx : int ← copy y
return-if …A…
…B…
}

⇒

{
push ecx # spill register
ecx ← copy y
{
break-unless …A…
«increment esp appropriately»
return
}
…B…
pop to ecx # single restore
}

Wrap up

Putting these ideas together, here's what factorial looks like in a bare-bones but type-safe system programming language targeting x86 (supporting only integers so far):

fn factorial n : int → result/eax : int {
# if (n <= 1) return 1
compare n, 1
{
break-if >
return 1
}
# otherwise return n * factorial(n-1)
{
break-if <=
# var tmp = n-1
var tmp/ebx : int ← copy n
decrement tmp
# return n * factorial(tmp)
var tmp2/eax : int ← factorial tmp
result ← multiply n, tmp2
return result
}
}

And here's the level-1 machine code I plan for it to be translated to:

factorial:
# function prologue
55/push-ebp
89/<- %ebp 4/r32/esp
# if (n <= 1) return 1
81 7/subop/compare *(ebp+8)
{
7f/jump-if-greater break/disp8
b8/copy-to-eax 1/imm32
e9/jump $factorial:end/disp32
}
# otherwise return n * factorial(n-1)
{
7e/jump-if-lesser-or-equal break/disp8
# var tmp = n-1
53/push-ebx # spill
8b/-> *(ebp+8) 3/r32/ebx
4b/decrement-ebx
# return n * factorial(tmp)
(factorial %ebx) # → eax
f7 4/subop/multiply-into-eax *(ebp+8)
5b/pop-to-ebx # restore
e9/jump $factorial:end/disp32
}
$factorial:end:
# function epilogue
89/<- %esp 5/r32/ebp
5d/pop-to-ebp
c3/return

This isn't as efficient as what I wrote by hand at the bottom of the previous post, but seems like a realistic translation based on this post.

Ok, time to get to work building it. I'd love to hear suggestions or feedback based on this design, either in the comments below or over email.

comments

  

Peter Van Sandt, 2019-11-22: Interesting to see something that is even more a nicer version of codegen for assembly. I also see how optimizers make programmers less able to reason about the output assembly. Couple of thoughts:

1. Have you considered based in this on SSA or LLVM IR rather than x86 ASM? It might be interesting to see what that would look like if there was a way to write LLVM IR in a way that was designed for humans to write.

2. Mathematical equivalences and fancy bitmasking is pretty hard for humans to come up with for every place that it's needed, and without an optimizer, you lose that. To keep the 1-1 equivalence of code with output, what do you think about an optimizing linter? Something that could complain about areas where your code could be optimized, but not actually do it for you.   

  

Kartik Agaram, 2019-11-22: I like both ideas! An optimizing linter sounds like a great idea, because it goes with the grain of this project: to keep humans in the loop, to encourage them to understand details, and to reward curiosity.

I'd be curious to hear what about LLVM IR you find to be hard for humans to write. It seemed fairly clean when I looked at it. The problem is not so much with the IR syntax itself but with all the myriad design decisions in the implementation that assume it's going to be just compilers emitting the IR.   

  

Anonymous, 2019-12-09: An optimizing linter has the problem of being destructive. It goes like this:

The programmer will write his or her program in a readable way. They'll run it through the compiler, which points out that something can be optimized, the programmer—having already gone through the process of writing the first implementation with all its constraints and other ins and outs fresh in their mind—will slap their head and mutter "of course!", and then replace the original naive implementation with one based on the notes the compiler has given. Chances are high that the result will be less comprehensible to other programmers who come along—or even to the same programmer revisiting their own code 6 months later.

What you really want is something like Knuth's "interactive program-manipulation system". https://cr.yp.to/qhasm/literature.html

The first use case could be doing away with inline concerns that `factorial`'s `tmp2` is a register variable. The original program P would elide storage class annotation altogether (which by default would be understood that it resides on the stack), and then your "transformations that make it efficient" would include specifying that `tmp2` can/should actually live in eax.

I've had a draft post on this topic for a while and just now dumped it on keybase. https://crussell.keybase.pub/drafts/optimization-after-the-fact.markdown?text=1

Also AIUI, "LLVM IR" doesn't actually exist. It's not stable.   

  

Kartik Agaram, 2019-12-09: Very interesting draft, thanks. I ended up favoriting both the Animats comment you linked to as well as its parent thread on Dafny.

Even though I find it more interesting, I don't follow all the intricacies of your verification-side argument (and theirs); I don't have much background in verification yet. But I spent some time thinking about the rewrite system you describe with similarities to Literate Programming and Aspect-Oriented Programming. I haven't been able to come up with a good way to separate a declarative 'spec' from optimizations using these techniques. This is why I'm currently using the hackier approach of a) having lots of tests, and b) gradually building up a complex system across multiple layers. My layers often end up repeating the code of an earlier layer but with greater elaboration. While the repetition is distasteful, it does allow the reader to start with a simpler version at an earlier layer and then separately see how it's optimized. And the tests ensure that the new version continues to pass old constraints in addition to new ones defined alongside it.

Maybe someday I or someone else will be able to replace many of Mu's tests with a verification system of some sort. But for now it's been hard enough to just support these hacks while bootstrapping from machine code.

Over the past year I've been working on a minimal-dependency hobbyist computing stack (everything above the processor) called Mu. The goal is to:

1. build up infrastructure people can enjoy programming on,
2. using as little code as possible, so that people can also hack on the underpinnings, modifying them to suit diverse desires.

Conventional stacks kinda support 1 if you squint, but they punt on 2, so it can take years to understand just one piece of infrastructure (like the C compiler). It looks like nobody understands the entire stack anymore. I'd like Mu to be a stack a single person can hold in their head all at once, and modify in radical ways.

(While it should support understanding everything, you aren't expected to understand everything. Mu tries to reward curiosity, but should get out of the way when you're just trying to get something done.)

One implication of fitting in a single head: Mu constrains the number of supported languages. Languages have a way of growing into isolated universes, and interoperation between languages adds its own complexities. It seems better for future readers if the stack minimizes the number of such boundaries, even if writers are inconvenienced somewhat.

I eventually want to make it easy to swap out one kind of language for another, so that people can program in Lisp-like or Python-like or C-like syntax according to their taste. But regardless of which notations any given Mu computer has, it will be parsimonious in the number of notations readers have to learn to understand and take ownership of a single computer.

Each of these notations needs to be simple enough that it can be implemented out of lower-level notations. The fact that C compilers are written in C contributes a lot of the complexity that makes compilers black magic to most people.

A year in, it's surprising how inevitable the design has seemed. If the journey starts at a specific processor architecture and the goal is to minimize layers of translation above it while paying attention to dependencies, the final destination seems quite inevitable (ignoring minor syntactic choices). This discovery seems worth sharing more broadly, if only so others can prove me wrong and suggest alternative designs.

Outline

Since Mu looks quite different from conventional stacks, I need a few blog posts to cover all the ground. My plan is to give Mu just 3 distinct languages (only the first currently exists; the third is not even planned yet).

• Level 1: just the processor's instruction set with some syntax sugar
• Level 2: a memory-safe language
• Level 3: an expressive high-level language

These levels don't quite map to familiar terms. Level 1 has some attributes of machine code and Assembly. Level 2 has some attributes of Assembly and very high-level languages.

An alternative view of this stack is the primary affordance each level provides:

• Level 1: structured control flow
• Level 2: strong typing
• Level 3: mould the computer to how people think

Each of these affordances requires a global change to the programming model. Within each level I try to keep things as habitable as possible using just local syntax sugar (tools that don't need to understand the entire codebase).

The rest of this post focuses on level 1. The sequel describes a preliminary design for level 2. I won't get to level 3 until I finish building level 2. So far I've written 40k lines of code (LoC) in level 1, and 30k LoC in an earlier prototype that has some resemblance to level 2. Since I want each level to be habitable in isolation, it seems like a good idea to write a decent amount of code in it before moving on to higher levels. (This is a big difference from past approaches to bootstrapping, which try to do as little as possible in each level before jumping to higher levels. The lower levels inevitably end up being hard for newcomers to understand or interactively take apart.)

Level 1: SubX

At the lowest level my goal is to pick a processor and make the experience of programming in raw machine code not completely suck.

I mentioned above that each level builds on levels below, but that's a lie at this level. I don't enjoy editing binary and don't want my readers to have to either. Instead I have an alternative plan, with two prongs:

• A C++ translator that converts a textual format to binary.
• A self-hosted translator that converts the textual format to binary.

The C++ translator is more familiar, but pulls in some gigantic dependencies. The self-hosted translator will look strange but have a tiny codebase and a tiny surface area (just 3 OS syscalls, for example). Both translators will emit identical binaries, which is helpful when debugging the system.

Complete details for how to operate these tools are in the Readme. This post is a quick tour of the major design choices, but if it's interesting you should clone the repo and read the Readme in a text editor. Mu is really intended to be played with interactively, rather than passively read.

Ok, design choices. My computer runs x86, and it's the most open platform I have. So Mu is going to run on x86. It is explicitly not designed to be portable. So we'll start with a quick tour of x86. Here's what you need to know.

The x86 instruction set is 40 years old. It started out as an 8-bit processor, then turned into a 16-bit, 32-bit and now 64-bit processor. It has accumulated hacks and bolted on features over its history. To help it fit in my head, I've chosen a fairly regular subset of x86 for SubX (hence the name), focusing on just 32-bit values (and a couple of instructions for 8-bit bytes so that I can iterate over strings).

Instructions

Machine code for any processor consists of linear sequences of instructions. All the nested block structure and nested calls of higher-level languages are gone by this point. All you have is long lists of instructions with the ability to conditionally skip some subsequences and run some subsequences repeatedly. (Really, instructions are just numbers, so all you have are long sequences of numbers.)

Every instruction in machine code starts with an opcode, some series of bits that specifies which instruction to run. Assembly languages then provide friendly names for opcodes like `add` and `jump`. In a complex instruction set like for the x86 processor, `add` maps to a whole family of opcodes, and there's significant logic to deduce the opcode for an instruction based on its arguments. It also takes a significant amount of code to provide good error messages. There are many reasonable-seeming combinations of operands that x86 doesn't let you add together, and it's hard to compress that knowledge into a short error message tailored to a specific situation.

SubX doesn't provide names for opcodes; you have to use the raw opcodes directly. This eliminates code for translating names to opcodes, and it also enormously simplifies error messages. The programmer needs to work from the list of opcodes, and each error needs to only handle a single case. In practice, this hasn't felt like a major hindrance, because understanding error messages returned by Assemblers often requires understanding the underlying opcodes anyway. I've been finding good error messages to be more valuable than syntactic conveniences. (I'd love feedback on this decision.)

To see the complete list of opcodes supported by SubX at any point in time, type:

$ bootstrap help opcodes

Operands

Each instruction operates on some small number of operands. In x86 instructions can't take more than 2 operands for the most part. Since there are only two operands, and since binary operations like addition are fundamental, most instructions both read and write from one operand:

• Add operand o1 to o2;
• subtract o1 from o2;
• compute the bitwise `AND` of o1 and o2, and store the result in o1;
• …and so on.

Operands may be stored in either registers or memory. Registers are some small number of named (really numbered) locations. The x86 processor has 8:

• eax (0)
• ecx (1)
• edx (2)
• ebx (3)
• esp (4)
• ebp (5)
• esi (6)
• edi (7)

Operands in memory are also usually specified using registers somehow:

• `*eax`: value in memory at address provided in eax
• `*(ecx+4)`: value in memory at address ecx+4
• …and so on.

All this gets turned into numbers, but we don't need the details for this post. Consult the Readme for details.

Error-checking

One big problem programming in raw x86 machine code is that instructions are not all the same size. Instruction boundaries aren't aligned to every 4 bytes, or something like that. The processor is parsing future instruction boundaries as it reads in earlier instructions. It's really easy to accidentally add an extra byte or forget a byte to an instruction. When that happens, bytes that were intended to be opcodes can be interpreted as operands, and vice versa. The program goes silently off the rails, and may not show an error message until much later. The difficulty of debugging such errors is arguably the single biggest obstacle to a good programming experience.

This is the point at which Assembly languages nope out and go build a whole new syntax for themselves, categorizing opcodes into instruction names and so on. Since SubX needs to be self-hosted and every feature in it needs to be programmed in SubX, its solution to this problem is to stay with machine code, but add lots of space for metadata. Here's a sample instruction in SubX:

89/<- 5/rm32/ebp 4/r32/esp # copy esp to ebp 

Instructions lie all on one line. They consist of multiple words separated by whitespace. Each word contains a datum until the first slash. The datum is the only part that makes it into the binary. Everything in a word after the datum and the first slash is metadata. As you see, you can have multiple bits of metadata squirrelled away in a word, all separated by slashes.

Metadata is optional and often ignored, so it's a good place for little comments. However, certain special words for argument types trigger error-checking. In the above instruction, Mu ignores the `/<-` and reads just the ‘89’. However, it knows that opcode 89 expects a `/rm32` and `/r32` argument. If it fails to see one of them in the rest of the instruction, it immediately flags an error. If it sees any of the other known argument types in the instruction when it doesn't expect them—it immediately flags an error. (The register names `/ebp` and `esp` are just comments to aid the reader.)

$ bootstrap translate init.linux examples/ex1.subx -o a.elf
'bb/copy-to-ebx' (copy imm32 to EBX): missing imm32 operand

(The code samples in this post hide some details that aren't important on a first encounter with Mu. I'll elide the actual opcodes further down.)

While this use of metadata is specific to the properties of x86, they're a general mechanism for lots of different checks one may want to apply. I used them in several ways in a previous prototype. I've started to think of the structure of words and metadata as “s-statements”, by analogy with s-expressions. A fairly fundamental uniform syntax that can be used in diverse situations where one doesn't want arbitrary nesting.

Structured programming

As I mentioned above, the primary motivation for the SubX layer is to make working with control flow more ergonomic. The x86 processor tracks what instruction to execute using the special eip register. This register can't be modified by most instructions. Only jumps and calls modify it.

jump 237  # add 237 to eip 

It gets tedious to adjust the byte offsets every time you add or delete an instruction. So SubX provides named labels for specific points in the instruction stream, just like conventional Assembly languages. For example:

jump-if-equal $foo
…
$foo:  # jump to here 

⇒

jump-if-equal 237

Another convenience (not usually found in Assembly language) is the special labels `{` and `}`, `break` and `loop`.

{
   jump-if-equal break
   …
   jump loop
}

⇒

$loop1:
   jump-if-equal $break1
   …
   jump $loop1
$break1:

Basically the `{` and `}` get translated into labels, and `break` gets translated into a jump to the enclosing `}`. Correspondingly, `loop` gets translated to a jump to the enclosing (earlier) `{`. This syntax is surprisingly ergonomic and proved surprisingly easy to teach to non-programmers during the Mu1 prototype. Where you would say, in an imperative language:

if (<predicate>) {
   …
}

in SubX you would say:

<flag> = <predicate>
{
   jump-unless <flag> break
   …
}

Functions

Idiomatic machine code programs consist of functions operating on data. No matter what your high-level language does, and no matter what processor it runs on, at bottom it's translated to some interplay between functions and data. This section gets into that interplay in some detail.

We keep a program's functions and data segregated in memory to a code segment and data segment, respectively. (There are a variety of historic reasons for this that are not interesting. There is also one currently topical reason that is very interesting: security. A segment is a contiguous block of memory that gets a single access restriction. Code segments can be executed from but not written to (after the OS loads them initially). Data segments can be written but not executed. This W^X constraint is a critical pillar for securing computers; bad things happen when programs can be induced to modify their own code.)

In addition to the data segment a program starts out with, it can request various segments of empty working memory. A crucial one needed for functions to work is the stack. Stacks help keep local variables in functions isolated from each other. In particular, they're necessary for recursive functions that call themselves either directly or indirectly. Each call must get new copies of locals that don't interfere with other calls.

Here's one way function calls can work (used by many modern platforms): Before making a call the caller pushes arguments on the stack. The function can now access them from the stack. After it returns the caller pops the arguments off the stack to clean up. Recursive calls get separate frames on the stack.

Since the stack is temporary space that gets cleaned up after a function returns, it's also an ideal place for local variables. Just push stuff on the stack and make sure to clean it up before you return. The caller is none the wiser.

Managing arguments and local variables does require each function to know precisely where they live. One unambiguous way to specify arguments and local variables (again used by many modern platforms) is as offsets off of a special stack pointer register (esp above). The x86 instruction set provides `push` instructions that automatically decrement esp, and `pop` instructions that automatically increment esp. (The stack grows downward.)

Bottomline: calls in SubX consist by convention of some number of `push` instructions, one `call` instruction, and some cleanup of the stack. SubX provides the following syntax sugar:

(f o1 o2 o3)

⇒

push o3
push o2
push o1
call f
add 12 to esp # pop 3 args * 4 bytes each

Strings

Strings (arrays of bytes, ignoring character encodings) are a workhorse of high-level languages, but Assembly doesn't make them convenient to deal with. Programming in SubX involves writing lots of automated tests, and tests are most useful when they give good error messages. So passing strings into functions is a crucial mechanism. SubX allows string literals. When it encounters one, it appends the new literal to the data segment and replaces it with its label in the code segment.

 == code
(f o1 o2 "foo")

 == data
…data…

⇒

 == code
(f o1 o2 $string1)

 == data
…data…
$string1:
   66 6f 6f  # Utf-8 for ‘f’ ‘o’ ‘o’

Tests

One of the ways I'm able to sling large programs at such a low level is by writing lots of automated tests. A test harness isn't a common sight in Assembly programming. SubX adds a single new mechanism that makes testing ergonomic: when emitting a binary it generates a new function called `run-tests` that calls every function in the program that starts with ‘test-’.

Putting all this syntax sugar together, here's a SubX function to compute the factorial of a number, along with one automated test:

factorial: # n : int → result/eax : int
# function prologue
55/push-ebp
89/<- ebp 4/r32/esp
# save registers
53/push-ebx
# if (n <= 1) return 1
81 7/subop/compare *(ebp+8) # n is at *(ebp+8)
{
7f/jump-if-greater break/disp8
b8/copy-to-eax 1/imm32
}
# otherwise return n * factorial(n-1)
{
7e/jump-if-lesser-or-equal break/disp8
# ebx = n-1
8b/-> *(ebp+8) 3/r32/ebx
4b/decrement-ebx
# return n * factorial(ebx)
(factorial ebx) # → eax
f7 4/subop/multiply-into-eax *(ebp+8)
}
# restore registers
5b/pop-to-ebx
# function epilogue
89/<- esp 5/r32/ebp
5d/pop-to-ebp
c3/return

test-factorial:
(factorial 5)
(check-ints-equal 120 eax "failure: factorial(5)")
c3/return

(Ignore all the magic numbers for opcodes, just trust that ‘5b’ means ‘pop to ebx’, that ‘5/r32’ means ‘ebp’, and so on.)

Summary

SubX is designed to be easy to self-host, so it mixes and matches features from machine code, conventional Assembly and higher-level programming languages:

• No mnemonics; programmer must provide all numeric opcodes and operands directly.
• Error-checking using metadata.
• Syntax sugar for function calls and expressions like `*(ebp+8)`.
• Literal strings.
• Automated test harness.

The combination of these mechanisms has been ergonomic enough that I've written 40k LoC in SubX over the past year. I've successfully gotten SubX bootstrapped in itself. I've built an emulator for SubX that can emit traces of instructions executed, and this trace provides me with a time-travel debugging experience. I can also package up SubX programs with a third-party OS kernel into bootable disk images that run natively or on a cloud server. In spite of these milestones, the syntax above is still (obviously) not entirely copacetic. In the next post I describe my attempts to design the next level up, with strong type-safety and memory-safety. Rather to my surprise, the design process continues to seem inevitable.

comments

  

Anonymous, 2019-10-18: I am unclear on why the actual opcodes themselves were retained in code that will obviously need to be fed through an assembler to produce a binary. Why not elide them and simply create a more ergonomic assembly language? Is the concern that the complexity of the assembler would threaten habitability more than the foreign-seeming syntax and necessity to memorize opcodes rather than mneumonics does?   

  

Kartik Agaram, 2020-01-04: Yeah, though I'm open to revisiting this decision. The trouble with conventional Assembly languages is that a mnemonic may expand to many opcodes depending on the arguments. That complicates things greatly.

There's a ticket open in the project to design mnemonics for SubX opcodes in a 1:1 manner. It's a hard problem. We want the mnemonics to be more useful/memorable than opcodes, but not too verbose. I haven't been able to come up with a design that satisfies these constraints, but maybe somebody else can?

Lately I tend to program in a certain unconventional manner. A series of design choices, each seemingly reasonable in isolation, take me pretty far from conventional wisdom.

1. Axiomatically, I care as much about the experience of reading my code as that of running my programs.
2. Programs are easier to grok when you can run them, so I try to keep my programs super easy to build.
3. Dependencies add moving parts when building from source, so I try to minimize them.
4. All languages tend to directly or indirectly depend on C, so I try to cut out the middle men and program directly in C (unless I'm prototyping).
5. Describing dependencies explicitly tends to make C projects (header files and so on) hard to reorganize, so I rely on small codebase size and automatically generated headers to keep my code supple.
6. Grokking strange new codebases is hard, so I organize my projects in layers that can be ignored in the beginning to focus on a tiny subset of code that still builds and runs.
7. Determining if a code change is good can be harder than making the change itself, so I try to provide lots of automated tests as guardrails for newcomers.
8. And finally, this list is already pretty long so I give up on almost everything else, making a virtue of a rough, low-polish aesthetic in hopes of minimizing my area of concern and so controlling complexity over time. Sometimes people are forced to go in and modify my codebase. So be it!

Applied together, these concerns make my projects look fairly unfamiliar at first glance, with strange directives mixed into what seems like a C program, files auto-generated by the build system, strange looking tests and so on. To help newcomers gain an initial orientation, here is a series of four example repos that gradually introduce my idioms:

• basic-build: a zero-dependency build system in 30 lines of code. All it needs is /bin/sh.
• basic-test: a bare-bones test harness for C in 45 lines of code.
• basic-whitebox-test: a sandbox for my white-box tests that enable more comprehensive testing, more radical code reorganizations, and more scalable “debug by print”.
• basic-layers: a sandbox for my non-modular, abstraction-busting approach to organizing large-ish projects.

My hope is that these repos act like foundational “meta layers” that help peel back some of the complexity in my larger Mu project, and so make it more accessible to others. They aren't really intended to be read in a browser, so git clone them (Mac or *nix) and try following the Readme. Comments and feedback most appreciated, particularly if you're moved to try building something using them.

(Update 2019-08-14: Remo Dentato has a project developing basic-build further.) ]]>