POPL Lecture notes: Understanding Objects
Table of Contents
1 Motivating Objects
The goal of this set of notes is to understand object-oriented programming from first principles by building several simple object systems in Scheme. Racket Scheme already has a full-fledged object system in place, but we will not rely on this at all. We will build our own object system ab initio relying, instead, on closures and environments. So you may want to ensure that you are comfortable with these ideas first.
Objects are entities that hold state in a set of state variables. The object's state may be accessed and manipulated via the object's interface. The interface could consist of identifiers, called fields or messages that refer to the object's state or functions that manipulate the state. Fields that are functions are called methods.
Usually, the object's interface is assumed fixed during the lifetime of the object, i.e., is not dependent on its state, but this is not strictly necessary.
There are at least three competing, but related, ways to motivate the idea of objects:
- Data Encapsulation and Invariant Preservation (Safety)
- Objects enclose data in the form of state variables. These variables can change via interactions. However, the object should be designed to be safe: that interactions with it should preserve certain properties (invariants) of the state that the object encapsulates.
- Late Binding (Dynamic Dispatch)
- Different objects may respond to different stimuli, also called messages, in different ways. Messages are identified through symbols, and the ability and the freedom to interpret the messages and respond lies with each object.
- State and Behaviour Extension (Inheritance and Delegation)
- The behaviour of an object is the relation that determines how the object responds to a given message. Extension means the creation of new entities that inherit state and behaviour from existing ones.
2 Data encapsulation: Objects as closures
Objects provide mechanisms for persisting data across interactions. Persistent means that data must have an indefinite extent, i.e., indefinite lifetime. The lifetime must extend beyond the life of the invocation of functions over them. Usually, designing the object involves addressing the invariance of the object's data across interactions. Invariance means that properties capturing the data's semantics are preserved.
2.1 Example
Consider the example of balance in a bank account. The state variable of this account is the account's balance and it continues to exist forever as an entity, as long as it is subject to withdrawals or deposits.
The notion of relatedness is best understood in terms of invariants
on data, i.e., what we want true about the data. For a bank account,
its balance must remain a number greater than equal to zero, i.e.,
balance >= 0 irrespective of how the balance state variable is
manipulated.
2.2 A naive design of account using a global variable to store state
In the naive design, the state variable balance is a global variable.
Two other functions deposit and withdraw operate on it.
2.2.1 Using a Global variable to hold the balance
;;; *balance* : nat?
(define *balance* 100) ;; opening balance in account
;;; deposit : nat? -> nat?
(define (deposit m) ;; deposit an amount m into the account
(set! *balance* (+ *balance* m)))
;;; withdraw : nat? -> void?
(define (withdraw m)
(if (< *balance* m)
(error 'account "balance ~a less than requested withdrawal ~a" *balance* m)
(set! *balance* (- *balance* m))))
The problem with this approach is that deposit and withdraw
together are unable to guarantee the invariant about balance, viz.,
that it should be always non-negative. The reason is that *balance*
is exposed and any other program may set its value to an arbitrary
amount as shown below.
(set! *balance* -500)
2.3 Account designed to use local state
The problem above is the uncontrolled (global) scope of the variable
*balance*.
2.3.1 Closures close over state variables
Controlling scope is best done with closures. In the code below, an
account is a set of three closures all of which share a common lexical
variable balance.
;; make-account : nat? -> (list procedure? procedure? procedure?)
(define make-account
(lambda (opening)
(let ([balance opening])
(let ([show ;; : () -> nat?
(lambda () balance)]
[deposit ;; : nat? -> void?
(lambda (m)
(set! balance (+ balance m)))]
[withdraw ;; : nat? -> void?
(lambda (m)
(if (< balance m)
(error 'withdraw "not enough balance to withdraw ~a" m)
(set! balance (- balance m))))])
(list show deposit withdraw)))))
(define acc (make-account 100))
(match-define (list acc-show acc-deposit acc-withdraw) acc)
(require rackunit)
(check-eq? (acc-show) 100 "acc1")
(acc-deposit 200)
(check-eq? (acc-show) 300 "acc2")
(acc-withdraw 300)
(check-eq? (acc-show) 0 "acc3")
2.4 Basic concepts related to objects
In object oriented programming, the following concepts are fundamental:
- Object
- An object is a container for a set of state variables.
- State
- The values of the set of state variables encapsulated by the object. The state of an object is persistent across interactions with the object.
- Construction interface
- A specification of how objects are created in terms of the type signature of its constructors.
- Interaction Interface
- A specification of how one can interact with the object. This is specified as a set of method signatures.
- Invariant
- A set of constraints that are held true across interactions with the object.
- Implementation
- An implementation of the methods and the constructors of the object.
3 Late Binding: Objects as environments
Objects are essentially environments that bind identifiers to mutable
cells. We are already familiar with environments as a way to
understand lexical scoping. For lexically scoped identifier x, its
denotation is determined statically, by locating its binding
occurrence. On the other hand, one could specify an environment
explicitly in which x is to be looked up. Such an environment
is essentially an object.
Recall the functional implementation of environments. The lookup of a
symbol x in an environment e was simply the function call (e
x). This is exactly the interface for looking up the (value of) a
symbol in an object.
3.1 Object interface
(e 'x)
Looks up the identifier x in the object obtained by evaluating the
expression e and returns the value sitting in the cell to which x
is bound (not the cell itself).
(e 'x 5)
Locates the cell to which identifier x is bound (binds x to a new
cell if x is unbound) in the object obtained by evaluating e and
puts in that cell the value 5. When x is not in the object, we
simply extend the object to contain x in its domain.
3.2 Implementing a simple object mechanism in Scheme
To implement objects, we want a way to do three things:
- Creation
- Create an object.
- Access
- Access to the state variables
- Modification
- Modification the state variables, which include the flexibility of creating a field when one doesn't exist.
We could re-implement the environment data type to do this. But hash tables (also called dictionaries) do exactly this.
;;; make-ground-obj : [] -> obj?
(define make-ground-obj
(lambda ()
(let ([table (make-hash)])
(lambda msg
(match msg
;; a list with one symbol
[(list (? symbol? x)) ;; it's a get
(hash-ref table x
(lambda ()
(error "obj: do not know field ~a" msg)))]
;; a symbol and a value
[(list (? symbol? x) v) ;; it's a set
(hash-set! table x v)]
[else (error 'make-ground-obj "invalid object lookup syntax ~a" msg)])))))
Every object is now a function created using the make-obj function.
The object allows access or mutation of fields.
(define o (make-ground-obj)) (o 'x 5) ;; returns void (o 'x) ;; returns 5 (o 'y) ;; Error since y is not a field in o.
3.3 Example: bank account
It is now easy to create an object denoting a bank account and
populate it with the field balance.
(require "obj-ground.rkt") (define a (make-ground-obj)) (require rackunit) (a 'balance 100) (check-eq? (a 'balance) 100 "ab100")
Note that it is just as easy to create and modify any other field after the object has been created.
3.4 Methods
A method is a function that operates on an object. By convention, the object is taken as the first argument to the method.
(define show-balance
(lambda (obj)
(obj 'balance)))
(define deposit
(lambda (obj m)
(let ([b (obj 'balance)])
(obj 'balance (+ b m)))))
(define withdraw
(lambda (obj m)
(let ([b (obj 'balance)])
(if (< b m)
(error 'withdraw "insufficient balance ~a" b)
(obj 'balance (- b m))))))
In some languages, like Python, by convention, the first formal parameter, which denotes an object, is called this. Note that this is an identifier, not a keyword. In languages like Java and Javascript , the this formal parameter is implicitly added to the signature of each method, so it is not an explicitly listed formal parameter. The origin and role of this is a source of persistent confusion to the beginning student of object oriented programming.
3.5 Installing methods in the object
The methods defined above may themselves be installed as fields of
the object a.
(a 'show-balance show-balance) (a 'deposit deposit) (a 'withdraw withdraw)
To protocol to invoke methods, shown below, is admittedly awkward:
((a 'deposit) a 100)
3.6 Defining a method call protocol
The function mcall, shown below protocol simplifies the application of methods:
(define mcall
(lambda (obj name . args)
(apply (obj name) (cons obj args))))
We can now use mcall to do a method call on the object a.
(require "mcall.rkt") (mcall a 'deposit 300) (mcall a 'show-balance) (mcall a 'withdraw 200) (mcall a 'show-balance)
Note that in the object a, the field balance is exposed. A call
(a 'b -100), for example, is all that is needed to break a's
invariant.
We will attend to this problem shortly, but first let us examine the third motivation for objects.
4 Inheritance extension: Objects as extended environments
The view of objects as environments easily lends itself to the idea of extension of implementation, sometimes erroneously referred to as code reuse. One way of facilitating extension of implementation is through inheritance. An object may be created to inherit another existing object. An object has its own fields that may override the fields of the parent object from which it inherits. Again, thinking of objects as environments helps, because inheritance is just like composition of environments.
4.0.1 Error Object
This object is the empty object, with no fields. Any
(define error-obj
(lambda (msg . args)
(error 'dispatch "no field ~a" msg)))
4.0.2 Constructing objects with inheritance
Now, an object may have a parent object when it is constructed. The code for this available in the racket source file ./obj.rkt
(define make-obj
(lambda maybe-parent
(let ([delegate (get-arg-or-default maybe-parent error-obj)])
(let ([table (make-hash)])
(lambda msg
(match msg
[(list (? symbol? x)) ;; a list with one symbol
(hash-ref table x ;; ;; it's a get
(lambda ()
(delegate x)))] ;; look up x in the delegate
[(list (? symbol? x) v) ;; it's a set
(hash-set! table x v)]
[else (error 'make-obj "invalid object lookup syntax ~a" msg)]))))))
(define get-arg-or-default
(lambda (args default)
(if (null? args)
default
(car args))))
4.0.3 Examples
;;; demonstrating inheritance ;;; ------------------------- (define b (make-obj)) ;; base object (b 'x 5) ;; install the binding (x 5) in b (define c (make-obj b)) ;; c inherits from b (require rackunit) ;; install the binding (y 7) in c (c 'y 7) ;; return y's binding => 7 (check-eq? (c 'y) 7 "c7") ;; return x's binding => 5 (check-eq? (c 'x) 5 "c5") ;; create the binding (x 3) in c (c 'x 3) ;; => 3 (check-eq? (c 'x) 3 "c3") ;; => 5 b's binding for x remains unchanged (check-eq? (b 'x) 5 "b5")
5 Safe dynamic dispatch
We have seen three views of objects so far: The first treats an object as a collection of functions that together share private, i.e., encapsulated state. The second shows how objects are ground (non-extended) environments that facilitate dynamic dispatch. The third builds on the second and allows objects to be viewed as extended environments.
In this section, we show how to combine dynamic dispatch with encapsulation. The result is an implementation of an object system that allows the creation of safe objects, i.e., objects that preserve their invariants. The encapsulation is achieved via closures. The dynamic dispatch is achieved by installing the closures against field names in the object.
5.1 An implementation of the bank account using safe objects
;;; make-account: nat? -> obj?
(define make-account
(lambda (initial-balance)
(let ([b initial-balance])
(let (
;; show-balance : () -> nat?
[show (lambda ()
b)]
;; deposit : nat? -> nat?
[deposit (lambda (m)
(set! b (+ b m)))]
;; withdraw : nat? -> void?
[withdraw
(lambda (m)
(if (< b m)
(error 'withdraw "not enough balance: ~a" m)
(set! b (- b m))))])))))
(let ([o (make-obj)])
(o 'show show)
(o 'deposit deposit)
(o 'withdraw withdraw)
o)
Note that the lexical variable b, denoting balance is not accessible
from outside the object.
(require rackunit) (define a (make-account 100)) ;; ((a 'show)) => 100 (check-eq? ((a 'show)) 100 "a1") ((a 'deposit) 200) ;; ((a 'show)) ; => 300 (check-eq? ((a 'show)) 300 "a2")
5.2 Using the closure call protocol for safe objects
Again, the interface for calling the closures can be made simpler.
The ccall (closure-call or closed-call) protocol shown below
cleans things up a little bit. (We called this send in an earlier
version of the notes).
;;; ccall.rkt
(define ccall
(lambda (obj fn-id . args)
(let ([fn (obj fn-id)])
(apply fn args))))
5.3 Using the ccall protocol for interacting with the safe account object
The account object a now admits interaction via ccall:
;;; back in account-safe.rkt (require "ccall.rkt") ;; (ccall a 'show) => 300 (check-eq? (ccall a 'show) 300 "a3") (ccall a 'deposit 200) ;; (ccall a 'show) ; => 500 (check-eq? (ccall a 'show) 500 "a4")
5.4 Key difference between Methods and Closures
Notice the key difference between methods and closures. Methods do
not need to close over the state variables of the object in which they
are installed. Instead, they access the state variables of the object
passed to them (identified by this). Hiding the state variable will
render the methods useless. In the above implementation of
make-account, however, closures denoted by the functions show,
deposit and withdraw close over the local state variable b of
the specific object in that holds both the state variable and the
function.
5.5 Safety
Safety refers to the property that the object's invariants are
preserved during the entire lifetime of the object: from its creation
through its interaction with other objects and till its ultimate
deletion. Note that the creation of the object via a legitimate call
to make-account (i.e., a call where the argument that initializes
the balance amount is a natural number) ensures that the object's
invariant (viz., the balance should be a natural) is maintained. All
calls of the account object's methods preserve this invariant. Even
if the methods themselves were destroyed, e.g., by setting the fields
show, deposit or withdraw to arbitrary values, the invariants on
the state variables would still be preserved. This is because the
state variables will remain inaccessible to any new values of the
method fields.
The only limitation seems to be the extensibility of the object. Although new methods could be installed in the object, these new methods would have no way of accessing the existing private state variables of the object.
6 Delegation
A safe object extends behaviour by delegation. It mimics the interface of the parent object by including the parent as one of its private fields. However it overrides certain methods of the parent by redefining them. The body of the overriding method optionally calls the parent's method, i.e., delegates to it. Notice that the object still does not have access to its parent's state; only its methods.
6.1 Example: a personal account object that extends an account object
;;; make-personal-account : string? init-balance -> personal-account?
(define make-personal-account
(lambda (name init-balance)
(let ([person-name name]
[a (make-account init-balance)]
[b (make-obj)])
;; withdraw : nat? -> void?
;; throws "amount too small" error
(let ([withdraw (lambda (v)
(if (< v 50)
(error 'withdraw "amount ~a too small" v)
(ccall a 'withdraw v)))]
;; show : () -> nat?
[show (lambda ()
(let ([b (ccall a 'show)])
(printf "~a has balance ~a~n" person-name b)
b))])
(b 'show show)
(b 'withdraw withdraw)
(b 'deposit (a 'deposit)) ; use a's deposit method
b))))
(define b (make-personal-account "Ajay" 500))
(require "ccall.rkt")
(require rackunit)
;;; (ccall b 'show) => 500
(check-eq? (ccall b 'show) 500 "b1")
(ccall b 'deposit 100)
;;; (ccall b 'show) => 600
(check-eq? (ccall b 'show) 600 "b2")
;;; (ccall b 'withdraw 25) raises error
(check-exn exn:fail?
(lambda ()
(ccall b 'withdraw 5))
"b3")
(ccall b 'withdraw 200)
;;; (ccall b 'show) => 400
(check-eq? (ccall b 'show) 400 "b4")
Note that in delegation a 'child' object may delegate to multiple 'parent' objects. The child object is not obligated to export the entire interface of the parent object. The child may add more methods, but these would not be privy to the parent's state variables.
7 Static versus Dynamic Object Oriented languages
In static object oriented languages like Java, the interface of an object is fixed once it is defined. In these languages, new state variables and/or methods or closures can not be installed in the object once it is created. This restriction has advantages in terms of safety.
In dynamic object languages, like Javascript, objects admit the addition of methods and state variables once created. However, such languages lack safety because they do not have a way to encapsulate their state variables.
So, it seems that one needs to choose between safety and dynamic extensibility of the object's state and/or interface.
The safe object paradigm regime presented in this chapter is a reasonable middle ground. Private state variables and the closures that operate on them need to be defined at the time of the object's creation. Any subsequent addition to the object's fields can not influence the object's state variables. Additionally, Delegation allows an object's behaviour or implementation to be extended in a safe way.
For dynamic object oriented languages like Javascript, it is best to construct safe objects and extend them using delegations. We will have more to say on this when we study the object mechanism of Javascript in detail later.
8 Source code
8.1 List of files
- ./account-global.rkt
- Implementation of account as a set of functions sharing a global state variable.
- ./account-closures.rkt
- Implementation of account as a set of closures, i.e., functions closing over a local state variable.
- ./account-ground-obj.rkt
- Implementation of account as a ground object with state variables and methods. The state variable is vulnerable to mutation.
- account-inherited.rkt
- This is left as an exercise.
- ./account-safe.rkt
- Implementation of account using safe objects, i.e., objects with private state and an interface consisting of closures.
- ./account-delegate.rkt
- Implementation of personal-account using safe objects and delegation.
- ./obj-ground.rkt
- Implementation of ground objects.
- ./obj.rkt
- Implementation of objects that support inheritance.
- ./mcall.rkt
- Implementation of the method call protocol.
- ./ccall.rkt
- Implementation of the closure call protocol.