Flow-sensitive typing
- 7 min read
- 4 chapters
Related on Lably
Through Expression (computer science), Control flow and Type conversion
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
This example in Ceylon illustrates the concept:
<span id="mwFQ"></span><span class="c1" id="mwFg">// Object? means the variable "name" is of type Object or else null</span> <span class="kt" id="mwFw">void</span><span class="w" id="mwGA"> </span><span class="nf" id="mwGQ">hello</span><span class="o" id="mwGg">(</span><span class="n" id="mwGw">Object</span><span class="o" id="mwHA">?</span><span class="w" id="mwHQ"> </span><span class="n" id="mwHg">name</span><span class="o" id="mwHw">)</span><span class="w" id="mwIA"> </span><span class="o" id="mwIQ">{</span> <span class="w" id="mwIg"> </span><span class="k" id="mwIw">if</span><span class="w" id="mwJA"> </span><span class="o" id="mwJQ">(</span><span class="k" id="mwJg">is</span><span class="w" id="mwJw"> </span><span class="n" id="mwKA">String</span><span class="w" id="mwKQ"> </span><span class="n" id="mwKg">name</span><span class="o" id="mwKw">)</span><span class="w" id="mwLA"> </span><span class="o" id="mwLQ">{</span> <span class="w" id="mwLg"> </span><span class="c1" id="mwLw">// "name" now has type String in this block</span> <span class="w" id="mwMA"> </span><span class="n" id="mwMQ">print</span><span class="o" id="mwMg">(</span><span class="s" id="mwMw">"Hello, ``name``!"</span><span class="o" id="mwNA">);</span> <span class="w" id="mwNQ"> </span><span class="c1" id="mwNg">// and it is possible to call String methods on the variable</span> <span class="w" id="mwNw"> </span><span class="n" id="mwOA">print</span><span class="o" id="mwOQ">(</span><span class="s" id="mwOg">" String.size is ``name.size``"</span><span class="o" id="mwOw">);</span> <span class="w" id="mwPA"> </span><span class="o" id="mwPQ">}</span> <span class="w" id="mwPg"> </span><span class="k" id="mwPw">else</span><span class="w" id="mwQA"> </span><span class="nf" id="mwQQ">if</span><span class="w" id="mwQg"> </span><span class="o" id="mwQw">(</span><span class="k" id="mwRA">exists</span><span class="w" id="mwRQ"> </span><span class="n" id="mwRg">name</span><span class="o" id="mwRw">)</span><span class="w" id="mwSA"> </span><span class="o" id="mwSQ">{</span> <span class="w" id="mwSg"> </span><span class="c1" id="mwSw">// "name" now has type Object in this block</span> <span class="w" id="mwTA"> </span><span class="n" id="mwTQ">print</span><span class="o" id="mwTg">(</span><span class="s" id="mwTw">"Hello, object ``name``!"</span><span class="o" id="mwUA">);</span> <span class="w" id="mwUQ"> </span><span class="o" id="mwUg">}</span> <span class="w" id="mwUw"> </span><span class="k" id="mwVA">else</span><span class="w" id="mwVQ"> </span><span class="o" id="mwVg">{</span> <span class="w" id="mwVw"> </span><span class="n" id="mwWA">print</span><span class="o" id="mwWQ">(</span><span class="s" id="mwWg">"Hello, world!"</span><span class="o" id="mwWw">);</span> <span class="w" id="mwXA"> </span><span class="o" id="mwXQ">}</span> <span class="o" id="mwXg">}</span> <span class="n" id="mwXw">hello</span><span class="o" id="mwYA">(</span><span class="kc" id="mwYQ">null</span><span class="o" id="mwYg">);</span> <span class="n" id="mwYw">hello</span><span class="o" id="mwZA">(</span><span class="mi" id="mwZQ">1</span><span class="o" id="mwZg">);</span> <span class="n" id="mwZw">hello</span><span class="o" id="mwaA">(</span><span class="s" id="mwaQ">"John Doe"</span><span class="o" id="mwag">);</span>and which outputs:
<span id="mwbg"></span><span class="go" id="mwbw">Hello, world!</span> <span class="go" id="mwcA">Hello, object 1!</span> <span class="go" id="mwcQ">Hello, John Doe!</span> <span class="go" id="mwcg"> String.size is 8</span>
Kotlin
This example is in Kotlin:
<span id="mweA"></span><span class="kd" id="mweQ">fun</span><span class="w" id="mweg"> </span><span class="nf" id="mwew">hello</span><span class="p" id="mwfA">(</span><span class="n" id="mwfQ">obj</span><span class="p" id="mwfg">:</span><span class="w" id="mwfw"> </span><span class="kt" id="mwgA">Any</span><span class="p" id="mwgQ">)</span><span class="w" id="mwgg"> </span><span class="p" id="mwgw">{</span> <span class="w" id="mwhA"> </span><span class="c1" id="mwhQ">// A type cast fails if `obj` is not a String</span> <span class="w" id="mwhg"> </span><span class="n" id="mwhw">obj</span><span class="w" id="mwiA"> </span><span class="k" id="mwiQ">as</span><span class="w" id="mwig"> </span><span class="kt" id="mwiw">String</span> <span class="w" id="mwjA"> </span><span class="c1" id="mwjQ">// Since the type cast did not fail, `obj` must be a String!</span> <span class="w" id="mwjg"> </span><span class="kd" id="mwjw">val</span><span class="w" id="mwkA"> </span><span class="nv" id="mwkQ">l</span><span class="w" id="mwkg"> </span><span class="o" id="mwkw">=</span><span class="w" id="mwlA"> </span><span class="n" id="mwlQ">obj</span><span class="p" id="mwlg">.</span><span class="na" id="mwlw">length</span> <span class="w" id="mwmA"> </span><span class="n" id="mwmQ">println</span><span class="p" id="mwmg">(</span><span class="s" id="mwmw">"'</span><span class="si" id="mwnA">$</span><span class="n" id="mwnQ">obj</span><span class="s" id="mwng">' is a string of length </span><span class="si" id="mwnw">$</span><span class="n" id="mwoA">l</span><span class="s" id="mwoQ">"</span><span class="p" id="mwog">)</span> <span class="p" id="mwow">}</span> <span class="w" id="mwpA"> </span> <span class="n" id="mwpQ">hello</span><span class="p" id="mwpg">(</span><span class="s" id="mwpw">"Mooooo"</span><span class="p" id="mwqA">)</span>Sign in to keep reading
3 more chapters are free with a Lably account.
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.
Finally, it increases type safety and can prevent problems due to null pointers, labeled by C.A.R. Hoare—the null reference inventor—as "the billion dollar mistake"
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 event, 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.
History and Implementations
The history of the idea goes back at least to Tony Hoare's "record class discriminators" from the mid-1960s. However, practical type systems including it as a feature are much more recent.
Typed Scheme, a type system for Scheme developed by Sam Tobin-Hochstadt and first published in 2008, was the first type system to include occurrence typing. Its successor, Typed Racket (a dialect of Racket), is also based on occurrence typing. Shortly after Typed Scheme, David J. Pearce independently reinvented flow-typing in Whiley.
Typed JavaScript observed that in "scripting" languages, flow-typing depends on more than conditional predicates; it also depends on state and control flow. This style has since been adopted in languages like Ceylon, TypeScript and Facebook Flow.
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#, Kotlin, and Lobster.
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:
<span id="mwARc"></span><span class="linenos" data-line="1" id="mwARg"></span><span class="kt" id="mwARk">int</span><span class="w" id="mwARo"> </span><span class="nf" id="mwARs">eval</span><span class="p" id="mwARw">(</span><span class="n" id="mwAR0">Node</span><span class="w" id="mwAR4"> </span><span class="n" id="mwAR8">n</span><span class="p" id="mwASA">)</span><span class="w" id="mwASE"> </span><span class="p" id="mwASI">{</span> <span class="linenos" data-line="2" id="mwASM"></span><span class="w" id="mwASQ"> </span><span class="k" id="mwASU">return</span><span class="w" id="mwASY"> </span><span class="k" id="mwASc">switch</span><span class="p" id="mwASg">(</span><span class="n" id="mwASk">n</span><span class="p" id="mwASo">)</span><span class="w" id="mwASs"> </span><span class="p" id="mwASw">{</span> <span class="linenos" data-line="3" id="mwAS0"></span><span class="w" id="mwAS4"> </span><span class="c1" id="mwAS8">// try to type cast "Node" into "IntNode", and create the variable "i" of type "int".</span> <span class="linenos" data-line="4" id="mwATA"></span><span class="w" id="mwATE"> </span><span class="c1" id="mwATI">// If that works, then return the value of "i"</span> <span class="linenos" data-line="5" id="mwATM"></span><span class="w" id="mwATQ"> </span><span class="k" id="mwATU">case</span><span class="w" id="mwATY"> </span><span class="n" id="mwATc">IntNode</span><span class="p" id="mwATg">(</span><span class="kt" id="mwATk">int</span><span class="w" id="mwATo"> </span><span class="n" id="mwATs">i</span><span class="p" id="mwATw">)</span><span class="w" id="mwAT0"> </span><span class="o" id="mwAT4">-></span><span class="w" id="mwAT8"> </span><span class="n" id="mwAUA">i</span><span class="p" id="mwAUE">;</span> <span class="linenos" data-line="6" id="mwAUI"></span><span class="w" id="mwAUM"> </span><span class="c1" id="mwAUQ">// try to type cast "Node" into "NegNode", and create the variable "n" of type "Node".</span> <span class="linenos" data-line="7" id="mwAUU"></span><span class="w" id="mwAUY"> </span><span class="c1" id="mwAUc">// If that works, then return the negation of evaluating the "n" node</span> <span class="linenos" data-line="8" id="mwAUg"></span><span class="w" id="mwAUk"> </span><span class="k" id="mwAUo">case</span><span class="w" id="mwAUs"> </span><span class="n" id="mwAUw">NegNode</span><span class="p" id="mwAU0">(</span><span class="n" id="mwAU4">Node</span><span class="w" id="mwAU8"> </span><span class="n" id="mwAVA">n</span><span class="p" id="mwAVE">)</span><span class="w" id="mwAVI"> </span><span class="o" id="mwAVM">-></span><span class="w" id="mwAVQ"> </span><span class="o" id="mwAVU">-</span><span class="n" id="mwAVY">eval</span><span class="p" id="mwAVc">(</span><span class="n" id="mwAVg">n</span><span class="p" id="mwAVk">);</span> <span class="linenos" data-line="9" id="mwAVo"></span><span class="w" id="mwAVs"> </span><span class="c1" id="mwAVw">// try to type cast "Node" into "AddNode", and create the variables "left" and "right" of type "Node".</span> <span class="linenos" data-line="10" id="mwAV0"></span><span class="w" id="mwAV4"> </span><span class="c1" id="mwAV8">// If that works, then return the addition of evaluating the "left" and "right" nodes</span> <span class="linenos" data-line="11" id="mwAWA"></span><span class="w" id="mwAWE"> </span><span class="k" id="mwAWI">case</span><span class="w" id="mwAWM"> </span><span class="n" id="mwAWQ">AddNode</span><span class="p" id="mwAWU">(</span><span class="n" id="mwAWY">Node</span><span class="w" id="mwAWc"> </span><span class="n" id="mwAWg">left</span><span class="p" id="mwAWk">,</span><span class="w" id="mwAWo"> </span><span class="n" id="mwAWs">Node</span><span class="w" id="mwAWw"> </span><span class="n" id="mwAW0">right</span><span class="p" id="mwAW4">)</span><span class="w" id="mwAW8"> </span><span class="o" id="mwAXA">-></span><span class="w" id="mwAXE"> </span><span class="n" id="mwAXI">eval</span><span class="p" id="mwAXM">(</span><span class="n" id="mwAXQ">left</span><span class="p" id="mwAXU">)</span><span class="w" id="mwAXY"> </span><span class="o" id="mwAXc">+</span><span class="w" id="mwAXg"> </span><span class="n" id="mwAXk">eval</span><span class="p" id="mwAXo">(</span><span class="n" id="mwAXs">right</span><span class="p" id="mwAXw">);</span> <span class="linenos" data-line="12" id="mwAX0"></span><span class="w" id="mwAX4"> </span><span class="c1" id="mwAX8">// try to type cast "Node" into "MulNode", and create the variables "left" and "right" of type "Node".</span> <span class="linenos" data-line="13" id="mwAYA"></span><span class="w" id="mwAYE"> </span><span class="c1" id="mwAYI">// If that works, then return the multiplication of evaluating the "left" and "right" nodes</span> <span class="linenos" data-line="14" id="mwAYM"></span><span class="w" id="mwAYQ"> </span><span class="k" id="mwAYU">case</span><span class="w" id="mwAYY"> </span><span class="n" id="mwAYc">MulNode</span><span class="p" id="mwAYg">(</span><span class="n" id="mwAYk">Node</span><span class="w" id="mwAYo"> </span><span class="n" id="mwAYs">left</span><span class="p" id="mwAYw">,</span><span class="w" id="mwAY0"> </span><span class="n" id="mwAY4">Node</span><span class="w" id="mwAY8"> </span><span class="n" id="mwAZA">right</span><span class="p" id="mwAZE">)</span><span class="w" id="mwAZI"> </span><span class="o" id="mwAZM">-></span><span class="w" id="mwAZQ"> </span><span class="n" id="mwAZU">eval</span><span class="p" id="mwAZY">(</span><span class="n" id="mwAZc">left</span><span class="p" id="mwAZg">)</span><span class="w" id="mwAZk"> </span><span class="o" id="mwAZo">*</span><span class="w" id="mwAZs"> </span><span class="n" id="mwAZw">eval</span><span class="p" id="mwAZ0">(</span><span class="n" id="mwAZ4">right</span><span class="p" id="mwAZ8">);</span> <span class="linenos" data-line="15" id="mwAaA"></span><span class="w" id="mwAaE"> </span><span class="c1" id="mwAaI">// no "default" because the compiler knows all the possible cases have been enumerated</span> <span class="linenos" data-line="16" id="mwAaM"></span><span class="w" id="mwAaQ"> </span><span class="p" id="mwAaU">};</span> <span class="linenos" data-line="17" id="mwAaY"></span><span class="p" id="mwAac">}</span>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.