1.1.1 Subexpression Evaluation and Continuations🔗ℹ

Some simplifications require more than one step. For example:

4 - (1 + 1) → 4 - 2 → 2

An expression that is not a value can always be partitioned into two parts: a redex (“reducible expression”), which is the part that can change in a single-step simplification (highlighted), and the continuation, which is the evaluation context surrounding the redex. In 4 - (1 + 1), the redex is (1 + 1), and the continuation is 4 - [], where [] takes the place of the redex as it is reduced. That is, the continuation says how to “continue” after the redex is reduced to a value.

Before some expressions can be evaluated, some or all of their sub-expressions must be evaluated. For example, in the expression 4 - (1 + 1), the use of - cannot be reduced until the subexpression (1 + 1) is reduced. Thus, the specification of each syntactic form specifies how (some of) its sub-expressions are evaluated and then how the results are combined to reduce the form away.

The dynamic extent of an expression is the sequence of evaluation steps during which the expression contains the redex.

1.1.2 Tail Position🔗ℹ

An expression expr1 is in tail position with respect to an enclosing expression expr2 if, whenever expr1 becomes a redex, its continuation is the same as was the enclosing expr2’s continuation.

For example, the (1 + 1) expression is not in tail position with respect to 4 - (1 + 1). To illustrate, we use the notation C[expr] to mean the expression that is produced by substituting expr in place of [] in some continuation C:

C[4 - (1 + 1)] → C[4 - 2]

In this case, the continuation for reducing (1 + 1) is C[(4 - [])], not just C. The requirement specified in the first paragraph above is not met.

In contrast, (1 + 1) is in tail position with respect to if 0 == 0 | (1 + 1) | 3 because, for any continuation C,

C[if 0 == 0 | (1 + 1) | 3] → C[if #true | (1 + 1) | 3] → C[1 + 1]

The requirement specified in the first paragraph is met. The steps in this reduction sequence are driven by the definition of if, and they do not depend on the continuation C. The “then” branch of an if form is always in tail position with respect to the if form. Due to a similar reduction rule for if and #false, the “else” branch of an if form is also in tail position.

Tail-position specifications provide a guarantee about the asymptotic space consumption of a computation. In general, the specification of tail positions accompanies the description of each syntactic form, such as if; subexpressions of a form are not in tail position unless documented otherwise.

1.1.3 Multiple Return Values🔗ℹ

A Rhombus expression can evaluate to multiple values, to provide symmetry with the fact that a function can accept multiple arguments.

Most continuations expect a certain number of result values, although some continuations can accept an arbitrary number. Indeed, most continuations, such as [] + 1, expect a single value. The continuation

block:

let (x, y) = []

body

expects two result values; the first result replaces x in body, and the second replaces y in body. The continuation

block:

[]

1 + 2

accepts any number of result values, because it ignores the result(s).

In general, the specification of a syntactic form indicates the number of values that it produces and the number that it expects from each of its sub-expressions. In addition, some functions (notably values) produce multiple values, and some functions (notably call_with_values) create continuations internally that accept a certain number of values.

1.1.4 Top-Level Variables🔗ℹ

Given

then an algebra student simplifies x + 1 as follows:

Rhombus works much the same way, in that a set of top-level variables (see also Variables and Locations) are available for substitutions on demand during evaluation. For example, given

def x = 10

then

x + 1 → 10 + 1 → 11

In Rhombus, the way definitions are created is just as important as the way they are used. Rhombus evaluation thus keeps track of both definitions and the current expression, and it extends the set of definitions in response to evaluating forms such as def.

Each evaluation step, then, transforms the current set of definitions and program into a new set of definitions and program. Before a def can be moved into the set of definitions, its expression (i.e., its right-hand side) must be reduced to a value. (The left-hand side is not an expression position, and so it is not evaluated.)

Using def again, a program can change the value associated with an existing top-level variable:

1.1.5 Objects and Imperative Update🔗ℹ

In addition to def for imperative update of top-level variables, various functions and operators enable the modification of elements within a mutable compound data structure. For example, [] with := modifies the content of an array.

To explain such modifications to data, we must distinguish between values, which are the results of expressions, and objects, which actually hold data.

A few kinds of objects can serve directly as values, including booleans, #void, and small exact integers. More generally, however, a value is a reference to an object stored somewhere else. For example, a value can refer to a particular array that currently holds the value 10 in its first slot. If an object is modified via one value, then the modification is visible through all the values that reference the object.

In the evaluation model, a set of objects must be carried along with each step in evaluation, just like the definition set. Operations that create objects, such as Array, add to the set of objects:

The distinction between a top-level variable and an object reference is crucial. A top-level variable is not a value, so it must be evaluated. Each time a variable expression is evaluated, the value of the variable is extracted from the current set of definitions. An object reference, in contrast, is a value and therefore needs no further evaluation. The evaluation steps above use ⟨o1⟩ for an object reference to distinguish it from a variable name.

An object reference can never appear directly in a text-based source program. A program representation created with Syntax.make, however, can embed direct references to existing objects.

1.1.6 Garbage Collection🔗ℹ

See Memory Management for functions related to garbage collection.

In the program state

evaluation cannot depend on ⟨o2⟩, because it is not part of the program to evaluate, and it is not referenced by any definition that is accessible by the program. The object is said to not be reachable. The object ⟨o2⟩ may therefore be removed from the program state by garbage collection.

A few special compound datatypes hold weak references to objects. Such weak references are treated specially by the garbage collector in determining which objects are reachable for the remainder of the computation. If an object is reachable only via a weak reference, then the object can be reclaimed, and the weak reference is replaced by a different value (typically #false).

As a special case, a fixnum is always considered reachable by the garbage collector. Many other values are always reachable due to the way they are implemented and used: A character is always reachable, and == characters are always ===. Similarly, PairList[], #true, #false, Port.eof, and #void are always reachable. Values produced by #%literal remain reachable when the #%literal expression itself is reachable.

1.1.7 Function Calls and Local Variables🔗ℹ

Given

an algebra student simplifies f(7) as follows:

The key step in this simplification is to take the body of the defined function f and replace each x with the actual value 7.

Rhombus function calls work much the same way. A function is an object, so evaluating f(7) starts with a variable lookup:

If a variable like x is made mutable, however, the value associated with the variable can be changed in the body of a function by using :=, as in the example fun (mutable x): x := 3; x. Since the value associated with a mutable argument variable x should be able to change, we cannot just substitute the value in for x when we first call the function.

Instead, a new location is created for each variable on each function call. The argument value is placed in the location, and each instance of the variable in the function body is replaced with the new location:

A location is the same as a top-level variable, but when a location is generated, it (conceptually) uses a name that has not been used before and that cannot be generated again or accessed directly.

Generating a location in this way means that := evaluates for local variables, including argument variables, in the same way as for top-level variables, because the local variable is always replaced with a location by the time the := form is evaluated:

The location-generation and substitution step of function call requires that the argument is a value. Therefore, in (fun (mutable x): x + 10)(1 + 2), the 1 + 2 subexpression must be simplified to the value 3, and then 3 can be placed into a location for x. In other words, Rhombus is a call-by-value language.

Evaluation of a local-variable form, such as

block:

let mutable x = 1 + 2

expr

is the same as for a function call. After 1 + 2 produces a value, it is stored in a fresh location that replaces every instance of x in expr.

1.1.8 Variables and Locations🔗ℹ

A variable is a placeholder for a value, and expressions in an initial program refer to variables. A top-level variable is both a variable and a location. Any other variable is always replaced by a location at run-time—conceptually, even in the case of variables that are not mutable. Thus, evaluation of expressions involves only locations. A single local variable (i.e., a non-top-level, non-module-level variable), such as an argument variable, can correspond to different locations during different calls.

For example, in the program

def y = (block: let x = 5; x) + 6

both y and x are variables. The y variable is a top-level variable, and the x is a local variable. When this code is evaluated, a location is created for x to hold the value 5, and a location is also created for y to hold the value 11.

The replacement of a variable with a location during evaluation implements Rhombus’s lexical scoping. For the purposes of substituting xloc for x, all variable bindings must use distinct names, so no x that is really a different variable will get replaced. Ensuring that distinction is one of the jobs of the macro expander; see Syntax Model. For example, when an argument variable x is replaced by the location xloc, it is replaced throughout the body of the function, including any nested fun forms. As a result, future references to the variable always access the same location.