Rosetta’s function definition and evaluation capability provides function definition and application capabilities and a collection of advanced capabilities for more sophisticated and powerful specifications. Like functions in traditional functional programming languages, Rosetta functions provide a mechanism for defining abstractions of expressions over parameters. Unlike functions in traditional imperative programming languages, Rosetta functions are pure and side-effect free.
A Rosetta function simply reduces to a value derived from its parameters and items defined in its static scope. Actual parameters that Rosetta functions are applied to cannot be altered by the function application, nor can other symbols in the static scope be altered. Each Rosetta function is simply an encapsulated expression defined over its parameters and items in scope. When evaluated, the encapsulated expression simply reduces to a value that replaces the function application. In this sense, Rosetta functions behave more like mathematical functions than functions and procedures from programming languages.
Throughout this chapter, a simple increment function defined over an integer type is used to demonstrate function properties. Its declaration:
inc(x::integer)::integer is x+1;
defines a parameter and its type, and range type, and a defining expression. For any expression, a, when inc(a) appears in a specification, it can be reduced to a+1.
Direct definition using this style is the simplest and most common mechanism for defining functions, but it is not the only mechanism. Like other Rosetta items, functions have labels, types, and values. While the direct definition mechanism defines all three in one syntactic construct, it is possible to define values and types for functions using more flexible techniques. Function variables, unknown constant functions, anonymous functions, and function values are defined by specifying selected aspects of a function item. This enables the system-level designer to describe function properties without providing a complete implementation when details are not known.
Evaluating Rosetta functions is a two-step process of replacing actual parameters with formal parameters and simplifying the resulting expression. Function evaluation allows replacement of functions by their instantiated values in expressions. Further, evaluation of Rosetta functions is lazy and uses a curried function semantics. As will be discussed later in this chapter, evaluating inc(3) involves replacing inc with its definition and instantiating that definition with 3. Informally:
inc(3) == 3+1 == 4
The direct definition approach provides a mechanism for succinctly specifying a signature and optional body for a known function. The format for all direct function definitions is:
f [[ [ variables ] ]]([[ parameters ]]) :: T [[ is e1 | constant ]] [[ where e2 ]] ;
Functions defined directly must include a function name, followed by an optional universally quantified parameter list, a parameter list, and a required type. The parameter list defines formal parameters for the function while the type defines its range. The universally quantified parameter list defines universally quantified parameters whose values are determined by inference mechanisms rather than direct instantiation.
To support defining functions at multiple levels of abstraction, Rosetta provides numerous definitional styles. The definition style used in any function declaration is determined by combination of optional is and where clauses. The is clause specifies that the function is constant and an optional expression defines the function’s value. If the expression is excluded, the keyword constant declares that the function’s value is constant although unknown. The where clause specifies a property that must be satisfied by any value associated with the function, but does not define a specific function. Both where and is clauses may be included in the same function.
We say a function is a variable or constant based on whether its definition can vary within a specification. Like all constants, a constant function is a function whose function value does not change. This implies that, evaluated with the same inputs, the resulting value will always be the same. Variable functions are functions whose value may change, implying that, at different times, evaluation with the same parameters may result in different values, depending on the function’s current value.
For example, var_fun defines a variable function whose value must be evaluated to a number greater than 5 for all inputs:
var_fun(x::integer)::integer where var_fun > 5;
There are any number of definitions that satisfy var_fun:
const_5(x::integer)::integer is 5; sqr_plus_5(x::integer)::integer is x*x+5;
var_fun is a variable function because either const_5 or sqr_plus_5 could be assigned to it and satisfy its constraints. In contrast, const_5 and sqr_plus_5 are constant functions because their function values are fully specified.
Table 6.1 lists the various definitional styles, showing how to identify them and their implications on the functions they define. The following sections define in detail the definitional styles, when they are used, and what implications they have on specifications.
Table 6.1. Styles for direct function definition
Definition Style | is Clause | where Clause | Resulting Function Definition |
|---|---|---|---|
Interpretable | expression | no | Function whose type is known, value is known and is constant |
Uninterpretable |
| no | Function whose type is known, value is unknown and is constant |
Qualified Interpretable | expression | yes | Function whose type is known, value is a known constant, and satisfies the where property |
Qualified Uninterpretable |
| yes | Function whose type is known, value is an unknown constant, and satisfies the where property |
Variable | no | no | Function whose type is known, value is unknown and is not constant |
Qualified Variable | no | yes | Function whose type is known, value is unknown and is not constant, and satisfies the specified where property |
An interpretable Rosetta function is defined by providing a signature followed by an is clause specifying an expression over parameters from the signature and other functions and constants. The signature defines the function name, formal parameters, and a result type. The is clause expression defines how to derive a value for any application of the associated function.
A simple interpretable function is inc for incrementing integers:
inc(x::integer)::integer is x+1;
In this definition, the function signature, inc(x::integer)::integer, is specified followed by an expression indicated by the is keyword, x+1, that defines the calculation performed by the function. The function signature defines a new item that is a function mapping from integer to integer, while the expression defines the actual mapping. Interpreted in the same manner as earlier item definitions, this suggests that inc(x::integer) is an integer whose value is x+1. This intuition is precisely correct — wherever inc(a) appears in a specification, it can be replaced by a+1 with assurance that its evaluation will result in an integer type.
A restriction placed on functions is that the expression following the is keyword must only reference items that are declared in its static scope. For example, the following are legal function declarations:
squared_sum(x,y::integer)::integer is (x+y)^2; area(r::real)::real is pi*r^2; mod_four(i::integer)::integer is if i>=3 then 0 else inc(i); x::integer; addx(y::integer)::integer is x+y;
The squared_sum definition is legal because it only references quantities defined in its parameter list. The area function is legal because it references only quantities defined in its parameter list and the constant pi. The mod_four function is legal because it references only quantities defined in its parameter list and the function definition inc provided earlier. The addx function is legal if x::integer occurs in its static scope. If the declaration of x did not occur in the static scope, the function declaration would be illegal.
Interpretable functions are the most commonly defined Rosetta functions and are so named because they can be interpreted for any parameter values. Specifically, given an interpretable function definition and actual parameters of the appropriate type, the function can always be evaluated with respect to those parameters.
Like any Rosetta definition, inc is an item with an associated type and value. In this case, the type of inc is a function defining a mapping from one integer value to another integer value. The encapsulated expression x+1 along with parameter declarations is the function value associated with the function. Like any other Rosetta declaration, the value of inc must be an element of its type. Because inc is a mapping from integer to integer and the type of the expression x+1 is integer in the context of the parameter declaration x::integer, the function value is of the appropriate type.
Literally, what the inc function definition states is that anywhere in the defining scope inc(a) can be replaced by a+1 for any arbitrary integer values. Whenever any function appears in an expression in a fully instantiated form, it can be replaced by the result of substituting formal parameters with actual parameters and evaluating the resulting expression. Specifically, if the function instantiation inc(3) appears in an expression, it can be replaced by the expression 3+1 and simplified to 4. For this reason, Rosetta functions are frequently viewed simply as encapsulations of expressions.
When a function’s value is constant, it is the function value, not the value resulting from applying a function, that is constant: inc is a constant function even though its return value varies. Wherever inc(a) appears in a specification, it will always be replaced by a+1 and never by another expression over a.
An example of an interpretable function definition is the classical definition of factorial:
Example 6.1. Interpretable Function Definition and Evaluation
fact(x::natural)::natural is if x=0 then 1 else x*fact(x-1) end if;
Because all interpretable functions can be evaluated over appropriate typed actual parameters, fact(2), we can provide a naive but useful demonstration of function evaluation. Evaluating fact(2) involves replacing the formal parameter x with the actual parameter 2 in the function expressing and simplifying:
1. fact(2) 2. ==if 2=0 then 1 else 2*factorial(2-1) end if 3. == 2*factorial(1) 4. == 2*if 1=0 then 1 else 1*factorial(1-1) end if 5. == 2*1*factorial(0) 6. == 2*1* if 0=0 then 1 else 2*factorial(0-1) end if 7. == 2*1*1 8. == 2
Other than using classical definitions for multiplication and subtraction to reduce numerical expressions, the only operations used to perform this calculation are substitution and instantiation.
A semantically precise definition of function evaluation will be provided later. However, this simple heuristic approach of replacing formal parameters with actual parameters and simplifying the result serves as an excellent starting point for understanding function evaluation.
Example 6.2. Interpretable Function Definitions
The opcode function pulls the first 4 bits from an input word. Such a function might be used to specify part of a decode operation in a CPU model:
opcode(x::word(16))::word(4) is x sub [0..3];
opcode is legally defined because it only references its formal parameters.
The circumference function defines the circumference of a circle in the classical manner. One way to define this is to provide a local definition for the value pi within the function definition:
circumference(r::real)::real is let pi::real be 3.14159 in pi*r^2.0 end let;
In this definition, the let expression defines a local value for pi that is constant over its scope. This function is legal because it only refers to values defined locally or its parameters.
An alternative definition uses the built-in definition of pi provided in the Rosetta prelude:
circumference(r::real)::real is pi^2.0;
This definition is also legal because the definition of pi is known to be constant due to the is clause used in its definition.
Finally, the definition of add for complex values might be specified as:
add(x,y::complex)::complex is
(rp(x)+rp(y))+(ip(x)+ip(y))*j;
This definition is again legal because it refers to constant values (j) and constant functions and operators (rp, ip, +, and *).
Adding a where clause to an interpretable function adds a constraint that must be satisfied by the function definition. Such functions are qualified interpretable functions because they are interpretable, but their definition is qualified by the requirement that they must satisfy their associated where clause property.
The definition syntax for qualified interpretable functions is identical to interpretable functions with the addition of a where clause following the function definition. The keyword where defines a boolean valued expression that must be true for any function definition. This boolean expression is defined over function parameters and constants defined in the scope of the definition. All parameter names are implicitly universally quantified in the where expression.
The increment function defined previously can be qualified using a where clause as follows:
inc(x::integer)::integer is x+1
where x>=0 implies inc(x)>0;
In this case, the where clause defines a correctness condition for the function definition specifying that whenever its actual parameter is greater than or equal to zero, interpreting the function results in a value greater than zero. Because all parameters are universally quantified, the where clause must be true for any instantiation of the function. The following examples are correct function definitions:
squared_sum(x,y::integer)::integer is (x+y)^2
where squared_sum(x,y)>=0;
area(r::real)::real is pi*r^2
where r>0 implies area(r)>=0;
mod_four(i::integer)::integer is
if i>=3 then 0 else inc(i)
where mod_four(i)>=0 and mod_four(i)=<3;
In each case, the where clause can be verified with respect to the interpretable function. If the where clause cannot be satisfied by the function definition, then the function is illegal. The following example is an incorrect function definition:
inc(x::integer)::integer is x+1
where inc(x)>0;
In this case, the definition of inc cannot be used to verify that all applications are greater than zero. On the contrary, counterexamples are easily found when the argument is negative.
Specifying assertions over a function definition using the where clause is important for verification tools that use its definition. Whenever the inc definition is used in a specification, the where clause can be assumed true. This can be used to assist verification tools by providing facts that need not be derived. Of course, properties proved to be true can be used in this manner. This behavior effectively caches verification results for use in later verification efforts.
Example 6.3. Qualified Interpretable Function Definitions
The factorial function can be defined with an associated where clause that asserts its value must be greater than 0:
fact(x::natural)::natural is if x=0 then 1 else x*factorial(x-1) end if where fact(x)>0;
This definition differs from the previous definition because the where clause must be satisfied. During type checking and static analysis, the specifier can attempt to verify the where clause using type checking, theorem proving, or model checking techniques.
The where clause can also be used by functions referencing fact. Given a qualified definition of inc:
inc(x::integer)::integer is x+1 where x>=0 implies inc(x)>0;
the where clause can be verified. When evaluated with a fact application as its argument:
inc(fact(x));
the inc function’s where in combination with the fact function’s where clause allows verification that the result is always greater than 0. By knowing fact(x)>0, it follows quite simply that fact(x)+1 is also greater than zero because the argument is always greater than 0. Such uses of where clauses are exceptionally powerful mechanisms for specifying correctness conditions on functions, terms, facets, and domains.
The constant keyword in conjunction with a function declaration provides a mechanism for defining a new function whose specific value is not known, but is constant. Such functions are uninterpretable because, although constant, their values are not known and cannot be evaluated in the general case. The signature of the function is defined in the same manner as for other directly defined functions, followed by the is keyword, with the is expression replaced by the constant keyword. For example:
addpolyglot(x,y::polyglot)::polyglot is constant;
defines a function, addpolyglot, that takes two items of type polyglot and results in a new item of type polyglot without providing a specific definition for the function. The constant keyword indicates that the value of addpolyglot is a constant even though its actual value is not known. Other functions can now use the addpolyglot function, knowing that addpolyglot(x,y) will always perform the same function in the context of this definition. Any actual function associated with addpolyglot must obey the definitional rules specified previously.
The where keyword is used to add constraints to an uninterpretable function definition without defining the function itself. Used with the constant keyword, constraints can be defined on a constant function usable in other function and facet definitions. Such declarations are referred to as qualified uninterpretable functions. Functions defined in this manner cannot be interpreted in the traditional fashion; however, any instance of the function must obey the constraints. This allows them to be used in analyzing designs. Declaration of qualified uninterpretable functions is identical to uninterpretable functions with the addition of a where clause. For example, the following definition makes the addpolyglot function commutative:
addpolyglot(x,y::polyglot)::polyglot is constant where addpolyglot(x,y) == addpolyglot(y,x);
The defined constraint is simply a boolean valued Rosetta expression defined over the parameters of the function. In this case, the constraint states that the order of arguments to addpolyglot is not significant.
Example 6.4. Defining Abstract Structures
In the definition of an abstract architecture, it is frequently necessary to define operations without defining the specific types operated on or the details of the operation. The following definition provides a mechanism for specifying an operation without significant detail:
manipulate_data([T::Type] x::T)::T is constant where manipulate_data(manipulate_data(x)) == x;
This declaration defines a function, manipulate_data, that must be its own inverse. In this case, we are not specifying the types involved in the operation.
Such functions do not lend themselves to simulation-based analysis, but can be exceptionally useful when defining system requirements before implementation directions are selected. When an implementation for manipulate_data is chosen, design decisions based on the where constraints can be enforced on the function, assuring that early decisions are reflected in the implementation.
Using the constant and where keywords may appear unusual for those accustomed to traditional simulation-style definition languages. The keywords are exceptionally useful when working at high levels of abstraction, where only some of the properties of a function are known. By defining a specific function, too much information may be added to the definition. Using the constant and where keywords allows specification of desired properties or simply the existence of a function without overspecifying its definition. Details can be added later or discovered during the design process while maintaining the original function definition.
When a function is defined with no is clause, no specific value is associated with the function definition. Functions defined in this manner are called variable functions or function variables. For example, the following definition defines a function that maps sequences of integer to a single integer:
fold(s::sequence(integer)) ::integer;
We know that the fold function takes a sequence and generates an integer value, but nothing more. Furthermore, fold is in every sense a traditional variable. Its type is known and fixed while its value may change and cannot be determined by the declaration. The implications of this are that evaluating fold on the same arguments may result in different values as the function’s value changes. While the function’s value may change, its signature cannot. Specifically, fold will always be a function that maps an integer sequence onto an integer within the scope of this definition.
When a function is defined with no is clause and a where clause, no specific value is associated with the function definition, but any value associated with the definition must satisfy the where clause definition. Functions defined in this manner are called qualified variable functions. Like variable functions, qualified variable functions are traditional variables. However, at any time the value associated with a qualified variable function must satisfy the boolean expression specified by the where clause. For example, the following definition defines a traditional cube root function over real values:
cubert(x::real)::real
where cubert(x)^3 == x;
From this definition we know that cubert is a function mapping one real value to another real value. However, without an is clause we do not know what the actual function is. The distinction between this declaration and a variable function declaration is that we know that cubert(x)^3==x for any parameter value. The properties of the qualified variable function are known even when the function value is not. Specifically, we do not know how to calculate the value associated with cubert, but we do know the properties of the evaluated function.
Using a qualified variable function is useful in abstract specification situations, where a function may not be completely defined but properties beyond parameter information and type are needed. The cubert example demonstrates this effectively in that no type condition placed on parameters can provide the same information as provided by the where clause.
Example 6.5. Variable Functions
Variable function definitions declare a function without defining its properties. This can be viewed as defining a function signature. Function signatures from the previous examples include:
fact(x::natural)::natural;
opcode(x::word(16))::word(4);
add(x,y::complex)::complex;
Each signature definition is obtained by simply omitting the is clause from the declaration. Each of these functions is declared, but the specifics of their definition is excluded. Defining function signatures in this manner is an excellent tool for defining abstract system-level properties when only incomplete information is available. Without more information, these variable functions cannot be evaluated.
Example 6.6. Interpretable Functions as Variable Functions
It is possible to use a qualified variable function to provide the same semantics as provided by interpretable functions, by asserting that evaluating the function is equal to the is clause expression. Using this technique, the inc function over integer can be defined as:
inc(x::integer)::integer where inc(x) = x+1;
This definition asserts that any value associated with inc must define a function that, when applied, must result in its argument plus one. The equals sign behaves much like the is keyword in that it provides a definition for the value produced by applying inc. The expression x+1 can be used to define a function value for inc. The distinction between this form of a qualified variable function and an interpretable function is that an interpretable function can always be evaluated by virtue of its definition semantics. This form of a qualified variable function may also be evaluated, but that fact arises from the semantics of the where clause property. Specifically, the property associates a unique value with each instantiation of inc. Other syntactic forms can achieve the same result. Where interpretable functions may always be evaluated, semantic analysis is required if qualified variable functions can be evaluated. This analysis is highly problematic for automated tools and in most cases cannot be performed. Thus, the interpretable function form is provided to define functions that tools can interpret automatically.
Like other Rosetta items, function items have types and values. The direct definition techniques discussed thus far combine the declaration of function items, function types, and function values into a single syntactic construct. However, it is possible to define functions in a manner identical to that for other items by specifying a label, type, and optional value.
Function values, also called anonymous functions, are the values associated with function items and represent an abstract expression defined over a collection of parameters. Function values correspond to abstractions or lambdas in the lambda calculus and lambda expressions in Lisp dialects, ML, and Haskell. Defined by excluding the function name and encapsulating the definition in the function former, function values provide values for functions without associating them with items. The definition:
<* (x::natural)::natural is x+1 *>
defines the function value that serves as the value of inc. The parameter list, return type, and expression are identical to the previous inc declaration, but are enclosed in a function former with no function name. The function is identical to inc in every way, but has no associated name. For example, function values and named functions are evaluated in exactly the same manner:
1. <* (x::natural)::natural is x+1 *>(1) 2. == <* ()::natural is 1+1 *> 3. == 1+1 ::natural 4. == 2 ::natural
In the first evaluation step, x is replaced by 1, resulting in an empty parameter list and an expression with no parameters. The function former delimiters can now be dropped in the second step because the function is nullary. Furthermore, we know that the expression must be the result type of the function. In the third and final evaluation step, the resulting expression is then simplified until it is in normal form, in this case resulting in a natural value.
Anonymous function signatures can also be defined in a similar manner. The definition:
<* (x::natural)::natural *>
is the signature of the function defined previously, but does not associate the signature with a name. This definition is called a function type because it describes a collection of functions all having the same parameter list and result type. The definition:
inc ::<* (x::natural)::natural *>
declares a new item inc whose type is a mapping from two natural to natural. This definition is semantically equivalent to the earlier inc signature definition that used the direct definition style. Specifically:
inc(x::natural)::natural == inc::<*(x::natural)::natural*>
The definition says that inc is of type <*(x::natural)::natural*> or alternatively that inc is a function that maps a natural number to another natural number.
Using the is notation, it is possible to define a function using the standard constant definition notation used for other types. By using a function type and a function value in the standard definition syntax, the following definition results:
inc ::<* (x::natural)::natural *> is <* (x::natural)::natural is x+1*>
This definition is equivalent to the preceding direct definition of inc and semantically defines the direct function definition shorthand. Specifically:
inc(x::natural)::natural isinc ::<* (x::natural)::natural *> is <* (x::natural)::natural is x+1*>
The inc item declaration defines it as a function mapping natural to natural. The is clause associates a function value with the declared function item in the same manner as for other item declarations. Specifically, the is clause asserts that the inc function is equivalent to the function mapping a natural number to its successor by adding one. Because this declaration uses an is clause, inc is a constant function, just as in the earlier definition. Conversely, when the is clause is not present, inc is a variable function.
Although the constant function declaration is equivalent to direct definition, it is highly recommended that direct definition be used for defining functions when the function value does not change. The clumsiness of this definition makes it difficult to read. Furthermore, the direct definition approach is easily recognized as a constant function by language processing tools, making optimization and interpretation simpler.
The formal syntax of the function former used to define anonymous functions and function types is:
<* [[ [ variables ] ]]([[ parameters ]] ) :: T [[ is e1 ]] [[ where e2 ]] *>
where variables is an optional list of universally quantified parameters, parameters is a list of declarations that define formal parameters, T is the result type, e1 is the expression associated with the optional is clause, and e2 is the expression associated with the optional where clause. With the exception of not specifying an item name, the form and semantics of the declaration are identical to those of the direct declaration approach. The notation <* fcn *> is referred to as a function former because it encapsulates expressions with a collection of local symbols to define a function value.
Although Rosetta is not an executable language, an operational semantics for function evaluation is defined. Rosetta functions use curried function and call-by-name semantics, and evaluate lazily. This evaluation style is used in lazy languages such as Haskell, Miranda, and Gopher, allowing Rosetta evaluation to treat equality the same way it is treated in mathematics. In Rosetta, = is equality, not assignment. If two terms are equal, then it should be possible to directly substitute one term for another. This is identical to mathematics and quite natural for specifications. The lazy, call-by-name approach facilitates this feature.
Example 6.7. Anonymous Functions and Function Types
The function signatures specified previously all have equivalent forms using function types. The following definitions:
fact(x::natural)::natural where fact(x)>0; opcode(x::word(16))::word(4) is constant; add(x,y::complex)::complex;
are equivalent to:
fact::<*(x::natural)::natural*> where fact(x)>0; opcode::<*(x::word(16))::word(4)*> is constant; add::<*(x,y::complex)::complex*>;
Like other variables, function variables defined in this manner can be constrained by terms in their declaration context. The following facet declares local versions of the previous functions:
facet demo(v::input complex)::continuous is fact::<*(x::natural)::natural*>; opcode::<*(x::word(16))::word(4)*> is constant; add::<*(x,y::complex)::complex*>; begin t1: forall (x::integer | fact(x) > 0); t2: opcode = <* (x::bitvector(16))::bitvector(4) is x sub[0,..3] *>; t3: add = <* (x,y::complex)::complex is (rp(x)+rp(y)+rp(v)) + (ip(x)+ip(y)+ip(v))*j * > end facet demo;
The term t1 places the same assertion on fact as the where clause used in its original definition. Specifically, it asserts that every application of fact to a value of type integer is greater than 0. Although semantically equivalent, this syntactic form makes it difficult for tools to recognize that the term asserts the same property. The term t2 defines opcode to be a constant function value equivalent to its earlier defined value. Specifically, the function value specified is the same function used in its interpretable definition. Like the previous term, the semantics of this term makes this definition equivalent to the earlier definition. Similarly, it is difficult for tools to recognize this form without some evaluation or static analysis. Finally, the term t3 defines a new concept called a quantity. A non-constant item, namely v, is referenced in its definition. Thus, the actual definition changes over time and is not a constant function or a function value. Such definitions will be explored later and provide an interesting mechanism for specifying simultaneous equations that define a system.
Currying refers to the process of treating any multi-parameter function like a unary function. The Rosetta function f(q,r,s,t) is expanded to its curried form f(q)(r)(s)(t) during evaluation. The curried semantics are quite common and provide a definition that supports partial evaluation and partial instantiation of functions. The technique is particularly powerful when dealing with higher-order functions.
Lazy evaluation implies that expression evaluation occurs only when the expression’s value is needed. In traditional imperative languages, parameters to most operators and functions are evaluated before the operator or function. In Rosetta, this is not the case. Terms are evaluated only when their values are needed. An excellent example is the if expression, where only the expression associated with the result of evaluating the condition is evaluated.
Call-by-name describes the parameter passing mechanism used to evaluate function application. When passing actual parameters to a function, they are not evaluated prior to resolving the function. The actual terms passed as parameters are substituted directly for the parameters inthe function’s associated expression. When the instantiated expression is evaluated, terms that were parameters are evaluated only when their values are needed.
When a complete, interpretable definition exists, repeatedly applying evaluation rules will result in a normal form that is also a value. When an incomplete definition exists, the same process will result in a normal form that is not yet a value. This is one major distinction between a specification language and a programming language. Regardless of whether the result is a value or not, meaningful information results. The normal form is typically simpler and can be used as a partial evaluation result. More importantly, it can be treated as an abstract value that describes a collection of values in abstract interpretation.
Two types of Rosetta functions may always be evaluated — interpretable functions and function values. Anonymous function values defined using an is clause provide an expression that defines the transformation implemented by a function. Thus, an anonymous function value can be evaluated by instantiating its associated expression and simplifying the result. The subset of Rosetta functions defined earlier as interpretable are named because they can always be interpreted. Like anonymous function values, the is clause defines an expression that is instantiated and evaluated. Closer examination reveals that the value associated with an interpretable function is an anonymous function value. Thus, the ability to evaluate function values applied to arguments gives us the ability to define interpretable functions.
Unfortunately, it is not possible to determine if an arbitrary function can be evaluated. Many technically uninterpretable functions defined using the where clause or using facet terms may in fact be interpretable. Rosetta only guarantees that anonymous function values and interpretable functions may be evaluated. Both definitions are easily recognized by the presence of an is clause in their declaration. Without an is clause, it is impossible in to determine if a function can be evaluated.
Evaluating a Rosetta function is a matter of replacing formal parameters with actual parameters in the function-expression and simplifying the resulting expression. The simplest example of function evaluation applies to the add function fully instantiated over literal parameters. A definition of an interpretable add function and an example interpretation result are shown here:
add(x,y::integer)::integer is x+y;
1. add(1,2)
2. == 1+2
3. == 3
In the evaluation, formal parameters are replaced by actual parameters in the add definition and the resulting expression is evaluated.
Closer examination of the instantiation and evaluation process reveals a powerful capability for currying and lazy evaluation that is essential in system-level design. Let us first re-examine the evaluation of the add function just performed in simplified fashion, looking more carefully at the evaluation process:
1. add(1,2)
2. == <* (x,y::integer)::integer is x+y *>(1,2)
3. == <* (y::integer)::integer is 1+y *>(2)
4. == <* ()::integer is 1+2 *>
5. == 1+2 ::integer
6. == 3 :: integer
When evaluating a function, the function item is replaced by its value. In the previous section we showed that every interpretable function item has an associated function value. Here, in step 2, the add item is replaced by its function value whose definition maps two integer parameters onto their sum. In step 3, the formal parameter, x, is replaced by the actual parameter, 1. The formal parameter is eliminated from the signature in this process and the result is a new function of one integer parameter applied to the remaining actual parameter. In step 4, the formal parameter, x, is replaced by the actual parameter, 2, again eliminating the formal parameter.
The function resulting from step 4 is nullary — having no remaining parameters. Its associated expression is fully instantiated and can be removed from the function value former. The empty parameter list is dropped and the function result type is associated with the resulting expression. Generalizing, we have the following rule for any nullary function:
where T is a type and e is an expression. Note that the definition can be used inversely to place an expression in a nullary function. This rule can be further generalized to define an abstraction rule. Given a variable v not free in e, the following rule can be defined:
The right side of the definition is the same, with the left side adding a parameter that is not free in e. What this means is that v does not appear in e unless it is declared somewhere in e. If that is the case, the value of v can have no effect on the evaluation of e and can be dropped during evaluation or added during abstraction.
The previous method for evaluating a multi-parameter function by successively applying the function to each parameter defines a curried function evaluation process, a classical evaluation semantics. It is at the same time simple and exceptionally powerful.
It is interesting to observe that the resulting process produces identical results if the parameters are instantiated in reverse order:
1. add(1,2) 2. == <* (x,y::integer)::integer is x+y *>(1,2) 3. == <* (x::integer)::integer is x+2 *>(1) 4. == <* ()::integer is 1+2 *> 5. == 1+2 ::integer 6. == 3 ::integer
or at the same time:
1. add(1,2) 2. == <* (x,y::integer)::integer isx+y*>(1,2)3. == <* ()::integer is 1+2 *> 4. == 1+2 ::integer 5. == 3 ::integer
This process, called beta-reduction, allows great flexibility in dealing with function evaluation. Not only is the instantiation process simple, it supports currying without enhancement of the function or evaluation definitions. Simply substitute and simplify — a process widely used in mathematics. Note that in subsequent evaluation examples, the nullary function and result type will frequently be dropped for brevity.
Nested functions work identically by applying the replace and simplify approach:
inc(add(4,5))
Rather than evaluating in the traditional style, expand the function definitions first. Using the definitions of inc and add results in the following anonymous function evaluation process:
1. <*(z::integer)::integer is z+1*> (<*(x,y::natural)::natural is x+y*>(4,5)) 2. == <* ()::integer is <* (x,y::natural)::natural is x+y *>(4,5) +1 *> 3. == <* (x,y::natural)::natural is x+y *>(4,5) + 1 ::integer 4. == <* (y::natural)::natural is 4+y *>(5) + 1 ::integer 5. == <* ()::natural is 4+5 *> + 1 6. == 4+5 ::natural + 1 ::integer 7. == 10 ::integer
In step 1, the function instantiations are replaced by their definitions. In step 2, the formal parameter, to inc is replaced by the actual parameter, which in this case happens to be an instantiated function. However, the process is unchanged — replace formal parameters with actual parameters and eliminate them from the signature in each step. In step 3, the function former associated with inc is eliminated, as there are no parameters to that function. Now evaluation turns to the add function, where the process is identical to that performed in the previous example.
The same result occurs regardless of the order of replacement and evaluation. The following process shows a different order resulting in the same result:
1. <* (z::integer)::integer is z+1 *>(add(4,5)) 2. == <* ()::integer is add(4)(5)+1 *> 3. == <*(x,y::natural)::natural is x+y *>(4)(5)+1 ::integer 4. == <* (y::natural)::natural is 4+y *>(5) + 1 ::integer 5. == <* ()::natural is 4+5 *> + 1 ::integer 6. == 4+5 ::natural + 1 ::integer 7. == 10 ::integer
Function evaluation becomes a simple matter of replacement of actual parameters by formal parameters and simplifying. Because this process can be performed in any order and can be stopped at any step, a wide range of function evaluation possibilities become available. Thus far, examples of function evaluation have included only fully instantiated, constant functions. The definition of function evaluation does not preclude designers or tools to evaluate functions partially, either by leaving parameters uninstantiated or by simply halting a simplification process before it completes. As shall be seen, partial evaluation provides for definition and evaluation techniques that directly support high-level specification and analysis.
As noted previously, Rosetta uses a curried function semantics to define evaluation. Thus, every Rosetta function can be expressed as a single argument function. This may seem odd, but it results in an exceptionally simple yet expressive mechanism for defining function evaluation. The addc function:
addc(x,y::integer)::integer is x+y;
can be expressed equivalently as:
addc(x::integer)::<*(y::integer)::integer*> is
<* (y::integer)::integer isx+y *>;
Looking carefully at this definition, what was a function of two arguments is now a function of one argument that results in a function of one argument. Specifically, the new function is a unary function over items of type integer that results in another unary function that maps items of type integer to type integer. But how is this equivalent to a two-argument function?
To understand the equivalence, examine the evaluation of addc(5)(4), the equivalent of evaluating add(5,4) using our earlier definition. We start by evaluating addc(5), remembering that Rosetta function evaluation is simply substitution of formal parameters for actual parameters:
1. addc(5) 2. == <* (x::integer)::<*(y::integer)::integer*> is <* (y::integer)::integer is x+y *>*>(5) 3. == <* <* (y::integer)::integer is 5+y *>*> 4. == <* (y::integer)::integer is 5+y *>
The evaluation progresses by first replacing the addc function with its value in step 2. Following this is the actual evaluation, replacing the formal parameter x with the actual parameter 5. In step 4, the outer function former is dropped because no parameters remain. The result is a new function value that adds 5 to its argument. Because this form cannot be evaluated further, it is called a normal form. In this case the normal form is also a value, specifically a function value. Not all normal forms will be values.
Now we can evaluate addc(5)(4) by applying the result of the previous evaluation of addc(5) to the formal parameter 4:
1. addc(5)(4)
2. == <* (y::integer)::integer is 5+y *>(4)
3. == <* ()::integer 5+4 *>
4. == 9 ::integer
In step 2, addc(5) is replaced with the result obtained in the previous evaluation and applied to 4. In step 3, y is replaced with 4, and finally the result is evaluated and 9 results, as anticipated.
It is not necessary to evaluate the results of calling the single-argument add function. Specifically, it is perfectly legitimate to call the function and treat the result itself as a function. The evaluation of addc(1) has the following form:
1. addc(1) 2. == <*(x::real)::<*(y::real)::real is x+y*>*>(1) 3. == <*(y::real):real is 1+y*>
This is exactly the definition of the function value previously associated with inc; inc can be now defined using this evaluation of addc:
inc::<*(x::integer)::integer*> is addc(1);
addc(1) evaluates to a function value that is the same as the definition of an increment function. Thus, it is perfectly legal to use the result of applying add as the value associated with the inc function definition.
Having discussed the evaluation of addc, it is important to remember that, semantically, addc and add are the same function. The only difference is that addc must be treated as a single parameter function while add can be treated as a two-parameter function or as a curried function. For this reason, using the add approach of specifying multiple parameters in the signature is more flexible and highly encouraged. We can always substitute and simplify as in previous examples, but the semantics of this process is defined by the curried approach discussed here. The definition for inc can use add instead of addc with virtually no modification:
inc::<*(x::integer)::integer*> is add(1);
The inc function is thus defined as a mapping from integer to integer whose value is the result of curried evaluation of the add function over the value 1.
When thinking about evaluating uninterpretable functions of any kind, little can be asserted. Evaluation cannot be guaranteed by syntactic analysis. Furthermore, no algorithm exists to determine whether a function can be evaluated for general functions. As a rule, if evaluation is necessary, use an interpretable function definition or associate the function with a constant in its declaration.
Example 6.8. Partial Evaluation
Partial evaluation is the process of taking a function and instantiating only a subset of its parameters. Curried functions provide the primitive concepts behind partial evaluation. Using Rosetta’s curried function semantics, it is possible to define a form of partial evaluation where any variable may be instantiated.
Consider the following definition of f over real numbers:
f(x,y,z::real)::real is (x+y)/z;
Like any function, f is applied by replacing formal parameters with actual parameters in the definition and evaluating the result. Specifically, f(1,2,3) is evaluated as follows:
1. f(1,2,3)
2. == <*(x,y,z::real)::real is(x+y)/z*>(1,2,3)
3. == <*(1+2)/3*>
4. == 1
We can make f an average function if the z parameter is instantiated with a constant 2. This is accomplished using the following notation:
<* (x,y::real)::real is f(x,y,2) *>
The definition of average follows directly as:
average::<*(x,y::real)::real is <*(x,y::real)::real is f(x,y,2)*>
Specifically, average is defined as a function from two real values to a third real value. The function value associated with average is the function f with its z parameter instantiated with 2. Partial evaluation is an exceptionally useful tool for defining and evaluating functions. The preceding example shows a simple case where a new function definition is produced through partial evaluation. The same technique can be used to make analysis simpler and faster as well as to perform analysis of new definitions.
Knowing this, function evaluation still occurs in a manner identical to that for interpretable functions. The following facet definition declares and defines a function, inc, in a highly general manner:
facet counter(x::output integer)::state_based is inc::<*(x::integer)::integer* > begin t1: forall (x::integer | inc(x) == x+1); t2: s'==inc(x); end facet counter;
This facet declaration defines a variable function and uses a new concept (defined in Chapter 7) called a quantifier in term t1 to provide a definition. The quantifier asserts that for any value, x::integer, inc(x) is equal to x+1. This should be immediately recognized as equivalent to previous definitions of the increment function. In term t2, inc(s) defines the value of the next state, s’.
Semantically, the value of inc(s) is known for any value of s. However, expecting a tool to determine this and evaluate the function appropriately is not appropriate. When defining systems requirements, such general specifications can play an important role when working at high levels of abstraction, as shall be seen in subsequent discussions.
Addition of a where clause makes an assertion on function evaluation. Specifically, the where clause specifies a boolean condition the function must always satisfy. If the function does satisfy the where clause, then evaluation proceeds as if the clause did not exist. If the function does not satisfy the clause, then evaluation results in bottom. The where clause can be associated with both interpretable and uninterpretable functions and plays an important role in evaluation and analysis.
Qualified interpretable functions are a form of interpretable function and thus can be evaluated in the same manner, with a change to reflect the presence of the where clause. Consider a definition of inc that includes a where clause:
inc(x::integer)::integer is x+1 where inc(x) > 0;
The where clause defines a condition on inc that asserts the result of incrementing is greater than 0. If we instantiate the where clause in the same manner as the function, the resulting evaluation informally looks as follows:
1. inc(2) where inc(2) > 0 2. == <* (x::integer)::integer is x+1 *>(2) where <* (x::integer)::integer is x+1 *>(2) > 0 3. == <* ()::integer is 2+1 *> where <* ()::integer is 2+1 * > > 0 4. == 2+1 ::integer where 2+1 ::integer > 0 5. == 3 ::integer where 3 ::integer > 0 6. == 3 ::integer where true 7. == 3 ::integer
In this case, the where clause is clearly true and the result of the function evaluation is the same as a simple interpretable function. If we evaluate the same function on a different value, inclusion of the where clause plays a more substantial role:
1. inc(-2) where inc(-2) > 0 2. == <* (x::integer)::integer is x+1 *>(-2) where <* (x::integer)::integer is x+1 *>(-2) > 0 3. == <* ()::integer is-2+1 *> where <* ()::integer is -2+1 * > > 0 4. == -2+1::integer where -2+1::integer > 0 5. == -1::integer where -1::integer > 0 6. == -1::integer where false 5. == bottom
In this case, the where clause is false and the result of the function evaluation is bottom.
The where clause plays a more important role in the definition of uninterpretable or variable functions by providing information about its eventual definition. The Rosetta prelude defines the square root function as follows:
sqrt(x::complex)::complex where sqrt(x)^2 == x;
The function does not specify a mechanism for calculating the square root, but asserts a condition on any implementation of it. Static analysis tools can use this information to perform various types of analysis. More importantly, the where clause provides implementation direction to a tool user or a specifier who might require a specific function instance. If a function value is associated with sqrt, the clause defines its requirements.
The where clause can be treated as a correctness condition on the function, or as an assertion for use by tools interpreting the function. Treated as a correctness condition, tools may either formally verify that an interpretable function satisfies its requirements or, as a program assertion, that it is evaluated when the function is evaluated. Type checkers will attempt to statically verify the where clause in an attempt to predict and avoid evaluation errors. When static verification cannot be performed, evaluation-time checking must be instituted.
Because function application is undefined whenever its associated where clause is violated, static analysis tools, including type checking systems, may assume that it is satisfied when analyzing surrounding specifications. This has many benefits, including assertion of function properties in a manner similar to that for type assertions. When a property is assumed or verified, the where clause can be added to assist verification tools by asserting properties.
Universally quantified parameters in function definitions provide Rosetta functions with a form of polymorphism by allowing type inference. When function applications are evaluated or statically checked, parameter values are specified by instantiating them with expressions. In contrast, universally quantified parameter values can be inferred rather than explicitly specified.
Example 6.9. Qualified, Uninterpretable Functions
A principle use for qualified function definition is defining requirements for functions whose implementations need not be specified. Such functions are frequently defined in the prelude, where the definitions of basic Rosetta functions are defined without regard to specific implementations. One such function is the choose operation over sets. Recall that choose(s) can evaluate to any element from s. If we use interpretable functions to define choose, we are required to specify a selection mechanism. Using the where clause, it is easy to define requirements without specifying mechanism:
choose[T::type](s::set(T))::T is constant
where choose(s) in s;
This definition of choose provides a precise definition without specifying how the operation is implemented.
A polymorphic form of the inc function provides a motivating example. The definition used thus far has the following form:
inc(x::integer)::integer is x+1;
We also know that inc is defined for subtypes of integer and for some super-types such as real. Subtypes present little problem, as we can simply use the traditional definition. However, supertypes cannot be handled by this definition. Furthermore, when a subtype of integer is used, the result will always be of type integer as specified by the function signature.
One solution to this is to make the operand type a parameter to inc:
inc(T::type; x::T)::T is x+1 where T =< number;
This new definition defines inc for any type that is a number, allowing the specifier to indicate the specific type. We now have a polymorphic inc that can be used in the following manner:
inc(natural,3) == 4::natural inc(real,3.0) == 4.0::real
This new form requires the type to be explicitly specified in the function application. Although this solves the original problem, it is still somewhat clumsy. Imagine requiring the type contained in a sequence to be specified each time an operation is applied.
The solution is provided by universally quantified parameters whose types are inferred by evaluation and static analysis tools. In the following definition, T is a universally quantified variable that represents a type:
inc[T::type](x::T)::T is x+1 where T =< number;
When this new inc is applied, the value of T is inferred rather than explicitly specified. For example, in the application inc(3), T will be inferred to have the value posint implying:
inc(3)::posint == 4::posint
Based on the value 3, the Rosetta type system constrains T to be the most specific type possible — in this case, posint. Similarly, in the application inc(3.4), T is constrained to posreal as the most specific type:
inc(3.4)::posreal == 4.4::posreal
The type system can be forced down a specific constraint path by either directly or indirectly constraining T. Directly constraining T simply involves providing an actual parameter in the traditional manner:
inc[real](3.4)::real == 4.4::real
Alternatively, type ascription can be used to specify the type of the actual parameter, indirectly constraining T:
inc(3.4::real)::real == 4.4::real
An interesting problem occurs when T is constrained to a type that is not closed under addition, such as negreal. A problematic example would be:
inc(-0.5)::negreal == 0.5::negreal
This case is prevented because the type signature of the addition operator prevents T from being constrained to negreal due to the presence of 1 in the addition expression. T can only be constrained to real. If the application attempts to constrain the type indirectly or directly to negreal, the result is a type error.
In contrast, consider a definition of inc using top as its domain and range:
inc_top(x::top)::top is x+1;
Like the polymorphic inc using universally quantified parameters, inc_top can be applied to any value. However, the similarities stop there. Because “+” is defined for any number type, if the type value associated with T satisfied inc’s original where clause, the addition could be performed. Additionally, nothing can be said about inc_top’s result type. If it is used in the context of other numbers, it will not satisfy typing rules. The lesson here is to use universally quantified parameters for polymorphic functions. Using top results in functions that are far more difficult to use. This lesson will hold wherever we see a need for polymorphism.
All of the examples thus far deal with using universally quantified parameters with types to implement polymorphism. They can also be used for other purposes, such as specifying operations over variable-length bit vector sorusing type inference to perform a kind of meta-specification. The key is that the Rosetta evaluation system must be able to infer a value for universally quantified parameters statically. Evaluation-time information cannot be used to resolve the parameter’s value.
We will see universally quantified parameters appear in the signatures of facets, components, and other Rosetta structures. In every case they play the same role as they do in function definition, providing a controlled form of parametric polymorphism. The same techniques will be used to determine their values either by specific instantiation or from implied constraints.