How to convert this Scheme code ?

Discussion of Common Lisp

How to convert this Scheme code ?

Postby anta40 » Sun Oct 12, 2008 4:33 am

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 ...
anta40
 
Posts: 18
Joined: Fri Oct 10, 2008 10:27 pm

Re: How to convert this Scheme code ?

Postby Exolon » Sun Oct 12, 2008 6:52 am

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?
Exolon
 
Posts: 49
Joined: Sat Jun 28, 2008 12:53 pm
Location: Ireland

Re: How to convert this Scheme code ?

Postby qbg » Sun Oct 12, 2008 9:51 am

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.
qbg
 
Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

Re: How to convert this Scheme code ?

Postby smithzv » Sun Oct 12, 2008 10:03 am

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
smithzv
 
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: How to convert this Scheme code ?

Postby Paul Donnelly » Sun Oct 12, 2008 11:09 am

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.
Paul Donnelly
 
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm


Return to Common Lisp

Who is online

Users browsing this forum: Bing [Bot] and 2 guests

cron