<div dir="ltr">One concern I have with implementing this through pattern matching is that it might make it really hard to optimize. For example, consider the following hypothetical fragment:<div><br></div><div><div>switch string {</div><div> case "x" (let remainder):</div><div> return arc4random() % 2 == 0 ? parse1() : parse2() </div></div><div><br></div><div>This would parse a string starting with x, and then continue parsing with either parse1 or parse2. </div><div><br></div><div>This is strictly more powerful (it allows you to implement parsers that are "dynamically" constructed depending on the input), and therefore less optimizable.</div><div><br></div><div>However, IANACE (I am not a compiler engineer), so hopefully my pessimism is unjust.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jan 25, 2017 at 7:23 PM, Joe Groff <span dir="ltr"><<a href="mailto:jgroff@apple.com" target="_blank">jgroff@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><span class=""><br><div><blockquote type="cite"><div>On Jan 24, 2017, at 9:35 PM, Chris Lattner via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</div><br class="m_5206423776705715240Apple-interchange-newline"><div><div style="word-wrap:break-word">On Jan 24, 2017, at 12:05 AM, Chris Eidhof via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:<br><div><blockquote type="cite"><br class="m_5206423776705715240Apple-interchange-newline"><div><div dir="ltr">I agree that being able to implement parsers in a nice way can be a huge step forward in being really good at string processing.</div></div></blockquote><div><br></div><div>+1 from me as well, I agree with Joe that Swift can learn a lot from Perl 6 grammar’s and we should take the time to do it right. Below I say “regex” a lot, but I really mean a more general grammar system (and even Perl 5 regex’s aren’t regular :-)</div><br><blockquote type="cite"><div><div dir="ltr"><div>There are a couple of possibilities that come to mind directly:</div><div><br></div><div>1. Build parsers right into the language (like Perl 6 grammars)</div><div>2. Provide a parser combinator language (e.g. <a href="https://github.com/davedufresne/SwiftParsec" target="_blank">https://github.com/<wbr>davedufresne/SwiftParsec</a>). </div><div>3. Rely on external tools like bison/yacc/etc.</div><div>4. Make it easy for people to write hand-written parsers (e.g. by providing an NSScanner alternative).</div></div></div></blockquote></div><div><br></div><div>My opinion is that #1 is the right path to start with, but it wouldn’t preclude doing #2. Here’s my rationale / half-baked thought process:</div><div><br></div><div>There are two important use cases for regex's: the literal case (e.g. /aa+b*/) and the dynamically computed case. The former is really what we’re talking about here, the latter should obviously be handled with some sort of Regex type which can be formed from string values or whatever. Regex literals in an expression context should default to producing the Regex type of course.</div><div><br></div><div>This means that when you pass a regex literal into an API call (e.g. split on a string), it is really just creating something of Regex type, and passing it down. If you wanted to introduce a parser combinator DSL, you could totally plug it into the system, by having the combinators produce something of the Regex type.</div><div><br></div><div>So why bless regex literals with language support at all? I see several reasons:</div><div><br></div><div>1. Diagnostics: These will be heavily used by people, and you want to have good compiler error and warning messages for them. You want to be able to validate the regex at compile time, not wait until runtime to detect syntactic mistakes like unbalanced parens.</div><div><br></div><div>2. Syntax Familiarity: To take advantage of people’s familiarity with other languages, we should strive to make the basic regex syntax familiar and obvious. I’d argue that /aa+b*/ should “just work” and do the thing you think it does. Relying on a combinator library to do that would be crazy.</div><div><br></div><div>3. Performance: Many regex’s are actually regular, so they can be trivially compiled into DFAs. There is a well understood body of work that can be simply dropped into the compiler to do this. Regex’s that are not regular can be compiled into hybrid DFA/NFA+backtracking schemes, and allowing a divide and conquer style of compiler optimization to do this is the path that makes the most sense (to me at least). Further, if you switch on a string and have a bunch of cases that are regex’s, you’d obviously want the compiler to generate a single state machine (like a lexer), not check each pattern in series.</div><div><br></div><div>4. Pattern matching greatness: One of the most obnoxious/error prone aspects of regex’s in many languages is that when you match a pattern, the various matches are dumped into numbered result values (often by the order of the parens in the pattern). This is totally barbaric: it begs for off by one errors, often breaks as the program is being evolved/maintained, etc. It is just as bad as printf/scanf! </div><div><br></div><div>You should instead be able to directly bind subexpressions into local variables. For example if you were trying to match something like “42: Chris”, you should be able to use straw man syntax like this:</div><div><br></div><div> case /(let id: \d+): (let name: \w+)/: print(id); print(name)</div><div><br></div><div>Unless we were willing to dramatically expand how patterns work, this requires baking support into the language.</div><div><br></div><div>5. Scanner/“Formatter" integration: Taking the above one step farther, we could have default patterns for known types (and make it extensible to user defined types of course). For example, \d+ is the obvious pattern for integers, so you should be able to write the above like this (in principle):</div><div><br></div><div><div> case /(let id: Int): (let name: \w+)/: print(id); print(name)</div><div><br></div><div>In addition to avoiding having to specify \d+ all the time, this eliminates the need for a “string to int” conversion after the pattern is matched, because id would be bound as type Int already.</div><div><br></div></div><div><br></div><div>Anyway, to summarize, I think that getting regex’s into the language is really important and expect them to be widely used. As such, I think it is worth burning compiler/language complexity to make them be truly great in Swift.</div></div></div></blockquote><br></div></span><div>Another good reason to bake them into pattern matching is that it would make it easier to optimize when you want to match one of multiple patterns. Often, you don't want just one grammar, but possibly one of many, and it'd be nice if switch-ing over multiple string patterns led to a reasonably efficient DFA/NFA/rec-descent machine based on the needs of the grammars being matched.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>-Joe</div><br></font></span></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">Chris Eidhof</div>
</div>