difference between labels and defun?

[Jinsong Zhao]

Hi there,

I learned that labels are used in Common Lisp for defining local functions.

(defun fib-1 (n)
(labels ((fib-iter (a b c)
(if (zerop c)
b
(fib-iter (+ a b) a (1- c)))))
(fib-iter 1 0 n)))

When I read SICP, I learned that the above code could be written as:

(defun fib-2 (n)
(defun fib-iter (a b c)
(if (zerop c)
b
(fib-iter (+ a b) a (1- c))))
(fib-iter 1 0 n)

It seems that the fib-2 function has a clear structure, isn't it?

Is there any difference between the two piece codes? Thanks in advance.

Best,
Jinsong

[Jack Mudge]

SICP is written using the Scheme language - which is a lisp-1, so all variable values and functions share the same namespace (Side note - in Scheme, it's (define) for both, without a distinct (defun) and (defvar), for exactly this reason.).

Common Lisp, on the other hand, is a lisp-2 (er, I guess more of a lisp-n, there are multiple values associated with a symbol, of which symbol-value and symbol-function are just two). In the Common Lisp version of your code, (labels) introduces function names. You could have something else by the same name that stores a data value instead.

For example, this is perfectly legal but would cause problems in Scheme:

(defun my-test-func ()
(labels ((minus-one (n) (1- z)))
(let ((minus-one 0))
(minus-one minus-one))))

The problem in Scheme is that when you attempt to call (minus-one minus-one), the value stored there is the number 0 - not the function (minus-one). In Common Lisp, those are separate, so the code returns -1 as expected.

[Jinsong Zhao]

On 2017/3/20 13:05, Jack Mudge wrote:
> On Sunday, March 19, 2017 at 6:06:35 PM UTC-7, Jinsong Zhao wrote:
>> Hi there,
>>
>> I learned that labels are used in Common Lisp for defining local functions.
>>
>> (defun fib-1 (n)
>> (labels ((fib-iter (a b c)
>> (if (zerop c)
>> b
>> (fib-iter (+ a b) a (1- c)))))
>> (fib-iter 1 0 n)))
>>
>> When I read SICP, I learned that the above code could be written as:
>>
>> (defun fib-2 (n)
>> (defun fib-iter (a b c)
>> (if (zerop c)
>> b
>> (fib-iter (+ a b) a (1- c))))
>> (fib-iter 1 0 n)
>>
>> It seems that the fib-2 function has a clear structure, isn't it?
>>
>> Is there any difference between the two piece codes? Thanks in advance.
>>
>> Best,
>> Jinsong
>
> SICP is written using the Scheme language - which is a lisp-1, so all variable values and functions share the same namespace (Side note - in Scheme, it's (define) for both, without a distinct (defun) and (defvar), for exactly this reason.).
>

Yes, I know SICP is written using Scheme. I know a little about Scheme.
Thanks for the explanation.

> Common Lisp, on the other hand, is a lisp-2 (er, I guess more of a lisp-n, there are multiple values associated with a symbol, of which symbol-value and symbol-function are just two). In the Common Lisp version of your code, (labels) introduces function names. You could have something else by the same name that stores a data value instead.
>
> For example, this is perfectly legal but would cause problems in Scheme:
>
> (defun my-test-func ()
> (labels ((minus-one (n) (1- z)))

here, a typo, z should be n.

> (let ((minus-one 0))
> (minus-one minus-one))))
>
> The problem in Scheme is that when you attempt to call (minus-one minus-one), the value stored there is the number 0 - not the function (minus-one). In Common Lisp, those are separate, so the code returns -1 as expected.
>

Thanks for the excellent example.

Best,
Jinsong

[Barry Fishman]

The primary difference is that in the first the fib-iter function is
only defined within the fib-2 function (lexically scoped), but in the
second it becomes a top level function that can be used anywhere in the
program, The equivalent of:

(defun fib-iter (a b c)
(if (zerop c)
b
(fib-iter (+ a b) a (1- c))))

(defun fib-2 (n)
(fib-iter 1 0 n))

If you wish to limit the scope of internal functions so they don't
exist in the global name-space, then the labels construct is preferred.

This may not be as significant if you are working within a package
and not exporting the fib-iter function. In general, when such helper
functions are use, they are given less generic names to indicate this
status.

The other approach is to put the internal state into optional arguments:

(defun fib-3 (n &optional (a 1) (b 0))
(if (zerop n)
b
(fib-3 (1- n) (+ a b) a)))

Which has the adverse effect of not being as clear about the number of
arguments the fib function should be given.

Recursive functions in Common Lisp may or may not be a problem,
depending on the number of recursions involved and whether the
implementation used does tail call optimization (TCO), which is not required.

The non-recursive approach would be something like:

(defun fib-4 (n)
(loop
for a = 1 then (+ a b)
and b = 0 then a
repeat n
finally (return b)))

--
Barry Fishman

[Pascal J. Bourguignon]

Yes.

The main difference is that in the second case, fib-iter won't be
defined until fib-2 is called. And when it will be called again,
fib-iter will be RE-defined. Also, as fib-iter is defined globally, it
may:

1- override an existing global fib-iter (which LABELS wouldn't do).

2- be overriden by another function, notably in another thread,
(which wouldn't be possible with LABELS).


So, in Common Lisp, you most definitely don't want to use defun inside
another defun.

Actually, in general in Common Lisp, you won't use any def* or define-*
operators in other places than the top-level (or top-level preserving
forms, such as EVAL-WHEN or PROGN).



--
__Pascal J. Bourguignon
http://www.informatimago.com