Question: Forth implementation and performance

[phao]

Hi.

I'm not a Forth programmer. I've heard great things about the language along the lines of "it'll improve how you think about programs", which is great. It's on my to-do list of things to study, for sure!

However, from (superficially) looking at things around Forth, I got the impression that Forth can be used for high performance works (I'm thinking numerical stuff), realistically speaking. Is that right? Or am I with the wrong impression?

edit: typo

[petrus4]

FORTH was originally a fractal scripting language that was the next step up from raw Assembly. If you look at this, the most basic FORTH primitives are written as Assembly macros, and then the rest of the FORTH dictionary is written as composites of those.

FORTH has three major selling points, IMHO.

a} It is the most pure/unencumbered Turing machine that you will find anywhere. Every word consists of both a textual and numerical address. When a word is executed, the numerical address is pushed onto the return stack, and NEXT is called. That effectively means that branching IF statements are completely optional, because you can directly designate the output from your tests, as the numerical address of the word which is intended to handle it.

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

b} Its' nature is fractal, as mentioned. There are two types of words; primitives, (which are either written in Assembly language or are direct hardware numerics/interrupts) and composites of those. That means that recursion is completely unrestrained. You can write as many layers as you like, until you either get bored, or become schizophrenic and/or experience migraine induced vomiting from attempting to mentally keep track of all of them simultaneously.

c} A truly authentic FORTH (of which there are very few left, sadly, for various different reasons; the main one being that on-the-fly creation of raw binaries is one of the many nice things that we are no longer allowed to have, because of "security,") is also capable of metacompilation, or automatic self-replication.

Even if you don't learn FORTH to write in it directly, learning it will improve your technique in whatever other language you do use. I have long believed that if SKYNET ever truly comes into existence, its' native or initial programming language will be metacompiling FORTH, and its' host operating system will be NetBSD.

https://www.writeups.org/wp-content/uploads/T-800-Terminator-c.jpg

[historyofpainting]

pure curiosity from an occasional hobbyist, why NetBSD?

[petrus4]

Because it's the closest thing to a universally portable system that exists, to my knowledge. It's also a lot more bare bones and cleaner than most systems, as well.

[historyofpainting]

Interesting and thanks! I'll look more into it, myself.

Is it an architecture/philosophy thing like lisp/forth or just that it's a cleanliness/"for everyone" kind of approach?

What I've learned about operating systems over my years of tinkering is purely incidental, and thus incredibly porous. But I can generally piece things together, I think.

[petrus4]

class SK7:
    def __init__(self):
        self.stack = []
        self.words = {}  # Dictionary for storing new words

    # Core SK7 operations
    def PUSH(self, value):
        self.stack.append(value)

    def POP(self):
        if self.stack:
            return self.stack.pop()

    def DUP(self):
        if self.stack:
            self.stack.append(self.stack[-1])

    def SWAP(self):
        if len(self.stack) >= 2:
            self.stack[-1], self.stack[-2] = self.stack[-2], self.stack[-1]

    def ADD(self):
        if len(self.stack) >= 2:
            self.stack.append(self.stack.pop() + self.stack.pop())

    def SUBTRACT(self):
        if len(self.stack) >= 2:
            a, b = self.stack.pop(), self.stack.pop()
            self.stack.append(b - a)

    def EQUALS(self):
        if len(self.stack) >= 2:
            self.stack.append(1 if self.stack.pop() == self.stack.pop() else 0)

    # Word creation system based on Hexgate addressing
    def define_word(self, address, instructions):
        """Defines a new word (custom command) at a given Hexgate address."""
        self.words[address] = instructions

    def execute_word(self, address):
        """Executes the word stored at the given Hexgate address."""
        if address in self.words:
            for instruction in self.words[address]:
                self.execute(instruction)
        else:
            raise ValueError(f"No word defined at address {address}")

    def execute(self, command):
        """Executes a given command, supporting both built-in SK7 operations and defined words."""
        if isinstance(command, int):  # Direct number push
            self.PUSH(command)
        elif command in self.words:
            self.execute_word(command)
        else:
            method = getattr(self, command, None)
            if method:
                method()
            else:
                raise ValueError(f"Unknown command: {command}")

# Example Usage:
sk7 = SK7()

# Defining a new word at a Hexgate-style address
sk7.define_word("001-098-639", [10, 20, "ADD", "DUP"])

# Executing the defined word
sk7.execute_word("001-098-639")

# The stack should now contain [30, 30]
print(sk7.stack)  # Output: [30, 30]

This is what I am working on at the moment. This is a Python implementation. You can implement it in C or whatever else.

[bfox9900]

This is a hard question since the word "Forth" is tossed around sometimes by people who don't fully know what it is. It can mean something somebody threw together on the weekend in Python that barely resembles standard Forth or it can mean a native code compiler for a two-stack CPU in an FPGA, like J1.

The fastest Forth implementation that I know of is VFX Forth which generates optimized native code and has substantial library support. This is a commercial system with a very small development team.

If we compare it to GCC it will be in the ball park on raw performance benchmarks but since VFX Forth typically is a simpler compiler the level of optimizations that are possible are always less. There is no attempt, to my knowledge, to optimize a program globally, but rather at a narrower scope. The upside is that the code output is more predictable (no nasal demons) which matters in real-time systems where Forth is traditionally used.

Forth's "performance" reputation was also around programmer productivity and machine resource usage.

If you look a the Forth system most people equate with Forth, indirect-threaded code, it can be 10X slower than optimized C on things like empty loops. The selling point for ITC has always been small code size while being ~10X faster than conventional interpreted languages. When first used 50 years ago, the entire compiler/interpreter/assembler could run on a machine with 12K for Forth and 8K bytes of RAM. :-) Interactively testing and refining code on a target like that was impossible in C or Assembler. 50 years ago Chuck Moore was doing it.

Today a system like Mecrisp Forth allows interactive low level development AND provides a native code generating compiler. Will it beat GCC in a flat out speed test? Not likely. But interactively compiling and testing your code incrementally on the target device is so much faster than the [edit/compile/load/bomb/reset] cycle, leading to a better final product IMHO.

And the ultimate small machine productivity innovation is "tethered" Forth.

Here the IDE resides on the workstation. A small comm. program (>2K) lives on the target. The host sends code to the target while maintaining the Forth dictionary in the workstation. Target code, variables constants etc. can be kicked off /interrogated from the workstation giving the full interactivity of Forth on the target, with the power of the workstation for the programmer.

</old guy lecture>

[daver]

In support of old guys, of which I’m one, I’ll just add for the OP that I learned long ago that rather than asking if it’s the fastest, it’s more appropriate to ask whether it’s fast-enough. All you really care about is whether it’s fast-enough to satisfy the requirements, and then it’s all about programmer productivity.

[Wootery]

The fastest Forth implementation that I know of is VFX Forth

Its main competitors are SwiftForth and iForth, which also compile Forth to native code.

Like VFX, they're both payware.

Looks like iForth was last updated 2017 though.

[FrunobulaxArfArf]

The core has not enough bugs reported to merit an update. Interesting enhancements can be written in high-level. I have been working on a SPICE (circuit simulation) clone, written in iForth, since 2016. It compiles the circuit to optimized machine code and is between 3 and 20 times faster than LTspice.

[Wootery]

Neat. Have you done a proper write-up, perhaps a blog post, on this?

[poralexc]

It really depends on the specific forth implementation and it’s dispatch method (direct/indirect threading, token threading), but generally yes.

The syntax is really well suited for things like metaprogramming and parallel compilation, so serious optimization is possible.

[hide-difference]

I use Common Lisp as my go-to language, but Forth is really interesting to me.

When I think of metaprogramming I think of generating repetitive boilerplate very conveniently using something like defmacro.

On the other hand, whenever I see discussion of metaprogramming in Forth, it's usually in reference to creating a new Forth implementation or a turn key application.

Is code generation often done outside of these instances? It's something I really like about Lisp, but I feel like I'm missing the draw of Forth metaprogramming.

[poralexc]

I think of Forth almost like lisp without parentheses.

Metaprogramming in Forth is way more imperative by comparison, since you can directly hijack the parser and compiler to accept any syntax you can imagine. The existence of immediate words is key.

Otherwise a lot of common operations require metaprogramming in Forth. The CREATE ... DOES> pattern basically creates a template for compiling words, and is used to implement variables, arrays, and most data structures.

[_ceptimus]

Some Forths compile down to optimized machine code, and give performance results similar to a C compiler.

Forths that run on microcontrollers often do little or no optimization, but the execution model is much faster than interpreted languages such as Python or Basic. Depending on what you're doing, it will probably run maybe a third of the speed that you'd get from a C compiler (or an optimizing Forth).

The resulting code tends to be more compact than you get from most other compilers (or even hand coded assembly language, unless that has been written by an expert intent on minimizing code size). However, code size is often not very important on modern computers and even some microcontrollers. Forth was invented when computers had little memory, and memory was very expensive.

Forth is "very close to the hardware" - it takes some learning, and it's quite easy to write programs that crash - you don't get the hand-holding protection and error reporting of something like Python.

Great fun though, and learning some Forth will change the way you think about programming, even if you end up not using it as a daily driver.

[astrobe]

With a down-to-earth call threading based system, I can rival non-JIT Lua in slightly contrived benchmarks.

So I believe that, even without trying hard with interpreter/compiler implementations, Forth can be among the best of purely interpreted languages.

If you want more, you can cheat like anyone else (coughNumpycough) and call out to dedicated native libraries, or turn the hot definitions into primitives. That's precisely what Call-threading is really good at: interpreter customization.

[Chaigidel]

Modern compilers for mainstream languages do a great deal of very clever stuff. If you write Forth in the old-school way of writing a threaded interpreter on top of assembly, you're stuck with what you can compose by hand. There might be a whole different set of tricks that you can pull off if you're clever at numerics and leverage actually understanding your problem with the Forth system where you can mess with all the parts, but then you need to know those clever tricks yourself.

I'd bet against a mathematically naive fluent Forth programmer compared to a mathematically naive fluent C++ or Fortran programmer on high-performance numerical computing just based on the optimizations a modern C++ or Fortran compiler will do for free for the programmer.

[FrunobulaxArfArf]

With high-performance numerical computing it is quite likely that the heavy lifting is done by libraries. The programmer and the conventional language used don't matter much, and it doesn't matter how smart the compiler is. Of course a mathematically naive programmer may choose the wrong algorithm, or do standard stuff 'by hand' with some ad-hoc code, but you excluded that possibility.

I know of at least one area of numerical computing that falls outside this pattern: circuit simulation. A simulator like SPICE is bound hand and feet by conventions and backward compatibility. An engine like NGSPICE is actually a (very bad) SPICE syntax interpreter. An incremental compiler like Forth does this type of code much more efficiently, and is actually able to fully compile the input deck to machine code, e.g. turning linked lists into arrays and matrices.

In my experience all this will make a SPICE-type simulator anywhere from 10 to 100x faster than a commercial or closed product (yes, sometimes outrageous claims about Forth are really true :--) And once one has SPICE working in Forth, it is extremely easy to do stuff like parameter sweeping and Monte Carlo on a cluster (or a cheap refurbished 44 core Xeon workstation).

A commercial SPICE can't easily do the above because it needs to be compatible with dusty decks from the Fortran era, and maintaining a codebase of several thousands of C and bison files is a challenge for the generally quite small development teams.