Recent content on Programming Linguistics
It is time for Cone to get a proper module system. This design space is complex and rife with historical missteps. In order to distill the topography of the landscape and clarify the key requirements, I felt it necessary to begin the journey with cross-language research and contemplation. I wound up pursuing three rabbit-chasing adventures in module wonderland: What do programmers want from…
Cone’s module system has been on my mind of late. The best design for modules is neither easy or obvious, as evidenced by how much modules vary from one language to the next. To guide my approach for Cone, I went back to basics: What is the role (and benefit) that modularity plays in programming (languages)? What role do modules play within this larger picture. This post synthesizes my…
I have long enjoyed the convenience of the “dot” dispatch syntax: instance.log("Ethereal cognistrands do not support quantum entanglement") The magic of Universal Function Call Syntax makes this sugar for a function call: log(instance, "Ethereal cognistrands do not support quantum entanglement") The broad popularity of method dispatch is driven by these benefits: Ad hoc polymorphism.…
Note: This is a heavily revised version of an earlier post The Cone compiler performs a data flow analysis pass after name resolution and type checking. Given that this sort of analysis is rarely covered by compiler literature, I thought it might be useful to jot down some thoughts about its purpose and intriguing mechanics. Trigger Warning: This blog post is highly technical and brief. It reads…
Let’s continue our journey of discovery through the wild jungle of programming paradigms by clearing away more obstructive vines. This post tackles the taxonomic distinction that many attempt to make between declarative and imperative programming. What becomes clear, after some study, is that “declarative” and “imperative” do not have singularly simple and clear…
Have our conversations about programming paradigms grown stale? It seems so. Paradigms like object-oriented programming and functional programming, the two most talked-about, are decades-old. Nearly always, conversations about them devolve into reciting the same desiccated stereotypes. Is this because the notion of a programming paradigm has outlived its usefulness? Dr. Harper appears to think so.…
The previous Lifecycle of a Reference post illuminates the working relationship between references and regions. It explains how a reference’s region annotations are programmer-definable struct-like types, which can specify an allocated object’s region state using fields, and region-based operations on an object (e.g., allocate and free) using methods. This, however, leaves out an…
Over two and half years ago, I described something I called Gradual Memory Management. Inspired by Rust and Pony, my paper proposed that it is feasible and desirable for a systems programming language to allow programs to exploit multiple memory management and permission strategies. Without putting memory and data race safety at risk, doing so would facilitate significant improvements to…
It is notable how often paradoxes arose in the historical journey that led to the Rise of Type Theory. Resolving Russell’s paradox led to his theory of types. Gödel’s Incompleteness theorems rested its proof around a variation of the Liar Paradox. Church and Turing recapitulated this result using their distinctive formalisms. Intuitionistic type theory was deliberately designed to…
After three dreary posts on syntax, let’s change the pace and pursue an entirely different, deeper and more fun topic! In our community’s #theory channel on Discord, someone asked: “Is there a basis for some of the mathematics related to type theory and its relationship to its usage in programming languages?” This triggered a spirited dialogue about the historical…
I seem to be on a roll with syntactic concerns lately, which is not where I typically spend most of my time. Today’s issue is, at least, more unusual than stylistic preferences regarding semicolons and significant indentation. This post explores the issues that arise when teaching the compiler to be agnostic as to whether it is parsing a value expression or a type expression. A value…
The last post focused narrowly on evaluating various techniques for semi-colon inference, thereby enabling a program to successfully compile even when the programmer omits statement-ending semicolons. This post broadens this theme, looding at how the compiler can take advantage of significant indentation when handling block inference and multi-line string literals. I wander into this topic knowing…
Many programming languages require that statements end with a semicolon. Some languages, such as Javascript, Go, Kotlin, Swift, Scala and Lua, make this requirement optional. Although a semicolon may be specified, it is not required to terminate a statement. This post explores the underlying rules various languages use to make semicolon inference possible. It also articulates the arguments for and…
The last two posts introduced the fundamental elements underlying Cone’s type system. They also distinguished between nominal vs. structural type equivalence. However, they were largely silent about subtyping relationships between types. Given how important subtyping is to Cone’s type versatility, I thought it might also be valuable to offer a detailed treatment of these mechanisms. My…
The prior post described the semantics underlying Cone’s fundamental types, for all types except the all-important pointer and reference types. The presence of versatile pointers/references as an explicit and distinctly-separate kind of type is a distinguishing characteristic of systems programming languages. I choose to cover them here as a separate post, since the safety guarantees of…
When I began work on the Cone programming language, I believed I had a confident handle on which primitive types this modern, safe systems language required: various sizes of atomic number types, fixed-size arrays, programmer-defined structs, raw pointers, safe references, discriminated (and raw) unions, generics, and limited support for void and tuples. My confidence was misplaced. Once or twice…
When the clock ticks over to a new decade, it is customary to look back, to reflect on how much we have accomplished, and then look forward, to sort out where we want to go. Ten years is long enough that substantive progress should be visible in the glacially-slow evolutionary pace of programming languages. One can see this by noticing how many now-influential languages had no notable marketplace…
Type theory has many kinds of typing mechanisms: product, sum, top, bottom, recursive, universal, existential, subtypes, linear, refinement, dependent, and so on. I have run across something different from all those, which I am calling “infectious typing”. If anyone knows a formal name and/or treatment for this mechanism, I would love to hear about it. Type composition allows us to…
In 2001, Trevor Jim (AT&T Research) and Greg Morrisett (Cornell) launched a joint project to develop a safe dialect of the C programming language, an outgrowth of earlier work on Typed Assembly Language. After five years of hard work and some published papers, the team (including Dan Grossman, Michael Hicks, Nik Swamy, and others) released Cyclone 1.0. And then the developers moved on to other…
The prior post, When Sum Types Inherit, shows that we can (and should) use the magic of inheritance to enrich sum types to offer as powerful a capability as traditional classes. Graph-based, variant node data structures benefit from variant nodes being able to support common fields, methods, and virtual dispatch. That result, however, raises a new question: do we really need two separate language…
Inheritance makes it easier than any other mechanism (e.g. generics, macros, composition/delegation) to define a type that reuses the state and some methods of other types. After reading my inheritance posts, I hope you are convinced that simplifying inheritance to a namespace-based mechanism ensures we obtain this convenient reuse capability, while avoiding most of the complexity and coupling…
After removing the interface, inversion of control, and protected access capabilities from traditional inheritance, what do we have left (besides composition)? This is what we have: placing a few extra tokens on a derived class causes all named fields and methods of one or more base classes to be absorbed as if explicitly incorporated. Further, certain inherited methods can be customized…
Anti-inheritance advocates are likely to enthusiastically support this post. It promotes the most useful feature of traditional inheritance (Interfaces), turning it into a more valuable abstraction that is largely independent of inheritance. It discards two other traditional features of inheritance, Inversion of Control and Protected Access, as both unnecessary and dangerous. Let’s examine…
I need to decide what sort of inheritance capability Cone will offer. None! I can hear some of you insist. “Inheritance has recently fallen out of favor as a programming design solution,” claims the Rust language book. “Favor object composition over class inheritance,” recommends the Design Patterns book in 1994. “Inheritance is Evil.” insists Nicolò Pignatelli.…
The execution of a program unfolds over some interval of time. The lifetime of every temporary resource (e.g., variable or object) is the time span between that resource’s “creation” and “destruction”. This lifetime is wholly contained within the typically-longer lifetime of the program. The goal of this post is to explore how versatile lifetime analysis has…
Note: You can read Russian translation here. I have always wanted the Cone compiler to be fast. Faster build times make it easier and more pleasant for the programmer to iterate and experiment quickly. Compilers built for speed, such as Turbo Pascal, D and Go, win praise and loyalty. Languages that struggle more with this, like C++ or Rust, get regular complaints and requests to speed up build…
The decades-long golden age of Moore’s Law is fading. Slow, bloated software will find it increasingly difficult to hide behind the skirt of ever-faster computer hardware. Given that businesses and users will not yield on their demand for speedy software, developers will need to get a lot better at architecting for performance. In his excellent article on Performance Culture, Joe Duffy…
To complete our three-part series on permissions, which began with Race-Safe Strategies, let’s talk about the transitional nature of reference permissions. When are permissions transitional? When we can safely create a copy of a reference which has a different permission than the reference it copied from. There are several ways in which this can happen, which this diagram summarizes (and the…
In my last post, Race-safe Strategies, one footnote stated “safety issues which look suspiciously similar to race conditions can crop up when a language supports the creation of “interior references” to shared, mutable values of certain types”. Let’s explore that now. I will begin by recapitulating Manish Goregaokar’s excellent post “The Problem With Single-Threaded…
I recently made the observation that many people seem unaware of the full collection of constraint mechanisms available for protecting race safety. Someone sensibly asked for a link to an article that provides a modern, comprehensive review. It turns out that the pickings are very slim; the best I could find is this Wikipedia article on thread safety. It’s accurate, but incomplete. To close…
Is it possible to improve on Rust’s single-owner strategy to support more complex data structures? Before digging into this challenge, let’s summarize the story so far… The Promise and Limitations of Single-Owner Rust’s single-owner memory management is a form of automatic memory management; a garbage collection strategy that is distinct from tracing and…
Most programming languages support only copy semantics. A value passed to a function or stored in a variable is a copy of the original value. We know it is a copy, because any change we make to the copy has no impact on the original value. A few languages, like C++ and Rust, also support move semantics. Unlike a copy, a transfer moves the original value to its new home; that value is no longer…
Note: The latter part of this post is outdated in terms of the mechanisms that the Cone compiler uses to de-alias ref-counted references. See this post for an updated description. In the world of automatic memory management, reference counting is considered to be one of the easiest to implement. The rules seem simple: When a reference is created to an allocated memory area, set its counter to 1…
Note: This is an outdated post, replaced by this post The Cone compiler performs a data flow analysis pass after name resolution and type checking. Given that this sort of analysis is rarely covered by compiler literature, I thought it might be useful to jot down some thoughts about its purpose and intriguing mechanics. Goals Like Rust (and unlike C), Cone applies constraints to references that…
As mentioned in the previous post, all typed nodes use the TypedNodeHdr common header. It only contains a pointer to the node’s type. This type field applies to every node in the “expression” group. This group holds all node types that return a value, including leaf nodes like literals and variables, function call nodes, and even the block and if nodes. The type check pass…
Working out effective name handling mechanisms in Cone’s IR took several tries. The key challenges: Although most node types don’t use names, the ones that do are spread out unevenly across every node group: a few expressions (variables and functions), most types, and some statements (e.g., module nodes). What is the best way to gain access to a node’s name information, given…
Having spoken about the compiler’s IR tree in general terms, let’s focus in on an important detail: how to represent a node that could be any arbitary type. Cone’s IR makes use of dozens of different types of nodes, each defined using a different struct. However, sometimes the compiler needs to point to a node without restricting which type of node it must be. For example,…
The Cone compiler uses a traditional pipeline to transform source programs into object files. The Intermediate Representation (IR) plays a central role in this design. It is the glue binding together the parser, semantic analysis passes, and the LLVM IR generator. The literature on effective IR design is relatively sparse as compared to other topics, such as parsing, type inference/theory, and…
Programming is real-life magic. Using incantations rich with arcane symbols, we bring life to inanimate objects. Amazingly, our bidden servants often do exactly what we ask. Programming languages are wands we use to help channel this magic. They are fascinating tools that I have always loved learning more about. I never wanted to create my own programming language. The world is already rich with…
Realtime, quality 3D is punishing on hardware and software alike. At least every 17 milliseconds, the scene needs to be updated and redrawn. Managing memory efficiently across the many large and small data structures that make up an interesting 3D scene is a well-known and important part of that challenge.