<div class="gmail_extra">[how do you tell gmail about the "mailing list" concept, so that it will default to "reply to list", rather than "reply to sender"?...]<br><br>I've been considering how to implement this ["?=" / better codegen for guards] without disturbing things too much - in particular, without making changes to Core Erlang.<br>
<div class="gmail_quote"><div class="gmail_extra">I believe that I can argue that the desired extentions simply cannot in general be represented with Core Erlang (at least not without duplicating code or tests).<br>
<br>These examples may not be minimal, but should illustrate that there is a problem:<br> a) receive T when element(1,T) ?= <<1,_>> -> ... end<br>
b) receive T when L ?= tuple_size(T), element(1,T) ?= <<D:L>> -> D end<br>These don't even include 'orelse'.<br><br>a) is quite simple, but could be fixed with appropriate new guard BIFs for binaries. Lacking such BIFs, there is a problem even without guard->body bindings.<br>
<br><div class="gmail_quote">Den 22. apr. 2012 00.32 skrev Robert Virding <span dir="ltr"><<a href="mailto:rvirding@gmail.com" target="_blank">rvirding@gmail.com</a>></span>:<div class="im"><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
The actual pattern match compiler does a pretty straight forward<br>
compilation of guards. It the optimiser which does some very weird<br>
things and seems pretty incomprehensible.</blockquote></div><div>Yes... only after dumping intermediate representations did I realize that it wasn't a half-baked attempt to improve handling of "andalso" and "orelse" in guards that caused the weird beam code. Rather, it's the peep-hole optimizer which does quite a bit work to make the code look good (and normally succeeds, except that it isn't optimized for handling guards).<br>
<br></div><div class="im"><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> One though I had when doing<br>
the pattern match compiler was whether we could instead move patterns<br>
in the head explicitly into the guard, have everything there, and work<br>
on that. That would optimise things like type tests in the guard. And<br>
in the case variable binding. There was a paper describing this but I<br>
can't remember it's name or author.<br></blockquote></div><div>A "Core Erlang 2" which relied on "if" rather than "case" as the central
branching construct, would certainly ensure that guards are treated no
worse than patterns.<br>I don't know how variable bindings would be handled most elegantly in that setting, but surely it can be done.<br><br>That would be quite a disruptive change, however. Changing just #c_clause{} might be a more realistic approach. My previous suggestion for that should be modified, though, to allow for bindings in 'orelse'.<br>
<br><br></div><div class="im"><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
I would personally like to have variable binding in the guards. I have<br>
a current use for it, so hurry up. :-)<br></blockquote></div><div>Doing the best I can in my spare time :-)<br>For the moment, we need a plan which is both general enough, sufficiently simple to implement, and palatable to the OTP team...<br>
Oh, and an updated semantics spec, of course. Richard, which EEP should we continue with?<br> <br><br></div><div><div class="h5"><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<span><font color="#888888">
Robert<br>
</font></span><div><div><br>
On 19 April 2012 00:00, Erik Søe Sørensen <<a href="mailto:eriksoe@gmail.com" target="_blank">eriksoe@gmail.com</a>> wrote:<br>
> Guards seem to be given a rather stepmotherly treatment in the compiler...<br>
> whether any decent code is generated appear to be entirely up to the mercy<br>
> of the peephole optimizer. That's worse than I'd imagined.<br>
><br>
> For instance,<br>
> g3(X) when X=:=foo orelse<br>
> X=:=bar orelse<br>
> X=:=baz -> ok.<br>
> generates the rather asymmetric<br>
><br>
> {select_val,{x,0},{f,11},{list,[{atom,foo},{f,12},{atom,bar},{f,12}]}}.<br>
> {label,11}.<br>
> {test,is_eq_exact,{f,9},[{x,0},{atom,baz}]}.<br>
> {label,12}.<br>
> {move,{atom,ok},{x,0}}.<br>
> return.<br>
><br>
> And worse, in some cases like<br>
> h(X,Y) when (X=:=a andalso Y>0) -> aa;<br>
> h(X,Y) when (X=:=b andalso Y>0) -> bb;<br>
> h(X,Y) when (X=:=c andalso Y>0) -> cc.<br>
> the size of the generated code is quadratic in the size of the source code:<br>
> {select_val,{x,0},<br>
> {f,29},<br>
> {list,[{atom,a},{f,31},{atom,b},{f,33},{atom,c},{f,35}]}}.<br>
> {label,31}.<br>
> {test,is_lt,{f,32},[{integer,0},{x,1}]}.<br>
> {move,{atom,aa},{x,0}}.<br>
> return.<br>
> {label,32}.<br>
> {select_val,{x,0},{f,29},{list,[{atom,b},{f,33},{atom,c},{f,35}]}}.<br>
> {label,33}.<br>
> {test,is_lt,{f,34},[{integer,0},{x,1}]}.<br>
> {move,{atom,bb},{x,0}}.<br>
> return.<br>
> {label,34}.<br>
> {test,is_eq_exact,{f,29},[{x,0},{atom,c}]}.<br>
> {label,35}.<br>
> {test,is_lt,{f,29},[{integer,0},{x,1}]}.<br>
> {move,{atom,cc},{x,0}}.<br>
> return.<br>
> (Notice the tables in the select_val instructions.)<br>
><br>
> This bad behaviour happens after the transition to beam code (in<br>
> beam_dead:combine_eqs(), afaict).<br>
> Looks like guards really would like to be taken into account during pattern<br>
> match compilation... (no offence, Dijkstra).<br>
><br>
> Anyway, the first roadblock appears to be that at the time when match<br>
> compilation occurs (at the core->kernel representation transition), guards<br>
> have already been flattened, meaning that what was at guard top-level in the<br>
> source code is more difficult to find.<br>
> For this reason, I'm considering a representation change of Core's clauses -<br>
> from<br>
> -record(c_clause, {anno=[], pats, % pats :: [Tree],<br>
> guard, % guard :: Tree,<br>
> body}). % body :: Tree<br>
> to<br>
> -record(c_clause, {anno=[], pats,<br>
> guard_pats :: [{Tree, Tree}], % {ExprToTest, Pattern}<br>
> guard_exp :: Tree,<br>
> body}).<br>
> such that the guard is split into a part that can integrated into the<br>
> pattern matching step, and a remainder that can't.<br>
> For instance, the guard "when Y > 0, element(1,X) =:= foo" would be<br>
> represented as<br>
> guard_pats = [{E1, P1}], guard_exp=E2<br>
> where E1 = repr. of "element(1,X)", P1 = repr. of "'foo'", and E2 = repr. of<br>
> "Y > 0".<br>
><br>
> Handling "P ?= E" at guard top level would then follow quite naturally: by<br>
> including {E,P} in guard_pats.<br>
> (As for scoping, it is handled in an earlier phase.)<br>
> Integrating type tests need a bit more, but that can be left for later if<br>
> necessary.<br>
><br>
> /Erik<br>
><br>
> Den 18. apr. 2012 14.54 skrev Erik Søe Sørensen <<a href="mailto:eriksoe@gmail.com" target="_blank">eriksoe@gmail.com</a>>:<br>
> [snip]<br>
><br>
>> Handling 'orelse' might be tricky, though; the current approach for ';'<br>
>> appears to be to simply duplicate the clause and let a downstream optimizer<br>
>> recognize the duplication, so I suppose that will work for 'orelse' as well.<br>
>> (Looking at generated code, I notice that 'orelse' and 'andalso' in guards<br>
>> gives rise (in R14B03) to some surprising - and suboptimal - code.)<br>
><br>
><br>
><br>
><br>
</div></div><div><div>> _______________________________________________<br>
> eeps mailing list<br>
> <a href="mailto:eeps@erlang.org" target="_blank">eeps@erlang.org</a><br>
> <a href="http://erlang.org/mailman/listinfo/eeps" target="_blank">http://erlang.org/mailman/listinfo/eeps</a><br>
><br>
</div></div></blockquote></div></div></div><br></div>
</div><br></div>