A type theory mnemonic for boolean operator precedence

yawaramin

Yawar Amin

Posted on September 16, 2024

A type theory mnemonic for boolean operator precedence

IN COMPUTER languages which support boolean operators like && (and) and || (or), && typically has higher precedence than ||. In other words, the following happens:

p && q || r == (p && q) || r
p || q && r == p || (q && r)
Enter fullscreen mode Exit fullscreen mode

You can take advantage of this to construct simpler expressions which don't need so many parentheses. Eg, let's look at Cloudflare's expression language:

http.host eq "app.foo.com" and http.request.uri.path eq "/api" or http.host eq "api.foo.com" and http.request.uri.path eq "/app"
Enter fullscreen mode Exit fullscreen mode

The above is equivalent to:

(http.host eq "app.foo.com" and http.request.uri.path eq "/api") or (http.host eq "api.foo.com" and http.request.uri.path eq "/app")
Enter fullscreen mode Exit fullscreen mode

Let's leave aside for a moment the argument that you should use parentheses for explicit grouping and readability; readability is a very subjective question. The bigger problem might be that, unless you regularly design or use such logical expressions, it might be difficult to remember this operator precedence.

Math operator precedence

However, one precedence rule that most people remember pretty easily is that of math operators like + and * (yes, I'm using the programming language symbol * instead of the math symbol ✖️). We of course know, probably since childhood, that multiplication has higher precedence than addition. So,

a * b + c == (a * b) + c
a + b * c == a + (b * c)
Enter fullscreen mode Exit fullscreen mode

Look familiar? These are the same precedence rules as for the logical operators shown above, where:

&& is equivalent to *
|| is equivalent to +
Enter fullscreen mode Exit fullscreen mode

The type theory connection

Of course, type theory enthusiasts know pretty well that the symbols + and * are used to represent sum types and product types. The name is no coincidence: a sum type like a + b has the same number of values as the sum of the numbers of values of a and b. And a product type like a * b has the same number of values as the product of the numbers of values of a and b.

Try working through an example where type a = bool (2 possible values) and type b = unit (1 possible value). How many values does the type a + b have, and how many does a * b have?

In type theory, sum types represent alternatives, so a + b means 'a value that can be a or b', while a * b means 'a value that contains a and b' (commonly known as a tuple or pair). So in the type theory world,

* == &&
+ == ||
Enter fullscreen mode Exit fullscreen mode

And very conveniently, they have the same precedence rules! So, if you are ever trying to remember the precedence, just remind yourself that 'and is times, or is plus'.

💖 💪 🙅 🚩
yawaramin
Yawar Amin

Posted on September 16, 2024

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

What was your win this week?
weeklyretro What was your win this week?

November 29, 2024

Where GitOps Meets ClickOps
devops Where GitOps Meets ClickOps

November 29, 2024

How to Use KitOps with MLflow
beginners How to Use KitOps with MLflow

November 29, 2024