Hlavní navigace

Factor: revoluce v programování nebo propadák?

Pavel Tišnovský

V závěrečné části našeho krátkého seriálu o programovacím jazyce Factor si popíšeme způsob psaní funkcionálních programů. Na závěr se pokusím uvést několik důvodů, proč se má smysl zabývat programovacími jazyky, které se nachází mimo „hlavní proud“ (mainstream) programovacích jazyků.

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 JoyFactor 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.

factor4

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

  1. 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.
  2. H.B.Curry and R.Feys:
    Combinatory Logic,
    North-Holland Publishing Company, 1958.
  3. 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.
  4. Charles Moore:
    Forth: a new way to program a mini-computer
    Astronomy and Astrophysics Supplement, (15), 1974.
  5. Robert Morris and Lorinda Cherry:
    Dc – an interactive desk calculator
    Technical report, AT&T Bell Laboratories
  6. Jaanus P.:
    Typing tools for typeless stack languages
    In Proceedings from the 23rd EuroForth Conference, pages 40–46, 2006.
  7. Manfred von Thun.:
    Joy: Forth's functional cousin
    In Proceedings from the 17th EuroForth Conference, 2001.
  8. Factor programming language:
    http://factor­code.org/
  9. Factor documentation:
    http://factor­code.org/respon­der/help/
  10. Factor FAQ:
    http://factor­code.org/faq.fhtml
  11. Factor: a practical stack language (blogpost):
    http://factor-language.blog­spot.com/
  12. Factor-talk --:
    https://lists­.sourceforge.net/lis­ts/listinfo/fac­tor-talk
  13. Factor-talk – archive:
    http://source­forge.net/mai­larchive/forum­.php?forum_na­me=factor-talk
  14. Wikipedia: Factor (programming language):
    http://en.wiki­pedia.org/wiki/Fac­tor_(programmin­g_language)
  15. Wikipedia: Slava Pestov:
    http://en.wiki­pedia.org/wiki/Sla­va_Pestov
  16. Pastebin (collaborative development over IRC):
    http://paste.fac­torcode.org/
  17. planet-factor:
    http://planet­.factorcode.or­g/
  18. Slava Pestov's retro HTML 1.0 home page:
    http://factor­code.org/slava/
  19. concatenative (IRC kanál o podobných programovacích jazycích):
    http://www.ir­cbrowse.com/cda­tes.html?chan­nel=concatena­tive
  20. Vocabulary index (dnes již docela rozsáhlé):
    http://factor­code.org/respon­der/help/show-help?topic=vocab-index
  21. Factor Magic:
    http://fun-factor.blogspot­.com/2007/03/fac­tor-magic.html
  22. Factor Magic, Part 2:
    http://fun-factor.blogspot­.com/2007/04/fac­tor-magic-part-2.html
  23. http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y.html – Joy Programming Language, stránka s rozcestníkem informací o programovacím jazyku Joy
  24. http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y/j01tut.html – Tutorial on Joy
  25. http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y/j06prg.html – Programming in Joy
  26. http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y/synops.html – Synopsis of the language Joy
  27. http://www.la­trobe.edu.au/phi­losophy/phimvt/jo­y/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
  28. http://www.ma­dore.org/~david/pro­grams/unlambda/ – Programovací jazyk Unlambda
Našli jste v článku chybu?

19. 2. 2008 17:13

Aha, ja jsem pouzival VESA verzi. Jinak se mrkni na http://objectmix.com/forth/168025-colorforth-iso-now-available-2.html vypada to, ze se to nekomu podarilo nabootovat z CD-ROM nebo i z USBcka. Ovsem opravdova frajerinka by byl ColorForth primo v BIOSu. Tech par kilo se tam najde, treba misto obrazku zobrazovaneho pri POSTu.

19. 2. 2008 16:19

Vsak co bys chtel vic? - zakladni slova se v hexa daji zapamatovat, pokud ovsem neni pouzito komprimace CF-stylu :-) Meli jsme ucitele, ktery znal opkody Z80 (teda nevim jestli vsechny) a tech je o dost vic nez nejaky ten swap, dup, drop, over, call, ret a lit :-)

Mel jsem dojem, ze CF beha na vsem, kde se da spustit VESA framebuffer v rozliseni 1024x768. To je snad podporovano vsude (minimalne spousta dister Linuxu uz startuje i konzoli v "grafice") a pokud by to notebook nahodou nez…

DigiZone.cz: Co chtějí operátoři při přechodu na DVB-T2?

Co chtějí operátoři při přechodu na DVB-T2?

DigiZone.cz: ČT láká na jarní programové tipy

ČT láká na jarní programové tipy

Lupa.cz: Proč Stream netočí jen Kancelář Blaník?

Proč Stream netočí jen Kancelář Blaník?

Podnikatel.cz: 3, 2, 1..EET startuje. Na co nezapomenout?

3, 2, 1..EET startuje. Na co nezapomenout?

Měšec.cz: Jak levně odeslat balík přímo z domu?

Jak levně odeslat balík přímo z domu?

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

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

Mondelez stahuje rizikovou čokoládu Milka

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

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

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

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

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

Jak vymáhat výživné zadarmo?

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?