Expressions, Values, Environments
An expression evaluates to a value in an environment
The fundamental loop of SML execution is: expression → environment → value.
An expression is anything that can be evaluated: a literal (42), a variable name (x), an arithmetic combination (3 + 4), a function application (f 5), or an if-expression.
An environment is the table of currently bound names (variables → values). When the interpreter sees a name, it looks it up in the environment. Def 1.3 (slides p.200) says declarations bind variables — every val or fun statement adds a new row to the environment.
Evaluation proceeds by replacing each subexpression with its value until only a value remains. A value is a fully evaluated expression: a literal, a tuple of values, or a function (which is itself a value — SML evaluates functions to closures).
Examples:
- 3 + 4 — evaluate 3 to 3, 4 to 4, then apply + → 7.
- (1, 2 + 3) — evaluate 2 + 3 first → 5, then build the pair (1, 5).
Evaluation is call-by-value: function arguments are evaluated before the function body runs. This makes evaluation deterministic and predictable.
- 0.0sSML: Parsing and Evaluating 1 + 2 * 3
- 1.0sSource expression 1 + 2 * 3 at the top.
- 1.8sAn arrow labelled parse takes us to the AST.
- 2.4sAST: + has children 1 and *; * has children 2 and 3.
- 4.4sHighlight the * subtree: it binds tightest (precedence).
- 4.8sEvaluate 2 * 3 = 6, then collapse that subtree to a leaf.
- 6.0sThe tree now has + with leaves 1 and 6.
- 7.7sHighlight the + node and compute 1 + 6 = 7.
- 9.0sResult is 7. Parse + evaluate together produce the answer.
3 + 4 evaluate to in SML?(1, 2 + 3), the subexpression 2 + 3 is evaluated ___ before the pair is built.