ugrás a tartalomhoz

The Y Combinator in PHP

inf · 2014. Ápr. 28. (H), 22.18
Y kombinátor PHP-ben
 ■
1

lambda kalkulus (off)

zzrek · 2014. Május. 1. (Cs), 10.35
Régen tanultam erről, és a blogmark hatására átnéztem ismét, de elakadtam a szintaxis értelmezésében, légyszi segítsetek (már ha valakit érdekel a dolog, ez ugyanis már elég offtopic)
A wikipédia alapján indultam el. (Találtam benne egyértelmű hibákat is, de erre most nem térnék ki)
A lambda kalkulusban írt kifejezések olvasása nehézkes (régies), a jelenleg szokványos kifejezés-kiértékelési logikától eltér, oda kell figyelni. Például a szóköznek nagyobb jelentősége van.


λx.(λy.(x + y)) 4 7
A wiki szerint ebből ez lesz:


λy.(4 + y)) 7
majd pedig:


4 + 7
Értelmezésem szerint a sorrend az fontos, tehát a 7 + 4 nem lenne helyes (nem feltételezhetjük, hogy a "+" jellel jelölt művelet kommutatív)

Lejjebb, a béta konverziónál viszont ezt találtam:
Vegyük például a (3 + 5) kifejezést. Ez β-ekvivalens a (λx.(x + 5)) 3 kifejezéssel, ami pedig β-ekvivalens a (λy.(λx.(x + y))) 3 5 kifejezéssel.


Viszont értelmezésem szerint a (λy.(λx.(x + y))) 3 5 kifejezés a végén 5+3 lesz, nem?

A kettő közt (az x és y cseréjén kívül) a zárójelezés különbözik:


λx.(λy.(x + y)) 4 7
ebből 4+7 lesz, viszont

(λy.(λx.(x + y))) 3 5
ebből 3+5 ?
Ezek alapján nem tudom, hogyan kell kezelni a zárójelet.

A "kiértékelhetőség" résznél ezért ezt sem tudom értelmezni:

(λx.x x) (λx.x x)
Hogyan lesz ebből saját maga? Hogyan kezeljem a zárójeleket a kifejezés kiértékelésénél?

A másik problémám ezzel, hogy a λx.x x kifejezés nekem egy olyan alfa-konverziónak tűnik, amiben egy változót saját magára nevezünk át. Van ennek értelme?

Megköszönném, ha valaki felvilágosítana.
2

Én is csak azért tettem ki,

inf · 2014. Május. 1. (Cs), 15.41
Én is csak azért tettem ki, mert kiégett az agyam, amikor megpróbáltam megérteni, hogy hogyan működik :D Ha valaki tudja, és egyszerűen elmagyarázható, akkor jelezze! :D (annyit írnak róla, hogy olyan nyelveknél, ahol nincs alapból ciklus, ott ez lehetőség a megvalósítására)
3

Megígérem

zzrek · 2014. Május. 1. (Cs), 18.42
Megígérem, hogy ha valaki elmagyarázza nekem amit fenn kérdeztem, akkor elmesélem neked, hogy mire yó az Y kombinátor, rendben? :-)
5

deal

inf · 2014. Május. 1. (Cs), 20.52
deal
4

A λx.x x JS

MadBence · 2014. Május. 1. (Cs), 19.59
A λx.x x JS megfelelője:
function id(f) { return f(f); }
tehát nem ez, amire te gondolsz:

// function id(x) { return x; }
id(x) // x szabad változó? nem lenne sok értelme
Azaz az első zárójelben lévő "függvény" változóit behelyettesíted a második zárójelben lévővel (ő az argumentum), és mivel az első zárójelben x x van, így az eredmény ugyanaz lesz, mint amiből kiindultál.

A 3+5 valóban rossz. A zárójelezés nem egységes, de alapvetően szerintem (λ var . body)-ként kellene zárójelezni, nem mint λ var . (body)
6

Nagyszerű

zzrek · 2014. Május. 2. (P), 00.15
Nagyszerű, végre valaki aki ért hozzá :-)

Az igaz, hogy
λx.x 2
az 
2
?
Ha igen, akkor hogy lesz λx.x x nem x ? A zárójel miatt? Vagy azért, mert a λx. mindkét utána lévő x-et kötött változóként jelöli? Kötött változó nem lehet paraméter? Ebben az esetben a "szóköz-alkalmazás-operátor" simán szóköz lesz, és nem jelent semmit? Huh, kicsit összezavarodok.
7

Dereng

zzrek · 2014. Május. 2. (P), 00.46
Kezd derengeni :-)
Tényleg a zárójelezés lehet a ludas.
(λx.x x) (λx.x x)

Ez a kifejezés a baloldalon absztrakciót tartalmaz, ebben a szóköz nem alkalmazás-operátor. Pusztán azért, mert a zárójelezés miatt az egész képviseli a definíciót.
Aláhúzással jelölöm, hogy hol van alkalmazás-operátor, a többi helyen pusztán helykitöltő szóköz van.
(λx.x x)_(λx.x x)
Vagyis magában ez a kifejezés:
λx.x x

tényleg úgy értlemezendő, hogy:
λx.x_x

vagyis kifejtve x.

Jól gondolom?
8

A (λx.x x) kifejezésben a

MadBence · 2014. Május. 2. (P), 13.00
A (λx.x x) kifejezésben a szóköz alkalmazás-operátor, de a kifejezés törzse nem x, hanem x x. Ha a második kifejezést behelyettesíted az elsőbe, visszakapod az eredeti kifejezést.
9

Már értem

zzrek · 2014. Május. 2. (P), 21.21
Már értem hogy hogyan lesz a kettőből ismét ugyanaz (hogy hogyan képzelhető el), csak nem vagyok biztos a szintaxisban, a kifejezés kiértékelésében (hogy hogyan alkothatom meg teljes bizonyossággal a szintaxisnak megfelelő a kifejezést, amit elképzeltem).
Ha a szóköz alkalmazás-operátor, akkor nem kéne végrehajtani az alkalmazást a kiértékelése során?
Abban nem tévedek, hogy a λx.x 2 az 2?
Ha nem tévedek, akkor viszont λx.x x az x, ugye?
Különbözik valamiben λx.x x és (λx.x x) ?
Esetleg az (λx.x x) (λx.x x) kifejezésben azért nem hatályos az alkalmazás-operátor a zárójelek belsejében, mert előbb a köztük (középen) lévő alkalmazás operátort kell kiértékelni?

Köszi a segítséget, és bocs ha butákat kérdezek. De azt hiszem, hogy már a határán vagyok, hogy végre teljesen megértsem, most már nem akarok megállni.
10

az λx.x 2 az 2, mert itt elég

MadBence · 2014. Május. 2. (P), 22.19
az λx.x 2 az 2, mert itt elég egyértelmű, hogy a λ-absztrakció a λx.x, és erre alkalmazzuk a 2-t. Ha jobban akarod látni, akkor (λx.x) 2-ként lehetne írni.

A λx.x x önmagában elég értelmetlen, hisz egy free/unbound (nem tudom mi a pontos terminológia) változó marad, és lóg a levegőben.

A zárójelezéssel egyértelművé lehet tenni, hogy melyik λ-absztrakció meddig tart. A λx.x 2 eredménye 2, ha (λx.x) 2 vagy λx.(x) 2-ként zárójelezzük (a lényeg, hogy látni lehessen egyértelműen, hogy mi a λ-absztrakció törzse).

A (λx.x x) önmagában csak egy absztrakció (függvény), de lehetne akár λx.(x x)-ként is zárójelezni.

A kérdésedre válaszolva pedig igen, a zárójelek arra valók, amire mindenhol máshol, a kiértékelés sorrendjét adod meg velük :).
11

Rendben

zzrek · 2014. Május. 2. (P), 23.13
Rendben, tehát (te mondtad ki azt a szót, hogy értelmetlen, pedig nekem is ez járt a fejemben, csak épp nem mertem kimondani) a (λx.x x) (λx.x x) kifejezésben úgy kerüljük el az önmagában értelmetlen (λx.x x) kifejezés kiértékelését, hogy a (λx.x x) (λx.x x) kiértékelése során első lépésben már önmagát adja vissza a kifejezés (és ezzel kiértékelési rekurzív végtelenciklusba kerülünk) [i]mielőtt[/i ]még a (λx.x x) önmagában álló rész kiértékelésére sor kerülhetne.
Ez nekem nem tetszik.
Természetes, hogy értelmetlen dolog jön ki, ha értelmetlenek az építőkövek. Ezt én nem nevezném önmagát visszaadó, érdekes kifejezésnek, hanem inkább arra való példának, hogy a szintaxis mennyire könnyen ad lehetőséget arra, hogy értelmetlen kifejezést építsünk fel (ráadásul olyat, ami elsőre nem is tűnik értelmetlennek).
Le a kalappal a lambda-kalkulus előtt, tényleg érdekes dolgokat lehet belőle kihozni, de szerintem túl laza a szintaxisa (túl megengedő) és túl könnyen lehet vele értelmetlen kifejezéseket gyártani.

Ezzel az okfejtéssel nem kell egyetértened és nem kérem, hogy fejtsd ki a véleményed, de ha mégis egyetértenél, akkor örülnék, ha megerősítenél ebben :-)

Köszönöm a segítséged, még egy utolsó kérdést engedj meg légyszi.
Ennek van értelme, ez kiértékelhető? Ha igen, akkor mi lesz belőle a redukálás után?

λx.x 2 3
(Remélem nem fárasztottalak túlságosan)
12

A trükk az, hogy nem

MadBence · 2014. Május. 3. (Szo), 00.55
A trükk az, hogy nem kiértékelni akarjuk a kifejezést (hiszen azt nem lehet), hanem csak β-redukálni, amit lépésenként lehet megtenni (nem lesz végtelen ciklus).

λx.x 2 3-nél nem tudom, hogy ez most (λx.x) 2 3 vagy (λx.x 2 3), bár igaziból mindegy, hiszen értelmetlen.
13

Jó

zzrek · 2014. Május. 3. (Szo), 21.32
Jó, azt hiszem ennyi most egyelőre elég volt :-)

(
Kicsit keveregnek a fogalmak, a wiki ezt mondja:
Ha megpróbáljuk kiértékelni, akkor azt tapasztaljuk, hogy a változó-behelyettesítés elvégzése után ugyanazt a kifejezést kaptuk vissza.

Vagyis "kiértékelni" próbálja, nem béta-redukálni.
Ezt majd még egy kicsit átnézem, most belefáradtam. :-)
)

Köszi a segítséget és a kitartást :-)