11
$\begingroup$

The most obvious way of supporting chained comparisons operators, such as a < b < c, is to rewrite it as (a < b) and (b < c). That's what I've done in my AEC-to-WebAssembly compiler, written in C++:

  } else if (text == "<" or text == ">" or text == "<=" or text == ">=") {
    if (children.at(0).text ==
        text) // Chained comparisons, such as `a < b < c`.
    {
      TreeNode andNode("and", lineNumber, columnNumber),
          secondChild(text, lineNumber, columnNumber);
      secondChild.children = {children.at(0).children.at(1), children.at(1)};
      andNode.children = {children.at(0), secondChild};
      std::cerr
          << "Line " << lineNumber << ", Column " << columnNumber
          << ", Compiler warning: Chained comparisons are not implemented "
             "correctly in this compiler. The middle term, in this case \""
          << children.at(0).children.at(1).text
          << "\", will be evaluated twice, possibly leading to unintended side "
             "effects. I am sorry about that, but, thus far, there does not "
             "seem to be a simple solution given the way the compiler is "
             "structured. I've started a StackExchange thread about that "
             "problem: https://langdev.stackexchange.com/q/3755/330"
          << std::endl;
      return ";;Chained comparison, converting " + getLispExpression() +
             " to " + andNode.getLispExpression() + "\n" +
             andNode.compile(context);
    }

However, there is a problem with that. Suppose that b is a function which has side-effects. As I've written it, the compiled code would call it twice instead of once.

For example, this program in AEC:

#target WASI

Integer16 counter := 0;

Function b() Which Returns Integer32 Does
    counter += 1;
    Return counter;
EndFunction

Function test() Which Returns Integer32 Does
    // By common sense, this should return 1. However, because of the
    // current AEC semantics, this returns 2.
    counter := 0;
    Integer16 a := 0, c := 2;
    Integer16 resultOfComparison := a <= b() <= c;
    Return counter;
EndFunction

If invoked with this program in JavaScript:

const fs = require("fs");
const buffer = fs.readFileSync("chainedComparisonWithSideEffects.wasm");
WebAssembly.instantiate(buffer).then((results) => {
  const exports = results.instance.exports;
  console.log("The test returns: " + exports.test());
});

It outputs The test returns: 2 instead of The test returns: 1.

So, how do you compile it correctly?

$\endgroup$
5
  • 7
    $\begingroup$ Evaluate the expression once and use it twice? Why do you need to have a tree rather than a DAG? $\endgroup$ Commented Apr 29 at 12:32
  • 5
    $\begingroup$ If you really need to use an expression tree at this stage rather than a DAG, you can postpone that to whenever you lower to the webasm DAG using something along the lines of let temp = b in a < temp and temp < c if you can create an anonymous temporary in your expression tree. $\endgroup$ Commented Apr 29 at 12:35
  • 4
    $\begingroup$ For correct semantics you (presumably) must evaluate a before b, so you must use locals for both. CPython can avoid locals by using the stack instructions DUP_TOP and ROT_THREE, but unfortunately WebAssembly doesn't have those. $\endgroup$
    – kaya3
    Commented Apr 29 at 13:29
  • $\begingroup$ @user1937198 What is DAG? $\endgroup$ Commented May 1 at 7:24
  • 3
    $\begingroup$ @FlatAssembler Directed Acyclic Graph: en.wikipedia.org/wiki/Directed_acyclic_graph Which allows representing that values may be consumed multiple times, which is an extreamly common desire when de-sugaring. $\endgroup$ Commented May 1 at 10:44

4 Answers 4

12
$\begingroup$

The trite answer is that if evaluating b twice is wrong, then it should only be evaluated once...

Disclaimer: I don't know AEC, so I'm going to make up syntax.

Desugaring or not

For the purpose of this answer, I'll define desugaring of AEC as a transformation to semantically equivalent AEC code.

The first question I would ask is whether you should desugar or not.

Desugaring has the advantage of removing constructs early, thereby potentially simplifying the rest of the compiler, but it does come with its own challenges: diagnostics should refer to the original source, the meaning shouldn't change, and sometimes it's just plain impossible to express the target semantics in the language.

So, if you can't desugar for any reason, don't. Move the problem to a later part of the compilation pipeline which will not suffer from the limitations that desugaring faces.

If you do wish to desugar, read on.

Variables

The desugaring requires introducing variables, which should definitely NOT shadow any existing variable.

A trick which may help is to cheat. Reserving a prefix for the "implementation", as C and C++ do, allows to use @1, @2, etc... when nobody else is allowed to. Otherwise, you need the set of in-scope variable names, and you need to avoid them.

With a Block Expression

If the language has block expressions1, you essentially want to replace a’ < b’ < c’ by the following:

{
    let @1 = a’;
    let @2 = b’;

    @1 < @2 && @2 < c’
}

(where a’ and co are place-holders for expressions)

If there are more elements, nest:

{
    let @1 = a’;
    let @2 = b’;

    @1 < @2 && {
        let @3 = c’;

        @2 < @3 && {
            let @4 = d’;

            @3 < @4
        }
    }
}

Block expressions are the best in that even in languages such as Rust where typing and borrowing are so strict, they avoid having to spell out the types, borrowing modes, etc...

1 Block expressions are the abilities to use a block as an expression.

With a Closure

In the absence of block expressions, the easiest is to introduce a closure:

def closure_42():
    @1 = a’
    @2 = b’

    if not (@1 < @2):
        return False

    @3 = c’

    if not (@2 < @3):
        return False

    # Possibly further expressions

    return True

The closure is then substituted in place of the replaced expression.

With a function

In the absence of closures, you can emulate it...

You essentially create a function which takes as input the union of all the variables referenced in the expression to replace. This works well in dynamically typed languages, or languages with templates.

def generated_42(v_0’, v_1’, v_2’, v_3’):
    @1 = a’
    @2 = b’

    if not (@1 < @2):
        return False

    @3 = c’

    if not (@2 < @3):
        return False

    # Possibly further expressions

    return True

Where v_0’, v_1’, v_2’, ... are the variables of the scope in which a’, b’, and c’ are defined that are referenced by a’, b’, and c’. Note that each reference variable need only be passed once, and they should have the same name as they had before.

In-situ

The last and least solution is an in-situ rewrite of the entire condition.

It's my least favorite because it requires rewriting the entire expression, not just the sub-expression a’ < b’ < c’, or at the very least rewriting the prefix of the expression up to the last sub-expression to rewrite. This makes the rewrite less local, so more annoying to do correctly, and it gets worse when you have multiple sub-expressions to rewrite in a single expression.

And on top of that it can't use short-circuiting.

Before:

    if foo() and a’ < b’ < c’ ... and bar():
        # Original block.

After:

    @condition = foo()

    if @condition:
        @1 = a’
        @2 = b’

        @condition = @1 < @2

    if @condition:
        @3 = c’

        @condition = @2 < @3

    # further chaining

    if @condition and bar():
        # Original block.

I do note the unfortunate issue of having to rewrite the entire condition, or rather, at least, the prefix of the condition if you feel fancy.

$\endgroup$
10
  • $\begingroup$ Even if the language doesn't have block expressions, it may make sense to desugar to an extended intermediate representation that does have them. $\endgroup$ Commented Apr 29 at 17:28
  • 1
    $\begingroup$ a is only evaluated once either way. Why do you include it in the list of variables that are introduced to prevent double-evaluation? $\endgroup$
    – amalloy
    Commented Apr 30 at 2:15
  • 2
    $\begingroup$ @amalloy: Because it needs to be evaluated before let b = b';, but used afterwards. $\endgroup$ Commented Apr 30 at 6:00
  • 1
    $\begingroup$ For a questioner potentially new to PL implementation, based on asking this question, I think that needed to be spelled out. Alternately, function encapsulation works fine with lazy evaluation, or pass-by-name parameters $\endgroup$ Commented Apr 30 at 14:04
  • 1
    $\begingroup$ @PhilMiller: Not convinced it's needed, to be honest.... but it doesn't take too much space so why not. $\endgroup$ Commented Apr 30 at 14:42
5
$\begingroup$

So this one depends on your operational semantics, in particular on whether your language exhibits Lazy or Eager Evaluation.
That said, please bear in mind that even in most eagerly-evaluated languages, the Boolean conjunction and disjunction operators (and and or) are exhibiting lazy evaluation.

x ∧ y sometimes mean that false ∧ (x/0) is legal and equal to false, while sometimes it is illegal.
This will become important in what follows.

Memoising And Rewriting

That one is simple enough: you just rewrite comparison chains to conjunctions or disjunctions.

x < y < z becomes x < y ∧ y < z.
Then, assuming Lazy Evaluation, this further gets lowered to force x < force y ∧ force y < force z where each term is memoised.
Assuming Eager Evaluation, the uses of force are explicitated using temporaries as so:
let x' = /*force*/ x;; y' = /*force*/ y in x' < y' ∧ y' < z.

Now, what 3 < 0 < explode() is supposed to do is up to whether Boolean conjunction is lazy or not.

Binary Comparisons Do Not Result In Booleans

That one is a bit more funky but works in existing languages and relies on the binary comparison operators returning a type that can both be turned into Booleans and be used in comparison chains.
It's simple: it holds a reference to its RHS and has the operators compare against the RHS.

Here is the approach illustrated in C++:

template<typename T>
struct ComparisonVariable
{
    const bool r;
    const T &rhs;

    operator bool() const
    {
        return r;
    }

    ComparisonVariable<T> operator <(const T &arg) const
    {
        return ComparisonVariable<T> { r && (bool) (rhs < arg), arg };
    }
};
struct Int
{
    int val;
    ComparisonVariable<Int> operator <(const Int &arg) const
    {
        return ComparisonVariable<Int> { val < arg.val, arg };
    }
};
/* ... */

extern "C" int printf(const char*, ...);
int main(int argc, char *argv[])
{
    Int x = { 1 }, y = { 2 }, z = { 3 };
    bool fst = x < y < z;
    bool snd = z < y < x;
    printf("%d %d", fst, snd);
}

x < y < z is (x.Int::operator <(y)).ComparisonVariable<Int>::operator <(z), where, as you can see, each operand only appears once.

$\endgroup$
4
$\begingroup$

You've got some good answers already but I'll just point out that I've had to do this twice, and done it in two different ways; both work.

Method one:

When I was writing a Python-to-Python compiler at Facebook we rewrote r = a() < b() < c() via the following steps:

  • Does the first operand possibly have a side effect? If no, we're done. If yes, rewrite to _a = a() ; r = _a < b() < c().

  • Does the second operand possibly have a side effect? Rewrite similarly, so now we have _a = a() ; _b = b(); r = _a < _b < c()

  • Is there more than one operator? If yes, it is now safe to rewrite the assignment as r = _a < _b and _b < c().

Method two:

C# does not have this kind of chained comparison but it has many other expressions where the specification says "... but the expression is only evaluated once". Our intermediate form after parsing but before IL generation has a pair of special nodes: one means "evaluate the referred-to expression and store it to a temp", the other means "fetch the value of the temp in the referred-to store expression". That makes the lowered form a DAG rather than a tree but that's not a big deal. The IL generator then decides whether to turn the temp into an unnamed local or a dup instruction or whatever.

Both work. In the first case I was already writing a Python-to-Python compiler so it made sense to do the lowering entirely in Python, in the second case it was just easier to have a custom intermediate format that we could special-case later; do whatever works best for your application.

$\endgroup$
1
$\begingroup$

You can translate it to

(a < (temp_b := b)) and (temp_b < c)

before code generation. temp_b should be a unique identifier generated by the compiler. Repeat this replacement for each step in the chained comparisons.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .