Convert Scheme to Lisp (Recursive)

Discussion of Common Lisp
Post Reply
lispnewbie
Posts: 3
Joined: Mon Nov 28, 2011 1:16 am

Convert Scheme to Lisp (Recursive)

Post by lispnewbie » Mon Nov 28, 2011 1:33 am

I'm using LISP for several months. I know that Scheme is very similar to LISP, but I cannot understand the following Scheme functions. I read somewhere on the internet that "let loop" is used to create a recursive functions, but its argument "let loop ((x x))" doesn't make sense to me. Could you please explain and convert one function from scheme to LISP? Thank you so much for your help.

Code: Select all

(define (remove x xs)
  (let loop ((xs xs) (zs '()))
    (cond ((null? xs) (reverse zs))
          ((equal? (car xs) x) (loop (cdr xs) zs))
          (else (loop (cdr xs) (cons (car xs) zs))))))


(define (min es t r)
  (let loop ((es es) (min-e nil) (min-c nil))
    (cond ((null? es) min-e)
          ((or (and (member (cadar es) r) (member (caddar es) r))
               (and (member (cadar es) t) (member (caddar es) t)))
            (loop (cdr es) min-e min-c))
          ((or (not min-c) (< (caar es) min-c))
            (loop (cdr es) (car es) (caar es)))
          (else (loop (cdr es) min-e min-c)))))

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Convert Scheme to Lisp (Recursive)

Post by gugamilare » Mon Nov 28, 2011 7:12 am

I guess what confused you is the macro let. In scheme, this:

Code: Select all

(let loop ((var1 value1) ... (varN valueN))
  <body>)
is a way of creating loops. It's Common Lisp equivalent would be:

Code: Select all

(labels ((loop (var1 ... varN)
            <body>))
  (loop value1 ... valueN))

lispnewbie
Posts: 3
Joined: Mon Nov 28, 2011 1:16 am

Re: Convert Scheme to Lisp (Recursive)

Post by lispnewbie » Mon Nov 28, 2011 9:10 am

gugamilare, thank you so much. Also, could you help me a little more:

After created in the labels funtions, loop can be called only one time as the second argument. Is it possible to call loop more than one time and inside the body? (like my "min" function).

Do you think there is a way to write "let loop" as a recursive function in common lisp?

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Convert Scheme to Lisp (Recursive)

Post by gugamilare » Mon Nov 28, 2011 9:58 am

lispnewbie wrote:After created in the labels funtions, loop can be called only one time as the second argument.
That is not true, you can call the function loop as many times as you want, either inside it's own body, inside the body of another function created in the macro labels or inside the body of labels itself.
lispnewbie wrote:Is it possible to call loop more than one time and inside the body? (like my "min" function).
Yes, there is no problem in calling a function recursively more than once.
lispnewbie wrote:Do you think there is a way to write "let loop" as a recursive function in common lisp?
A local function inside labels that calls itself is already a recursive function. Unless you are thinking about not creating a local function and defining remove and min as recursive functions.

Just one note, though: Common Lisp already has functions named removed and min, so you should rename those functions.

saulgoode
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: Convert Scheme to Lisp (Recursive)

Post by saulgoode » Tue Nov 29, 2011 1:58 am

Just to elaborate a little on the explanation of the Scheme end of things.

The named let form

Code: Select all

(let loop ((var1 value1) ... (varN valueN))
  <body> )
is (as gugamilare suggested) merely syntactic sugar for a form that would originally be something akin to the following:

Code: Select all

(let ((loop #f))
  (set! loop (lambda (var1 ... varN)
                     <body> ))
  (loop value1 ... valueN) )
It would not work to assign the lambda directly -- as in (let ((loop (lambda ... ) -- because then 'loop' will not have been defined at the time the lambda is being created; just as "(let ((x x)) ..." would fail if 'x' has not been defined previously. By creating 'loop' before it is actually bound with the lambda, it can then be referenced within the lambda's body. The initial assignment of 'loop' (#f) does not matter because it gets re-bound to the lambda before the lambda is ever applied to the values.


As a side note, the normal let form:

Code: Select all

(let ((var1 value1) ... (varN valueN))
  <body> )
is similarly syntactic sugar for an application of a lambda:

Code: Select all

((lambda (var1 ... varN)
         <body> )
  value1 ... valueN )

lispnewbie
Posts: 3
Joined: Mon Nov 28, 2011 1:16 am

Re: Convert Scheme to Lisp (Recursive)

Post by lispnewbie » Tue Nov 29, 2011 12:31 pm

Thanks, guys. i didn't wrote these scheme functions, I found them online when I searched for Lisp. The way they named args and values made me confused. Now I can understand and can convert them to a similar common lisp function.

Code: Select all

(defun remove1 (x xs)
	(labels ((loop (a1 zs)
			(cond  ((null a1) (reverse zs))
				((equal (car a1) x) (loop (cdr a1) zs))
				(t (loop (cdr a1) (cons (car a1) zs))))
			))
		(loop xs '())
	)
)

Post Reply