missing slides from lecture #8

missing slides fromlecture #8 בחרומ אובמ 1

---

How does the interpreter prints lists and pairs ?? בחרומ אובמ 2

---

First version, using dot notation (define (print-list-structure x) (define (print-contents x) (print-list-structure (car x)) (display " . ") (print-list-structure (cdr x))) (cond ((null? x) (display "()")) ((atom? x) (display x)) (else (display "(") (print-contents x) (display ")")))) (p-l-s (list 1 2 3)) ==> (1 . (2 . (3 . ()))) בחרומ אובמ 3

---

Second version, try to identify lists (define (print-list-structure x) (define (print-contents x) (print-list-structure (car x)) (cond ((null? (cdr x)) nil) ((atom? (cdr x)) (display " . ") (print-list-structure (cdr x))) (else (display " ") (print-contents (cdr x))) (cond ((null? x) (display "()")) ((atom? x) (display x)) (else (display "(") (print-contents x) (display ")")))) (p-l-s (list 1 2 3)) ==> (1 2 3) 4

---

More examples How to create the fol owing output ? ( 1 2 . 3) (cons 1 (cons 2 3)) (1. 2 3) cannot בחרומ אובמ 5

---

Lecture #10 בחרומ אובמ 6

---

A bigger example: symbolic diffrentiation בחרומ אובמ 7

---

3. A better implementation 1. Use cond instead of nested if expressions2. Use data abstraction • To use cond: • write a predicate that col ects al tests to get to a branch: (define sum-expr? (lambda (e) (and (pair? e) (eq? (car e) ‘+)))); type: Expr -> boolean • do this for every branch: (define variable? (lambda (e) (and (not (p ב a חר i ומ r או ?במ e)) (symbol? e)))) 8

---

Use data abstractions • To eliminate dependence on the representation: (define make-sum (lambda (e1 e2) (list ‘+ e1 e2)) (define addend (lambda (sum) (cadr sum))) בחרומ אובמ 9

---

A better implementation (define deriv (lambda (expr var) (cond ((number? expr) 0) ((variable? expr) (if (eq? expr var) 1 0)) ((sum-expr? expr) (make-sum (deriv (addend expr) var) (deriv (augend expr) var))) ((product-expr? expr) <handle product expression>) (else (error "unknown expression type" expr)) )) בחרומ אובמ 10

---

Deriv: Reduction problem (deriv ‘(+ x 3) ‘x) ==> (+ 1 0) (deriv ‘(* x y) ‘x) ==> (+ (* x 0) (* 1 y)) (deriv ‘(* (* x y) (+ x 3)) ‘x) ==> (+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+ x 3))) בחרומ אובמ 11

---

Changes are isolated (deriv ‘(+ x y) ‘x) ==> (+ 1 0) (a list!) (define (make-sum a1 a2) (cond ((=number? a1 0) a2) ((=number? a2 0) a1) ((and (number? a1) (number? a2)) (+ a1 a2)) (else (list ‘+ a1 a2)))) (define (=number? exp num) (and (number? exp) (= exp num))) (deriv ‘(+ x y) ‘x) ==> 1(deriv ‘(* x y) ‘x) ==> y בחרומ אובמ 12

---

Variable number of arguments in sums and products (deriv ’(+ (* x 3) 10 (+ 2 x)) ’x) (define (augend s) (if (null? (cdddr s)) (caddr s) (cons ‘+ (cddr s)))) (augend ’(+ (* x 3) 10 (+ 2 x))) ==> (+ 10 (+ 2 x)) (deriv ’(+ (* x 3) 10 (+ 2 x)) ’x) ==> 4 בחרומ אובמ 13

---

Variable number of summands and multipliers (deriv ‘(+ (* x a) (* x b) (* x c)) ‘x) =>(+ a (+ b c)) (define (make-sum a1 a2) (cond ((=number? a1 0) a2) ((=number? a2 0) a1) ((and (number? a1) (number? a2)) (+ a1 a2)) ((sum? a2) (cons ‘+ (cons a1 (cdr a2)))) (else (list ‘+ a1 a2)))) (deriv ‘(+ (* x a) (* x b) (* x c)) ‘x) =>(+ a b c) בחרומ אובמ 14

---

Adding exponential expressions (fn)’ = nf(n-1)f’ (define (deriv exp var) (cond …… ((exponential exp) (make-product (make-product (exponent exp) (make-exponential (base exp) (- (exponent exp) 1))) (deriv (base exp) var))) בחרומ אובמ 15

---

Constructors and selectors for exponentiation (define (make-exponential b e) (cond ((= e 0) 1) ((= e 1) b) (else (list ‘** b e)))) (define (exponential? exp) (and (pair? exp) (eq? (car exp) ‘**))) (define (base exp) (cadr exp))(define (exponent exp) (caddr exp)) בחרומ אובמ 16

---

Representing sets בחרומ אובמ 17

---

Definitions A set is a collection of distinct items (element-of-set? x set) (adjoin-set x set) (union-set s1 s2) (intersection-set s1 s2) בחרומ אובמ 18

---

Version 1: Represent a set as an unordered list (define (element-of-set? x set) (cond ((null? set) false) ((equal? x (car set)) true) (else (element-of-set? x (cdr set))) equal? : Like eq? for symbols. Works for numbers Works recursively for compounds: Apply equal? to the components. (eq? (list ‘a ‘b) (list ‘a ‘b)) (equal? (list ‘a ‘b) (list ‘a ‘b)) בחרומ אובמ 19

---

Version 1: Represent a set as a list (define (adjoin-set x set) (if (element-of-set? x set) set (cons x set))) בחרומ אובמ 20

---

Version 1: Represent a set as a list (define (intersection-set set1 set2) (cond ((or (null? set1) (null? set2)) ‘()) ((element-of-set? (car set1) set2) (cons (car set1) (intersection-set (cdr set1) set2))) (else (intersection-set (cdr set1) set2)))) בחרומ אובמ 21

---

Version 1: Represent a set as a list (define (union-set set1 set2) (cond ((null? set1) set2)) ((not (element-of-set? (car set1) set2)) (cons (car set1) (union-set (cdr set1) set2))) (else (union-set (cdr set1) set2)))) (define (union-set set1 set2) (cond ((null? set1) set2)) (else (adjoin-set (car set1) (union-set (cdr set1) set2))) בחרומ אובמ 22

---

Complexity Element-of-set Θ(n)Adjoin-set Θ(n) Intersection-set Θ(n2) Union-set Θ(n2) בחרומ אובמ 23

---

Version 2: Representing a set as an ordered list (define (element-of-set? x set) (cond ((null? set) false) ((= x (car set)) true) ((< x (car set)) false) (else (element-of-set? x (cdr set))) n/2 steps on average ∈ Θ(n) Adjoin-set is similar, please try by yourself בחרומ אובמ 24

---

Ordered lists (cont.) (define (intersection-set set1 set2) (cond ((or (null? set1) (null? set2)) ‘()) ((element-of-set? (car set1) set2) (cons (car set1) (intersection-set (cdr set1) set2))) (else (intersection-set (cdr set1) set2)))) Can we do it better ? בחרומ אובמ 25

---

Ordered lists (cont.) (define (intersection-set set1 set2) (if (or (null? set1) (null? set2)) ‘() (let ((x1 (car set1)) (x2 (car set2))) (cond ((= x1 x2) (cons x1 (intersection-set (cdr set1) (cdr set2)))) ((< x1 x2) (intersection-set (cdr set1) set2)) ((< x2 x1) (intersection-set set1 (cdr set2))) בחרומ אובמ 26

---

Ordered lists (Cont.) set1 set2 intersection (1 3 7 9) (1 4 6 7) (1 (3 7 9) (4 6 7) (1 (7 9) (4 6 7) (1 (7 9) (6 7) (1 (7 9) (7) (1 (9) () (1 7) Time and space ∈ Θ(n) Union — similar בחרומ אובמ 27

---

Complexity unordered ordered Element-of-set Θ(n) Θ(n) Adjoin-set Θ(n) Θ(n) Intersection-set Θ(n2) Θ(n) Union-set Θ(n2) Θ(n) בחרומ אובמ 28

---

Representing sets as binary trees 7 3 3 9 1 7 5 1 5 12 9 12 בחרומ אובמ 29

---

Representing sets as binary trees (Cont.) 7 (define (entry tree) (car tree)) 3 9 (define (left-branch tree) (cadr tree)) 1 5 12 (define (right-branch tree) (caddr tree)) (define (make-tree entry left right) (list entry left right)) בחרומ אובמ 30

---

Representing sets as binary trees (Cont.) (define (element-of-set? x set) (cond ((null? set) false) ((= x (entry set)) true) ((< x (entry set)) (element-of-set? x (left-branch set))) ((> x (entry set)) (element-of-set? x (right-branch set))) Complexity: Θ(d) If tree is balanced d ≈ log(n) בחרומ אובמ 31

---

Representing sets as binary trees (Cont.) 1 7 3 3 9 5 1 5 12 7 9 12 בחרומ אובמ 32

---

Representing sets as binary trees (Cont.) (define (adjoin-set x set) (cond ((null? set) (make-tree x ‘() ‘())) ((= x (entry set)) set) ((< x (entry set)) (make-tree (entry set) (adjoin-set x (left-branch set)) (right-branch set))) ((> x (entry set)) (make-tree (entry set) (left-branch set) (adjoin-set x (right-branch set))) בחרומ אובמ 33

---

Complexity unordered ordered trees Element-of-set Θ(n) Θ(n) Θ(log(n)) Adjoin-set Θ(n) Θ(n) Θ(log(n)) Intersection-set Θ(n2) Θ(n) Θ(nlog(n)) Union-set Θ(n2) Θ(n) Θ(nlog(n)) בחרומ אובמ 34

---