## Vocabulary

## Questions

## Notes

- Compound data: just like compound function, we enhance our expressive power of our language. And elevate the conceptual level at which we can design our programs.
- Glue data together: compound data glue data together to reduce the complexity of system.
- Data abstraction: modularity data can separate the part of function to deal with data and the part to deal with how the data be repesented.

1 | // repesent, and deal with rational number |

# 2.1 Introduction to Data Abstraction

## Vocabulary

- Data abstraction: compare to function abstraction, data abstraction hide the detail of how to compound it and expose what is

## Questions

## Notes

- 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.

# 2.1.1 Example: Arithmetic Operations for Rational Numbers

## Vocabulary

## Questions

## Notes

- Wishful thinking: assuming something that we have even we not yet implement them, then build something upon them.
- The step of abstract the arithmetic operations of rational:
- We operate base on data abstraction, so we first hide the detail of data abstraction(wishful thinking)
- We assume that we can construct a rational number, and can extracting its numerator and denominator.

1 | function make_rati(n, d) // make rational number which equal n / d |

1 | function add(a, b) { |

- use pair to implement the assuming functions make_rati, numer, denom.

1 | function pair(head, tail) // construct a pair with head and tail |

- Exercise 2.1
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// handle positive and negative, we only change make_rati

// since it is the only function that modify/create pair

function make_rati(n, d) {

const m = gcd(n, d)

if(n * d > 0) {

return pair(n / m, d / m)

} else if(n * d < 0) {

if(n < 0) {

return pair(n / m, d / m)

} else {

return pair(n / m, -d / m)

}

}

// 'd is zero needs handle'

}

// if don't use * to judge, can make some helper function

function make_rati(n, d) {

const m = gcd(n, d)

// abstract n and d, only use the sign to compute

// think about is it necessary to use n and d directly

// or we can extract the essence to compute

function sign(x) {

return x < 0

? -1

: x > 0

? 1

: 0

}

function abs(x) {

return x < 0

? -x

: x;

}

return pair(sign(n) * sign(d) * abs(n / m), abs(d / m))

}

# 2.1.2 Abstraction Barriers

## Vocabulary

## Questions

## Notes

In general, the underlying idea of data abstraction is to identify for each type of data object a basic set of operations in terms of which all manipulations of data objects of that type will be expressed, and then to use only those operations in manipulating the data.

The horizontal lines represent _abstraction barriers_ that isolate different "levels" of the system. The barriers will hide the implement details below it. All complex data can be repesent by some ways using primitive data. How to repesent data influnences the programs that operate it. But if we only modify the implementation that will not affect the programs build upon it. The data-abstraction methodology gives us a way to defer that decision without losing the ability to make progress on the rest of the system. (For example, fe no need to wait until the be api finished, fe can start develop whenever the api document(interface) is given).Exercise 2.2

1 | // from top to bottom, using data-abstraction barriers to construct the system |

- Exercise 2.3

1 | interface { |

# 2.1.3 What Is Meant by Data?

## Vocabulary

- Data: as defined by some collection of selectors and constructors, together with specified conditions that these functions must fulfill in order to be a valid representation.

## Questions

## Notes

- If one can obey the rules and implement the selectors and onstructors, it can use as the data. It should not matter how it implement.
- Message passing: use function represent data, and pass a message to get specify return.
- message passing pair

1 | // fulfill: z = pair(x, y) head(z) = x tail(z) = y |

- Exercise 2.4

1 | function tail(z) { |

- Exercise 2.5

1 | function pair(a, b) { |

- Exercise 2.6

1 | const zero = f => x => x |

# 2.1.4 Extended Exercise: Interval Arithmetic

## Vocabulary

## Questions

## Notes

- Exercise 2.7

1 | function make_interval(x, y) { |

- Exercise 2.8

1 | function sub_interval(x, y) { |

- Exercise 2.9

1 | // proof: width A + width B = width C, where C is A + B (interval) |

- Exercise 2.10

1 | function div_interval(x, y) { |

- Exercise 2.11

1 | function mul_interval(x, y) { |

- Exercise 2.12

1 | function make_center_percent(c, p) { |

- Exercise 2.13

1 | // a * b -> pa * pb |

If we only see two endpoints, some problems will become harder to solve. But if we change aspect to see data, it will be come eaiser.