Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!bcm!dimacs.rutgers.edu!rutgers!rochester!pt.cs.cmu.edu!a.gp.cs.cmu.edu!koopman
From: koopman@a.gp.cs.cmu.edu (Philip Koopman)
Newsgroups: comp.lang.forth
Subject: Re: Strippers   (posted for Igor Agamirzian)
Message-ID: <11973@pt.cs.cmu.edu>
Date: 16 Feb 91 03:16:32 GMT
Organization: Carnegie-Mellon University, CS/RI
Lines: 99

>     Method 1.
>
>     The stripper works in conjunction with the
>     metacompiler.  ...
>
     That's a nice method, and it's used in the AstroFORTH automatic target
compiler. The  resulting code  consists only of those words, which are used
(directly or  not) by  the main  (root) word of the program being compiled.
There are two remarks:

     1. It is impossible (or, maybe, too complex to be useful) to handle an
unrestricted CREATE  ... DOES>  construction (though it is a common problem
of metacompilation).  The data  structure, created  by a defining word, may
include pointers  to some  words, and  nobody knows  about it, except DOES>
part. OK,  too egg-headed metacompiler probably can understand something in
DOES>, but what about ;CODE ?

     2.  The   algorithm  with  the  reference  counting  you  describe  is
incomplete. Imagine:

     : A ... ; : B ... A ... ; : C ... ;

where C  is the  word to  be compiled.  Reference count  A will be nonzero,
though it  will be  zero for B. So the code for C is to include code for A,
which is not used (and can be much more larger than code for C).
     The correct algorithm will be something like that:

     BEGIN
         LOOK-THROUGH-THE-SOURCE-AND-SET-REFERENCE-COUNTS
         ARE-THERE-WORDS-WITH-ZERO-REFERENCE-COUNT? WHILE
         REMOVE-ALL-WORDS-WITH-ZERO-REFERENCE-COUNT
     REPEAT

     That's correct,  but  I  don't  like  it.  My  metacompiler  uses  the
recursive scheme of marking of the used words. The procedure is:

     : MARK ( word --- )
         IS-THIS-WORD-MARKED? NOT
         IF MARK-THIS-WORD
            MARK-DOES-PART-OF-DEFINING-WORD
            BEGIN
                ARE-THERE-MORE-REFERENCES? WHILE
                TAKE-NEXT-REFERENCE MARK
            REPEAT
         THEN DROP ;

     TAKE-REFERENCE-TO-ROOT MARK

     It is easily seen, that the details of this algorithm depends on class
of the  word to  be processed  (or on the method of its definition: by ":",
"VARIABLE", "CODE",  etc.) So  it looks  very  natural  to  have  the  MARK
operation for  each defining  word -  and to  EXECUTE it from the main MARK
procedure  indirectly  during  compilation  (like  DOES  operation  of  the
defining word  is executed  indirectly during  run of the program). So each
defining word  becomes an object with the standard set of operation (we use
some other  operations, such  as MERGE,  PRINT, etc.)  and all  the set  of
defining words - a metaclass in the terms of object-oriented programming.

     Mitch Bradley writes in his reply:

>
>>    Method 2.
>>
>>    The stripper compresses a running forth system.
>
>That's how mine works.
>
>>    and fixes up all references to this words.  Obviously, this
>>    part of the task is more difficult if you opt for subroutine
>>    threading and inline code.
>
>Not really.  Any threading technique other than token threading is about
>equally difficult to relocate the references. It helps a lot to have a
>relocation bitmap identifying which memory locations contain pointers.
>
     I'm sure  that it  really helps.  But... Hi,  Mitch: I  have  a  small
question for  you. Who  will build this bitmap for the word, defined by the
user defined definition word? I can imagine a built-in scheme for the colon
definitions compilation.  The only way I see to create a correct relocation
bitmap in  any case  is a  tagged stack  with @ and ! (and all other memory
access operations)  reading and  updating the bitmap, and stack operations,
computing a  type of  result  (for  example,  address+integer=address,  and
integer+integer=integer. But  what will be address+address?). I'm sure that
it isn't what we want.

     My opinion  is that  here is  the same  problem -  the problem  of the
"compile-time interpretation"  of the  definition words.  And the only real
way of  the solving  of this problem is development of the CREATE ... DOES>
construction to  the real  class definition.  I think  that solving of this
problem has  a great  meaning,  because  the  metacompilers  are  the  most
nonstandard (and  nonportable) components  of all  FORTH-based  development
systems. Isn't it a time to discuss metacompilation in the future ANS-FORTH
standard?

-- 
-- Igor Agamirzian

Office: +7(812)350-2523    Home: +7(812)314-6055    Fax: +7(812)217-5105
Address: 37 Rackova Str. # 4, Leningrad 191011 U.S.S.R.