* Polymorphism - Introduction
An operation is *polymorphic* if it works correctly for arguments of
different types.

Two different kinds of polymorphism:
    Universal - the operation can handle different types using the
    same code.
    Ad hoc    - Different types may be handled using different code.

Examples of polymorphic operations:
    + operation in C can take integer arguments or float arguments.
    
All reasonable data abstractions can provide polymorphism : if the
operation works correctly with one particular interface, then it can
work with any other data abstraction with the same interface.

* Bundled and Unbundled Data Abstractions - Introduction

We will discuss two particular styles of data abstraction, and how
polymorphism works in these:
	1. Unbundled implementation: an ADT where the Data and the
	functions on the ADT are stored separately. 

	2. Bundled data abstractions, as in objects, where both the
	ADT and the operations are members of the data abstraction.
	A bundled data type provides two kinds of entities:
		1. Value
		2. Operation.

** The problem with unbundled data

Suppose we implement a stack in the following unbundled form.

--------------------------
fun {NewStack} nil end
fun {Push X S} X|S end
fun {Pop S ?X} 
    case S 
    of H|T then 
	X=H
        T
    end
end
fun {IsEmpty S} S==nil end
--------------------------

A programmer who realizes that the stack is implemented as a list, can
do S.1.2.1 to get the second element on the stack, which violates the
data abstraction. This is the basic problem: how do we ensure that
programmers do not manipulate the stack directly except through the
functions that we provide?

** Secure Data Types 
We can introduce protection boundaries with the help of *Secure data
types*. We introduce the notion of a *name*. A name is a literal that
is unique in the system. There are exactly two operations supported by
names: 
	1. {NewName} : create a new name. This is a stateful function,
		since repeated calls must return different values.
	2. N1==N2

A name cannot be printed.

** Secure Unbundled ADT

The basic idea to secure an unbundled data type is to wrap the data
inside secure functions. These functions will allow access to the
internal data only if you give it a correct key.

--------------------------
proc {NewWrapper ?Wrap ?Unwrap}
   Key = {NewName}
in
   fun {Wrap X}
      fun {$ K} if K==Key then X end end
   end
   fun {Unwrap WrappedObject}
      {WrappedObject Key}
   end
end
% {Unwrap {Wrap 2}} = {{Wrap 2} Key} = 2
--------------------------

Using this, we can implement a secure stack as follows.

--------------------------
declare NewStack Push Pop IsEmpty 
local Wrap Unwrap in
   {NewWrapper Wrap Unwrap}
   fun {NewStack} {Wrap nil} end
   fun {Push X S} {Wrap X|{Unwrap S}} end
   fun {Pop S ?X}
      case {Unwrap S}
      of H|T then
	 X=H
	 {Wrap T}
      end
   end
   fun {IsEmpty S} {Unwrap S}==nil end
end
--------------------------

We can now implement a stateful version, in an encapsulated manner.

--------------------------
declare NewStack Push Pop IsEmpty 
local Wrap Unwrap in
   {NewWrapper Wrap Unwrap}
   fun {NewStack} {Wrap {NewCell nil}} end
   fun {Push X S} 
      C={Unwrap S} C:=X|@C {Wrap C}
   end
   fun {Pop S ?X}
      C={Unwrap S}
      case @C
      of H|T then
	 X=H C:=S1 {Wrap C}
      end
   end
   fun {IsEmpty S} @{Unwrap S}==nil end
end
--------------------------


Using this, we can now discuss polymorphism.

* Polymorphism in Bundled and Unbundled abstractions

Polymorphism in the object style is easier. In the unbundled style, it
requires first-class modules.

** Collection Type

Unbundled:				Bundled:
--------------------------		------------------- 
declare Collection			fun {NewCollection}
local Wrap Unwrap			    S={NewStack}
    {NewWrapper Wrap Unwrap}		    fun {Put X}
    fun {NewCollection}			    	{S.put X}
    	{Wrap {Stack.new}}		    end
    end
    fun {Put C X}			    fun {Get}
    	S = {Unwrap C}			    	{S.pop}
    in					    end
	{Stack.push X S}
    end		    
    fun {Get C ?X}			    fun {IsEmpty}
        S={Unwrap C}			    	{S.isEmpty}
    in					    end
        {Stack.pop S X}         	in 
    end		     			   collection(put:Put
    fun {IsEmpty C}				      get:Get
    	{Stack.isEmpty {Unwrap C}}		      isEmpty:IsEmpty)
    end		       	       	  	end
in                                      ------------------------------
    Collection =
     collection(new:NewCollection
                put:Put
                get:Get
                isEmpty:IsEmpty)
end
--------------------------

Example Use:

--------------------------             -------------------------------
C={Collection.new}
{Collection.put C 1}
{Collection.put C 2}
X={Collection.get C}
{Browse X}
-------------------------