SCIP 2.1 Introduction to Data Abstraction

Mix.install([])

2.1 Introduction to Data Abstraction

Compound Data: an abstracted data object made of combined data objects.

Data Abstraction: isolating the represention of data objects from the use of the data objects.

Abstraction Barriers: defined segments of a program erected by Data Abstractions.

Conventional Interfaces: compound data objects can be used as interfaces.

Symbolic Expressions: data whose parts can be arbitary symbols rather than just numbers.

Generic Operations: operations that handle different types of data.

Data-Directed Programming: a technique whereby individual data representations can be designed in isolation and then combined additively (i.e., without modification).

Pairs

Lisp provides a compoud structure called a pair, which can be constructed with the primitive procedure cons (“construct”). The parts of a pair can be extracted using the primitive procedures car and cdr :

(define x (cons 1 2))
(car x)
;; 1
(cdr x)
;; 2

Notice that a pair is a data object that can be:

• given a name
• manipulated

Data objects constructed from pairs are called list-structured data.

Representing Rational Numbers

We can use pairs to represent rational numbers:

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

We have made a constructor via make-rat and selectors via numer and denom.

2.1.2 Abstraction Barriers

Underlying data abstraction is the idea that one should identify for each type of data object a basic set of operations in terms of which all manipulations of that type will be expressed and then to only use those operations to manipulate data.

We structure a program to create abstraction barriers that isolate the different levels of a system. The -- lines represent such barriers:

-- Programs that use rational numbers --

> Rational numbers in problem domain

-- add-rat sub-rat --

> Rational numbers as numerators and denominators

-- make-rat numer denom --

> Rational numbers as pairs

-- cons car cdr --

> However pairs are represented

In effect, procedures at each level are the interfaces that define the abstraction barriers and connect the different levels.

2.1.3 What is Meant by Data?

Data is defined by some collection of selectors and constructors, together with specified conditions that these procedures must fulfill in order to be valid representations.

Note that this definition can apply to both high and low level representations. Note also that the “data” may not be represented under the hood in any sort of intuitive way: what is paramount is that the procedures fulfill the condition. Such procedural representations of data is a style of programming often called message passing.

defmodule Pair do
  def cons(a, b) do
    fn
      0 -> a
      1 -> b
    end
  end

  def car(z) do
    z.(0)
  end

  def cdr(z) do
    z.(1)
  end
end

pair = Pair.cons(3, 4)
IO.puts(Pair.car(pair))
IO.puts(Pair.cdr(pair))