let bindings & lambda expressions

Discussion of Common Lisp
Post Reply
pottendo
Posts: 4
Joined: Mon Apr 26, 2010 2:01 pm

let bindings & lambda expressions

Post by pottendo » Mon Apr 26, 2010 2:52 pm

hi Experts!

I'm new so please be patient with me - I tried to search the web and this forum, but didn't find a useful hint.

For my own educational purposes I'm writing a Lisp interpreter (in Java).
Now I have a question related to the visibility of variables, closures, functions - and the "correct" interpretation.

Consider the following s-exp (it doesn't do anything useful):
(let* ((y (lambda (x) (when x (funcall y (cdr x)))))) (funcall y '(a b c)))

The idea is to locally bind a lambda-expr to a variable `y', which is to be called in the let body.
[ note, I know that `flet' should be the way to go, but let's keep the example for a second ]
The function happens to be recursive.

SBCL gives me:
CL-USER> (let* ((y (lambda (x) (when x (funcall y (cdr x)))))) (funcall y '(a b c)))
The variable Y is unbound.
[Condition of type UNBOUND-VARIABLE]

(as GNU CL does).

I wonder, why this is the case. I mean, at eval time of the let expression, the lambda expression can be bound to `y' and the `bindings' of the let are successfull (and SBCL is happy, when I don't `funcall'!). `Y' should then be bound to my function and should be kept within the closure of the function returned by my lambda expression. So during `funcall' the `Y' is visible from the closure and should be callable even within the function itself.

btw, my implementation throws `unbound Y' as well, if I change the expression to
(let ((y (lambda (x) (when x (funcall y (cdr x)))))) (funcall y '(a b c)))
(without `*' after the let).
This is more an accident that "design", I have to admit. But somehow consistent with the let vs. let* semantics.

As I'm the newbie, I think I must have overlooked something.
Can you point me to the relevant part of CLtL specs where I might seek for enlightenment?

thanx,
pottendo

PS: Note that I'm doing an interpreter (not compiler, yet).
PPS: If you're interested in my project, send me an email.
--
You know, you've been hacking Lisp too long,
(when...

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

Re: let bindings & lambda expressions

Post by ramarren » Mon Apr 26, 2010 10:38 pm

pottendo wrote:I wonder, why this is the case. I mean, at eval time of the let expression, the lambda expression can be bound to `y' and the `bindings' of the let are successfull (and SBCL is happy, when I don't `funcall'!). `Y' should then be bound to my function and should be kept within the closure of the function returned by my lambda expression. So during `funcall' the `Y' is visible from the closure and should be callable even within the function itself.
I am not sure if you quite understand the difference between lexical scope and dynamic extent. That the lambda function doesn't see the binding of Y has nothing to do with time, but it is because bindings created by LET* are not in lexical scope within their init forms.
CLHS wrote:...first evaluates the expression init-form-1, then binds the variable var1 to that value; then it evaluates init-form-2 and binds var2, and so on.
This is indicated by the warning emitted when compiling the form in SBCL:

Code: Select all

CL-USER> (compile nil '(lambda () 
                        (let* ((y (lambda (x)
                                    (when x
                                      (funcall y (cdr x))))))
                          (funcall y '(a b c)))))
; 
; caught WARNING:
;   undefined variable: Y
; 
; compilation unit finished
;   Undefined variable:
;     Y
;   caught 1 WARNING condition

pottendo
Posts: 4
Joined: Mon Apr 26, 2010 2:01 pm

Re: let bindings & lambda expressions

Post by pottendo » Tue Apr 27, 2010 2:01 am

hi,

thanx for the quick response.
Ramarren wrote: ...
I am not sure if you quite understand the difference between lexical scope and dynamic extent. That the lambda function doesn't see the binding of Y has nothing to do with time, but it is because bindings created by LET* are not in lexical scope within their init forms.
You may be right about my understanding. ;)
Although my implementation somehow seems to understand.

Reading the specs again I find the following quite clear supporting SBCL et al.:
CLHS wrote: The special form let has the property that the scope of the name binding does not include any initial value form. For let*, a variable's scope also includes the remaining initial value forms for subsequent variable bindings.
Someone might interpret `... scope also includes the remaining initial value forms' in a way that the `current' variable might be already part of those `remaining' init-value forms. However this only makes sense if the init-form is a lambda expression, where the body is not evaluated (valid for interpreters, compilers might see things differently).
I assume, that's the reason, why `flet' has been invented.

bye,
pottendo
--
You know, you've been hacking Lisp too long,
(when...

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: let bindings & lambda expressions

Post by Jasper » Tue Apr 27, 2010 7:57 am

Code: Select all

(let ((y (lambda (x) (when x (funcall y (cdr x)))))) (funcall y '(a b c)))
Y is not yet defined in the LAMBDA there. It is only defined in the body, or in the case of LET*, subsequent vars and the body. So you cannot make a recursive function with putting the output into a LET from LAMBDA.
pottendo wrote:I assume, that's the reason, why `flet' has been invented.
Actually, you might want to look at LABELS,(should've been called FLET*) this can do recursive definition of local functions; it would do your example thusly:(not tested)

Code: Select all

(labels ((y (x)
           (when x (y (cdr x))))
   (y '(a b c))) ;==> nil

pottendo
Posts: 4
Joined: Mon Apr 26, 2010 2:01 pm

Re: let bindings & lambda expressions

Post by pottendo » Tue Apr 27, 2010 9:11 am

hi,

thanx for the comment.
actually I know how to overcome (using `labels) the problems in this scenario. I just wanted to understand better (which I do now) to have a correct implementation.
Unfortunately, as I'm doing an interpreter it's more difficult to inhibit the visibility of `y' in the lambda body in case of let*, as my implementation takes care of the closure and related handling of the bindings (dynamic-extents) when `lambda' is evaluated.
It doesn't do anything with the body, so a potential recursive access to a variable-binding in the function body is only detectable at invocation time - again, all this applies to my current implementation.

I already have a `solution' in mind, I won't share before I see a proof of concept... ;)

bye,
pottendo
--
You know, you've been hacking Lisp too long,
(when...

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

Re: let bindings & lambda expressions

Post by ramarren » Tue Apr 27, 2010 9:58 am

pottendo wrote:Unfortunately, as I'm doing an interpreter it's more difficult to inhibit the visibility of `y' in the lambda body in case of let*, as my implementation takes care of the closure and related handling of the bindings (dynamic-extents) when `lambda' is evaluated.
If you are 'inhibiting' the visibility of a binding then you should probably rethink what you are doing. First, decide whether the default scope is lexical or indefinite.

If it is lexical, then there is nothing to inhibit, since the 'y' lexical mark will refer to different storage, and that it has the same name will be irrelevant. Answers to this stackoverflow question provide some hints on how to build lexical scope in an interpreter.

If your interpreter uses indefinite scope, then the closure seeing the 'y' binding is a valid behaviour, since all variables are essentially global.

Trying to 'inhibit visibility' case by case will only lead to very confused semantics.

pottendo
Posts: 4
Joined: Mon Apr 26, 2010 2:01 pm

Re: let bindings & lambda expressions

Post by pottendo » Wed Apr 28, 2010 1:39 pm

hi,

as I use the CL specs as a reference I want the semantics of a CL implementation. So I want to see lexical scoping.
My fix I had in mind indeed solved the non-compliance.

Thanx for the hint to http://stackoverflow.com/questions/2384 ... mplemented
There are interesting links to find there.
My implementation follows the suggestion
stackoverflow wrote: * In your interpreter, variables are always looked up in an environment table passed in by the caller/kept as a variable, not some global env-stack. That is, eval(expression, env) => value.
* When interpreted code calls a function, the environment is NOT passed to that function. apply(function, arguments) => value.
* When an interpreted function is called, the environment its body is evaluated in is the environment in which the function definition was made, and has nothing whatsoever to do with the caller. So if you have a local function, then it is a closure, that is, a data structure containing fields {function definition, env-at-definition-time}.
bye,
pottendo
--
You know, you've been hacking Lisp too long,
(when...

dlweinreb
Posts: 41
Joined: Tue Jul 01, 2008 5:11 am
Location: Lexington, MA
Contact:

Re: let bindings & lambda expressions

Post by dlweinreb » Sat May 08, 2010 9:26 am

The basic idea for evaluating a "let" (of one variable, just to keep it simple) is: first, evaluate the init form, in the current environment, and call the result R. Then, make the variable, and make its value be R. So the variable has not yet been created/bound while the init form is being evaluated.

You should definitely use "labels" for this, so that the function can be recursive.

Post Reply