Ch.6 Introduction to ML programming

§ 6.14. Left-to-right applicative order evaluation

To write a program that manipulate states, it is necessary to fix the order of execution of each part of the program. In a functional language, where a program is a composition of expression, program execution corresponds to obtain the value of an expression. This process is called evaluation of an expression. In ML, expressions are evaluated in the following order.

  1. The same level sub-expressions are evaluated from left to right. For example, (power 2) (power 2 2) is evaluated by first evaluating (power 2) to obtain a function that computes power of 2 and then (power 2 2) is evaluated to obtain 4, and finally the power 2 function is applied to 4 to yield 14.

  2. A sequence of declarations are evaluated in the order of the declarations.

  3. The body of a function is not evaluated until the function is applied to an argument.

ML also provide the following syntax to control evaluation order.

expr  ::=
|(expr;;expr)    (sequential evaluation)

(expr1 ;exprn) is evaluated by evaluating expr1 through exprn sequentially, and yields the value of the last expression exprn.

By manipulating reference types in the evaluation order, an imperative operation can be written as a function. For example, a function that generate a new name by maintaining a mutable state is defined as follows.

fun makeNewId () =
    val cell = ref 0
    fun newId () =
        val id = !cell
        (cell := id + 1; id)