Re: Why such poor recursive behaviour?

Article View: comp.lang.functional

Article #1114

Back to comp.lang.functional Previous Next

#1114

From: namekuseijin
Date: Thu, 31 Jul 2008 18:26

35 lines
2667 bytes

On 31 jul, 07:50, "Kjetil S. Matheussen" <k.s.matheus...@notam02.no>
wrote:
> real    0m1.725s
> user    0m1.635s
> sys     0m0.003s
>
> Which means that Stalin scheme is about 22% faster than C
> for this particular benchmark, and stalin scheme is a
> dynamic typed functional language.

Whoa!  That's exactly the kind of impressive achievment a functional
language should provide, at least regarding recursive behaviour.

Just out of curiosity, your implementation of fib is tree-recursive or
tail-recursive?  That should make a lot of difference, huh?  The PLT-
Scheme version there is a naive tree-recursion:

(define (fib n)
    (cond ((< n 2) 1)
	  (else (+ (fib (- n 2)) (fib (- n 1))))))

A tail-recursive one should fare much better:

(define (fib n)
  (let fb ((x n) (r 1) (r2 0))
    (cond ((= x 0) r2)
          ((= x 1) r)
          (else (fb (- x 1) (+ r2 r) r)))))

Is Stalin capable of automatically turn tree-recursive into tail-
recursive?

Very impressive, anyway.  If only its name didn't spread so much
fear... ;)

Technical Details

Message-ID: <d3fa2579-c181-48a7-ac44-e4f24b0a71f0@i76g2000hsf.googlegroups.com>

Path: arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!postnews.google.com!i76g2000hsf.googlegroups.com!not-for-mail

References: <525fb940-a88e-4276-bd80-86b0b178a08a@m3g2000hsc.googlegroups.com> <Pine.LNX.4.58.0807311242130.25184@notam02.uio.no>

Show Full Headers

Complete Article Headers

X-Google-Thread: 107f24,904ab2e1d637ae0f
X-Google-Thread: ff861,904ab2e1d637ae0f
X-Google-Thread: 10707f,904ab2e1d637ae0f
X-Google-Thread: 103d24,904ab2e1d637ae0f
X-Google-Thread: f4fd2,904ab2e1d637ae0f
X-Google-Attributes: gid107f24,gidff861,gid10707f,gid103d24,gidf4fd2,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII
Path: arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!postnews.google.com!i76g2000hsf.googlegroups.com!not-for-mail
From: namekuseijin <namekuseijin@gmail.com>
Newsgroups: comp.lang.functional,fa.caml,fa.haskell,comp.lang.scheme,comp.lang.lisp
Subject: Re: Why such poor recursive behaviour?
Date: Thu, 31 Jul 2008 11:26:26 -0700 (PDT)
Organization: http://groups.google.com
Lines: 35
Message-ID: <d3fa2579-c181-48a7-ac44-e4f24b0a71f0@i76g2000hsf.googlegroups.com>
References: <525fb940-a88e-4276-bd80-86b0b178a08a@m3g2000hsc.googlegroups.com> 
 <Pine.LNX.4.58.0807311242130.25184@notam02.uio.no>
NNTP-Posting-Host: 189.60.59.171
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1217528787 13824 127.0.0.1 (31 Jul 2008 18:26:27 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Thu, 31 Jul 2008 18:26:27 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: i76g2000hsf.googlegroups.com; posting-host=189.60.59.171; 
 posting-account=AhEwOgoAAABfI1IAWWBiHDSU2pvzqVnt
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; pt-BR; rv:1.9.0.1) 
 Gecko/2008070208 Firefox/3.0.1,gzip(gfe),gzip(gfe)

Reply to Parent Message