Essence and Foundation of the Practical Type System (PTS)

Introduction

In this article we'll take a closer look at PTS — its goals and non-goals, its history, what to avoid, and its core types.

Context

This section provides essential contextual information necessary for grasping the essence of PTS.

History

The Practical Type System (PTS) originated in the Practical Programming Language (PPL). I created PPL to try out how a programming language could help writing more reliable and maintainable code in less time. PPL is a compiled, high-level, object-oriented and functional programming language designed for application programming.

I wrote the first versions of PPL in Java. After some iterations, I bootstrapped the PPL compiler in PPL, so that PPL was eventually written in PPL.

Notably, PPL was used to write:

• The first versions of the Practical Data and Markup Language (PDML).

• The first versions of the Practical Markup Language (PML) (which I've been using since 2019 to write all my articles, including the original version of this one).

  Note: PDML and PML were eventually rewritten in Java, to render them more suitable for open-source projects.

• Some minor parts of a commercial ERP application.

Hence PPL wasn't just a toy language — it was tested and usable to a certain extent, albeit still far from being production-ready (incomplete documentation, a rudimentary standard library, no IDE support, etc.). Because of its immaturity, PPL was never open-sourced. It is now hibernating for a few years — but that might change in the future.

The point is, PPL helped me to learn a lot about language design and type systems, and now I want to share and discuss what I've learned. Constructive feedback is most welcome, and the resulting knowledge will hopefully be useful to design future programming languages.

In a nutshell: PTS is a set of ideas which I fleshed out in PPL, and I'm now publishing them since they seem to be useful.

We need to differentiate between the PTS paradigm and the PTS syntax. Both emerged from PPL, and they'll be introduced in the next sections.

if (condition) {
    i = 1;
} else {
    i = 2;
}

if condition
    i = 1
else
    i = 2
.

if condition
i = 1
else
i = 2
.

No-Go 'Features'

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.

— Antoine de Saint-Exupéry

Excellent advice!

Before adding features, we should first think hard about what not to add.

Whole classes of bugs and unnecessary complexity can easily be eliminated by simply not supporting several features, even if they are popular and might make sense in other contexts.

Below is a list of features that raise the risk of software bugs, add unnecessary complexity, and often jeopardize productivity and deprive us of the joy of coding. Some of these features are more related to the programming language, but since they go hand in hand with the type system they are worth mentioning here.

The following features have no place in PTS:

• Undefined state

  Example: No protection against using an uninitialized variable. The variable might contain any random garbage that happens to be in memory when its value is accessed.

  For more information and examples, read the Wikipedia article Undefined value, which warns us:

  There is no limit on what might happen. At best, an easily detectable crash; at worst, a subtle error in a seemingly unrelated computation.

• Undefined behavior

  Undefined behavior means that the behavior of the application can become totally unpredictable because of some language use case which is neither specified by the programming language, nor by its implementations (compilers/interpreters).

  For example, in some languages integer division by zero results in undefined behavior.

  Wikipedia states:

  In the C community, undefined behavior may be humorously referred to as 'nasal demons', after a comp.std.c post that explained undefined behavior as allowing the compiler to do anything it chooses, even 'to make demons fly out of your nose'.

  For practical illustrations showing what this really means I recommend delving into the following articles:

  • What Every C Programmer Should Know About Undefined Behavior #2/3, written by Chris Lattner (co-founder of LLVM and Clang compiler)

  • A Guide to Undefined Behavior in C and C++, Part 1, written by John Regehr, Professor of Computer Science, University of Utah

  Undefined state and undefined behavior are scary — really scary.

• Unspecified behavior

  Unspecified behavior is closely related to undefined behavior, albeit different from it. In this case the behavior is unspecified by the programming language too, but the compiler/interpreter chooses what to do, and this might be specified in the documentation of the tool.

  For example, compiler A does X in a given situation, while compiler B does Y.

  This opens the door to different run-time behaviors for the same source code, depending on the compiler/interpreter used in the given context, as well as the host OS and underlying hardware architecture. For example, an application might run correctly if compiled with one compiler, but fails to run properly if compiled with another compiler.

• Silently ignored errors

  Example: silently ignored arithmetic overflow errors, such as 2_000_000_000 + 2_000_000_000 (addition of two signed 32 bits integers) being incorrectly evaluated to -294_967_296 in C#, Java, and other programming languages.

• Unsafe null-handling

  No protection against the infamous null pointer dereference (nowadays synonym with the "billion dollar mistake").

• Mutable data by default

  Data should be immutable by default, and mutable only when explicitly specified. For a summary of the rationale see section Make all data structures immutable, unless there is a good reason to make them mutable! in my article Fundamental Pragmatics for Successful Programmers.

• Shared mutable data

  Shared mutable data can cause weird behavior and bugs that are extremely difficult to find and fix. This is well explained in Henrik Eichenhardt's article Why shared mutable state is the root of all evil.

• Implicit type conversion/coercion

  Implicit type conversions/coercions are error-prone whenever there is a risk of silently ignored loss of information, wrong data, or other nasty bugs.

  There are different variations of this "no-go feature".

  Probably the most prominent case is the implicit conversion/coercion between numeric types of different natures and/or different ranges, such as coercing a floating point number into an integer number, or a 32-bit integer into a 16-bit integer.

  Another example would be a string that is implicitly coerced into a number, or zero if the string doesn't represent a valid number.

• Dynamic typing

  A type system designed for mid- to large-size projects should support static typing, because it allows catching more bugs at compile-time, and offers other advantages.

  The following are some dynamically typed programming languages: JavaScript, Lisp, Lua, PHP, Python, and Ruby.

  Static typing is used in C, C++, C#, Go, Haskell, Java, Kotlin, Rust, and other languages.

  Note

  Static typing does not prevent a type system from providing also mechanisms that mimic dynamic typing, if needed.

• Buffer overflowing
• Pointer arithmetics

  For a quick overview, see What are the dangers of pointers in C?

• Manual memory management
• Value types and reference types co-existing for the same data

  There are important differences between value types and reference types, and ignoring them can lead to subtle bugs.

  For example, when an object is changed in a function, this change will be reflected in the calling context only in case of a reference type. If the data is passed by value, the change will not be propagated to the calling context.

  In C# and Java, integers can be values or references.

  C# example: int i1 = 1; object i2 = 1;

  Java example: int i1 = 1; Integer i2 = 1;

  For more information, read Value Type and Reference Type (related to C#, but mostly applicable to other languages too).

• Excessive functionality in the root type of the type hierarchy

  Examples: Equality, comparison, hashing, copying functions/methods, and further functionality present in the root type (well explained for C# and Java in Jon Skeet's article Redesigning System.Object/java.lang.Object).

• Other

  Unneeded complexity and error-proneness can be caused by various other type system or language constructs. For example, the following horrors are all found in JavaScript:

  • truthy, falsy, and nullish values

  • shadowed and hoisted variables

  • complex rules for == and === operators

  • exotic objects.

To keep this section short, we won't elaborate on the perils of the above features. Practice shows that they have all caused numerous software application failures — some of them resulting in disasters. Just remember:

• The Ariane 5 rocket exploded due to coercing a 64-bit number into a 16-bit space.

• Microsoft states: "70 percent of all security bugs are memory safety issues".

More examples can easily be found in JavaScript . The good part of the type system in JavaScript is that it teaches us how not to design a practical type system. People are now well aware of the many idiosyncrasies lurking in this language and hitting unexpectedly in all kinds of applications. Some of them are just funny, others might leave you speechless. Many examples are shown in What the f*ck JavaScript? (my favorite: null is falsy, but not false). There is even a song called Bug in the JavaScript, written by Dylan Beattie, an excellent speaker and the creator of the esoteric Rockstar programming language.

Core Types

Every type system needs to provide some core, native types. Core types are the building blocks for more complex types; they provide an essential foundation for creating customized, project-specific types.

This section provides a quick overview of PTS core types. Type operations (e.g. how to get a sub-string or how to filter a collection) and implementation details are out of scope.

'a'
'1'
'!'
'\n'        // <line feed>
'\''        // '
'\u2714'    // ✔
'\U001F600' // 😀

"foo"                        // foo

"line 1\nline 2"             // line 1
                             // line 2

"\"Hello\" \\ \U0001F60A"    // "Hello" \ 😊

write_line ( """File: C:\foo\bar.txt
SQL command: select "first_name", "last_name" from "employees"
line \3\
""" )

const name = "Peter Deutsch"
const quote = "If you get the data structures and their invariants right, most of the code will just write itself."
write_line ( """{{name.to_upper_case}} said:
    "{{quote}}"""" )

File: C:\foo\bar.txt
SQL command: select "first_name", "last_name" from "employees"
line \3\

PETER DEUTSCH said:
    "If you get the data structures and their invariants right, most of the code will just write itself."

123
0
-123

// largest prime number found with a mechanical calculator by Aimé Ferrier:
20988936657440586486151264256610222593863921

123.45
0.0
-1.007

// pi with 50 decimals:
3.14159265358979323846264338327950288419716939937510

// using an exponent:
10E10
-123.45E-12

[list<string> "good" "better" "best"]

[mutable_list<any> "abc" 'd' 'd' 1+1]

[list<boolean> true false true]

[list true false true]

[set "Tim" "Tom" "Tam"]

[map<string,any>
    "digit" : 1
    "letter": 'a'
] 

What's Next?

By now you should have a good overview of what PTS is, isn't, and aims to achieve.

We want a type system that simplifies defining reliable types, and we want bugs to be detected as early as possible in the development cycle — preferably at compile-/edit-time, or else as soon as possible at run-time.

In the next articles we'll progressively discover the features required to achieve the goal of writing more reliable and maintainable code in less time. We'll talk about record and union types, null-safety, error handling, constrained scalars, eradication of the empty string, and more.

Acknowledgment

Many thanks to Tristano Ajmone for his useful feedback to improve this article.