Chris Pollett>Old Classes>PIC 15, Fall 1999>Practice Final
ANSWER:
mutator: this is a function which changes the value assigned to
an existing variable. For example, the function set!.
event-driven simulation: a simulation in which updates of the state
of the simulator are triggered by events. For instance, in our
wire simulator a change in the value of a wire would trigger a bunch
of procedures which need to be run by propagate.
definite clause grammar: A DCG
is a grammar with rules of the form [non-terminal] --> list of [terminal]s, [non-terminal], and Prolog rules or of the form
[non-terminal],[terminal] --> list of [terminal]s, [non-terminal], and Prolog goals. Non-terminals are allowed to be Prolog predicates. After the internal translation is done a k-ary predicate non-terminal in a DCG will become a k+2-ary Prolog predicate. As an example,
num(0) --> [zero].
num(s(X)) --> [one, greater, than], num(X).
unifier: a variable substitution which makes a list of terms equal.
For example,
(define (cons x y)
(define (set-x! v) (set! x v))
(define (set-y! v) (set! y v))
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else (error "Undefined operation -- CONS" m))))
dispatch)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
(define (set-car! z new-value)
((z 'set-car!) new-value)
z)
(define (set-cdr! z new-value)
((z 'set-cdr!) new-value)
z)
Draw the environment diagrams to illustrate the evaluation of the sequence
of expressions:
(define x (cons (cons 1 2 ) 3))
(define y (cons x x))
(set-car! (cdr y) 4)
(car x)
Answer:
Before we we do the define x, the global environment looks like
###############################
# #
# cons : ----------- #
# car: ... | #
# cdr: ... | #
# set-car!: ... | #
# set-cdr!: ... | #
# | #
###################|###########
| ^
O O---|
|
V
Parameter: x y
Body: (define (set-x! v) (set! x v))
(define (set-y! v) (set! y v))
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else (error "Undefined operation -- CONS" m))))
dispatch
To save clutter I haven't draw the arrows Parameters/Body parts of car,cdr,
set-car!, and set-cdr!
To evaluate (define x (cons (cons 1 2 ) 3)) we add x to the global environment,
we then create a new frame E1 which references the global frame where
we will evaluate (cons (cons 1 2) 3). To evaluate this expression we must bind
the parameters x and y of cons with the result of (cons 1 2) and 3. To compute
(cons 1 2) we create a new frame E2 which references E1 and bind x to 1 in this
frame and y to 2. and then do the defines in the body of cons and return dispatch.
So at this point our environment diagram looks like:
Global Frame
###################################
# #
# cons : #
# car: ... #
# cdr: ... #
# set-car!: ... #
# set-cdr!: ... #
# #
# x: will be result of # E2#####################
# (cons (cons 1 2 ) 3) # # #
################################### # x: 1 #
^ # y: 2 #
| # set-x!:... #
E1 ####################<-----# set-y!:... #
# # # dispatch:- #
# # # | #
# x:--------------------\ ###########|#########
# y: 3 # | -----------| ^
# # V |
# # --O O---
# more to be added # |
# in a moment # V
# # parameter: m
####################
body:(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else (error "Undefined operation -- CONS" m)))
I've deleted the lines to the definitions of set-x! and set-y! for readability.
Notice both x in E1 and dispatch in E2 point to the same things. This
is because the value of dispatch is what is returned from the computation of
(cons 1 2). Now that we've seen how the result of (cons 1 2) is bound to
x in E1 we can complete the computation of (define x (cons (cons 1 2) 3))
to get:
Global Frame
###################################
# #
# cons : #
# car: ... #
# cdr: ... #
# set-car!: ... #
# set-cdr!: ... #
# #
# x:-- # E2#####################
# | # # #
#####|############################# # x: 1 #
| ^ # y: 2 #
| | # set-x!:... #
| E1 ####################<-----# set-y!:... #
| # # # dispatch:- #
| # # # | #
| # x:--------------------\ ###########|#########
| # y: 3 # | -----------| ^
| # set-x!:... # V |
| # set-y!:... # --O O---
| # dispatch: - # |
| # | # V
| # | # parameter: m
| ############|#######
\-------------------| ^ body:(cond ((eq? m 'car) x) ...
V |
--O O--
|
V
parameter: m
body: (cond ((eq? m 'car) x) ...
To compute (define y (cons x x)), we create a new frame E3 referencing
the global environment in which to evaluate (cons x x). The environment
we get as a result of this computation looks like:
Global Frame
###################################
# #
# cons : #
# car: ... #
# cdr: ... #
# set-car!: ... #
# set-cdr!: ... #
# #
# x:----- # E2#####################
# y: | # # #
#/######|########################## # x: 1 #
| ^ | ^ # y: 2 #
| | | | # set-x!:... #
| | | E1 ####################<-----# set-y!:... #
| | | # # # dispatch:- #
| | | # # # | #
| | | # x:--------------------\ ###########|#########
| | | # y: 3 # | -----------| ^
| | | # set-x!:... # V |
| | | # set-y!:... # --O O---
| | | # dispatch: - # |
| | | # | # V
| | | # | # parameter: m
| | | ############|#######
| | \-------------------| ^ body:(cond ((eq? m 'car) x) ...
| | / / V |
| | | | -O O---
| | E3 | | |
| ############|##|## V
| # | | # parameter: m
| # x:--------- | # body: (cond ((eq? m 'car) x) ...
| # y:------------ #
| # set-x!:... #
| # set-y!:... #
| # dispatch:- #
| # | #
| ###########|######
\-------------| ^
V |
-O O--
|
V
parameter: m
body: (cond ((eq? m 'car) x) ...
That is, x and y in E3 point to the same place as x in the global frame.
We next compute (set-car! (cdr y) 4). To do this we first create a frame
E4 off the global frame to compute the set-car!. In this frame z is bound
to the result of (cdr y) and new-value is bound to 4. To compute
(cdr y) we create a frame E5 off of E4 in which the variable z is bound to
the value of y (in this case the value of y in the global frame which is
the same as the value of dispatch in E3). In E5
we then compute (z 'cdr). To do this we create a frame E6 off of the
frame E3 (since the function z looks for values of variables using the E3 frame).
In E6 the value m is bound to 'cdr. We then evaluate in E6
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else (error "Undefined operation -- CONS" m)))
So the value returned by (z 'cdr) will be the value of y in E3 which is the same
as the value of dispatch in E1. So z in E4 is set to this value and the frames E5
and E6 disappear. To complete our computation of (set-car! (cdr y) 4)
we now compute ((z 'set-car!) new-value) in E1. i.e., ((z 'set-car!) 4).
(The function z looks for values of variables using the E1 frame)
First we evaluate (z 'set-car!) by creating a frame E7 off of E1
where m is bound to 'set-car! evaluating the body of z in E7 returns
the function which is the value of set-x! in E1. This function is then applied to
4. To do this we create a frame E8 off of E1 where v is bound to 4 and
evaluate (set! x v). So this change the value of x in E1 to 4.
The final picture after
evaluating (set-car! (cdr y) 4) looks like:
Global Frame
###################################
# #
# cons : #
# car: ... #
# cdr: ... #
# set-car!: ... #
# set-cdr!: ... #
# #
# x:----- #
# y: | #
#/######|##########################
| ^ | ^
| | | |
| | | E1 ####################
| | | # #
| | | # #
| | | # x: 4 #
| | | # y: 3 #
| | | # set-x!:... #
| | | # set-y!:... #
| | | # dispatch: - #
| | | # | #
| | | # | #
| | | ############|#######
| | \-------------------| ^
| | / / V |
| | | | -O O---
| | E3 | | |
| ############|##|## V
| # | | # parameter: m
| # x:--------- | # body: (cond ((eq? m 'car) x) ...
| # y:------------ #
| # set-x!:... #
| # set-y!:... #
| # dispatch:- #
| # | #
| ###########|######
\-------------| ^
V |
-O O--
|
V
parameter: m
body: (cond ((eq? m 'car) x) ...
Lastly, we compute (car x). To do this we create a frame E9 off the
global frame where z is bound the the value of x in the global frame.
We then evaluate (z 'car) in E9. Now x in the global frame is
the same as dispatch in E1 , so is a function which looks up the values
of any variables it needs from E1. So to evaluate (z 'car)
we create a frame E10 off of E1
and bind the value of m to 'car and then evaluate: (cond ((eq? m 'car) x) ...)
Since (eq? m 'car) holds we get back the value of x in E10 which is
the same as its value in E1 which is 4. This is then the value (z 'car)
and hence (car x) returns.
(define (stream-map proc . argstreams)
(if ([??] (car argstreams))
the-empty-stream
([??]
(apply proc (map [??] argstreams))
(apply stream-map
(cons proc (map [??] argstreams))))))
The answer is:
(define (stream-map proc . argstreams)
(if (null? (car argstreams))
the-empty-stream
(stream-cons
(apply proc (map stream-car argstreams))
(apply stream-map
(cons proc (map stream-cdr argstreams))))))
Recall the function (eval exp env) from class which classifies exp as a primitive or special form and then directs exp to the appropriate function for evaluation. In the case of an and special form exp would be directed to the function (eval-and exp env). Explain how to implement eval-and.
The answer is:
(define (eval-and exps env)
(cond ((last-exp? exps) (eval (first-exp exps) env))
(else (if (eval (first-exp exps) env)
(eval-and (rest-exp exps end))
#f))))
(define (last-exp? exps) (eq? (cdr exps) '()))
(define (first-exp exps) (car exps) )
(define (rest-exps exps) (cdr exps) )
lookup(Key,dict(Key,X,_,_), Value) :- !, X= Value.
lookup(Key,dict(Key1,_,Left,_), Value) :- Key < Key1,
lookup(Key,Left,Value).
lookup(Key,dict(Key1,_,_,Right), Value) :- Key > Key1,
lookup(Key,Right,Value).
Explain how the following query would be evaluated:
|?- lookup(3,D,bob), lookup(4,D,bill), lookup(2,D,jane),lookup(4,D,X).
ANSWER: To evaluate this query we try to satisfy each goal in turn. So we first try to satisfy lookup(3,D,bob). Since D is an unassigned variable, this goal will match with the head of the first rule above using the substitution Key = 3, D = dict(3,X,_,_), Value = bob. Satisfying the tail of this rule sets X=bob so now D = dict(3,bob,_,_). At this point we've satisfied lookup(3,D,bob), so we try to satisfy lookup(4,D,bill). This will not match the first rule since D = dict(3,bob,_,_) and since 4 not equal to 3. It will match the head of the second rule but when it tries to evaluate Key < Key1 we'd compare 4 <3 and this rule would fail. So we try the third rule , this matches lookup(4,D,bill) where we set Key =4, D = dict(3,bob,_,Right), Key1 = 3, Value =bill . Notice one of our previous anonymous variable has now been associated with the name Right. When we try to evaluate the body of this rule, we satisfy Key > Key1 and try to do lookup(4,Right,bill). Using the first rule we get Right = dict(4,bill,_,_) so D is now dict(3,bob,_, dict(4,bill,_,_)). We have now satisfied the second goal of our query. We now try to satisfy lookup(2,D,jane). Given the value of D this won't match the head of the first rule; however, it will match with the second rule where Key =2, D = dict(3,bob,Left, dict(4,bill,_,_)) , Key1 = 3, Value =jane. Satisfying the body of the second rule we first verify Key < Key1, then do lookup(2,Left,jane). Satisfying this will give Left = dict(2,jane,_,_), so D=dict(3,bob,dict(2,jane,_,_), dict(4,bill,_,_)) . We've now satisfied the third goal. We now try to satisfy the last goal lookup(4,D,X). This will match with the third rule using the substitution Key =4, D=dict(3,bob,dict(2,jane,_,_), dict(4,bill,_,_)), Key1 = 3, Right=dict(4,bill,_,_), Value =X. So satisfy the body of this clause we need to satisfy lookup(4,Right,Value); that is, lookup(4,dict(4,bill,_,_),X). Using the first rule this binds X to bill. The final output will be
D=dict(3,bob,dict(2,jane,_,_), dict(4,bill,_,_)) X=bill
f_1(f_2(X_1,X_4), f_2(f_3(X_2),X_3))
and
f_1(X_5, f_2(f_3(X_5), X_5)).
Show step by step how the algorithm for mgu's would operate on these two terms and also show what that algorithm would then output.
Sorry for the mixture of infix prefix notation. final will only use prefix notation. Initialization Pass: ==================== failure = #f Stack = ((= f_1(f_2(X_1,X_4),f_2(f_3(X_2),X_3)) f_1(X_5,f_2(f_3(X_5),X_5)) ) ) Theta = () 2nd Pass: ==================== Equal function symbol case failure = #f Stack = ( (= f_2(X_1,X_4) X_5) (= f_2(f_3(X_2),X_3)) f_2(f_3(X_5),X_5)) ) Theta = () 3rd Pass: ==================== Something equal a variable case failure = #f Stack = ( (= f_2(f_3( X_2 ),X_3)) f_2(f_3( f_2(X_1,X_4)), f_2(X_1,X_4))) ) Theta = ( (= X_5 f_2(X_1,X_4) )) 4rth Pass: ==================== Equal function symbol case failure = #f Stack = ( (= f_3( X_2 ) f_3( f_2(X_1,X_4))) (= X_3 f_2(X_1,X_4)) ) Theta = ( (= X_5 f_2(X_1,X_4) )) 5th Pass: ==================== Equal function symbol case failure = #f Stack = ( (= X_2 f_2(X_1,X_4)) (= X_3 f_2(X_1,X_4)) ) Theta = ( (= X_5 f_2(X_1,X_4)) 6th Pass: ==================== Something equal a variable case failure = #f Stack = ( (= X_3 f_2(X_1,X_4)) ) Theta = ( (= X_2 f_2(X_1,X_4) (= X_5 f_2(X_1,X_4) ) 7th Pass: ==================== Something equal a variable case failure = #f Stack = ( ) Theta = ( (= X_3 f_2(X_1,X_4)) (= X_2 f_2(X_1,X_4) (= X_5 f_2(X_1,X_4) ) Then Theta is returned.