CSE271: Principles of Programming Languages

Procedures

Jooyong Yi (UNIST)

Procedures

[Concrete Syntax]
Program ::= Expression

Expression ::= ...
            | proc (Identifier) Expression
            | (Expression Expression)

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

Expression ::= ...
            |  proc-exp (var body)       // var: formal parameter
            |  call-exp (rator rand)

Spec of Procedures

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

Functions in Python

def inc(x):
    return x + 1

x = inc
print(x)

Functions in Python

def inc(x):
    return x + 1

x = inc
print(x)

<function inc at 0x7f8b3c7b7d30>

Values We Used So Far

(num-val 3)
(num-val 10)
(bool-val #t)
(bool-val #f)

Spec of Procedures

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

• enough?

Consider the following program

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))

Spec of Procedures

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

Spec of Procedures

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

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

Procedure 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 -((f 1),(g 1)) >>
 ρ₁)
=
(value-of
  << let f = proc (z) -(z,x)
     in let x = 100
        in let g = proc (z) -(z,x)
           in -((f 1),(g 1)) >>
  ρ₂)

• ρ₂ = [x=200]ρ₁

Procedure Example

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

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

Procedure Example

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

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

Procedure Example

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

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

Procedure Example

(value-of
  << -((f 1),(g 1)) >>
  ρ₅)
=
(num-val (- (exp-val->num (value-of <<(f 1)>> ρ₅))
            (exp-val->num (value-of <<(g 1)>> ρ₅))))

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

Procedure Example

(value-of <<(f 1)>> ρ₅)
=
(value-of <<(-(z,x))>> [z=1]ρ₂)

• ρ₂ = [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 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟=𝑣𝑎𝑙]ρ₂)

Procedure Example

(value-of <<(f 1)>> ρ₅)
=
(value-of <<(-(z,x))>> [z=1]ρ₂)
= 
(num-val -199)

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

Procedure Example

(value-of
  << -((f 1),(g 1)) >>
  ρ₅)
=
(num-val (- (exp-val->num (value-of <<(f 1)>> ρ₅))
            (exp-val->num (value-of <<(g 1)>> ρ₅))))
=
(num-val (- (exp-val->num (num-val -199))
            (exp-val->num (value-of <<(g 1)>> ρ₅))))            

Procedure Example

(value-of <<(g 1)>> ρ₅)
=
(value-of <<-(z,x)>> [z=1]ρ₄)

• ρ₂ = [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 𝑏𝑜𝑑𝑦 [𝑣𝑎𝑟=𝑣𝑎𝑙]ρ₂)

Procedure Example

(value-of <<(g 1)>> ρ₅)
=
(value-of <<-(z,x)>> [z=1]ρ₄)
=
(num-val -99)

Procedure Example

(num-val (- (exp-val->num (num-val -199))
            (exp-val->num (value-of <<(g 1)>> ρ₅))))
=
(num-val (- (exp-val->num (num-val -199))
            (exp-val->num (num-val -99))))

Procedure Example

(num-val (- (exp-val->num (num-val -199))
            (exp-val->num (value-of <<(g 1)>> ρ₅))))
=
(num-val (- (exp-val->num (num-val -199))
            (exp-val->num (num-val -99))))
=
(num-val -100)            

Spec and Impl of Procedures

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

(define-datatype proc proc?                                                                          
  (procedure
    (var identifier?)
    (body expression?)
    (saved-env environment?)))

(define-datatype expval expval?
  (num-val (num number?))
  (bool-val (bool boolean?))
  (proc-val (proc proc?)))

(define value-of                                                                          
  (lambda (exp env)
    (cases expression exp      
      ...
      (proc-exp (var body)
        (proc-val (procedure var body env))))))

Spec and Impl of Procedures

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

(define apply-procedure                                                                      
  (lambda (proc1 val)
    (cases proc proc1
      (procedure (var body saved-env)
        (value-of body (extend-env var val saved-env))))))

(define value-of                                                                          
  (lambda (exp env)
    (cases expression exp      
      ...
      (call-exp (rator rand)
        (let ((proc (expval->proc (value-of rator env)))
              (arg (value-of rand env)))
          (apply-procedure proc arg))))))

Terminology: Closure

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

• (procedure 𝑣𝑎𝑟 𝑏𝑜𝑑𝑦 ρ₂) is called a closure.
  • A closure contains everything needed to evaluate a procedure.