Document fait avec Nvu Document made with Nvu

Technical pages
Vocabulary and memory

Program memory
Starting up process
Instructions description
Vocabulary and chained list
Instruction searching


The object of this page is to describe principles for the management of the set of FORTH instructions ( vocabulary) in my system by justifying them. This description is cut in several paragraphs:

Attention, although my system is completely based on the FORTH, it is indispensable indeed to study the contents of this page to be able to benefit from optimal performances of the processor.

Program memory

If one disregards various mass memories (hard disk, ...) one can consider that a computer board possesses 3 types of memories being able to contain at the same moment programs and data:

  • the ROM or very slow permanent employee allowing the system starting up at the power on,
  • the very fast static RAM but of weak capacity,
  • the dynamic RAM of strong capacity but relatively slow.

All the craftiness consists in optimizing the program and data location in these various memories in functions of wished performances.

Starting up process

The ROM contains the minimum of program allowing to star system:

  • various logical codes necessary for the processor initialization (" RESET's " vector, stacks addresses, ...),
  • program and code for the downloading of the indispensable FPGAS for the RAM access and to the files systems containing the set of the other programs.

The starting up process is so contained in the ROM which has for inconvenience to be very slow what involves the load of the FORTH kernel in the RAM. As soon as this load is realized, the processor does not use any more the ROM to benefit from the maximum of speed of execution.

By definition, the FORTH kernel contains the set of instructions the most used in any program. It is for it that it is loaded in the static RAM which contains also the real-time kernel, variable system as well as the data and return stacks.

Given that the static RAM is of weak capacity (there is it all the same 512 KiloBytes!) any new instruction is compiled by default in the dynamic RAM. A directive " ZONE_RAPIDE " allows the programmer to add instructions in the static RAM to optimize its code (graphic or arithmetical primitives for example). This primitive must be situated just before the definition of the instruction to be optimized hurriedly. From the end of the instruction definition, the compiler goes back in dynamic RAM.

Instructions description

Each of instructions compiled in the memory is consisted according to the following table:

 Nb. of bytes
 These 4 bytes contain gap in number of bytes enter its header address which follows and that of of the previous instruction header address. This number is always even. It is 0 when it is about the first instruction.

 This byte informs the compiler about the instruction characteristics:

  • bit 7: put in 1 if instruction is immediate (that is executed in compilation mode),
  • bit 6: put in 1 if instruction is direct (that is tha its contents are directly compiled in the instruction which uses it in compilation mode),
  • bits 5 - 0: they contain the number of characters of the instruction name (1 in 63).

One can use this address to show the character string of the instruction name by using the sequence " COUNT 63 AND TYPE".

 1 - 63
 It is the character string giving the instruction name in ASCII code.
 0 or 1
This byte is added with the value 0 if its address is odd. The processor can indeed execute of the code only if this one is stored in even addresses.
 It is the code of the instruction wrote in the processor language. It is always ended by the code of return from subroutine.

The first 4 bytes correspond to the value "HERE" more 4 less that of variable " START " at the time of the compilation of the previous instruction. When a new instruction is create by the word ":", the contents of variable " START " are subtracted from the value "HERE" then incremented with 4 and compiled ("HERE" is then incremented with 4). The contents of variable " START " are then replaced by the value "HERE". The character string followed by the code are then compiled.

Instruction "IMMEDIATE" positions the bit 7 of the first byte in "1" if instruction must be executed in compilation mode.

Instruction "DIRECT" positions the bit 6 of the first byte in "1" if instruction must be directly compiled and not called by an instruction of jump to subroutine. This is indispensable completely to benefit from performances of the processor for basic instructions (" DUP ", " DROP ", "+", ...). In the case of a processor not FORTH as the MC68030, the use of one of these instructions amounts to write a program in assembler language.

If the bits 7 and 6 of this byte are all in "1", it is then about an instruction which will be executed in interpretation AND compilation mode.

The character string containing the instruction name is the type of that manipulable directly by any FORTH kernel. The minimal length is of 1 (instructions " + " , " - " , " / " , " * " , ...) and is pu an upper limit at 63 (length which is relatively impractical to use). It is evident that it can not there have of character "space".

A byte is added if address following the character string is odd to allow to start code at an even address as requires i the processor (padding byte).

Follows finally appropriate code for the instruction which is directly interpretable by the processor.

Vocabulary and chained list

To understand the location of various instructions in the memory, here is a table presenting a really very poor FORTH because it possesses only 5 instructions but, I hope, very clearly to show the vocabulary organization:

Static RAM ( fast execution time)
 Instruction 1
 Byte containing characteristics 1
 Character string containing the name 1
 Code 1
 Instruction 2 pointer -Instruction 1 pointer
 Instruction 2
 Byte containing characteristics 2
 Character string containing the name 2
 Code 2
 Instruction 4 pointer - Instruction 3 pointer
 Instruction 4
 Byte containing characteristics 4
 Character string containing the name 4
 Code 4
Dynamic RAM ( relatively slow execution time)
 Instruction 3 pointer - Instruction 2 pointer
 Instruction 3
 Byte containing characteristics 3
 Character string containing the name 3
 Code 3
 Instruction 5 pointer - Instruction 4 pointer
 Instruction 5
 Byte containing characteristics 5
 Character string containing the name 5
 Code 5

One well finds an instructions chained list establishing the vocabulary of the language FORTH. To find an instruction, the most simple way is to leave of the last created instruction (variable " START " pointing its address) and to go back up until the name corresponds or then till the beginning the memory if it does not exist (a gap equal to 0 indicates tha one arrived at the beginning of the vocabulary).

This method, very simple to implement, possesses the inconvenience of future more and more slow according to the increase of the instructions number. And so the original FORTH was introduced with the notion of multiple vocabularies. This allows to optimize the time of search with the inconvenience not to arrange the se of instructions at any time. But I abandoned this idea for the benefit of another method explained in the following paragraph.

Instructions searching

To optimize the compilation time, I chose the method of binary search of the instructions which is similar to the method used to look for a word in a dictionary or an encyclopedia.

The big advantage of a dictionary is that all the words are alphabetized what allows whoever knowing the alphabet to find a word by eliminating half of the pages in every comparison with regard to examined words. To simplify, if one possesses a dictionary of 1000 pages, know that you will have to examine only a maximum number of 10 pages to find the word which interests you (logarithm in base 2 of the 1000 for math student).

To apply this very effective method to the FORTH vocabulary, it is enough to have an in order alphabetical representation of instructions what makes very simply with a table containing the list of all the instructions pointers, classified in the alphabetical order of the instructions names.

To clear up this speech, nothing is worth a small demonstration:

Let us suppose a FORTH vocabulary constituted by only 10 instructions named each with the first 10 letters of the alphabe and in the order (rather disorder) following: " H ", " B ", "I", " A ", " D ", " F ", " C ", " E ", " G " and " J " (first defined instruction is " H " and the last one is " J "). If I want to execute instruction " A ", the interpreter has to leave of " J " and make 7 comparisons before finding deliberate instruction.

By making a simple calculation, one can estimate the average number of comparisons in: 10 (search of "Hr") +9 (search of " B ") +...+1 (search of " J ") the whole divided by 10 (number of instructions) what corresponds in 5,5.

Now, let us realize a table containing the addresses of each of these instructions classified in the alphabetical order:

 Number of instruction : 10
 Address of the instruction " A "
 Address of the instruction " B "
  Address of the instruction " C "
 Address of the instruction " D "
 Address of the instruction " E "
 Address of the instruction " F "
 Address of the instruction " G "
 Address of the instruction " H "
 Address of the instruction " I "
 Address of the instruction " J "

To find instruction " A ", my searching algorithm is going to begin by seizing the number of instructions is 10. It is going then to point at half of the table and to be so on the address of the instruction " F ". The comparison of the 2 character string is going to give a lower result in " F ". It is going then to point at lower half of the table is on the address of the instruction " C ". The even lower being result of the comparison, the algorithm points then known " B " then finally on " A ". This gives a total number of 4 comparisons to compare with 7 for the previous algorithm.

Let us make now the estimation of the average number of comparisons: 4 (search of "A") +3 (search of " B ") +2 (search of " C ") +4 (search of " D ") +3 (search of " E ") +1 (search of " F ") +4 (search for "G" ) 3 (search for "H" ) 2 (search for "I") 3 (" search of " J ") the whole divided by 10 what corresponds in 2,9 ( to compare in 5,5 of the previous algorithm).

The notion of multiple vocabularies becomes so obsolete. The doubling of the instruction number introduces only a supplementary comparison!