difference between labels and defun within a function?

[Jinsong Zhao]

Hi there,

I learned that labels are used in Common Lisp for defining 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

[Kaz Kylheku]

On 2017-03-20, Jinsong Zhao <jsz...@yeah.net> wrote:
> Hi there,
>
> I learned that labels are used in Common Lisp for defining 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?

defun defines top-level functions. The second fib-2 has a deceptive
structure. It looks as if it defines a locally scoped function, but
in fact does not.

defun is effectively a "statement" which has a side effect. When
defun is *evaluated*, it binds a function to the given symbol in
the top-level function environment.

In the second fib-2 above, fib-iter doesn't exist until the first
time when fib-2 is called. Then a side-effect takes place: the fib-2
symbol's function binding is modified to point to the function
definition. This happens each time fib-2 is called.

By contrast, labels doesn't have a side effect; it is a lexical
binding construct which extends the lexical environment.
The binding it establishes isn't visible outside of that scope.

Since fib-iter is going to be global anyway, it should be defined
by a top-level defun.

Then it can be treated properly by the Lisp file compiler
(which specially recognizes defuns when they are top-level
froms) and we avoid the problem of every call to fib-2
having a side-effect of defining fib-iter.

[Jack Mudge]

I hadn't noticed that there's a duplicate thread for this and replied to the other one!

Correct me if I'm wrong, but isn't (defun) invalid in Scheme, whch SICP teaches? (define) has the side effect, but it is lexically scoped, so that in the SICP version (which appears to be in error) that is a lexical binding, within the scope of the outer define (incorrectly written as 'defun' in fib-2).

[Kaz Kylheku]

Indeed; where in SICP did he read about "defun" ...

In Scheme, define is a gadget which basically translates to let during
the code walking phase.

It can't be defined as an (ordinary) macro because it splices into the
surrounding syntax.

Something like:

(form ... (define x y) ...) -> (form ... (let ((x y)) ...))

[Jeff Barnett]

Kaz Kylheku wrote on 3/19/2017 9:01 PM:
> On 2017-03-20, Jinsong Zhao <jsz...@yeah.net> wrote:
>> Hi there,
>>
>> I learned that labels are used in Common Lisp for defining 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?
>
> defun defines top-level functions. The second fib-2 has a deceptive
> structure. It looks as if it defines a locally scoped function, but
> in fact does not.
>
> defun is effectively a "statement" which has a side effect. When
> defun is *evaluated*, it binds a function to the given symbol in
> the top-level function environment.

But isn't the inner defun "locally scoped", e.g., couldn't it reference
n? Of course each invocation of the outer defun would bind a different
n. I believe that scope rules for the inner defun are just like labels
or flet. The difference is what happens to the name of the definition,
and when and where.
--
Jeff Barnett

[Madhu]

* Jeff Barnett <oans9o$npv$1...@dont-email.me> :
Wrote on Mon, 20 Mar 2017 00:22:28 -0600:

| But isn't the inner defun "locally scoped", e.g., couldn't it
| reference n? Of course each invocation of the outer defun would bind
| a different n.

Yes, and on each invocation, the inner defun is re-evaluated and the
fdefinition is replaced with a new definition that closes over this `n'
location.

| I believe that scope rules for the inner defun are just like labels or
| flet.

Better to say they are just like for defun. I don't think they should
be compared with labels or flet, because while these two are local, with
defun a toplevel definition is always established.

| The difference is what happens to the name of the definition, and when
| and where.

The rules for flet and labels are more nuanced: eg. an flet can refer to
an outer definition with the #'outer syntax in its body.

labels is equivalent to flet except that the scope of the
defined function names for labels encompasses the function
definitions themselves as well as the body.

While it makes no sense for an inner defun to shadow the outer defun as
they are all global.

[Jack Mudge]

Yes. The other major difference that comes to mind is that (let ((x y)) ...) allows functions to be bound in Scheme (since it's a lisp-1; they share the same namespace as variables) -- that's where (labels) comes in in CL, and I think where part of the confusion comes from in the original example.

[Rob Warnock]

Kaz Kylheku <336-98...@kylheku.com> wrote:
+---------------

| It can't be defined as an (ordinary) macro because it splices into the
| surrounding syntax.
| Something like:
| (form ... (define x y) ...) -> (form ... (let ((x y)) ...))

+---------------

It's actually LETREC rather than LET, see:

http://schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-8.html#%_sec_5.2.2
5.2.2 Internal definitions

And if there are multiple adjacent internal DEFINEs,
they're all collected into *one* equivalent LETREC
[example at above URL]. Also, it's am equivalent
LETREC, *not* a (hypothetical) "LETREC*":

Just as for the equivalent LETREC expression, it must be
possible to evaluate each <expression> of every internal
definition in a <body> without assigning or referring to
the value of any <variable> being defined.

That is, something like this is not allowed:

(define (foo x)
(define bar (+ x 1))
(define baz (* bar 2))
baz)

Use a single LET* here instead of multiple DEFINEs.

(define (foo x)
(let* ((bar (+ x 1))
(baz (* bar 2)))
baz))


-Rob

-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <http://rpw3.org/>
San Mateo, CA 94403

[Jinsong Zhao]

Thanks for the explanation. I noticed that I can invoke the fib-iter
after fib-2 was called. It means that fib-iter in fib-2 is not locally
scoped.

In Scheme, I tried using glide, the fib-iter defined within fib-2 is
locally scoped. Is it so called the difference between lisp-1 and lisp-2?

Thanks again.

Best,
Jinsong

[Jinsong Zhao]

Sorry for the duplicated thread. The first thread is formatted messily.
So I delete it and posted again. However, I don't recognized that the
post message can't be deleted.

>
> Correct me if I'm wrong, but isn't (defun) invalid in Scheme, whch SICP teaches? (define) has the side effect, but it is lexically scoped, so that in the SICP version (which appears to be in error) that is a lexical binding, within the scope of the outer define (incorrectly written as 'defun' in fib-2).
>

There is not defun in Scheme. I know SICP using Scheme, and using define
instead of defun.

Thanks for the explanation.

Best,
Jinsong

[Jack Mudge]

I think it is more accurate to say that the result of calling fib-2 has a "global" side effect of defining fib-iter. fib-iter would have access to the variable n, which is closed over, that is not accessible outside of it after fib-2 has returned.

Example:

(defun test (n)
(defun test-inner (p)
(+ n p)))
(test 3) ; returns function test-inner, but now...
(test-inner 4) ; returns 7

This is called a closure. Scheme supports these, too, and in fact your inner defines, if they define functions, would be closed over as well. They just wouldn't *also* be saved in the "global" scope.

(Note that I put "global" in quotes; it's not exactly global - it's in the current package in CL.)

>
> In Scheme, I tried using glide, the fib-iter defined within fib-2 is
> locally scoped. Is it so called the difference between lisp-1 and lisp-2?
>

More or less. The question to ask when comparing a lisp-1 and a lisp-2 is how many values can be associated with a single symbol?

In Scheme, the answer is "exactly one"; if you

(define x
(lambda (y)
(+ y 5))
x ; returns a function
(x 3) ; returns 8
(x x) ; error - can't add function to integer or similar.

(Explicit lambda for clarity) But then subsequently:

(define x 5)
x ; returns 5
(x 3) ; error - not a function or similar.

So in Scheme, the symbol 'x refers to *either* a function or a variable, but not both. That is why it is a lisp-1.

In Common Lisp, on the other hand, the symbol 'x can hold a separate value for a variable and a function. My example in your duplicate thread was meant to address this (as I read it as the source of confusion), but here's perhaps a simpler example:

(defun x (y)
(+ y 5))
(defvar x 3)
(x x) ; returns 8 ***different from Scheme here.***

As clearly seen in the last expression, 'x can be either a function or a variable depending on where it is used. It is at least a lisp-2 because of that. You can address these values directly:

(symbol-function 'x) ; returns a function
(symbol-value 'x) ; returns 3



> Thanks again.
>
> Best,
> Jinsong

Hope it helps! I've used Scheme for longer than I've used CL, so I'm reasonably sure I've probably made some subtle error here, which hopefully someone will point out. The examples do work, though, I just tested them. :)

[Madhu]

* Jack Mudge <062b6264-14c2-409b...@googlegroups.com> :
Wrote on Mon, 20 Mar 2017 20:00:02 -0700 (PDT):

| This is called a closure. Scheme supports these, too, and in fact your
| inner defines, if they define functions, would be closed over as
| well. They just wouldn't *also* be saved in the "global" scope.
|
| (Note that I put "global" in quotes; it's not exactly global - it's in
| the current package in CL.)

This idea is wrong. In CL package are completely orthogonal to scoping.
The symbol may be qualified with a package name, but the function
binding for that symbol is still established in the global environment

[Jack Mudge]

My disclaimer seems to have been spot on.

Here is an example of what I was trying to articulate:

(defpackage test-1
(:use :cl))
(in-package test-1)
(defun test-func (n)
(+ n 5)

(defpackage test-2
(:use :cl))
(in-package test-2)
(test-func 3)

The last expression fails; my current understanding is that this is because the function was bound to the 'test-func symbol and interned in package test-1, which is the concept I was attempting to articulate.

(in-package test-2)
(test-1::test-func 3) ; returns 8

This still feels like a package-local/global distinction to me, but I think I understand why it is incorrect to phrase it that way: The binding for 'test-1::test-func to that particular function is accessible regardless of which package you happen to be in, it's just a question of whether it needs to be qualified with a package or not.

Is that more in line with what you have in mind?

[Kaz Kylheku]

The "global environment" Madhu is referring to isn't a feature of the
package system. It binds symbols to functions. The symbols come from
various packages.

(test-func 3) fails because the token test-func is interned in the
test-2 package, giving rise to the symbol test2::test-func.
This symbol is not related to test-1::test-func.

Make no mistake though: the failing lookup which results in the
error message **is looking** in the **same** global environment where
test-1::test-func has a binding! It's not finding what it is looking
for simply because it's looking for a binding of test-2::test-func.

Such a binding can coexist with test-1::test func; you just
haven't defined it.

That's the point of packages: we can have different symbols called
"TEST-FUNC" in different packages, and use them side by side
in the same environment.

Any environment.

A class can have slots that are named by symbols from different
packages.

A lexical scope can have variables named by symbols from
different packages.

A tagbody can have labels from different packages.

Etc.

[Jack Mudge]

I'd associated symbols with packages and bindings with symbols, but clearly that isn't a transitive relation. Thank you for the clarification!