느긋한 계산과 엄격한 계산

시간 제한1초메모리 제한128 MB

요약

Lisp 형태의 작은 언어에서 함수 정의를 읽고, 지연 평가(메모이제이션 포함)와 엄격 평가 각각에서 산술 연산이 몇 번 실행되는지 세어 출력한다. 끝나지 않는 식은 건너뛴다.

난이도: 보통10점 중 7점
유형: 구현, 재귀, 시뮬레이션, 동적 계획법
정답자: 아직 제출이 없습니다

문제

실무에서 쓰이는 대부분의 프로그래밍 언어는 엄격한 계산(strict evaluation) 을 사용한다. 함수를 호출하면 인자로 넘긴 식을 먼저 계산하고, 그 결과 값을 함수에 전달한다. 그러나 이것이 유일한 방법은 아니다. 어떤 언어는 특정 연산자에 대해 느긋한 계산(lazy evaluation) 을 수행한다(예를 들어 C++의 && 와 || 는 결과를 결정하는 데 필요한 만큼의 인자만 계산한다).

작은 식 언어를 정의하고, 느긋한 계산과 엄격한 계산에서 각 산술 연산이 몇 번 실행되는지를 세어 보자.

식. 식은 다음 중 하나이다.

상수: 부호 있는 32비트 정수. 예: 3, 0, -2, 123.
이름: 내장 함수 또는 사용자 정의 함수의 이름. 이름은 소문자 영문 알파벳 최대 32글자로 이루어진 단어이다. 예: f, add.
함수 호출: (function arg1 ... argN) 형태. 여기서 function 은 $N$ 개의 인자를 받는 함수로 계산되는 식이고, arg1 ... argN 은 인자로 넘길 식이다. 예: (f 3 5), (add 2 (add 1 2)).

계산 규칙.

상수는 자기 자신으로 계산된다.
이름은 그것이 가리키는 함수로 계산된다.
함수 호출은 다음과 같이 계산된다.
- 느긋한 계산에서는 함수 식을 먼저 계산한 뒤, 각 형식 매개변수를 대응하는 인자 식 에 묶어 본문을 계산한다. 인자 식은 그 값이 실제로 필요할 때에만, 그리고 많아야 한 번만 계산된다. 한 번 계산되면 그 값이 해당 매개변수의 모든 출현을 대체한다(메모이제이션).
- 엄격한 계산에서는 모든 식을 먼저 계산한다(함수 식은 함수로, 인자는 값으로). 그런 다음 각 형식 매개변수를 대응하는 인자 값으로 치환하여 본문을 계산한다.

내장 함수 (모두 두 개의 인자를 받는다):

함수	결과
`add x y`	$x + y$
`sub x y`	$x - y$
`mult x y`	$x \times y$
`div x y`	정수 나눗셈 (C/C++/Java의 `/`)
`rem x y`	나머지 (C/C++/Java의 `%`)
`true x y`	$x$ (항상 첫 번째 인자)
`false x y`	$y$ (항상 두 번째 인자)
`eq x y`	$x$ 와 $y$ 가 같은 상수이면 `true`, 아니면 `false`
`gt x y`	$x > y$ 이면 `true`, 아니면 `false`

eq 와 gt 는 함수 true/false 를 돌려주므로, 불리언 값이 두 갈래 선택자 역할을 겸한다.

사용자 정의 함수 는 name arg1 ... argN = body 문법으로 정의한다. arg1 ... argN 은 서로 다른 단어(소문자 최대 32글자)로 형식 매개변수이며, body 는 상수나 이름이 올 수 있는 자리에 매개변수가 나타날 수 있는 식이다. 인자가 없는(0개) 함수도 허용된다. 형식 매개변수는 함수 이름을 가릴 수 있으나, 함수 이름은 모두 서로 다르다.

내장 함수의 인자 계산. 엄격한 계산에서는 모든 내장 함수가 자신의 인자를 모두 계산한다. 느긋한 계산에서는 add, sub, mult, div, rem, eq, gt 는 두 인자를 모두 계산하지만, true 와 false 는 자신이 돌려주는 한쪽 인자만 계산한다.

오버플로와 나눗셈. 모든 산술은 부호 있는 32비트 정수에서 이루어지며, C/C++/Java의 +, -, *, /, % 연산자와 똑같이 넘침(wrap-around)이 일어난다. div 와 rem 은 0 쪽으로 절삭(truncate toward zero)한다. 0으로 나누는 경우는 없다.

정지하지 않는 경우. 각 테스트 식에 대해, 느긋한 계산과 엄격한 계산 중 어느 한쪽이라도 $2345$ 번의 함수 계산을 넘겨도 끝나지 않으면 그 식은 무한 루프로 간주한다. 그 식은 통째로 건너뛰고, 어느 쪽 계산에서도 그 식의 연산 횟수를 전혀 더하지 않는다.

입력

입력은 두 부분으로 이루어진다.

첫 번째 부분에는 $1000$ 개 미만의 함수 정의가 한 줄에 하나씩 주어지고, 그 뒤에 빈 줄 하나가 온다. 전방 참조(뒤에 정의되는 함수를 먼저 참조하는 것)와 재귀가 허용된다.

두 번째 부분에는 $1000$ 개 미만의 테스트 식이 한 줄에 하나씩 주어지고, 그 뒤에 빈 줄 하나가 온다. 함수 이름과 인자는 하나의 공백으로 구분되며, 괄호 주위에는 여분의 공백이 없다. 각 식은 느긋한 계산과 엄격한 계산 두 방식 모두로 계산된다.

모든 정의와 식은 문법적으로 올바르며, 산술 내장 함수는 항상 정수에만 적용되고, 0으로 나누는 경우는 없다. 각 줄은 최대 $255$ 글자이다.

출력

건너뛰지 않은 모든 테스트 식에서 각 산술 연산이 몇 번 실행되었는지를 정확히 여섯 줄로 출력한다.

첫 줄은 머리글 operator lazy strict 이다. 다음 다섯 줄은 각각 op lazy strict 형태이며, op 는 add, sub, mult, div, rem 중 하나이다(이 순서대로). lazy 는 느긋한 계산에서 op 가 실행된 총 횟수, strict 는 엄격한 계산에서의 총 횟수이다. 각 줄의 토큰은 공백 하나로 구분한다.

operator lazy strict
add <lazy> <strict>
sub <lazy> <strict>
mult <lazy> <strict>
div <lazy> <strict>
rem <lazy> <strict>

이 다섯 개의 산술 연산만 센다. true, false, eq, gt 는 절대로 세지 않는다.

예제3

예제 1

입력

if cond truepart elsepart = (cond truepart elsepart)
fact x = (facta x 1)
facta x a = (if (eq x 0) a (facta (sub x 1) (mult a x)))
and x y = (x y false)
ident x = x
two = 2
op op x = ((if (eq op 1) add sub) op x)
not op = (op false true)
sum n = (suma n 0)
suma n a = (((gt n 1) suma false) (sub n 1) (add a n))

(true (add 1 2) (mult 1 2))
5
true
(and (gt (op (sub 2 1) 1) 5) (eq (two) (op 1 1)))
(false (sub 1 2) (sum 4))
((eq (true 1 2) (false 2 1)) (add 1 2) (sub 1 2))
(fact 3)

예상 출력

operator lazy strict
add 7 8
sub 4 7
mult 0 1
div 0 0
rem 0 0

예제 2

입력


(add (mult 3 4) (sub 10 2))
(div 17 5)
(rem 17 5)

예상 출력

operator lazy strict
add 1 1
sub 1 1
mult 1 1
div 1 1
rem 1 1

예제 3

입력


(true (add 1 1) (mult 2 2))
(false (sub 5 3) (div 8 2))

예상 출력

operator lazy strict
add 1 1
sub 0 1
mult 0 1
div 1 1
rem 0 0