Problem Description
Most of the programming languages used in practice perform strictevaluation.
When a function is called, the expressions passed in the function arguments (for instance a + b in f (a + b, 3)) are evaluated first,and the resulting values are passed to the function.
However, this is not the only way how expressions can be evaluated, and in fact, even such a mainstream language as C++ is sometimes performing lazy evaluation: the operators && and jj evaluate only those arguments that are needed to determine the value of the expression.
Pal Christian is now working on a comparative study of the performance of the lazy and strict evaluation. Pal wants to evaluate in both ways a set of expressions that follow this simplied syntax:
－－an expression is either a constant, a name, or a function call
－－a constant is a signed 32-bit integer; for example, 3, 0, -2, 123 are constants;
－－a name is a name of a built-in or user-dened function, for example, f , or add are names; names are words containing up to 32 lowercase letters from the English alphabet;
－－function call has the form: ( f unction arg1 . . . argN ), where f unction is an expression that evaluates to some function of N arguments, and arg1 . . . argN are expressions that evaluate to arguments passed to the function. For example, ( f 3 5 ) , or ( add 2 ( add 1 2 )) are valid function calls.
Expressions are evaluated according to the following simple rules:
－－constants evaluate to themselves
－－names evaluate to the functions they denote
－－function calls:
in lazy evaluation: the first expression is evaluated first to obtain a function, whose function body, with formal parameters substituted for the expressions provided as the arguments, is evaluated; however, whenever some argument gets evaluated while evaluating the function body, the resulting value will replace all occurences of the same parameter in that function body. In other words, the expression passed in the argument is never evaluated more than once.
in strict evaluation: all expressions are evaluated first: the first expression should evaluate to a function, the remaining to values that are used as function arguments; the result is the result of evaluating the corresponding function body, where all occurences of formal parameters are replaced by the values obtained by evaluating the arguments.
The following built-in functions are available: add x y - sum of the constants x and y, sub x y - returns the value x-y, mult x y - product of x and y, div x y - integer division, and rem x y - remainder (same semantics as '/' and '%' in C, C++ or Java), true x y - always returns x, f alse x y - always returns y , eq x y - returns true if x and y is the same constant, otherwise returns f alse, gt x y - returns true if x is greater than y, otherwise returns f alse.
User-defined functions are defined using the following syntax:
f unction name arg1 . . . argN = body, where arg1 . . . argN are distinct words (up to 32 English lowercase letters), denoting the formal parameters of the function, and the body is an expression. The formal parameters can occur in the body of the function in place of constants or names. The function name and the formal parameters are separated by a single space. There is one space on both sides of the "=". Functions with zero (no) rguments are legal. Note that the formal parameters can overshadow the function names (i.e. op in definition of not in sample input overshadows the function name op), but each function must have a unique name.
Input
The first part of the input contains (less than 1000) lines with one function denition each, followed by a single empty line. Forward references (that is, referring to functions dened later in the input) and recursion are legal. The second part of the input contains less than 1000 test expressions. Each test expression is an expresion occupying a single line. Function names and the arguments are always separated by a single space, but there are no extra spaces around parentheses (see sample input). There is an empty line after the last expression. Expressions are to be evaluated by both the lazy and the strict evaluation. You can assume that all function definitions and expressions are syntactically correct, and that the arithmetic built-in functions (add, sub,
mult, div, rem, eq, gt) will always be called with integers only, and no division by 0 occurs. Overows outside the 32-bit integer range are legal and do not require any special treatment (just use the value produced by C, C++, or Java operators +, -, *, /, or %). In strict evaluation, built-in functions evaluate all their arguments too. In lazy evaluation, arithmetic built-in functions always evaluate all their arguments. All lines on the input contain no more than 255 characters including spaces.
Output
The program should produce a table in exactly the following format:
operator lazy_evaluation strict_evaluation
add addlazy addstrict
sub sublazy substrict
mult multlazy multstrict
div divlazy divstrict
rem remlazy remstrict
where each is an integer - how many times op has been executed in lazy evaluation of all expressions, and is the number of evaluations of in strict evaluation. Spaces can occur arbitrarily. If the evaluation of a test expression does not terminate after a total of 2345 function evaluations , you can assume that it is in an innite loop, the program should skip that expression, and do not count it into the totals (omit counting operations both in lazy and strict evaluation of this expression).
Sample Input
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)
Sample Output
operator lazy_evaluation strict_evaluation
add 7 8
sub 4 7
mult 0 1
div 0 0
rem 0 0
