12.1 Precedence in Bindings

In chapter 1 we introduces the basics for binding to C functions. We wrote code like this:

  type mybool = "bool";
  
  const myfalse : mybool = "false";
  const mytrue : mybool = "true";
  
  fun myand : mybool * mybool -> mybool = "$1&&$2";
  fun myor : mybool * mybool -> mybool = "$1||$2";
  fun mynot : mybool -> mybool = "!$1";
  
  proc myprint : mybool= '::std::cout<<($1??"mytrue":"myfalse")<<::std::endl;' 
    requires header "#include <iostream>"
  ;

but we glossed over an important issue. We understand intuitively how Felix generates calculations by substitution. For example we understand that this works:

  fun calc(x:mybool, y:mybool, z:mybool) =>
    myand (myor (mynot x, myor (y, mynot z)), myand (x,y));
  ;
  myprint (calc (mytrue, myfalse, mytrue));

myfalse

but what does the generated code look like? Roughly we expect this:

  ((!(x))||((y)||(!(z))))&&((x)&&(y))

We expect Felix to generate

  $1&&$2 --> ($1)||($2)

to get the precedence right: we have to put parens around the arguments, because we don't know what they are. We're tempted to make it even worse by emitting parens around the whole expression as well (just in case .. :)

But this is not what you get. Instead you will see:

  (!x||y||!z)&&x&&y

or something similar. Only the necessary parens are emitted. How does Felix do this?

Well, you would be right that it does some kind of micro parsing. First, Felix has the followin built-in precedence names:

let precedence = [
  "atom";
  "primary";
  "postfix";
  "unary";
  "cast";
  "pm";
  "mult";
  "add";
  "shift";
  "rel";
  "eq";
  "band";
  "bxor";
  "bor";
  "and";
  "xor";
  "or";
  "cond";
  "assign";
  "comma";
  "expr";
]

These names related to the ISO C++ Standard grammar. Next, we extend the syntax for a binding as so:

  fun someand : mybool * mybool -> mybool =
    "$1:band  &&  $2:bor" is band
  ;

Here, we have provided a grammar production by specifying the nonterminal for argument 1 as band, for argument 2 as bor and the whole expression as band. This is like writing:

  band = band "&&" bor

in some grammar. It tells the precedence of the arguments and resulting expression. If Felix has this information on every C function binding, it can calculate when parentheses are required to keep the grouping correct, and when then can be omitted.

This is the general form of a function binding. Procedure bindings also allow the precedence specification on arguments but have no need for one on the return value because there isn't one.

But we did not put this information into our bindings! Why did it work? The answer is a bit simplistic: there's a lookup table for common cases and Felix just remaps your string if it matches:

let remaps = [
  "$1++",("$1:postfix ++ ","postfix");
  "$1--",("$1:postfix -- ","postfix");
  "$1($2)",("$1:postfix($2:assign)","postfix");
  "$1[$2]",("$1:postfix[$2:expr]","postfix");
  "$1->$2",("$1:postfix->$2:atom","postfix");

  "$1.*$2",("$1:pm.*$2:cast","pm");
  "$1->*$2",("$1:pm->*$2:cast","pm");

  "~$1",("~$1:unary","unary");
  "+$1",("+ $1:unary","unary");
  "-$1",("- $1:unary","unary");
  "!$1",("!$1:unary","unary");
  "&$1",("& $1:unary","unary");
  "*$1",("*$1:unary","unary");
  "++$1",("++ $1:unary","unary");
  "--$1",("-- $1:unary","unary");

  "$1*$2",("$1:mult * $2:pm","mult");
  "$1/$2",("$1:mult / $2:pm","mult");
  "$1%$2",("$1:mult % $2:pm","mult");

  "$1+$2",("$1:add + $2:mult","add");
  "$1-$2",("$1:add - $2:mult","add");

  "$1<<$2",("$1:shift << $2:add","shift");
  "$1>>$2",("$1:shift >> $2:add","shift");

  "$1<$2",("($1:rel < $2:shift)","rel");
  "$1>$2",("($1:rel > $2:shift)","rel");
  "$1>=$2",("($1:rel >= $2:shift)","rel");
  "$1<=$2",("($1:rel <= $2:shift)","rel");

  "$1==$2",("($1:eq == $2:rel)","eq");
  "$1!=$2",("($1:eq != $2:rel)","eq");

  "$1&$2",("$1:band & $2:eq","band");
  "$1|$2",("$1:bor | $2:band","bor");
  "$1^$2",("$1:bxor ^ $2:bor","bxor");

  "$1&&$2",("$1:and && $2:bxor","and");
  "$1||$2",("$1:or || $2:and","or");


  "$1+=$2",("$1:cond += $2:assign","assign");
  "$1-=$2",("$1:cond -= $2:assign","assign");
  "$1*=$2",("$1:cond *= $2:assign","assign");
  "$1/=$2",("$1:cond /= $2:assign","assign");
  "$1%=$2",("$1:cond %= $2:assign","assign");
  "$1<<=$2",("$1:cond <<= $2:assign","assign");
  "$1>>=$2",("$1:cond >>= $2:assign","assign");
  "$1&=$2",("$1:cond &= $2:assign","assign");
  "$1|=$2",("$1:cond |= $2:assign","assign");
  "$1^=$2",("$1:cond ^= $2:assign","assign");
  "$1:comma,$2:comma",("$1,$2","comma");

  (* common library stuff: a hack but safe, prolly should fix in library*)
  "&::std::cout",("&::std::cout","unary");
  "&::std::cerr",("&::std::cerr","unary");
  "$1.size()",("$1:postfix.size()","postfix");
  "$1.data[$2]",("$1:postfix.data[$2:expr]","postfix");

  "::flx::rtl::strutil::str<int>($1)",("::flx::rtl::strutil::str<int>($1:assign)","postfix");
  "::flx::rtl::strutil::str<#1>($1)",("::flx::rtl::strutil::str<#1>($1:assign)","postfix");
  "static_cast<#0>($1)",("static_cast<#0>($1:assign)","postfix");
  "reinterpret<?1>($1)",("reinterpret<?1>($1:assign)","postfix");
]

There's also a rather lame micro parser that checks for function applications like:

"func(...)"

where func is an identifier, and gives such an expression the postfix precedence, and the most trivial case:

"identifier"

is known to be an atom.

The micro parser might do extra work in future, but for now, if you are not sure that Felix recognizes your binding expression you have two choices: you can put the precedence codes in, or you can let Felix insert parentheses unconditionally. The micro parsing is conservative, if Felix isn't sure it always puts in parentheses.

You may wonder what the purpose of all this is. The answer is: sometimes you may need to actually read the generated C++. For debugging, for example. This is hard to do if it is littered with gratuitous parentheses! Can you parse this?

  ((!(x))||((y)||(!(z))))&&((x)&&(y))

No? I couldn't either. I got it wrong several times. In fact I don't even know if its right now!