일반적으로 유용한 RPython 모듈

Contents

• 일반적으로 유용한 RPython 모듈
  • listsort
  • nonconst
  • objectmodel
  • rarithmetic
  • rbigint
  • rrandom
  • rsocket
  • rstrategies
  • streamio
  • 언롤(unroll)
  • rsre
  • 파싱
  • 정규 표현식
  • EBNF
  • 파스 트리
    • 방문자(Visitors)
  • 트리 변환
    • [symbol_1 symbol_2 … symbol_n]
    • <symbol>
    • >nonterminal_1 nonterminal_2 … nonterminal_n<
  • EBNF 문법 형식의 확장
  • 전체 예제

이 페이지는 rpython/rlib의 일부 모듈을 나열하며, 각 모듈을 어떤 용도로 사용할 수 있는지에 대한 힌트도 함께 제공합니다. 여기의 모듈들은 RPython 프로그램에 유용한 일반적인 라이브러리를 구성합니다(표준 라이브러리 모듈 대부분이 RPython이 아니기 때문입니다). 이 모듈들 대부분은 아직 다소 미완성 상태이며, 언젠가 변경될 가능성이 있습니다. 보통 모듈을 어떻게 사용하는지 감을 잡으려면 rpython/rlib/test의 테스트를 살펴보는 것이 유용합니다.

listsort

timsort 정렬 알고리즘의 구현은 rpython/rlib/listsort.py 모듈에 들어 있습니다(리스트의 sort 메서드는 RPython이 아닙니다). 이를 사용하려면 MySort = listsort.make_timsort_class(lt=my_comparison_func)를 호출하여 (전역적으로) 하나의 클래스를 만드십시오. 다른 선택적 인자도 있지만, 보통은 lt=...로 리스트에 있는 두 객체를 비교하는 함수를 전달합니다. 리스트의 “타입”과 비교 함수마다 하나의 클래스가 필요합니다.

MySort의 생성자는 인자로 리스트를 받으며, 이 리스트는 MySort 인스턴스의 sort 메서드가 호출될 때 제자리에서 정렬됩니다.

nonconst

주로 테스트에서 유용하게 쓰이는 모듈이 rpython/rlib/nonconst.py입니다. 상당한 상수 폴딩(constant folding)을 수행하는 것이 flow graph builder와 annotator인데, 이는 테스트에서 때때로 바람직하지 않습니다. 특정 값에 대한 상수 폴딩(constant folding)을 방지하려면 NonConst 클래스를 사용하십시오. NonConst의 생성자는 임의의 값을 받습니다. 어노테이션 중에는 NonConst의 인스턴스가 그 값처럼 동작하지만, 상수 접기는 일어나지 않습니다.

objectmodel

다양한 기능이 뒤섞인 잡동사니 모듈이 바로 rpython/rlib/objectmodel.py입니다. 그중에서 더 유용한 것들은 다음과 같습니다:

ComputedIntSymbolic:

어노테이터는 ComputedIntSymbolic의 인스턴스를 값을 알 수 없는 정수처럼 취급합니다. 값은 인자가 없는 함수(클래스의 생성자에 전달되어야 함)에 의해 결정됩니다. 백엔드가 코드를 생성할 때, 값을 결정하기 위해 그 함수가 호출됩니다.

CDefinedIntSymbolic:

CDefinedIntSymbolic의 인스턴스도 애노테이터(annotator)에 의해 값을 알 수 없는 정수처럼 취급됩니다. C 코드가 생성될 때 이들은 심볼릭(symbolic)의 속성 expr로 표현되며, 이는 생성자의 첫 번째 인자이기도 합니다.

r_dict:

RPython의 dict와 유사한 객체입니다. r_dict의 생성자는 딕셔너리의 항목을 비교하고 해싱하는 데 사용되는 두 함수 key_eq와 key_hash를 받습니다.

instantiate(cls):

__init__을 호출하지 않고 클래스 cls를 인스턴스화합니다.

we_are_translated():

이 함수는 CPython 위에서 실행될 때 False를 반환하지만, 애너테이터(annotator)는 그 반환값을 True로 여깁니다. 따라서 이는 번역(translation) 이후와는 다르게 CPython 위에서 다른 동작을 하도록 사용할 수 있습니다. 이는 매우 드물게 사용해야 합니다(주로 최적화나 디버그 코드에서).

cast_object_to_weakaddress(obj):

obj에 대한 일종의 “약한 참조(weak reference)”를 반환하지만, 어떠한 편의성도 제공하지 않습니다. 반환되는 약한 주소는 객체가 소멸되어도 무효화되지 않으므로, 객체가 언제 소멸되는지는 직접 파악해야 합니다. 극히 주의해서 사용하십시오.

cast_weakadress_to_object(obj):

이전 함수의 역함수입니다. 객체가 소멸했다면 세그폴트가 발생합니다.

UnboxedValue:

이것은 정확히 하나의 정수 필드를 가지는 클래스의 기반 클래스로 사용해야 하는 클래스입니다. 이 클래스는 정확히 하나의 항목이 정의된 __slots__을 가져야 합니다. 번역(translation) 이후에는 이 클래스의 인스턴스가 할당되지 않고, 최하위 비트가 설정된 포인터, 즉 태그된 포인터*로 표현됩니다.

rarithmetic

일반 Python 코드와 RPython 코드에서 산술 코드의 동작에 나타나는 작은 차이를 처리하는 기능은 rpython/rlib/rarithmetic.py 모듈에 들어 있습니다. 그중 대부분은 이미 RPython description에서 설명되어 있습니다.

rbigint

모듈 rpython/rlib/rbigint.py는 Python long 타입(RPython 자체에서는 지원되지 않음)의 완전한 RPython 구현을 담고 있습니다. rbigint 클래스가 그 구현을 담고 있습니다. rbigint 인스턴스를 생성하려면 정적 메서드 fromint, frombool, fromfloat, fromdecimalstr를 사용하십시오. 다른 타입으로 다시 변환하려면 메서드 toint, tobool, touint, tofloat를 사용하십시오. RPython은 연산자 오버로딩을 지원하지 않으므로, 일반적으로 앞뒤에 “__”가 붙는 rbigint의 모든 특수 메서드는 가독성을 높이기 위해 이 밑줄이 생략되어 있습니다(따라서 두 rbigint 인스턴스를 더할 때 a.add(b)를 사용할 수 있습니다).

rrandom

메르센 트위스터(mersenne twister) 난수 생성기의 구현은 rpython/rlib/rrandom.py 모듈에 포함되어 있습니다. 이 모듈은 Random이라는 하나의 클래스를 포함하고 있으며, 이 클래스에는 무엇보다도 0.0과 1.0 사이의 의사 난수 부동소수점 수를 반환하는 random 메서드가 있습니다.

rsocket

소켓 표준 라이브러리의 기능을 약간 다른 인터페이스로 구현한 RPython 코드가 rpython/rlib/rsocket.py 모듈에 들어 있습니다. Python 소켓 API의 어려움은 주소가 “타입이 명확한(well-typed)” 객체가 아니라는 점입니다: 주소 체계(address family)에 따라 튜플이거나 문자열이거나 그 밖의 형태일 수 있는데, 이는 RPython에 적합하지 않습니다. 대신 rsocket은 전형적인 정적 객체지향 프로그래밍 스타일로 Address 클래스들의 계층 구조를 담고 있습니다.

rstrategies

RPython VM들에서 저장소 전략(storage strategy)을 구현하기 위한 라이브러리는 rpython/rlib/rstrategies 모듈에 들어 있습니다. 이 라이브러리는 언어 독립적이며 확장 가능합니다. 더 자세한 내용과 예제는 rstrategies documentation에서 확인할 수 있습니다.

streamio

RPython 스트림 I/O 구현은 rpython/rlib/streamio.py에 들어 있으며, 이는 Guido van Rossum이 Python 3000에서 예정된 새로운 파일 구현의 프로토타입으로서 CPython 샌드박스에 sio.py로 작성을 시작한 것입니다.

언롤(unroll)

무엇보다도, rpython/rlib/unroll.py 모듈은 반복자(iterator)를 감싸는 함수 unrolling_iterable을 포함합니다. RPython 코드에서 반복자에 대해 루프를 도는 것은 결과로 만들어지는 흐름 그래프(flow graph)에 루프를 만들어내지 않고, 대신 그 루프를 펼칩니다.

rsre

PyPy에서 사용하는 정규 표현식의 구현입니다. 다른 언어에서 재사용하기 어렵다는 점에 유의하십시오: Python에서 정규 표현식은 먼저 표준 라이브러리의 순수 Python 코드에 의해 바이트코드 형식으로 컴파일됩니다. 이 저수준 모듈은 이 바이트코드 형식만 이해합니다. 완전한 Python 인터프리터 없이는 정규식 구문을 바이트코드 형식으로 변환할 수 없습니다. (정적 정규식만 있는 제한된 사용 사례를 위한 편법이 있습니다: 이런 경우 번역(translation) 중에 미리 컴파일할 수 있습니다. 또는 런타임에 정규식을 변환하기 위해서만 Python 하위 프로세스를 실행하는 방법을 상상해 볼 수도 있습니다…)

파싱

RPython에서 토크나이저와 파서를 생성하기 위한 rpython/rlib/parsing/ 모듈은 아직 개발 중인 모듈입니다. 이 모듈은 여전히 매우 실험적이며, 약간 비표준적인 방식이기는 하지만 실제로는 Prolog interpreter에서만 사용되고 있습니다. 토크나이저/문법을 지정하는 가장 쉬운 방법은 정규 표현식과 간단한 EBNF 형식을 사용하여 작성하는 것입니다.

정규 표현식은 유한 오토마톤을 사용하여 구현됩니다. 파싱 엔진은 packrat parsing을 사용하는데, 이는 O(n) 파싱 시간을 가지면서도 LL(n) 및 LR(n) 문법보다 더 강력합니다.

정규 표현식

정규 표현식 문법은 대부분 re 모듈 문법의 부분집합입니다. 참고: 이는 rlib.rsre와 다릅니다. 기본적으로 특수 문자가 아닌 문자는 자기 자신과 일치합니다. 정규 표현식을 연결하면, 그 결과는 각각의 정규 표현식이 일치시키는 문자열들의 연결과 일치합니다.

|

R|S는 R과 매치되거나 S와 매치되는 어느 문자열이든 매치합니다.

*

R*는 R의 0회 이상 반복과 일치합니다.

+

R+는 R의 1회 이상 반복과 일치합니다.

?

R?는 R의 0회 또는 1회 반복과 일치합니다.

(...)

괄호는 정규 표현식을 그룹화하는 데 사용할 수 있습니다(단, Python의 re 모듈과 달리 이 그룹의 내용을 나중에 다시 매칭할 수는 없다는 점에 유의하십시오).

{m}

R{m}은 R을 정확히 m번 반복한 것과 일치합니다.

{m, n}

R{m, n}은 R이 m회에서 n회까지(m과 n을 포함) 반복되는 것과 일치합니다.

[]

문자 집합과 일치합니다. 일치시킬 문자들을 순서대로 나열할 수 있습니다. -를 사용하여 문자 범위를 지정할 수 있습니다. 예를 들어 [ac-eg]는 문자 a, c, d, e, g와 일치합니다. ^로 시작하면 전체 집합을 반전시킬 수 있습니다. 따라서 [^a]는 a를 제외한 모든 문자와 일치합니다.

정규 표현식을 파싱하고 이에 대한 매처를 얻으려면, rpython.rlib.parsing.regexparse 모듈의 make_runner(s) 함수를 사용할 수 있습니다. 이 함수는 input이 문자열과 일치하는지 여부에 따라 True 또는 False를 반환하는 recognize(input) 메서드를 가진 객체를 반환합니다.

EBNF

토크나이저와 문법을 기술하기 위해 rpython.rlib.parsing.ebnfparse는 이를 위한 구문을 정의합니다.

문법 파일은 규칙들의 시퀀스를 포함합니다. 각 규칙은 정규 표현식 또는 문법 규칙을 기술합니다.

정규 표현식 규칙은 다음과 같은 형식을 가집니다:

NAME: "regex";

NAME은 정규 표현식이 생성하는 토큰의 이름이며(대문자로만 이루어져야 합니다), regex는 위에서 설명한 구문을 따르는 정규 표현식입니다. 토큰 이름 중 하나는 특별하게 처리됩니다: IGNORE라는 토큰은 파서로 전달되기 전에 토큰 스트림에서 걸러지므로, 주석이나 의미 없는 공백을 매칭하는 데 사용할 수 있습니다.

문법 규칙은 다음과 같은 형태를 가집니다:

name: expansion_1 | expansion_2 | ... | expansion_n;

여기서 expansion_i는 비단말(nonterminal) 또는 토큰 이름의 시퀀스입니다:

symbol_1 symbol_2 symbol_3 ... symbol_n

이는 소문자로 이루어져야 하는 비단말 기호 name가 확장 중 어느 하나로 확장될 수 있음을 의미합니다. 확장은 토큰 이름, 비단말 이름 또는 리터럴(따옴표로 둘러싸인, 글자 그대로 일치하는 문자열)의 시퀀스로 구성될 수 있습니다.

이를 더 명확하게 하는 예시:

IGNORE: " ";
DECIMAL: "0|[1-9][0-9]*";
additive: multitive "+" additive |
          multitive;
multitive: primary "*" multitive |
           primary;
primary: "(" additive ")" | DECIMAL;

이 문법은 덧셈과 곱셈을 포함하는 산술 표현식의 구문을 설명합니다. 토크나이저는 DECIMAL 토큰이나 리터럴 “+”, “*”, “(“, “)” 중 하나와 일치하는 토큰의 스트림을 생성합니다. 공백은 모두 무시됩니다. 이 문법은 연산자의 우선순위를 따르는 구문 트리를 생성합니다. 예를 들어 12 + 4 * 5 표현식은 다음과 같은 트리로 파싱됩니다:

파스 트리

파싱 과정은 Symbol과 Nonterminal의 인스턴스로 구성된 트리를 구축하며, 전자는 토큰에 해당하고 후자는 비단말 기호에 해당합니다. 두 클래스는 모두 rpython/rlib/parsing/tree.py 모듈에 있습니다. 파스 트리(parse tree)의 pygame 뷰를 얻기 위해 Nonterminal 인스턴스의 view() 메서드를 사용할 수 있습니다.

Symbol 인스턴스는 다음 속성을 가집니다: 토큰의 이름인 symbol과, 일치한 소스인 additional_info입니다.

Nonterminal 인스턴스는 다음과 같은 속성을 가집니다: symbol은 비단말(nonterminal)의 이름이고, children은 자식 속성들의 목록입니다.

방문자(Visitors)

RPython으로 작성된 파스 트리를 위한 트리 방문자(visitor)를 작성하려면, rpython/rlib/parsing/tree.py에 사용할 수 있는 특수 베이스클래스 RPythonVisitor가 있습니다. 클래스가 이를 사용하면, node 인자에 따라 적절한 visit_<symbol> 메서드를 호출하는 dispatch(node) 메서드가 생겨납니다. 여기서 <symbol>은 방문된 노드의 symbol 속성으로 대체됩니다.

방문자(visitor)가 RPython이 되려면, 모든 visit 메서드의 반환값이 같은 타입이어야 합니다.

트리 변환

위의 산술 예제 트리에서 보듯이, 기본적으로 파스 트리에는 실제로 유용한 정보를 전달하지 않는 노드가 많이 포함되어 있습니다. 이 중 일부를 제거하기 위해, 문법 형식에는 추가 노드를 제거하도록 트리를 변환하는 방문자(visitor)를 자동으로 생성하는 지원 기능이 있습니다. 이러한 변환 중 가장 단순한 것은 그냥 노드를 제거하는 것이지만, 더 복잡한 것들도 있습니다.

이러한 변형(transformation)의 구문은 비단말(nonterminal) 확장 내의 기호를 […], <…> 또는 >…<로 둘러싸는 것입니다.

[symbol_1 symbol_2 … symbol_n]

이렇게 하면 트리에서 둘러싸인 기호를 완전히 제거하는 트랜스포머가 생성됩니다.

예제:

IGNORE: " ";
n: "A" [","] n | "A";

문자열 “A, A, A”를 파싱하면 다음과 같은 트리를 얻습니다:

변환 후 트리에서는 “,” 노드가 제거됩니다:

<symbol>

이는 부모를 기호로 치환합니다. 당연히 부모는 한 번만 치환될 수 있으므로, 모든 확장(expansion)은 <…>로 둘러싸인 기호를 최대 하나만 포함할 수 있습니다.

예시:

IGNORE: " ";
n: "a" "b" "c" m;
m: "(" <n> ")" | "d";

문자열 “a b c (a b c d)”를 파싱하면 다음과 같은 트리가 나옵니다:

변환 후 트리는 다음과 같은 모습입니다:

>nonterminal_1 nonterminal_2 … nonterminal_n<

이는 nonterminal_1부터 nonterminal_n까지의 노드를 해당 자식 노드로 대체합니다.

예제:

IGNORE: " ";
DECIMAL: "0|[1-9][0-9]*";
list: DECIMAL >list< | DECIMAL;

문자열 “1 2”를 파싱하면 다음과 같은 트리가 나옵니다:

변환 후 트리는 다음과 같은 모습입니다:

이 변환은 재귀적으로 동작한다는 점에 유의하십시오. 이는 다음도 동작한다는 것을 의미합니다: 문자열 “1 2 3 4 5”가 파싱되면 트리는 처음에 다음과 같은 모습입니다:

하지만 변환 후에는 전체 구조가 자식이 많은 하나의 노드로 축소됩니다:

EBNF 문법 형식의 확장

EBNF 문법 형식에는 실제로는 문법 설탕(syntactic sugar)에 불과하지만 문법을 작성하는 수고를 덜어주는 몇 가지 확장이 있습니다. 이는 다음과 같습니다:

symbol?:

symbol의 0회 또는 1회 반복과 일치합니다

symbol*:

symbol의 0회 이상 반복과 일치합니다. 트리 변환 후, 이러한 모든 반복은 현재 symbol의 자식이 됩니다.

symbol+:

symbol의 1회 이상 반복과 일치합니다. 트리 변환 후에는 이러한 반복이 모두 현재 symbol의 자식이 됩니다.

이러한 것들은 문법에 올바른 방식으로 규칙을 몇 가지 더 추가하여 구현됩니다. 예시: 문법:

s: a b? c;

다음과 같은 모습으로 변환됩니다:

s: a >_maybe_symbol_0_< c | a c;
_maybe_symbol_0_: b;

문법:

s: a b* c;

다음과 같은 모습으로 변환됩니다:

s: a >_star_symbol_0< c | a c;
_star_symbol_0: b >_symbol_star_0< | b;

문법:

s: a b+ c;

다음과 같은 형태로 변환됩니다:

s: a >_plus_symbol_0< c;
_plus_symbol_0: b >_plus_symbol_0< | b;

전체 예제

json format을 위한 반쯤 완성된 파서:

STRING: "\\"[^\\\\"]*\\"";
NUMBER: "\-?(0|[1-9][0-9]*)(\.[0-9]+)?([eE][\+\-]?[0-9]+)?";
IGNORE: " |\n";
value: <STRING> | <NUMBER> | <object> | <array> | <"null"> |
       <"true"> | <"false">;
object: ["{"] (entry [","])* entry ["}"];
array: ["["] (value [","])* value ["]"];
entry: STRING [":"] value;

문자열을 파싱한 결과 트리는:

{"a": "5", "b": [1, null, 3, true, {"f": "g", "h": 6}]}

다음과 같습니다: