Python 1.6 The balanced language

[Neel Krishnaswami]

Suchandra Thapa <ssthapa at harper.uchicago.edu> wrote:
> 
> Actually I think clean is a pure functional oo language.  It's just
> that being oo seems to imply that you have some state to your
> objects.  Not sure anyone would get around this paradox.

No, the distinguishing features of OO are that a) subtyping exists,
and b) the types of objects are used to do dynamic dispatch. Mutable
state is not necessary -- in both Dylan and Ocaml, it's common to
write code in an "object-functional" style, with lots of objects but
no mutation.

In a language like ML, you can write a function to find the
length of a list like so:

fun len lst = case lst of
                []      => 0
              | x :: xs => 1 + len xs;

val len = fn : 'a list -> int


The type 'a list -> int means that the len function can accept a list
of any type of object -- it can find the length of a list of ints, or
strings or any other type. IOW, the 'a is a *type variable*, which
parameterizes the type declaration.

Now, if you look at the code for len, you'll notice that there is no
code that depends on the type of the elements of the list. It doesn't
matter what the type of the elements are, so you can let them be
anything. (This is called the type erasure property.) The flip side of
this is that you can't write polymorphic code that varies with the
type of the elements.

In an OO language, you might the write code for a list class like so:

class EmptyList:
    def __len__(self):
	return 0

class List:
    def __init__(self, head, tail):
	self.head = head 
        self.tail = tail
    def __len__(self):
	return 1 + len(tail)

lst = List(3, List(1, List(2, EmptyList())))

So if we call len on lst, we get

>>> len(lst)
2

So far, this is the same as in ML. Now, suppose we want to write
a linked list class that maintains its size as a field, so that
finding the length is fast. We could define in Python:

class SizedList(List):
    def __init__(self, head, tail):
	self.head = head
	self.tail = tail
	self.size = 1 + len(self.tail)
    def __len__(self):
	return self.size

lst2 = SizedList('a', SizedList('b', SizedList('c', EmptyList())))

Now, if we call 

>>> len(lst1) # lst1 is of type List
2

>>> len(lst2) # lst2 is of type SizedList
3

The equivalent  definition in ML would be something like

datatype 'a Sizedlist = Empty | Cons(int, 'a, 'a Sizedlist);

but it is impossible[*] to extend the len function to give you the
length of a Sizedlist in ML because a different method must be called,
depending on the type of the argument to len, and the overloading must
be resolved -at runtime- by the precise type of the argument. You
would need to define a new function (say sizedlist_len) in order to
get the size of a sized list.

But if subtyping and overloading *did* exist in ML, then it would be
perfectly feasible to write this deifnition -- and note that there is
no mutation anywhere in it. And in fact it *is* possible in OCaml.


Neel

[*] I'm aware of functors, but they are a subtlety that doesn't
matter for the main thrust of this post.