In this post, I want to play with our programming languages and explore how can we implement a minimal type system. In order to do so I will build the system on top of a dynamic language so that the ideas are more easily exposed; for fun and practice, I chose Lua, but any other language can do really (provided it supports higher order functions). Don't worry if you cannot run Lua on your machine, the point is not to give you a useful executable, but code to read and understand the concept. While I assume a minimal level of programming knowledge, you might need to take a few moments to
understand how Lua's tables work. Other than that, the code is easy to read, the type system we develop is very basic and works pretty much the way you expect it to.
The problem: Dealing with conflicting representations
Instead of taking the dangerously naive approach of trying to define what a "type system" really means (you can always go check
Wikipedia), I will start by exposing a fairly common problem and build a solution from there. How do you deal with conflicting representations of the same data? Imagine you're given the task of merging two (or several) complex systems which offer similar functionality but represent data internally differently. It could be two forum websites representing topics and posts differently or ERP systems using different representations for items? In order to keep this as simple as possible, we will study a textbook math case:
Complex numbers.
Complex numbers come in 2 forms
Most of us learned in high school that there are two obvious ways of representing complex numbers:
- rectangular form
- polar form
If you're not familiar with complex numbers at all, I suggest you take a few moments to read about them (the Wikipedia article I linked to is a start, for more Google is your friend). In any case here's a quick reminder of what you need to know:
Complex numbers are expressed in terms of the imaginary number
i, such as i**2 == -1. (Physicist refer to this number as
j).
The first form of representing these numbers consists of define a
Real Part and an
Imaginary Part. This is the "rectangular form". There is another part to represent them which has a lot to do with the way we draw these numbers on a plane and it is by defining a Magnitude and an Angle. Conversion from one form to the other can be done using the following formulas.
Let z be a complex number:
- Magnitude(z) == sqrt(RealPart(z)**2 + ImaginaryPart(z)**2)
- Angle(z) == arctan(ImaginaryPart(z) / RealPart(z))
- RealPart(z) == Magnitude(z) * cos(Angle(z))
- ImagPart(z) == Magnitude(z) * sin(Angle(z))
Let's turn this into code
Here's how we're going to implement this. Each representation will define a constructor, a 4 selectors: realPart, imagPart, magnitude, angle. The functions are written according to the formulas defined in the above paragraph.
Rectangular form
function makeComplex (real, imag)
return {realpart=real, imagpart=imag}
end
function realPart (z)
return z.realpart
end
function imagPart (z)
return z.imagpart
end
function magnitude(z)
return math.sqrt((z.realpart ^ 2) + (z.imagpart ^ 2))
end
function angle(z)
-- # for simplicity's sake, we're ignoring the case where z.realpart == 0
-- # which is the case for pure imaginary numbers
return math.atan(z.imagpart / z.realpart)
end
Polar form
function makeComplex (mag, ang)
return {magnitude=mag, angle=ang}
end
function realPart (z)
return z.magnitude * math.cos(z.angle)
end
function imagPart (z)
return z.magnitude * math.sin(z.angle)
end
function magnitude (z)
return z.magnitude
end
function angle (z)
return z.angle
end
Introducting generic operations
While it could be argued that one representation is /better/ than the other, the reality of the matter might force us to have these 2 representations coexisting in the same system. A common reason would be the merging of two legacy systems into one, for example. How can we use each of the 4 selectors on an object without knowing which representation it's using beforehand?
The simplest solution consists of attaching a "label" (more appropriately called "type") to the object. This can be done in 3 steps:
- Modify the constructor to attach a type to the objects.
- Modify the selectors' names to indicate on which type of data they operate.
- Write generic operators that would call the appropriate selector according to the type.
This is exactly what we're going to do:
Generic operators
function realPart(z)
if z.type == "rectangular" then
return realPartRectangular(z)
end
else if z.type == "polar" then
return realPartPolar(z)
end
else
error ()
end
end
function imagPart(z)
if z.type == "rectangular" then
return imagPartRectangular(z)
end
else if z.type == "polar" then
return imagPartPolar(z)
end
else
error ()
end
end
function magnitude(z)
if z.type == "rectangular" then
return magnitudeRectangular(z)
end
else if z.type == "polar" then
return magnitudePolar(z)
end
else
error ()
end
end
function angle(z)
if z.type == "rectangular" then
return angleRectangular(z)
end
else if z.type == "polar" then
return anglePolar(z)
end
else
error ()
end
end
New Rectangular Form
function makeComplexRectangular (real, imag)
return {realpart=real, imagpart=imag, type="rectangular"}
end
function realPartRectangular (z)
return z.realpart
end
function imagPartRectangular (z)
return z.imagpart
end
function magnitudeRectangular (z)
return math.sqrt((z.realpart ^ 2) + (z.imagpart ^ 2))
end
function angleRectangular (z)
-- # for simplicity's sake, we're ignoring the case where z.realpart == 0
-- # which is the case for pure imaginary numbers
return math.atan(z.imagpart / z.realpart)
end
New Polar form
function makeComplexPolar (mag, ang)
return {magnitude=mag, angle=ang}
end
function realPartPolar (z)
return z.magnitude * math.cos(z.angle)
end
function imagPartPolar (z)
return z.magnitude * math.sin(z.angle)
end
function magnitudePolar (z)
return z.magnitude
end
function anglePolar (z)
return z.angle
end