-------------------------------------
-- CSE505 Homework 5 Sample Solutions
--

-- Question 1

(--
`Tree' is declared abstract because at runtime no "instances" of `Tree'
(in Cecil, this means no anonymous children of `Tree') are supposed to be
created and the `Tree' object itself is not supposed to be manipulated
directly.  Abstract objects/classes are used to factor out code shared
by its descendants (such as `print_string') and declare the interface the
descendants must implement (which includes, e.g., the `do' method).

For a template/concrete object/class, the typechecker must ensure that
all signatures applicable to it are properly implemented.  For an
abstract object/class, there is no need to check that; instead, it
must be checked that no instances of it are created.
--)


-- Question 2

(--
The `print_string' method is a factored method because it is defined for
Tree and is inherited by all its descendants (unless they overwrite it).

The body of this method sends `do' message to its argument (which is
the equivalent of "self" in Cecil).  The subclasses of Tree define
their own do methods, so the behavior of `print_string' depends on the
behavior of `do' implemented by the subclasses.
--)


-- Question 3
--
-- (Note: the code here is essentially the same as in the sample
--  solution for Homework 4 but with less white space in it.)

----------------------
-- declare the hierarchy and creation methods
----------------------

abstract object Tree[`T];
  --
  -- declare the interface
  signature print_string(t:Tree[`T]):string;
  signature do(t:Tree[`T], closure:&(elm:T):void):void;
  signature reduce_tree(t:Tree[`T], op:&(x:T,y:T):T, unit:T):T;

(--
For `insert' and `member' to work, we need to ensure that the `=' and `<'
messages sent to tree elements are type-correct.  For that, we need to
constrain the tree element type T.  Here are several alternatives.

We chose to use a subtype F-bounded constraint `T <= ordered[T]' (see
the definition or `ordered[T]' in the stdlib file `comparable.cecil'),
for example,

	signature insert(t:Tree[`T], val:T):Tree[T]
	  where T <= ordered[T];

Cecil allows the same constraint to be expressed using a more convenient
syntax, by putting it next to the backquoted type variable:

	signature insert(t:Tree[`T <= Ordered[T]], val:T):Tree[T];

Alternatively, we could use signature constraints to specify that the two
messages that we care about should be provided by tree elemetns:

	signature insert(t:Tree[`T], val:T):Tree[T]
	  where signature =(T,T):bool, signature <(T,T):bool;

Currently, Cecil does not provide a way to specify these constraints
more conveniently; this is one reason we use signature constraints
less often than subtype constraints in Vortex code.

Another issue is whether we want to constrain the type parameter of the
`insert' and `member' methods only or for any tree in general.  So far
we have only considered constraining the type parameters of `insert' and
`member'.  This means that we can have trees whose elements do not
provide `=' and `<' and so we cannot run `insert' and `member' on them
(the typechecker ensures statically that these methods are not run on
such trees).  However, we can still create such trees using `new_node'
and run `do' and `reduce_tree' on them.

Alternatively, we may choose to require that all trees support `member'
and `insert'.  Then, we would constrain the type parameter of `Tree' and
`Node', for example, using the signature constraints:

	abstract object Tree[`T]
	  where signature =(T,T):bool, signature <(T,T):bool;

	template object Node[`T] isa Tree[T]
	  where signature =(T,T):bool, signature <(T,T):bool;

So, we wouldn't be able (disallowed statically by the typechecker) to
create trees whose elements don't support `=' and `<', but we would be
allowed to run `member' and `insert' on any legal tree.

There would be no need to impose these constraints particularly on the
`member' and `insert' methods - they would be inferred automatically by
the typechecker whenever `Tree' or `Node' is parameterized with a
backquoted type variable, for example:

	signature insert(t:Tree[`Elm], val:Elm):Tree[Elm];
	-- "where signature =(Elm,Elm):bool,signature <(Elm,Elm):bool" inferred
	-- automatically by typechecker
--)

  signature insert(t:Tree[`T], val:T):Tree[T] where T <= ordered[T];
  signature member(t:Tree[`T], val:T):bool   where T <= ordered[T];

template object Node[`T] isa Tree[T];
  --
  var field left(n@:Node[`T]):Tree[T];
  var field right(n@:Node[`T]):Tree[T];
  var field element(n@:Node[`T]):T;

-- Empty is a subtype of Tree with any element type
concrete object Empty isa Tree[`T];

method print_string(tree@:Tree[`T]):string
{   let var s:string   := "tree{";
    let var first:bool := true;
    tree.do(&(elem:T){
	if(first, { first := false }, { s := s || "," });
	s := s || elem.print_string;
    });
    s || "}"  }

-- must specify explicitly the type of tree elements, for example,
-- to allow creating a tree of numbers given an integer
--
method new_node[`T](value:T):Tree[T]
{ object isa Node[T] { left := Empty, right := Empty, element := value } }

-- here, the tree element type can be inferred from l and r
method new_node(l:Tree[`T], r:Tree[`T], value:T):Tree[T]
{ object isa Node[T] { left := l, right := r, element := value } }


----------------------
-- example trees
--
let emptyTree:Empty := Empty;
let var mutableEmptyTree:Tree[int] := Empty;
let var unitTree:Tree[num] := new_node[num](5);
let var complexTree:Tree[num] := new_node(Empty, unitTree, 2);


----------------------
-- insert, member
----------------------

method insert(n@:Node[`T], val:T):Tree[T] where T <= ordered[T]
{   if(val = n.element, { ^n });
    if (val < n.element,
	{ new_node(insert(n.left, val), n.right, n.element) },
	{ new_node(n.left, insert(n.right, val), n.element) }) }

-- here we use a separate type annotation for `n' to know the element
-- type of the tree we are handling
--
method insert(n@Empty:Tree[`T], val:T):Tree[T] { new_node[T](val) }


method member(n@:Empty, val:`T):bool { false }

method member(n@:Node[`T], val:T):bool where T <= ordered[T]
{   if (val = n.element, { ^true });
    if (val < n.element,
	{ member(n.left, val) },
	{ member(n.right, val) }) }


----------------------
-- example tests
--
insert(Empty, 4);
member(complexTree, 3);
member(insert(complexTree, 3), 3);


----------------------
-- do, sum_tree
----------------------

method do(n@:Empty, closure:&(elm:`T):void):void { }
method do(n@:Node[`T], closure:&(elm:T):void):void
{   eval(closure, n.element);
    do(n.left, closure);
    do(n.right, closure);
}

-- tree whose element type is any subtype of number is OK
method sum_tree(tree@:Tree[`T]):num  where T <= num
{   let var sum:num := 0;
    tree.do( &(element:T) { sum := sum + element; });
    sum  }

-- testing
sum_tree(complexTree);


----------------------
-- reduce_tree
----------------------

method reduce_tree(tree@:Empty, operator:&(x:T,y:T):T, unit:`T):T { unit }
method reduce_tree(tree@:Node[`T], operator:&(x:T,y:T):T, unit:T):T
{   eval(operator,
	 eval(operator,
	      reduce_tree(tree.left, operator, unit),
	      tree.element),
	 reduce_tree(tree.right, operator, unit)) }


-- It is possible to have a more general typing of reduce_tree
-- (for simplicity, here I wrote it with `do').
-- It is up to the typechecker to find the appropriate types for T and S.
--
method generalized_reduce_tree(tree:Tree[`T],
			       op:&(x:S, y:T):`S, unit:`S):S
{   let var accum:S := unit;
    tree.do(&(elm:T){ accum := eval(op, accum, elm) });
    accum }


-- Now, with this more general typing, we can write `sum_tree'
-- so that it actually typechecks
--
method reduce_sum_tree(tree@:Tree[`T]):T|int where T <= num
{   generalized_reduce_tree(tree, &(x:T|int,y:T) { x + y }, 0) }


-- testing
reduce_sum_tree(complexTree);


----------------------
-- adding Singleton
----------------------

template object Singleton[`T] isa Tree[T];
  var field element(s@:Singleton[`T]):T;

method new_singleton[`T](value:T):Tree[T]
{   object isa Singleton[T] { element := value } }

method insert(s@:Singleton[`T], value:T):Tree[T] where T <= ordered[T]
{   if (s.element = value, { ^s });
    if (s.element < value,
	{ new_node(s, Empty, value) },
	{ new_node(Empty, s, value) }) }

method member(s@:Singleton[`T], value:T):bool where T <= ordered[T]
{   s.element = value }

method do(s@:Singleton[`T], closure:&(elm:`T):void):void
{   eval(closure, s.element) }