开发者

How can I tell if my tail-recursive Scheme function is being optimized correctly

开发者 https://www.devze.com 2023-01-25 06:35 出处:网络
I have a Scheme function who\'s basic form looks like this (define (foo param var) (cond ((end-condition) (return-something))

I have a Scheme function who's basic form looks like this

(define (foo param var)  
  (cond ((end-condition) (return-something))  
        ((other-end-condit) (return-something-else))  
        (else  
         (let ((newvar (if some-condition   
                           (make-some-updated var)  
                           (destructive-update! var))))  
           (foo param newvar)))))  

I feel like this is pretty clearly something that needs to be optimized to iteration in compilation, but when I compile it (with chicken) it still runs incredibly slowly. (if I understand the R5RS specs: http://groups.csail.mit.开发者_Python百科edu/mac/ftpdir/scheme-reports/r5rs-html.old/r5rs_22.html, this looks like it should work)

I wrote the same exact algorithm with a while loop in python and the interpreted program terminated in seconds. My compiled scheme takes about 15 minutes, and I am positive the algorithm is the same.

I think this is a tail recursion not getting optimized issue, as I can't think what else it could possibly be, but I cant figure it out. Any ideas? For what its worth, the var is a hash and the destructive update is merely adding an element, although it also returns the updated hash to be passed in as newvar.


That function is indeed tail-recursive, so you're good there. However, tail recursion just means that stack space won't grow, not that your program is guaranteed to run fast. If you want to see if your program is really running tail-recursively, run it while watching the total memory taken by Chicken (and make sure you aren't allocating memory in make-some-updated, which you might be). If the memory grows, then Chicken isn't compiling your program correctly according to the standard.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号