Great question! I vaguely remember reading it in a tan Knuth book, and the subject and algorithm feels very Knuthian to me, but I can't remember exactly. But this book has that title and looks like the book I remember having, and also looks like Knuth's books, so maybe I got confused and that's the book:

https://www.amazon.com/introduction-structures-applications-...

Here's some old email I wrote about it -- it turns out I did go on to write an interactive Forth window manager (for X10, with pie menus, and you could "fling" windows and it would start a Forth task to bounce them around on the screen -- see hacks.f), which foreshadowed my later work with NeWS (or its original name SunDew, as Mitch called it, which he ported to the Atari ST).

https://donhopkins.com/home/archive/piemenu/uwm1/

https://donhopkins.com/home/archive/piemenu/uwm1/uwm.f

https://donhopkins.com/home/archive/piemenu/uwm1/fuwm-main.f

https://donhopkins.com/home/archive/piemenu/uwm1/hacks.f

I made a diagnostic test which memory mapped the black and white framebuffer and ran memory allocator tests in video memory, so I could watch them. But I was using a shitty random number generator, and it looked suspicious.

Mitch sent me a better one based on the Unix random number generator, but it was pretty shitty too: The low bit alternates between 0 and one, so if you use "RND 1 AND" to flip a coin you get 0 1 0 1 0 ... So Mitch warned me that "Try dividing by two to get rid of the bogus lsb."

After I got it to work, I used it as a screen saver, so people would think my Sun 3/160 was broken and would leave it alone.

Memory allocators are easy. Random number are hard!

To: Mitch Bradley <wmb@sun.com>
From: Don Hopkins <don@brillig.umd.edu>
Date: Mon, Jul 28, 1986, 6:16 AM
Subject: Dynamic storage manager

Here's a dynamic storage manager I wrote. It runs under cforth and the
68000 forth.

I'm sending two files: "records.f", and "dbuf.f". The first contains
some words that are used to define records, like in pascal. The second
is my dynamic storage manager.

I wrote an earlier version of this for my Apple ProDOS Forth system,
as well as a set of string functions that used it. I'm going to port
this much revised (and more portable) version back to the Apple, and
update the string handling functions.

You may want to change the records.f file. I commented out some code
in dopasrec that optomized field accessing words with zero offset,
that was not completely portable.

I ran it through 100000 tests, and it worked fine. (I can't wait to
port it to the Apple, and run the tests on the hires screen. Not as
many, though. A Vax 8600 running cforth can do things a 1 MHZ 6502 is
not allowed to think about.) Bet it would look cool run in the Sun
screen memory.

Mike Gallaher and I will be arriving in Fornicalia around the evening
of the 9th. We should be getting a rental car. When are you usualy
around Sun and how do we find you? Mike's staying with Gosling.
I may need a place to stay near Sun for a few days.

I'll bring a tape of interesting things. I've been doing some work
with the X window system, enhancing the "uwm" window manager. Do you
have a X interface for Forth written? If not, I'll write it. I would
love to build an interactive forth window manager.

-Don

From: Mitch Bradley <wmb@sun.com>
From: Don Hopkins <don@brillig.umd.edu>
Date: Mon, Jul 28, 1986, 10:33 AM
Subject: Storage allocator and stuff

Thanks for the code. I'll try it out within the next few days as
time permits.

You can stay with us for 2 or 3 nights if that would help.
My wife and I have a spare bedroom in our house.

Gosling knows where my office is. I'm usually in from 9:30 or 10:00
onwards. My leaving time is rather variable.

I haven't done much with X, because I've been doing some stuff with
Gosling's new PostScript-based window system, SunDew.
You'll see when you get here. X pales in comparison to SunDew.

I'd be happy for you to do any Forth interfaces that interest you.
I haven't been doing much with Forth/Unix stuff lately, because I've
been working on the Atari ST Forth.

Mitch

From: Mitch Bradley <wmb@sun.com>
To: Don Hopkins <don@brillig.umd.edu>
Date: Wed, Jul 30, 1986, 12:44 AM
Subject: re: records.f

Here's how to make the "compile-time noop" stuff for the first field
portable:

: donothing ( -- ) does> drop ;

: dopasrec ( -- ) does> @ create inrecord @ if
walign over ?dup if
, dooffsetr else
donothing immediate then
+ else
allot then ;

Now, here's how I do the same thing: The underlying semantics are
similar, but I believe that my names are more in keeping with accepted
Forth naming conventions.

: struct 0 ;
: field: ( offset size -- offset' )
create over , +
does> @ +
;
: byte: /c field: ;
: word: /w field: ;
: long: /l field: ;
: normal: /n field: ;
: union: 0 field: ;
: unused + ;

: size: constant ;
: ;struct drop ;

\ Example:

struct
byte: >b1
byte: >b2
word: >w1
long: >l1
size: /foo

struct
byte: >c1
7 unused
/foo field: >foo
;struct

Note the use of ">" instead of "." to introduce field names. This is
consistent with the conventional usage of ">" to denote the conversion
of one address to another address (as in >NAME , >BODY , etc.).
"." is a bad choice because it usually indicates printing or display.

A variation on this, which I hope to test one of these days, is to
give the "struct" word a DOES> clause, which is used as the run-time
action of the fields. This would allow you to easily define structures
based at particular addresses, without having to explicitly mention
the base address before each structure member.

Mitch

From: Don Hopkins <don@brillig.umd.edu>
To: Mitch Bradley <wmb@sun.com>
Date: Thu, 31 Jul 86 13:44:55 EDT
Subject: Random number generator

The RND word included in the dbuf.f file is evil and should be flushed.
I ran the test in dbuf.f in stand alone mode in the video
memory of a Sun-3. I noticed that many of the buffers were just sitting
there, never getting picked to be freed. I got pissed at the RND
function and wrote a studly overkill, which gives much more pleasing
results on the screen. I modified the test to fill each allocated block
with a random nonzero byte, and to erase memory before freeing it. You
can really tell what's going on. The Sun-3 is a FAST machine!

I did some tests with random bit-mashing ones I made up off the top of
my head, and with the one in the 68000 forth (the same as the one you
sent me), and was pretty unsuccessful in terms of non-repetitiveness,
so I wrote this studly wastefull overkill version that gives pleasing
effects.

create rnd-state 255 /n + allot

: pretty-fucking-random-as-far-as-I-can-tell-without-lots-of-heavy-theoretical-anaylsis ( --- n )
rnd dup 255 and rnd-state +
dup c@ rnd-state + c@ seed +!
rnd swap +! ;

I wrote an Apple ProDOS Forth system, based on the FIG 6502 Forth. I'd
like to adapt it to be metacompilable. This will make it a lot easier
to port some of the more modern features that your system has. I'm
writing a ProDOS interface for your file system right now in another
emacs window. I want to add devices that know about reading other
operating system formats, and other partitions on the hard disk.

-Don

From: Mitch Bradley <wmb@sun.com>
To: Don Hopkins <don@brillig.umd.edu>
Date: 31 Jul 86 10:34:13 PDT (Thu)
Subject: Re: Random number generator

Try this one and let me know how it works. I copied this one out
of the Unix library. Try dividing by two to get rid of the bogus
lsb.

\ 31-bit random number generator. Uses a linear congruential generator.
\ The result is a positive number in the range 0 <= n < 2^31
\ The lsb of this number is no good. It always toggles.
\ The rest of the bits are pretty good.
decimal
lvariable seed
: random ( -- l )
seed l@
1103515245 * 12345 +
th 7fff.ffff land
ldup seed l!
;

From: Don Hopkins <don@brillig.umd.edu>
To: Mitch Bradley <wmb@sun.com>
Date: Fri, 30 Jan 87 17:15:25 EST
Subject: multitasking and memory allocation

I'm having some problems with the multitasking package with forth.
I've linked in a lot of C code, and that's using the unix malloc,
and forth is using its own simple malloc, for multitasking. I'm afraid
there are some weird interactions between multitasking and the linked
in C code. Do you have some time for a phone call so I can describe what's
going on? I'm wondering if forth should be using the unix malloc, but
the details of the interactions between linking in C code, multitasking,
how, when, and to what symbols are resolved, and the phase of the moon,
have me quite confused as to what to do to make the damn machine Do What
I Mean. I'd like to at lease replace the simple malloc with the nice malloc
I wrote, but I think it would be a real pain to get the C programs to know
about that. It seems it's easier to call C from forth than forth from C.
Have you got any good tricks for doing the latter? Also, when you link in
two programs that use the same unix libraries, do they each have their own
copy? (i.e. two competing mallocs?!) If not, how in the world does it work?
(What sort of monkey wrench do shared libraries throw into the works, and
is a monkey wrench just the tool needed or what?)

-Do