- Really 2 prominent organizational strategies for programs:
- Concentrating on objects and how their behaviours change over time
- Substitution model is not appropriate and will be replaced with environment model of computation
- Concentrating on streams like in signal processing systems
- Will be discussing delayed evaluation model of computation
- Concentrating on objects and how their behaviours change over time
- Objects have a state if it changes over time
- Can alter the vale of the defined variable with set! (implementation dependant)
- procedures which end with ! by convention change value of variable
- With begin keyword we can group and evaluate expressions part of a sequence
- Following code procedure shows how to create an “environment” for which only that procedure can modify the value of balance
- Substitution model of evaluation doesn’t work here; i.e. can’t substitute 100 for balance everytime as the code suggests
- Each call to make-withdraw defines procedures associated with balance. Dispatch takes a tag and returns corresponding method: message-passing programming
#lang sicp ; same as new-withdraw but now we set balance before-hand (define (make-account balance) (define (widthdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insuffient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (define (dispatch m) (cond ((eq? m 'widthdraw) widthdraw) ((eq? m 'deposit) deposit) (else (error "Unknown tag:" m)))) dispatch) ; everytime make-account is called; call dispatch (define W1 (make-account 100)) ; associating make-account procedure with variable W1 (define W2 (make-account 100)) ((W1 'widthdraw) 3) ; calling make-account which in turn calls dispatch ((W2 'deposit) 50) ; calling make-account which in turn calls dispatch
#lang sicp
(define (make-accumulator sum)
(lambda (inc)
(set! sum (+ sum inc))
sum))
(define S1 (make-accumulator 10))
(define S2 (make-accumulator 10))
(S1 10)
(S1 10)
(S2 5)#lang sicp
(define (make-monitored func) ; procedure which takes function
(let ((count 0)) ; set internal count variable
(define (apply-procedure amount)
(set! count (+ count 1)) ; inc everytime make-monitored called
(func amount))
(define (dispatch m)
(cond ((eq? m 'how-many-calls?) count)
((eq? m 'reset) (begin (set! count 0) count))
(else (apply-procedure m))))
dispatch))
(define s (make-monitored sqrt))
(s 100)
(s 'how-many-calls?)
(s 100)
(s 'how-many-calls?)
(s 'reset)#lang sicp
(define (make-account balance password)
(let ((incorrect-count 0))
(define (widthdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insuffient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch p m)
(cond ((> incorrect-count 7) (error "Calling the cops"))
((not (eq? p password))
(begin (set! incorrect-count (+ incorrect-count 1))
(error "Incorrect password")))
((eq? m 'widthdraw) widthdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown tag:" m))))
dispatch))
(define acc (make-account 100 'secret-password))
((acc 'secret-password 'widthdraw) 40)
((acc 'secret-password 'deposit) 40)
((acc 'another-password 'deposit) 40)- Viewing systems as objects with states can lead to modular design
- Great for modelling computational objects whose state changes over time
- No longer use substitution model of evaluation
- No evaluation model with “nice” mathematical properties
- With assignments we cannot be sure a procedure with the same arguments to the same function will produce the same result
- Programming with no assignments is referred to as functional programming
- With state, variables are no longer just names for value
- Cannot determine “change” without some a priori notion of “sameness”
- Imperative programming: making extensive use of assignments
- Bugs susceptible to imperative programs and not functional ones:
- Order of assignments becomes very important
- This is worse when executing concurrent programs
- Imperative programs not more performant than calling procedures
- May be easier to start with functional programming over imperative; as being concerned with the order of assignments detract from important concepts
#lang sicp
#lang sicp
(define (make-function x)
(lambda (y) (begin (set! x (* x y))
x)))
; order of evaluation of subexpressions matter with assigment
(define f (make-function -1))
(+ (f 0) (f 1))
(define s (make-function -1))
(+ (s 1) (s 0))- Environments are made up of a sequence of frames
- Frame: a table of bindings which associate variable names with values
- each frame (except the global environment) has a pointer to enclosing environment. We can think of this as a stack of frames. If a variable name is not found in the current frame, move up frames until it is found
- value of variable w.r.t environment is given by first frame in environment with a binding to that variable
- if no frame has a binding to that variable; the variable is unbound
- Top level frame is our global environment. It has no enclosing environments
- frame may be shared across multiple environments
- Expressions are meaningless without respect to an environment. e.g (+ 1 1) the symbol + only means addition in an environment which defines addition (has an inherited context)
- Shift in viewpoint from substitution model:
- variables not name for value but box in which we can store things
- procedures not mathematical functions but object with inherited context
- Procedures created by evaluating a lambda expression (see. below)
- “define” creates definitions by adding bindings to frames
(define (square x) (* x x))
; is the same as
(define square (lambda (x) (* x x)))- A procedure created by lambda expression relative to a given environment. Resulting procedure consists of “double bubble” (i.e. code in lambda expression and pointer to environment in which it was created)
- Procedure is an object applied to set of arguments by constructing a frame Binding the formal parameters of the procedure to the arguments of the call
- Evaluating the body of the procedure results in the creation of a new environment (i.e. sequence of frames).
- The new frame has (points to) the enclosing environment of the environment for which procedure object is being applied
- “defining” symbol creates binding in current environment frame
- “set!” first locates the first frame with binding of the variable in the environment and changes binding to represent the new value
- if variable unbound (i.e. no environment frame binding) it will throw an error
- We use this model for building an interpreter later
#lang sicp
(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (f a) (sum-of-squares (+ a 1) (* a 2)))
;; global environment has bindings to lambda expressions square, sum-of-squares and f
(f 5)
;; evaluating a procedure creates new environment (e.g. E1) (points to global)
;; need to evaluate subexpressions
;; from E1 (no binding for sum-of-squares found) we move up to global environment
;; (+ a 1) and (* a 2) subexpression evaluated -> 6 and 10
;; applying 6 and 10 to proedure sum-of-squares results in new environment (e.g. E2) (points to global)
;; now evaluate subexpressions
;; find square in global frame
;; evaluate first square subexpression results in E3 (points to global)
;; evaluate second square subexpression results in E4 (points to global)
;; because we are setting up different environments for each procedure call; we can keep different bindings for variables names resued (e.g. x)(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
;; global environment has bindings to lambda expression factorial
(factorial 6)
;; evaluate new procedure results in new environment E1
;; create binding in frame: n = 6
;; evaluate subexpression (* n (factorial (- n 1)))
;; n -> 6 and (- n 1) -> 5
;; evaluate (factorial 5) results in new environment E2 points to E1 (not global)
;; create binding in E2: n = 6
;; evaluate subexpression (* n (factorial (- n 1)))
;; n -> 5 and (- n 1) -> 4
;; evaluate (factorial 4) results in new environment E3 points to E2
;; ...#lang sicp
(define (factorial n) (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product) (+ counter 1) (max-count))))
;; global environment has bindings for factorial and fact-iter
(factorial 6)
;; evaluating (factorial 6) creates new environment E1
;; evaluate (fact-iter 6) creates new environment E2 points to E1
;; move up to global environment to find binding for (fact-iter)- Replacing substitution model with environment model does not sort out issue of tail end recursion using constant memory space. (That is addressed again in Chapter 5)
How did this code work?
#lang sicp
(define (make-withdraw balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insuffient funds")))
;; create binding for make-withdraw in global environment
(define W1 (make-withdraw 100))
;; evaluate make-withdraw resulting in creating environment E1 which binds balance to 100
;; lambda is evaluated resulting procedure object (double bubble pointing to code and E1) which is then bound to W1 in the global environment
(W1 50)
;; Now we can create frame where 50 is bound to amount (parameter of lambda)
;; this frame is enclosed by E1 (NOT global environment) because this is the environment specified by the W1 procedure object (double bubble pointing to E1)
;; amount found in first frame; whilst balance is found one frame above
(define W2 (make-withdraw 100))
;; evaluate make-withdraw resulting in new environment E2 and bind balance in new frame to 100
;; bind procedure object (double bubble pointing code to E2) resulting from lambda to W2 in global environment
;; thus W1 and W2 act as separate objects- multiple instances of procedure objects (double bubble) may share the code body or keep a separate copy of the code. Up to interpreter implementation to decide
- Remember (let ((<var> <exp>)) <body>) is syntactic sugar for ((lambda (<var>) <body>) <exp>)
#lang sicp (define (make-withdraw initial-amount) (let ((balance initial-amount)) (lambda (amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insuffient funds"))))
#lang sicp
;; procedure with internal definitions
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
;; sqrt bound to global environment
(sqrt 2)
;; sqrt called; new environment E1 created
;; E1 binds parameter x to 2
;; symbol good-enough added to E1 with procedure object (double bubble) pointing back to E1
;; similarily for improve and sqrt-iter
;; expression sqrt-iter evaluated forming environment E2 pointing to E1
;; E2 binds guess to 1.0
;; evaluating good-enough? in sqrt-iter forms E3 pointing to E1 and creates new binding in E3 guess to 1.0
;; notice sqrt-iter and good-enough? guess parameters are separated
;;- internal procedure evaluations create environments which point to the environment created the enclosing procedure’s call
- internal definitions are a useful technique for modularizing programs because:
- names of local procedures don’t interfer with external procedures
- local procedures can access arguments of the enclosing procedure as free variables
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else
(error "Unknown request: MAKE-ACCOUNT"
m))))
dispatch)
;; define make-account binding in global environment
(define acc (make-account 50))
;; evaluate make-account creating environment E1, double bubble procedure object which points to global environment
;; widthdraw, deposit and dispatch bindings added to E1 (internal definitions)
;; in E1 bind balance to 50
;; make binding acc in global environment
((acc 'deposit) 40)
;; evaluate (acc 'deposit) by creating environment E2 which points to
((acc 'withdraw) 60)- What happens when compound objects with mutable data?
- Mutators: operations which modify data objects
- Chapter 2 we used pairs to model complex objects (i.e. lists, trees …)
- Similarly we’ll look at mutable pairs
- Primitives set-car! and set-cdr! are available to us
- set-car! takes 2 parameters: existing pair pointer and pointer which will replace
- set-cdr! takes 2 parameters: existing pair pointer and pair which will be added on
- return values are dependent on implementation
- consider the case set-car! replaces pair pointer with another; the original is now garbage. Lisp has a garbage collector which recycles the memory used by this now replaced pair pointer
- We can define cons in terms of the two mutators
#lang sicp (define (cons x y) (let ((new (get-new-pair))) (set-car! new x) (set-cdr! new y) new))
#lang sicp
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))
(define (append! x y)
(set-cdr! (last-pair x) y)
x)
(define (last-pair x)
(if (null? (cdr x))
x
(last-pair (cdr x))))
(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))
(cdr x) ;; expecting b
(define w (append! x y))
(cdr x) ;; expecting ('b 'c 'd);; DONT RUN THIS
#lang sicp
(define (last-pair x)
(if (null? (cdr x))
x
(last-pair (cdr x))))
(define (make-cycle x)
(set-cdr! (last-pair x) x)
x)
(define z (make-cycle (list 'a 'b 'c))) ; last pair |'c | null | -> |'c | 'a |
(last-pair z) ;; creates forever loop#lang sicp
(define (mystery x)
(define (loop x y)
(if (null? x)
y
(let ((temp (cdr x)))
(set-cdr! x y)
(loop temp x))))
(loop x '()))- different structures can be composed of shared pairs
- this is only significant when dealing with mutators
- use eq? primitive to check if same pointers (i.e. same object)
- beware unexpected results with mutation
- Previously shown that pairs are represented with just procedures (functions)
#lang sicp (define (cons x y) (define (dispatch m) (cond ((eq? m 'car) x) ((eq? m 'cdr) y) (else (error "Undefined operation: CONS" m)))) dispatch)
- We can do something similar with mutable data
#lang sicp (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)
- Assignment requires us to modify environment which itself is a mutable data structure
- cons, car and cdr cannot represent queues on their own
- queue: FIFO data structure
- typically adding to the end means scanning the queue to find end
- inefficient O(n)
- instead have queue structure also contains a pointer to the last pair
- inserting now O(1)
- Queue = front and rear pointers
#lang sicp
;; Queue implementation
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item)
(set-car! queue item))
(define (set-rear-ptr! queue item)
(set-cdr! queue item))
(define (empty-queue? queue)
(null? (front-ptr queue)))
(define (make-queue)
(cons '() '()))
(define (front-queue queue)
(if (empty-queue? queue)
(error "FRONT called with an empty queue")
(car (front-ptr queue))))
(define (insert-queue! queue item)
(let ((new-pair (cons item '()))) ; define new item as a pair
(cond ((empty-queue? queue) ; if empty set first and last pointer to new item
(set-front-ptr! queue new-pair)
(set-rear-ptr! queue new-pair)
queue)
(else (set-cdr! (rear-ptr queue) new-pair) ; else add item to the rear
(set-rear-ptr! queue new-pair) ; update rear-ptr to new item
queue))))
(define (delete-queue! queue)
((cond ((empty-queue? queue)
(error "Cannot delete empty queue"))
(else (set-front-ptr! queue (cdr (front-ptr queue))) ; only need to update first element
; no need to update rear-ptr since we only look at front-ptr to evaluate if queue is empty
queue))))- Keep record of records with identifying keys
- headed list: tables are constructed with a backbone pair which hold dummy key-value pairs
- car points to the key-value pair
- cdr points to the next “backbone” pair
- lookup defined by assoc operation
- will be useful for meta-circular evaluator
#lang sicp ;; recursively search records and return value (define (assoc key records) (cond ((null? records) false) ((equal? key (caar records)) (car records)) ; if key equal to key in key-value pair, return "backbone" pair (else (assoc key (cdr records))))) (define (lookup key table) (let ((record (assoc key (cdr table)))) ; get key-value pair (if record (cdr record) ; return value in key-value pair false))) (define (insert! key value table) (let ((record (assoc key (cdr table)))) (if record (set-cdr! record value) ; update value at key if exists (set-cdr! table (cons (cons key value) (cdr table))))) ; else create key-value pair linked to "backbone" pair connected to the rest of table 'ok) (define (make-table) (list '*table))
- 2 keys index each value
- effectively have 2 “backbone” chains
#lang sicp (define (assoc key records) (cond ((null? records) false) ((equal? key (caar records)) (car records)) (else (assoc key (cdr records))))) (define (lookup key-1 key-2 table) (let ((subtable (assoc key-1 (cdr table)))) (if subtable (let ((record (assoc key-2 (cdr subtable)))) (if record (cdr record) false)) false))) (define (insert! key-1 key-2 value table) (let ((subtable (assoc key-1 (cdr table)))) (if subtable (let ((record (assoc key-2 (cdr subtable)))) (if record (set-cdr! record value) (set-cdr! subtable (cons (cons key-2 value) (cdr subtable))))) (set-cdr! table (cons (list key-1 (cons key-2 value)) (cdr table))))) 'ok)
#lang sicp
(define (make-table)
(let ((local-table (list '*table*)))
;; define lookup procedure
;; define insert! procedure
(define (dispatch m)
(cond ((eq? m 'lookup) lookup)
((eq? m 'insert!) insert!)
(else (error "Unknown operation: TABLE"))))
dispatch))
(define my-table (make-table))
(define get (my-table 'lookup))
(define put (my-table 'insert!))#lang sicp
(define (make-table same-key?)
(let ((local-table (list '*table*)))
(define (assoc key records)
(cond ((null? records) false)
((same-key? key (caar records) (car records)))
(else (assoc (cdr records)))))
;; define lookup
;; define insert!
;; define dispatch
))
- Memoization/tabulation: increase the performance of algorithms by storing previously calculated values
#lang sicp (define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f x))) (insert! x result table) result))))))
- Writing an event driven simulator
- Objects which corresponds to components on a circuit
- Wire has value of 0 or 1
- Function boxes connect wires to output wires
- Output signal is time delayed depending on function box
- We are designing a “language” of circuits
- language requires primitives, abstractions and combinations
- we are just defining primitives
- abstractions and combinations are inherited by Lisp
- “if a compound object does not look like a primitive, then there is something wrong with the language”
#lang sicp
; want to represent wires like:
(define A (make-wire))
(define B (make-wire))
; want higher order structures like the following half-adder
(define (half-adder a b s c)
(let ((d (make-wire)) (e (make-wire))) ; define internal wires
(or-gate a b d)
(and-gate a b c)
(and-gate d e s)
'ok))
;; can build even higher abstractions (e.g. full adder) on top of higher order structures as if they were primitives (e.g. half adder)
;; define primitive function that force change on wires
; (get-signal <wire>)
; (set-signal! <wire> <value>)
; (add-action! <wire> <procedure of no arguments>)
;; primitive digital logic
; inverter gate
(define (inverter input output)
; invert signal logic
(define (logical-not s)
(cond ((= s 0) 1)
((= s 1) 0)
(else (error "Invalid signal: INVERTER" s))))
(define (invert-input)
; let new-value be logical not of current value
; apply delay and set signal to new value
(let ((new-value (logical-not (get-signal input))))
(after-delay inverter-delay (lambda () (set-signal! output new-value))))
; apply action to let other signals know to change
(add-action! input invert-input) 'ok))
; and gate
(define (and-gate a1 a2 output)
; and gate logic
(define (logical-and s1 s2)
(cond ((and (= s1 1) (= s2 1)) 1)
((or (= s1 0) (= s2 0)) 0)
(else (error "Invalid signal: AND" s))))
; apply and gate action
(define (and-action-procedure)
(let ((new-value (logical-and (get-signal a1) (get-signal a2))))
(after-delay and-gate-delay (lambda () (set-signal! output new-value)))))
(add-action! a1 and-action-procedure)
(add-action! a2 and-action-procedure)
'ok)
; or gate
(define (or-gate a1 a2 output)
; or gate logic
(define (logical-or s1 s2)
(cond (or (= s1 1) (= s2 1) 1)
(and (= s1 0) (= s2 0) 0)
(else (error "Invalid signal: OR" s))))
; apply or gate action
(define (or-action-procedure)
(let ((new-value (logical-or (get-signal a1) (get-signal a2))))
(after-delay or-gate-delay (lambda () (set-signal! output new-value)))))
(add-action! a1 or-action-procedure)
(add-action! a2 or-action-procedure)
'ok)
(define (call-each procedures)
(if (null? procedures)
'done
(begin ((car procedures)) ; return top procedure
(call-each (cdr procedures))))) ; then recursively call rest of procedures
(define (make-wire)
; define local variables; captured by a new environment
(let ((signal-value 0) (action-procedures '()))
(define (set-my-signal! new-value)
(if (not (= signal-value new-value))
(begin (set! signal-value new-value)
(call-each action-procedures))
'done))
(define (accept-action-procedure! proc)
(set! action-procedures (cons proc action-procedures))
(proc))
(define (dispatch m)
(cond ((eq? m 'get-signal) signal-value) ; simple value return
((eq? m 'set-signal!) set-my-signal!)
((eq? m 'add-action!) accept-action-procedure)
(else (error "Unknown operation: WIRE" m))))
dispatch))
(define (call-each procedures)
(if (null? procedures)
'done
(begin ((car procedures) ; apply procedure
(call-each (cdr procedures))))))
; syntactic sugar. There is no fundamental difference between data and procedures
(define (get-signal wire) (wire 'get-signal))
(define (set-signal! wire new-value)
((wire 'set-signal!) new-value))
(define (add-action! wire action-procedure)
((wire 'add-action!) action-procedure))
;; defining a time deplay with an agenda
; need to define:
; (make-agenda)
; (empty-agenda?)
; (first-agenda-item <agenda>)
; (remove-first-agenda-item! <agenda>)
; (add-to-agenda! <time> <action> <agenda>)
; (current-time <agenda>)
(define (make-agenda) (list 0))
(define (current-time agenda) (car agenda))
(define (set-current-time! agenda time)
(set-car! agenda time))- How to simulate time delays
- Use structure called an agenda: organizes time and actions
accept-action-procedure! (see make-wire) immediately runs the first proc on make-wire initialization. This is due to …
- Assignment introduces time
- Natural objects in the world act concurrently
- Time is an imposed ordering of events
- Serialized procedures: certain collections of procedures in each serialized set that can be run concurrently
#lang sicp (define x 10) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (+ x 1)))) ; above produces 5 different outcomes (reading/writing x is interleaved) (define s (make-serializer)) (parallel-execute (s (lambda () (set! x (* x x)))) (s (lambda () (set! x (+ x 1))))) ; above produces 2 different outcomes. the read/writes within the serialized set are sequential
- Useful when used with a single shared resource
#lang sicp
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((s (make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw) (s withdraw)) ; steps within withdraw are serialized; another concurrent withdraw/deposit won't change balance until 1st withdraw done
((eq? m 'deposit) (s deposit)) ; steps within deposit are serialized
((eq? m 'balance) balance)
(else (error "Unknown request: MAKE-ACCOUNT" m))))
dispatch))
#lang sicp
(define x 10)
(define s (make-serializer))
(parallel-execute
(lambda () (set! x ((s (lambda () (* x x))))))
(s (lambda () (set! x (+ x 1)))))
;; the set! operation is not serialized (i.e. writing to x is not serialized)
;; options: 101 121 11 (squaring and setting x happens after x is read in second procedure)#lang sicp
(define x 10)
(parallel-execute
(lambda () (set! x (* x x)))
(lambda () (set! x (* x x x))))
;; Possible options:
;; 10^5
;; 100^3
;; 1000^2
;; 10*1000
;; 10*10*100 = 100^2No. Returning the balance is a single read operation. Serializing is useful for concurrent commands making read/write access to shared memory
Initially calling withdraw/deposit, we add the procedure to already initialized serializer set. Now withdraw/deposit procedures are already serialized on initialization. Now we are not adding procedures to serializer set but instead calling procedures already belonging to the serializer set. Change is safe to make.✔
#lang sicp
;; consider exchange a1 andn a2 and another process a1 and a3
;; even though widthdraw and deposit serialized
;; a second process could calculate difference before 1st exchange is done
;; producing incorrect results
(define (exchange account1 account2)
(let ((difference (- (account1 'balance)
(account2 'balance))))
((account1 'widthdraw) difference)
((account2 'deposit) difference)))
- Using a serializer is straightforward when using a single shared resource
- When dealing with multiple shared resources it is useful to expose the serializer
- In the following example, we are performing an exchange operation between 2 bank accounts (multiple shared resources)
- By exposing serializer, we can use both accounts’ serializer to serialize the entire operation
- This comes at the cost of breaking modularity, as the instance of the object is now responsible for serialization
(define (make-account-and-serializer balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (let ((balance-serializer (make-serializer))) (define (dispatch m) (cond ((eq? m 'withdraw) withdraw) ; note not serialized. see ex 3.45 ((eq? m 'deposit) deposit) ; note not serialized ((eq? m 'balance) balance) ((eq? m 'serializer) balance-serializer) ; return local serializer (else (error "Unknown request: MAKE-ACCOUNT" m)))) dispatch)) (define (deposit account amount) (let ((s (account 'serializer)) (d (account 'deposit))) ((s d) amount))) ; serialize depositing an amount (define (exchange account1 account2) ; still defined as before (let ((difference (- (account1 'balance) (account2 'balance)))) ((account1 'widthdraw) difference) ((account2 'deposit) difference))) ; solving the problem of concurrently exchanging a1 and a2 and exchaning a1 and a3 ; one transaction may change a1 balance before other transaction finishes (define (serialized-exchange account1 account2) (let ((serializer1 (account1 'serializer)) (serializer2 (account2 'serializer))) ((serializer1 (serializer2 exhange)) account1 account2))) ; combining serializers to serialize the entire operation
In the exchange problem, we needed to read from both accounts a1 and a2 (multiple shared resource access).
In the transfer problem, the operation on “from-account” is independent to “to-account.” Hence, more sophisticated serialization is not required assuming account’s withdraw and deposit procedures are serialized internally. ✔
Why didn’t we serialize withdraw and deposit procedures when exposing bank account serializer?
An operation like serialized-exchange includes withdraw and deposit procedure calls. Internally serialized withdraw and deposit procedures result in nested additions to the same serializer set.
Run into an issue where steps within serialized-exchange call withdraw/deposit but withdraw/deposit are waiting for serialized-exchange to complete. ✔
- Mutex = mutual + exclusion
- Has 2 operations:
- Acquire: Once acquired no other acquire operations on that mutex
- release
- Variant of semaphore
- Mutex is a one element cell with boolean value
- Any process must test the mutex when attempting to acquire it
- If false; loop testing it over and over again
- If true; acquire it
- releasing mutex is setting contents to false
- must be performed atomically: we must ensure when a process acquires the mutex, it must set it to true before any other process checks mutex
- otherwise we have the same concurrency issue as before
- how the testing works depends on how system runs concurrent processes
- on a sequential processor, we use a time-slicing mechanism that cycles through processes, letting them run for a short time before interrupting it and moving onto the next
- multiprocessing computers provide instructions that support atomic operations directly in hardware
- in the case two processes request mutex in exactly the same time; an arbiter (hardware device) must decide. It is not possible to make a completely fair arbiter
#lang sicp
(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))
; we must ensure when a process acquires the mutex, it must set it to true before any other process checks mutex
;; following will not suffice
;; (define (test-and-set! cell)
;; (if (car cell)
;; true
;; (begin (set-car! cell true)
;; false)))
(define (test-and-set! cell)
(without-interrupts ;; disables time-slicing interrupts whilst procedure is running
; ensures another process does not read mutex whilst another process is acquiring it
; specifically for sequential computer
(lambda ()
(if (car cell)
true
(begin (set-cdr! cell true)
false)))))
(define (clear! cell) (set-car! cell false))
(define (make-serializer)
(let ((mutex (make-mutex)))
(lambda (p)
(define (serialized-p . args)
(mutex 'aquire)
(let ((val (apply p args)))
(mutex 'release)
val))
serialized-p)))- Process 1 attempts to exchange a1 and a2
- Concurrently Process 2 exchange a2 and a1
- P1 acquires lock on a1
- P2 acquires lock on a2
- P1 waits for P2 to release a2
- P2 waits for P1 to release a1
- Avoid deadlock with a unique identification number and always protect account with the lowest-number account first
- More sophisticated techniques for different types of problems. See “deadlock-recovery” methods
- Avoid deadlock by first acquiring the lowest account number first
- Process 1 attempts to exchange a1 and a2
- Concurrently Process 2 exchange a2 and a1
- P1 acquires lock on a1 (lowest number)
- P2 will try to acquire lock on a1 (lowest number)
- P2 will wait for a1 to be freed by P1
(define (make-account-and-serializer account-number balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((balance-serializer (make-serializer))
(account-number account-number))
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw) ; note not serialized. see ex 3.45
((eq? m 'deposit) deposit) ; note not serialized
((eq? m 'balance) balance)
((eq? m 'account-number) account-number)
((eq? m 'serializer) balance-serializer) ; return local serializer
(else (error "Unknown request: MAKE-ACCOUNT" m))))
dispatch))
(define (exchange account1 account2) ; still defined as before
(let ((difference (- (account1 'balance)
(account2 'balance))))
((account1 'widthdraw) difference)
((account2 'deposit) difference)))
; solving the problem of concurrently exchanging a1 and a2 and exchaning a1 and a3
; one transaction may change a1 balance before other transaction finishes
; acquire lowest number account first to prevent deadlock
(define (serialized-exchange account1 account2)
(let ((serializer1 (account1 'serializer))
(serializer2 (account2 'serializer)))
(if (> (account1 'account-number) (account2 'account-number))
((serializer2 (serializer1 exchange)) account1 account2)
((serializer1 (serializer2 exhange)) account1 account2)))); combining serializers to serialize the entire operation- Introducing state means we are concerned about the synchronizations of events
- Intriguing connection between communication and time arises in the Theory of Relativity
- If we consider state as a function, no longer emphasize change (function does not change)
- Data which changes over time could be modeled as streams
- Streams allow us to model state without assignment
- Previously looked at modularity with functions
- Inefficient to be copying large data structures (typically lists) at every step in flow
- Streams combine iterative approach and procedures as signals approach
- Idea is to construct stream only partly
- Preserve the illusion entire stream exists
- Same as list otherwise
- Similar to implementation of rational numbers (simplification can happen at construction or selection); cdr operations of a stream happen at selection time
- deplay: special form that “promises” to return object later
- force: special form forcing stream to fulfill promise
- Delayed driven programming aka “demand driven” programming
#lang sicp ; (delay <exp>) -> returns some "promise" object ; (delay <exp>) --> syntactic sugar for (lambda () <exp>) ; (cons <a> (delay <b>)) ; cannot convert this to a procedure as it would automatically cause <b> to be evaluated (define (stream-car stream) (car stream)) (define (stream-cdr stream) (force (cdr stream))) (define (force delayed-object) (delayed-object)) (define (memo-proc proc) (let ((already-run? false) (result false)) (lambda () (if (not already-run?) (begin (set! result (proc)) (set! already-run? true) result) result)))) (define (stream-ref s n) (if (= n 0) (stream-car s) (stream-ref (stream-cdr s) (- n 1)))) ;; recursively apply process to first element (define (stream-map proc s) (if (stream-null? s) the-empty-stream (cons (proc (stream-car s)) (stream-map proc (stream-cdr s))))) (define (stream-for-each proc s) (if (stream-null? s) 'done (begin (proc (stream-car s)) (stream-for-each proc (stream-cdr s))))) (define (display-line x) (newline) (display x)) (define (display-stream s) (stream-for-each-display display-line s))
- Streams in action
#lang sicp
; stream-enumerate-interval returns (cons 10000 (delay (stream-enumerate-interval 10001 100000)))
; car is 10000
; promises to find the rest of interval if requested
; next promise (cons 10001 (delay (stream-enumerate-interval 10002 100000)))
(define (stream-enumerate-interval low high)
(if (> low high)
the-empty-stream
(cons-stream low (stream-enumerate-interval (+ low 1) high))))
(define (stream-filter pred stream)
(cond ((stream-null? stream) the-empty-stream)
((pred (stream-car stream)) ; if true return car + filter rest
(cons-stream (stream-car stream)
(stream-filter pred (stream-cdr stream))))
(else (stream-filter pred (stream-cdr stream))))) ; else just filter rest
(stream-car
(stream-cdr
(stream-filter prime? (stream-enumerate-interval 10000 100000))))
; stream-enumerate-interal -> (cons 10000 (delay (stream-enumerate-interval 10001 100000)))
; stream-filter -> tests 10000 (not prime) then calls stream-filter pred (stream-cdr stream)
; (stream-cdr stream) -> (cons 10001 (delay (stream-enumerate-interval 10002 100000)))
; carry on until (stream-car stream) -> 10007
; this is passed to stream-cdr which forces (stream-filter ... ) again
; until (stream-car stream) -> 10009
; which is passed to stream-car (returns 10009) and completes
; hence we only generated and tested numbers 10000 to 10009#lang sicp
; multiple list
; if no more lists return null
; else
; construct pair with
; apply proc on all elements of one the lists
; and apply proc on the rest of the lists
(define (stream-map proc . argstreams) ; argstreams is a list not stream
(if (null? (car argstreams))
the-empty-stream
(stream-cons
(apply proc (map (car argstreams)))
(apply stream-map (cons proc (map (cdr argstreams)))))))- We can represent streams that are infinity long; but we will only evaluate a finite portion of the stream
#lang sicp (define (integers-starting-from n) (cons-stream n (integers-starting-from (+ n 1)))) (define integers (integers-starting-from 1)) ; produces 1 and promise to produce integers at 2 ; integers will go infinitly but we are only evaluating a finite number of integers (define (divisible? x y) (= (remainder x y) 0)) (define no-sevens (stream-filter (lambda (x) (not (divisible? x 7))) integers)) (stream-ref no-sevens 100)
- Recursive way to define streams…
#lang racket
(define ones (stream-cons 1 ones))
; returns:
; car ones -> 1
; cdr ones -> promise for the rest of ones
;; ==================================================================
(define (stream-map proc . argstreams)
(if (null? (car argstreams))
empty-stream
(stream-cons
(apply proc (map (car argstreams)))
(apply stream-map (cons proc (map (cdr argstreams)))))))
(define (add-streams s1 s2) (stream-map + s1 s2)) ; see exercise 3.50
;; ==================================================================
(define integers
(stream-cons 1 (add-streams ones integers)))
; 1 + first element of integers = 2
; 1 + second element of integers = 3
; 1 + third element of integers = 4 ...
;; ==================================================================
(define fibs
(stream-cons 0 (stream-cons 1 (add-streams (stream-cdr fibs) fibs))))
; add cdr fibs (next element in fibs) to current element in fibs
;; ==================================================================
(define (scale-stream stream factor)
(stream-map (lambda () (* x factor)) stream)#lang racket
(define s (stream-cons 1 (add-streams s s)))
; creates a stream where the next element is double the previous one (i.e. x2)#lang racket
(define (stream-map proc . argstreams)
(if (null? (car argstreams))
empty-stream
(stream-cons
(apply proc (map (car argstreams)))
(apply stream-map (cons proc (map (cdr argstreams)))))))
(define (add-streams s1 s2) (stream-map + s1 s2))
(define (mul-streams s1 s2) (stream-map * s1 s2))
(define ones (stream-cons 1 ones))
(define integers
(stream-cons 1 (add-streams ones integers)))
(define factorial
(stream-cons 1 (mul-streams (cdr integers) integers)))