Lazy and Strict Evaluation

Time limit1sMemory limit128 MB

Summary

Given function definitions in a small Lisp-like language, count how many times each arithmetic operation runs under lazy (memoized) versus strict evaluation, skipping non-terminating tests.

Level: Medium7 of 10
Topics: Implementation, Recursion, Simulation, Dynamic programming
Solved: No attempts yet

Problem

Most programming languages use strict evaluation: when a function is called, the argument expressions are evaluated first and the resulting values are passed to the function. This is not the only strategy. Some languages perform lazy evaluation for certain operators (for example, && and || in C++ evaluate only as many arguments as are needed to determine the result).

We study a small expression language and count how often each arithmetic operation runs under lazy and strict evaluation.

Expressions. An expression is one of:

a constant: a signed 32-bit integer, e.g. 3, 0, -2, 123;
a name: the name of a built-in or user-defined function; a name is a word of up to 32 lowercase English letters, e.g. f, add;
a function call of the form (function arg1 ... argN), where function is an expression that evaluates to a function of N arguments and arg1 ... argN are expressions; e.g. (f 3 5) or (add 2 (add 1 2)).

Evaluation rules.

A constant evaluates to itself.
A name evaluates to the function it denotes.
A function call is evaluated as follows:
- Under lazy evaluation, the function expression is evaluated first, then its body is evaluated with each formal parameter bound to the expression supplied as the matching argument. An argument expression is evaluated only when its value is actually needed, and at most once: once evaluated, its value replaces every occurrence of that parameter (memoization).
- Under strict evaluation, every expression is evaluated first (the function expression to a function, the arguments to values), and then the body is evaluated with each formal parameter replaced by the corresponding argument value.

Built-in functions (each takes two arguments):

function	result
`add x y`	$x + y$
`sub x y`	$x - y$
`mult x y`	$x \times y$
`div x y`	integer division (C/C++/Java `/`)
`rem x y`	remainder (C/C++/Java `%`)
`true x y`	$x$ (always the first argument)
`false x y`	$y$ (always the second argument)
`eq x y`	`true` if $x$ and $y$ are the same constant, otherwise `false`
`gt x y`	`true` if $x > y$ , otherwise `false`

Because eq and gt return the functions true/false, booleans double as two-way selectors.

User-defined functions use the syntax name arg1 ... argN = body, where arg1 ... argN are distinct words (up to 32 lowercase letters) — the formal parameters — and body is an expression in which the parameters may appear wherever a constant or a name may appear. A function may take zero arguments. Formal parameters may shadow function names, but every function name is unique.

Argument evaluation of built-ins. Under strict evaluation every built-in evaluates all of its arguments. Under lazy evaluation the built-ins add, sub, mult, div, rem, eq, gt still evaluate both arguments, while true and false evaluate only the single argument they return.

Overflow and division. All arithmetic is on signed 32-bit integers and wraps around exactly as the C/C++/Java operators +, -, *, /, % would; div and rem truncate toward zero. No division by zero ever occurs.

Non-termination. For each test expression, if either the lazy or the strict evaluation performs more than $2345$ function evaluations without finishing, treat that expression as an infinite loop: skip it entirely and add none of its operation counts, for either mode.

Input

The input has two parts.

The first part lists fewer than $1000$ function definitions, one per line, followed by a single empty line. Forward references (referring to a function defined later) and recursion are allowed.

The second part lists fewer than $1000$ test expressions, one per line, followed by a single empty line. Function names and arguments are separated by single spaces, with no extra spaces around parentheses. Every expression is evaluated both lazily and strictly.

All definitions and expressions are syntactically correct; the arithmetic built-ins are always applied to integers only, and no division by zero occurs. Every line contains at most $255$ characters.

Output

Print exactly six lines counting how many times each arithmetic operation is executed across all test expressions that are not skipped.

The first line is the header operator lazy strict. Each of the next five lines has the form op lazy strict, where op is one of add, sub, mult, div, rem (in this order), lazy is the total number of executions of op under lazy evaluation, and strict is the total under strict evaluation. Tokens on every line are separated by single spaces:

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

Only these five arithmetic operations are counted; true, false, eq, and gt are never counted.

Examples3

Example 1

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)

Expected output

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

Example 2

Input


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

Expected output

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

Example 3

Input


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

Expected output

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