How does Forth manage memory?
David Betz
Posts: 14,516
There seem to be lots of Forth enthusiasts here. I'm wondering if anyone can tell me how Forth manages memory. Since it's an interactive language it's possible to define functions (words) on the fly. What happens if I redefine a word? Is the old definition removed and the memory that it occupied reclaimed or does the new definition just shadow the old definition?
Comments
Forth includes a word called forget that removes all definitions to the word argument passed. So it's possible to pop off a definition and everything that depends upon it. This allows for a crude form of garbage collection to say the least. What I do instead is keep my source on the PC and reinitalize the system if I had too many changes to a word.
A redefinition is normally just a new definition with the same name as an earlier one, the previous word cannot be referenced anymore as the new version has precedence in the dictionary search. This means that the code for the old word is still valid for all those definitions which referenced it at the time they were compiled. The new word normally can have no impact on precompiled code.
There is a mechanism in Tachyon for revectoring the old code to point to the new as Tachyon uses a vector table for all high level defintiions. It is also possible to reclaim that old code space as well as the name space as once again we just move all the code after it back down and readjust the vectors although that mechanism has not yet been implemented.
Typical Forths however use indirect addresses so they would not be happy if the code is not where it's supposed to be.
How does Forth manage memory?
Well, you have a couple of stacks that if over-run, they crash. And then the dictionary space has a word Free to tell you how much free space is available in the dictionary for new additions.
All the dictionary entries are chained and dependent on the previous dictionary entries. So the search of the dictionary space starts with the last entry and goes toward the first. If two definitions have the same name, you will only reach the last one (unless you do something fancy to get to the earlier one).
Old definitions are not removed unless you expressly remove them. But I suppose that if you want a definition to be continually redefined as an important programing feature, there would be a way to get what you want.
~~~~~~~~~~
The main points are that the dictionary is usually used in two fashions.
A. As a learning tool, where the dictionary might be filled with all sorts of experimental nonsense that can be purged back to the original state.
B. As a programing project, where the dictionary additons might all be written to a text file and then loaded enmasse to have the desired use start on a single command.
Those are the usually uses.
But one could have other modes of use where you are reprograming, learning, and using in alternation. I think that if you had a ROV with Forth, this might be the case. The ROV gets stuck in a situation that you haven't forseen, so you run diagnostics, try a few new routines to get it unstuck, and then load a revised program to avoid more of the same. That is all very possible. I find this possiblity delightful and less dreary than using C, Spin, or PASM for the same.
Thanks everyone for your explanations!
Parallax has a long standing interest in robotics and I am a bit facinated by the abilities of device to roam in places that are hard for humans to get to and to be able to perform useful tasks.
What exactly do you expect Forth to do?
Forth's interactivity in such a space constrained environment is certainly a big advantage, and I don’t think I've ever called new in my Propgcc programs either. I tend to use either static or stack allocation, and avoid memory leaks.
Doctor: Well then stop doing that.
Now, if the only computer you had was something of the power of a Z80 or Propeller and your only way to communicate with it was an ASR33 teletype or Morse Key, then yes, Forth is very impressive in that you can put a whole high level language (sort of) system into such a small machine and have a self hosting environment. Brilliant.
But, that is not what we do. We talk to our embedded systems with PCs running terminal emulators. Perhaps even phones and tablets. Those machines have giga bytes of RAM and storage. Compiling Spin or C or whatever little program for an MCU is just a little hiccup in their operation. They do more work rendering the fonts in the terminals. Even if you hook your Prop to a modern VGA screen that screen probably has enough processing power on board to run the Spin compiler.
It does not make sense.
It has not made sense since 8 bit computers and compilers running under CP/M.
Stop poking yourself in the eye with that stick!
At least old-school basic is readable after a few months. May as well program in another write-only language like Brain***k. We have several interpreters like that around here too that just as many people have used.
You actually get quite a bit, paid for with very little penalty.
Oh but it does - there's still something to be said for the immediacy and proximity of interactive programming; certainly on smaller, deeply embedded systems particularly.
David isn't completely off his rocker.
KC_Rob, I do agree. That is the attraction and the frustration of the "try to like it" part. Until such time that I can actually write any even marginally useful program in Forth with out having a nervous break down there is no advantage to that immediacy. I have had an easier time editing op codes in HEX using the monitor programs of 6800 and Z80 microprocessor systems.
Besides, writing in Spin and hitting the compile/download button is as interactive as I ever need a system to be.
A core set of words runs in that, to which everything else is built.
I am curious about what that core looks like for more standard expressions.
The problem with other languages that provide the same or similar functionality is the huge performance hit you take for using them.
David, having done a number of things like this over the years, I would suggest that instead of Forth you consider Tiny BASIC as a starting point. It's not very efficient but it's very, very small. The interpreter probably wouldn't fit in a Cog but the runtime kernal would, and the interpreter could be written in (somewhat extended) Tiny BASIC.
Original TB stores line numbers in binary and the rest of the program in ASCII. There are 26 permanent variables named A-Z, and whatever memory is left over is devoted to a "vector" array addressible from !(0) to !(whatever). Strings are not supported. The math expression evaluator uses recursion to implement true precedence of operators and containing function calls with full expressions as arguments within expressions.
Once you get it running, you have a number of mostly very easy optimization paths.
* Add a tokenizer so you can use a tables instead of parsing keywords at runtime.
* Tokenize numeric constants
* Create a separate line number table and use binary search instead of linear scan to find jump targets
* or better, create jump tokens with space for an address to be pre-compiled in pre-runtime
* Add a string vector growing from the opposite end of space, with fixed length storage
* Add DIM and fixed variable storage eating away at the vector
* Add procedure names (still needing line numbers for the simple editor though)
* Static local variables of the internal form procname_varname if DIM is in a PROC
Most of this is trivially easy once you've understood and ported the original simple Tiny Basic interpreter, and can add up to a surprisingly capable development environment. Here is a version that adds strings very similar to the one I reverse engineered when I was a teenager:
http://www.vintagecomputer.net/cisc367/DrDobbs%20Apr%2076%20Minol%20Listing%20w-corrections.pdf
Or perhaps all of that?
Because...I have always assumed, perhaps wrongly, that the reason Forth manages to pack all that performance, in all the above ways, into such a small space is precisely because of it's stack based RPN syntax.
That is to say there is no other language that can do that, unless it looks and behaves much as Forth does.
It will be interesting to see what you come up with.