PEP 275 – 여러 값에 대한 스위칭
- Author:
- Marc-André Lemburg <mal at lemburg.com>
- Status:
- Rejected
- Type:
- Standards Track
- Created:
- 10-Nov-2001
- Python-Version:
- 2.6
- Post-History:
번역·라이선스 안내
이 비공식 한국어 번역은 원문 Copyright 절의 Public Domain 조건에 따라 제공합니다. 원저자와 공식 원문은 그대로 표시합니다. 수정되지 않은 기준 원문 · 공식 최신판
거부 공지
Python 3000을 위한 유사한 PEP인 PEP 3103도 이미 거부되었으므로, 이 제안 또한 채택될 가능성이 없습니다.
초록
이 PEP는 여러 가능한 값 중 하나를 가지는 단일 변수에 대한 스위칭 처리와 관련하여 Python의 성능을 향상시키기 위한 전략을 제안합니다.
문제
Python 2.5까지, 다중 값 스위치를 작성하는 일반적인 방법은 다음과 같은 유형의 긴 스위치 구문을 사용하는 것이었습니다.:
if x == 'first state':
...
elif x == 'second state':
...
elif x == 'third state':
...
elif x == 'fourth state':
...
else:
# default handling
...
이는 짧은 스위치 구문에서는 잘 동작하는데, 로컬 변수(이 경우 변수 x)를 반복적으로 로드하고 이를 어떤 상수와 비교하는 오버헤드가 낮기 때문입니다(평균적으로 O(n)의 복잡도를 가집니다). 그러나 파서를 작성할 때 필요한 것과 같은 상태 머신을 작성하기 위해 이러한 구문을 사용하면, 가능한 상태의 수가 쉽게 10개 이상에 이를 수 있습니다.
이 문제에 대한 현재의 해법은, 스위치 변수의 값에 따라 실행할 케이스 구현 메서드를 찾기 위해 디스패치 테이블을 사용하는 데 있습니다(예를 들어 완전 해시 테이블을 사용하는 등의 방법으로 평균 O(1)의 복잡도를 갖도록 조정할 수 있습니다). 이는 서로 다른 케이스 메서드에서 복잡하고 긴 처리를 요구하는 상태 머신에서는 잘 동작합니다. 케이스당 한두 개의 명령만 처리하는 경우에는 성능이 좋지 않습니다. 예를 들면 다음과 같습니다.
def handle_data(self, data):
self.stack.append(data)
이에 대한 좋은 예로는 Python 객체를 직렬화하는 데 사용되는 pickle.py에 구현된 상태 머신을 들 수 있습니다. 그 밖의 대표적인 사례로는 XML SAX 파서와 인터넷 프로토콜 핸들러가 있습니다.
제안된 해법들
이 PEP는 서로 다르지만 반드시 상충하지는 않는 두 가지 해법을 제안합니다.
- 위와 같은 if-elif-else 구문을 감지하여 점프 오프셋을 저장하기 위해 읽기 전용 딕셔너리를 사용하는 특수 옵코드를 생성하는 최적화를 Python 컴파일러와 VM에 추가하는 방법.
- C 스타일의 switch 문을 모방한 새로운 구문을 Python에 추가하는 방법.
첫 번째 해법은 언어에 새로운 키워드를 추가하는 데 의존하지 않는다는 이점이 있는 반면, 두 번째 해법은 더 깔끔해 보입니다. 두 방법 모두 스위칭 변수가 불변이고 해시 가능함을 보장하기 위한 어느 정도의 런타임 오버헤드를 수반합니다.
두 해법 모두 올바른 점프 위치를 찾기 위해 딕셔너리 조회를 사용하므로, 스위치 변수와 상수 모두가 딕셔너리 구현과 호환되어야 한다는(해시 가능하고, 비교 가능하며, a==b => hash(a)==hash(b)) 점에서 동일한 문제 영역을 공유합니다.
해법 1: if-elif-else 최적화하기
구현:
컴파일러가 다음과 같은 시그니처를 갖는 if-elif-else 구문을 감지할 수 있어야 합니다.:
if x == 'first':...
elif x == 'second':...
else:...
즉, 좌변은 항상 동일한 변수를 참조하고, 우변은 해시 가능한 불변내장 타입을 참조해야 합니다. 우변들이 모두 같은 타입일 필요는 없지만, 좌변의 스위치 변수 타입과 비교 가능해야 합니다.
그런 다음 컴파일러는 읽기 전용(완전) 해시 테이블을 설정하여 상수에 저장하고, 표준 if-elif-else 바이트코드 스트림 앞에 다음과 같은 런타임 동작을 유발하는 SWITCH 옵코드를 추가할 수 있습니다.
런타임에 SWITCH는 x가 잘 알려진 불변타입(문자열, 유니코드, 숫자) 중 하나인지 검사하고, 해시 테이블을 사용하여 올바른 옵코드 스니펫을 찾습니다. 이 조건이 충족되지 않으면, 인터프리터는 단순히 SWITCH 옵코드를 건너뛰고 통상적인 if-elif-else 바이트코드 스트림을 계속 진행함으로써 표준 if-elif-else 처리로 되돌아가야 합니다.
문제점:
새로운 최적화는 (해당 최적화의 영향을 받는 if-elif-else 구문에서 __cmp__ 호출 수를 줄이고 __hash__호출을 추가함으로써) 현재의 Python 의미론을 변경해서는 안 됩니다. 이를 보장하려면, 스위칭은 “from __future__” 스타일의 플래그가 사용되는 경우이거나, 스위칭 변수가 int, float, string, unicode 등 내장 불변 타입 중 하나인 경우(서브타입은 여전히 불변인지 여부가 명확하지 않으므로 제외)에만 안전하게 구현할 수 있습니다.
jump-table 딕셔너리의 사후 수정(이는 보호된 코드에 도달하는 데 사용될 수 있음)을 방지하기 위해, jump-table은 읽기 전용 타입(예: 읽기 전용 딕셔너리)이어야 합니다.
이 최적화는 최소 n개의 케이스를 갖는 if-elif-else 구문에만 사용해야 합니다(n은 성능 테스트에 따라 아직 정의되지 않은 값입니다).
해결책 2: Python에 switch 문 추가
새로운 문법
switch EXPR:
case CONSTANT:
SUITE
case CONSTANT:
SUITE
...
else:
SUITE
(들여쓰기 변형은 제외)
“else” 부분은 선택 사항입니다. else 부분이 주어지지 않고 정의된 케이스 중 어느 것도 일치하지 않으면, 아무 동작도 취해지지 않고 switch 문은 무시됩니다. 이는 현재 if 문의 동작 방식과 일치합니다. 이 상황을 예외로 알리고자 하는 사용자는 의도한 동작을 구현하는 else 분기를 정의할 수 있습니다.
상수들이 모두 같은 타입일 필요는 없지만, switch 변수의 타입과 비교 가능해야 한다는 점에 유의하십시오.
구현
컴파일러는 이를 다음과 유사한 바이트코드로 컴파일해야 할 것입니다:
def whatis(x):
switch(x):
case 'one':
print '1'
case 'two':
print '2'
case 'three':
print '3'
else:
print "D'oh!"
다음과 같이 됩니다(POP_TOP과 SET_LINENO는 생략함):
6 LOAD_FAST 0 (x)
9 LOAD_CONST 1 (switch-table-1)
12 SWITCH 26 (to 38)
14 LOAD_CONST 2 ('1')
17 PRINT_ITEM
18 PRINT_NEWLINE
19 JUMP 43
22 LOAD_CONST 3 ('2')
25 PRINT_ITEM
26 PRINT_NEWLINE
27 JUMP 43
30 LOAD_CONST 4 ('3')
33 PRINT_ITEM
34 PRINT_NEWLINE
35 JUMP 43
38 LOAD_CONST 5 ("D'oh!")
41 PRINT_ITEM
42 PRINT_NEWLINE
>>43 LOAD_CONST 0 (None)
46 RETURN_VALUE
‘SWITCH’ 옵코드는 ‘x’에 따라 14, 22, 30 또는 38로 점프합니다.
Thomas Wouters는 위 내용을 보여주는 패치를 작성했습니다. [1]에서 다운로드할 수 있습니다.
문제점
switch 문은 (C의 switch 문처럼) fall-through 동작을 구현해서는 안 됩니다. 각 case는 완전하고 독립적인 suite를 정의합니다. 이는 if-elif-else 문과 매우 유사합니다. 이는 또한 반복문 내부의 switch 문에서 break를 사용할 수 있게 합니다.
인터프리터가 switch 변수 x가 해시 가능하지 않다는 것을 발견하면, 실행 시점에 이 문제를 지적하는 TypeError를 발생시켜야 합니다.
기존 키워드를 재사용하고 새로운 키워드(“switch”와 “case”) 두 개를 추가하는 것을 피하는 다른 문법 제안들도 있었습니다. 다른 이들은 이름이 같지만 의미가 약간 다른(예: break 없는 fall-through) C의 키워드와 혼동을 피하기 위해 키워드가 새로운 용어를 사용해야 한다고 주장했습니다. 제안된 변형 중 일부:
case EXPR:
of CONSTANT:
SUITE
of CONSTANT:
SUITE
else:
SUITE
case EXPR:
if CONSTANT:
SUITE
if CONSTANT:
SUITE
else:
SUITE
when EXPR:
in CONSTANT_TUPLE:
SUITE
in CONSTANT_TUPLE:
SUITE
...
else:
SUITE
switch 문은 하나의 섹션에 여러 값을 허용하도록 확장될 수 있습니다(예: case ‘a’, ‘b’, ‘c’: …). 또 다른 제안된 확장은 값의 범위를 허용하는 것입니다(예: case 10..14: …). 이는 아마도 연기되어야 하겠지만, 첫 번째 버전을 설계하고 구현할 때 이미 염두에 두어야 합니다.
예제
다음 예제들은 모두 해결책 2에서 제안한 새로운 문법을 사용합니다. 하지만 이 예제들은 모두 해결책 1에서도 동작할 것입니다.
switch EXPR: switch x:
case CONSTANT: case "first":
SUITE print x
case CONSTANT: case "second":
SUITE x = x**2
... print x
else: else:
SUITE print "whoops!"
case EXPR: case x:
of CONSTANT: of "first":
SUITE print x
of CONSTANT: of "second":
SUITE print x**2
else: else:
SUITE print "whoops!"
case EXPR: case state:
if CONSTANT: if "first":
SUITE state = "second"
if CONSTANT: if "second":
SUITE state = "third"
else: else:
SUITE state = "first"
when EXPR: when state:
in CONSTANT_TUPLE: in ("first", "second"):
SUITE print state
in CONSTANT_TUPLE: state = next_state(state)
SUITE in ("seventh",):
... print "done"
else: break # out of loop!
SUITE else:
print "middle state"
state = next_state(state)
다음은 Jack Jansen이 발견한 또 다른 멋진 응용 사례입니다(인자 타입에 따른 switch):
switch type(x).__name__:
case 'int':
SUITE
case 'string':
SUITE
범위
XXX “from __future__ import switch”를 설명합니다
기여자
- Martin von Löwis (최적화 아이디어와 관련된 문제)
- Thomas Wouters (switch 문 + 바이트코드 컴파일러 예제)
- Skip Montanaro (디스패치 아이디어, 예제)
- Donald Beaudry (switch 구문)
- Greg Ewing (switch 구문)
- Jack Jansen (타입 스위칭 예제)
참조
Copyright
This document has been placed in the public domain.