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:
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).
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 <[email protected]>
From: Don Hopkins <[email protected]>
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 <[email protected]>
From: Don Hopkins <[email protected]>
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.
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.
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 <[email protected]>
To: Mitch Bradley <[email protected]>
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.
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 <[email protected]>
To: Don Hopkins <[email protected]>
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 <[email protected]>
To: Mitch Bradley <[email protected]>
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?)
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 <[email protected]> From: Don Hopkins <[email protected]> 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 <[email protected]> From: Don Hopkins <[email protected]> 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 <[email protected]> To: Don Hopkins <[email protected]> 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:
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. 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 <[email protected]> To: Mitch Bradley <[email protected]> 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.
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 <[email protected]> To: Don Hopkins <[email protected]> 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.
From: Don Hopkins <[email protected]> To: Mitch Bradley <[email protected]> Date: Fri, 30 Jan 87 17:15:25 EST Subject: multitasking and memory allocationI'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