section id="indirect-threaded-code" xreflabel="Nepřímo zřetězený kód"
rcsinfo="$Header: /home/radek/cvs/forth-book/sec-indirect_threaded_code.xml,v 1.7 2005/11/09 23:11:35 radek Exp $"
Prvotní implemetace forthu, používající nepřímo zřetězený kód je historicky nejstarší a původní implementací. Je také jednou z často používaných implemetací. Základní struktura slova ve slovníku vypadá následovně:
+----------+-----+-------+ | hlavička | CFA | PF | +----------+-----+-------+
STATUS: .BYTE NAME: .STRING LINK: .WORD CFA: .WORD PF: .WORDS
Tomuto vzoru odpovídají všechna slova. Základní (nízkoúrovňová) slova ve strojovém kódu mají v poli CFA hodnotu ukazující na pole parametrů PF, které obsahuje přímo strojový k slova.
.---.
/ v
+----------+-----+-------------+
| hlavička | CFA | PF |
+----------+-----+-------------+Vysokoúrovňové slovo, tedy slovo překládané kompilátorem :, obsahuje v CFA ukazatel na strojový kód interpretu vysokoúrovňových slov jenž se obvykle nazývá DOCOLON, DOCOL nebo ENTER. V poli PF je pak řada ukazatelů na těla slov. Tedy na CFA pole slov pomocí nichž je toto slovo definováno.
+----------+-----+---------------------------------+
| Hlavička | CFA | adr1 adr2 adr3 ... adr_exit |
+----------+-----+---------------------------------+
|
v
ENTERTento mechanismus nám umožňuje snadno rozšířit implementaci forthu o nové druhy interpretů. Například můžeme mít interpreter 4 bitových čí 8-mi bitových instrukcí. Tím můžeme uspořit paměti.
Nyní, když víme, jak vypadá struktura slov ve slovníku, můžeme si ukázet definice základních slov/operací. Jedná se o slova/procedury/funkce next, enter a exit. Ukážeme si nyní jak tyto operace implementovat na našem virtuálním procesoru.
Představme si, že máme slovo SQUARE které je definováno takto:
: SQUARE DUP * ;
Na následujícím obrázku je vidět jak jsou jednotlivá slova ve slovníku a kód provázány ukazateli.
Obrázek 7.2. Provázaní slov v ITC modelu
IP
|
v
PF slova FOO ----+--------+--------+--------+--------+----
jenž používá ... | GETNUM | SQUARE | GROK | ...
slovo SQUARE ----+--------+--------+--------+--------+----
/
/
v
Definice +---------------++------+------+------+------+
slova |HEADER: ||CFA: |PF: |
SQUARE | 6 SQUARE link || ENTER| DUP | * | EXIT |
+---------------++------+------+------+------+
/ \
/ \
/ v
Definice slova / +------------++-----+------------------+
DUP ve strojovém / | HEADER: ||CFA: |PF: |
kódu / | 3 DUP link ||PF --> strojový kód DUP |
/ +------------++-----+--+---------------+
/ \__/^
/
v
+--------------------+
| strojový kód slova |
| ENTER |
+--------------------+FIXME:Rutina next provádí přechod od jedné instrukce (adresy) v seznamu PF k následující instrukci (adrese). IP ukazuje na následující instrukci, tedy tu jenž se má vykonat.
V průběhu vykonávání slova FOO, na obrázku úplně nahoře, ukazuje registr IP na instrukci SQUARE. Procedura NEXT začne získáním adresy instrukce SQUARE a uložením této do registru W. Registr W tedy obsahuje adresu CFA pole slova SQUARE. Obsah registru IP je poté zvětšen o velikost buňky aby ukazoval na následující instrukci za instrukcí SQUARE. Následuje vykonání slova SQUARE skokem na adresu uloženou v jeho CFA. Formálně si to zapíšeme takto:
# Vykonání dalšího slova v definici slova FOO.
# Tedy vykonej slova SQUARE ne které ukazuje IP
# IP ukazuje na slovo které se má vykonat (SQUARE)
# W nedefinováno
next: [ip] → w # W obsahuje adresu CFA slova SQUARE
ip + cell → ip # Posun IP na GROK
# continue [w] Nepřímý skok na adresu v CFA SQUARE
[w] → w # dereference w
continue w # Pokračuj ve vykonávání programu na adrese CFA SQUARE
# Před převedením řízení na CFA slova SQUARE mají
# registry následující hodnoty:
# IP ukazuje na následující slovo GROK, jenž se bude
# vykonávat po ukončení slova SQUARE
# W ukazuje na CFA slova SQUAREProtože je slovo SQUARE definováno kompilátorem :, je v jeho CFA adresa interpretu ENTER. Poslední instrukce rutiny NEXT tedy končí skokem na strojový kód interpretu ENTER.
Prvním krokem interpretu ENTER je tedy uschování hodnoty ukazatele instrukcí IP do zásobníku návratových adres RS. Je to proto, abychom mohli pokračovat v interpretaci slova FOO vykonáním další instrukce v pořadí, GROK. Poté uložím do IP obsah W které ukazuje na CFA slova SQUARE. Rutina končí voláním procedury NEXT. V tomto cyklu vykonání NEXT ukazuje IP na CFA SQUARE. Dojde tedy k získání adresy ENTER uložené v tomto CFA a ke skoku na tuto adresu. FIXME:
# ENTER (DOCOL or DOCOLON)
# IP ukazuje na slovo GROK, jenž se má vykonat
# po ukončení interpretace slova SQUARE
# W ukazuje na CFA slova SQUARE
enter: #push ip to rp Uschování IP do zásobníku RS (návratových adres)
ip → [rp]; rp+cell → rp
w + cell → ip # IP ukazuje na PF slova SQUARE
continue on next # Vykonej slovo SQUAREPoslední slove v definici SQUARE je EXIT. To provede návrat k bodu zpraování slova FOO.
# EXIT called ;S in fig-Forth
exit: #pop ip from rp # Obnov IP ze zásobníku, to nyní ukazuje na GROK
[rp] → ip
rp - cell → rp
continuee next # Pokračuj vykonáním slova GROKVe zkratce jsou tedy procedury NEXT, ENTER a EXIT definovány takto:
next: [ip] → w; ip + cell → ip; jmp (w) enter: rp - cell → rp; ip + cell → [rp]; w → ip; next exit: [rp] → ip; rp + cell → rp; next
Pro implementaci kde buňka má velikost jednoho slova a základní adresovatelnou jednotkou je jedno slovo, můžeme zápis za pomocí pre decrement ( -- ) a post increment ( ++ ) operátorů zjednodušit takto:
next: [ip++] → w; jmp (w) // enter: ip + 1 → [--rp]; w → ip; next exit: [rp++] → ip; next
Pro implemetaci kde velikost buňky je dvojnásobkem základní paměťové jednotky, typickým příkladem je implementace 16-ti bitového Forthu na 8-mi bitovém procesoru, to bude vypadat následovně:
next: [ip] → w; ip + 2 → ip; jmp (w) // enter: rp - 2 → rp; ip + 2 → [rp]; w → ip; next exit: [rp] → ip; rp + 2 → rp; next
Zkontrolováno podle MOVING FORTH, Part1: Design Decisions in the Forth Kernel by Brad Rodriguez, a důkladně promyšleno.
Všiměte si, že při vstupu do funkce ENTER ukazuje W na CFA slova jenž se má interpretovat. Proto před vastní interpretací (NEXT) je nutno do IP zapsat hodnotu o jednu buňku (CELL) větší, aby IP ukazoval na PF, tedy na první instrukci/adresu. Toto posunutí na následující buňku by se dalo přemístnit do funkce NEXT a to tak že by se instrukce jmp (w) nahradila instrukcí jmp (w)+. Výsledný kód by tedy vypadal:
next: (ip) → w
ip+
jmp (w)+Po rozepsání složitějších obratů za užití pomocného registru X:
next: (ip) → w
ip + cell → ip
(w) → x
w + cell → w
jmp xDůvod proč to tak učinit je jeden. Pokud budem mít alespoň dva interprety, nebudeme operaci W+cell provádět dvakrát, v každém vstupním bodu ENTRY a ENTRY2.
FIXME:Zbytek probrat a vyřadit.
Teď si je trochu blíže rozepíšeme.
Vnitřní interpret NEXT pro virtuální procesor
NEXT: (IP) → W ; úschova ukazatele do pracovního registru
next IP → IP ; posunutí na další adresu v definici (ip++)
(W) → X ; dereference adresy
JUMP X ; vykonání slova v definiciK vnitřnímu interpretu je třeba dodat kód interpretu vysokoúrovňových slov ENTER
ENTER: ; PUSH IP TO RSP
prev RSP → RSP
IP → (RSP)
next W → IP ; uložení adresy PFA do IP
JUMP NEXT
definice slova je ukončena adresou procedury EXIT ukončení definice
EXIT: ; POP IP FROM RSP
(RSP) → IP
next RSP → RSP
JUMP NEXTEach code field contains a machine code fragment. So, in the case of a primitive (machine code) definition, the xt is the address of the machin code itself.
Struktura slova ve slovníku
+----------+-----+---------------------------------+ | Hlavička | CFA | PF: adr1 adr2 adr3 ... adr_exit | +----------+-----+---------------------------------+
+----+-----+-----+-------------+ | NF | LF^ | CF^ | PF | +----+-----+-----+-------------+
; DOCOLON někdy nazývaná ENTER
DOCOLON: PUSH IP ; IP→-(RSP)
W + 2→IP ; PFA(W)→IP
; IP ukazuje na první adresu v PF
JUMP NEXT ; Skok do interpreteru adres
; DOSEMI někdy nazývaná EXIT poslední adresa v PF
DOSEMI: POP IP ; (RSP)+→IP
JUMP NEXT
NEXT: (IP)→W
IP + 2→IP ; posun na další adresu
(W)→X ;
JUMP (X)