Types in programming as mathematical sets
Types in programming can (and should) be considered as mathematical sets.
The idea, although obvious, has long disappeared from my head.
That’s why I decided to write this article: to remind myself and those who also forgot about it or didn’t even know about it.
First, let's remember the main definition:
Many is a collection of elements that share a common property and are considered as a whole. The elements of a set can be anything: numbers, objects, symbols, etc.
1. Set of integers: {1, 2, 3, 4}
2. Many vowels of the Russian alphabet: {A, E, I, O, U, Y, E, Yu, Ya}
In programming, we often think of data types as something different from mathematical sets. But looking at data types differently can expand our understanding of how they are structured and related to each other.
Let's look a little more closely.
I will give examples in C#, but they can be perceived as pseudo-code
Integer types as sets of numbers
Let's look at integer types.
We can think of them as sets of numbers with certain ranges:
Reminder
x ∈ ℤ should be understood as “x belongs to the set of integers”
sbyte
: {x ∈ ℤ | -128 ≤ x ≤ 127}short
(Int16): {x ∈ ℤ | -32.768 ≤ x ≤ 32.767}int
(Int32): {x ∈ ℤ | -2,147,483,648 ≤ x ≤ 2,147,483,647}long
(Int64): {x ∈ ℤ | -9,223,372,036,854,775,808 ≤ x ≤ 9,223,372,036,854,775,807}
From this point of view, each integer type is a subset of the next larger type.
Here's the type short
is a subset of type int
which in turn is a subset of the type long
.
Subset relationships and type conversion
Understanding types as sets helps you better understand why some type casts are safe and others are not. For example:
// Безопасное приведение от short к int: каждый элемент множества "short"
// также является допустимым элементом для множества "int".
short s = 1000;
int i = s;
However, the opposite is not always true:
// Небезопасное приведение: требует явного приведения типов и может привести
// к потере данных, поскольку не каждый элемент множества "int"
// является элементом множества "short".
int i = 40000;
short s = (short)i;
bool as a set
Type bool
in C# can be thought of as a set with exactly two elements:
Enum types as finite sets
Enumerations in C# are excellent examples of finite sets. For example:
enum DaysOfWeek
{
Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday
}
Transfer DaysOfWeek
can be considered as a set: {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday}.
Complex types as sets
Let's see how we can think of more complex types as sets.
Transport example
We have a hierarchy of transport types:
class Vehicle
{
public string Make { get; set; }
public string Model { get; set; }
}
class Car : Vehicle
{
public int NumberOfDoors { get; set; }
}
class AudiCar : Car
{
public string AudiSpecificFeature { get; set; }
}
Let's look at these types as sets:
Vehicle
: Set of all possible vehicles with make and model.Car
: SubsetVehicle
including all vehicles with doors.AudiCar
: SubsetCar
including all vehicles with Audi-specific features.
Reminder
A ⊂ B should be understood as “the set A is a subset of B.”
In terms of sets it would look like this:
Vehicle
= {x | x has make and model}Car
= {x ∈ Vehicle | x has doors}AudiCar
= {x ∈ Car | x has Audi-specific features}
It can be concluded that AudiCar
⊂ Car
⊂ Vehicle
.
Example with electronic devices
Consider the hierarchy of electronic devices:
class ElectronicDevice
{
public string PowerOn() {}
}
class Smartphone : ElectronicDevice
{
public string MakeCall() {}
public string SendText() {}
}
class DualCameraSmartphone : Smartphone
{
public string TakePhoto() { }
}
We can also think of these types as sets:
ElectronicDevice
: The set of all possible devices that can be turned on.Smartphone
: SubsetElectronicDevice
which includes all devices capable of making calls and sending messages.DualCameraSmartphone
: SubsetSmartphone
which includes all smartphones with the ability to take high-quality photos using a dual camera.
In terms of sets:
ElectronicDevice
= {x | x may be included}Smartphone
= {x ∈ElectronicDevice
| x can make calls and send messages}DualCameraSmartphone
= {x ∈Smartphone
| x can take photos}
Respectively, DualCameraSmartphone
⊂ Smartphone
⊂ ElectronicDevice
.
Example with interfaces
Interfaces can also be viewed in terms of sets.
For example:
interface IComparable
{
int CompareTo(object obj);
}
interface IEquatable<T>
{
bool Equals(T other);
}
We can imagine the interface IComparable
as the set of all objects that have a method CompareTo(object obj)
and the interface IEquatable<T>
– as the set of all objects that have a method Equals(T other)
.
A class that implements multiple interfaces can be thought of as belonging to the intersection of these sets:
class CompareableInt : IComparable, IEquatable<int>
{
public int Value { get; set; }
public int CompareTo(object obj) {}
public bool Equals(int other) {}
}
Reminder
A ∩ B should be understood as “the intersection of the sets A and B.”
In terms of sets, CompareableInt
belongs to IComparable
∩ IEquatable<int>
.
Barbara Liskov's Substitution Principle
Barbara Liskov's substitution principle (the L from SOLID) is a fundamental principle of object-oriented programming that is closely related to our idea of types as sets.
The principle states that objects in a program should be replaced by instances of their subtypes without affecting the correctness of the program.
In set terms, this means that each element of set A must behave as elements of the wider set B are expected to behave if A ⊂ B.
Consider a famous example of a violation of this principle:
class Rectangle
{
public virtual int Width { get; set; }
public virtual int Height { get; set; }
public int Area() => Width * Height; }
}
class Square : Rectangle
{
public override int Width
{ set { base.Width = base.Height = value; } }
public override int Height
{ set { base.Width = base.Height = value; } }
}
Highlight:
This is where our Debug.Assert() will behave differently depending on what type of object was actually passed to the method – Rectangle
or Square
.
void IncreaseWidth(Rectangle rectangle)
{
int originalHeight = rectangle.Height;
rectangle.Width += 1;
Debug.Assert(rectangle.Height == originalHeight); // Для квадрата это будет неверно.
}
To comply with the LSP, we need to ensure that all operations that are true for the elements of the set Rectangle
are also true for elements of its subset Square
.
This code example does not respect this guarantee, so the principle is violated.
What did you want to say?
I wanted to say that if you, like me, are bogged down in shifting DTOs, setting up infrastructure, tracking in Jira/Asana/Whatever, endless calls/correspondences and have forgotten that programming is, in fact, Beautiful, – try to look at everyday things (types, inheritance, interfaces, etc.) from a different, unusual point of view.
Afterword
In fact, there is a whole area that also covers what we talked about today.
It's called – “Type Theory“.
So if you're even remotely interested in what I've shared, I encourage you to continue exploring and dive a little deeper.
You can start, for example, from here https://habr.com/ru/articles/758542/