1

I found it seems only in lisp can define this:

(lambda (x)(+ x y 1))

in other languages,even it's functional language,a variable must define first,then to use it

so in lisp,there is concept "free variable","bound variable".Is other language have this concept?because all variable must define first,so all variable is "bound variable"?The variable have an initial value,in the global or other scope?

I think the lambda concept is early,but if any variable,or value,must define first then to use,isn't it easyier to understand and to use?

Thanks!

Improve this question
3
  • 2
    There are thousand of languages where variables doesn't have to be declared or defined before use. A couple of the more prominent being Python and Javascript. Commented Jul 2, 2019 at 7:44
  • this is common in many languages, eg. python: f=lambda x: x+y Commented Jul 2, 2019 at 7:44
  • Thanks! I only know some languages.In ocaml or f#,when define "fun x->x+y+1",got error "unbound value y".In ruby,I can define " a=->(x){x+y+1}",but when use "a.call(1)",got same error.In scala got same error:"(x:Int)=>x+y+1".and In the imperative language,ofcouse I got same error.only in lisp(r5rs in rocket),I can define: (lambda (x)(+ x y 1)) and I can use it: ((lambda (x)(+ x y 1)) 1) ;;got 2 Commented Jul 2, 2019 at 8:02

3 Answers 3

Reset to default
5

I think this question has two parts. There is a general question of free variable access in Lisp (and other languages), which is a large subject since there are many, many Lisps and even more other languages, including ones with dynamic scope for some variables (CL) and ones which have only dynamic scope (elisp until recently, many other old implementations). There is also a question about when variable references need to get resolved in Lisps (and other languages), and in particalar the need for forward references and when and how they get resolved..

In this answer I am only addressing the second part, about forward references, which I think is what is directly confusing you. I will give examples using Racket, with the r5rs language, as that is what you have used in a comment.

First of all, any language which supports recursion without jumping through extreme hoops (aka using the Y combinator) needs to support references to names which are not yet bound, which are called forward references. Consider this:

#lang r5rs

(define foo
  (lambda (x)
    (if (null? x)
        0
        (+ 1 (foo (cdr x))))))

OK, so when the function is evaluated there is a reference to foo for the recursive call. But foo is not yet bound at that point, because foo is going to be bound to the function itself and that's what we're defining. And indeed if you do something like this:

(let ((r (lambda (x)
           (if (null? x)
               0
               (+ 1 (r (cdr x)))))))
  r)

This is an error, because r is indeed not yet defined. Instead you need to use letrec which does suitable magic to ensure that things work.

Well, you might argue that letrec turns into something like this:

(let ((r #f))
  (set! r (lambda (x)
            (if (null? x)
                0
                (+ 1 (r (cdr x))))))
  r)

And perhaps it does. But what about this?

#lang r5rs

(define foo
  (lambda (x)
    (if (null? x)
        0
        (bar x))))

(define bar
  (lambda (x)
    (+ 1 (foo (cdr x)))))

And for on for more elaborate programs.

So there is a general problem here about forward reference. It is essentially impossible to write programs in such a way that, in the text of the program, there are not references to names which are not yet known about. Note that in the above program foo refers to bar and bar refers to foo so there is no order of the definitions of foo and bar which does not involve references to names which are not yet bound in the source.

Note that this problem affects essentially all programming languages: this is nothing unique to Lisp-family languages.

So, how is this resolved? Well, the answer is 'it depends on how the specific language you care about is defined'. I am not completely sure what the R5RS specification says about this, but I think I am sure what Racket says about it.

What Racket says is that forward references all need to be sorted out at the module level. So if I have a Racket source file like this:

#lang r5rs

(define a
  (lambda (x) (+ x y)))

(define y 1)

This is fine, because at the end of the module both a and x are defined, and so the definition of a is fine. This is no different than the definitions of foo and bar above, and note that a source file like this:

#lang r5rs

(define foo
  (lambda (x)
    (if (null? x)
        0
        (bar x))))

is not legal: bar is not bound:

$ racket ts.rkt
ts.rkt:7:9: bar: unbound identifier
[...]

So the answer to the question of forward-reference is two-fold:

  • writing programs in almost any practical language, and in particular in Lisps, requires forward references to names which are not yet bound at the point of reference;
  • language specifications need to define when and how such forward references get resolved.

I think that this is what is confusing you. In particular a Racket module which contains only this:

#lang r5rs

(define a (lambda (x) (+ x y)))

Is not legal in Racket. But this module:

#lang r5rs

(define a (lambda (x) (+ x y)))
(define y 1)

Is legal, because y is bound at the point when forward references get resolved.

Common Lisp is more complicated than this for two reasons:

  • it's a Lisp-2, so function and variable bindings live in different namespaces;
  • there are no standard toplevel lexical variable bindings.

So for instance if we take something like this (assumed to be at toplevel, with no other user definitions preceeding it):

(defun foo (x)
  (+ x y))

Then y can't be a reference to a lexical variable, because the lexical environment of foo is empty, since there are no toplevel lexical variable bindings.

So y must be a reference to a dynamic variable (a special variable in CL speak). But in fact, CL resolves the forward-reference problem for dynamic variables by saying that such references are not allowed. So the above definition is not legal CL. Many compilers will compile it with a warning, but they don't have to.

The following variant, however, is fine (note I've used the CL convention for dynamic variables).

(defvar *y* 1)

(defun foo (x)
  (+ x *y*))

This is fine because *y* is known about before foo is defined.

And in fact I lied: forward references to dynamic vaiables are allowed, but you have to tell the language about them:

(defun foo (x)
  (declare (special *y*))
  (+ x *y*))

And now, if there is a later (defvar *y* ...) (or equivalent) a call to foo will be fine. If there is no such globally-special proclamation of *y* then I think what happens if foo is called is either undefined or an error (and I kind of hope the latter but I'm not sure.

Finally, even without a global special proclamation for *y*, this is also fine:

(let ((*y* 3))
  (declare (special *y*))
  (foo 1))

This is fine because *y* is locally declared special (there is a bound declaration for it).

Forward references to functions are allowed in CL, and there are complicated rules about when they need to be resolved which I am not sure I can remember.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

AFAIK in CL, forward references are delimited by compilation units, i.e. files and the outermost with-compilation-unit (clhs.lisp.se/Body/m_w_comp.htm) blocks.
@coredump I don't think so: you can compile a file with a function which calls an unknown function, load that file and then define the unknown function and I am almost sure that should work (assuming there were no ftype declarations &c). The compiler could warn but I think no more than that.
I was thinking about warnings, yes; it is true that CL does not object having unknown things
3

In Common Lisp the exact effects of using undefined variables is undefined.

Common Lisp compilers will warn:

* (lambda (x) (+ x y 1))

; in: LAMBDA (X)
;     (+ X Y 1)
; --> + 
; ==>
;   (+ X Y)
; 
; caught WARNING:
;   undefined variable: COMMON-LISP-USER::Y
; 
; compilation unit finished
;   Undefined variable:
;     Y
;   caught 1 WARNING condition
#<FUNCTION (LAMBDA (X)) {226A95BB}>
Improve this answer

2 Comments

Thanks,I tried it.common lisp only give a warn,but allow it.clojure will not allow it ,give a error
@wangkai Clojure is a language that looks like Lisp; it borrows a lot of its syntax and concepts, but also brings in a lot of restrictions. It makes sense to allow free variables when compiling a lambda (with only a warning), because it's possible for those variables to exist later when the lambda is executed.
2

There are a few exceptions to the rule about being defined first and for all of them they define them on mention to some standard value. Eg. JavaScript uses undefined, perl uses undef, etc.

A bound variable is a variable form the current function scope. A free variable is either from a nested function scope or global, but they need to exist at runtime. 

(define test 
  ((lambda (a) 
     (lambda (b) 
       (list g a b)))
    5))
(define g 0)
(test 10)

So in the inner fucntion that has b as a bound variable. g and a are free variables since they are not from that functions parameters. That's what free means, and g doesn't need to be defined before mention in functions, but needs to exist before calling code that mentions.

In a lexical scoped language 5 will be bound to a such that the result will be (0 5 10) while in a dynamicly scoped language, eg. PicoLisp with slightly different syntax for the same, the answer would be (0 2 10) since the binding a in the creation of test is out of scope the second the code inside it has finished.

Almost all languages are lexically scoped. eg. all of OPs language tags (Ocaml, F#, Haskell, C# and Clojure) are lexically scoped.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.