continuations - why scala doesn't make tail call optimization? -


just playing continuations. goal create function receive function parameter, , execution amount - , return function apply parameter given amount times.

the implementation looks pretty obvious

def n_times[t](func:t=>t,count:int):t=>t = {   @tailrec   def n_times_cont(cnt:int, continuation:t=>t):t=>t= cnt match {         case _ if cnt < 1 => throw new illegalargumentexception(s"count wrong $count")         case 1 => continuation         case _ => n_times_cont(cnt-1,i=>continuation(func(i)))       }   n_times_cont(count, func) }  def inc (x:int) = x+1      val res1 = n_times(inc,1000)(1)  // works ok, returns 1001  val res = n_times(inc,10000000)(1) // fails

but there no problem - code fails stackoverflow error. why there no tail-call optimization here?

i'm running in eclipse using scala plugin, , returns exception in thread "main" java.lang.stackoverflowerror @ scala.runtime.boxesruntime.boxtointeger(unknown source) @ task_mult$$anonfun$1.apply(task_mult.scala:25) @ task_mult$$anonfun$n_times_cont$1$1.apply(task_mult.scala:18)

p.s.

f# code, direct translation, working without issues

let n_times_cnt func count =      let rec n_times_impl count' continuation =          match count'         | _ when count'<1 -> failwith "wrong count"         | 1 -> continuation         | _ -> n_times_impl (count'-1) (func >> continuation)      n_times_impl count func  let inc x = x+1 let res = (n_times_cnt inc 10000000) 1  printfn "%o" res

the scala standard library has implementation of trampolines in scala.util.control.tailcalls. revisiting implementation... when build nested calls continuation(func(t)), tail calls, not optimized compiler. so, let's build t => tailrec[t], stack frames replaced objects in heap. return function take argument , pass trampolined function:

import util.control.tailcalls._ def n_times_trampolined[t](func: t => t, count: int): t => t = {   @annotation.tailrec   def n_times_cont(cnt: int, continuation: t => tailrec[t]): t => tailrec[t] = cnt match {     case _ if cnt < 1 => throw new illegalargumentexception(s"count wrong $count")     case 1 => continuation     case _ => n_times_cont(cnt - 1, t => tailcall(continuation(func(t))))   }   val lifted : t => tailrec[t] = t => done(func(t))   t => n_times_cont(count, lifted)(t).result }

Comments

Post a Comment

Popular posts from this blog

php - mySql Join with 4 tables -

select * web_user e inner join web_audio ce on ce.uid = e.uid inner join web_videos c on c.uid = e.uid inner join web_images d on d.uid = e.uid e.uid = '1' we have scenario have 4 tables , want fetch records on basis of uid web_user table rest of tables fetch records on basis of web_user uid. have 6 records database. returning 8 time. below response of mysql query. uid ufname ulname uemail username upassword uaddress ucity ustate uzipcode uphone uimage usertype ugenre website biography uverifycode featured activate ustatus upaid aid uid a_filename a_uploadname a_genre a_singername a_approve a_price vid uid v_filename v_uploadname v_short_desc v_singername v_approve v_price iid uid upload_file i_approve ========================== 1 muhammad mohsin mohsin@balianti.com mohsin 213123 test addresss 0 1 40100 333-2335-5555 fds_896_autumn-mist.jpg 1 6 null null 202cb962ac59075b964b07152d234b70 1 1 1 1 1 1 asd muhammad_709.mp3 5 asd 0 0.00 1 1 test video muhammad_578.flv ...
Read more

css - Text drops down with smaller window -

i've adapted css use in website , can't quite figure out why 1 aspect of page acting way acting. basically, when shrink window below size horizontally, of text "drops down". becomes issue if user viewing website through ipad vertical orientation. can view issue here . i'm hoping make if window gets smaller, placement of text remains intact. the problem area not have enough space put both side navigation , content on 1 line. make automatically adjust page's width when exceeds decrements of width. this code example, , highly unlikely work. if see css more clearly, provide exact code. @media , (max-width:960px) { /* assuming #wrapper 960px across */ #content {width:560px;} /* opposed 720px */ } edit the content drops down @ 980px, have shrink width after there. @media , (max-width:980px) { #container {width:520px;} }
Read more

c# - DetailsView in ASP.Net - How to add another column on the side/add a control in each row? -

i have detailsview control on page used edit various fields of record, works in respect. i looking way add 1 column (and if works, why not more) right, absolutely read-only, show same fields of record comparison purposes. i aware there no obvious way such thing out of box detailsview . have looked other controls (transposed gridview , recommended formview , listview ), nothing satisfies. have special data binding setup using detailsview , can't out of without losing features. anyone on how "hack in" additional columns (for display only) on detailsview ? the solution have now, use second detailsview , visible set false in aspx. in code, make sure databind hidden detailsview hosts data third column first, initial detailsview named itemdetails . and in item created event, pass third column html rendering of hidden controls (in last code block) : protected void itemdetails_itemcreated(object sender, eventargs e) { if (dataite...
Read more