Flow-sensitive typing

In programming language theory, flow-sensitive typing (also called flow typing or occurrence typing) is a type system where the type of an expression depends on its position in the control flow.

In statically typed languages, a type of an expression is determined by the types of the sub-expressions that compose it. However, in flow-sensitive typing, an expression's type may be updated to a more specific type if it follows an operation that validates its type. Validating operations can include type predicates, imperative updates, and control flow.

Examples

Ceylon

See the following example in Ceylon which illustrates the concept:

// Object? means the variable "name" is of type Object or else nullvoidhello(Object?name){if(isStringname){// "name" now has type String in this blockprint("Hello, ``name``!");// and it is possible to call String methods on the variableprint(" String.size is ``name.size``");}elseif(existsname){// "name" now has type Object in this blockprint("Hello, object ``name``!");}else{print("Hello, world!");}}hello(null);hello(1);hello("John Doe");

and which outputs:

Hello, world! Hello, object 1! Hello, John Doe!  String.size is 8

Kotlin

See this example in Kotlin:

funhello(obj:Any){// A type cast fails if `obj` is not a StringobjasString// Since the type cast did not fail, `obj` must be a String!vall=obj.lengthprintln("'$obj' is a string of length $l")}hello("Mooooo")

Benefits

This technique coupled with type inference reduces the need for writing type annotations for all variables or to do type casting, like is seen with dynamic languages that use duck typing. It reduces verbosity and makes for terser code, easier to read and modify.

It can also help language implementers provide implementations that execute dynamic languages faster by predicting the type of objects statically. ^[1]

Finally, it increases type safety and can prevent problems due to null pointers ^{[ how? ]}, labeled by C.A.R. Hoare—the null reference inventor—as "the billion dollar mistake" ^[2]

From a Programming Languages perspective, it's reasonable to say that flow-sensitive typing is the feature that finally made it possible to build usable type-safe programming languages with union types and without rampant dynamic checking. Until this point, attempts to add this feature to languages such as Scheme generally resulted in intractably large type representations. One example of a system with limited support for union types is Wright and Cartwright's "Soft Scheme." ^[3]

Implementations

Typed Scheme, a type system for Scheme, was the first type system with this feature. ^[4] Its successor, Typed Racket (a dialect of Racket), is also based on occurrence typing. ^[5] Shortly after Typed Scheme, David J. Pearce independently reinvented flow-typing in Whiley. ^{[6] [7]}

Typed JavaScript observed that in "scripting" languages, flow-typing depends on more than conditional predicates; it also depends on state and control flow. ^[8] This style has since been adopted in languages like Ceylon, ^[9] TypeScript ^[10] and Facebook Flow. ^[11]

There are also a few languages that don't have union types but do have nullable types, that have a limited form of this feature that only applies to nullable types, such as C#, ^[12] Kotlin, ^{[13] [14]} and Lobster. ^[15]

Alternatives

Pattern matching reaches the same goals as flow-sensitive typing, namely reducing verbosity and making up for terser code, easier to read and modify. It achieves this is in a different way, it allows to match the type of a structure, extract data out of it at the same time by declaring new variable. As such, it reduces the ceremony around type casting and value extraction. Pattern matching works best when used in conjunction with algebraic data types because all the cases can be enumerated and statically checked by the compiler.

See this example mock for Java: ^[16]

inteval(Noden){returnswitch(n){// try to type cast "Node" into "IntNode", and create the variable "i" of type "int".// If that works, then return the value of "i"caseIntNode(inti)->i;// try to type cast "Node" into "NegNode", and create the variable "n" of type "Node".// If that works, then return the negation of evaluating the "n" nodecaseNegNode(Noden)->-eval(n);// try to type cast "Node" into "AddNode", and create the variables "left" and "right" of type "Node".// If that works, then return the addition of evaluating the "left" and "right" nodescaseAddNode(Nodeleft,Noderight)->eval(left)+eval(right);// try to type cast "Node" into "MulNode", and create the variables "left" and "right" of type "Node".// If that works, then return the multiplication of evaluating the "left" and "right" nodescaseMulNode(Nodeleft,Noderight)->eval(left)*eval(right);// no "default" because the compiler knows all the possible cases have been enumerated};}

In a statically typed language, the advantage of pattern matching over flow-sensitive typing is that the type of a variable always stays the same: it does not change depending on control flow. When writing down the pattern to be matched, a new variable is declared that will have the new type.

References

1. Lukas Eder (11 December 2014). "The Inconvenient Truth About Dynamic vs. Static Typing". blog.jooq.org. Retrieved 11 March 2016.
2. Tony Hoare (2009-08-25). "Null References: The Billion Dollar Mistake". InfoQ.com. I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.
3. Wright, Andrew; Cartwright, Robert (1 Jan 1997). "A practical soft type system for scheme". ACM Transactions on Programming Languages and Systems. 19 (1): 87--152. doi:10.1145/239912.239917 . Retrieved 2024-05-04.
4. "The Design and Implementation of Typed Scheme | POPL, 2008". dl.acm.org.
5. "5 Occurrence Typing". docs.racket-lang.org.
6. David J. Pearce (22 September 2010). "On Flow-Sensitive Types in Whiley". whiley.org. Archived from the original on 11 March 2016. Retrieved 11 March 2016.
7. David J. Pearce (8 April 2012). "Whiley - Flow Typing". whiley.org. Archived from the original on 11 March 2016. Retrieved 11 March 2016.
8. "Typing Local Control and State Using Flow Analysis" . Retrieved 14 November 2016.
9. "Ceylon - Quick introduction - Typesafe null and flow-sensitive typing". ceylon-lang.org. Retrieved 11 March 2016.
10. Ryan Cavanaugh (18 November 2014). "TypeScript 1.4 sneak peek: union types, type guards, and more". blogs.msdn.microsoft.com. Retrieved 11 March 2016.
11. Avik Chaudhuri; Basil Hosmer; Gabriel Levi (18 November 2014). "Flow, a new static type checker for JavaScript". code.facebook.com. Retrieved 11 March 2016.
12. "Design with nullable reference types". docs.microsoft.com.
13. "Null Safety". kotlinlang.org. Retrieved 11 March 2016.
14. "Type Checks and Casts". kotlinlang.org. Retrieved 11 March 2016.
15. "The Lobster Type System". aardappel.github.io.
16. Gavin Bierman and Brian Goetz (19 September 2023). "JEP 441: Pattern Matching for switch". openjdk.org. Retrieved 14 November 2023.