Understand Data Abstraction With Examples
Mar 29th, 2019 - written by Kimserey with .
Data abstraction allows us to think about complex systems in term of their properties rather than their implementations. Reasoning in term of properties provides a ground of assumptions which can be used to create new systems. In common programming languages, abstraction is present everywhere, as interfaces, as abstract and regular classes, as functions, as function signatures, as user interfaces, etc. All of theses tools provide a way to build layers of abstraction which we can work on top of to create new functionalities by manipulating data on the appropriate layer.
Today we will look at an example of data abstraction of numbers including rational numbers, a model explained in SICP Chapter 2.4, to get a sense of the importance of abstraction. We will be focusing on arithemtic operations being addition, substraction, multiplication, and division.
Numbers
Languages usually come with the numbers arithmetic operators, therefore we can define the procedures add-num, sub-num, mul-num, and div-num, which underneath uses the primitive functions provided by the language.
1
2
3
4
5
6
7
(define (add-num x y) (+ x y))
(define (sub-num x y) (- x y))
(define (mul-num x y) (* x y))
(define (div-num x y) (/ x y))
Since we will be introducing another format of number later (rational numbers), we need a way to differenciate between both, to do that we will tag the number.
1
(define (tag x) (cons 'num x))
To ease creation of numbers, we provide constructor make-num.
1
(define (make-num x) (tag x))
As the tag procedure will only be used by make-num, we can move it to be internal to the local scope of make-num.
1
2
3
(define (make-num x)
(define (tag x) (cons 'num x))
(tag x))
And to ease access to the concrete, untagged, value, we provide value.
1
2
3
4
5
(define (value x)
(if (pair? x)
(cdr x)
(error "Value provided isn't tagged:"
x)))
We also define a predicate num? identifying if the arguments provided are all numbers.
1
2
3
4
5
6
(define (num? . xs)
(if (null? xs)
#t
(and (pair? (car xs))
(equal? 'num (caar xs))
(apply num? (cdr xs)))))
The notation . args allows num? to take arbitrary arguments, then treats the arguments as a list within the procedure. apply is a procedure which takes a list of values and applies them one after the other as argument of a procedure. Using both, . args and apply, we can recursively apply num? to execute the predicate over all arguments.
We can then change our operators to specifically work on 'num type.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define (add-num x y)
(if (num? x y)
(make-num (+ (value x) (value y)))
(error "Values provided aren't numbers of type 'num:"
x y)))
(define (sub-num x y)
(if (num? x y)
(make-num (- (value x) (value y)))
(error "Values provided aren't numbers of type 'num:"
x y)))
(define (mul-num x y)
(if (num? x y)
(make-num (* (value x) (value y)))
(error "Values provided aren't numbers of type 'num:"
x y)))
(define (div-num x y)
(if (num? x y)
(make-num (/ (value x) (value y)))
(error "Values provided aren't numbers of type 'num:"
x y)))
Each one of the procedures expects input as 'num, extracts the values of each number using the value selector, applies the native operation, and constructs a new number with make-num constructor.
What we end up here is a number abstraction with a set of operators, operating on the number. Tagging allows us to specify the type 'num of the value.
Let’s see how we can define another number type.
Rational Numbers
In contrast to our first representation of single value numbers, rational numbers are represented with two values, as a fraction, with a numerator and a denominator $\frac{n}{d}$.
To construct rational numbers, we provide a make-rat constructor which combines a numerator and a denomitor, and tag the construct with a type 'rational.
1
2
3
(define (make-rat n d)
(define (tag x) (cons 'rational x))
(tag (cons n d)))
Untagged value can be extracted by reusing the value procedure created earlier. Rat? predicate validates if the arguments provided are rational numbers.
1
2
3
4
5
6
(define (rat? . xs)
(if (null? xs)
#t
(and (pair? (car xs))
(equal? 'rational (caar xs))
(apply rat? (cdr xs)))))
The recursive logic of rat? and num? being similar, we can extract a common procedure and refactore both procedures.
1
2
3
4
5
6
(define (num-type? type . xs)
(if (null? xs)
#t
(and (pair? (car xs))
(equal? type (caar xs))
(apply is-num-type? type (cdr xs)))))
The types which was previously explicitly defined, 'num and 'rational, have been moved as an argument of the procedure. Num? and rat? are then simplified by applying the concrete type together with the arguments to num-type?.
1
2
3
4
5
(define (num? . xs)
(apply num-type? 'num xs))
(define (rat? . xs)
(apply num-type? 'rational xs))
To access properties of rational numbers, we provide numer
1
2
3
4
5
(define (numer x)
(if (rat? x)
(car (value x))
(error "Value provided isn't a rational number:"
x)))
and denom selectors.
1
2
3
4
5
(define (denom x)
(if (rat? x)
(cdr (value x))
(error "Value provided isn't a rational number:"
x)))
Adding or substracting rationals is calculated by converting both rationals to the same denominator
\[\begin{split} \frac{n_{1}}{d_{1}}+\frac{n_{2}}{d_{2}} &= \frac{n_{1} * d_{2} + n_{2} * d_{1}}{d_{1} * d_{2}}\\ &and\\ \frac{n_{1}}{d_{1}}-\frac{n_{2}}{d_{2}} &= \frac{n_{1} * d_{2} - n_{2} * d_{1}}{d_{1} * d_{2}}\\ \end{split}\]which can then implemented as a add-rat procedure.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (add-rat r1 r2)
(if (rat? r1 r2)
(make-rat
(+ (* (numer r1) (denom r2)) (* (numer r2) (denom r1)))
(* (denom r1) (denom r2)))
(error "Values provided aren't rationals:"
r1 r2)))
(define (sub-rat r1 r2)
(if (rat? r1 r2)
(make-rat
(- (* (numer r1) (denom r2)) (* (numer r2) (denom r1)))
(* (denom r1) (denom r2)))
(error "Values provided aren't rationals:"
r1 r2)))
Multiplications are executed by multiplying the numerators together and denominators together.
\[\frac{n_{1}}{d_{1}}*\frac{n_{2}}{d_{2}} = \frac{n_{1} * n_{2}}{d_{1} * d_{2}}\]1
2
3
4
5
6
7
(define (mul-rat r1 r2)
(if (rat? r1 r2)
(make-rat
(* (numer r1) (numer r2))
(* (denom r1) (denom r2)))
(error "Values provided aren't rationals:"
r1 r2)))
Dividing by a fraction is equivalent to multiplying by the inverse of a the fraction. The inverse being the numerator becoming the denominator and vice-versa.
\[\frac{n_{1}}{d_{1}}*\frac{n_{2}}{d_{2}} = \frac{n_{1}}{d_{1}}*\frac{d_{2}}{n_{2}}\]1
2
(define (div-rat r1 r2)
(mul-rat r1 (make-rat (denom r2) (numer r1))))
From here executing any operation results in a non-simplified form.
1
2
> (mul-rat (make-rat 5 2) (make-rat 1 5))
'(rational 5 . 10)
Ideally for $\frac{5}{10}$, we would want the result to be $\frac{1}{2}$. As we have been using a common constructor make-rat to construct rationals, we are able to incorporate a simplification logic using gcd, greatest common divisor.
One of gcd implementation can be done following the Euclidean algorithm, which demonstrates that the greatest common divisor between a value $a$ and $b$ is equal to the geatest common divisor between $b$ and the rest $r$ from $\frac{a}{b}$.
Using this definition, we can create a gcd procedure which recursively apply gcd until the greatest common denominator is found – when $r=0$.
1
2
3
(define (gcd a b)
(let ([rest (modulo a b)])
(if (zero? rest) b (gcd b rest))))
We can then use gcd in make-rat.
1
2
3
4
(define (make-rat n d)
(define (tag x) (cons 'rational x))
(let ([g (gcd n d)])
(tag (cons (/ n g) (/ d g)))))
Re-executing the multiplication will result in a simplified fraction.
1
2
> (mul-rat (make-rat 5 2) (make-rat 1 5))
'(rational 1 . 2)
In fact any operation will now be simplified as the constructor was used in all operations.
1
2
> (add-rat (make-rat 5 10) (make-rat 5 5))
'(rational 3 . 2)
We now have two abstractions, numbers and fractions, and have independent arithmetic operations for each of the abstractions, also called the lower-level. In constrast, a higher-level is an optimal interface to work with, where the differentation between number types is not visible. The higher-level being built on top of the lower-level, we can build an arithmetic-package which provides arithmetic operations taking generic numbers.
Generic Abstraction
We have created two abstractions, an abstraction of a number and an abstraction of a rational number handling the same arithmetic operations. Those abstractions can then be used as a ground layer to provide a single arithmetic package with add, sub, mul, and div handling operations on any number, whether rational or not.
To implement the generic operations, we use apply-operation, a procedure which finds the appropriate operation matching the arguments types, and applies it.
1
2
3
4
5
6
7
(define (add x y) (apply-operation 'add x y))
(define (sub x y) (apply-operation 'sub x y))
(define (mul x y) (apply-operation 'mul x y))
(define (div x y) (apply-operation 'div x y))
Apply-operation uses get-operation, a procedure retrieving an operation from a table, which we will define later.
1
2
3
4
5
6
7
(define (apply-operation name . args)
(let* ([tags (map get-tag args)]
[op (get-operation name tags)])
(if op
(apply op args)
(error "No operation found for:"
name args tags))))
Get-tag retrieves the tag on a tagged number.
1
2
3
4
5
(define (get-tag x)
(if (pair? x)
(car x)
(error "Value provided is not tagged:"
x)))
Get-op retrieves a procedure provided the name of the operation and the tags of the arguments. We can visualize the operations as a table having the operation as row key and the types as column key, with the cell value being the procedure.
| (‘num ‘num) | (‘rational ‘rational) | |
|---|---|---|
| add | add-num | add-rat |
| sub | sub-num | sub-rat |
| mul | mul-num | mul-rat |
| div | div-num | div-rat |
Since the operation table holds the operation available, we provide a install-operation operator together with the get-operation. The set operator simply cons together an operation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define operation-table '())
(define (get-operation name tags)
(define (get ops)
(cond
[(null? ops) #f]
[(and
(equal? name (caar ops))
(equal? tags (cadar ops)))
(caddar ops)]
[else (get (cdr ops))]))
(get operation-table))
(define (install-operation name tags operation)
(set! operation-table (cons (list name tags operation) operation-table)))
Using this, we can fill the table with the arithmetic operations we have created earlier in two procedures install-number-package and install-rational-package.
Additionally, we can enclose all previously defined operations specifically targeting each type of numbers. This provide a way to separate the two contexts and make procedures only available in the packages contexts.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
(define (install-number-package)
; prelude procedures
(define (num? . xs)
(apply num-type? 'num xs))
; constructor
(define (make x)
(define (tag x) (cons 'num x))
(tag x))
; operations
(define (add x y)
(if (num? x y)
(make (+ (value x) (value y)))
(error "Values provided aren't numbers of type 'num:"
x y)))
(define (sub x y)
(if (num? x y)
(make (- (value x) (value y)))
(error "Values provided aren't numbers of type 'num:"
x y)))
(define (mul x y)
(if (num? x y)
(make (* (value x) (value y)))
(error "Values provided aren't numbers of type 'num:"
x y)))
(define (div x y)
(if (num? x y)
(make (/ (value x) (value y)))
(error "Values provided aren't numbers of type 'num:"
x y)))
; populate op-table
(install-operation 'make 'num make)
(install-operation 'add '(num num) add)
(install-operation 'sub '(num num) sub)
(install-operation 'mul '(num num) mul)
(install-operation 'div '(num num) div)
'done)
We also provide a default constructor for numbers
1
(define (make-num x) ((get-op 'make 'num) x))
and similarly for rationals.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
(define (install-rational-package)
; prelude procedures
(define (rat? . xs)
(apply num-type? 'rational xs))
(define (numer x)
(if (rat? x)
(car (value x))
(error "Value provided isn't a rational number:"
x)))
(define (denom x)
(if (rat? x)
(cdr (value x))
(error "Value provided isn't a rational number:"
x)))
; constructor
(define (make n d)
(define (tag x) (cons 'rational x))
(let ([g (gcd n d)])
(tag (cons (/ n g) (/ d g)))))
; operations
(define (add r1 r2)
(if (rat? r1 r2)
(make (+ (* (numer r1) (denom r2)) (* (numer r2) (denom r1)))
(* (denom r1) (denom r2)))
(error "Values provided aren't rationals:"
r1 r2)))
(define (sub r1 r2)
(if (rat? r1 r2)
(make (- (* (numer r1) (denom r2)) (* (numer r2) (denom r1)))
(* (denom r1) (denom r2)))
(error "Values provided aren't rationals:"
r1 r2)))
(define (mul r1 r2)
(if (rat? r1 r2)
(make (* (numer r1) (numer r2))
(* (denom r1) (denom r2)))
(error "Values provided aren't rationals:"
r1 r2)))
(define (div r1 r2)
(mul r1 (make (denom r2) (numer r1))))
; populate operation-table
(install-operation 'make 'rational make)
(install-operation 'add '(rational rational) add)
(install-operation 'sub '(rational rational) sub)
(install-operation 'mul '(rational rational) mul)
(install-operation 'div '(rational rational) div)
; populate op-table
'done)
Which we also provide a default constructor.
1
(define (make-rat n d) ((get-op 'make 'rational) n d))
Evaluating those procedures will install the functions into the operation-table.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> (install-number-package)
'done
> (install-rational-package)
'done
> operation-table
'((div (rational rational) #<procedure:div>)
(mul (rational rational) #<procedure:mul>)
(sub (rational rational) #<procedure:sub>)
(add (rational rational) #<procedure:add>)
(make rational #<procedure:make>)
(div (num num) #<procedure:div>)
(mul (num num) #<procedure:mul>)
(sub (num num) #<procedure:sub>)
(add (num num) #<procedure:add>)
(make num #<procedure:make>))
We can now use the arithmetic procedures defined at the beginning of the section.
1
2
3
4
5
6
7
8
9
10
11
> (add (make-num 2) (make-num 10))
'(num . 12)
> (mul (make-num 2) (make-num 10))
'(num . 20)
> (add (make-rat 1 2) (make-rat 1 10))
'(rational 3 . 5)
> (mul (make-rat 1 2) (make-rat 1 10))
'(rational 1 . 20)
We now end up with operators operating on a higher-level where internal types aren’t visible. The numbers come inside the arithmetic operations, and are redirected to the right lower-level operation package. The operators exposed on the higher-level package are said to be generic.
Even though we are able to accepted any type, we have no operators defined to operate on operations combining different types. For numbers, we can easily transform a number to a fraction with denomitor of one. Knowing that, we can introduce the concept of Data Coercion.
Data Coercion
So far we were only able to add numbers of the same type. In order to execute operations between numbers and rationals, we can recognize that numbers can be represented by fractions over one, $\frac{n}{1}$. This process of recognizing that a type can be expressed under the form of another type is called coercion.
We can create a procedure transforming number to fraction.
1
2
(define (number->rational n)
(make-rat (value n) 1))
1
2
> (number->rational (make-num 10))
'(rational 10 . 1)
Next we can register it as a package in a coercion-table which follows the same pattern as our operation-table.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define coercion-table '())
(define (get-coercion t1 t2)
(define (get ops)
(cond
[(null? ops) #f]
[(and
(eq? t1 (caar ops))
(eq? t2 (cadar ops)))
(caddar ops)]
[else (get (cdr ops))]))
(get coercion-table))
(define (install-coercion t1 t2 operation)
(set! coercion-table (cons (list t1 t2 operation) coercion-table)))
We install the coercion function the same way as we installed the arithmetic operations.
1
2
3
4
5
6
7
(define (install-coercion-package)
(define (number->rational n)
(make-rat n 1))
; populate coercion-table
(install-coercion 'number 'rational number->rational)
'done)
Lastly we can modify our apply-operation to raise the types to rationals in the event of any of them being numbers.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(define (apply-operation name . args)
(let* ([tags (map get-tag args)]
[t1 (car tags)]
[t2 (cadr tags)])
(if (eq? t1 t2)
(let ([op (get-operation name tags)])
(if op
(apply op args)
(error "No operation found for:"
name args tags)))
(let ([t1->t2 (get-coercion t1 t2)]
[t2->t1 (get-coercion t2 t1)])
(cond
[t1->t2 (apply-operation name (t1->t2 (car args)) (cadr args))]
[t2->t1 (apply-operation name (car args) (t2->t1 (cadr args)))]
[else (error "No operation found for:"
name args tags)])))))
To simplify the example, we consider only scenarios for operations of two arguments. We first check if the arguments types are of the same type. If they are we look for the operation in the operation-table. If they aren’t, we lookup for the coercions between t1->t2 and t2->t1 to handle the placement of arguments in both way. Making this check allows us to only use a single way coercion procedure instead of having to define two. Then using the first coercion procedure found, we raise the type and re-apply the apply-operation procedure.
Once we have put in place the coercion logic, we will now be able to add numbers and rationals as part of the same operation.
1
2
3
4
5
6
7
8
9
(install-number-package)
(install-rational-package)
(install-coercion-package)
> (mul (make-num 1) (make-rat 2 5))
'(rational 2 . 5)
> (add (make-num 5) (make-rat 2 5))
'(rational 27 . 5)
An interesting point to note is that usage complexity and data complexity move in opposite directions. The higher we are in the levels of abstraction, the easier the usage becomes, but the more complex the data we hold becomes. This observation can be seen in common languages and common frameworks, where the easiest objects to manipulate implements many abstraction layers underneath. That concludes today’s post on Data Abstraction!
Conclusion
Today we looked at examples of Data Abstractions. We created two abstractions, numbers and rationals, and defined arithmetic operations operating on those abstractions. We saw how numbers and rationals could be used as a lower-level layer for abstracting numbers, and how we could create a generic, number type agnostic, higher-level layer operating on those abstractions. Lastly we looked at data coercion which allowed us to define translations between one type to another, in order to provide higher flexibility to the generic operations. I hope you liked this post, and I’ll see you on the next one!