2. Mutable lists: setcar! , setcdr!
3. Environment based interpreter and compiler for imperative programming.
We evaluate the let expression after it has been translated into an application:
; 2. Type: [Number> [Symbol> [Unit> Number] union
; 3. Purpose: represent a chess player.
; 2. Type: Number>[Symbol>Number]
; 3. Purpose: keep track of the player's score in Chess Game.
; 4. Example: ((makeplayer 39) 'queen) expected value 30
(letrec ((f1 lambdaexp1)
...
(fn lambdaexpn))
e1...em)
We demonstrate running the enveval algorithm on a local recursive procedure, fact:
enveval[ (letrec ((fact (lambda (n)
(if (= n 0) 1
(* n (fact ( n 1))))))
(fact 3)),GE]==>
enveval[ ((lambda (fact)
(set! fact (lambda (n)
(if (= n 0) 1
(* n (fact ( n 1)))))
(fact 3)) 'uassigned), GE]
==> enveval[ (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:
==> enveval[(fact 3),E1]
==> enveval[fact]
==>lookupvaribalevalue(fact,E1) ==> closure B in fig. 1
==> enveval[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 = extendenvironment(makeframe([n],[body(B)]),E1)
enveval[(* n (fact ( n 1))), E2]==>
enveval[*,E2] ==>
enveval [n,E2]==> 3 (lookup)
enveval[(fact ( n 1)), E2]==>
enveval[fact, E2]==>
lookupvariablevalue(fact,E2)==> closure B in fig. 2
…
The builtin LIST type has the mutators 'setcar!' and 'setcdr!'.
; Type: PAIR(T1,T2) * T > Unit
; Purpose: modify the car/cdr pointer of 'pair' to point to 'value'
; Signature: setcar!(pair, value)
; Signature: setcdr!(pair, value)
Example 4 (draw boxpointer diagrams):
> (define x (list (list 'a 'b) 'c 'd) )
> x
((a b) c d)
> (define y (list 'e 'f))
> (setcar! x y)
> x
((e f) c d) ; The value of x has been changed by setcar!.
; 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))
> (setcdr! x x)
> x
#0=(1 . #0#)
Example 5
; 1. Signature: modifylist!(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 modifylist!
(lambda (lst from to)
(let ((f (memq from lst))
(t (memq to lst)))
(if (and f t)
(setcdr! f t)))))
We use the builtin procedure memq(e, li) which returns the remainder of the list starting with 'e', or #f otherwise.
>(modifylist! (list 1 2 3 4) 4 2)
1234234234…
>(modifylist! (list 1 2 3 4) 2 4)
124 (noncircular)
3. Metacircular 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,
>(enveval '(define x 0) tge)
>(enveval '(define n 4) tge)
>(enveval '(while (> n 0)
(begin
(set! x (+ x n))
(set! n ( n 1))) )
tge)
ok
>(enveval x tge)
10
Add ASP procedures
(define while?
(lambda (exp) (taggedlist? exp 'while)))
(define whilepred
(lambda (exp) (car (getcontent exp))))
(define whilebody
(lambda (exp) (cadr (getcontent exp))))
Option 1 – Adding while as a derived expression (syntactic sugar):

Add to derived?
(define derived?
(lambda (exp)
(or … (while? exp))))

Add to shallowderive
(define shallowderive
(lambda (exp)
(cond … ((while? exp) (while>iterationexpression exp)))))

Add the translation procedure: while>iterationexpression
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>iterationexpression
(lambda (exp)
(let ((pred (makelambda '() (list (whilepred exp))))
(body(makelambda '() (list (whilebody exp)))))
(makelet
(list (list 'body body) (list 'pred pred))
(makeletrec
(list (list 'iter (makelambda '()
(list (makeif (makeapplication 'pred '() )
(makebegin (list (makeapplication 'body '())
(makeapplication 'iter '())))
'(quote ok))))))
(makeapplication 'iter '()))))))
Option 2  Add while as a special form to enveval:

Add while to the specialform? procedure.
(define specialform?
(lambda (exp)
(or (quoted? exp) (lambda? exp) ... (while? exp))))

Add an evalspecialform procedure.
(define evalspecialform
(lambda (exp env)
(cond …((while? exp) (evalwhile exp env)))))

Add evalwhile procedures
(define evalwhile (lambda (exp env)
(let ((pred (whilepred exp))
(body (whilebody exp)))
(letrec ((iter (lambda ()
(if (enveval pred env)
(begin
(enveval body env)
(iter))
'ok))))
(iter))))
Adding while to the compiler as a special form:

Add an analyzespecialop procedure.
(define analyzespecialform
(lambda (exp)
(cond …((while? exp) (analyzewhile exp)))))

Make analysis of exp components
(define analyzewhile
(lambda (exp)
(let ((pred (analyze (whilepred exp)))
(body (analyze (whilebody 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 enveval, but it is hard to translate it to the analyzer .
(define evalwhile (lambda (exp env)
(let ((pred (whilepred exp))
(body (whilebody exp)))
(if (enveval pred env)
(begin (enveval body env)
(evalwhile 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 makeaccount
(let* ((accountlist (list 'AccList))
;; initialize account list to the empty list
(allbalances (lambda ()
(map (lambda (acc) ((acc 'getbalance)))
(cdr accountlist)))))
(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))
(getbalance (lambda() balance))
(dispatch
(lambda (m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
((eq? m 'getbalance) getbalance)
((eq? m 'allbalances) allbalances)))))
;; letrec body: add new account to list, then return it
(setcdr! accountlist (cons dispatch (cdr accountlist)))
dispatch))))
The environment diagram for the following run example:
(define acc1 (makeaccount 1))
(define acc2 (makeaccount 2))
((acc2 'deposit) 2) ==> 4
((acc2 'allbalances)) ==> (4 1)
withdraw
deposite
getbalance
dispatch
P:(withdraw,
deposite)
B:(setcdr!...
'AccList
E1
tge
E2
allbalances
accountlist
makeaccount
acc1
acc2
Balance =1
P:(accountlist)
B:(let(allbalances…)
Balance = 2
4
P:(allbalances)
B:( lambda(balance)…)
P:()
B: (map…)
P:(withdraw,
deposite)
B:(setcdr!...
P:(balance)
B:(letrec…)
withdraw
deposite
getbalance
dispatch

What would happen if we omit the 'dispatch' at the end of the code?
The example above shows how OOP is implement by ImperativeProgramming:

Here we implemented the 'class' account.

The constructor is: makeaccount.

The object is dispatch. Its field is balance.

accountlist is a private static field. allbalances is a static procedure.
Private staticaccesible only to accounts.

We have the getter: getbalance, and the methods: withdraw, deposite.
Share with your friends: