Forth: The programming language that writes itself

Charles H. Moore and the pursuit of simplicity.

A talk by Dave Gauer, 2023. Made with minslides, which I made for this talk.
Use the J and K keys to go forward and backward.
You can also just scroll down like a regular web page.
Toggle notes/annotations with the N key.

Please note that these are slides for a talk.

HERE is the same content as a regular web page. (WORK IN PROGRESS!) This will eventually contain the content that was spoken (but better) along with any updates/fixes.

Oh, hello Hacker News!

The Legend

When I was a wee programmer, I would sit around the virtual Usenet campfires listening to the tall tales and legends of the elders.

The Legend

I learned about magical languages with lots of (((((parenthesis))))).

The Legend

I listened, wide-eyed, to true tech tales like The Story of Mel.

The Legend

And I heard tell of a programming language so flexible that you could change the values of integers.

The Legend

They said that language was called Forth and it was created by a mad wizard called Chuck Moore who could write any program in a couple screens of code.

The Legend

Years went by and I wrote a lot of PHP. I lost friends to the Internet Explorer 6 wars.

But I never forgot about the legend of Forth.

The blog series programming in the twenty-first century by game developer James Hague gave me the final push.

Forth was a recurring theme and it just sounded so darned interesting.

So I went on an adventure and I came back and I think I have some answers.

(Oh, and I confirmed the legend. I can make any integer equal anything I want. Stick around 'til the end to see that Forth magic trick.)

Postfix (RPN) notation

I thought this was what Forth was all about:

        3 4 +
        7
    

Noob:

$ bc
bc 1.07.1
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006,
2008, 2012-2017 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
(3 * 4) + (5 * 6)
42
    

Pro:

$ dc
3 4 * 5 6 * + p
42
    

Forth pro:

3 4 * 5 6 * + .
42
    

That's true, but then I learned some more...

Stack-based

        Op   The Stack
        --   ---------
        3     3
        4     3  4
        *     12
        5     12 5
        6     12 5  6
        *     12 30
        +     42
        .
    

Forth:

        CAKE DUP HAVE EAT 
    

Lack of explicit names for intermediate values.

If I ask you to add these numbers:

        2 6 1 3 7
    

Do you feel a need to give a name to each sum pair...or even the running total?

That's true, but then I learned some more...

Concatenative programming

Ah, this must be it because it sounds fancy.

Contrast with applicative language:

        eat(bake(prove(mix(ingredients))))
    

Concatenative language:

        ingredients mix prove bake eat
    

The canonical example of a concatenative language is Joy

Joy

Manfred von Thun inspired by Backus's 1977 ACM Turing Award lecture:

Joy

Joy is kind of like starting with a Lisp

Minus function parameters

Minus variables

Minus traditional control structures

Joy

All functions are unary (an arity of 1)

Stack in, stack out

A program is a list of data and functions

Joy's superpower: combinators

Combinators

Higher-order functions like map:

        inc = function(n){ return n + 1; };

        bigger = list.map(inc);
    

        list [inc] map
    

To Mock a Mockingbird

Identity

        (I x) = x
    

K and S

        (K x y) = x

        (S x y z) = (x z (y z))
    

Combinators: A Centennial View

Combinators let us factor out explicit loops.

        foo.map(bar)
    

        temp = [];
        for(i=0; i<foo.length; i++){
            temp[i] = bar(foo[i]);
        }
    

And in Joy, combinators can factor out all sorts of logic

Even different flavors of recursion made feasable by the uniformly unary functions.

Here's a factorial definition:

fac  == [null] [succ] [dup pred] [*] linrec
    

Forth has higher order functions too with word "execution tokens" (function pointers).

        EXECUTE
    

You can very compactly define words such as MAP, FOLD, and REDUCE.

Forth is definitely concatenative.

However,

        2 3 +
    

Forth: "Push 2, then 3 on the stack; pop both and add them; push the result, 5, on the stack."

Joy: "The composition of the functions 2, 3, and + is identical to the function 5."

All these aspects of Forth:

• Postfix notation (RPN)
• Stack-oriented
• Concatenative programming style

Are true.

They are all perfectly valid and complementary ways of describing the language Forth:

        CAKE EAT
    

Yes, postfix notation was definitely in the air (Zuse's Z3 1938).

And yes, stacks were known in the time of Forth's origins, but generally limited (2-4 items in registers).

But Joy (and the term "concatenative programming") come from the 1980s.

We need to go back to the 1950s.

Smithsonian Astrophysical Observatory and MIT 1958

Fortran on punchards

"Compiling took 30 minutes...you got one shot per day"

-- Chuck Moore, Forth, the Early years

Made an interactive interpreter.

On a computer with nothing we would recognize as a terminal.

Control an astronomical calculation program using statement numbers.

Arguably, this really is the origins of the thing that will be named Forth.

And the statement numbers would be equivalent to the words:

        WORD
        NUMBER
        INTERPRET
        ABORT
    

Free-form input unusual at the time, but super handy alternative to recompiling every time you want to change the numbers.

Stanford 1961

CURVE written in Stanford's own Algol implementation.

A much more sophisticated interpreter.

Now has a data stack and stack manipulation operators:

        + - * IF ELSE DUP DROP SWAP
    

Freelancin' 1965

"With the TTY came paper-tape and some of the most un-friendly software imaginable - hours of editing and punching and loading and assembling and printing and loading and testing and repeating."

-- Chuck Moore, Forth, the Early years

And terminals! terminal input and output

        KEY EMIT CR SPACE DIGIT
    

Also, in-forth editor (kinda IDE, kinda OS).

1968

IBM 1130 minicomputer at a big textiles manufacturer.

16 bit, 8k ram.

Backup was via punch/reader.

With disks, now we can have file names!

Limited to 5 characters.

Moore's "fourth generation" system becomes FORTH.

Now have a return call stack, allowing nested definitions

        : double dup + ;
        : quad double double ;
    

1970

Univac 1108

Same textile company.

Written in assembler and could call COBOL modules because that's what the corporate suits wanted in 1970.

Moore hates complexity

NRAO - Early 1970s

National Radio Astronomy Observatory - Computer control software for radio telescopes.

At this time, there are talks of patenting Forth.

Moore believes ideas shouldn't be patented.

He also rejects the standardization of Forth.

"All of my fears of the standard and none of the advantages of the standard have come to pass. Any spirit of innovation has been thoroughly quelched.

Underground Forths are still needed.

I said I thought the standard should be a publication standard but they wanted an execution standard."

-- Chuck Moore, 1997

Ported to the IBM 360/50

And to the Honeywell 316

And to the Honeywell DDP-116

And to the DEC PDP-11 (yes, that PDP-11)

All of this porting possible because of indirect threaded code.

Threaded code is not related to concurrency, i.e. "multi-threaded programming".

It's code that consists almost completely of calls to subroutines.

Could be machine code or interpreted.

Direct calls:

        call 0x0804000
        call eax
    or
        jmp 0x0804000
        jmp eax
    

Indirect calls:

        call [eax]
    or
        jmp [eax]
    

Calling indirect threaded code:

        mov eax, esi
        call [eax]
    

Storing threaded code:

<addr pointing to code>
<addr pointing to code>
<addr pointing to code>
<addr pointing to code>
    

Storing indirect threaded code:

<addr pointing to addr pointing to code>
<addr pointing to addr pointing to code>
<addr pointing to addr pointing to code>
<addr pointing to addr pointing to code>
    

Threaded code was much more common in the days of yore.

It is very dense, compact on disk and in memory.

That's Forth's origin story.

• Postfix notation (RPN)
• Stack-oriented
• Concatenative programming style
• Interpreted
• Highly adaptable to machine architectures
• Extremely compact

This gives us the why.

But somewhere along the way, I came across these quotes...

"To understand Forth, you have to implement a Forth."

-- Somebody on the Internet

"Take a look at JonesForth."

-- Everybody on the Internet

JonesForth

My NASM port of JonesForth: nasmjf

Opening the third eye by (re)implementing Forth.

JonesForth ascii art:

nasmjf ascii art:

But that's just the tip of the iceberg!

nasmjf inner/outer interpreter diagram:

To get from one code word to another uses a bit of assembly pasted at the end of each in a chunk called the NEXT macro. Here it is from nasmjf:

%macro NEXT 0
    lodsd     ; NEXT: Load from memory into eax, inc esi to point to next word.
    jmp [eax] ; Jump to whatever code we're now pointing at.
%endmacro
    

To get from one colon word to another uses a bit of assembly pasted at the end of each in a chunk called the EXIT macro. Here it is from nasmjf:

DEFCODE "EXIT",EXIT,0
    POPRSP esi            ; pop return stack into esi
NEXT
    

My comment in nasmjf attempting to explain the execution of indirect threaded code as a nested sequence of sequence of NEXT and EXIT and QUIT:

; QUIT (INTERPRET)
;     * regular word
;         DOCOL
;         NEXT
;         * regular word
;             DOCOL (codeword
;             NEXT
;             * code word
;                 <machine code>
;             NEXT
;             * code word
;                 <machine code>
;             NEXT
;         EXIT
;         NEXT
;    EXIT
;    NEXT
; QUIT (BRANCH -8 back to INTERPRET for more)

Absolutely nothing else drives the flow of an indirect threaded Forth application. It's addresses stored in registers and one or two line assembly instructions at the end of the word that manipulate the return stack as needed and jump to the next instruction.

Don't you see how simple it is?

Forth is complex when taken as a whole. But it is made of tiny pieces, each of which is very simple. The concept was created over a period of years on very constrained systems. Each part created only as needed.

Code words

Simple:

DEFCODE "SWAP",SWAP,0
    pop eax
    pop ebx
    push eax
    push ebx
NEXT
    

Code words

Simpler:

DEFCODE "DUP",DUP,0
    mov eax, [esp]
    push eax
NEXT
    

Code words

Simplest:

DEFCODE "DROP",DROP,0
    pop eax
NEXT
    

Code words in action

8 7      8 7
SWAP     7 8
DROP     7
DUP      7 7
    

Code words

nasmjf has 130 code words. Mostly for efficiency.

Code words

sectorforth has 10.

Regular ("colon") words

: SDD SWAP DROP DUP ;
8 7      8 7
SDD      7 7
    

How "colon" works

: SDD SWAP DROP DUP ;
    

Colon (:) fetches the word name and sets "compile mode".

Semicolon (;) completes the word's entry in the dictionary and unsets "compile mode".

• Putting the address of a word in memory
• Putting the code to push a literal onto the stack

Almost no syntax = simple interpreter

• WORD (Overloaded term, sorry. Blame Chuck!)
• Is it in the dictionary? (Compiling?)
• Is it a literal? (Compiling?)
• Otherwise, error!

8 7 SWAP DUP DROP

: SDD SWAP DROP DUP ; 8 7 SDD
    

Almost no syntax = extreme extensibility.

The definition of IF...THEN from jonesforth.f:

: IF IMMEDIATE ' 0BRANCH , HERE @ 0 , ;

: THEN IMMEDIATE DUP HERE @ SWAP - SWAP ! ;
    

Almost no syntax = extreme extensibility!!!!!

The definition of ( ) nested comments from jonesforth.f:

: ( IMMEDIATE
    1
    BEGIN
        KEY DUP '(' = IF DROP 1+
        ELSE ')' = IF 1- THEN
        THEN
    DUP 0= UNTIL
    DROP
;

(
    From now on we can use ( ... ) for comments.
...
    

The dictionary uses a linked list and word matching is done from the most recently defined word, so:

• You can redefine any word, even ones originally defined in assembly.
• Uses of previous definitions don't break because the links to the previous words still point to the original.
• You are in complete control.
• Forth = freedom

It's not just the language itself that is unusually flexible, the usage of Forth allows for really surprising flexibility.

Example paraphrased from Thinking Forth. Say we create a variable to hold a number of apples:

VARIABLE APPLES
20 APPLES !
APPLES ? 20
	

Forth variables put addresses on the stack.

We pepper our program with this APPLES variable.

Then we are told that we must now keep track of two different kinds of apples: red and green. What to do?

A new variable will store the current type of apples.

VARIABLE COLOR
	

A new variable and word will deal with red apples. The word sets the type of apple by storing the address of REDS in COLOR.

VARIABLE REDS
: RED REDS COLOR ! ;
	

Same for green.

VARIABLE GREENS
: GREEN GREENS COLOR ! ;
	

And change APPLES from a variable to a word that gets the current count by color:

: APPLES COLOR @ ;
	

Now we have to re-write any use of APPLES, right?

Wrong! The use of APPLES is identical. The syntax hasn't changed one bit for any existing code. We just need to make sure we've set the right color.

20 RED APPLES !
30 GREEN APPLES !

GREEN APPLES ? 30
APPLES ? 30

RED
APPLES ? 20
	

"I didn't create Forth, I discovered it."

-- Chuck, apocryphally

Making nasmjf gave me so many ideas, I had to try some experiments.

Meow5

An exercise in extreme concatenative programming where all code is concatenated (inlined).

Meow5

: meow "Meow. " print ;
meow
Meow.

: meow5 meow meow meow meow meow ;
meow5
Meow. Meow. Meow. Meow. Meow.
	

Meow5

Despite attempting to make something radically different, it's remarkable how many times Forth's solution was the path of least resistance.

"Aha! That's why."

Example: string quoting

        " Hello World."
    

Meow5 has this quoting:

        "Hello World."
    

But the effects are cascading...and limit flexibility

"Aha! That's why."

This is why I titled this "The programming language that writes itself"

• In the boostrapping sense
• In the metaprogramming sense
• In the "mathematical truth" sense

PlanckForth

Hand-written 1Kb binary

Forth is an idea that has taken form in countless applications, many of them custom and home-grown.

• Power plants, robotics, missile tracking systems, industrial automation.
• Embedded language in video games.
• Microcontrollers.
• Legacy: databases, accounting, word processors, graphics, and computation systems.
• On the modern OpenFirmware boot loader.

Jupiter Ace, 1982

Operating system: Forth.

OS and library of routines in 8 KB of ROM.

"Ten times faster than [interpreted] BASIC" and less than half the memory requirements.

Canon Cat, 1987

Operating system: Forth.

OS and office suite in 256 KB of ROM.

Innovative interface by Jef Raskin.

NASA

The 2003 list by NASA's James Rash is too long to easily list.

Space Shuttle Scientific Instrumentation Interface

"There is always great concern about software reliability, especially with flight software."

NASA Robot Arm Simulator

Control of 50-foot long, six-joint arm for Space Shuttle simulator. Extensive math routines convert two three-axis joystick commands into required joint velocities in six different co-ordinate systems. Entire system developed by one programmer in five weeks.

Shuttle Essential Services Node

Multitasking operating system, Forth language compiler, and libraries for UT69R000 radiation-hardened microprocessor used in Space Shuttle instrumentation.

• Direct execution of Forth
• Radiation hardened
• 8MHz clock, extremely low latency
• Two stacks, 256 words deep

Rosetta and Philae

First mission to send a lander to a comet!

Forth used for the Rosetta Ion and Electron Sensor instrument, using Harris RTX2010 Forth microprocessor.

The Philae lander is powered by two 8MHz Harris RTX2010 16-bit stack processors...used by the Philae CDMS to control all aspects of the lander.

Stop Writing Dead Programs

Awesome talk by Jack Rusher

Stop Writing Dead Programs

"...Space probes written in Lisp and Forth have been debugged while off world... If they had proven their programs correct by construction, shipped them into space, and then found out their spec was wrong, they would have just had some dead junk on Mars. But what these guys had was the ability to fix things while they are running on space probes... In addition, the spec is always wrong!"

-- Jack Rusher, Stop Writing Dead Programs, 2022

When we defeat the alien kill-bots and reprogram them, it will surely be with a Forth of some sort.

Forth is an idea

What about Chuck?

Charles H. Moore founded Forth, Inc in 1973. Has been porting Forth to various systems since.

colorForth

Fighting the good fight against software complexity since the 1950s.

"I am utterly frustrated with the software I have to deal with. Windows is beyond comprehension! UNIX is no better. DOS is no better. There is no reason for an OS. It is a non-thing. Maybe it was needed at one time.

-- Chuck Moore, 1997

"If they are starting from the OS they have made the first mistake. The OS isn't going to fit on a floppy disk and boot in ten seconds."

-- Chuck Moore, 1999

Instead of being rewritten, software has features added. And becomes more complex. So complex that no one dares change it, or improve it, for fear of unintended consequences. But adding to it seems relatively safe. We need dedicated programmers who commit their careers to single applications. Rewriting them over and over until they're perfect.

-- Chuck Moore, 2009

His real love seems to be hardware. Remember that Harris RTX2010? That's basically his design.

Has been designing hardware since 1983 starting with the Novix N400 gate array and dev board.

(An improved processor sold to Harris to become the RTX* chips.)

Has been designing chips ever since.

With his own VLSI software, "OKAD", written in 500 lines of Forth, of course.

GreenArrays. "Programming a 144-computer chip to minimize power" (2013)

144 asynchronous computers on a chip. Idle cores use 100 nW. Active ones use 4 mW, run at 666 Mips, then return to idle. All computers running flat out: 550mW (half a Watt).

"If you talk about molecular computers that are circulating in your bloodstream, they aren't going to have very much power and they aren't going to have very much memory and they aren't going to be able to use much energy.

-- Chuck Moore, Programming a 144-computer chip to minimize power, 2013

I think Forth-likes have a strong future as we look towards:

• Tiny, ubiquitious computers
• Solar power
• Heavily constrained VMs

The Legend Confirmed

Now, behold a new definition of the integer 4:

    : 4 12 ;
    

Which results in:

    ." The value of 4 is " 4 . CR
    The value of 4 is 12