I. Sequencing and Imperative Programming (4.5) What features of a language like Pascal or C haven't we discussed? A. caution in reasoning ------------------------------------------ CAUTION: SIDE EFFECTS (4.5) def: a *side effect* is either (define called! (let ((count 0)) (lambda () (begin (set! count (+ count 1)) count)))) (called!) ==> 1 (list (called!) (called!)) ==>? def: an expression E is *referentially transparent* if ------------------------------------------ Can all side effects be thought of as assignments? Are C++ expressions referentially transparent? Scheme expressions? B. sequencing (4.5.1) In C, C++, or Pascal, what syntax is designed for side effects? 1. begin Why is the semicolon needed? What does it mean semantically? ------------------------------------------ SEMICOLON AND ASSIGNMENT SYNTAX In Pascal In C/C++/Java x := x + 1; x = x + 1; y := y + x; y = y + x; z := x + y; z = x + y; procname := z + 1 return z+1; Example in Scheme: (begin (set! x (+ x 1)) (set! y (+ y x)) (set! z (+ x y)) (+ z 1)) Scheme Syntax: ::= (begin ) | (set! ) ::= {}* ::= ::= ------------------------------------------ Does this affect scoping? Does it in other languges? 2. implicit begin ------------------------------------------ SYNTACTIC SUGAR: IMPLICIT BEGIN problem: (define fact ; TYPE: (-> (number) number) (lambda (n) (begin (displayln "Entering fact with n = " n) (let ((ans (if (zero? n) 1 (* n (fact (- n 1)))))) (begin (displayln "Result from fact = " ans) ans))))) sugared form: (define fact ; TYPE: (-> (number) number) (lambda (n) (displayln "Entering fact with n = " n) (let ((ans (if (zero? n) 1 (* n (fact (- n 1)))))) (displayln "Result from fact = " ans) ans))) ------------------------------------------ ------------------------------------------ SYNTAX OF BODIES ::= {}* ::= of lambda, let, letrec, cond clause, case-clause is sugar for begin (lambda (formals) e1 ... en) = (lambda (formals) (begin e1 ... en)) (let (bindings) e1 ... en) = (let (bindings) (begin e1 ... en)) (cond (t1 e1 e2) (t2 e3 e4)) = (cond (t1 (begin e1 e2)) (t2 (begin e3 e4))) ------------------------------------------ How would you change the fact procedure to use implicit begin? ------------------------------------------ WATCH OUT FOR SYNTAX ERRORS IN IF (if (zero? n) (displayln "n = " n) 1 (* n (fact (- n 1)))) SEMANTIC ERRORS IN COND (define sum ; TYPE: (-> ((list number)) number) (lambda (lon) (cond ((null? lon) 0) (else (cdr lon) (+ (car lon) (sum lon)))))) ------------------------------------------ What are the errors? C. order of evaluation Are arguments to procedures evaluated in some particular order? How about the order of side effect in (map display '(a fine day))? ------------------------------------------ ORDER OF EVALUATION % scheme 1 ]=> (+ (begin (write 'x) 3) (begin (write 'y) 4)) 1 ]=> (map write '(a fine day)) 1 ]=> (for-each write '(a fine day)) (define map ;; TYPE: (-> ((-> (T) S) (list T)) ;; (list S)) (lambda (f ls) (if (null? ls) '() (cons (f (car ls)) (map f (cdr ls)))))) (define for-each ;; TYPE: (-> ((-> (T) void) (list T)) ;; void) (lambda (f ls) ------------------------------------------ To write run-regression-tests, is map or for-each used? II. data structure mutation (4.5.3) ------------------------------------------ DATA STRUCTURE MUTATION lists and pairs: set-car! : (-> ((pair S T) S) void) set-cdr! : (-> ((pair S T) T) void) vectors: vector-set! : (-> ((vector T) number T) void) def: an object is *mutable* if an object is *immutable* if ------------------------------------------ What is vector-set! like in C, C++, Pascal? Do you think Scheme also allows mutation of strings? integers? A. what is an object? ------------------------------------------ EXPRESSIONS EVALUATE TO OBJECTS ___________ (vector 2 3 4) ==> |_*_|_*_|_*_| | | | _v_ _v_ _v_ |2| |3| |4| ____ 'hi ==> |_hi_| ___ (+ 2 1) ==> |_3_| ------------------------------------------ B. what does cons do? ------------------------------------------ WHAT CONS DOES _____ _____ ____ (cons 3 '()) ----> | | --|--> |_()_| |__|__|_____| | | _v_ |_3_| _____ _____ ____ (cons 3 '()) ----> | | --|--> |_()_| |__|__|_____| | | _v_ |_3_| _____ _____ ___ (cons 3 4) ------> | | --|--> |_4_| |__|__|_____| | | _v_ |_3_| ------------------------------------------ ------------------------------------------ ANOTHER EXAMPLE (cons 'x (cons 'y (cons 'z '()))) ------------------------------------------ C. set-car! and set-cdr! ------------------------------------------ EFFECT OF SET-CAR! AND SET-CDR! (define a (cons 1 (cons 2 '()))) (set-car! a 342) (set-cdr! a 227) ------------------------------------------ D. modeling objects in Scheme ------------------------------------------ AN ADT FOR OBJECTS (CELLS) Operations make-cell: (-> (datum) cell) cell?: (-> (datum) boolean) cell-ref: (-> (cell) datum) cell-set!: (-> (cell datum) void) cell-swap!: (-> (cell cell) void) Behavior ------------------------------------------ ------------------------------------------ CELL IMPLEMENTATION (Fig. 4.5.1) (define cell-tag "cell") (define make-cell ;; TYPE: (-> (Expressed-Value) (cell T)) (lambda (x) (define cell? ;; TYPE: (-> (datum) boolean) (lambda (x) (and (vector? x) (= (vector-length x) 2) (eq? (vector-ref x 0) cell-tag)))) (define cell-ref ;; TYPE: (-> ((cell T)) T) (lambda (x) (define cell-set! ;; TYPE: (-> ((cell T) T) void) (lambda (x value) (define cell-swap! ;; TYPE: (-> ((cell T) (cell T)) void) (lambda (cell-1 cell-2) (let ((temp (cell-ref cell-1))) (cell-set! cell-1 (cell-ref cell-2)) (cell-set! cell-2 temp)))) ------------------------------------------ III. sharing (4.6) ------------------------------------------ SHARING (4.6) > (define a (cons 1 (cons 2 '()))) > (define b (cons (cons 3 '()) (cons 4 (cons 5 '())))) > (define c (cons a (cdr b))) > (set-car! (cdr b) a) > (eq? (car (cdr b)) a) ------------------------------------------ Can you draw what happens if we do (set-car! b a)? ------------------------------------------ > (define a (cons 1 (cons 2 '()))) > (define b (cons (cons 3 '()) (cons 4 (cons 5 '())))) > (define c (cons a (cdr b))) > (set-car! b a) > (equal? c b) > (eq? c b) a: [ *--]--->[ * | *-]--> [ * | *-]--> () ^ | | | v v | 1 2 \ \ \ c: [ *--]--->[ * | * ] \ \ \ b: [ *--]--->[ * | * ] | / \ / v vv [ * | * ] [ * | *-]-->[ * | * ] | | | | | v v v v v 3 () 4 5 () ------------------------------------------ ------------------------------------------ CIRCULARITY (define f (cons 1 '())) > (set-cdr! f f) > f ------------------------------------------ A. append! ------------------------------------------ DANGEROUS APPEND! (define append! ;;TYPE:(-> ((list T) (list T)) (list T)) (lambda (ls1 ls2) ;; MODIFIES: ls1 ;; EFFECT: modify ls1 to have the ;; elements of ls1 followed by ls2's (define last-pair ;; TYPE: (-> ((nonempty-list T)) ;; (pair T (list T))) (lambda (x) (if (null? (cdr x)) x (last-pair (cdr x))))) ------------------------------------------ ------------------------------------------ EXAMPLE OF APPEND! > (define c (list 3 4)) > (define d (list 2)) > (define y (append! c d)) c: [ *--]--->[ * | *-]--> [ * | *-]--> () | | v v 3 4 d: [ *--]--->[ * | *-]--> () | v 2 ------------------------------------------ What is c? d? y? After executing append! what are c? d? y? Is it any different if we execute (define y (append! (cdr c) d))? ------------------------------------------ EXAMPLE OF APPEND! > (define c (list 3 4)) > (define d (list 2)) > (define y (append! (cdr c) d)) c: [ *--]--->[ * | *-]--> [ * | *-]--> () | | v v 3 4 d: [ *--]--->[ * | *-]--> () | v 2 ------------------------------------------ What if we use append instead of append!? ------------------------------------------ RECALL THE SAFE APPEND PROCEDURE (define append ;; TYPE: (-> ((list T) (list T)) ;; (list T)) (lambda (ls1 ls2) (if (null? ls1) ls2 (cons (car ls1) (append (cdr ls1) ls2))))) ------------------------------------------ ------------------------------------------ USING APPEND INSTEAD > (define c (list 3 4)) > (define d (list 2)) > (define y (append c d)) c: [ *--]--->[ * | *-]--> [ * | *-]--> () | | v v 3 4 d: [ *--]--->[ * | *-]--> () | v 2 ------------------------------------------ B. what define and set! do ------------------------------------------ DEFINE AND SET! (define a (cons 3 '())) ___ _____ _____ ____ a:[ --]----------> | | --|--> |_()_| |__|__|_____| | | _v_ |_3_| (set! a (cons 4 (cons 5 '()))) ------------------------------------------ ------------------------------------------ NESTED DEFINES VS. SET (define a (cons 3 '())) (define a-set! ;; TYPE: (-> ((list number)) ;; (list number)) (lambda (lon) (define a lon) lon)) (a-set! (cons 2 '())) ___ _____ _____ ____ a:[ --]----------> | | --|--> |_()_| |__|__|_____| | | _v_ |_3_| ------------------------------------------ C. garbage How is this handled in Scheme? C++? Java? D. using set! and local bindings to make objects. ------------------------------------------ AN OO STACK ADT > (send a-stack 'push! 1) > (send a-stack 'push! 2) > (send a-stack 'top) > (send a-stack 'pop!) > (send a-stack 'top) > (send a-stack 'pop!) In C++ syntax, how would you write (send a-stack 'push! 1) ------------------------------------------ What's your idea of what an object is like in C++? ------------------------------------------ PLAN FOR OBJECTS AND SEND Idea: object = closure = environment (data members) and methods map (fun members) methods map : message -> method So: message send = ------------------------------------------ ------------------------------------------ EXAMPLE OBJECT (define a-stack (let ((stk '())) (lambda (message) (case message ((empty?) (lambda () (null? stk))) ((push!) (lambda (x) (set! stk (cons x stk)))) (else (error "stack: Invalid message" message)))))) ------------------------------------------ What does the message send then look like with this rep of objects? ------------------------------------------ MESSAGE SEND (send obj msg arg1 arg2 ...) = ((obj msg) arg1 arg2 ...) (define send ;; TYPE: (-> (datum ...) datum) (lambda send-args ;; this isn't very careful (if (< (length send-args) 2) (error "send: too few args") (let ((obj (car send-args)) (msg (cadr send-args)) (args (cddr send-args))) (apply (obj msg) args))))) ------------------------------------------ This gives us exactly one stack. How can we set it up to make more? (if time) can you turn this into the same for cells?