Search code examples
language-featureslexical-scopedynamic-scope

When does lexical scoping binding take place - in runtime or compile time?


C language take scope binding during compile time (variable reference get fixed address - doesn't change at all), that is example of static scoping.

Elisp language take scope binding during run time (variable point to top of own personal reference stack, let/defun/... special forms add to the top of stack on entry from top on the leave - in that time capture modified), that is example of dynamic scoping.

What type of binding used in lexical scoping?

Such language as Common Lisp, Python, R, JavaScript state that they implement lexical scoping.

What technics are used in implementation for that languages?

I hear about environments that carried with function appearance. If I right - when was environments created?

Is it possible or usual to construct and bind environment to function by developer manually? Some thing like call( bind_env(make_env({buf: [...], len: 5}), myfunc) )


Solution

  • In short, lexical scoping takes place at compile time (or more precisely, at the time when the function definition is evaluated). Also, lexical scoping can be static scoping: this is how ML-languages (SML, OCaml, Haskell) do it.

    Environments

    Every function is defined in some environment. Also, each function creates its own local environment nested in enclosing environment. Top level environment is where all usual variables, functions (+, -, sin, map, etc.) and syntax (relevant for languages that can extend syntax, like Common Lisp, Scheme, Clojure) are defined.

    Each function creates its own local environment nested in enclosing environment (e.g., top level or of other function). Function arguments and all local variables live in this environment. If function reference a variable or a function that is not defined in the local environment (called free in this environment) it is found in enclosing environment of the function definition (or higher in enclosing env of enclosing environment if it is not found there and so on). This is different from dynamic scoping where the value would be found in the environment from where the function is called.

    I am going to illustrate this using Scheme:

    y is free in this definition

    (define (foo x)
        (+ x y))
    

    Here is y defined in top-level environment

    (define y 1)
    

    Introduce local 'y', but foo will use y from enclosing (top-level) environment of the definition. Hence, the result is 2 and not 11.

    (let ((y 10))
         (foo 1))
     => 2
    

    You can also define a function (or a procedure in Scheme's terms) with a local environment enclosing it:

     (define bar
         (let ((y 100))
              (lambda (x) (+ x y))))
    
    (bar 1)
    => 101
    

    Here procedure value bar is defined to be a procedure. Variable y is again free in the procedure body. But enclosing environment is created by let form in which y is defined to be 100. So, when bar is called, it is that value of y which is fetched and not top-level (in a dynamically scoped language it would have returned 2).

    Answering your last question, it is possible to create your own environment manually, but it would be too much work and probably wouldn't be very efficient. When the language is implemented (for example, Scheme interpreter), that is exactly what the language developer is doing.

    Good explanation of environments is shown in SICP, Chapter 3

    Other comments

    AFAIK, from Emacs 23, ELisp is using lexical scoping as well as dynamic scoping (similarly to Common Lisp, see below).

    Common Lisp uses lexical scoping for local variables (introduced by let form) and dynamic scoping for global variables (they are also called special; it is possible to declare a local variable special, but it is rarely used) defined with defvar and defparameter. To distinguish them from lexically scoped variables, their names usually have "ear muffs", for example *standard-input*. Top-level functions are also special in CL, which can be rather dangerous: one can unknowingly alter behavior by shadowing top-level function. This why CL standard specifies the locks on standard library function to prevent their re-definition.

    Scheme, in contrast, always uses lexical scoping. Dynamic scoping, however, is useful sometimes (Richard Stallman makes a good point on it). To overcome this, many Scheme implementations introduced so-called parameters (implemented using lexical scoping).

    Languages like Common Lisp, Scheme, Clojure, Python keep a dynamic reference to a variable: you can construct the variable name from a string (intern a symbol in Lisp's terms) and find its value. More static languages, like C, OCaml or Haskell, cannot do that (unless some form of reflection is used). But this has a weak connection to what kind of scoping they use.