A recursive let causes any matching to unbound variables to fail.

Here's an example. Note that variable x is unbound, but the match fails and therefore the whole strategy fails. Removing the offending line causes the strategy to succeed, and return 15.

example =
  let lambda =
      ?x ;      // <- Offending line
      if <eq> (0, <id>) then !0 else
        <add> (<id>, <subt ; lambda> (<id>, 1))
      end
  in <lambda> 5
  end

This bug happens only when the let is recursive (so it gets its own strategy and is not optimized away). The variable x is clearly an unbound variable, but the match fails.


The generated Java code shows why the match causes the strategy to fail. The let is represented as its own strategy u_19 that has fields for any captured variables. A match will fail if x is bound and not equal to the matched term. In this case, we would expect x to be unbound, and therefore the match should always succeed.

final class u_19 extends Strategy 
{ 
  TermReference x;

  public IStrategoTerm invoke(Context context, IStrategoTerm term)
  { 
    ITermFactory termFactory = context.getFactory();
    Fail22:
    { 
      if(x.value == null)
        x.value = term;
      else
        if(x.value != term && !x.value.match(term))
          break Fail22;
      // ...
    }
    return null;
  }

But here's the generated Java code for the example strategy. It binds x in the let to a TermReference. Since x is no longer an unbound variable, the match fails.

public class example_0_0 extends Strategy 
{ 
  public static example_0_0 instance = new example_0_0();

  public IStrategoTerm invoke(Context context, IStrategoTerm term)
  { 
    context.push("example_0_0");
    Fail21:
    { 
      TermReference x = new TermReference();
      // ...
      u_19 u_190 = new u_19();
      u_190.x = x;
      term = u_190.invoke(context, term);
      if(term == null)
        break Fail21;
      // ...
    }
    context.popOnFailure();
    return null;
  }
}
Submitted by D. Pelsmaeker on 7 May 2015 at 13:20

Log in to post comments