Coconut aneb funkcionální nadstavba nad Pythonem (2.část)

Obsah

1. Coconut aneb funkcionální nadstavba nad Pythonem (2.část)

2. Zřetězení většího množství generátorů

3. Operátor ?? (operátor koalescence)

4. Operátor ??=

5. Elvis operator

6. Elvis operator a přístup k prvkům v datové struktuře

7. Elvis operator a přístup k atributům objektů

8. Zápis některých operátorů s využitím Unicode znaků

9. Příklad použití Unicode znaků

10. Pattern matching: základní klauzule

11. Pattern matching: složitější příklady použití

12. Rekurze a koncová rekurze

13. Klasická rekurze v Pythonu a její omezení

14. Optimalizace koncové rekurze v Coconutu

15. Repositář s demonstračními příklady

16. Odkazy na Internetu

1. Coconut aneb funkcionální nadstavba nad Pythonem (2.část)

V úvodní části článku o programovacím jazyku Coconut jsme si vysvětlili, jakým způsobem se vlastně zdrojové kódy napsané v Coconutu překládají (transkompilují) do Pythonu. Taktéž jsme se seznámili s některými zajímavými rysy tohoto jazyka, zejména s neměnitelnými (immutable) datovými typy, funkcemi vyššího řádu určenými pro zpracování sekvencí, zkráceným zápisem lambda výrazů, infixovým zápisem při volání funkcí a/nebo při deklaraci funkcí a v neposlední řadě taktéž o kompozici funkcí a vytvoření „kolony“ funkcí, které si mezi sebou předávají vypočtené mezivýsledky.

Dnes si popíšeme další zajímavé vlastnosti tohoto jazyka. Především se jedná o nové operátory ??, ??= a ?. (Elvis operator), které znají například vývojáři používající jazyk C#. Dále si řekneme, jak lze (alternativně) zapisovat vybrané operátory pomocí Unicode znaků (což nepatrně připomíná APL), popíšeme si konstrukce používané při pattern matchingu a taktéž se budeme zabývat problematikou optimalizace koncové rekurze, kterou jazyk Coconut taktéž podporuje, na rozdíl od standardního Pythonu (resp. přesněji řečeno standardního CPythonu).

2. Zřetězení většího množství generátorů

První užitečnou vlastností programovacího jazyka Coconut, s níž se v dnešním článku seznámíme, je možnost zřetězení většího množství generátorů, takže se vlastně (alespoň z pohledu programátora-uživatele) vytvoří generátor nový, který nejprve vrátí všechny prvky vytvořené prvním generátorem a následně prvky vytvořené generátorem druhým. Pro tento účel se používá nový operátor zapisovaný jako „čtyřtečka“. Podívejme se na jednoduchý příklad, v němž jsou nejprve definovány dva generátory, z nichž každý postupně vrátí maximálně čtyři prvky. Po spojení generátorů operátorem :: dostaneme posloupnost osmi prvků:

def generator1():
    values = ["a1", "b1", "c1", "d1"]
    for value in values:
        yield value
 
def generator2():
    values = ["a2", "b2", "c2", "d2"]
    for value in values:
        yield value
 
for v in generator1()::generator2():
    print(v)

Příklad výstupu vypsaného po spuštění:

a1
b1
c1
d1
a2
b2
c2
d2

Pro zajímavost se podívejme, jak vlastně vypadá kód vygenerovaný transpřekladačem Coconutu:

def generator1():
    values = ["a1", "b1", "c1", "d1"]
    for value in values:
        yield value
 
def generator2():
    values = ["a2", "b2", "c2", "d2"]
    for value in values:
        yield value
 
for v in _coconut.itertools.chain.from_iterable((f() for f in (lambda: generator1(), lambda: generator2()))):
    print(v)

Můžeme si vyzkoušet i nepatrně složitější příklad s konfigurovatelným generátorem, kterému se při jeho konstrukci předává suffix vracených hodnot. Ten stejný generátor zřetězíme celkem třikrát:

def generator3(suffix):
    values = ["a", "b", "c", "d", "e"]
    for value in values:
        yield "{v}{s}".format(v=value, s=suffix)
 
for v in generator3("1")::generator3("2")::generator3("3"):
    print(v)

Příklad výstupu:

a1
b1
c1
d1
e1
a2
b2
c2
d2
e2
a3
b3
c3
d3
e3

Opět se podívejme, jaký kód se vytvořil transpřekladačem:

def generator3(suffix):
    values = ["a", "b", "c", "d", "e"]
    for value in values:
        yield "{v}{s}".format(v=value, s=suffix)
 
for v in _coconut.itertools.chain.from_iterable((f() for f in (lambda: generator3("1"), lambda: generator3("2"), lambda: generator3("3")))):
    print(v)

Použít samozřejmě můžeme i funkci range(), například pro vygenerování série hodnot připomínajících digitalizovaný trojúhelníkový signál:

for i in range(0, 10)::range(10, 0, -1):
    print(i)

S výstupem:

0
1
2
3
4
5
6
7
8
9
10
9
8
7
6
5
4
3
2
1

3. Operátor ?? (operátor koalescence)

V některých programovacích jazycích, například v C#, PHP 7 či Swiftu, se setkáme s takzvaným operátorem koalescence (neboli operátorem nulového sjednocení). Jedná se o binární operátor, tj. o operátor, na jehož levé straně je umístěn první operand a na pravé straně operand druhý. Pokud má operand na levé straně hodnotu odlišnou od None, vrátí se jeho hodnota, aniž by se zpracovával (vyhodnocoval) operand pravý. Pokud však levý operand obsahuje None (nemá hodnotu), vrátí se vyhodnocený pravý operand. Samotný operátor koalescence se v mnoha jazycích zapisuje dvěma znaky ?? (výjimkou je Perl používající //), což je zvyklost, která zůstala v Coconutu zachována.

Podívejme se na jednoduché (a nutno říci, že poněkud umělé) příklady:

import os
 
v1 = None
v2 = "Some"
 
print(v1 ?? v2)
 
v3 = "Some"
v4 = "Something else"
 
print(v3 ?? v4)
 
v5 = None
v6 = None
 
print(v5 ?? v6)
 
print(os.getenv('EDITOR') ?? "notepad")
print(os.getenv('XXEDITOR') ?? "notepad")

Příklad výstupu:

Some
Some
None
vim
notepad

Transpřeklad do Pythonu je v tomto případě přímočarý – použije se konstrukce if-else zapsaná ve výrazu:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# __coconut_hash__ = 0x109f876f
 
# Compiled with Coconut version 1.3.0 [Dead Parrot]
 
# Coconut Header: -------------------------------------------------------------
 
# Compiled Coconut: -----------------------------------------------------------
 
import os
 
v1 = None
v2 = "Some"
 
print(v2 if v1 is None else v1)
 
v3 = "Some"
v4 = "Something else"
 
print(v4 if v3 is None else v3)
 
v5 = None
v6 = None
 
print(v6 if v5 is None else v5)
 
print((lambda _coconut_none_coalesce_item: "notepad" if _coconut_none_coalesce_item is None else _coconut_none_coalesce_item)(os.getenv('EDITOR')))
print((lambda _coconut_none_coalesce_item: "notepad" if _coconut_none_coalesce_item is None else _coconut_none_coalesce_item)(os.getenv('XXEDITOR')))

4. Operátor ??=

V jazyce Coconut nalezneme ještě další velmi podobný operátor zapisovaný trojicí znaků ??=. Opět se jedná o binární operátor s dvojicí operandů, jehož význam je následující:

• Pokud levý operand obsahuje None, přiřaď do něj hodnotu operandu pravého; tato hodnota je výsledkem celého výrazu
• V opačném případě je hodnota celého výrazu rovna levému operandu (aby bylo možné používat složitější výrazy)

Podívejme se na velmi jednoduchý příklad se slovníkem. Budeme měnit hodnoty uložené pod různými klíči, ovšem díky použití operátoru ??= namísto pouhého přiřazení operátorem = se nezmění ty hodnoty, které jsou rozdílné od None:

slovnik = {
    "prvni": 1,
    "druhy": 2,
    "treti": 3,
    "posledni": None
}
 
print(slovnik)
 
slovnik["prvni"] ??= 1000
 
print(slovnik)
 
slovnik["posledni"] ??= 1000
 
print(slovnik)
 
slovnik["neexistujici"] ??= 10
 
print(slovnik)

Nejprve se podívejme na způsob transpřekladu z Coconutu do Pythonu, z něhož je zřejmý přesný význam operátoru ??=:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# __coconut_hash__ = 0xbe97918d
 
# Compiled with Coconut version 1.3.0 [Dead Parrot]
 
# Coconut Header: -------------------------------------------------------------
 
 
# Compiled Coconut: -----------------------------------------------------------
 
slovnik = {"prvni": 1, "druhy": 2, "treti": 3, "posledni": None}
 
print(slovnik)
 
slovnik["prvni"] = 1000 if slovnik["prvni"] is None else slovnik["prvni"]
 
print(slovnik)
 
slovnik["posledni"] = 1000 if slovnik["posledni"] is None else slovnik["posledni"]
 
print(slovnik)
 
slovnik["neexistujici"] = 10 if slovnik["neexistujici"] is None else slovnik["neexistujici"]
 
print(slovnik)

Z výše uvedeného kódu je možné vydedukovat, že poslední přiřazení skončí s chybou, protože Python (což je velmi dobře!) rozlišuje mezi hodnotou None uloženou pod nějakým klíčem a mezi neexistující dvojicí klíč:hodnota:

{u'druhy': 2, u'posledni': None, u'prvni': 1, u'treti': 3}
{u'druhy': 2, u'posledni': None, u'prvni': 1, u'treti': 3}
{u'druhy': 2, u'posledni': 1000, u'prvni': 1, u'treti': 3}
Traceback (most recent call last):
  File "10_??=_operator.py", line 650, in <module>
    slovnik["neexistujici"] = 10 if slovnik["neexistujici"] is None else slovnik["neexistujici"]
KeyError: u'neexistujici'

5. Elvis operator

V některých programovacích jazycích se můžeme setkat s neoficiálním termínem „Elvis operator“ (podívejte se na fotky Elvise Presleyho a zjistíte, proč je použit právě tento název). Termín Elvis operator má hned dva významy – buď se může jednat o zkrácení ternárního operátoru ?: na operátor binární (bez druhé větve) nebo se může jednat o takzvaný „safe navigation operator“, který se většinou zapisuje dvojicí znaků ?.. V jazyku Coconut najdeme právě „safe navigation operator“, což je binární operátor, který funguje podobně jako stávající operátor . (tečka), ovšem pravá strana (metoda, atribut) se zpracuje pouze tehdy, pokud je objekt na levé straně tohoto operátoru rozdílný od None. Tyto operátory lze samozřejmě v případě potřeby „zřetězit“, tj. lze například přistupovat k atributům atributů, a to bez nebezpečí, že by došlo k vyvolání výjimky.

6. Elvis operator a přístup k prvkům v datové struktuře

Podívejme se na jednoduchý příklad, v němž chceme vypsat hodnotu posledního dosaženého skóre ze slovníku, který představuje stav hry:

game1 = {
    "player" : {
        "name": "Kvido",
        "nick": "kvido"
    },
    "results": {
        "score": {
            "last": 1000,
            "top": 2000
        },
        "lives": 0
    }
}

Následující funkce sice bude fungovat, ale jen ve chvíli, kdy má slovník očekávanou strukturu:

def print_last_score_variant_A(game):
    score = game.get("results").get("score").get("last")
    print("Score: {s}".format(s=score))
 
print("\nVariant A")
print_last_score_variant_A(game1)

Pro následující (částečnou) strukturu však dojde k výjimce:

game2 = {
    "player" : {
        "name": "Kvido",
        "nick": "kvido"
    }
}

Jedno z možných pythonovských řešení může vypadat tak, že metoda get vrátí namísto None prázdný slovník, což je sice krátký zápis, ale poněkud nepřehledný (původní význam algoritmu se trošku ztrácí):

def print_last_score_variant_B(game):
    score = game.get("results", {}).get("score", {}).get("last")
    print("Score: {s}".format(s=score))
 
print("\nVariant B")
print_last_score_variant_B(game1)
print_last_score_variant_B(game2)

Alternativně můžeme použít Elvis operator, který je kratší i přehlednější:

def print_last_score_variant_C(game):
    score = game.get("results")?.get("score")?.get("last")
    print("Score: {s}".format(s=score))
 
print("\nVariant C")
print_last_score_variant_C(game1)
print_last_score_variant_C(game2)

Pro zajímavost se podívejme, jak se vlastně Elvis operator transpřeložil do Pythonu. Není to příliš čitelný kód, ale je poměrně přímočarý:

def print_last_score_variant_C(game):
    score = (lambda x: None if x is None else (lambda x: None if x is None else x.get("last"))(x.get("score")))(game.get("results"))
    print("Score: {s}".format(s=score))

7. Elvis operator a přístup k atributům objektů

Stejně užitečné může být použití Elvis operátoru pro přístup k atributům objektů a atributům atributů (atributů…). Předchozí příklad můžeme přepsat takovým způsobem, aby se namísto běžného slovníku používaly objekty (schválně jsem strukturu zjednodušil):

class Player:
    def __init__(self, name, nick):
        self.name = name
        self.nick = nick
 
class Score:
    def __init__(self,last, top):
        self.last = last
        self.top =top
 
class Game:
    def __init__(self,player, score, lives):
        self.player = player
        self.score = score
        self.lives = lives

Funkce, která po předání objektu typu Game vypíše hodnotu posledního skóre, můžeme napsat velmi jednoduše bez toho, že by hrozilo vyhození výjimky:

def print_last_score_variant_D(game):
    score = game?.score?.last
    print("Score: {s}".format(s=score))
 

Očekávané chování si můžeme jednoduše otestovat:

game1_obj = Game(Player("Kvido", "kvido"),
                 Score(1000, 2000),
                 0)
 
game2_obj = Game(Player("Kvido", "kvido"),
                 None, 0)
 
print("\nVariant D")
print_last_score_variant_D(game1_obj)
print_last_score_variant_D(game2_obj)

S výsledkem:

Variant D
Score: 1000
Score: None

Opět se podívejme na způsob transpřekladu do Pythonu:

def print_last_score_variant_D(game):
    score = (lambda x: None if x is None else (lambda x: None if x is None else x.last)(x.score))(game)
    print("Score: {s}".format(s=score))

8. Zápis některých operátorů s využitím Unicode znaků

Jazyk Coconut se sice nesnaží napodobit můj oblíbený jazyk APL [1] [2], ovšem umožňuje (jako i některé další jazyky ze třetího tisíciletí :-) alternativní zápis některých operandů s využitím Unicode znaků. Ostatně podívejte se na následující tabulku:

Poznámka: tyto znaky nemusíte pracně zapisovat přes pravý Alt, protože například textový editor Vim umožňuje zápis necelých dvou tisíc Unicode znaků pomocí „digraphs“ (http://vimdoc.sourceforge­.net/htmldoc/digraph.html), které původně vznikly emulací psacího stroje (tisk dvou znaků přes sebe). Postačuje napsat příkaz :dig s výpisem dostupných znaků a paznaků.

9. Příklad použití Unicode znaků

Podívejme se nyní na příklady použití Unicode znaků v příkladech. Nutno říci, že (subjektivně) se zápis v některých případech zjednodušil, minimálně pro čtení, ovšem samotný zápis operátorů je komplikovanější. Ostatně posuďte sami:

result = 60⋅7÷10
print(result)
 
if result ≥ 40 and result ≤ 50:
    print("very close")
 
print(1 « 10)
print(1 ⊕ 255)
 
-42 ↦ abs ↦ print
 
"B" ↦ ord ↦ abs ↦ hex ↦ print
 
range(11) ↦ sum ↦ print
 
range(11) ↦ reversed ↦ sum ↦ print
 
"B" ↦ hex ∘ abs ∘ ord ↦ print
 
range(11) ↦ sum ∘ reversed ↦ print

Transpřeklad takto zapsaných operátorů je velmi přímočarý:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# __coconut_hash__ = 0x3d5464d
 
# Compiled with Coconut version 1.3.0 [Dead Parrot]
 
# Coconut Header: -------------------------------------------------------------
 
 
# Compiled Coconut: -----------------------------------------------------------
 
result = 60 * 7 / 10
print(result)
 
if result >= 40 and result <= 50:
    print("very close")
 
print(1 << 10)
print(1 ^ 255)
 
(print)((abs)(-42))
 
(print)((hex)((abs)((ord)("B"))))
 
(print)((sum)(range(11)))
 
(print)((sum)((reversed)(range(11))))
 
(print)((_coconut_forward_compose(ord, abs, hex))("B"))
 
(print)((_coconut_forward_compose(reversed, sum))(range(11)))

10. Pattern matching: základní klauzule

Jazyk Coconut podporuje i pattern matching, jenž je ve funkcionálních jazycích poměrně běžný. Pattern matching je realizován jazykovou konstrukcí používající nová klíčová slova case a match. V nejjednodušším případě dokážeme pomocí těchto slov nahradit poměrně špatně čitelnou konstrukci if-elif-elif…-else:

def factorial_variant_A(n):
    case n:
        match 0:
            return 1
        match 1:
            return 1
        match x:
            return x * factorial_variant_A(x-1)
    else:
        raise TypeError("expecting integer >= 0")

V tomto případě se bude interpret snažit najít ten vzor (pattern), který nejlépe a jednoznačně odpovídá vstupu, tj. hodnotě proměnné n. Postupně se testují vzorky 0, 1 a jakákoli jiná hodnota.

Povšimněte si toho, že se na třetím řádku match x objevuje x, což je proměnná platná jen v rámci dané větve a to (samozřejmě) pouze v tom případě, že se tato větev bude provádět.

Ve skutečnosti se však mohou v části match použít i další klauzule, zejména klauzule s podmínkou. Předchozí příklad nepracuje korektně pro záporná čísla, takže doplníme příslušnou podmínku:

def factorial_variant_B(n):
    case n:
        match 0:
            return 1
        match 1:
            return 1
        match x if x > 1:
            return x * factorial_variant_B(x-1)
    else:
        raise TypeError("expecting integer >= 0")

Zde klademe na třetí vzorek další podmínku, takže mu nebude odpovídat jakákoli hodnota proměnné n, ale pouze hodnota větší než 1.

Ani tato úprava však nezajistí zcela korektní chování. Ostatně si sami vyzkoušejte, co se stane při volání s hodnotou 1.5. Přidáme tedy další klauzuli na kontrolu typu s využitím operátoru is:

def factorial_variant_C(n):
    case n:
        match 0:
            return 1
        match 1:
            return 1
        match x is int if x > 1:
            return x * factorial_variant_C(x-1)
    else:
        raise TypeError("expecting integer >= 0")

11. Pattern matching: složitější příklady použití

Ukažme si některé poněkud složitější příklady použití pattern matchingu. Například funkci, která rozhodne o tom, jak velký seznam je jí předán:

def type(x):
    case x:
        match [a, b]:
            return "list, 2 items"
        match [a]:
            return "list, 1 item"
        match []:
            return "empty list"

Otestování vzájemného vztahu dvou hodnot ve dvojici (seznamu, n-tici):

def pair(p):
    case p:
        match [x,x]:
            return "same values!"
        match [x,y] if x>y:
            return "1st value is greater"
        match [x,y]:
            return "2nd value is greater"
    else:
        return "other"

Pokud se další funkci předá řetězec začínající na „My name is “, vezme se z něj další text a přiřadí do proměnné name:

def say_hello(s):
    case s:
        match "My name is " + name:
            return "Hi " + name

Specifikovat je možné začátek i konec řetěze (ovšem ne regulárním výrazem):

def get_name(s):
    case s:
        match name + "@root.cz":
            return name
 
def say_hello2(s):
    case s:
        match "My name is " + name + ".":
            return "Hi " + name

12. Rekurze a koncová rekurze

Programovací jazyk Coconut podporuje i optimalizaci koncové rekurze, což je technologie známá pod označením TCO neboli Tail Call Optimization. Nejdříve si však popíšeme, jak je rekurze řešená v samotném Pythonu (konkrétně v CPythonu) a jaká jsou její omezení.

V naprosté většině algoritmů se objevují bloky kódu, které se mají iterativně opakovat. Při programování s využitím funkcionálního paradigmatu se iterace vyjadřuje formou rekurze. Ta je samozřejmě v jazyku Python podporována (mezi jediné známější a v praxi používané jazyky, které rekurzi nepodporovaly, patřil původní FORTRAN a BASIC; psáno naschvál verzálkami). V některých případech je teoreticky možné jeden typ rekurze (při níž se parametry a návratové adresy musí ukládat na zásobník) nazvaný koncová rekurze optimalizovat, což zjednodušeně řečeno znamená, že se namísto skutečného rekurzivního volání funkce interně provede obyčejný skok (koncový skok či koncové volání) bez nutnosti alokace místa na zásobníku pro parametry volané funkce a návratové adresy.

Optimalizovaná koncová rekurze představuje při správném použití velmi silnou programovací techniku, protože umožňuje zapisovat mnoho algoritmů v mnohdy elegantní rekurzivní formě (naproti tomu autor Pythonu doporučuje používat explicitní zápis smyčky či generátorovou notaci seznamů), ovšem skutečné zpracování takto zapsaných algoritmů je stejně efektivní jako provádění programové smyčky (každou koncovou rekurzi lze nahradit smyčkou a naopak). Ovšem jen ve chvíli, kdy překladač či interpret daného programovacího jazyka dokáže koncovou rekurzi optimalizovat, což například není případ Pythonu (i když se objevilo několik návrhů na úpravu interpretu i několik rozšiřujících modulů).

13. Klasická rekurze v Pythonu a její omezení

Typickým „školním“ příkladem ukazujícím rozdíl mezi normální (plnou, skutečnou) rekurzí a koncovou rekurzí je výpočet faktoriálu. Ten můžeme zapsat mnoha způsoby, například (jak je to v matematice obvyklé), rekurzivně (zde bez kontrol, zda je zadáno kladné celé číslo!):

def factorial(n):
    if n < 2:
        return 1
    else:
        return n*factorial(n-1)

Chování si můžeme jednoduše vyzkoušet:

for n in range(0, 11):
    print("{n}! = {f}".format(n=n, f=factorial(n)))

S očekávaným výsledkem:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

Z teoretického hlediska není na výše uvedené funkci nic nekorektního, ovšem při jejím praktickém používání brzy narazíme na limit způsobený omezenou velikostí zásobníku:

print(factorial(998))
print(factorial(999))
print(factorial(1000))

Podle verze Pythonu (2.x, 3.x) program vypočte faktoriál 998, Python 2.x vypočítá i faktoriál 999 (Python 3.x již zde zhavaruje), ovšem posléze dojde k překročení limitu zásobníku:

998
4027900501272209945382406745976015873066815457564711036474473577877262386372662
8687892313161858799279327326187206926532395562249549029885775908291258252711811
5540044131204964883707335062250983503282788739735011132006982444941985587005283
3780245208118682621495874739612984175986444702539017517287412178507405765322677
0021339872268114421977718630056298045480415170513378035696863643383049931961081
8197341194914502752560687555393768328059805942027406941465687273867068997087966
2635720033962406439251567153263633401414988030191879355452210924407527782568461
6693410323568411034647789039917938738764933248351085268065836314778365182198635
1375529220618900164975188281042287183543472177292257232652561904125692525097177
9993325186354470006164529999840307397153182191697073237996473757976873670132582
0336412948289108999137681930729225220552462634970526186400345385358987062075859
6211518646408335184218571196396412300835983314926628732700876798309217005024417
5957099044497069307963377988617539419021259649364125010072841471142609356331961
0734142386307123138516605594991443269593961122799016933824802793984359762890352
5815803809004448863145157344706452445088044626373001304259830129153477630812429
6401059379747616677850452039875082597760602858260912617450492754193936806136753
6626423271530543088921638461106913566243239104372599880588166305491309198163384
2006354699525518784828195856033032645477338126512662942408363494651203239333321
5021142528114117131488433705948011457775750356303128859897798638883207592248821
2714154436625150397491010072165067381030357707464015411283339304727602579981122
4571534249672518380758145683914398263952929391318702517417558325636082722982882
3725948165824868267286146331997262112730727751313252222401001409528425724908018
2299422406997161353460348787499685249862358438310601453383065002241105366850816
5547838962087111297947300444414551980512439088964301520461155436870989509667681
8051499779930444441384285820651427873564555286811143926809508154182080723935326
1612233943443703442428784211931605888112988747423999233655676433796853803686194
9918847009763612475872782742568849805927378373244946190707168428807837146267156
2431852137243645467011005577145204623350840821764311733469293303940714760718135
9875958881895431239423433132770022445501587177547610037161503194094509878889482
8812648426365776746774528000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000
 
999
  File "recursive_factorial.py", line 5, in factorial
    return n*factorial(n-1)
  File "recursive_factorial.py", line 5, in factorial
    return n*factorial(n-1)
  File "recursive_factorial.py", line 5, in factorial
    return n*factorial(n-1)
  File "recursive_factorial.py", line 2, in factorial
    if n < 2:
RuntimeError: maximum recursion depth exceeded in comparison

Kdo uhodne, proč Python 2.x dokáže vypočítat i faktoriál 999, zatímco u Pythonu 3.x dojde k překročení limitu?

Mimochodem, maximální hloubku rekurze zjistíte velmi snadno:

import sys
 
print(sys.getrecursionlimit())

Výše uvedený rekurzivní výpočet lze relativně malou úpravou převést na výpočet který by teoreticky mohl vést na koncové volání:

def factorial(n, acc=1):
    if n < 2:
        return acc
    else:
        return factorial(n-1, acc*n)

Proč tom tak je? Představte si, že n a acc budou lokální proměnné a namísto rekurzivního volání funkce factorial pouze modifikujeme hodnoty těchto proměnných a provedeme skok na začátek funkce. Vzhledem k tomu, že si nemusíme pamatovat mezivýsledky (jako je tomu u původního výpočtu), není nutné jejich uložení na zásobník a kód se tedy transformuje do staré dobré programové smyčky.

Chování si opět můžeme snadno otestovat:

for n in range(0, 11):
    print("{n}! = {f}".format(n=n, f=factorial(n)))
 
print(factorial(999))
print(factorial(1000))

S výsledky:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
40238...
...
...
  File "tail_call_factorial.py", line 5, in factorial
    return factorial(n-1, acc*n)
  File "tail_call_factorial.py", line 5, in factorial
    return factorial(n-1, acc*n)
  File "tail_call_factorial.py", line 5, in factorial
    return factorial(n-1, acc*n)
  File "tail_call_factorial.py", line 5, in factorial
    return factorial(n-1, acc*n)
RuntimeError: maximum recursion depth exceeded

Ani v tomto případě nám tedy interpret Pythonu nepomohl a neprovedl TCO!

14. Optimalizace koncové rekurze v Coconutu

Zkusme si napsat výpočet faktoriálu s koncovou rekurzí v Coconutu. Je to snadné, navíc je program korektněji ochráněn před špatnými vstupy:

def factorial_tco(n, acc=1):
    case n:
        match 0:
            return acc
        match 1:
            return acc
        match _ is int if n > 1:
            return factorial_tco(n-1, acc*n)
    else:
        raise TypeError("expecting integer >= 0")

Po transpřekladu do Pythonu se můžeme přesvědčit o tom, že výpočet faktoriálu 1000 a dokonce i 10000 již proběhne korektně, protože se provedla TCO:

for n in range(11):
    print("{n}!={f}".format(n=n, f=factorial_tco(n)))
 
print(factorial_tco(1000))
print(factorial_tco(10000))

S výsledky:

0!=1
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
402387260077093773543702433923
...
...
...
mnoho nul na konci...

Opět se podívejme na způsob transpřekladu do Pythonu:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# __coconut_hash__ = 0x8f8983fe
 
# Compiled with Coconut version 1.3.0 [Dead Parrot]
 
# Coconut Header: -------------------------------------------------------------
 
 
# Compiled Coconut: -----------------------------------------------------------
 
@_coconut_tco
def factorial_tco(n, acc=1):
    def _coconut_mock_func(n, acc=1): return n, acc
    while True:
        _coconut_match_to = n
        _coconut_match_check = False
        if _coconut_match_to == 0:
            _coconut_match_check = True
        if _coconut_match_check:
            return acc
        if not _coconut_match_check:
            if _coconut_match_to == 1:
                _coconut_match_check = True
            if _coconut_match_check:
                return acc
        if not _coconut_match_check:
            if _coconut.isinstance(_coconut_match_to, int):
                _coconut_match_check = True
            if _coconut_match_check and not (n > 1):
                _coconut_match_check = False
            if _coconut_match_check:
                if factorial_tco is _coconut_recursive_func_0:
                    n, acc = _coconut_mock_func(n - 1, acc * n)
                    continue
                else:
                    return _coconut_tail_call(factorial_tco, n - 1, acc * n)
        if not _coconut_match_check:
            raise TypeError("expecting integer >= 0")
 
        return None
_coconut_recursive_func_0 = factorial_tco
for n in range(11):
    print("{n}!={f}".format(n=n, f=factorial_tco(n)))
 
print(factorial_tco(1000))
print(factorial_tco(10000))

15. Repositář s demonstračními příklady

Zdrojové kódy všech dnes popsaných demonstračních příkladů naleznete pod následujícími odkazy:

Poznámka: ke každému zdrojovému kódu napsanému v jazyku Coconut je přiložen i vygenerovaný (transkompilovaný) kód v Pythonu, ovšem bez zbytečného boilerplate.

16. Odkazy na Internetu

1. Null coalescing operator
   https://en.wikipedia.org/wi­ki/Null_coalescing_operator
2. Operátor koalescence
   https://cs.wikipedia.org/wi­ki/Oper%C3%A1tor_koalescen­ce
3. Elvis operator
   https://en.wikipedia.org/wi­ki/Elvis_operator
4. Safe navigation operator
   https://en.wikipedia.org/wi­ki/Safe_navigation_operator
5. Setting stacksize in a python script
   https://stackoverflow.com/qu­estions/5061582/setting-stacksize-in-a-python-script
6. What is the maximum recursion depth in Python, and how to increase it?
   https://stackoverflow.com/qu­estions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it?rq=1
7. Does Python optimize tail recursion?
   https://stackoverflow.com/qu­estions/13591970/does-python-optimize-tail-recursion
8. Programovací jazyk APL: programování bez smyček
   https://www.root.cz/clanky/pro­gramovaci-jazyk-apl-programovani-bez-smycek/
9. Programovací jazyk APL – dokončení
   https://www.root.cz/clanky/pro­gramovaci-jazyk-apl-dokonceni/
10. Tail call
    https://en.wikipedia.org/wi­ki/Tail_call
11. Tail Call Optimization for Python
    https://github.com/baruchel/tco
12. Tail Recursion Elimination
    http://neopythonic.blogspot­.cz/2009/04/tail-recursion-elimination.html
13. Origins of Python's „Functional“ Features
    http://python-history.blogspot.cz/2009/04/origins-of-pythons-functional-features.html
14. Tail recursion decorator revisited
    http://fiber-space.de/wordpress/2009/04/20/tail-recursion-decorator-revisited/
15. Koncová rekurze
    https://cs.wikipedia.org/wi­ki/Koncov%C3%A1_rekurze
16. Recursion (computer science)
    https://en.wikipedia.org/wi­ki/Recursion_%28computer_sci­ence%29
17. Coconut: Simple, elegant, Pythonic functional programming
    http://coconut-lang.org/
18. coconut 1.1.0 (Python package index)
    https://pypi.python.org/py­pi/coconut/1.1.0
19. Coconut Tutorial
    http://coconut.readthedoc­s.io/en/master/HELP.html
20. Coconut FAQ
    http://coconut.readthedoc­s.io/en/master/FAQ.html
21. Coconut Documentation
    http://coconut.readthedoc­s.io/en/master/DOCS.html
22. Coconut na Redditu
    https://www.reddit.com/r/Pyt­hon/comments/4owzu7/coconut_fun­ctional_programming_in_pyt­hon/
23. Repositář na GitHubu
    https://github.com/evhub/coconut
24. patterns
    https://github.com/Suor/patterns
25. Source-to-source compiler
    https://en.wikipedia.org/wiki/Source-to-source_compiler
26. The Lua VM, on the Web
    https://kripken.github.io/lu­a.vm.js/lua.vm.js.html
27. Lua.vm.js REPL
    https://kripken.github.io/lu­a.vm.js/repl.html
28. lua2js
    https://www.npmjs.com/package/lua2js
29. Wisp na GitHubu
    https://github.com/Gozala/wisp
30. Wisp playground
    http://www.jeditoolkit.com/try-wisp/
31. REPL v prohlížeči
    http://www.jeditoolkit.com/in­teractivate-wisp/
32. Minification (programming)
    https://en.wikipedia.org/wi­ki/Minification_(programmin­g)
33. JavaScript is Assembly Language for the Web: Sematic Markup is Dead! Clean vs. Machine-coded HTML
    http://www.hanselman.com/blog/Ja­vaScriptIsAssemblyLanguage­ForTheWebSematicMarkupIsDe­adCleanVsMachinecodedHTML­.aspx
34. JavaScript is Web Assembly Language and that's OK.
    http://www.hanselman.com/blog/Ja­vaScriptIsWebAssemblyLangu­ageAndThatsOK.aspx
35. Dart
    https://www.dartlang.org/
36. CoffeeScript
    http://coffeescript.org/
37. TypeScript
    http://www.typescriptlang.org/
38. JavaScript: The Web Assembly Language?
    http://www.informit.com/ar­ticles/article.aspx?p=1856657
39. asm.js
    http://asmjs.org/
40. List of languages that compile to JS
    https://github.com/jashke­nas/coffeescript/wiki/List-of-languages-that-compile-to-JS
41. Permutation
    https://en.wikipedia.org/wi­ki/Permutation
42. Pattern matching
    https://en.wikipedia.org/wi­ki/Pattern_matching
43. Pattern matching v Rustu
    https://www.root.cz/clanky/rust-funkce-lambda-vyrazy-a-rozhodovaci-konstrukce-match/#k13
44. SNOBOL
    https://en.wikipedia.org/wiki/SNOBOL
45. Podpůrný plugin pro Vim
    https://github.com/manicma­niac/coconut.vim
46. Příkaz (programování)
    https://cs.wikipedia.org/wi­ki/P%C5%99%C3%ADkaz_%28pro­gramov%C3%A1n%C3%AD%29
47. Threading Macros Guide
    https://clojure.org/guides/thre­ading_macros