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 || 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 simplified 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-defined 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: ( function arg1 . . . argN ), where function 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, false 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 false.
User-defined functions are defined using the following syntax: function 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) arguments 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.