|
The expression “<tt>double 1</tt>” is replaced by <tt>1+1</tt>. The latter can be replaced by <tt>2</tt> if we interpret the operator “<tt>+</tt>” to be defined by an infinite set of equations, e.g.,<tt>1+1 = 2, 1+2 = 3</tt>, etc. In a similar way, one can evaluate nested expressions (where the subexpression to be replaced are quoted):
'double (1+2)' → '(1+2)'+(1+2) → 3+'(1+2)' → '3+3' → 6
There is also another order of evaluation if we replace the arguments of operators from right to left:
'double (1+2)' → (1+2)+'(1+2)' → '(1+2)'+3 → '3+3' → 6
In this case, both derivations lead to the same result. This indicates a fundamental property of declarative languages, also termed referential transparency: the value of a computed result does not depend on the order or time of evaluation due to the absence of side effects. This simplifies the reasoning about and maintenance of declarative programs.
Obviously, these are not all possible evaluation orders since one can also evaluate the argument of double before applying its defining equation:
double '(1+2)' → 'double 3' → '3+3' → 6
In this case, we obtain the same result with less evaluation steps. ...
In this case, we obtain the same result with less evaluation steps. This leads to questions about appropriate evaluation strategies, where a strategy can be considered as a function that determines, given an expression, the next subexpression to be replaced: which strategies are able to compute values for which classes of programs? As we will see, there are important differences in case of recursive programs. If there are several strategies, which strategies are better w.r.t. the number of evaluation steps, implementation effort, etc? Many works in the area of functional logic programming have been devoted to find appropriate evaluation strategies. A detailed account of the development of such strategies can be found in [38]. In the following, we will survey only the strategies that are relevant for current functional logic languages.
AlthoughAs functional languages arelike based on the lambda calculus that is purely based on function definitions and applications, modern functional languages offer more features for convenient[[haskell (programming. Inlanguage)|Haskell]] particulardo, theyCurry supportsupports the definition of algebraic data types by enumerating their constructors. For instance, the type of Boolean values consists of the constructors <tt>True</tt> and <tt>False</tt> that are declared as follows:
False that are declared as follows:
data Bool = True | False
| 