3 Main Features of Curry

3.2 Expressions

A function can be regarded as a parameterized expression with a name. Thus, we begin by explaining what an expression is and how it is used. Most expressions are built from simpler subexpressions, a situation that calls for a recursive, or inductive, definition.

An expression is either a symbol or literal value or is the application of an expression to another expression.

A symbol or literal value is referred to as an atom. For example, numbers and the Boolean symbols “True” and “False” are examples of atoms. Atoms constitute the most elementary expressions. These elementary expressions can be combined to create more complex expressions, e.g., “2 + 3” or “not  True”. The combination is referred to as a function application. Since a function application is a very common activity, it is convenient to denote it as simply as possible. This convenience is obtained to the extreme by writing the two expressions one near the other as in “not  True”. This notation is referred to as juxtaposition.

In the above expressions, the symbols “+” and “not” are operations. Both are predefined in the standard library Prelude. Although conceptually the symbols “+” and “not” are alike, syntactically they differ. The symbol “+” is a infix operator as in the ordinary mathematical notation. Infix operators have a precedence and an associativity so that the expression “2 + 3 * 4” is understood as “2 + (3 * 4)” and the expression “4 - 3 - 2” is understood as “(4 - 3) - 2”. The precedence and associativity of an infix symbol are defined in a program by a declaration. The following declarations, from the prelude, define these parameters for some ordinary arithmetic operations:

infixl 7 *, div‘, mod
infixl 6 +, -
infix  4  <, >, <=, >=

For example, the precedence of the addition and subtraction operators is 6 and their associativity is left. The relational operators have precedence 4 and are not associative. Operators with a higher precedence bind stronger, i.e., the expression “4 < 2 + 3” is interpreted as “4 < (2 + 3)”.

Infix declarations must always occur at the beginning of a program. The precedence of an operator is an integer between 0 and 9 inclusive. The associativity of an operator is either left, denoted by the keyword “infixl” or right, denoted by the keyword “infixr”. Non-associative infix operators are declared using the keyword “infix”.

Most often, an infix operator is any user-defined sequence of characters taken from the set “~!@#$%^&*+-=<>?./|\:”. Alphanumeric identifiers can be defined and used as infix operators if they are surrounded by backquotes, as “‘div‘” and “‘mod‘” in the previous declaration. For example, for any integer value x, the following expression evaluates to x itself.


x ‘div‘ 2 * 2 + x ‘mod‘ 2

Non-infix symbols are prefix. They are applied by prefixing them to their arguments as in “not  True”.

Exercise 1

Define a predicate, read as “factors” and denoted by the infix operator “./.”, that tells whether an integer is a factor of another integer. The predicate should work for every input and 0 should not be a factor of any integer. The operator should be non-associative and have precedence 7. [Browse Answer][Download Answer]

A symbol, whether infix or prefix, can only be applied to values of an appropriate type. As one would expect, the Boolean negation operator can be applied only to a Boolean value. For example, the expression “not  2” is an error. The compiler/interpreter would report that the expression is incorrectly typed. We will discuss types in more detail after presenting data declarations.

The application of an expression to another is a binary operation. The expression that is being applied is referred to as the function of the application. The other expression is referred to as the argument. Thus, in “not  True”, “not” is the function and “True” is the argument. The situation is slightly more complicated for infix operations. The reading of “2 + 3” is that the function “+” is applied to the expression “2”. The result is a function which is further applied to the expression “3”.

Expressions can also be conditional, i.e., depend on the value of a Boolean expression. Such conditional expressions have the form “if b then e_1 else e_2”. The value of this expression is the value of e_1 if b evaluates to True, or the value of e_2 if b evaluates to False. Thus, the value of “if 3>4 then 2*2 else 3*4” is 12.