Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Lifting mechanism causes difficulties with avoiding redecoration #140

Open
krame505 opened this issue Mar 1, 2019 · 0 comments
Open

Lifting mechanism causes difficulties with avoiding redecoration #140

krame505 opened this issue Mar 1, 2019 · 0 comments

Comments

@krame505
Copy link
Member

krame505 commented Mar 1, 2019

This is an interesting case that Ted and I were discussing yesterday, and actually turned out to be a bug with the optimization I made to the algebraic data type extension to avoid redecorating the RHSs of match expressions.

Essentially, a match expression forwards to something of the form

({/*RHS_type*/ _match_result;
  {
    // pattern 1 variable decls
    if (/*pattern_1_matches*/) {
      _match_result = /*pattern_1_RHS*/;
      goto end;
    }
  }
  // ... other patterns ...
  printf("match failure\n");
  exit(1);
  end:
  _match_result;})

In order to compute RHS_type in the forward (and to perform error checking), we need to decorate the RHSs of each pattern. To avoid re-doing this decoration in the forward (and causing a potentially exponential performance hit) we can wrap up these expressions with decExpr, if they are to receive effectively the same environment in the forward as when they are initially decorated. This is mostly true since they recieve all the same pattern variable defs as before, and _match_result isn't referenced in any of these expressions.

However there is a problem: Due to the existence of the lifting mechanism, the type expression for RHS_type can lift definitions that otherwise would have been lifted by one of the RHS expressions! This can happen if, for instance, the RHS of a pattern contains the first occurrence of a type template instantiation, so the type expression for RHS_type in the forward would end up as the first occurence of that type, thus causing the template instantiation to be repeated. In addition to being a performance problem, this would result in the instantiation declaration being duplicated in the host tree.

A solution to this that I have been testing is to introduce a new form of type expression wrapping a type, producing no definitions, that is not translated back to an actual type expression until lifting takes place. This type expression (known as completedTypeExpr since the type will be completed later) can be used in a forward in the case when the expression from which the type originates (guaranteed to also lift any corresponding declarations needed for the type) is used after a declaration in which the type is required.

completedTypeExpr also has a corresponding type, completedType, which wraps the actual type and is translated back to a corresponding completedTypeExpr. Since the completedType exists in places where the corresponding definitions don't yet exist in the environment, error checking in the host language should handle completedType in the same way as error type. However this will never cause any errors to be missed, as completedType only should occur in forward trees, and extension productions that introduce completedType should fully error-check their children prior to forwarding.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant