Transcript Abstraction

Abstraction



A way of managing complexity for large programs
A means of separating details of computation from
use of computation
Types of Abstraction
 Data Abstraction (Today)
 Procedural Abstraction (Later)
Data Abstraction: Motivation

Languages come with primitives, which are built in
data types and operations.
 Ex: numbers, strings, booleans
 Ex: +, -, *, /, substring, eq?

Sometimes, we want to group pieces of information.
Abstract Data Types: ADTs

We want to create our own data types, which
we can treat as a unit.
 We want to be able to do the following:






“glue” data together to make them
Access parts of them
Apply procedures to them
Generate new versions of them
Modify them (later. For now, ADT’s are all
immutable)
Create expressions that include them as subunits
ADTs in Scheme: cons


Scheme provides 2 ways of gluing
things together: cons and list
Cons stands for “constructor”.
Joings two pieces of data together.

(cons x y) creates a pair




(cons 1 2) -> (1 . 2)
(car p) returns the first element
(cdr p) returns second element
(pair? p) returns whether p is a pair
A cons cell:
car
cdr
ADTs in Scheme: list

A list is a bunch of cons
cells linked together used
to join multiple things

(list a b c …) creates a list



cdr l
l:
(list 1 2 3) ->
(1 2 3)

A list:
(car l) returns the first
element
(cdr l) returns a list of
the rest of the elements
(list-ref l n) returns
the nth element of
car l
At the end of a list is a null. Null is written as ‘()
Practice with car, cdr, cons, list

What do the following print out?
 (list
1 (list 2 (list 3 4)))
 (car (cdr (list 1 2 3)))
 (cons (list 1 2 3) 4)

What prints the following?
 (1
(2 3) 4)
 (1 (2 . 3) 4)
 (((1) 2) 3)
Example: Rational Numbers


A rational number is a number that can be
represented as n/d where n, d are integers.
We can represent a rational number with a cons
cell:

Constructor:


(define (make-rat n d) (cons n d))
Accessors:
(define (numer r) (car r))
 (define (denom r) (cdr r))


Contract: This must hold regardless of implementation
(numer (make-rat n d)) -> n
 (denom (name-rat n d)) -> d

Example: Rational Number

The ADT must fulfill the following contract
regardless of implementation



(numer (make-rat n d)) -> n
(denom (name-rat n d)) -> d
Rational Numbers can also be implemented with a
list. Still fulfills contract.



(define (make-rat n d) (list n d))
(define (numer r) (car r))
(define (denom r) (cadr r))
Example: Rational Numbers

Some operations:
(define (*rat x y)
(make-rat
(* (numer x) (numer
(* (denom x) (denom
 (define (eq-rat x y)
(and (= (numer x) (numer
(= (denom x) (denom

y))
y))))
y))
y))))
Do you see a problem with this???
Example: Rational Numbers



Suppose we have the rational number 1/2 and 2/4. They are
equal, but our eq-rat method says otherwise.
How to fix it? Make sure our rational numbers are always in
lowest terms.
The following function finds the greatest common denominator

(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
Example: Rational Numbers

We can add a call to gcd in our constructor so that
we always make rational numbers in lowest terms:
(define (make-rat n d)
(cons (/ n (gcd n d)) (/ d (gcd n d))))
Because the methods that produce new rational numbers
(+rat, *rat) are defined in terms of make-rat, this is the only
place we have to make changes -> Advantage of
abstraction!

Summary: Rational Numbers

Constructor


(define (make-rat n d) (let ((g (gcd n d))
(cons (/ n g) (/ d g))))
Accessors
(define (numer r) (car r))
 (define (denom r) (cdr r))


Contract
(numer (make-rat n d)) -> n
 (denom (make-rat n d)) -> d


Sample operation

(define (*rat x y)
(make-rat (* (numer x)
(numer y))
(* (denom x) (denom y))))