Demystifying Type (and some Un-Paradoxing)

This piece examines the concept of "type" in programming languages and suggests a simplified approach to understanding its role. The author initially struggled with the true nature and purpose of type, concluding that it adds little value compared to other foundational elements.

The history of type theory stems from attempts to address issues like Russell's Paradox and the limitations of certain academic systems. The Curry-Howard correspondence, rather than being a mysterious link between unrelated ideas, reflects the integration of relational logic within programming language type systems.

The author argues that type is essentially synonymous with relational membership, a concept that can be understood through set membership or truth values on predicate functions. While type may appear indispensable due to its historical context and associated baggage, the author posits that type can be reduced to a more straightforward representation grounded in relational logic.

A critical distinction arises between what can be reliably computed at compile time (type) and what can be computed at runtime (value). The author suggests that this distinction is largely pragmatic and unnecessary, advocating for a unified representation that integrates compilation and execution more seamlessly.

The concept of type as something known when a program is written, as opposed to what can be reliably computed during compilation, is crucial. This implies a subset of relational truths that can be inferred from code at the time of writing, providing an implicit context for the program. By using type to disambiguate language at the syntactic level, programmers can clarify the intended meaning of terms like "length," enhancing code readability and reducing ambiguity.

Ultimately, the author concludes that type serves primarily as a tool for disambiguating language at the syntactic level, ensuring that the intended meaning of terms is clear to both the programmer and the compiler. This function, though seemingly special, is fundamentally an application of relational logic, reinforcing the argument that type should be viewed as an ordinary relational construct rather than a unique or indispensable concept in programming language theory.