Hlavní navigace

Programujeme ve Factoru

Pavel Tišnovský 5. 2. 2008

Ve druhé části článku o netradičním programovacím jazyce Factor si ukážeme základní i pokročilejší programátorské postupy, které je možné v tomto jazyku používat při tvorbě aplikací, zejména práci se zásobníkem operandů a úschovným zásobníkem. Také si popíšeme způsob práce se základními datovými typy.

Obsah

1. Zásobníkový efekt (stack effect)
2. Operátory určené pro manipulaci se zásobníkem
3. Operátory sloužící pro odstranění položek ze zásobníku
4. Operátory sloužící pro vytvoření kopie (duplikaci) položek na zásobníku
5. Operátory sloužící pro změnu pořadí položek na zásobníku
6. Operátory určené pro manipulaci s úschovným zásobníkem
7. Základní datové typy
8. Matematické operace
9. Obsah třetí části článku o programovacím jazyku Factor

1. Zásobníkový efekt (stack effect)

V prakticky všech programovacích jazycích, které pro vyhodnocování matematických, logických a dalších výrazů používají zásobník, se vyskytuje množina příkazů (můžeme jim říkat i operátory či slova), které slouží pro manipulaci se zásobníkem, resp. pro manipulaci s hodnotami uloženými na zásobníku, konkrétně blízko jeho vrcholu. Vzhledem k existenci těchto operátorů se již nejedná o čistě postfixové jazyky. Ty jsou samy o sobě sice důležité z teoretického hlediska (existují například jednozásobníkové či vícezásobníkové automaty), ovšem z hlediska praktického je důležité s položkami uloženými na zásobníku manipulovat, zejména v jazycích, ve kterých se nepoužívají proměnné, nebo je využití proměnných z různých důvodů omezeno, například kvůli větším možnostem refaktoringu a jednotkových testů.

Dále popsaná skupina operátorů jazyka Factor je z velké části inspirována Forthem Chucka Moorea a částečně také PostScriptem (jazykem určeným pro popis tiskové stránky od firmy Adobe Systems). Bližší informace o těchto jazycích je možné nalézt například v seriálu Programovací jazyk Forth a Grafické formáty. Už před několika desítkami let programátoři píšící aplikace v programovacím jazyce Forth používali pro popis vlivu slov (příkazů) na položky uložené na zásobníku takzvaný zásobníkový efekt (stack effect). Pro další čtení je důležité si čtení zásobníkového efektu osvojit.

Nejedná se ve své podstatě o nic složitého: uvnitř kulatých závorek, které ve ForthuFactoru značí začátek a konec poznámky se zásobníkovým efektem, je symbolicky zapsán stav části zásobníku před provedením operace a po dvojici znaků stav zásobníku po provedení dané operace. Vzhledem k tomu, že na zásobníku může být uloženo teoreticky libovolné množství hodnot a daná operace většinou ovlivňuje pouze hodnoty umístěné blízko jeho vrcholu, je zásobníkový efekt zapsán pouze pro ty pozice na zásobníku, které jsou operací nějakým způsobem dotčeny, tj. operace tyto hodnoty přečte, zruší či modifikuje. Položky umístěné níže nemá cenu zapisovat, jen by zápis zbytečně komplikovaly. Položka umístěná nejvíce vlevo je ve skutečnosti uložena na spodnějších místech zásobníku, než položky napravo od ní.

factor21

Ve vývojovém prostředí Factoru se zásobníkový efekt vypisuje pro každý známý operátor na informačním řádku (ten je zobrazený v inverzních barvách ve spodní části okna)

Následuje jednoduchý příklad zápisu zásobníkového efektu pro operaci součtu dvou čísel. Nejprve je zapsán název operace, v tomto případě nazvané plus. Poté je zapsána otevírací kulatá závorka značící začátek poznámky, za níž následuje stav nejvyšších položek zásobníku před provedením operace. Po oddělovači představovaném dvojicí znaků je uveden stav nejvyšších položek po provedení operace, za nímž následuje uzavírací kulatá závorka značící konec poznámky (ve skutečnosti jsou i kulaté závorky běžnými slovy jazyka a proto musí být od okolních slov odděleny alespoň jednou mezerou).

Vzhledem k tomu, že operace sčítání načte dvě hodnoty ze zásobníku a zpět vloží jejich součet, jsou použity odlišné symboly x, y a z, přičemž samozřejmě platí, že z=x+y:

! "hlavička" operátoru plus
plus ( x y -- z ) 

Pokud by nějaká operace například prohazovala hodnoty uložené na zásobníku, ale jinak by je žádným způsobem neměnila, byly by použity stejné symboly, což je případ dále popsaného operátoru swap či rot.

! "hlavička" operátorů swap a rot
swap ( x y -- y x )
rot  ( x y z -- y z x ) 

2. Operátory určené pro manipulaci se zásobníkem

Prakticky ve všech programech napsaných v programovacím jazyku Factor se nevyhneme manipulaci s hodnotami uloženými na zásobníku. Je to především z toho důvodu, že je sice možné pro meziúschovu hodnot použít proměnné (tak jako ve většině imperativních jazycích), ale není to příliš vhodné, ať už z hlediska rozšiřitelnosti nebo testovatelnosti programu (kód mající za vstup i výstup pouze zásobník je od ostatního kódu velmi izolovaný a tím pádem i přenositelný a snadno testovatelný).

Mezi operátory, pomocí kterých lze v programovacím jazyce Factor manipulovat se zásobníkem, patří především operátory pro odstranění položek ze zásobníku (dropping), operátory pro kopie (duplikace) hodnot umístěných na zásobníku (duplicating), operátory pro změnu pořadí položek umístěných na zásobníku a konečně operátory, které manipulují s takzvaným úschovným zásobníkem (retain stack), který ve Factoru nahrazuje zásobník návratových adres (return stack) známý především z programovacího jazyka Forth.

factor22

Takzvaný browser ve vývojovém prostředí Factoru slouží především k procházení dokumentace

3. Operátory sloužící pro odstranění položek ze zásobníku

Tyto operátory slouží pro odstranění jedné nebo více hodnot, jež se nachází buď přímo na vrcholu zásobníku (TOS – Top Of Stack) nebo na nejbližších nižších místech. V mnoha případech se při programování setkáme s tím, že nějaká operace zanechala na zásobníku hodnotu, kterou již pro další práci nepotřebujeme (také se může jednat o hodnotu, kterou tam z určitého důvodu vložil sám programátor). Z toho důvodu je možné použít jeden z níže uvedených „mazacích“ operátorů nebo si napsat operátor vlastní. Názvy těchto operátorů se vyskytly již v jazyce Forth. Operátory 2drop a 3drop jsou vlastně pouze zkratkami programů drop drop a drop drop drop:

Operace Zásobníkový efekt Popis
drop ( x – ) odstranění hodnoty z vrcholu zásobníku (TOS)
2drop ( x y – ) odstranění hodnot z vrcholu zásobníku (TOS) a místa pod vrcholem
3drop ( x y z – ) odstranění tří nejvyšších položek ze zásobníku
nip ( x y – y ) odstranění pouze druhé nejvyšší položky ze zásobníku
2nip ( x y z – z ) odstranění druhé a třetí nejvyšší položky ze zásobníku
factor23

Trasování programu při výskytu chyby v integrovaném vývojovém prostředí Factoru

4. Operátory sloužící pro vytvoření kopie (duplikaci) položek na zásobníku

Prakticky stejně často jako odstraňování položek ze zásobníku potřebujeme i jejich kopii, čili – řečeno jazykem Chucka Moorea – duplikaci. Například většina aritmetických operací, mezi něž patří i operace +, max, floor nebo neg, automaticky odstraňuje své operandy a někdy nastane situace, kdy je původní hodnota důležitá pro další výpočet. Právě tehdy se využijí následující operace. Všimněte si odlišnosti vlivu operátoru 2dup od kódu dup dup. V obou případech se sice na zásobníku objeví dvě další položky, ovšem s rozdílnými hodnotami.

Operace Zásobníkový efekt Popis
dup ( x – x x ) duplikace hodnoty uložené na vrcholu zásobníku
2dup ( x y – x y x y ) duplikace dvou nejvyšších hodnot na zásobníku se zachováním pořadí
3dup ( x y z – x y z x y z ) duplikace tří nejvyšších hodnot na zásobníku se zachování jejich pořadí
dupd ( x y – x x y ) duplikace hodnoty uložené těsně pod vrcholem zásobníku
over ( x y – x y x ) hodnota uložená těsně pod vrcholem zásobníku je okopírována na jeho vrchol
pick ( x y z – x y z x ) podobné operaci over, ale vybírá se třetí nejvyšší hodnota
tuck ( x y – y x y ) položka ležící na vrcholu zásobníku je zduplikována na třetí místo

5. Operátory sloužící pro změnu pořadí položek na zásobníku

Vzhledem k tomu, že v programovacím jazyce Factor se proměnné využívají jen v minimální míře, se může velmi často stát, že hodnoty na zásobníku jsou uloženy v jiném pořadí, než je pro některé funkce žádoucí. Zatímco například při použití operátoru +, *, max či min na pořadí položek ve své podstatě vůbec nezáleží, je tomu u operátoru -, / či dokonce ^ přesně naopak. Pro „přerovnání“ zásobníku slouží následující operátory, které můžeme najít i ve většině implementací programovacího jazyka Forth.

Operace Zásobníkový efekt Popis
swap ( x y – y x ) prohození dvou nejvyšších položek na zásobníku
swapd ( x y z – y x z ) prohození druhé a třetí nejvyšší položky
rot ( x y z – y z x ) „rotace“ tří nejvyšších položek uložených na zásobníku
-rot ( x y z – z x y ) zpětná „rotace“ tří nejvyšších položek uložených na zásobníku
roll ( x y z t – y z t x ) podobné operaci rot, ale prováděné se čtyřmi položkami
-roll ( x y z t – t x y z ) podobné operaci -rot, ale prováděné se čtyřmi položkami

Operátory roll a -roll jsou poněkud výjimečné tím, že zasahují až na čtvrtou nejvyšší položku zásobníku a proto je někteří autoři nedoporučují používat, především z důvodu relativní složitosti pochopení jejich funkce v programu.

factor24

Inspektor v integrovaném vývojovém prostředí Factoru slouží pro výpis a navigaci mezi různými programovými objekty

6. Operátory určené pro manipulaci s úschovným zásobníkem

Už v programovacím jazyku Forth (/serialy/pro­gramovaci-jazyk-forth/) jsme se mohli setkat s dvojicí zásobníků. Prvním zásobníkem je zásobník operandů (operand stack), druhým zásobníkem pak zásobník návratových adres (return stack). Všechny operátory, které byly popsány v předchozích kapitolách, manipulovaly s obsahem zásobníku operandů. Stejně tak i matematické operace popsané dále pracují se zásobníkem operandů. To nám v naprosté většině případů vyhovuje.

Ovšem v některých případech může být vhodné si některou hodnotu ze zásobníku operandů „odložit“ a po nějakém čase zase vrátit na jeho vrchol. Právě k tomuto účelu bylo ve Forthu možné použít zásobník návratových adres, který kromě této funkcionality sloužil – jak jeho název napovídá – k ukládání návratových adres jednotlivých volaných slov (operandů). Z tohoto důvodu bylo absolutně nutné před ukončením daného slova obnovit obsah zásobníku návratových adres, protože jinak by interpret při návratu skočil na špatné místo v paměti. Tomuto postupu se někdy říká vyvažování zásobníku (stack ballancing).

Programovací jazyk Factor nám nedovolí přímý přístup k návratovým adresám, pokud tedy nepoužijeme funkce pro práci s VM (virtuálním strojem, i to je totiž možné, i když se u intepretovaného kódu adresy mohou měnit). Naproti tomu existuje velké množství algoritmů, které by se využitím dalšího zásobníku do značné zpřehlednily, protože by operátory mohly přímo přistupovat k níže položeným hodnotám na zásobníku. Proto je ve Factoru vytvořen i takzvaný úschovný zásobník (retain stack), který plní při manipulaci s hodnotami podobnou funkci jako Forthovský zásobník návratových adres. I tento zásobník je nutné vyvažovat, což je částečně hlídáno samotným interpreterem. Vzhledem k vhodně zvolenému názvu – retain stack vs return stack – jsou i slova pracující s tímto pomocným zásobníkem stejná, jako v původním Forthu:

Operace Zásobníkový efekt Popis
>r ( x – ) hodnota uložená na vrcholu zásobníku (operandů) je přenesena na úschovný zásobník
r> ( – x ) hodnota uložená na vrcholu úschovného zásobníku je přenesena na vrchol zásobníku operandů

Všimněte si, že žádné další operace není možné s úschovným zásobníkem přímo provádět, tj. není zde například příkaz podobný dup, swap či rot. Z tohoto důvodu je nutné se na úschovný zásobník dívat jako na skutečný zásobník, s jehož položkami se dá manipulovat pouze pomocí jejich vkládání (push) či naopak vyjímání (pop). V případě, že jste stejně jako já zvyklí spíše na „přiřazovací“ a ne „přesunovací“ operace, můžete si vytvořit dvě nová slova pro přesun hodnot z a na úschovný zásobník. Slova se ve Factoru vytváří naprosto stejným způsobem jako ve Forthu, tj. znak : značí začátek definice slova (přepnutí do režimu překladu) a znak ; značí příkaz return a současně také konec definice slova:

! definice dvou nových operátorů
: r< >r ;
: <r r> ; 

Nová slova si můžeme velmi snadno otestovat:

! test nově nadefinovaných operátorů

! uložení hodnoty 10 na zásobník operandů
10

! přesun této hodnoty na úschovný zásobník
! (zásobník operandů se vyprázdní)
r<

! tisk obsahu zásobníku operandů
.s
_

! přesun hodnoty z úschovného zásobníku
! na vrchol zásobníku operandů
<r

! tisk obsahu zásobníku operandů
.s
10 
factor25

Walker v integrovaném vývojovém prostředí Factoru využívá ve větší míře reflexe

7. Základní datové typy

Mezi základní datové typy, které mohou být přímo ukládány na zásobník operandů i na úschovný zásobník, patří samozřejmě numerické hodnoty, podobně jako v mnoha dalších programovacích jazycích. Kromě datových typů odpovídajících možnostem daného procesoru či matematického koprocesoru (fixnum, float) jsou ve Factoru dostupné i datové typy, které musí být interně zpracovávány složitějším, a tím pádem i pomalejším, způsobem (bignum, ratio, complex):

Název typu Význam
fixnum celé číslo s velikostí odpovídající šířce slova procesoru
bignum celé číslo s prakticky neomezeným rozsahem hodnot
ratio racionální čísla zapisovaná ve formě zlomku m/n
float obecně iracionální čísla interně reprezentovaná ve formě mantissa×2expo­nent
complex komplexní čísla

Již ze zápisu číselného literálu (konstanty) interpreter pozná, o jaký typ se jedná:

! rozlišení typu číselné hodnoty
42           ! jedná se o numerický typ fixnum
123456789000 ! jedná se o numerický typ bignum
1/3          ! jedná se o numerický typ ratio
1.3          ! jedná se o numerický typ float
C{ 1 2 }     ! komplexní číslo 

O objektech jsme si prozatím nic neříkali, ale už z předchozího zápisu je zřejmé, že komplexní čísla jsou představována zvláštním typem zabudovaného objektu. Zajímavý je také zápis racionálních čísel pomocí zlomku. To je umožněno mj. i díky tomu, že při použití postfixové notace se prakticky všechny ASCII znaky typu +, -, *, /, #, @ apod. mohou nacházet i uvnitř identifikátorů, zatímco v jazycích používajících infixovou notaci tomu tak v naprosté většině případů být nemůže. Racionální čísla jsou automaticky normalizována, tj. zlomek je do nejvyšší možné míry zjednodušen (oblíbená část středoškolské matematiky :-). Třídu, do které spadá hodnota uložená na vrcholu zásobníku je možné zjistit velmi jednoduše voláním operátoru class, který na zásobník vrací jméno příslušné třídy:

! rozlišení třídy, do které spadá číselná hodnota
42 class .
fixnum

123456789000 class .
bignum 
factor26

Listener v integrovaném vývojovém prostředí Factoru

8. Matematické operace

S numerickými hodnotami uloženými na zásobníku je možné provádět velké množství matematických operací. Ve Factoru se do velké míry používá vlastnost typická i pro další zásobníkové jazyky – matematická operace (funkce) může vracet více výsledků, které jsou v přesně definovaném pořadí uloženy na zásobník. Jedná se například o následující operace:

Operace (slovo) Zásobníkový efekt Význam
< ( x y – ? ) porovnání dvou numerických hodnot
<= ( x y – ? ) porovnání dvou numerických hodnot
> ( x y – ? ) porovnání dvou numerických hodnot
>= ( x y – ? ) porovnání dvou numerických hodnot
~ ( x y epsilon – ? ) porovnání, zda se reálná čísla liší o hodnotu vyšší než epsilon
fixnum? ( object – ? ) test, zda je objekt typu fixnum
bignum? ( object – ? ) test, zda je objekt typu bignum
even? ( n – ? ) test, zda je celé číslo sudé
odd? ( n – ? ) test, zda je celé číslo liché
power-of-2? ( n – ? ) test, zda je celé číslo mocninou dvou
zero? ( x – ? ) test na nulovost hodnoty
between? ( x y z – ? ) test, zda hodnota x leží v zadaném intervalu
+ ( x y – z ) součet
( x y – z ) rozdíl
* ( x y – z ) součin
/ ( x y – z ) podíl
/f ( x y – z ) podíl dvou reálných čísel
mod ( x y – z ) dělení modulo
/mod ( x y – z w ) podíl a zbytek po dělení
neg ( x – -x ) změna znaménka
recip ( x – y ) výpočet převrácené hodnoty
1+ ( x – y ) inkrementace (obdoba céčkového operátoru ++)
1– ( x – y ) dekrementace (obdoba céčkového operátoru –)
min ( x y – z ) výpočet minima dvou hodnot
max ( x y – z ) výpočet maxima dvou hodnot
sgn ( x – n ) vyjádření znaménka či nulovosti čísla
ceiling ( x – y ) zaokrouhlení čísla směrem nahoru
floor ( x – y ) zaokrouhlení čísla směrem dolů
truncate ( x – y ) odříznutí desetinné části
round ( x – y ) zaokrouhlení čísla na nejbližší celé číslo
>fixnum ( x – n ) převod objektu na číslo typu fixnum
>bignum ( x – n ) převod objektu na číslo typu bignum
>fraction ( a/b – a b ) převod racionálního čísla na čitatele a jmenovatele
numerator ( a/b – a ) získání hodnoty čitatele (celé číslo)
denominator ( a/b – b ) získání hodnoty jmenovatele (celé kladné nenulové číslo)
real ( z – x ) získání reálné hodnoty komplexního čísla
imaginary ( z – y ) získání imaginární hodnoty komplexního čísla
>rect ( z – x y ) převod komplexního čísla na reálnou a imaginární část
rect> ( x y – z ) vytvoření komplexního čísla ze dvou čísel reálných (složka 1 a i)
conjugate ( z – z* ) výpočet čísla komplexně sdruženého
gcd ( x y – a d ) výpočet největšího společného dělitele, tak aby platilo a*y=d mod x
log ( x – n) výpočet celočíselného dvojkového logaritmu
factor27

Na posledním listu integrovaného vývojového prostředí Factoru se nachází Listener

9. Obsah třetí části článku o programovacím jazyku Factor

Ve třetí části tohoto článku si ukážeme především práci s řetězci a kolekcemi (ve skutečnosti jsou i řetězce zpracovávány jako kolekce, což je v několika ohledech výhodné), citaci programů a jejich evaluaci, která je podobná postupům známým z programovacího jazyka Joy, náhradu podmínkových příkazů a smyček pomocí operátorů, práci s n-ticemi (tuples) a další pokročilejší metody používané při programování v jazyku Factor. Nezapomeneme ani na popis integrovaného vývojového prostředí.

Našli jste v článku chybu?

10. 2. 2008 4:44

Trm (neregistrovaný)
``Vzhledem k tomu, že jsem znal lidi co znali lidi co roota založili, čtu ho od jeho počátku''

Hmm, to je sice vsechno pekne, ale neznamenato, ze nejsi kus sulina. Tisnovsky be BUH a jeho clanky jsou to jedine, co na rootu za neco stoji. Krome teda curaku, jako ses ty.

7. 2. 2008 20:00

Aspa (neregistrovaný)
Ufff, clovece, sice jsem ten clanek necetl a asi ani cist nebudu (nedostatek sentimentu), ale clanka P. Tisnovskeho jsou zde na Rootu uz pekne dlouho top-notch stuff.

Ano, kvalita Rootu klesa, skoro se chce rict, ze raketove, nicmene radsi bych si precetl fundovany clanek na tema, ktere me alespon vzdalene zajima, nez 10 ostatnich blogu/clanku/news o tom jak je 'tr00 kvlt 0ss linuzzz' lepsi nez micr0$oft widle...

Vase kritika clanku je krajne stupidni a myslim, ze si to P. Tisnovsky ne…



Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Lupa.cz: Seznam mění vedení. Pavel Zima v čele končí

Seznam mění vedení. Pavel Zima v čele končí

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

Root.cz: 250 Mbit/s po telefonní lince, když máte štěstí

250 Mbit/s po telefonní lince, když máte štěstí

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

DigiZone.cz: Flix TV má set-top box s HEVC

Flix TV má set-top box s HEVC

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Podnikatel.cz: Babiš: E-shopy z EET možná vyjmeme

Babiš: E-shopy z EET možná vyjmeme

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Vitalia.cz: Manželka je bio, ale na sex moc není

Manželka je bio, ale na sex moc není