Junctions 如何评估?

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

How are Junctions evaluated?

问题

关于Junctions的概念最初由Damian Conway引入,旨在模拟量子叠加并表达量子计算算法。

尽管这可能很有趣,但叠加和崩溃的概念在编程上并没有意义,评估规则远非明确。

英文:

The idea of Junctions were originally introduced by Damian Conway in order to mimick Quantum superposition and express Quantum Computing algorithms.

As cute at this may be, the concepts of superposition and collapsing don't make sense in a programming context and the evaluations rules are far from being clear.

答案1

得分: 14

一个联接(junction)只是一个包装器内的一组值,该包装器可以是 anyallonenone,具体取决于用于创建联接的运算符。我们稍后将讨论这四种类型之间的区别;在大多数情况下,它们的行为完全相同。

当您将联接传递给任何函数、方法或运算符(除了明确声明接受 Junction 的函数、方法或运算符之外),调用将会“自动线程化”,结果将是一个联接。这实际上非常简单,一点也不像量子计算:
(1 & 2 & 3) * 2 等于 1 * 2 & 2 * 2 & 3 * 2 等于
2 & 4 & 6,而 f(any(1, 2, 3)) 等于 any(f(1), f(2), f(3))。联接中项目的顺序与集合一样,并且如果感觉需要,Raku 可以并行评估自动线程化的操作,因此可能会同时调用多次 f

当将联接强制转换为 Bool 时,无论是通过上下文还是通过像 so 这样的显式运算符,它都变成了一个单一的值。any 联接只有在其包含的任何值为真时才为 True,而 all 联接只有在其所有值为真时才为真(包括包含没有值的情况),none 联接只有在其所有值都不为真时才为真,而 one 联接只有在内部 恰好一个 值为真时才为真。

所以假设我们有:

my @words = <raku is fun>;
if all(@words).chars < 10 {
    say "nice short words";
}

这将打印出来,因为 all(@words).chars < 10 等同于
all('raku'.chars, 'is'.chars, 'fun'.chars) < 10,这是
all(4, 2, 3) < 10,这是
all(4 < 10, 2 < 10, 3 < 10),这是
all(True, True, True),而 so all(True, True, True)True

同样,如果 $num 是 3 的倍数或 5 的倍数但不是 15 的倍数,so $num %% one(3, 5) 将为真。

英文:

A junction is just a set of values inside of a wrapper which is any, all, one, or none depending on the operator used to create the junction. We'll talk about the differences between the four types later; for the most part they behave exactly the same.

When you pass a junction to any function, method, or operator except those explicitly declared to take a Junction, the call is "autothreaded" and the result will be a junction. This is actually very simple and not at all quantum:
(1 &amp; 2 &amp; 3) * 2 equals 1 * 2 &amp; 2 * 2 &amp; 3 * 2 equals
2 &amp; 4 &amp; 6, and f(any(1, 2, 3)) equals any(f(1), f(2), f(3)). The order of items in a junction, as with a set, is insignificant, and Raku can, if it feels like it, evaluate autothreaded operations in parallel, so there might be more than one call to f going on at once.

When a junction is coerced to Bool, either by context or by an explicit operator like so, it becomes a single value. An any junction will be True if any of the values it contains are true, an all junction is true only if all of its values are true (including the case where it contains no values), a none junction is true if none of its values are true, and a one if exactly one value inside is true.

So suppose we have

my @words = &lt;raku is fun&gt;;
if all(@words).chars &lt; 10 {
    say &quot;nice short words&quot;;
}

this will print, because all(@words).chars &lt; 10 is the same as
all(&#39;raku&#39;.chars, &#39;is&#39;.chars, &#39;fun&#39;.chars) &lt; 10, which is
all(4, 2, 3) &lt; 10, which is
all(4 &lt; 10, 2 &lt; 10, 3 &lt; 10), which is
all(True, True, True), and so all(True, True, True) is True.

Likewise so $num %% one(3, 5) will be true if $num is a multiple of 3, or a multiple of 5, but not a multiple of 15.

答案2

得分: 3

根据Hobbs的回答和评论,发现连接词的分配行为并不是全部的故事。如果是这样的话,以下表达式的评估将如何进行:

(1 | 2) + (3 &amp; 4)

1 + (3 &amp; 4)       ==&gt; all(4, 5)
2 + (3 &amp; 4)       ==&gt; all(5, 6)

(4 &amp; 5) | (5 &amp; 6) ==&gt; any(all(4, 5), all(5, 6))

但实际的评估产生了:

(1 | 2) + (3 &amp; 4) ==&gt; all(any(4, 5), any(5, 6))

连接词类型影响由多个连接词组成的表达式的评估。解决方案在这里找到:https://design.raku.org/S09.html#Junctions,我将引用它。

如果两个或多个参数是连接词,那么被选择为“自动线程”的参数是:

  • 最左边的allnone连接词(如果有的话),否则
  • 最左边的oneany连接词

这些测试按照这个顺序应用。

然后,每组调用的结果都会递归地自动线程,直到不再有连接词参数为止。也就是说:

   substr(&quot;camel&quot;, 0|1, 2&amp;3)
-&gt; all( substr(&quot;camel&quot;, 0|1, 2),      # 自动线程连词参数
        substr(&quot;camel&quot;, 0|1, 3)
      )
-&gt; all( any( substr(&quot;camel&quot;, 0, 2),   # 自动线程联结参数
             substr(&quot;camel&quot;, 1, 2),
           ),
        any( substr(&quot;camel&quot;, 0, 3),   # 自动线程联结参数
             substr(&quot;camel&quot;, 1, 3),
           )
      )
-&gt; all( any( &quot;ca&quot;,                    # 评估
             &quot;am&quot;,
           ),
        any( &quot;cam&quot;,
             &quot;ame&quot;,
           )
-&gt; (&quot;ca&quot;|&quot;am&quot;) &amp; (&quot;cam&quot;|&quot;ame&quot;)        # 重新组合联结的结果

按照这些规则,(1 | 2) + (3 &amp; 4) 的评估如下:

(1 | 2) + (3 &amp; 4)

((1 | 2) + 3) &amp; ((1 | 2) + 4)

(4 | 5) &amp; (5 | 6)

相同的规则还正确推导了以下表达式的评估:

any(1, 2) + all(10, 20)
==&gt;
all(any(11, 12), any(21, 22))

all(1, 2) + any(10, 20)
==&gt;
all(any(11, 21), any(12, 22))

one(1, 2, 3) + any(4, 5)
==&gt;
one(any(5, 6), any(6, 7), any(7, 8))

one(1, 2, 3) + one(4, 5)
==&gt;
one(one(5, 6), one(6, 7), one(7, 8))

one(1, 2, 3) + all(4, 5)
==&gt;
all(one(5, 6, 7), one(6, 7, 8))

one(1, 2, 3) + none(4, 5)
==&gt;
none(one(5, 6, 7), one(6, 7, 8))

这些基本表达式评估规则在https://docs.raku.org/type/Junction中完全没有提到,因此官方文档没有提供任何帮助。

附言:
对于raiph也要表示赞赏,他也找到了答案。

编辑:
阅读了https://design.raku.org/S09.html#Junctions的这一部分后,你可能会认为包含连接词的表达式会在编译时使用宏进行展开,但事实并非如此。一切都发生在运行时,但在下面的AUTOTHREAD方法中发生的事情看起来很像宏扩展过程。

连接词如何评估?

  • 常规值(任何类型的值,不是连接词的值)会被评估为它们自己

  • 连接词(有4种连接词类型:any、all、one、none)会被评估为它们自己

  • any()、all()、one()、none()(或它们的对应运算符infix:<|>, infix:<&>, infix:<^>. none()没有对应的运算符)会按照正常方式评估它们的参数,并构造并返回一个连接词值。参数的类型(Any或Junction)是无关紧要的。

(这里的类型实际上指的是类型/子类型)

  • 函数调用,其中所有参数都是Any类型,或者是Junction类型但具有相应的参数也是Junction类型(或Mu类型),被视为常规函数调用。

  • 至少有一个参数是Junction类型,且具有相应的参数是Any类型的函数调用,多重分派失败并回退到https://github.com/rakudo/rakudo/blob/main/src/core.c/Junction.pm6中的method AUTOTHREAD(&call, |args)

下面是在Perl中简化的(并且大部分是正确的)AUTOTHREAD的翻译。

调用infix:<+>(1 | 2, 3)的效果是

英文:

As a follow up on Hobbs answer and comments:

As it turns out, the distributivity behavior of the junctions is not the whole story. This is how the following expression would be evaluated if that were the case.

(1 | 2) + (3 &amp; 4)

1 + (3 &amp; 4)       ==&gt; all(4, 5)
2 + (3 &amp; 4)       ==&gt; all(5, 6)

(4 &amp; 5) | (5 &amp; 6) ==&gt; any(all(4, 5), all(5, 6))

but the actual evaluation produces:

(1 | 2) + (3 &amp; 4) ==&gt; all(any(4, 5), any(5, 6))

The junctive types affect the evaluation of an expression composed of more than one junctions.
The solution was found here: https://design.raku.org/S09.html#Junctions, which I'll just quote.

> If two or more arguments are junctive, then the argument that is chosen to be "autothreaded" is:
> * the left-most all or none junction (if any), or else
> * the left-most one or any junction
>
> with the tests applied in that order.
>
> Each of the resulting set of calls is then recursively autothreaded until no more junctive arguments remain. That is:

   substr(&quot;camel&quot;, 0|1, 2&amp;3)
-&gt; all( substr(&quot;camel&quot;, 0|1, 2),      # autothread the conjunctive arg
        substr(&quot;camel&quot;, 0|1, 3)
      )
-&gt; all( any( substr(&quot;camel&quot;, 0, 2),   # autothread the disjunctive arg
             substr(&quot;camel&quot;, 1, 2),
           ),
        any( substr(&quot;camel&quot;, 0, 3),   # autothread the disjunctive arg
             substr(&quot;camel&quot;, 1, 3),
           )
      )
-&gt; all( any( &quot;ca&quot;,                    # evaluate
             &quot;am&quot;,
           ),
        any( &quot;cam&quot;,
             &quot;ame&quot;,
           )
-&gt; (&quot;ca&quot;|&quot;am&quot;) &amp; (&quot;cam&quot;|&quot;ame&quot;)        # recombine results in junctions

Following these rules, (1 | 2) + (3 &amp; 4) is evaluated as follows:

(1 | 2) + (3 &amp; 4)

((1 | 2) + 3) &amp; ((1 | 2) + 4)

(4 | 5) &amp; (5 | 6)

The same rules also correctly derive the evaluation of the following expressions:

any(1, 2) + all(10, 20)
==&gt;
all(any(11, 12), any(21, 22))

all(1, 2) + any(10, 20)
==&gt;
all(any(11, 21), any(12, 22))


one(1, 2, 3) + any(4, 5)
==&gt;
one(any(5, 6), any(6, 7), any(7, 8))

one(1, 2, 3) + one(4, 5)
==&gt;
one(one(5, 6), one(6, 7), one(7, 8))

one(1, 2, 3) + all(4, 5)
==&gt;
all(one(5, 6, 7), one(6, 7, 8))

one(1, 2, 3) + none(4, 5)
==&gt;
none(one(5, 6, 7), one(6, 7, 8))

Those basic expression evaluation rules are completely missing from https://docs.raku.org/type/Junction, so the official documentation wasn't of any help.

PS:
Kudos to raiph for finding the answer too.

EDIT:

After reading this section https://design.raku.org/S09.html#Junctions, you would think that expressions containing junctions would be desugared at compile time with macros but that's not how it is done. Everything happens at run time but what happens in the AUTOTHREAD method below looks a lot like the macro expansion process.

How are junctions evaluated?

  • regular values (values of type Any, any value that isn't a junction) evaluate to themselves

  • junctions (there are 4 junctive types: any, all, one, none) evaluate to themselves

  • any(), all(), one(), none() (or their respective operators infix:<|>, infix:<&>, infix:<^>. none() does not have an associated operator) have their arguments evaluated normally and a junction value is constructed and returned. The type of the arguments (Any or Junction) is irrelevant.

(type really means type/subtype here)

  • function calls where all arguments are of the type Any, or of the type Junction but with a corresponding parameter also of type Junction (or Mu) are regular function calls

  • function calls with at least one argument of type Junction with a corresponding parameter of type Any have multiple dispatch failing and falling back to method AUTOTHREAD(&amp;call, |args) in https://github.com/rakudo/rakudo/blob/main/src/core.c/Junction.pm6.

Below is a simplified (and mostly correct) translation of AUTOTHREAD in Perl.

Calling infix:&lt;+&gt;(1 | 2, 3) have the effect that infix:&lt;+&gt;(1, 3) | infix:&lt;+&gt;(2, 3) is returned and that process is really similar to macro expansion, which is possible because of the indirection created by the multiple dispatch and the fallback to AUTOTHREAD. This is both fascinating and horrifying.

sub AUTOTHREAD {
    my ($call, $args) = @_;
    my $positionals = $args-&gt;{list};

    sub thread_junction {
        my $pos = shift;
        my $junction = $positionals-&gt;[$pos];
        my @storage = $junction-&gt;{eigenstates}-&gt;@*;
        my @result;

        for (my $i=0; $i &lt; @storage; $i++) {
            $positionals-&gt;[$pos] = $storage[$i];
            push @result, $call-&gt;($args);   # really multiple_dispatch($call, $args)
        }
        Junction-&gt;new(type =&gt; $junction-&gt;{type}, eigenstates =&gt; \@result);
    }

    for (my $i=0; $i &lt; $positionals-&gt;@*; $i++) {
        my $arg = $positionals-&gt;[$i];
        if ($arg isa Junction) {
            if ($arg-&gt;{type} eq &quot;all&quot; || $arg-&gt;{type} eq &quot;none&quot;) {
                return thread_junction($i);
            }
        }
    }

    for (my $i=0; $i &lt; $positionals-&gt;@*; $i++) {
        my $arg = $positionals-&gt;[$i];
        if ($arg isa Junction) {
            if ($arg-&gt;{type} eq &quot;any&quot; || $arg-&gt;{type} eq &quot;one&quot;) {
                return thread_junction($i);
            }
        }
    }

    my $named = $args-&gt;{hash};

    for my $key (keys $named-&gt;%*) {
        my $arg = $named-&gt;{$key};
        if ($arg isa Junction) {

            my $junction = $arg;
            my @storage = $junction-&gt;{eigenstates}-&gt;@*;
            my @result;

            for (my $i=0; $i &lt; @storage; $i++) {
                $named-&gt;{$key} = $storage[$i];
                push @result, $call-&gt;($args);   # really multiple_dispatch($call, $args)
            }
            return Junction-&gt;new(type =&gt; $junction-&gt;{type}, eigenstates =&gt; \@result);
        }
    }

    $call-&gt;($args);   # really multiple_dispatch($call, $args)
}

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

发表评论

匿名网友

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

确定