Totális és parciális függvények

 ( enpassant | 2018. szeptember 24., hétfő - 8:00 )

Totális függvények

Sokak által ismert a függvények és az eljárások (utasítások) közötti különbség. Az is ismert, hogy milyen előnyei vannak a függvényeknek az eljárásokkal szemben, amiért célszerűbb inkább azokat használni. Az már kevésbé ismert, hogy a függvényeket két nagy csoportba sorolhatjuk, parciális és totális. Ebben a cikkben megvizsgáljuk a parciális és totális függvények tulajdonságait, és azt, hogy miért célszerűbb utóbbiakat alkalmazni.

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

Magyarul itt a parciális függvény (matekban is van parciális, csak ott mást jelent) ahol nem bajlódunk a kivételekkel? :D

Koszi a cikket! Kicsit hasonlit a multkori Scalas peldadra, ott is ez volt a lenyeg: "Making illegal states unrepresentable"

Az egyszerűség (KISS, Occam's razor, Least Power, You aren't gonna need it, Less is more) az alapja az egyszerű, könnyen érthető, tesztelhető, módosítható programok készítésének, amiből sok másik elv is következik (Making illegal states unrepresentable, Single responsibility, Interface segregation, ...), illetve az elsődlegesen használandó eszközök is következnek (immutable data, pure function, total function, ...).

Megmutatja a másik végletet is, ami bonyolultságot hoz a programunkba (Annotation, Exception, DI frameworks, ORM, Encapsulation, Inheritance, ...).

Így ezek sokszor előkerülnek az írásaimban. ;-)

Nagyon nehéz felismerni, mi egyszerű és mi az ami csak annak látszik, de nagyon bonyolult. Ebben a témában ezek nagyon jó videók Venkat Subramaniamtól:

The Art of Simplicity,
Do not walk away from Complexity, Run

amit te parcialisnak nevezel, azt en siman csak bug-nak...

--
"dolgozni mar reg nem akarok" - HZuid_7086 'iddqd' zoli berserk mode-ba kapcsol

Matematikus szemmel nézve azért annyi huncutság van az egészben, hogy a programozási nyelvtől függetlenül* gyakorlatilag csak parciális függvényeket tudunk definiálni, sőt legtöbbször azt sem triviális megmondani, hogy MELY értékekre lesz definiálatlan a megadott függvény. Ennek egyik alapvető oka, hogy valójában a gép számára

1) az int típus nem az egészek halmazát jelenti, hanem a gépen ábrázolható egészeket
2) a double vagy real vagy akármi dettó, az ábrázolható lebegőpontosakat

tehát a példákban emlegetett százalék függvény nemcsak a 100*10/0-ra, hanem a 100*10^1000/10^1000-re és még egy csomó értékre ad "furcsa" eredményeket.

*Persze lehet szoftveresen "végtelen" pontosságú bigInt és bigFloat típusokat implementálni, de így sem kapjuk meg az összes egészet, pl. a gép memória korlátjai miatt.

Ezzel az "objektíve zűrös" helyzettel a különböző nyelvek és szabványok különböző kreatív megoldásokkal próbálnak megküzdeni.

A kimondottan (numerikus) számolásra való Octave nyelvben pl.

octave:1> max([1.,10.^100])
ans = 1.0000e+100
octave:2> sin(10.^100),sqrt(10.^100),exp(10.^100)
ans = -0.38064
ans = 1.0000e+50
ans = Inf
octave:3> sin(10.^1000),sqrt(10.^1000),exp(10.^1000)
ans = NaN
ans = Inf
ans = Inf
octave:4> max([1.,10.^100,10.^1000])
ans = Inf
octave:5> sin(exp(10.^2)^7)
ans = -0.20976
octave:6> sin(exp(10.^2)^8)
ans = NaN

Jajj erről a hsz-ről felsejlettek a régi "szép" Numerikus Matematika órák, a túrótorta királyával :D
Azt hittem 3.14ci után már nem lehet baj. Hát lett :D

> Matematikus szemmel nézve azért annyi huncutság van az egészben, hogy a programozási nyelvtől függetlenül* gyakorlatilag csak parciális függvényeket tudunk definiálni

Konstans 0?

OK, meg még véges sok, pl.
const 1
const 2
...

De az f(x) = 2^1000/2^1000 - 1 már érdekesebb lehet...

Ügyes próbálkozás, de azért ez nem így van. ;-)

Azt remekül észrevetted, hogy "matematikus szemmel" pontatlanul fogalmaztam. Egész számot írtam, miközben a -2147483648 és a 2147483647 közötti egész számokra gondoltam.

Ezen túl viszont már nincs igazad, mert a parciális függvény esetén van olyan input érték, amihez nincs output érték rendelve.
A percentOptional és percentStrict függvényeknél nincs olyan input érték, amihez ne lenne output érték rendelve. Azon értékek amikről írsz, azok nincsenek benne a függvény értékkészletében (input), így nem is érdekesek a számunkra. Amik benne vannak, azokhoz pedig van output érték rendelve.

Azon értékek amikről írsz, azok nincsenek benne a függvény értékkészletében (input),

pontosabban az értelmezési tartományában

...Ezen túl viszont már nincs igazad, mert a parciális függvény esetén van olyan input érték, amihez nincs output érték rendelve.

hát ezt nem is merném vitatni :-)

Csak arra próbáltam rámutatni, hogy messze nem triviális kérdés az, hogy egy parciális függvény hol van értelmezve és hol nincs. Ez általában nem intézhető el triviális/egyszerű kivételkezeléssel. És nem is csupán a függvény képletén múlik, hanem a gépi aritmetikán és a standard függvények kiszámításának ezoterikus részletein.

Például hol van értelmezve

0) x -> x^2 egész x argumentumokra? (hint: mikor csordul túl x)

1) x -> sqrt(x^2) egész x argumentumokra?

2) x -> sin(exp(x)) lebegőpontos ("valós") x argumentumokra (lásd korábbi példák)

és ezek még csak triviális/egyszerű képletekkel megadott függvények.

Csak arra próbáltam rámutatni, hogy messze nem triviális kérdés, hogy egy parciális függvény hol van értelmezve és hol nincs

Ez teljesen rendben van, köszönöm is az észrevételt!

Általában nem olyan tragikus a helyzet, vagy könnyedén lekorlátozható az értelmezési tartomány egy biztosan megfelelőre, vagy eleve diszkrét elemekből áll az input.
Az is igaz, hogy lehet olyan, ahol nem egyszerű lekorlátozni, de a mindennapi gyakorlatban ilyen nagyon ritkán fordul elő. Ha előfordul ilyen, arra is írtam megoldást, bővítsük az outputok körét (értékkészlet ;-).

Ha viszont még azt sem tudja eldönteni a programozó, hogy parciális vagy sem, akkor meg nincs is miről beszélni, mert akkor biztosan nem fogja kezelni a problémás eseteket sem. ;-)

"Általában nem olyan tragikus a helyzet, vagy könnyedén lekorlátozható az értelmezési tartomány egy biztosan megfelelőre"
De akkor a példádra visszatérve úgy kell megadni *minden* argumentum típusát (és nem csak intet használni, felelőtlenül), hogy tényleg totális függvény legyen, parciális helyett.
Szóval szép a mórickapéldád, de sokkal szebb lenne, ha tényleg megmutatnád a példában, hogy minden bemenet számít. Pláne akkor, ha azt mondod, hogy "könnyedén lekorlátozható az értelmezési tartomány egy biztosan megfelelőre, vagy eleve diszkrét elemekből áll az input", akkor azt meg is kell tenni minden esetben.

Eleinte szimplán trollkodásnak vettem a hozzászólásod, de lehet, hogy tévedek és nem az, csak a gúnyolódó stílus miatt tűnt annak, ezért megpróbálok érdemben válaszolni rá.

De akkor a példádra visszatérve úgy kell megadni *minden* argumentum típusát (és nem csak intet használni, felelőtlenül), hogy tényleg totális függvény legyen, parciális helyett.

Így van, akkor totális egy függvény, ha minden inputra ad vissza értéket, és ez így is van az említett int paraméter ellenére. Nem attól lesz totális, hogy minden paramétert bekorlátozunk, hanem attól, hogy minden inputra ad outputot.

Pláne akkor, ha azt mondod, hogy "könnyedén lekorlátozható

Igen, ezt mondom, és meg is mutattam a cikkben, hogy az int könnyen lekorlátozható egy olyan adatszerkezetre, amiben nincs benne minden int érték (NotZeroInt). Ezáltal az összes bemenetre ad vissza outputot a függvény.

Bár már korábban azt hittem, többet nem szólok hozzá, de azért mégis .-)

...és meg is mutattam a cikkben, hogy az int könnyen lekorlátozható egy olyan adatszerkezetre, amiben nincs benne minden int érték (NotZeroInt). Ezáltal az összes bemenetre ad vissza outputot a függvény...

Azt hiszem, még mindig elsikkadt valami. Ahhoz, hogy (pl. egy egészeken, vagy azok részhalmazán értelmezett) "gépi függvény" adott inputra értelmezve legyen (vagyis "rendes" számértéket adjon vissza) 2 dolog szükséges:

1) az input benne legyen az értelmezési tartomány azon leszűkített részében, amin (azt gondoljuk, hogy :-) már totális a függvényünk, tehát biztosan értelmezve van

2) Úgy legyen megírva a függvényt kiszámító kód, hogy ilyen értékekre valóban ki tudjon számolni valami értelmes értéket, futása közben ne léphessen föl semmi kivételes állapot.

Néha az első, néha a második teljesítése a bonyolultabb.

Egy filozófiai kérdés: ha egy (pl. bonyolult rekurziókkal definiált) függvény adott inputra timeout-tal elszáll, akkor ott vajon definiálva van-e?

Például a Fibonacci sorozat rekurzív és nem rekurzív implementációi ugyanazt a függvényt definiálják-e?

A matematikai képlettel megadott függvény és az adott nyelven leprogramozott, a képlettel látszólag ekvivalens kódból álló "gépi függvény" a triviális esetektől eltekintve
- különböző értelmezési tartományú
- különböző értékkészletű és
- sok, még gépi számként pontosan megadható input esetén is eltérő értékeket ad vissza.

Egy filozófiai kérdés: ha egy (pl. bonyolult rekurziókkal definiált) függvény adott inputra timeout-tal elszáll, akkor ott vajon definiálva van-e?

Igen, ez az egész, amit vázolsz az főleg filozófiai, nem gyakorlati probléma.
A konkrét esetben, ha az a függvény sajátosságaiból fakad, hogy elszáll, akkor szerintem ott nincs definiálva.
Például:
1. figyeli, hogy mióta fut és adott idő fölött timeout-ol,
2. a rekurzív hívások egyre növelik a stack méretét és amiatt lesz StackOverflowException.

Ez a cikkben nem igazán érintett eset, amikor az input és az output alapján lehetne totális a függvény, de az implementáció (hibás volta?) miatt nem az, vagy pontosabban filozófiai kérdés, hogy az vagy nem az.

A matematikai képletes rész meg nem igazán a totális/parciális kérdéskör, hanem inkább a jól működik vagy sem kérdéskör.

En alapbol nem ertem, hogy miert kapsz ennyi "salt"-ot ezek ala a cikkek ala. A mutlkori bolgbejegzsesed alatt, a shop-os peldadnal is voltak akik odajottek es elkezdtek fikazni.
Mintha legalabb is direktbe nekik artottal volna valamit.

Harom lehetoseget latok:
- szimplan nem ertik mirol szolnak az FP alapjai es csak ugy irkalnak a vakvilagba
- faj nekik, hogy valaki probal valamilyen erteket produkalni amig ok nem es amiatt trollkodniuk kell
- tenyleg tudnak valamit csak nem hajlandoak elarulni

Nekem tetszenek az irasaid es azt latom, hogy sajnos nagyon sokan akik programoznak foggalmuk sincs ezekrol a dolgokrol es pl olyan dolgokra amik siman megoldhatok lennenek mondjuk a type system adottsagaival arra tesztet irnak, mert nem tudjak, hogy ilyet is lehet.

En is problalom egyebkent ezeket a szemleleteket terjeszteni, de sajnos nem mindenki nyitott rajuk, mert egy kis extra brain powerre lenne szukseg, meg ez nem a "megszokott/tanult" Java kodolas.

Akarhogy is legyen, en csak biztatni tudlak, hogy ne foglalkozz a haterekkel es blogolj tovabb, mert hasznos!

+1

Köszi, ez most nagyon jól esett!
Pedig ezután a cikk után is sokadszorra elhatároztam, hogy nem fogok írni többet.

Azt a pár órát más hasznos dologgal is el tudom tölteni, nem kapok értük negatív kritikát, sőt esetleg még meg is dicsérnek.

Mondjuk arra jók voltak ezen írásaim, hogy már nem húzom fel magam az ilyeneken. Elég könnyen elengedem, ha valaki nem fogja fel, hogy miről írok. Illetve van egy-pár ember itt a Hup-on, akiknek szinte soha nem is válaszolok.

Még egyszer köszi!

Én nem látom :/
Melyikekkel volt baj?

subs