let bindings & lambda expressions

[pottendo]

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.

[ramarren]

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.

...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]

hi,

thanx for the quick response.

...
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.:

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

[Jasper]

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.

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]

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

[ramarren]

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]

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

* 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

[dlweinreb]

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.