home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / prolog / 1581 < prev    next >
Encoding:
Text File  |  1992-08-22  |  3.6 KB  |  166 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!mcsun!sunic!sics.se!sics.se!boortz
  3. From: boortz@sics.se (Kent Boortz)
  4. Subject: Re: Threaded code
  5. In-Reply-To: serge@irisa.fr's message of 21 Aug 92 09:45:12 GMT
  6. Message-ID: <1992Aug23.035238.29633@sics.se>
  7. Sender: news@sics.se
  8. Organization: Swedish Institute of Computer Science, Kista
  9. References: <1992Aug21.094512.20782@irisa.fr>
  10. Date: Sun, 23 Aug 1992 03:52:38 GMT
  11. Lines: 153
  12.  
  13.  
  14. In article <1992Aug21.094512.20782@irisa.fr> serge@irisa.fr (Serge Le Huitouze) writes:
  15.  
  16.    I would like to know what a "threaded code" implementation of Prolog is.
  17.  
  18.  
  19. It is probably about how to write efficient emulators. The Prolog code
  20. in many implementations is compiled to "byte code". This is a sequence
  21. of data that is read at runtime by an emulator that performs the actions,
  22. i.e. executes the byte code. In an emulator written in C, like in SICStus, 
  23. the byte codes are decoded in a switch statement like:
  24.  
  25.     emulate:
  26.       switch (*(pc++))
  27.         {
  28.         case GET_STRUCTURE:
  29.           /* code to do a get_structure */
  30.           goto emulate;
  31.           .
  32.           .
  33.         case PROCEED:
  34.           /* code to do a proceed */
  35.           goto emulate;
  36.         }
  37.     }
  38.     
  39. In pseudo assembler it could be compiled to:
  40.     
  41.     r1 = jmparray;
  42.     *(r1 + 0) = get_structure;
  43.      .
  44.      .
  45.     *(r1 + n) = proceed;
  46.     
  47.     emulate:
  48.     {
  49.       r0 = *pc;
  50.       if (r0 < GET_STRUCTURE) goto exit;
  51.       if (r0 > PROCEED) goto exit;
  52.       r0 <<= 2;
  53.       r2 = *(r1 + r0);
  54.       jmp(r2);
  55.     }
  56.     
  57.     get_structure:
  58.       /* code to do a get_structure */
  59.       goto emulate;
  60.     
  61.     proceed:
  62.       /* code to do a proceed */
  63.       goto emulate;
  64.     
  65.     exit:
  66.  
  67. If the C compiler supports threaded code you can take the addresses of the
  68. labels and store them in an array. Inderect threaded code:
  69.  
  70.     jmparray[GET_STRUCTURE] = get_structure;
  71.      .
  72.      .
  73.     jmparray[PROCEED] = proceed;
  74.     
  75.     
  76.     emulate:
  77.       goto jmparray[*pc];
  78.     get_structure:
  79.       /* code to do a get_structure */
  80.       goto jmparray[*pc];
  81.  
  82.     proceed:
  83.       /* code to do a proceed */
  84.       goto jmparray[*pc];
  85.  
  86.  
  87. Note that the emulation code is placed in bottom of the code for each byte
  88. instruction. This way the entry "emulate" is use only once and the jump to 
  89. it is removed. In pseudocode:
  90.  
  91.     r1 = jmparray;
  92.     *(r1 + 0) = &get_structure;
  93.      .
  94.      .
  95.     *(r1 + n) = &proceed;
  96.     
  97.     emulate:
  98.     {
  99.       r0 = *pc;
  100.       r0 <<= 2;
  101.       r2 = *(r1 + r0);
  102.       jmp(r2);
  103.     }
  104.     
  105.     get_structure:
  106.       /* code to do a get_structure */
  107.     {
  108.       r0 = *pc;
  109.       r0 <<= 2;
  110.       r2 = *(r1 + r0);
  111.       jmp(r2);
  112.     }
  113.     
  114.     proceed:
  115.       /* code to do a proceed */
  116.     {
  117.       r0 = *pc;
  118.       r0 <<= 2;
  119.       r2 = *(r1 + r0);
  120.       jmp(r2);
  121.     }
  122.  
  123.  
  124. Finally the predefined bytecodes could be replaced by the address to
  125. the labels at load time. This is "direct threaded code", in pseudocode:
  126.  
  127.     emulate:
  128.     {
  129.       r0 = *pc;
  130.       jmp(r0);
  131.     }
  132.     
  133.     get_structure:
  134.       /* code to do a get_structure */
  135.     {
  136.       r0 = *pc;
  137.       jmp(r0);
  138.     }
  139.     
  140.     proceed:
  141.       /* code to do a proceed */
  142.     {
  143.       r0 = *pc;
  144.       jmp(r0);
  145.     }
  146.  
  147. A cleaver C compiler could compile the switch code and indirect threaded
  148. code to equal code. The main problem is the range check of the argument
  149. to the switch. I think that if you use an enumerated type as
  150. the value to switch on, and all the values are covered in the cases
  151. the test should be removed. I don't think any C compiler do this. Note that
  152. each test is really at least two instructions, a compare and a jmp instruction.
  153.  
  154. The direct threaded code uses less code but instead each bytecode/jmpaddress 
  155. require a 32 bit field in the program area. The fetch could be slower and more
  156. memory consumed by the prolog programs could lead to more frequent paging.
  157.  
  158. The only C compiler I know of that support threaded code is GCC 2.X.
  159. Someone told me that in the old days they all did so it is just coming
  160. back ;-)
  161.  
  162.  
  163. --
  164. Kent Boortz
  165. boortz@sics.se
  166.