Custom operators, Associativity and Precedence in F#

10 Sep 2014

Introduction

F# is a really nice language for creating embedded domain specific languages. One of the features of F# that affords this is the ability to define custom prefix and infix operators. A nice example of a simple embedded domain specific language (eDSL) for working with XML can be found on fssnip. While experimenting with my own simple eDSLs I've found that the documentation around how custom operators are defined, their precedence and their associativity somewhat confusing and even incomplete in places. I did some investigating and put together this guide/cheatsheet, more as a reminder for myself but others might find it useful. Its been assembled from the F# documenation, the F# language specfication and also a number of experiments I've conducted, so there may be a mistake or two. This guide is not supposed to be definitive authority on custom operators, associativity and precendence, that is enshrined in both the F# compiler source code and the F# language specification. This guide is really just a helpful cheatsheet that covers most of the common cases and scenarios and is hopefully somewhat easier to consult than the language specification.

Prefix Operators

Prefix operators are unary operations i.e. they only have a single operand. The most familiar prefix operator to most developers would be something like (in C#):

bool result = !true

Where ! is defined as the unary negation operator. It takes its single argument, the boolean value true, and applies the ! function to produce the value false.

Prefix operators come in two varieties: tilde-prefixed (~) or bang-prefixed (!).

Tilde-prefix operators

Tilde-prefix operators must start with the tilde character (~) and the subsquent operator characters can only be selected from a limited set. The set of tilde-prefixed operator characters it's possible to use are +, -, +., -., %, %%, &, &&. It's possible to use these characters as part of both prefix and infix operators but we'll talk about their use as prefix operators to start with. They are classified as prefix operators if they are preceded by the tilde character in the operator definition.

In addition, tilde-prefixed operators can be made up of any number of tilde characters as long as the tilde is the only character.

When using a tilde-prefix operator in an expression the tilde character is omitted, unless the tilde character is the only character in the operator.

Here is the complete set of tilde-prefix operator definitions that it's possible to define and as well as example usage:

//Operator definnitions
let ( ~~ ) a = a 
let ( ~~~ ) a = a   //Or any number of tilde characters 
let ( ~+ ) a = a
let ( ~+.) a = a 
let ( ~- ) a = a 
let ( ~-. ) a = a 
let ( ~% ) a = a
let ( ~%% ) a = a 
let ( ~& ) a = a 
let ( ~&& ) a = a

//Usage
type MyType = MyType of string
let foo = MyType "abc"

(~~ foo)  |> ignore 
(~~~ foo) |> ignore 
(+ foo)   |> ignore 
(+. foo)  |> ignore 
(- foo)   |> ignore
(-. foo)  |> ignore 
(% foo)   |> ignore 
(%% foo)  |> ignore 
(& foo)   |> ignore 
(&& foo)  |> ignore

Bang-prefix operators

Bang-prefix operators are much less restrictive than the tilde-prefix operators. They must begin with the ! character but can be followed by any number and any combination of the following characters: !, %, &, +, ., /, <, =, >, @,^, |, ~, ?, **. The one exception to this rule is that you cannot define a prefix operator that begins != . This character sequence is reserved as an infix operator only. Bang-prefix operators require the bang to be included as part of the expression during usage.

Here's some examples:

//Operator definitions
let ( !! ) a = a 
let ( !% ) a = a 
let ( !& ) a = a 
let ( !* ) a = a 
let ( !+ ) a = a 
let ( !. ) a = a 
let ( !/ ) a = a 
let ( !< ) a = a 
let ( !> ) a = a
let ( !@ ) a = a 
let ( !^ ) a = a 
let ( !| ) a = a 
let ( !~ ) a = a 
let ( !? ) a = a 
let ( !>+@ ) a = a  //Or any combination of the above infix characters
                    //following the bang
let ( !//>) a = a   //Or any combination of the above infix characters 
                    //following the bang

//let ( != ) a = a  // Not Allowed!  
//let ( !=@ ) a = a // Not Allowed (or any other character sequence 
                    //starting with !=)!

//Usage
type MyType = MyType of string
let foo = MyType "abc"

!! foo |> ignore 
!% foo |> ignore 
!& foo |> ignore 
!* foo |> ignore 
!+ foo |> ignore
!. foo |> ignore 
!/ foo |> ignore 
!< foo |> ignore 
!> foo |> ignore 
!@ foo |> ignore
!^ foo |> ignore 
!| foo |> ignore 
!~ foo |> ignore 
!? foo |> ignore 

!>+@ foo |> ignore //A random selection of characters
!//> foo |> ignore

Infix Operators

Infix operators are the more common operator type and are binary operators, that is, they have two operands:

let num = 1 + 2

Where + is defined as the binary addition operator which takes arguments 1 and 2 and adds them together to produce the number 3.

Infix operators may be defined as

  1. Consisting only of the single character +, -, %, &, $, @, <, >, =, ?.
  2. Consisting of any character sequences starting with: +OP, -OP, <OP, >OP, =OP, |OP, &OP, ^OP, *OP, /OP, %OP, @OP. Where OP is one or more of the following characters: !, %, &, *, +, -, ., /, <, =, >, @, ^, |, ~ e.g. +%|. Finally, infix-operators beginning with these characters can be preceded by any number of . characters. The . character does not change the associativity or precedence.
  3. Consisting only of the multiple character sequence (with special precendence and associativity rules, discussed in the following section) !=, :=, or, ||, &&, ?<-

What do these rule mean in practice? You can define single character infix operators:

let ( + ) a b = a //Ok
let ( % ) a b = a //Ok

let ( : ) a b = a //Not ok! The : is not in the set of characters for single
                  //character infix operators

You can define multiple character infix operators:

let ( ++ ) a b = a   //Ok
let ( >>= ) a b = a  //Ok
let ( <@> ) a b = a  //OK
let ( @-^//) a b = a //A random selection of allowable characters but still OK

let ( .+ ) a b = a   //Ok. Preceded by . character
let ( ...+) a b = a  //Still Ok. Any number of preceeding . characters are allowed


let ( ¬= ) a b = a  //Not Ok! Starts with an incorrect first character
let ( @¬ ) a b = a  //Not Ok! First character is ok but is followed by an
                    //incorrect character

let ( <$> ) a b = a //Not Ok! Whilst the $ can be used as a single character
                    //infix-operator, it is not allowed to be used in multiple
                    //character infix-operator sequences.

And you can define mutliple character infix operators that have special precedence and associativity rules. These rules are discussed further down.

let ( != ) a b = a //Ok but special precedence and associativity rules apply
let ( := ) a b = a //Ok but special precedence and associativity rules apply
let ( or ) a b = a //Ok but special precedence and associativity rules apply
let ( || ) a b = a //Ok but special precedence and associativity rules apply

Using custom infix operators works exactly like you'd expect. There's no ommitting of characters as there is with tilde-prefix operators:

let ( ++ ) a b = a

type MyType = MyType of string
let foo = MyType "abc"

let result = foo ++ foo

Associativity and Precedence

The associativity and precendece of an operator is given by the operator type and also the operators first letter. The following table shows the associativity and precedence for custom operators only. Items higher up in the table have a higher precedence than items lower in the table. Please note that this table only shows the rules for customer operators. The full set of associativity and precendence rules can be found in the documentation or the language specification.

Operator Associativity
Any prefix operator Left
Infix operator starting with ** Right
Infix operator starting with *, / or %
Left
Infix operator starting with - or + Left
Infix operator starting with ^ Right
Infix operator starting with !=, <, >, =, |, &, $, @ Left
Infix operator &, && (no subsequent characters) Left
Infix operator or or || Left
Infix operator := Left

Let's see some examples:

let ( ^ ) a b = a  //Associates to the right
let ( ^= ) a b = a //Same associativity and precedence rules as ^ because it's
                   //only the first character that matters

let foo = MyType "abc"

let result1 = foo ^ foo ^ foo         //Parsed as (foo ^ (foo ^ foo))
let result2 = foo ^= foo ^= foo       //Parsed as (foo ^= (foo ^= foo))
let result3 = foo ^ foo ^= foo ^ foo  //Parsed as (foo ^ (foo ^= (foo ^ foo)))

let ( ++ ) a b = a               //Associates to the left

let result4 = foo ++ foo ++ foo  //Parsed as ((foo ++ foo) ++ foo)

let result5 = foo ++ foo ^ foo   //Parsed as ((foo ++ foo)) ^ foo) because + has 
                                 //higher precedence than ^

We saw that when defining infix operators that some combinations of characters will have special associativity and precedence rules, irrespetive of the first character in the operator:

(* Associtivity and precedence defined by the the first character, |.
   Associates to the left has same precedence as |- and higher precedence 
   than ||
*) 
let ( |+ ) a b = a 

(* Associtivity and precedence defined by the the first character, |.
   Associates to the left has same precedence as |+ and higher precedence 
   than ||
*) 
let ( |- ) a b = a 

(* Has special rules. Associates to the left, has lower precedence than |+
   and |- 
*) 
let ( || ) a b = a  

Some characters can be used as both a prefix and an infix operators at the same time. Here's an example of the - being used as both a prefix and an infix operator simultaneously:

//Operator Definition 
let ( ~- ) a = a 
let ( - ) a b = a

let a, b, c, d = (MyType "a"), (MyType "b"), (MyType "c"), (MyType "d")

let result = a - - b - - c - d

(* We know that prefix operators have the highest precedence and associates to the
   left. We also know that the - infix operator has a lower precedence and also
   associates to the left. Therefore the above expression will be parsed as 
   (((a - (- b)) - (- c)) - d)
*)

These rules are particularly nuanced. When starting out with F# I wondered whether it would be possible to write infix functions using something like Haskell's backtick syntax. I came across the following solution:

let ( </ ) a b = a |> b
let ( /> ) a b = a <| b
let modulo a b = a % b

let result = 10 </modulo/> 3

It turns out that this doesn't quite operate like I expected:

let result = 10 </modulo/> 3 // result = 3!
let result = 10 % 3          // result = 1

We can use the information in the table above to deduce what went wrong. Operators beginning with the / character have a higher precendence than operators beginning with the < character.

let result = 10 </modulo/> 3

//expands to
let result = 10 </ (modulo /> 3)
let result = 10 </ (modulo <| 3)
let result = 10 </ (fun x -> 3 % x) //modulo, partially applied
let result = 10 |> (fun x -> 3 % x)
let result = 3 % 10
let result = 3

An alternative representation of the "infix function" syntax could be:

let result = 10 |> modulo <| 3  //result = 1

This method works as expected. Again, we can use the associativity and precendence rules above to see that both leading characters | and < have the same precedence and they associate to the left.

let result = 10 |> modulo <| 3

//Expands to
let result = (10 |> modulo) <| 3
let result = (fun x -> 10 % x) <| 3 //modulo, partially applied
let result = 10 % 3
let result = 1

Published on 10 Sep 2014 permalink Find me on Github

comments powered by Disqus