Show HN: forthy2 – a higher level Forth-remix in C++

They make great foundations, since their simplicity allows them to be conveniently adapted to whatever purpose.

I too find dogmatic Forth a struggle to reason about, which is why we're here I guess. A type system in combination with generic methods help a lot, since most mistakes are caught in dispatch and give reasonable error messages.

Forth has a data stack and return stack. Messing with the return stack seems like a practical joke on the programmer sometimes. I guess we don't live with the same constraints that made forth popular in the first place.

I've been playing with Joy the last few years. (My project: https://joypy.osdn.io/ )

My experience has been that, once you get used to it, it's much easier to reason about Joy expressions than other notations/languages. The power of the combinators makes it easy to design functions.

Judge for yourself, here's the "Tak" function:

    def tak(x, y, z):
        if y < x:
            result = tak( 
                tak(x-1, y, z),
                tak(y-1, z, x),
                tak(z-1, x, y)
            )
        else:
            result = y
        return result

'''

Let's derive tak in Joy.

We know it's a recursive function that applies itself four times, so it should be pretty interesting. The genrec combinator expects four quoted programs:

    x y z [P] [T] [R0] [R1] genrec

The predicate and base case are easy:

    x y z [pop >] [pop popd] [R0] [R1] genrec

This leaves us with the two recursive quotes to be derived. We want something like this:

                x y z R0 [tak] R1
    ------------------------------------------------
       x -- y z tak y -- z x tak z -- x y tak tak

If we assume that the three input vars have already been duplicated twice then it's simple enough to write three small functions that prepare each triplet of values for tak:

    x y z [--] dipd tak x y z [--] dip rolldown tak x y z -- rollup tak tak

Considering just these three sub-functions in parallel...

    x y z [--] dipd         tak
    x y z [--] dip rolldown tak
    x y z  --  rollup       tak

...we let them be quoted and executed with the i combinator.

    x y z [[--] dipd]         i tak
    x y z [[--] dip rolldown] i tak
    x y z [ --  rollup]       i tak

We then quote [i tak] and extract it from the three sub-functions with app3.

    x y z [[--] dipd] [[--] dip rolldown] [-- rollup] [i tak] app3

This reduces the number of appearances of tak from four to two and takes care of providing the input values to each sub-function without explicit duplication. To complete the tak function we have to ditch the original three values from the stack and call tak one more time:

    x y z x' y' z' [popop pop] dipdd tak

Let's define some helper functions and review:

    K0 == [--] dipd
    K1 == [--] dip rolldown
    K2 ==  --  rollup
    popopopddd == [popop pop] dipdd


                     x y z R0 [tak] R1
    -----------------------------------------------------
       x y z [K0] [K1] [K2] [i tak] app3 popopopddd tak

From here we proceed somewhat automatically, our goal is to have a single quoted [tak] in our expression. First, quote the bare tak and the cleanup function and execute them with i, and extract the app3 call with dip:

    x y z [K0] [K1] [K2] [i tak] app3 [popopopddd tak] i

    x y z [K0] [K1] [K2] [i tak] [popopopddd tak] [app3] dip i

(If popopopddd represented a value rather than a function we might have used dipd on [app3] and just quoted tak. Or we could quote [app3 popopopddd] and use dip. However, doing it this way gives us a symmetry that we're going to use in the next step.)

This leaves two quoted functions that end in tak. Carve off [tak] from each with concat and abstract with the ii combinator:

    x y z [K0] [K1] [K2] [i] [tak] concat [popopopddd] [tak] concat [app3] dip i

    x y z [K0] [K1] [K2] [i] [popopopddd] [[tak] concat] ii [app3] dip i

We now have one appearance of [tak] but it's quoted, get it out with cons:

    x y z [K0] [K1] [K2] [i] [popopopddd] [tak] [concat] cons ii [app3] dip i

And we are done. We have definitions for R0 and R1:

    R0 == [K0] [K1] [K2] [i] [popopopddd]
    R1 == [concat] cons ii [app3] dip i

For ease of understanding, here is the above sequence played forward, as it were:

    x y z [K0] [K1] [K2] [i] [popopopddd]  [tak] [concat] cons ii   [app3] dip i
    x y z [K0] [K1] [K2] [i] [popopopddd] [[tak]  concat]      ii   [app3] dip i
    x y z [K0] [K1] [K2] [i] [tak] concat [popopopddd] [tak] concat [app3] dip i
    x y z [K0] [K1] [K2] [i   tak]        [popopopddd   tak]        [app3] dip i
    x y z [K0] [K1] [K2] [i   tak]  app3  [popopopddd   tak]                   i
    x y z           ...                   [popopopddd   tak]                   i
    x y z  x'   y'   z'                   [popopopddd   tak]                   i
    x y z  x'   y'   z'                    popopopddd   tak
           x'   y'   z'                                 tak

Putting it all together, we have a new library function (that needs a better name) and five wee auxiliary functions to make tak:

    popopopddd == [popop pop] dipdd

    tak.x == [--] dipd
    tak.y == [--] dip rolldown
    tak.z == -- rollup
    tak.R0 == [tak.x] [tak.y] [tak.z] [i] [popopopddd]
    tak.R1 == [concat] cons ii [app3] dip i

    tak == [pop >] [pop popd] [tak.R0] [tak.R1] genrec

The advanced combinator shuffling in the definition of tak is geometrically simple.

The patterns I used to manipulate the program code are very simple. In Joy, metaprogramming is easy, and most programs are meta-programs in the sense that they build other programs and then execute them as a matter of course.

I should note that I'm working too hard maybe, Factor language provides for something like e.g. writing:

                   x y z [tak] foo
    ------------------------------------------------
       x -- y z tak y -- z x tak z -- x y tak tak

where:

    foo == [\3 -- \2 \1 \0 i \2 -- \1 \3 \0 i \1 -- \3 \2 \0 dup b] interpolate i

It's a quote with special interpolation markers that are replaced by the stack item that they index (meaning \0 is replaces with [tak], \1 with z, etc.) followed by an interpolate function that does the replacing.

A facility like this is pretty convenient and almost certainly more efficient. To make it work in Joy there would have to be some modifications to support the special interpolation markers.

On the other hand, the use of app3 implies concurrency that is not explicit in the interpolated version.

I had a lot of fun playing with Factor several years ago. The problem, as you pointed out, was that it was indeed difficult to reason about programs. The stack is implicit, so when you glance at code to try to figure out what it does, you have to manipulate the stack in your head as you think about it, effectively carrying out the computation anyway. That became too much for me after a while, and I gave up. Maybe I should pick it up again, though.

I'm sorry, I'm not quite following. I don't get what you mean by dropping the stack in this context. Could you point to where in the README you're having trouble?

The implementation is definitely less Forthy as a consequence of embedding in C++ rather than aiming for rock bottom.

Bodies, or scopes, are first class though. You can take their references and/or quote them.

Aight, seems like I need to adjust the required CMake version. It would help if I had any idea which version introduced add_link_options.

Anyways, the easiest way forward for you is most probably to upgrade your CMake.

One of the main motivations in this case is embedding in C++, rather than trying to replace it. So far the language is implemented as a high level VM/interpreter, I'm planning to eventually emit C++ to get standalone executables and a 20-30% speed up.

So no, I didn't do anything :) It's all C++, all the way.

I suspect most standard Forths don't give a crap about the CPU, they like to implement everything themselves.