Ar Python optimizuoja uodegos rekursiją?

Turiu šį kodo fragmentą, kuris nepavyksta, su šia klaida:

RuntimeError: viršytas maksimalus grįžimo gylis

Bandžiau jį perrašyti, kad būtų galima atlikti uodegos rekursių optimizavimą (TCO). Manau, kad šis kodeksas turėjo būti sėkmingas, jei būtų atliktas TCO.

 def trisum(n, csum): if n == 0: return csum else: return trisum(n - 1, csum + n) print(trisum(1000, 0)) 

Ar turėčiau daryti išvadą, kad „Python“ nevykdo jokio tipo TCO, ar man reikia ją apibrėžti kitaip?

144
27 нояб. nustatė Jordan Mack 27 lapkričio. 2012-11-27 22:53 '12 10:53 val. 2012-11-27 22:53
@ 6 atsakymai

Ne, ir ji niekada nebus, nes Guido nori turėti tinkamus pėdsakus.

http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html

http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html

Su šia konversija galite rankiniu būdu pašalinti rekursiją.

 >>> def trisum(n, csum): ... while True: # change recursion to a while loop ... if n == 0: ... return csum ... n, csum = n - 1, csum + n # update parameters instead of tail recursion >>> trisum(1000,0) 500500 
151
27 нояб. John La Rooy atsakymas lapkričio 27 d 2012-11-27 22:55 '12, 10:55 val. 2012-11-27 22:55

Redaguoti (2015-07-02): Laikui bėgant, mano atsakymas tapo gana populiarus, ir, kadangi iš pradžių buvo daugiau nuoseklumo nei bet kas kitas, aš nusprendžiau šiek tiek laiko ir pakartoti, užrašyti jį pilnai (tačiau originalus atsakymas gali būti rastas pabaigos).

Redaguoti (2015-07-12): Galiausiai paskelbiau modulį, kuris atlieka uodegos pokalbių optimizavimą (apdorojant tiek uodegos atkūrimą, tiek tęsimą): https://github.com/baruchel/tco

Uodegos rekursijos optimizavimas pythone

Dažnai teigiama, kad uodegos rekursija neatitinka pythoninio kodavimo metodo ir kad nereikėtų nerimauti, kaip ją įterpti į kilpą. Nenoriu ginčytis šiuo požiūriu; Kartais man patinka išbandyti ar pristatyti naujas idėjas kaip uodegos rekursines funkcijas, o ne su kilpomis dėl įvairių priežasčių (daugiausia dėmesio skiriant procesui, turint dvidešimt trumpų funkcijų mano ekrane tose pačiose ir ne tik trijose „pythonic“ funkcijose, veikiančiose) nei redaguoti mano kodą ir tt).

Python uodegos rekursijos optimizavimas yra gana paprastas. Nors sakoma, kad tai neįmanoma arba labai sunku, manau, tai galima pasiekti pasitelkiant elegantiškus, trumpus ir bendruosius sprendimus; Aš net manau, kad dauguma šių sprendimų nenaudoja „Python“ funkcijų kitaip nei turėtų. Grynos lambda išraiškos, kurios veikia kartu su labai standartinėmis kilpomis, leidžia greitai, efektyviai ir visiškai panaudoti įrankius uodegos rekursų optimizavimui įgyvendinti.

Kaip asmeninį patogumą parašiau nedidelį modulį, kuris įgyvendina šį optimizavimą dviem skirtingais būdais. Norėčiau čia aptarti dvi pagrindines funkcijas.

Švarus būdas: pakeisti Y kombinatorių

Y kombinatorius yra gerai žinomas; ji leidžia jums naudoti lambda funkcijas rekursyviu būdu, tačiau vien tik neleidžia į ciklą integruoti rekursinius skambučius. Lambda Calculus negali to padaryti. Tačiau mažas Y kombinatoriaus pokytis gali apsaugoti rekursinį skambutį, kuris bus iš tikrųjų įvertintas. Todėl vertinimas gali būti atidėtas.

Čia yra garsioji Y kombinatoriaus išraiška:

 lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))) 

Su labai mažais pakeitimais galėčiau gauti:

 lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args))) 

Užuot skambinusi, funkcija f dabar grąžina funkciją, kuri atlieka tą patį skambutį, tačiau, kadangi ji grąžina, vertinimą galima atlikti vėliau iš išorės.

Mano kodas yra:

 def bet(func): b = (lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args))))(func) def wrapper(*args): out = b(*args) while callable(out): out = out() return out return wrapper 

Funkciją galima naudoti taip: Čia pateikiami du pavyzdžiai, kai faktiškai ir Fibonacci:

 >>> from recursion import * >>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) ) >>> fac(5,1) 120 >>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) ) >>> fibo(10,0,1) 55 

Akivaizdu, kad rekursijos gylis nebėra problema:

border=0
 >>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000) 42 

Tai, žinoma, yra vienintelis tikrasis funkcijos tikslas.

Su šiuo optimizavimu negali būti atliekamas tik vienas dalykas: jis negali būti naudojamas su uodegos rekursine funkcija, kuri vertina kitą funkciją (tai kyla iš to, kad vadinamieji grąžinti objektai yra traktuojami kaip papildomi rekursiniai skambučiai be jokio skirtumo). Kadangi man paprastai nereikia tokios funkcijos, esu labai patenkintas aukščiau pateiktu kodu. Tačiau, norint pateikti bendresnį modulį, aš šiek tiek daugiau galvojau, kaip rasti keletą būdų išspręsti šią problemą (žr. Kitą skyrių).

Kalbant apie šio proceso greitį (tačiau tai nėra reali problema), tai yra gana gera; uodegos rekursijos funkcijos vertinamos daug greičiau nei naudojant šį kodą naudojant paprastesnes išraiškas:

 def bet1(func): def wrapper(*args): out = func(lambda *x: lambda: x)(*args) while callable(out): out = func(lambda *x: lambda: x)(*out()) return out return wrapper 

Manau, kad vienos išraiškos, net ir sudėtingos, vertinimas vyksta daug greičiau nei vertinant kelias paprastas išraiškas, kurios yra šioje antrojoje versijoje. Negalėjau išsaugoti šios naujos funkcijos į savo modulį, ir nematau jokių aplinkybių, kai ją galima naudoti vietoj „oficialaus“.

Tęstinis stilius su išimtimis

Čia yra bendresnė funkcija; ji gali apdoroti visas uodegos rekursines funkcijas, įskaitant tas, kurios grįžta į kitas funkcijas. Rekursiniai skambučiai yra atpažįstami iš kitų grąžinimo verčių, išskyrus išimtis. Šie sprendimai yra lėtesni nei ankstesni; greičiau kodas galbūt būtų parašytas naudojant tam tikras specialiąsias reikšmes, pvz., „vėliavos“, esančias pagrindinėje kilpoje, bet man nepatinka idėja naudoti specialias reikšmes ar vidinius raktinius žodžius. Yra šiek tiek absurdiško išimčių naudojimo išaiškinimo: jei Python nepatinka uodegos rekursiški skambučiai, išimtis turi įvykti, kai įvyksta uodegos rekursiškas skambutis, o pythoninis kelias bus išimtis, kad rastų švarų sprendimą, kuris iš tikrųjų vyksta čia ...

 class _RecursiveCall(Exception): def __init__(self, *args): self.args = args def _recursiveCallback(*args): raise _RecursiveCall(*args) def bet0(func): def wrapper(*args): while True: try: return func(_recursiveCallback)(*args) except _RecursiveCall as e: args = e.args return wrapper 

Dabar galite naudoti visas funkcijas. Toliau pateiktame pavyzdyje f(n) yra vertinamas pagal bet kurią teigiamą n reikšmę:

 >>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) ) >>> f(5)(42) 42 

Žinoma, galima teigti, kad išimtys nėra skirtos panaudoti vertimui perorientuoti (kaip goto operatorius, o veikiau stiliaus tęsinys), kurį turiu pripažinti. Bet, vėlgi, man atrodo, kad idėja naudoti vieną eilę try kuris yra return bando kažką grįžti (normalus elgesys), tačiau negalime to padaryti dėl rekursinio skambučio (išimtis).

Pirminis atsakymas (2013-08-29).

Aš parašiau labai mažą papildinį, skirtą uodegos rekursijai. Ją galite rasti su mano paaiškinimais: https://groups.google.com/forum/?hl=fr#!topic/comp.>

Jis gali įterpti lambda funkciją, parašytą uodegos rekursijos būdu į kitą funkciją, kuri ją įvertins kaip kilpą.

Įdomiausias šios mažos funkcijos bruožas, mano nuomone, yra tai, kad ši funkcija nesiremia nešvaria programine įranga, bet tik paprastu „lambda“ skaičiavimu: funkcijos kitimas pasikeičia, kai jis įterpiamas į kitą lambda. funkcija, kuri yra labai panaši į Y-kombinatorių.

Linkėjimai

29 авг. Thomas Baruchel atsakymas rugpjūčio 29 d 2013-08-29 12:08 '13, 12:08 2013-08-29 12:08

Guido žodis yra http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Neseniai paskelbiau įrašą į savo „Python“ istorijos dienoraštį apie „Python“ funkcionalumo kilmę. Šoninė pastaba apie uodegos palaikymo rekursijos pašalinimo (TRE) trūkumą iš karto sukėlė keletą pastabų apie tai, kaip gaila, kad Python to nepadaro, įskaitant nuorodas į neseniai paskelbtus kitų žmonių įrašus, bandančius „įrodyti“, kad TRE gali būti lengvai pridėta prie „Python“. Taigi leiskite man ginti savo poziciją (ir tai, ko aš nenoriu TRE kalba). Jei jums reikia trumpo atsakymo, tiesiog unikalus. Čia pateikiamas ilgas atsakymas:

19
27 нояб. Atsakymą pateikė Jon Clements, lapkričio 27 d 2012-11-27 22:56 '12, 10:56 pm 2012-11-27 22:56

CPython nepalaiko ir tikriausiai niekada nepalaiko uodegų optimizavimo pagal Guido pareiškimus šiuo klausimu. Girdėjau argumentų, kad dėl to sunku derinti dėl to, kaip jis keičia kamino pėdsaką.

6
27 нояб. atsakymas duotas rekursyviam lapkričio 27 d. 2012-11-27 22:55 '12, 10:55 val. 2012-11-27 22:55

Išbandykite eksperimentinį makropijos TCO įgyvendinimą.

3
15 июля '15 в 3:11 2015-07-15 03:11 Marko Lawrence'o atsakymas liepos 15 d. 15, 03:11 2015-07-15 03:11

Be uodegos rekursijos optimizavimo, galite rankiniu būdu nustatyti rekursijos gylį:

 import sys sys.setrecursionlimit(5500000) print("recursion limit:%d " % (sys.getrecursionlimit())) 
1
09 июня '16 в 17:38 2016-06-09 17:38 atsakymas pateikiamas zhenv5 birželio 09 '16, 17:38 2016-06-09 17:38