Wednesday, November 12, 2014

The Strange Case of the Branching Dictionary

In which our protagonist tries to convince us that the weird structure of Tali Forth's dictionary is actually an amazingly clever idea.

So the weather in Germany has finally turned horrible again, which means that I can return to indoor pursuits. Ask me again why Autumn is my favorite time of year.

Anyway. Many months ago, we left off with the promise that we'd be examining the dictionary of Tali Forth. This contains the Forth "words" that make up the language, things like DROP or LOOP.

The basic structure is simple: A linked list of entries. When we define a new word, it is added to the dictionary. When we type a word, the dictionary is searched from newest to oldest entries until it is found. Remember the flow chart in the previous entry: If a word is not found, Forth checks to see if it is a number. If that fails, it complains.

If we take a closer look at a single dictionary entry, we see it consists of two parts: A "head" and a "body". The body is the actual "payload" of code that is executed when the word is executed. For example, the DROP instruction in Tali Forth is are simply the 65c02 instructions INX INX plus a RTS at the end. The header provides stuff like the link to the next entry in the list, the string of the word ("DROP"), the length of that string, and some flags.

There are various ways to construct a Forth dictionary entry (Brad Rodriguez has an excellent explanation of what the different parts do, including examples from other Forth versions). The problems are always the same: We need a pointer to the start of the dictionary, so we know where to find the information in the header, and we need a pointer to the code in the body to execute the word the entry represents.

Of course, it would be really cool if those pointers were one and the same, right? Heh. So here is how Tali Forth solves the problem:

Ascii drawing of a the Tali Forth dictionary entry, version ALPHA 004. Including as an image for those of who insist on using fancy-pants variable space fonts instead of monospaced.

We'll get to the first two bytes -- the BRA stuff -- in a moment. The byte after that includes the flags and five bits for the length of the name string. Then, we have a pointer to the next entry in the dictionary, followed by the pointer to the end of our body. This is used for compiling short words directly into machine code. The next to fields are of variable length: The the word as an Ascii string, and the payload of code in the body itself.

Now, notice we do something really ... different: Every entry starts with a BRA instruction. This is only available on the 65c02, not the original 6502, and tells the CPU to jump ahead (or back). Here, we have it set up so it jumps to the beginning of the body.

What this means is that we can execute any Tali Forth word in the dictionary by simply jumping to its first byte. Which just so happens to be where the link from the previous entry points us to. This way, we only have to deal with one 16-bit address and don't have to read or calculate where the body begins. In Forth terms, this is our Execution Token (XT). Pretty cool, right? Well, except that we pay a hefty penalty. Every single dictionary entry is two bytes longer and takes up to four cycles longer.

In the end, I decided to go ahead with the setup because it is simpler than all the others I could think of. Remember, simplicity is a primary goal.

(What I'm more worried about is if we actually need the pointer to the end of the body, or if we can't figure out another way of figuring out where to stop compilation.)

In the source code, an entry looks like this:

Tali Forth source code for the DROP entry in the dictionary. Remember, if this looks different to you than other assembler code, it is because we use the Orphis Assembler 2.0

By the time of the next entry, we'll probably have cleaned up the code enough to have it posted on GitHub like a real project. As long as it keeps raining in Germany, that is.

Saturday, May 17, 2014

The Dragon-Free Internals of Forth

In which our protagonist is amazed that the core structure of Forth is so simple even he can understand it.

Forth was not invented by a bunch of eggheads at a university, but by a guy who needed to get real work done. Chuck Moore started programming in the 50's at the Smithsonian Astrophysical Observatory with code that computed ephemerides, orbital elements and satellite station positions. After graduate school at Stanford, he worked as freelance programmer, using a bunch of routines and concepts he had developed on the way over and over again:

Working in Fortran, Algol, Jovial, PL/I and various assemblers, he continued to use his interpreter as much as possible, literally carrying around his card deck and recoding it as necessary.

This "interpreter" would evolve into the language now called Forth. Moore rewrote it for various computers systems, and even later, hardware remained a moving target:

Throughout the 70's, as he implemented Forth on 18 different CPUs (...), he invariably wrote for each his own assembler, his own disk and terminal drivers, even his own multiply and divide subroutines (on machines that required them, as many did).

Keeping stuff simple not only was a philosophy, but a necessity.

So while the internals of boffin languages can be so complex and scary they make people think of dragons, the core of Forth is so simple it seems almost snarky:

The flow chart of a Forth system. From Lost at C? Forth might be the answer by Tom Napier and Eric Krieg.

The only non-trivial concept here are the "immediate" words: As the name says, those are executed right way -- "immediately" -- even if we're in compile mode. LITERAL for instance is a compile-only, immediate word that makes sure the word will later push a number on the stack.

So "compiling" in Forth means adding new words -- what other languages call "functions" -- to the dictionary. In its simplest form, this does not involve math, complex algorithms, or dragons (though of course we have nothing against dragons, because dragons are awesome). In other words, it is something even we can do.

The major question then becomes how to design the dictionary. In the next entry, we'll look at that more closely, because Tali Forth does something weird.

Tuesday, April 15, 2014

Real Jedi make their own Forth

In which our protagonist takes matters into his own hands, needlessly quotes Chaucer, and gets his Star Wars mythology mixed up.

It turns out that there is a problem with the "standard" Forth for the 65c02, FIG Forth -- it is old, as in, really old. Trying to learn modern Forth with it is like trying to learn modern English by studying The Canterbury Tales: Not impossible, but probably not a good idea.

But now is tyme to yow for to telle
How that we baren us that ilke nyght,
Whan we were in that hostelrie alyght;
And after wol I telle of our viage
And al the remenaunt of oure pilgrimage.

Strangely, nobody seems to be working on a modern version of a lesser-used programming language for a 30-year-old CPU. So I decided to write my own. Hence the headline.

And thus was born Tali Forth for the 65c02, which has now reached a late ALPHA stage (and is free to use, but at your own risk). The basics are there except for some more complicated words such as DOES> and ?DO, and some legacy words such as, yes, WORD. IF/ELSE/THEN and DO/LOOP work, and so does POSTPONE, which is one of those words that is really, really powerful, but will give you nightmares trying to understand it the first time.

(About the name: I always liked it, and it seems we're not going to have more kids. If it sounds familiar, you're probably thinking of Tali'Zorah vas Normandy, a secondary character in the Mass Effect universe. For the record, and EA's lawyers, this software has absolutely nothing to do with the game or the companies that made it.)

Screenshot of Tali Forth running on the py65mon emulator. Multiline formatting still sucks, and though DOES> is listed, it is currently just an empty dictionary entry. I should probably define KEELAH somehow.

I decided on four criteria for this implementation (see here for more detail):

Simple. Duh -- if I'm writing it, it will have to be simple. For this reason, I chose to use Subroutine Threaded Code (STC), where each word that is not native machine code is accessed by a JSR. Brad Rodriguez of CamelForth fame explains the differences between the various models nicely.

Specific. For the 65c02 only, and as close to the metal as possible for speed. Well, and because I really like to program assembler.

Standardized. Roughly following the ANSI Forth standard. Actually, I used the ANS Forth 200x draft document. Ahead of the curve!

Speedy. When forced to choose between speed and size, go for speed (within reason). It would still be nice to stay under 8 kbyte for the core routines so they fit in the ROM chip that starts at E000.

Current high-level commands. These will probably be joined by ?DO and +LOOP once I figure out how to code them. Long-term, I'll consider replacing the individual strings with a long one so you can just add further commands to the end and EVALUATE them without all this hassle.

So. What has writing 230 kbyte of (grotesquely over-commented) source code by hand for 5.9 kbyte (and counting) of assembled machine code taught me?

First, it is amazing how simple Forth really is under the hood. Once the basic interpreter loop is up and running, you just code word after word, and compiling stuff is a breeze. No wonder "Forthwrights" (a term said to be invented by Al Kreever) look down on the complexity of other languages. Understanding POSTPONE is the problem, not coding it.

Second, I have given up trying to read anything but the most trivial Forth code without drawing stack diagrams. As true as the previous statement is, a lot of the power of Forth is in the implicit rules -- the way the stack works, for instance -- which takes extra effort to understand. This fits with the reports that the inventor of Forth, Chuck Moore, prepares stuff before coding:

His programming style is thoughtful. He thinks about the problem a lot and writes very little code. He thinks it through again and rewrites the code. He objects to letting too much code accumulate from historic reasons and likes to rewrite. He is the most productive programmer I have ever seen yet he has only written about 15K of code in the last fifteen years.

Which could lead us to a discussion about the definition of "productivity", and the time pressure modern-day programmers -- the article is from 1998 -- are under. But we'll skip that here.

In the end, the combination of power and complexity means the Jedi joke isn't quite right: It should probably read "Sith" in the title. I have a definite feeling of having joined the Dark Side, where you can do amazing stuff with very little effort, but pay a definite price. So far, no cookies.

In the next entry, we'll discuss design details of Tali Forth. Some of them are, well, curious.

Thursday, February 20, 2014

How I came to join the underground computer cult of Forth

In which our protagonist talks at length about Forth with the disconcerting fervor of the newly converted and reorientates his grand project accordingly.

Since I never get anything done in November or December anyway -- somebody in the family is always sick -- I said "screw it" this year and left the Übersquirrel in a dust-proof box. Instead, I have been learning Forth, a programming language that everybody keeps talking about in the forum. It was time well spent: Forth will blow your mind and change the way you look at programming in general. It will also make the Übersquirrel that much more powerful.

So, this entry is all about Forth.

(If you are not interested in fringe programming languages or speculation on the mental state of their inventors, this is your cue to go do something else. From here on, it's stacks all the way down.)

Chances are, you dimly remember Forth as a minor programming language popular in the 80s for small computer systems and now mainly used in hardware setups, embedded systems, or boot loaders like Open Firmware. In fact, most people have never seen any actual Forth code. This is probably a good thing: What immediately comes to mind is that whoever invented the language must be either batshit crazy or a friggin' genius.

A snippet of Forth code from my first larger project, a 65c02 disassembler. What looks like the result of your cat stepping all over the keyboard actually makes sense.

That would be Charles Moore, and it is considered polite in Forth circles to go with the genius option. There is ample support for this idea, but you do have to survive the shock of first contact with the language and dig down a bit to appreciate it. Put briefly, you need to get from the weird to the wow.

Let's start with the word "language". Forth is actually a programming language, an operating system, and a shell rolled in to one. Even the language part is iffy: It is more a sort of low-level meta-language. As Leo Brodie explains in his classic Thinking in Forth:

Forth is a programming environment for creating application-oriented languages.

This "environment" is not limited to software. There are amazingly simple "stack machine" CPUs that are built just for Forth. Some are used in spacecraft such as the Cassini-Huygens mission currently at Saturn. We're are talking about a whole computer ecosystem outside of the mainstream.

In his (highly recommended) blog post "My history with Forth and stack machines", Yossi Kreinin compares Forth to bacteria that strip down their biochemical machinery to the absolute minimum. I'd compare it to a whole different branch in the tree of life, like suddenly discovering there is not only photosynthesis, but also chemosynthesis going on in the ocean vents. This gives us another parallel: Half of the time, nobody really knows what the hell is going on down there.

More on that later. Let's look at actual Forth.

It's a stack-based language with "postfix" or "reversed polish notation" (RPN) notation like the upmarket HP calculators. This is normal "infix" representation:

2 + 4 =

This is what they taught you in school, this is what you are familiar with, and this is probably how you think. In contrast, postfix looks like this:

2 4 +

Other people explain this all better and in more detail elsewhere. The important thing is that postfix makes a bunch of things a lot easier, because the order is implicit. There are situations where infix must use brackets and follow special rules:

2 * (4 + 6) =

Postfix thinks that is totally lame and stupid.

4 6 + 2 *

Done right, parameter passing becomes trivial, because what you need magically appears where it should be, right on top of the stack (do it wrong, and you spend your time moving stuff up and on the stack and feel like an idiot). Stack machines generally do some things better and worse than others, but we'll skip that here.

After a lifetime of thinking in infix, postfix makes your brain hurt (there is a lot of that with Forth initially; I'm still recovering from POSTPONE). Calculations like those above are not really the problem, at least with some practice. It's that Forth uses postfix for everything, including branching and loops. This is the Forth version of IF-THEN (using capital letters for readability):

done? IF stop-it THEN

IF-THEN-ELSE gets really screwy:

done? IF stop-it ELSE keep-going THEN

In the beginning, it helps to think of THEN either as "after all this is done" or simply ENDIF, which was actually a synonym in earlier versions of Forth.

This example shows us something else about Forth that takes getting use to: Special characters aren't. If you are used to the Unix shell, the Forth way of marking variable and word names with question marks, periods, hashes, quotation marks, and all sorts of other "reserved" characters will freak you out. However, these conventions make perfect sense once you have understood the conventions. Something like PARROTDEAD? returns a true or false value, while ?PARROTDEAD is only executed if the top "cell" on the stack is non-zero. Anything with a dot at the beginning such as .CURSE should print something, and >BYTE is understood to be an index.

I've been talking about "words". Now we're getting to the part that is not just weird, but actually kind of cool, if not quite wow yet. Forth starts you off in an interpreted mode -- type stuff and it happens, like Python -- but lets you compile code into "words", little subroutines. Their definitions start with a colon and end with a semicolon:

: .FOUR 2 2 + . ;

The single period at the end of the definition takes the first element on the stack -- the number four in our case -- and prints it to the screen. When Forth reaches the semicolon, the word .FOUR is compiled and added to the "dictionary" of the language. It is now just as much a first-class citizen as, say, IF or + (addition). Dude, you have just expanded the language.

In fact, Forth is basically just a bunch of words and a rather primitive loop structure to handle them. This is why implementations can be so small, and why lots of people write their own [PDF] interpreter/compiler from scratch. Try doing that with C.

Forth does come with a set of "core" words, defined by ANSI "ANS" Forth 94. Unfortunately, this takes us back to weird world, because it is hard to believe that they weren't picked by Dr. Seuss. Some are short -- BL or BYE -- some are long -- EXECUTE or ENVIRONMENT? -- some are cryptic -- >R or 2@ -- and some are chatty -- OPEN-FILE or TIME&DATE. There doesn't seem to be any system to the selection. You just have to memorize them, or hope your cat steps on the right keys.

Once you do know them, you can build your own words using the ":" and ";" syntax. Ideally, a Forth program is "highly factored", with each word consisting of not much more than two lines of code. You start off with low-level primitive words at the beginning, and use those as building-blocks to create more and more powerful stuff lower down.

In a prefect world, you steadily increase the abstraction level until you end up with something amazingly simple in plain English (or whatever) like


to control your Death Star.

At this point, your reaction is probably something like, big deal, I can write subroutines in my favorite language as well. True. But now we come to the part that separates the men from the boys, the women from the girls and the three-meter aliens from the dog-derivatives: In Forth, you can define new words that let you make your own definitions. Kreinin speaks of his shock upon figuring out that things like IF and THEN are defined through other code -- "conditional primitives aren't":

It's as if a conventional program modified the assembly instructions generated from it at compile time. What? How? Who? How do I wrap my mind around this?

Being able to new words that control "compiling" -- what Forth calls what you do between the ":" and the ";" -- are what gives the language its real power. More Kreinen (emphasis in the original):

To this day, I find it shocking that you can define defining words like CONSTANT, FIELD, CLASS, METHOD -- something reserved to built-in keywords and syntactic conventions in most languages -- and you can do it so compactly using such crude facilities so trivial to implement.

At this point, let's skip over the technical bits in what is already a way too long blog post and get to the larger picture.

Most languages give you a toolbox that you can use to solve your problem -- say, Python's Standard Library with its famous "batteries included". You get a hammer, a screwdriver, a chain saw, and used in the right sequence in the right way, these let you build a table. Forth lets you build your own tools. You can write your own language to fit the problem. It doesn't even bother with standard data types like lists: Roll your own, custom-fit to your task!

This is also where the problems start.

A screenshot of the PDF of the first page of the source listing of the ancient Forth version FIG Forth. Some of us remember the sound that those printers made.

In the hands of a good or even great programmer who understands the problem and has the clarity of vision to figure out the best solution, Forth is amazing. Brodie walks the reader through the design of a script to convert an Arabic number to Roman numerals and the result is so short and compact it will make you cry. This is Forth at its most elegant.

However, understanding Forth code requires extra effort, because you can't just trace the steps in the sense of hammer-saw-hammer. You have to understand the mental representation the programmer developed of the problem, the language he invented to realize it, and the whole Rube Goldberg contraption he built to replace saws and hammers.

So in the real world, reading other people's Forth code can be a joy, with words flowing from top to bottom in a well-structured narrative while the angels sing praise to its conceptional beauty. Or it can be a mind-bending hell of cryptic words set in a sea of low-level symbols that make the stack writhe and thrash in agony. This is why Forth has a certain reputation as a "write-only" language: Other people's code can be a serious pain in the ass.

Which is where we come back to the Übersquirrel.

Forth is the most powerful thing I will be able to get running on this chip (don't talk to me about BASIC, ever; I grew up with it). I'm pretty much the only person who is going to read my stuff anyway. And there is an old version of Forth called FIG Forth that has been ported to the 6502 and is freely available.

So what we are going to do now is stop work on Squirrel OS and see what we can do with FIG Forth in 8 kb of ROM. Either we keep Forth as the operating system, or we go back to the monitor program we have been working on.

For those who are interested in Forth -

The book everybody begins with is Starting Forth by Leo Brodie, the one with the famous silly drawings. I would recommend skimming first it to get a feeling for the language, and then read the more philosophical Thinking in Forth as soon as possible to give you the "why" of everything. Then, either go back to Starting for the real work or switch to a modern treatment such as Programming Forth [PDF] by Stephen Pelc. To write actual code, I have been using gforth because it runs on pretty much any platform (including Android 4.4). This is ANS ("ANSI") Forth and quite different from FIG Forth.

Finally, if you are interested in the history of programming languages, Moore has released his reasoning behind Forth from 1970 in Programming a Problem-Orientated Language.

Later I'll show you how to write a program in a forgotten language: machine language. By that I mean sitting at the console and entering absolute, binary instructions with the switches.

That's a bit more basic than even I like it.