sdh@thumper.bellcore.com (Retief of the CDT) (09/13/89)
I need some help pronto. I'm writing a forth compiler for a 68000 machine, and am trying to implement it in a way that doesn't require access to the contiguous address space of the machine. In effect, when a word is compiled, it is shoved in a dynamically allocated block in a heap that is relocatable. All function calls would be rerouted through a dispatcher that would located the handle of the code block, lock it down and execute it. Upon return, it would unlock the block and return to the calling word. This poses a minor problem with variables, since a variable would push an address (in its own block) and return. The address will be incorrect if the variable's block is moved. This is easliy circumvented by putting all variables in a relocatable block acess from a register. This means that the address pushed on the stack for a variable is the displacement from the start of the variable block. I would like to include a word that given another word would assemble that word and words it calls into one small executable block, that no longer requires the dispatcher. Effectively, the interpretter is an incremental compiler, and can produce upon request a turnkey application that will only carry around the baggage of the functions it uses. The problem that this poses is that the language MUST have keywords. When a word is initially compiled, there is no way to grab a hold of WHERE the word is being compiled. This makes compile-time executable words an impossibility. I am writing this as an independent project at school. My advisor is not a FORTH guru, and thought it quite reasonable to allow the net to decide what action to take. The question comes down to: Should I implement my concept of a FORTH machine which takes away compile time executable objects (making the compiler not extensible), but making the the language "safe" in a machine where poking indiscriminantly into the address space could cause a segmentation fault. In addition, the word "forget" is safe in that it can be made to destroy only the word in question. It can produce turnkey apllications with minimal code over head. OR Should I simply implement FORTH as it stands, allowing the compiler extensions at the cost of dangerous memory practices. I realize that if I do the first it is no longer forth, but a warped hybrid. Please advise me on which approach I should take. If you need more info, ask me and I'll post anything I've left out. Steve Hawley sdh@flash.bellcore.com hawley@occs.oberlin.edu hawley@cwru.edu
bouma@cs.purdue.EDU (William J. Bouma) (09/15/89)
In article <1715@thumper.bellcore.com> sdh@thumper.bellcore.com (Retief of the CDT) writes: > I need some help pronto. I'm writing a forth compiler for a 68000 >machine, and am trying to implement it in a way that doesn't require >access to the contiguous address space of the machine. In effect, when a >word is compiled, it is shoved in a dynamically allocated block in a heap that >is relocatable. All function calls would be rerouted through a dispatcher >that would located the handle of the code block, lock it down >and execute it. Upon return, it would unlock the block and return to the >calling word. Why? You mention two features that this scheme would facilitate. One is forgetting just a word rather than a word and what follows in memory. The other is producing an application without unused code. But you can get both of these advantages in a normal forth without dynamic code movement. All you need is a compaction routine similar to a garbage collector in lisp. To produce a minimal application you just forget all the words that aren't used. Then run the compaction to move the words and data blocks around to eliminate the gaps of unused memory. >I realize that if I do the first it is no longer forth, but a warped hybrid. Well, any step away from the forth83 standard is a step in the right direction! >Please advise me on which approach I should take. If you need more info, >ask me and I'll post anything I've left out. Just, are there any other advantages of your dynamic code movement? Forth with compaction seems like it would be simpler to write and less error prone than the scheme you have presented. -- Bill <bouma@cs.purdue.edu> || ...!purdue!bouma
sdh@wind.bellcore.com (Stephen D Hawley) (09/15/89)
In article <7972@medusa.cs.purdue.edu> bouma@cs.purdue.EDU (William J. Bouma) writes: > Why? You mention two features that this scheme would facilitate. > One is forgetting just a word rather than a word and what follows > in memory. The other is producing an application without unused > code. But you can get both of these advantages in a normal forth > without dynamic code movement. All you need is a compaction routine > similar to a garbage collector in lisp. To produce a minimal > application you just forget all the words that aren't used. Then > run the compaction to move the words and data blocks around to > eliminate the gaps of unused memory. > Just, are there any other advantages of your dynamic code movement? > Forth with compaction seems like it would be simpler to write and > less error prone than the scheme you have presented. You can't "just foget all the words that aren't used". Forget will eliminate everything defined after as well. What if you want to forget something in the middle? You're screwed. Compaction is also unsafe - you have to adjust the addresses of all the everything you move. You have to write a garbage collector. These are notoriously slow techniques. If you generate code that is threaded through JSR's and may include inline code, this gets harder. Less error prone? I think not. Ask anyone who has implemented LISP (like me, for example), just how free of errors garbage collection routines are. Forth is dangerous in a machine that does not have memory protection (such as the macintosh). FORTH words like , or HERE are villanous. FORTH is modular enough without letting you change the way the compiler works. My scheme would use a heap allocation system for the code blocks that is completely robust and safe. If you can't assume that addressing the entire memory space is a safe practice, then the current paradigm of operation for FORTH is unsafe. Zipping through memory, enlarging code space is not safe. What if the segment gets swapped out and swapped in somewhere else? This only works if you have virtual memory, which I assure you, the Mac does not have. How can I make the compiler comletely solid? Effectively, I would like to eliminate any possibility of compile-time segmentation faults. This, I feel is a bigger win than "smaller is better". The advantage of dynamic code movement is that in a system with memory allocated from a heap in 2 ways (relocatable and non-relocatable), you take advantage of the system's own memory management by using relocatable blocks, so that the heap doesn't get fragmented. You can allocate one big block for code space, but how big is big? If you guess too big, you're being a hog. You may not be able to run some things. If you underestimate, you'll be thrashing with calls to realloc() to get more space. The advantage is that you only ever use as much space you need. Thanks for the input. I guess I wasn't very clear about the target system. The reason is has to be safe in memory is the potential of trashing desk accessories or (if running under the multifinder), other applications. Steve Hawley sdh@flash.bellcore.com hawley@occs.oberlin.edu hawley@cwru.edu "Up is where you hang your hat." --Jim Blandy, computer scientist
dlyons@Apple.COM (David Lyons) (09/15/89)
In article <7972@medusa.cs.purdue.edu> bouma@cs.purdue.EDU (William J. Bouma) writes: > [...] are there any other advantages of your dynamic code movement? > less error prone than the scheme you have presented. This may not be directly related to the original posting, but in environments such as the Macintosh and Apple IIgs, there is a Memory Manager that you have to request memory from--there's no guarantee that you can get the *same* memory from one execution of your program to the next, so a traditional Forth architecture (with lots of pointers) is a problem. Even if the processor provides some kind of "base register" & you use offsets rather than absolute pointers, there are still problems. For example, how do you "grow" the block of memory allocated for your dictionary? You have to allocate all the space you want in the beginning, *or* you have to be prepared to *not* be able to grow your block, even if the amount of memory you want is available (probably split up into several pieces). The closest the 65816 comes to providing a base register is to limit the main Forth memory area to 64K and allocate a memory block of up to 64K, starting at a 64K boundary--at least one commercial GS Forth, called GS16Forth, uses this approach. It works, and it has the advantage (?) that things are still 16 bits long. (I'd rather have 24- or 32-bit pointers/offsets, but not necessarily 24- or 32-bit integers, by default. I suspect this would break a lot of existing Forth code.) Has anybody seen Forth systems using this sort of approach? -- --Dave Lyons, Apple Computer, Inc. | DAL Systems AppleLink--Apple Edition: DAVE.LYONS | P.O. Box 875 AppleLink--Personal Edition: Dave Lyons | Cupertino, CA 95015-0875 GEnie: D.LYONS2 or DAVE.LYONS CompuServe: 72177,3233 Internet/BITNET: dlyons@apple.com UUCP: ...!ames!apple!dlyons My opinions are my own, not Apple's.
dlyons@Apple.COM (David Lyons) (09/15/89)
In article <17623@bellcore.bellcore.com> sdh@wind.UUCP (Stephen D Hawley) writes: >In article <7972@medusa.cs.purdue.edu> bouma@cs.purdue.EDU (William J. Bouma) writes: >[...] You have to write a garbage collector. Not necessarily--the host system may already have one as part of its memory management routines. (For forgetting a single word, this would mean having each word in its own memory block, & possibly using something more complicated than pointers for most operations. Handles, for example.) >[...] >Forth is dangerous in a machine that does not have memory protection [...] Gee...*anything* is dangerous in a machine that doesn't have memory protection. I spend a large amount of time tracking down "Who stomped on *that* byte?" problems (mostly on the Apple IIgs--in my programs and other people's), and the source is usually assembly, Pascal, or C. -- --Dave Lyons, Apple Computer, Inc. | DAL Systems AppleLink--Apple Edition: DAVE.LYONS | P.O. Box 875 AppleLink--Personal Edition: Dave Lyons | Cupertino, CA 95015-0875 GEnie: D.LYONS2 or DAVE.LYONS CompuServe: 72177,3233 Internet/BITNET: dlyons@apple.com UUCP: ...!ames!apple!dlyons My opinions are my own, not Apple's.
bouma@cs.purdue.EDU (William J. Bouma) (09/16/89)
In article <17623@bellcore.bellcore.com> sdh@wind.UUCP (Stephen D Hawley) writes: >In article <7972@medusa.cs.purdue.edu> bouma@cs.purdue.EDU (William J. Bouma) writes: >> Why? You mention two features that this scheme would facilitate. >> One is forgetting just a word rather than a word and what follows >> in memory. The other is producing an application without unused >> code. But you can get both of these advantages in a normal forth >> without dynamic code movement. All you need is a compaction routine >> similar to a garbage collector in lisp. > >You can't "just foget all the words that aren't used". Forget will eliminate >everything defined after as well. What if you want to forget something in the >middle? You're screwed. And what is stopping me? It is trivial to write 'forget' so that it just eliminates one word from the dictionary, and frees just its memory! Sure this leaves chunks of unused memory interspersed with valid forth junk, but that is where compaction comes in. > Compaction is also unsafe - you have to adjust >the addresses of all the everything you move. You have to write a garbage >collector. These are notoriously slow techniques. If you generate code that >is threaded through JSR's and may include inline code, this gets harder. Less >error prone? I think not. Ask anyone who has implemented LISP (like me, for >example), just how free of errors garbage collection routines are. Don't tell me that just because you personally could not write an error free garbage collector that they don't work! Yes, they can be slow, but GC only happens when memory has apparently run out. This should not happen very often. It seems you want to adjust addresses on the fly, fine. All I am saying is that you can wait until you need to, then adjust the addresses. >Zipping through memory, enlarging code space is not safe. What if the segment >gets swapped out and swapped in somewhere else? This only works if you have >virtual memory, which I assure you, the Mac does not have. How can the mac swap memory around without maintaing virtual addresses? Could you explain more clearly exactly what it is the mac does about memory management? >Effectively, I would like to eliminate any possibility of compile-time >segmentation faults. This, I feel is a bigger win than "smaller is better". Perhaps I will understand what you mean here after you clarify how the mac handles segments? >Thanks for the input. I guess I wasn't very clear about the target system. You still aren't clear, at least to me. -- Bill <bouma@cs.purdue.edu> || ...!purdue!bouma
A-PIRARD@BLIULG11.BITNET (Andr'e PIRARD) (09/18/89)
>>You can't "just foget all the words that aren't used". Forget will eliminate >>everything defined after as well. What if you want to forget something in the >>middle? You're screwed. Wouldn't you think of forgetting your assembler after using it? The way we do it in Comforth is as follows: TEMPORARY CODE DUMMY END-CODE \ Load assembler overlay in temporary storage PERMANENT ... DISPOSE TEMPORARY: defines the base of an alternate area up high in dictionary space, if not already defined. Starts compiling there (makes it active). PERMANENT: returns compiling to regular dictionary. DISPOSE: FORGET all words from the alternate area (linked "in the middle"). Undefine the alternate dictionary area. Any "compilation utility" or such can be between PERMANENT and DISPOSE. All that's provided one knows what one is doing, of course. Andr .
ejm@midian.UUCP (E.J. McKernan) (09/21/89)
In article <7990@medusa.cs.purdue.edu>, bouma@cs.purdue.EDU (William J. Bouma) writes: > In article <17623@bellcore.bellcore.com> sdh@wind.UUCP (Stephen D Hawley) writes: > >> Why? You mention two features that this scheme would facilitate. > >> One is forgetting just a word rather than a word and what follows > >> in memory. The other is producing an application without unused > >> code. But you can get both of these advantages in a normal forth > >> without dynamic code movement. All you need is a compaction routine > >> similar to a garbage collector in lisp. > > > >You can't "just foget all the words that aren't used". Forget will eliminate > >everything defined after as well. What if you want to forget something in the > >middle? You're screwed. > > And what is stopping me? It is trivial to write 'forget' so that it > just eliminates one word from the dictionary, and frees just its > memory! Sure this leaves chunks of unused memory interspersed with > valid forth junk, but that is where compaction comes in. > But you've overlooked a small (large? ;-)) problem. If you forget a word that other words have used in their compilation then you must also forget them. Suppose that you've defined FOO. Then you've defined BAR using FOO. You then forget FOO. Later after one of the garbage collection episodes, the code space that was used for FOO may have been used for something else. When you now execute BAR it just might not do what you intended. ----------------------------------------------- E.J. McKernan - Midian Electronics - Tucson, AZ uucp: ...!uunet!arizona!midian!ejm internet: midian!ejm@arizona.edu snail: Midian Electronics 2302 E. 22nd St Tucson, AZ 85713 voice: 602-884-7981
wmb@SUN.COM (Mitch Bradley) (09/22/89)
One issue that has not been explicitly raised in all this discussion about
garbage collection is the problem of determining which locations have
to be relocated and which don't.
The general problem arises in a surprising number of contexts, and
none of the Forth standards have dealt with it. Use of position-independent
encoding does not even solve the problem; you still have to know exactly
which data structures to store in the position-indepdent format.
The problem occurs in any one of the following scenarios:
a) An entire Forth dictionary image is saved and then re-used at a
different address (as in a multi-process OS on a machine with no MMU)
b) Multiple precompiled "overlays" or "modules" are saved, and then
re-loaded, more than one at a time.
c) A "garbage-collecting" or "hole-eliminating" FORGET scheme is used.
d) A "turnkey compiler", which is capable of eliminating unused code
from the application, is used.
e) Supply your own examples.
Here are some Forth operator usages which are particularly troublesome:
1) The use of "," to compile an address into a colon definition or word list.
2) The use of "!" to store an address into a variable.
3) The use of "," or "!" to store a link, as in a linked list of
dictionary words, or a voc-link chain.
4) The use of "!" to remember the address of a word in an execution variable.
5) The use of "!" to remember the address of a variable or other data
structure.
The basic problem is that Forth "sweeps under the rug" the distinction
between numbers and addresses. Not only do addresses have relocation
implications, they also have different arithmetic properties (they are
unsigned), granularity of memory access, and alignment restrictions.
In the case of the PC, addresses are so bizarre that only IBM could
have created a standard around a particular chip which will remain unnamed.
As a start toward addressing the relocation issue, I use a set of 3
"address-class" data types, which I call "tokens", "links", and "addresses".
token: The execution address of a Forth word. Returned by "'", can
be used by "EXECUTE".
link: Represents the successor of a node in a linked list.
address: Represents the address of an arbitrary data structure.
Each such type requires a minimum of 3 operators: xxx@ , xxx! , and /xxx
(store, fetch, and sizeof).
I use the convention that, when one of these address items appears on
the data stack, it is an absolute address. Only when the item is transferred
to and from memory does encoding (such as conversion to an offset or a token
number, or the setting of a bit in a relocation bitmap) take place.
The "absolute address when it's on the stack" convention is not strictly
necessary, but it is convenient.
In many implementations, tokens, links, and addresses are encoded in the
same way. However, in some implementation schemes, the distinction is
necessary. For instance, in a true token-threaded scheme, the token
table may represent only executable words, while the addresses of
other data structures may be encoded differently. In a memory-limited
system, it may be worthwhile to encode links using small variable-length
relative offsets.
Observation about links: If links are relocated, what do you use as the
list terminator value? 0 is not a good choice, because it can relocate
to a non-zero value. I like to use the beginning address of the Forth
dictionary as the sentinel value; I call that address "origin". It
relocates properly. All tests for "end of list" must then resolve to
"origin =" rather than "0=".
When I converted my system to be relocatable, it was quite a chore.
Now that it has been done, I frequently run across beneficial side effects,
such as the ability to run on machines with oddball memory maps,
the ability to change kernel implementation techniques (to tune
for different environments) without affecting user code, and increased
ease of porting to different CPU architectures.
Mitchtoma@tekgvs.LABS.TEK.COM (Tom Almy) (09/22/89)
Arrgh! I've read enough. It's not *that* difficult to implement a Forth with dynamic memory management. I've played around with it. You just have to use "token threading". The "compilation addresses" that are compiled into a colon definition are actually indices into a table of real compilation addresses. When the body of a colon definition gets moved, all that is necessary is to revise the address in the table. The only other important issues: 1) code words must use position independent code so they can be relocated or else the garbage collector must know they are immovable. 2) colon definitions must also be relocatable (the branch functions must use relative addressing). While the dictionary organization allows shadowing of definitions (a luxury not available in other languages, typically), I wrote a REDEFINE word that would replace the earlier definition with a new one. This allows fixing definitions without having to recompile any of the following words in the dictionary (a big plus). While I never concerned myself with a selective FORGET, it wouldn't be that difficult to safely implement. I propose two schemes: 1) (Name field, the header, is atached somehow to the definition body) -- Replace pointer in token table with pointer to word called *DELETED* defined: : *DELETED* ABORT" Attempt to execute deleted function" ; If FOO uses BAR (: FOO BAR 10 + ; for example) and BAR is forgotten, the if FOO is decompiled, it will look like : FOO *DELETED* 10 + ; and will cause an error if executed. 2) A somewhat friendlier implementation would use second token table pointing to the name field. FORGET would replace the body with one that does the abort, but decompiling would yield the original definition of FOO, and the "error" definition of BAR. A later re-definition of BAR, using REDEFINE, would allow FOO to work again. The garbage collector would mark unused tokens and delete the name fields (and bodies) of any tokens that were not used and had "error" bodies. (Note that just deleting unused tokens would not work because the system would start going away as top level words started going away!). As a heretic remark, anyone that is really interested in a dynamic Forth (with all its attendant bloating and sluggishness) should look at LISP or, better yet Smalltalk. I spent a year on a Smalltalk implementation, and the guts of Smalltalk bear a suprising resemblence to Forth + dynamic memory management. Get a copy of "Smalltalk-80 The Language and Its Implementation", by Adele Goldberg and David Robson, and plow your way through Part Four. Lots of it looks like a direct steal from Forth! Of course the Smalltalk language is a lot different, but it compiles into token threaded code for a stack machine! A hot Forth/Smalltalk programmer could easily add a Forth like compiler to the environment and run Forth programs. Tom Almy toma@tekgvs.labs.tek.com Standard Disclaimers Apply
toma@tekgvs.LABS.TEK.COM (Tom Almy) (09/22/89)
(My second posting on this topic) After reading Mitch Bradley's posting, I realized that I needed an addenda. I never had to concern myself with garbage collection/compaction in the Forth I was working on. But it is true that in such environments you can't leave raw addresses lying around. This means that @ and ! as we know them are forbidden! But, again, taking the hint from Smalltalk, executing a "variable" could leave an address token on the stack which @ and ! could interpret to to their work. There would have to be indexing @ and ! operations since you could not do integer arithmetic on address tokens. In Smalltalk, roughly speaking, "variables" leave the offset into one of several types of data storarage areas, and there are several different types of @ and ! operations, different ones for each type of storage area. My proposal is more Forth-like, but would still require major rewriting of Forth code. Example: : TYPE 0 ?DO COUNT EMIT LOOP DROP ; would need to be written as : TYPE 0 ?DO DUP I CI@ EMIT LOOP DROP ; \ CI@ is a character indexed fetch since COUNT would no longer be acceptable. And think of all the places where the sequence "COUNT TYPE" occurs! That would need to be replaced with: : COUNT-TYPE DUP 0 CI@ 1+ 1 ?DO DUP I CI@ EMIT LOOP DROP ; Tom Almy toma@tekgvs.labs.tek.com Standard Disclaimers Apply