Zásobníkové jazyky a jazyk Forth

Zásobníkové jazyky a jazyk Forth

Copyright © Rudolf Pecinovský, Soubor: FORTH_a_Zasobnikove_jazyky.doc, verze 1.00.2413, uloženo po 12.11.2012 – 15:06

1 z 64

Obsah 1. Historie a koncepce 2. Základy jazyka Forth 3. Algoritmické konstrukce 4. Vnitřní architektura 5. Definice datových struktur 6. Shrnutí


2 z 64

1. Historie a koncepce Obsah 1.1 Dělení jazyků 1.2 Zásobníkové jazyky 1.3 Historie a jazyka Forth 1/2 1.4 Historie a jazyka Forth 2/2 1.5 Zajímavé vlastnosti 1/3 1.6 Zajímavé vlastnosti 2/3 1.7 Zajímavé vlastnosti 3/3 1.8 Proč je málo rozšířený 1.9 Kde je možné se o jazyku dozvědět 1.10 Kde je možné se o jazyku dozvědět


3 z 64

1.1 Dělení jazyků ►

Deklarativní × Imperativní ● Deklarativní popisují, jaký má být výsledek (SQL, Prolog, HTML, …) ● Imperativní popisují, jak získat výsledek (většina známých jazyků)

►

Procedurální × Funkcionální × Logické ● Procedurální: Fortran, Algol, Pascal, C, Java … ● Funkcionální: Lisp, Logo, Scheme, F# ... ● Logické: Planner, Prolog

►

Prefixové × infixové × postfixové ● Prefixové: Lisp ● Infixové: Většina současných jazyků ● Postfixové: Forth, Postscript


4 z 64

1.2 Zásobníkové jazyky ►

Jsou založeny na představě zásobníkového procesoru

►

Používají jeden či více zásobníků, z nichž každý plní specifický účel

►

Převážně používají postfixovou notaci, která bývá označována jako obrácená polská notace ● Polská notace je alternativní označení pro prefixovou notaci ● Zavedl ji v roce 1920 Jan Łukasiewicz, když se snažit odstranit závorky


5 z 64

1.3 Historie a jazyka Forth ►

Autor: Charles H. Moore

►

Vytvořil jej v 60. letech a poprvé oficiálně použil při přípravě programu pro řízení 11metrového radioteleskopu

►

Protože byl autor s možnostmi tehdejších systémů nespokojen, vytvořil Forth současně jako jazyk, platformu, vývojové prostředí a svým způsobem i operační systém

►

Forth byl vytvořen jako jazyk pro osobní potřebu, který měl usnadnit řešení zadaných úkolů, ale rychle se rozšířil a stále si drží své místo mezi nejpopulárnějšími jazyky

1/2

● Původně se jazyk jmenoval FOURTH,

protože jej autor považoval za jazyk čtvrté generace, ale operační systém počítače, pro nějž byl vytvořen, dovoloval nejvýše pětiznakové identifikátory souborů


6 z 64

1.4 Historie a jazyka Forth ►

2/2

Autorovi jazyka vadilo množství jazyků potřebné pro zvládnutí práce s počítačem: ● Překladače a řídící programy byly v assembleru ● Pro řízení chodu se používal Job Control Language ● Pro tvorbu různých druh aplikací se používaly různé jazyky

►

Chtěl navrhnout jazyk, který by byl ● Jednoduchý, malý a čistý ● Snadno přenositelný ● Univerzální a snadno rozšiřitelný

►

Během 70. let implementoval toto prostředí postupně na 18 počítačích; pro každý musel vytvořit: ● Assembler ● Ovladače konzoly, disků a dalších periferií ● Většinou také vlastní knihovnu aritmetických operací


7 z 64

1.5 ►

Zajímavé vlastnosti

1/3

Forth je jedním za tří imperativních jazyků, které jsou základem všech dalších ● Prefix: Lisp ● Infix: Fortran Algol (C; Pascal) ● Postfix: Forth

►

Forth patří svým duchem spíš k funkcionálním jazykům

►

Forth má chameleonské schopnosti přizpůsobit se problému => při vývoji aplikací přirozeně vznikají doménově specifické jazyky, v nichž je ve finále aplikace vyvinuta ● Ve Forthu se nedá poznat, které části byly v původní instalaci

a co doprogramoval programátor sám ● Ve Forthu můžete definovat vlastní algoritmické konstrukce, vlastní primitivní datové typy a dokonce i vlastní paradigmata


8 z 64

1.6 Zajímavé vlastnosti ►

S výjimkou velmi malého jádra (okolo 50 primitiv) je celý interpret Forthu napsán ve Forthu

►

Napsat vlastní interpret Forthu je tak v silách většiny programátorů

2/3

● Znám člověka, který napsal vlastní Forth ve svých 11 letech ►

Ve Forthu je naprogramováno i vývojové prostředí, debugger, správa paměti, práce s disky, multiuživatelský přístup, paralelní procesy atd.

►

Forth je schopen pracovat (a v řadě případů také pracuje) i na počítačích bez operačního systému


9 z 64

1.7 Zajímavé vlastnosti ►

3/3

Programy napsané ve Forthu bývají výrazně menší než programy v jiných jazycích ● Sám jsem naprogramoval makroasembler se strukturovanými konstrukcemi

(podmínky, cykly), který zabral 800 bajtů

►

Vzhledem k DSL povaze Forthu bývají programátorské týmy hotovy výrazně rychleji, než bývá zvykem


10 z 64

1.8 Proč je málo rozšířený ►

Podle Tiobe je v rozšíření jazyků na 38. místě

►

Zavádí nezvyklé paradigma, které řadu programátorů zaskočí

►

Je to jazyk, který vám dovolí úplně vše, což programátory zvyklé na obezděné pískoviště mainstreamových jazyků silně znejistí

►

Jazyk funguje jako zesilovač programátorských schopností ● Dobří programátoři píší ještě lepší programy ● Špatní programátoři píší ještě větší prasárny


11 z 64

1.9 Kde je možné se o jazyku dozvědět ● Seriál z Amatérského rádia 2003 ● ● ● ● ● ●

http://publikace.pecinovsky.cz/ Seriál Programovací jazyk Forth http://www.root.cz/serialy/programovaci-jazyk-forth/ The Evolution of Forth http://www.forth.com/resources/evolution/evolve_0.html Starting FORTH by Leo Brodie http://www.forth.com/starting-forth/index.html Thinking Forth http://thinking-forth.sourceforge.net/ Programming Forth http://www.mpeforth.com/arena/ProgramForth.pdf Forth Standard 200x (Draft 12.1 – 30th September 2012) http://www.forth200x.org/documents/forth12-1.pdf


12 z 64

1.10 Kde je možné se o jazyku dozvědět ►

Implementace v jazyku Java s českou dokumentací

● Bc. Petr Kováč: Interpret jazyka Forth jako nástroj pro návrh

interních doménově specifických jazyků. Bakalářská práce. VŠE

►

►

► ► ►

J2EE Forth and J2SE Forth

http://sourceforge.net/projects/j2eeforth/ http://heanet.dl.sourceforge.net/project/j2eeforth/downloads/J2EE_Forth_ and_Manuals_1_0_31.zip

Win32Forth

http://www.win32forth.org/ Dokumentace: http://win32forth.sourceforge.net/doc/p-index.htm

GForth (Forth pod licencí GNU)

http://www.complang.tuwien.ac.at/forth/gforth/

myForth – Forth v Javě běžící jako aplet

http://www.angelfire.com/mn2/myyahtzee/mylarge.html

Forth Interested Group – implementace verze figForth http://www.forth.org/fig-forth/contents.html §


13 z 64

2. Základy jazyka Forth Obsah 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Syntaxe jazyka Forth Koncepce Hybridní povaha Trocha zkratek Slova pro tisk Základní operace se zásobníkem 1/3 Základní operace se zásobníkem 2/3 Základní operace se zásobníkem 3/3 Aritmetické operace

2.10 Definice nových slov 2.11 Tištěný text v definici 2.12 Komentáře 2.13 Proměnné a číselné soustavy 2.14 Číselné soustavy 2.15 Příklad: Tisk slova v různých bázích 2.16 Práce se ZNA 2.17 Nestandardní možnosti


14 z 64

2.1 Syntaxe jazyka Forth ►

Jazyk má jediný syntaktický element: slovo

►

Slovo je libovolná posloupnost nebílých znaků

►

Program je posloupnosti slov oddělených bílými znaky

►

Slovo je ekvivalentem procedury / funkce / metody známé z klasických jazyků

►

Uživatel si může definovat vlastní slova

►

Definovaná slova se ukládají do slovníku

►

Při provádění se systém pokusí najít slovo ve slovníku; nenajde-li je, pokusí se je interpretovat jako číslo; nepodaří-li se mu to, ohlásí chybu


15 z 64

2.2 Koncepce ►

Koncepce jazyka je postavena na dvou zásobnících ● Operační (pracovní) zásobník operandů označovaný jako

uživatelský zásobník (UZ) nebo jenom zásobník ● Systémový zásobník označovaný jako zásobník návratových adres (ZNA) ►

Některé verze používají ještě další zásobník pro aritmetiku v plovoucí čárce

►

Slova Forthu: ● očekávají svoje parametry na zásobníku, ● odkud si je odeberou ● a kam následně vrátí požadovaný výsledek


16 z 64

2.3 Hybridní povaha ►

Hybridní koncepce (obdobně jako Java, C#, …): ● program se převede do mezikódu, ● který se při spuštění programu interpretuje

►

O překlad do mezikódu se stará tzv. vnější interpret, který zpracovává každý řádek hned jak je zadán ● Spouštěná slova nechá ihned provést ● Definovaná slova převede do mezikódu

(což je vlastně provedení slova definujícího nové slovo)

►

O vlastní provádění se stará tzv. vnitřní interpret, který interpretuje mezikód vytvořený vnějším interpretem

►

Vytvořený mezikód je systém schopen kdykoliv „dekompilovat“ na původní zdrojový tvar

►

Program může sloužit jako interaktivní prostředí, v němž můžete kdykoliv cokoliv upravit


17 z 64

2.4 Trocha zkratek ►

UZ – uživatelský zásobník

►

ZNA – Zásobník návratových adres

►

TOS

►

NOS – Položka pod vrškem zásobníku (next on stack)

►

NNOS – Položka „pod“ NOS

►

Zásobníku budeme kreslit:

– Vršek zásobníku (top of stack)

● Od kořene zleva doprava – TOS je poslední vpravo ● Od kořene shora dolů – TOS je poslední dole ►

RA – Návratová adresa (return address)


18 z 64

2.5 Slova pro tisk ►

. \ w ® Vytiskne hodnotu na TOS v aktuálním číselném základu

►

.S \ ... ® ... Vytiskne obsah zásobníku, aniž by jej měnilo

►

CR Odřádkuje

►

SPACE Vytiskne mezeru

►

EMIT \ w ® Vytiskne znak, jehož kód je na zásobníku

►

Příklad: 1 2 . . 3 SPACE 4 . 33 EMIT . Vytiskne: 21 4!3


19 z 64

2.6 Základní operace se zásobníkem ►

DROP \ w ® Smaže vrchní položku ze zásobníku

►

DUP \ w ® w w Duplikuje vršek zásobníku

►

NIP \ w1 w2 ® w2 Duplikuje vršek zásobníku

►

SWAP \ w1 w2 ® w2 w1 Prohodí vrchní dvě položky na zásobníku

►

OVER \ w1 w2 ® w1 w2 w1 Zkopíruje původní NOS na nový TOS

►

TUCK \ w1 w2 ® w2 w1 w2 Zkopíruje původní NOS na nový TOS


1/3

20 z 64


ROT \ w1 w2 w3 ® w2 w3 w1 Rotuje vrchní tři položky zásobníku „vlevo“, resp. přesune třetí položku na zásobníku na TOS

►

-ROT \ w1 w2 w3 ® w3 w1 w2 Rotuje vrchní tři položky zásobníku „vpravo“, resp. zasune položku na zásobníku jako třetí

►

ROLL \ w0 w1 … wN N ® w1 … wN w0 Přesune zadanou položku na TOS

►

‐ROLL \ w0 … w(N‐1) wN N ® wN w0 … w(N‐1) Zasune TOS na zadanou pozici na zásobníku

►

2DUP

2/3

\ w1 w2 ® w1 w2 w1 w2


21 z 64


2DROP \ w1 w2 ® Smaže vrchní položku ze zásobníku

►

2DUP \ w1 w2 ® w1 w2 w1 w2 Duplikuje vršek zásobníku

►

2NIP \ w1 w2 w3 w4 ® w3 w4 Duplikuje vršek zásobníku

►

2SWAP \ w1 w2 w3 w4 ® w3 w4 w1 w2 Prohodí vrchní dvě položky na zásobníku

►

2OVER \ w1 w2 w3 w4 ® w1 w2 w3 w4 w1 w2 Zkopíruje původní NOS na nový TOS

►

2TUCK \ w1 w2 w3 w4 ® w3 w4 w1 w2 w3 w4 Zkopíruje původní NOS na nový TOS


3/3

22 z 64

2.9 Aritmetické operace ►

Používá se obrácená polská (= postfixová) notace

►

Příklad: ((2 + 3) * (7 – 4)) ** 2 2 3 + 7 4 ‐ * DUP * . ——————————————————————————————— 2 2 5 5 5 5 15 15 225 3 7 7 3 15 4

►

Příklad: (13 – 8) **3 / (2 + 4) 13 8 ‐ DUP DUP * * 2 4 + / . ——————————————————————————————————————————— 13 13 5 5 5 5 125 125 125 125 20 8 5 5 25 2 2 6 5 4


23 z 64

2.10 Definice nových slov ►

K definici nových slov slouží slovo : následované názvem definovaného slova

►

Definice slova je standardně ukončována slovem ;

►

: 2NA DUP * ; ——————————————————————————————— N N N^2 N

►

: 3NA DUP 2NA * ; ——————————————————————————————— N N N N^3 N N^2


24 z 64

2.11 Tištěný text v definici ►

." Používá se v definicích slov; vytiskne následující text v definici až po znak " (uvozovky) Za slovem ." musí být JEDNA mezera, další se berou jako text

►

: POZDRAV ." Dobrý den" ;


25 z 64

2.12 Komentáře ►

( V definičním režimu označuje začátek komentáře. Komentářem je text za následující mezerou až po zavírací závorku – může tedy zabírat několik řádků

►

\ Označuje začátek komentáře končícího koncem řádku


26 z 64

2.13 Proměnné a číselné soustavy ►

@ \ Adr  Val Nahradí na TOS adresu hodnotou na této adrese

►

! \ Val Adr  Uloží hodnotu z NOS na adresu z TOS

►

VARIABLE ● DEFINICE: Definuje proměnnou s názvem, který následuje

a vynuluje ji ● PROVÁDĚNÍ: Uloží na TOS adresu dané proměnné ● POUŽITÍ: VARIABLE PREDMET ( Vytvoří proměnnou PŘEDMĚT) 101 PREDMET ! ( Uloží do ní hodnotu 101) PREDMET @ ( Obsah proměnné uloží na zásobník) ►

: 2*= ( Adr – Slovo, jež zdvojnásobí obsah proměnné) DUP @ 2* ( Adr 2*Hodn – Z kopie adresy vezmu hodnotu a zdvojím) SWAP ( 2*Hodn Adr – Při ukládání musí být adresa na TOS) ! ; ( Zdvojnásobená hodnota je uložena v proměnné)


27 z 64

2.14 Číselné soustavy ►

BASE Proměnná uchovávající základ používané číselné soustavy pro IO

►

DECIMAL Nastaví vstup a výstup v desítkové soustavě : DECIMAL 10 BASE ! ;

►

Změním-li číselnou soustavu, platí pro čtení i psaní => ovlivní definici programu i tisky


28 z 64

2.15 Příklad: Tisk slova v různých bázích ►

: DEC DECIMAL ;

►

: BIN 2 BASE ! ; ( Nastaví IO ve dvojkové soustavě)

►

: HEX 16 BASE ! ; ( Nastaví IO v šestnáctkové soustavě)

►

: .B ( Vytiskne TOS v šestnáctkové, desítkové a binární soust.) BASE @ SWAP ." TOS = " DUP HEX . ." (H) = " DUP DEC . ." (D) = " BIN . ." (B) " BASE ! ;


29 z 64

2.16 Práce se ZNA ►

>R \ w ® Uloží TOS na ZNA

►

R> \ ® w Uloží TOS ZNA na TOS a odebere jej ze ZNA

►

: R@ \ ® w Nedestruktivní čtení TOS ZNA R> R> DUP >R SWAP >R ; ————————————————————————————— |N RA|N RA| RA| RA|N N|N N|N |RA N| N| N| RA| |RA N|

►

: OVER >R DUP R> SWAP ;


30 z 64

2.17 Nestandardní možnosti ►

Jazyk umožňuje vlastními silami definovat konstrukce, které jsou v jiných jazycích součástí jejich syntaxe a jejich změna je pro programátora nedosažitelná

►

: EXIT \ ® w Předčasné opuštění procedury (return uprostřed definice) R> DROP ; —————————-————————————————————— |RACaler RAExir|RACaler |RACaler |RAExit§


31 z 64

3. Algoritmické konstrukce Obsah 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8

Podmíněný příkaz IF … ENDIF Příklady použití IF Příklady použití IF Podmíněné větvení IF … ELSE … ENDIF Cyklus s parametrem DO … LOOP Cyklus se zadaným přírůstkem Cyklus BEGIN ... UNTIL Cyklus BEGIN ... WHILE ... REPEAT


32 z 64

3.1 Podmíněný příkaz IF … ENDIF ►

NEGATE \ N ® –N Obrátí znaménko TOS

►

< \ N1 N2 ® (N1
►

0< \ N ® (N<0) Zjistí, zda je TOS < 0

►

IF \ N ® Přečte TOS a nastaví pokračování dle jeho hodnoty

►

ENDIF THEN Označuje konec části, která se má vykonat při splněné podmínce


33 z 64

3.2 Příklady použití IF ►

: ABS \ w ® Abs(w) DUP 0< IF NEGATE ENDIF ; ————————————————————————— N N N N ‐N |N| N N<0

►

: MAX \ w1 w2 ® Max(w1, w2) 2DUP < IF SWAP ENDIF DROP ; ———————————————————————————————— N1 N1 N1 N1 N2 Max Max N2 N2 N2 N2 N1 Min N1 N1

34 z 64

3.3 Příklady použití IF ►

QUIT \ ... ® Ukončí vykonávání programu, vyčistí ZNA a vrátí se do interpretačního režimu

►

: ?DUP \ w  w w? ( Zduplikuje nenulovou hodnotu na TOS) DUP 0<> IF DUP ENDIF ;

►

: MIN \ w1 w2 ® Min(w1, w2) 2DUP > IF SWAP ENDIF DROP ;

►

: MEZE \ n HM ® ( Ověří, že 0 <= NOS < TOS) OVER <= SWAP 0< OR IF ———————————————————————————————— n n n (HM<=n) (HM<=n) zle? HM HM (HM<=n) n (n<0) n CR CR ." Index mimo meze" QUIT ENDIF ;


35 z 64

3.4 Podmíněné větvení IF … ELSE … ENDIF ►

: SIGN \ w ® Signum(w) (= ‐1 × 0 × 1) DUP 0< IF DROP –1 ELSE 0= IF 0 ELSE 1 ENDIF ENDIF ;


36 z 64

3.5 Cyklus s parametrem DO … LOOP ►

DO \ Konec Start ® Očekává v TOS počáteční a v NOS ukončovací hodnotu parametru cyklu

►

LOOP \ ® Ukončuje tělo cyklu

►

I \ ® w Umístí na TOS hodnotu parametru cyklu

►

J \ ® w Umístí na TOS hodnotu parametru vnějšího cyklu

►

: SPACES \ n ® ( Vytiskne zadaný počet mezer) 0 DO SPACE LOOP ;

►

: PREVTAB \ Konec První ® ( Vytiskne tabulku převodů ) DO I .B CR LOOP ;


37 z 64

3.6 Cyklus se zadaným přírůstkem ►

+LOOP \ w ® Ukončuje tělo cyklu

►

PICK \ w0 w1 … wN N ® w1 … wN w0 Zkopíruje na TOS zadanou položku zásobníku; položka pod zadaným indexem má index 0

►

SP@ \ ® Adr Uloží na TOS adresu původního TOS

►

: DEPTH

►

: .S \ ® ( Vytiskne obsah zásobníku) 0 DEPTH 2 ‐ DO I PICK . SPACE ‐1 +LOOP ; ( 2‐ aby se odebrala přidaná 0, druhá možnost: DEPTH 0 SWAP )

\ ® N ( Vrátí počet položek na zásobníku)


38 z 64

3.7 Cyklus BEGIN ... UNTIL ►

BEGIN \ ® Slouží pouze jako návěští označující začátek cyklu

►

UNTIL \ f ® Testuje TOS na jeho pravdivostní hodnotu. V případě FALSE opakuje cyklus, tj. vrací výpočet za BEGIN v případě TRUE ukončuje cyklus a pokračuje následujícím slovem


39 z 64

3.7.1 Příklad: Nejmenší společný násobek : NSN \ w1 w2 ® nsn Spočte nejmenší společný násobek čísel na TOS a NOS 2DUP < IF SWAP ENDIF \ TOS je menší z obou čísel >R 0 \ Menší uloženo na ZNA, odhad = 0 BEGIN \ NOS je větší číslo, TOS je odhad NSN OVER + \ Připočtu NOS k TOS a získám nový odhad DUP R@ MOD 0= \ Je dělitelný druhým (větším) číslem? UNTIL \ Dokud není, opakuj cyklus SWAP \ Ulož výsledek k zapamatování DROP R> DROP ; \ Smaž obě výchozí čísla


40 z 64

3.8 Cyklus BEGIN ... WHILE ... REPEAT ►

BEGIN \ ® Slouží pouze jako návěští označující začátek cyklu

►

WHILE \ f ® Testuje TOS na jeho pravdivostní hodnotu. V případě TRUE pokračuje dál, v případě FALSE ukončí cyklus a pokračuje prvním slovem za slovem REPEAT

►

REPEAT \ ® Vrací výpočet zpět za slovo BEGIN


41 z 64

3.8.1 Příklady: Nejmenší společný násobek ►

: NSN \ w1 w2 ® nsn Spočte nejmenší společný násobek čísel na TOS a NOS 2DUP < IF SWAP ENDIF \ TOS je menší z obou čísel >R DUP \ NOS = TOS je větší číslo i výchozí odhad BEGIN DUP R@ MOD \ Je odhad dělitelný druhým číslem? WHILE \ Pokud ne, spočti další odhad OVER + \ TOS = nový odhad REPEAT SWAP DROP R> DROP ; \ Smaž obě čísla


42 z 64

3.8.2 Příklady: Největší společný dělitel ►

: EUKL \ w1 w2 ® nsd Spočte největšího společného dělitele čísel na TOS a NOS podle Eukleidova algoritmu BEGIN DDUP <> WHILE \ Pokračuj, dokud je NOS <> TOS DDUP > \ TOS říká, zda byl TOS menší IF SWAP ENDIF \ TOS = větší z obou čísel OVER ‐ \ TOS = rozdíl obou čísel REPEAT DROP ; \ Obě NSD => smaž jedno z nich§


43 z 64

4. Vnitřní architektura Obsah 4.1 Struktura slovníku 4.1.1 Používané zkratky 4.2 Propojení součástí 4.2.1 Nepřímé propojení – indirect threaded code 4.2.2 Přímé propojení– direct threaded code 4.2.3 Propojení přes volání podprogramů 4.2.4 Používání „in-line“ kódu 4.2.5 Propojení prostřednictvím symbolů 4.3 Používání registrů


44 z 64

4.1 Struktura slovníku ►

Následující ukázka je z 8bitového počítače, na vícebitových bývají slova zarovnána na hranici paměťového slova, tj. na 16 nebo 32 bajtů

►

Program je velice kompaktní, často kratší než jeho ekvivalent napsaný v assembleru

►

Tento způsob uložení nerozlišuje fázi zadávání a běhu programu ● Hned poté, co program napíšete, je přeložen a takto uložen ● Když později slovo voláte, spustí se uložená definice

►

Protože Forth překládá slovo ihned, není možné používat dopředné odkazy – ty se musejí zadávat přes pomocná slova, která se naplní až bude odkazované slovo definováno


45 z 64

NFA

LFA CFA PFA

NFA

LFA CFA

Adresa 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

Obsah 4 2 D U P SA : OVER

Význam Délka jména Jméno Spojovací adresa vedoucí na předchůdce Adresa výkonné části překladače Adresa slova směřuje na jeho AVCP

OVER EXIT 3 R O T

Délka jména Jméno

101

Spojovací adresa vedoucí na předchůdce

124

Slovo definované v assembleru => adresa těla


46 z 64

4.1.1 Používané zkratky ►

NFA = Name-field address je adresa pole, v němž začíná název daného slova

►

LFA = Link-field address je adresa pole obsahující odkaz na NFA předchozího slova => prostřednictvím LFA jsou zřetězena všechna slova ve slovníku

►

CFA = Code-field address je adresa pole, v němž je uložen kód (případně odkaz na kód), který se spustí při zavolání daného slova

►

PFA = Parameter Field Address označuje začátek oblasti, v níž jsou v definicích ve Forthu uloženy CFA slov, která se mají vykonat


47 z 64

4.2 Propojení součástí ►

Forth bývá implementován jako propojený („sešitý“) jazyk (threaded language)

►

Tato „sešitost“ je jednou z jeho typických vlastností

►

Většina slova je definována jako posloupnosti odkazů na jiná slova

►

Způsob zakomponování těchto odkazů a způsob jejich následné interpretace se mohou v jednotlivých implementacích lišit


48 z 64

4.2.1 Nepřímé propojení – indirect threaded code ►

Implementace podle standardu Forth83 používali nepřímé propojení; jiné způsoby jsou pouze snahou o zvýšení efektivity

►

Následující obrázek popisuje propojení částí kódu definice: : SQUARE DUP * ;


49 z 64

►

Při vykonávání slova se postupuje následovně: 1. Načte se CFA slova, které se má vykonat 2. Na této adrese se zjistí adresa kódu, který se má provést ● U slov definovaných veš strojovém kódu ukazuje přímo na kód, který se spustí (je často v na PFA) ● U slov definovaných ve Forthu ukazuje na kód, který uloží návratovou hodnotu na ZNA a začne provádět slova v paměti začínající na PFA 3. Provede se příslušný kód 4. Přejde se na další slovo v definici

►

Hlavní výhodou nepřímého volání je úspora paměti, protože na všech místech, odkud je slovo voláno, je pouze jeho adresa, čímž ušetříme bajty potřebné pro kód instrukce ● Implementace využívající nepřímé volání proto často generují kratší kód,

než kdybychom tutéž funkčnost naprogramovali klasicky v asembleru


50 z 64

4.2.2 Přímé propojení– direct threaded code ►

Nepřímé propojení vede na řadu nepřímých volání, která mohou být na některých procesorech velmi pomalá

►

Některé implementace proto začaly používat přímé propojení které se od nepřímého liší pouze v tom, že v CFA není pouhá adresa, ale přímo instrukce, která skáče na výkonnou část překladače


51 z 64

►

Použití přímého propojení vede vždy ke zvýšení rychlosti, ale nemusí vždy vést ke zvětšení potřebné paměti

►

Příklady: ● Z80 – Počet instrukcí vnitřního interpretu se sníží z 11 na 7,

ale délka kódu se zvětší o polovinu ● Motorola 68000 – rychlost se zvýší, ale délka kódu se nezmění ● Zilog Super8 – délka kódu se dokonce zmenší na polovinu, protože tento procesor má v instrukčním souboru speciální instrukce pro podporu práce ve dvoubajtovém Forthu ►

Otázkou bývá, jak zakončovat definice v kódu ● Skokem na část kódu, která:

přesune IP (Instruction Pointer) v aktuální definici na další slovo a ● spustí provádění tohoto slova ● Zopakováním tohoto kódu na konci každé definice ● Vzhledem k tomu, že u moderních procesorů zabírá tento kód od jedné do tří instrukcí, bývá často v zájmu rychlosti kopírován ●


52 z 64

4.2.3 Propojení přes volání podprogramů ►

Definice ve Forthu jsou pouhými seznamy podprogramů, které se mají provést => není třeba je interpretovat, ale můžeme je přímo zavolat a provést ● Kód se tím dále zrychlí ● Na druhou stranu se také zvětší, a to až o 50 % ● U některých procesorů se tím zkomplikuje práce se zásobníkem


53 z 64

4.2.4 Používání „in-line“ kódu ►

Na starších procesorech byla i jednoduchá slova definována prostřednictvím několika instrukcí

►

U novějších procesorů lze klíčová primitiva naprogramovat prostřednictvím jedné či dvou instrukcí

►

Při používání STC se proto často některá primitiva nevolají, ale jejich kód se na dané místo přímo zapíše


54 z 64

4.2.5 Propojení prostřednictvím symbolů ►

Předchozí způsoby preferovaly rychlost na úkor spotřeba paměti; někdy je ale času dost, zato otázka paměti bývá kritická

►

Propojení prostřednictvím symbolů bývá o něco pomalejší, ale na druhou stranu bývá úspornější na paměť


55 z 64

4.3 Používání registrů ►

W – Working Register

►

IP – Instruction Pointer

►

PSP – Parameter Stack (Data Stack) Pointer

►

RSP – Return Stack Pointer

►

UP – User Pointer

►

X – Working Register

►

TOS – Top of Stack§


56 z 64

5. Definice datových struktur Obsah 5.1 Tvorba nových objektů jazyka 5.1.1 CREATE (dříve a ;CODE 5.1.3 Příklad 5.2 Další vlastnosti


57 z 64

5.1 Tvorba nových objektů jazyka ►

Slovo : (dvojtečka) se chová jako překladač, protože definuje nová slova a překládá je do vnitřní podoby

►

Dvojtečka ale definuje jenom výkonná slova, pro další druhy slov je třeba definovat jejich vlastní překladače

►

Při definici překladačů je třeba definovat dvě činnosti ● Co se bude provádět při definici daného slova ● Co se bude provádět při vykonávání daného slova

►

CREATE (dříve
►

DOES> Definuje, co se bude provádět, když dané slovo někdo zavolá

►

;CODE Totéž, ale pro výkonnou část ve strojovém kódu


58 z 64

5.1.1 CREATE (dříve
Rozpozná ve vstupním textu název definovaného slova

►

Vytvoří hlavičku slova obsahující název …

►

a přidá do ní LFA napojující slovo na jeho předchůdce

►

Připraví pole označované Code Field (tj. na CFA) aby do něj mohla být později vložena adresu (při ITC; při DTC, CTC či TTC jiný odpovídající údaj) budoucí výkonné části


59 z 64

5.1.2 DOES> a ;CODE ►

Ukládají do Code Field informaci definovaného slova informaci, která:

►

;CODE zabezpečí spuštění příslušného strojového kódu

►

DOES> zabezpečí spuštění kódu napsaného ve Forthu

►

Vytvořený kód přitom obdrží na TOS PFA vytvořeného slova


60 z 64

5.1.3 Příklad ►

: VARIABLE ( Definuje proměnnou a inicializuje ji na 0) CREATE 0 , ( Uloží nulu do slovníku) DOES> ( Nemusí nic dělat, protože PFA je již na TOS) ;

►

: CONSTANT ( Definuje konstantu, které přiřadí hodnotu TOS) CREATE , ( Hodnotu z TOS uloží do slovníku) DOES> @ ( PFA na TOS nahradí uloženou hodnotou) ;


61 z 64

►

: VEKTOR ( Definuje jednorozměrné pole) CREATE ( Akce prováděná při překladu: Vytvoření hlavičky) ( Očekává na TOS počet prvků vytvářeného pole) DUP , ( Uložení délky vektoru) 0 DO 0 , LOOP ( Vynulování obsahu) DOES> ( Akce prováděná při spuštění slova) ( Očekává index požadovaného prvku a na TOS PFA) DDUP MEZE ( Test: 0 <= Index < PočetPrvků) 2+ ( index PFA+2 ‐‐ Na TOS je adresa počátečního prvku) SWAP 2* ( Index se vynásobí délkou slova) + ( Sečte se s adrsou počátku pole) ; ( Na TOS je adresu prvku se zadaným indexem)

►

Druhou možností je definovat vektor obdobně jako proměnnou, tj. při zavolání nechat uložit na TOS adresu a neprovádět žádnou další akci a pro získání adresy indexovaného prvku definovat slovo []


62 z 64

5.2 Další vlastnosti ►

Výše popsaným způsobem lze přidávat nejrůznější konstrukce ● Algoritmické konstrukce ● Datové struktury ● Objekty ve stylu OOP ● Výjimky ● Práci s vlákny ● …

►

Forth od začátku podporuje jmenné prostory – označuje je jako slovníky – VOCABULARY ● Slovníky mají stromovou strukturu ● Slovo z synovského slovníku vidí i na slova z rodičovských slovníků

(podobné dědičnosti)

►

Není problém definovat výkonnostně kritická slova v assembleru§


63 z 64

6. Shrnutí ►

Koncepce jazyka je tak jednoduchá, že není problém vytvořit vlastní implementaci šitou na míru konkrétním potřebám

►

Jazyk se hojně používá při práci s jednoúčelovými zařízeními bez vlastního operačního systému

►

V řadě případů se sice používají existující implementace, ale většinou si uživatel vytvoří vlastní

►

Existující implementace slouží v mnoha případech spíše jako návody či inspirace pro vytvoření vlastní

►

Je to pravděpodobně jazyk s největším množstvím implementací


64 z 64

Zásobníkové jazyky a jazyk Forth

Recommend Documents