1.1.8절에서 프로시저가 상위 프로시저 일부라면, 상위 프로시저가 일하는 절차를 요약해서 하위 프로시저 속에 감추는 것으로 볼 수 있다는 것을 알았다. 다른 의미로 보면, 프로시저 내용을 모르더라도 같은 동작을 하는 다른 프로시저가 있다면 부품처럼 맞바꿔 사용할 수 있다는 의미다. 요약한 프로시저를 사용하기 때문에, 프로시저에 절차를 표현해서 정의하는 하위 부분과 사용하는 상위 부분을 나누어 생각할 수 있다. 그 경계를 요약의 경계로 구분할 수 있다. 데이터에서 이와 같은 개념이 데이터 요약이다. 데이터도 마찬가지로 묶음 데이터를 만드는 부분과 사용하는 부분으로 구분할 수 있다.
데이터 요약 관점에서 프로그램을 작성할 때 복잡한 데이터는 요약한 데이터로 연산할 수 있어야 한다. 데이터에 조건을 달지 않아야 하고, 데이터를 사용하는 프로그램에도 드러내지 않아야 한다. 데이터를 만드는 부분과 사용하는 부분을 이어주는 인터페이스를 선택자selector와 구성자constructor 라고 부른다. 유리수 프로시저를 설계하면서 설명해보자.
분자와 분모로 유리수를 짜맞추는 연산 constructor와 유리수에서 분모와 분자를 골라내는 연산 selector를 다음 프로시저로 정의하자.
make_rational(n, d) 분자가 n이고 분모가 d인 유리수를 내놓는다.
number(x) 유리수 x의 분자를 내놓는다.
denominator(x) 유리수 x의 분모를 내놓는다.
여기 세 프로시저는 어떻게 정의했는지 몰라도 이 프로시저만 있으면, 아래와 같은 관계로 유리수 연산들을 만들 수 있다.
func add_rational(x: Rational, y: Rational) -> Rational {
return make_rational(n: number(r: x) * denominator(r: y) + number(r: y) * denominator(r: x),
d: denominator(r: x) * denominator(r: y))
}
func sub_rational(x: Rational, y: Rational) -> Rational {
return make_rational(n: number(r: x) * denominator(r: y) - number(r: y) * denominator(r: x),
d: denominator(r: x) * denominator(r: y))
}
func mul_rational(x: Rational, y: Rational) -> Rational {
return make_rational(n: number(r: x) * number(r: y) ,
d: denominator(r: x) * denominator(r: y))
}
func div_rational(x: Rational, y: Rational) -> Rational {
return make_rational(n: number(r: x) * denominator(r: y),
d: denominator(r: x) * number(r: y))
}
func equal_rational(x: Rational, y: Rational) -> Bool {
return number(r: x) * denominator(r: y) == number(r: y) * denominator(r: x)
}스킴Scheme에서는 데이터를 짝을 맞춰서 표현하기 위해서 쌍Pair이라는 데이터 구조를 사용한다. 스위프트에서 Pair 대신에 Tuple을 사용한다. 튜플에서 내부 값을 골라낼 때는 .0, .1 등을 사용한다.
let x = (1, 2)
x.0
> 1
x.1
> 2튜플에는 이름을 붙일 수도 있고, 연산하기 위해 전달할 수도 있다. 다른 튜플을 새로운 튜플로 묶을 수도 있다.
let x = (1, 2)
let y = (3, 4)
let z = (x, y)
z.0.0
> 3
z.1.0
> 1튜플은 엄밀히 말해서 쌍이 아니라 여러 값을 묶을 수도 있다.
let t = (1, 2, 3)
let q = (9, 10, 11, 12)복잡한 데이터 구조를 만들 때 튜플을 확장하면 리스트 구조를 갖춘 데이터를 만들 수 있다.
튜플을 활용해서 위에서 만든 유리수 시스템을 완성해보자.
typealias Rational = (Int, Int)
func make_rational(n: Int, d: Int) -> Rational {
return Rational(number: n, denominator: d)
}
func number(r: Rational) -> Int {
return r.0
}
func denominator(r: Rational) -> Int {
return r.1
}이렇게 Rational 이란 튜플을 새로운 타입 이름으로 별명typealias를 지정할 수 있다.
스위프트 튜플에서는 r.0 또는 r.1 순서 대신에 이름을 붙일 수도 있다.
typealias Rational = (number:Int, denominator:Int)
func make_rational(n: Int, d: Int) -> Rational {
return Rational(number: n, denominator: d)
}
func number(r: Rational) -> Int {
return r.number
}
func denominator(r: Rational) -> Int {
return r.denominator
}이제 계산 결과를 나타낼 때 분자 / 분모 차례로 유리수를 찍을 수도 있다.
func print_rational(x: Rational) {
print("\(number(r:x)) / \(denominator(r:x))")
}모든 시스템 프로시저를 만들었으니까, 제대로 돌아가는지 살펴보자.
let one_half = make_rational(n: 1, d: 2)
print_rational(x: one_half)
let one_third = make_rational(n: 1, d: 3)
print_rational(x: add_rational(x: one_half, y: one_third))
print_rational(x: mul_rational(x: one_half, y: one_third))
print_rational(x: add_rational(x: one_third, y: one_third))마지막 계산 결과는 6/9가 출력되고 기약분수가 아니다. 이 문제를 해결하려면 make_rational()을 고쳐야 한다. 1.2.5절에서 만든 gcd 프로시저를 써서, 분자와 분모를 최대공약수로 나누어서 기약분수로 만든다.
func make_rational(n: Int, d: Int) -> Rational {
let g = gcd(a: n, b: d)
return Rational(number: n / g, denominator: d / g)
}이제 print_rational(x: add_rational(x: one_third, y: one_third))를 실행하면 2/3 값이 출력된다. 다른 연산 프로시저는 고치지 않았고 단지 make_rational()만 고쳤다.
func sign(_ x: Int) -> Int {
if x < 0 {
return -1
}
else if x > 0 {
return 1
}
return 0
}
func make_rational(n: Int, d: Int) -> Rational {
let g = gcd(a: n, b: d)
return Rational(number: sign(n) * sign(d) * abs(n / g), denominator: abs(d / g))
}유리수 예제에서 부족한 부분을 살펴보자. make_rational()으로 데이터를 만들고, number()와 denominator()로 데이터를 골라내서 유리수 연산을 정의했다. 데이터를 요약하기 위해 바탕이 되는 생각은, 데이터 물체가 어떤 타입인지 결정할 연산이 무엇인가 고려해 보는 것이다. 이러한 기본 연산은 그 타입에 속하는 모든 물체를 표현할 수 있고, 딱 그 연산만으로 데이터를 계산할 수 있다.
유리수 시스템은 그림2.1처럼 생각할 수 있다. 그림에서 가로 선은 요약의 경계 abstraction barrier라고 한다. 이렇게 시스템을 구성하는 부품들은 저마다 다른 수준level에 위치한다. 각자 수준마다 데이터를 사용하는 상위 프로그램과 데이터를 구현하는 하위 프로그램이 생긴다. 경계에 있는 프로시저들은 요약의 경계를 연결해주는 인터페이스다.
데이터를 사용하는 프로그램에서는 데이터를 표현하는 방식이 바뀌면 프로그램도 함께 고쳐줘야 한다. 이렇게 경계를 나눠놓으면 프로그램을 관리하고 고치기가 쉬워진다. 데이터 표현에 영향을 받는 부분을 프로그램을 구성하는 부품의 일부로 제한하도록 설계해야 한다. 그렇지 않으면 대규모 프로그램을 작성할 때 크나큰 대가를 치른다.
앞에서 만든 유리수를 생성할 때부터 분자와 분모를 약분하지 않고, 만들어 놓은 유리수에서 분자와 분모를 꺼낼 때만 약분하도록 작성할 수도 있다.
func make_rational(n: Int, d: Int) -> Rational {
return Rational(number: n, denominator: d)
}
func number(r: Rational) -> Int {
let g = gcd(a: r.0, b: r.1)
return r.0 / g
}
func denominator(r: Rational) -> Int {
let g = gcd(a: r.0, b: r.1)
return r.1 / g
}유리수 분자와 분모를 가져오는 경우가 많은 프로그램이라면 이전처럼 처음 유리수를 생성할 때 gcd를 계산하는 것이 좋다. 그렇지 않다면 지금처럼 값을 가져갈 때 gcd 계산을 해도 된다. 여기서 주목할 것은 이렇게 데이터를 어떤 방식으로 가져오더라도, add_rational() 이나 sub_rational()은 바꿀 필요가 없다.
typealias Point = (x:Double, y:Double)
typealias Segment = (start:Point, end:Point)
func x_point(p: Point) -> Double {
return p.x
}
func y_point(p: Point) -> Double {
return p.y
}
func make_point(x: Double, y: Double) -> Point {
return Point(x: x, y: y)
}
func make_segment(start: Point, end: Point) -> Segment {
return Segment(start: start, end: end)
}
func start_segment(s: Segment) -> Point {
return s.start
}
func end_segment(s: Segment) -> Point {
return s.end
}
func average(a: Double, b: Double) -> Double {
return (a + b) / 2.0
}
func mid_point(x: Segment) -> Point {
let a = start_segment(s: x)
let b = end_segment(s: x)
return make_point(x: average(a: x_point(p: a), b: x_point(p: b)),
y: average(a: y_point(p: a), b: y_point(p: b)))
}첫번째 구현
typealias Rect = (bottomLeft: Point, topRight: Point)
func make_rect(bottomLeft: Point, topRight: Point) -> Rect {
return Rect(bottomLeft: bottomLeft, topRight: topRight)
}
func top_right(rect: Rect) -> Point {
return rect.topRight
}
func bottom_right(rect: Rect) -> Point {
return make_point(x: x_point(p: rect.topRight),
y: y_point(p: rect.bottomLeft))
}
func top_left(rect: Rect) -> Point {
return make_point(x: x_point(p: rect.bottomLeft),
y: y_point(p: rect.topRight))
}
func bottom_left(rect: Rect) -> Point {
return rect.bottomLeft
}
func width_rect(_ rect: Rect) -> Double {
return abs(x_point(p: bottom_left(rect: rect)) - x_point(p: bottom_right(rect: rect)))
}
func height_rect(_ rect: Rect) -> Double {
return abs(y_point(p: bottom_left(rect: rect)) - y_point(p: top_left(rect: rect)))
}
func area_rect(_ rect: Rect) -> Double {
return width_rect(rect) * height_rect(rect)
}
func preimeter_rect(_ rect: Rect) -> Double {
return 2 * (width_rect(rect) + height_rect(rect))
}두번째 구현
typealias Rect = (bottomLeft: Point, size: (width: Double, height: Double))
func make_rect(bottomLeft: Point, width: Double, height: Double) -> Rect {
return Rect(bottomLeft: bottomLeft, size: (width, height) )
}
func height_rect(_ rect: Rect) -> Double {
return rect.size.height
}
func width_rect(_ rect: Rect) -> Double {
return rect.size.width
}
func area_rect(_ rect: Rect) -> Double {
return width_rect(rect) * height_rect(rect)
}
func preimeter_rect(_ rect: Rect) -> Double {
return 2 * (width_rect(rect) + height_rect(rect))
}도대체 데이터data란 무엇을 의미하는가? 단지 연산으로 짜맞추거나 골라내는 것으로 설명하기에 부족하다.
유리수라는 데이터를 만드는 데 바탕이 되는 연산 make_rational, number, denomiator가 만족해야 할 조건은 (number x) / (denominator x) = n / d 뿐이다. 데이터는 이런 프로시저가 알맞은 데이터 표현을 만들어 내는지 따질 수 있는 조건까지 함께 정의해놓은 것이다.
C.A.R. Hoare가 제안한 요약한 모형(abstract model)법은 이미 정의된 데이터 타입을 빌려서 새로운 타입을 정의한다. 또 다른 방법으로 대수 명세법(algebraic specification)이 있는데 프로시저를 요약한 대수 체계 원소로 보고, 그 성질을 공리로 밝힌다. Liskov and Zilles 1975 논문을 참고하자.
앞에서 설명한 유리수 시스템을 돌아보자. 두 물체를 쌍으로 묶어서 튜플로 만들수 있다면, 튜플에서 다시 골라낼 수 있다는 점이다. 이 조건을 만족하도록 데이터 표현을 쓰지 않고 단지 cons, car, cdr 프로시저만 써서 정의할 수도 있다.
enum RationalError : Error {
case InvalidParameter
}
func cons(x: Int, y: Int) -> (Int) throws -> Int {
return { m in
if m == 0 { return x }
else if m == 1 { return y }
throw RationalError.InvalidParameter
}
}
func car(z: (Int) throws -> Int) throws -> Int {
return try z(0)
}
func cdr(z: (Int) throws -> Int) throws -> Int {
return try z(1)
}이렇게 데이터를 프로시저로 나타내면 그대로 데이터라고 생각하기는 어렵다. 그럼에도 이 프로시저를 위에서 밝힌 데이터 조건을 만족하는지 증명하면 아무런 문제가 되지 않는다. cons()가 내놓는 값이 클로저라는 것을 눈여겨보자. 내부에서 선언한 클로저를 리턴하는 데, 인자 하나를 받아서 그 값이 0이면 x를 1이면 y를 내놓는다. 데이터를 사용하도록 구현하는 것과 cons, car, cdr 같은 인터페이스만 구현해도 구분하지 못한다. 하지만 이렇게 데이터 구조를 사용하지 않는 프로시저로 표현한 것은 실제로 사용한다는 것은 아니다. 이런 방식으로 구현해도 튜플 대신 쌍을 구현할 수 있다는 것이다. 프로시저를 물체처럼 다룰 수 있으면, 합친 데이터를 나타내는 표현도 가능해진다. 데이터를 프로시저로 표현하는 기법을 메시지 패싱message passing이라고 한다.
pass
pass
프로시저로 쌍 데이터 구조를 표현할 수 있을 뿐만 아니라, 양의 정수를 표현할 수도 있다. 0과 1과 같은 동작도 프로시저와 연산만으로 표현할 수 있다.
이런 표현을 람다 계산법을 만들어 낸 알론조 처치의 이름을 따서 처치의 수 Church numeral라 부른다.
typealias fx = (Int) -> Int
typealias fn = (@escaping fx) -> fx
let zero = { (f : fx) in { (x : Int) in x }}
let one = { (f : @escaping fx) in { x in f(x) }}
let two = { (f : @escaping fx) in { x in f(f(x)) }}
func add(_ n : @escaping fn) -> fn {
return { (f : @escaping fx) in { x in n(f)(x) } }
}
func plus(_ n : @escaping fn, _ m : @escaping fn) -> fn {
return { (f : @escaping fx) in { x in n(f)(m(f)(x)) } }
}
let three = plus(one, two)
func church_to_number(_ c : @escaping fn) -> Int {
return c({ n in n + 1})(0)
}
church_to_number(three)
저장 값은 레지스터를 만드는 제조사가 공개한 허용 오차를 따른다. 6.8Ω 허용 오차 10% 레지스터를 구매했다면 실제 저항 값은 6.8 - 0.68 = 6.12에서 6.8 + 0.68 = 7.48 사이가 된다. 이런 방식으로 6.8Ω 10% 저항과 4.7Ω 5% 저항을 병렬로 연결하면 2.58Ω에서 2.97Ω 사이가 된다.
부정확한 양을 나타낼 수 있는 구간inverval 값을 계산할 수 있는 시스템을 설계해보자. 구간 값은 결과 값의 범위를 나타낸다. 구간 값을 더하고, 빼고, 곱하고, 나눈 결과는 다시 구간 값이 된다.
우선 구간을 표현하며 요약하는 물체가 있다고 가정하자. 구간 값은 하한과 상한 값을 두 끝점으로 나타낸다. 그리고 구간을 이루는 양 끝점을 받아서 구간 데이터를 만드는 make_interval가 이미 있다고 가정하자.
이런 가정하에 구간 값을 더하는 프로시저를 만들어보자. 이 프로시저는 두 구간 값에서 하한끼리 더하고, 상한끼리 더한 값을 새로운 하한과 상한으로 하는 구간을 만들면 된다.
func add_interval(x: Interval, y: Interval) -> Interval {
return make_interval(lower: x.lower + y.lower , upper: x.upper + y.upper)
}구간 값을 곱하는 프로시저도 만들어 보자. 이 프로시저는 다음과 같이 두 구간의 상한과 하한을 조합해서 곱하는 모든 경우를 계산해서 가장 큰 값을 상한으로, 가장 작은 값을 하한으로 내놓아야 한다.
func mul_interval(x: Interval, y: Interval) -> Interval {
let p1 = x.lower * y.lower
let p2 = x.lower * y.upper
let p3 = x.upper * y.lower
let p4 = x.upper * y.upper
return make_interval(lower: min(p1, p2, p3, p4), upper: max(p1, p2, p3, p4))
}구간 값을 나누는 프로시저를 만들어보자. 두번 째 인자로 받은 구간에 대한 역수를 구해서 첫 번째 인자로 받은 구간과 곱해야 한다.
func div_interval(x: Interval, y: Interval) -> Interval {
return mul_interval(x: x, y: make_interval(lower: 1.0 / y.upper, upper: 1.0 / y.lower))
}typealias Interval = (lower:Double, upper:Double)로 정의한 Interval 튜플에서 upper와 lower를 구분하는 함수를 만들면 다음과 같다.
func upper(_ x: Interval) -> Double {
return x.upper
}
func lower(_ x: Interval) -> Double {
return x.lower
}func sub_interval(x: Interval, y: Interval) -> Interval {
return make_interval(lower: lower(x) - lower(y) , upper: upper(x) - upper(y))
}구간 값의 폭width는 구간의 상한에서 하한을 빼고 반으로 나눈 값을 말한다. 폭은 구간 값이 정확하지 않은 정도를 나타낸다. 구간 i에 대해 폭 W(i), 하한값 L(i), 상한값 U(i)이라고 가정하면 다음과 같다.
구간에 0이 들어있는 경우 문제가 될 수 있으니까 개선해보자. 0이 포함된 경우는 Interval로 계산할 수가 없기 때문에 아무런 값이 없다는 의미로 nil을 리턴한다.
func div_interval(x: Interval, y: Interval) -> Interval? {
if lower(y) <= 0 && upper(y) >= 0 {
return nil
}
return mul_interval(x: x, y: make_interval(lower: 1.0 / y.upper, upper: 1.0 / y.lower))
}구간 양 끝점의 부호가 어떻게 되는지 검사하면, mul_interval 프로시저에서 계산하는 방법이 아홉 가지로 나눌 수 있다. 그 중에서 두 번 곱셈하는 경우는 한 번 뿐이 없다. 이렇게 mul_interval을 개선하면 다음과 같다.
func positive(n: Double) -> Bool {
return n >= 0
}
func trouble_interval(xl: Double, xu: Double, yl: Double, yu: Double) -> Interval {
let p1 = xl * yl
let p2 = xl * yu
let p3 = xu * yl
let p4 = xu * yu
return make_interval(lower: min(p1, p2, p3, p4), upper: max(p1, p2, p3, p4))
}
func mul_interval(x: Interval, y: Interval) -> Interval? {
switch (positive(x.lower), positive(x.upper), positive(y.lower), positive(y.upper)) {
case (true, true, true, true):
return make_interval(lower: x.lower * y.lower, upper: x.upper * y.upper)
case (true, true, false, true):
return make_interval(lower: x.upper * y.lower, upper: x.upper * y.upper)
case (true, true, false, false):
return make_interval(lower: x.upper * y.lower, upper: x.lower * y.upper)
case (false, true, true, true):
return make_interval(lower: x.lower * y.upper, upper: x.upper * y.upper)
case (false, true, false, false):
return make_interval(lower: x.upper * y.lower, upper: x.lower * y.upper)
case (false, false, true, true):
return make_interval(lower: x.lower * y.upper, upper: x.upper * y.lower)
case (false, false, false, true):
return make_interval(lower: x.lower * y.upper, upper: x.lower * y.lower)
case (false, false, false, false):
return make_interval(lower: x.upper * y.upper, upper: x.lower * y.lower)
case (false, true, false, true):
return trouble_interval(xl: x.lower, xu: x.upper, yl: y.lower, yu: y.upper)
default:
return nil
}
}이렇게 해서 프로시저를 고친 다음 이 프로그램이 필요한 사람에게 보여줬더니, 구간 가운데 값과 허용 오차로 나타낸 수를 다루는 프로그램이 필요하다고 한다. 구간을 [3.35, 3.65]로 나타내는 게 아니라 3.5 ± 0.15 형태로 표시해야 한다. 그래서 다음과 같이 center와 width를 다루는 새로운 프로시저를 추가했다.
func make_interval(center: Double, width: Double) -> Interval {
return make_interval(lower: center - width, upper: center + width)
}
func center(_ i: Interval) -> Double {
return (i.lower + i.upper) / 2
}
func width(_ i: Interval) -> Double {
return (i.upper - i.lower) / 2
}구간 가운데 값과 허용 오차를 인자로 받아서 구간 값을 만드는 make(center: Double, percent: Double) 프로시저와 percent 프로시저를 구현한다.
func make(center: Double, percent: Double) -> Interval {
let width = center * (percent / 100)
return make_interval(center: center, width: width)
}
func percent(_ i: Interval) -> Double {
return (width(i) / center(i)) * 100
}증명은 패스
병렬 저항을 구할 때 대수적으로 같은 결과를 나타내는 공식이 두 개가 있어서 각각 프로그램으로 구현했다.
func par1(r1: Interval, r2: Interval) -> Interval? {
return div_interval(x: mul_interval(x: r1, y: r2), y: add_interval(x: r1, y: r2))
}
func par2(r1: Interval, r2: Interval) -> Interval? {
let one = make_interval(lower: 1, upper: 1)
return div_interval(x: one,
y: add_interval(x: div_interval(x: one, y: r1)!,
y: div_interval(x: one, y: r2)!))
}그런데 이렇게 구현하고 보니, 계산 결과값이 같지 않았다.
두 계산 방식의 결과값이 다른 문제를 해결하려면 어떻게 해야하나? 구간 값 A, B가 있고 A/A 와 A/B를 구할 때 동작하는 방식을 확인해봐야 한다. 특히 A/A를 계산한 구간 값은 길이는 0이고 정확하게 1이어야 한다. 그렇지 않으면 여러 번 계산이 반복될 수록 오차가 누적되서 최종 결과값이 달라진다.
구간을 계산할 때 부정확한 수를 담은 변수를 되풀이해서 사용하지 않는 공식이 오차 범위를 더 줄인다고 한다. 위에서 병렬 저항을 계산하는 par2가 par1보다 나은 프로그램이라고 할 수 있나?
이런 경우는 의존성 문제 라고 부르는 데, par2가 매개 변수 R1과 R2를 더 적게 사용한다.
구간 산술 연산에서 의존성 문제를 해결하기 위해서는 선형 다항식 형태로 테일러 급수 방식으로 계산할 수 있다. 하지만 쉽지 않은 문제다.
다음 2.2 계층 구조 데이터와 닫힘 성질 Hierarchical Data and the Closure Property