dvanhorn @ λ-calcul.us

Fector: Persistent Functional Vectors for Racket

Tuesday, May 3, 2011

Based on the presentation of functional vectors in Conchon and Filliâtre, ML Workshop 2007, which in turn is based on Baker, CACM 1978.

The library provides functional vectors in two flavors: thread-safe, type disjoint, and structurally equal; or fast(er).

PLaneT Package Repository : PLaneT > dvanhorn > fector.plt

Here’s a comparison of both flavors against the random-access lists in the RaList library, the random-access lists in the Purely Functional Data Structures library, Racket’s hash tables, and a simple implementation representing vectors of X as functions in (Nat -> X). The benchmark and numbers are from Jay McCarthy and on github.

% rk bench-fvector.rkt fec:fast: cpu: 6.45 real: 6.5 gc: 0.0 (averaged over 20 runs) fec:slow: cpu: 8.2 real: 8.249999999999998 gc: 0.0 (averaged over 20 runs) ralist: cpu: 18.549999999999997 real: 18.949999999999996 gc: 0.0 (averaged over 20 runs) sbal: cpu: 19.700000000000003 real: 21.15 gc: 0.25 (averaged over 20 runs) hasheq: cpu: 47.95000000000001 real: 48.4 gc: 2.9499999999999993 (averaged over 20 runs) fvec: cpu: 114.45 real: 118.64999999999999 gc: 0.0 (averaged over 20 runs) Normalized: fec:fast: cpu: 1.00 real: 1.00 gc: inf (averaged over 20 runs) fec:slow: cpu: 1.27 real: 1.27 gc: inf (averaged over 20 runs) ralist: cpu: 2.88 real: 2.92 gc: inf (averaged over 20 runs) sbal: cpu: 3.05 real: 3.25 gc: inf (averaged over 20 runs) hasheq: cpu: 7.43 real: 7.45 gc: inf (averaged over 20 runs) fvec: cpu: 17.74 real: 18.25 gc: inf (averaged over 20 runs)

Filed in Announce, Racket | Comments (0)

Chad looks sad

Monday, May 2, 2011

Filed in Racket | Comments (0)

List challenge

Sunday, May 1, 2011

Can your list library do this?

[Some examples and timing information are below.]

Welcome to Racket v5.1.1.3. > (require (planet dvanhorn/ralist:3:4)) > (length (make-list (expt 2 100000) 'x)) 99900209301438450794403276433003359098042913905418169177152927386314583246 42573483274873313324496504031643944455558549300187996607656176562908471354 24749287519888962987367109324635042737311247926580027853124108873708560528 72283901645686910268506759235179146970528576446968015248323454755432502927 86520806957770971741102232042976351205330777996897925116619870771785775955 52172008132029520461794922925929562392096579787355815866752549579731314480 62492602618379413050805826860315351341787396228349908863577580621046066363 72130587795322344972010808486369541401835851359858035603574021872908155566 58060718646126897283979462184226757934963889335724758876195913765676241112 50207087048704651793963987101092003639347456180906016133778985602968635985 58024761448933047052222860131377095958357319485898496404572383875170702242 33263343689442329738187773315328694421793612530190786890360366328316150272 61399341528040711719149239033418749353944558963012921972564177172335435447 51552379310892268182402452755752094704642185943862865632744231332084742221 55149331500271775006422882621182254934960055745733496467848326918095189595 57691745096732244177404328404558821091379053756467721399766217852650571698 54834562487518322383250318645505472114369934167981678170255122812978065194 80629540533915465747994129749919034850754433641450563165739600669338242731 64340395801212802609842122475142078347122248314103040686037196401618557416 56439472253464945249700314509890093162268952744428705476425472253167514521 18223145538837430823264220063302513753312936516434172520625615531179473861 91429047614456549271284181751835313270529754953705614382395732279396730301 06077456848477427832195349227983836436163764742969545906672369124136325932 12333564313589446521910188212382974090791638602323545095938876673640322957 79939011521544480036372150691155911119960015305891077294210322304242620356 93493216052927569625858445822354594645276923108197305806280326516736449343 76173240975334233328973028295917356927301328642331175960523049517167703316 37095222569524604021433876551976440165281480223483318810975594219604764793 88520198541017348985948511005469246617234143135309938405923268953586538886 97442700860702863550208556202954935248005079652156491968326510674410096782 29519541616177175429975200098873073778762106858907709694116104380286239504 45323789591870760289260393489826100774887672852918106468489143893649064784 59121161219330070790053705904218801285655940369907088803296687161165596123 23319983109232250828661803218804394475729867620969358197843859279692501233 26935194693207724335527365566248223787833888074999276831633440318604463618 70378978431303284382347041094430659147192834119097518523921232767438499056 15636884329390394420026175309768506051329371014490863961416205560535473355 69926700941375271829142407234267937565069765567475934101310225342830080409 07958732954421355130730205017159842423076046920973290729014160635396088055 92023573768856478522400927771114891344924169956071717862984365339781808694 74106751111353523711540436599310889697485658800887861974934357929246204051 76724601225061840401196628987267380307049836121797448467910074784635619466 48292247361341151355671792917819680560537264841411283478582412591219546011 84412409349782963317042002530418661694962318735860652485410222211869544223 78828918971208051457514136196480536972316457056499847953765717454812859740 60773391587753323552156094359192751993510142222469630170137174193375049192 95363295101115292951836282819191821651676455946515828048984256116748150367 80526787866271699964929694937704579487614662811092998202073701333032445100 53853785511888034741481986651145793226849009930002367361685552941734420599 25371965244997925483159343706343970371809611470323074186985035054722289027 17485033336832830028113291084169315045738993318393459329299494279601530975 61187089189295284490742432847670062431711716227317666067961019678022045645 89015899524704741001158110963633731329388356868949408759334176909387806398 58464730058892817599884447748613006315306876007008483726752778977735683004 27789027721056838330214702797285953363321105640642639097245799496861629080 19604141753935768876587992428549912151737924270343248648414247456838889541 89324145098750575940301324969754169695533029688021930487416350109792003621 02387682751763699809776149796360967043481401241306835768799049974365962964 95705459524735382000363770324894982103331332913562315169854410415317054193 92823472339884845355217320368808831210094394143493828220354965028153075108 70986046812248029738256312449893319652962023726085865090503079933086520012 31671915182765742095689513136184095412121473786311042897717861448158316965 84876694955482625250496122704471471222962027468236290980387746937698735894 21254417923552983874798304502539097887334697326030975441564748054737327327 67248652759034995336354126953900458854988683574927864615252040800490114785 89228908544335399699478086747161351978583857145642158317119300411798944079 02683463575503398880867251278835772976264992138274365739929273022387925769 24232785487201297255386071968303782483063725899808484638503828356258403917 31187269438146455365169006253002321759134308475521590147529914921529694436 23669108332336937679931382092758700242462383312182367152367720984171877038 60172308522448043176333602759733161201262248323085329288986154559221427378 50741097882224472951266357222556716977940976734154301728926833263507745121 01678691213344656807397973727114619192999381181788275414217929268837902854 30909942441260511945849237909966329550263865701114884142266162969810073652 71092850457947086150809405457779786430150489995863416470052822056278600886 40257094324442540440342431402038120748575379990160664655209869807905893473 20243050635907363821521280600041827529325485247927904235727598574209554632 36383093242825071151880177563373981152376199468626327055063509985125433387 55946015409008620142936256737383316930823288543270014874766351188308851737 75268819526360165345900556160767713453617655450974424979076063906093300028 41696484759402704666946848659363642542862524164483665217392258652847424495 23633023053114134493323398223365516114314691319001704882268365259163997239 12626616140205707996727383529597479125488961419287261259757561701592645823 54115192217725391965103434479368036905700381305655786631101147631318957155 63365187277579919088628907654949520194749221488514170792523523942938017011 49485239005844358329748769279941586384640877265901749104933238853465429979 25390056131156228824114719215813721012026739964862283161043028726873984033 51421202995166108461931646880759445269652485700705544521525474934504348529 17987512185973647190461515413582582139040172118295702327537027389787793506 90404493855358765050355715587287320159688506133114547710157569937544109749 33741159911991149627268017180389509078030411844000755854685609769656695843 25627283327416418044590727844680051360774154288412712456353383625469068936 43090206821675045981932174451336291385398315456061045969260450878770030418 45791534782917257628106327221080358260609045724606192042375803631472001587 49075361633785243462298769917887808671453928846572417223504887766803869453 47458883190759735529280070924147137069664702953070050708309141249277140477 61934590073152062336342261281370745041625204734495974156788820038454467743 88950379192344594171245510231738995030348421937088083329709108176561010708 69315802069506009642835204664733336116347666410631124706517380251059940926 69089840466632986136488548712306599035657723276676960571870572768143949325 59371368029375974604116075641599919402266794230681485723361363592903676841 48035832809312750680111157161506276155660715823661226854426833027472584929 48758520897908509628352355279784914755637443184839934746333003309724970128 08415900969455190375849945750379465019166009861502794606130794726898507849 61030388484603542339217544950587615713034470041582308022578669330051212683 18460095102035431743237832921768659760762754124218928081388728801758131092 96020150746331979561488146333412674896256883784351178477592660577212734269 32838238471174608378220993964661230834395216957658106542377198189957384043 03159309732150599013712183997625850554354595163400551490805656273304753625 28926945020226163130902420795006258931367813005222140742964756194053782182 45283309702155421092963869300546001192717830276156350571573540567265252417 59254363718634718362920121624566620936420746055008424493472898306195060775 70528754845277680661218358066130291463288932240701043887535007851997159198 39008465459699619713839972349586374980658243938461504918404848581919356066 71259680185748778195611043352384208734177433851857356631012927574092805868 40011804854994149478736882949368786637202682607198707656286436753775709560 34971839740556550526942521835430134891078523451779551975751648471154592846 60037545584854709947374937966158410404142398757633352017955186448566322015 98556341934286668912522153446348791218159622744525372314219184738770596659 94218127540361366043853882920181020485091771779148525602624252980249230922 95621770627700276592881584739948042550677309034200434916329135886446274153 18468517462580180901314477358637486528221274450661883667873545037139535563 26034977820999241655911160209743749143236078787933101505241704743782355350 62056170175721753870617511929197156603630283023438195849465943284604829319 60515124867123604625653903565173322856758210937541222674223847046664733620 29282483406513781447536774767188222009838968201978421672401549125336043643 78474797706336579054181335230108045599585473796858647089377916593402237955 37045273849435441105983887969741143051069401271065628507537039823308867819 86829817141518521827149361311096398402191244832342390139255381172595415320 94350029548076402919827657415140429566669531773040033587015037034974248978 98108939453026976878231557938158928996868766367603579055322794822757659104 81283521974572402234756991465024063673049283328615187504912987345793087499 94880486812508029046064462235695627679648989148699242019464585213551657098 87118378290437174375625282606140534611987395334677500936625746765638459629 52187226277747348049123396519428135372506866078207668386256548727903802048 67780999917543808157898208252555662349839332174914938649662841168898746650 05414748264599972752003370084542592544301190399041231752771993767799847551 27944801291384203432315488813793252488717209938119572216314810167027487737 91618309689373487201689449032996589325119965041096536746189148615994816320 40891930577238630396311858213341337110096389113836596895914715370925073998 46168204642644729078897652559350513654697836460318382061956057851756150497 26618176490303049821385347386962122346261140430356009670425470123173604497 24623287452575151198771801585742829389025650825988275495110865424704218337 26402307804568165142051780741819609640151346176079436276961222812611861091 27668148805009509638890328777108376510519000761280584739692587687379373066 64751387942217354694021157675557568970168734104342446525522568974329716152 74255811050349504571893175244707041030776083036553671418038872360294887280 55907527111155907947569269039785196019397903117680703568019449361068506405 68519290645048685535628256787225734544146565541187816717729850612874044620 89071850210851802505292459035981411752272032055264259775198441074249217924 20390800146062259994221097171761187468458026737248013656038669099710713472 55859723217027554055085082090418987534829222004178998475030519537179062001 50933302302388180651918240555081867216471170230752992265222803382040411338 66253358150429341151439809399864163656339236206738742593427134447012427027 22227197573203194489407856355511639619115985907995399083680129468810771595 93808490811125193801641486625014109528668091482850312393896099765917597731 54327971739457625603650235879315599261708523150742478498142565646930081050 61976397395591733545472917526739598790117477449217745771908169489543790314 57815266738968941060458835144502613064563723768763112996457669947576734067 35835372187049351773202147794039725665325817316592021997529428244327781021 07532160580104432121067208273876100778332426569624765621063126975491546224 34397806125399931389391578200856001117131977344313041299821562698509889572 27781595245056404355349798558722345219917784195641066221220490390178867379 97905270552302412002780864726282517525092332555378737792434915926182736151 24259224272587269984401413256795464047574245112610285739419347971638318713 83707227824226193840210108962712816857322877642102987088955571483977434974 18109849633633910397778254225179400022143485886207532122646613614487518735 14249446957583674478502801319303390194973871616311380086409340852929772974 14628361422011205730274273095666588498849651342951882879370161474995046851 85116851709758146686994243673140036992381232483920618628663037402351333907 77190745522424851574872613607504802096097656786202523235627302555705438672 91892555716723968719916696518347369874402959423952208634813414840298389394 85593327256627318194137735451891544384960966451285561476772564932516923822 00322973348333172630620005919206744113691324372040357809867644089467236733 45499039052836824114220118869492653245313993237641005639967442736936065868 51243936737155349696358970470706246743064681511525580772367129358691546677 17928067460319744366023566481191117532423979227160321393269090043143357251 19355917857874389319108367222197495943852176828172055374339879393724206984 22586002026702204502341484432231418159837133223467338185995720215212999066 85531859376518812281564434984289780404447425317318719824988021905612475683 50531219366840911136134517403804000412814745274536875301227412262925494310 08458868082627169312891414237466973215688306962596297824286828479758198382 34034522270875734539389712691017483517997132092291174643545502392662938545 57426308404732459893743078368758640879143123192283073049753624817085798498 70550314357368660453504099679685389802578477910419231052505144696885248726 34436536945392137219471599815662445433056279828277734958466675701896990098 51101644910479936029229616451329952242714049081869480808181447654414760708 34943179921347693205775493727581146799477819807044909830887802418354528095 57626817822159641071221650999519696193236876695992433693901867583047795134 85649674966430069785481208610130290264826404023166210182586041727345019708 38570222765188590393123627245232006535983907604127898007628220791246163222 71305190667802964427322876346006028921331609405739600352360814948785578481 99236040337092439208957851009536662455380471184198340685899489340265181327 41951749125192568729824877982938351710224389886834755562218214866075518628 42050844124085508840849940522654853577667886444468050430128598846991550169 26211730495502683654983406379433415847973906669732718175671111234452127011 38287733170703648843560692535012857745637166012927846194135756491508269323 01006355908799183148017960666489360686487556915470086060270390964009051460 93605130372809849899764729342059710761043657066703696367310866167730643613 33184164332104073479210775688703754193241101764488071673304176268034528127 94672924445291916188209533594566715845094147630153703258810925492162060242 39983839396395708642683155577379235428304771690538507219399272668305672274 42913752680237178175908437269780708099690192695002592421020485193953805155 15866326641823045212937104684021880666516523143859749808162142014805135513 18654530148712982499386242721543453723918022151261158548619753989831108881 96358875565793593310597895992053240439684590862193232015232257668969509415 39839372130874724773294449305375757769436268032831605506035321968500120719 51916714260633640561790062186716046386842490672475728557640716313978246391 88693789635247708232195940400450829593853651517642510129335911478337995658 50176617578542996683741724783883864589231992004119639092535422607419941218 19501962515981370764670850224792016491740567949940249675930031299570997420 26595785390010668925864718839026058417582396497109522944729874183273952292 24759215694369568203747773104951412881843121031747660050732861304569814187 67387058355896805688120629016723897076030395497082734184840690372151798622 66581929555420755695654139976814235027490594662592770986044588793675562143 70964870574466531981477289217729093779983495276999514506115720439412868712 15387568425680366223213695080419157374690099170480398859472604862586844497 62362318724085339500204989295963618739437408918888568903691128987832325892 60133115526090113191196253652938464399346566649027110852283447018476839157 36238952397327811583993551780220761774507559291383814685265773091522905025 09145241134006895661073761320484545645543610238773087594308408699782711315 42551347205893933945301354813524417675413138501277002415626193616964970994 41569335416665909357597847759464689539235162297236734036508058861862098881 23677098892944769654360324668874429740130365009770291603536426502844618046 12813732400603494788970772326236492751554501373179727761527223600859659873 66938414676850301661035169883909955706593317132195740032510463036041962952 76316972893990945091279545361627593486818455830168634280653205028729105026 90664372617066177843931115473714975909611614449381210674603725145261627161 52129350431411241558498475740918784584101773250305532072376619339702544883 35435069113577757765584551136714634629223114497809546405079026755854160954 26055778340646735618939850316030304668752257970838799329876918298682297066 73562466479396533654545442683864043226502960288812985572421981872080402072 96077496128886166773288838620609977925416822156713703667391333322086520871 90447304859301746679357817383083240645958501817726744769037652317874014263 65021720931026192630465421127080947696823922073837974820570347931965251392 21370199877543931178601238198924707047629587501516299912892933069025343575 48825145494846932832289820295650690330847048251774413116646477475072347786 15180553434668580409871322734530818367945643644301552462741581007310693230 80734901590517008753654169600998911569598454702926629374049393677685285723 03975469118102146926721933384656305367384653782497004950620940350660624458 44126279023842427852805515992531882627862715319895671653983854289093115771 22438618119724985644233907558812574859217687149721341833317289714977694982 11722733766987836121278846528934947067699514678583595507412156837503293782 23523786651032669234498876906197941165749364183479148239839880020676499672 89214983486424468737742286438563064425223461210639952418146166111391586408 08974041394587984903668269548819780876602195996484677114569815936756790476 81120470557406023512374990122585673579651070132515622378437549947472368838 21060645969480067316032381351192535148322216761442411144695361182838761115 79591131036242074151082632204837454040414699047964707311342836830015824735 07129223311197890131797016517640330366496067495186286568360325563532056173 86602749327417799524243899880581322620681297935615821202736455540414428705 85713183523895174247123905075891935349057026830281281070475060318170927443 48065048434221341522015796267763936426981688514855452068978020362574960435 84180735523092410264794436423951474855853980259367017205588767985309971043 29040488446754170191891227574575240212174489032668116064783798500463986419 36457920821052660575039211953114575926214008306603017681201785603286502201 71413811642155986702637531155554821958388905393544592180587272433749899242 04154281666682184637486333752272907799420896054526486386251641171804911290 34513781400215068999667620807326513804277924609307622634469941591932231425 65029996403134383564087766689537759857473403120477091886596355579944643688 20598124204047780294380393245972220754173958959669203405216168083758892163 60485847899296639031073499456670278306104831308628726806610153007455216698 93857383782690975026078691245077096697355744971063878379083608563324774011 42660458879771284333508934175212084313354915580594521750376672813681898970 10757950349759311471138511775290847083826469309436638378514887987236887715 34770333456570254004964039987760745951276145936694695508877796318400093229 97373677051851257323323012713421093706868095026436222551087287714163560171 62762670401689968162872133264222683778553278878223102045397622725830149026 09710931194995685950834598509258803363019551891846212990914920155838298607 56819073737595857334826171379470359250397212631431619215957145108174403411 48479043866012842446433628573924423167674110364175577769918867199105114569 02002905771699177497748359489810115650557253501242519595931483440417116222 20550458967163675447804289348838550027521149752624642112201077486233347624 61825765971784039804366176695605670499367893503708931746175602820746790581 10806280348893136768773133234721178541038289213080580369302853910384704528 01834405831325274412992835573270402822090195156005444976463593206508376086 44739896927093811205042512669308348399999568602163561489401674425640784693 50152730245749435722205009403680810321136898946443062041659878360406811331 21713350496050494416547288392637860786838573151536637341631256612260323597 77424739403247934787407703527254365324553084382508656938643300209571207191 22826689237609273524467576647981797622831709248187143189474449928329051087 06686626390146275460018668358362206244555382886714362141577363824485257066 46534230020033860871856833870952825642318923373058274678251029052392144641 17590700082862874915647212962223100149842773910585262712095702633425139069 27554124992582689875591304848905908366504738656900598072651268264380980008 07687168897497670057472282851654309354694237012969012252000417759752780993 41399149455675655415791289014141807180970818010668626000334746783492116354 33074176655619786541294433157961085673390721097081524769436020823107737731 92559355919193615099922418518697625118219715984493964229232225869395832058 49537600173388242916813257003198490942805178528782842560021549233235032941 87284260110962343206148554757903880284922813939713097918056244770349429953 05859094150312374002134454316070495388091178705710456862116210696550230288 86617060314580222884344906879404890744067164557565160596397488164744575409 40089191108394512623399045336477254174133133082115375898307739040254973975 16208258378983849962008747496223314363545535997104728963962629146755422817 35624665804212007275401273982269651802596130334329792865330063654175676003 36968824392639128071312303876007603995728565833339083859253424933715307045 74714827435510374171470240068674191418743982304492027720096822824746408027 79068104741602882613440803256607530230172031981070796893051954145239327661 78390582894393214614889482169591857949850226385831870447329029979047319375 38035439202857063506724842450089206897129953082137473352557929825658034697 79504974053329506220584586976782376547358092670753891736652401577525890202 35488322748067896132846682186597286978559267282682265645757795867057109772 83966051015163871636153219182036527298975868077864430448966286703931884869 21931839182927172554503767733076856308657600665342622254535057629030862718 93736432744808355892822010237495153466526285750422295099544601442880185906 14433796791427174132782869759982599938190844774697752205678983953785701546 09157695006128689610825519373486612568225010585752375050450503641627804406 67690513056480719101413228506348266572682851193305943371737389962365471553 48165916300868385209054910601945967582237019115135811420715212206735219487 77069521608531717477580542554138038978873716058241771904252401056370661792 99639580870671708387295023805723854761049506173268958794824031956949900059 45937198490041045500344150140661545269946090944413914390718663090092496918 12468813088126242358787204856089608234037677437509496768451058059579977189 00660535490335996178424512109614487706318746691029235662777116520352264701 61662964880838089978876877693082208565300681539408567480413494694918707049 92660210066455819832886130678021460369893174499939107231230405088342485383 79674220884706038533494392814751968579129217444191738639873915590891585931 07504494199694258569205038912775500925600292255660282457330541643704829653 51532695757311986033153861767127072322962670122480612322195488891848040149 35775713130230889750134857360035713430704662815717872002157870598330285640 18514036741685235792023064406441594485865662469054779640865724626118340632 13025126230896949713642334585419351128373132157232101577687884147986752364 44171129847235476314271585029343474643412723022573579209708343991049839401 97899798703518377860107786672261022416844986863988742275806312725814743966 76719404444290071284914286251867085092358453277091441099575357659812178523 75684893442967036868618122992803343345669649346077090359223180407284982764 09558738544914554164806210986190904493317612889661353254130623139919714623 32768487224184119088841054819270878948939590681778579588918587881426099241 76775386238240600245182114903516012449289394057849405543217358977950386779 24486147694487346718635838172966270733414040276310298215623031421577433792 94616649374361560459036060298581224576085252700570061877609582745974967405 31588216269598285114300632089773047313346117214294580540717887622301146255 85105209307617714932786035412627198805228268641070550493643705558169458308 40650960447321868266858216903784868032280479864021706315653687489290467679 01586470937947876237301382202637378882282756416372587267092160243407727929 85656798252349464283761629187175569934546937247597446443745861235777688426 47346924365909558553162571564807969034052671504760754742676960038255814034 35471652083459886453843259390815439291893908989610908352199251905353039835 90815162892475710433547864249549807413887453860231133295913906360066945394 37438690759589121288758007804082911975207095278133335550232776761783391381 79410510941299968043010389947505124323233143112066359872661861008471725469 69087266374568584666461620932234276806846017185167024276711259130800595830 53658180035991214447685286534985397013876080817020918472863351368783745251 29293629437313779779416816313098368883362459248827004253327531017403740185 81551926631475880324503163498289440909414594357098393314540779376385338848 24056964583661906580362312059760037127664830995125859310214290237306052000 88341574972440502886340250002874705523368854106859338903966237991377648571 57720937496810557182777814296592442516667031101358206253165189069364626636 13376783677001574909561444962828205690820330013121289873007855206280915035 88033407174623351114283809655065181827117782596414734227588580316247364825 35088792762990748132426924617141695210685488182753616127869552164123832632 46164034602771053052217127416909831714425842754359325193708367920524870186 21270857453151819707979762415632236962753030362501005740150318524177138171 69169590665504804942674736966560518195277297404407824874163530870748034471 26307550453018768734511631260002571765708294113447159058326859464022975489 06186856971552932533367919290450918133898903953122611407760414634139512025 31990687206904506543173607993524347910820396954780619264532546440531245863 62026016156957888326419910345519741792140396061817459467332211367113051675 84497072208063824930928534825774708275493986060850848638654991291222039189 53793323218143449984586805572679155535252121139077233890379794274852093095 04641599639196053296030292739274663906234190084882219800040754390250718430 16848086615700902205315827385741726790231019356606424366083408020278639226 36524533955047062441089577910492989083970977158068570365278729328467719522 74875201321856644284239116502005786314083266606564469023548865452436995428 17305438348153252515631160343894144061259966226495987876900371241240630507 27130493610607775193517666843509790951124703777285270451816535562856216567 61979382960837252084759203181114384404005114613990326273362146150667851880 07932756348644480372696327847581845346850956536538072380773679352624214553 30888336797270741928388726854849773873066700075519657614315839411020424926 23133242770270821710047137152167948872468741189259805623910487138975034203 37667334498906005211172784467053052132742533218973497888830794362609912556 97413508394340617507128764452220395574551500194429962327393170914879051488 12821582894579949748623433452865460274945133477267345362799684706610937707 68804837956786049988732728727315878519550521694698657175937287598451499408 73667356996903222126190733721319849728737148239220563611582767192936875179 50957314775347729780073870450969204201405641649670458849057466793682155521 90109502796602359020062956342662169755616626195672140343980362191824317724 21104848239016221214332463945118321907370362763625569475353726194361269966 45342229589006736952014870393865015087074414735220220770411070088328030731 54504108572176244860032457452964244580155088753558144512891817368634611656 71110501511097147605443615379202075461150735291679353598037462331580354025 07293585422134950239655004818456256327794930441926282941363007224150758144 47768895556961602574142385927441574047721764347494866318318264821008378574 90802221991221446941174002708561590951048858459673923326023018437403287028 08569782311182460392642129024729192535226787567897868564600570545108945374 19064937155889425332970348698269338663457480780107871925412978490715527668 34053624072289750180164174866952266394688977998297470344148466052329775319 14266638473906810541671168066131262918834764800639654762345192540580400257 72795085906181732600018835667757624963508451226641055755164513447026208348 54807761737019236264063848313718420874772230944679786612216496898423227892 48762605167898686475739012260361067924661728390016267344059903224026536343 55030155298326451986588130394258661773498728023189254427801611331835427610 32580023939426078587569494851193007158539298431639675755313524842212748148 64027297307155457109423432471856970523635672286551516265672389248080659279 44895307870815360666674131459826079881127875465631300778574348418961080949 91194360375610753263594141434768824946925307877906932752908959099450652720 71979419682741840819830567497688086236460819345623637702467815073133466197 92311993911719597935283311749682050057729993856647698426081551894086677632 08554831598361888504483399113515051329097039900889190631333758040948869558 95465912648104534621430295733375992898959329664444686900648674531661878821 29719414619191413297867337528370299519070617992417814024935628500653627377 16363555697200032469961306652824516951672731618313938675587912782649337580 40011059211372270839123518459709107480669852696080909181872978501574064544 54826447107863338659911318881013774631898449674598901154033425931534774008 21107348184715212533745072715381310482966129790814776632697913945703573905 37422769779633811568396223208402597025155304734389883109376

Here is how long it took to construct this list:
> (time (length (make-list (expt 2 100000) 'x))) cpu time: 5659 real time: 5678 gc time: 1823

And just so you don’t think I’m cheating, you can reference any element of the list, i.e.:
> (define ls (make-list (expt 2 100000) 'x))) > (list-ref ls 100) 'x > (time (list-ref ls 100)) cpu time: 3 real time: 3 gc time: 0 'x > (list-ref ls 100000000000000) 'x > (time (list-ref ls 100000000000000)) cpu time: 1750 real time: 1763 gc time: 209 'x

You can also update any element. Since it’s a functional list, you want keep a reference to the updated list:
(define ls* (list-set ls 8989891824312123128989813 'q))

If you want to see how long that took, here it is:
> (define ls* (time (list-set ls 8989891824312123128989813 'q))) cpu time: 1850 real time: 1864 gc time: 291

And:
> (time (list-ref ls* 8989891824312123128989813)) cpu time: 1766 real time: 1774 gc time: 225 'q

And you can still do operations like length, or even fetch the last element:
> (time (last ls*)) cpu time: 3302 real time: 3350 gc time: 436 'x

[Note that last should be much faster, but I have a naive implementation for the moment.]

[Update: version 3:5 of the ralist library now has a fast last operation:
> (time (last ls*)) cpu time: 1 real time: 2 gc time: 0 'x
That's not so bad!]

I’ve been asked for a hint about the implementation, but I can give much more than a hint — the full source code is here:

http://bit.ly/ralist

It’s based on Chris Okasaki’s FPCA ‘95 paper. The idea is actually very simple and beautiful. I recommend reading the original, lovely paper.

Filed in Racket | Comments (0)

Deriving cosine: higher-order functions in modern languages

Sunday, February 27, 2011

In a higher-order language, computation can produce not just scalar values, but also values with behavior. In other words, computations can compute computations. It’s a powerful idea, and higher-order programming languages are everywhere, but what do they look like? Here’s a classic example of a higher-order function, the derivative function, written in a bunch of different languages. In each example, I use the derivative function to compute a cosine function from a sine function.

(I know that even modern versions of Fortran have support for object and closures. If you speak Fortran and can translate the example, please let me know.)

Python:

from math import sin

e = 0.0001

# (ℝ → ℝ) → (ℝ → ℝ)
def deriv(f):
    def fp(x):
        return ((f(x+e) - f(x-e)) / (2*e));
    return fp

print deriv(sin)(4)

JavaScript:

var ε = 0.0001;

// (ℝ → ℝ) → (ℝ → ℝ)
function deriv(f) {
  return function (x) {
    return (f(x+ε) - f(x-ε)) / (2*ε);
  };
}

deriv(Math.sin)(4);

Ruby:

# -*- coding: utf-8 -*-
class Calculus
  def e
    0.0001
  end

  # (ℝ → ℝ) → (ℝ → ℝ)
  def deriv(f)
    fp = lambda { |x|
      (f.call(x+e) - f.call(x-e)) / (2*e)
    }
    return fp
  end
end

puts Calculus.new.deriv(lambda { |x| Math.sin(x) }).call(4)

Scala:

def ε = 0.0001

// (ℝ → ℝ) → (ℝ → ℝ)
def deriv(f: Double => Double) = {
  def fp(x: Double) =
    (f(x+ε) - f(x-ε)) / (2*ε)
  fp _
}

object Main {
  def main(args: Array[String]) {
    println(deriv(math.sin)(4))
  }
}

C#:

using System;
public class Calculus {
  static double ε = 0.0001;

  // (ℝ → ℝ) → (ℝ → ℝ)
  static Func<double, double>
  deriv(Func<double, double> f) {
    return (x)
      => (f(x+ε) - f(x-ε)) / (2*ε);
  }

  static public void Main() {
    Console.WriteLine(deriv(Math.Sin)(4));
  }
}

Java:

interface Func<X,Y> {
    Y apply(X x);
}

class Calculus {
    Double ε = 0.0001;

    // (ℝ → ℝ) → (ℝ → ℝ)
    public Func<Double, Double>
    deriv(final Func<Double, Double> f) {
        return new Func<Double,Double>() {
            public Double apply(Double x) {
                return ((f.apply(x+ε) - f.apply(x-ε)) / (2*ε));
            }
        };
    }
}

class Sin implements Func<Double, Double> {
    public Double apply(Double x) {
        return Math.sin(x);
    }
}

class Main {
    public static void main(String[] args) {
        System.out.println(
           new Calculus().deriv(new Sin()).apply(4d));
    }
}

X10:

class Calculus {
  val ε = 0.0001;

  // (ℝ → ℝ) → (ℝ → ℝ)
  def deriv(f: (Double) => Double) {
    val fp = (x: Double) =>
      (f(x+ε) - f(x-ε)) / (2*ε);
    return fp;
  }
}

public class Deriv {
  public static def main(args: Array[String](1)) {
    val cos = new Calculus().deriv((x: Double) => Math.sin(x));
    x10.io.Console.OUT.println(cos(4.0));
  }
}

Racket (thanks to Robby Findler):

#lang racket

(define ε 0.0001)

;; (ℝ → ℝ) → (ℝ → ℝ)
(define ((deriv f) x)
  (/ (- (f (+ x ε))
        (f (- x ε)))
     (* 2 ε)))

((deriv sin) 4)

Filed in CSharp, Java, JavaScript, Python, Ruby, Scala, Scheme, X10 | Comments (0)

ACM Computing Survey: Control-flow Analysis of Functional Programs

Friday, February 4, 2011

Jan Midtgaard’s excellent survey on CFA has been accepted by ACM Computing Surveys and is now “forthcoming”. It’s been a valuable resource to me and others; I recommend it to anyone interested in the literature on CFA.

http://www.brics.dk/~jmi/Midtgaard%3aCSur10.html

Control-flow Analysis of Functional Programs
Jan Midtgaard, ACM Computing Surveys, 2010, forthcoming

Abstract

We present a survey of control-flow analysis of functional programs, which has been the subject of extensive investigation throughout the past 30 years. Analyses of the control flow of functional programs have been formulated in multiple settings and have led to many different approximations, starting with the seminal works of Jones, Shivers, and Sestoft. In this paper, we survey control-flow analysis of functional programs by structuring the multitude of formulations and approximations and comparing them.

Filed in Announce, CFA | Comments (0)

NEPLS, March 4 @ Northeastern

Thursday, February 3, 2011

The next New England Programming Languages and Systems Symposium will take place on March 4th at Northeastern University. Please mark it in your calendars!

The speaker selection committee solicits talks for this meeting. To propose yourself or someone else, send a title, list of authors, and a brief description. You may provide UP TO ONE PAGE of description, but you can keep it as short as a paragraph. We particularly invite talks by researchers from outside the area who are visiting on the date of the NEPLS meeting.

Talks can vary in length. Though 30-minute conference-style slots are traditional, speakers may request slots of as little as 5 minutes; we encourage the shorter formats. This variety permits the presentation of smaller results, preliminary work, progress reports on ongoing projects (such as language standards and compiler toolkits), and updates to past presentations. In general, NEPLS talks need not sound like conference presentations.

The submission deadline is February 17th. Send your proposal to talks@nepls.org. (Replying to this message will work in most cases, but some mailing lists masquerade as your correspondents — please check before responding.)

More details about NEPLS are available on the NEPLS webpage:

http://www.nepls.org/

Sam Tobin-Hochstadt & David Van Horn

Filed in Announce | Comments (1)

Highlights from POPL 2011

Monday, January 31, 2011

Some of my personal highlights from POPL 2011 (in order of appearance):

Pick your contexts well: understanding object-sensitivity
Yannis Smaragdakis, Martin Bravenboer, Ondrej Lhoták
Correct blame for contracts: no more scapegoating
Christos Dimoulas, Robert Bruce Findler, Cormac Flanagan, Matthias Felleisen
A separation logic for refining concurrent objects
Aaron Joseph Turon, Mitchell Wand
Symmetric lenses
Martin Hofmann, Benjamin Pierce, Daniel Wagner
Regular expression containment: coinductive axiomatization and computational interpretation
Fritz Henglein, Lasse Nielsen
Practical affine types
Jesse A. Tov, Riccardo Pucella
Dynamic inference of static types for Ruby
Jong-hoon (David) An, Avik Chaudhuri, Jeffrey S. Foster, Michael Hicks
EigenCFA: accelerating flow analysis with GPUs
Tarun Prabhu, Shreyas Ramalingam, Matthew Might, Mary Hall
Verifying higher-order functional programs with pattern-matching algebraic data types
C.-H. Luke Ong, Steven James Ramsay

[Keep in mind: I saw less than half the talks, so I'm sure I missed a lot of good work and if I didn't mention something here, it doesn't mean I didn't like it.]

I would have to say “Dynamic inference of static types for Ruby” stood out above the others. What a cool idea.

Filed in Talks | Comments (1)

Photos from POPL 2011

Saturday, January 29, 2011

Some photos from POPL 2011 in Austin, Texas.

Filed in Photos | Comments (0)

TFP 20101 Best student paper

Wednesday, January 5, 2011

Evaluating Call-By-Need on the Control Stack won the best student paper award at TFP 2010. The citation reads:

This thought-provoking paper combines theory and practice in a novel method for call-by-need evaluation. It uses the control stack and de Bruijn numbers for resolving variable references and incorporates a compacting, garbage-collection-like algorithm to keep the stack size small. The algorithm is backed up by a correctness proof, which makes it an excellent example of the well-defined, forward-looking contribution to functional programming that the TFP Symposium seeks for its program.

Filed in Announce | Comments (0)

ICFP 2011, Tokyo, Call for Papers

Friday, December 10, 2010

The 16th ACM SIGPLAN International Conference on Functional Programming, which will be held in Tokyo, Japan, September 19-21, 2011. The Call for Papers has been posted. Submissions are due March 24, 2011. Submit!

ICFP 2011 seeks original papers on the art and science of functional programming. Submissions are invited on all topics from principles to practice, from foundations to features, and from abstraction to application. The scope includes all languages that encourage functional programming, including both purely applicative and imperative languages, as well as languages with objects, concurrency, or parallelism. Particular topics of interest include

Language Design: type systems; concurrency and distribution; modules; components and composition; metaprogramming; relations to imperative, object-oriented, or logic programming; interoperability

Implementation: abstract machines; virtual machines; interpretation; compilation; compile-time and run-time optimization; memory management; multi-threading; exploiting parallel hardware; interfaces to foreign functions, services, components, or low-level machine resources

Software-Development Techniques: algorithms and data structures; design patterns; specification; verification; validation; proof assistants; debugging; testing; tracing; profiling

Foundations: formal semantics; lambda calculus; rewriting; type theory; mathematical logic; monads; continuations; delimited continuations; global, delimited, or local effects

Transformation and Analysis: abstract interpretation; partial evaluation; program transformation; program calculation; program proofs; normalization by evaluation

Applications and Domain-Specific Languages: symbolic computing; formal-methods tools; artificial intelligence; systems programming; distributed-systems and web programming; hardware design; databases; XML processing; scientific and numerical computing; graphical user interfaces; multimedia programming; scripting; system administration; security; education

Functional Pearls: elegant, instructive, and fun essays on functional programming

Experience Reports: short papers that provide evidence that functional programming really works or describe obstacles that have kept it from working in a particular application

Filed in Announce | Comments (0)

Fector: Persistent Functional Vectors for Racket

Chad looks sad

List challenge

Deriving cosine: higher-order functions in modern languages

ACM Computing Survey: Control-flow Analysis of Functional Programs

NEPLS, March 4 @ Northeastern

Highlights from POPL 2011

Photos from POPL 2011

TFP 20101 Best student paper

ICFP 2011, Tokyo, Call for Papers

on twitter

Blogroll

Categories

Archives

Meta