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

Understanding the type system for brs #677

Closed
kripken opened this issue Apr 29, 2016 · 28 comments
Closed

Understanding the type system for brs #677

kripken opened this issue Apr 29, 2016 · 28 comments
Milestone

Comments

@kripken
Copy link
Member

kripken commented Apr 29, 2016

I can't figure out why these three should pass (all from spec test suite):

(module (func              (block $l (br $l (i32.const 1)))))

(module (func (result i32) (block $l (br $l (i32.const 1)))))

(assert_invalid
  (module (func (result f32) (block $l (br_if $l (f32.const 0) (i32.const 1)))))
  "type mismatch"
)

Is there documentation for the type system somewhere that I should read, that would explain why the last is bad but not the first two? Basically, documentation for the types of brs in particular?

I've mostly just looked at the spec tests and gotten things working, but I'm trying to enable complete validation testing in binaryen, and I see failures that suggest I have no idea how this type system actually works :)

@ghost
Copy link

ghost commented Apr 29, 2016

For the first two, consider their equivalent simplifications which are valid. The consumer is not expecting values so the excess are discarded.

(func (block $l (br $l (i32.const 1)))) == (func (i32.const1))

(func (result i32) (block $l (br $l (i32.const 1)))) == (func (result i32) (i32.const 1))

Correction: The last case is invalid because the fall-through value is empty but a single value is expected.

(func (result f32) (block $l (br_if $l (f32.const 0) (i32.const 1)))) == (func (result f32) (nop))

I demonstrated the multiple-value type system in WebAssembly/wabt#66 and proved it fits a single pass compiler, and the break operators accept a single argument expression. If you want to understand how the current type system could extrapolate to multiple value then this might help.

It might be a little confusing that an arity count has just been added to the very common break operators. I argued against it. Go figure.

I no longer think it is productive to explore these issues. There is discussion of removing the void type, in which case no value could be implicitly discarded, and the issue goes away. An expressionless encoding would achieve the same.

@kripken
Copy link
Member Author

kripken commented Apr 29, 2016

Sorry, that just makes me more confused. What is a "simplification"? Is it just to explain the concept, or is that how a checker would actually work?

All I'm looking for here is the concrete rules of how I assign a type to br, br_if, br_table and block, and what are the error conditions there. For example, the type of i32.const is clearly i32 - I just want simple rules for those other nodes. Or are there no simple rules?

@ghost
Copy link

ghost commented Apr 29, 2016

unreachable - type none
nop - type void
br - type none
br_if - type void
br_table - type none
block - parametric, so a union of the type of all the break and fall-through expressions. If all are type none then the result type is none, otherwise ignore any with type none (it's the empty set). Otherwise if all are type void then the result is type void. Otherwise if at least one type is void and at least one type is i32 i64 f32 or f64 then the result is type optional which is invalid to consume where a value is expected and the number of values is not fixed, but ok if no value is consumed. Otherwise if the types differ then the result is type union which is invalid to consume where a value is expected but the number of values is known and it is ok when no value is consumed. Otherwise the types are the same and one of i32, i64, f32, f64.

@kripken
Copy link
Member Author

kripken commented Apr 29, 2016

Thanks!

This looks fairly complex - I'm not surprised that I couldn't figure it out just by reading the tests ;)

How did we arrive at this system - where was the design discussed? I see no mention of a none type, nor a void type anywhere in the design repo. (I guess it's implemented in the spec repo as part of the ml proto, but it's hard (for me at least) to know what is actually part of the spec and what is an implementation detail.)

@ghost
Copy link

ghost commented Apr 29, 2016

@kripken The spec is defined in terms of a top down type system so does not need to even reference the type none as unreachable code just does not check the expected type. The spec might refer to the void type above as none, or have I mixed them up, I was trying to use the SM naming. You might be able to substitute the void type for the union and optional types, and that would simplify it somewhat. The union type helps with expressions of more than one value where only some are consumed, and the optional type is need if the case of a fixed number of values of different types is needed.

@rossberg
Copy link
Member

rossberg commented Apr 29, 2016

A couple of clarifications and corrections:

  • The type system has no direction; it simply defines constraints on the relation between types of some expressions.
  • Expressions types are of the form value_type?, and "void" is just shorthand for the empty case (written None in ml-proto, because its an option type).
  • There is no other type, as far as the type system is concerned.

The most interesting ones of those constraints are:

  • The type of nop is void.
  • The type of block has to be the same as the type of its last expression.
  • The type of an unconditional control transfer (br, br_table, return, unreachable) is unconstrained.
  • The type of br_if is void.
  • The type of the optional argument to a br* has to be a suptype of the type of the targeted block.

A type T is a subtype of U if and only if T = U, or U is void.

Note in particular that the result type of br_if is void, because it does not produce a value in the false case. That is different from br, which can be unconstrained (i.e., polymorphic), because it is statically known to never return to its surrounding expression. (The difference perhaps becomes more obvious when you expand br_if to its real meaning, which is an if with a nop in one of its branches).

As for your original question: the block in your third example has to have type f32, because that's the result type of the function. The type of its last expression, br_if is void, however. Not so in the other two examples, where the br's can be given type f32, because they're polymorphic.

@kripken
Copy link
Member Author

kripken commented Apr 29, 2016

@rossberg-chromium I think I'm still confused. So

  1. blocks are simple, they always have the type of their last expression, and
  2. It is brs that are complex, since they have what you call "unconstrained" type.

Hence if a block has a br as its last expression, by 1 the type of that br must be the type of the block? But how do we tell the type of the block? I can see two options:

a. look at brs with a value that go to that block, or
b. look at where the block flows to, and see what type is expected there

?

I guess it has to be a since the block return value might be ignored?

I may still be missing something big here, but a second question: It seems like the above rules imply that the type of a node can change if it is moved around - e.g. the exact same br might have a different type if it's not at the end of a block (or it might change based on other brs changing), all of that due to the 1 and 2 from before. Is this the case? If so then a node doesn't have a type by itself, it only has a type due to its relations to other nodes.?

@rossberg
Copy link
Member

[Reposting, because Github garbled the quotes badly, and editing can't fix it?]

@rossberg-chromium https://github.com/rossberg-chromium I think I'm
still confused. So

  1. blocks are simple, they always have the type of their last
    expression, and
  2. It is brs that are complex, since they have what you call
    "unconstrained" type.

Well, unconstrained means that there is nothing to check. Is that more
complex? :)

Hence if a block has a br as its last expression, by 1 the type of that br
must be the type of the block? But how do we tell the type of the block?
I can see two options:

a. look at brs with a value that go to that block, or
b. look at where the block flows to, and see what type is expected there

?

I guess it has to be a since the block return value might be ignored?

Now you are asking about an algorithm. Technically, a type system is not,
by itself, the definition of an algorithm. It just imposes a set of
constraints.

There are various algorithmic ways to check these constraints, but
fortunately it's fairly simple for Wasm. Two recursive approaches we have
been discussing in the past (there are others) are top-down vs bottom up
(IIUC, corresponding to your b and a, respectively):

  • With the current type system, top down is actually very straightforward:
    you always know what type is expected from a (sub)expression, so you can
    just make that an input to the recursive algorithm, and check against it.
    Breaks are trivial in that case, because you already know the type of the
    targeted block. Checks are modulo subtyping, which is all it takes to deal
    with ignored values (i.e., for subexpressions whose value is ignored you
    pass in void, which is matched by anything).
  • However, if you want to check in one pass with decoding, then the
    post-order format necessitates a bottom-up approach, where the type is an
    output of the recursive algorithm. In addition, the algorithm must record
    the types of all local uses of labels, and once it gets up to a
    corresponding block, check that they are all consistent (in the current
    system, compute their least upper bound, and that of the last expression,
    and make the result the type of the block).

I may still be missing something big here, but a second question: It seems
like the above rules imply that the type of a node can change if it is
moved around
- e.g. the exact same br might have a different type if
it's not at the end of a block (or it might change based on other brs
changing), all of that due to the 1 and 2 from before. Is this the case? If
so then a node doesn't have a type by itself, it only has a type due to its
relations to other nodes.?

Yes. That is the nature of any form of type polymorphism (parametric,
subtyping, or other). However, there typically is the notion of
a principal type for any given expression that subsumes all
possibilities. Depending on what forms of polymorphism a language has,
there are different ways to express that. For Wasm, you could e.g.
introduce type variables as placeholders for (yet) unconstrained types.

@kripken
Copy link
Member Author

kripken commented Apr 29, 2016

In addition, the algorithm must record
the types of all local uses of labels, and once it gets up to a
corresponding block, check that they are all consistent (in the current
system, compute their least upper bound, and that of the last expression,
and make the result the type of the block).

Ok, thanks, I think I get it now.

Yes. That is the nature of any form of type polymorphism (parametric,
subtyping, or other).

But is that complexity necessary here? Instead of

  1. blocks have the type of their last expression, and
  2. brs have unconstrained type, so we figure it out depending on usage (e.g. if at the end of a block, we find the block type from the block's brs, then give it to that last br in the block; and then the block has the type of its last expression as required in 1).

We could instead have

a. blocks have the type of the values that brs to them have, or if they have none, that of their last expression, and
b. brs always have the empty type.

By not requiring that blocks have the type of their last expression, we can let brs always have the empty type. So a br at the end of a block has the empty type, and also if there were something after it in that block (it wasn't the last anymore) it would still have the empty type. In other words, we trivially know the type of a br, and we also know it won't change if we move it around.

I believe these two are equivalent in practice, I think the only difference is the internal type of the br.

@rossberg
Copy link
Member

Not sure I understand. A block has to yield a consistent type, no matter how it's exited. So the value from its final expression must have the same type as any associated break argument. Something like

(i32.neg (block $l (if (cond) (br $l (i32.const 1)) (nop)))

cannot possibly be allowed.

Also, the last expression does not affect type checking complexity. Either way, you have to check that all associated break arguments are consistent, the last value is just one more expression to consider (and any (block $l ... (x)) can be treated as (block $l ... (br $l (x)))).

The only alternative to the current design would be to remove break arguments entirely, and require all blocks that are targeted by a break to have type void. Not entirely unreasonable, but a somewhat sad limitation for an expression language.

@kripken
Copy link
Member Author

kripken commented Apr 29, 2016

Perhaps I wasn't clear enough, sorry. In 1-2 and a-b I wasn't specifying all the validation. I was specifying how the type can be determined, assuming correctness. Full validation needs a tiny bit more work. Specifically, 1-2 also require

3: all breaks to the block have the same value type (but tolerate inconsistency if it is not consumed; see bottom of this post)

and a-b also require

c: all breaks to the block have the same value type, and also the last element in the block must have the same type

As a result, your example that should fail to validate does in fact fail to validate in a-c. (I think: your example has 7 open parens, but only 6 closing, so maybe it's missing one in a way that I guessed wrongly.)

The issue here isn't complexity in the sense of how much work needs to be done. It's how hard it is to understand the type system. Obviously subjective. But in yours, the type of brs depends on their location. In mine, the type of brs is trivial and fixed.

And there is additional complexity for blocks as well that feels unnecessary. Consider these two examples:

(module (func $br_if-drop1 (block (br_if 0 (i32.const 1) (i32.const 1)))))

(module (func $br_if-drop2 (result i32) (block (br_if 0 (i32.const 1) (i32.const 1)))))

(only difference is adding a result in the second)

In your type system, the second fails. In mine, both fail. I claim that this is less complex, as in mine, whether a block is valid or not does not depend on the block's location. You can move the block around, it doesn't matter. And these examples, shouldn't both fail? We have here a block with a branch of an i32, so the presumed type should be i32; however, br_if is an instruction that may not branch, and if it does not, we are returning a nop, in effect. That's clearly wrong, isn't it?

Or is there some value to allowing it to validate, and only fail lazily if the wrongness is used?

The only alternative to the current design would be to remove break arguments entirely

I certainly hope not! :) I think there is an alternative, as described above. Unless I missed something...

@binji
Copy link
Member

binji commented Apr 29, 2016

@kripken Right, you're describing something similar to what @jcbeyler brought up here: WebAssembly/spec#179. Then the type checking was tightened here: WebAssembly/spec#180. Then after much discussion was loosened here: WebAssembly/spec#271.

From the last link:

Motivation: not allowing optional operands to be implicitly dropped (1) reduced the compositionality of the language, (2) made it harder to allow multiple targets (like with a br_if also returning its operand), and (3) put an extra burden on bottom-up type checkers, where the arity might not be known upfront. And with multiple value, we eventually would want to lift this restriction again anyway.

(this space so the quote above doesn't get merged with the quote below)

whether a block is valid or not does not depend on the block's location

I don't think that's the right way to think of it. (block (br_if 0 (i32.const 1) (i32.const 1))) always has the void type, just as i32.const always has the i32 type. Neither is valid or invalid in isolation.

And these examples, shouldn't both fail? We have here a block with a branch of an i32, so the presumed type should be i32; however, br_if is an instruction that may not branch, and if it does not, we are returning a nop, in effect. That's clearly wrong, isn't it?

No, since there is a control flow path that returns no value (the br_if condition is false), then the optional br_if value operand must be discarded. There is an alternative discussed here where the value would flow through in the false case too.

@rossberg
Copy link
Member

Okay, I believe your suggestion boils down to whether we allow implicit dropping for break arguments. That is indeed the very issue that @binji linked to.

FWIW, Luke and I have recently discussed introducing an explicit drop operator and removing all implicit dropping from the type system. That would slightly simplify this aspect (at least declaratively; ironically, I found out the other day that it actually makes the type checking algorithm somewhat more complicated, exactly because it has to check more).

@ghost
Copy link

ghost commented Apr 29, 2016

@rossberg-chromium A block does not have 'to yield a consistent type, no matter how it's exited'. It could yield no values (void), one value (i32,i64,f32,f64), two values or more, and the None type, all on different exit paths and so long as the value(s) are not consumed it could work just fine for wasm. The constraint in wasm could be that only a single consistent type i32,i64,f32,f64 can be consumed either as a single value type. All the exit paths from a block can be handled in the same manner by the type system, and the fall-through and break expression do not have to be handled differently. This is proven by demonstration WebAssembly/wabt#66 and the type checking was not complex and perhaps a page or two of code. Happy to work through this with anyone wanting to understand the perspective, but I now suggest an expressionless encoding which has a much simpler type system and there is no need to reason about void or none types rather just single value i32, i64, f32 and f64 types. Perhaps drop is not simplifying the type system because it is not an atomic part of operators, and if so then this might be more rationale for the expressionless encoding.

@kripken
Copy link
Member Author

kripken commented Apr 29, 2016

@binji: thanks for the links! Ok, it sounds like this issue is documented in various issues in the spec repo? I'll try to read all of those. (However, it's a lot to read. As in the first part of this issue, I think it would be valuable to have a single summary of the type system somewhere.)

I totally understand if you guys don't want to discuss this with me further until I read all those issues in depth, so I guess we can close this.

But after a first read through them, I don't see where what I and @jcbeyler suggested reduced compositionality in an important way? A direct example would be helpful. Is it one of the many new tests added in that last PR? I'm not sure what to look for. For example, in the following quote is something that the proposal would indeed make no longer validate, yet it's clearly not helpful that it does validate? To not validate it would lose nothing of value.

I don't think that's the right way to think of it. (block (br_if 0 (i32.const 1) (i32.const 1))) always has the void type, just as i32.const always has the i32 type. Neither is valid or invalid in isolation.

But what does it mean for that block to have void type? I am arguing that block should not be valid at all. It's a logical impossibility, it can flow out either an i32 or a nothing. Why should we wait to see if it's used to give an error is what I'm asking.

@ghost
Copy link

ghost commented Apr 29, 2016

@kripken For the example in question, and noting that the constant condition is not seen by the type system, the block can return type i32 or void so the precise result type of the block is (or (values i32) (values)). What is being suggested is that this is effectively the same as type void as it is invalid to consume their result type, but if some operator depended on knowing the number of values then this simplification would no longer be valid as void is zero values not zero-or-one value. In the type system demonstrated in WebAssembly/wabt#66 this type is simplified to (values optional) which allows the compiler to also reason that the number of values is not consistent.

@kripken
Copy link
Member Author

kripken commented Apr 29, 2016

@JSStats: What I am saying is that allowing a block to have a type that is the union of i32 and void is not useful, and should already be an error. That way the error occurs on the block - where the error is - instead of being checked lazily only if actually used. As a bonus, the type system doesn't even need unions.

Unless there is a useful use of them, but I don't see one yet.

@ghost
Copy link

ghost commented Apr 29, 2016

@kripken It is a useful as being able to discard unused values in expression based language. The utility can be demonstrated in technical terms of encoding efficiency. e.g (block $l1 (br_if $l1 <cond>) (call_returning_i32)) versus (block $l1 (br_if $l1 <cond>) (drop (call_returning_i32))).

@rossberg
Copy link
Member

On 29 April 2016 at 23:38, JSStats notifications@github.com wrote:

@rossberg-chromium https://github.com/rossberg-chromium A block does
not have 'to yield a consistent type, no matter how it's exited'. It could
yield no values (void), one value (i32,i64,f32,f64), two values or more,
and the None type, all on different exit paths and so long as the value(s)
are not consumed it could work just fine for wasm.

No, it can't. If you want to be able to think of Wasm as a stack machine,
then all exits need to join with a consistent stack shape.

However, that does not mean that the type system does not allow the
examples you're describing. You're just holding it wrong. :) It does allow
them by constraining all break arguments to be void directly in those
cases, which they always can be, via subtyping -- that is, superfluous
values are considered immediately dropped as part of the respective break
evaluation, not later. All branches hence yield void consistently.

From the POV of a traditional evaluator that's mostly isomorphic to your
interpretation. And an implementation is of course free to implement the
checks in any equivalent way it sees fit. But keeping the stack
interpretation valid is an important design constraint. We could not allow
anything that would require union types.

@ghost
Copy link

ghost commented Apr 30, 2016

@rossberg-chromium See the demonstration at WebAssembly/wabt#66 which supports different types on all the block exits and still compiles to a stack machine in a single pass, and it balances the stack! It's been demonstrated, it works fine, it's relatively simple.

A multiple-pass runtime compiler will know before code generation that the type is a complex union and that it is not consumed, it could effectively drop all values.

Practical optimizing compilers will not be emitting code in one pass, just converting to an SSA form, and when they find complex unions just drop the definitions as it knows they are not consumed. The generated code will be every bit as good as if there were explicit drop operators, but it will be encoded more efficiently and less verbosely for the producer.

A single-pass runtime compiler might have emitted some code for some exits before it discovers that the type is a complex union and can not be validly consumed. A compiler to a stack machine just has to balance the remaining exits by dropping values or filling as necessary.

@rossberg
Copy link
Member

rossberg commented Apr 30, 2016

@JSStats, as I said, different isomorphic interpretations are possible. However, the crucial meta constraint is that the type system can only correctly support a stack machine if any use of union types is so restricted that you can still reformulate the rules without them.

@kripken
Copy link
Member Author

kripken commented Apr 30, 2016

@JSStats: Fair point, in rule (c) above it should be amended to "all brs must have the same returned value type, and if that is a concrete type, the last element in the block must match it." (Then the last element can have its value discarded if necessary.)

@rossberg-chromium: Where did this new constraint of "support a stack machine" come from?

@ghost
Copy link

ghost commented Apr 30, 2016

@kripken If 'rule (c)' is just a rule for cases in which the value can be consumed then yes. If it implies that it is invalid for any of the break values to have different types then this would not be necessary.

For example the follow could be valid so long as the result is not consumed:

(block $l1
  (br_if $l1 (call_returning_void) <cond1>)
  (br_if $l1 (call_returning_i32) <cond2>)
  (br_if $l1 (call_returning_f32) <cond3>)
  (br_if $l1 (call_returning_i32_i64) <cond4>)
  (br_if $l1 (call_returning_i64_i32) <cond5>)
  (call_returning_f64))

and could be seen as a more efficient and less verbose encoding of

(block $l1
  (br_if $l1 (call_returning_void) <cond1>)
  (br_if $l1 (drop (call_returning_i32)) <cond2>)
  (br_if $l1 (drop (call_returning_f32)) <cond3>)
  (br_if $l1 (drop_two_values (call_returning_i32_i64)) <cond4>)
  (br_if $l1 (drop_two_values (call_returning_i64_i32)) <cond5>)
  (drop (call_returning_f64)))

All the break value expressions could just be moved above the br_ifs into the block where their results would be discarded, but consider multiple value cases (i32.eqz (block $l1 (br_if $l1 (call_returning_i32_i32) <cond>) (call_returning_i32_f64))). Btw I can't see wasm ever getting multiple-value expressions, so could focus on optimizing for single value expressions, but it is not clear that that decision has been made and perhaps people are still exploring the solution space.

@kripken
Copy link
Member Author

kripken commented May 1, 2016

@JSStats: I see, thank you. Those examples helped me understand why this flexibility is useful.

@kripken
Copy link
Member Author

kripken commented May 18, 2016

I guess I still don't understand the type system for brs. A new spec test (26 in labels.wast) requires that this fail:

(func
  (block l
    (f32.neg
      (br_if l (i32.const 1))
    )
    (nop)
  )
)

Why does it fail? The output of the block is not consumed, so it's valid for it to have an invalid type, isn't it?

@rossberg
Copy link
Member

It needs to fail because the br_if has type void, so cannot be used as an argument to f32.neg.

@kripken
Copy link
Member Author

kripken commented May 18, 2016

Oh, thanks! Heh, I guess that's what I get for trying to do this at 10pm... :)

@sunfishcode sunfishcode modified the milestone: MVP Jul 8, 2016
@kripken
Copy link
Member Author

kripken commented Jul 26, 2016

This was mostly clarification, closing.

@kripken kripken closed this as completed Jul 26, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants