Page 1 of 1

How to convert this Scheme code ?

PostPosted: Sun Oct 12, 2008 4:33 am
by anta40
I recently found a code about fast Fibonacci function at this page :
http://www.reddit.com/r/programming/comments/2mzy3/ask_reddit_whats_the_fastest_fibonacci_algorithm

Code: Select all
(define (pair-multiply p1 p2)
  (let ((ac (* (car p1) (car p2)))
        (ad (* (car p1) (cadr p2)))
        (bc (* (cadr p1) (car p2)))
        (bd (* (cadr p1) (cadr p2))))
    (list (+ ac ad bc) (+ ac bd))))

(define (pair-pow p n)
  (cond
    ((= n 1) p)
    ((even? n)
     (let ((result (pair-pow p (truncate (/ n 2)))))
       (pair-multiply result result)))
    (else
     (let ((result (pair-pow p (truncate (/ n 2)))))
       (pair-multiply p (pair-multiply result result))))))

(define (fib n)
  (if (zero? n)
      0
      (car (pair-pow '(1 0) n))))


My quick attempt is :
Code: Select all
(defun pair-multiply (p1 p2)
  (let ((ac (* (car p1) (car p2)))
      (ad (* (car p1) (cadr p2)))
      (bc (* (cadr p1) (car p2)))
      (bd (* (cadr p1) (cadr p2))))
   (list (+ ac ad bc) (+ ac bd))))

(defun pair-pow (p n)
  (cond
   ((= n 1) p)
   ((evenp n)
    (let ((result (pair-pow p (truncate (/ n 2)))))
      (pair-multiply result result)))
   (let ((result (pair-pow p (truncate (/ n 2)))))
     (pair-multiply p (pair-multiply result result)))))

(defun fast-fib (n)
  (if (zerop n)
   0
   (car (pair-pow '(1 0) n)))


And CLISP says :
;; Loading file fibonacci.lisp ...
*** - SYSTEM::%EXPAND-FORM: (RESULT (PAIR-POW P (TRUNCATE (/ N 2)))) should be
a lambda expression
The following restarts are available:
SKIP :R1 skip (DEFUN PAIR-POW # ...)
STOP :R2 stop loading file C:\Users\Andre\Codes\fibonacci.lisp
ABORT :R3 Abort main loop
Break 1 [2]>


I wonder where my mistake is ...

Re: How to convert this Scheme code ?

PostPosted: Sun Oct 12, 2008 6:52 am
by Exolon
Hi, the 'default' answer for a cond still needs an expression, which yours doesn't have.

This works for me:
Code: Select all
(defun pair-pow (p n)
  (cond
   ((= n 1) p)
   ((evenp n)
    (let ((result (pair-pow p (truncate (/ n 2)))))
      (pair-multiply result result)))
   (t (let ((result (pair-pow p (truncate (/ n 2)))))
     (pair-multiply p (pair-multiply result result))))))


[edit]
SBCL gave quite unhelpful (to a newbie like myself, anyway) advice as well... is debugging Lisp always so tricky?

Re: How to convert this Scheme code ?

PostPosted: Sun Oct 12, 2008 9:51 am
by qbg
Exolon wrote:[edit]
SBCL gave quite unhelpful (to a newbie like myself, anyway) advice as well... is debugging Lisp always so tricky?

Are you talking about something like this for PAIR-POW (from the first post)?
Code: Select all
; in: LAMBDA NIL
;     ((RESULT (PAIR-POW P (TRUNCATE (/ N 2)))))
;
; caught ERROR:
;   illegal function call

;     (PAIR-MULTIPLY P (PAIR-MULTIPLY RESULT RESULT))
; ==>
;   P
;
; note: deleting unreachable code

; in: LAMBDA NIL
;     (COND ((= N 1) P)
;           ((EVENP N)
;            (LET ((RESULT #))
;              (PAIR-MULTIPLY RESULT RESULT)))
;           (LET ((RESULT (PAIR-POW P #)))
;             (PAIR-MULTIPLY P (PAIR-MULTIPLY RESULT RESULT))))
; --> IF COND IF COND
; ==>
;   (IF LET
;       (PROGN
;        ((RESULT (PAIR-POW P #)))
;        (PAIR-MULTIPLY P (PAIR-MULTIPLY RESULT RESULT)))
;       NIL)
;
; caught WARNING:
;   undefined variable: LET

;     (PAIR-MULTIPLY RESULT RESULT)

; caught WARNING:
;   undefined variable: RESULT

;
; caught WARNING:
;   These variables are undefined:
;     LET RESULT
; compilation unit finished
;   caught 1 ERROR condition
;   caught 3 WARNING conditions
;   printed 1 note

You just need to remember what SBCL is doing here. Remember that COND is a macro, so here the error is showing up from the macroexpanded code. In particular, you can see:
Code: Select all
;   (IF LET
;       (PROGN
;        ((RESULT (PAIR-POW P #)))
;        (PAIR-MULTIPLY P (PAIR-MULTIPLY RESULT RESULT)))
;       NIL)

This isn't the code you would want produced, so that is a hint that you problem probably lies around (let ((result ...))) in the code.

If you were using SLIME and the code was in a file, SLIME would highlight underline the sections of code that the notes are talking about.

SBCL, in its typical very verbose, helpful, and pedantic style, is detecting the error before you run the code, which would drop you into the Lisp debugger.

Re: How to convert this Scheme code ?

PostPosted: Sun Oct 12, 2008 10:03 am
by smithzv
SBCL gave quite unhelpful (to a newbie like myself, anyway) advice as well... is debugging Lisp always so tricky?


In my experience, yes. But in my experience with other compilers (non-Lisp), they also give fairly unhelpful messages. Of course these messages all make sense in retrospect. CLISP is complaining about a form like (form1 &rest more-stuff) where form1 doesn't look like a function name or a lambda expression. SBCL probably complained about this and the undefined variable LET.

All of these things serve as cues to your previous experiences with debugging, which help you figure out what you did wrong. I think the same is true of most any debugging experience. I know that's why I usually feel that debugging C is easier than debugging Lisp. I have years of experience with C that tells me that "parse error before ..." means a missing semicolon, "nested functions are not supported" means I missed a closing brace (somewhere), and so on.

As for interactive debugging, I have never really gotten the hang of it. I end up using print statement quite often. I remember the power of gdb and how I could debug problems much faster than my printf-ing boss because I knew how to use it. Seems like I have become less of an expert in debugging since switching to Lisp. Does anyone know of any resources out there for advanced lisp debugging, maybe with Slime?

Zach

Re: How to convert this Scheme code ?

PostPosted: Sun Oct 12, 2008 11:09 am
by Paul Donnelly
Exolon wrote:SBCL gave quite unhelpful (to a newbie like myself, anyway) advice as well... is debugging Lisp always so tricky?

I think most Lispers would say it's easy, especially compared to the lengthy yet meaningless errors you get in other languages. To me, that error said that something was funny around (RESULT (PAIR-POW P (TRUNCATE (/ N 2)))), and looking at it it was obvious that the COND was malformed there. And with Slime, I can press enter when on a note in the *SLIME Compiler-Notes* buffer, and it will move the cursor in the other window to the code in question.