这个单子解析器是否引起了空间泄漏?

huangapple go评论64阅读模式
英文:

Does this monadic parser cause space leaks?

问题

I was reading the arrow tutorial.
https://en.wikibooks.org/wiki/Haskell/Understanding_arrows#Avoiding_leaks.
And I got confused reading this part

solfege :: Parser Char String
solfege = string "Do" <|> string "Re" <|> string "Mi"

Through this last example, we can indicate which issue Swierstra and Duponcheel were trying to tackle. When solfege is run on the string "Fa", we can't detect the parser will fail until all of the three alternatives have failed. If we had more complex parsers in which one of the alternatives might fail only after attempting to consume a lot of the input stream, we would have to descend down the chain of parsers in the very same way. All of the input that can possibly be consumed by later parsers must be retained in memory in case one of them happens to be able to consume it. That can lead to much more space usage than you would naively expect − a situation often called a space leak.

I don't understand that solfege has risk of causing space leaks. Every alternative in solfege(string "Do", string "Re", and string "Mi") fails on the comparison with 'F', the first character of "Fa". If these alternatives consume more than one character and fail, then I can accept that solfege causes space leaks. However, that's only possible when string's implementation is dumb. Also, it's hard for me to imagine a monadic parser that fails late after consuming unnecessary tokens, unless it's poorly written on purpose.

Am I missing something in the article?

英文:

I was reading the arrow tutorial.
https://en.wikibooks.org/wiki/Haskell/Understanding_arrows#Avoiding_leaks.
And I got confused reading this part

solfege :: Parser Char String
solfege = string &quot;Do&quot; &lt;|&gt; string &quot;Re&quot; &lt;|&gt; string &quot;Mi&quot;

> Through this last example, we can indicate which issue Swierstra and Duponcheel were trying to tackle. When solfege is run on the string "Fa", we can't detect the parser will fail until all of the three alternatives have failed. If we had more complex parsers in which one of the alternatives might fail only after attempting to consume a lot of the input stream, we would have to descend down the chain of parsers in the very same way. All of the input that can possibly be consumed by later parsers must be retained in memory in case one of them happens to be able to consume it. That can lead to much more space usage than you would naively expect − a situation often called a space leak.

I don't understand that solfege has risk of causing space leaks. Every alternative in solfege(string &quot;Do&quot;, string &quot;Re&quot;, and string &quot;Mi&quot;) fails on the comparison with 'F', the first character of "Fa". If these alternatives consume more than one character and fail, then I can accept that solfege causes space leaks. However, that's only possible when string's implementation is dumb. Also, it's hard for me to imagine a monadic parser that fails late after consuming unnecessary tokens, unless it's poorly written on purpose.

Am I missing something in the article?

答案1

得分: 1

"你可能忽略了关键部分,就是这一段:

> 如果我们有更复杂的解析器,其中其中一个备选方案只有在尝试消耗大量输入流后才可能失败...

因此,string &quot;Do&quot; 不是要字面理解,而是代表一个执行更多工作并可能需要在输入中任意远的地方查看以确定是否应该失败的解析器。"

英文:

The key part that you probably glossed over is this bit:

> If we had more complex parsers in which one of the alternatives might fail only after attempting to consume a lot of the input stream, ...

So, string &quot;Do&quot; is not meant to be taken literally, but as standing in for a parser that does more work and may have to look arbitrarily far ahead in the input to know whether it should fail or not.

huangapple
  • 本文由 发表于 2023年4月11日 00:12:08
  • 转载请务必保留本文链接:https://go.coder-hub.com/75978730.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定