                                               עקרונות שפות תכנות, סמסטר ב- 2011
תרגול 14 - Imperative programming
Topics: 1. Mutable data: local state, letrec, set!
2. Mutable lists: set-car! , set-cdr!
3. Environment based interpreter and compiler for imperative programming.
Mutable data
Example 1: counter
(define counter
(let ((count 0))
(lambda () (set! count (+ count 1))
count)))
How would this work in the substitution model?
We evaluate the let expression after it has been translated into an application:
applicative-eval [ ((lambda (count)
(lambda () (begin (set! count (+ count 1))
count))
0)]
applicative-eval [ (lambda () (begin (set! 0 (+ 0 1)) 0)) ]
applicative-eval [ (begin (set! 0 (+ 0 1)) 0) ] ==> 0
The counter would always return its initial value 0. This implies that the substitution model cannot account for change! Change requires objects that keep local states. The substitution step has to be strengthened to enable binding of variables (parameters) to actual argument values. Therefore, we will use the environment model:
Note that count is the local state of the counter object.
Conclusion: In functional languages, objects are implemented as runtime generated closures.
>(counter)
1
>(counter)
2
Example 2: The Chess Player
A chase player object is represented by a dispatch procedure that, based on a given message invokes internal procedures of the object. The local state of the object is stored by total and steps which keep track of the player’s score and the number of steps he has taken, respectively.
; 1. Signature: make-player (total)
; 2. Type: [Number--> [Symbol--> [Unit--> Number] union
; [Unit-->Unit] union
; [Symbol-->Unit]]]
; 3. Purpose: represent a chess player.
(define make-player
(lambda (total)
(letrec ((steps 0)
(get-steps (lambda () steps))
(set-steps! (lambda () (set! steps (+ steps 1))))
(get-total (lambda () total))
(set-total! (lambda (piece)
(let ((piece-value (cond ((eq? piece 'queen) 9)
((eq? piece 'rook) 5)
((eq? piece 'bishop) 3)
((eq? piece 'knight) 3)
((eq? piece 'pawn) 1)
(else 0))))
(set! total (- total piece-value)))))
(dispatch (lambda (m) (cond
((eq? m 'set-total) set-total!)
((eq? m 'set-steps) set-steps!)
((eq? m 'get-total) get-total)
((eq? m 'get-steps) get-steps)
(else (error "Unknown request"))))))
dispatch)))
The internal procedure set-score! updates the player’s score each time he loses some piece. The player has an initial total of points and according to the piece he loses his total of point is updated. We will examine a simpler representation of a chess player using only the set-score! procedure:
A chess player is now represented only by a procedure that keeps track of his total points.
; 1. Signature: make-player (total)
; 2. Type: Number-->[Symbol-->Number]
; 3. Purpose: keep track of the player's score in Chess Game.
; 4. Example: ((make-player 39) 'queen) expected value 30
(define make-player (lambda (total)
(lambda (piece)
(let ((piece-value (cond ((eq? piece 'queen) 9)
((eq? piece 'rook) 5)
((eq? piece 'bishop) 3)
((eq? piece 'knight) 3)
((eq? piece 'pawn) 1)
(else 0))))
(set! total (- total piece-value))
total))))
A running example by using the environment model as we know it:
((make-player 39) ‘queen)
GE
30
P=(piece-value)
B=(set!...)
total
piece ='queen
E2
current-total= 39
P=(piece)
B=(let…)
E1
P=(total)
B=(lambda…
make-player
E3
piece-value=9
Example 3 - letrec:
The letrec expression can be used to define local recursive procedures. The evaluation rule for this expression is not supported by the functional programming model (e.g, applicative-eval) without rewriting the code of the recursive procedure. However, it can be supported by the imperative programming model. We use the environment model also for imperative programming.
To support the letrec expression, it is handled as a derived expression:
(let ((f1 ’unassigned)
...
(fn ’unassigned))
(set! f1 lambda-exp1)
...
(set! fn lambda-expn)
e1...em)
(letrec ((f1 lambda-exp1)
...
(fn lambda-expn))
e1...em)
We demonstrate running the env-eval algorithm on a local recursive procedure, fact:
env-eval[ (letrec ((fact (lambda (n)
(if (= n 0) 1
(* n (fact (- n 1))))))
(fact 3)),GE]==>
env-eval[ ((lambda (fact)
(set! fact (lambda (n)
(if (= n 0) 1
(* n (fact (- n 1)))))
(fact 3)) 'uassigned), GE]
==> env-eval[ (set! fact (lambda (n)
(if (= n 0) 1
(* n (fact (- n 1))))), E1]
Result so far:
GE
fact='unassigned
(fact 3)
Params: n
Body: (if… )
Parameters: fact
Body: (set..)
(fact 3)
E1
A
B
Figure 1
Continued evaluation:
==> env-eval[(fact 3),E1]
==> env-eval[fact]
==>lookup-varibale-value(fact,E1) ==> closure B in fig. 1
==> env-eval[3]==> 3
Le
GE
fact:
(fact 3)
E2
Parameters: n
Body: (if…)
n: 3
(* n (fact (- n 1)))
Parameters: fact
Body: (set!...
(fact 3)
E1
A
B
Figure 2
t E2 = extend-environment(make-frame([n],[body(B)]),E1)
env-eval[(* n (fact (- n 1))), E2]==>
env-eval[*,E2] ==>
env-eval [n,E2]==> 3 (lookup)
env-eval[(fact (- n 1)), E2]==>
env-eval[fact, E2]==>
lookup-variable-value(fact,E2)==> closure B in fig. 2
…
The built-in LIST type has the mutators 'set-car!' and 'set-cdr!'.
; Type: PAIR(T1,T2) * T -> Unit
; Purpose: modify the car/cdr pointer of 'pair' to point to 'value'
; Signature: set-car!(pair, value)
; Signature: set-cdr!(pair, value)
Example 4 (draw box-pointer diagrams):
> (define x (list (list 'a 'b) 'c 'd) )
> x
((a b) c d)
> (define y (list 'e 'f))
> (set-car! x y)
> x
((e f) c d) ; The value of x has been changed by set-car!.
; This is different than the following which makes
; a new pair z with the same value.
> (define z (cons y (cdr x)) )
> z
((e f) c d)
> x ; Notice that x hasn't changed:
((e f) c d)
>(equal? x z)
#t
> (eq? x z) ; equal? is the overloaded procedure that checks equality recursively.
#f ;eq? is an overloaded procedure that checks if the pointers are the
; same. That is, if the compared arguments are the same data (object).
> (define x (list 1 2 3))
> (set-cdr! x x)
> x
#0=(1 . #0#)
Example 5
; 1. Signature: modify-list!(lst, from, to)
; 2. Type: List(T)*T*T -> Unit
; 3. Purpose: Modify the cdr of the element 'from' to point to the
part of the list starting with 'to', if 'from' and 'to' are
members of the list.
(define modify-list!
(lambda (lst from to)
(let ((f (memq from lst))
(t (memq to lst)))
(if (and f t)
(set-cdr! f t)))))
We use the built-in procedure memq(e, li) which returns the remainder of the list starting with 'e', or #f otherwise.
>(modify-list! (list 1 2 3 4) 4 2)
1234234234…
>(modify-list! (list 1 2 3 4) 2 4)
124 (non-circular)
3. Meta-circular environment based interpreter for imperative programming
Example 6
A reminder: In the imperative programming evaluator, support for set! expressions is added, which gives motivation for supporting while expressions. For example,
Syntax: (while
)
>(define x 0)
>(define n 4)
>(while (> n 0)
(begin (set! x (+ x n))
(set! n (- n 1))) )
>x
10
Question1: Can a while expression be supported in a functional programming evaluator?
Question2: Can while be defined as a user procedure (in the imperative model)?
Example,
>(env-eval '(define x 0) t-g-e)
>(env-eval '(define n 4) t-g-e)
>(env-eval '(while (> n 0)
(begin
(set! x (+ x n))
(set! n (- n 1))) )
t-g-e)
ok
>(env-eval x t-g-e)
10
Add ASP procedures
(define while?
(lambda (exp) (tagged-list? exp 'while)))
(define while-pred
(lambda (exp) (car (get-content exp))))
(define while-body
(lambda (exp) (cadr (get-content exp))))
Option 1 – Adding while as a derived expression (syntactic sugar):
-
Add to derived?
(define derived?
(lambda (exp)
(or … (while? exp))))
-
Add to shallow-derive
(define shallow-derive
(lambda (exp)
(cond … ((while? exp) (while->iteration-expression exp)))))
-
Add the translation procedure: while->iteration-expression
First try:
(while (> n 0)
(begin (set! x (+ x n))
(set! n (- n 1))))
Is translated to
(letrec ((iter (lambda ()
(if (> n 0)
(begin
(begin (set! x (+ x n))
(set! n (- n 1)))
(iter))
'ok))))
(iter))
But: There is a problem with this translation. What if iter is already used in the expression? For example,
(while (> (iter n) 0)
(set! n (- n (iter n))))
Is translated to
(letrec ((iter (lambda ()
(if (> (iter n) 0))
(begin
(set! n (- n (iter n)))
(iter))
'ok))))
(iter))
Second try:
(let ((pred (lambda () (> (iter n) 0)))
(body (lambda () (set! n (- n (iter n))))))
(letrec ((iter (lambda ()
(if (pred)
(begin (body) (iter))
'ok))))
(iter)))
The local variable iter does not collide with the outer definition.
The translation procedure:
(define while->iteration-expression
(lambda (exp)
(let ((pred (make-lambda '() (list (while-pred exp))))
(body(make-lambda '() (list (while-body exp)))))
(make-let
(list (list 'body body) (list 'pred pred))
(make-letrec
(list (list 'iter (make-lambda '()
(list (make-if (make-application 'pred '() )
(make-begin (list (make-application 'body '())
(make-application 'iter '())))
'(quote ok))))))
(make-application 'iter '()))))))
Option 2 - Add while as a special form to env-eval:
-
Add while to the special-form? procedure.
(define special-form?
(lambda (exp)
(or (quoted? exp) (lambda? exp) ... (while? exp))))
-
Add an eval-special-form procedure.
(define eval-special-form
(lambda (exp env)
(cond …((while? exp) (eval-while exp env)))))
-
Add eval-while procedures
(define eval-while (lambda (exp env)
(let ((pred (while-pred exp))
(body (while-body exp)))
(letrec ((iter (lambda ()
(if (env-eval pred env)
(begin
(env-eval body env)
(iter))
'ok))))
(iter))))
Adding while to the compiler as a special form:
-
Add an analyze-special-op procedure.
(define analyze-special-form
(lambda (exp)
(cond …((while? exp) (analyze-while exp)))))
-
Make analysis of exp components
(define analyze-while
(lambda (exp)
(let ((pred (analyze (while-pred exp)))
(body (analyze (while-body exp))))
(lambda (env)
(letrec ((iter (lambda()
(if (pred env)
(begin (body env)
(iter))
'ok))))
(iter)))))
Note: When translating the code of the evaluator, for the purpose of adjusting it to the analyzer, it is important that the eval will not be part of the computation of expression, and that it will not produce new code. For example, the following code can be used in env-eval, but it is hard to translate it to the analyzer .
(define eval-while (lambda (exp env)
(let ((pred (while-pred exp))
(body (while-body exp)))
(if (env-eval pred env)
(begin (env-eval body env)
(eval-while exp env))
'ok))))
Optional page
4. Mutable ADTs data
Adding imperative programming capabilities (set!) effects how we design ADT.
A value/instance returned by an ADT constructor procedure (i.e. object) can have a changing state (local variables). We add data operators, called MUTATORS, which modify its state.
Example: Bank account ADT
Suppose we wish to maintain a list containing all the created bank accounts, such that
-
The list is accessible only through bank accounts.
-
The list is shared (all bank account see the same list).
-
Each account can see the balance of all other accounts but can't change them (withdraw/deposit)
(define make-account
(let* ((account-list (list 'AccList))
;; initialize account list to the empty list
(all-balances (lambda ()
(map (lambda (acc) ((acc 'get-balance)))
(cdr account-list)))))
(lambda (balance)
(letrec (
(withdraw (lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds")))
(deposit (lambda (amount)
(set! balance (+ balance amount))
balance))
(get-balance (lambda() balance))
(dispatch
(lambda (m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
((eq? m 'get-balance) get-balance)
((eq? m 'all-balances) all-balances)))))
;; letrec body: add new account to list, then return it
(set-cdr! account-list (cons dispatch (cdr account-list)))
dispatch))))
The environment diagram for the following run example:
(define acc1 (make-account 1))
(define acc2 (make-account 2))
((acc2 'deposit) 2) ==> 4
((acc2 'all-balances)) ==> (4 1)
withdraw
deposite
get-balance
dispatch
P:(withdraw,
deposite)
B:(set-cdr!...
'AccList
E1
t-g-e
E2
all-balances
account-list
make-account
acc1
acc2
Balance =1
P:(account-list)
B:(let(all-balances…)
Balance = 2
4
P:(all-balances)
B:( lambda(balance)…)
P:()
B: (map…)
P:(withdraw,
deposite)
B:(set-cdr!...
P:(balance)
B:(letrec…)
withdraw
deposite
get-balance
dispatch
-
What would happen if we omit the 'dispatch' at the end of the code?
The example above shows how OOP is implement by Imperative-Programming:
-
Here we implemented the 'class' account.
-
The constructor is: make-account.
-
The object is dispatch. Its field is balance.
-
account-list is a private static field. all-balances is a static procedure.
Private static-accesible only to accounts.
-
We have the getter: get-balance, and the methods: withdraw, deposite.
Share with your friends: | 
