Meow5: The Conclusion

Let’s take a quick tour. Here we have the "hello world" of concatenative programming:

This tiny example shows the concatenative data flow - the "Meow!\n" string comes before print. The function expects to find the string to print already on "the stack", waiting for it.

If we don’t have a string for print, we get a segmentation fault, which is the computer equivalent of a hissing cat:

What happened here is a stack underflow. We tried to access a value from an empty stack. Let’s get a disclaimer out of the way: I programmed almost no safety checks into Meow5. Almost any mistake will result in a seg fault!

You can also do the usual RPN-style mathematical operations and stack manipulations. In these examples, ps means "print stack":

This is often called stack-based programming and is the hallmark of languages such as Forth and PostScript.

Concatenative languages can act a lot like human speech. In fact, Forth calls its functions "words" and stores them in a "dictionary".

Functions in Meow5 are defined with def, which is short for 'definition'. It’s fun to make silly examples:

The pour-two-drink-one function is composed of other functions by naming them in order. This composition can be used as a larger composition and so on. This is somewhat true of most languages with functions, but a concatenative language uses this as its primary (or even sole) mechanism for building up programs.

Are you wondering what would happen if we drank one more cup after reaching zero? Let’s find out!

That’s no accident. Meow5 can help us get to the bottom of this by displaying the value in hexadecimal:

Ah, that’s better. This is what you get when you subtract 1 from 0 in a 32-bit two’s complement computer. This value either means 4,294,967,295 (if we treat it as an unsigned integer), or -1 (if we treat it as a signed integer).

So we either have a lot of tea or we owe the universe a cup tea, depending on how we consider our little tea-drinking model.

Meow5 can also display numbers in binary, which can be a fun visual aid for two’s complement tea drinking:

This is just playing around, but I hope you get a sense of the natural language feel you can get from a concatenative language. The long string of commands at the beginning is uninterrupted with anything that resembles "computer syntax" and is also devoid of variable names or other parameter-passing mechanisms. Each "word" in the statement simply operates on the value left by the previous word.

I also like this example because it highlights the almost absurd juxtaposition between the high-level wordplay of the tea scenario with the low-level behavior of bits and bytes in the CPU!

Now let’s dive into the part that makes Meow5 unique: machine code concatenation as the mechanism of function composition.

Every def in Meow5 is a sequence of i386 machine code. We can see this machine code with the inspect def. Let’s look at really simple instruction, pop, which literally translates into a single byte i386 machine code instruction:

Or here’s a 3-byte one, dup, which duplicates the value on the top of the stack:

Sharp eyes will note that dup begins with the machine code of pop. The Meow5 magic happens when we compose them into a new def and the machine code is concatenated inline:

As we can see, this new pppd def is exactly what we asked for: three copies of pop followed by one copy of dup.

The magic is that there is no magic. Meow5 is just copying and pasting.

This brings us to Meow5’s namesake program, five copies of a "meow" printing statement:

These string printing defs are considerably larger than the dup and pop examples:

Which gets at the heart of the thing: the meow5 def is, indeed exactly five times as large as meow. And if we use meow5 multiple times inside another def, like this:

Then we’ll be multiplying the duplication again and on and on.

The question is: at what point is the duplication harmful? And what does a modern out-of-order executing, predictive, pipelined CPU with megabytes of on-die cache think of code written this way? I suspect the answer varies as circumstances change. I’ve found that I’m not all that interested in benchmarking it myself. I just wanted to see it work.

As I alluded above, one of the really cool things about this concatenated machine code approach is that every def is a completely self-contained copy of all of the other defs it uses. You can think of it as "inlining" on the small scale and "static linking" on the large scale (except it’s not linking, it’s more inlining).

Meow5 comes with a command called elf which writes out a def as an ELF executable. (And, beware, it will do this whether or not the def is actually a viable stand-alone program.)

Let’s try it! I’ll interactively "compile" a new stand-alone hello world program, test it out, and then write it to disk:

Now let’s try out the written executable:

Well, it printed but then, oh dear! What happened?

Well, here’s something that is usually hidden from users of "normal" programming languages: the CPU actually has no idea where our program ends! It got to the end of our print instruction and…​just kept executing whatever nonsense happened to be in memory after that.

To stop the program cleanly, we need to tell the operating system to exit our program. How do we do this? Okay, this is really fun.

You see how I exited the Meow5 interpreter with the exit def above?

We can use that same exit def in our program to quit it cleanly. To indicate that everything was okay, we also explicitly exit with the status 0 by putting a 0 on the stack for exit to pass to Linux with the exit system call:

You’ll notice I did not test the meow def in the interpreter this time before I wrote the ELF file. Can you guess why? :-)

Let’s test this executable:

Yay, no segmentation fault this time! This is a well behaved hello world.

How big is this thing, anyway?

It’s 142 bytes. Not too shabby. Especially since the ELF header is 84 of those bytes (52 bytes for the main header + 32 bytes for the program header). Which leaves 58 bytes for our program itself.

Does that add up? We can find out!

Yup! The actual program is the exact contents of the meow def. Nothing more, nothing less.

This also means the def contains the "Meow!\n" string itself, 4d 65 6f 77 21 0a 00 (0a is a newline and 00 is an ASCII 'NUL' to terminate the string.) The string is inlined right there with the machine code that prints it. I’m doing that with this one weird trick I re-invented, though I was not in the least surprised to learn that it’s a common technique from the Olden Days when people did this sort of thing all the time.

I’d originally planned to store strings and other data the "right way", in a separate memory segment as specificed in the ELF loader and I ended up writing some tools in Zig called Mez and Zem to assist me with this. The mez program became rather pretty by the time I was done because I understand things better if I can see them.

Here’s the colorful terminal output mez when given the meow program we created above:

You can perhaps see that the ELF header and entry point math work out the way I described them earlier.

One of the big challenges with Meow5 was that to make stand-alone executables work, all code had to be completely position independent, including the data!

I gained a much deeper understanding of the flow of machine code execution while building Meow5!

None of this project would have happened if I hadn’t done the first "season" of Assembly Nights, in which I ported the JonesForth implementation of Forth to NASM assembly.

Not only did I learn one method for implementing a Forth from JonesForth, I learned how stuff like this is build in assembly. And in the process, I got all sorts of fun ideas, including this "let’s just concatenate machine code to make programs" one.

Then, about halfway through writing Meow5, I wrote this massive article with a really long title: Forth: The programming language that writes itself: The Web Page ("Charles H. Moore and the pursuit of simplicity.")

In that article, I describe the nascent Meow5 as a "…​thought experiment taken too far," which is absolutely right.

And I wrote

As a perfect example, I deviated from Forth’s string quoting. A string in Forth looks like this:

The reason for the extra space at the beginning is that there is a word named " which gathers up the rest of the input until it hits the " character at the end.

What this means is that there is no special syntax for strings in Forth. You can replace the " word with your own to change its behavior!

I decided Meow5 would have string quoting as part of the language so you can write the string above in the much more natural-looking way:

But as a consequence, the " quote character became part of the language and it can no longer be replaced by the end user. The interpreter itself checks for the " character.

And unlike Forth, you cannot create a def in Meow5 that starts with a quote character. You could say that this is no great loss, and I would agree. But it has literally doubled the amount of syntax in Meow5. Forth has only one syntactical element: whitespace. Meow5 has two: whitespace and the quote.

(Mind you, I think the trade-off was worth it in this case. Strings are super common and useful in all of the programming I do, so special treatment is warranted and I don’t regret the decision.)

In the giant Forth article, I also mentioned that there were several other cases where I tried to deviate from Chuck Moore’s wisdom and ended up giving up and taking his path. In each case, Moore had discovered the simplest possible way to do it. Moore’s path was that of the least resistance. If my way had been easier, I would have stuck with it, believe me!

Like a traditional Forth "dictionary", Meow5 stores defs as a linked list. Instead of having "heads", my defs store metadata about themselves in "tails". This has two advantages.

The first advantage is that I can write the tail metadata after I’m done writing the machine code of the def, so I know everything I need to know about it (notably the total length of said machine code).

The second advantage is that I can use the word "tail", which seems like something a cat-themed language should have.

Like Forth, you can define new definitions with the same names as old definitions, which will cause the new definition to take precedence over the old one:

Both meow defs still exist, which is mostly academic in Meow5, but is very important in Forth.

Meow5 has an all def, which lists all definitions currently in memory by traversing the tails and printing their names:

As we can see, there are now two meow entries listed. When we call meow, though, only the mostly recently defined one is used.

In Meow5, there is no reason to keep the old definition of meow around because it will never be accessed. But in Forth, this allows existing word definitions to continue using whatever version of the word they happend to use when defined.

However, both languages allow you to extend any function by calling the original and doing additional work. Here I extend a cow def so it quotes its moo:

In most Forths, the new cow would actually "call" the old cow. In Meow5, the new cow contains the old cow.

The other thing contained in the tails are flags indicating whether the def can be called in "immediate" mode or "compile" mode or both. We’ll see an example of the difference between these two modes of execution in the next section.

A third flag, "runcomp", is deep voodoo. It indicates that the def runs while you’re compiling a new def, rather than be compiled into the new def. If this flag didn’t exist, it would be impossible to have a def like ;, which ends the compilation of the current def and writes the tail entry!

A fun example of a "runcomp" def and of the extensibility of the language is the way I implemented comments in Meow5:

The # character is not part of the language! It’s not syntax. It’s just a def like any other:

When called, the # def reads the incoming stream of source code, even in compile mode, and throws away all input until it hits a newline character!

My entire goal with Meow5 revolved around proving that machine code concatenation could work. So as soon as I saw this for the first time, I was basically done:

But part of me couldn’t be satisfied with putting all of that work into getting this thing off the ground…​but leave it with no control structures!

So I came up with the "simplest thing that could possibly work." Here’s my "if" statement. It’s a def called ?:

The ? def checks for 0 (false) or non-0 (true) from the stack. If the value was true, it runs the subsequent def. If it’s false, it doesn’t.

To make this work, there are actually two definitions of ?.

The easy one works in "immediate" mode. That version runs in the interpreter immeditately as you type it. The example above shows this. As soon as I type 0 ? meow and hit the Enter key, a 0 is pushed on the stack, the ? def runs, pops the value off the stack, determines it to be "false", and skips the meow def by eating the next token of input so meow does not get called! If a non-zero ("true") value was on the stack instead, ? does nothing and the meow def runs.

The harder version is for "compile" mode. It looks identical, but the way it works is very different. Here’s an example:

Like the immediate mode example that came before it, the "Meow!" is only printed when we put a non-zero (true) value on the stack. But this time, the ? def was part of (compiled into) another def called maybe-meow.

To make the compile mode version of the ? def work, the raw machine code for a conditional jump was concatenated with the machine code of the meow def. The size of the jump is the exact byte size of the meow def machine code. The effect is to skip over the meow code when the condition is "false".

It’s actually really hard to do anything useful with this in Meow5 because I haven’t added any handy comparison operators or anything like that. But I’m sure someone can figure out how to make it execute any arbitrary program…​

Anyway, once I’d figured out how to do an "if" statement, I knew loops couldn’t be too far off.

Sure enough, implementing loop? was a relatively simple matter of sandwiching a def with two jumps. The first one is the conditional jump I used for ?. The second one is unconditional; it always jumps back to the conditional so it can be tested again.

Here’s my comment in the Meow5 source:

Makes perfect sense, right? Well, not to me! I had to work it out on paper first.

Let’s see it in action by rewriting the meow5 def with a looping version:

Oh no! There’s no way to stop this meowing machine short of killing it with Ctrl+C.

The problem with this program is that the loop condition is always "true".

One way to fix this is have the meow def decrement the value on the stack so that it will eventually be 0 ("false"):

Awkward? You betcha! But it works and that’s good enough for me. The loop itself accounts for exactly 15 more bytes of machine code surrounding the def being looped.

If we add an exit to the five-meows-loop def above, we can export it as an executable ELF file that prints five meows at the command line that weighs a mere 160 bytes compared with the 317 byte non-looping, redundant meow meow meow meow meow version:

They both appear to perform identically, of course:

But the machine code is quite different!

The five concatenated copies version:

Versus the loop version:

In some ways, the five copies version follows a more "pure" Meow5 path by using only concatenated machine code instead of conditional jumps.

This project took me over a year of evenings, though there were many gaps, including a 5-month one that spanned the entire summer. This is where having a dev log and shell scripts saved this project from certain abandonment. I wrote about this in Next Note and Run.sh.

For many months, I was averaging something like one or two lines of assembly code per night. Keeping it fun and focused was vital to keep me at it over that span of time.

I learned about linkers and loaders.

I discovered old-school position-independent data embedding hacks.

I discovered the advantages and disadvantages of null-terminated strings.

Late in the project, I discovered the edb debugger (github.com), which is a huge improvement over GDB for assembly program debugging, especially for programs like those exported by Meow5 with no sections or labels!

I learned a ton while I made this silly thing. Knowing it was never going to be a "real" language made it easier to experiment without fear.

You can view the source of Meow5 and all related files here:

The Meow5 Repo

In particular, you can "follow along" with the entire adventure by reading the log01.txt - log14.txt files in the repo. They capture my entire process (including plenty of wrong turns and false starts) from start to end.

I’ve already got the next Assembly Nights "season" lined up and it’s going to be pretty ambitious. In fact, it would have seemed just about impossible to me two years ago when I began my nighttime assembly adventures.

Thanks for reading and until the next season begins, happy hacking everyone!