04 - Call by value, call by name

Az előző posztban láthattuk, hogy pl. egy $\mathrm{tailSum}(4-1,5+4)$ hívást intéztünk, az futás közben előbb kiértékeli az első argumentumot: $\mathrm{tailSum}(3,5+4)$, majd a másodikat (szép sorban az összeset), $\mathrm{tailSum}(3,9)$ és miután már megvan az argumentumok értéke, ezután hívja meg a függvényt (és, a substitution modelnek megfelelően, itt épp a $3$ és a $9$ értékeket helyettesíti be a függvénytörzsben a formális paraméterek helyére).

Ha egy függvény egy paraméterére ez az eljárás, azt call-by-value, azaz CBV konvenciónak nevezzük, és a Scala esetében ez az alapértelmezett viselkedés.

Egy másik lehetőség lenne az, hogy (ennek a konkrét kifejezésnek az esetében) nem értékeljük ki a $4-1$ ill. $5+4$ kifejezések értékeit, hanem így ahogy vannak helyettesítjük be őket a formális paraméterek helyére. Ezt a konvenciót nevezik call-by-name, azaz CBN -nek.

Értékeljük ki az előző poszt $\mathrm{tailSum}(5,0)$ kifejezésének értékét úgy, hogy CBN kezeljük a paramétereket:

$\begin{align*}\mathrm{tailSum}(5,0)&\triangleright \mathrm{if}(5\leq 0)~0~\mathrm{else}~\mathrm{tailSum}(5-1,0+5)\\&\triangleright \mathrm{if}(\mathrm{false})~0~\mathrm{else}~\mathrm{tailSum}(5-1,0+5)\\&\triangleright \mathrm{tailSum}(5-1,0+5)\\&\triangleright \mathrm{if}((5-1)\leq 0)~0~\mathrm{else}~\mathrm{tailSum}((5-1)-1,0+5+(5-1)))\\&\triangleright \mathrm{if}(4\leq 0)~0~\mathrm{else}~\mathrm{tailSum}((5-1)-1,0+5+(5-1)))\\&\triangleright \mathrm{if}(\mathrm{false})~0+5~\mathrm{else}~\mathrm{tailSum}((5-1)-1,0+5+(5-1)))\\&\triangleright \mathrm{tailSum}((5-1)-1,0+5+(5-1)))\\&\triangleright\mathrm{if}((5-1)-1\leq 0)~0+5+(5-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+(5-2))\\&\triangleright\mathrm{if}(4-1\leq 0)~0+5+(5-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+((5-1)-1))\\&\triangleright\mathrm{if}(3\leq 0)~0+5+(5-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+((5-1)-1))\\&\triangleright\mathrm{if}(\mathrm{false})~0+5+(5-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+((5-1)-1))\\&\triangleright\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+((5-1)-1))\\&\triangleright \mathrm{if}(((5-1)-1)-1\leq 0)~0+5+(5-1)+((5-1)-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1)-1,0+5+(5-1)+((5-1)-1)+(((5-1)-1)-1))\\\end{align*}$

(itt most akkor leállunk, mert nem fér ki a képernyőre széltében) hát. Persze, sejtjük, hogy ez matematikailag ugyanaz, mint a call-by-value implementáció, de rengetegszer számolja ki ugyanazokat a kifejezéseket (ami, ha nincs mellékhatása az adott kifejezésnek, érezhetően fölösleges meló), másrészt mintha a kifejezés mérete is így, hogy nem értékeljük ki a belső részeit, növekedne.

Scalában ha egy paramétert call-by-name akarunk átadni, azt a kettőspont és a típus közé írt $=>$ jelöli. A $\mathrm{tailSum}$ függvény call-by-name hívva:

import scala.annotation.tailrec

object Main extends App {
  def tailSum(n: Int) = {
    @tailrec
    def tailSum(n: =>Int, acc: =>Int): Int =
      if (n <= 0) acc else tailSum(n - 1, acc + n)

    tailSum(n, 0)
  }

  println(tailSum(20000)) //StackOverflowError
}

és talán nem lep meg senkit: ez így ebben a formában megint kivételt fog nekünk dobni - kapunk egy $\mathrm{StackOverflowError}$t. Hogy ez pontosan miért történik, azt később érteni is fogjuk - dióhéjban, a call-by-name paramétereknél a fordító egy függvényt fog nekünk készíteni és fordítani, és ezeknek a függvényeknek az egymásba stackelése lesz az, amit nem bír el a call stack.

Felmerül a kérdés, hogy ugyan miért akarna bárki call-by-name paramétert. Amit meg tudunk spórolni: ha a paramétert a függvény törzsének kiértékelésekor maximum egyszer értékeljük ki és előfordulhat, hogy egyáltalán nem, akkor érdemes lehet call-by-name hívni, főleg, ha az adott paramétert esetleg sokáig tarhat kiértékelni (ha aztán nem is használjuk, akkor minek értékeljük ki - hacsaknem egy mellékhatást szeretnénk előhozni).

Egy példa lehet a logikai műveletek (éselés, vagyolás) gyorsított kiértékelése: ha az első argumentum már meghatározza a kifejezés értékét, a másodikat nem értékeljük ki. Erre pl. egy if-else megoldás:

object Main extends App {
  def loop: Boolean = loop //végtelen ciklus
  def myNeg(x: Boolean) = if(x) false else true
  def myAnd(x: Boolean, y: =>Boolean) = if (x) y else false
  def myOr(x: Boolean, y: =>Boolean) = if (x) true else y

  println(myAnd(false, loop)) //prints false
}

Persze Scalában a Boolean változókat a C-ben / Javában szokott módon, direktben is tudjuk a $!$, $\&\&$ és $||$ operátorokkal negálni, éselni ill. vagyolni, de példának jó ez. Figyeljük meg azt is, hogy a $\mathrm{myAnd}(\mathrm{false},\mathrm{loop})$ hívás, mivel a $\mathrm{loop}$ kifejezés végtelen ciklusban értékelődik ki és nem is terminál (sőt, mivel tail recursive, a call stacket sem tölti, ezért ha ki próbáljuk értékelni, utána kézzel ki kell lőni a programot, nem öli meg a JVM), mégis terminál, mert a második paraméter call-by-name és ennél a kifejezésnél nem lesz szükség az értékére. Ebből jó lehet a call-by-name paraméterátadás, de van overheadje is és többször kiértékelni sem biztos, hogy akarjuk a kifejezéseinket.