Question on 'let example - Successful Lisp

Discussion of Common Lisp
Post Reply
macrolyte
Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America

Question on 'let example - Successful Lisp

Post by macrolyte » Sun Jan 26, 2014 1:43 pm

Hi,
I'm stuck on a particular example used in the above mentioned book. The relevant code can be found here.

Code: Select all


; Closure captures assigned variable -- probably wrong 
? (let ((fns ()))
    (dotimes (i 3)
      (push #'(lambda () i) fns))
    (mapcar #'funcall fns))
(3 3 3)

What I think I know, so far:
  • 1. the 'let encloses all the variables within its scope: the loop variable 'i and the empty list 'fns.

    2. 'dotimes simply repeats the enclosed functions '3 times, (zero indexed so... (0 1 2)).

    3. 'push is cons'ing the lambda function onto 'fns (nice)

    4. the list (3 3 3) is undesired and is the effect of the closure created by the 'let over the iteration variable 'i. WHY?!
which really ain't much... so since I'm using Emacs/Slime/Clisp for learning/development I bravely tried:

Code: Select all


(step (let ((fn ()))(dotimes (i 3)(push #'(lambda()i)fn))))

And promptly had my mind blown. I won't post all the output since most of it would be overkill however this:

Code: Select all


step 9 --> (CONS #'(LAMBDA NIL I) FN)
Step 9 [29]> :s

step 10 --> #'(LAMBDA NIL I)
Step 10 [30]> :s

step 10 ==> value: #<FUNCTION :LAMBDA NIL I>
step 10 --> FN
Step 10 [31]> :s

step 10 ==> value: (#<FUNCTION :LAMBDA NIL I>)
step 9 ==> value: (#<FUNCTION :LAMBDA NIL I> #<FUNCTION :LAMBDA NIL I>)
step 8 ==> value: (#<FUNCTION :LAMBDA NIL I> #<FUNCTION :LAMBDA NIL I>)
step 7 ==> value: (#<FUNCTION :LAMBDA NIL I> #<FUNCTION :LAMBDA NIL I>)
step 7 --> (PSETQ I (1+ I))
Step 7 [32]> :s

step 8 --> (1+ I)
Step 8 [33]> :s

step 9 --> I
Step 9 [34]> :s

step 9 ==> value: 1
step 8 ==> value: 2
step 7 ==> value: NIL
step 7 --> (GO #:LOOP-3858)
Step 7 [35]> :s

step 7 --> (IF (>= I 3) (GO #:END-3859))
Step 7 [36]> :s

step 8 --> (>= I 3)
Step 8 [37]> :s

step 9 --> I
Step 9 [38]> :s

step 9 ==> value: 2
step 9 --> 3
Step 9 [39]> :s

step 9 ==> value: 3
step 8 ==> value: NIL
step 7 ==> value: NIL
step 7 --> (PUSH #'(LAMBDA NIL I) FN)

I believe that what I''m seeing is when in (step 9 ==> value: 3) evaluation, '3 is used because it's the last returned. Of course I may most certainly be dead wrong... I'm hoping that someone can explain this to me, please. Since this is my first post I'd like to send a shout out to everyone here. I am fascinated by Lisp and would like to use it correctly and with understanding as well as I possibly can. Respect and thanks to all.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Question on 'let example - Successful Lisp

Post by ramarren » Tue Jan 28, 2014 10:32 am

macrolyte wrote: 4. the list (3 3 3) is undesired and is the effect of the closure created by the 'let over the iteration variable 'i. WHY?!
The closures here are created by LAMBDA, which creates an anonymous function closing over its environment. LET is incidental and just holds the anonymous functions so that they can be called after the iteration.

There are three separate closures created, one for each iteration, but they are all over the same variable 'i', which is being modified by DOTIMES, so that once the functions are evaluated they all return the value of the variable 'i' at the time they are called, that is, 3.

Note that in the context of closures it is said that a construct 'encloses' or 'captures' something that is defined outside of it, in this case LAMBDA captures the 'i' defined in enveloping DOTIME, because it means that once captured the variable referenced remains valid even after the capturing closure leaves the scope it was originally defined in.

macrolyte
Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America

Re: Question on 'let example - Successful Lisp

Post by macrolyte » Tue Jan 28, 2014 2:03 pm

Thanks so very much for your reply. I'm still having a little trouble seeing it so:
Ramarren wrote:
The closures here are created by LAMBDA, which creates an anonymous function closing over its environment. LET is incidental and just holds the anonymous functions so that they can be called after the iteration.

Code: Select all


    -->(defparameter fns ()) ;; empty list
    -->fn
    -->NIL
    -->(dotimes (i 3)(push #'(lambda()i)fns)) ;; NO 'let
    -->NIL

So the 'let WAS incidental! Continuing :
Ramarren wrote:
There are three separate closures created, one for each iteration, but they are all over the same variable 'i', which is being modified by DOTIMES, so that once the functions are evaluated they all return the value of the variable 'i' at the time they are called, that is, 3.

Code: Select all


    -->(dotimes (i 3)(push #'(lambda()i)fns)(print i))
    0
    1
    2 NIL              ;; THIS COMPLETELY ELIMINATES BOTH THE 'let AND THE 'dotimes IN TOTAL!
    -->fns
    (#<FUNCTION :LAMBDA NIL I> #<FUNCTION :LAMBDA NIL I> #<FUNCTION :LAMBDA NIL I>) ;; THREE SEPARATE CLOSURES OVER THE SAME VARIABLE 'i
    -->(funcall (car fns))
    3
    -->(funcall (car (cdr fns)))
    3
    -->(funcall (car (cddr fns)))
    3                   ;; THE VALUE AT THE TIME EACH FUNCTION WAS CALLED?

Not knowing the mechanics of 'dotimes, especially in the context of the closure created by the lambda expression has me slightly confused. Believe me when I say I believe YOU, I just don't know how to deconstruct this process. I doubt there is a way to 'print what is going on, I'll try using the step macro again, unless you could do a very short code walk through perhaps ? ;)

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Question on 'let example - Successful Lisp

Post by ramarren » Tue Jan 28, 2014 2:21 pm

There are multiple ways to implement DOTIMES complying with specification, but the most common would essentially execute something like this:

Code: Select all

(let ((fns ()))
  (let ((i 0))
    (push #'(lambda ()
              i)
          fns)
    (setf i (1+ i))
    (push #'(lambda ()
              i)
          fns)
    (setf i (1+ i))
    (push #'(lambda ()
              i)
          fns)
    (setf i (1+ i)))
  (list (funcall (car fns))
        (funcall (cadr fns))
        (funcall (caddr fns))))
Observe the nesting carefully. Despite the fact that the LET which establishes the 'i' variable ends before the function is called, the memory location remains valid and functions which are referring to it can be safely called and return its value. All three anonymous functions refer to the same variable, so they return the same value.

There is nothing special about DOTIMES, the same applies to everything that modifies a value of a variable. The issue is that DOTIMES is not actually specified to modify the iteration variable, since it could for example create a new binding with the same time each time, so the behaviour cannot be relied on.

macrolyte
Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America

Re: Question on 'let example - Successful Lisp

Post by macrolyte » Tue Jan 28, 2014 5:54 pm

Ramarren wrote:
Despite the fact that the LET which establishes the 'i' variable ends before the function is called, the memory location remains valid and functions which are referring to it can be safely called and return its value. All three anonymous functions refer to the same variable, so they return the same value.

If I understand you correctly, the last value of 'i remains bound to it even AFTER the form is completed and it is this value which is used by the functions? Wow. And I really didn't expect the (3 3 3)...

I think I'll need some liquor after this...

Goheeca
Posts: 271
Joined: Thu May 10, 2012 12:54 pm
Contact:

Re: Question on 'let example - Successful Lisp

Post by Goheeca » Wed Jan 29, 2014 3:06 am

That's lexical closures. When you capture the variable which is bound by let, it remains valid. You dynamically (in run-time) leave that block, but lexically the lambda is still enclosed by a let form.
Example:

Code: Select all

* (let ((data))
  (list (lambda () data)
        (lambda (new) (setf data new))))

(#<CLOSURE (LAMBDA #) {24B85095}> #<CLOSURE (LAMBDA #) {24B850A5}>)
* (defvar closure *)

CLOSURE
* (funcall (second closure) 1)

1
* (funcall (first closure))

1
* (funcall (second closure) 2)

2
* (funcall (first closure))

2
*
The first lambda is a getter and the second one is a setter.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version). Temporary mirrors of aferomentioned: CLHS and a dark version.

Post Reply