CSE271: Principles of Programming Languages

Scoping

Jooyong Yi (UNIST)

Review: Let Expression Example

let z = 5
in let x = 3
   in let y = -(x,1)
      in let x = 4
         in -(z, -(x,y))

Review: Let Expression Example

let z = 5
in let x = 3
   in let y = -(x,1)
      in let x = 4
         in -(z, -(x,y))

       (value-of 𝑒𝑥𝑝 ρ) = 𝑣𝑎𝑙
---------------------------------------------
(value-of (let-exp 𝑣𝑎𝑟 𝑒𝑥𝑝 𝑏𝑜𝑑𝑦) ρ)
= (value-of 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟 = 𝑣𝑎𝑙]ρ) 

Review: Procedure Example

let x = 200
in let f = proc (z) -(z,x)
   in let x = 100
      in let g = proc (z) -(z,x)
         in -((f 1),(g 1))

Review: Procedure Example

let x = 200
in let f = proc (z) -(z,x)
   in let x = 100
      in let g = proc (z) -(z,x)
         in -((f 1),(g 1))

(value-of (proc-exp 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦) ρ)  = (proc-val (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ))

  (value-of 𝑟𝑎𝑡𝑜𝑟 ρ₁) = (proc-val (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ₂))
  (value-of 𝑟𝑎𝑛𝑑 ρ₁) = 𝑣𝑎𝑙
----------------------------------------------------------------
  (value-of (call-exp 𝑟𝑎𝑡𝑜𝑟 𝑟𝑎𝑛𝑑) ρ₁) = (value-of 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟=𝑣𝑎𝑙]ρ₂)

Example

let x = 200
in let f = proc (z) -(z,x)
   in let x = 100
      in let g = proc (z) (z x)
         in (g f)

Example

(value-of
  <<let x = 200
    in let f = proc (z) -(z,x)
       in let x = 100
          in let g = proc (z) (z x)
             in (g f)>>
 ρ₀)             
=
(value-of
  <<let f = proc (z) -(z,x)
       in let x = 100
          in let g = proc (z) (z x)
             in (g f)>>
   ρ₁)

• ρ₁ = [x=200]ρ₀

Example

(value-of
  <<let f = proc (z) -(z,x)
       in let x = 100
          in let g = proc (z) (z x)
             in (g f)>>
   ρ₁)
=
(value-of
  <<let x = 100
       in let g = proc (z) (z x)
          in (g f)>>
   ρ₂)   

• ρ₁ = [x=200]ρ₀
• ρ₂ = [f=(proc-val (procedure z <<-(z,x)>> ρ₁)]ρ₁

Example

(value-of
  <<let x = 100
       in let g = proc (z) (z x)
          in (g f)>>
   ρ₂)   
=
(value-of
  <<let g = proc (z) (z x)
          in (g f)>>
   ρ₃)   

• ρ₁ = [x=200]ρ₀
• ρ₂ = [f=(proc-val (procedure z <<-(z,x)>> ρ₁)]ρ₁
• ρ₃ = [x=100]ρ₂

Example

(value-of
  <<let g = proc (z) (z x)
          in (g f)>>
   ρ₃)   
=
(value-of
  <<(g f)>>
   ρ₄)      

• ρ₁ = [x=200]ρ₀
• ρ₂ = [f=(proc-val (procedure z <<-(z,x)>> ρ₁)]ρ₁
• ρ₃ = [x=100]ρ₂
• ρ₄ = [g=(proc-val (procedure z (z x) ρ₃)]ρ₃

Example

(value-of <<(g f)>> ρ₄) 
= (value-of <<(z x)>> [z=(value-of f ρ₄)]ρ₃)          

• ρ₁ = [x=200]ρ₀
• ρ₂ = [f=(proc-val (procedure z <<-(z,x)>> ρ₁)]ρ₁
• ρ₃ = [x=100]ρ₂
• ρ₄ = [g=(proc-val (procedure z (z x) ρ₃)]ρ₃

  (value-of 𝑟𝑎𝑡𝑜𝑟 ρ₁) = (proc-val (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ₂))
  (value-of 𝑟𝑎𝑛𝑑 ρ₁) = 𝑣𝑎𝑙
----------------------------------------------------------------
  (value-of (call-exp 𝑟𝑎𝑡𝑜𝑟 𝑟𝑎𝑛𝑑) ρ₁) = (value-of 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟=𝑣𝑎𝑙]ρ₂)

Example

(value-of <<(z x)>> [z=(value-of f ρ₄)]ρ₃)          
= (value-of <<-(z,x)>> [z=100]ρ₁)          

• ρ₁ = [x=200]ρ₀
• ρ₂ = [f=(proc-val (procedure z <<-(z,x)>> ρ₁)]ρ₁
• ρ₃ = [x=100]ρ₂
• ρ₄ = [g=(proc-val (procedure z (z x) ρ₃)]ρ₃

  (value-of 𝑟𝑎𝑡𝑜𝑟 ρ₁) = (proc-val (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ₂))
  (value-of 𝑟𝑎𝑛𝑑 ρ₁) = 𝑣𝑎𝑙
----------------------------------------------------------------
  (value-of (call-exp 𝑟𝑎𝑡𝑜𝑟 𝑟𝑎𝑛𝑑) ρ₁) = (value-of 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟=𝑣𝑎𝑙]ρ₂)

Example

(value-of <<-(z,x)>> [z=100]ρ₁)          
= -(100,200)
= -100          

• ρ₁ = [x=200]ρ₀
• ρ₂ = [f=(proc-val (procedure z <<-(z,x)>> ρ₁)]ρ₁
• ρ₃ = [x=100]ρ₂
• ρ₄ = [g=(proc-val (procedure z (z x) ρ₃)]ρ₃

  (value-of 𝑟𝑎𝑡𝑜𝑟 ρ₁) = (proc-val (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ₂))
  (value-of 𝑟𝑎𝑛𝑑 ρ₁) = 𝑣𝑎𝑙
----------------------------------------------------------------
  (value-of (call-exp 𝑟𝑎𝑡𝑜𝑟 𝑟𝑎𝑛𝑑) ρ₁) = (value-of 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟=𝑣𝑎𝑙]ρ₂)

Review

let x = 200
in let f = proc (z) -(z,x)        // x = ? 
   in let x = 100
      in let g = proc (z) (z x)  // x = ?
         in (g f)

Lexical Scoping

let x = 200
in let f = proc (z) -(z,x)        // x = 200
   in let x = 100
      in let g = proc (z) (z x)  // x = 100
         in (g f)

Lexical Scoping

let x = 200
in let f = proc (z) -(z,x)        // x = 200
   in let x = 100
      in let g = proc (z) (z x)  // x = 100
         in (g f)

• A.k.a. static scoping

Dynamic Scoping

let a = 3
in let p = proc (x) -(x,a)
   in let a = 5
      in -(a, (p 2))

Scoping

• Scoping rules answer the question:
  • What is the value of a variable at a given point in the program?

Contour Diagram

• Scoping rules answer the question:
  • What is the value of a variable at a given point in the program?

let z = 5
|-(1)------------------------------------| (1) scope of z=5
| in let x = 3                           |
|    |-(2)----------------------------|  | (2) scope of x=3
|    | in let y = -(x,1)              |  |
|    |   |-(3)---------------------|  |  | (3) scope of y=-(x,1)
|    |   | in let x = 4            |  |  |
|    |   |    |-(4)-------------|  |  |  | (4) scope of x=4
|    |   |    | in -(z, -(x,y)) |  |  |  |
|    |   |    ------------------|  |  |  |
|    |   --------------------------|  |  |
|    ---------------------------------|  |
-----------------------------------------|

Binding

• Binding rules answer the question:
  • Which value is bound to a variable at a given point in the program?

Static Scoping vs Dynamic Scoping

(value-of (proc-exp 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦) ρ)  = (proc-val (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ))

  (value-of 𝑟𝑎𝑡𝑜𝑟 ρ₁) = (proc-val (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ₂))
  (value-of 𝑟𝑎𝑛𝑑 ρ₁) = 𝑣𝑎𝑙
---------------------------------------------------------------- [Static]
  (value-of (call-exp 𝑟𝑎𝑡𝑜𝑟 𝑟𝑎𝑛𝑑) ρ₁) = (value-of 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟=𝑣𝑎𝑙]ρ₂)

  (value-of 𝑟𝑎𝑡𝑜𝑟 ρ₁) = (proc-val (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ₂))
  (value-of 𝑟𝑎𝑛𝑑 ρ₁) = 𝑣𝑎𝑙
---------------------------------------------------------------- [Dynamic]
  (value-of (call-exp 𝑟𝑎𝑡𝑜𝑟 𝑟𝑎𝑛𝑑) ρ₁) = (value-of 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟=𝑣𝑎𝑙]ρ₁)