Tag: Computing

About half a year ago, I wrote a small FORTH interpreter in portable C. As opposed to gforth (GNU Forth), it only depends on the standard C library and it can be built in just seconds. The resulting binary (including the dictionary image) is only 55 kB in size.

Why did I build this? Because other FORTH implementations ether leave out some functionality I considered important (such as vocabularies or floating point numbers) and because gforth required too many dependencies to be built from source. Plus I wanted some FORTH system to run on a stand-alone RP2350-based system that generates DVI video in software and can also access USB peripherals like a mouse, a keyboard and a USB drive.

The FORTH system consists of two parts:

• The virtual machine written in portable C. It interprets byte instructions via a giant switch statement. Some instructions access operating system functions.
• The dictionary image. It contains the functions written in FORTH and the FORTH interpreter itself.

The file kernel.img is provided, a minimal dictionary image that is just capable enough to load more FORTH code to extend itself into a full FORTH system. The dictionary image of the full FORTH system is then written to a file.

Two versions of the FORTH interpreter are compiled:

• bforth can load a dictionary image from a file. It can be used to load kernel.img and extend itself into forth,img
• forth has a dictionary image embedded in its code. It must first be created by bforth and then be converted to a C header file.

This is not as fast as gforth, but reasonably fast for a FORTH implemented in C. All addressing in FORTH is done relative to the base of the dictionary image. Even though it can run on a 64-bit system, the FORTH virtual machine is a 32-bit machine. At the moment, execution addresses are even restricted to 24 bit. 16 MB should be really more than enough for a FORTH system like this.

This FORTH system is known to run under Linux on x86-64, x86-32, arm64 and riscv-64. It should also work on arm32. In its current form, FORTH requires the system to be little-endian. All currently relevant systems are little-endian. If you want to try it out, please get it from https://github.com/lennart-benschop/embeddable-forth

Last year (2025) I presented at T-Dose too. I hereby share the slides of this presentation as well. Agon is a modern 8-bit machine based around the Zilog eZ80, designed in 2022 by Bernardo Kastrup.

This is the original Libreoffice doc.

Last weekend I presented at T-Dose, the Technical Dutch Open Source Event in Geldrop, The Netherlands. My presentation was about the FORTH programming language and it has been recorded and hopefully it will be published soon. See https://www.t-dose.org

In an earlier post I told about FORTH already. I added some examples to the slides, that I presented (or intended to present) live during the show on a text terminal. I did carry an actual Raspberry Pi Pico running Zeptoforth, where I could demonstrate a blinking LED.

This is the same file as a PDF.

When Konrad Zuse designed his first mechanical computer in 1936, it supported binary floating point operations, much like modern IEEE-754, but with less precision (only 22 bits). It even had special values for infinity. Its successor, the Z3 was based on relays and was completed in 1941. It used the same type of floating point numbers.

Electronic computers started to get floating point in the late 1950s. Every computer architecture had its own floating point format and its own quirks. In those years, floating point got a bad reputation of being intrinsically inexact. When I studied at the university in the late 1980s. that was still the common wisdom. Never rely on any exact value, not even 2.0 × 2.0 is exactly equal to 4.0.

Some early machines, like the IBM 7094, had a 36-bit word size and proper binary floating point. Single precision was 36 bits and double precision was 72 bits. The IBM System 360, introduced in 1965, had a word size of 32 bits instead of 36 bits. Worse still. the floating point format was base-16 instead of base-2. For normal numbers, the mantissa could have a value between 2²⁰ and 2²⁴ – 1, or 0x100000.. 0xFFFFFF. Incrementing the exponent by 1 would increase the value of the number by a factor of 16. This way we had only 21 significant bits for some values and 24 for other values. Even worse still, the computations were not as accurate as they could have been within the constraints of this format, because no guard bits were used. Needless to say, some users of the IBM System 360 were not happy with its much inferior floating point accuracy.

Numerical programming was emerging as a significant discipline in computer science. Using clever tricks they could get much more accurate results from floating point operations than they were entitled to. The problem was: different computer architectures required different clever tricks. Floating point hardware was primarily designed to be fast, even if that meant loss of precision in some corner cases.

IEEE-754

Something had to be done to clear up this mess. Some good ideas:

• Use a pure binary floating point format: 32 bits for single precision and 64 bits for double precision. Pure binary formats allow for an implicit leading one, so even though only 23 mantissa bits are stored, a 24-bit number in the range 2²³ … 2²⁴-1 can be represented. This format was used by Digital Equipment Corporation (DEC) in the PDP-11 and VAX machines. This turned out to be much better than IBM’s base-16 format.
• Specify the exact value that must be returned for each operation. Do this with four different rounding modes that each implementation must support. No more stupid shortcuts to compromise accuracy
• Specify distinct values for + and – Infinity and a set of NaN (Not a Number) values for completely invalid results.

One thing that was annoying on every floating point system before IEEE-754: there was a large gap between zero and the smallest positive floating point number. This gap was much larger than the gaps between numbers with the lowest exponent. For example: there ware millions of numbers between 2^-126 and 2^-125, but there are no numbers between 0 and 2^-126. Therefore, A == B was not equivalent to A – B == 0. For example the number 1.5×2^-126 – 2^-126 would be zero, while these numbers are different.

A solution to this problem would be to reserve the lowest possible exponent value for the value 0 and any numbers between 0 and 2^-126. These numbers were to be called subnormal numbers. This feature was costly to implement in hardware, so many hardware vendors (most notably DEC) were opposed to it, but the software guys won this one.

Work on IEEE-754 started in the 1970s and while the standard was only released in 1985, Intel announced the 8087 floating point unit already in 1980. This processor implemented the standard before it was a published standard.

Some scripts contain thousands of different characters, so an 8-bit character code for any of these would be futile to begin with. While different vendors in different countries each tried to fit their ideal character set into an 8-bit code, China and Japan already knew this would not work for them.

Japan developed a multi-byte code Shift-JIS, in which ASCII characters would take 1 byte and Kanji (or Katanana or Hirigana) would take two bytes each. Chinese speaking countries had the Big5 character code, using a similar concept.

Unicode was already envisioned in 1987, the year the first official 8-bit character code for Western European languages (ISO-8859-1) became an ISO standard.

The 16-bit Code

Unicode was to become a 16-bit code, rather than an 8-bit code. It should include all characters from all scripts used in modern languages. No Egyptian hieroglyphics, but Chinese, Japanese and Korean had to be included. With a 16-bit code you have up to 65536 different characters.

How many Chinese characters are there? A person is considered literate if he or she knows around 3,000 characters. But a good dictionary contains 20,000 different characters. But if you count them all, including characters only appearing in ancient texts and some proper names, you get close to 100,000.

Chinese, Japanese Kanji and the corresponding Korean characters are basically the same character set. much like our Dutch letter A is the same letter as the French letter A.

The “Han” characters from Chinese, Japanese and Korean should be unified. A set of around 20,000 was considered sufficient.

Hangul is the other script used in Korea. In Korean there are about 11,000 possible Hangul syllables, each consisting of three “letters”, stacked on top of each other. Korean Hangul is typically encoded using one code point per syllable. You can compare that to the accented letters in Latin. The é is composed of the letter e with an acute accent ´ stacked on top of it. Yet the letter é is normally encoded using a single code point instead of a separate letter e and a combining acute accent.

Combined CJK characters plus Hangul syllables would already consume half of the available code points. But all other scripts would have only tens of characters each, a few hundred at worst, when there were so many different accented characters. A quick back-of-the-envelope calculation showed that it would work out. Latin, Greek Cyrillic, Arabic, Hebrew, Thai, Devanagari, Georgian, Armenian, all of them combined would occupy a relatively small fraction of the code space.

The first version of Unicode was released in 1991 as a 16-bit code. Each character now occupied two bytes instead of one, but once you got over that, it would be simple. It took a few years for CJK characters and Korean Hangul syllables to be included.

Unicode always had to have some unused characters available, so new symbols (for example new currency symbols like the Euro sign) could always be added.

16-bit Unicode can be stored either in little-endian or in big-endian format. A Unicode file typically contains the value 0xFEFF, which is the byte order mark. The swapped value 0xFFFE is not a valid character and the system opening the file can see which byte order the file should be in.

It took nearly two decades for Unicode to be nearly universally adopted. In Western European countries, 8-bit codes were sufficient and in the USA, ASCII was sufficient. Why use twice the memory and disk space if ASCII works just fine?

UTF-8

One clever trick however, made the transition to Unicode in the USA a no-brainer. It was invented in 1992 by Ken Thompson and Rob Pike (of Unix and Plan9 fame). This is called UTF-8 (Unicode Transformation Format). Character codes between 0x00 and 0x7f are transferred as-is. So ASCII remains ASCII. Character codes in the range 0x80..0x7ff would be encoded by two bytes: one in the range (0xC2..0xDF), followed by a byte in the range 0x80..0xBF. Character codes in the range 0x800..0xFFFF would be encode by 3 bytes: on in the range 0xE0..0xEF, followed by two bytes in the range 0x80..0xBF. This could be extended to longer encodings for higher character codes.

UTF-8 has the following desirable properties:

• ASCII files are valid UTF-8.
• If a program is 8-bit clean (it ignores and.or transfers unchanged any bytes in the range 0x80..0xFF), it can cope with UTF-8 files. For example a compiler that knows only ASCII, can pass bytes in string literals unchanged and ignore comments, so it can handle UTF-8 source files to some extent.
• UTF-8 is self-synchronising. Any byte value in the range 0x80..0xBF cannot be the start of a character. Any byte value in the range 0xC0..0xFF is the start of a multi-byte character and it tells you how many trailing bytes are going to follow.

Efficiency depends on the script and language used:

• For ASCII files it is one byte per character, just as efficient as ASCII, twice as efficient as 16-bit Unicode.
• For Latin scripts it is almost as efficient as 8-bit character codes. The occasional accented letter takes two bytes instead of one, but in most languages these form only a small fraction of the characters.
• For Greek, Cyrillic, Arabic and Hebrew, all letters will take 2 bytes each, but digits, spaces, commas etc. will only take one byte each, so we are still better off than with 16-bit Unicode (but worse than with an 8-bit code).
• Even for languages like Chinese, we are not that worse off compared to 16-bit Unicode. Text files typically contain a large fraction of spaces, digits and punctuation, each of which takes only one byte.

Increased Processing Requirements

Even though UTF-8 made the transition from ASCII to Unicode easy, Unicode still requires considerable processing power compared to 8-bit character sets. This used to be a problem in the 1990s.

While an ASCII-only font takes a few kilobytes, a full Unicode font easily takes megabytes. Chinese characters require more pixels to be recognisable, compared to ASCII characters. Plus we have way more characters.

Arabic requires complex rendering algorithms to display correctly, because it’s a cursive script with no.printed form with separate letters. Both Arabic and Hebrew require right-to-left printing. Bidirectional text support is one of the trickiest and most counterintuitive aspects of text processing. A text in Hebrew is to be presented from right to left, but a multi-digit number inside such a text is to be presented from left to right again. But when there is a list of such numbers separated by commas, the numbers have to be presented with the first number rightmost, but the digits inside each number are from left to right. We can have English quoted words inside a Hebrew quote, inside an overall English text.

Converting a string to uppercase is trivial in ASCII. In Unicode we have quite a bit more characters to put in a lookup table and the code points of a lowercase letter and corresponding uppercase letter have no fixed relationship.

Sorting requires quite a bit more processing, You have to run a language-dependent collation algorithm on each string. Depending on the language, the letter Ö might sort after Z (Swedish), equivalent to OE (Some German conventions) or equivalent to O where the presence of an accent is only a second-level collation criterion (Dutch).

Some systems only handle a subset of Unicode well, for example only Latin, Greek and Cyrillic.

The 20.09-bit Code.

In 1996 it turned out that 16 bits was not really enough for Unicode. For one thing, all Chinese characters (around 100,000) had to go in. Further we wanted to include historic scripts like Egyptian hieroglyphics and cuneiform after all. Emoji weren’t even a thing at the time.

After playing with the idea to extend Unicode to 32, 31 or 30 bits, they finally made it a 20.09-bit code. To be exact, Unicode supports up to 17×65536 code points. This is the number supported by UTF-16. UTF-8 now requires up to 4 bytes to represent each Unicode character.

UTF-16 works as follows:

• Code points in the range 0xD800..0xDFFF are unassigned.
• Each character in the range 0x0000..0xFFFF represents itself as a single 16-bit value. This range is called the Basic Multilingual Plane. It excludes the range 0xD800..0xDFFF as these code points are unassigned.
• Each character in the range 0x10000…0x10FFFF is represented by two 16-bit values: one in the range 0xD800..0xDBFF and one in the range 0xDC00..0xDFFF. These two 16-bit values are called surrogate values and they can never appear on their own, was these code points are unassigned.

This way, the vast majority of characters in daily usage are in the Basic Multilingual Plane (0x0000..0xFFFF) and can be represented by a single 16-bit value. Programs that were designed to handle 16-bit Unicode, would continue to do so for these characters.

The more exotic characters are now represented by two 16-bit values. They take 4 bytes each, both in UTF-8 and in UTF-16.