Code Inclusion and Partial Classes

4.1 Include Clauses

include A a->b, c->, d->private d; 
private include D e->readonly f; 

Code inclusion permits the re-use of code from a parent concrete class in child concrete class . Including code is a purely syntactic operation in Sather. To help illustrate the following examples, we repeat the interface of EMPLOYEE from page 56.

class EMPLOYEE is private attr wage:INT; readonly attr name:STR; attr id:INT; const high_salary:INT := 40000;   create(a_name:STR, a_id:INT, a_wage:INT):SAME is ...   highly_paid:BOOL is ... end;

Routines that are redefined in the child class over-ride the corresponding routines in the included class. For instance suppose we define a new kind of EMPLOYEE - a MANAGER, who has a number of subordinates.

class MANAGER is include EMPLOYEE create->private oldcreate; -- Include employee code and rename create to 'oldcreate'   readonly attr numsubordinates:INT; -- Public attribute   create(aname:STR, aid:INT,awage:INT,nsubs:INT):SAME is -- Create a new manager with the name 'aname' -- and the id 'aid' and number of subordinates = 'nsubs' res ::= oldcreate(aname,aid,awage); res.numsubordinates := nsubs; return res; end; end;

See the EMPLOYEE definition on page 56. The create routine of the MANAGER class extends the EMPLOYEE create routine, which has been renamed to oldcreate (renaming is explained below) and is called by the new create routine.

Points to Note

• The order of inclusion is not significant and cannot affect conflicts.

• External classes may be included if the interface to the language permits this; external Fortran and C classes may not be included.

• Immutable (see page 119) and reference classes cannot be mixed into a single class during inclusion. In the case of arrays (see page 105), there cannot be include paths from reference types to AVAL or from immutable types to AREF i.e. reference types cannot include an immutable array portion and immutable classes cannot include a reference array portion.

• There must be no cycle of classes such that each class includes the next, ignoring the values of any type parameters.

  class A is include B;... class B is include C;... class C is include A; ..

• If SAME occurs in included code it is interpreted as the eventual type of the class (as late as possible). We make use of this fact every time we include a create routine that returns SAME

  class FOO is create:SAME is return new; end;   class SON_OF_FOO is include FOO; -- Since create returns SAME, we have create:SON_OF_FOO;   class GRANDSON_OF_FOO is include SON_OF_FOO; -- Now we have create:GRANDSON_OF_FOO;   a ::= #GRANDSON_OF_FOO; -- Calls GRANDSON_OF_FOO::create:SAME, -- which returns a GRANDSON_OF_FOO.

4.1.1 Renaming

class MANAGER is 
 private include EMPLOYEE;  
 -- All included features are made private 
class MANAGER is 
 private include EMPLOYEE  id->id; 
 -- Makes the "id" routine public and others stay private

class MANAGER is 
 include EMPLOYEE  id->; -- Undefine the "id" routine
  attr id:MANAGER_ID;     -- This ' id' has a different type

Points to note

• All overloaded features must be renamed at the same time - there is no way to specify them individually.

• A public routine can be made private by either a private include or by renaming the individual routine to be private

  class MANAGER is include EMPLOYEE id->private id; -- Renames both reader and writer routines of the attribute 'id'

• In a private include, renaming a particular feature has the effect of making just that one feature public. For instance

  class MANAGER is private include EMPLOYEE name->name; -- only 'name' is made public

• Iterator names may only be renamed as iterator names.

• It is an error if there are no appropriate methods to rename in the included class.

• Both a reader and a writer method must exist if 'readonly' is used in a renaming clause.

  class I_INTERVAL is private attr first, size:INT; finish:INT is return first + size - 1 end; finish(fin:INT) is size := fin - first + 1; end; ...   class LINE_SEGMENT is include I_INTERVAL finish->readonly finish; -- makes private finish(fin:INT) -- and leaves public finish:INT;

4.1.2 Multiple Inclusion

class PARENT1 is 
   attr a:INT; 
   create:SAME is  return new.init;  end; 
   private init:SAME is a := 42; return self; end; 
end;

The other parent is similarly defined

class PARENT2 is attr c:INT; create:SAME is return new.init end; private init:SAME is c := 72 end; end;

In the child class, both parents are initialized by calling the initialization routines in the included classes

class DERIVED is include PARENT1 init-> PARENT_init; include PARENT2 init-> PARENT2_init; -- Rename init   attr b:INT;   create:SAME is -- a gets the value 42, b the value 99 and c the value 72 return new.PARENT1_init.PARENT2_init.init end;   private init:SAME is b := 99; return self; end; -- class DERIVED

4.1.3 Resolving conflicts

For now, we simply note that if we have signatures with the same name in two included classes, we can simply rename one of them away i.e.

class FOO is include BAR bar->; -- eliminate this 'bar' routine include BAR2; -- Use the 'bar' routine from BAR2

4.2 Partial Classes and Stub routines

A stub feature may only be present in a partial class. They have no body and are used to reserve a signature for redefinition by an including class. If code in a partial class contains calls to an unimplemented method, that method must be explicitly provided as a stub. The following class is a stub debugging class which checks on the value of a boolean and then prints out a debugging message (preceeding by the class name of 'self')

partial class DEBUG_MSG is stub debug:BOOL;   debug_msg(msg:STR) is -- Prints out the type of "self" and a debugging message if not debug then -- Don't print out the message if the debug flag is false return end; type_str:STR; -- Declared here since used in both branches of the if if ~void(self) then type_id:INT := SYS::tp(self); -- SYS::tp will not work if self is void! type_str:STR := SYS::str_for_tp(type_id); else type_str := "VOID SELF"; end; #OUT+ "Debug in class:"+type_str +" "+ msg+"\n"; end; end;

This class can be used by some other class - for instance, a main routine that wants to print out all the arguments to main. The stub routine 'debug' must be filled in using either an attribute (a constant, in this case) or a routine.

class MAIN is include DEBUG_MSG;   const debug:BOOL := true; -- Fill in the stub.   main(args:ARRAY{STR}) is loop arg:STR := args.elt! debug_msg("Argument:"+arg); -- Print out the argument end; end; end;

Points to note

• Partial classes cannot be used to instantiate parameters of a parametrized class. For example, 'ARRAY{DEBUG_MSG}' would not be legal.

• Create cannot be called on a partial class, nor can a partial class occur as the type of a variable or attribute.

4.2.1 Mixins: A Prompt Example

Now suppose that we have a 'COMPUTE' class that requires a prompt for some input data. It can leave the prompt routine as a stub, which will later be filled in by some prompt class

partial class COMPUTE is stub prompt_user:STR;   main is res ::= prompt_user; -- Convert it to an integer and do something with it i:INT := res.cursor.get_int; #OUT+" I'm going to compute with this number, now:"+i+"\n"; .... end;   end; -- partial class COMPUTE

We can now create different computation classes by mixing an arbitrary prompt style with the main computation partial class.

class COMPUTE_A is include COMPUTE; include PROMPT_STYLE_A; end; -- class COMPUTE_A   class COMPUTE_B is include COMPUTE; include PROMPT_STYLE_B; end; -- class COMPUTE_B

Abstract Classes and Subtyping

5.1 Abstracting over Implementations

5.1.1 Implementing a Stack using an Array

class ARR_STACK is private attr elems:ARRAY{INT}; private attr index:INT; -- Points to the next location to insert   create:SAME is res::=new; res.elems:=#ARRAY{INT}(5); res.index := 0; return res; end;   push(e:INT) is if index > elems.size then new_elems:ARRAY{INT} := #ARRAY{INT}(index * 2); -- copy over the old elements loop new_elems.set!(elems.elt!) end; elems := new_elems; end; elems[index] := e; index := index + 1; end;   pop:INT is index := index - 1; return elems[index]; end;   is_empty:INT is return index = 0 end; end;

It would be appropriate to also shrink the array when elements are popped from the stack, but we ignore this complexity for now.

5.1.2 A Stack Calculator

class RPN_CALCULATOR is
   private attr stack:ARR_STACK;
 
   create:SAME is res ::=new; res.stack := #ARR_STACK; return res; end;
 
   push(e:INT) is stack.push(e) end;
   
   add:INT is
     -- Add the two top two eleemnts 
     if stack.is_empty then empty_err; return 0; end;
     arg1:INT := stack.pop;
     if stack.is_empty then empty_err; return 0 end;
     arg2:INT := stack.pop
     return arg1 + arg2;     
   end;
 
   private empty_err is #ERR+"No operands available!" end;
end;

5.1.3 A Linked List Representation of a Stack

class STACK_ELEM_HOLDER is
   readonly attr data:INT;
   attr next:INT_STACK_ELEM;
   create(data:INT):SAME is
      res ::= new; res.data := data; res.next := void; return res;
   end;
end;

class LINK_STACK is
    private attr head:STACK_ELEM_HOLDER;
    create:SAME is  res ::= new; return res; end;
    
    push(e:INT) is 
       elem_holder ::= #STACK_ELEM_HOLDER(e);
       elem_holder.ext := head;
       head := elem_holder;
    end;
   
    pop:INT is
      res:INT :+ head.data;
      head := head.next;
    end;
    
    is_empty:BOOL is return void(head) end;  
end;

5.1.4 Switching Representations:Polymorphism

It would be nice to be able to write code such that we could transparently replace one kind of stack by the other. If we are to do this, we would need to be able to refer to them indirectly, through some interface which hides which particular implementation we are using. Interfaces of this sort are described by abstract classes in Sather. An abstract class that describes the stack abstraction is

abstract class $STACK is create:SAME; push(e:INT); pop:INT; is_empty:BOOL; end;

Note that the interface just specifies the operations on the stack, and says nothing about how they are implemented. We have to then specify how our two implementations conform to this abstraction. This is indicated in the definition of our implementations. More details on this will follow in the sections below.

class ARR_STACK < $STACK is ... same definition as before ...   class LINK_STACK < $STACK is ... same definition as before ...

The calculator class can then be written as follows

class RPN_CALCULATOR is private attr stack:$STACK; create(s:$STACK):SAME is res::= new; res.stack:=s; return res; end;   ... 'add' and 'push' behave the same end;

In this modified calculator, we provide a stack of our choice when creating the calculator. Any implementation that conforms to our stack abstraction my be used in place of the array based stackt

s:LINK_STACK := #LINK_STACK; calc:RPN_CALCULATOR := #RPN_CAlCULATOR(s); calc.push(3); calc.push(5); #OUT+calc.add; -- Prints out 8

5.2 Abstract Class Definitions

abstract class $SHIPPING_CRATE  is 
 destination:$LOCATION; 
 weight:FLT; 
end; -- abstract class $SHIPPING_CRATE

Abstract types can never be created! Unlike concrete classes, they merely specify an interface to an object, not an object itself. All you can do with an abstract type is to declare a variable to be of that type. Such a variable can point to any actual object which is a subtype of that abstract class. How we determine what objects such an abstract variable can point to is the subject of the next section.

Note that we can, of course, provide a create routine in the abstract class

abstract class $SHIPPING_CRATE is create:SAME; ...

However, we can never call this creation routine on a void abstract class i.e. the following is prohibited

crate:$SHIPPING_CRATE := #$SHIPPING_CRATE; -- ILLEGAL

f:FLT := $SHIPPING_CRATE::weight;  -- ILLEGAL

Example: An abstract employee

abstract class $EMPLOYEE is 
 -- Definition of an abstract type.  Any concrete class that 
 -- subtypes from this abstract class must provide these routines. 
 name:STR; 
 id:INT; 
end; 

More abstract class examples

abstract class $STR is
 -- Ensures that subtypes have a 'str' routine
 str:STR;   -- Return a string form of the object
end; 

abstract class $FOO is
 foo(arg:INT);      -- method A
 foo(arg:BOOL);      -- method B
 foo(arg:$FOO);      -- method C
 foo(a, b:INT)     ; -- method D
end;

5.3 Subtyping

abstract class $SHIPPING_CRATE< $CRATE is ...

Points to note about subtyping:

• Every type is automatically a subtype of $OB

• Only abstract types can be mentioned in the subtyping clause

• When a subtyping clause is used in a partial class, it enforces the basic subtyping rule using the stub routine.

• There must be no cycle of abstract types such that each appears in the subtype list of the next, ignoring the values of any type parameters but not their number.

• A subtyping clause may not refer to SAME.

• SAME is only permitted as a return type or on out arguments in abstract class signatures.

5.3.1 The Type Graph

abstract class $TRANSPORT is ... 
abstract class $FAST is ... 
abstract class $ROAD_TRANSPORT < $TRANSPORT is ...
abstract class $AIR_TRANSPORT < $TRANSPORT, $FAST is ...
class CAR < $ROAD_TRANSPORT is ...
class DC10 < $AIR_TRANSPORT is ...

5.3.2 Dynamic Dispatch and Subtyping

An example: Generalizing Employees

class EMPLOYEE < $EMPLOYEE is ... 
   -- Employee, as defined earlier
 
class MANAGER < $EMPLOYEE is ... 
   -- Manager as defined earlier on page 56

class TESTEMPLOYEE is 
 main is 
  employees:ARRAY{$EMPLOYEE} := #ARRAY{$EMPLOYEE}(3); 
   -- employees is a 3 element array of employees
   i:INT := 0; wage:INT := 0; 
   loop until!(i = employees.size); 
    emp:$EMPLOYEE := employees[i]; 
    emp_wage:INT := emp.wage; 
    -- emp.wage is a dispatched call on "'age'
    wage := wage+emp_wage;
   end;  
  #OUT+wage+"\n"; 
 end; 
end; 

5.4 Supertyping

If both subtyping and supertyping clauses are present, then each type in the supertyping list must be a subtype of each type in the subtyping list using only edges introduced by subtyping clauses. This ensures that the subtype relationship can be tested by examining only definitions reachable from the two types in question, and that errors of supertyping are localized.You define supertypes of already existing types. The supertype can only contain routines that are found in the subtype i.e. it cannot extend the interface of the subtype.

abstract class $IS_EMPTY > $LIST, $SET is is_empty:BOOL; end;

5.4.1 Using supertyping

5.5 Type Conformance

5.5.1 Contravariant conformance

abstract class $UPPER is ... 
abstract class $MIDDLE < $UPPER is...
abstract class $LOWER < $MMIDDLE is ...

abstract class $SUPER is  
 foo(a1:$MIDDLE, out a2:$MIDDLE, inout a3:$MIDDLE):$MIDDLE;
end;

• Normal arguments (with the mode in) must have the same type or a supertypes

• out arguments and return values must have the same type or a subtype

• inout arguments must have the same type

abstract class $SUPER is  
 foo(a1:$MIDDLE, out a2:$MIDDLE, inout a3:$MIDDLE):$MIDDLE;
end;

Suppose we start with herbivores and carnivores, each of which are capable of eating

abstract class $HERBIVORE is eat(food:$PLANT);   abstract class $CARNIVORE is eat(food:$MEAT);   abstract class $FOOD is ... abstract class $PLANT < $FOOD is... abstract class $MEAT < $FOOD is...

What does not work

abstract class $OMNIVORE is eat(food:$FOOD);
abstract class $CARNIVORE < $OMNIVORE is ..
abstract class $HERBIVORE < $OMNIVORE is ...

To illustrate this, consider a variable of type $OMNIVORE, which holds a herbivore.

cow:$HERBIVORE := -- assigned to a COW object animal:$OMNIVORE := cow; meat:$MEAT; animal.eat(meat);

This last call would try to feed the animal meat, which is quite legal according to the signature of $OMNIVORE::eat($FOOD), since $MEAT is a subtype of $FOOD. However, the animal happens to be a cow, which is a herbivore and cannot eat meat.

What does work

abstract class $CARNIVORE is   eat(food:$MEAT); ...
abstract class $HERBIVORE is   eat(food:$PLANT);...
abstract class $OMNIVORE < $HERBIVORE, $CARNIVORE is 
     eat(food:$FOOD); ...

5.5.2 Subtyping = substitutability

5.6 The typecase statement

The typecase statement provides us with the ability to make use of the actual type of an object held by a variable of an abstract type.

a:$OB := 5; ... some other code... res:STR; typecase a when INT then -- 'a' is of type INT in this branch #OUT+"Integer result:"+a; when FLT then -- 'a' is of type FLT in this branch #OUT+"Real result:"+a when $STR then -- 'a' is $STR and supports '.str' #OUT+"Other printable result:"+a.str; else #OUT+"Non printable result"; end;

t The typecase must act on a local variable or an argument of a method.On execution, each successive type specifier is tested for being a supertype of the type of the object held by the variable. The statement list following the first matching type specifier is executed and control passes to the statement following the typecase.

Points to note

• It is not legal to assign to the typecase variable within the statement lists.

• If the object's type is not a subtype of any of the type specifiers and an else clause is present, then the statement list following it is executed.

• It is a fatal error for no branch to match in the absence of an else clause.

• If the value of the variable is void when the typecase is executed, then its type is taken to be the declared type of the variable. In the above example, the declared type of a is $OB , which does not match any of the branches, so the else clause is taken

• The variable of the typecase must be a local variable or a method argument.

• If the typecase appears in an iterator, then the mode of the argument must be once; otherwise, the type of object that such an argument holds could change.

• The typecase does not search for the branch with the tightest match - it goes down the first branch that matches.

• After a branch has been selected, the typecase tries to cast the variable to as narrow a type as possible - if the declared type of the variable is actually stronger than (a subtype of) the chosen branch, then the variable will keep the stronger, declared type. For instance

  a:$SET{INT}; typecase a when INT then ... -- a will never get here, INT is not < $SET{INT} when $OB then ... -- a has the type of $SET{INT} which is stronger than $OB

Typecase Example

peter ::=  #EMPLOYEE("Peter",1);      -- Name = "Peter", id = 1 
paul  ::=  #MANAGER("Paul",12,10);    -- id = 12,10 subordinates 
mary  ::=  #MANAGER("Mary",15,11);    -- id = 15,11 subordinates
employees:ARRAY{$EMPLOYEE} := |peter,paul,mary|; 
totalsubs:INT := 0; 
loop employee:$EMPLOYEE := employees.elt!; -- yields array elements
 typecase employee 
 when MANAGER then 
  totalsubs := totalsubs + employee.numsubordinates; 
 else  end; 
end; 
#OUT+"Number of subordinates:"+totalsubs+"\n"; 

5.7 The Overloading Rule

As a preliminary warning:the overloading are flexible, but are intended to support the coexistance of multiple functions that have the same meaning, but differ in some implementation detail. Calling functions that do different things by the same name is wrong, unwholesome and severely frowned upon! Hence, using the function name times with different number of arguments to mean

5.7.1 Extending Overloading

Overloading based on Concrete Argument Types

plus(a:INT):INT is ...
plus(a:FLT):INT is ...

Overloading based on Abstract Argument Types

abstract class $STR is
  str:STR;
end;

Now consider the interface to the FILE class. In the file class we would like to have a general purpose routine that appends any old $STR object, by calling the str routine on it and then appending the resulting string. This allows us to append any subtype of $STR to a file at the cost of a run-time dispatch. We also want to define more efficient, special case routines (that avoid the dispatched call to the str routine) for common classes, such as integers

class FILE is -- Standard output class (1) plus(s:$STR) is .... (2) plus(s:INT) is ...

. The problem arises at the point of call

f:FILE := FILE::open_for_read("myfile"); a:INT := 3; f+a;

Now which plus routine should we invoke? Clearly, both routines are valid, since INT is a subtype of $STR. We want the strongest or most specific among the matching methods, (2) in the example above. Though the notion of the most specific routine may be clear in this case, it can easily get murky when there are more arguments and the type graph is more complex.

The Demon of Ambiguity

abstract class $BINARY_PRINTABLE is
   -- Subtypes can provide a binary version of themselves
   binary_str:STR;
end;

class FILE is
(1)  plus(s:$STR) is ..
(2)  plus(s:$BINARY_STR) is ...
(3)  plus(s:INT) is ...

f:FILE;
f+3.0;

class FLTD < $BINARY_STR, $STR is 
  binary_str:STR is ... binary version
  str:STR is ... decimal version

The above problem arises because neither (1) nor (2) is more specific than the other - the problem could be solved if we could always impose some ordering on the overloaded methods, such that there is a most specific method for any call.

We could resolve the above problem by ruling the FILE class to be illegal, since there is a common subtype to both $STR and $BINARY_STR, namely FLTD. Thus, a possible rule would be that overloading based on abstract arguments is permitted, provided that the abstract types involved have no subtypes in common.

However, the problem is somewhat worse than this in Sather, since both subtyping and supertyping edges can be introduced after the fact. Thus, if we have the following definition of FLTD

class FLTD < $BINARY_STR is binary_str:STR is ... str:STR is ...

the file class will work. However, at a later point, a user can introduce new edges that cause the same ambiguity described above to reappear!

abstract class $BRIDGE_FLTD < $STR > FLTD is end;

Adding this new class introduces an additional edge into the type graph and breaks existing code.

The essense of the full-fledged overloading rule avoids this problem by requiring that the type of the argument in one of the routines must be known to be more specific than the type of the argument in the corresponding position in the other routine. Insisting that a subtyping relationship between corresponding arguments must exist, effectively ensures that one of the methods will be more specific in any given context. Most importantly, this specificity cannot be affected by the addition of new edges to the type graph. Thus, the following definition of $BINARY_STR would permit the overloading in the FILE class to work properly

abstract class $BINARY_STR < $STR is binary_str:STR; end;

When the 'plus' routine is called with a FLTD, the routine 'plus($BINARY_STR)' is unambiguously more specific than 'plus($STR)'.

5.7.2 Permissible overloading

Overload 1.: The presence/absence of a return value

Overload 2.: The number of arguments

Overload 3.: In at least one case corresponding arguments must have different marked modes (in and once modes are not marked at the point of call and are treated as being the same from the point of view of overloading).

Overload 4.: In at least one of the in, once or inout argument positions: (a) both types are concrete and different or (b) there is a subtyping relationship between the corresponding arguments i.e. one must be more specific than the other. Note that this subtyping ordering between the two arguments cannot be changed by other additions to the type graph, so that working libraries cannot be broken by adding new code.

Note that this definition of permissible permissible coexistance is the converse of the definition of conflict in the specification. That is, if two signatures cannot coexist, they conflict and vice-versa.

abstract class $VEC is ... abstract class $SPARSE_VEC < $VEC is ... abstract class $DENSE_VEC < $VEC is...   class DENSE_VEC < $DENSE_VEC is ... class SPARSE_VEC < $SPARSE_VEC is ....

Given the above definitions of vectors, we can define a multiply and add routine in the matrix class

abstract class $MATRIX is   (1) mul_add(by1:$VEC, add1:$SPARSE_VEC); (2) mul_add(by2:$DENSE_VEC, add2:$VEC); -- (1) and (2) can overload, since the arg types can be ordered -- by2:$DENSE_VEC < by1:$VEC, -- add2:$VEC > add1:$SPARSE_VEC (3) mul_add(by3:DENSE_VEC, add3:SPARSE_VEC); -- (3) does not conflict with the (1) and (2) because there -- is a subtyping relation between corresponding arguments. -- (vs 1) by3:DENSE_VEC < by1:$VEC , -- add3:SPARSE_VEC < add1:$SPARSE_VEC -- (vs 2) by3:DENSE_VEC < by2:$DENSE_VEC , -- add3:SPARSE_VEC < add2:$VEC

While any of the above conditions ensures that a pair of routines can co-exist in an interface, it still does not describe which one will be chosen during a call.

Finding matching signatures

f:$MATRIX;
f.mul_add(DENSE_VEC, SPARSE_VEC);     -- Matches (1), (2) and (3)
f.mul_add($DENSE_VEC, $SPARSE_VEC);   -- Matches (1) and (2)
f.mul_add($DENSE_VEC, $DENSE_VEC);    -- Matches (2)
f.mul_add($SPARSE_VEC, SPARSE_VEC);   -- Matches (1)

Finding a most specific matching signature

f:$MATRIX;
f.mul_add(DENSE_VEC, SPARSE_VEC)      -- (3) is most specific
f.mul_add($DENSE_VEC, $DENSE_VEC);    -- Only one match
f.mul_add($SPARSE_VEC, $SPARSE_VEC);  -- Only one match

More examples

All the following can co-exist with the above signature

foo(a:A, out b:B):INT -- Presence return value (Overload 1) foo(a:A) -- Number of arguments (Overload 2) foo(a:A, b:B) -- Mode of second argument (Overload 3) foo(a:B, out b:B) -- Different concrete types in -- the first argument (Overload 4a)

The following cannot be overloaded with foo(a:A,out b:B):INT;

foo(a:A,b:B):BOOL; -- Same number, types of arguments, -- both have a return type. -- Difference in actual return type cannot be used to overload

For another example, this time using abstract classes, consider the mathematical abstraction of a ring over numbers and integers. The following can be overloaded with the 'plus' function in a class which describes the mathematical notion of rings

abstract class $RING is plus(arg:$RING):$RING;   abstract class $INT < $RING is plus(arg:$INT):$RING; -- By Overload 4 since he type of arg:$INT < arg:$RING   abstract class $CPX < $RING is plus(arg:$CPX):$RING; -- By Overload 4b, since the type of arg:$CPX < arg:$RING

The overloading works because there is a subtyping relationship between the arguments 'arg' to 'plus' The following overloading also works

abstract class $RING is mul_add(ring_arg1:$RING, ring_arg2:$RING);   abstract class $INT < $RING is mul_add(int_arg1:$INT, int_arg2:$INT); -- int_arg1:$INT < ring_arg:$INT and -- int_arg2:$INT < ring_arg2:$INT

Now there is a subtyping relationship between $INT::mul_add and $RING::mul_add for both 'arg1' and 'arg2', but there is no subtyping

This somewhat complex rule permits interesting kinds of overloading that are needed to implement a kind of statically resolved, type-safe co-variance which is useful in the libraries, while not sacrificing compositionality. Externally introducing subtyping or supertyping edges into the typegraph cannot suddenly break overloading in a library.

5.7.3 Overloading as Statically resolved Multi-Methods

abstract class $FIELD_ELEMENT is
  add(f:$FIELD_ELEMENT):$FIELD_ELEMENT;
 
abstract class $NUMBER < $FIELD_ELEMENT is
  add(f:$NUMBER):$NUMBER
 
abstract class $INTEGER < $NUMBER is
  add(f:$INTEGER):$INGEGER

5.7.4 Conflicts when subtyping

It is important to note that a conflict occurs when two signatures are so similar that they cannot co-exist by the over-loading rules. This happens when there is not even one argument where there is a sub- or supertyping relationship or where both arguments are concrete. As a consequence, you can always construct a signature that is more general than the conflicting signatures

abstract class $ANIMAL is ... abstract class $PIG < $ANIMAL is ... abstract class $COW < $ANIMAL is ... abstract class $COW_FARM is has(a:$COW); end; abstract class $PIG_FARM is has(a:$PIG); end;   abstract class $ANIMAL_FARM < $COW_FARM, $PIG_FARM is -- The signatures for has(a:$COW) and has(a:$PIG) must -- be generalized has(a:$ANIMAL); -- $ANIMAL is a supertype of $COW and $PIG, so this 'has' -- conforms to both the supertype 'has' signatures end;

In the above example, when we create a more general farm, we must provide a signature that conforms to all the conflicting signatures by generalizing the in arguments. If the arguments in the parent used the out mode, we would have to use a subtype in the child. A problem is exposed if the mode of the arguments in the parents is inout

abstract class $COW_FARM is processes(inout a:$COW); end; abstract class $PIG_FARM is processes(inout a:$PIG); end;   -- ILLEGAL! abstract class $ANIMAL_FARM < $COW_FARM, $PIG_FARM is -- No signature can conform to both the 'processes' signatures -- in the $COW_FARM and $PIG_FARM

5.7.5 Conflicts during code inclusion

Conflicting Methods

1. First, let us consider the resolution method for routines. Conflicts can occur between methods in different classes that have been included and must be resolved by renaming the offending feature in all but one of the included classes.

class PARENT1 is foo(INT):INT; class PARENT2 is foo(INT):BOOL; -- conflicts with PARENT1::foo class PARENT3 is foo(INT):FLT; -- would similarly conflict   class CHILD is include PARENT1 foo -> parent1_foo; -- Include and rename away the routine 'foo' include PARENT2 foo -> parent2_foo; -- Include and rename away the routine 'foo' include PARENT3; -- Use the routine from this class

2. The other way to resolve method conflicts is to explicitly define a method in the child class that will then over-ride all the parent methods.

class CHILD is include PARENT1; include PARENT2; include PARENT3; foo(INT):BOOL is -- over-rides all the included, conflicting routines.

Conflicting Attributes

class PARENT is
 attr foo:INT;
class CHILD is
 foo:BOOL;   -- ILLEGAL!
 -- Conflicts with the included reader for 'foo' i.e. foo:INT

class PARENT is
 foo(arg:INT);
class CHILD is
 include PARENT;
 -- ILLEGAL! attr foo:INT;  
 -- the writer routine foo(INT) conflicts 
 -- with the writer for the include attribute foo(INT)

5.7.6 Points to note

• It is not possible to overload based based solely on out or inout arguments (by the pre-condition for applying the overload rule 4a and 4b)

• When a class explicitly defines a signature and includes a conflicting signature from another class, the included signature is over-ridden. This might lead to included signatures unexpectedly disappearing, instead of overloading.

• In certain special cases, subtyping from two classes with conflicting signatures that use out or inout arguments might not be possible, since the conflict cannot be resolved.

5.7.7 Overloading in Parametrized Classes

5.7.8 Why not use the return type to resolve conflicts?

5.8 When Covariance Ails You

[This section attempts to provide some insight into dealing with covariance. It is not essential to understanding the language, but might help in the design of your type hierarchy.]

5.8.1 But don't animals eat food?

abstract class $ANIMAL is   eat(food:$FOOD); ....
abstract class $HERBIVORE < $ANIMAL is...
abstract class $CARNIVORE < $ANIMAL is...

5.8.2 Solution 1: Refactor the type hierarchy

5.8.3 Solution 2: Eliminate the offending method

Since we do not know the kind of food a general animal can eat, it may be reasonable to just omit the 'eat' signature from the definition of $ANIMAL. We would thus have

5.8.4 Solution 3: Dynamically Determine the Type

abstract class $ANIMAL is   eat(arg:$FOOD); ...
abstract class $HERBIVORE < $ANIMAL is -- supports eat(f:$FOOD);
 
class COW < $HERBIVORE is
 eat(arg:$FOOD) is
  typecase arg
  when $PLANT then .. -- eat it!
  else raise "Cows only eat plants!"; end;
 end;
end; 

This approach carries the danger that if a cow is fed some non-plant food, the error may only be discovered at run-time, when the routine is actually called. Furthermore, such errors may be discovered after an arbitrarily long time, when the incorrect call to the 'eat' routine actually occurs during execution.

This loss of static type-safety is inherent in languages that support co-variance, such as Eiffel. The problem can be somewhat ameliorated though the use of type-inference, but there will always be cases where type-inference cannot prove that a certain call is type-safe.

Sather permits the user to break type-safety, but only through the use of a typecase on the arguments. Such case of type un-safety uses are clearly visible in the code and are far from the default in user code.

5.8.5 Solution 4: Parametrize by the Argument Type

Parametrized Classes and Arrays

6.1 Parametrized concrete types

class PAIR{T1,T2} is 
   readonly attr first:T1; 
   readonly attr second:T2;
   
    create(a_first:T1, a_second:T2):SAME is 
      res ::= new;  
      res.first := a_first; 
      res.second := a_second;  
      return res; 
    end; 
end; 

c ::= #PAIR{INT,INT}(5,5);     -- Holds a  pair of integers 
d ::= #PAIR{INT,FLT}(5,5.0);   -- Holds an integer and a FLT 
e ::= #PAIR{STR,INT}("this",5);-- A string and an integer 
f:INT := e.second; 
g:FLT := d.second; 

6.1.1 Why Parametrize?

For instance, we could define a pair to hold $OBs

class OB_PAIR is readonly attr first,second:$OB; create(a_first, a_second:$OB):SAME is res ::= new; res.first := a_first; res.second := a_second; return res; end; end; -- class OB_PAIR

There is no problem with defining OB_PAIR objects; in fact, it looks a little simpler.

c ::= #OB_PAIR(5,5); -- Holds a pair of integers d ::= #OB_PAIR(5,5.0); -- Holds an integer and a FLT

However, when the time comes to extract the components of the pair, we are in trouble:

-- f:INT := e.second; ILLEGAL! second is declared to be a $OB 

We can typecase on the return value:
   
f_ob:$OB := e.second; 
f:INT; 
typecase f_ob when INT then f := f_ob end; 

The parametrized version of the pair container gets around all these problems by essentially annotating the type of the container with the types of the objects it contains; the types of the contained objects are the type parameter.

6.2 Support for Arrays

 a:ARRAY{INT} := |1,2,3|;

In addition to the standard accessing function, arrays provide many operations, ranging from trivial routines that return the size of the array to routines that will sort arbitrary arrays. See the array class in the container library for more details. There are several aspects to supporting arrays:

• Support for accessing array elements

• Support for objects which represent arrays

• Support for initializing these arrays using literals

6.2.1 Array Access

class TRIO is
  private attr a,b,c:FLT;
  create:SAME is return new end;
  aget(i:INT):FLT is 
     case i
     when 0 then return a
     when 1 then return b
     when 2 then return c
     else raise "Bad array index!\n"; end;
   end;
   aset(i:INT, val:FLT) is 
      case i
      when 0 then a := val;
      when 1 then b := val;
      when 2 then c := val;
   end;
end; 

trio:TRIO := #TRIO;  -- Calls TRIO::create
trio[2] := 1;
#OUT+trio[2];        -- Prints out 1

6.2.2 Array Classes: Including AREF and calling new();

class POLYGON is
   private include AREF{POINT} 
        aget->private old_aget, aset->private old_aset;  
           -- Rename aget and aset
                            
   create(n_points:INT):SAME  is
       -- Create a new polygon with a 'n_points' points
       res:SAME := new(n_points);  -- Note that the new takes 
       -- as argument of the size of the array
   end;
 
   aget(i:INT):POINT is
      if i > asize then raise "Not enough polygon points!" end;
      return old_aget(i);
   end;
 
   aset(i:INT, val:POINT) is
      if i > asize then raise "Not enough polygon points!" end;
      old_aset(i,val);
   end;
end;

poly:POLYGON := #POLYGON(3);
poly[0] := #POINT(3,4);
poly[1] := #POINT(5,6);
poly[2] := #POINT(0,0);

asize:INT                        -- Returns the size of the array
aelt!:T;                         -- Yields successive array elements
aelt!(once beg:INT):T;           -- Yields elements from index 'beg'
aelt!(once beg,once num:INT):T;  -- Yields 'num' elts from index 'beg'
aelt!(once beg,once num,once step:INT):T; 
     -- Yields 'num' elements, starting at index 'beg' with a 'step'
... Analgous versions of aset! ..
acopy(src:SAME);                  -- Copy what fits from 'src' to self 
acopy(beg:INT,src:SAME);          -- Start copying into index 'beg'
acopy(beg:INT,num:INT,src:SAME);   
    -- Copy 'num' elements into self starting at index 'beg' of self
aind!:INT;                         -- Yields successive array indices

6.2.3 Standard Arrays: ARRAY{T}

class ARRAY{T} is
 private include AREF{T} 
  -- Make these public.
  aget->aget,
  aset->aset,
  asize->asize;
 ...
 contains(e:T):BOOL is ... end
 ...
end; 

Array Literals

a:ARRAY{INT} := |2,4,6,8|;
b:ARRAY{STR} := |"apple","orange"|;

The type is taken to be the declared type of the context in which it appears and it must be ARRAY{T} for some type T. An array creation expression may not appear

• as the right hand side of a '::=' assignment

• as a method argument in which the overloading resolution is ambiguous

• as the left argument of the dot '.' operator.

a:INT := |1,2,3|.size -- ILLEGAL

6.2.4 Multi-dimensional Arrays

a:ARRAY{ARRAY{INT}} := ||1,2,3|,|3,4,5|,|5,6,7||;

6.3 Type Bounds

For our example, we will return to employees and managers. Recall that the employee abstraction was defined as:

abstract class $EMPLOYEE is name:STR; id:INT; end;

We can now build a container class that holds employees. The container class makes use of a standard library class, a LIST, which is also parametrized over the types of things being held.

class EMPLOYEE_REGISTER{ETP < $EMPLOYEE} is private attr emps:LIST{ETP};   create:SAME is res ::= new; res.emps := #; return res; end;   add_employee(e:ETP) is emps.append(e); end;   n_employees:INT is return emps.size end;   longest_name:INT is -- Return the length of the longest employee name i:INT := 0; cur_longest:INT := 0; loop until!(i=n_employees); employee:ETP := emps[i]; name:STR := employee.name; -- The type-bound has the ".name" routine if name.size > cur_longest then cur_longest := name.size; end; end; return cur_longest; end; end;

The routine of interest is "longest_name". The use of this routine is not important, but we can imagine that such a routine might be useful in formatting some printout of employee data. In this routine we go through all employees in the list, and for each employee we look at the "name". With the typebound on ETP, we know that ETP must be a subtype of $EMPLOYEE. Hence, it must have a routine "name" which returns a STR.

If we did not have the typebound (there is an implicit typebound of $OB), we could not do anything with the resulting "employee"; all we could assume is that it was a $OB, which is not very useful.

6.3.1 Why have typebounds?

6.3.2 Supertyping and Type Bounds

You may, however, wish to create a parametrized type which is instantiated with classes from an existing library which are not under the typebound you require. For instance, suppose you want to create a class PRINTABLE_ SET, whose parameters must support both hash and the standard string printing routine str. The library contains the following abstract classes.

abstract class $HASH < $IS_EQ is hash:INT; end; abstract class $STR is str:STR; end;

However, our PRINTABLE_SET{T} must take all kinds of objects that support both $HASH and $STR, such as integers, floating point numbers etc. How do we support this, without modifying the distributed library?

abstract class $HASH_AND_STR > INT, FLT, STR is hash:INT; str:STR; end;   class PRINTABLE_SET{T < $HASH_AND_STR} is ... -- Set whose elements can be printed   str:STR is res:STR := ""; loop res := res+",".separate!(elt!.str); end; return res; end;

The PRINTABLE_SET class can now be instantiated using integers, floating point numbers and strings. Thus, supertyping provides a way of creating supertypes without modifying the original classes (which is not possible if the original types are in a different library).

Note that this is only useful if the original classes cannot be modified. In general, it is usually far simpler and easier to understand if standard subtyping is used.

A more complicated example arises if we want to create a sorted set, whose elements must be hashable and comparable. From the library we have.

abstract class $HASH < $IS_EQ is hash:INT; end; abstract class $IS_LT{T} < $IS_EQ is -- comparable values is_lt(elt:T):BOOL; end;

However, our SORTABLE_SET{T} must only take objects that support both $HASH and $IS_LT{T}

abstract class $ORDERED_HASH{T} < $HASH, $IS_LT{T} is end;   class ORDERED_SET{T < $ORDERED_HASH{T}} is ... -- Set whose elements can be sorted   sort is -- ... uses the < routine on elements which are of type T end;

The above definition works in a straightforward way for user classes. For instance, a POINT class as defined below, can be used in a ORDERED_SET{POINT}

class POINT < $ORDERED_HASH{POINT} is .... -- define hash:INT and is_lt(POINT):BOOL

But how can you create an ordered set of integers, for instance? The solution is somewhat laborious. You have to create dummy classes that specify the subtyping link for each different parametrization of $ORDERED_HASH

abstract class $DUMMY_INT > INT < $ORDERED_HASH{INT} is end; abstract class $DUMMY_STR > STR < $ORDERED_HASH{STR} is end; abstract class $DUMMY_FLT > FLT < $ORDERED_HASH{FLT} is end;

Note that the above classes are only needed because we are not directly modifying INT and FLT to subtype from $ORDRED_HASH{T}. In the following diagram , recall that since there is no relationship between different class parametrizations, it is necessary to think of them as separate types.

6.4 Parametrized Abstract Classes

Sather abstract classes may be similarly parametrized by any number of type parameters. Each type parameter may have an optional type bound; this forces any actual parameter to be a subtype of the corresponding type bound. Given the following definitions,

abstract class $A{T < $BAR} is foo(b:T):T; end; -- abstract class $A{T} abstract $BAR is end; class BAR < $BAR is end;

we may then instantiate an abstract variable a:$A{BAR}. BAR instantiates the parameter T and hence must be under the type bound for T, namely$BAR. If a type-bound is not specified then a type bound of $OB is assumed.

How are different parametrizations related?

6.5 Overloading

6.5.1 Overloading In the Parametrized Class Interface

class FOO{T1<$STR ,T2<$ELT} is
 
(1)  bar(a:T1);
(2)  bar(a:T2);

FOO{ARRAY{INT}, ARRAY{INT}}

for instance, the two versions of 'bar' will essentially be identical.

6.5.2 Overloading Resolution within the Parametrized Class

For all calls within the parametrized class, the resolution of overloading is done with respect to the type bounds of the parameters. Consider a class that makes use of output streams

abstract class $OSTREAM is plus(s:$STR); end;

A parametrized class can then write to any output stream

class FOO{S < $OSTREAM} is   attr x,y:INT;   describe(s:S) is s+"Self is:"; s+x; s+",";s+y; end; end;

Now, suppose we instantiate the class FOO with a FILE

class FILE < $OSTREAM is (1) plus(s:$STR) is ... (2) plus(s:INT) is ...   a:FOO{FILE} := .. f:FILE := FILE::open_for_read("myfile"); a.describe(f)

Only '(1) plus($STR)' will be called in FOO{FILE}, even though the more specific '(2) plus(INT)' is available in FILE.

The reason for this behavior is to preseve the ability to analyze a stand alone class, which is needed for separate compilation of parametrized classes - this requires that the behavior of the parametrized class be completely determined by the typebounds and not based on the existance of specialized overloaded routines in particular instantiations.

Operator Redefinition

7.1 Method Names for Operators

class POINT is 
 readonly attr x,y:INT;
 create(x,y:INT):SAME is ... -- same as before
 plus(s:POINT):POINT  is  return #POINT(x + s.x, y + s.y); end;

p1:POINT := #POINT(3,5); 
p2:POINT := #POINT(4,6);
p3:POINT := p1 + p2;  --  p3 is set to the point 7,11

7.2 Operator expressions

Below are the routines that correspond to unary operators, for arithmetic and logical negation

Unary Operators

Unary Operator	Routine
- expr	expr.negate
~ expr	expr.not

.

In addition to the unary and binary operators, there are additional operators that are defined in terms of a combination of the unary and binary operators

Compound Operators

Operator	Translation	Operator	Translation
expr1 <= expr2	expr2.is_lt(expr1).not	expr1 /= expr2	expr1.is_eq(expr2).not
expr1 >= expr2	expr1.is_lt(expr2).not	expr1 > expr2	expr2.is_lt(expr1)

[3].

The form '[expression list]' is translated into a call on the routine aget. For instance,

a := [3,5]; -- Equivalent to a := aget(3,5); Used in the array class f := arr[2]; -- Equivalent to f := arr.aget(2); Used outside the array

This is described in more detail later.

Grouping

7.2.1 Operator precedence

Points to note

• The >, >= and /= operators are not directly translated into their own routine. Rather, they are defined in terms of is_lt and is_eq.

• Each of these transformations is applied after the component expressions have themselves been transformed.

• 'out' and 'inout' modes may not be used with the syntactic sugar expressions.

• The '<=' and '>' expressions do not reverse the original left to right order of argument evaluation.

• and' and or' are not listed as syntactic sugar for operations in BOOL'; this allows short-circuiting the evaluation of subexpression.

• The aget and aset routines are meant to support array like indexed access and require at least one index argument.

Syntactic sugar example

-- Written using syntactic sugar
r := (x^2 + y^2).sqrt;
 
-- Written without sugar
r := (x.pow(2).plus(y.pow(2))).sqrt

7.3 Array Access Routines

a:ARRAY{INT} := |1,2,3|;
a[2] := 5;             -- Sets the third element of the array to 5
#OUT+a[0];             -- Prints out '1'
c:ARRAY2{INT} := ||1,2,3|,|4,5,6|,|7,8,9||;
#OUT + c[2,2];         -- Prints out '9'

a[2] := 5; -- equivalent to a.aset(2,5);
#OUT+a[1]; -- equivalent to #OUT+a.aget(1);

Thus, classes which are not arrays can make use of the array notation as they please:

class INT is -- The standard integer class aget(i:INT):BOOL is -- returns the 'i'th bit of the integer end;

In order for a class to actually have an array portion, it must inherit from AREF{T} (if it is a reference class) or AVAL{T} if it is a value class. The array setting notation is not as useful for immutable classes, since any modification of an immutable class must return a whole new object.

Immutable Classes

At a fundamental level: immutable classes define objects which, once created, never change their value. A variable of an immutable type may only be changed by re-assigning to that variable. When we wish to only modify some portion of an immutable class, we are compelled to reassign the whole object. For experienced C programmers the difference between immutable and reference classes is similar to the difference between structs (immutable types) and pointers to structs (reference types). Because of that difference, reference objects can be referred to from more than one variable (aliased), while immutable objects cannot.

This section illustrates the definition of immutable types using a simple version of the complex number class, CPX. We also describe the benefits of immutable classes and when they should be used. Finally, we close with a description of a how to transparently replace in immutable class by a standard reference class which implements value semantics.

8.1 Defining Immutable Classes

8.1.1 Immutable Class Example

immutable class CPX  is 
 readonly attr real,imag:FLT; 
 
 create(re,im:FLT):SAME is 
  -- Returns a complex number with real and imaginary parts set 
  res:SAME;
  res := res.real(re);
  res := res.im(im);
  return res;
 end;
 
 plus(c:SAME):SAME is 
  -- Return a complex number, the sum of 'self' and c'. 
  return  #SAME(real+c.real,imag+c.imag); 
 end; 
end; -- immutable class CPX

 b:CPX := #(2.0,3.0); 
 d:CPX := #(4.0,5.0); 
 c:CPX := b+d;  

8.1.2 Creating a new object

8.1.3 Initial value of immutable objects

Void value of the basic classes:

Class	Initial Value	Class	Initial Value
INT	0	CHAR	'\0'
FLT	0.0	FLTD	0.0d
BOOL	false

8.1.4 Attribute access routines

re(new_re_part:FLT):SAME 

which returns a copy of the original CPX object in which the attribute 're' has the new value 'new_re_value'. Contrast this with a reference class, in which the setting routine would have the signature

re(new_re_part:FLT);

The syntax of the setting routines of immutable classes is a common source of confusion.

8.1.5 Points to note

• There must be no cycle of immutable types such that each type has an attribute whose type is in the cycle. In the following example, the class PAIR has a FIRST_PART that contains a PAIR - leading to an infinite loop and an infinite size structure.

  immutable class PAIR is attr first:FIRST_PART; attr second:SECOND_PART; ... immutable class FIRST_PART is attr begin:PAIR;...

• Accessing an attribute of a void immutable object will always work. Accessing an attribute of a void reference object results in a fatal error

• The 'void' value for the basic classes are useful values - false is the 'void' value for the BOOL class, and 0 for the number classes.

8.2 Using Immutable Classes

To begin with, immutable classes cannot suffer from aliasing problems, since they are immutable. You can get the same effect with reference classes by not providing any modifying operations in the interface - any operation that would modify the object, returns a new object instead. For example, take a look at the STR class

Immutable classes may have several efficiency advantages over reference classes in certain circumstances. Since they are usually stored on the stack, they have no heap management overhead and need not be garbage collected. They also don't use space to store a tag, and the absence of aliasing makes more C compiler optimizations possible. For a small class like CPX, all these factors combine to give a significant win over a reference class implementation. On the other hand, copying large immutable objects onto the stack can incur significant overhead. Unfortunately the efficiency of an immutable class appears directly tied to how smart the C compiler is; "gcc" is not very bright in this respect.

Note that when an immutable class is passed as an argument to a function which is expecting an abstract type, the compiler boxes it i.e. it is given a temporary reference class wrapper with a type-tag. Thus, immutable objects behaves exactly like an immutable reference objects in this situation.

Rules of Thumb

• You want the class to have immutable semantics. You could still consider an immutable reference class.

• The class is small - the exact speed trade-offs have not been investigated, but immutable classes have so far been used when there are a fewer than a handful of attributes.

• There are going to be a large number of objects of that class. This goes along with the previous point. For instance, if you are going to have large arrays of complex numbers, then the space that would be required for an object pointer and an object tag may be considerable.

Closures

9.1 Creating and Calling Closures

9.1.1 Creating a closure

a:ROUT{INT}:INT :=  bind(3.plus(_))
b:ITER:INT := bind(3.times!);

swap(inout x, inout y:INT) is  tmp::= x;  x := y; y:=tmp; end;

The routine 'swap' swaps the values of the two arguments, 'x' and 'y'. 'r' is a closure for binding the 'swap' routine.

r:ROUT{inout INT, inout INT} := bind(swap(_,_));

9.1.2 Calling a closure

The previously defined closures are invoked as shown

#OUT+ a.call(4); -- Prints out 7, where a is bind(3.plus(_) sum:INT := 0; loop sum := sum + b.call!; end; #OUT+sum; -- Prints out 3 (0+1+2)

In the following example, we define a bound routine that takes an INT as an argument and returns an INT.

br:ROUT{INT}:INT := bind(1.plus(_)); #OUT+br.call(9); -- Prints out '10'

The variable br is typed as a bound routine which takes an integer as argument and returns an integer. The routine 1.plus, which is of the appropriate type, is then assigned to br. The routine associated with br may then be invoked by the built in function call. Just as we would when calling the routine INT::plus(INT), we must supply the integer argument to the bound routine.

9.1.3 Binding overloaded routines

class FLT is
   plus(f:FLT):FLT  -- add self and 'i' and return the result
   plus(i:INT):FLT; -- add self and 'f' (after converting 'i' to FLT)
end;   

b ::= bind(_.plus(_));

In case of ambiguity, the right method must be determined by the context in which the binding takes place.

Binding in an assignment

b:ROUT{FLT,FLT}:FLT := bind(_.plus(_)); -- Selects the first 'plus' 

Binding in a call

reduce(a:ARRAY{FLT}, br:ROUT{FLT,FLT}:FLT):FLT is
  res:FLT := 0.0;
  loop el:FLT := a.elt!; res := br.call(res,el); end;
  return res;
end;

a:ARRAY{FLT} := |1.0,7.0,3.0|;
#OUT + reduce(a,bind(_.plus(_))); 
-- Prints '11.0', the sum of the elements of 'a'

r:ROUT{FLT,FLT}:FLT := bind(_.plus(_));
#OUT+reduce(a,r);

9.1.4 Points to note

• out and inout arguments must be left unbound. This is a reasonable restriction, since such arguments must return a value to the calling context. If such an argument were bound, when the closure is invoked, variables that existed at the point of closure binding would be affected. Such variables might not even be alive at the point where the closure is actually invoked.

9.1.5 Binding some arguments

class MAIN is 
 
 foo(a:INT, b:INT):INT is return(a+b+10) end;
 
 main is 
  br1:ROUT{INT,INT}:INT := bind(foo(_,_));   
  br2:ROUT{INT}:INT := bind(foo(10,_)); 
  #OUT+br1.call(4,3)+","+br2.call(9); -- Should print 17 and  29
 end; 
end;

Here we double every element of an array by applying a routine closure r to each element of an array.

r :ROUT{INT}:INT := bind(2.times(_)); loop a.set!(r.call(a.elt!)) end

9.1.6 Leaving self unbound

r :ROUT{INT} := bind(_.plus(3));
#OUT + r.call(5);                        -- prints '8'

 ... from the INT class 
plus(arg:INT):INT is        ... definition of plus 
 
main is 
  plusbr1:ROUT{INT,INT}:INT:=bind(_.plus(_));  -- self and arg unbound
  br1res:INT := plusbr1.call(9,10);         -- Returns 19 
  plusbr2:ROUT{INT}:INT := bind(3.plus(_)); -- Binding self only
  br2res:INT := plusbr2.call(15);           -- Returns 18 
  plusbr3:ROUT{INT}:INT := bind(_.plus(9)); -- Binding arg only
  br3res:INT := plusbr3.call(11);           -- Returns 20 
  #OUT+br1res+","+br2res+","+br3res;        -- 19,18,20 
end; 

9.2 Further Examples of Closures

9.2.1 Closures for Applicative Programming

every(test:ROUT{T}:BOOL):BOOL is 
 -- True if every element of self satisfies 'test'. 
  loop 
  e ::= elt!;   -- Iterate through the array elements
  if ~test.call(e) then return false end  
  -- If e fails the test, return false immediately
 end; 
  return true 
end; 

select(e:ARRAY{INT}, r:ROUT{INT}:BOOL):INT is
  -- Return the index of the first element in the array 'e' that 
  -- satisfies the predicate 'r'.
  -- Return -1 if no element of 'e' satisfies the predicate.
  loop i:INT := e.ind!;
       if r.call(e[i]) then  return i end;
  end;
  return -1;
end;
        
 

a:ARRAY{INT} := |1,2,3,7|;
br:ROUT{INT}:BOOL := bind(_.is_eq(3));
#OUT + select(a,br);  -- Prints the index of the first element of 'a'
                      -- that is equal to '3'. The index printed is '2'

9.2.2 Menu Structures

class MENU is 
 
  private attr menu_actions:MAP{STR,ROUT}; 
        -- Hash table from strings to closures
  private attr default_action:ROUT{STR};
 
  create(default_act:ROUT{STR}):SAME is 
    res:SAME := new; 
    res.menu_actions := #MAP{STR,ROUT}; 
    res.default_action := default_act;
    return(res)    
  end; 
 
  add_item(name:STR, func:ROUT) is menu_actions[name] := func end;
     -- Add a menu item to the hash table, indexed by 'name' 
  
  run is   
     loop 
       #OUT+">"; 
       command: STR := IN::get_str;  -- Gets the next line of  input
       if command = "done" then break!
       elsif menu_actions.has_ind(command) then
   menu_actions[command].call;
       else 
   default_action.call(command); 
       end;
     end;   
   end;    
end; 

class CALCULATOR is
   
   private attr stack:A_STACK{INT};
   private attr menu:MENU;
   
   create:SAME is res ::= new; res.init; return res; end;
   
   private init is   -- Initialize the calculator attributes
      stack := #; 
      menu := #MENU(bind(push(_)));
      menu.add_menu_item("add",bind(add)); 
      menu.add_menu_item("times",bind(times)); 
   end;
   
   run is menu.run; end;
   ....
  

push(s:STR) is
      -- Convert the value 's' into an INT and push it onto the stack
      -- Do nothing if the string is not a valid integer
      c: STR_CURSOR := s.cursor;
      i: INT := c.int;
      if c.has_error then #ERR+"Bad integer value:"+s; 
      else  stack.push(i); end;
   end;
   
   add is  -- Add the two top stack values and push/print the result
      sum:INT := stack.pop+stack.pop;
      #OUT+sum+"\n";
      stack.push(sum);
   end;
   
   times is  -- Multiply the top stack values and push/print the result
      product:INT := stack.pop*stack.pop;
      #OUT+product+"\n";
      stack.push(product);
   end;
end;  -- class CALCULATOR

class MAIN is  main is c: CALCULATOR := #;   c.run;  end;end;

After compiling the program, we can then run the resulting executable

pts/1 samosa:~/Sather>a.out >3 >4 >add 7 >10 >11 >times 110 >done pts/1 samosa:~/Sather>

9.2.3 Iterator closures

Exceptions

10.1 Throwing and Catching Exceptions

10.1.1 Throwing Exceptions with raise

 add_if_positive(i:INT) is 
    if i < 0 then
       raise "Negative value:"+i+"\n";
    end;
 end;

10.1.2 Catching Exceptions with protect

 protect 
      foo; 
  when $STR then #ERR+"An error in foo!:"+exception.str;
  when INT then #ERR+"INT error="+exception; -- 'exception' of type INT
  else
     -- Some other error handling
  end;

In the protect clause, the exception raised may be referred to by the built in expression 'exception'[4], which refers to the exception object. The type of the exception object can be used to categorize the exception and to discriminate between exceptions when they are actually caught. In fact, the when clauses may be viewed as a typecase (see page 90) on the exception object.

Points to note

• No statements may follow a raise statement in a statement list because they can never be executed.

• If there is no else clause in a protect statement, and none of the types in the when branches matches the type of the exception object, then the exception is passed to the next higher protect statement

10.1.3 Usage to avoid

 test_bool:BOOL is 
    protect 
        current_state ::= save_state; 
        b ::= get_bool; 
        restore_state(current_state); 
     when STR_CURSOR_EX then return(false); end; 
     return(true); 
  end; 

10.1.4 Alternatives to Exceptions

10.2 A more elaborate example

get_bool(file_name:STR):BOOL is
 f:FILE := FILE::open_for_read(file_name);
 if f.error then   raise #FILE_OPEN_EXC(file_name);  end;
 s:STR := f.str;  -- Read the file into a string
 f.close;          -- Close the file
 res:BOOL;
 bool ::= "";
 i:INT := 0;
 loop until!(~(s[i].is_alpha) or (s[i].is_space) or i >= s.size);
   bool := bool + s[i]; i := i + 1;
 end;
 case bool
 when "true","t","True","T","TRUE" then  return true;
 when "false","f","False","F","FALSE" then return false;
 else  
  raise #PARSE_BAD_BOOL_EXC(s); 
 end;
end;

protect 
   file_name:STR; ... set to a value
   b:BOOL := get_bool(s);
when FILE_OPEN_EXC then #ERR+"Could not open:"+exception.file_name+"\n";
when PARSE_BAD_BOOL_EXC then 
    #ERR+"Error in reading boolean:"+exception.str+"\n";
end;

class FILE_OPEN_EXC is
 readonly attr str:STR:
 create(file_name:STR):SAME is 
  res::=new; res.str := file_name; return res;
 end;
end;

Safety Features

These safety features are associated with the notion of programming contracts. The precondition of a method is the contract that the method requires the caller to fulfill. It is a statement of the condition of the world that the method needs to find, in order to work correctly. The postcondition is a contract that the method guarantees, if its precondition has been met. It is a statement of the state the method will leave the world in, when it is finished executing. These programming contracts are very important in the creation of robust, reusable code.

In addition to providing a level of checking, these safety features are also an invaluable form of documentation. Since preconditions and postconditions must actually execute, they can be trusted to be accurate and up-to-date, unlike method comments which may easily fall out of sync with the code.

11.1 Preconditions

The optional 'pre' construct of method definitions contains a boolean expression which must evaluate to true whenever the method is called; it is a fatal error if it evaluates to false.The expression may refer to self and to the routine's arguments. For iterators, pre and post conditions are checked before and after every invocation of the iterator (not just the first or last time the iterator is called).

class POSITIVE_INTERVAL is readonly attr start, finish:INT; create(start, finish:INT) -- Ensure that the interval is positive on positive numbers pre start > 0 and finish > 0 and finish-start >= 0 is res ::= new; res.start := start; res.finish := finish; return res; end; end; -- class POSITIVE_INTERVAL

Note that it is usually not appropriate to place conditions on the internal state in the precondition. This is an inappropriate conduct, since it may be impossible for the caller to determine whether the conduct can be properly fulfilled.

move_by(i:INT) pre start > 0 is ...

The test on 'start' is actually verifying something about the internal state of the object, and has nothing to do with the caller of the routine. Tests such as the one above are more appropriately placed in assertions.

11.2 Postconditions

The optional 'post' construct of method definitions contains a boolean expression which must evaluate to true whenever the method returns; it is a fatal error if it evaluates to false. The expression may refer to self and to the method's arguments.

class VECTOR is ... norm:FLT; -- norm of the vector   normalize post norm = 1.0 is ... -- Normalize the vector. The norm of the result must be 1.0

It is frequently useful to refer to the values of the arguments before the call, as well as the result of the method call. A problem arises because the initial argument values are no longer known by the time the method terminates, since they may have been arbitrarily modified. Also, since the post condition is outside the scope of the method body, it cannot easily refer to values which are computed before the method executes. The solution to this problem consists of using result expressions which provide the return value of the method and initial expressions which are evaluated at the time the method is invoked.

11.2.1 initial expressions

add(a:INT):INT post initial(a)>result is ..

11.2.2 result expressions

sum:INT  post result > 5 is . -- Means that the value return must be > 5

Result expressions may only appear within the postconditions of methods that have return values and may not appear within initial expressions. A result expression returns the value returned by the routine or yielded by the iterator. The type of a result expression is the return type of the method in which it appears (INT, in the above example).

11.2.3 Example

class CALCULATOR is
 readonly attr sum:INT;  -- Always kept positive 
 
 add_positive(x:INT):INT pre x > 0 post result >= initial(x) is
         return sum + x; end; 
 

11.3 Assertions

11.3.1 assert statements

private attr arr:ARRAY{INT};  
...
sum_of_elts is
 -- 
 sum:INT := 0;
 loop e ::= arr.elt!;
  assert e > 0;
  sum := sum + e;
 end;
 return sum;
end;

11.4 Invariants

11.4.1 The invariant routine

Consider a class with a list (we use the library class A_LIST) whose size must always be at least 1. Such a situtation could arise if the array usually contains the same sort of elements and we want to use the first element of the array as a prototypical element)

class PROTO_LIST is private attr l:A_LIST{FOO};   create(first_elt:FOO):SAME is res ::= new; res.l := #; res.l.append(first_elt); return res; end;   invariant:BOOL is return l.size > 0 end;   delete_last:FOO is return l.delete_elt(l.size-1); end;

If the 'delete_last' operation is called on the last element, then the assertion will be violated and an error will result.

proto:FOO := #; -- Some FOO object a:PROTO_LIST := #(FOO); last :FOO := a.delete_last; -- At runtime, an invariant violation will occur -- for trying to remove the last element.

The invariant is checked at the end of every public method. However, the invariant is not checked after a private routine. If we have the additional routines

delete_and_add is f :FOO res ::= internal_delete_last; l.append(res); return res; end;   private internal_delete_last:FOO is return l.delete_elt(l.size-1); end;

Now we can call 'delete_and_add'

proto:FOO := #; a:PROTO_LIST := #(FOO); last:FOO := a.delete_and_add; -- does not violate the class invariant

The private call to 'internal_delete_last' does violate the invariant, but it is not checked, since it is a private routine.

Built-in classes

12.1 Fundamental Classes

12.1.1 $OB

12.1.2 Array support

• 'AREF{T}' is a reference array class. Any reference class which includes it obtains an array of elements of type T in addition to any attributes it has defined. In such classes, new has a single integer argument that specifies the size of the array portion. It defines routines and iters named: 'asize', 'aget', 'aset', 'aclear', 'acopy', 'aelt!', 'aset!', and 'aind!'. Array indices start at zero.

• 'ARRAY{T}' includes from 'AREF' and defines general purpose array objects. They may be directly constructed by array creation expressions.

• 'AVAL{T}' is the immutable class analog of 'AREF'. Classes which include 'AVAL' must define asize as an integer constant which determines the size of the array portion.

12.2 Tuples

'TUP' names a set of parameterized immutable types called tuples, one for each number of parameters. Each has as many attributes as parameters and they are named 't1', 't2', etc. Each is declared by the type of the corresponding parameter (e.g. 'TUP{INT,FLT}' has attributes 't1:INT' and 't2:FLT'). It defines 'create' with an argument corresponding to each attribute.

12.3 The SYS Class

12.4 Object Finalization: $FINALIZE

12.5 Basic Classes and Literal Forms

12.5.1 Booleans and the BOOL class

Examples:	a:BOOL := true
	b ::= false;
	c:BOOL := a.and(b);
	if a.and(b).or(d) then
	end;

if  b.has_value and b.get_value > 3 then
  -- The short circuit and will only evaluate b.get_value  
    -- if b.has_value is true
end;

12.5.2 Characters and the CHAR class

Examples:	c:CHAR := 'a'
	new_line:CHAR := '\n';
	code_16:CHAR := '\016';

• '\a' is an alert such as a bell,

• '\b' is the backspace character,

• '\f' is the form feed character,

• '\n' is the newline character,

• '\r' is the carriage return character,

• '\t' is the horizontal tab character,

• '\v' is the vertical tab character,

• '\\' is the backslash character,

• '\'' is the single quote character

• '\"' is the double quote character.

12.5.3 The string class, STR

Examples:	s:STR := "a string literal"
	d:STR := "concat" "enation\015"
	-- d is "concatenation\015"

12.5.4 Integers and the INT class

Examples:	a:INT := 14;
	b:INT := -4532
	c:INT := 39_8322_983_298
	binary:INT := 0b101011;
	bin:INT := -0b_101010_1010
	octal:ITN := 0o37323
	hex_num:INT:= 0x_ea_75_67

Underscores may be used to separate the digits of an integer to improve readability - this may be particularly useful for very long binary numbers.

12.5.5 Infinite precision integers and the INTI class

Examples:	b:INTI := -4532i
	infinite_hex:INTI := 0o373254i

12.5.6 Floating point numbers: the FLT and FLTD classes

Examples:	f:FLT := 12.34
	fd:FLTD := 3.498_239e-8d

flt_literal_expression [-] decimal_int . decimal_int [e [-] decimal_int] [ d ]

FLT and FLTD objects represent floating point numbers according to the single and double representations defined by the IEEE-754-1985 standard (see also page 143). A floating point literal is of type FLT unless suffixed by 'd' designating a FLTD literal. The optional 'e' portion is used to specify a power of 10 by which to multiply the decimal value. Underscores may be used within floating point literals to improve readability and are ignored. Literal values are only legal if they are within the range specified by the IEEE standard.

Sather does not do implicit type coercions (such as promoting an integer to floating point when used in a floating point context.) Types must instead be promoted explicitly by the programmer. This avoids a number of portability and precision issues (for example, when an integer can't be represented by the floating point representation.

The following two expressions are equivalent. In the first, the 'd' is a literal suffix denoting the type. In the second, '3.14' is the literal and '.fltd' is an explicit conversion.

3.14d -- A double precision literal 3.14.fltd -- Single, but converted

12.6 Library Conventions

• Classes which are related should reflect this in their names. For example, there are many examples in the library of an abstraction, classes implementing the abstraction, and code testing implementations of the abstraction. For example, in the standard library the set abstraction is named $SET, H_SET is a hash table implementation, and the test code is TEST_SET.

• Some classes implement an immutable, 'mathematical' abstraction (eg. integers), and others implement mutable "object" abstractions that can be modified in place (eg. arrays). For most objects, the mutable, object semantics are natural and efficient. However, for classes such as sets, the semantics may be different from those of the traditional mathematical set entities.

• Classes with immutable semantics are given their 'mathematical' names: STR, VEC, $SET. When separate abstractions exist to handle value and reference semantics, the method value will be provided in the reference version to provide an immutable snapshop of the reference class.

• Conversions from a type FOO to a type BAR occur in two ways: by defining an appropriate 'create(f:FOO):BAR' routine in BAR as seen above, or be defining a routine 'bar:BAR' in FOO. For example, in the standard library conversion of a FLT to a FLTD is done by calling the routine 'fltd:FLTD' defined in FLT.

• Methods which return a BOOL (called predicates), usually have the prefix 'is_'. For example, 'is_prime' tests integers for primality.

• Abstract classes that require a single method should be named after that method. For example, subtypes of $HASH define the method 'hash'.

• If there is a single iterator in a container class which returns all of the items, it should be named 'elt!'. If there is a single iterator which sets the items, it should be named 'set!'. In general, iterators should have singular ('elt!') rather than plural ('elts!') names if the choice is arbitrary.

12.6.1 Object Identity

The SYS class (page 142) can be used to obtain equality based on pointer or structural notions of identity. This class also provides built-in mechanisms for comparison and hashing.

IS_EQ

abstract class $IS_EQ is   
 is_eq(e:$OB):BOOL;
end; 

class STR < $IS_EQ is ...
 is_eq(arg:$OB):BOOL is ... end;
 ...
end; -- class STR.

Programmer defined hash functions and $HASH

abstract class $HASH is  
 hash:INT;
end; 

Objects that can be copied and $COPY

.abstract class $COPY is  
 copy:SAME;
end; 

12.6.2 Nil and void

It is often algorithmically convenient to have a sentinel value which has a special interpretation. For example, hash tables often distinguish empty table entries without a separate bit indicating that an entry is empty. Because void is a legitimate value for immutable types, void can't be used as this sentinel value. For this reason, classes may define a 'nil' value to be used to represent the non-existence of an immutable object. Such classes subtype from $NIL and define the routines 'nil:SAME' and 'is_nil: BOOL'.

The 'nil' value is generally a rarely used or illegal value. For INT, it is the most negative representable integer. For floating point types, it is NaN. 'is_nil' is necessary because NaN is defined by IEEE to not be equal to itself.

abstract class $NIL is nil:SAME; is_nil:BOOL; end; -- anstract class $NIL