An atomic expression is the simplest expression consisting of a value or an item label. Such expressions are called atomic because they cannot be reduced to a simpler form and have no identifiable parts. Examples of atomic expressions include:

 1          // Value of 1 in base 10
-16         // Value of -16 in base 10
21111     // Value of 15 in base 2
123e2       // Value of 12300 in base 10
21111e1   // 11110 in base 2

'a'      //Character a
a        //Item named a
"Hello"  //String value
Hello    //Item named Hello
true // Boolean true value

The examples shown demonstrate several mechanisms for specifying atomic items ranging from number values and string literals to item names.

An item label used as an expression refers to the item it names. Thus, the type associated with an item label is the type of its item’s declaration. Because each item must be declared and each declaration includes a type, the type of a declared item is always known.

The type associated with a literal value is discussed extensively in Chapter 4. For now it is sufficient to understand that a literal’s type is its most restrictive legal type. For example, the number 3 is an element of several types, including complex, real, and posreal. When appearing in a specification, its type is posint because no subtype of posint contains 3. However, when performing type checking, 3 can be treated as posint or any of its supertypes.

A function application is simply the instantiation of a function with a collection of actual parameters. For example:

cos(x)

is the application of the cosine function to an item, x.

Function applications are specified using the following form:

f(e0,e1,e2,...,en)

where f is the name of an item whose type is a function and e₀ through e_n are expressions representing the function’s actual parameters; e_k may be any expression of the same type or a subtype of its associated formal parameter in the definition of f. Thus, actual parameters may be function applications, sequence references, literals, or any other expression satisfying type conditions. Examples of function applications include:

inc(1)           // Increment the value 1
add(1,2)         // Add the values 1 and 1
inc(x)           // Increment the value of x
add(1,inc(x))    // Add the value 1 to inc(x)

Functions of a single argument are frequently referred to as unary functions, and unary functions whose return type is boolean are referred to as predicates. Functions of two arguments are frequently referred to as binary functions, while binary functions whose return type is boolean are referred to as relations.

Rosetta function application is lazy and defined using curried function semantics. Curried function semantics turns multi-parameter functions into a sequence of unary function applications. For example:

add(1,inc(x)) == (add(1))(inc(x))

The application of the two-argument add function to its first argument results in a unary function that adds 1 to its argument. When this result is applied to inc(x), it adds one to the result of the function application. It is perfectly legal to partially specify function arguments. Specifically, the following definition of inc can be perfectly legal:

inc == add(1)

The inc function that increments its argument is equivalent to the add function with one argument instantiated with one. Currying and function evaluation will be explained later. For now one need only understand that function applications are applications of function items to formal parameters and that curried functions are allowed.

The type of a function application whose formal parameters are of the correct type is the return type specified in its declaration. If the formal parameters are not of the correct type, the function application’s type cannot be determined and it is not soundly typed. Consider a simple function declaration for an increment function:

inc(x::natural)::natural is x+1;

Legal applications of inc include:

inc(1)
inc(inc(1))
inc(2+3)

In each case, the formal parameter to inc can be determined to be a subtype of natural. Thus, the type of each application is natural, the type specified by inc’s declaration. In contrast, illegal applications of inc include:

inc('a')
inc(-1)
inc([1,2,3])

In each case, the formal parameter is not a subtype of natural, no type can be inferred, and the application is not well-typed.

An operator application is a special syntax for function application. For example:

x + y // add x to y

%x       // convert x from boolean to bit
1,2,3    // form a set containing 1,2, and 3

are all operator applications and represent the following function applications:

__+__(x,y)
%__(a)
{__}{1,2,3}

where the function name is obtained by replacing arguments with underscores.

Operators come in four forms, infix, prefix, postfix, and mixfix. The most common operator form is the traditional infix notation used for traditional mathematical operators. Infix operators use the syntax:

x o y

where o is the operator being applied and x and y are arguments to the operator. Examples of infix operations include:

1 + sqrt(x)                    // add 1 to square root of x
x or y                        // boolean disjunction of x and y
x & "⊔error"                 // concatenate x with a literal string

Prefix operations are also quite common and include many mathematical operators such as negation and size. The syntax for prefix operations is:

o x

where o is the prefix operation and x is its argument. Examples of prefix operators include:

-x // negate x
#x // size of x
%x // convert x to a boolean or bit

Mixfix operators are special operators, where the arguments are mixed within the operation. There are several forms of mixfix operations, including formers and if expressions. Formers are used to collect items and form new items representing collections such as sequences and sets. The syntax of a former is generally:

< arglist >

where “<” and “>” represent the name of the former and arglist is a comma-separated collection of arguments. Examples of formers include set formers, sequence formers, and function formers:

 {1,2,3}       // set containing 1,2, and 3
 {*1,1,3*}     // multiset containing 1,1, and 3
 [1,2,3]       // sequence containing 1,2, and 3
 <* (x::integer)::integer *>       // function type or signature
 <* (x::integer)::integer is x+1 *> // anonymous function

The syntax of the function former differs from the set and sequence formers.

Operators are special syntactic forms of function calls. In the case of pre- and postfix operations, the definition of the operation is provided by a unary function. In the case of infix operations, the defining function is binary. Mixfix operations differ based on the number of arguments, but still use a traditional function for their semantic definition. Special function names derived from operator symbols allow definition of operator functions. We take the operator and replace parameters with double underscores to form the name. For example, the names for the % and + operators are defined as follows:

%__       // function name for % operation
__+__     // function name for + operation

The following equivalences define mapping from operators to function applications:

%x  %__(x)
a+b+c  __+__(__+__(a,b),c)

Now operators and functions share a common semantics for evaluation. Such equivalences, called derived forms, allow sharing of semantics across language constructs.

Because operators are special forms for functions, the types associated with operator application are defined in the same manner. Specifically, if operator arguments are of a type compatible with the operator, then the operator application type is obtained from the function signature. Unfortunately, overloading of operators complicates this process substantially, with the number operations introducing significant complexity. Chapter 4 discusses operators over basic types extensively and describes operator type inference.

An if expression specifies choice between values based on a boolean expression. The if expression:

if x>0.3 then 1 else 0 end if

equals 1 if x>0.3 and 0 if it does not. Thus the term:

X′ = if x>0.3 then 1 else 0 end if

asserts that the next value of x equals the result of evaluating the if expression.

Most traditional programming languages use an if statement rather than an if expression. The distinction is that an if expression, like all expressions, has an associated value. An if statement simply orders the application of other statements. This distinction appears in the previous example. It can be rewritten in a form similar to an if statement by lifting the if outside the equality:

if x>0.3 then x′ = 1 else x′ = 0 end if

The net result is the same — an assertion of a value for x in the next state. The formal syntax of the if expression uses the traditional block style more typical of if statements and includes an elseif option:

if c0 then e0
   [[elseif ck then ek]]*
   else en
 end if

In the if expression, all c_j expressions must be of type boolean while all e_j expressions must be of the same type. This assures that the if expression will have a single type. The if expression evaluates to the first e_j associated with a true condition. If no conditions are true, then evaluation results in e_n associated with the else keyword. Although the if expression is block-oriented and reminiscent of imperative languages, it is a true expression and not a statement. Like all expressions, if expressions have values and types.

The most common form of the if expression is the simple if-then-else form:

if ec then et else ef end if;

The rule for evaluating this expression is a simplification of the general semantics. When e_c is true, the expression is equal to e_t. When e_c is false, the expression is equal to e_f. Specifically:

if true then et else ef end if  et

if true then et else ef end if  ef

These two equivalences define two-thirds of the if semantics. The final rule states that when e_t is an expression other than a boolean value, it must be evaluated first.

Understanding the elseif construct is a simple extension of the if expression presented so far. The following expression:

x′ = if x>0 then 1
       elseif x<0 then -1
       else 0
     end if

is equivalent to:

x′ = if x>0 then 1
       else if x<0 then -1
              else 0
            end if;
    end if;

Applying the previous rules to this form results in the expected behavior. If x>0 the expression is equal to 1. If x<0 then the expression is equal to -1. Otherwise the expression is equal to 0.

The if expression must be viewed like all other operators as a function with an associated type and value. The value is determined by evaluating one of the two expressions based on a boolean condition. Again, the if expression does not define paths or sequences of instructions in a Rosetta specification.

if x=1 then f(x) else g(x) end if;

if p(x) then f(x)
  elseif q(x) then g(x)
  else h(x)
end if;

The type of an if expression is derived from the sub-expressions defined in the then and else clauses. The conditional expression must be of type boolean and the then and else expressions must be of the same type. If these conditions hold, the type of the if expression is the type of the then and else expressions. When elseif clauses are present, they must share the type of the then and else clauses. The following if expression defines a signumm, or sign, operation:

if x >= 0 then 1 else -1 end if;

x >= 0 is a boolean expression, thus the type of the if expression is the common type of 1 and -1, or integer. It can be used wherever an integer is allowed. The following forms are legal uses of this expression:

 (if x >= 0 then 1 else -1 end if) + 1;
 sgn(x::integer)::integer is if x>= 0 then 1 else -1 end if;

In contrast, the following forms are not legal uses:

 s(if x >=0 then 1 else -1 end if)
 (if x >=0 then 1 else -1 end if) and 1

In the first case, sequence access must use a natural value. Because the if expression is of type integer, there is no guarantee that when evaluated the result can be used to access a sequence element. In the second case, and expects bit arguments.

Although the if expression can produce a value 1::bit, it is not guaranteed to produce a bit.

facet mux(i0,i1,c:: input bit; z:: output bit)::state_based is
begin
  if c=0 then z'=i0 else z' = i1 end if;
end facet mux;

facet mux(i0,i1,c:: input bit; z::output
bit)::state_based is begin
  z'=if c=0 then i0 else i1 end if;
end facet mux;

It should be noted that if an if expression’s type is determined to be top, it is virtually useless as a specification expression. If a system is to be well-typed, the only place such an expression can be used is where a top is expected. Few functions are general enough to operate on top typed arguments.

if true then -1 else 1 end if :: integer

if x<1 then j else -1 end if :: complex

if x=y then j else -j end if :: imaginary

if x>0 then 1
  elseif x=0 then 0
  else -1
end if :: integer

if x>0 then 1
  elseif x=0 then 'a'
  else -1
end if ::  top

A case expression allows selection from among many alternatives based on set membership. The case expression is much like the if expression, but checks to determine if the result of evaluating an expression is contained in a set of items, rather than checking a boolean value. For example:

case x is
 {0,1,2} -> x+1 |
 {3} -> 0
end case;

represents a state transition function for a modulo four counter. If the value of x is in the set {0,1,2}, then the case expression evaluates to x+1. If the value of x is in the set {3}, then the form evaluates to 0. Like the if expression, the case expression evaluates to a value. Assuming that x is the current state and x’ is the next state, the following form defines a mechanism for calculating the next state in a zero to three counter:

x' = case x is
 {0,1,2} -> x+1 |
 {3} -> 0
end case;

The general syntax for a case expression is:

case e is
  s0 -> e0
  [[ | sn-> en]]*
end case;

The case expression evaluates to e_k associated with the first s_k containing the result of evaluating e. If e is not contained in any s_k, then the case expression is bottom. No default case is provided; however, using the type top will result in a default case. Specifically, the top type is defined as the set containing all possible Rosetta values. Thus, any value of e will be an element of top. Specifically:

case x  is
 {0,1,2} -> x+1 |
 {3} -> 0 |
 top -> bottom
end case;

will evaluate to bottom if x is not contained in either the set {0,1,2} or the set {3}. The value bottom is an element of all sets and will commonly be used to represent an error or default case when choices are specified. This case specifies the same behavior as leaving the top case off. An alternate approach specifies a kind of reset behavior when the selection expression is out of range:

case x is
 {0,1,2} -> x+1 |
 {3} -> 0 |
 top -> 0
end case;

In this example, the expression will evaluate to 0 when the selection expression is out of range. A counter using this definition will always reset to 0 when the current state is illegal.

The previous example illustrates several common Rosetta specification techniques that will be examined throughout the remainder of this text. The terms are declarative constructs that must be simultaneously true. Thus, the output value, the next state value, and the state type are constrained concurrently, not sequentially. Both the case and if expressions have values and are not sequencing statements. Finally, the use of the decorated variable, current', denotes the value of current in the next state.

Determining the type of a case expression is identical to determining the type of an if expression. The most common of the possible result expressions is the type of the case expression. Unlike the if expression, there is no requirement on the selection expression. The presence of the top type again assures that a least common supertype is available.

facet counter(clk, reset::input bit;
           value:: output word(2))::state_based is
  current::state;
begin
  state_def: state = word(2);
  next_state: current' = if event(clk) and clk=1
     then if reset=1 then b"00"
             else case current is
               b"00" -> b"01" |
               b"01" -> b"10" |
               b"10" -> b"11" |
               b"11" -> b"00"
             end case
         end if
     else current;
     end if;
  output_ val: value = current;
end facet counter;

case x is
 0,1,2 -> x+1 |
 3 -> 0 |
 top -> 0
end case :: natural

The let expression defines local items and their scopes. The expression:

let pi::real be 3.1415 in
   pi*radius*radius
end let;

evaluates to the area of a circle. The value of pi is defined to be the real value 3.1415 in the scope of the let expression.

The syntax of a let expression is:

let v0 :: T 0 be e0 [[; vn:: Tn be en]]* in
  e
end let;

The let keyword is followed by a declarative section where one or more local items may be defined. The syntax of local item declarations is identical to the syntax of a traditional item declaration except that the keyword is is replaced by the keyword be for readability. Semantically, declarations are identical. Like traditional item declarations, let declarations are defined by specifying a name and type using the type membership operator. The be clause is required and specifies a value for the local item. Within the scope of the let expressions, these items behave as traditional items. Like traditional declarations, multiple items of the same type may be specified using a comma-separated collection of item names in the declaration. Within e, any variable defined in the let declaration section is visible. For example, given area::boolean:

let pi::real be 3.14159 in
  if area then pi*r^2 else 2*pi*r end if
end let;

defines a let expression that either calculates the area or radius of a circle. The let expression declares and defines a local value, pi, that is visible in the if expression used to calculate the indicated value.

Like all Rosetta expressions, the let expression simplifies to a value and has a type. In the previous example, the let expression’s value is the if expression in the context of local variables. The let expression’s type is the type of its encapsulated expression with the types of local variables added to the expression’s context.

Let expressions may be nested in the traditional fashion. In the following specification, the variable x of type T₁ has the associated expression v₁, while y of type T₂ has the expression v₂. Both may be referenced in the expression e:

let x::T1 be v1 in
  let y::T2 be v2 in
    e
  end let
end let;

This expression may also be written as:

let x::T1 be v1; y::T2 be v2 in e end let;

Semantically, the let expression is actually a letrec expression. Languages such as Scheme and Common Lisp provide separate let and letrec constructs. A traditional let construct is not recursive. The defined variable cannot be referenced in the expression defining its value. A letrec, traditionally defined as a derived form of the traditional let construct, is recursive and allows such references.

let newx::real be x+dx; newy::real be y+dy in
  update_position(newx,newy)
end let

let (pi::real be 3.14159) in
  if area then pi*r^2 else 2*pi*r end if
end let:: real

Compound expressions are formed from atomic expressions, function applications, operator applications, and if, case, and let expressions by replacing formal parameters with expressions of an appropriate type. If e_k and g_k are legal expressions, then the following forms are examples of legal compound expressions:

e1 o e2        // Infix operator application
o e1              // Prefix operator application
(e1)              // Parenthesized expression
f(e1)             // Application of function f to e1
[inc(e1),3]       // Sequence of inc(e1) and 3
if e1             // If expression
 then e2
 else e3
end if
case e1  of       // Case expression with 3 options
 {e2}-> g2 |
 {e3}-> g3 |
 top -> gtop       // Default case
end case
let v::T be e1 in  // Let expression
e2
end let

Each of these compound expressions assumes that expressions are of a type compatible with their associated formal parameter or position in the expression. For example, the if expression mandates that e₁ be boolean and e₂ and e₃ share a common supertype. If type conditions are met, then these represent templates for legal compound expressions. Because e_k can be compound expressions, arbitrarily complex expressions can be formed through substitutions.

All Rosetta operations fall into one of several classes that define operator precedence, as illustrated in Table 3.1. Parenthesized expressions are of highest precedence followed by type assertions. Prefix, product, sum, and relational operations follow in that order. Function applications and mixfix value and type formers follow next, with equivalence having the lowest precedence. As other operations are defined, they will attempt to assume canonical positions in the precedence table. Parentheses may always be used to specify precedence explicitly rather than relying on precedence rules.

When defined, all operation symbols are assigned to a class and remain in that class regardless of their functional definition. For example, e₁ + e₂ could be redefined to perform a multiplication operation. However, e₁ + e₂ will always have lower precedence as compared to a multiplication operation defined by e₁ * e₂. All binary operations are left associative unless otherwise specified.

Currently Rosetta provides no mechanism for defining precedence of new operations. If users introduce new operator syntax using domain structures, they are required to disambiguate precedence explicitly using parentheses. This is rarely an issue, as new operations are typically introduced using function definitions.