Obsah
1. Factor: revoluce v programování nebo propadák?
2. Základy funkcionálního programování ve Factoru
3. Práce s kolekcemi a sekvencemi
4. Příklad různých přístupů k programování: výpočet faktoriálu
5. Smysl programovacích jazyků, které nespadají do hlavního proudu
6. Literatura a odkazy na Internetu
1. Factor: revoluce v programování nebo propadák?
Programovací jazyky Joy a Factor, které popisuji v tomto seriálu, sice nepatří mezi příliš známou ani rozšířenou skupinu programovacích jazyků, ovšem jedná se o jazyky, které do programování přinesly poměrně zásadní novinku spočívající v použití paradigmatu založeného na kompozici funkcí, ukládání citovaných programů na zásobník (s možností další manipulace s nimi) a také na použití rekurzivních kombinátorů.
Už jenom díky těmto vlastnostem se jedná o plnohodnotné funkcionální jazyky, což představuje poměrně zásadní průlom v nazírání na všechny „zásobníkové“ jazyky – ty jsou odvozeny od Forthu, tj. jazyka imperativního (pro zajímavost: Forth byl jeden z prvních reálně použitelných programovacích jazyků, které podporovaly procedurální zápis algoritmů). V průběhu téměř čtyřiceti let od vzniku Forthu se sice programátoři snažili tento jazyk o funkcionální paradigma rozšířit, opravdu čistě a elegantně se to ale podařilo až v programovacím jazyku Joy, kterým byl inspirován i zde popisovaný Factor.
Ovšem ve Factoru je možné kromě funkcionálního paradigmatu používat i paradigma objektové. V současnosti se – nutno říci, že pro středně velké a velké projekty celkem oprávněně – toto paradigma používá nejčastěji, dokonce se mnoho objektových knihoven zcela zjevně inspirovalo funkcionálním programováním – viz například neměnné objekty používané v několika návrhových vzorech a doporučované i takovým odborníkem, jakým je Joshua Bloch.
V následujících kapitolách si nejdříve popíšeme funkcionální programování ve Factoru, a posléze si dovolím připsat krátké zamýšlení nad smyslem programovacích jazyků, které z různých důvodů nespadají do hlavního „vývojářského proudu“ a které mohou z pohledu manažerů vypadat jako bezvýznamnosti. Samozřejmě budu psát především o vážně míněných netradičních jazycích, i když i takové jazykové perly jako Unlambda, BrainF*ck nebo Whitespace přináší do vývojářského světa trošku potřebného humoru a osvěžení.
2. Základy funkcionálního programování ve Factoru
V článku o programovacím jazyce Joy (viz odkazy na konci textu) jsme si řekli, že vyčíslitelné (spočitatelné) funkce je možné získat z takzvaných počátečních funkcí, což je nulová funkce (zero function), funkce následníka (successor function) a projekce (projection), ze kterých jsou vytvářeny funkce složitější. Mezi základní způsoby tvorby složitějších funkcí patří kombinace funkcí, kompozice funkcí a primitivní rekurze. Pro parciálně rekurzivní funkce se zavádí ještě operace zvaná minimalizace.
V jazyce Joy i Factor se ve velké míře využívá především kompozice funkcí. Jedná se o binární operaci, ovšem vzhledem k tomu, že v obou těchto jazycích je použita postfixová notace, tak se zcela eliminuje nutnost zápisu operace kompozice funkcí přímo do zdrojových textů programů, protože již ze vzájemné pozice jmen jednotlivých funkcí je zřejmé, jaké je pořadí operací – je určeno přesně tím pořadím, jakým program čteme, tj. zleva doprava, neboli opačně, než je tomu u většiny funkcionálních programovacích jazyků založených na lambda kalkulu.
Pro začátek si zopakujme, že ve Factoru se nové funkce vytváří naprosto stejným způsobem jako ve Forthu, tj. začátek definované funkce je uvozen znakem : (dvojtečka) a konec znakem ; (středník), který je interně překládán jako návrat z funkce (return). V některé literatuře se tento způsob vytváření nových funkcí nazývá colon definition. Všechny funkce své parametry čtou ze zásobníku a výsledek nebo výsledky (může jich být i více) opět ukládají na zásobník. To mnohdy vede k velmi úspornému zápisu kódu:
! vytvoření nové funkce square, která vypočte druhou mocninu argumentu
: square dup * ;
! novou funkci si můžeme ihned otestovat
42 square .s
1764
! vytvoření nové funkce neg, která změní znaménko svého argumentu
: neg 0 swap - ;
! opět můžeme provést jednoduchý test
6502 neg .
-6502 Kromě toho je možné ve Factoru, podobně jako v dříve popsaném jazyku Joy, používat takzvané citované programy. Jedná se o libovolně dlouhou a samozřejmě také libovolně složitou sekvenci příkazů uloženou mezi hranaté závorky [ a ]. Jinými slovy to znamená, že program je zapsán na zásobník jako běžný seznam a posléze je tento program buď přímo spuštěn nebo použit v dalších operacích, například podmíněných výrazech, smyčkách či náhradě rekurze pomocí rekurzivních manipulátorů.
Nejjednodušší možností, jak s částí programu zapsanou v seznamu pracovat, je jeho spuštění. To lze provést pomocí operátoru call (zavolej (podprogram)), který svým použitím odpovídá příkazu eval známého z jiných programovacích jazyků. Ukažme si jednoduchý příklad:
! přímé spuštění sekvence příkazů
21 2 * .
42
! uložení citovaného programu na zásobník
[ 21 2 * . ]
! kontrola, zda je program skutečně na zásobníku uložen
.s
[ 21 2 * . ]
! zkusíme program spustit
call
42 Dalším příkladem je opakované spuštění určité části kódu. Ve své podstatě se nejedná o nic jiného, než o jednoduchý ekvivalent počítané programové smyčky nahrazené funkcí times, která na zásobníku očekává počet opakování, tj. celočíselnou hodnotu a dále citovaný program, který se bude n-krát opakovat:
10 [ "Nebudu se paní učitelce smát za zády do očí" print ] times
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
Nebudu se paní učitelce smát za zády do očí
3. Práce s kolekcemi a sekvencemi
Programovací jazyk Factor plně podporuje práci s kolekcemi. Kolekcí je v tomto kontextu myšlena sekvence (především pole, vektor, řetězec a citovaný program, popř. jakýkoli jiný objekt implementující dané rozhraní), asociativní pole (známé také pod označením hešovací mapa) nebo další složitější datová struktura, do které se ukládají hodnoty (z implementovaných kolekcí jmenujme dvojitě vázaný seznam, orientovaný graf atd.).
Zajímavé je, že další datové struktury je možné do jazyka poměrně jednoduchým způsobem přidat, což by ještě nebylo nijak zvláštní, ale lze pro ně vytvořit i speciální syntaxi, což už tak běžné není. Je to umožněno zejména díky tomu, že Factor má sám o sobě syntaxi tak jednoduchou, že si nemusí rezervovat prakticky žádné speciální znaky ani klíčová slova, která by měla speciální význam; tudíž je možné tyto znaky použít mimo jiné i pro vytváření kolekcí. Typickým příkladem mohou být pole, pro která jsou vytvořena slova/funkce pojmenovaná symboly { a }. Tyto symboly slouží, jak jste ostatně mohli uhodnout, ke konstrukci pole:
{ 1 2 3 10 20 } Podobné je to s vektory, pro něž je vytvořeno slovo V{, které taktéž nahrazuje konstruktor kolekce:
V{ 1 2 3 4 5 } Existuje pouze málo programovacích jazyků, které nabízí takovou volnost při vytváření vlastní syntaxe. Čestnou výjimkou je Lisp a z něho odvozené jazyky.
Ve Factoru se, podobně jako v dalších funkcionálních jazycích, velmi často používají funkce, které jako svůj argument přijímají jiné funkce. Typickým příkladem je funkce map, pomocí které je možné aplikovat libovolnou funkci zapsanou citovaným programem na seznam nebo pole (to je uloženo na druhém nejvyšším místě zásobníku):
! výpočet druhé mocniny pro všechny prvky seznamu
[ 1 2 3 4 ] [ dup * ] map .s
[ 1 4 9 16]
! definice nového slova/funkce square
: square dup * ;
! použití slova/funkce square na celé pole
{ 1 2 3 4 } [ square ] map .s
{ 1 4 9 16 }
! výpočet převrácené hodnoty pro zadaný seznam
: inv 1.0 swap / ;
[ 1 2 5 10 ] [ inv ] map .
[ 1.0 0.5 0.2 0.1 ] Dalším typicky funkcionálním obratem je použití funkce reduce, která postupně aplikuje nějakou binární operaci na sekvenci (které je funkci reduce předána v jednom parametru) a mezivýsledek. V první iteraci je místo mezivýsledku použita hodnota uložená na druhém místě zásobníku (tato hodnota se někdy nazývá identita):
! [ 1 2 3 4 5 ] - vstupní sekvence
! 100 - identita
! [ + ] - aplikovaná binární operace
[ 1 2 3 4 5 ] 100 [ + ] reduce .
115
4. Příklad různých přístupů k programování: výpočet faktoriálu
Výpočet faktoriálu patří mezi typické algoritmy, na nichž se dají ukázat různé přístupy k programování. Školní implementace bývají typicky založeny na „naivní“ rekurzi, v běžných programech se programátoři většinou spoléhají na klasickou programovou smyčku a ve funkcionálních jazycích lze s výhodou použít koncovou rekurzi (tail recursion). Dalo by se říci, že klasická „školní rekurze“ je tou nejhorší variantou, pojďme však dále. Ve Factoru lze použít výše uvedenou funkci reduce a zapsat faktoriál následujícím způsobem:
: factorial1 1 [ 1+ * ] reduce ; Při spuštění této funkce je ze zásobníku přečtena celočíselná hodnota, která je použita jako výchozí sekvence. Je zde využito faktu, že i jedno číslo se může chovat jako sekvence. Například číslo 3 se chová jako sekvence hodnot 0, 1 a 2. Právě této skvělé vlastnosti (která kupodivu chybí i v jinak skvělém Lispu) je využito při výpočtu faktoriálu. Funkce 1+ představuje prostou inkrementaci hodnoty, tj. náhradu literálu 1 a funkce +. Výsledek si ihned můžeme otestovat:
0 factorial1 .
1
-10 factorial1 .
1
2 factorial1 .
2
42 factorial1 .
1405006117752879898543142606244511569936384000000000 Ovšem to není jediná cesta, jak dojít ke kýženému výsledku. Pokud se budeme chtít vyhnout klasickým smyčkám a rekurzi, můžeme ještě využít dalšího slova, které nám Factor nabízí. Jedná se o slovo product, které očekává na zásobníku sekvenci a vrátí její produkt, tj. hodnotu vzniklou postupným vynásobením všech hodnot uložených v této sekvenci. Zbývá nám tedy sekvenci vytvořit na základě zadané hodnoty.
Samozřejmě není vhodné použít smyčku (to bychom vlastně vytloukali klín klínem), ale můžeme použít například funkci nazvanou zajímavě ale docela vhodně [1,b], která je uložena ve slovníku „math.ranges“. Jedná se o funkci, která po přečtení celého kladného čísla ze zásobníku uloží nazpět sekvenci od 1 až do velikosti tohoto čísla (jde o podobnou operaci, jakou nabízí třeba Haskell). Výsledný program pro výpočet faktoriálu tedy může být velmi jednoduchý:
! import knihovny math.ranges
USING: math.ranges ;
! vytvoření nové varianty funkce faktoriálu
: factorial2 [1,b] product ;
! test
0 factorial2 .
0 (!!!)
-10 factorial2 .
0 (!!!)
2 factorial2 .
2
42 factorial2 .
1405006117752879898543142606244511569936384000000000 Pro zcela korektní výpočet by bylo vhodné místo [1,b] volat spíše upravenou funkci, která pro hodnoty menší než 1 vrací sekvenci s jedinou hodnotou 1 a ne nula. Úprava je možná buď s využitím operátoru if nebo min.
5. Smysl programovacích jazyků, které nespadají do hlavního proudu
Na Rootu bylo publikováno už několik článků o programovacích jazycích, které zcela jistě není možné zařadit do hlavního vývojářského proudu. Kromě specialit vhodných spíše pro pobavení (BrainF*uck, Whitespace) než pro seriózní práci nebo výzkum byly popsány i jazyky, které ve své době naznačily další směr vývoje celé této oblasti IT. Jde například o Forth (absolutně minimalistický a přitom praktický jazyk, který programátorům odhaluje i své interní struktury), Perl a Tcl (tyto jazyky zapříčinily vzestup skriptovacích jazyků), Lisp či APL (velmi expresivní jazyk se zajímavou :-) sadou operátorů). Každý z těchto jazyků přinesl nějaké nosné nápady či užitečné techniky, které byly později okopírovány do jazyků dalších a mnohdy i úspěšnějších.
Strom vývoje programovacích jazyků (poloručně vytvořeno z PostScriptového zdroje; původní autor je uveden vlevo dole)
Tak jako v jiných oblastech, i v programovacích jazycích může na první pohled bláznivý či „nepraktický“ nápad vést ke vzniku užitečné techniky, která je následně všemi okopírována. Jako příklad lze uvést například regulární výrazy zabudované přímo do jazyka. V dobách kralování Céčka, Fortranu a Ady bylo prakticky nemyslitelné do jazyka přidávat tak abstraktní konstrukce jako regulární výrazy – pro ně byly vyhrazeny speciální utility a jednoúčelové nástroje typu awk či grep. Ovšem poté, co se ukázala jejich užitečnost v Perlu se prakticky nesetkáme s dynamickým programovacím jazykem, který by regulární výrazy neobsahoval a algolská větev jazyků (mezi něž řadím například i Javu) je alespoň obsahuje ve svých standardních knihovnách.
Obdobné je to s některými funkcionálními prvky, které se postupně z Lispu či Smalltalku přenáší přes moderní dynamické jazyky (Perl, Python, Ruby, Tcl) do mainstreamových jazyků. Příkladem je velmi užitečná funkcionální konstrukce typu for-each, která po tom, co se objevila v Javě 1.5 (Tiger), prakticky nahradila (snad kromě numerických algoritmů) klasickou procedurální smyčku for. Na funkce vyššího řádu typu map, apply či reduce zase můžeme narazit v jazycích typu Python, nebo i v Logu či právě ve Factoru.
Myslím si, že je jen otázkou času, kdy se některé konstrukce a programátorské obraty zavedené například v Haskellu (mimochodem: další nepatřičně opomíjený jazyk), Selfu nebo Factoru objeví v dnes nejčastěji používaných jazycích. Zda to uškodí čistotě těchto jazyků je otázkou, ale výše zmíněný příklad poměrně čistě implantované konstrukce typu for-each do Javy je příslibem, že se vhodné řešení dá vymyslet.
Stejné je to i se sekvencemi popsanými ve třetí a čtvrté kapitole tohoto článku, které mohou při správném použití mnoho algoritmů zjednodušit a nahradit mnohdy do sebe zamotané programové smyčky čistým funkcionální o objektovým kódem. I to je jeden z důvodů, proč další programovací jazyky vznikají a proč jsou o těch zajímavějších publikovány články.
6. Literatura a odkazy na Internetu
- John Backus:
Can programming by liberated from the von Neumann style?: A functional style and its algebra of programs,
Source Communications of the ACM archive, 21(8):613–641, August 1978. - H.B.Curry and R.Feys:
Combinatory Logic,
North-Holland Publishing Company, 1958. - Paul Hudak et al.:
Report on the programming language Haskell: a non-strict, purely functional language version 1.2.,
SIGPLAN Not., 27(5):1–164, 1992. ISSN 0362–1340. - Charles Moore:
Forth: a new way to program a mini-computer
Astronomy and Astrophysics Supplement, (15), 1974. - Robert Morris and Lorinda Cherry:
Dc – an interactive desk calculator
Technical report, AT&T Bell Laboratories - Jaanus P.:
Typing tools for typeless stack languages
In Proceedings from the 23rd EuroForth Conference, pages 40–46, 2006. - Manfred von Thun.:
Joy: Forth's functional cousin
In Proceedings from the 17th EuroForth Conference, 2001. - Factor programming language:
http://factorcode.org/ - Factor documentation:
http://factorcode.org/responder/help/ - Factor FAQ:
http://factorcode.org/faq.fhtml - Factor: a practical stack language (blogpost):
http://factor-language.blogspot.com/ - Factor-talk --:
https://lists.sourceforge.net/lists/listinfo/factor-talk - Factor-talk – archive:
http://sourceforge.net/mailarchive/forum.php?forum_name=factor-talk - Wikipedia: Factor (programming language):
http://en.wikipedia.org/wiki/Factor_(programming_language) - Wikipedia: Slava Pestov:
http://en.wikipedia.org/wiki/Slava_Pestov - Pastebin (collaborative development over IRC):
http://paste.factorcode.org/ - planet-factor:
http://planet.factorcode.org/ - Slava Pestov's retro HTML 1.0 home page:
http://factorcode.org/slava/ - concatenative (IRC kanál o podobných programovacích jazycích):
http://www.ircbrowse.com/cdates.html?channel=concatenative - Vocabulary index (dnes již docela rozsáhlé):
http://factorcode.org/responder/help/show-help?topic=vocab-index - Factor Magic:
http://fun-factor.blogspot.com/2007/03/factor-magic.html - Factor Magic, Part 2:
http://fun-factor.blogspot.com/2007/04/factor-magic-part-2.html - http://www.latrobe.edu.au/philosophy/phimvt/joy.html – Joy Programming Language, stránka s rozcestníkem informací o programovacím jazyku Joy
- http://www.latrobe.edu.au/philosophy/phimvt/joy/j01tut.html – Tutorial on Joy
- http://www.latrobe.edu.au/philosophy/phimvt/joy/j06prg.html – Programming in Joy
- http://www.latrobe.edu.au/philosophy/phimvt/joy/synops.html – Synopsis of the language Joy
- http://www.latrobe.edu.au/philosophy/phimvt/joy/faq.html – Frequently Asked Questions about Joy, obsahuje i částečné porovnání s dalšími programovacími jazyky založenými na zásobníkovém kódu
- http://www.madore.org/~david/programs/unlambda/ – Programovací jazyk Unlambda
