0xDEADBEEF

[RSS]
««« »»»

Striktní a líné jazyky

24. 6. 2018

Fran­ti­šek Řezáč napsal článek o tom, že Ope­rá­tory nejsou (vždy) funkce. To je pravda a není k tomu třeba do­dá­vat nic víc.

Stojí to ale za po­zor­nost jen v pří­padě strikt­ních ja­zy­cích typu C a Java, kde jsou ar­gu­menty funkce vy­hod­no­ceny vždy před jejím za­vo­lá­ním (ap­pli­ca­tive order/call by value). V ta­ko­vém pro­středí není jed­no­duše možné napsat vlastní funkci OR nebo AND, která se chová stejně jako ve­sta­věné ope­rá­tory || nebo &&. Ty v kla­sické sortě céčku po­dob­ných jazyků vy­hod­notí druhý ar­gu­ment jen pokud je to ne­zbytně nutné. Toho bez funkcí vyš­šího řádu (jak FR po­dotknul) není možné do­sáh­nout. Proto v nich ope­rá­tory za­u­jí­mají spe­ci­ální místo.

Mě to koplo ne­dávno, když jsem psal in­ter­pret jed­no­du­chého li­pov­ského jazyka1 , kde od­lo­že­ného vy­hod­no­co­vání bylo ne­zbytné k tomu, aby ná­sle­du­jící kód ne­skon­šil NullPointerException.

(if (and (nil? x) (.nonEmpty x)) (something))

V líných ja­zy­cích nebo těch, které pod­po­rují call-by-name nebo call-by-need, ope­rá­tory v prin­cipu nemají spe­ci­ální po­sta­vení2 a jsou to jen další metody.

Ve Scale můžu napsat vlastní funkci OR takto:

def OR(a: Boolean, b: => Boolean): Boolean = if (a) true else b

Typ => Boolean ozna­čuje call-by-name bo­o­lean. b není vy­hod­no­ceno při za­vo­lání funkce, na­místo toho bude vy­hod­no­ceno na každém místě, kde je v těle funkce po­u­žito. Kom­pi­lá­tor call-by-name pa­ra­metr zabalí do ano­nymní funkce, která je pak opa­ko­vaně volána.

Nejde ale o plně líné neboli call-by-need vy­hod­no­co­vání jako na­pří­klad v Haskellu. V něm je ne­vy­hod­no­cený výraz re­pre­zen­to­ván struk­tu­rou běžně na­zý­va­nou thunk, která uka­zuje na kód. Když je při­nu­cena se vy­hod­no­tit (na­pří­klad pat­tern matchin­gem), je od­ka­zo­vaný pro­gram vy­ko­nán a thunk je ato­micky za­mě­něn na vý­sle­dek. Líné jazyky mají tu vlast­nost, že ne­vy­hod­no­cené nemusí být jen ar­gu­menty funkce, ale celé datové struk­tury. Můžu mít masivní strom, ale když jsem četl jen z jedné cesty k listům, všechny ne­na­vští­vené od­bočky zů­sta­nou jako ne­vy­hod­no­cené thunky.

Call-by-need je tedy call-by-name do­pl­něné s me­mo­i­zací.

Ve Scale je to možné emu­lo­vat takto:

def f(_a: => X) = {
  lazy val a = _a
  ???
}

Když někde po­u­žiji pro­měn­nou a dojde k jejímu vy­hod­no­cení jen jednou a vý­sledná hod­nota se bude recyklo­vat při každém dalším po­u­žití.


Po­známky:


  1. Jme­no­val se Lispy a byl za­mýš­lený jako skrip­to­vací ná­stroj pro as­cii­blog. Psalo se v něm pří­jemně, ale na­ko­nec jsem ho na­hra­dil za ja­vascript ve­sta­věný do Javy.
  2. Kom­pi­lá­tor o nich ví a proto bych si do­vo­lil od­ha­do­vat, že pro ně vy­ge­ne­ruje lepší kód.
píše k47 (@kaja47, k47)