[SICP-ch3] Modularity, Objects, and State

ch-3 Modularity, Objects, and State

3.1 Assignment and Local State

System decomposed into computational objects with time-varying state

language must provide an assignment operator to enable us to change the value


3.1.1 Local State Variables

model the situation of withdrawing money from a bank account

1
2
3
4
5
6
(define (make-withdraw balance)
	(lambda (amount)
		(if (>= balance amount)
			(begin (set! balance (- balance amount))
				   balance)
			"Insufficient funds")))

3.1.2 The Benefits of Introducing Assignment

viewing systems as collections of objects with local state is a powerful technique for maintaining a modular design

1
2
3
4
5
6
7
(define rand (let ((x random-init))
	(lambda ()
		(set! x (rand-update x))
		x)))

(define (cesaro-test)
	(= (gcd (rand) (rand)) 1))
  • assignment encapsulates the state of the random-number generator within the rand procedure,
  • so that the details of random-number generation remain independent of the rest of the program
  • therefore easy to isolate the Monte Carlo idea

3.1.3 The Costs of Introducing Assignment

the substitution model failed


functional programming

  • Programming without assignments

  • procedure with the same arguments will produce the same result

  • can be viewed as computing mathematical functions

imperative programming

  • using explicit assignment to update the values

Pitfalls

  • the order of the assignments
  • several processes execute concurrently

Sameness and change

referentially transparent

  • A language that supports the concept that “equals can be substituted for equals”

violated when we include set!

  • cannot determine sameness without observing the effects of change

3.2 The Environment Model of Evaluation

A variable can no longer be considered to be a name for a value,

but designate a “place” in which values can be stored


Environment

  • a sequence of frames
  • each frame is a table of bindings, associate name and value

3.2.1 The Rules for Evaluation

Define procedure

  • a procedure is always a pair – consisting of some code and a pointer to an environment
  • define creates definitions by adding bindings to frames

Apply procedure

  • create a new environment – containing a frame that binds the parameters to the arguments’ value

3.2.2 Applying Simple Procedures

each call to square creates a new environment containing a binding for x


3.2.3 Frames as the Repository of Local State

how procedures and assignment can be used to represent objects with local state


3.2.4 Internal Definitions


make local procedure definitions a useful technique for modularizing programs

  • local names do not interfere external names
  • local procedures can access the arguments of the enclosing procedure

3.3 Modeling with Mutable Data

Mutators

  • Data abstraction modify compound data objects

3.3.1 Mutable List Structure

  • set-car! and set-cdr!
  • modify car & cdr pointer

Sharing and identity

use the predicate eq? to detect sharing in list structures


3.3.2 Representing Queues

( insert-queue! <queue> <item> )

( delete-queue! <queue> <item )


3.3.3 Representing Tables

assoc returns the record that has the given key as its car

lookup then checks to see that the resulting record returned by assoc is not false, and returns the value ( the cdr ) of the record

insertfirst see if there is already a record, if not, consing key and value than insert in table


3.3.4 A Simulator for Digital Circuits

event-driven simulation

  • actions (“events”) trigger further events that happen at a later time, which in turn trigger more events

wires carry digital signals

function boxes connect wires carrying input signals to other output wires

1
2
3
4
5
6
7
8
9
10
11
(define (inverter input output)
	(define (invert-input)
		(let ((new-value (logical-not (get-signal input))))	
			(after-delay inverter-delay
				(lambda () (set-signal! output new-value)))))
		(add-action! input invert-input) 'ok)

(define (after-delay delay action)
	(add-to-agenda! (+ delay (current-time the-agenda))
					action
					the-agenda))

agenda contains a schedule of things to do

propagateexecuting each procedure on the agenda in sequence


3.3.5 Propagation of Constraints


3.4 Concurrency: Time Is of the Essence

by introducing assignment, we are forced to admit time into our computational models

Objects in the world are acting concurrently —all at once.


3.4.1 The Nature of Time in Concurrent Systems


3.4.2 Mechanisms for Controlling Concurrency

using serializer

1
2
3
4
5
6
7
8
(define (make-account balance)	
	(let ((protected (make-serializer)))
		(define (dispatch m)
			(cond ((eq? m 'withdraw) (protected withdraw))
				  ((eq? m 'deposit) (protected deposit))
				  ((eq? m 'balance) balance)
				  (else (error "Unknown request: MAKE-ACCOUNT" m))))
dispatch))

With this implementation, two processes cannot be withdrawing from or depositing into a single account concurrently.


Complexity

  • concurrent programming can be treacherously difficult when there are multiple shared resources

Implementing serializers

  • synchronization mechanism called a mutex ( acquired & release )
1
2
3
4
5
6
7
8
9
10
11
12
(define (make-mutex)
	(let ((cell (list false)))
		(define (the-mutex m)
			(cond ((eq? m 'acquire)
				   (if (test-and-set! cell)
						(the-mutex 'acquire))); retry
				  ((eq? m 'release) (clear! cell))))
		the-mutex))

;actual implementation depends on how our system runs concurrent processes
(define (test-and-set! cell)
	(if (car cell) true (begin (set-car! cell true) false)))

Deadlock

  • Each process is stalled forever, waiting for the other

Concurrency, time, and communication

The basic phenomenon here is that synchronizing different processes, establishing shared state, or imposing an order on events requires communication among the processes.


3.5 Streams

an alternative approach to modeling state


Computational Object

real-world computer
real-world objects with local state computational objects with local variables
time variation in the real world time variation in the computer
implement the time variation of the states assignments to the local variables

streams

  • model change in terms of sequences that represent the time histories

3.5.1 Streams Are Delayed Lists

Streams allows one to formulate programs as sequence manipulations, while ataining the efficiency of incremental computation.


basic idea

  • construct a stream only partially
  • when accessed, automatically construct just enough more of itself to produce the required part
  • preserving the illusion that the entire stream exists

Delayed Evaluation

cons-stream

1
2
(cons-stream ⟨ a ⟩ ⟨ b ⟩ 
		== (cons ⟨ a ⟩ (delay ⟨ b ⟩ )) )

selectors

1
2
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

Implementing delay and force

  • delay must package an expression so that it can be evaluated late
1
2
(delay ⟨ exp ⟩ )
		== (lambda () ⟨ exp ⟩ )
  • force simply calls the procedure (of no arguments)
1
(define (force delayed-object) (delayed-object))
  • Optimization for forcing the same delayed object: Memoize
1
2
(delay ⟨ exp ⟩ )
		== (memo-proc (lambda () ⟨ exp ⟩ ))

3.5.2 Infinite Streams

1
2
3
(define (integers-starting-from n)
		(cons-stream n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))

Defining streams implicitly

1
2
3
4
(define fibs
		(cons-stream
		0
		(cons-stream 1 (add-streams (stream-cdr fibs) fibs))))


3.5.3 Exploiting the Stream Paradigm

1
2
3
4
5
(define (pi-summands n)
		(cons-stream (/ 1.0 n)
			(stream-map - (pi-summands (+ n 2)))))
(define pi-stream
		(scale-stream (partial-sums (pi-summands 1)) 4))

sequence accelerator

Even better, we can accelerate the accelerated sequence, and recursively accelerate that, and so on.


Infinite streams of pairs

interleave

Streams as signals

signal-processing systems that contain feedback loops

1
2
3
4
5
6
(define (integral integrand initial-value dt)
	(define int
		(cons-stream initial-value
			(add-streams (scale-stream integrand dt)
						  int)))
int)

3.5.4 Streams and Delayed Evaluation

Unfortunately, stream models of systems with loops may require uses of delay beyond the “hidden” delay supplied by cons-stream .

1
2
3
4
5
6
7
8
9
10
11
12
;does not work, because in the first line of solve the call to integral requires that the input dy be defined, which does not happen until the second line of solve

(define (solve f y0 dt)
		(define y (integral dy y0 dt))
		(define dy (stream-map f y))
		y)

;Correct Definition
(define (solve f y0 dt)
		(define y (integral (delay dy) y0 dt))
		(define dy (stream-map f y))
		y)

Normal-order evaluation

Delay and Force

  • provides great programming flexibility
  • but also can make our programs more complex

normal-order evaluation language ( Section 4.2 )

  • all arguments to procedures are automatically delayed

  • arguments are forced only when they are actually needed

Mutability and Delayed evaluation do not mix well

  • Unfortunately, including delays in procedure calls wreaks-havoc(破坏) with our ability to design programs that depend on the order of events
  • such as programs that use assignment, mutate data, or perform input or output.

3.5.5 Modularity of Functional Programs and Modularity of Objects

benefits of Assignment

  • increase the modularity by encapsulating states

Stream can provide an equivalent modularity without assignment.


A functional-programming view of time

Modeling with objects Functional programming language
Assignment and Mutable objects Stream that represents the time history of states
matches the way interacting with the world well-defined mathematical functions whose behavior does not change
raise problems of constraining the order and syncronizing raise problems when we wish to design interactive systems

We can model the world as a collection of separate, time-bound, interacting objects with state, or we can model the world as a single, timeless, stateless unity.

Each view has powerful advantages, but neither view alone is completely satisfactory. A grand unification has yet to emerge