Transcript stk

Assignments
cs7100(Prasad)
L13Assg
1
l-value vs. r-value
• Pascal/Ada:
• C/Java:
x := x + 1
x=x+1
l-value = location, address, reference, …
r-value = int, real, (sometimes even) address, …
Environment binds an identifier to a location.
env : ids -> locations
Store binds a location to a value.
store : locations -> values
assign-op : location x value x store -> store
cs7100(Prasad)
L13Assg
2
Sharing
• For functional subset, it is sufficient to
model env as a function from ids to values.
• For imperative programming that has both
assignment and sharing, separating env
and store is necessary.
 E.g., sharing/aliasing
 E.g., call by reference
Point p =
new Point();
Point q = p;
cs7100(Prasad)
void f(Point p){};
f(q);
L13Assg
3
Side-effect causing Scheme primitives
• Initialize variable: (define <var>
• Update variable: (set! <var>
• Other ops:
display, write,
<exp>)
<exp>)
set-car!, set-cdr!,...
(set! x y)
denotes location
denotes value
• Sequencing:
(begin
cs7100(Prasad)
<exp1> <exp2> … <expn>)
L13Assg
4
Extending object (not meta-) language
and the interpreter to support variable
assignment
cs7100(Prasad)
L13Assg
5
Modifying environment and the interpreter
• An identifier denotes the address of a
mutable data structure that holds a value
(that is, it models a memory location).
• This address is called a reference, and the
contents of these references are modified by
a variable assignment.
• Variable reference
(var-exp (id)
(deref (apply-env-ref env id)))
cs7100(Prasad)
L13Assg
6
(define-datatype reference reference?
(a-ref
(position integer?)
Refer to full
(vec vector?)))
interpreter code
for contextual
details
(define deref
(lambda (ref)
(cases reference ref
(a-ref (pos vec)
(vector-ref vec pos)))))
(define setref!
(lambda (ref val)
(cases reference ref
(a-ref (pos vec)
(vector-set! vec pos val)))
1))
cs7100(Prasad)
L13Assg
7
(define apply-env-ref
(lambda (env sym)
(cases environment env
(empty-env-record ()
(eopl:error 'apply-env-ref "No binding for ~s" sym) )
(extended-env-record (syms vals env)
(let ((pos (rib-find-position sym syms)))
(if (number? pos)
(a-ref pos vals)
(apply-env-ref env sym)))))))
(define apply-env
(lambda (env sym)
(deref (apply-env-ref env sym))))
cs7100(Prasad)
L13Assg
Refer to full
interpreter code
for contextual
details
8
(define extend-env-recursively
(lambda (proc-names idss bodies old-env)
(let ((len (length proc-names)))
(let ((vec (make-vector len)))
(let ((env (extended-env-record proc-names vec old-env)))
(for-each
(lambda (pos ids body)
(vector-set! vec pos (closure ids body env)))
(iota len) idss bodies)
env)))))
Refer to full
interpreter code
for contextual
details
cs7100(Prasad)
L13Assg
9
Introduction of variable assignment
• Syntax
<expression> ::=
set <identifier> = <expression>
• Abstract Syntax
varassign-exp (id rhs-exp)
• Semantics
(varassign-exp (var exp)
(set-ref! (apply-env-ref env id)
(eval-expression rhs-exp
env) ) )
l-value
cs7100(Prasad)
r-value
L13Assg
10
Simulating letrec using let and assignment
(letrec
((var1 exp1) (var2 exp2))
exp
)
(* exp1 and exp2 are lambda-forms *)
(let ((var1 ’*) (var2 ’*))
(set! var1 exp1)
(set! var2 exp2)
exp
)
cs7100(Prasad)
L13Assg
11
Simulating Objects and Classes
cs7100(Prasad)
L13Assg
12
Defining a stack object
(define empty? '())
(let
(define push!
'())
(define
pop!
'())
(define
top
'())
( (stk '()) )
(set! empty? (lambda() (null? stk)))
(set! push! (lambda(x)
(set! stk (cons x stk))))
(set!
pop! (lambda()
(set! stk (cdr stk))))
(set!
top (lambda() (car stk)))
)
cs7100(Prasad)
L13Assg
13
Using the stack object
> (empty?)
#t
> (push!
> (top)
5)
5
> (pop!)
> (empty?)
#t
cs7100(Prasad)
• Only one stack object.
• Scope of stk is
limited (encapsulation),
but its lifetime is not.
– representation pvt.
– methods public.
• Persistent state.
• Ops. share data and
change state.
L13Assg
14
stack object : Message passing style
(define stack
(let ( (stk '()) )
(lambda (msg)
(case msg
((empty?) (lambda () (null? stk)) )
(( push!) (lambda (x)
(set! stk (cons x stk))) )
(( pop! ) (lambda ()
(set! stk
((top)
(else
(cdr stk))) )
(lambda () (car stk)) )
'error ) )
)))
cs7100(Prasad)
L13Assg
15
Object vs. Class
> (stack 'empty?)
> ((stack 'empty?))
#t
> ((stack 'push!) 5)
> ((stack 'top))
5
> ((stack 'empty?))
() or #f
> ((stack 'pop!))
> ((stack 'empty?))
#t
cs7100(Prasad)
› (define s1
(make-stack))
› (define s2
(make-stack))
› ((s1 'push!) 1)
› ((s2 'push!) 2)
› ( (s1 'top) )
1
› ( (s1 'top) )
1
› ( (s2 'top) )
2
L13Assg
16
Instance/Object vs. Class/Type
(define stack
(define make-stack
(lambda()
(let ((stk '()) )
(let ((stk '()) )
(lambda (msg)
(case
(lambda (msg)
msg
(case
...
...
)
)
))
))
)
cs7100(Prasad)
msg
))
L13Assg
17
stack class : Message passing style
(define make-stack
(lambda ()
(let
( (stk '()) )
(lambda (msg)
(case
msg
((empty?) (lambda () (null? stk)) )
(( push!) (lambda (x)
(set! stk (cons x stk))) )
(( pop! ) (lambda ()
(set! stk
((top)
(else
(cdr stk))) )
(lambda () (car stk)) )
'error )
)))
)
)
cs7100(Prasad)
L13Assg
18
Template for class definition
(define class-name
(let ((class-var
val))
(lambda ()
(let ((inst-var val))
(lambda (msg)
(case msg
((m1)
code)
((m2)
code)
((c3)
code)
(else ’error) ))
) ) ) )
cs7100(Prasad)
L13Assg
19
(define make-stack
(let ((pushed 0))
(lambda ()
(let ((stk '())
(local-pushed 0)
)
(lambda (message)
(case message
((empty?) (lambda () (null? stk)))
((push!) (lambda (x)
(set! pushed (+ pushed 1))
(set! local-pushed (+ local-pushed 1))
(set! stk (cons x stk))))
((pop!) (lambda ()
(if (null? stk)
(error "Stack: Underflow")
(begin
(set! pushed (- pushed 1))
(set! local-pushed (- local-pushed 1))
(set! stk (cdr stk))))))
((top) (lambda ()
(if (null? stk)
(error "Stack: Underflow")
(car stk))))
((local-pushed) (lambda () local-pushed))
((pushed) (lambda () pushed))
(else (error "Stack: Invalid message" message))))) )))
cs7100(Prasad)
L13Assg
20
make-stack
(lambda ()
(let (…)
… pushed = 0
)
)
(make-stack)
(lambda (msg)
…
)
cs7100(Prasad)
(make-stack)
stk = ()
local-pushed = 0
(lambda (msg)
…
)
L13Assg
stk = ()
local-pushed = 0
21
Rewrite in Java
public class Stackclass {
static int pushed;
private Vector stk; private int localpushed;
static { pushed := 0 }
public Stackclass(){
localpushed = 0;
stk = new Vector();
}
public boolean empty() {
return stk.isEmpty()
};
public void push(Object x){
pushed++; localpushed++;
stk.addElement(x);
}
cs7100(Prasad)
...
L13Assg
22
...
public void pop(){
if (stk.isEmpty())
throw new Exception(“Stack Empty”);
else { --pushed; --localpushed;
stk.removeElementAt(stk.size()-1);
}
}
public Object top(){
if (empty())
throw new Exception(“Stack Empty”);
else return stk.lastElement();
}
public int pushed() { return pushed; }
public int localpushed(){
return localpushed; }
}
cs7100(Prasad)
L13Assg
23
Approximate Environment
cs7100(Prasad)
L13Assg
24
Rewrite in Java
public class Test {
public static void main(String [] args) {
Stackclass stack1 = new Stackclass();
Stackclass stack1 = new Stackclass();
stack1.push(new Integer(7));
stack1.top();
stack2.push(new Integer(6));
stack2.push(new Integer(8));
stack2.top();
stack1.localpushed();
stack2.localpushed();
stack1.pushed();
stack2.pushed();
}
}
cs7100(Prasad)
L13Assg
25
Approximate
Environment
cs7100(Prasad)
L13Assg
26
Inheritance
Share and reuse classes with
modifications to fields and methods
Improve programmer productivity
and aid code evolution
cs7100(Prasad)
L13Assg
27
Inheritance in Java
class Boundedstackclass extends Stack {
private int bound;
Boundedstackclass() {
super();
bound = 10;
}
public void push(Object x) {
if (size() < bound)
super.push(x);
else new Exception(“Overflow”);
}
public void setbound(int x){
bound = x;
}
}
• Specify only incremental changes.
• Access parent’s version of a method through super.
cs7100(Prasad)
L13Assg
28
Composition and Delegation in Java
class Boundedstackclass {
private int bound;
private Stack stk;
Boundedstackclass() {
stk = new Stack();
bound = 10;
}
public void push(Object x) {
if (size() < bound)
stk.push(x);
else new Exception(”Overflow”);
}
public void setbound(int x){
bound = x;
}
public Object top() {
return stk.top();
}
...
}
Explicit list of other delegated stack methods
cs7100(Prasad)
L13Assg
29
Delegation
(define make-bounded-stack
(lambda (n)
(let ((bound n) (stk (make-stack)))
(lambda (message)
(case message
((push!)
(if (< ((stk 'local-pushed)) bound)
(stk 'push!)
(error “Overflow”)))
((set-bound!)
(lambda (x) (set! bound x)))
((set-stack!)
(lambda (s) (set! stk s)))
(else (stk message))
)
))))
cs7100(Prasad)
L13Assg
30
Delegation
(define stk
(make-bounded-stack 24))
( (stk 'push!) 3)
( (stk 'top) )
(((make-bounded-stack 24)
'push!) 3)
; (((make-bounded-stack 24) 'top))
cs7100(Prasad)
L13Assg
31
Delegation vs Inheritance
• Code
sharing
by • Code
sharing
by
organization
of
organization
of
objects.
Delegate
classes.
Single vs
message handling.
multiple inheritance.
• Dynamic and flexible. • Static but efficient.
When and how to
Type
determines
delegate can depend
message
on system state.
interpretation.
• E.g., Java 1.1 Event • E.g., Java 1.0 Event
Model
Model
cs7100(Prasad)
L13Assg
32
Scoping: Lexical vs Static
class A {
static int cv;
int iv;
}
class Test {
public static void main(String [] args){
int iv, cv;
class B extends A {
void print() {
System.out.print( “”+ cv + iv ); /*error*/
System.out.println( “”+this.cv +this.iv );
}
}
new B(). print();
}
}
cs7100(Prasad)
L13Assg
33
Binding: Dynamic vs Static
class A {
static int cv = 10;
int iv = 70;
int f() {return 40;}
void print() {
System.out.println( “”+ cv + iv + f());
}}
class B extends A {
static int cv = 33 ;
int iv = 88;
int f() {return 55;}
}
class Test2 {
public static void main(String [] args){
new A(). print();
new B(). print();
}}
cs7100(Prasad)
L13Assg
34
Advanced Topics
• Multiple Inheritance
• E.g., C++, Eiffel.
• Meta-classes
• E.g., Smalltalk.
• Inner/Nested classes
• E.g., Java.
• Polymorphic Static Typing
• E.g., ML, Haskell.
cs7100(Prasad)
L13Assg
35