03 - szelekció és a substitution model

Szelekció

...avagy ,,if''. Láttuk, hogy kifejezéseket többféle módon építhetünk és kapnak típust:

  • egy literált ha beírunk, annak adott lesz az értéke és a típusa is, pl. ha "Hello Scala" a literálunk, az egy String típusú érték, egyben kifejezés; ha 42, akkor Int típusú érték; ha false, akkor Boolean típusú
  • és alkalmazhatunk függvényeket (beépítettet vagy sem), ha az argumentumok típusa megfelel a függvény fejlécének, akkor a kifejezés ,,well-formed'' és típusa a függvény kimeneti típusa

Egy további lehetőség az if-else konstrukció: ha B egy Boolean típusú kifejezés és E1, E2 pedig valami T típusú kifejezések, akkor if( B ) E1 else E2 is egy T típusú kifejezés.

Intuitíve nagyon hasonló történik, mint egy imperatív nyelvben: ha B igaz, akkor a kifejezés értéke az E1 kifejezés értéke, ha pedig hamis, akkor az E2 kifejezés értéke lesz.

De hogy ez pontosabban mit jelent, ahhoz meg kell ismerjük az operatív szemantikát, ami ,,matematikailag'' definiálja, hogy mi is az, hogy ,,kiértékelés''.

Operatív szemantika: ▹

Mikor ,,kiértékelünk'' egy értéket, akkor formailag egyszerű dolgunk van: ha van egy kifejezésünk, az már vagy egy ,,érték'', azaz egy ,,végeredmény'', és akkor már ki van értékelve, vagy pedig egy olyan kifejezés, melynek a kiértékelését még nem fejeztük be.

A kiértékelésben egy lépés végrehajtásának a jele a ▹ lesz, mert ez szokott lenni sok helyen, az operatív háromszög. Például, ha a kifejezésünk a 3*(1+2), akkor egy lépéssel később az 1+2 rész-kifejezést fogjuk kiértékelni 3-má, más nem változik, és kapjuk tehát, hogy egy lépéssel később hogy állunk: 3*(1+2) ▹ 3*(3), amit tovább értékelhetünk: egy szám egy zárójelben az maga a szám, azaz 3*(3) ▹ 3*3, és ezek után a 3*3-at tovább tudjuk értékelni az intek beépített szorzása alapján 3*3 ▹ 9 módon. Így azt kaptuk, hogy 3*(1+2) ▹ 3*(3) ▹ 3*3 ▹ 9, és ez a vége a 9 már egy olyan érték, amit nem tudunk tovább átírni, így ez az, ami a kiértékelés ,,eredménye'', ha ez a kifejezés egy értékadás jobb oldalán van, akkor a bal oldali néven nevezett értékkel ezt a 9 számot fogjuk jelölni.

Az if-else kifejezés operatív szemantikájának a szabályai pedig:

  • if(true) E1 else E2 ▹ E1 - ez azt mondja, hogy ha a feltétel true, akkor dobjunk el E1-en kívül mindent, és csak azt értékeljük ki tovább, az lesz az eredmény
  • if(false) E1 else E2 ▹ E2 - ez meg azt mondja, hogy ha a feltétel false, akkor E2-vel számoljunk csak tovább, a kifejezés többi részét eldobhatjuk
  • ha if(B1) E1 else E2 és B1 ▹ B2, akkor if(B1) E1 else E2 ▹ if(B2) E1 else E2 - ez meg azt mondja, hogy ha a feltétel még nincs kiértékelve konkrét igaz/hamisra, de tudunk rajta tovább számolni, akkor számoljuk tovább a feltételt (in particular, a két ágon a kifejezésekhez még ne nyúljunk addig, amíg a feltétel kiértékelése nincs kész).

Függvények

Minden funkcionális nyelven lehet függvényeket deklarálni valamilyen szintaxissal - hiszen a funkcionális azt is jelenti, hogy vannak benne függvények.

Scalában függvényeket a def kulcsszóval deklarálunk:

1
2
3
def f( n: Int ): Int = {
  n * 2
}

egy valid függvénydeklaráció. Nézzük, mit tanultunk ebből:

  • def kulcsszóval kell kezdeni, utána jön a függvény neve
  • eztán nyitójelben jönnek a paraméterek, név : típus alakban, egyébként vesszőkkel elválasztva, végül egy csukójel
  • eztán kettősponttal a függvény visszatérési típusa
  • majd egy egyenlőségjel, utána meg egy kifejezés, melyben használhatjuk a formális paramétereket is.
  • nincs return! a függvény törzse is csak egy kifejezés, ami kiértékelődik valamire és az lesz a ,,visszatérési érték''
  • ha több kifejezés van egymás után a függvény törzsében, akkor az ily módon összetett kifejezés értéke az utolsó kifejezés értéke lesz.

Ahogy pedig egy függvényhívást kiértékelünk:

  • ha van egy def f( x1: T1, x2: T2, ..., xn: Tn ) : T = E függvénydeklarációnk,
  • és valahol a kódban egy f( v1, v2, ..., vn ) kifejezésünk,
  • akkor erre az f( v1, v2, ..., vn ) ▹ E[x1/v1, x2/v2, ..., x/vn] átírást alkalmazzuk,
  • ami azt jelenti, hogy a függvény törzsében az összes x1 formális argumentumot a v1-re, az összes x2-t v2-re stv. cserélünk, kapunk egy (jó hosszú) kifejezést, majd ezt értékeljük tovább.

Call-by-name, call-by-value

Fontos megkülönböztetnünk azt, hogy mikor egy f( v1, v2, ..., vn ) alakú kifejezést (,,függvényhívást'') kell kiértékelnünk, amikor a v1, v2 stb. nem feltétlenül értékek még, hanem lehetnek még nem kiértékelt kifejezések, tehát pl. további függvényhívások stb, akkor mit kell tennünk: előbb kiértékelni az összes argumentumot, és csak aztán behelyettesíteni, vagy behelyettesíteni a kifejezéseket ,,ahogy vannak'' és majd ha odaér a számítás, akkor kiértékelni?

Minden paraméterre külön-külön definiálhatjuk, hogy call-by-name vagy call-by-value legyenek kiértékelve:

  • ha az xi paraméter call-by-value, akkor előbb ki kell értékeljük az argumentumot, és csak eztán helyettesíthetjük be,
  • ha pedig call-by-name, akkor magát a kifejezést, amivel hívtuk a függvényt, kiértékelés nélkül kell beelyettesítsük.

Mindkét megközelítésnek vannak előnyei és hátrányai.

Egy példa kiértékelés

Nézzük a következő függvényt:

1
2
3
def dup( n: Int ): Int = {
  if ( n == 0 ) 0 else 2 + dup( n-1 )
}

Ha most kiértékeljük a dup(2) kifejezést, call-by-value konvencióval (Scalában ez a default), akkor ezt kapjuk:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
dup(2)  if( 2 == 0 ) 0 else 2 + dup( 2-1 ) //ezen a ponton még nem értékeljük ki a 2-1-et!
// csak a függvény törzsében mindenhol az n paraméter helyére beírtuk, hogy 2
        if( false )  0 else 2 + dup( 2-1 ) // 2==0 volt a feltétel, ami hamis
        2 + dup( 2-1 )                     // if(false) E1 else E2 ▹ E2
        2 + dup( 1 )                       // CALL BY VALUE miatt előbb kiértékeljük
        2 + { if ( 1 == 0 ) 0 else 2 + dup( 1-1 ) }
        2 + { if ( false ) 0 else 2 + dup( 1-1 ) }
        2 + { 2 + dup( 1-1 ) }
        2 + { 2 + dup( 0 ) }
        2 + { 2 + { if ( 0 == 0 ) 0 else 2 + dup( 0-1 ) } }
        2 + { 2 + { if ( true ) 0 else 2 + dup( 0-1 ) } } //most true lett a feltétel
        2 + { 2 + { 0 } } // if(true) E1 else E2 ▹ E1
        2 + { 2 + 0 }     // érték van egy kapcsosban, már nem kell
        2 + { 2 }         // 2+0 = 2 elvégzése
        2 + 2             // érték a kapcsosban
        4                 // 2x2 az 4 yeay

Scalában ha egy paraméter call-by-name kezelendő, annak a jele a => prefix megadása a típus előtt:

1
2
3
def dup( n: => Int ): Int = {  //így most call-by-name
  if ( n == 0 ) 0 else 2 + dup( n-1 )
}

Ekkor pedig a dup(2) kiértékelése így zajlik:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
dup(2)  if( 2 == 0 ) 0 else 2 + dup( 2-1 ) 
        if( false )  0 else 2 + dup( 2-1 ) // egy darabig nem változik semmi
        2 + dup( 2-1 )                     // if(false) E1 else E2 ▹ E2
        2 + { if( 2-1==0 ) 0 else 2 + dup( 2-1-1 ) }// CALL BY NAME miatt behelyettesítjük 2-1 -ként
        2 + { if( 1==0 ) 0 else 2 + dup( 2-1-1 ) }  // részletesen, most a feltétel két oldalát értékeljük ki
        2 + { if( false ) 0 else 2 + dup( 2-1-1 ) }
        2 + { 2 + dup( 2-1-1 ) }
        2 + { 2 + { if( 2-1-1==0 ) 0 else 2 + dup(2-1-1-1) } }
        2 + { 2 + { if( 1-1==0 ) 0 else 2 + dup(2-1-1-1) } }
        2 + { 2 + { if( 0==0 ) 0 else 2 + dup(2-1-1-1) } }
        2 + { 2 + { if( true ) 0 else 2 + dup(2-1-1-1) } }
        2 + { 2 + { 0 } }
        2 + { 2 + 0 } //kapcsos eltüntetés, műveletek elvégzése stb
        2 + { 2 } 
        2 + 2
        4             //yeay, még mindig 4

Látható, hogy a call-by-name érkező argumentumokat ha sokszor használjuk a függvény kiértékelésében, akkor mindannyiszor ki is fogja számolni a kód; erre még visszatérünk majd. Ökölszabályként ha egy bejövő argumentumot mindenképp használunk is legalább egyszor, akkor call-by-value érdemes átadni, ha pedig 0-szor vagy 1-szer, akkor indokolt lehet a call-by-name átadás.

Egy szokásos példa: a faktoriális függvény

Nézzük most akkor példaképp a következő Scala kódot (az object Main extends App részt mostantól nem írjuk ki, végül is nem számít, hogy ez a részlet épp egy futtatható App belsejében van vagy máshol):

1
2
3
4
def fact( n: Int ): Int = {
  if( n <= 1 ) 1 else n * fact( n-1 )
}
println( fact(5) )

Kérdések

  • Próbáljuk meg végigvezetni a fenti faktoriális függvény kiértékelését, ha az argumentumot call-by-name veszi át! A println függvény mindenképp call-by-value kezeli az argumentumát.
    válasz mutatása
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
println( fact(5) )  println( { if( 5 <= 1 ) 1 else 5 * fact( 5-1 ) } )
/* a fact(5)-öt értékeljük, a fact függvény törzsében
   n helyébe 5-öt írva mindenhol */
 println( { if( false ) 1 else 5 * fact( 5-1 ) } )
// kiértékeltük az 5 <= 1 feltételt, false lett
 println( { 5 * fact( 5-1 ) } )
// az if(false) alakú kifejezés az else ágára íródik át
 println( { 5 * fact( 4 ) } )
// mivel fact call-by-value kéri az argumentumot, ezért kiértékeltük előbb
 println( { 5 * { if( 4 <= 1 ) 1 else 4 * fact( 4 - 1 ) } } )
// behelyettesítettük a 4-et mindenhol a függvénytörzsben n helyére
 println( { 5 * { if( false ) 1 else 4 * fact( 4 - 1 ) } } )
// kiértékeltük a feltételt
 println( { 5 * { 4 * fact( 4 - 1 ) } } )
// hamis if feltétel, else ágra írjuk át
 println( { 5 * { 4 * fact( 3 ) } } )
// fact call-by-value, kiértékeljük az argumentumot
 println( { 5 * { 4 * { if( 3 <= 1 ) 1 else 3 * fact( 3-1 ) } } } )
 println( { 5 * { 4 * { if( false ) 1 else 3 * fact( 3-1 ) } } } )
 println( { 5 * { 4 * { 3 * fact( 3-1 ) } } } )
 println( { 5 * { 4 * { 3 * fact( 2 ) } } } )
 println( { 5 * { 4 * { 3 * { if( 2 <= 1 ) 1 else 2 * fact( 2-1 ) } } } } )
 println( { 5 * { 4 * { 3 * { if( false ) 1 else 2 * fact( 2-1 ) } } } } )
 println( { 5 * { 4 * { 3 * { 2 * fact( 2-1 ) } } } } )
 println( { 5 * { 4 * { 3 * { 2 * fact( 1 ) } } } } )
 println( { 5 * { 4 * { 3 * { 2 * { if( 1 <= 1 ) 1 else fact( 1-1 ) } } } } } )
// most true lesz a feltétel
 println( { 5 * { 4 * { 3 * { 2 * { if( true ) 1 else fact( 1-1 ) } } } } } )
// amit az if első részkifejezésére írunk át
 println( { 5 * { 4 * { 3 * { 2 * { 1 } } } } } )
// most pedig: ha egy kifejezés van egy kapcsoson belül, akkor elvesszük a kapcsost
 println( { 5 * { 4 * { 3 * { 2 * 1 } } } } )
// elvégezzük a 2*1 szorzást
 println( { 5 * { 4 * { 3 * { 2 } } } } )
// kapcsos nem kell
 println( { 5 * { 4 * { 3 * 2 } } } )
// szorzás
 println( { 5 * { 4 * { 6 } } } )
 println( { 5 * { 4 * 6 } } )
 println( { 5 * { 24 } } )
 println( { 5 * 24 } )
 println( { 120 } )
 println( 120 )
// ez pedig kiírja konzolra a 120-as számot, majd visszatér a visszatérési értékkel, ami (), mert println Unit:
 ()
// és itt a vége.
  • Próbáljuk meg végigvezetni ugyanezt úgy is, ha a fact függvény név szerint kapja meg paraméterét!

Utolsó frissítés: 2020-12-22 21:04:26