I was talking to someone in #forth on libera.chat today about a very nice object system that he's built, and it gave me some ideas that I wanted to play with. I ended up hacking together a little closure implementation in C. I'll probably never use it in this form, and I don't have my own software blog, so I'll share it here.

The goal:

By "closure" I mean that I want to be able to allocate a function that is bound to some persistent state. I want to be able to call this function or pass it as a callback without ever having to pass its state with it. In this example, the returned closure will take a single integer argument, but what's executed (what you get to write) takes two arguments: the integer, and a pointer to your closure context. So imagine, for example, a situation where you must interface with some API that accepts a callback:

int shittyapi(void (*callback)(int));

However, for reentrancy or whatever reason, you want to pass more arguments to your callback. You could do some stuff with thread-local store and maintain a make-shift context stack (I have done this before to use qsort() in a reentrant way when qsort_r() wasn't available), but it can be kind of ugly. Wouldn't it be nice if you could write your callback:

int myfunc(int x, void *mycontext);

But pass to shittyapi() some form of this which takes only the integer and magically keeps track of your mycontext pointer? E.g.,

struct closure *c = mkclosure(myfunc, sizeof (struct mycontext));
*(struct mycontext)c->arg = {
<initialize your context data here>
};
shittyapi(c->func);

How it works, the short version:

In the spirit of forth, when you create a closure, it allocates and populates some memory with the following:

<machine code to add the context arg and jump to your function>
<the address of your function>
<your context data>

At first I toyed with writing the code to generate that machine code. I think that ultimately that would be the optimum solution because it would eliminate some indirection and save some space. But for the sake of simplicity, it occurred to me that if I use an indirect jump, then that machine code can be the same regardless of where it is relative to its target function! Which means I can use GCC's inline assembler to generate a copy of the machine code for me, use symbols to mark its bounds, and then just memcpy() it wherever I need it.

Of course, the glaring limitation here is that the function signature is baked into the implementation. The example I described above can only transform int (*)(int) into int (*)(int, void *), and the example in the implementation below can only transform void (*)(int) into void (*)(int, void *). So obviously the next step would be to pipe sources through some preprocessor to generate these (which as I understand is how objective-C and Vala work), but that's beyond the scope here. I just wanted to see it work. And it does!

Source below.


/* includes includes includes... */
#define _GNU_SOURCE
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

/* The first challenge is that, for this to work, I will need to be able to
* generate machine code at run time and execute it; however, pages used by
* malloc() are mapped without the executable protection bit, so I'll have to
* map my own memory for this purpose. In a real application this would of
* course be managed somehow so that you can free closures and reuse this
* memory, but for this exercise I'm just going to stupidly allocate by
* advancing a pointer and not support reuse. */
static char *mem;
void mem_init(void)
{
mem = mmap(0, 0x1000, PROT_EXEC | PROT_WRITE | PROT_READ,
MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
if (mem == MAP_FAILED) {
perror("mmap");
exit(1);
}
}

/* As mentioned before, stupid allocator is stupid. Just return the next address
* and advance the pointer to the next available. There is no way to free
* closures and reuse this memory in this example. */
void *mem_alloc(size_t n)
{
n = (n + 7) & ~7; /* keep it quad-aligned */
void *p = mem;
mem += n;
return p;
}

/* What's returned to the caller. The caller gets the struct back just so that
* he may initialize his data, but he is not required to keep this around. Once
* the contents of arg[] are initialized, the caller is free to forget about
* this and only pass the function pointer around. func is the closure, and it
* knows how to find its arg address. */
struct closure {
void (*func)(int); /* the returned closure */
char arg[]; /* data that's been "closed over" */
};

struct closure_hack {
/* Here I store the passed-in function just before what's returned to
* the caller so that the trampoline can jump to it. A fancier way to do
* this would be to actually write something to generate the appropriate
* machine code to jump directly to the passed-in function instead of
* using a fixed indirect jump. The indirect jump is easier to implement
* because the machine code is always the same, so it can simply be
* memcpy()ed into place. */
void (*func)(int, void *);
struct closure c;
};

/* Create a trampoline template. This code will actually never be executed in
* this location, but it will be copied to closure memory and executed there
* (hence the use of indirect-through-%rip instructions for position
* independence).
* The trampoline[] and trampoline_end[] symbols are just empty symbols which
* will be resolved to addresses by the linker so that they can be used to
* determine the location and size of this code fragment later. */
extern char const trampoline[], trampoline_end[];
__asm__ ("\
/* I need for the parameter field (trampoline_end) to be\n\
* quad-aligned, and I need for the size of this code fragment to be\n\
* constant regardless of its location, so it also must be\n\
* quad-aligned. */\n\
.align 8\n\
trampoline:\n\
lea trampoline_end+16(%rip), %rsi\n\
jmp *trampoline_end(%rip)\n\
/* As mentioned above, align the parameter */\n\
.align 8\n\
trampoline_end:\n\
");

/* The closure allocator! Give it a function and a data size and it returns a
* new closure. The data c->arg is left for the caller to initialize. */
struct closure *mkclosure(void (*func)(int, void *), size_t n)
{
size_t tn = trampoline_end - trampoline;
char *p = mem_alloc(tn + sizeof (struct closure_hack) + n);
memcpy(p, trampoline, tn);
struct closure_hack *c = (struct closure_hack *)(p + tn);
*(void **)&c->func = func;
*(void **)&c->c.func = p;
return &c->c;
}

/* An "accumulator" closure; take a pased-in integer, add it to a persistent
* accumulator value, and print the result. */
static void accumulator(int n, void *arg)
{
int *a = arg;
*a += n;
printf("%d\n", *a);
}

/* Make and return an accumulator that starts at the given init value. */
static void (*mkaccumulator(int init))(int)
{
struct closure *c = mkclosure(accumulator, sizeof (int));
*(int *)c->arg = init;
return c->func;
}

int main(void)
{
mem_init(); /* mmap my special executable memory pool */
void (*a)(int) = mkaccumulator(0); /* make an accumulator starting at 0 */
void (*b)(int) = mkaccumulator(100); /* make another one, start it at 100 */
a(1); /* prints 1 */
b(2); /* prints 102 */
a(3); /* prints 4 */
b(4); /* prints 106 */
return 0;
}

*(void **)&c->func = func;
*(void **)&c->c.func = p;

Whoops, that top one doesn't need to be like that. That can be a straight assignment "c->func = func;" for type-checking. That was an artifact of copying the line below it. C is anal about assigning (void *) to function pointers, so you have to do some dirty stuff to make it happen.

I wish I had even a little bit of a clue what I was looking at there. It seems lke a lot of effort went into it.

2024-01-23 14:38 from IGnatius T Foobar <ajc@citadel.org>
I wish I had even a little bit of a clue what I was looking at there.

It seems lke a lot of effort went into it.

I've been debating another progress update post, but I haven't been able to write a draft yet that isn't laughably long. The short version: as predicted, I fell off the wagon and spent the last three months staring at my screen tinkering with FORTH and FORTH-related ideas. It's been a journey. Lots of thoughts going, now, and I don't know which ones to chase first.

Oops, and I forgot to close with

And I'm losing my mind.

2024-01-25 01:10 from Nurb432 <nurb432@uncensored.citadel.org>
Welcome to the rabbit hole. Enjoy your stay.

Oh, I've been here before. It's exactly why the last time I decided I don't need to be in the language or compiler design business.

Here's a peek of part of what I'm going through now. I've written nearly the same FORTH interpreter at least five times over in the past three months -- once in assembler, a couple of times in my assembler FORTH itself (long story short: failed meta-FORTH attempts), once or twice in C, and the latest one is in assembler again (sort of a return to roots but with lessons learned). In doing so, I've been aggressively refining the parsing loop (along with several other things). And now I've reached a point where I'm curious about taking some of the techniques I've refined and parsing something other than FORTH.

And then I have started thinking about project development in general. I think that's what this is ultimately all about for me. If you want to develop a desktop application, you usually sit down and start writing code in a new directory. You might install some dependencies and tie them into your build system (whether it be Make or something else). If it's an embedded application, like bare metal firmware, then you'll probably install a cross compiler. The issue is that all of these are very dependent on your OS, your package manager (if there is one), your SDK (if you're unfortunate to be forced to use one for some embedded target), and so on.

I have never been comfortable with these out-of-tree build dependencies. I begrudgingly tolerate (or rationalize) the compiler and standard Unix tools like Make, sh, awk, etc., but have always done my best to avoid "to build this you need to install a hundred development libraries and you have to have Python version 69 and JVM 9000 and you need to do it in a docker container and it only works if the OS image is RHEL 7.7.8.7.2.2.sqrt(-1).2.2.0.2.1-rc34." Some of these packages, I wonder: does anybody actually know what all ends up in that binary?? And don't even get me started on Yocto. It's basically what I just described, but at the OS level, and intended for building Linux distros for "embedded targets." Software security nightmare in a nutshell. If you thought
IoT was bad in concept, you should see the shit they're using to build the OSes for them. Anyway, I'm going off on another rant.

I get the impression that the "old school" FORTH development model (platform differences aside) was the polar opposite to this. Not only did Moore and friends not use cross-platform libraries, I don't think they even used a common cross compiler! When CM wanted to start a new project, I think for him, step one was: write a compiler.

I'm not sure if, in the end, I'll be using FORTH or something else, but I think I'm headed toward experimenting with this sort of work flow. And that finally brings me to my current dilemma: what exactly does that look like in execution? My train of thought has gone through three options so far.

1) system/forth -> project/forth source -> target source -> target image
This is more or less where I started and why I wrote a FORTH in assembler and then tried to write a couple of meta-FORTHs. The idea was to have a single host FORTH interpreter (say, /usr/local/bin/zelgoforth) that could serve as the base language for defining cross compilers, and each project would include the source for its own cross compiler (which is interpreted by zelgoforth), which in turn parses the target source to produce a target image.

2) system/cc -> project/forth.c source -> project/forth compiler -> target source -> target image
The problem with option #1 is that it still pulls in an external dependency -- zelgoforth -- and worse, it's an obscure dependency. So then I thought, what if the project-specific FORTH cross compiler is bootstrapped from C, which is ubiquitous? Now you can build the project on any system capable of compiling C for itself, which is every major desktop platform. The downside is that it's actually easier to write FORTH in assembler or in itself (with a built-in assembler) than it is to write FORTH in C.

3) system/cc -> project/zlang.c source -> project/zlang compiler -> target source -> target image
And the natural progression from #2: if I concede and write the cross compiler in C, then why does the target language have to be FORTH? It could be anything. In fact, this removes a middle man. I've always heard "FORTH is a language where you build your language to describe the problem." Well, why don't I just build the language to describe my problem in the cross compiler I'm writing for the project in the first place? And it could be simple, too. It could have a C-like syntax or a Haskell like syntax or anything I can imagine, but it doesn't have to support all of the features those general purpose languages support. It only has to support exactly enough to write the intended application. And if it doesn't support enough to add some feature in the future: well, good news! The compiler source is right there, you can just add the feature. Imagine writing code in a C-like language, but there are no typedef, struct, or union definitions. Seems very limiting, right? But you don't need them. If you want to define a new type, you just add it to the compiler, which is source controlled right alongside with your target source. Strangely, this is both very "FORTHy" (you write a DSL specific to your application), and also very "unFORTHy" (flat out reject compiler extensibility from target source, just change the compiler source).

And this is what I mean about not knowing what to pursue. I think that I have reached a decision point in front of me, and I'm not sure yet where I want to go. Maybe I need to go for a walk through the mountains or take some LSD, whatever it is that new age weirdos do to "find themselves," to arrive at which path has the most promising future.

Or maybe I need to set this down and put my attention toward something that actually produces tangible results, like running a horse farm or something.

You have to know your target environment. Portability and size are rivals now. If you really are developing for embedded systems, you can target specific hardware (making the software smaller) or build an abstraction layer (making the software larger). Gone are the days where you mount a floppy and it just runs :)

I think you're operating in an uncommon space. It looks like most people either pig out on hardware so they can put a Java runtime on their microwave, or operate in the microcontroller world where small is still possible.

There has been progress here, but I'm not at a place yet where I want to share. Stay tuned!

Geezeless crackers! It's been a long time since I wrote anything in Java, and I hadn't realized how complicated the world has become. It's now impossible to write anything in Java without installing gigantic build frameworks. Vast expanses of dependencies and declarations and build tools and lifecycle management and directory hierarchies.

LoanShark and others who "do java" are probably smiling right now and saying "ahhhh.... yup."

So now I've got to spend half a week learning the environment so I can write 100 lines of code that will plug into an existing system. For those who have forgotten, this is called "progress".

Hey wow, it's been since 2018 that I wrote any Java on a regular basis. These days I get paid to write Elixir, in the Phoenix framework.



Initially I was kinda put-off by the lack of strong/static typing, but you quickly learn to deal with this and you don't miss it much.

The purely-functional/immutable heap paradigm takes a little more getting used to, but it really only gets in the way on rare occasions when you're trying to implement a trickier, more CPU-bound algorithm.

Likewise, you might think that the lack of shared-mutable-memory multithreading is a performance drawback, but it's something I've rarely missed in practice. And when it's gone, you've eliminated a whole class of bug hazards.