함수형 언어 인터프리터와 호출 프로파일링

아주 작은 함수형 언어의 인터프리터를 구현한다. 인터프리터는 입력으로 들어오는 표현식, 대입문, 함수 정의를 한 줄씩 읽어 처리한다. 함수 정의는 기억되어 이후 표현식에서 다시 사용할 수 있고, 표현식은 읽는 즉시 계산되어 결과가 출력된다. 이 언어가 다루는 자료형은 정수뿐이다.

입력은 여러 줄로 이루어지며, 각 줄은 하나의 동작을 나타낸다. 한 줄은 100자를 넘지 않는다. 동작의 종류는 다음과 같다.

1. <expression> — 표현식을 정수로 계산하여 그 결과를 출력한다.
2. set <identifier> = <expression> — 대입문. <identifier>는 변수를 가리킨다. 처음 보는 이름이면 새 변수를 만들어 표현식의 값을 넣고, 이미 있는 이름이면 값을 갱신한다.
3. def <identifier> ( <parameter> ) = <expression> — 정수 매개변수 하나를 갖는 함수 <identifier>를 정의한다. <parameter>는 <number> 또는 <identifier>이다. 숫자이면 매개변수가 그 값일 때의 정의이고, 식별자이면 모든 값에 대한 일반 정의이다. 정의가 나온 순서가 중요하다. 한 함수의 모든 정의는 그대로 보관되며, 함수를 호출하면 입력 순서대로 매개변수가 처음으로 일치하는 정의를 찾아 사용한다(숫자 정의는 인자가 그 값과 같을 때 일치하고, 식별자 정의는 항상 일치한다). 따라서 한번 정해진 동작은 나중에 바꿀 수 없다.
4. profile — 정의된 각 함수에 대해, 마지막 profile(또는 프로그램 시작) 이후 각 정의 줄에서 이루어진 호출 횟수를 보고한다. 출력 형식은 아래를 참고한다.
5. exit — 입력의 끝.

각 줄은 exit를 만날 때까지 한 줄씩 즉시 처리한다. 이 언어가 다루는 자료형은 정수뿐이며, 값은 항상 -1,000,000 이상 1,000,000 이하이다(양 끝 포함).

표현식 문법은 다음과 같고, 연산자 우선순위는 일반적인 규칙을 따른다(먼저 factor, 다음 term, 마지막으로 expression을 계산).

• <expression>은 <term>들의 합(+)과 차(-)이며 왼쪽에서 오른쪽으로 계산한다(예: a + b - 3 + 4 - c).
• <term>은 <factor>들의 곱(*), 몫(/), 나머지(%)이며 왼쪽에서 오른쪽으로 계산한다(예: 3 * 4 / 5 % x). 나눗셈은 정수 나눗셈이고, 나머지는 음수에 대해서는 절대 사용되지 않는다.
• <factor>는 <number>, 변수 또는 현재 함수의 매개변수인 <identifier>, <identifier>(<expression>) 형태의 함수 호출, 또는 괄호로 묶인 (<expression>)이다.
• <number>는 0 이상 1,000,000 이하의 십진수이다.
• <identifier>는 대소문자 영문자로 이루어진 문자열이며 대소문자를 구분한다(예: A와 a는 다른 변수). 예약어 def, set, profile, exit는 식별자로 쓸 수 없다.

공백은 단어를 구분하는 경우를 제외하면 무시된다. 모든 입력은 문법적으로 올바르며, 모든 함수 호출은 반드시 종료하고, 모든 표현식의 결과는 허용 범위 안에 있다고 가정해도 된다. 한 함수의 한 정의 줄에 기록되는 총 호출 횟수는 1,000,000을 넘지 않는다.

표현식의 결과는 각각 한 줄에 출력하며, 앞에 >> (초과 기호 두 개와 공백 한 칸)를 붙인다.

profile의 결과는 정의된 각 함수마다 한 줄씩, <identifier> calls: n1 n2 n3 ... => nt 형식으로 출력한다. 여기서 ni는 입력 순서로 i번째 정의 줄에서 이루어진 호출 횟수이고, nt는 그 함수에 대한 총 호출 횟수이다(모두 공백 하나로 구분). 함수는 처음 정의된 순서대로 출력한다.