Revision to php TCO trampoline

github.com/shaunxcode/php-trampoline

Sometimes I wake up at 6am with the frightful knowledge that there is an edge case to something I wrote somewhere which is incorrect. The only thing worse than knowing someone on the internet is wrong (http://xkcd.com/386/) is knowing you were wrong on the internet.

I realized in a dream that my trampoline would not work with higher order functions as it currently stands because the while loop is based on is_callable, obviously if your function is meant to return a function you would not want it to be executed immediately (particularly because it probably expects arguments etc.). All of a sudden the whole throwing an exception approach made sense - however thanks to php5.3s __invoke method I can handle this cleanly by wrapping each tail call in an instance of TrampolineBounce and then check "$return instanceof TrampolineBounce".

I figured if I am going to need a Trampoline class I may as well leverage __callStatic to allow for easier invocation of trampolined functions. With out further ado:

namespace Trampoline;

class Bounce {
        private $func;
        public function __construct($func) {
                $this->func = $func;
        }

        function __invoke() {
                return call_user_func_array($this->func, array());
        }
}

class Trampoline {
        public static function Bounce($func) {
                return new Bounce($func);
        }

        public static function __callStatic($func, $args) {
                $return = call_user_func_array($func, $args);
                while($return instanceof Bounce) {
                        $return = $return();
                }

                return $return;
        }
}

function even($n) {
        return $n == 0 ? true : Trampoline::Bounce(function() use($n) { return odd($n - 1);});
}

function odd($n) {
        return $n == 0 ? false : Trampoline::Bounce(function() use($n) { return even($n - 1);});
}


echo Trampoline::even(1500) ? 'Yep' : 'Nope';

tail call optimization in php 5.3

*note this has been revised: (http://commonphp.blogspot.com/2010/12/revision-to-php-tco-trampoline.html) *

So I have been holding off on releasing my php lisp for the past couple of months for a few reasons. The first was I wanted to get quasiquotes/macros working correctly and the other was I wanted to get TCO working correctly. I checked quasiquotation and macro expansion off a few weeks ago and have been wrestling with TCO since. There are many work arounds such as only using higher order functions like map etc. which "underneath" use php foreach/while etc. but this always felt like a hack. Today I will show how I am accomplishing TCO. It is actually "pretty" enough that I would even use this technique in "normal" php if the need arose i.e. when implementing an algorithm where mutual recursion is the cleanest way of dealing with a given problem.

I had heard "tail" of a magical device called a "trampoline" but had yet to see one implemented in php. First lets set the scene for why such a thing is necessary.

Regular mutually recursive functions:

function even($n) { 
    return $n == 0 ? true : odd($n - 1);
}

function odd($n) { 
    return $n == 0 ? false: even($n - 1);
}

echo even(15000000) ? 'Yep' : 'Nope'; 

Result?
Fatal error: Allowed memory size of 335544320 bytes exhausted (tried to allocate 261900 bytes)

As you can imagine this would blow the stack pretty quickly. The solution is to return closures which close over the next function to be executed by the trampoline:

function trampoline($func, $args) { 
    $return = call_user_func_array($func, $args);
    while(is_callable($return)) {
        $return = $return();
    }
    return $return;
}

Ready for trampoline version of functions, notice the closures being returned:

function even($n) { 
    return $n == 0 ? true : function() use($n) { return odd($n - 1); };
}

function odd($n) { 
    return $n == 0 ? false : function() use($n) { return even($n - 1); };
}

echo trampoline('even', array(15000000)) ? 'Yep' : 'Nope';

No more blowing the stack!

For another example here's a tail call version of factorial:

function fact($n) {
    $product = function($min, $max) use($n, &$product) { 
    return $min == $n ? 
        $max : 
        function() use(&$product, $min, $max) {
            return $product(bcadd($min, 1), bcmul($min, $max));
        };
    };
    return $product(1, $n);
}

echo trampoline('fact', array(5050));

Result?
48424893876442346868149955534231630311152316586879831768663469768542209496025625521335165836597244986775871359731653944863304801472363186993340977071916545094098397335673370033050095301846673812319519184368943848940208083286841710046697935471447379350531958006231636490517114754236601801475241025829782559539886360417931118962453657701734674670226076209971728976092053885317753609072349073735823517244188123450674446015646408575152721563438720528695200000950089076496921144117143216432888312645825602479454709341393797835166357888263581672355452853869124012486552503932416596193377435247315025743200744002301394585228500268455104719958806656594340592125681513366273489623936710098205543483870278942617415439360839831622538877203695372405175195820803498878614463408507559071691975942963055323977023975579962356660525443011519924497192606177308403911494610046020125224506026847906849303464211582255596044461695809931170735992902861015153948973924760246045409447614027579732580231716105662183345892311470363765765619375852044952237375592745997667408717094345683918382540158972633294341661753292428842087402347931146455707829443369742629955406096433554614672210416043568566713315721328986242009438119615170550083892805000693555351590233960368408610557369747063249171375287938142229602269575258888078115537273321885243640816116313033760859934727694805934472650247398590268106132632051710011975357435411073973400518009267243861234604382480972044372345571394804592046625365990943593155118312928026092849203020843936635478814979107242813498013904401479307173527813374488927846868388843629960975688405420793866362748625568963809336537735196635482323869611480442317616213118017936592673957745954854119905353862738630397953491904711075413351939493239103430359228666385849114266162025489907918597974910444817388693635468572983832473160429177887474388606642754513228627277514269543214565586593047881932646980529181738704933529003783674019143726269073240250043051103116046759758599556492457493255007087656022414606222859948126380313826837273496022239059049197478197470692778763575742323649675518937743998020384086092356484327490394949151360442183700474945898304321062066355143800014715430781407860862440970162255814321544952627961522489938257459652704978558232366966762259286202122152536234765500508950380085381022529769410646695981455932497274422145956223070614311782386939393660505071468075609946312266961804079078124972138751570252042991908322662337184841517195535818561858155408260788044667462475133702274158651640293943156955741104099223849587202623924618562507307459878359309762592535803298228381823574279830281362305301068394370171580376856819398786773168976316243886413852653396055497826310062540076987247412010421678922894559582379982459315131410353844686814801084428315428961052501286596189198414322404856396902069457672137306587727429077418184644185029820725981473585275798688633870939149445242039540994144936753560145261967645980942905198036844963065770953567278843744815101688364553167567561127581285151504170857163788476814410430818485342212602471021116122232536945437600193563274350613219002205135771961855617387540043201574995936521078443417355808962389471634447182986942493573328833479027327904592963332830948909056606878114712587614797355021919494836468834407159424831076501904939674180550971070685974826026825572462514492992573071756584471446779582538562871889253777491503761958039422843336111308820256625552392100765429247159402181090198939792727134760027285582388085697688779314720476653237742989447851866203189262136310101262960823946227816914290542573075004229606139191853412465867836753036378462157616915664130017838805074756547841197620513628237540972492294319305705734478032962949128924196666202655682340324787692515590130551301935088659828410687356942341790891345277677382788831208787364801395111486357308798265828146035781558094135067110230536901270297547242166950881473214274739101845553727897045531119954725288893493225046788944932736466460550726919323972814208640861318915500012832311138673106892856437774916302054198800992266101283582978474791023088963610289841529824634218025633260218581419143652195694797922926870213605428040752771533690783079334348985159752481190866305108822791928707079718613729022578623134006395058165941963834815415900225540158365512962747234118295298072392721688699472738462833608355509413369430747483292086244416854740060940250464784905488189338770945263660330117646978971876652613557429461658723058825915031208985735140615497693407650641375234834094995218262573623896322220855235269130698919365626682758374382064483940359436309642974808514506879129036989811006578121058886468214783989745311306991381502598738427646690529026148074559926029141700545754931041231062108024348298640252182862477489626497023992723452959298403206063199087668949604632790351230972033067574210447769545912131839504735995523543564698434762288745349217285435045940022877153117114056361355516568793184887831573689961226955484323093901470710251285589637162339096014594590326637778408537708815313301255641448290264509028416236493070536691277554818638552346553208672413541183818357851114016689498361821413896379525442756652690413158967535936279206144987763854912793024225936394940295690129089121120860291418297457810220526616453514910819323035995322046111221378283408895173068084562318564077990588079762019973028279392634257796579680892376694383912153702257752771918240121360797334802574067759177201695444664008395141273331798769390706217716413944484444589448011804566872918201233352031246374079426621952856774873141762004642963805009605909976650733467147648933063451549234764105261843727285344810237038664893806272788248667617929188856335934471876757762121375528223069436338430636550586312429972101590001624825194534053466559441823558494047711923047787608650174147236583346033499704371720807668032648824335082469921765890357796559326553963051584575314243179379693972869819018936515241128344111174643025352717517264399068943122072909168503889489366305203869840440783566583673872512529607991028619785374051069353232798743538451929474739656942294561359950279354484262386048300967384230958861468226703153885216880543889184923233329346644468452757677009730774828691754812914301660783522852525684240191438648246859144805142924667100195015093959485990061146668886559862309819174810279322086728633972728154606053167707643070032164693171224226003284900895506902979108769760815523818908193387378633599962338329201288673602475038425763910335696933668401126584246627457560953522086694366649469599705521441640238122010959682479428036962415722220141394447107341640961359500927881874233095198411689068446492958685137714321262410692218565491447540332778657853504520774359829079460075117251206648241533763048331739049003142679483361884913145518268997761626564746070642120683866637049087132932456214339322178452985208536699837965699909310064620090804584888468392476355755579270080782553655541381943286896134122662506174668761696780529727626382334663869879097172088652428923258543798284963386781746966688860322027736021528016691959550581844902683467447609407368122794497183432069868909471472548153656903880703201644425109624545859826873667750937614607390493457875484953740767611339667576173714034455565432308153130757930008532562324042807264432614157844822751708067421611502291046796482944889562484299548170367202226348895651943485134487355907416500408163581341989736946778288899701341554759826542507320619287649549795982662920054235475749643320872348617927891303979446402061121132359483927554056402873178493913139966737132973717633632447161627037227392256332565547672908601616412069162541656417328547927835344764379080034006834438837309816235465641185216815046674945763955984713681604516254849662824411306353793798089671114185280187265849418052077836852589180241592723184733541106406465656205948358954948142025233991272905001141355021729920577475479281289486806270011744359500435621608814756150544407957227147107089215203809044297767994104686800618204519792063487603872622575538947815450619856182485749773834231277713725309254568969583149073554526597574846552798676406462337998787339779028992439990039978154586413759133622409437489561164656777421746380264056302768613928564315667912312952457404411495519474886250396579083072312029449210229223734219955586387114225996549617982828293430386694221527613218115999731321291884322073808127116054283436992190175171603278221120478118125795564192351195970923490210310910133096302509169175624548014311817872937471722034686941769631047594296358186560148127293467958839434265463971529119297056567953684958757245231554391244311041212876924918500484087772698403206170331941238143489798776660534676579046337828982028986348099030601184836047434217855703008400176583770452171688793096489449429186708279868381214066539707277515059120768682704305155217982248302399219666594196559372775947145581773723282195411033360764337292946984272715506254608876131243628417716054202032599008485959729298011133493587411121592451061195248871236550219323568794733198388938084043968597320732717910476328327887684545483577062955807065986440317073048021931109482880059179684697878805723379654977018391836443141027833877379573134035147846614695719532905855359486154082235216657769559165736626734582602844219961653790266071295624034376769110677927593476162673165371870321528606055962225071216770606048742973083597090117219781320947530791012971233612874212167300949205392589536160373120473483108568345225335577313624485693021092445510802644688591070751584819925697407862940653022261735482476498456623897965943740384974312102003102503405987723190936549669116934059002978404863724434029651459171929972224636473192846126682034744452198659199773243765555394223202793062777093231567712374298614503785227247044790390230170449231471025389935822203023342537851424261619334224815629159006888149337227458290876318073016643545061947091539741062518116457909282507014366747914604640619597780018271697736234489832448906487488167612194968404133122879631080718761096322629749242740599130685431498769606882708624503872378150881580793787863737584355460103940532518865937858605854476146840248883570271489049276259843458637015215238959285845598888570553863679704803156416650276687716857598414761640580833928733883633835389587148355501394145096219531824605734660342901357825854824533481203519236387571460898657123958733206267932786756738047919023782881760608578646872699523991805943926237776113774398337350917182253520526962590153838195949497674171793321672290838421458771652486169401420831215559578522629914795737160039551091814038045014141164820901176264063896563274263280283566146499227688707995123583313957488864707245532192866843267707404232105194327568792851170384048440120280104065824324895974735080562974987135989427850162706790819742752770673925751139449717572950066181333226422371275841399550790779378722199692256665985844973214290417466996736463656592057379723789125163155964154625281239640046452862780603936207280664294883639688906345127219732436103075763451035422059632678374543779848932298460317103368289281025974169671272176383711807597354081467243350813365849007681882657888031711208469929623879339045017847389034606030926200455252399928369014924250363511229402299134698234156077158889592184980239170939501976466282865503049323617696621577333707865541600453933439576081214463590926434086384747290541542956399056962056229808127723780675081863094174281718420041021021738137563902621285687570410794757069128146157463269445164824140810572619018262027820086204868288731570345974912460949952968977302815206146117344553964793868988818958005020677285939064713111149888845649122939779041112120103892513478651508392217974531543376928740368199784888020421470272916459151814416040117267729799572111113430173741099889364201242246402948747813374749761369635840602934801976235850307624671917843079911771168517196726786713522653929181501433771224598604194250156742985226389799732276295274717715643984526333979308207645737104136935577625600314512836136271115660651134990573752618766965589069059676285129729732662084619078729162659020226938244891662847624627441891710694949940459227354409221979111240807882850754281611301674487520083457930422881455622420345738892296143055690156793547311809505543345371574649444927866169060334457904017188783393683115952245289189776402314456755190701764830857379904237952920537930837101480626961392776308489600995416134740406176538114983299708968857197075820121096069101496947802184680898394989647393102640058875148772532514830965041682985531620318115129285743608361213991132382738975462458617395619613187809486070987315723381903277922746195238195752905633836870278707046586517135634008007513341884363874996422486463455702922902696818946264796634960559597402803593333400937678136319820912555570462398816832063531837359091080659789751716369244408831250173156802380436362475465330236414904123853473096649894512457823362094181780912054103436914017980019455398250827412935061689262299438765336556444028008141319555636511769936177287956920799719676548107901075208403027364066932296087105441105308233895669378571717426107611042700373090786826809357637920085583810333407384012506569539408308629504276425574350546071484766182755577320350092810707004993335303482992232100488260296389559828488542505497559354326474562253495080783576216166234312096015413769488264005498554434439616686883956930058964562125319715331423528773748137428825047204186186648001874137240953303168262859474441442364125373820078661928648678801874400337808524510807407292324770665786283834004819341447708739358303385371869359181326822754638005614357757088482815667552921043175589353835686768950622306463118223568914503995372430337670295660500254935570486455145607978192630525671852896912768541854734619733961476555472299897874821466782568991296975858100442257963419860785714800116609046347135848549904523395244469912871910348036936480662845699967192884116216409488999878911387634858801666284371199007716171100287801287860307049091775742741060304901180847344576070072887286804106341674016729286661940027108142630650637758836422914341360842554401092646434224130444935704965676057926041362775924786583432602640154170852804440351577248486945824032635382183769612125595063262772078130555155831993351782956959696608968709544714953809612896233163746852346991803469348501042522744077168092081901244451643409807267936512732460961147488822964796202735500820301014818688579847672354195891890954086978215346979986227790640259391170662626734729071467762656777507642626883458780766449547354683123105196509097488881829974869470326766694168376589702024017800739547467144404227676674351665468804862538125870908797276169065403720549323187458536526037850524207766074436322836938304257311371902601828532364832899357200542907831617866643720527906804105301881269555094766929366731873712163397632411978533831454925115992025126122572575243124108927948251985272760453761040442900279614459490962271192658777575358243219372257723044331255857441455137934349703756882320673204480286229329737047565154624737913976783040219275254317566702293970510158407465954045780946698855495818114759070368009209396367465717100483910841200597758805510253615045052314093062210028464178602712271706991877647528837796369531833743493455280297995225803903076950864895339985477756937031227397457811500378614493909582380416368640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


So in other words PHLISP should be officially released by christmas eve.