🚀 go-pugleaf

On Thu, 31 Jul 2008, namekuseijin wrote:

> 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)))))
> 
> 


Maybe, but that would be cheating.

According to the benchmark page, fib must be
implemented like this:

Fib(n)
  n < 2     = 1
  otherwise = Fib(n-2) + Fib(n-1)


Apropos cheating, I'm not 100% sure the gcc version of Ack is playing
fair though...:

Ack(x,y)
  x = 0     = y+1
  y = 0     = Ack(x-1,1)
  otherwise = Ack(x-1, Ack(x,y-1))

vs.

static inline int ack(register int x, register int y){
  if (x == 0) {
    return y + 1;
  }
  return ack(x - 1, ((y | 0) ? ack(x, y - 1) : 1));
}




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

At least not for Fib:


/* FIB[7] */
int f7(int a668)
{
    int t1297;
    int t1298;
    int t1299;
    int t1300;
    int t1301;
    int t1302;
    int t1303;
    int t1304;
    int t1305;
    int t1306;
    /* x60 recursive.scm:40:960 */
    /* x40 recursive.scm:40:967 */
    /* x38 recursive.scm:40:970 */
    t1297 = a668;
    /* x39 recursive.scm:40:972 */
    t1298 = 2;
    /* x18678 recursive.scm:40:968 */
    if (!(t1297 < t1298))
	goto l366;
    /* x43 */
    /* x42 */
    /* x41 recursive.scm:40:975 */
    return 1;
  l366:
    /* x59 */
    /* x58 */
    /* x57 recursive.scm:41:992 */
    /* x50 recursive.scm:41:995 */
    /* x49 recursive.scm:41:1000 */
    /* x47 recursive.scm:41:1003 */
    t1302 = a668;
    /* x48 recursive.scm:41:1005 */
    t1303 = 2;
    /* x18676 recursive.scm:41:1001 */
    t1301 = t1302 - t1303;
    /* x45 recursive.scm:41:996 */
    t1299 = f7(t1301);
    /* x56 recursive.scm:41:1009 */
    /* x55 recursive.scm:41:1014 */
    /* x53 recursive.scm:41:1017 */
    t1305 = a668;
    /* x54 recursive.scm:41:1019 */
    t1306 = 1;
    /* x18675 recursive.scm:41:1015 */
    t1304 = t1305 - t1306;
    /* x51 recursive.scm:41:1010 */
    t1300 = f7(t1304);
    /* x18677 recursive.scm:41:993 */
    return t1299 + t1300;
}



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

Yeah. ;)