PatternTest 没有优化? [英] PatternTest not optimized?

问题描述

在准备对 Mathematica 中 PatternTest 的意外行为 的响应时，我遇到了一个意外的Mathematica 我自己的行为.

In preparing a response to An unexpected behavior of PatternTest in Mathematica I came across an unexpected Mathematica behavior of my own.

请考虑:

test = (Print[##]; False) &;
MatchQ[{1, 2, 3, 4, 5}, {x__?test, y__}]

During evaluation of In[1]:= 1

During evaluation of In[1]:= 1

During evaluation of In[1]:= 1

During evaluation of In[1]:= 1

False

因为，正如 Simon 在文档中的引用所言:

Since, as Simon's quote of the documentation concisely states:

在__?test这样的形式中，序列中的每个元素都与__匹配应用测试时必须产生 True.

In a form such as __?test every element in the sequence matched by __ must yield True when test is applied.

我想知道为什么 Mathematica 会分别测试列表的第一个元素四次.当然，有四种方法可以构成底层模式 {x__, y__} ，如果这是一个 Condition 测试，那么构成序列 x 的所有元素 需要进行测试，但我认为这里不是这种情况.

I am wondering why Mathematica is testing the first element of the list four separate times. Of course there are four ways to make up the underlying pattern {x__, y__} and if this were a Condition test then all elements that make up the sequence x would need to be tested, but I don't think that is the case here.

逻辑是否不认为如果列表的第一个元素失败 PatternTest 那么给定的模式不能匹配?

Does the logic not hold that if the first element of the list fails PatternTest then given pattern cannot match?

从 yoda 的回答中借用一个例子，这里是另一个似乎过度评估的例子:

Borrowing an example from yoda's answer, here is another example of what appears to be excess evaluation:

In[1]:= test2 = (Print@##; Positive@##) &;
MatchQ[{1, 2, 3, 4, -5}, {x__?test2, y__?Negative}]

During evaluation of In[1]:= 1

During evaluation of In[1]:= 1

During evaluation of In[1]:= 2

During evaluation of In[1]:= 1

During evaluation of In[1]:= 2

During evaluation of In[1]:= 3

During evaluation of In[1]:= 1

During evaluation of In[1]:= 2

During evaluation of In[1]:= 3

During evaluation of In[1]:= 4

Out[2]= True

我承认我以前从未探索过模式匹配的这个方面，而且我对这种看似低效的做法感到不安.这真的和看起来一样糟糕，还是某种自动缓存正在发生?Print 似乎表明了这一点.

I admit to having never explored this aspect of pattern matching before, and I am disturbed by the seeming inefficiency of this. Is this really as bad as it looks, or is some kind of automatic caching taking place? Print appears to indicate against that.

• 有没有更有效的基于模式的方式来写这个?

正确的模式匹配行为是否需要这种级别的冗余，为什么?

Is this level of redundancy required for correct pattern matching behavior, and why?

我匆忙做出了错误的断言，但我放弃了，因为下面的好答案解决了这个问题.请在以后的回答中忽略它.

I made a false assertion in haste, but I leave it because good answers below address it. Please ignore it in future answers.

很容易证明在其他方面也做了类似的优化案例:

It is easy to demonstrate that a similar optimization is made in other cases:

MatchQ[{-1, 2, 3, 4, 5}, {__?Positive, y__?test}]

(不打印任何内容.)

False

这里Mathematica 甚至从不为y 测试任何元素.

Here Mathematica correctly never even tests any elements for y.

推荐答案

我想每个人都忘记了测试函数中可能存在的副作用.这是我认为正在发生的事情:正如 Mr.Wizard 和其他人提到的，模式可以通过多种方式匹配，只是组合.对于 {x} 和 {y} 的每个组合，首先测试 x 模式.顺便说一句，定义多个参数的函数(##)没有意义，因为正如@Simon 解释的那样，测试函数单独应用于序列中的每个元素.这也解释了为什么只打印第一个元素 (-1):一旦找到第一个不匹配的元素，模式匹配器就会停止并继续测试下一个可用的组合.

I think everyone is forgetting about the side effects that are possible in test functions. Here is what I think is happening: as Mr.Wizard and others mentioned, there are several ways the pattern may match, just combinatorially. For each combination of {x} and {y}, the x pattern is first tested. By the way, there is no point in defining functions of multiple arguments (##), since, as @Simon explained, the test function is applied separately to each element in the sequence. And this also explains why only the first element (-1) is printed: as soon as the first non-matching element is found, the pattern-matcher stops and goes on to test the next available combination.

这是一个更能说明问题的例子:

Here is a more illustrative example:

In[20]:= 
MatchQ[{-1,2,3,4,5},{_,x__?(Function[Print[#];Positive[#]])}]
During evaluation of In[20]:= 2
During evaluation of In[20]:= 3
During evaluation of In[20]:= 4
During evaluation of In[20]:= 5

Out[20]= True

现在它打印所有这些，因为函数被一个一个地应用于它们，在这种情况下它必须这样做.

Now it prints all of them, since the function is applied to them one by one, as it has to in this case.

现在是问题的关键.这里我设置了一个带有副作用的测试函数，它在测试第一个元素后决定改变主意:

Now to the crux of the matter. Here I set up a test function with a side effect, which decides to change its mind after it tests the very first element:

Module[{flag = False}, 
  ClearAll[test3]; 
  test3[x_] := 
     With[{fl = flag}, 
        If[! flag, flag = True]; 
        Print[x]; 
        fl
     ]
];

第一个组合(即 {-1},{2,3,4,5} 将被拒绝，因为函数首先给出 False.第二个然而，一个 ({-1,2},{3,4,5}) 将被接受.这正是我们观察到的:

The first combination (which is {-1},{2,3,4,5} will be rejected since the function gives False at first. The second one ({-1,2},{3,4,5}) will be accepted however. And this is exactly what we observe:

In[22]:= 
MatchQ[{-1,2,3,4,5},{x__?test3,y__}]
During evaluation of In[22]:= -1
During evaluation of In[22]:= -1
During evaluation of In[22]:= 2

Out[22]= True

一旦模式匹配器找到匹配项，打印就会停止.

The printing stopped as soon as the pattern-matcher found a match.

现在，从这里很明显，问题中提到的优化和其他一些答案通常是不可能的，因为模式匹配器无法控制测试函数中可能存在的可变状态.

Now, from here it must be obvious that the optimization mentioned in the question and some other answers is not generally possible, since pattern-matcher has no control over the mutable state possibly present in the testing functions.

在考虑模式匹配时，我们通常将其视为与评估分离的过程，这在很大程度上是正确的，因为模式匹配器是系统的内置组件，一旦模式和表达式评估，在很大程度上绕过了主评估循环.然而，有一些值得注意的例外，这使得模式匹配更加强大，但代价是让它与评估器纠缠在一起.其中包括Condition 和PatternTest 的使用，因为这两个是主要评估过程的入口点"，否则将与模式匹配过程隔离.一旦模式匹配器命中其中之一，它就会在要测试的条件上调用主评估器，然后一切皆有可能.这让我再次看到，当使用 PatternTest 和 Condition 的测试不存在时，模式匹配器是最有效的，并且模式是完全句法的 - 在 中在这种情况下，它可以优化.

When thinking about the pattern-matching, we usually view it as a process separate from evaluation, which is largely true, since the pattern-matcher is a built-in component of the system which, once patterns and expressions evaluate, takes over and largely bypasses the main evaluation loop. There are however notable exceptions, which make the pattern-matching more powerful at the price of getting it entangled with the evaluator. These include the uses of Condition and PatternTest, since these two are the "entry points" of the main evaluation process into the otherwise isolated from it pattern-matching process. Once the pattern-matcher hits one of these, it invokes the main evaluator on the condition to be tested, and anything is possible then. Which brings me once again to the observation that the pattern-matcher is most efficient when tests using PatternTest and Condition are absent, and the patterns are completely syntactic - in that case, it can optimize.

这篇关于PatternTest 没有优化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！