TDDC74 Programming: Abstraktion och modellering

10.02.2014
Föreläsning 6
Data Abstraktion
TDDC74 Programming:
Abstraktion och modellering
VT 2014
Johannes Schmidt
Institutionen för datavetenskap
Linköpings universitet
*
*
*
*
*
Dugga 1
Data Abstraktion: Family exempel
Data Abstraktion: Binary Tree exempel
PUTPROP, GETPROP, APPLY
Data Abstraktion: Data-Directed-Prog. exempel
* SICP 2, Del 3
Data Abstraktion: What
properties does a person have?
A person has:
- Name
- Birth year
- Father
- Mother
- Sex
- …
Data Abstraktion:
Using a person object
; Constructor
(create-person name birthyear father mother sex)
; Selectors
(name person)
(birthyear person)
(father person)
(mother person)
(sex person)
; Recognizers
(define (female? person)
(eq? (sex person) 'w))
(define (male? person)
(eq? (sex person) 'm))
; Comparators
(define (older p1 p2)(< (birthyear p1) (birthyear p2)))
Implementation of Constructor
and Selectors (v1)
Implementation of Constructor
and Selectors (v2)
; Constructor
; Constructor
(define (create-person nameP birthyearP fatherP motherP sexP)
(define (create-person nameP birthyearP fatherP motherP sexP)
(list nameP birthyearP fatherP motherP sexP))
(list birthyearP nameP fatherP motherP sexP))
; Selectors
; Selectors
(define (name person) (car person))
(define (birthyear person) (car person))
(define (birthyear person) (cadr person))
(define (name person) (cadr person))
(define (father person) (caddr person))
(define (father person) (caddr person))
(define (mother person) (cadddr person))
(define (mother person) (cadddr person))
(define (sex person) (cadddr (cdr person)))
(define (sex person) (cadddr (cdr person)))
1
10.02.2014
Implementation of Constructor
and Selectors (v3)
assv
– lst must be a list of
(assv e lst)
; Constructor
pairs. Locates the first element of lst whose
car is equal to e according to eqv?. If such an
element exists, the pair (i.e., an element of lst)
is returned. Otherwise, the result is #f.
(define (create-person nameP birthyearP fatherP motherP sexP)
(define mylist (list (cons
(cons
(cons
(cons
(assv 'key3 mylist )
> (key3 . 11)
(define (name person)
'key1
'key2
'key3
'key4
3)
17)
11)
242)))
Binary trees in programming
root
(list (cons 'name nameP)
(cons 'birthyear birthyearP)
(cons 'father fatherP)
(cons 'mother motherP)
(cons 'sex sexP)))
; Selectors
(cdr (assv 'name person)))
(define (birthyear person) (cdr (assv 'birthyear person)))
(define (father person)
(cdr (assv 'father person)))
(define (mother person)
(cdr (assv 'mother person)))
(define (sex person)
(cdr (assv 'sex person)))
What properties do we
need from a (binary) tree?
A node-entity, with methods:
3
parent
children
8
2
9
6
4

get-value – returns the nodes value
get-left – returns the left branch
get-right – returns the right branch
leaf? – test if the tree is a leaf (no children)
empty? – test if the tree is empty

Constructor – (make-btree value left right)


7


leaves
Each node has:
1. Value
2. left child
3. right child
Implementation of Constructor
and Selectors (v1)
Implementation of Constructor
and Selectors (v2)
; Constructors
; Constructors
(define (make-btree value left right)
(define (make-btree value left right)
(list value left right))
(define (make-empty-btree)
())
; Selectors
(cons value (cons left right)))
(define (make-empty-btree)
'E)
; Selectors
(define (get-value btree)
(car btree))
(define (get-value btree)
(car btree))
(define (get-left btree)
(car (cdr btree)))
(define (get-left btree)
(car (cdr btree)))
(define (get-right btree)
(car (cdr (cdr btree))))
(define (get-right btree)
(cdr (cdr btree)))
; Predicates
; Predicates : unchanged!
(define (empty-btree? btree) (eqv? btree (make-empty-btree)))
(define (empty-btree? btree) (eqv? btree (make-empty-btree)))
(define (leaf? btree)
(define (leaf? btree)
(and (empty-btree? (get-left btree))
(empty-btree? (get-right btree))))
(and (empty-btree? (get-left btree))
(empty-btree? (get-right btree))))
2
10.02.2014
Is e present in the tree?
Exhaustive search:
A remark on binary search
Intelligent search:
(only possible if the tree is a Binary Search Tree:
(define (btree-present? e btree)
left branch = smaller elements, right branch = greater elements)
(cond ((empty-btree? btree) #f)
((equal? (get-value btree) e) #t)
(define (bstree-present? e btree)
(else (or (btree-present? e (get-left btree))
(btree-present? e (get-right btree))))))
(cond ((empty-btree? btree) #f)
((equal? (get-value btree) e) #t)
(else (if (< e (get-value btree))
(bstree-present? e (get-left btree))
(bstree-present? e (get-right btree))))))
Scenario: represent
geometric objects v1
Scenario: represent
geometric objects v2
(define (make-circle radius) radius)
(define (make-circle radius) (list 'circle radius))
(define (make-square side)
side)
(define (make-square side)
(list 'square side))
(define (make-rect a b)
(cons a b))
(define (make-rect a b)
(list 'rect a b))
(define (circle-area param)
(* (car param) (car param) pi))
(define (square-area param)
(* (car param) (car param)))
(define (rect-area param)
(* (car param) (cadr param)))
(define (circle-circ param)
(* 2 (car param) pi))
(define (circle-area radius)
(* radius radius pi))
(define (square-area side)
(* side side))
(define (rect-area param)
(* (car param) (cdr param)))
(define (circle-circ radius)
(* 2 radius pi))
(define (square-circ param)
(* (car param) 4))
(define (square-circ side)
(* side 4))
(define (rect-circ param)
(+ (* 2 (car param))
(define (rect-circ param)
(+ (* 2 (car param))
(* 2 (cdr param))))
(* 2 (cadr param))))
(define (tag
object) (car object))
(define (data object) (cdr object))
Scenario: represent
geometric objects v2
Apply
(define (area object)
(cond ((eqv? (tag object) 'circle) (circle-area (data object)))
((eqv? (tag object) 'square) (square-area (data object)))
((eqv? (tag object) 'rect)
(rect-area
(data object)))))
(define (circ object)
(cond ((eqv? (tag object) 'circle) (circle-circ (data object)))
((eqv? (tag object) 'square) (square-circ (data object)))
((eqv? (tag object) 'rect)
(area mycircle)
(area mysquare)
(rect-circ
(apply proc l) – applies proc to the
parameters in the list l.
(data object)))))
Uniform area and circ methods
for all objects!
(circ mysquare)
But we can make that more elegant…
(circ myrect)
1. Use apply 2. use putprop / getprop
> (apply + '(1 2 3))
6
> (apply * '(3 5 6))
90
3
10.02.2014
putprop / getprop
(putprop
object-type
operation-name
object-type-specific-operation)
Saves the 3-tuple in a table.
(getprop object-type
operation-name)
Allows to retrieve the accociated
object-type-specific-operation.
Scenario: represent
geometric objects v3
(putprop 'circle 'area
circle-area)
(putprop 'square 'area
square-area)
(putprop 'rect
rect-area)
'area
(define (area object)
(let* ((tag (tag object))
(proc (getprop tag 'area)))
(if (not proc)
(error "No area method found -- AREA" tag)
(apply proc (data object)))))
(area mycircle)
(area mysquare)
Scenario: represent
geometric objects v3
(define (make-circle radius) (list 'circle radius))
(define (make-square side)
(list 'square side))
(define (make-rect a b)
(list 'rect a b))
(define (circle-area radius)
(* radius radius pi))
(define (square-area side)
(* side side))
(define (rect-area a b)
(* a b))
(define (circle-circ radius)
(* 2 radius pi))
(define (square-circ side)
(* side 4))
(define (rect-circ a b)
(+ (* 2 a) (* 2 b)))
(define (tag
object) (car object))
(define (data object) (cdr object))
SICP on Data Abstraction
The basic idea of data abstraction is to structure the
programs that are to use compound data objects so
that they operate on “abstract data.” That is, our
programs should use data in such a way as to make no
assumptions about the data that are not strictly
necessary for performing the task at hand. At the same
time, a “concrete” data representation is defined
independent of the programs that use the data. The
interface between these two parts of our system will be
a set of procedures, called selectors and constructors,
that implement the abstract data in terms of the
concrete representation.
– Abelson, Sussman, & Sussman: SICP
(area myrect)
Data Abstraction - essence
Data Abstraktion:
Using a person object
Interface
Specification
No scheme code!
; Constructor
Specify an interface.
Make its
Implementation
Independent from its
Usage.
(create-person name birthyear father mother sex)
; Selectors
(name person)
(birthyear person)
(father person)
(mother person)
(sex person)
; Recognizers
(define (female? person)
(eq? (sex person) 'w))
(define (male? person)
(eq? (sex person) 'm))
; Comparators
(define (older p1 p2)(< (birthyear p1) (birthyear p2)))
4
10.02.2014
Data Abstraktion:
Using a person object
Implementation of Constructor
and Selectors (v1)
Usage
; Constructor
(create-person name birthyear father mother sex)
; Constructor
(define (create-person nameP birthyearP fatherP motherP sexP)
(list nameP birthyearP fatherP motherP sexP))
; Selectors
(name person)
(birthyear person)
(father person)
(mother person)
(sex person)
; Selectors
(define (name person) (car person))
(define (birthyear person) (cadr person))
(define (father person) (caddr person))
; Recognizers
(define (female? person)
(eq? (sex person) 'w))
(define (mother person) (cadddr person))
(define (male? person)
(eq? (sex person) 'm))
(define (sex person) (cadddr (cdr person)))
; Comparators
(define (older p1 p2)(< (birthyear p1) (birthyear p2)))
What properties do we
need from a (binary) tree?
A node-entity, with methods:
Interface
Specification

get-value – returns the nodes value
get-left – returns the left branch
get-right – returns the right branch
leaf? – test if the tree is a leaf (no children)
empty? – test if the tree is empty

Constructor – (make-btree value left right)




Implementation
Is e present in the tree?
Usage
Exhaustive search:
(define (btree-present? e btree)
(cond ((empty-btree? btree) #f)
((equal? (get-value btree) e) #t)
(else (or (btree-present? e (get-left btree))
(btree-present? e (get-right btree))))))
Implementation of Constructor
Implementation
and Selectors (v1)
; Constructors
(define (make-btree value left right)
(list value left right))
(define (make-empty-btree)
())
; Selectors
(define (get-value btree)
(car btree))
(define (get-left btree)
(car (cdr btree)))
(define (get-right btree)
(car (cdr (cdr btree))))
; Predicates
(define (empty-btree? btree) (eqv? btree (make-empty-btree)))
(define (leaf? btree)
(and (empty-btree? (get-left btree))
(empty-btree? (get-right btree))))
5

Download Report