Hlavní navigace

Matematika v příkazové řádce IV - utilita dc (1)

14. 2. 2006
Doba čtení: 11 minut

Sdílet

Ve čtvrtém pokračování seriálu věnovaného programovým nástrojům určeným pro matematické výpočty prováděné zejména v příkazovém řádku si popíšeme základy práce s utilitou dc, která slouží – podobně jako minule a předminule popisovaná utilita bc – k aritmetickým výpočtům a jejich skriptování.

Obsah

1. Úvodní informace o utilitě dc
2. Přednosti a zápory utility dc
3. Zásobník a postfixový zápis matematických výrazů
4. Operace se zásobníkem v dc
5. Aritmetické operátory, matematické výrazy
6. Řízení přesnosti výpočtů a konverze mezi číselnými soustavami
7. Obsah dalšího pokračování tohoto seriálu

1. Úvodní informace o utilitě dc

Nástroj dc (desk calculator) slouží k provádění aritmetických operací s prakticky neomezeným rozsahem a přesností použitých numerických hodnot, proto se také někdy nazývá arbitrary precision calculator. Na rozdíl od všech dále popsaných utilit se dc vyznačuje především tím, že se pro zápis všech aritmetických operací používá takzvaná obrácená polská notace (reverse polish notation, také postfixová notace), tj. nejdříve jsou uvedeny operandy a teprve po nich operátor. Předností tohoto způsobu zápisu matematických operací je absence závorek a zjednodušení vlastního interpreteru, který by při použití „obyčejné“ (infixové) notace nejprve musel zadané výrazy upravovat do notace postfixové (ať již přímou formou, přes derivační stromy nebo rekurzivním sestupem). Postfixová notace je také konzistentní, infixově se totiž ve skutečnosti zapisují pouze některé operace (sčítání, odečítání atd.), funkce se většinou zapisují prefixově, tj. před operand, některé též postfixově (například faktoriál).

Další zvláštností utility dc jsou takzvané registry. Na ty lze pohlížet jako na proměnné, jejich počet je však omezen počtem písmen abecedy – jména registrů jsou totiž pouze jednoznaková, podobně jako u některých primitivnějších interpreterů jazyka Basic. V registrech však nemusí být uložena pouze jedna hodnota, každý registr se chová jako samostatný zásobník, do nějž je možné hodnoty postupně ukládat (operace push) a zase z něj vybírat (operace pop). V makrech (což jsou ve skutečnosti textové substituce) jsou tyto operace velmi často používány pro naprogramování komplexnějších ak­cí.

2. Přednosti a zápory utility dc

dc je po všech stránkách pozoruhodná aplikace. Syntaxe použitých příkazů a operací je totiž tak zahuštěná, že se jí vyrovnají snad pouze konfigurační soubory programu sendmail nebo některé Perlovské skripty :-) (a samozřejmě programy dodávané do soutěže The International Obfuscated C Code Contest). Na druhou stranu se však ukazuje, že spojení zásobníkově orientovaného jazyka (které s sebou přináší i zmíněnou obrácenou polskou notaci) a propracovaného systému maker umožňuje vytvářet i složité programové konstrukce a dokonce i celé komplexní nadstavbové aplikace. Další významnou předností je, že dc je zahrnuta do standardu POSIX, je tedy možné počítat s tím, že každá unixová distribuce bude dc obsahovat, bez ohledu na použitou platformu.

3. Zásobník a postfixový zápis matematických výrazů

Při práci s utilitou dc se nevyhneme častým manipulacím se zásobníky, ať už pomocí explicitně zadaných příkazů (duplikace hodnot v zásobníku) či implicitními operacemi (například při provádění matematických výpočtů). Zásobníky jsou v dc použity zejména z toho důvodu, aby se zjednodušilo zadávání a provádění aritmetických operací – to však má za následek nutnost použití takzvané převrácené polské notace (Reverse Polish Notation – RPN) při zápisu matematických výrazů. V dalším textu si popíšeme jak základy práce se zásobníky, tak i způsob práce s RPN. Pro začátek budu citovat text s úvodem do RPN, kterou používá například firma Hewlett-Packard v některých svých kalkulátorech:

If you're a frequent calculator user, you owe it to yourself to investigate the advantages of RPN. RPN stands for Reverse Polish Notation. Reverse Polish Notation was developed in 1920 by Jan Lukasiewicz as a way to write a mathematical expression without using parentheses and brackets. Hewlett-Packard Co., realizing that Lukasiewicz's met­hod was superior to standard algebraic expressions when using calculators and computers, adapted RPN for its first hand-held scientific calculator, the HP35, in 1972.
Hewlett-Packard Development Company The RPN Method: An Overview and History

Softwarový vývojář, který programuje či alespoň zná některý z dnes nejčastěji používaných procedurálních nebo objektově orientovaných jazyků (jmenujme například C, C++, Java, Perl, Ruby, Python – částečně funkcionální, Visual Basic a Tcl), je většinou značně překvapen (možná i znechucen), pokud poprvé uvidí program napsaný ve skriptovacím jazyce používaném utilitou dc. Toto překvapení, které se však u znalců programovacího jazyka Forth většinou nekoná :-), je způsobeno zejména výše zmiňovanou postfixovou notací zápisu.

Už na základní škole se však každý člověk učí takzvanou infixovou notaci zápisu, ve které se nejčastěji používané matematické operátory zapisují mezi své operandy. Vzhledem k různé prioritě operátorů (například operátor násobení má definitoricky větší prioritu než sčítání) je však nutné v infixové notaci velmi často používat závorky. Rozdíl mezi následujícími dvěma výrazy uvedenými v infixové notaci je zřejmý:

a+b*c
(a+b)*c 

Při použití postfixové notace však nejsou závorky ve výrazech NIKDY zapotřebí, protože se priorita operací vyjadřuje přímo posloupností operátorů. Výše uvedené výrazy lze tedy do postfixové notace přepsat následovně:

a b c * +   nebo též   b c * a +
a b + c *   nebo též   c a b + * 

Všimněte si, že u výše uvedených výrazů napsaných na levé straně se oproti infixové notaci nemění pořadí operátorů. Toho se často využívá při algoritmickém převodu mezi infixovou a postfixovou notací. Tento převod provádí vlastně každý překladač či interpreter programovacího jazyka včetně minule popisované utility bc, a to buď přímo (mimochodem většinou opět s využitím zásobníku), nebo takzvaným rekurzivním sestupem podle gramatických pravidel daného jazyka.

Jaké jsou však výhody postfixového zápisu výrazů oproti zápisu infixovému? Mezi základní přednost patří už zmíněná absence závorek, pomocí nichž se v infixové notaci mění priority operací. Priorita je totiž v postfixové notaci velmi intuitivně určena přímo pozicí operátoru či funkce ve výrazu. Toho využívaly i kalkulačky HP, které žádné klávesy se závorkami neobsahovaly. Původní klávesnice byly vybaveny pouze tlačítky s číslicemi, čtyřmi klávesami pro základní matematické operace (ty se zadávaly za operandy) a klávesou [Enter], která prováděla uložení právě zobrazené hodnoty na displeji do zásobníku operandů (konkrétně na jeho vrchol – TOP či SP).

Mezi druhou výhodu postfixové notace patří – pro mnohé možná poněkud překvapivě – konzistence zápisu. Ve skutečnosti se totiž v běžně používané infixové notaci zapisují pouze některé základní matematické operace, jako je sčítání, násobení nebo dělení. Další operace se zapisují pomocí funkcí v prefixové notaci (například sinus, odmocnina, logaritmus, minimum) a některé dokonce v notaci postfixové (pravděpodobně nejznámější „postfixovou funkcí“ je faktoriál, který se zapisuje znakem vykřičníku umístěného za operand).

Pomocí postfixové notace je možné zapisovat všechny operace i funkce, dokonce ani nezáleží na počtu operandů (stírá se tím rozdíl mezi unárními, binárními, ternárními apod. operacemi). Ve skutečnosti není v postfixové notaci prakticky žádný rozdíl mezi operacemi a funkcemi, takže pro ně není nutné zavádět nějaká zvláštní syntaktická pravidla. Mezi běžně používané funkce, které mají dva operandy, patří logaritmus o libovolném základu, exponenciální funkce a například také (spíše programátorská, avšak praktická) funkce atan2.

Důsledkem výše uvedených skutečností je fakt, že znaky běžně používané pro aritmetické operátory je možné použít i pro jiné účely, podobně jako například v jazyce Lisp nebo Scheme (což jsou mimochodem jazyky používající prefixovou notaci, tou se zde však nebudeme zabývat).

Zásobník (anglicky stack), jenž je použit při zpracování aritmetických výrazů zapsaných v postfixové notaci, je z hlediska programování a programovacích technik dynamická datová struktura, pomocí které lze, podobně jako u implementačně příbuzného jednosměrně či obousměrně vázaného seznamu, ukládat a zpětně získávat data. Zásobník se od seznamu a dalších dynamických datových struktur jako je fronta, strom či graf liší především množinou základních operací, určenou pro práci s touto datovou strukturou.

Datová struktura zásobník nebo jeho hardwarová implementace se někdy označuje akronymem LIFO, který pochází z anglického výrazu Last In – First Out. Tento výraz docela přesně vystihuje základní vlastnost zásobníku: data, která byla do zásobníku vložena nejpozději, lze nejdříve přečíst. Naopak to platí samozřejmě také: nejdříve vložená data do zásobníku lze přečíst až po vyjmutí všech později vložených dat. Čistě implementovaný zásobník totiž neumožňuje přímo manipulovat s daty uloženými pod jeho vrcholem.

Zásobník si můžeme znázornit i graficky spolu se dvěma základními operacemi: vložení prvku (operace push) a vyjmutí prvku spolu s navrácením jeho hodnoty (operace pop):

math_4_1
Obrázek 1: Dynamická datová struktura zásobník společně s dvojicí základních operací

Princip práce s daty u zásobníku je tedy přesně opačný než u další lineární dynamické datové struktury – fronty (anglicky queue) – ze které je možné data číst pouze v tom pořadí, v jakém byla zapsána. Fronta se proto označuje akronymem FIFO, tj. First In – First Out.

Také frontu je možné znázornit graficky. Všimněte si rozdílných míst, ve kterých do fronty data vstupují pomocí operace push a vystupují pomocí operace pop.

math_4_2
Obrázek 2: Dynamická datová struktura fronta společně s dvojicí základních operací

4. Operace se zásobníkem v dc

Pravděpodobně nejjednodušší a současně nejčastěji prováděnou operací se zásobníkem, která je v utilitě dc implementována, je uložení číselné hodnoty na zásobník. To se provede tím způsobem, že se zapíše celé číslo (není přitom podporován exponenciální způsob zápisu) a následně se stiskne klávesa [Enter] nebo jiná klávesa generující bílý znak ([Space], někdy také [Tab]). Je nutné pamatovat na to, že zásobník je datová struktura typu LIFO (Last In, First Out), tj. naposledy zapsaná hodnota je přečtena jako první. Velikost zásobníku, tj.  maximální povolený počet ukládaných hodnot, je sice omezen, jedná se však o poměrně velký počet položek (216 apod.), takže se jím většinou nemusíme zabývat – samozřejmě pokud se zapsaný skript například nezacyklí. Příklad jednoduchého skriptu, který na zásobník uloží tři čísla:

10
20
30
q
ukončení aplikace dc 

S číselnými hodnotami uloženými na zásobníku je možné provádět různé operace (jinak by ostatně nemělo cenu je na zásobník ukládat :-). Často je zapotřebí získat (tj. vytisknout) hodnotu, která je uložena na vrcholu zásobníku. To zajistí příkaz p (od slova print). Tento příkaz přečte hodnotu uloženou na vrcholu zásobníku a vytiskne ji na standardní výstup, přičemž je za vytištěné číslo vložen znak pro konec řádku. Samotná hodnota je přitom na zásobníku ponechána, jeho obsah tedy není změněn. Následuje příklad použití příkazu p (vstup uživatele je vytisknutý tučně, výstup programu je zobrazen normálním neproporcionálním fontem):

10
20
30
p
30
p
30
p
30 

Všimněte si, že je vždy vytištěna pouze hodnota 30, tj. naposledy vložené číslo. Pro výpis obsahu celého zásobníku (například pro účely ladění) je možné použít příkaz f (od slova fše :-)). Tento příkaz pouze tiskne uložené hodnoty, aniž by obsah zásobníku změnil:

10
20
30
f
30
20
10 

Ve výše uvedeném příkladu opět stojí za povšimnutí, že se hodnoty vytisknou v opačném pořadí. Je tomu tak proto, že se tiskne od vrcholu zásobníku (TOS či SP) směrem k jeho začátku (SB). Vzhledem k tomu, že dc při zápisu výrazů nerozlišuje mezi bílým znakem a znakem pro konec řádku, je možné předchozí příklad napsat i následujícím způsobem:

10 20 30 f
30
20
10 

Příkaz lze dokonce spojit s předchozí číslicí:

10 20 30f
30
20
10 

Mezi další operace, které lze se zásobníkem provádět, patří:

Operace – významy
Operace Význam
c vymazání veškerého obsahu zásobníku
d poslední vložená položka v zásobníku je zduplikována
r výměna hodnot mezi nejvyšší a druhou nejvyšší hodnotou na zásobníku

Znalci Forthu nebo PostScriptu jistě uhodli, že operace d získala své jméno z příkazu/slova dup a operace r ze slova rot.

5. Aritmetické operátory, matematické výrazy

Aritmetické operace se ve skriptovacím jazyku dc zapisují právě v postfixové (RPN) notaci. Ve výpisu níže jsou uvedeny příklady zápisu některých základních i složitějších aritmetických výrazů a jejich kombinací spolu s příkazem pro tisk obsahu zásobníku:

10 20 + p c
30
10 20 * pc
200
10 20 -pc
-10
10 20 / pc
0 (celočíselné dělení - není nastaven radix)
10 20 % pc
10 (dělení modulo)
10 20 + 30 * pc
900
5 4 3 2 1 * * * * p
120
5 4 3 2 1****p
120 

Význam výše uvedených operací je následující: samotný zápis čísla znamená, že se toto číslo uloží do zásobníku. Zápis operátoru způsobí, že se operandy vyberou ze zásobníku, provede se s nimi zadaná operace a výsledek se uloží zpět na zásobník. Vzhledem k tomu, že všechny výše zapsané aritmetické operace jsou binární, vyberou se ze zásobníku vždy dvě hodnoty a zpět se zapíše pouze hodnota jediná, tj. počet položek na zásobníku se po provedené operaci o jednu sníží.

Vzhledem k jednoduchosti parseru, který je v utilitě dc použit, je nutné explicitně rozlišit binární operaci - (odečítání) od zápisu záporného čísla. Z toho důvodu se záporná čísla zapisují pomocí znaku _ (podtržení).

Kromě výše uvedené pětice základních operací jsou v dc podporovány i operace další, zejména dělení se zbytkem (to v infixové notaci zapsat nelze), výpočet libovolné mocniny a druhé odmocniny. Následuje příklad použití těchto operací:

10 3 ~ f
1
3
celočíselný podíl je roven třem, zbytek je 1

2 10 ^ f
1024
výpočet desáté mocniny hodnoty 2

256 v f
16
výpočet druhé odmocniny hodnoty 256 

6. Řízení přesnosti výpočtů a konverze mezi číselnými soustavami

Při pohledu na výsledky výše uvedených aritmetických výrazů jste si pravděpodobně všimli, že všechny vypočtené hodnoty byly celočíselné. To však neznamená, že dc pracuje pouze s celými čísly, jde pouze o počáteční nastavení. Přesnost výpočtů (resp. výsledků operací) se řídí takzvaným radixem, který udává maximální počet číslic uvedených za desetinnou tečkou. Radix se nastavuje pomocí příkazu k, který očekává na zásobníku jedno číslo udávající radix. Pokud na zásobníku žádné číslo uvedeno není, je to při vyvolání tohoto příkazu považováno za chybu. Vše si můžeme ozřejmit na následujícím příkladu, který počítá druhou odmocninu z deseti při použití různého radixu:

10 v p
3
1 k 10 v p
3.1
2 k 10 v p
3.16
10 k 10 v p
3.1622776601
30 k 10 v p
3.162277660168379331998893544432
c k
dc: stack empty 

Číselná soustava vstupujících číselných hodnot se mění příkazem i, který na vrcholu zásobníku očekává číslo udávající základ soustavy. Podobně se číselná soustava tisknutých číselných hodnot mění příkazem o. V následujícím příkladu je proveden převod některých čísel ze soustavy desítkové do dalších soustav (jak je ze zápisů patrné, s menším počtem „úhozů“ snad ani nejdou konverze zapsat):

UX DAy - tip 2

1 2 127 128 255 256 f
256
255
128
127
2
1
2 o f
100000000
11111111
10000000
1111111
10
1
8 o f
400
377
200
177
2
1
16 o f
100
FF
80
7F
2
1
2of
100000000
11111111
10000000
1111111
10
1
8of
400
377
200
177
2
1
16of
100
FF
80
7F
2
1 

7. Obsah dalšího pokračování tohoto seriálu

V dalším pokračování tohoto seriálu dokončíme popis utility dc. Budeme se zabývat použitím proměnných (které jsou zde vytvořeny jako zásobníky), a také systémem zpracování řetězců, které se v dc používají zejména pro programování maker.

Byl pro vás článek přínosný?

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.