함수 분석

오늘도 프로그램을 분석하는 키파는 PS-Lang에 메모이제이션 기능을 지원하려고 프로그램을 분석한 뒤 다음과 같은 구조를 만들었습니다. (newline은 강제 개행 문자(line feed)를 의미합니다.)

α-list = ε | α α-list\
α-space = α space-list\
program = func-space-list\
\
command = func | define | refer | block\
func = "`FUNCTION`" space-list name space-list block\
define = "`DEFINE`" space-list name\
refer = "`REFER`" space-list name\
block = "`{`" space-list command-space-list space-list "`}`"\
\
name = alphabet alphabet-list\
alphabet = "`a`" | "`b`" | "`c`" | ... | "`z`"\
space = "` `" | newline

모든 define 및 func의 변수 $v$에 대해 $v$의 scope $S(v)$는 프로그램의 parse tree에서 $v$의 조상 중 가장 안쪽에 있는 block을 뜻합니다. func는 scope 전에 오는 이름이 define된 것과 같은 효과를 가지므로 자기 자신을 재귀 호출할 수 있습니다. C/C++에서와 마찬가지로 다음 두 가지 프로그램은 허용하지 않습니다.

• 재정의 오류. define 혹은 func의 변수 $v$의 이름을 $N(v)$라 할 때, define 혹은 func의 변수 $v$, $w$에 대해 $N(v) = N(w)$이면서 $S(v) = S(w)$인 경우입니다.
• 자유로운 변수 오류. refer의 변수 $v$에 대해 parse tree를 전위 순회할 때 define($N(v)$)가 현재 노드보다 앞에 한 번도 나타나지 않는 경우입니다.

어떤 함수에 메모이제이션을 적용할지 정하기 위해 키파는 간단한 기준을 쓰기로 했습니다. 함수가 함수 밖에 있는 (자기 자신을 제외한) 변수를 참조하지 않으면 순수 함수로 정의합니다. 순수 함수의 결괏값은 인자에만 따라 달라지므로, 호출할 때 메모이제이션을 적용할 수 있습니다.

프로그램이 주어지면 각 함수가 순수 함수인지 판단하는 프로그램을 작성하세요.

프로그램은 여러 줄에 걸쳐 주어집니다. 주어진 프로그램의 parse tree에서 command 노드는 최대 $10^4$개 등장합니다. 주어진 프로그램의 오류(재정의 혹은 자유로운 변수)는 최대 하나입니다.

주어진 프로그램에서 space는 연속으로 10번보다 많이 나타나지 않습니다. 또 프로그램을 줄 단위로 보았을 때, 맨 마지막 줄을 제외하고 공백(" ")만 포함된 줄은 없습니다. 맨 마지막 줄이 공백으로만 이루어져 있다면, 그 줄은 빈 줄입니다.

연속된 소문자는 8자보다 많이 주어지지 않습니다.

프로그램을 분석한 결과를 다음과 같이 출력합니다.

• 프로그램이 재정의 오류를 일으키면 Redefined를 출력합니다.
• 프로그램이 자유로운 변수 오류를 일으키면 Unbound를 출력합니다.
• 프로그램이 아무 오류도 일으키지 않으면, 다른 func 안에 들어 있지 않은 모든 func $v$를 program의 text에 등장한 순서대로 출력합니다. $v$가 순수 함수이면 N(v)와 "pure"를, 순수 함수가 아니면 N(v)와 "not pure"를 공백을 사이에 두고 출력합니다. (따옴표 제외)

프로그램이 오류를 일으키지 않을 경우, 함수 안의 함수에 대해서는 순수 함수 여부를 출력하지 않습니다.

함수가 순수 함수인지를 튜링 완전한 언어에 대해 완벽하게(sound and complete) 판별하는 문제는 계산 불가능한 문제입니다.