Functional - A hairy loop

Author

A hairy loop

Xcriber51

2006-09-22, 7:01 pm

Hi

I'm new to LISP. Can you tell me why the loop below doesn't terminate?

(defun mod (n m)
(loop while (>= n m) do
(setq n (- n m)))
(return n))

Yes, I know, this is procedural thinking, LISP already has a MOD, etc. Any
ideas how I can implement it in a "purely" functional way?

Thanks

-- Ken

Pascal Bourguignon

2006-09-22, 7:01 pm

"Xcriber51" <xcriber@[OMITTED]> writes:

> Hi
>
> I'm new to LISP. Can you tell me why the loop below doesn't terminate?
>
> (defun mod (n m)
> (loop while (>= n m) do
> (setq n (- n m)))
> (return n))

Perhaps because you passed 0 for m?
Otherwise, it breaks in error because there's no block named NIL.

> Yes, I know, this is procedural thinking, LISP already has a MOD, etc. Any
> ideas how I can implement it in a "purely" functional way?

In emacs lisp:

(defun mod (n m)
(assert (< 0 m))
(loop while (>= n m) do
(setq n (- n m)))
n)

or:

(require 'cl)
(defun* mod (n m)
(assert (plusp m))
(loop while (>= n m) do
(setq n (- n m)))
(return-from mod n))

In Common Lisp:

(defun mod (n m)
(assert (plusp m))
(loop :while (>= n m)
:do (decf n m))
n)

or:

(defun mod (n m)
(assert (plusp m))
(loop :while (>= n m)
:do (decf n m))
(return-from mod n))

If you don't want to use assignment, you can write it as:

(defun mod (n m)
(assert (plusp m))
(if (< n m)
n
(mod (- n m) m)))

Of course they're erroneous when n<0.

A better definition would be:

(defun mod (n m)
(assert (and (realp n) (realp m) (plusp m)))
(cond ((minusp n) (mod (+ n m) m))
((< n m) n)
(t (mod (- n m) m))))

--
__Pascal Bourguignon__ http://www.informatimago.com/

"Klingon function calls do not have "parameters" -- they have
"arguments" and they ALWAYS WIN THEM."

Denis Bueno

2006-09-22, 9:59 pm

Xcriber51 wrote:
> Hi
>
> I'm new to LISP. Can you tell me why the loop below doesn't terminate?
>
> (defun mod (n m)
> (loop while (>= n m) do
> (setq n (- n m)))
> (return n))

If m = 0 and n >= m initially, n will never decrease; so it won't
terminate.

If m < 0 and n >= m initially, n will increase without bound; so it
won't terminate.

>
> Yes, I know, this is procedural thinking, LISP already has a MOD, etc. Any
> ideas how I can implement it in a "purely" functional way?

To get the same behavior as the loop above, you need to think about how
to loop using recursion. That sounds earth-shatteringly obvious, but if
I said more I fear I'd give the answer away.

There is merit in learning how recursion is powerful enough to
implement loops. However, some will tell you
[http://www-static.cc.gatech.edu/~sh...papers/loop.pdf] that writing
recursive functions just for looping is bad design. Judge for yourself.

-Denis

Denis Bueno

2006-09-22, 9:59 pm

Xcriber51

2006-09-23, 7:00 pm

Thanks, everyone.

I wasn't calling the function with either M = 0 or N < 0, but never mind
that. I'll study your suggestions -- and read that article, too.

In the meantime, I found a Qi solution -- with pattern matching and guards
-- which I hope is closer to the functional style:

(define mod {number --> number}
_ M -> "#DIV/0" where (= M 0)
N M -> (mod N (abs M)) where (< M 0)
N M -> (mod (+ N M) M) where (< N 0)
N M -> (mod (- N M) M) where (>= N M)
N _ -> N)

(This may not be mathematically entirely correct, but disregard that here.
I was just curious how it could be done.)

I can also use this as a helper function for its complement, the "div"
function:

(define div {number --> number}
N M -> (/ (- N (mod N M)) M))

Anyway, thanks again!

-- Ken

P.S. Yes, I like the functional thing -- especially after years of brain
damage with C/C++.

Sponsored Links