Value-oriented programming

One of the goals of this course is to give you ways of thinking about how com-puter programs work—such an ability is crucial when you’re trying to understand what a program is going to do when you run it. Without being able to predict a program’s behavior, it is hard, if not impossible, to code up some desired function-ality or (even worse) to understand someone else’s code.

For that reason, this course will spend a significant amount of time developing different models of computation: ways of thinking about how a program executes that can aid you in predicting its behavior. Eventually, we will grow these mod-els of computation to encompass the most complicated features of object-oriented programming in Java, but to get there, we will begin much more humbly, with value-oriented programming.

Intuitively, the idea of value-oriented programming is that the way we run an OCaml expression is to calculate it to a value, which is just the result of a compu-tation. All of the constants of the primitive data types mentioned above ( like ³,

"hello",^true, etc.) are values, and we will see more kinds of values later. Impor-tantly, the value-oriented programming we do in OCaml is pure—the only thing that an expression can do is compute to a value. This means that other kinds of programs, for instance ones that print to a terminal, display some graphics, or oth-erwise have some kind of effects on the world fall outside the realm of OCaml’s

value-oriented programming. It may seem limiting, at first, to restrict ourselves to such “simple” programs, but, as we will see, pure programs are quite expressive.

Not only that, they are also particularly easy to reason about.

Value-oriented programming is already familiar to you from doing arithmetic calculations from math classes, where you “simplify” the expression 1 + 2 to be 3.

As we will see, OCaml generalizes that idea of simplification to more structured kinds of data, but the underlying idea is the same: replace more complex expres-sions by simpler ones.

To make the idea of a programming model more concrete, we first introduce some notation that let us talk about how an OCaml expression reaches an answer.

We write ’hexpi =⇒ hval i’ to mean that the expression hexpi computes to the answer value hval i, a process called evaluation.

The symbol ’=⇒’ is not part of OCaml’s syntax;

it is notation that we use to talk about the OCaml language.

For example:

17 =⇒ 17 2 + 3 =⇒ ⁵

2 + (5 * 3) =⇒ ¹⁷

"answer is "ˆ(string_of_int 42) =⇒ "answer is 42"

true || false =⇒ true

17 + "hello" 6=⇒ this doesn’t compute!

The value of an expression is computed by calculating. For values, there is no more calculation left to do—they are done. For expressions built out of operations, we first calculate the values of the subexpressions and then apply the operation to those results.

Importantly, for value-oriented programs, this idea of computation by evalu-ation scales to arbitrarily complicated expressions. For instance, we can describe the behavior of a call to the^profitfunction (from last chapter) like this:

profit 500 =⇒ ⁴¹⁵²⁰

This notion of evaluation captures the “end-to-end” behavior of an OCaml expression—it says how to compute a final answer starting from a (potentially quite complex) starting expression.

Of course the hardware of a “real computer” doesn’t compute expressions like

profit 500 all in one big step, as the notation =⇒ suggests. Internally the pro-cessor performs many, many tiny steps of calculation to arrive at the final answer, which in this case is ⁴¹⁵²⁰. The details of exactly how that works for a program-ming language like OCaml (or Java) are beyond the scope of this class. When we write^{profit 500}=⇒ 41520we are giving an abstract model of how the program computes; the abstraction hides most of the details.

Nevertheless, it will sometimes be useful to think about smaller steps of com-putation performed by the program, so that we can imagine how the computer will arrive at a simple answer value like ⁴¹⁵²⁰ starting from a complex

expres-sion like^{profit 500}. We will distinguish the “large step” evaluation indicated by

’=⇒’ from this new “small step” evaluation by writing the latter using the notation

’7−→’. The difference is that the 7−→ arrow will let us talk about the intermediate stages of a computation. For example:

(2 + 3) * (5 - 2)

7−→ ⁵ * (5 - 2) because^{2 + 3}7−→⁵

7−→ ⁵ * 3 because^{5 - 2}7−→³

7−→ ¹⁵

As indicated in the example above, for the purposes of this course, we will assume that the operations on the primitive types ^int, ^string, and ^bool do the

“expected thing” in one step of calculation. (Though in reality, even this hides many details about what’s going on in the hardware.)

The =⇒ and 7−→ descriptions of evaluation should agree with one another in the sense that a large step is just the end result of performing some number of smalls steps, one after the other. The example above shows how we can justify writing^{(2 + 3}) * (5 - 2)=⇒15because the expression^{(2 + 3}) * (5 - 2) sim-plifies to¹⁵after several 7−→ steps.

Here is another example, this time using boolean values:

true || (false || not true)

7−→ true || (false || false) because^{not true}7−→false

7−→ true || false because^{false || false}7−→false

7−→ true because^{true || false}7−→true

if

-

-

OCaml’s^if-^then-^elseconstruct provides a useful way to choose between two dif-ferent result values based on a boolean condition. Importantly, OCaml’s^ifis itself an expression,¹ which means that parentheses can be used to group them just like any other expression. Here are some simple examples of conditional expressions:

if true then 3 else 4

(if 3 > 4 then 100 else 0) + 17

Because OCaml is value oriented, the way to think about ^if is that it chooses one of two expression to evaluate. We run an ^if expression by first running the boolean test expression (which must evaluate to either ^trueor^false). The value computed by the whole^if-^then-^elseis then either the value of the^thenbranch or the value of the^elsebranch, depending on whether the test was^trueor^false.

1It behaves like the ternary ? : expression form found in languages in the C family, including Java.

For example, we have:

(if 3 > 4 then 5 + 1 else 6 + 2) + 17

7−→ ^(if false then 5 + 1 else 6 + 2) + 17

7−→ ^{(6 + 2) + 17} because the test was^false 7−→ ^{8 + 17}

7−→ ²⁵

Note: Unlike C and Java, in which^ifis a statement form rather than an expression form, it does not make sense in OCaml to leave off the ^elseclause of an^if expression. (What would such an expression evaluate to in the case that the test was^false?) Moreover, since either of the expressions in the branches of the ^ifmight be selected, they must both be of the same type.

Here are some erroneous uses of^if:

if true then 3 (* BAD: no else clause *) if false then 3 else "hello" (* BAD: branch types differ *)

Note that becauseif-then-elseis an expression form, multipleif-then-elses can be nested together to create a “cascading” conditional:

if 3 > 4 then "abc"

else if 5 > 4 then "def"

else if 7 > 6 then "ghi"

else "klm"

This expression evaluates to"def".