CS217 Day 4 Monday, April 3, 2000

Scoping and Binding of Variables

• Problem: Given a Scheme expression, mark each identifier as to whether it is free (must have a value at the top level) or bound (gets its value from an argument in a procedure call) or a let. If a variable is bound identify where it is declared.

  A variable can denote either a reference or a declaration. Variables are declared in formal parameter lists in lambda expressions and in "decls" within let, letrec expressions.

  (let ((x 3))
    (+ (let ((x (+ x 1)))
         ((lambda (x)
  	  (* x x))
  	x))
      x))
  
  (let ((x 3)
        (y 4)
        (z 5))
    (+ (let ((x (+ x 1)))
         ((lambda (x y)
  	  (* x y z))
  	x
          z))
      x))
  

• A C++ example:

  // scope.cc
  
  #include 
  
  void main() {
    int x = 3;
    int y;
    { 
      int x1 = x;
      int x = 4;
      {
        y = x + x1;
      }
    }
    cout << y << endl;
  }
  

• A an illegal Java example. In Java, you can't make an inner declaration of the same variable.

  // Scope.java
  
  public class Scope {
  
    public static int sqr(int x) {
      return x * x;
    }
  
    public static void main(String[] args) {
      int x = 3;
      int y;
      { 
        int x1 = x;
        int x = x1 + 1;  // NOT ALLOWED.  Can change x to x2.
  
        {
  	y = 10*x + x1;
        };
      }
      System.out.println(y);
    }
  }
  

• Each variable in a declaration has a region, the text in which the variable has meaning. The scope of a variable is its region except for the region of a redeclaration of the variable.

• We can identify the declaration of an occurrence of a variable v by giving its lexical address (: d p), where d is the variables lexical depth and p is its 0-based position within the list of variables in a declaration. The lexical depth of a variable is the number of declaration passed in scanning outward to get to a declaration of the variable.

  If an occurrence of a variable has a declaration, it is bound. Otherwise it is free.

• The depth of a variable within a list of lists of variables (vars0 ...) is the zero-based index of the first list in which it occurs, and its position is its zero-based position within that list.

  ;; index-of -- returns index of simple datum in a list or #f
  
  (define index-of
    (lambda (x lst)
      (if (null? lst)
  	#f
  	(if (eqv? x (car lst))
  	    0
  	    (let ((v (index-of x (cdr lst))))
  	      (if v
  		  (+ v 1)
  		  v))))))
  
  ;; (depth-pos v vlsts d0) -- returns depth and position, (: d p),
  ;; of a variable within a list of lists, vlsts, relative to d0,
  ;; else (: free).
  
  (define depth-pos
    (lambda (v vlsts d)
      (if (null? vlsts)
  	(list ': 'free)
      (let ((p (index-of v (car vlsts))))
        (if p
  	  (list ': d p)
  	  (depth-pos v (cdr vlsts) (+ d 1)))))))
  
  ;; Examples of depth-pos
  
  (depth-pos 'x '((x y) (x y z) (u v)) 0)
  (depth-pos 'y '((x y) (x y z) (u v)) 0)
  (depth-pos 'z '((x y) (x y z) (u v)) 0)
  (depth-pos 'u '((x y) (x y z) (u v)) 0)
  (depth-pos 'v '((x y) (x y z) (u v)) 0)
  (depth-pos 'w '((x y) (x y z) (u v)) 0)
  
  

We can use depth-pos to write lex-add which returns the lexical address of a Scheme datum relative to given nested declarations. E.g.,

;; (lex-add exp vlsts) => lexical address of exp relative to vlsts.
;; [exp] ::= [symbol] | (lambda [varlist] [exp]) | ({[exp]}+)

(define lex-add
  (lambda (exp vlsts)
    (cond ((symbol? exp)
	   (cons exp (depth-pos exp vlsts 0)))
	  ((eqv? (car exp) 'lambda)
	   (let ((formals (cadr exp))
		 (body (caddr exp)))
	     (list
	       'lambda
	       formals
	       (lex-add body (cons formals vlsts)))))
	  (else
	    (map (lambda (e)
		   (lex-add e vlsts))
	      exp)))))

;; Examples of lex-add

(lex-add '(x y z) '((x) (x y)))

(lex-add '((lambda (x y)
	     ((lambda (y z)
		(x y z w))
	      (x y z w)))
	   (x y z w))
  '())

Scheme code: cs217d4.scm

Formal Syntax for Scheme expressions (From R5RS, 7.1.3)

[expression] ::= [variable] | [literal] | [procedure call]
                | [lambda expression] | [conditional] | [assignment]
                | [derived expression] | [macro use] | [macro block]

[literal] ::= [quotation] | [self-evaluating]

[self-evaluating] ::= [boolean] | [number] | [character] | [string]

[quotation] ::= '[datum] | (quote [datum])

[procedure call] ::= ([operator] [operand]*)

[operator] ::= [expression]

[operand] ::= [expression]

[lambda expression] ::= (lambda [formals] [body])

[formals] ::= ([variable]*) | [variable] | ([variable]+ . [variable])

[body] ::= [definition]* [sequence]

[sequence] ::= [command]* [expression]

[command] ::= [expression]

[conditional] ::= (if [test] [consequent] [alternate])

[test] ::= [expression]

[consequent] ::= [expression]

[alternate] ::= [expression] | [empty]

[assignment] ::= (set! [variable] [expression])

[derived expression] ::=
       (cond [cond clause]+)
     | (cond [cond clause]* (else [sequence]))
     | (case [expression]
         [case clause]+)
     | (case [expression]
         [case clause]*
         (else [sequence]))
     | (and [test]*)
     | (or [test]*)
     | (let ([binding spec]*) [body])
     | (let [variable] ([binding spec]*) [body])
     | (let* ([binding spec]*) [body])
     | (letrec ([binding spec]*) [body])
     | (begin [sequence])
     | (do ([iteration spec]*)
           ([test] [do result])
         [command]*)
     | (delay [expression])
     | [quasiquotation]

[cond clause] ::= ([test] [sequence])
                 | ([test])
                 | ([test] =] [recipient])

[recipient] ::= [expression]

[case clause] ::= (([datum]*) [sequence])

[binding spec] ::= ([variable] [expression])

[iteration spec] ::= ([variable] [init] [step]) | ([variable] [init])

[init] ::= [expression]

[step] ::= [expression]

[do result] ::= [sequence] | [empty]

[macro use] ::= ([keyword] [datum]*)

[keyword] ::= [identifier]

[macro block] ::= (let-syntax ([syntax spec]*) [body])
                 | (letrec-syntax ([syntax spec]*) [body])

[syntax spec] ::= ([keyword] [transformer spec])