자바스크립트로 배우는 SICP - 21. 테이블 그리고 디지털 회로 시뮬레이터 구현하기

테이블을 도식화하고 리스트와 쌍 자료구조로 표현해보기! 그리고 디지털 회로 시뮬레이터 추상화해보기!

2023-11-15 | 독서 | 12min

오늘은 테이블을 리스트로 구현하는 방법과 디지털 회로 시뮬레이터를 구현하는 방법에 대한 내용이었다. 서로 약간 다른 섹션에 속하기에 나누어서 다뤄보겠다!

테이블을 리스트로

흔히 우리가 아는 테이블은 키 값과 그에 대응하는 레코드 값이 짝지어져 있는 것으로 알고 있다. 이를 리스트로 구현할 수는 없을까? 한가지 예시를 생각해보자.

a: 1
b: 2
c: 3

위와 같은 레코드들은 어떻게 표현할 수 있을까? 우선 이를 앞서 다뤘던 상자-포인터 표기법 을 이용해 표시하면 다음과 같다!

우선 어떤 테이블이던 간에 헤드는 항상 “*table*” 이라고 가정하자! 이 그림은 레코드들을 테이블에서 목록 구조로 표현한 것이다!

여기에서 a 라는 키 값에 대응하는 값인 1 을 얻기 위해서는 head 의 head 를 확인하여 해당 키 값이 a 인지 확인하는 과정을 거쳐야 한다! 이러한 키 값을 확인하는 함수를 assoc 함수라고 하면 이는 다음과 같이 구현될 것이다!

function assoc(key, records) {
    return is_null(records)
           ? undefined
           : equal(key, head(head(records)))
           ? head(records)
           : assoc(key, tail(records));
}

코드의 내용은 간단하다! 레코드의 목록을 받아 레코드가 비어있지 않다면, 해당 레코드의 head 의 head 값이 key 값과 동일한지 equal 을 통해 확인하여(즉, key 값이 헤드인 레코드인지 확인하는 작업이다) 해당 키 값이 헤드인 레코드를 반환하도록 한다! 만약 키 값이 존재하지 않는다면, 재귀적으로 tail 에 대해서도 assoc 과정을 진행한다!

이 함수를 이용하면 특정 키 값을 가지고서 테이블의 레코드 값에 접근하는 lookup 함수를 구현할 수 있다. 이는 다음과 같다!

function lookup(key, table) {
    const record = assoc(key, tail(table));
    return is_undefined(record)
           ? undefined
           : tail(record);
}

매개변수로 키 값을 받아 assoc 함수로 테이블에 키 값에 대응하는 레코드를 선별하여 비어있다면 undefined 를, 아님 tail 값을 반환한다!

2차원 테이블은?

앞서 보았던 예시는 1차원 테이블 한정적이었다. 그럼 2차원 테이블은 어떻게 구현할까?

"math":
    "+":  43
    "-":  45
    "*":  42
"letters":
    "a":  97
    "b":  98

위와 같은 상황이라고 해보자! 이를 도식화하면 아래와 같을 것이다!

위를 이용하여 lookup 함수를 구현한다면 어떤 방식을 이용하면 될까?

단순하게, 키 값을 비교하는 과정을 한번 더 하면 된다. 우선 깊이 1인 키 값들에 대해서 존재 여부를 확인하고 없다면, 깊이가 2인 키 값들을 비교하면 된다! 코드는 다음과 같다.

function lookup(key_1, key_2, table) {
    const subtable = assoc(key_1, tail(table));
    if (is_undefined(subtable)) {
        return undefined;
    } else {
        const record = assoc(key_2, tail(subtable));
        return is_undefined(record)
               ? undefined
               : tail(record);
    }
}

이전에 assoc 함수가 키 값에 대응하는 레코드를 돌려주는 역할을 했었다. 이를 이용하여 매개 변수로 받은 첫 키 값을 이용하여 해당 키 값에 대응하는 레코드가 있는지 확인하는 과정을 거치고 있을 경우, 해당 레코드를 대상으로 다시 assoc 함수를 이용하여 두 번째 키 값에 대응하는 레코드가 있는 지를 확인한다!

이제 멘탈 모델이 세워졌으니 insert 하는 함수는 그리 어렵지 않을 것이다! 우선 코드부터 보자.

function insert(key_1, key_2, value, table) {
    const subtable = assoc(key_1, tail(table));
    if (is_undefined(subtable)) {
        set_tail(table, pair(list(key_1, pair(key_2, value)), tail(table)));
    } else {
        const record = assoc(key_2, tail(table));
        if (is_undefined(record)) {
            set_tail(subtable, pair(pair(key_2, value), tail(subtable)));
        } else {
            set_tail(record, value);
        }
    }
    return "ok";
}

역시 두 개의 키 값을 받는다. 그리고 assoc 으로 첫 키 값에 대응하는 레코드가 있는 지 확인하는 과정까지 동일하다.

만약, 레코드가 없을 경우 새롭게 추가해야 하므로, 현재 table의 tail에 매개변수로 받은 레코드를 쌍 구조로 만들고 추가하면 된다.

그리고 첫 키 값에 대응하는 레코드를 찾았다면, 해당 레코드에서 다시 두 번째 키 값에 대해 쌍 구조를 만들고 추가하는 과정을 거치면 된다!

프로그램이 커지면서 여러 테이블을 이용할 상황이 발생했다고 생각해보자! 이런 경우에는 매번 insert 나 lookup 같은 함수들을 구현하고 있을 수는 없을 것이다. 그렇기에 이를 make_table 로 테이블을 만든다고 할 때, 해당 함수 로직 내에 구현해두면 make_table 을 이용하는 어떤 테이블이든 해당 테이블의 상태를 지역 상태로써 관리할 수 있을 것이다!

논리회로 시뮬레이터

이제 디지털 회로 시뮬레이션을 구현해보자! 갑자기 웬 디지털 회로이냐?라는 생각이지만은, 디지털 회로 또한 개별적인 요소들의 모임이 하나의 복잡한 연산을 수행하는 회로로써 역할을 하기에 추상화의 적용이 매우 중요하다고 볼 수 있다!

디지털 회로 시뮬레이션은 보통 사건 주도적 시뮬레이션 또는 이벤트 주도적 시뮬레이션 이라고 부른다. 즉, 하나의 사건 또는 이벤트가 다른 사건들을 촉발하는 방식으로 이뤄진다는 것이다.

디지털 회로를 구성하는 대표적인 세 개의 게이트들이 있다!(짐작이 갈 것이다…!)

바로 인버터 , AND 게이트 , OR 게이트 이다!

이들을 조합하면 흔히 하는 덧셈 연산을 수행하는 반가산기를 만들 수 있다는 사실을 알 것이다! (자세한 내용은 여기를 참고하자)

반가산기

반가산기 그림으로 표현하면 아래와 같다.

그럼 이를 어떻게 코드로 표현하고 시뮬레이션을 진행할까?

우선 A, B, C, D, E, S 라는 지점들을 정의해야 한다. 그리고 각 지점들을 연결하는데에 있어 해당 연산이 인버터/AND/OR 의 연산들 중 하나이므로, 지점들을 매개변수로 받아 이어주는 역할을 수행하는 함수들을 정의해줘야 할 것이다. 이를 코드로 표현하면 다음과 같다.

const a = make_wire();
const b = make_wire();
const c = make_wire();
const d = make_wire();
const e = make_wire();
const s = make_wire();

이렇게 만든 각 지점들에 대한 연산을 수행하는 함수들은 다음과 같이 만들 수 있을 것이다.

or_gate(a, b, c); // a와 b에 or 연산의 결과가 c로
and_gate(a, b, c); // a와 b에 and 연산의 결과가 c로
inverter(c, d); // c의 인버터 연산의 결과가 d로

그럼 이제 문제는 매우 간단해진다! 반가산기를 위의 함수들을 이용하여 구성하면 다음과 같을 것이다!

function half_adder(a, b, s, c) {
    const d = make_wire();
    const e = make_wire();
    or_gate(a, b, d);
    and_gate(a, b, c);
    inverter(c, e);
    and_gate(d, e, s);
    return "ok";
}

우선 반가산기의 내부의 상태로 d와 e를 만든다. 각 지점들은 최종 연산 결과 상태까지로의 경유지 역할을 할 것이다. 그리고 도식화된 그림의 방법대로 or, and, inverter 단계를 적용하고 ok를 반환하면 끝!

전가산기

반가산기가 두 개 있으면 전가산기를 만들 수 있다! 전가산기를 도식화한 그림은 다음과 같다!

그럼 앞서 구현한 half_adder 를 이용하여 코드로 구현하면 다음과 같을 것이다.

function full_adder(a, b, c_in, sum, c_out) {
    const s = make_wire();
    const c1 = make_wire();
    const c2 = make_wire();
    half_adder(b, c_in, s, c1);
    half_adder(a, s, sum, c2);
    or_gate(c1, c2, c_out);
    return "ok";
}

전가산기의 중간 상태로는 반가산기와 반가산기 사이, 그리고 반가산기와 or 게이트 사이의 두 지점들이 있기에 이들에 대한 지역 상태를 만들어준다.

그리고 해당 경유지를 이용하여 그림대로 half_adder 를 두 번 적용하고 or 게이트까지 적용하면 최종 결과를 얻을 수 있다!

오늘은 여기까지! 크게는 테이블과 디지털 회로 시뮬레이션을 구현해보는 내용에 대해서 알아보았다! 생각보다 내용이 까다롭지만, 찬찬히 읽어보니 잘 읽혔다! 특히나 반가산기와 전가산기를 구현하는 코드는 생각해보지도 않았던 부분이라 너무나 신선하고 좋았던 추상화의 예시였다! 쨋든 오늘도 너무나 알찼다! 😆