How to implement polymorphism in a turing complete environment?

Question

I'm currently programming in an unnamed turing complete language which has support for pointers, primitive data types, structures, closures, and garbage collection, among other things.

I'm trying to use this language to implement an object oriented design pattern. So far, I have implemented the following algorithm:

make object (base class) subroutine:
    create data structure
    associate structure as an 'Object'
    return data structure

make shape (extends from object) subroutine:
    call make object
    associate data structure as a 'Shape'
    add 'getPerimeter' & 'getArea' subroutines to data structure
    return data structure

make circle (extends from shape) subroutine:
    call make shape
    associate data structure as a 'Circle'
    add 'getCircumference' as subroutine to data structure
    re-define 'getPerimeter' & 'getArea' subroutines to data structure
    return data structure


output shape area subroutine
    assert shape is a Shape
    print, call shape.getArea

This so far has worked great. Sub-classes correctly inherent the fields of their super-classes.

However, I am no longer able to take the extended classes and 'treat them as their super-class forms' anymore. For example, I can no longer treat a Circle specifically as a Shape, because when it was made into a Circle it was augmented with Circle member functions like getCircumference. I cannot typecast it to be strictly a Shape or an Object, as its now been defined with sub-class functionality.

In Java terms, I can do this:

Fruit a = new Fruit(); // eat()
Apple b = new Apple(); // removeSeeds()
b.removeSeeds();
b.eat();

But I cannot do this:

Fruit a = new Apple();
a.removeSeeds(); // undefined

How can polymorphism be implemented in this sense?

Answer 1

So, first, a question. Are you using dynamic or static dispatch? i.e. if Circle and Shape provide implementations of the same method, and you cast a Circle to a Shape, which one gets called?

If you're using static dispatch, one way to do it is, instead of making a Circle by taking a shape and adding fields, you make Circle its own type, with a special Super field that is a Circle. Any time Circle methods reference Shape fields/methods, you desugar into Super.field. Casting a Circle to a Shape then just involves looking up the shape that's stored.

If you're using Dynamic dispatch, but are using static typing, instead you can use "duck typing" internally, that is, the "type" of something is just which methods/fields are accessible. So in this system, you could construct a Circle as you've described, and when you cast it to a Shape, there's no runtime effect. Your typechecker just ensures that no Circle methods are called on a Shape, even if its runtime representation is a Circle.

Finally, if you're using dynamic dispatch and dynamic typing, then you probably don't need to ever cast a Circle to a Shape (since there's no typechecker to stop you from calling Shape methods on a Circle). The trick here is that your assert shape is a Shape should return True for anything that is a subclass of Shape. So as long as that check succeeds for a Circle, you're fine. This is why such a check is called instanceof in Python: you're not accessing the type of the value, you're checking if it is a subclass of the desired type.

I'm not sure how Turing Completeness factors into anything: Java, Python, and other subclassing languages are all Turing Complete. Java's type system is even Turing Complete!

One final pedantic note: what you call "polymorphism" is better described as "subclass polymorphism". There are, in PL theory, many other kinds of polymorphism, such as parametric (i.e. generics), and ad-hoc (i.e. overloading).