Ch.6 Introduction to ML programming

§ 6.9. Function application syntax

powerUncurry is just like a C function taking a pair of arguments. Unlike C and other procedural languages, ML also allows the programmer to write a function that takes multiple arguments in a sequence like powerCurry. For proper understanding of this feature, let us review function application syntax. In mathematics, function application is written as f(x), but in ML it is written as f x, simply juxtaposing function and its argument.

Let expr be the expressions consisting of constants, variables and function applications. Its syntax is given by the following grammar.

expr  ::=c    (constants)
|x    (variables)
|expr expr (function application)

This grammar is ambiguous in the sequence of function applications. To understand this problem, let us examine familiar arithmetic expressions. Suppose we introduce expr+expr, expr-expr, and expr*expr for integer addition, subtraction and multiplication. Then we can write 10 - 6 - 2 but this expression itself does not determine the order of subtractions. As a consequence, two different results are possible: (10 - 6) - 2 = 2 or 10 - (6 - 2) = 4. As in elementary school arithmetic, ML interprets this as (10 - 6) - 2 = 2. We say that the subtraction associates to the left or is left associative. For anther example, ML interprets 10 + 6 * 2 as 10 + (6 * 2). We say that the multiplication * associates stronger than addition +.

In ML and other lambda calculus based functional languages, there is the following important rule:

function application associates to the left and its associatibity is the strongest

e1 e2 e3  en is interpreted as ( ((e1 e2) e3)  en). For example, powerCurry 2 3 is interpreted as ((powerCurry 2) 3).