Ordered

4.1.1. ordered: type;

An ordered type is any type whose examples are partially or completely ordered.

Commentary

As defined above, an ordered type is any type whose examples are partially or completely ordered. The type ordered is the supertype of all ordered types in Easel.

# STATUS: planned

olives: type is enum(large, jumbo, gigantic, colossal);
my_ints: type is 2..6;
confirm olives << ordered; # olives are a subtype of type ordered
confirm my_ints << ordered; # my_ints are a subtype of type ordered

Users can declare a new ordered type by defining a less-than operator 4.1. New types can be declared to inherit from ordered, but unless the less-than operator is defined, the type cannot be used in relational expressions.

# STATUS: planned

cars: type is ordered;
sedan: type is 
	property cars;
SUV: type is 
	property cars;
Honda: sedan := new car;
Trooper: SUV := new car;
if (Honda < Trooper) then
	null();# Error

Here the simple fact of declaring cars to be ordered does not define a comparison operator, so that the if condition fails. Note however that in reasoning about ordered types, the Easel system will assume that a less-than operator exists even if it has not been defined.

The type ordered is used in the definition of enumerations and numbers. Unless the less-than operator is defined, user-declared ordered types are not very useful, as the above example shows.

Note also that any type for which the less-than operator has been defined is a subtype of ordered, whether it is explicitly declared that way or not.

Equality is built in for all types, and the greater-than, greater-than-or-equal-to, and less-than-or-equal-to relations are all derived from the less-than relationship.

4.1.2. "<"(ordered, ordered): boolean;

Authors may define the less than operation for any ordered type. Less than must be transitive and non reflexive, but need not define a complete ordering. Less than returns true iff its first argument appears earlier in the (partial) ordering than the second argument, false if the second argument is earlier than the first and nil if the arguments are unordered. The built-in less than operation applies to enumeration types and to numbers.

Commentary

The built-in less than operator allows comparisons to be made between examples of ordered types such as enumeration types. For example:

# STATUS: current

olive: type is enum(large, jumbo, gigantic, colossal);
my_olive :: olive := colossal;
your_olive :: olive := jumbo;
confirm your_olive < my_olive;

Authors may declare new ordered types by defining a less-than operator. If the type is only partially ordered, it will be undefined for some values of the type, whereas if it is totally ordered, it will be defined for all values.

# STATUS: planned

type lieutenant;
type general;
type soldier is private ~ lieutenant ~ general;
type officer is lieutenant ~ general;
	"<"(x: officer, y: officer) is
		if x isa lieutenant & y isa general then
			return true;
		else
			return false;
	"<"(x: soldier, y: soldier) is
		if x isa private & y isa lieutenant | y isa general then
			return true;
		else
			return ?;
confirm any private < general & any private < lieutenant;
confirm any lieutenant < any general;

Here the type officer is fully ordered, because the less-than operator is defined for all values of officers, while the type soldier is partially ordered, since the less-than operators are only defined for privates.

The less-than operator must be transitive and non-reflexive, but need not define a complete ordering. It must return:

True if its first argument appears earlier in the (partial) ordering than the second argument
False if the second argument is earlier than the first
False if the two arguments appear at the same position in the ordering
? if the arguments are unordered

4.1.3. ">"(x: ordered, y: ordered): boolean #{is  y < x}#;

The greater than operation is automatically defined whenever less than is defined.

4.1.4. "<="(x: ordered, y: ordered): boolean #{is !(y < x)}#;

The less than or equal operation is automatically defined whenever less than is defined.

4.1.5. ">="(x: ordered, y: ordered): boolean #{is !(x < y)}#;

The greater than or equal operation is automatically defined whenever less than is defined.

4.2. Scalar Types

Any type whose examples are fully ordered is a scalar type. Scalar types include enumerations (5.7.2), machine integers (4.3.1), numbers (5.1.1), integers, and real numbers. Integers and real numbers are not supported. Complex numbers are not scalars.

4.2.1. scalar: ordered type;

A scalar type is an ordered type whose values form a fully ordered sequence.

Commentary

The soldiers example in 4.1.2 illustrates the difference between scalar and partially ordered types; here is another example:

# STATUS: planned

totally_ordered(i: int): scalar;
partially_ordered(i: int): scalar;
T3: totally_ordered := totally_ordered 3;
T9: totally_ordered := totally_ordered 9;

"<"(x: totally_ordered, y: totally_ordered): boolean is
	return (x.i < y.i);

"<"(x: partially_ordered, y: partially_ordered): boolean is
	if (x.i < 1000 & y.i < 1000) then
		return true;
	else
		return ?;

confirm T3 < T9;

Here the types totally_ordered and partially_ordered are identical except for the fact that the less-than operator for partially_ordered is undefined for values above 1000.

4.2.2. min(vector...): any;

The min operation applies to one or more arguments of the same type. It returns the minimum value among its arguments as defined by their ordering. If there are vector arguments, they must all be of the same dimension, and scalar arguments will be applied to all dimensions of the vectors.

Commentary

# STATUS: current

rainbow: type is enum(r, o, y, g, b, i, v);
smallest :: rainbow := min(y, b, o, i);
biggest :: rainbow := max(y, b, o, i);
confirm smallest = o;
confirm biggest = i;
confirm min(vector(0, 2, 13), 4, vector(7, 0.3, 10)) = vector(0, 0.3, 4);

4.2.3. max(vector...): any;

The max operation applies to one or more arguments of the same type. It returns the maximum value among its arguments as defined by their ordering. If there are vector arguments, they must all be of the same dimension, and scalar arguments will be applied to all dimensions of the vectors.

Commentary

# STATUS: current

confirm max(vector(0, 2, 3), 4.1, vector(7, 1, 0)) = vector(7, 4.1, 4.1);

4.3. Machine Integers

Machine integers are a built-in enumeration type for the integers in the range -32768 .. 32767. Machine integers all have literals as defined in A.3 . Relational operations (see 4.1), enumeration operations (see 5.7) and the operations of this section apply to machine integers. Machine integers may be used anywhere numbers are required. Numbers that are integers in the range of machine integers may be used anywhere machine integers are required. It is illegal to use any other number where an integer is required. The bit by bit operations of Section 4.4 operate on integers.

4.3.1. int: number type;

The definition of int in the current implementation is:

int: enumeration type is
	# integer in -2^15.. 2^15-1	
	property int << number;

Commentary

The type int represents machine integers. Machine integers may be used anywhere numbers are required, and numbers that are integers may be used anywhere machine integers are required. It is illegal to use any other number where an integer is required.

# STATUS: planned

a :: number := 1.234;
b :: number := 1.0;
i :: int := 3;
j :: int := a; # Illegal
k :: int := b; # Legal
l :: int := 1.234; # Illegal
c :: number := i; # Legal

4.3.2. indexer: enumeration int type;

The type indexer is the type of all integers in the range -2^15..2^15-1.

Commentary

The primary use of indexer is to declare indexing operations in the Easel Package Standard.

# STATUS: current

L: (list int) := new list int;
push(L, 1, 2, 3, 4, 5);
confirm L[4.0-1.0] = 4;

4.3.3. permute(n: indexer): list;

This routine returns a random permutation of the integers 0.. n-1. The resulting values may be used as indices on any list of n elements to randomly permute the order of reference.

Commentary

This routine returns a random permutation of the integers 0 through n-1. The resulting values may be used as indices on any list of n elements to permute the order of reference randomly.

# STATUS: current

l :: list := new list any;

l := permute 5;
confirm (length l) = 5;
for i: each (0..4) do
	confirm l[i] >= 0;
	confirm l[i] < 5;

In the following statements, the list shuffle is being used to scramble the hand upon output.

# STATUS: current

deal(): action is
	face_cards: type is enum(jack, queen, king, ace);
	hand: type is list face_cards;
	shuffle :: list := new list any;
	
	shuffle := permute 4;
	H :: hand := new hand;
	H := hand'[jack, queen, king, ace];
	output(H, "\cr");
	output(shuffle, "\cr");
	for i: each (0..3) do
		# prints e.g. king queen ace jack
		output(H[shuffle[i]], "\cr"); 
deal();

4.4. Bitwise Operations

Commentary

The following example illustrate the use of bit-wise operations. The first two comment lines define the equivalence between two decimal and binary numbers being used. The next line shows how pair-wise ANDing of the binary bit strings of these two numbers results on the binary number 1000 (8 decimal).

# STATUS: current

# 10 (decimal) = 1010 (binary)
# 12 (decimal) = 1100 (binary) 
confirm band(10, 12) = 8;
confirm bor(10, 12) = 14;
confirm bxor(10, 12) = 6;
confirm (bnot 10) = (-11);
confirm bsr(10, 2) = 2;
confirm bsc(10, 12) = 40960;
confirm bsa(10, 2) = 2;
confirm bsa((-10), 2) = (-3);

4.4.1. band(int, int): int;

Perform a bit-wise and operation on the integers.

4.4.2. bor(int, int): int;

Perform a bit-wise or operation on the integers.

4.4.3. bxor(int, int): int;

Perform a bit-wise exclusive or operation on the integers.

4.4.4. bnot(int): int;

Complement each bit in the integer.

4.4.5. bsr(x: int, n: int): int;

Shift x right by n bits.

4.4.6. bsl(x: int, n: int): int;

Shift x left by n bits.

4.4.7. bsc(x: int, n: int): int;

Circular shift the first integer n bits to the right.

Commentary

Left circular shifts may be done by bsc 16-n. For example, a left shift 7 of 3 can be done by

bsc(3, 9);

4.4.8. bsa(x: int, n: int): int;

Perform a (non-circular) right shift, preserving the sign bit.

4.4.9. first_bit_different(int, int): int;

The first_bit_different operator compares the bits in the two integers and returns the bit position of the most significant bit that is different. The least significant bit is bit 0. If the two integers are identical, first_bit_different returns -1.

Commentary

Note that although the first bit is determined starting at the most significant bit, to accommodate different integer widths, the bit position returned is counted starting from the least significant bit.

Here is an example of first_bit_different:

# STATUS: current

confirm first_bit_different(01001#2, 01100#2) = 2;

The two integers differ in the third bit from the right, so first_bit_different returns 3.

Note that if one of the integers is 0, first_bit_different can be used as a first_bit_set function.

# STATUS: current

confirm first_bit_different(01000#2, 0) = 3;

Table of Contents

For more information, contact SEI Customer Relations, customer-relations@sei.cmu.edu

return to top | Easel Language Reference Manual and Users' Guide
Easel main page