Rekurze v Javě (i jinde)

[Filip Jirsák]

Technická poznámka pro zajímavost: nepokračování bloku kódu může způsobit nejen výjimka, ale i nekonečná rekurze. Např. Scala má typ `Nothing`, který se typicky používá jako typ výsledku funkce, která nikdy neskončí.

Znamená to, že to Scala překládá do jiného bajtkódu, než je volání funkce? Tj. neukládá se volání na zásobník a může to být skutečná nekonečná rekurze?

[Reklama]

[registrovany_ava]

Technická poznámka pro zajímavost: nepokračování bloku kódu může způsobit nejen výjimka, ale i nekonečná rekurze. Např. Scala má typ `Nothing`, který se typicky používá jako typ výsledku funkce, která nikdy neskončí.

Znamená to, že to Scala překládá do jiného bajtkódu, než je volání funkce? Tj. neukládá se volání na zásobník a může to být skutečná nekonečná rekurze?

Asi narážíš na

def x: Nothing = x

Do bajtkódu jsem se nedíval. Zkusil jsem to pustit a zásobník nepřetéká. Scala v omezené míře (https://www.scala-exercises.org/scala_tutorial/tail_recursion) převádí tail rekurzi na smyčku (dokonce je možné funkci přidat anotaci @tailrec, která říká, že u funkce se očekává, že je tail rekurzivní, a pokud by nebyla, je to compile error). V tomhle  případě je ale překladač asi ještě chytřejší, protože při spuštění to ani nežere CPU, možná (ale opravdu jen spekuluju) prostě to vlákno zaparkuje a hotovo.

[registrovany_ava]

def notImplemented: Nothing = throw new RuntimeException("Not implemented")

Kód: [Vybrat]

???

Jasně, rozepsal jsem to jen z didaktických důvodů.

[registrovany_ava]

Technická poznámka pro zajímavost: nepokračování bloku kódu může způsobit nejen výjimka, ale i nekonečná rekurze. Např. Scala má typ `Nothing`, který se typicky používá jako typ výsledku funkce, která nikdy neskončí.

Znamená to, že to Scala překládá do jiného bajtkódu, než je volání funkce? Tj. neukládá se volání na zásobník a může to být skutečná nekonečná rekurze?

Tak jsem z toho ten bajtkód dostal:

public scala.runtime.Nothing$ x();
  Code:
     0: goto          0

A CPU to žere, předtím jsem to nějak blbě pustil.

[Filip Jirsák]

Tak jsem z toho ten bajtkód dostal:

public scala.runtime.Nothing$ x();
  Code:
     0: goto          0

A CPU to žere, předtím jsem to nějak blbě pustil.

Díky.

[Reklama]

[Ink]

Technická poznámka pro zajímavost: nepokračování bloku kódu může způsobit nejen výjimka, ale i nekonečná rekurze. Např. Scala má typ `Nothing`, který se typicky používá jako typ výsledku funkce, která nikdy neskončí.

Znamená to, že to Scala překládá do jiného bajtkódu, než je volání funkce? Tj. neukládá se volání na zásobník a může to být skutečná nekonečná rekurze?

Scala to obchází pomocí tzv. trampolíny: https://free.cofree.io/2017/08/24/trampoline/

[registrovany_ava]

Technická poznámka pro zajímavost: nepokračování bloku kódu může způsobit nejen výjimka, ale i nekonečná rekurze. Např. Scala má typ `Nothing`, který se typicky používá jako typ výsledku funkce, která nikdy neskončí.

Znamená to, že to Scala překládá do jiného bajtkódu, než je volání funkce? Tj. neukládá se volání na zásobník a může to být skutečná nekonečná rekurze?

Scala to obchází pomocí tzv. trampolíny: https://free.cofree.io/2017/08/24/trampoline/

Trampolína není nic Scala-specifického, Scala žádnou automatickou trampolínozaci AFAIK nedělá, článek co odkazuješ vypráví o tom jak si rekurzivní funkci ztrampolínovat ručně. Tail rekurzivní funkce (tedy i tu co jsem uvedl já) Scala převádí sama na obyčejnou smyčku (jak je vidět i z bajtkódu co jsem postnul), obecné rekurzivní funkce se volají obyčejně přes zásobník.

[Ink]

Scala to obchází pomocí tzv. trampolíny: https://free.cofree.io/2017/08/24/trampoline/

Trampolína není nic Scala-specifického, Scala žádnou automatickou trampolínozaci AFAIK nedělá, článek co odkazuješ vypráví o tom jak si rekurzivní funkci ztrampolínovat ručně. Tail rekurzivní funkce (tedy i tu co jsem uvedl já) Scala převádí sama na obyčejnou smyčku (jak je vidět i z bajtkódu co jsem postnul), obecné rekurzivní funkce se volají obyčejně přes zásobník.

No to je zajímavé, matně jsem si pamatoval, že to dělá automaticky (a netvrdil jsem, že to je specifické pro Scalu). Třeba tady píšou: However, to support TCO, Scala uses a well-known technique called a trampoline. Z čeho jsem tu informaci kdysi čerpal a jak to tam formulovali, už si nepamatuju.

Možná šlo fakt o tohle.

[registrovany_ava]

Scala to obchází pomocí tzv. trampolíny: https://free.cofree.io/2017/08/24/trampoline/

Trampolína není nic Scala-specifického, Scala žádnou automatickou trampolínozaci AFAIK nedělá, článek co odkazuješ vypráví o tom jak si rekurzivní funkci ztrampolínovat ručně. Tail rekurzivní funkce (tedy i tu co jsem uvedl já) Scala převádí sama na obyčejnou smyčku (jak je vidět i z bajtkódu co jsem postnul), obecné rekurzivní funkce se volají obyčejně přes zásobník.

No to je zajímavé, matně jsem si pamatoval, že to dělá automaticky (a netvrdil jsem, že to je specifické pro Scalu). Třeba tady píšou: However, to support TCO, Scala uses a well-known technique called a trampoline. Z čeho jsem tu informaci kdysi čerpal a jak to tam formulovali, už si nepamatuju.

Možná šlo fakt o tohle.

No úplně pro jistotu jsem to ještě zkusil, https://scalafiddle.io/sf/J2aN2OT/0:

def a(x: Int): Int = if (x == 0) {x} else {1 + a(x - 1)}
println("Finished")

a(100000)

přeteče (volání `a` není v tail pozici).

Tak možná se o tom ve Scale kdysi uvažovalo, nebo tam mají chybu, nevím. Každopádně díky za zajímavé odkazy. scala.util.control.TailCalls jsem ani neznal.

[registrovany_ava]

Scala to obchází pomocí tzv. trampolíny: https://free.cofree.io/2017/08/24/trampoline/

Trampolína není nic Scala-specifického, Scala žádnou automatickou trampolínozaci AFAIK nedělá, článek co odkazuješ vypráví o tom jak si rekurzivní funkci ztrampolínovat ručně. Tail rekurzivní funkce (tedy i tu co jsem uvedl já) Scala převádí sama na obyčejnou smyčku (jak je vidět i z bajtkódu co jsem postnul), obecné rekurzivní funkce se volají obyčejně přes zásobník.

No to je zajímavé, matně jsem si pamatoval, že to dělá automaticky (a netvrdil jsem, že to je specifické pro Scalu). Třeba tady píšou: However, to support TCO, Scala uses a well-known technique called a trampoline. Z čeho jsem tu informaci kdysi čerpal a jak to tam formulovali, už si nepamatuju.

Možná šlo fakt o tohle.

Jo, on ten článek asi myslí tu "podporu ve Scale" právě tak, že je ve standardní knihovně implementace trampolíny, která je m****a (nemusí se tu to slovo vyskytnout v každé druhé diskuzi :-), tudíž ji lze ve Scale narozdíl od většiny mainstreamových jazyků vyjádřit, a ještě má syntaktickou podporu pro snadné vytváření díky for comprehension.

[Ink]

Jo, on ten článek asi myslí tu "podporu ve Scale" právě tak, že je ve standardní knihovně implementace trampolíny, která je m****a (nemusí se tu to slovo vyskytnout v každé druhé diskuzi :-), tudíž ji lze ve Scale narozdíl od většiny mainstreamových jazyků vyjádřit, a ještě má syntaktickou podporu pro snadné vytváření díky for comprehension.

Já jsem se Scalou koketoval už před nevím kolika lety, tak jsem teď googloval. Ovšem s tou Monikou jsi mě dostal, přemýšlel jsem, co za sprosté slovo jsi přiřadil trampolíně.