CSE271: Principles of Programming Languages

Environment

Jooyong Yi (UNIST)

Interpreter

                                   Input to P
                                       ↓
Program P → [Front End] → AST → [ Interpreter ]
                                       ↓
                                   Output of P

• Front End: Lexer and Parser

Simple Language

[Concrete Syntax]
Program ::= Expression

Expression ::= Number

[Abstract Syntax]
Program ::= a-program (exp)

Expression ::= const-exp (num)

Example

Program ::= a-program (exp)

Expression ::= const-exp (num)

#(struct:a-program #(struct:const-exp 5))

          a-program
              |
          const-exp
              |
              5

Interpreter

#(struct:a-program #(struct:const-exp 5)) → [ Interpreter ]

• Suppose that our program only expresses a value.
  • Interpreter = Evaluator

Evaluator

#(struct:a-program #(struct:const-exp 5)) → [ value-of-program ]

;; value-of-program : Program -> ExpVal
(define value-of-program 
  (lambda (pgm)
    (cases program pgm
      (a-program (exp1)
        (value-of exp1 (init-env))))))

Evaluating Constant Expressions

#(struct:a-program #(struct:const-exp 5)) → [ value-of-program ]

;; value-of-program : Program -> ExpVal
(define value-of-program 
  (lambda (pgm)
    (cases program pgm
      (a-program (exp)
        (value-of exp (init-env))))))

(value-of (const-exp 𝑛) ρ) = (num-val 𝑛)

Evaluating Constant Expressions

(value-of (const-exp 𝑛) ρ) = (num-val 𝑛)

;; value-of : Exp * Env -> ExpVal
(define value-of
  (lambda (exp env)
    (cases expression exp
      (const-exp (n)
        (num-val n)))))

Adding Variable Expressions

[Concrete Syntax]
Program ::= Expression

Expression ::= Number
            |  Identifier

[Abstract Syntax]
Program ::= a-program (exp)

Expression ::= const-exp (num)
            |  var-exp (var)

Adding Variable Expressions

(struct:a-program #(struct:var-exp x)) → [ value-of-program ]

          a-program
              |
           var-exp
              |
              x

;; value-of-program : Program -> ExpVal
(define value-of-program 
  (lambda (pgm)
    (cases program pgm
      (a-program (exp)
        (value-of exp (init-env))))))

Evaluating Variable Expressions

(struct:a-program #(struct:var-exp x)) → [ value-of-program ]

;; value-of-program : Program -> ExpVal
(define value-of-program 
  (lambda (pgm)
    (cases program pgm
      (a-program (exp)
        (value-of exp (init-env))))))

(value-of (var-exp 𝑣𝑎𝑟) ρ) = ??

Environment

int x = 5;
int y = 7;

|----|----|
| x  |  5 |
|----|----|
| y  |  7 |
|----|----|

Environment

int x = 5;
int y = 7;

|----|----|
| x  |  5 |
|----|----|
| y  |  7 |
|----|----|

• Mathematically, an environment is a function from variables to values.

Environment

int x = 5;
int y = 7;

|----|----|
| x  |  5 |
|----|----|
| y  |  7 |
|----|----|

• Mathematically, an environment is a function from variables to values.
• An interpreter maintains an environment.
  • An environment is one of the data we need to handle in an interpreter.

The Environment Interface

• (empty-env): an empty environment

The Environment Interface

• (empty-env): an empty environment
• (extend-env 𝑣𝑎𝑟 𝑣𝑎𝑙 ρ) = ρ' where
  

The Environment Interface

• (empty-env): an empty environment
• (extend-env 𝑣𝑎𝑟 𝑣𝑎𝑙 ρ)
• (apply-env ρ 𝑣𝑎𝑟) = ρ(𝑣𝑎𝑟)

Implementing Environment

• (empty-env): an empty environment

;; empty-env : () -> Env
(define empty-env
  (lambda ()
    (list 'empty-env)))

Implementing Environment

• (extend-env 𝑣𝑎𝑟 𝑣𝑎𝑙 ρ) = ρ' where
  

;; extend-env : Var * SchemeVal * Env -> Env 
(define extend-env
  (lambda (var val env)
    (list 'extend-env var val env)))

Implementing Environment

• (extend-env 𝑣𝑎𝑟 𝑣𝑎𝑙 ρ) = ρ' where
  

;; extend-env : Var * SchemeVal * Env -> Env 
(define extend-env
  (lambda (var val env)
    (list 'extend-env var val env)))

> (extend-env 'x 5 (extend-env 'y 7 (empty-env)))
(extend-env x 5 (extend-env y 7 (empty-env)))

Implementing Environment

• (apply-env ρ 𝑣𝑎𝑟) = ρ(𝑣𝑎𝑟)

;; apply-env : Env * Var -> SchemeVal
(define apply-env
  (lambda (env search-var)
    (cond
      ((eqv? (car env) 'empty-env)
        (report-no-binding-found search-var))
      ((eqv? (car env) 'extend-env)
        (let ((saved-var (cadr env))
              (saved-val (caddr env))
              (saved-env (cadddr env)))
          (if (eqv? search-var saved-var)
              saved-val
              (apply-env saved-env search-var))))
      (else
        (report-invalid-env env)))))

Mathematical Definition ≠ Implementation

• (extend-env 𝑣𝑎𝑟 𝑣𝑎𝑙 ρ) = ρ' where
  

;; extend-env : Var * SchemeVal * Env -> Env 
(define extend-env
  (lambda (var val env)
    (list 'extend-env var val env)))

Mathematical Definition = Implementation

• (extend-env 𝑣𝑎𝑟 𝑣𝑎𝑙 ρ) = ρ' where
  

;; extend-env : Var * SchemeVal * Env -> Env
(define extend-env
  (lambda (saved-var saved-val saved-env)
    (lambda (search-var)
      (if (eqv? search-var saved-var)
          saved-val
          (apply-env saved-env search-var)))))

• Env = Var -> SchemeVal

Mathematical Definition = Implementation

• (apply-env ρ 𝑣𝑎𝑟) = ρ(𝑣𝑎𝑟)

;; apply-env : Env * Var -> SchemeVal
(define apply-env
  (lambda (env search-var)
    (env search-var)))    

Mathematical Definition = Implementation

• (empty-env): an empty environment

;; empty-env : () -> Env
(define empty-env
  (lambda ()
    (lambda (search-var)
      (report-no-binding-found search-var))))

Evaluating Variable Expressions

(struct:a-program #(struct:var-exp x)) → [ value-of-program ]

;; value-of-program : Program -> ExpVal
(define value-of-program 
  (lambda (pgm)
    (cases program pgm
      (a-program (exp)
        (value-of exp (init-env))))))

(value-of (var-exp 𝑣𝑎𝑟) ρ) = ??

Evaluating Variable Expressions

(struct:a-program #(struct:var-exp x)) → [ value-of-program ]

;; value-of-program : Program -> ExpVal
(define value-of-program 
  (lambda (pgm)
    (cases program pgm
      (a-program (exp)
        (value-of exp (init-env))))))

(value-of (var-exp 𝑣𝑎𝑟) ρ) = (apply-env ρ 𝑣𝑎𝑟)

Implementing Variable Expression Evaluation

(value-of (var-exp 𝑣𝑎𝑟) ρ) = (apply-env ρ 𝑣𝑎𝑟)

;; value-of : Exp * Env -> ExpVal
(define value-of
  (lambda (exp env)
    (cases expression exp
      (const-exp (n)
        (num-val n)))
      (var-exp (var) 
        (apply-env env var))))

Adding Diff Expressions

[Concrete Syntax]
Program ::= Expression

Expression ::= Number
            |  Identifier
            |  - (Expression, Expression)

[Abstract Syntax]
Program ::= a-program (exp)

Expression ::= const-exp (num)
            |  var-exp (var)
            |  diff-exp (exp1 exp2)

Evaluating Diff Expressions

;; value-of : Exp * Env -> ExpVal
(value-of (diff-exp 𝑒𝑥𝑝₁ 𝑒𝑥𝑝₂) ρ) = ??

Evaluating Diff Expressions

;; value-of : Exp * Env -> ExpVal
(value-of (diff-exp 𝑒𝑥𝑝₁ 𝑒𝑥𝑝₂) ρ)
= (num-val (- (expval->num (value-of 𝑒𝑥𝑝₁ ρ))
              (expval->num (value-of 𝑒𝑝𝑥₂ ρ))))

Implementing Diff Expressions Evaluation

;; value-of : Exp * Env -> ExpVal
(define value-of
  (lambda (exp env)
    (cases expression exp
      (const-exp (n)
        (num-val n)))
      (var-exp (var) 
        (apply-env env var)))
      (diff-exp (exp1 exp2)
        (let ((val1 (value-of exp1 env))
              (val2 (value-of exp2 env)))
          (let ((num1 (expval->num val1))
                (num2 (expval->num val2)))
            (num-val (- num1 num2))))))

Adding Let Expressions

[Concrete Syntax]
Program ::= Expression

Expression ::= Number
            |  Identifier
            |  - (Expression, Expression)
            |  let Identifier = Expression in Expression

[Abstract Syntax]
Program ::= a-program (exp)

Expression ::= const-exp (num)
            |  var-exp (var)
            |  diff-exp (exp1 exp2)
            |  let-exp (var exp body)

Let Expression Example

let x = 5 
in - (x, 3)

Let Expression Example

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

Evaluating Let Expressions

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

Implementing Let Expression Evaluation

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

;; value-of : Exp * Env -> ExpVal
(define value-of
  (lambda (exp env)
    (cases expression exp
      (const-exp (n)
        (num-val n)))    
      ...
      (let-exp (var exp body)
        (let ((val (value-of exp env)))
          (value-of body 
            (extend-env var val env))))))

Let Expression Evaluation Example

(value-of
  <<let x = 7
    in let y = 2
       in let y = let x = -(x,1) in -(x,y)
          in -(-(x,8),y)>>
  ρ₀)

Let Expression Evaluation Example

(value-of
  <<let x = 7
    in let y = 2
       in let y = let x = -(x,1) in -(x,y)
          in -(-(x,8),y)>>
  ρ₀)
= 
(value-of
  <<let y = 2
    in let y = let x = -(x,1) in -(x,y)
       in -(-(x,8),y)>>
  [x=7]ρ₀)  

Let Expression Evaluation Example

(value-of
  <<let y = 2
    in let y = let x = -(x,1) in -(x,y)
       in -(-(x,8),y)>>
  [x=7]ρ₀)  
=
(value-of
  <<let y = let x = -(x,1) in -(x,y)
    in -(-(x,8),y)>>
  [y=2][x=7]ρ₀)  

Let Expression Evaluation Example

(value-of
  <<let y = let x = -(x,1) in -(x,y)
    in -(-(x,8),y)>>
  [y=2][x=7]ρ₀)  
=
(value-of
  <<-(-(x,8),y)>>
  [y=(value-of <<let x = -(x,1) in -(x,y)>> ρ₁)]ρ₁)    

• ρ₁ = [y=2][x=7]ρ₀

Let Expression Evaluation Example

(value-of
  <<-(-(x,8),y)>>
  [y=(value-of <<let x = -(x,1) in -(x,y)>> ρ₁)]ρ₁)    
=
(value-of
  <<-(-(x,8),y)>>  
  [y=(value-of <<-(x,y)>> [x=(value-of <<-(x,1)>> ρ₁)]ρ₁)]ρ₁)

• ρ₁ = [y=2][x=7]ρ₀

Let Expression Evaluation Example

(value-of
  <<-(-(x,8),y)>>  
  [y=(value-of <<-(x,y)>> [x=(value-of <<-(x,1)>> ρ₁)]ρ₁)]ρ₁)
=
(value-of
  <<-(-(x,8),y)>>  
  [y=(value-of <<-(x,y)>> [x=(value-of <<-(7,1)>> ρ₁)]ρ₁)]ρ₁)  

• ρ₁ = [y=2][x=7]ρ₀

Let Expression Evaluation Example

(value-of
  <<-(-(x,8),y)>>  
  [y=(value-of <<-(x,y)>> [x=(value-of <<-(x,1)>> ρ₁)]ρ₁)]ρ₁)
=
(value-of
  <<-(-(x,8),y)>>  
  [y=(value-of <<-(x,y)>> [x=(value-of <<-(7,1)>> ρ₁)]ρ₁)]ρ₁)  
=
(value-of
  <<-(-(x,8),y)>>  
  [y=(value-of <<-(x,y)>> [x=6]ρ₁)]ρ₁)  

• ρ₁ = [y=2][x=7]ρ₀

Let Expression Evaluation Example

(value-of
  <<-(-(x,8),y)>>  
  [y=(value-of <<-(x,y)>> [x=6]ρ₁)]ρ₁)  
=
(value-of
  <<-(-(x,8),y)>>  
  [y=(value-of <<-(6,2)>> [x=6]ρ₁)]ρ₁)
=    
(value-of
  <<-(-(x,8),y)>>  
  [y=4]ρ₁)

• ρ₁ = [y=2][x=7]ρ₀

Let Expression Evaluation Example

(value-of
  <<-(-(x,8),y)>>  
  [y=4]ρ₁)
=
(value-of
  <<-(-(7,8),4)>>  
  [y=4]ρ₁)  
=
-5  

• ρ₁ = [y=2][x=7]ρ₀