Ok..this mail was interesting! I dont know Guile or Lisp or Scheme. But I found the code quite readable..so was able to understand. Tail recursion optimization is implemented in guile- which we can understand from your example.
Ok for those who dont know what tail-recursion optimization is, have a look at this simple explanation at wiki:http://en.wikipedia.org/wiki/Tail_recursion Ya as you said..its more like a simple goto. As the recursive call is made as the last statement. The function need not store the return address in stacks on each recursive call. The optimization is done by returning the value immediately to the caller..thereby saving lots of stack space! So why not do this in python also? :D I know a little bit of python.So a few searches led me to this example. #This is tail recursion implemented in python. #This code was taken from this link:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088 #Have added a few extra comments. #!/usr/bin/env python2.4 # This program shows off a python decorator( # which implements tail call optimization. It # does this by throwing an exception if it is # it's own grandparent, and catching such # exceptions to recall the stack. import sys class TailRecurseException: def __init__(self, args, kwargs): self.args = args self.kwargs = kwargs def tail_call_optimized(g): """ This function decorates a function with tail call optimization. It does this by throwing an exception if it is it's own grandparent, and catching such exceptions to fake the tail call optimization. This function fails if the decorated function recurses in a non-tail context. """ #see http://docs.python.org/lib/inspect-types.html for stack frame object reference def func(*args, **kwargs): f = sys._getframe() if f.f_back and f.f_back.f_back \ and f.f_back.f_back.f_code == f.f_code: raise TailRecurseException(args, kwargs) else: while 1: try: return g(*args, **kwargs) except TailRecurseException, e: args = e.args kwargs = e.kwargs func.__doc__ = g.__doc__ return func def factorial(n, acc=1): "calculate a factorial" if n == 0: return acc return factorial(n-1, n*acc) factorial=tail_call_optimized(factorial) print factorial(10000) # prints a big, big number, # but doesn't hit the recursion limit. def fib(i, current = 0, next = 1): if i == 0: return current else: return fib(i - 1, next, current + next) fib=tail_call_optimized(fib) print fib(10000) # also prints a big number, # but doesn't hit the recursion limit. The code above is well commented. So if i summarise.. what it tries to do is simple: There is this function factiorial() which we want to optimize by tail-recursion. So we transform this function to another one tail_call_optimized(). Now this tail_call_optimized() function takes care of checking for tail-recursive call..and returning result immediately to the caller. For accessing stack frames they have used the "sys" module. So bottomline is tail-recursion can be implemented in other scripting languages also. Its an optimization technique which the guile pple directly implemented in the guile language. On Sun, 05 Mar 2006 Mahesh Aravind wrote : >Hi there, > > Grab a pencil and paper and get ready for some serious number crunching. > > I was poking around my system for something new and came across a > scripting language presumably launched by the FSF. As you might guess, > anything out of FSF has to have RMS's blessings to be a success. This > one undoubtadly was inspired by GNU Emacs, and is built as a replacement > (or work along-side) for the common scripting languages such as Perl, > Python, Tcl, and even bash. > > It's called Guile. Like the Info page says: > > "Guile" (which can stand for _GNU Ubiquitous Intelligent Language > Extension_) is the GNU extension language. It started out as an > embeddable Scheme interpreter, and has rapidly evolved into a > kitchen-sink package including a standalone Scheme interpreter, an > embeddable Scheme interpreter, several graphics options, other > languages that can be used along with Scheme (for now just _ctax_ > and _Tcl_), and hooks for much more. > > Now, Scheme is a dialect of Lisp. What's Lisp famous for? Recursion. > I coded a simple factorial program (this one comes with the Tutorial). > > Note: `=>' denotes return value in Lisp lingo, and `-|' denotes messages > printed other than the output. > > (define (fact n) > (if (zero? n) > 1 > (* n (fact (- n 1))))) > => fact > > OK, everything went well and I got the answer as the tutorial said: > > (fact 5) > => 120 > > A bigger number was met with an error message: > > (fact 500) > -| > ERROR: Stack overflow > ABORT: (stack-overflow) > > > But what surprised me was when the tutorial gave another factorial > example. Its called "Tail Recursive Factorization": > > (define (nfact n) > (define (loop k l) > (if (zero? k) l > (loop (- k 1) (* k l)))) > (loop n 1)) > => nfact > > (nfact 500) > =>1220136825991110068701238785423046926253574342803192842192413588385845 > 373153881997605496447502203281863013616477148203584163378722078177200480 > 785205159329285477907571939330603772960859086270429174547882424912726344 > 305670173270769461062802310452644218878789465754777149863494367781037644 > 274033827365397471386477878495438489595537537990423241061271326984327745 > 715546309977202781014561081188373709531016356324432987029563896628911658 > 974769572087926928871281780070265174507768410719624390394322536422605234 > 945850129918571501248706961568141625359056693423813008856249246891564126 > 775654481886506593847951775360894005745238940335798476363944905313062323 > 749066445048824665075946735862074637925184200459369692981022263971952597 > 190945217823331756934581508552332820762820023402626907898342451712006207 > 714640979456116127629145951237229913340169552363850942885592018727433795 > 173014586357570828355780158735432768888680120399882384702151467605445407 > 663535984174430480128938313896881639487469658817504506926365338175055478 > 128640000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000 > > (Numbers are broken at 72 column width for formating.) > > My box is a Celeron 634MHz, 2 x 64MB RAM. > > Now any one with a common sense and basic machine architecture knowledge > knows that after a certain limit any variable used for numerical purpose > has a tendancy to overflow. How can a 32-bit machine handle such a big > number escapes me. That too, prints the result in less than > half-a-second!! > > Or is it that Stallman really *IS* God??? Gosh! Now I'm starting to > believe that GNU/Linux _is_ the next best thing since sliced bread. > > To double check (whether this is a unique feature of Lisp) I immediatly > converted the program to the easily accesible Lisp machine I had -- GNU > Emacs. Note: Emacs Lisp is another dialect with slight syntax change. > > (defun fact (n) > (if (zerop n) > 1 > (* n (fact (- n 1))))) > => fact > > (fact 10) > => 3628800 > > Yup, everything went well. Now the other loop. > > (defun nfact (n) > (defun loop (k l) > (if (zerop k) > l > (loop (- k 1) (* k l)))) > (loop n 1)) > => fact > > (nfact 10) > => 3628800 > > (nfact 500) > > Oh no, that horrible hairy Emacs debugger chased me away with a stack > overflow error. Ok, so this ain't a Lisp feature. It's unique to > Scheme/Guile. > > > Dear fellow Linux hackers (esp. Lisp hackers), > > Could you please please enlighten this GNUbie as to what makes this > miracle. I am a Lisp novice, but this clearly fascinates me. I would > like to have some logical explanation. > > Revelation: I remember reading somewhere that a tail recursion is > nothing but a `goto' that can return values. That isn't helping me > either. > > Any help would be very much appreciated. > > Regards, > Mahesh Aravind. > > -- > And the Grand Finale. > > (nfact 5000) > =>4228577926605543522201064200233584405390786674626646748849782402181358 > 052708108200690899047871706387537084746657300685445878486066683812736337 > 210893772787631279390363058462160643904478986982239871929708896211612652 > 968321775500399242196837031469072644728787897904047548841622152266719284 > 109692369104495659717363529484002238403811206448202308576711045023061748 > 947554283097617817240408053248099278093287840554861993645482912118762582 > 488021891739779000502132125980436392446264607705113588465951086754705858 > 339246552255890354744359883473831789880346330084586315102090915099356538 > 200109330479657425567419309170551728052002360750859911976352287559079020 > 433697431235069168312119244959715562674075214621989862330886259983028598 > 648575787494459631152869708867100462684236481789899054546908613916132183 > 441741488071862344481148312094903611965468727677556178868287202691048140 > 924564103418359756042764581615131785759016610717825441569808833593727299 > 956033713712004710494376562911424886053352994996423006999722049181201008 > 190594391406750532650047755338508990979451015510914869070044071195723360 > 262433681323302187092876991968066565697527904222582678415610833764257810 > 326292026872110702746813943511286015023261906499591718973641763784364912 > 197091098409445148953589591038041769419566578348220717491055127526391483 > 811720526048269651626427100949193933326610301043605304591170145572095847 > 143537219482466867934673759048722681334102078609036571088063766162497495 > 074131070774016821805859455264451714092774692300626975113460441745679467 > 358287822616295842486751573791729427241787831054298582451175755118845065 > 744248275746608002385883784923962473687615070157677258983211286322955370 > 449025163879251275908417917446404669135310473479844649961545955420139963 > 173574763017400367961929199421907628954456562617670417995381611333873128 > 235115341525813090879158836383516647972259129442706535571425117373238072 > 326329581217979166796923296870969239010032555747890550998074870610472306 > 461959849552396576122086738665141716993075576918979026751573420758647963 > 453384468350859654907273263219105040642897130962245051620646694680988699 > 171221274045040206849232662417601329102278666872703052847094525268254966 > 177724996452066998369259106908940826374010434983715911264558222806063613 > 941153443167717699343536642849282944364147696158819936613882555774877099 > 370045947539078451490344345211745605940399162684446976618213874707053255 > 595779331964609966621453775649354741697085623892147732228655071824904300 > 161861421927604523076706211429617672747041236161072200097437586474927536 > 651495321647808490751463300710166913134206628825626182838658369836321087 > 607104275160733483477884147967324270804108607618412818883071150989821353 > 384066106521470870468747609954274736735094515535997690403673533855510525 > 716826503176824057439934148623923319814325791821933218989404508650136109 > 980983839931109963559813280010497315885963121318538012050467876429106693 > 656004373056334319848790489985247012933007893445328681566797628804955328 > 463860201334802652798369463933849956750499937078147465615434389304313842 > 378789818478028860099710886956329883477118631223827859636531151323779313 > 736473974293694114990287519722279995451826154882989511519266821124513553 > 184722099904353559498872999220350620398160110863762365397821723802378466 > 506736245106350344231873153383082120438047109994192278210397475527174160 > 438901697239613055493718448361198035658960620250090936643993601720073836 > 133544050943290724765189095025077246758419894122246593921631163520381473 > 624795285397320893095334219106357028055766297201565565107677808059334536 > 311218295617928876730028024509321227788529684182082617784769556449803856 > 912757873726780409591587117339711031652326780607981276092461735041201826 > 668742628053852758439791676090077433807484207511851191029219603393762809 > 867536650852128692553215367879325218825741018661370543289737358627253701 > 785588066398513503869440396049282588201804191780736496938858025977583988 > 920143897471654659735108526057062344020696370656601295357340435829614734 > 272758056308395106673753492596595185756469397232182757800032505938953038 > 205396975588705115430739208274224405162997087395997684612062466290981123 > 680125798912848025050940289169597650793954371913113793144274051355996303 > 756422145272943417972461875979640742391478389935415658347161568584990367 > 730566113538333670875489004130919816763307490415103375973072468858392469 > 417155482957307506185058815819595289926602256269034395733134506669729521 > 152306686962279209477799743365744726734714089280714112838880826933773780 > 772931041107675136394762006108580405960196390580157610023374638693522283 > 858014349571781255814458629300424794040657368598620079146045902554139299 > 500880447103847589903265480973381669405000854527237135713949024638203086 > 685418028383175276680642784895610057558599917189667864491540635700144971 > 942498789208597312542755675145752063991181507363974831024907938417256534 > 218942767691165981534300846370877695102954151365517346750540152397060425 > 717460010899684404988459854779779050316325684891565572310064997264987214 > 808001817703577015029830088794872438877188844168330347087232395053776422 > 329440957732191375823716739247042167230022568831357792303946889006624661 > 825326584907244067670249395796972174674855629981831496656117439976804820 > 941662574638796603051712749251192263676153375243816562173307716501295209 > 887548564671318626023876199643348679615144083289020610828331808912213258 > 536828564699160079521051669604516954306142123057430068772174071554732179 > 575770175959676405638127291538675136987123955705423509992286059754699621 > 861955313541321391264366769004654299968116805507378667706659880270629725 > 020018828458861453443687714553613044144656133690928627482769819468364805 > 509529686817587148599729730823329240947770852752799233048927196333147515 > 633111927461503892192906167806079013834511370663006843762671998855151436 > 812661373199121032354697867564212106248990055535640229243458312642310383 > 634167817199083541404117177401859506066741983481433454442471914368282256 > 543800478603905759224170718026706468754542116269587467953985407844646541 > 403817511499652736211235408801669902801490332251394608326681709307138688 > 265499773742861277894177847526813283718187591036421408817832207398080597 > 142032853097214430418454591830028334087057831382849732837612861829271367 > 451618973662072373961327909449840141544083040744053930675407671261825475 > 971308434703113898156953659717885640227506742374003236218500947652675219 > 419012413874782798834264708736168124853844440127725210500722793158530962 > 791211311601677720779525726138002406844218854535371213419022363796840123 > 852552886071899677256942274333239485950755708390618774501596521844149981 > 554761075480080541923184369481917326314306035483997907833072676367290909 > 807728273558543480322600674725370977854645677611818073674243673917698637 > 580721458597914850337005929949637933691002834445580898380540176354037371 > 330193112930809582876121073803748006602697678428883582657374865567858688 > 220151430462496559957603797686853181923658064691995840718454936069221697 > 761375426622396586449897709214781347091279174608716302208219814346542450 > 657312626830895790310128933607886441072301848054003731360142162291591469 > 920198841482900144143128009031021078333050902384357267794161772468734115 > 035987000031510928157003310817274156246804329772050704504566838986263017 > 029893011453644774168567325123303764778817490360525726055206843706161165 > 397551325413693038677832672082273236642492064323630892687688266509396918 > 616832717397574795529932424061869924203637819294853680980352563310924482 > 152692762191162591458863936770346534803678871261333671169682264509149970 > 554485212597518700847200256746587524039320610459030700394382520193831024 > 809290196846024721712983216282379946271253663599718983744250991206736883 > 837382996538920306628430745475590742353452740292116060913463276847495220 > 460104095756073481551016772031875800892244947529220310938416615888235849 > 939317451499143955573576415841854798317024285239654510875254254647772945 > 952303609464165419977979471368063449159987724091764431373711785422107405 > 721211668686921532404900803842059211926228754408982614789081236989563670 > 808046876285244998974408556779694569090423405303559435246407516778739531 > 139286986143472275721449468918960932943754767412349077927543383494123230 > 600787676100899491561269340389211483702171933876178233703589258171128695 > 634500013676198971454009866434619221976769759300105552251989130021230217 > 808319343308804465929545521659118559392025797811229520653573629144784049 > 464745650031154980720565803606673808895727464643754280558193222993050892 > 878068745374013271002744283179253550034515366931721120882276039428097886 > 457273069799712856495769343540040307284405817466483766584980399589642433 > 701834541517202853378109041131244624329033539642966511094828368845801275 > 887012931560992250445181254601132749860144704377573138810013192761246761 > 166148335289355575031060184497889943782746138546517082416131676814639118 > 700008128451443414067399854300727723037581116135110943556148963239297508 > 463831529302635825353617848375585196669499722519355159538072078386151421 > 302844500517952397609684331982925989216232235823963902625488568558754581 > 983715590084478600867459457091181287932282220517675093718661100131936258 > 452234939498295111992808378605235064127693375481306095942644634250776011 > 473342091391285416281831722621437830629624081493919971875281063673488766 > 784816023427432300271581924041876865458265193619906873368928867151338402 > 454861109824820044827217994966587122571744290449167811948241656315603034 > 738333176651212180527807959582202983306119451640194133155503796629802153 > 576807311245305859159697099739880557435500832790718449597523535946443547 > 896803721263445094230702539951028644582374546777610135569162123097522861 > 520532139987456730341276765033696366823066655520515624911325289261558638 > 685031008491809205076806582659152761637199286942583506048597322739492860 > 802606406275213410078018151056237879262120394247818334394338772063958011 > 158090841907943201951782357401905465959902896177117761952703540511937272 > 297222484420804400987503694112776865930221330106250318620851450764210529 > 805088371979860525577503039496061584428388468661375109684415673098380793 > 943495700130292651779571206255558519513135740298975892834755253344098589 > 114006944493084328740050155543325877938950802411285387587259451364008383 > 249444713464368261481954060041148458702340729266977406313258786347906676 > 982661815012561176922757152912491648217023728844163576009968511009394114 > 446776281860070722785223149410485643962557968082212899357992622085538892 > 211647652208503677064764914961337893537615373915691778222377448376141202 > 533426225080073005134734227714273331063459718032402442269504580905393266 > 891036193819988388440362317952824354953624896707341559480676885153210730 > 644760778596286278522836572445643064490962775171726569542383929419584095 > 272532816595725345314283896298940058865394868241171139296273569389734829 > 358546502786894370147983838260020582088535170732162887252145222052659696 > 149621478848401290045077372524246050743396608181829602960191963141249985 > 384220176951103613805617010163577435425311486693699941309409083682200719 > 364351119785927824934914770521872265461091995972694391524004679011736025 > 210300518860803370848401148102463512882639861700818048883807502035214483 > 487408491547187144788578095745154995050050707894288428884100278777774559 > 811323199406241765321486863165817367744100840634369599895192883108691245 > 178663425593534582425894113905164694403775626658215778459368299096797545 > 483505104736337708391510338546396027534864016352046338843423467149356414 > 291608568467248742447820551137591682364722977936129710803025309344781155 > 277375404589689903548080583093812673235935630985465643762093853710528083 > 446071890760033887816180198532737594985669167047034484383635034163683252 > 664032241745194766781404283193274828518821403443193844454754567652534196 > 591943321325854322700707590385652396682271713000091891220508451852615146 > 279377175975288529786379317112125295294433237579100729090017035587637986 > 124802814630939443919169501293363150452851635393128685864274372961094461 > 012356048774398632996118997559659966087490492711676852686753359912975832 > 090895532964095236401160600784950053778927837501473441221237779077271341 > 466474044898375894876754232945468993542203416699613666989765299785807958 > 990558640503885070831373330768397668824636809923552197272418317351276461 > 891123804858831155694778881017597089776821496443403179244430851703036922 > 141376211943886419895083603393064590373618429370287107583219666075461137 > 610763625439286143162428907540210822336200123093847373122203742690338385 > 799286785729394341682870537633740919381846322611317409342781179188916424 > 475135434784460405494553798345561633538158684416920545186989194341753866 > 639003357567656032643637679067216266203308784255451572081172463812515126 > 698466858872090131448616325604610195133718145852499881766299251421450147 > 102061931903736713803476634310297052224147850301882751063474462412587079 > 373390850957577243167350668850942087615361644404437558601606258370913005 > 741620652736709418886679645705507447247141370019681652159543806985159994 > 833613575213221061318847719266419423953514122335467464614917430134758660 > 373381765326045574029254722793602889261893858996956568767830171868739887 > 638876259727439760628132634466476794136797261849333950746658204416779898 > 066042039371166663366962825693490973483911558690048560325122192415342685 > 223693160367654910477027335215401431683388729684054432969676840360731824 > 353362248654338235981235441675146083407811666618587817339806241992545778 > 534626780390399375578027599429572052810437756669793968381093411189594757 > 662201912175350936389854652830786923706625123236843902355876362283246571 > 611837140788076611621795178879728018415720196390844002690374503811927971 > 703144898718150313199921115639083030172880126106420620053592402782773939 > 180263917177201361259847769339806470637630226088853599375950790887890817 > 918021957680333819686051204871076108748984115687401599530206390981389932 > 610955388682640840121608310405259745392515764037328890867369483664047346 > 227085600408916107822219434051797945501553476829668553200975019055814199 > 145911241815010622556274112315713773586971943741308220273838438159406385 > 713879133375923623304404534872330472406687841333330478989952552214688479 > 738135680839956445330052225513201552677688954127703292786708274900411720 > 766631127836381523435476816631211890868649913802362817752759460612118133 > 420547918016192203469127603819005280123439735982704614998145113246181956 > 585282320446582700820649346802515565112728220838115631922565099452012226 > 666032260593962470197076685803962869755511151899730490850517587653067857 > 580006604240668941706203038467858602573706343525995868850886796540044651 > 877902089429351532173167501137380314660346424294890763222281337632999196 > 413365020286272892680875600366137706074635755150790879820997226601304729 > 078257469081754519524055737913131131706173231915986739715883731081689169 > 686577041506955129476523861348157669675803647620052890602227445317443054 > 984028630488508695577615286503260809411606885706988947620464785008843039 > 731074127741919616974505171103290828152012738886634226314921470902200169 > 406365048120470360167386022906716298164111982022686079613247395500575675 > 645682047546190404230110623713673959956789408847059768595145050172415177 > 460173514309909726155093783347200000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000 > 00000000000000000000000000000000000000000000000000000000 > > > > >--------------------------------- >Yahoo! Mail >Bring photos to life! New PhotoMail makes sharing a breeze. >_______________________________________________ >Mailinglist mailing list >Mailinglist at ilug-cochin.org >http://ilug-cochin.org/mailman/listinfo/mailinglist_ilug-cochin.org -------------- next part -------------- An HTML attachment was scrubbed... URL: http://ilug-cochin.org/pipermail/mailinglist_ilug-cochin.org/attachments/20060307/5d13635f/attachment-0001.htm
