그래프 만들기: shared

shared는 상호 참조하는(cyclic) 데이터 구조를 만들 수 있게 해주는 구문 폼입니다. letrec과 비슷하지만, 구조화된 데이터의 생성을 특별히 인식해 그래프 형태의 불변 데이터도 만들 수 있습니다.

출처: Racket Reference

본문

(require racket/shared) ; package: base

이 섹션에 문서화된 바인딩은 racket/shared와 racket 라이브러리가 제공하지만, racket/base는 제공하지 않습니다.

syntax

(shared ([id expr] ...) body ...+)

expr에 따라 공유 구조를 갖는 id들을 바인딩한 다음 body들을 평가하고, 마지막 표현식의 결과를 반환합니다.

shared 폼은 letrec과 비슷합니다. 다만 (부분 매크로 전개 후) 특별한 형태의 expr을 인식해 그래프 구조 데이터를 만들며, 그에 대응하는 letrec은 대신 use-before-initialization 오류를 만들 것입니다.

각 expr(부분 전개 후)은 다음 shared-expr 문법에 맞춰 대조(match)되는데, 한 생성 규칙에서 더 앞의 변형이 더 뒤의 변형보다 우선합니다:

shared-expr      = shell-expr
                 | plain-expr

shell-expr       = (cons in-immutable-expr in-immutable-expr)
                 | (list in-immutable-expr ...)
                 | (list* in-immutable-expr ...)
                 | (append early-expr ... in-immutable-expr)
                 | (vector-immutable in-immutable-expr ...)
                 | (box-immutable in-immutable-expr)
                 | (mcons patchable-expr patchable-expr)
                 | (vector patchable-expr ...)
                 | (box patchable-expr)
                 | (prefix:make-id patchable-expr ...)

in-immutable-expr = shell-id
                  | shell-expr
                  | early-expr

shell-id          = id

patchable-expr    = expr

early-expr        = expr

plain-expr        = expr

위의 prefix:make-id 식별자는 세 종류의 참조와 일치합니다. 첫 번째 종류는 이름 중간에 make-가 들어 있고 prefix:id가 전체 변이자(mutator) 바인딩 집합을 가진 구조 정보(structure information)에 트랜스포머 바인딩을 갖는 모든 바인딩입니다(Structure Type Transformer Binding 참고). 두 번째 종류는 그 자체로 구조 정보에 트랜스포머 바인딩을 가진 식별자입니다. 세 번째 종류는 값이 구조 정보에 트랜스포머 바인딩을 가진 식별자인 'constructor-for 구문 속성을 가진 식별자입니다. 한편 shell-id는 반드시 shared 폼이 shell-expr에 바인딩한 id들 중 하나여야 합니다.

shared 폼의 expr들이 shared-expr으로 분석될 때(우선 순위를 위해 변형들의 순서를 고려), early-expr로 분석된 하위 표현식들은 shared 폼이 평가될 때 먼저 평가됩니다. 이러한 표현식들 사이에서는 shared 폼 안에 나타나는 순서대로 평가됩니다. 그러나 shared가 바인딩한 id에 대한 어떤 참조도 use-before-initialization 오류를 만들며, shared 폼 안에서 해당 id의 바인딩이 대응하는 early-expr보다 앞에 나타난다 해도 마찬가지입니다.

그 다음으로 shell-id와 shell-expr(patchable-expr과 early-expr 하위 표현식은 제외)이 사실상 평가됩니다:

shell-id 참조는 body 안에서 해당 id가 만들어낼 값과 같은 값을 만듭니다. 단 그 id가 set!으로 절대 변이되지 않는다고 가정합니다. shell-id 참조에 대한 이 특별한 처리는 shared가 순환 데이터(불변 순환 데이터 포함)의 생성을 지원하는 한 방식입니다.
(mcons patchable-expr patchable-expr), (vector patchable-expr ...), (box patchable-expr), (prefix:make-id patchable-expr ...) 형태의 shell-expr은 내용 위치가 undefined로 초기화된 변이 가능한 값을 만듭니다. 각 내용 위치는 뒤에서 대응하는 patchable-expr 표현식이 평가된 후에 패치(즉 갱신)됩니다.

그 다음에 plain-expr들이 letrec처럼 평가됩니다. 여기서 id 참조는, 그 id 바인딩의 오른쪽이 평가되기 전에 평가된다면 exn:fail:contract:variable을 발생시킵니다.

마지막으로, patchable-expr들이 평가되고 그 값들이 shell-expr 결과의 undefined들을 대체합니다. 이 시점에서는 모든 id가 바인딩되어 있으므로, patchable-expr은 데이터 순환(단, 변이를 통해 만들 수 있는 순환만)을 만들 수 있습니다.

예시:

> (shared ([a (cons 1 a)])
    a)

#0='(1 . #0#)
> (shared ([a (cons 1 b)]
           [b (cons 2 a)])
    a)

#0='(1 2 . #0#)
> (shared ([a (cons 1 b)]
           [b 7])
    a)

'(1 . 7)
> (shared ([a a]) ; no indirection...
    a)

a: undefined;

 cannot use before initialization
> (shared ([a (cons 1 b)] ; b is early...
           [b a])
    a)

a: undefined;

 cannot use before initialization
> (shared ([a (mcons 1 b)] ; b is patchable...
           [b a])
    a)

#0=(mcons 1 #0#)
> (shared ([a (vector b b b)]
           [b (box 1)])
    (set-box! b 5)
    a)

'#(#&5 #&5 #&5)
> (shared ([a (box b)]
           [b (vector (unbox a)   ; unbox after a is patched
                      (unbox c))] ; unbox before c is patched
           [c (box b)])
    b)

#0='#(#0# #<undefined>)

더 알아보기

letrec 관련 구문 폼
Structure Type Transformer Binding 관련 문서
불변 쌍, 불변 벡터, 불변 박스 관련 자료