폴란드 표기법

폴란드 표기법(PN) 또는 전위 표기법은 논리, 산술 그리고 대수학(algebra)에 대한 하나의 표기법 양식이다. 그것의 두드러지는 특징은 연산자를 피연산자의 왼쪽에 둔다는 점이다. 연산자에 대한 피연산자의 개수(arity)가 고정되어 있다면, 그 결과는 애매모호함없이 구문 분석 가능한 둥근 괄호(parenthese) 혹은 다른 괄호들이 없는 구문이 된다. 폴란드의 논리학자 얀 우카시에비치(Jan Łukasiewicz)가 명제 논리를 단순화하기 위해 1924년에 이 표기법을 고안했다. 이외에 일반 폴란드 표기법(NPN), 우카시에비치 표기법, 바르샤바 표기법, 접두사 표기법 등으로도 알려져 있다. 때때로 폴란드 표기법이라는 용어는 연산자가 피연산자의 오른쪽에 놓이는 폴란드 후위 표기법 혹은 역 폴란드 표기법까지를 포함하는 용어로 사용된다.

폴란드 표기법이 프로그래밍 언어의 인터프리터에 의해 수학적 표현식에 대한 문법으로써 사용되는 경우, 곧바로 추상 문법 트리로 구문 분석되며, 사실 동일하게 전단사 함수를 정의할 수 있다. 그런 이유로, 리스프(Lisp)와 관련 프로그래밍 언어들은 그들의 전체 문법을 전위 표기법의 측면에서 정의한다(그리고 다른 언어들은 후위 표기법을 사용한다).

더 이상 논리학에서 많이 쓰이지는 않지만, 그 이후로 폴란드 표기법은 컴퓨터 과학에서 그 위치를 이어나가고 있다.

역사

얀 우카시에비치가 쓴 논문 <Remarks on Nicod's Axiom and on "Generalizing Deduction"> 180 페이지의 인용에서 "1924년, 괄호에 자유로운 표기법의 아이디어를 얻었다. 나의 논문 Łukasiewicz(1) 610페이지 각주에서 이 표기법을 처음 사용했다"며 해당 표기법을 고안한 방법에 대해 언급하고 있다. 우카시에비치가 인용한 참고 문헌은 폴란드의 석판 인쇄된 보고서인 듯 하다. 우카시에비치의 Remarks on Nicod's Axiom and on "Generalizing Deduction" 참고 논문은 1965년에 Journal of Symbolic Logic에서 H. A. Pogorzelski에 의해 검토되었다.

알론조 처치(Alonzo Church)는 수학적 논리에 관한 그의 유서깊은 책에서, 이 표기법을 표기 체계에서 주목할 가치가 있는 것으로 언급하면서 화이트헤드와 러셀의 논리적 표기 해석과 Principia Mathematica의 업적과도 대조했다.

1951년에 쓰여진 우카시에비치의 책 Aristotle's Syllogistic from the Standpoint of Modern Formal Logic에서, 그는 그의 표기법의 원칙은 괄호를 피하기 위해 인자 앞에 함수적 술어를 쓰는 것이었으며, 1929년부터 그의 논리학 논문에서 그의 표기법을 사용해 왔다고 언급한다. 한 가지 예를 들자면, 그 뒤에 그는 Alfred Tarski와 1930년에 공저한 명제 논리에 관한 논문에서 인용한다.

산술

전위 표기법에서, 숫자 1과 2를 더하는 표현식은 "1 + 2"가 아닌 "+ 1 2"로 작성된다. 좀 더 복잡한 표현식을 보자면, 연산자는 피연산자의 앞에 놓이지만, 피연산자는 그 자체로 다른 피연산자를 포함하는 표현식이 될 수도 있다. 예를 들어, 다음과 같이 관례 상의 중위 표기법으로 작성된 표현식

$(5-6)\times 7$

은 전 표기법에서 다음과 같이 작성될 수 있다

$\times (-\ 5\ 6)\ 7$

간단한 산술 연산자는 (적어도 산술적인 측면에서) 모두 바이너리 함수(두 개의 인자를 갖는 함수)이기 때문에, 어떠한 전위 표현도 모호하지 않으며, 전위 표현식을 괄호로 묶는 것은 불필요하다. 그것으로 봤을 때, 이전 표현식은 다음과 같이 좀 더 단순화될 수 있다

$\times -\ 5\ 6\ 7$

곱셈의 처리는 두 피연산자 (즉, 5 - 6과 7)가 다른 계산을 마칠 때까지 연기된다. 어떤 표기법과 마찬가지로, 가장 안쪽의 표현식이 먼저 평가되는데, 전위 표기법에서 이런 "가장 안쪽"이라는 것은 괄호 보다는 순서에 의해 정해질 수도 있다.

고전적인 표기법에서, 중위 버전의 둥근 괄호가 필수적이었는데, 다음과 같이 그 위치를 옮기거나

$5-(6\times 7)$

다음과 같이 단순히 제거하는 경우

$5-6\times 7$

그 의미와 전체 표현식의 결과는 선행 규칙(연산 순서)에 기인해 변경될 것이다.

유사하게

$5-(6\times 7)$

은 다음과 같이 폴란드 표기법으로 작성될 수 있다:

$-\ 5\times 6\ 7$

컴퓨터 프로그래밍

전위 표기법은 Lisp의 S-표현식에서 폭넓은 애플리케이션을 추구해왔는데, 여기서 언어 내 연산자가 그 자체로 데이터(일급 함수)이기에 괄호(bracket)는 필수적이다. Lisp 함수는 또 변수의 arity를 가지고 있다. Lisp과 유사한 Tcl이라는 프로그래밍 언어도 mathop 라이브러리를 통해 폴란드 표기법을 사용한다. Ambi라는 프로그래밍 언어는 산술 연산과 프로그램 구조를 위해 폴란드 표기법을 사용한다. 하위 역 폴란드 표기법은 PostScript와 Forth와 같은 많은 스택 기반 프로그래밍 언어에서 사용되며, 특히 휴렛-패커드의 특정 계산기의 연산 원칙이기도 하다.

CoffeeScript 문법 또한 전위 표기법을 사용해 호출되는 함수를 허용하는 반면 다른 언어들에서는 단항 후위 문법을 여전히 지원 중이다.

표현식의 반환 값 개수는 표현식 내 피연산자의 개수와 연산자의 전체 피연산자 개수에서 연산자의 반환 값의 전체 개수를 뺀 것의 차가 된다.

연산 순서

연산 순서는 전위 표기법의 구조 내에서 정의되며 쉽게 결정할 수 있다. 한 가지 염두에 두어야 할 것은 연산 실행 시, 두번째 피연산자에 의해 첫번째 피연산자에 연산이 적용된다는 것이다. 이것은 가환산성 연산의 경우에는 이슈가 아니지만, 나누기 또는 뺄셈과 같은 비가환산성 연산의 경우, 이러한 사실이 구문 분석에 중대한 영향을 끼친다. 다음 구문을 예로 보자:

$\div \ 10\ 5=2$

위 표현식은 "10을 5로 나눈다"고 읽는다. 그래서 결과는 2이며 올바르지 않은 분석의 결과로 1/2이 되지 않는다.

전위 표기법은 둥근 괄호를 필요로 하지 않고 연산의 순서를 쉽게 구별할 수 있는 본질적인 능력 덕분에 스택 기반의 연산에 특히 많이 사용된다. 전위 표기법에서 연산의 순서를 평가하기 위해, 중위 표기법처럼 연산의 계층을 기억하고 있을 필요가 전혀 없다. 그 대신에 먼저 평가할 연산자가 어떤 것인지를 알아내기 위해 표기법을 직접 탐색한다. 표현식을 왼쪽에서 오른쪽으로 읽으면, 먼저 연산자를 찾고 그 뒤에 두 개의 피연산자를 찾는다. 만약 다른 연산자가 두 개의 피연산자를 발견하기 전에 나오면, 새로운 피연산자가 풀릴 때까지 이전 연산자를 곁에 둔다. 이 과정은 연산자가 풀릴 때까지 계속되는데, 완전한 구문 내에는 연산자보다 한 개 이상의 피연산자가 더 많으므로, 결국 완료된다. 표현식이 풀리고 나면, 연산자와 두 개의 피연산자는 새로운 피연산자가 된다. 하나의 연산자와 두 개의 피연산자는 제거되고 하나의 피연산자가 추가되기 때문에, 하나의 연산자와 하나의 피연산자의 절대 손실이 존재하며, 이것은 N개의 연산자와 N+1개의 피연산자를 가진 표현식을 남기므로 반복적인 과정을 계속할 수 있게 된다. 이것이 프로그래밍 언어에서 전위 표기법 구문을 평가하기 위해 스택을 사용하는 이면의 일반적인 이론이다(비록 그 과정을 처리하는 다양한 알고리즘이 있긴 하지만) . 한번 분석되고 나면, 증가되는 편의로 관례와의 구분을 허용함으로써 전위 표기법의 구문은 인간의 마음에 덜 위협적으로 바뀌게 된다. 전위 표기법을 사용하는 복잡한 구문이 연산 순서를 통해 판독될 수 있는 용이함을 보여준다:

$-\times \div 15-7+1\ 1\ 3+2+1\ 1=$

$-\times \div 15-7\ 2\qquad 3+2+1\ 1=$

$-\times \div 15\ 5\quad \quad \quad \ \ \ 3+2+1\ 1=$

$-\times 3\qquad \qquad \quad \ \ \ 3+2+1\ 1=$

$-9\qquad \qquad \qquad \quad \ \ +2+1\ 1=$

$-9\qquad \qquad \qquad \quad \ \ +2\ 2\quad \ \ \ =$

$-9\qquad \qquad \qquad \qquad 4\qquad \quad \ =$

$5$

이것은 중위 표기법으로 다음과 같다: $((15\div (7-(1+1)))\times 3)-(2+(1+1))=5$

다음은 스택을 이용한 전위 평가의 구현(pseudo 코드)이다. 이 구현에서는 입력 문자열이 오른쪽에서 왼쪽으로 읽힌다. 이것은 문자열을 왼쪽에서 오른쪽으로 처리했던, 위에서 설명한 알고리즘과는 차이가 있다. 두 알고리즘은 유효한 모든 문자열에 대해 동일한 값을 계산한다.

Scan the given prefix expression from right to left
for each symbol
 {
  if operand then
    push onto stack
  if operator then
   {
    operand1=pop stack
    operand2=pop stack
    compute operand1 operator operand2
    push result onto stack
   }
 }
return top of stack as result

이 알고리즘을 위 예제에 적용하면 다음과 같은 결과를 얻는다:

$-\times \div 15-7+1\ 1\ 3+2+1\ 1=$

$-\times \div 15-7+1\ 1\ 3+2\ 2\quad \ \ \ =$

$-\times \div 15-7+1\ 1\ 3+4\quad \quad \ \ =$

$-\times \div 15-7\ 2\qquad 3+4\quad \quad \ \ =$

$-\times \div 15\ 5\ \ \ \quad \qquad 3+4\quad \quad \ \ =$

$-\times 3\qquad \quad \ \ \ \qquad 3+4\quad \quad \ \ =$

$-9\qquad \qquad \qquad \quad \ \ +4\quad \quad \ \ =$

$5$

예제

이 예제는 이전과 같은 표현식과 알고리즘을 사용한다.

$-\times \div 15-7+1\ 1\ 3+2+1\ 1$

토큰	액션	스택	비고
1	Operand	1	스택에 푸쉬
1	Operand	1 1	스택에 푸쉬
+	Operator	2	두 개의 피연산자 (1, 1)을 팝, (1 + 1 = 2)을 계산하고 스택에 푸쉬
2	Operand	2 2	스택에 푸쉬
+	Operator	4	두 개의 피연산자 (2, 2)을 팝, (2 + 2 = 4)을 계산하고 스택에 푸쉬
3	Operand	3 4	스택에 푸쉬
1	Operand	1 3 4	스택에 푸쉬
1	Operand	1 1 3 4	스택에 푸쉬
+	Operator	2 3 4	두 개의 피연산자 (1, 1)을 팝, (1 + 1= 2)을 계산하고 스택에 푸쉬
7	Operand	7 2 3 4	스택에 푸쉬
−	Operator	5 3 4	두 개의 피연산자 (7, 2)을 팝, (7 - 2 = 5)을 계산하고 스택에 푸쉬
15	Operand	15 5 3 4	스택에 푸쉬
÷	Operator	3 3 4	두 개의 피연산자 (15, 5)을 팝, (15 ÷ 5 = 3)을 계산하고 스택에 푸쉬
×	Operator	9 4	두 개의 피연산자 (3, 3)을 팝, (3 × 3 = 9)을 계산하고 스택에 푸쉬
−	Operator	5	두 개의 피연산자 (9, 4)을 팝, (9 - 4 = 5)을 계산하고 스택에 푸쉬

결과는 스택 제일 위에 남는다.

논리학을 위한 폴란드 표기법

아래 표는 명제 논리를 위한 얀 우카시에비치의 핵심을 보여준다. 폴란드 표기법 표의 몇 가지 문자들은 보이는 것처럼 폴란드의 특정 단어들을 위해 존재한다:

개념	관례상의 표기법	폴란드 표기법	폴란드 단어
부정	$\neg \varphi$	$\mathrm {N} \varphi$	negacja
논리곱	$\varphi \land \psi$	$\mathrm {K} \varphi \psi$	koniunkcja
논리합	$\varphi \lor \psi$	$\mathrm {A} \varphi \psi$	alternatywa
Material conditional	$\varphi \to \psi$	$\mathrm {C} \varphi \psi$	implikacja
Biconditional	$\varphi \leftrightarrow \psi$	$\mathrm {E} \varphi \psi$	ekwiwalencja
Falsum	$\bot$	$\mathrm {O}$	fałsz
부정논리곱	$\varphi \mid \psi$	$\mathrm {D} \varphi \psi$	dysjunkcja
Possibility	$\Diamond \varphi$	$\mathrm {M} \varphi$	możliwość
Necessity	$\Box \varphi$	$\mathrm {L} \varphi$	konieczność
보편 양화사Universal quantifier)	$\forall p\,\varphi$	$\Pi p\,\varphi$	kwantyfikator ogólny
존재 양화사(Existential quantifier)	$\exists p\,\varphi$	$\Sigma p\,\varphi$	kwantyfikator szczegółowy