A Forth Vocabulary for Iteration | Hacker News Reader

A Forth Vocabulary for Iteration

blog.information-superhighway.net

112 pointspanic22 comments

> At some point I came across some writing that suggested that Forth had a “loop control stack”. Wouldn't it be nice if I could implement some kind of loop control stack that worked for all kinds of iteration?...I added two loop control stacks – what I call the i-stack, and the next-stack. The i-stack contains the current value(s) being iterated over, and is read from with the i and j words like normal.

So much of what we do has already been done. In Brad Rodriguez' "Moving Forth" series (c 1993) he talks about classical Forth having 5 registers, 2 of which point to stacks. He then explores which of these 2 could point to a hardware stack, and how this decision has been taken historically with other Forths.

I like someone who blogs about Forth in 2023. But if they are truly curious about Forth they'll find themselves reading a bit of history. Forth has been around for quite some time now.

http://www.bradrodriguez.com/papers/moving1.htm (speaking of history, this paper itself has a nice compilation of references)

Btw information-superhighway.net does have some excellent articles where they dig a bit more into history behind things: https://blog.information-superhighway.net/spellcaster

> I like someone who blogs about Forth in 2023. But if they are truly curious about Forth they'll find themselves reading a bit of history. Forth has been around for quite some time now.

I've found that many people passionate about something will have read quite a bit about its history. Hardly seems sporting to imply that the author is ignorant of everything; perhaps this is something they overlooked.

Off hand, this reminds me a lot of the Lua "generic for loop" logic:

https://www.lua.org/manual/5.4/manual.html#3.3.5

I always found it weird to use, but it is a pretty simple API for implementing generic iterators.

Speaking of Lua, it reminds me of LuaJIT and Mike Pall with his hot loops coded in assembly. There are places where performance increases weigh more, iteration is definitely a candidate.

So elegant. Always loved Forth in a platonic kind of way, just couldn't ever stand the stack shuffling myself.

Always loved Forth in a platonic kind of way

I love this turn of phrase and will definitely steal it. In my hobby electronics stuff (esp mc68k) I always think 'I need some software and this is exactly the kind of thing Forth should be good for', and while I have managed to write a Forth once or twice, I always noped right out of making it a place I'd want to spend all my (computing) time.

stack shuffling is a code smell in Forth; cf https://blog.information-superhighway.net/forth-the-local-va...

(I believe Moore has a small, fixed-size stack on his chips; go too deep and you start reusing stack slots. Somewhere I've seen code that rolled over a fixed stack on purpose but I can no longer recall if it was in a ColorForth or in an x86 math coprocessor)

>most implementations in C switch between several nearly-identical code blocks depending on how steep the line is

...which the code in this blog post avoids by defining words that compare dx with dy and return pointers to the "short" and "long" coordinate? You could do the same in C or most other languages.

The problem is that in other languages, a Sufficiently Advanced Optimizer™ could at least in theory analyze the source code, and then emit those nearly-identical code blocks, whereas Forth is more like a platform-independent macroassembler: there is no zero-cost abstraction, every word you write in the source code will result in some predetermined machine instructions being executed (and usually with extra interpreter overhead).

Actual assembly code seems less confining, since at least you have a few different registers and addressing modes to play with, rather than just a stack.

I still kind of like the idea of Forth, but pretty much agree with this article: http://yosefk.com/blog/my-history-with-forth-stack-machines....

> every word you write in the source code will result in some predetermined machine instructions being executed

Not strictly.. I wrote a partially optimizing Forth compiler that could combine compiled words when building new words that used them from the interpreter, analyze the generated assembly for unnecessary stack movement of arguments, and eliminate the stack movement and if necessary emit MOV instructions to fixup the output results into the correct input registers.

This was not terribly difficult. The harder part was susequently decoding the concatenated x86 instruction streams to do this type of analysis, but once the PUSH and POP trains were spotted, they were super easy to just eliminate.

With careful coding of the assembly words, you could guarantee that common expressions never needed any MOV fixups and could just pass results that were sitting directly in the registers.

Any chance you thinking about the rollover of a number in "The Story of Mel, A Real Programmer"?

No, it was defo in one of the two places I mentioned, but The Story of Mel is great.

I like how they called them desk-sized not because they were the right size to sit on a desk, but because they took as much floor space as a desk: https://www.masswerk.at/nowgobang/images/lgp-30-features.jpg

I wish I'd known about Forth in my first job in the late 80s. We were writing 8-bit assembler on small slow machines, and I've always suspected that Forth could have been a good productivity solution for those circumstances.

Fast forward to the 21st century and I still think Forth is cool, but I don't have any actual urge to use it.

Mitch Bradley came up with a nice way to refactor the Forth compiler/interpreter and control structures, so that you could use them immediately at top level! Traditional FORTHs only let you use IF, DO, WHILE, etc in : definitions, but they work fine at top level in Mitch's Forths (including CForth and Open Firmware).

I've written about it before on HN:

https://news.ycombinator.com/item?id=29261810

Speaking of Forth experts -- there's Mitch Bradley, who created OpenFirmware:

[...]

Mitch Bradley's 68k forth lets you use interactive conditionals and loops in the top level outer interpreter!

I think he wrote a paper about that feature, which I might be able to dig up ... Here's something related he wrote about refactoring the outer interpreter, but not what I'm thinking of:

https://groups.google.com/forum/#!topic/comp.lang.forth/lKQj...

[...]

I got a quick reply from Mitch Bradley!

Yes I wrote a paper but I probably can't find it. The easiest place to look would be in the Open Firmware source.

https://github.com/MitchBradley/openfirmware/blob/master/for...

The magic is all in +level and -level. Search for those in kernel.fth to see other places they are used to achieve a similar effect, e.g. in abort"

For an alternative but effectively equivalent formulation, see:

https://github.com/MitchBradley/cforth/blob/master/src/cfort...

and

https://github.com/MitchBradley/cforth/blob/master/src/cfort...

[...]

https://news.ycombinator.com/item?id=29264309

In PostScript that would be:

/PostScript Know? { Honk! } { /PostScript Learn! } ifelse

FORTH doesn't have an IFELSE unless you define it yourself of course, but it would have no way of telling which part of your code was the conditional, part to do if true, or part to do if false, since white space and line breaks have no meaning to it, except for a few cases like \ comments. The IF comes between the conditional and the part to do if true, the ELSE comes between the part to do if true and the part to do if false, and the THEN comes at the end.

The structure of PostScript code, conditionals, and flow control is homoiconic, made of nested arrays, like polymorphic JSON arrays, where FORTH code is flat untyped arrays of threaded pointers with relative branching.

Forth has an "inner interpreter" called NEXT that threads from one pointer to the next (sometimes implemented as one machine language instruction, or just a few), and also an "outer interpreter" or compiler that translates text into threaded code for the inner interpreter.

https://en.wikipedia.org/wiki/Polymorphism_(computer_science...

https://en.wikipedia.org/wiki/Homoiconicity

https://en.wikipedia.org/wiki/Threaded_code

Here's Mitch Bradley's implementation of interactive control structures (IF, ELSE, THEN, BEGIN, UNTIL, AGAIN, REPEAT, WHILE, DO, LOOP, etc) in the outer interpreter of his FORTH system, which actually allows you to use conditionals and loops at the interactive top level of the interpreter, not just in compiled words (which solves a traditional and frustrating limitation of classic FORTH).

https://github.com/MitchBradley/openfirmware/blob/master/for...

Here is an alternative but equivalent implementation of interactive Forth control structures in his CForth (Forth implemented in C, of course):

https://github.com/MitchBradley/cforth/blob/master/src/cfort...

Here's some more of Mitch's beautiful code from OpenFirmware, his Forth kernel meta-compiler written in Forth, which supports 8, 16, 32, an 64 bit, big-endian and little-endian architectures, as well as direct, indirect, and token threaded code:

https://github.com/MitchBradley/openfirmware/blob/master/for...

https://en.wikipedia.org/wiki/Threaded_code#Direct_threading

https://en.wikipedia.org/wiki/Threaded_code#Indirect_threadi...

https://en.wikipedia.org/wiki/Threaded_code#Token_threading

[...]

https://news.ycombinator.com/item?id=29265144

Some FORTH systems even have a "metacompiler" that lets one FORTH system compile another FORTH system for the same or different CPU, word size, byte order, threading technique, with or without a built-in compiler, etc, from the same source code!

OpenFirmware (the FORTH burnt into boot roms of SPARC, PowerPC, OLPC, and other systems) is a great highly refined example that supports many different architectures:

openfirmware/forth/kernel/metacompile.fth

https://github.com/openbios/openfirmware/blob/master/forth/k...

openfirmware/forth/kernel/meta1.fth

https://github.com/openbios/openfirmware/blob/master/forth/k...

The OpenFirmware kernel is a Forth meta-compiler, which can compile itself on any architecture, and also cross-compile for different target architectures.

It has cross-architecture extensions to FORTH (like \16 \32 comments and /n /n* generically typed words) that make it possible to write platform, word size, byte order, and threading independent code, and compile images (stripped or with headers) for embedded systems (like the OLPC boot ROMs) and new CPU architectures (like Sun's transition from 68K to SPARC), and share code with a more powerful development environments.

https://en.wikipedia.org/wiki/Compiler-compiler#Forth_metaco...

[...]

https://news.ycombinator.com/item?id=29264489

[...]

Here's some IBM-PC Forth for the CAM-6 cellular automata machine that was block based -- check out the unique idiosyncratic right-justified reverse-indentation style (starting with KGET), which is not standard Forth style, but sure looks cool and poetic, like E E CUMMINGS ON CAPS LOCK:

https://donhopkins.com/home/code/tomt-cam-forth-scr.txt

https://donhopkins.com/home/code/tomt-users-forth-scr.txt

[...]

https://news.ycombinator.com/item?id=29261868

Coco Conn and Paul Rother wrote this up about what they did with FORTH at HOMER & Assoc, who made some really classic music videos including Atomic Dog, and hired Charles Moore himself! Here's what Coco Conn posted about it, and some discussion and links about it that I'm including with her permission:

[...]

Forth & Charles Moore

We hired Forth, Inc. and got Charles Moore, the inventor of FORTH to program the console host computer. I learned FORTH and worked with Charles. I programmed the 2K byte EPROM in each visual channel. On the Master Z80 system we ran PolyForth a multi tasking system in 32K bytes. We had an extra 16K RAM for buffers and things. If I remember right, the system ran four tasks, but that was 20 years ago, my memory may be hazy.

Anyway, I learn not only FORTH from Charles Moore, but also how to factor code in to small reusable routines, WORDs they're called in FORTH. I learned Object Oriented Programming without knowing it. Also a lot of use of vectors. Its a cool language. Charles Moore was a great inspiration to me, and really taught me a great deal that they never taught me in computer programming school.

[...]

You worked with Charles Moore? That sounds like a heck of a good story. I feel like he's so underrated as a computer luminary.

I worked with Mitch Bradley at Sun, but not Charles Moore. That was an excerpt from the story written by Coco Conn and Paul Rother about the company they founded with Peter Conn, HOMER & Assoc, which made an early interactive video editing and special effects system that was written in FORTH, which they hired Charles Moore to work on.

The whole story is here, with links to some of the classic music videos they made (like Atomic Doc, Abracadabra, Bongo Bongo, and the Flying Logos SigGraph demo):

https://news.ycombinator.com/item?id=29261868

George Clinton - Atomic Dog (Official Music Video) HD

https://www.youtube.com/watch?v=LMVZ36VA0wg

Steve Miller Band - Abracadabra

https://www.youtube.com/watch?v=tY8B0uQpwZs

Steve Miller Band - Bongo Bongo

https://www.youtube.com/watch?v=_NrsRZdMI-A

Flying Logos for 1989 Siggraph Electronic Theater:

https://www.youtube.com/watch?v=9hIOfEiy4lc

>First shown at the 1989 Siggraph Electronic Theater to a rave response, this 3 minute humourous film went on to win several top computer graphic awards that same year including Niccograph of Japan.

>With a voiceover soundtrack written by Peter Conn and animations assembled from various productions done during the previous year, the film unfolds as a client calls into Flying Logos, Inc. to have his logo visualized. In the course of the conversation, we see and hear the juxtaposition of the technical versus the anticipated, the imagination versus the possibility.

>But more important than amusing audiences and winning awards, this landmark film marked the debut of the PC as a fully capable production system to do broadcast quality work, which up to then was only done by large companies with very expensive graphic workstations.

[Don: I truly believe that in some other alternate dimension, there is a Flying Logo Heaven where the souls of dead flying logos go, where they dramatically promenade and swoop and spin around each other in pomp and pageantry to bombastic theme music. It would make a great screen saver, at least! Somewhere the Sun Logo and the SGI Logo are still dancing together.]

http://leftbrain.us/rotherHistory/homer.html

>In front of the Optical Printer 7-bit Paint system, Homer and Associates, circa 1982.

>Homer and Associates was really one of a kind kinda of company. Founded by Peter Conn, originally I got hired to program Homer II, a visual realtime mixing console. Homer I is another whole story, but before my time. Homer II consisted of 16 slide projectors, 4 movie projectors, a 4 track tape recorder, 24 visual channels (each with its own Z80) touch sensitive sliders, a master Z80 S100 bus system and featuring "the joy stick bumper " control, which looked liked the gear shift right out of a 1964 mustang convertible.

>The idea was that you would program a visual sequence, then play the sequence in sync with the sound track on the joystick, including cascades, bumps, cuts, etc. The whole thing would be recorded, and if you wanted to, like an audio mixer, go back and do over dubs, making corrections. Then once you had the perfect "hero" recording, you take the 8" floppy disc with the hero recording and the trays of slides to the optical printer, and record it to motion picture film, making multiple passes, one tray at a time. Now that I think about it, it was a crazy idea. We actually got the whole thing to work. And it worked great!

George Clinton - Atomic Dog (Official Music Video) HD

Forth and P-Funk. I certainly didn't get up this morning thinking I'd end it knowing they were related. ^mindblown^

Damn. Now I want this for Mecrisp Stellaris (a self-hosted Forth for ARM v6M/v7M) with good code generation.

There’s a concatenative languages discord btw. Email/msg me [contact-details-redacted]

There is a Discord for Factor, too.

https://discord.gg/QxJYZx3QDf

I just love seeing people still hacking with FORTH

Just curious, are Forth users mostly embedded/hardware devs?

I'm a mobile app dev, don't see how Forth is practical for my work. And if I want to go low level, well there's assembly.

Generally, yes, but I've seen a lot of GUIs created in FORTH as well. It's "general purpose" enough that you could use it pretty much anywhere, though your experience would be best with a FORTH that supports C FFI and in contexts where that's a reasonable approach. I do high level scripting in FORTH sometimes, for example.

The issues I have with FORTH is it's actually pretty hard to use it for substantially complex/large applications due to lacking many modern facilities for organizing code. Most don't have the concept of modules and simply including other .fs files is not sufficient due to namespace collisions

Reply on news.ycombinator.com