"Strong typing vs. strong testing"

[Raffael Cavallaro]

On 2010-10-01 16:47:02 -0400, BartC said:

> I had a quick look at Lisp to see if your claims had any basis. I tried 
> this program:
> 
> (defun fib (n)
>    (if (< n 2)
>        n
>        (+ n (fib (- n 1)) (fib (- n 2)) )
> ))
> 
> But it gave the wrong results and it took ages to figure out why. Even 
> after downloading a working version for comparison, it's was difficult 
> to spot the extraneous 'n' (I think I was concentrating on getting the 
> round brackets all in the right places).

I saw it immediately, but I'm familiar with lisp and you are not - 
those two parentheses (what you call "round brackets") on a line by 
themselves are a dead giveaway.

> 
> I thought you were saying that Lisp (and dynamic typing in general) was 
> better for pointing out errors? The above error in C would have been 
> picked up more easily I think (due to less parentheses clutter, and 
> more obvious separators between terms).
> 
> As for speed, executing fib(38) took about 60 seconds on my machine 
> (gnu clisp with no switches set). (Compared with 3.5 seconds, for my 
> own interpreted, dynamic language, and 0.6 seconds for C.)

Compiled lisp is fast, but you need to actually compile it:

CL-USER 96 > (defun fib (n)
             (declare (optimize speed (debug 0)))
             (if (< n 2)
               n
               (+ (fib (- n 1)) (fib (- n 2)))))
FIB

CL-USER 97 > (compile 'fib)
FIB
NIL
NIL

CL-USER 98 > (time (fib 38))
Timing the evaluation of (FIB 38)

User time    =        0.888
System time  =        0.002
Elapsed time =        0.877
Allocation   = 142568 bytes
0 Page faults
39088169

which is in the same range as your .6 seconds for your equivalent c program.

What happens when you want fib(1000) or fib(1000000)? Then the naive 
recursive version isn't very useful (it's just too slow), and the 
result is going to overflow c integer types.

in lisp:

CL-USER 118 > (defun fact (n) (if (zerop n) 1 (* n (fact (1- n)))))
FACT

CL-USER 119 > (defun fib (n)
                (/ (loop for k from 1 to n by 2
                         sum (/ (* (expt 5 (/ (1- k) 2)) (fact n))
                                (fact k) (fact (- n k))))
                   (expt 2 (1- n))))
FIB

CL-USER 120 > (compile 'fact)
FACT
NIL
NIL

CL-USER 121 > (compile 'fib)
FIB
NIL
NIL

CL-USER 122 > (time (fib 1000))
Timing the evaluation of (FIB 1000)

User time    =        0.760
System time  =        0.007
Elapsed time =        0.748
Allocation   = 474522008 bytes
147 Page faults
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

warmest 

regards,

Ralph

-- 
Raffael Cavallaro