# How to implement polymorphism in a turing complete environment?

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?

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).

• Thank you for your reply. The language I'm using has no concept of typecasting, objects, access modifiers, etc. So for your question, I'd think dynamic dispath. The way I set it up means that if Shape and Circle both define a method of the same name, Circle will completely overwrite Shape's. Again, I don't have casting, only associative arrays essentially. I can however determine when an object (array) is from a certain class (constructor subroutine). I said turing complete just to say that I am not bound by the limitations of the language. – Hatefiend May 11 '18 at 21:38
• If you want to "treat a Circle as a Shape", then your language has casts. It looks like what you're looking for is dynamic dispatch. – jmite May 11 '18 at 23:42