Tutorial 2026-02-04

Environments

CS 146 Tutorial 5

Faux Racket

exp = (fun(id) exp)
| ( exp exp)
| (with (id exp) exp)
| id
| (op exp exp)

• Subsitution Rules

(with (x 1 )
      (with ( y ( + x 1 ))
       ( f( fun (x) ( * x 3)) y)))

• fun(x) is Shadowing the (* 3) .

(with (y ( + 1 1 ))
 ((fun(x) ( * x 3 )) y)

with (y  2) 
 (( fun ... ) y )) 
 
 ((fun ( x) ( * x 3 )) 2 )
 ( * 2 3 ) => 6

Do not substitute with a with or fun that redefines a var from the outer scope

Look at the code posted in the tutorial handouts for full demonstration and code.

• Subst rebuilds the AST at every step.

defer substitution

• Remember the value of the value of the var subst, only when we need to evaluate a var.

  • How?

    • Use AL ( represented by [])

(with ( x 1 )     []
  ( with y 2)
   ( + x y ))
   
(with ( y 2)      [ ( x, 1)]
 (+ x y ))
 
 ( + x y )       [ ( y,2) (x,1)]
 => ( + x y)       [ ( y,2 ) (x,1)]
 => ( + 1 2 )
 => 3

Thus what does

(with ( f ( fun (x) ( + x n )))
 ( with ( n 2 )
      ( f 1 )  )

produce?

It's SUPPOSE to error, because of local definitions ( scoping issue of n), but are interpreter doesn't break. Why?

• f uses n before it is defined

• locals are being treated like globals

• fun's and with's should have their own environment

(with ( n 2 ) ( f 1 )) [ ( f, ( fun ( x) ... ) ]
(f  1)                 [ ( n , 2 ) , ( f, fun ... )]
((fun (x) ( + x n )) 1)    [ ( x,1), (n,2), (f,fn...)]
(+ 1 n)
(+ 1 2) => 3

Alt...
       [(x,1), (f, (fun (x))]