Blog | Okomentovaný ěľščř plugin

Okomentovaný ěľščř plugin

Jakub Vrána napsal daleko rychlejší implementaci pluginu ěľščř, který jsem vám dal minulý týden k dispozici. Proč jsem nepoužil daleko jednodušší řešení? A proč je zdroják takový, jaký je?

Prvotní motiv byl: něco se naučit.

Chtěl jsem psát co nejvíc funkcionálně a to ikdyž jsem věděl, že je možné napsat kód rychleji.

1) kouzlo funkcionálního programování

V čem jsou funkcionální jazyky kouzelné, je to, že se dají snadno rozšířit. Dnešní moderní hitovka jsou funkce map a filter, které považujeme za „základ funkcionálního programování“. To přitom ale vůbec není pravda.

Co je daleko běžnější postup, je konstrukce (v pseudojazyku):

hodnota = [1, 2, 3, 4]

nasobDvema([]) {
        nasobDvema(hodnota, [])
}

# odchyt, jen pokud je 1. parametr prazdne pole
nasobDvema([], accumulator) {
        return accumulator
}

# vytahne z listu 1. prvek
nasobDvema([first|rest]) {
        return nasobDvema([ first * 2 | nasobDvema(rest)])
}

nasobDvema(hodnota) # [2, 4, 6, 8]

Když si budu chtít do Erlangu doprogramovat filter, je to snadné:

% filtr prázdného seznamu je prázdný seznam
filter( _, [] ) -> [].

% filtr běžného seznamu je seznam
% thx za inspiraci u Ondry Klejcha
filter( Func, [H|T] ) ->
  if
    Func(H) == true -> [ H | filter( Pred, T ) ];
    true -> filter( Func, T )
  end.

A co jsem tedy sledoval ve zdrojáku?

# toto je gateway, podobne jako v prikladu z Erlangu
rewrite: (value) ->
        @rewrite-with-replaces value, @replaces!

# projdi vsechny prvky
rewrite-with-replaces: (value, replaces) ->
        key = @first-key-in replaces
        if key is null
                value
        else
                # vypocitej upravu pro 1. znak a vytvor pole bez 1. znaku
                @rewrite-with-replaces value-replaced, replaces-without-first

Tady vidíte to, že JavaScript neumí pattern matching (LiveScript umí takový falešný pattern matching, který by mi tu moc nepomohl). Kdyby uměl, vypadal by zdroják spíš takhle:

rewrite-with-replaces: (value, []) ->
                value

rewrite-with-replaces: (value, replaces) ->
        key = @first-key-in replaces
        # vypocitej upravu pro 1. znak a vytvor pole bez 1. znaku
        @rewrite-with-replaces value-replaced, replaces-without-first

Něco podobného jsem udělal nejen nad jednotlivými znaky stringu, ale i nad jednotlivými znaky.

Samozřejmě, šlo by to řešit i tím, že bych vzal hodnotu a napsal bych:

new-value = value.replace new RegExp("/puvodniZnak/", "g"), "novyZnak"

Ale to jsem neudělal právě proto, že jsem se chtěl neco naučit.

2) tail call optimalizace

Další specialitou, kterou nemají všechny procedurální jazyky, ale snad všechny funkcionální jazyky, to je tail call optimalizace. Ve zkratce: pokaždé, když zavoláte v běžném jazyce rekurzi, zapíše se do stacku. A jak budete zanořovat a zanořovat, dojde vám paměť (u PHP jsem obvykle končil někde u 50-500. úrovně zanoření, kdy vás už usekne runtime).

Pokud volání rekurze je naprosto poslední funkce, která je ve funkci v dané větvi volána, jedná se o tail call. Pokud používáte tail call a jazyk s tím počítá, nezanořuje se stack a vše běží v pořádku.

Takže vlastně argument, že mám 15 volání rekurze, je u funkcionálního jazyka s tail call naprosto jedno. Mezi 150 miliony iteracemi ve foreach a 150 miliony rekurzivního volání pomocí tail call, není žádný výrazný rozdíl (snad jen v tom, že volání funkce zahazuje neustále kontext lokálních proměnných, což, pevně věřím, se dá optimalizovat na pár assemblerových instrukcí).

3) 2 mutable proměnné

Pokud bych chtěl psát úplně čistě funkcionálně, musel bych se vyhnout mutable proměnným. Což jsem ve dvou případech porušil.

První je vytvoření kopie objektu bez jednoho atributu. Implementoval jsem to následovně:

replaces-without-first = replaces # zkopíruju objekt
delete replaces-without-first[key] # zbavím se prvku, který nechci

Kdybych chtěl toto napsat čistě funkcionálně, musel bych to implementovat jinak. Hlavně bych potřeboval funkci, která vytvoří kopii objektu s jedním změněným atributem. Což, pokud vím, JavaScript neumí a tím znemožňuje čistě funkcionální programování. Leda by si člověk tuto funkci napsal, smířil se, že ta je uvnitř "nečistá" a zbytek už psal dobře.

Pak už bych jen volal funkci, která by postupně rekurzí přidávala atributy do druhého objektu, dokud by neměl počet atributů přesně o 1 menší (to je ten, který nechceme).

Vypadalo by to asi následovně:

Mám funkci object-with-key-value a předstírám, že nevidím, jak to mění hodnotu objektu:

object-with-key-value(object, key, value) ->
        object[key] = value
        object

Pak mám funkci:

object-without-key(without-key, object) ->
        copy-from-to-without-key(object, {}, without-key)

copy-from-to-without-key(from-object, to-object, without-key)
        if length(to-object) + 1 < length(from-object)
                for key of from-object
                        if key isnt without-key
                                new-object = object-with-key-value(to-object, key, from-object[key])
                                copy-from-to-without-key(from-object, new-object, without-key)
        else
                to-object

Druhé porušení je hledání prvního klíče v objektu:

first-key-in: (replaces) ->
        first-key = null
        for key of replaces
                if replaces.has-own-property key
                        first-key = key
                        break
        first-key

Toto by šlo implementovat čistě funkcionálně:

first-key-in: (replaces) ->
        for key of replaces
                if replaces.has-own-property key
                        return key

A vlastně ani nevím, proč to tak ve zdrojáku nemám.

4) Zhodnocení

Proč se vlastně drbat s něčím takovým, když můžu všechno jednoduše napsat procedurálně? Je to taková moje kata. Postup, jak se naučit nový přístup, který mi třeba pomůže někdy vyřešit elegantněji problém, který bych dřív řešil otrocky.

A navíc, myslím, že v době vícejádrových procesorů čeká funkcionální programování renesance. Ale to nechme prorokům.

Programování

Předejte zkušenosti i dalším a sdílejte tento článek!



Jiří Knesl
Business & IT konzultant

Jiří Knesl poprvé začal programovat v roce 1993. Od té doby, díky skvělým učitelům a později zákazníkům, měl možnost neustále růst v oboru vývoje webových aplikací a informačních systémů. v roce 2002 se přidal zájem o ekonomii a v roce 2006 o organizaci práce. Vším tím se konstantně profesně zabývá jak ve svém podnikání, tak i u zákazníků. Za posledních 5 let vydal na tato témata přes 400 článků.

Prohlédněte si moje reference

Mám zkušenosti z rozsáhlých projektů pro korporace, velké podniky, střední i malé firmy, ale i pro startupy v cloudu. Zvyšoval jsem jejich know-how, pomáhal nastavovat jejich organizační strukturu, byl lektorem a mentorem v náročných situacích. Podívejte se, jak vidí můj přínos samotní klienti.

Sledujte mé postřehy na sociálních sítích